منبع پایان نامه با موضوع الگوریتم، ژنتیک، بهینه، سازی

ه کمینه سازی به بیشینه سازی تبدیل شود.

2-10-9- انتخاب159
در مرحله انتخاب، یک سری از کروموزوم ها برگزیده می شوند تا به نسل بعد منتقل شوند. بعد از انتخاب، عملگرهای ژنتیک روی یک یا دو عضو برگزیده اعمال می شوند. معیار در انتخاب اعضا ارزش تطابق آنها می باشد اما روند انتخاب حالت تصادفی دارد. انتخاب باید به گونه ای صورت بگیرد تا جایی که ممکن است هر نسل جدید نسبت به نسل قبلی اش میانگین بهتری داشته باشد. روش های متداول انتخاب عبارتند از:
انتخاب بر اساس چرخ رولت160
انتخاب بر اساس تورنامنت161
انتخاب بر اساس بهترین ها162
انتخاب بر اساس حذف درصدی از بدترین اعضا163

2-10-9-1- انتخاب بر اساس تورنامنت
1- محاسبه مقدار برازندگی هر کروموزوم
2- انتخاب اندازه تورنامنت (معمولاً 2 یا 3 )
3- به تعداد اندازه تورنامنت کروموزوم از جمعیت فعلی بصورت کاملاً تصادفی انتخاب می کنیم.
4- بهترین کروموزوم از این کروموزوم ها (بر اساس برازش) به نسل بعد کپی می کنیم.

2-10-9-2- انتخاب بر اساس بهترین ها
زمانی که از عملگرهای ژنتیکی (تقاطع و جهش) استفاده می شود ممکن است بهترین کروموزوم از دست بروند. نخبه گرایی روشی برای نگهداری یک کپی از بهترین ها در نسل جدید است. مکانیسم فوق، الگوریتم ژنتیک را مجبور می سازد، تا همواره تعدادی از بهترین ها را در هر نسل نگه دارد. به تجربه ثابت شده است که این مکانیسم عملکرد الگوریتم ژنتیک را بهبود داده و در ضمن زمان همگرایی را کوتاه می کند.

2-10-9-3- انتخاب بر اساس حذف درصدی از بدترین اعضا
1- محاسبه مقدار برازندگی هر کروموزوم
2- کروموزوم ها را بر اساس مقدار برازندگی مرتب می کنیم.
3- به اندازه Pt درصد از بدترین کروموزوم ها را حذف می کنیم.
4- به جای اعضای حذف شده، اعضای جدید جایگزین می کنیم.

2-10-10- عملگر تقاطع164
مهمترین عملگر در الگوریتم ژنتیک، عملگر تقاطع است. تقاطع، فرآیندی است که در آن نسل قدیمی کروموزوم ها با یکدیگر مخلوط و ترکیب می شوند تا نسل تازه های از کروموزوم ها بوجود بیاید. جفت هایی که در قسمت انتخاب، به عنوان والد در نظر گرفته شدند، در این قسمت ژن هایشان را با هم مبادله می کنند و اعضایی جدید به نام فرزند به وجود می آورند. هر فرزند باید خصوصیاتی را از هر والدش به ارث ببرد. تقاطع در الگوریتم ژنتیک باعث از بین رفتن پراکندگی یا تنوع ژنتیکی می شود. زیرا اجازه می دهد ژن های خوب یکدیگر را بیابند.
احتمال تقاطع (پیوند زنی) pc پارامتری است که تعداد مورد انتظار کروموزوم ها را برای تقاطع تعریف می کند. مراحل 1 و2 باید برای تمام کروموزوم ها تکرار شوند.
تولید یک عدد تصادفی r در بازه صفر تا یک.
2- اگر r pc برقرار باشد کرموزوم مورد نظر برای پیوند زنی انتخاب می شود.
پیوند زنی n نقطه ای: n نقطه پیوند زنی از کد ژنتیک به صورت تصادفی انتخاب شده و رشته های بین نقاط 1,2,…,n-1,n با یکدیگر تعویض می شوند.

2-10-11- جهش165
در طبیعت برخی عوامل مانند اشعه ماورای بنفش باعث به وجود آمدن تغییرات غیرقابل پیش بینی در کروموزوم ها ی موجود جاندار می شوند. از آنجایی که الگوریتم های ژنتیکی از قانون تکامل پیروی می کنند در این الگوریتم ها نیز عملگر جهش با احتمال کم اعمال می شود تا کروموزوم های خوب بدست آمده از فرایند پیوند زنی از دست نرود، که البته این کلی نیست. جهش باعث جستجو در فضاهای دست نخورده مسئله می شود. می توان استنباط کرد که مهمترین وظیفه جهش اجتناب از همگرایی به بهینه محلی است.
این عملگر می تواند روی هر یک از کروموزوم های حاصل از عملگر تقاطع عمل شود. بدین ترتیب که به ازای هر ژن از کروموزوم، یک عدد تصادفی تولید می گردد. اگر مقدار این عدد تصادفی از مقدار pm کمتر باشد، در آن ژن عمل جهش انجام می شود.

2-10-12- معیار توقف
برای اینکه تشخیص دهیم چه موقع الگوریتم از اجرا متوقف شود، از شیوه های مختلفی می توان استفاده کرد. به طور کلی تحت شرایط زیر می توان الگوریتم را متوقف کرد.
تعداد نسل ها
عدم بهبود از یک نسل به نسل دیگر
رسیدن به یک نقطه خاص از فضای جستجو
تکامل نسل ها تا یک مدت زمان پردازش
تعداد کروموزوم های جدید

2-11- نمودار جریان الگوریتم به همراه شبه کد آن
1. تولید جمعیت تصادفی اولیه.
2. بررسی تابع مطلوبیت f(x) هر کروموزوم در جمعیت.
3. ایجاد یک جمعیت جدید بر اساس تکرار قدم های زیر.
3-1. انتخاب دو کروموزوم والد از یک جمعیت بر اساس میزان مطلوبیت آنها
3-2. در نظر گرفتن مقدار مشخصی برای احتمال اعمال عملگر تقاطعی و سپس انجام عملیات تر کیب روی والدین به منظور ایجاد فرزندان. اگر هیچ ترکیب جدیدی صورت نگیرد فرزندان همان والدین خواهند بود.
3-3. در نظر گرفتن احتمال جهش و سپس تغییر فرزندان در هر لوکوس.
3-4. جایگزینی فرزندان جدید در جمعیت جدید.
4. استفاده از جمعیت جدید برای اجرای بعدی الگوریتم.
5. توقف اجرای الگوریتم در صورت مشاهده شرایط توقف و برگرداندن بهترین جواب در جمعیت فعلی.
6. رفتن به قدم 2.
جدول(2- 4). شبه کد الگوریتم ژنتیک.

Step 1: Set t:=0
Step 2: Generate initial population, p(t)
Step 3: Evaluate p(t) to create fitness values
Step 4: While (not termination condition) do:
Step 5: Recombine p(t) to yield ch(t), selecting from p(t) according to the fitness values.
Step 6: Evaluate ch(t)
Step 7: Generate p(t+1) from p(t) and ch(t)
Step 8: Set t:=t+1
Step 9: End
Step 10: Stop
p(t) : والدین در نسل t ام
ch(t) : نوزاد در نسل
t ام

و بالاخره شکل(2-7) تصویری نمادین از طرز کار الگوریتم ژنتیک را نشان می دهد.

شکل(2-7). تصویری نمادین از طرز کار الگوریتم ژنتیک

عملگرهای دیگری از جمله : نخبه گرایی166 ، معکوس سازی167 ، چیرگی168 ، تکرار درون کروموزوم169 و حذف170 نیز برای استفاده در الگوریتم های ژنتیک وجود دارند . همچنین مفاهیمی نظیر قلمروسازی171 و شراکت172 برای بهبود کارآیی الگوریتم های ژنتیک در بهینه سازی توابع چند کوهانه 173و نیز بهینه سازی چند هدفی ارائه شده است گلدبرگ(1989)]9[. با این وجود یک الگوریتم ژنتیک ساده شامل سه عملگر پایه : تولید مثل، ترکیب و جهش با یک تنظیم پارامتر مناسب می تواند تعدادی از مسائل مهم بهینه سازی را حل کند.

2-12- کاربرد الگوریتم های ژنتیک در بهینه سازی
برای حل یک مسئله بهینه سازی توسط الگوریتم های ژنتیک باید بتوان فضای جواب مسئله را با استفاده از یک نمایش کروموزومی پوشش داد. همچنین لازم است تابع هدف مسئله بهینه سازی به عنوان مبنای رتبه بندی و ارزیابی این کروموزوم ها قرار گیرد . بر این اساس عملا ” محدودیتی بر سر راه استفاده از الگوریتم های ژنتیک در حل مسائل بهینه سازی وجود ندارد. دجونگ (1975)]3[ با استفاده از ? تابع آزمایشی به بررسی کارآیی الگوریتم های ژنتیک در حل مسائل بهینه سازی پرداخت .
مسائل انتخابی وی به گونه ای بودند که ویژگی های زیر را در مسائل بهینه سازی پوشش می دادند:
پیوستگی و ناپیوستگی
محدب و نامحدب بودن
تک کوهانه و چند کوهانه بودن
کوادراتیک و غیر کوادراتیک بودن
کم بعد174 و پر بعد175 بودن
قطعی و احتمالی بودن
بر اساس تحقیقات دجونگ، الگوریتم ژنتیک در بهینه سازی توابع هموار تک کوهانه اولویت خاصی نسبت به سایر روشهای بهینه سازی ندارد . با این وجود در حالت کلی و در شرایطی که با توابع هدف غیر هموار و چند کوهانه سر و کار داشته باشیم، الگوریتم های ژنتیک عملکرد خوبی در بهینه سازی آنها از خود نشان داده اند گلدبرگ(1989) ]9[ .

2-12-1- استراتژی برخورد با محدودیت ها
بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد چگونگی برخورد با محدودیت های مساله می باشد زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزوم های غیرموجه می شود. چند تکنیک معمول جهت مواجهه با محدودیت، وجود دارد که در ادامه به چند تا از آنها اشاره می شود.

2-12-1-1- استراتژی اصلاح عملگرها176
یک روش برای جلوگیری از تولید کروموزوم غیر موجه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزوم ها، کروموزوم تولید شده نیز موجه باشد. همچنین می توان عملگرهای ترکیب و جهش را طوری طراحی کرد که احتمال زایش جواب های نشدنی از والدین شدنی به حداقل ممکن برسد (میخائیلویکس و جانیکو1991]26[). در این حالت یکسری مشکلات وجود دارد. مثلا پیدا کردن عملگری که دارای شرایط فوق باشد بسیار دشوار بوده و از مساله ای به مساله دیگر متفاوت می باشد. اگرچه این تکنیک روشی را برای هدایت فرآیند جستجو به سمت جواب های شدنی ارائه می نماید، هنگامی که آنها شناخته شده نیستند مقادیر جریمه های اعمال شده جهت اصلاح عملگرها بسیار وابسته به مسئله می باشد . ریچاردسون و همکاران (1989) ]31[
2-12-1-2- استراتژی ردی177
در این روش پس از تولید هر کروموزوم آن را از نظر موجه بودن تست کرده و در صورت غیرموجه بودن حذف می گردد. این روش بسیار ساده و کارا می باشد.

2-12-1-3- استراتژی اصلاحی178
در این روش به جای اینکه کروموزوم غیرموجه حذف گردد تبدیل به یک کروموزوم موجه می شود. این روش نیز مانند روش اول به مساله وابسته بوده و یافتن فر آیند اصلاح گاهی بسیار پیچیده می باشد.

2-12-1-4- استراتژی جریمه ای179
در این روش بر خلاف سه روش قبل که از ورود جواب های غیر موجه جلوگیری می کردند، جواب های غیر موجه با احتمال کم امکان حضور می یابند. ساده ترین راه برای اعمال محدودیت های مسئله در الگوریتم ژنتیک، تخصیص مقادیر کوچک شایستگی به جواب های نشدنی است گلدبرگ(1989)]9[. بدین ترتیب جواب های نشدنی خود به خود در فرآیند انتخاب حذف می شوند.
سه روش فوق دارای این اشکال بودند که به هیچ نقطه ای بیرون از فضای موجه توجه نمی کردند، اما در بعضی مسایل بهینه سازی جواب های غیر موجه درصد زیادی از جمعیت را اشغال می کنند. در چنین شرایطی اگر جستجو فقط در ناحیه موجه انجام گیرد شاید یافتن جواب موجه خیلی وقت گیر و مشکل باشد. استراتژی جریمه ای از متداول ترین تکنیک های مورد استفاده برای پذیرش با جواب های غیرموجه می باشد که در آن ابتدا محدودیت های مساله در نظر گرفته نمی شوند، سپس برای هر تخلف از محدودیت ها، یک جریمه اختصاص داده می شود که این جریمه در تابع هدف قرار می گیرد.

2-13- بهینه سازی چند هدفی با استفاده از الگوریتم های ژنتیک
در طی دو دهه گذشته، به الگوریتم های ژنتیک بخاطر پتانسیل بالای آن به عنوان یک رویکرد جدید به مسائل بهینه سازی چند هدفه که تحت عنوان روش های تکاملی یا بهینه سازی چند هدفه ژنتیک شناخته می شود، توجه خاصی شده است. ویژگی های ذاتی الگوریتم های ژنتیک بیانگر دلایل مناسب بودن جستجوی ژنتیک در مسائل بهینه سازی چند هدفه هستند. ویژگی های اصلی الگوریتم ژنتیک چند جهته بودن و جستجوی سراسری با حفظ جمعیتی از حل های خوب از نسلی به نسل دیگر است. ایده استفاده از الگوریتم های ژنتیک در یک مسئله چند معیاری در سال ???? توسط روزنبرگ در قالب استفاده از خ
واص چندگانه180 در جستجوی ژنتیک ارائه شد . با این وجود نخستین کاربرد عملی این پیشنهاد در سال ???? توسط شافر صورت گرفت گلدبرگ(1989)] 9[. الگوریتم ژنتیک معروفترین روش ابتکاری برای طراحی بهینه سازی مسائل چند هدفه می باشد. جانز و دوستان(2002)]20[ گزارش دادند که 90 درصد روشهای بهینه سازی چند هدفه در مسئله مورد نظرشان تقریبی از لبه بهینه پارتو را بدست می آورند. شافر(1985)]32[ در الگوریتم VEGA181 جامعه هر نسل را به زیرجامعه هایی با اندازه مساوی و به تعداد اهداف مسئله تقسیم نمود . در هر یک از این زیرجامعه ها یک هدف مستقلا ً مبنای انتخاب کروموزوم ها قرار می گیرد. پس از الگوریتم VEGA الگوریتم های ژنتیک دیگری نیز برای مسائل بهینه سازی چند هدفی توسعه یافته است. از جمله این الگوریتم ها می توان HLGA یا WBGA (هالجا و لین ???2]?7[)، FFGA (فانسکا و فلمینگ ???3]7[)، MOGA (فانسکا و فلمینگ (1995)]5[)، NPGA (هورن و نافپلیوتیس(1993)]13[ و (1994)]12[)،PAES (ناولز و کرن(1999)]22[)، NSGA وNSGA|| (اسرینیواس و دب (1995)]33[ و دب (2002)]4[) و SPEA و SPEA|| (زیتزیلر (1999)]37[ و زیتززیلر و دوستان (2001)]38[) ،MOGLS (جاسزکیویز (1998و2003)]18[و]17[)، RWGA (موراتا وایشیبوچی (1??5)]28[)،PESA (کرن و ناولز (2000)]2[)، RDGA (لو و ین (2003)]25[)،DMOEA (ین و لو (2003)]34[)، اشاره نمود. الگوریتم ژنتیک نیاز به مباحث ریاضی زیادی ندارد و میتواند انواع توابع هدف و محدودیت را پوشش دهد. بخاطر طبیعت تکاملی بودنش، الگوریتم های ژنتیک میتوانند برای جستجوی جواب ها بدون استفاده از ساختار ریاضیاتی مسئله بکار برده شود. بنابراین این امید را داریم که بسیاری از مسائل پیچیده با استفاده از الگوریتم های ژنتیک بجای استفاده از روش های مرسوم حل شوند. بدلیل اینکه الگوریتم ژنتیک، به عنوان یک متاهیورستیک، انعطاف پذیری زیادی برای استفاده از روش های مرسوم در چارچوب خود دارد، میتوانیم از مزایای الگوریتم ژنتیک و روش های مرسوم به صورت همزمان برای پیاده سازی کاراتر الگوریتم استفاده کنیم. افزایش مطالعات بکارگیری الگوریتم های ژنتیک در مسائل بهینه سازی چند هدفه و مباحث سخت تئوریک، چالش های عملی را در جوامع ریاضی مطرح کرده است. جدول (2-5) تعدادی از الگوریتم های ژنتیک چند هدفه مشهور با مزایا، معایب ومکانیسم های بکار گرفته شده در آنها را نشان می دهد.
جدول (2-5). الگوریتم های ژنتیک چند هدفه مشهور و ویژگیهای آنها

2-13-1- طراحی اصول واجزای الگوریتم ژنتیک چند هدفه
2-13-1-1- توابع هدف چندگانه
VEGA اولین الگوریتم ژنتیک بود که برای بدست آوردن تقریبی از مجموعه بهینه پارتو با استفاده از جوابهای غیر مسلط مورد استفاده قرار گرفت. در الگوریتم VEGA، جمعیت P_t بطور تصادفی به k زیر جمعیت ?P_1,P?_2 ?,?,P?_k ( برابر با تعداد هدفها) تقسیم می شود سپس ، به هر جواب واقع در زیر جمعیت P_i یک مقدار شایستگی با توجه به تابع هدف Z_i تخصیص می یابد. جوابها از این زیر جمعیت ها با گزینش متناسب برای تقاطع و جهش انتخاب می شوند عملگرهای تقاطع و جهش بر روی جمعیت جدی