در این بخش فیلم آموزش حل مسئله TSP با الگوریتم ژنتیک GA در متلب قرار داده شده است. الگوریتم ژنتیک Genetic Algorithm یکی از الگوریتم های پرکاربرد و محبوب برای حل مسائل سخت می باشد و به وفور از این الگوریتم استفاده می شود. مفهوم آسان و قابل درک این الگوریتم آن را به عنوان الگوریتم پرکاربرد در زمینه های الگوریتم های تکاملی بدل کرده است. به سادگی می توان از الگوریتم ژنتیک برای حل مسئله فروشنده دوره گرد Travelling Salesman Problem استفاده کرد. در ادامه توضیحات کاملی درباره محتوا و سرفصل های فیلم آموزشی بیان خواهد شد.

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

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

الگوریتم ژنتیک واقعی که بر اساس ایده ي تکامل بیولوژیکی در طبیعت عمل می نمایند، بر روي جمعیتی از راه حل های بالقوه یا کروموزوم ها که هر یک می توانند به‌عنوان پاسخی از مسئله تلقی شوند، با اعمال عملگرهای ژنتیکی به جستجوي راه حل نهایی می پردازند. در الگوریتم ژنتیکی، بسیاري از مکانیزم هایی که در زیست شناسی وجود دارد، نظیر انتخاب ژن برتر، ترکیب ژن ها، جهش ژن ها، مهاجرت افراد جمعیت، محلی بودن گونه ها و … شبیه سازي می شوند. در این الگوریتم ها، جستجو بر روي مجموعه هايی از راه حل ها به‌صورت موازي انجام می شود، درحالی‌که در روش هاي سنتی جستجو به‌صورت ترتیبی است.

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

در آغاز الگوریتم، تعدادي از افراد به‌عنوان جمعیت اولیه و معمولاً به‌صورت تصادفی ساخته‌شده و معیاري از کیفیت به نام تابع هدف یا برازندگی براي تک  تک آن ها ارزیابی می شود. اگر شرط رسیدن به جواب برقرار نباشد (به جواب بهینه نرسیده باشیم)، نسل بعدي با انتخاب والدین بر اساس میزان برازندگی آن ها تولید می شود. در هر نسل، بهترین هاي آن نسل انتخاب می شوند و پس از زادوولد، مجموعه جدیدي از فرزندان را تولید می کنند.

کروموزوم هاي موجود در جمعیت بر اساس مقدار برازندگی به‌عنوان والد انتخاب می شوند. سپس تولید مثل، بین جفت کروموزوم ها انجام می گیرد تا فرزندان ایجاد شوند و فرزندان با احتمالی ثابت دچار جهش می شوند. سپس میزان برازندگی فرزندان جدید محاسبه‌شده و جمعیت جدید، از جایگزینی فرزندان با والدین ایجاد می شود و جمعیت ایجادشده جدید به‌عنوان نسل بعدي شناخته می‌شود و فرایند تکرار می شود. در این فرایند، افراد مناسب تر با احتمال بیشتري در نسل هاي بعد باقی خواهند ماند و این فرایند تا برقرار شدن شرط خاتمه تکرار می شود. الگوریتم زمانی پایان خواهد یافت که بهبودي بر روي جواب ها صورت نگیرد و یا اینکه تعداد مشخصی نسل تولید شود.

مسئله فروشنده دورگرد TSP

برای حل فروشنده دوره گرد با ژنتیک بایستی مساله فروشنده دوره گرد Travelling salesman problem یا به اختصار TSP تشریح شود. TSP مساله اي است که شرح آن خيلي آسان مي باشد. تعريف آن بدين صورت است که تعداد متناهي شهر با هزينه پيمايش بين هر جفت از آنها داده مي شود و هدف مساله اين است که يک فروشنده دوره گرد تمامي اين شهرها را به گونه ای ملاقات کند که هر يک از اين شهرها را فقط يک بارملاقات کرده و دوباره به شهر آغازين برگردد با اين شرط که با کمترين هزينه پيمايش اين کار را انجام دهد.

به طور کلي هدف پيدا کردن کم هزينه ترين تور براي ملاقات همه شهرها و بازگشت به شهر آغازين حرکت است. مساله فروشنده دوره گرد در شکل ساده و اختصاري با نام TSP شناخته مي شود. شکل  زیر يک نمونه جواب از مساله فروشنده دوره گرد که در سال 1591 براي 15 شهر از کشور آمريکا مطرح شد را نشان مي دهد که با روش شاخه وحد حل شد.

فهرست سرفصل ها و رئوس مطالب مطرح شده در این مجموعه آموزشی:

  • بیان تئوری و مفاهیم مسئله TSP و الگوریتم ژنتیک GA
    • بیان مفهوم مسئله فروشنده دوره گرد TSP
    • بیان مفهوم تکامل در الگوریتم ژنتیک
    • بیان اصطلاحات مهم الگوریتم ژنتیک
    • بیان عملگرهای انتخاب، Crossover، جهش
    • مراحل کلی و روند الگوریتم ژنتیک برای حل مسئله فروشنده دوره گرد
  • پیاده سازی مسئله در متلب
    • ایجاد مدلی از محل قرارگیری شهرها و فاصله آنها
    • نحوه ایجاد جمعیت اولیه
    • بدست آوردن تابع Fitness
    • انتخاب والدین
    • جابجایی یا Crossover
    • جهش یا Mutation
    • برش یا Truncation
    • رسم شهرها و نحوه پیمایش

مشخصات فیلم آموزشی

نام اثر : حل مسئله TSP با الگوریتم ژنتیک GA در متلب

مدرس : مهندس امین جلیل زاده

مدت زمان : 1 ساعت و 48 دقیقه

زبان آموزش : فارسی

حجم فایل : 2 فایل با فرمت rar با حجم (جمعاً 197 مگابایت)

فرمت ویدئو : MP4 با کیفیت بالا


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

پیش نمایش 1

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

پیش نمایش 2

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

درباره محصول

فیلم آموزش حل مسئله TSP با الگوریتم ژنتیک GA در متلب عنوان محصولی است که در این پست به آن پرداخته شده است. در این آموزش به توضیح و تشریح تئوری و مفاهیم الگوریتم ژنتیک برای حل مسئله فروشنده دوره گرد در متلب پرداخته شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و بازبینی شده است. محصول دارای نشان تضمین کیفیت پی استور می باشد. برای دانلود محصول آن را خریداری کنید.

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

  1. امین جلیل زاده

    نظرات و پیشنهادات خود را با ما در میان بگذارید.

دیدگاه خود را بنویسید

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