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

صفحه 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‏ ‏اعضای والد نسل بعد ا ‏اعمال عملگرهای ژنتیکی ( تقاطعی؛ جهش؛ تولید مجددب بروی جمعیت والد جهت تولید فرزندان جدید ‎۳ ‏پذیرش فرزندان با برازندگی بهتر نسبت به والدین خود و و ایجاد نسل جدید ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

آشنایی الگوریتم های ژنتیک ‏Genetic Algorithms در طبيعت ،گونه های زنده ،جهت ادامه بقا ،مجبورند خود را با شرايط محيطی وفق دهند .اين کار تحت فرآيندی بنام تکامل صورت مي گيرد. تقسیم بندی کلی روشهای حل مسایل بهینه سازی • روشهای دقیق ( : )Exactروشهایی مانند (سیمپلکس ،دوگان ،شبکه، شاخه و حد ،برنامه ریزی پویا ،الگرانژین و )...که دستیابی به حل بهینه را تضمین می کنند. • روشهای غیردقیق ( : )No Exactروشهایی که در صدد دستیابی به حل های نزدیک به بهینه می باشند ولی دستیابی به حل بهینه را تضمین نمی کنند .رویکردهای ابتکاری مانند Hungarianبرای حل مسأله تخصیص یا Johnsonبرای حل مسأله زمانبندی دو ماشین و یا روشهای فوق ابتکاری برگرفته از مکانیزم های طبیعی متعلق به این دسته می باشند. ‏irmgn.ir بهینه سراسری و موضعی F(x) x Local x Global N(xLocal,) irmgn.ir x  تعریف همسایگی ( : )Neighborhoodیک همسایگیاز جواب شدنی xXمانند ) N(x,به مجموعه ای از جواب های شدنی گفته می شود که با اعمال عملگر بروی xقابل دستیابی باشند .عملگر می تواند به معنی حذف ،اضافه یا تغییر عناصر موجود در xباشد .به عملگر اصطالحًا حرکت ( )Moveنیز گفته می شود. تعریف بهینه موضعی ( : )Local Optimumهرگاه یکهمسایگی مانند ) N(x,یافت شود بگونه ای که حل xاز هر حل موجود در آن همسایگی بهتر باشد؛ به xاصطالحًا بهینه موضعی گفته می شود. ‏irmgn.ir مفهوم NP ‏k ‏T )(nb ‏T ae a ! k 1 k ‏ ‏nb ‏n تعریف : NPعبارت NPمخفف (Non –Deterministic )Polynomialبه معنای چندجمله ای نامعین بوده و در بحث پیچیدگی محاسبات مطرح می گردد .عبارت فوق به مسایلی اطالق می گردد که زمان حل آنها توسط یک الگوریتم دقیق برحسب ابعاد مسأله از نوع یک سری چندجمله ای نامعین مانند سری نمایی باشد .مسایلی همانند TSP، knapsackو ...جزء مسایل NPمی باشند. ، Job Shop Scheduling ‏irmgn.ir روش ابتکاری تعریف :یک روش ابتکاری عبارت است از تکنیکی که حل های نزدیکبه بهینه را با یک هزینه محاسباتی قابل قبول جستجو می کند .ولی تضمینی برای رسیدن به حل بهینه نمی دهد. توجه به این نکته حائز اهمیت می باشد که در اکثر مدلسازی ها؛ نمی توان کلیه پارامترهای مؤثر بر شرایط مسأله را وارد مدل نمود ،لذا تضمینی وجود ندارد که بهترین حل بدست آمده توسط مدل همان حل مطلوب برای شرایط واقعی باشد .حال این سئوال مطرح می باشد که یک حل دقیق از یک مدل تقریبی بهتر می باشد یا یک حل تقریبی از یک مدل دقیق؟ در پاسخ به این سئوال رویکردهای فراابتکاری این امکان را مهیا می سازند که بتوانیم یک حل تقریبًا خوب را از یک مدل کامًال دقیق بدست آوریم چراکه افزایش پیچیدگی مسأله تأثیر چندانی در عملکرد آنها نخواهد داشت. ‏irmgn.ir روشهای ابتکاری بر مبنای مکانیزم های طبیعی - شبکه های عصبی مصنوعی()Artificial Neural Network الگوریتم های ژنتیک ()Genetic Algorithm جستجوی ممنوع ()Tabu Search سرد شدن تدریجی ()Simulated Annealing جامعه مورچگان ()Ant Colony ‏irmgn.ir مبانی الگوریتم ژنتیک ارگانیسم های طبیعی جهت ادامه بقای خود ناچار به تطبیق هرچه بیشتر با محیط اطرافخود می باشند. ارگانیسم هایی که نتوانند خود را با محیط و شرايط زيست محيطی که در آن حضوردارند ،تطبیق دهند ،محکوم به فنا می باشند. خصوصیات هر ارگانیسم طبیعی در یک رشته بنام کروموزوم کد شده است. کروموزوم ها خود متشکل از تعدادی اجزاء بنام ژن می باشند بطوریکه هر ژن با توجه بهمقدارخود ،مبین خصوصيات ارگانیسم مانند اندازه قد؛ وزن ،رنگ مو ،رنگ پوست ،رنگ چشم ،نوع رفتار و ....می باشد .به مقادیری که هر ژن می تواند اختیار کند allelesو به موقعيت مکانی ژن درکروموزوم Locusمی گویند. هر موجود زنده در سیر تکامل خود خصوصیات والدینش را نیز به ارث می برد. نوع گونه زنده ( )Organismبه ساختارکروموزوم (،)Genotype or Structureمقادیر ژن آن و تأثيرات ناشی از محيط اطراف ( )Phenotypeبستگی دارد. ‏irmgn.ir الگوریتم ژنتیک در يک نگاه الگوریتم ژنتیک اولين بار توسط جان هلند در 1975مطرح گرديد .اساس الگوریتم ژنتیک ،تکامل طبیعی می باشد .الگوریتم ژنتیک بر خالف ساير رويکردهای فراابتکاری؛ بجای کار بروی يک جواب (کروموزوم) منفرد؛ در هرتکرار بروی جمعيتی از جواب ها کار می کند .به جمعيت ( )Populationفوق در هر تکرار الگوريتم نسل ( )Generationگفته می شود .برای توليد نسل جديد ،برخی از جواب ها در نسل فعلی انتخاب می شوند که به آن جمعيت والد ( )Mating poolمی گويند. کروموزوم های جمعيت والد با استفاده از سه عملگر اساسی ژنتيک بنام های تقاطع ( )Crossoverو جهش ( )Mutationيا حضور مجدد ( ،)Reproductionفرزندان ( )Offspringخود را جهت حضور در نسل بعدی توليد می کنند .عملگر جهش عمومًا برای حفظ سطح قابل قبولی از تنوع ( )Diversityدر جمعيت مورد استفاده قرار مي گيرد .فرازندانی برای حضور در نسل بعدی پذيرفته می شوند که دارای برازندگی ( )Fitness-Profit-Goodness-Utilityبهتری نسبت به والدين خود باشند .اين امر موجب می گردد که نسل جديد نسبت به نسل قبلی تکامل ( )Evolutionیابد .با افزايش تکرارالگوريتم ،متوسط برازندگی نسل ها بهبود خواهد ‏irmgn.ir فضای جواب همگرا گردد. یافت تا اينکه الگوريتم به ناحيه خاصی از همسانی ذاتی و تئوری الگو مفهوم بنيادين هلند برای توسعه تحليل نظری الگوريتم های ژنتيک مفهوم الگو ( )Schemaمی باشد .فرض کنيد يک کروموزوم باينری به طول Nمفروض می باشد بطوريکه هر ژن آن فقط مقادیر 0يا 1را می تواند داشته باشند .يک الگو به مجموعه ای از کروموزوم های مشابه گفته می شود که در تعداد مشخصی از ژن ها از لحاظ مکان و مقدار همسان باشند .الگو می تواند مبين يک ابرصفحه در فضای Nبعدی باشد .شکل زير يک الگو و دو نمونه ( )Instanceمتعلق به آن را نشان می دهد بطوريکه بجای عالمت * مقدار 0يا 1می تواند قرار گيرد. 0 1 0 1 0 1 0 1 0 0 1 0 1 1 * * 0 * * 1 * در حالت کلی يک کروموزوم باينری بطول N؛ تعداد 2Nنوع الگو دارد .زيرا در هر مکان؛ عالمت * يا يک مقدار واقعی می تواند قرار گيرد .با بدست آوردن برازندگی کروموزوم های متعلق به يک الگو می توان اطالعاتی در مورد برازندگی يک الگو خاص بدست آورد .هدف اصلی يافتن الگوهایی با برازندگی باالتر می باشد. ‏irmgn.ir همسانی ذاتی و تئوری الگو هلند ثابت کرد که تحت شرايط یکسان؛ پردازش يک جمعيت به اندازه Mدر يک نسل به معنای پردازش ) O(M3الگو می باشد .او همچنين ثابت کرد که با بکار بردن عملگرهای ژنتیکی؛ هرالگوی ارائه شده در نسل فعلی هم ارز با برازندگی نسبی خود؛ مستقل از الگوهای ديگر افزايش يا کاهش خواهد يافت .برای اثبات ادعاهای فوق به تعاریف زير نياز می باشد: -1طول الگو :فاصله بين اولين و آخرين ژن تعريف شده در الگو. -2ترتيب الگو :تعداد ژنهای تعريف شده در الگو. -3نرخ برازندگی الگو :نسبت متوسط برازندگي الگو به متوسط برازندگی جمعيت طول الگو = 4 * * 0 * * ترتيب الگو = 2 ‏irmgn.ir 1 * تطبیق مفاهيم ژنتیکی با مفاهيم بهينه سازی مفاهيم ژنتيکی مفاهيم بهينه سازی نسل جمعيتی از جوابهای شدنی عملگر ژنتيکی توليدحل همسايه مقدار برازندگی مقدار تابع هدف -مطلوبيت تکامل حرکت بسوی بهينه موضعی کروموزوم جواب شدنی ( يک نقطه از فضای مسأله) ‏irmgn.ir شش گام اساسی در طراحی یک الگوریتم ژنتیک جهت مسايل بهينه سازی - 1طراحی ساختار کرموزوم یا نحوه نمایش حل مسأله (.)Representation -2استراتژی توليد جمعيت اوليه (. )Seeding -3استراتژی انتخاب جمعيت والد ( )Mating Poolيا مکانيزم انتخاب. -4طراحی يا انتخاب عملگرهای ژنتيکی متناسب با ساختارکروموزوم و قيود مسأله)Operators( . -5نحوه محاسبه برازندگي يا کيفيت کروموزوم ها (.)Fitness -6تعيين معيار توقف.)Stop Criteria( . ‏irmgn.ir طراحی ساختار کرموزوم يا نحوه نمايش حل مسأله ماهيت ساختار کروموزوم بستگی به کيفيت متغير تصميم و قيود مسأله دارد .مواردی همچون پيوسته/گسسته ،باينری/غيرباينری بودن متغير تصميم و يا تعداد بعد آن ،همچنين نوع ارتباط بين متغيرهای تصميم در قيود مسأله مبنای اصلی طراحی کروموزوم می باشند. به عنوان نمونه؛ در يک مسأله Single Machineبا 7کار و با تابع هدفی از جنس ديرکرد ( ، )Tardinessبا توجه به اينکه هر توالی ممکن از کارها برای مسأله شدنی می باشد؛ می توان از ساختاری مانند شکل زير برای نمايش حل شدنی يا کرموزوم استفاده کرد. جهت ارضای قيود اساسی مسأله هر ژن فقط يکی از مقادير 1تا 7را می تواند اختيار کند. شکل زير يک نقطه از فضای شدنی مسأله يا به عبارت ديگر يک توالی از کارها را نشان می دهد. ][7 ][6 ][5 ][4 ][3 ][2 ][1 6 7 1 2 4 5 3 توالی ( مکان ژن) ‏irmgn.ir کار ( مقدار ژن) ساختار کرموزوم در مسأله Job Shopبا فرض بيکاری عمدی در حالتی که هدف از جنس کمينه سازی زودکرد نيز باشد استفاده از بيکاری عمدی مدنظر می باشد .برای نمایش کروموزوم در چنين حالتی ،می توان عالوه بر سطر مربوط به نمایش توالی کارها ،سطر ديگری به کرموزوم جهت نمایش مقدار بيکاری عمدی اضافه کرد .با توجه به نوع مسأله مقادير اين سطر می توانند عدد صحيح يا حقيقی باشند و محدوديتی برای مقادير اين سطر به لحاظ تئوريک وجود ندارد .به عنوان نمونه ،مقدار 1در سطر 2و مکان [ ]3به معنای وجود 1واحد بيکاری عمدی قبل از کار 4می باشد. ][7 ][6 ][5 ][4 ][3 ][2 ][1 6 0 7 0 1 1 2 3 4 1 5 0 3 2 ‏irmgn.ir ساختار کرموزوم در مسأله پوشش مجموعه (Set )Covering در مسأله پوشش مجموعه؛ Nنقطه تقاضا موجود می باشد که بايد خدمات خاصی به آنها ارايه گردد .در kنقطه فوق ،يک مرکز خدمت دهی بصورت بالقوه موجود است .هر نقطه فاقد امکانات جهت استفاده از حداقل یکي از مراکز فوق بايد تا حد معينی بدان نزديک باشد. هدف تإسيس یا استقرار تسهيالت در يک يا چند نقطه فاقد مرکز خدمت دهی می باشد بطوريکه کليه نقاط فاقد امکانات سرويس دهی شده و هزينه تأسيس يا استقرار کمينه گردد. فرض کنيد 7شهر موجود می باشد که بايد بدانها خدمات آتش نشانی ارائه گردد بطوريکه در شهرهای 2و 4مرکز آتش نشانی وجود دارد .در 5شهر ديگر می توان بصورت بالفعل مرکز آتش نشانی تأسيس نمود .در نتيجه ساختار کروموزوم را می توان بصورت شکل زير با ژنهای باينری درنظر گرفت بطوريکه مقدار 1برای ژن iام به معنای تأسيس مرکز آتش نشانی در شهر iمی باشد .طبق فرض شهرهای 2و 4همواره مقدار 1را دارند. ][7 ][6 ][5 ][4Fixed ][3 ][2Fixed ][1 1 1 0 1 0 1 0 ‏irmgn.ir ساختار کرموزوم در مسأله تشکيل سلول (Cell )Formation هدف از مسأله تشکيل سلول در حالت کالسيک؛ پردازش تعدادی قطعه توسط برخی انواع ماشين های موردنياز آنها می باشد بگونه ای هزينه نقل و انتقاالت مواد و ترافيک درون کارگاه کمينه گردد .اين کار با تشکيل خانواده قطعات و گروه های ماشين انجام می شود. بطوريکه با تخصيص هر خانواده قطعه به يک گروه ماشين ،يک سلول پردازشی ایجاد می گردد .با توجه به اينکه هر قطعه نياز به چند نوع پردازش مختلف دارد ،لذا احتماًال به بيش از يک سلول جهت پردازش نياز خواهد داشت .البته با اين فرض اوليه که از هر نوع ماشين فقط يک عدد در دسترس بوده و يا تعدد ماشين ها مجار نباشد .همچنين حداکثر تعداد مجاز سلولها نيز از ابتدا مشخص می باشد .فرض کنيد 7نوع قطعه و 5نوع ماشين در دسترس بوده و حداکثر تشکيل 3سلول مجاز باشد .در اين حالت می توان از يک کروموزوم به طول 7+5استفاده کرد بطوريکه مقادير ژن برای آن نشان دهنده شماره سلول می باشد. تخصيص ماشين به سلول تخصيص قطعه به سلول [1] [2 [3 [4 [5 [6 [7 [1] [2 [3 [4 [5 ] ] ] ] ] ] ] ] ] ] 1 2 1 3 3 1 ‏irmgn.ir 2 3 3 1 2 1 استراتژی توليد جمعيت اوليه ()Seeding جهت توليد جمعيت اوليه عمومًا از روش توليد تصادفی کروموزوم ها استفاده می شود .در روش تصادفی از آنجائيکه کروموزوم ها متعلق به نواحی مختلف فضای جواب می باشند لذا تنوع کروموزوم ها باال است؛ در نتيجه در تکرارهای اوليه الگوريتم؛ تکامل نسل ها سريعتر انجام می گيرد ولی با افزايش تکرار، تشابه کروموزوم ها نيز افزايش يافته تا اينکه در نهايت الگوريتم به يک يا چند حل شاخص همگرا گردد .در برخی از تحقيقات ،از تکنيک های ابتکاری يا فراابتکاری ديگر همانند SAيا TSنیز جهت بدست آوردن يک جمعيت اوليه با کيفيت باال استفاده شده است .اگرچه اشکال عمده روش فوق افزايش احتمال همگرايي زودرس ( )Premature Convergenceيا کاهش تنوع در جمعيت می باشد. ‏irmgn.ir شروع انتخاب يک کروموزوم بصورت تصادفي خ ير خ ير آيا کروموزوم موجه است؟ بله آيا کروموزوم غير تکراري است؟ بله افزودن اين کروموزوم به جمعيت اوليه خ ير آيا تعداد جمعيت اوليه برابر nاست؟ بله ‏irmgn.irان پاي نحوه ايجاد جمعيت اوليه تعداد جمعيت اوليه = n مکانيزم انتخاب جمعيت والد ()Mating Pool مکانيزم انتخاب تعيين می کند که کدام يک از کروموزوم های نسل فعلی بطور مستقيم يا غيرمستقيم در نسل بعد نيز حضور يابند .شکل زير تقسيم بندی جامعی از مکانيزم های انتخاب که تاکنون ارائه شده است را نشان می دهد. مکانيزمهای انتخاب مکانيزمهای بر مبنای رتبه بندی مدلهای ارزش انتظاری مدلهای نخبه مدلهای ارزش انتظاری نخبه رتبه بندی ترنمنت سنتی مکانيزمهای تصادفی ‏Speciation ‏irmgn.ir نمونه گيری تصادفی جامع ()SUS ترنمنت تصادفی چرخ رولتی ()RWS تعريف فشار انتخاب ()Selection Pressure فشار انتخاب عبارت است از احتمال انتخاب برازندترين اعضای نسل فعلی .فشار انتخاب باال منجر به يک جستجوی تهاجمی می گردد ،بطوريکه باعث بهربرداری از اطالعاتی می گردد که تاکنون در طول فرآيند جستجو بدست آمده بدون آنکه در صدد کاوش مناطق اکتشاف نشده فضای جواب باشد .فشار انتخاب باال عمومًا موجب همگرايي زودرس ( بهينه موضعی) شده در حاليکه فشار انتخاب پايين ممکن است روند تکامل نسل ها را دچار نقصان سازد. ‏irmgn.ir تشريح برخی از مکانيزم های انتخاب -1انتخاب چرخ رولتی ( :)RWSدر اين روش احتمال انتخاب کروموزوم ها با برازندگی بيشتر باالتر می باشد .به عبارت ديگر به هر کروموزوم به نسبت برازندگی آن ،يک شانس انتخاب داده می شود .در نتيجه ممکن است بعضی از کروموزوم ها چندبار انتخاب شده و يا اصًال انتخاب نشوند. -2مدلهای نخبه :در اين روش برازنده ترين اعضای نسل فعلی بايد در نسل بعد حضور يابند. -3روش ترنمنت ( :)Tournamentدر اين روش در هر تکرار يک مجموعه k عضوی از نسل فعلی انتخاب شده و بهترين آنها برای حضور در نسل بعد انتخاب می شوند .به پارامتر kاندازه ترنمنت می گويند .اين کار به تعداد نسل ها تکرار می شود. طبیعی است که با افزايش مقدار kفشار انتخاب نيز افزايش مي یابد. -4روش رتبه بندی ( :)Rankingدر اين روش اعضای نسل فعلی برحسب درجه برازندگی از بهترين تا بدترين مرتب شده و هر عضو به تعداد دفعات ممکن نسخه برداری می شود .سپس يک رويکرد انتخاب مقتضی اعمال می گردد .اين روش برای مسايل چند هدفی مناسب می باشدirmgn.ir . عملگر جهش 0 1 1 0 0 1 والدين فرزند ‏irmgn.ir 1 3 2 4 5 )Rank X ( عملگر تقاطعی Parent 1 3 2 4 5 1 0.92 0.68 0.54 0.32 0.08 1 0.46 2 0.82 3 1.78 4 0.76 5 1.04     3 Parent 2 5 1 4 2 0.86 0.72 0.38 0.22 0.14  irmgn.ir )Rank X ( عملگر تقاطعی Parent 1 3 2 4 5 1 0.92 0.68 0.54 0.32 0.08 1 0.46 2 0.82 3 1.78 4 0.76 5 1.04 3 Parent 2 5 1 4 2 0.86 0.72 0.38 0.22 0.14 Offspring irmgn.ir )عملگر تقاطعی (تک نقطه ای Parent 1 0 1 1 0 0 1 Parent 2 0 0 1 Offspring 2 Offspring 1 irmgn.ir 0  کروموزوم10 نمونه ای از تکامل در الگوريتم ژنتيک با جمعيتی برابر با Population Fitness (t) Relative Fitness Population Fitness Relative Fitness (t+1) 0101001 010 F(t)1 Z(t)1 0101001100 F(t+1)1 Z(t+1)1 0000111 001 F(t)2 Z(t)2 0011001010 F(t+1)2 Z(t+1)2 1010100 001 F(t)3 Z(t)3 1000101001 F(t+1)3 Z(t+1)3 00110011 00 F(t)4 Z(t)4 0011100001 F(t+1)4 Z(t+1)4 000000 0001 F(t)5 Z(t)5 0000000001 F(t+1)5 Z(t+1)5 10011001 11 F(t)6 Z(t)6 1000111110 F(t+1)6 Z(t+1)6 1010100 010 F(t)7 Z(t)7 0010110100 F(t+1)7 Z(t+1)7 11001001 00 F(t)8 Z(t)8 1100010001 F(t+1)8 Z(t+1)8 irmgn.ir نمای کلی از الگوريتم ژنتيک کالسيک مقداردهی به پارامترهای اوليه مسأله ( اندازه جمعيت؛ حداکثرتعداد نسل ها؛ نرخ اعمال عملگرها) توليد جمعيت اوليه و محاسبه مقادير برازندگی نسبی هر عضو جمعيت توقف بله خير تعداد نسل ها از حداکثر مجاز تجاوز کرده است؟ تعيين اعضای والد نسل بعد از جمعيت فعلی اعمال عملگرهای ژنتیکی ( تقاطعی؛ جهش؛ توليد مجدد) بروی جمعيت والد جهت توليد فرزندان جديد پذيرش فرزندان با برازندگی بهتر نسبت به والدين خود و و ايجاد نسل جديد ‏irmgn.ir