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

[M!Zare 48,037]

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

 

الگوریتم ژنتیک برای حل مسائل از سه قانون اصلی پیروی می کند.

 

قوانین انتخاب: با این قوانین افراد برای تولید نسل بعدی انتخاب می شوند.

 

قوانین تلفیق: این قوانین دو والد را با هم تلفیق کرده و فرزندان که نسل بعدی می شوند را ایجاد می کند.

 

قوانین جهش: یک تغییر تصادفی بر روی افراد ایجاد می کند و افراد جدیدی را در جمعیت تولید می کند.

[M!Zare 48,037]

برخی از اصطلاحات مورد استفاده در الگوریتم ژنتیک

 

تابع شایستگی

 

همان تابع هدف است که ما قصد بهینه کردن آن را داریم و می توان در یک M-File نوشت و به عنوان آرگومان ورودی به GA فراخوانی کرد.

 

افراد

 

هر نقطه ای که بتوان به تابع شایستگی داد یک فرد است. مقدار تابع شایستگی به ازای آن فرد، امتیاز آن فرد می شود.

به عنوان مثال اگر تابع شایستگی بدین صورت باشد:

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

بردار(2و3و1) یک فرد حساب می شود و امتیاز این فرد 178 است.

 

گاهی اوقات از فرد به عنوان ژنوم و بردار فرد به عنوان ژن یاد می شود.

[M!Zare 48,037]

جمعیت و نسل

 

یک آرایه از افراد جمعیت را تشکیل می دهد. فرض کنیم که اندازه جمعیت 100 است و تابع شایستگی چهار متغیر داره، بنابراین ماتریس جمعیت یک ماتریس 4*100 خواهد بود.

یک فرد می تواند بیش از یک سطر در ماتریس جمعیت تکرار شود.

 

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

 

 

گوناگونی

 

میانگین فاصله افراد در یک جمعیت را گوناگونی گویند. اگر جمعیت دارای گوناگونی بالایی باشد ، میانگین فاصله زیاد می شود و اگر میانگین فاصله کم باشد، جمعیت گوناگونی پایینی دارد.

[M!Zare 48,037]

گوناگونی در متلب بسیار حائز اهمیت است و هر چه بیشتر باشد بدین مفهوم است که الگوریتم ناحیه بزرگتری را مورد جستجو و قرار می دهد.

 

 

میزان شایستگی و بهترین میزان شایستگی

 

مقدار شایستگی یک فرد، مقدار تابع شایستگی به ازای آن فرد است.

جعبه ابزار ga مقدار کمینه تابع را نشان می دهد و بهترین میزان شایستگی کمترین مقدار شایستگی به دست آمده به ازای افراد مختلف است.

[M!Zare 48,037]

والدین و فرزندان

 

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

[M!Zare 48,037]

نحوه عملکرد الگوریتم

 

1- ابتدا با یک جمعیت آغازین تصادفی الگوریتم شروع میشود.

 

2- در ادامه الگوریتم یک جمعیت جدید (نسل) ایجاد میکند و در هر سری نسل ها بهبود می یابد. روند ایجاد نسل ها بدین صورت است:

 

الف) با محاسبه مقدار تابع شایستگی افراد حاضر در جمعیت به هر کدام از اعضای آن یک امتیاز میدهیم.

ب) امتیازها را مقیاس بندی میکنیم.

پ) افراد شایسته تر به عنوان والدین انتخاب می شوند.

ت) به کمک والدین ، فرزندان بر اثر تلفیق و جهش ایجاد می شوند.

ث) جمعیت حاضر با فرزندان جایگزین شده و نسل بعدی ادامه می یابد.

 

3- با رسیدن به یکی از شرایط از پیش تعیین شده، الگوریتم متوقف می شود.

[M!Zare 48,037]

جمعیت

 

بصورت پیش فرض همانگونه که در تصویر نمایش داده شده است، جمعیت اولیه توسط الگوریتم، 20 در نظر گرفته می شود، که البته می توان آن را تغییر داد. همچنین بصورت پیش فرض محدوده جمعیت آغازین نیز بین صفر و یک است. (در تصویر قبل میتوان این محدوده را دید) اگر محدوده نقطه مینیمم را میدانیم، میتوان این محدوده را کوچکتر کرد.

[M!Zare 48,037]

تولید نسل بعدی

 

از سه روش برای تولید نسل بعدی می توان استفاده کرد:

 

1- تشخیص فرزندان نخبه: افرادی که در جمعیت حاضر شایستگی بیشتری دارند و بصورت اتوماتیک به نسل بعد منتقل می شوند.

 

2- تولید تلفیقی : با ترکیب بردار والدین ایجاد می شود.

 

3- تولید فرزندان جهش یافته : با ایجاد یک تغییر تصادفی یا جهش در والدین ایجاد می شود.

[M!Zare 48,037]

شرایط توقف الگوریتم:

 

 

برخی از شرایط توقف الگوریتم بدین صورت است:

 

1- تعداد نسل ها به مقدار معینی برسد.

 

2- به محدودیت زمانی تعیین شده (بر حسب ثانیه ) برسیم.

 

3- به محدودیت شایستگی تعیین شده (کوچکتر، مساوی از یک مقدار) برسیم.

 

4- رکود نسلی ایجاد شود یعنی از یک نسلی به بعد پیشرفتی حاصل نشود.

 

5- رکود زمانی حاصل شود یعنی تابع هدف برای زمان معینی پیشرفتی نداشته باشد.

 

با حصول هر یک از این شرایط الگوریتم متوقف می شود.

[M!Zare 48,037]

برای تست کردن الگوریتم ژنتیک ، همانطور که در Help نرم افزار هم توضیح داده شده است از تابع Rstriginsfcn استفاده می شود.

برای مشاهده این محتوا لطفاً ثبت نام کنید یا وارد شوید.

• ورود
• یا
• ثبت نام

این تابع مینیمم های زیادی دارد که تنها یکی از آنها سراسری و ما بقی محلی هستند. از این رو برای چک کردن الگوریتم بسیار مناسب است.

[M!Zare 48,037]

برای شروع دستور gatool رو در متلب تایپ میکنیم.

 

در قسمت Fitness Function تابع شایستگی را تایپ میکنیم....@ یک handle از تابع رو تهیه میکند و تابعی که قبلا نوشته شده و در Mfile ذخیره شده است را به صورت @نام تابع فراخوانی میکنیم.

 

تعداد متغیرها: اندازه بردار ورودی به تابع شایستگی را نشان میدهد که برای این تابع دو ، X1 و X2 است.

[M!Zare 48,037]

برای شروع برنامه کافی است که کلید start رو بزنیم..

در پنجره Current iteration تعداد تکرارها و در پنجره پایینی مقدار تابع بهینه و نقطه بهینه و دلیل توقف داده می شود.

[Moment 15,228]

تابع شایستگی رو خودمون بر حسب متغیرامون باید تعریف کنیم؟خود برنامه به صورت پیش فرض توابع خاصی نداره که شاید به دردمون بخوره؟

[M!Zare 48,037]

تابع شایستگی رو خودمون بر حسب متغیرامون باید تعریف کنیم؟خود برنامه به صورت پیش فرض توابع خاصی نداره که شاید به دردمون بخوره؟

توابع متلب خیلی زیاده و در قسمت Help یک بخش جدا داره..function Brower..ولی برای موارد خاص فکر کنم اگر خودمون تابع تعریف کنیم بهتره

[M!Zare 48,037]

برای رسم شکل از قسمت plot استفاده میکنیم و نمودارهایی که تمایل داریم رسم شود را تیک میزنیم...امکان رسم چندین نمودار با یکدیگر وجود دارد.

 

 

 

[M!Zare 48,037]

اگر هیچکدام از این نمودارها برای انجام کار ما کافی نبود، تابع رسم شکل خودمان را تعریف کرده و در بخش custom function به همراه علامت @ فراخوانی میکنیم.

 

تولید مجدد نتایج

 

use random states from pervious run را اگر تیک بزنیم، مقادیر با مقادیر تصادفی قبلی مقدار دهی می شود. (واسه من وقتی که این تیک رو میزنم همه نتایج ثابت میمونه) و بنابراین از این تیک استفاده نمی شود تا از مزایای انتخاب تصادفی بهره ببریم. فقط در مواردی به کار میاید که بخواهیم نتایج را به دیگران نشان بدهیم یا یک مورد خاص را اجرا کنیم.

[M!Zare 48,037]

تنظیمات رابط گرافیکی در بخش Option صورت میگیره.

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

زمانیکه در محاسبات از بردارها و ماتریس های بزرگ استفاده می شود، تعیین مقدار متغیرها در فضای کار ساده تر است.

 

[M!Zare 48,037]

می توان داده ها را بین فضای کاری متلب و جعبه ابزار الگوریتم ژنتیک جابجا کرد. برای اینکار از دستور های import و export از منو File استفاده می شود.

 

 

 

 

موادری که شامل این جابجایی می شود:

 

تعریف مساله که شامل تعریف تابع شایستگی و تعداد متغیرهاست.

 

Option های خاص جاری

 

نتیجه اجرای الگوریتم

[Lean 56,968]

یه زمانی به شدت علاقه مند به الگوریتم ها متاهیوریستیک بودم به خصوص ژنتیک در زمینه بهینه سازی خیلی قوی محسوب میشه پیشنهاد می کنم با الگوریتم رقابت استعماری هم کار کنی

[M!Zare 48,037]

یه زمانی به شدت علاقه مند به الگوریتم ها متاهیوریستیک بودم به خصوص ژنتیک در زمینه بهینه سازی خیلی قوی محسوب میشه پیشنهاد می کنم با الگوریتم رقابت استعماری هم کار کنی

پس شما با این الگوریتم آشنایید؟