رفتن به مطلب

ارسال های توصیه شده

درود....

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

لینک به دیدگاه
  • پاسخ 46
  • ایجاد شد
  • آخرین پاسخ

بهترین ارسال کنندگان این موضوع

بهترین ارسال کنندگان این موضوع

حل مساله فروشنده دوره گرد:

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

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

لینک به دیدگاه

شروع برنامه:

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

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

لینک به دیدگاه

تعریف پارامترهای مساله TSP یا Travelling Salesman Problem

 

تعداد شهرها

تعیین موقعیت جغرافیایی شهرها (بین صفر و یک ) که به دو صورت امکان پذیر است..شهرهای از پیش موقعیت مشخص شده و یا انتخاب موقعیت شهر ها بصورت تصادفی

نمایش موقعیت شهرها بر روی نقشه

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

لینک به دیدگاه

:a030:بالاخره تایپیکش رو زدی...خیلی منتظر بودم

منم هستم

:ws3: متلب نصب میکنم که جا نمونم

؟راستی کسی هست اینجا خفن باشه در زمینه الگوریتم ژنتیک

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

لینک به دیدگاه

تعیین فاصله بین شهر ها با تعریف تابع

 

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

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

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

این تابع را در برنامه اصلی بدین صورت قرار میدهیم...

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

پاسخ یک نمونه محاسبات بدین صورت است...

CityDistance =

0 0.6130 0.4107 0.1429 0.3163

0.6130 0 0.6198 0.6384 0.9252

0.4107 0.6198 0 0.5500 0.5486

0.1429 0.6384 0.5500 0 0.3641

0.3163 0.9252 0.5486 0.3641 0

لینک به دیدگاه

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

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

 

ورودی های این تابع: شماره شهر مبدا، فاصله بین شهرها و تعداد شهرها است.

برای اینکه شهرها در یک حلقه بسته باشن و شهر آخر به شهر اول متصل شود، یک بردار تعریف میکنیم که شهر انتهایی آن با شهر ابتدایی یکی است.

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

دو تا شهر تعریف میکنیم....شهری که هم اکنون در آن قرار داریم و شهری که قرار است پس از این شهر به آن برویم....(این شهر ها در تابع مسافرت مشخص شده اند که بصورت رندم محاسبه می شوند.)

مسیر پیموده شده در هر نقطه ای می شود مسیر پیموده شده تا شهر قبل به اضافه فاصله بین این شهر و شهر قبلی

 

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

 

در تابع اصلی نیز متغیر tarvel که نشان دهنده شماره شهر انتخابی است و تابع مسیر پیموده شده را اضافه میکنیم.


[font=Courier New][size=2][font=Courier New][size=2]CityNum = 5;
[/size][/font][/size][/font][font=Courier New][size=2][color=#0000ff]
[/color][/size][/font] [font=Courier New][size=2][font=Courier New][size=2] XCity = rand (1, CityNum);

YCity = rand (1, CityNum);

[/size][/font][/size][/font][font=Courier New][size=2][font=Courier New][size=2]plot (XCity,YCity,[/size][/font][/size][/font][font=Courier New][size=2][color=#a020f0][font=Courier New][size=2][color=#a020f0][font=Courier New][size=2][color=#a020f0]'p'[/color][/size][/font][/color][/size][/font][/color][/size][/font][font=Courier New][size=2][font=Courier New][size=2])[/size][/font][/size][/font]
[font=Courier New][size=2][font=Courier New][size=2]
CityDistance = CityDistance_Fcn (XCity,YCity);
[/size][/font][/size][/font]
[font=Courier New][size=2][font=Courier New][size=2]Travel = randperm(CityNum);

TravelDistance = TravelDistance_fcn(Travel,CityDistance,CityNum);

[/size][/font][/size][/font]

لینک به دیدگاه

پارامترهای الگوریتم:

 

تعداد جمعیت

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

درصد نگهداری

درصد cross

تولید جمعیت اولیه

 

محاسبه تعداد نگهداری شده از جمعیت که برای رند شدن انها دستور round استفاده میکنیم.

محاسبه تعداد cross شده

محاسبه تعداد جمعیت اولیه

 

تخمین جمعیت اولیه بستگی به پیچیدگی مساله دارد. اگر تعداد Iteration را هم 100 قرار دهیم نزدیک 10000 حالت میشود که تقریبا کافی است.

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

لینک به دیدگاه

جمعیت های اولیه:

 

جمعیت اولیه ترکیبی از شهرهاست.

دستور randperm(x) اعداد تصاوفی بین 1تا x رو نمایش میده.

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

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

لینک به دیدگاه

نوشتن تابع هزینه

 

برای هزینه یک تابع تعریف میکنیم. که با گرفتن جمعیت، هزینه را حساب میکند.با استفاده از حلقه نیز هزینه مسیرهای مختلف را محاسبه میکنیم.

شمارنده های حلقه به اندازه جمعیت تغییر میکند ولی چون جمعیت بصورت ستونی بود، اندازه آن را ملاک قرار داده و بصورت سطری استفاده میکنیم.

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

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

بدلیل اینکه در تابع مسیر حرکت دوره گرد، فاصله شهرها و تعداد آن مورد نیاز است ، آنها را نیز در ورودی تابع هزینه لحاظ میکنیم.

 

برنامه اصلی بدین صورت نوشته می شود.

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

لینک به دیدگاه

برای اینکه هزینه ها را از کمتر به بیشتر مرتب کنیم از دستور sort یا مرتب سازی متلب استفاده میکنیم. که در فایل اکسل workspace می توان این تغییرات را مشاهده کرد.

 

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

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

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

لینک به دیدگاه

حالا وقت آن رسیده که بهترین های جمعیت رو انتخاب و به نسل بعد منتقل کنیم.

ابتدا یک حلقه را برای انجام عملیات سعی و خطا تعریف میکنیم.

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

با دستورات Keeppercent و KeepNum قبلا روند آن را مشخص کرده ایم. حال با دستور KeepPop تعیین میکنیم که چه مقدار از جمعیت رو برداره. و بدین صورت بهترین های جمعیت برداشته میشه.

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

لینک به دیدگاه

سپس به انتخاب والدین و CrossOver (انتقال نسل) میپردازیم . برای این کار یک تابع تعریف میکنیم که ورودی آن والدین و خروجی آن نسل ایجاد شده یعنی همان فرزندان هستند. نسل منتقل شده را نصف کروموزوم ها ( تعداد کروموزوم ها با تعداد والدین یکسان است) در نظر میگیریم و برای اینکه عدد آن کاملا صحیح شود از دستور round استفاده میکنیم.

حال تا نقطه انتقال نسل دو حالت را برای هر والد در نظر میگریم....از ابتدا تا نقطه Cross و بعد از نقطه Cross تا انتها

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

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

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

لینک به دیدگاه

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

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

ابتدا یک شمارنده برای بخش دوم که متغیرهای تکراری از آنجا شروع می شود تعریف میکنیم. و سپس با استفاده از دستور ismember چک میکنیم که این نسل در نسل قبل از Cross هم بوده یا نه؟ اگر بوده متغیر دیگری به تعداد کروموزوم ها تولید میکنیم که بخش دوم Cross هیچ عدد تکراری با بخش اول نداشته باشد. ~ علامت منفی است...اگر عضو نیست.

 

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

نحوه نوشتن دستور کاملا منطقی هست ولی نمیدونم چرا گاهی اوقات واسه من متغیرهای تکراری هم میده:ws52: اگر شما دلیلش رو میدونید حتما در اینجا بیان کنید.

لینک به دیدگاه

انتخاب والدین با استفاده از شیوه Tournment

 

 

تابع انتخاب والدین رو تعریف میکنیم که با گرفتن تابع هزینه و تعداد انتخابی، اندیس هایی از تابع هزینه را به ما برگرداند.

جمعیت مورد بررسی را به اندازه تعداد اعضای ماتریس هزینه در نظر میگیریم.

با تعریف یک حلقه به تعداد، اندیس های انتخابی کار رو شروع میکنیم. R را بصورت انتخاب تصادفی جمعیت تعریف میکنیم.

اندیس انتخابی: از ماتریس R درایه اول تا چهارم رو در نظر میگیریم و برای هزینه نیز، هزینه درایه های انتخاب شده در R را محاسبه میکنیم. برای انتخاب کمترین هزینه از دستور find و mim استفاده میکنیم.

در یک حالتی که بسیار هم کم پیش میاید، دو عدد از چهار هزینه یکسان داده باشن که تعیین میکنیم اندیس اولی را انتخاب کند.

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

برنامه اصلی را نیز می نویسیم....تعداد انتخابی مساوی همان تعداد Cross است.

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

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

 

پس از مشخص شدن اندیس والدین انها را از ماتریس جمعیت بیرون میکشیم.

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

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

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

لینک به دیدگاه

جهش

 

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

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

لینک به دیدگاه

جمعیت جدید

 

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

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

لینک به دیدگاه

نمایش نمودار همگرایی

 

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

 

سپس ان را رسم میکنیم. برای اینکه دو تا شکل همزمان رسم شود از دستور Hold on استفاده میکنیم.

برای محور افقی نیز محدودیت حداکثر تعداد سعی و خطار را مشخص میکنیم.

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

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

لینک به دیدگاه

نتیجه نهایی

 

با توجه به تعریف هایی که از قبل انجام دادیم، ردیف اول جمعیت بهینه ترین پاسخ ها را دارد.

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

لینک به دیدگاه

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

برای دسترسی به این جعبه ابزار کافی است در workspace متلب عبارت gatool را تایپ نمایید تا پنجره زیر ظاهر شود.

 

uiudzkt61joxzwmugyv0.jpg

لینک به دیدگاه

به گفتگو بپیوندید

هم اکنون می توانید مطلب خود را ارسال نمایید و بعداً ثبت نام کنید. اگر حساب کاربری دارید، برای ارسال با حساب کاربری خود اکنون وارد شوید .

مهمان
ارسال پاسخ به این موضوع ...

×   شما در حال چسباندن محتوایی با قالب بندی هستید.   حذف قالب بندی

  تنها استفاده از 75 اموجی مجاز می باشد.

×   لینک شما به صورت اتوماتیک جای گذاری شد.   نمایش به صورت لینک

×   محتوای قبلی شما بازگردانی شد.   پاک کردن محتوای ویرایشگر

×   شما مستقیما نمی توانید تصویر خود را قرار دهید. یا آن را اینجا بارگذاری کنید یا از یک URL قرار دهید.


×
×
  • اضافه کردن...