مجموعه آموزش های الگوریتم رقابت استعماری در متلب

الگوریتم رقابت استعماری یا Imperialist Competitive Algorithm (به اختصار ICA) یکی از جدیدترین الگوریتم های بهینه سازی هوشمند است که در حوزه هوش محاسباتی و محاسبات تکاملی معرفی شده است. جان مایه اصلی این الگوریتم، شبیه سازی فرایند سیاسی استعمار است. به همان صورت که الگوریتم ژنتیک، تکامل زیستی را شبیه سازی می کند، در الگوریتم رقابت استعماری، از تکامل سیاسی استفاده شده است. این الگوریتم در سال ۲۰۰۷ توسط اسماعیل آتش پز گرگری و مرحوم پروفسور کارو لوکاس (Caro Lucas) (استاد فقید دانشگاه تهران) معرفی شد و تاکنون در کاربردهای فراوان و زمینه های تحقیقاتی متنوعی، به عنوان ابزار بهینه سازی مورد استفاده قرار گرفته است. قدرت بالای این الگوریتم، به خصوص در برخورد با مسائل پیوسته، باعث شده است که الگوریتم رقابت استعماری به عنوان یکی از ابزارهای مهم در زمینه بهینه سازی به حساب بیاید.

درس یکم: الگوریتم رقابت استعماری — شامل مباحث تئوری و عملی

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

فهرست سرفصل ها و رئوس مطالب مطرح شده در درس یکم در ادامه آمده است:

• مروری بر مبانی بهینه سازی
• مبانی تئوری الگوریتم رقابت استعماری یا ICA
• تشریح بخش های مختلف الگوریتم رقابت استعماری و کارکرد آن ها
• سناریوهای مختلف قابل استفاده در پیاده سازی الگوریتم رقابت استعماری
• ایده های فراگیر در زمینه محاسبات تکاملی و ادغام آن ها در الگوریتم رقابت استعماری
• تاثیر پارامترها و اپراتورها (عملگرها) در عملکرد کلی الگوریتم رقابت استعماری
• پیاده سازی گام به گام الگوریتم ICA در محیط متلب
• پیاده سازی اپراتورها و اجزای الگوریتم به طرق مختلف
• حل یک مساله نمونه و ساده
• جمع بندی و نتیجه گیری های نهایی

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

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

فهرست سرفصل ها و رئوس مطالب مطرح شده در درس دوم در ادامه آمده است:

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

درس سوم: درون یابی توابع شعاعی پایه یا RBF با الگوریتم رقابت استعماری

در این درس که مربوط به درون یابی توابع شعاعی پایه یا RBF با الگوریتم رقابت استعماری است، در واقع تنظیم ضرایب یک شبکه عصبی RBF به صورت یک مساله بهینه سازی بیان شده است و توسط الگوریتم رقابت استعماری انجام پذیرفته است.

فهرست سرفصل ها و رئوس مطالب مطرح شده در درس سوم در ادامه آمده است:

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

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

مساله کوچکترین درخت پوشا به صورت یک مساله بهینه سازی گسسته باینری (صفر و یک) بیان شده است و از این رو، این درس دارای اهمیت ویژه ای است. زیرا در این درس نحوه استفاده از الگوریتم رقابت استعماری برای حل مسائل باینری آموزش داده شده است، و این درس می تواند سرمشق مناسبی برای استفاده از الگوریتم رقابت استعماری برای حل مسائل گسسته و باینری باشد. همچنین با الهام از الگوریتم های ژنتیک باینری، اپراتور انقلاب (یا Revolution) در این درس بازنگری شده است، به نحوی که عملکرد الگوریتم را برای حل مسائل باینری بهبود دهد.

فهرست سرفصل ها و رئوس مطالب مطرح شده در درس چهارم در ادامه آمده است:

• تعریف ریاضی مساله کوچکترین درخت پوشا یا Minimum Spanning Tree
• مروری بر مبانی نظریه گراف
• قضایا و لم های مربوط به تشخیص متصل بودن گراف ها
• پیاده سازی الگوریتم های مورد استفاده از تئوری گراف ها
• چگونگی استفاده از الگوریتم رقابت استعماری برای حل مسائل باینری
• حل مساله کوچکترین درخت پوشا با استفاده از الگوریتم رقابت استعماری
• بهبود عملکرد الگوریتم با الهام از الگوریتم ژنتیک باینری و اصلاح عملگر انقلاب یا Revolution
• نمایش گرافیکی نتایج حاصل از حل مساله
• جمع بندی و نتیجه گیری های نهایی

درس پنجم: حل مسائل جایگشتی با الگوریتم رقابت استعماری

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

• مساله فروشنده دوره گرد یا Traveling Salesman Problem (به اختصار TSP) که به جرات می توان گفت که معروف ترین مساله بهینه سازی جایگشتی است و کاربردهای فراوانی دارد.
• مساله تخصیص درجه دو یا Quadratic Assignment Problem (به اختصار QAP) که دارای کاربردهای وسیعی در علوم مهندسی است.
• مساله n وزیر یا n-Queen Probem (به اختصار nQP) که یک مساله کلاسیک در بهینه سازی و تحقیق در عملیات است.
• مساله زمان بندی پایه یا Basic Scheduling Problem که مادر تمام مسائل زمان بندی است و قطعا شیوه حل آن می تواند الگوی مناسبی برای حل سایر انواع مسائل زمان بندی باشد.

رویکردهای ارائه شده در این درس بسیار فراگیر و عمومی هستند و می توان از نکات تئوری و عملی بیان شده برای حل سایر مسائل جایگشتی نیز استفاده نمود. همچنین، به راحتی می توان نکات مورد بحث در این درس را با سایر الگوریتم های بهینه سازی پیوسته مانند: بهینه سای ازدحام ذرات یا PSO و تکامل تفاصلی یا DE، مورد استفاده قرار داد. در این درس اپراتور انقلاب یا Revolution مورد بازنگری قرار گرفته است و تغییراتی در آن اعمال شده است که عمکلرد الگوریتم رقابت استعماری برای حل مسائل جایگشتی بهبود یابد.

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

• تعریف ریاضی مساله فروشنده دوره گرد یا TSP
• نحوه کدینگ پاسخ یک مساله جایگشتی به صورت پیوسته
• پیاده سازی تابع هزینه و مدل ریاضی مربوط به مساله فروشنده دوره گرد
• حل مساله TSP با استفاده از الگوریتم رقابت استعماری
• نمایش گرافیکی نتایج حل مساله TSP با استفاده از الگوریتم رقابت استعماری
• بهبود عملکرد الگوریتم رقابت استعماری با اصلاح اپراتور انقلاب یا Revolution
• تعریف ریاضی مساله تخصیص درجه دو یا QAP
• پیاده سازی تابع هدف و مدل ریاضی مربوط به مساله QAP
• حل مساله QAP با استفاده از الگوریتم رقابت استعماری
• نمایش گرافیکی نتایج حاصل از حل مساله QAP
• تعریف ریاضی مساله n وزیر یا n-Queen Problem
• پیاده سازی تابع هدف و مدل ریاضی مربوط به مساله n وزیر
• حل مساله n وزیر با استفاده از الگوریتم رقابت استعماری
• نمایش گرافیکی نتایج حاصل از حل مساله n وزیر
• تعریف ریاضی مساله زمان بندی ساده و مفاهیم بنیادی مربوطه
• پیاده سازی تابع هزینه و مدل ریاضی مربوط به مساله زمان بندی
• حل مساله زمان بندی با استفاده از الگوریتم رقابت استعماری
• نمایش گرافیکی چارت زمان بندی حاصل از حل مساله زمان بندی
• جمع بندی و نتیجه گیری های نهایی