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

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

وراثتی فرایند های تکراری هستند که هر مرحله تکراری را نسل و مجموعه ای از پاسخ ها در هر نسل را جمعیت می نامند.
الگوریتم های ژنتیک، جستجوی اصلی را در فضای پاسخ به اجرا می گذارند. این الگوریتم ها با تولید نسل آغاز می شوند که وظیفه ایجاد مجموعه نقاط جستجوی اولیه به نام جمعیت اولیه۵۲ را بر عهده دارند و به طور انتخابی یا تصادفی تعیین می شوند. از آنجا که الگوریتم ژنتیک برای هدایت عملیات جستجو به طرف نقطه بهینه از روش های آماری استفاده می کند، در فرایندی که به انتخاب طبیعی وابسته است، جمعیت موجود به تناسب برازندگی۵۳ افراد آن برای نسل بعد انتخاب می شود. سپس عملگرهای ژنتیکی شامل انتخاب۵۴، ترکیب۵۵، جهش۵۶ و دیگر عملگرهای احتمالی اعمال شده و جمعیت جدید بوجود می آید. پس از آن، جمعیت جدیدی جایگزین جمعیت پیشین می شود و این چرخه ادامه می یابد. معمولا جمعیت جدید برازندگی بیشتری دارد. این بدان معناست که از نسلی به نسل دیگر جمعیت بهبود می یابد. هنگامی جستجو نتیجه بخش خواهد بود که به حداکثر نسل ممکن رسیده باشیم یا همگرایی حاصل شده باشد یا معیارهای توقف برآورده شده باشد.
۲-۱۱-۳- عملگرهای الگوریتم ژنتیک
به طور خلاصه الگوریتم ژنتیک از عملگرهای زیر تشکیل شده است :
Encoding
این مرحله شاید مشکل ترین مرحله حل مسئله به روش الگوریتم ژنتیک باشد. الگوریتم ژنتیک به جای اینکه بر روی پارامترها یا متغیرهای مسئله کار کند با شکل کدشده آنها سر و کار دارد.
یکی از روش های کد کردن، کدکردن دودویی می باشد که در آن هدف تبدیل جواب مسئله به رشته ای از اعداد باینری است.
Evaluation
تابع برازندگی از اعمال تبدیل مناسب بر روی تابع هدف یعنی تابعی که قرار است بهینه شود بدست می آید. ایـن تابع هر رشته را با یک مقدار عددی ارزیابی می کند که کیفیت آن را مشخص می نماید. هر چه کیفیت رشته جواب بالاتر باشد مقدار برازندگی جواب بیشتر است و احتمال مشارکت برای تولید نسل بعدی نیز افزایش خواهد یافت.
Crossover
مهم ترین عملگر در الگوریتم ژنتیک، عملگر ترکیب است. ترکیب فرایندی است که در آن نسل قدیمی کروموزوم ها با یکدیگر مخلوط و ترکیب می شوند تا نسل های تازه ای از کروموزوم ها به وجود بیاید. جفت هایی که در قسمت انتخاب ، به عنوان والـد در نظر گرفته شدند ، در این قسمت ژن هایشان را با هم مبادله می کنند و اعضایی جدید به وجود می آورند. ترکیب در الگوریتم ژنتیک باعث از بین رفتن پراکندگی یا تنوع ژنتیکی جمعیت می شود زیرا اجازه می دهد ژن های خوب یکدیگر را بیابند.
Mutation
جهش نیز عملگر دیگری می باشد که جواب های ممکن دیگری را متولد می کند. در الگوریتم ژنتیک بعد از اینکه یک عضو در جمعیت جدید به وجود آمـد ، هر ژن آن با احتمال جهش ، جهش می یابد. در جهش ممکن است ژنی از مجموعه ژن های جمعیت حذف شود یا ژنی که تا به حال در جمعیت وجود نداشته است به آن اضافه شود. جهش یک ژن به معنای تغییر آن ژن است و وابسته به نوع کدگذاری، از روش های متفاوت جهش استفاده می شود.

Decoding
عکس عمل Encoding است. در این مرحله بعد از اینکه الگوریتم بهترین جواب را برای مسئله ارائه کرد لازم است عکس عمل کدگذاری روی جواب ها اعمال شود تا بتوانیم نسخه واقعی جواب را در دست داشته باشیم.
نحوه کلی عملکرد الگوریتم های ژنتیک مطابق با چرخه زیر می باشد :
ابتدا کلیه افراد موجود در جمعیت ارزیابی می شوند. سپس افراد جدید با استفاده از عملگر های تلفیق و جهش تولید می شوند و افراد قدیمی و تکراری از جمعیت جدید حذف می گردند. یک تکرار از حلقه یاد شده تحت عنوان ایجاد یک نسل شناخته می شود. اولین نسل (نسل ف ) از این فرایند به صورت تصادفی ایجاد شده و سپس عملگرهای ژنتیک با اندازه گیری میزان برازندگی آنها جمعیت را از نظر کارایی برای حل مسئله مورد ارزیابی قرار می دهند. در اینجا الگوریتم ژنتیک به صورت شبه کد بیان شده است :
PSEUDO CODE of GA
t := t; // start with an initial time
intpopulation p(t) ; //initialize a usually random population of individuals
evaluate p(t) ; // evaluate fitness of all initial individuals of population
while ( not down ) do // test for termination criterion ( time, fitness, etc.)
t := t+t; // increase the time counter
p’ : = select parents p(t) ; // select a sub-population for offspring production
recombine p’(t) ; // recombine the “genes” of selected parents
mutate p’(t) ; // perturb the mated population stochastically
evaluatep,p’(t) ; // evaluate it’s new fitness
p : = survive p,p’(t) ; // select the survivors from actual fitness
end GA.

شکل ۲-۲ دیاگرام بلوکی الگوریتم ژنتیک ساده[۳]
۲-۱۱-۴- کد کردن۵۷
الگوریتم ژنتیک به جای اینکه بر روی پارامترها یا متغیرهای مسئله کار کند، با شکل کدشده آنها سر و کار دارد. یکی از روش های کد کردن، کد کردن دودویی می باشد که در آن هدف تبدیل جواب مسئله به رشته ای از اعداد باینری است. تعداد بیت هایی که برای کدگذاری متغیرها استفاده می شود به دقت مورد نظر برای جواب ها، محدوده تغییر پارامترها و رابطه بین متغیرها وابسته است. رشته یا دنباله ای از بیت ها که به عنوان شکل کد شده یک جواب از مسئله مورد نظر می باشد، کروموزوم نامیده می شود. در حقیقت بیت های یـک کروموزوم ، نقش ژن ها در طبیعت را بـازی می کنند. یکی از ویژگی های اصلی الگوریتم ژنتیک آن است که به طور متناوب بر روی فضای کدینگ و فضای جواب کار می کند. عملگرهای ژنتیک بر روی فضای کدینگ یا کروموزوم ها اعمال شده، در حالی که انتخاب و ارزیابی بر روی فضای جواب عمل می نماید. در طبیعت نیز به همین شکل است یعنی افراد (کروموزوم ها) در یک فضای حقیقی غ
یر کدشده در حالت فنوتیپ حضور دارند. در صورت کد شدن با هر مکانیسمی حالت ژنوتیپ خود را بروز می دهند.
کدگذاری باینری :
این تبدیل، تبدیل استاندارد در الگوریتم های ژنتیک می باشد. کدگذاری باینری ساده ترین کدگذاری و بهترین تبدیل برای عملگرهای ژنتیک است اما در مسائل پیچیده این نوع تبدیل چندان مناسب نیست چون معمولا باعث می شود طول کروموزوم ها برای نگهداری اطلاعات پاسخ، بسیار بزرگ شود.
کدگذاری جایگشتی :
در بسیاری از مسائـل مانند مسئله فروشنده دوره گرد ، با جایگشت های مختلفی از مجموعه راه ها روبرو هستیم. در این مسئله تعدادی شهر داریم که فاصله میان آنها معلوم است و با شروع از یک شهر و ختم به همان شهر بایستی از تمام شهرها فقط و فقط یکبار عبور نماییم و کمترین مسافت ممکن را طی کنیم. نکته ای که در اینجا مهم است و باعث شده تا کدینگ باینری روش مناسبی برای این مسئله نباشد، این است که حتما باید برش میان دو والد به نحوی صورت بگیرد که هیچ عنصر تکراری وجود نداشته باشد.
کدگذاری مقدار :
تمامی مکانیسم های برش مانند حالت باینری، استفاده می شود. برای عملگر جهش نیز مانند زیر عمل می شود :
(۱.۲۹ ۵.۶۸ ۲.۸۶ ۴.۱۱ ۵.۵۵ ) ⇒ (۱.۲۹ ۵.۶۸ ۲.۷۳ ۴.۲۲ ۵.۵۵)

یعنی به بعضی از ژن ها بطور تصادفی عددی اضافه شده یا از آنها کم می گردد.
۲-۱۱-۵- ایجاد جمعیت اولیه
پس از تعیین سیستم کدینگ و مشخص شدن روش تبدیل هر جواب به کروموزوم، باید یک جمعیت اولیه از کروموزوم ها تولید نمود. در اکثر موارد ، جمعیت اولیه بـه صورت تصادفی تولید می شود. اما گاهی اوقات برای بالا بردن سرعت و کیفیت الگوریتم از روش های ابتکاری نیز برای تولید جمعیت اولیه استفاده می گردد. در هر صورت عمومی ترین و راحت ترین روش، استفاده از یک رویکرد تصادفی می باشد. اندازه جمعیت اولیه معمولا به طول رشته کد شده وابسته است. به عنوان مثال اگر کروموزوم ها در یک مسئله ۳۲ بیتی هستند قطعا باید جمعیت انتخابی اولیه بیشتر از حالتی باشد که کروموزوم ها به عنوان مثال ۱۶ بیتی هستند. آنگاه به کروموزوم های انتخاب شده با توجه به یک تابع برازش، مقداری حقیقی که نشان دهنده ارزش آنها است تخصیص داده می شود و مراحل الگوریتم های ژنتیک ادامه می یابد.
اندازه ی جمعیت
گلدبرگ برای محاسبه بهترین اندازه جمعیت برای کدهای دودویی متغیرهای پیوسته تا طول حداکثر ۶۰ رشته مقدار زیر را پیشنهاد می کند :
N_pop=====×〖〖〖〗^((“((((” ×Lc))
Lc بیانگر طول کروموزوم می باشد. اگر تعداد کروموزوم ها بسیار کم باشد GA امکان انجام عمل ترکیب کمتری خواهد داشت و تنها بخشی کوچک از فضای جستجو کشف خواهد شد. از طرفی دیگر، اگر تعداد کروموزوم ها بسیار زیاد باشد روند GA کند خواهد بود. بررسی نشان داده است که در نتیجه برخی محدودیت ها (که عمدتا به کدگذاری و خود مسئله بستگی دارد) استفاده از جمعیت زیاد، ثمربخش نخواهد بود زیرا این کار، مسئله را سریعتر از حالتی که جمعیتی متوسط استفاده شود، حل نخواهد کرد[۲۲].
در صورتی که تعداد اعضای جمعیت بسیار زیاد باشد، اگرچه وضعیت جستجو ممکن است به صورت بهتری نمایش داده شود زیرا با افزایش تعداد رشته ها، انتخاب رشته بهتر امکان پذیر می شود ولی از طرفی نیازمندی های حافظه کامپیوتر و زمان اجرای آن زیاد می شود. اگر تعداد اعضای جمعیت نیز کوچک تر از حد مشخصی باشد، جمعیت مورد نظر فقط قسمت کوچکی از فضای جستجو را نشان می دهـد و ممکن است جستجو برای رسیدن بـه حل بهینه در ایـن جمعیت موفقیت آمیز نباشد یا مستلزم صرف زمان زیادی باشد. در عمل تعداد اعضای جمعیت مقداری است که به صورت تجربی به دست آمده و نشان داده شده است که با این تعداد رشته در جمعیت می توان به حل های مناسبی دست یافت. این تعداد ۲ الی ۲.۵ برابر طول هر رشته می باشد.
۲-۱۱-۶- تابع برازندگی۵۸
تابع برازندگی نوع خاصی از تابع هدف۵۹ است که در الگوریتم های تکاملی، کیفیت بهینه سازی را برای یک راه حل اندازه گیری می کند. یک راه حل در این الگوریتم ها در قالب یک کروموزوم بیان می شود. به کمک تابع برازندگی یک کروموزوم با بقیه کروموزوم ها مقایسه می گردد. کروموزوم های بهینه یا کروموزوم هایی که برازندگی بیشتری دارند، فرصت می یابند تا از طریق تکنیک های مختلف با هم ترکیب شده و نسل جدید و بهتری ایجاد نمایند.
تعریف تابع برازندگی با توجه به تعریف مسئله انجام می شود، تابع برازندگی کروموزوم ها را در قالب ساختار فیزیکی تفسیر کرده و میزان برازندگی آن را اندازه گیری می کند. در واقع تابع برازندگی یک معیار مناسب برای انتخاب کروموزوم ها ایجاد می کند.
۲-۱۱-۷- انتخاب
در مرحله انتخاب، یک جفت از کروموزوم ها برگزیده می شوند تا با هم ترکیب شوند. عملگر انتخاب رابط بین دو نسل است و بعضی از اعضای نسل کنونی را به آینده منتقل می کند. بعد از انتخاب، عملگرهای ژنتیک روی دو عضو برگزیده اعمال می شوند. معیار در انتخاب اعضا، ارزش تطابق آنها می باشد اما روند انتخاب حالتی تصادفی دارد.
شاید انتخاب مستقیم و ترتیبی به این شکل که بهترین اعضا دو به دو انتخاب شوند، در نگاه اول روش مناسبی به نظر برسد اما باید به نکته ای توجه داشت که ما در الگوریتم ژنتیک با ژن ها روبرو هستیم. یک عضو با برازندگی پایین اگرچه در نسل خودش عضو مناسبی نمی باشد اما ممکن است شامل ژن های خوبـی باشد و اگر شـانس انتخاب شدنش صفر باشـد ، ایـن ژن های خوب نمی توانند به نسل های بعد منتقل شوند. پس روش انتخاب باید به گو
نه ای باشد که به این عضو نیز شانس انتخاب شدن بدهد. راه حل مناسب، طراحی روش انتخاب به گونه ای است که احتمال انتخاب شدن اعضای با برازندگی بالاتر بیشتر باشد. انتخاب باید به گونه ای صورت بگیرد که تا جایی که ممکن است هر نسل جدید نسبت به نسل قبلی اش برازندگی میانگین بهتری داشته باشد. روش های مختلفی برای انتخاب کروموزوم ها و ادغام آنها وجود دارد که مهم ترین این روش ها عبارتند از :
۱- روش چرخ رولت۶۰
۲- روش بولتزمن۶۱
۳- روش مسابقه ای۶۲
۴- روش رتبه بندی۶۳
۵- روش حالت پایدار۶۴
روش چرخ رولت
ساده تـرین راه بـرای انتخاب ، انتخاب بـه روش چرخ رولت می باشد. ایـن روش یـک نمونـه برداری شانسی با جایگزینی است. این روش مبتنی بر شانس به این صورت انجام می شود که کلیه افراد بر مبنای میزان برازندگی خود بر روی نواحی همجوار یک خط نگاشت می شوند. اندازه ناحیه مربوط به هر فرد با توجه به اندازه برازندگی آن تعیین می شود. سپس یک عدد تصادفی تولید شده و با توجه به اندازه این عدد، فرد انتخاب می شود. این فرایند آنقدر تکرار می شود تا اینکه تعداد مورد نظر والدین (جمعیت تولید مثلی) تأمین گردد. می توان به جای خط از یک دایره به این منظور استفاده نمود.
انتخاب چرخ رولت که اولین بار توسط هالند پیشنهاد شد یکی از مناسب ترین انتخاب های تصادفی بوده که ایده آن، احتمال انتخاب می باشد. احتمال انتخاب متناظر با هر کروموزوم، بر اساس برازندگی آن محاسبه شده که اگر f_k مقدار برازندگی کروموزوم k ام باشد، احتمال بقای متناظر با آن کروموزوم عبارت است از :
P_k=f_k/(∑_(i=”(” )^n▒f_i )
حال کروموزوم ها را بر اساس P_k مرتب کرده و q_k که همان مقادیر تجمعی P_k می باشد به صورت زیر بدست می آید :
q_k=∑_(i=”_” )^k▒P_i
چرخ رولت به این صورت عمل می کند که برای انتخاب هر کروموزوم یک عدد تصادفی بین صفر و یک تولید کرده و عدد مذکور در هـر بازه ای قرار گرفت ، کروموزوم متناظر بـا آن انتخاب می شود. البته روش پیاده کردن چرخ رولت به این شکل است که یک دایره در نظر گرفته و آن را به تعداد کروموزوم ها طوری تقسیم می کنیم

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *