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

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

در راستای پوشش نیازهای علمی جامعه هوش محاسباتی ایران، بسته کاملی از فیلم های آموزشی الگوریتم رقابت استعماری توسط متلب سایت تهیه شده اند که می توانند به عنوان مرجع کاملی برای دانشجویان و دانشپژوهان مورد استفاده قرار بگیرند. بخشی از این مجموعه آموزشی، که در این پست قصد معرفی آن را داریم، مربوط به حل مسأله کوچکترین درخت پوشا یا Minimum Spaing Tree با الگوریتم رقابت استعماری است. مسأله طراحی کوچکترین درخت پوشا، کاربردهای وسیعی در زمینه های علمی و مهندسی دارد، که از میان آن ها می توان به طراحی بهینه سیستم های مخابراتی، شبکه های کامپیوتری و سیستم های انتقال توان الکتریکی اشاره نمود.

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

مطالب و مباحث این فیلم آموزشی به زبان فارسی روان، و توسط مهندس سید مصطفی کلامی هریس ارائه شده است.

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

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