SI: Swarm Intelligence

پیاده سازی حل مسئله تساوی ساده ریاضی به کمک الگوریتم ژنتیک در نرم افزار متلب

پیاده سازی حل مسئله تساوی ساده ریاضی به کمک الگوریتم ژنتیک در نرم افزار متلب

بیان مسئله:

فرض کنید تساوی a+2b+3c+4d=30 برقرار باشد با استفاده از الگوریتم ژنتیک مقادیر a,b,c,d به گونه ای  تعیین شود که تساوی برقرار باشد. در ابتدا باید تابع هدف فرمول بندی شود. که در این مثال هدف مینیم کردن تابع f(x)=a+2b+3c+4d-30 می باشد. چون چهار متغیر در معادله وجود دارد می توان کروموزوم را به شکل 1 ایجاد کرد. در ادامه هر کدام از مراحل الگوریتم ژنتیک همراه با کد آورده شده است.

 

شکل 1: تشکیل کروموزوم برای معادله ریاضی f(x) با چهار متغیر

پیاده سازی تابع هدف به کمک فایل Fchromosome :

همان طور که در کد ذیل آورده شده است کروموزوم ها یا همان راه حل ها را از تابع اصلی به عنوان ورودی دریافت می کند. و سپس تابع هدف به کمک ژن ها در این مثال متغیرهای a,b,c,d به تعداد 6 کروموزوم بدست می آید. و در انتها یک آرایه یک بعدی سطری با 6 عنصر به عنوان جواب هر کرموزوم به تابع اصلی به عنوان خروجی برگردانده می شود.


پیاده سازی عملگر انتخاب به کمک فایل Fselectmath1 :

از بین راه حل هایی که در هر جمعیت تولید شده است باید والدین با شانس بیشتر انتخاب گردد. بدین منظور کروموزوم ها یا راه حل های یک جمعیت و مقدار تابع هدف هر راه حل به عنوان ورودی به تابع Fselectmath1 داده می شود. پس از بدست آوردن احتمال انتخاب هر راه حل و میزان Fitness و مجموع کل یا Total به کمک جمع تجمعی و از روی چرخه رولت newchromosome ها انتخاب می شوند. Newchromosome,Pr,Fitness,Total به عنوان خروجی به تابع اصلی برگردانده می شود.


پیاده سازی عملگر تقاطع به کمک فایل Fcrossmath1 :

 

پس از انتخاب والدین با شایستگی بیشتر حال نوبت به استفاده از عملگر تقاطع رسیده است. میزان نرخ تقاطع یعنی cross_rate و راه حل های یک جمعیت که در آن والدین با شایستگی بیشتر انتخاب شده است به عنوان newchromosome از تابع اصلی دریافت می شود. در این مثال از تقاطع تک نقطه ای استفاده شده است که در آن به صورت تصادفی محل تقاطع انتخاب شده و از همان نقطه و به تعداد cross_rate کروموزوم عملگر تقاطع اعمال می گردد. در نهایت راه حل های جدید پس از اعمال تقاطع و تعداد انتخاب کروموزوم به عنوان خروجی به تابع اصلی برگردانده می شود.


پیاده سازی عملگر جهش به کمک تابع Fmutationmath1 :

پس از عملیات تقاطع باید از عملگر جهش استفاده شود. در این عملگر mutation_rate به عنوان نرخ جهش و newchromosome1 به عنوان جمعیتی که روی آن عملگر تقاطع رخ داده است به عنوان دو ورودی تابع Fmutationmath1 محسوب می شود. در این تابع از روی تعداد ژن ها و انتخاب ژن به تعداد mutation_rate روی این ژن های انتخاب شده عملیات جهش صورت می گیرد. در این مثال عملیات جهش با انتخاب مقدار ژن تصادفی بین 0 تا 30 برای هر ژن محقق می شود. در نهایت newchromosome2 به عنوان جمعیت جدید پس از جهش، Rmutation جایگاه ژنی که می خواهد جهش روی آن رخ دهد و x مقادیر جدید ژن های با موقعیت Rmutation به عنوان خروجی به تابع اصلی برگردانده می شود.


پیاده سازی تابع اصلی حل مسئله تساوی ساده ریاضی به کمک تابع math1:

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


پس از این عملیات و پایان تعداد تکرار با بدست آوردن میانگین راه حل های یک جمعیت و میزان تکرار به عنوان محور افقی یک نمودار به صورت شکل 2 بدست می آید. که در آن میزان بهبود یا عدم بهبود هر جمعیت در هر تکرار به نمایش در آمده است.

 

شکل 2: نمودار میانگین راه حل های هر جمعیت و تعداد تکرار در الگوریتم ژنتیک برای حل مسئله ساده ریاضی

کد متلب این مسئله به کمک الگوریتم ژنتیک در لینک

http://cdn.persiangig.com/download/BZV6MnGYOW/programming.rar/dl

قابل دریافت می باشد.

[1]. http://cdn.persiangig.com/download/2wctetN12Z/1_GA.pdf/dl.