تحقیق رایگان درمورد الگوریتم ژنتیک، فرآیند ارزیابی، انتخاب طبیعی

دانلود پایان نامه ارشد

موازی نامرتبط با فرض وجود دوبارهکاری که در آن به دنبال کمینهکردن بیشینه زمان تکمیل کارها میباشیم نیز در دسته مسائل Strongly NP-hard طبقهبندی میشود. از این روی، حل این مسئله برای اندازههای متوسط و بزرگ با استفاده از الگوریتمهای بهینهسازی دقیق در یک زمان محاسباتی معقول امکانپذیر نیست. از پرکاربردترین روشهای موجود بهمنظور حل مسائل در یک زمان محاسباتی موجه میتوان به الگوریتمهای فراابتکاری اشاره کرد که نسل جدیدی از الگوریتمهای تقریبی بر مبنای بکارگیری روشهای ابتکاری برگرفته از رویکردهای جستجوی موضعی و ساختاری بهمنظور جستجوی کارا و اثربخش فضای جستجو میباشند و از مهمترین ویژگی آنها میتوان به بکارگیری استراتژیهای جستجوی منحصربفرد بهمنظور اجتناب از قرارگیری در دام جوابهای بهینه محلی اشاره کرد.
در ادامه این فصل به تشریح مبانی الگوریتمهای فراابتکاری بکار رفته در تحقیق پیش رو شامل الگوریتمهای ژنتیک و زنبور عسل پرداخته میشود.

3-6. الگوریتم ژنتیک
الگوریتمهای تکاملی بهعنوان دستهای از الگوریتمهای بهینهسازی محسوب میشوند که مبنای تصادفی دارند و در بیشتر موارد، برای جستجوی نقطه بهینه سراسری118 در فضای پیچیده و بزرگ، مناسب میباشند و کمتر در نقطه بهینه محلی119 گرفتار میشوند. علم وراثت شاخهای از زیست شناسی است که به بحث درباره وراثت و تنوع جانداران میپردازد. هر موجود زنده در یکایک سلولهای خود دارای نوعی ماده ژنتیکی است که از والدین خود به ارث برده است. واحدهای وراثتی در این ماده که از نسلی به نسل دیگر انتقال مییابند (به ارث میرسند) ژن120 نامیده میشوند. این ماده ژنتیکی از کروموزومهایی تشکیل شده که در هسته سلول قرار دارند.
همانطور که میدانیم کروموزوم فرزند از ترکیب کروموزومهای متناظر والدینش بوجود میآید به همین دلیل فرزند حاصل بعضی از ویژگیهای پدر و بعضی از ویژگیهای مادر خود را به ارث میبرد. این احتمال نیز وجود دارد که طی پروسه تولید مثل در اثر خطایی در در کپی برداری از کروموزومها، ژنی از کروموزومها دستخوش تغییر شود که احتمالا باعث بروز یا حذف یک ویژگی خاص در موجود مورد نظر خواهد شد. چنین رخدادی را به اصطلاح جهش121 مینامند.
از میان افراد یک جمعیت از موجودات هم نوع، افراد برازنده تر به تعداد بیشتری میتوانند رشد کنند و فرزندان بیشتری نیز به وجود آورند که این فرزندان، اغلب قابلیت والدینشان را به ارث میبرند. بنابراین در طول نسلها گونههای برازندهتر بقا مییابند و آنها که ضعیفترند منقرض میشوند. این پروسه در طول قرنهای متمادی باعث بروز نوعی تکامل در موجودات میگردد. اکنون زمان آن فرا رسیده است که به تشابه بین پروسه تکامل و الگوریتمهای بهینه سازی توجه کنیم. اگر یک موجود را سیستمی در نظر بگیریم که ویژگیهای آن موجود پارامترهای آن سیستم مورد نظر باشد، پدیده تکامل همانند یک الگوریتم بهینهسازی، بهترین ترکیب از آن ویژگیها را برای موجود فراهم میآورد.

3-6-1. تاریخچه الگوریتم ژنتیک
از سال 1960 تقلید از پدیدههای طبیعی برای استفاده در الگوریتمهای قوی جهت حل مسائل مشکل بهینهسازی مورد توجه قرار گرفت که تکنیکهای الگوریتمهای تکاملی122 نام گرفتند. الگوریتم ژنتیک که اولین بار توسط جان هالند ]68[، در دانشگاه میشیگان پیشنهاد شد و استراتژیها و برنامهریزیهای تکاملی که توسط رچنبرگ123 و چیفل124 و فوگوگل125 و کوزا126 ایجاد شدند، از جمله روشهای محاسبه تکاملی هستند. ابتدا توسط هالند یک مفهوم اولیه از الگوریتم ژنتیک ارائه شد و سپس گلدبرگ ]69[، آن را توصیف کرد.
روشهای بهینهسازی الهام گرفته از طبیعت با روشهای متعارف بهینهسازی تفاوت مهمی دارند. در روشهای متعارف، هر جواب کاندیدای جدید در صورتی بهعنوان جواب جدید انتخاب میشود که مقدار تابع هدف را بهبود بخشد ولی در الگوریتمهای الهام گرفته از طبیعت به تمام جوابهای کاندیدای جدید شانس انتخاب داده میشود. الگوریتم ژنتیک یکی از مهمترین الگوریتمهای فراابتکاری میباشد که از آن برای بهینهسازی توابع مختلف استفاده میشود. در این الگوریتم اطلاعات گذشته با توجه به موروثی بودن الگوریتم استخراج شده و در روند جستجو مورد استفاده قرار میگیرد.
الگوریتم ژنتیک از روشهای فراابتکاری الهام گرفته از طبیعت میباشد و در واقع یکی از تکنیکهای جستجو تصادفی میباشد که بر اساس انتخاب طبیعی و نسل شناسی طبیعی کار میکند. این الگوریتم دارای تفاوت اساسی با دیگر روشهای متداول بهینهسازی است که گلدبرگ این تفاوت را به صورت زیر بیان کرده است ]69[.
الگوریتم ژنتیک با مجموعهای از جوابهای کد گذاری شده کار میکند نه با خود آنها.
الگوریتم ژنتیک در یک جمعیت از جوابها و یا مجموعهای از آنها شروع به جستجو میکند نه با یک جواب و در واقع با کل جامعه کار میکند نه با یک فرد جامعه (یک تعداد زیادی از مجموعه جواب را بصورت موازی پیش میبرد).
الگوریتم ژنتیک از اطلاعات تابع برازش استفاده میکند نه از مشتقها یا علوم کمکی دیگر.
الگوریتم ژنتیک از قواعد مبتنی بر احتمال استفاده میکند و نه از قواعد قطعی.
3-6-2. واژگان ژنتیک
از آنجا که الگوریتم ژنتیک از هر دو علم کامپیوتر و ژنتیک طبیعی نشأت گرفته است واژههای مورد استفاده در آن مخلوطی از واژههای طبیعی و مصنوعی است.
مفاهیم اولیه که در فهم الگوریتم ژنتیک بسیار موثر هستند عبارتند از :
کروموزوم127: اساس الگوریتم ژنتیک تبدیل هر مجموعه جواب به یک مجموعه کدگذاری شده است. این کد را اصطلاحا کروموزوم گویند. به هر کروموزوم، فرد128، رشته129 و ساختار130 نیز گفته میشود. همچنین میتوان آنها را ژنوتیپ131 نامید.
فنوتیپ132 : هر کروموزوم متناظر با یک مجموعه جواب از مسئله است. مجموعه متناظر با هر کروموزوم را یک فنوتیپ میگویند. عناصر تشکیل دهنده یک کروموزوم که معمولا اعداد هستند را ژن میگویند. ژنها را رمزگشا133 نامیدهاند.

شکل 3-8 .مقایسه فضاهای ژنوتیپ و فنوتیپ

مکان: محل قرار گرفتن ژن در کروموزوم را یک مکان میگویند.
جمعیت134: مجموعهای از کروموزومها را یک جمعیت میگویند.
نسل135: هر تکرار136 را یک نسل میگویند.
3-6-3. ساختار الگوریتم ژنتیک
ابتدا پیش از هر مسئله باید مکانیزمی برای تبدیل جواب مسئله به یک کروموزوم پیدا کنیم. برای یافتن کروموزوم مورد نظر از روشهای کدگذاری استفاده میکنیم. سپس یک مجموعه از کروموزومها به عنوان جمعیت آغازین تهیه میگردند که تعداد آنها توسط کاربر تعریف میشود و اغلب به صورت تصادفی هستند. بعد از این مرحله باید به کمک عملگرهای ژنتیکی که به دو دسته عمده عملگر تقاطعی و عملگر جهشی تقسیم میشوند اقدام به ایجاد کروموزومهای جدید موسوم به فرزند کرد. برای انتخاب کروموزومهایی که باید نقش والدین را ایفا کنند از دو مفهوم نرخ تقاطعی و نرخ جهشی استفاده میشود که میزان آنها توسط کاربر تعیین میشود. بعد از تولید یک سری کروموزوم جدید، باید با استفاده از عمل تحول اقدام به انتخاب برازندهترین کروموزومها نمود. این فرآیند که در فرآیند انتخاب نمود مییابد گلچین کردن کروموزومهای برازنده در میان فرزندان است بهطوری که تعداد کروموزومهای منتخب برابر با اندازه جمعیت اولیه باشد. فرآیند انتخاب مبتنی بر مقدار برازندگی است. در حقیقت فرآیند ارزیابی، محوریترین بحث در فرآیند انتخاب است.
تا به اینجا یک تکرار یا یک نسل از الگوریتم طی شده است. الگوریتم بعد از طی چندین نسل به تدریج به سمت جواب بهینه همگرا میشود. شرط توقف مسئله طی کردن تعداد معینی تکرار و یا طی شدن زمان تعیین شده میباشد که پیش از آغاز الگوریتم توسط کاربر تعیین میشود. در زیر الگوریتم ژنتیک در حالت کلی آورده شده است :
1. Initialization
1-1. Parameter setting (Pc, Pm, Stop Criteria, Pop Size, Selection Strategy, Crossover Operator, Mutation Operator, Perform, Scalability, Number of Generation)
1-2. Initialize Population (Randomly)
2. Fitness Evaluation
Repeat
3. Individual Selection for Mating Pool
(Size of Mating Pool = Pop Size)
4. For each consecutive pair apply crossover
(For each consecutive pair apply Crossover with probability Pc)
5. Mutate children
(For each new-born apply mutation with probability pm)
6. Replace the Current Population by the resulting Mating Pool
7. Fitness Evaluation
Until Stopping Criteria is met
3-6-4. کدگذاری
همانطور که در بخش قبل عنوان شد اولین گام در بکارگیری و پیادهسازی یک الگوریتم نمایش جوابهای مسئله بصورت یک کروموزوم است. در حقیقت این عمل یک مفهوم کلیدی در الگوریتم ژنتیک میباشد. یکی از ویژگیهای اصلی الگوریتم ژنتیک آن است که به طور متناوب بر روی فضای کدینگ و فضای جواب کار میکند. عملیات ژنتیک بر روی فضای کدینگ یا کروموزوم اعمال میشود در حالیکه انتخاب و ارزیابی بر روی فضای جواب عمل مینماید]69[.
هنگام استفاده از کدینگ با سه مفهوم اساسی زیر روبرو هستیم :
قانونمند بودن کروموزوم137
موجه بودن کروموزوم138
منحصر به فرد بودن ترسیم139
قانونمندی کروموزوم مربوط به زمان بکارگیری عملیات ژنتیک میباشد. یعنی گاهی اوقات ممکن است کروموزومهایی تولید شوند که با هیچ عضوی از فضای جواب متناظر نباشند. موجه بودن یک کروموزوم مربوط به حالتی است که بعد از رمز گشایی، همه محدودیتهای مسئله را ارضا میکند، در غیر اینصورت کروموزوم غیر موجه خواهد بود.

شکل 3-9. فضای موجه، ناموجه و غیرقانونی
انواع ارتباط بین فضای کدینگ و فضای جواب به صورتهای زیر میباشد:
ترسیم 1 به 1
ترسیم n به 1
ترسیم 1 به n
اولین و سومین ترسیم بهترتیب بهترین و ناخوشایندترین حالت میباشند]69[. مهم ترین اجزای GA در عمل به 5 مرحله تقسیم می شود، که عبارتند از:
جمعیت اولیه
نحوه نمایش
تطبیق تابع برازش و بدست آوردن برازندگی هر جواب
انتخاب استراتژی
اپراتورهای ژنتیک
3-6-5. ایجاد جمعیت اولیه
اولین مرحله بعد از تعیین تکنیکی که برای تبدیل هر جواب به یک کروموزوم بکار میرود ایجاد یک جمعیت اولیه از کروموزومهاست. در این مرحله جواب اولیه معمولا به صورت تصادفی تولید میشود. البته در بعضی موارد با توجه به نوع مسئله و برای بالا بردن سرعت همگرایی الگوریتم از روشهای ابتکاری نیز استفاده گردیده است.
به طور کلی بعضی از محققین همچون ریوز140، اسمیت141 و کاپاسالیس142 مفهوم بذر افشانی143 را ارائه کردهاند. آنها پیشنهاد کردهاند که بهجای استفاده از یک رویکرد تصادفی در ایجاد جمعیت اولیه، از جوابهای حاصله از دیگر الگوریتمهای ابتکاری استفاده شود. به هر حال عمومیترین و فراگیرترین روش، استفاده از یک رویکرد تصادفی است.
3-6-6. اعمال ژنتیک
عملیات ژنتیک فرآیند انتقال موروثی ژنها را برای ایجاد اولاد جدید در هر نسل تقلید میکنند. یک بخش مهم در الگوریتم ژنتیک ایجاد کروموزومهای جدید موسوم به فرزندان144 از طریق بعضی کروموزومهای قدیم موسوم به والدین145 است. این فرآیند مهم توسط عملیات ژنتیک صورت میگیرد. به طور کلی این عملیات توسط دو عملگر عمده انجام میشود؛ عملگر جهشی و عملگر تقاطعی.
اما عملا انتخاب عملگرها بر حسب نوع مسئله تعریف شده و کاملا به توانایی تحلیل گر وابسته بوده و تجربی میباشند. کارایی این عملگرها در رسیدن به جواب بهینه در مسائل مختلف متفاوت است. بعضی از عملگرها فقط یک کروموزوم را در نظر گرفته و بر اساس اطلاعات آن، کروموزوم جدید ایجاد میکنند اما بعضی دیگر روی چند کروموزوم یا حتی روی کلیه کروموزومهای جمعیت قبل، عملیات انجام میدهند. به هر حال عملگرها بر اساس نحوه کار به صورت زیر دسته بندی میشوند:
3-6-6-1. عملگرهای تقاطعی146
عملگرهایی که یک یا چند نقطه از دو یا چند جواب را انتخاب و مقادیر آن را تعویض میکنند. این عملگرها یک جواب را در نظر گرفته و محلهایی از جواب را با جوابهای دیگر

پایان نامه
Previous Entries تحقیق رایگان درمورد سلسله مراتب، تحلیل حساسیت، نظریه پیچیدگی Next Entries تحقیق رایگان درمورد كروموزوم، تقسيم، میکنیم.