آشنایی الگوریتم های ژنتیک

صفحه 1:
آشنایی الگوریتم های ژنتیک سی!ظ) نسم در طبیعت. گونه های زنده. جهت ادامه بقاء مجبورند خود را با شرایط محيطى وفق دهند. اين کار تحت فرآیندی بنام تكامل. صورت مي ‎ops‏ 

صفحه 2:
تقسیم بندی کلی روشهای حل مسایل بهینه سازی روشهاى دقيق ‎HExact)‏ روشهایی مانند (سیمپلکس, دوگان» شبكه. شاخه و حد. برنامه ریزی پویاء لاگرانژین و...) که دستیابی به حل بهينه را تضمین می کنند. روشهای غیردقیق (۳۵01 40: روشهایی که در صدد دستیابی به حل های نزدیک به بهینه می باشند ولی دستیابی به حل بهینه را تضمین نمی کنند. رویکردهای ابتکاری مانند ۳1110671010 برای حل مسأله تخصيص يا 10125012 براى حل مسأله زمانبندی دو ماشین و یا روشهاى فوق ابتكارى بركرفته از مكانيزم هاى طبيعى متعلق به اين دسته مى باشند. سود 

صفحه 3:
ضعی بهینه سراسری و مو F(x) nae 6 (xLocal ‏ره‎ 

صفحه 4:
- تعریف همسایگی ‎Bile % :tNeighborhood)‏ از جواب شدنی 7 مانند (6,0) ۲ به مجموعه ای از جواب های شدنی گفته می شود که با اعمال عملگر 8 بروی « قابل دستیابی باشند. عملگر ۵ می تواند به معنی حذف. اضافه یا تغییر عناصر موجود در : باشد. به عملگر ۵ اصطلاحاً حرکت (۷۲0۷6) نیز گفته می شود. تعريف 4.4 590( ‎sLocal Optimum)‏ هرگاه یک همسایگی مانند (0,8) یافت شود بگونه ای که حل < از هر حل موجود در آن همسایگی بهتر باشد؛ به اصطلاحاً بهینه موضعی گفته می شود. سود 

صفحه 5:
T =ae” = ay ar n Non -Deterministic) ais. NP ole: NP & > ‏به معنای چندجمله ای نامعین بوده و در بحث پیچیدگی‎ “Polynomial ‏محاسبات مطرح می گردد. عبارت فوق به مسایلی اطلاق می گردد که زمان‎ ‏حل آنها توسط یک الگوریتم دقیق برحسب ابعاد مسأله از نوع یک سری‎ 19۳. ‏چندجمله ای نامعین مانند سری نمایی باشد. مسایلی همانند‎ ‏باشند.‎ ge NP plc +5> ..g knapsack. Job Shop Scheduling 

صفحه 6:
هر قاری روش ابتکاری - تعریف : یک روش ابتکاری عبارت است از تکنیکی که حل های نزدیک به بهینه را با یک هزینه محاسباتی قابل قبول جستجو می کند. ولی تضمینی برای رسیدن به حل بهینه نمی دهد. توجه به این نکته حائز اهمیت می باشد که در اکثر مدلسازی ‎le‏ نمی توان کلیه پارامترهای موثر بر شرایط مسأله را وارد مدل نمود. رک تضمینی وجود ندارد که بهترین حل بدست آمده توسط مدل همان حل مطلوب برای شرایط واقعی باشد. حال این سئوال مطرح می باشد که یک ق از یک مدل تقریبی بهتر می باشد یا یک حل تقریبی از یک یق؟ در پاسخ به این سئوال رویکردهای فراابتکاری این امکان را مهیا می سازند که بتوانیم یک حل تقریباً خوب را از یک مدل کاملا دقیق بدست آوریم چراکه افزایش پیچیدگی مسأله تأثیر چندانی در عملکرد آنها نخواهد داشت. سود 

صفحه 7:
روشهای ابتکاری بر مبنای مکانیزم های طبیعی شبکه های عصبی مصنوعی ‎Artificial Neural)‏ ‎(Network‏ 4Genetic Algorithm) S235 cl ‏الگور بتم‎ (Tabu Search) € 9:00 ‏جستجوی‎ ‎(Simulated Annealing) (27) Qu ‏سرد‎ ‎(Ant Colony) ¢;\R> )90 4x0l> سود 

صفحه 8:
مان مبانی الگوریتم ژنتیک - ارگانیسم های طبیعی جهت ادامه بقای خود ناچار به تطبیق هرچه بیشتر با محیط اطراف خود می باشند. - ارگانیسم هایی که نتوانند خود را با محیط و شرایط زیست محیطی که در آن حضور دارند. تطبیق دهند. محکوم به فنا می باشند. - خصوصیات هر ارگانیسم طبیعی در یک رشته بنام کروموزوم کد شده است. - کروموزوم ها خود متشکل از تعدادی اجزاء بنام ژن می باشند بطوریکه هر ژن با توجه به مقدارخود» مبین خصوصیات ار گانیسم مانند اندازه قد؛ وزن» رنگ موء رنگ پوست. رنگ چشم. نوع رفتار و... می باشد. به مقادیری که هر ژن می تواند اختیار کند 5 و به موقعیت مکانی ژن در کروموزوم ‎co LOCUS‏ گویند. - هر موجود زنده در سیر تکامل خود خصوصیات والدینش را نیز به ارث می برد. «Genotype or Structure) pg 55035 bls 4 Organism) ou; 455 gs - مقادیر ژن آن و تأثیرات ناشی از محیط اطراف (60011۳6) بستگی دارد. 

صفحه 9:
الگوریتم ژنتیک در یک نگاه الكوريتم ثنتيك اولين بار توسط جان هلند هذ ۵ مطرح كرديد. اساس الكوريتم ژنتیک تکامل طبیعی می باشد. الگوریتم ژنتیک بر خلاف سایر رويكردهاى فرابتکاری؛ بجای کار بروی یک جواب (کروموزوم) منفرد؛ در هرتکرار بروی جمعیتی از جواب ها كار مى ‎G38 Population) cram a iS‏ در هر تکرار الگوریتم نسل ‎lp 09d Le af (Generation)‏ توليد نسل جديد. برخى از جواب ها در نسل فعلى انتخاب مى شوند كه به آن جمعيت والد ‎ge Mating pool)‏ كويند. کروموزوم های جمعیت والد با استفاده از سه عملگر اساسی ژنتیک بنام های تقاطع (0۲0950۷61) و چهش (2108 ۷10 یا حضور ‎(Reproduction) sams‏ فرزندان ‎(Offspring)‏ خود را جهت حضور در نسل بعدی تولید می کنند. عملگر جهش عموماً برای حفظ سطح قابل قبولی از تنوع (017615113) در جمعیت مورد استفاده قرار می گیرد. فرازندانی برای حضور در نسل بعدی پذیرفته می شوند که دارای ‎Cod 6 tue (Fitness-Profit-Goodness-Utility) 5.53,‏ 2 والدين خود باشند. اين امر موجب می گردد که نسل جدید نسبت به نسل قبلی تکامل ‎Evolution‏ یابد. با تکرارالگوریتم» متوسط برازندگی نسل ها بهبود خواهد يافت تا اينكه الكوريتم به ناحيه خاصى /ز"فضتاى جواب همكرا كردد. 

صفحه 10:
همسانی ذاتی و تئوری الکو مفهوم بنیادین هلند برای توسعه تحلیل نظری الگوریتم های ژنتیک مفهوم الگو (50116102) می باشد. فرض کنید یک کروموزوم باینری به طول 1۷ مفروض می باشد بطوریکه هر ژن آن فقط مقادیر ۰ یا ۱ را می تواند داشته باشند. یک الگو به مجموعه ای از کروموزوم های مشابه گفته می شود که در تعداد مشخصی از ژن ها از لحاظ مکان و مقدار همسان باشند. الكو مى تواند مبين يك ابرصفحه در فضاى 2 بعدى باشد. شكل زیر یک الگو و دو نمونه (105120600) متعلق به آن را نشان مى دهد بطوريكه بجاى علامت # مقدار ‎٠‏ يا ‎١‏ مى تواند قرار كيرد. 0 6|] © | 0 06 | ٩ ۱ ۰] 0۱*۱] ‏۶ص‎ ۶ 0 6 | © | 0 0 | ۵ | 0 در حالت کلی یک کروموزوم بایشری بطول ۷ ؛ تعداد 24 نوع الكو دارد. زيرا در هر مكان؛ علامت # يا يك مقدار واقعى مى تواند قرار گیرد. با بدست آوردن برازندگی کروموزوم هاى متعلق به يك الكو مى توان اطلاعاتى در مورد برازندكى يك الكو خاص بدست آورد. هدف اصلى يافتن الكوهايى با برازندكى بالاتر مى باشد. سود 

صفحه 11:
همسانی ذاتی و تئوری الکو هلند ثابت کرد که تحت شرایط یکسان؛ پردازش یک جمعیت به اندازه /۸ در یک نسل به معنای پردازش (/0)/1) الگو می باشد. او همچنین ثابت کرد که با بکار بردن عملگرهای ژنتیکی؛ هرالگوی ارائه شده در نسل فعلی هم ارز با برازندگی نسبی خود؛ مستقل از الگوهای دیگر افزایش یا کاهش خواهد یافت. برای اثبات ادعاهای فوق به تعاريف زير نياز مى ‎Bibl‏ _ ‎-١‏ طول الكو : فاصله بين اولين و آخرين رن تعريف شده در الكو. ۲- ترتیب الگو: تعداد ژنهای تعریف شده در الگو. ۳- نرخ برازندگی الگو : نسبت متوسط برازندگی الگو به متوسط برازندگی جمعیت طول الكو - ۴ 

صفحه 12:
تطبیق مفاهیم ژنتیکی با مفاهیم بهینه سازی مفاهیم ژنتیکی مفاهیم بهینه سازی کروموزوم جواب شدنی ( يك نقطه از فضای مسأله) تسل جمعیتی از جوابهای شدنی عملگر ژنتیکی توليدحل همسايه مقدار برازندگی مقدار تابع هدف - مطلوبیت تكامل حرکت بسوی بهینه موضعی سود 

صفحه 13:
شش گام اساسی در طراحی یک الگوریتم ژنتیک جهت مسایل بهینه سازی ۱- طراحی ساختار کرموزوم یا نحوه نمایش حل مسأله ‎(Representation)‏ ‏۲- استراتژی تولید جمعیت اولیه (66601060 . ۳- استراتژی انتخاب جمعیت والد (2001 ‎Mating‏ یا مکانیزم انتخاب. ۴- طراحی یا انتخاب عملگرهای ژنتیکی متناسب با ساختارکروموزوم و ‎(Operators) Sls 99.8‏ ۵- نحوه محاسبه برازندگی پا کیفیت کروموزوم ‎(Fitness) le‏ ‎«Stop Criteria) 4855 es Gui -¥‏ سود 

صفحه 14:
طراحی ساختار کرموزوم با نحوه نمایش حل مساله ماهیت ساختار کروموزوم بستگی به کیفیت متغیر تصمیم و قیود مسأله دارد. مواردی همچون پیوسته اگسسته. باینری/غیرباینری بودن متفیر تصمیم و یا تعداد بعد آن» همچنین نوع ارتباط بین متغیرهای تصمیم در قیود مسأله مبنای اصلی طراحی کروموزوم می باشند. به عنوان نمونه؛ در یک مسأله 11206 016ص8 با ۷ کار و با تابع هدفی از جنس دیرکرد (12010655) . با توجه به اینکه هر توالی ممکن از کارها برای مسأله شدنی می باشد؛ می توان از ساختاری مانند شکل زیر برای نمایش حل شدنی يا کرموزوم استفاده کرد. جهت ارضای قیود اساسی مسأله هر ژن فقط یکی از مقادیر ۱ تا ۷ را می تواند اختیار کند. شکل زیر یک نقطه از فضای شدنی مسأله یا به عبارت دیگر یک توالی از کارها را تشان می دهد ‎[S] 91 1‏ 01 [9 91 1 ‎e q ? 6‏ @ 2 9 7 توالی (مکان ژن) کار ( مقدار ژن) سود 

صفحه 15:
ساختار کرموزوم در سأله 51:00 ط0[با فرض بیکاری عمدی در حالتی که هدف از جنس کمینه سازی زودکرد نیز باشد استفاده از بیکاری عمدی مدنظر می باشد. برای نمایش کروموزوم در چنین حالتی؛ می توان علاوه بر سطر مربوط به نمايش توالى كارهاء سطر ديكرى به كرموزوم جهت نمايش مقدار بيكارى عمدى اضافه كرد. با توجه به نوع مسأله مقادير اين سطر مى توانند عدد صحيح يا حقيقى باشند و محدوديتى براى مقادير اين سطر به لحاظ تئوريك وجود ندارد. به عنوان نمونه. مقدار ‎١‏ در سطر ؟ و مكان [؟] به معنای وجود اواحد بیکاری عمدی قبل از کار ۴ مى باشد. ] 9 8 0 9 9 ‏لها‎ ‎9 8 ‏اف‎ 6 qd 8 6 8 © qa 9 71 © 0 سود 

صفحه 16:
5 ۳ ساختار كرموزوم در مسأله بوشش مجموعه (56©1 ‎(Covering‏ ‏در مسأله پوشش مجموعه؛ ۸۷ نقطه تقاضا موجود می باشد که باید خدمات خاصی به آنها ارایه گردد. در ۶ نقطه فوق, یک مرکز خدمت دهی بصورت بالقوه موجود است. هر نقطه فاقد امکانات جهت استفاده از حداقل یکی از مراکز فوق باید تا حد معینی بدان نزدیک باشد. هدف تاسیس یا استقرار تسهیلات در یک یا چند نقطه فاقد مرکز خدد دهی می باشد بطوریکه کلیه نقاط فاقد امکانات سرویس دهی شده و هزینه تأسیس یا استقرار كمينه كردد. فرض کنید ۷ شهر موجود می باشد که بايد بدانها خدمات آتش نشانی ارائه گرده بطوریکه در شهرهای ۲و۴ مرکز آتش نشانی وجود دارد. در ۵ شهر دیگر می توان بصورت بالفعل مرکز آتش نشانی تأسیس نمود. در نتیجه ساختار كروموزوم را مى توان بصورت شكل زير با زنهاى باينرى درنظر كرفت بطوريكه مقدار براى رن 7 ام به معناى تأسيس مركز 7 انى در شهر 4 مى باشد. طبق فرض شهرهای ۲و۴ همواره مقدار ارا دارند. 1 9 ]9[ 0 61 61 1 Fixed. Fixed. ٠ ۳ ۰ ۳ ۰ ۲۰ ee 

صفحه 17:
ساختار کر موزوم در مسأله تشکیل سلول (611 ‎(Formation‏ هدف از مسأله تشکیل سلول در حالت کلاسیک؛ پردازش تعدادی قطعه توسط برخی انواع ماشین های موردنیاز آنها می باشد بگونه ای هزینه نقل و انتقالات مواد و ترافیک درون کارگاه کمینه گردد. اين کار با تشکیل خانواده قطعات و ‎ost‏ های ماشین انجام می شود. بطوریکه با تخصیص هر خانواده قطعه به یک گروه ماشین» یک سلول پردازشی ایجاد می گردد. با توجه به اينکه هر قطعه نیاز به چند نوع پردازش مختلف داد لذا احتمالا به بيش از یک سلول جهت پردازش نیاز خواهد داشت. البته با این فرض اولیه که از هر نوع ماشین فقط یک عدد در دسترس بوده و یا تعدد ماشین ها مجار نباشد. همچنین حداکثر تعداد مجاز سلولها نیز از ابتدا مشخص می باشد. فرض کنید ۷ نوع قطعه و ۵ نوع ماشین در دسترس بوده و حداکثر تشکیل ۳ سلول مجاز باشد. در این حالت می توان از یک کروموزوم به طول ۷:۵ استفاده کرد بطوریکه مقادیر ژن برای آن نشان دهنده شماره سلول می باشد. تخصیص ماثيين به سلول | تخصيص قتلعه به سلول 6 هم و 6 10 ۶ 6 م خم هم ۱ 0 [ 1١ 1١ 1 1 1 1111 (9 ۱۵ 64 

صفحه 18:
استراتژی تولید جمعیت 91 49 ‎(Seeding)‏ جهت تولید جمعیت اولیه عموما از روش تولید تصادفی کروموزوم ها استفاده می شود. در روش تصادفی از آنجائیکه کروموزوم ها متعلق به نواحی مختلف فضای جواب می باشند لذا تنوع کروموزوم ها بالا است؛ در نتیجه در تکرارهای اولیه الگوریتم؛ تکامل نسل ها سریعتر انجام می گیرد ولى با افزايش تكرارء تشابه كروموزوم ها نيز افزايش يافته تا اينكه در نهایت الگوریتم به یک یا چند حل شاخص همگرا گردد. در برخی از تحقیقات. از تکنیک های ابتکاری یا فراابتکاری دیگر همانند 9۵ یا 75 نیز جهت بدست آوردن یک جمعیت اولیه با کیفیت بالا استفاده شده است. اگرچه اشکال عمده روش فوق افزایش احتمال همگرایی زودرس ‎Utal’ L Premature Convergence)‏ تنوع در جمعیت می باشد. سود 

صفحه 19:
نحوه ایجاد جمعیت اولیه تعداد جمعیت اولیه - 5 

صفحه 20:
(Mating Pool) Wg Curce Wil ‏مکانیزم‎ مکانیزم انتخاب تعیین می کند که کدام یک از کروموزوم های نسل فعلی بطور مستقیم يا غیرمستقیم در نسل بعد نیز حضور یابند. شکل زیر تقسیم بندی جامعی از مکانیزم های انتخاب که تاکنون ارائه شده است را نشان می دهد. 

صفحه 21:
تعریف فشار انتخاب (۶۲۲6عع۳ ‎(Selection‏ فشار انتخاب عبارث است از احتمال انتخاب برازندترین اعضای نسل فعلی: فشار انتخاب بالا منجر به یک جستجوی تهاجمی می گردد. بطوریکه باعث بهربرداری از اطلاعاتی می گردد که تاکنون در طول فرآیند جستجو بدست آمده بدون آنکه در صدد کاوش مناطق اکتشاف نشده فضای جواب باشد. فشار انتخاب بالا عموماً موجب همگرایی زودرس ( بهینه موضعی) شده در حالیکه فشار انتخاب پایین ممکن است روند تکامل نسل ها را دچار نقصان سازد. سود 

صفحه 22:
تشریح برخی از مکانیزم های انتخاب ۱- انتخاب چرخ رولتی د181۷5): در این روش احتمال انتخاب کروموزوم ها با برازندگی بیشتر بالاتر می باشد. به عبارت دیگر به هر کروموزوم به نسبت برازندگی آن. یک شانس انتخاب داده می شود. در نتیجه ممکن است بعضی از کروموزوم ها چندبار انتخاب شده و یا اصلاً انتخاب نشوند. ۲- مدلهای نخبه: در اين روش برازنده ترین اعضای نسل فعلی باید در نسل بعد حضور يابند. "- روش ترنمنت 1'01333333312613212): در اين روش در هر تكرار يك مجموعه 4 عضوی از نسل فعلی انتخاب:فنده وابهترین آنها برای-حضور:در سل بعد ‎ee SEI‏ شوند. به پارامتر 6 اندازه ترنمنت می گویند. این کار به تعداد نسل ها تکرار می شود. طبیعی است که با افزایش مقدار ۸ فشار انتخاب نیز افزایش می یابد. ۴-روش رتبه بندی د18۸10161170): در اين روش اعضای نسل فعلی برحسب درجه برازندگی از بهترین تا بدترین مرتب شده و هر عضو به تعداد دفعات ممکن نسخه برداری می شود. سپس یک رویکرد انتخاب مقتضی اعمال می گردد. اين روش برای مستایل چنف هدقی منانسب مى بباشلد سود 

صفحه 23:
| | ا ‎sw, Elo]‏ [121۴1210] 0 فرزند 

صفحه 24:
(Rank X ) ‏عملگر تقاطعی‎ € 3 | 0 0.69 0.78 0.86 0628 ۶ 0 ای ۰19 6 ۳3 0۵.9 0.66 0.66 0۵9 0 

صفحه 25:
(Rank X ) ‏عملگر تقاطعی‎ Paect I ‏عوجت‎ © 5161616104 91916 0۵.99 0.66 0.66 0.66 0.06 0.69 0.9 0.66 0.66 0.06: 9 are OPP pricey 

صفحه 26:
عملگر تقاطعی (تک نقطه ای) تس ها 0 سول OPPsprtcq ٩ ‏مسروعع0‎ © 

صفحه 27:
نمونه ای از تکامل در الگوریتم ژنتیک با جمعیتی برابر با ۱۰ کروموزوم Rekive Prose Zen, Zee, Zen, Zen, Zen, Zen, Zen, +1) Ze, aces Press Fen, Fen, Fen, Fen, Fen, Fun, Fen, + Fen, اك Popuatca (#0) 0000000000 0000000000 100000 2 » '! 0 0000 00000000002 0000000000 2200 سرد Rete Cress Zo, Zo, نیج 0 0۹ 00 0000 ood 0000000 ood 00 00 000000000 220 22200 00 100000 00 2200 oo 

صفحه 28:
نمای کلی از الگوریتم ژنتیک کلاسیک اتعداد نسل ها از حداکثر مجاز تجاوز كرده است؟ حم ‎at‏ | | سس ‎ ‎ ‎ ‏مقداردهى به بارامترهاى اوليه مسأله ( اندازه جمعیت؛ حداکثرتعداد نسل ها؛ نرخ اعمال عملگرها) 1ك ‏توليد جمعيت اوليه و محاسبه مقادير برازندكى نسبى هر عضو جمعيت ‎TE‏ ‏اعضای والد نسل بعد ا ‏اعمال عملگرهای ژنتیکی ( تقاطعی؛ جهش؛ تولید مجددب بروی جمعیت والد جهت تولید فرزندان جدید ‎۳ ‏پذیرش فرزندان با برازندگی بهتر نسبت به والدین خود و و ایجاد نسل جدید ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎