الگوریتم ژنتیک چیست؟

3-  تشریح الگوریتم ژنتیک :

3-1- مفهوم الگوریتم ژنتیک :

الگوریتم ژنتیک را می­توان به طور ساده، یک روش جستجوگر نامید که بر پایه­ی مشاهده­ی خصوصیات فرزندان نسل­های متوالی، و انتخاب فرزندان بر اساس اصل (اثبات نشده­ی) بقای بهترین، پایه­ریزی شده است. الگوریتم ژنتیک بر روی فرزندان یک نسل، (مجموعه جواب­های مسئله در یک مرحله)، از قوانین موجود در علم ژنتیک تقلید کرده و با بکار بردن آنها، به تولید فرزندان با خصوصیات بهتر، (جواب­های نزدیک­تر به هدف مسئله) می­پردازد و در هر نسل به کمک فرآیندی انتخابی که بر اساس ارزش جواب­ها می­باشد و تولید مثل فرزندان (جواب­های) جدید، تقریب بهتری از جواب نهایی را بدست می­آورد. این فرآیند باعث می­شود که نسل­های جدید با شرایط مسئله سازگارتر باشند، این رقابت میان فرزندان (جوابها) و پیروز شدن فرزندِ شایسته­تر (جواب بهتر) و انتخاب شدنشان توسط الگوریتم ژنتیک برای تولید مثل بعدی و کنار رفتن فرزندان یا همان ژ­ن­های مغلوب که در حقیقت جواب­های دور از هدف مسئله می­باشند روش کارآمدی برای حل مسائل پیچیده به خصوص مسائل پیچیده­ی بهینه سازی که باید بهترین جواب را از میان جواب­های قابل قبول انتخاب کرد می­باشد.

3-2- معرفی اصطلاحاتی که در ژنتیک الگوریتم به کار می­رود :

3-2-1- افراد[1] و کروموزم­ها[2]:

نقاطی که می­توانند ورودی تابع شایستگی باشند، افراد  نامیده می­شوند، این افراد که تقریب­هایی از جواب نهایی هستند زمانی که این مقادیر، به صورت رشته­هایی از ارقام یا حروف کدگذاری می­شوند     به آن ها کروموزم گفته می­شود به هر یک از مؤلفه­های برداری یا بیت­های تشکیل دهنده­ی یک کروموزم که ویژگی­های آن کروموزم را مشخص می­کند ژن[3] گفته می­شود . متداول­ترین روش کدگذاری افراد، سیستم کدگذاری  دودویی[4] با اعداد صفر و یک است که از کنار هم قرار گرفتن این کدها یک کروموزم ایجاد می­گردد.

همچنین در هر مسئله­ی الگوریتم ژنتیک، تابع برازندگی از چند متغیر مستقل تشکیل می­شود که به هر یک از این متغیر­ها یک فنوتایپ[5] گویند. بنابر این کروموزمِ معرفِ هرفرد، برای اینکه در یک تابع برازندگی صدق کند باید از فنوتایپ­ها تشکیل شود در نتیجه هر کروموزم از چند فنوتایپ تشکیل شده است.

3-2-2- جمعیت[6] و نسل[7]:

جمعیت، به مجموعه­ای از افراد گویند که در هر مرحله به صورت یک آرایه نوشته می­شوند. به طور مثال اگر تابع شامل سه متغیر و تعداد جمعیت 100 نفر باشد، آن را به صورت ماتریسی در 100 ردیف و با 3 ستون نمایش می­دهند.

الگوریتم ژنتیک در هر مرحله بر روی این جمعیت کار خواهد کرد و به طور معمول برای هر متغیر جمعیت شامل 30 تا 100 فرد است.

3-2-3-  جمعیت اولیه[8] :

بعد از تصمیم­گیری در مورد نحوه­ی کدگذاریِ کروموزم­ها، جمعیت اولیه باید ایجاد گردد. این مرحله معمولاً با  انتخاب تصادفیِ مقادیر در محدوده­ی مجاز صورت می­گیرد. به محدوده­ی مجاز فضای جستجو[9] گفته می­شود که فضای شامل مجموعه جواب امکان­پذیر برای حل مسئله را شامل می­شود؛ هر نقطه از این محدوده می­تواند یک جواب برای حل مسئله باشد ولی واضح است که لزوماً بهترین جواب برای حل مسئله نخواهند بود.

جمعیت اولیه فوق­العاده مهم است، اگر ما بدانیم نقطه­ بهینه، تقریباً کجا واقع شده است درنتیجه گستره­ی جمعیت اولیه را بر همین اساس تنظیم می­کنیم امّا در صورت عدم آگاهی از مکان حدودیِ نقطه­ی بهینه کار دشوار می­شود چون نسل اولیه خوبی تعیین نشده و به احتمال فراوان زمان  رسیدن به جواب مطلوب را کاهش داده و احتمال یافتن کمینه­ی مطلق مسئله کاهش می­دهد.

3-2-4- والدین[10] و فرزندان[11] :

الگوریتم ژنتیک بیشتر، افرادی را که مقادیر بهتری دارند به عنوان والدین انتخاب می کند و با کار بر روی آنها فرزندانی برای نسل بعد به وجود می آورد. (مقادیر تابع به ازای هر فرد را نمره­ی[12] آن فرد می­نامند.)

3-2-5- تابع هدف[13] :

تابع هدف، هدف و خواسته­ی ما از طرح مسأله است. تابع هدف، شاخصی از نحوه­ی عملکرد افراد در فضای مسئله است. برای مثال اگر هدف ما از حل مسئله یافتن جواب کمینه باشد، مناسب­ترین فرد آن است که تابع هدفش کمترین مقدار را داشته باشد.

3-2-6- تابع برازندگی[14] :

این تابع برای تبدیل مقادیر تابع هدف به مقیاسی برای سازگاری و کارایی نسبی افراد، به کار می­رود و از تابع هدف مشتق می­شود. اصولاً ژنتیک الگوریتم برای حل مسائل بیشینه مناسب است، بنابر این برای حل مسائل کمینه سازی باید با  استفاده از یک سری تبدیل­ها آن را به مقدار بیشینه تبدیل کنیم.

اگر تابع هدف را با f(x) و تابع برازش را با F(x)  نشان دهیم آنگاه از تبدیل های زیر می­توانیم برای بدست آوردن تابع برازش از تابع هدف استفاده کنیم.

برای مسائل بیشینه سازی :  (3)                                                                F(x) = f(x)                     برای مسائل کمینه سازی :  (4)                      if  f(x) ¹ 0                      F(x) = 1/f(x)            F(x) = 1/(1+f(x))               if  f(x) = 0                     (5)                   

3-2-6- تنوع جمعیتی[15] :

فاصله­ی متوسط بین افراد در یک جمعیت را  تنوع جمعیت گویند. یک جمعیت در صورتی تنوع بالایی دارد که فاصله­ی بین افراد آن زیاد باشد ودر غیر این صورت تنوع کم است.

3-2-7- انتخاب[16] :

هرگاه فردی در یک نسل انتخاب شود، به این معنی است که  این فرد شایستگی تولید مثل و یا حضور مستقیم در مرحله بعد را خواهد داشت. مرحله­ی اول انتخاب؛ مربوط به تعیین برازندگی افراد باتوجه به نمره­ی آن­ها می باشد که تعیین کننده­ی احتمال شرکت آنها در مرحله­ی تکثیر است و مرحله­ی دوم انتخاب احتمالی افراد است که بر اساس برازش نسبی صورت می­گیرد.

انتخاب، شیوه­ها و تکنیک­های متنوعی دارد که بسته به نوع مسئله و شرایط حاکم بر آن از این از هر یک از این تکنیک­ها و روش­ها استفاده می­شود.

3-2-7-1- روش انتخاب چرخ گردان[17] :

مهم­ترین و معمول­ترین روش انتخاب، روش چرخ گردان است. هر فرد یک نمره­ی برازندگی را نسبت به عملکردش در تابع برازندگی بدست می­آورد، در این روش باید تمام این نمرات را با هم جمع زد و در یک فاصله­ی از یک تا مجموع نمرات برازش­ها در نظر گرفت، حال با تقسیم نمره­ی برازش هر فرد بر حاصل جمع نمراتِ برازشِ افراد، احتمال انتخاب هر فرد  در طی فرآیند انتخاب بدست می­آید و طبیعتاً حاصل جمع این احتمال­ها برابر یک خواهد بود.

برای انتخاب هر فرد، عددی تصادفی بین صفر تا یک در نظر گرفته می­شود و فردی که این نقطه در محدوده­ی مربوط به آن قرار می­گیرد انتخاب می­شود. برای تعیین محدوده­ی هر فرد باید به شکل زیر عمل کرد:

اگر تعداد افراد را n در نظر گیرم، محدوده­ی هر فرد با استفاده از روش احتمال تجمیعی[18] مشخص می شود. یعنی برای پیدا کردن محدوده­ی مربوط به i امین فرد، ابتدا مجموع احتمالات مربوط به (i-1) نفر قبل را بدست می­آوریم که مثلاً می شود عدد A، حال اگر احتمال فرد i ام را که مثلاً عددی برابر با B می­باشد با A جمع کنیم عدد C بدست می­آید. محدوده­ی مربوط به فرد i ام ازA آغاز می­شود و در C به پایان می­رسد.

 در این روش می­توان برای جلوگیری از تولید مثل زیاد یک والد و در نتیجه یک نواختی جواب­ها اندازه­ی احتمال هر والد را بعد از انتخاب شدنش کاهش داد.

البته در برخی مسائل با توجه به نوع مسئله و ویژگی­های آن، روش انتخاب میزِ گردان چندان مناسب نیست، به خصوص در مواردی که نمرات برازندگی افراد خیلی با هم تفاوت داشته باشد که  نتیجه­ی این امرکندی وهمگرایی ناگهانی جستجو به خاطر کوچکی سریع فضای جستجو می­باشد.

در این موارد می­توان از سایر روش­های انتخاب مانند روش رقابتی[19]، روش رتبه­بندی[20] و روش­های و متد­های انتخابی ِدیگر استفاده کرد.

3-2-8- تولید نسل جدید[21] یا تولید مثل[22] :

در این بخش به مهم­ترین عملگرهای الگوریتم ژنتیک که برای تولید نسل بعدی از روی نسل قبل

به کار می­رود اشاره می­شود.

3-2-8-1- عملگر نخبه­[23]گرا :

بر طبق این عملگر افرادی که در نسل فعال از بهترین نمره­ی برازندگی برخوردارند، به طور خودکار به نسل بعد منتقل می­شوند. این عملگر باعث افزایش کارایی الگوریتم ژنتیک می­شود، زیرا مانع از گم شدن جواب­هایِ خوبِ بدست آمده می­شود.

معمولاً بهترین افرادِ نسل فعال، یعنی والدین را جایگزینِ بدترین فرزندان تولید شده می­نمایند. البته باید توجه داشت در مواردی که تعداد زیادی جواب نزدیک به هم وجود داشته باشد، این روش از ثبات لازم برخوردار نیست ولی در مواردی که مسئله یک بهینه­ی کلی داشته باشد این عملگر مؤثر و مناسب به نظر می­رسد.

3-2-8-2- عملگر تقاطع[24] :

وقتی که افراد یک نسل بر اساس برازندگی خود در مرحله­ی انتخاب، گزینش شوند این عملگر با ترکیب ژن­های یک جفت والدِ برگزیده، کروموزمِ معرف فرد جدید را به وجود می­آورد. همانند کروموزم­ها در طبیعت، فرزندان حاصل از این عملگر هر یک بخشی از اطلاعات روی کروموزم­های والد را دارند

می­توان گفت عملگر اصلیِ ایجاد نسل جدید در مرحله­ی تکثیر، تقاطع یا همان پیوند است.

این عملگر یک عملگرِ ترکیبی است که شامل سه مرحله می­شود. در مرحله نخست یک جفت از کروموزم­های برگزیده را به طور تصادفی انتخاب می­کند؛ در مرحله­ی دوم محلی را برای ادغام به طور تصادفی در طول رشته­ی کروموزم انتخاب می­کند و سرانجام در مرحله­ی سوم، مقدار دو رشته را با توجه به محل ادغام که مشخص کرده­­ایم جابجا می­کند.

روش های مختلفی برای ادغام و تقاطع وجود دارد که بسته به نظر کاربر و شرایط مسئله باید از آنها استفاده کرد. مهمترین این روشها عبارتند از : روش تقاطع تک نقطه­ای[25]، روش تقاطع دو نقطه­ای[26]، روش تقاطع چند نقطه­ای[27]، روش تقاطع یک نواخت[28]، روش تقاطع ماتریسی[29] و...

در اینجا لازم است به یک مفهوم مهم دیگر یعنی نرخ تقاطع اشاره کنیم. با تعیین این نرخ که عددی بین صفر تا یک است ما تعیین می­کنیم که چند درصد از جمعیت فعالِ حاضر باید در عمل تقاطع شرکت کنند.

دقت شود اگر این مقدار خیلی زیاد باشد، باعث می­شود تا فرصت تطابق در کروموزم از دست برود وهمچنین اگر این مقدار خیلی کم باشد تعداد فرزندان تولید شده کافی نخواهد بود. معمولاً کمترین مقداری را که برای نرخ تقاطع در نظر می­گیرند نباید از 5/0 کمتر باشد. بر طبق نتایج تجربی بهترین نرخ تقاطع باید بین 80 تا 95 درصد باشد

3-2-8-3- عملگر جهش[30] :

در این عملگر با تغییرات تصادفی بر روی ژن یا ژن­هایِ کروموزم یک والد، کروموزم­هایِ معرّف فرد جدید به وجود می­آیند. در جهش، کروموزمِ هر فرد به تنهایی و بدون نیاز به ادغام با کروموزم فرد دیگر بر اساس قوانین احتمال می­تواند تغییر کند.

جهش معمولاً به عنوان یک عملگر اصلی در الگوریتم ژنتیک شناخته می­شود که مسئول تولید مجدد ژن­های گم­شده و جلوگیری از کوچک شدن فضای جستجوی الگوریتم ژنتیک از طریق فراهم آوردن افراد تصادفی در همسایگی جمعیت می­باشد.به عبارت دیگر به کمک این عملگر می­توان امید داشت که کروموزم­های خوبی که در مراحل انتخاب یا تکثیر حذف شده­اند، دوباره احیا شوند این عملگر همچنین تضمین می­کند که بدون توجه به پراکندگی اولیه، احتمال جستجوی هر نقطه از فضای مسأله هیچ­گاه صفر نشود. این عملگر منجر به تولید افرادی می­شود که قبلاً هرگز وجود نداشته­اند و ممکن است منجر به یافتن راه حل بهتری برای مسئله بشوند؛ همچنین این عملگر در جلوگیری از به دام افتادنِ الگوریتمِ جستجو در کمینه­های محلی مفید است.

معمولاً تصور می­شود که عملگر تقاطع اصلی­ترین عملگری است که منجر به انجام یک جستجوی کامل در فضای جستجو می­شود. تکامل ساده که شامل عملیات انتخاب و جهش می­شود، حتی بدون عملیات تقاطع دارای قدرت بالایی برای جستجو می­باشد. در واقع می­توان گفت الگوریتم ژنتیکی که تنها حاوی عملگر جهش باشد از الگوریتم ژنتیکی که تنها از عملگر تقاطع بهره می­برد بهتر عمل می­کند زیرا با همگرایی جمعیت، جهش تأثیر بیشتری از تقاطع خواهد داشت. بدون جهش، تقاطع تنها منجر به همگرایی زودرس خواهد شد. در نتیجه می­توان گفت که جهش با وجود احتمال وقوع کم (معمولاً بین001/0 تا 01/0) تأثیر بسیار زیادی درعملکرد الگوریتم  ژنتیک دارد.

در نمایش دودوییِ کروموزم افراد، جهش به معنای تغییرمقدار یکی از ژن­های کروموزم­ از صفر به یک و یا بلعکس می­باشد. عملگر برای این کار یک احتمال کوچک نظیر Pm  را در نظر می­گیرد که به آن اصطلاحاً نرخِ جهش[31] گفته می­شود؛ همانطور که اشاره شد این احتمال معمولاً عددی کوچک

بین001/0 تا 01/0 است، سپس یک عدد تصادفی بین صفر تا یک در تولید می­شود، اگر این عدد کوچکتر از Pm بود مقدار بیت یا همان ژن کروموزم تغییر می­کند و در غیر این صورت مقدار بیت تغییری نخواهد کرد. بیت­های یک رشته به صورت مستقل جهش می­یابند، به این ترتیب که جهش یک بیت بر روی احتمال جهش سایر بیت­ها تأثیری ندارد.

البته جهش علاوه بر مزایایی که دارد دارای اشکالاتی نیز می­باشد، از جمله اینکه جهش، احتمال تمایل به سمت افراد با برازندگی کمتر را افزایش می­دهد، در نتیجه می­تواند زمان همگرایی را به تأخیر بیاندازد. به همین علت پیشنهاد می­شود که این عملگر پارامتریزه شود، بدین صورت که با افزایش همگرایی جمعیت، نرخ جهش کاهش یابد.

توجه داشته باشید که غالباً عملگر جهش برروی افرادی که برای عمل تقاطع در نظر گرفته می­شوند عمل نمی­کند.

سه عملگر نخبه­گرا، تقاطع و جهش، مهمترین عملگرها در تولید نسل جدید می­باشند که به صورت شماتیک در شکل ----- نشان داده شده­اند

به جز این سه عملگر، الگوریتم ژنتیک از عملگرهای دیگری نیز برای تولید مثل استفاده می­کند که با توجه به شرایط حاکم بر مسئله و نوع آن به کار می­روند. برخی از این عملگر­ها عبارتند از: عملگر مهاجرت[32]، عملگر حذف[33]، عملگر معکوس کردن[34]، عملگر جداسازی[35] و...

3-2-9-  دستور خاتمه­ی الگوریتم :

از آنجا که الگوریتم ژنتیک یک روش جستجوی تصادفی است، ارائه­ی فرمولی خاص برای پایان آن مشکل است. ممکن است برازش جمعیت برای تعدادی از نسل­ها ثابت باقی مانده و باعث ایجاد این تصور شود که به جواب نهایی رسیده­ایم. یکی از شیوه­های معمول برای پایان­دادن به الگوریتم، متوقف کردن آن بعد از تولید تعداد مشخصی نسل است. از آنجا که در بعضی عملگرها نیاز است که تعداد کل نسل­ها را بدانیم، این شیوه مناسب به نظر می­رسد. بعد از اتمام تکرار الگوریتم تا تعداد نسلی که به عنوان ورودی به الگوریتم داده­ایم، کیفیت جواب­های نهایی بررسی می­شود که در صورت ارضا نشدنِ جواب­های مدنظر، الگوریتم تا تعداد مشخصِ دیگری ادامه پیدا کرده و یا از ابتدا و با چینش جمعیت اولیه­ی متفاوتی و احیاناً برخی تنظیمات جدید، اجرا می­شود.

3-2-11- بعضی از مهم­ترین مزایا و محاسن الگوریتم ژنتیک :

1- الگوریتم ژنتیک همزمان با یک مجموعه از نقاط جستجو را شروع می­کند، نه با یک نقطه­ی تنها.

2- الگوریتم ژنتیک به مشتق­گیری و یا هرگونه اطلاعات کمکی نیاز ندارد وتنها تابع هدف و شیوه­ی تعیین برازش از اطلاعات خام، روند جستجو را مشخص می­کند.

3- الگوریتم ژنتیک به سرعت می­تواند یک مجموعه­ی بزرگ از راه حل­ها را پویش نماید، همچنین راه حل­های نامناسب تأثیر منفی­ای بر روی راه ­حل نهایی نداشته و به آسانی حذف می­شوند.

4- در این روش هیچ نیازی به خطی سازی مسئله وجود ندارد.

5- سایر الگوریتم­های بهینه سازی یک نقص بزرگ نسبت به الگوریتم ژنتیک دارند. زیرا این الگوریتم­ها نیاز به یک حدس اولیه در ارتباط با راه حل می­باشند که این حدس اولیه تأثیر زیادی بر روی نتیجه­ی نهایی دارد. بر خلاف این الگوریتم­ها الگوریتم ژنتیک تنها نیاز به یک محدوده­ی جستجو می­باشد که این محدوده با توجه به دانش اولیه در مورد خصوصیات فیزیکیِ سیستم قابل طرح است. الگوریتم ژنتیک  به صورت مؤثر کل فضای راه حل­ها را جستجو می­کند. این نوع جستجوی الگوریتم ژنتیک را بر خلاف سایر روش­ها از افتادن در تله­ی نقاط کمینه­ی محلی دور نگه می­دارد_.

6- الگوریتم ژنتیک نیازی ندارد که تابع هدف خوش رفتار باشد.

7- الگوریتم ژنتیک یک مجموعه از جواب­های بالقوه را ارائه می­دهد و انتخاب جواب نهایی بر عهده­ی کاربر است. در مواردی که مسئله جواب واحد ندارد، مانند بهینه سازی چند هدفه، الگوریتم ژنتیک برای مشخص­کردن همزمان جواب­ها مفید خواهد بود.

8- در مسائل گسسته یا پیوسته با کمینه­های محلی بسیار زیاد به دنبال کمینه­ی کلی می­گردد.(حال آنکه بتوان به این کمینه­ مطلق رسید یا نه به تنظیمات ما برای حل آن مسئله بستگی دارد.)

9- الگوریتم ژنتیک از قوانین احتمال گذرا استفاده می­کند و نه از نوع قطعی آن بر خلاف دیگر روش­های بهینه سازی.

تهیه و تنظیم از علی مصباحی دانشجوی مهندسی مکانیک جامدات دانشگاه بو علی سینای همدان

---

[1] - Individuals

[2] - Chromosomes

[3] - Gene

[4] - Binary

[5] - Phenotypes

[6] - Populations

[7] - Generations

[8] - Initial Population

[9] - Search space

[10] - Parents

[11] - Children

[12] - score

[13] - Objective function

[14] - Fitness function

[15] - Diversity

[16] - Selection

[17] - Roulette wheel

[18] - Expected count

[19] - Tournament

[20] - Rank

[21] - Creating the next Generation

[22] - Reproduction

[23] - Elite

[24] - Crossover

[25] - Single-Sight Crossover

[26] - Tow-point Crossover

[27] - Multi point Crossover

[28] - Uniform Crossover

[29] - Matrix Crossover

[30] - Mutation

[31] - Mutation Rate

[32] - Migration

[33] - Deletion

[34] - Inversion

[35] - Segregation