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

800x600

1 معرفي

روش‌هاي جستجوي مرسوم اغلب قادر نيستند جواب بهينه توابع غيرخطي را بيابند. در چنين زماني، روش جستجوي تصادفي ممكن است مفيد باشد. به هر حال روش‌هاي جستجوي غير مستقيم در مقياس بزرگ ناكارامداند. الگوريتم ژنتيك روش جستجوي مستقيمي است كه توسط هالند(Holland 1975) ارائه شد، كه قادر به يافتن بهينه سراسري در يك فضاي جستجو پيچيده است. الگوريتم ژنتيك از روي تكامل تدريجي طبيعت مدل شده است كه در آن عملگرهايي به كار گرفته شده كه از فرايند‌هاي تكامل تدريجي طبيعت نشأت گرفته است. اين عملگرها كه عملگرهاي ژنتيك نام دارند. در طول ايجاد چندين نسل ، افراد را در جمعيت براي بهبود نسل‌شان دست‌كاري مي‌كنند. همانطوري كه در بخص بعدي توضيح داده مي‌شود افراد در جمعيت شبيه كروموزومها هستند و معممولاً بصورت رشته‌اي از اعداد دودويي نشان داده مي‌شود.

تكامل تدريجي جمعيتِ كروموزوم‌ها از «قاعده الگو»تبعيت مي‌كند(Holland 1975). يك الگو با توجه به شباهت بيت‌ها در مكان‌هاي معلوم كروموزوم‌ها، نشان دهنده مجموعه‌اي از كروموزوم‌ها يعني زيرمجموعه‌اي از جمعيت، است. براي مثال الگوي 1*0* مجموعه‌اي از كروموزوم‌ها را تشريح مي‌كند كه اولين و سومين بيت‌‌ آن 1 و صفر است. در اينجا نماد * يعني كه هر مقدار صفر يا يك را مي‌تواند بپذيرد. هر الگو با دو پارامتر مشخص مي‌شود: طول بين اولين و آخرين بيت، و تعداد بيت.

الگوريتم ژنتيك نيازي به دانستن اينكه مسأله‌اي كه بايد بهينه شود ندارد و بطور مستقيم با پارامترهاي مسأله كاري ندارد. الگوريتم با كدها كه نشان دهنده پارامترهاي مسأله‌اندكار مي‌كند. الگوريتم ژنتيك داراي چهار عمل اصلي است.

2 نمايش

دو روش متعارف براي مسائل بهينه‌يابي عددي موجود است(michalewicz 1992; Davis 1991). روشي عالي نشان دادن بصورت رشته دودويي است كه پارامتر جمعيت بصورت صفر يا يك نمايش داده مي‌شود. ديگر روش نمايش زمزگذاري يكنواخت و رمزگذاري با مقياس خاكستري است. اين روش برداري از اعداد صحيح يا اعشاري است كه هر عدد اعشاري يا صحيح شماره پارامتر واحدي است.

3 ايجاد جمعيت

در شروع بهينه‌يابي، الگوريتم نياز به جواب اوليه دارد. دو روش ايجاد جواب اوليه وجود دارد. استفاده از اعداد بصورت تصادفي و اين زماني است كه اطلاعات ضعيفي وجود دارد. روش دوم دانشي كه درمورد مسأله بهينه‌يابي دارد جوابي انتخاب مي‌كند و اين كار باعث مي‌شود واگرايي مسأله از بهينه مطلق كم شود.

4 عملگر‌هاي ژنتيك

در شكل(2-3) فلوچارتي از يك الگوريتم ژنتيك ساده به نمايش درآمده است. سه عملگر متعارف وجود دارد. انتخاب[1]، تقاطع[2]، جهش[3]

انتخاب. هدف رويه انتخاب اين است كه چند كپي از كروموزوم‌ها جمعيتي كه داراي مقدار تابع برازندگي بيشتري هستند مجدد توليد شود. اين رويه تاثير مهمي دارد روي حركت جستجو به سمت منطقه‌اي كه يافتن جواب‌هاي خوب در زمان كمتر محتمل‌تر باشد. با اين وجود گوناگوني جمعيت بايد براي جلوگيري از واگرايي و رسيدن به جواب بهينه مطلق باقي بماند. در الگوريتم ژنتيك دو رويه انتخاب مهم‌تر وجود دارد: انتخاب به نسبت[4] و انتخاب بر پايه رتبه(Whitely 1989).

انتخاب به نسبت كه معمولاض «چرخه رولت» ناميده مي‌شود مكانيزمي مانند چرخه رولت دارد. مقادير برازندگي كروموزوم‌ها نشان دهنده پهناي شكاف روي چرخ است. بعد از گرداندن تصادفي چرخ براي انتخاب كروموزوم‌ها براي انتخاب نسل بعدي، كروموزوم‌هاي كه در چرخ شكاف پهن‌تر دارند نشان دهنده مقدار برازندگي بيشتر و احتمال انتخاب بيشتر هستند.

يكي از راههاي جلوگيري از اينكه سريع به واگرايي رسيد اين است كه حوزه آموزش تخصيص داده شده به هر كروموزوم‌ تنها را محدود كنيم، بنابراين هر كروموزوم‌ به تنهايي زادو ولد زيادي نمي‌كند. رويه توليد بر پايه رتبه بر اين ايده استوار است. با توجه به اين رويه، هر كروموزوم‌ يك تعداد مورد انتظار زاد و ولد مي‌كند كه بر اساس رتبه‌اش در مقدار برازندگي‌اش است(Baker 1985).

تقاطع. اين عمليات يك از آنهايي است كه باعث شده تا الگوريتم ژتيك از ديگر الگوريتم‌ها متفاوت باشد. و آن اين است كه دو كروموزوم‌ جديد(فرزندان) از دو كروموزوم‌ حاضر(والدين) جمعيت بر اساس عملگر تقاطع ايجاد مي‌شوند. روش‌هاي زيادي هستند: تقاطع يك نقطه‌اي، دونقطه‌اي، تقاطع چرخه و تقاطع يكنواخت.

براي مثال در تقاطع يك نقطه‌اي، نقطه‌اي به صورت تصادفي به عنوان نقطه برش در طول والدين انتخاب مي‌شود و جاي آن دو بخش با هم تقسيم مي‌شود.

جهش. در اين رويه، تمام كروموزوم‌ها جمعيت بيت به بيت چك مي‌شوند و مقادير بيت بصورت تصادفي مطابق نرخ مشخصي معكوس مي‌شوند. اين عمل باعث مي‌شود كه الگوريتم ساير فضاي جستجو را نيز بپيمايد زيرا بر اين اساس به يكباره با تبديل كروموزوم‌ به كروموزوم‌ جديدي فضاي جستجو عوض مي‌شود.

واژگون سازي[5].در اين عملگر يكي از كروموزوم‌ها در هر زمان انتخاب مي‌شود و دو نقطه به صورت تصادفي انتخاب مي‌شود و جاي آن دو با هم عوض مي‌شود. اين عمل بيشتر در مسائلي از قبيل مسأله انخاب مكان، استقرار و فروشنده دوره‌گرد به كار مي‌رود.

[1] selection

[2] crossover

[3] mutation

[4] Proportional

[5] inversion

Normal 0 false false false EN-US X-NONE AR-SA /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Calibri","sans-serif"; mso-bidi-font-family:Arial;}

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

1 معرفي

2 نمايش

3 ايجاد جمعيت

4 عملگر‌هاي ژنتيك

مطالب مشابه :

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

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

الگوریتم ژنتیک

مسئله کوله پشتی چیست؟

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

الگوريتم مورچگان چیست؟ توضیح با یک مثال ساده

ژنتیک و اصلاح نباتات

الگوریتم ژنتیک

الگوريتم ژنتيك و فرايند بهينه سازي ...