در این پست یک نسخه از کدهای مربوط به الگوریتم رقابت استعماری (Imperialist Competitive Algorithm) که به اختصار ICA نامیده می شود، ارائه شده است. این کدها در متلب می باشند و به سادگی قابل اعمال به انواع مسائل بهینه سازی هستند. به همراه کدها یک فایل کوتاه متنی توضیحات مربوط نحوه استفاده از کد ها موجود می باشد. در نهایت یک فیلم کوتاه نیز نحوه استفاده از این کدها را به خوبی نمایش می دهد. این فیلم در پاسخ به سوال یکی از دوستان در مورد نحوه استفاده از کدها تهیه شده است. اما مشاهده آن برای بسیاری از دوستان که خود کدها و فایل کوتاه آموزشی همراه آن برایشان کافی نبوده است، توصیه می شود. به زودی فیلم های کامل تر و بهتری راجع به الگوریتم رقابت استعماری بر روی وب قرار خواهند گرفت. در ضمن این فیلم به زبان فارسی می باشد.
نکته: برای دریافت فایل ها، از لینک Google Doc پس از کلیک بر روی لینک ها باید از اکانت گوگل (جی میل) خود استفاده کنید.
لینک دانلود فایل دیکدر که شاید نصب آن برای مشاهده فیلم در بعضی کامپیوتر ها مورد نیاز باشد.
مشاهده فیلم در یوتیوب
فیلم مذکور را در صورت دسترسی به یوتیوب می توانید در این لینک ببینید.
توضیحات مربوط به توابع موجود در کنار کدهای آماده:
شبه کد الگوریتم رقابت استعماری همانگونه که در
فایل راهنمای فارسی آن بطور مفصل توضیح داده شده است، به صورت زیر است.
- چند نقطه تصادفي روي تابع انتخاب کرده و امپراطوري‌هاي اوليه را تشکيل بده.
- مستعمرات را به سمت کشور امپرياليست حرکت بده (سياست همسان‌سازي یا جذب).
- عملگر انقلاب (Revolution) را اعمال کن.
- اگر مستعمره‌اي در يک امپراطوري، وجود داشته باشد که هزينه‌اي کمتر از امپرياليست داشته باشد؛ جاي مستعمره و امپرياليست را با هم عوض کن.
- هزينه‌ي کل يک امپراطوري را حساب کن (با در نظر گرفتن هزينه‌ي امپرياليست و مستعمراتشان).
- يک (یا چند) ستعمره از ضعيف‌ترين امپراطوري انتخاب کرده و آن را به امپراطوري‌اي که بيشترين احتمال تصاحب را دارد، بده.
- امپراطوري‌هاي ضعيف را حذف کن.
- اگر تنها يک امپراطوري باقي مانده باشد، توقف کن وگرنه به 2 برو.
نکته مهم: شبه کد فوق مربوط به نسخه اولیه معرفی شده از الگوریتم است. نسخه های جدید تر الگوریتم در بندهایی از این شبه کد ممکن است با آنچه در بالا آمد، متفاوت باشند.
در فایل زیپ شده کدها چندین تابع وجود دارند که به ترتیب الفبا در زیر مرتب شده اند. در ادامه در کنار هر تابع ارتباط آن با بخشی از الگوریتم رقابت استعماری نوشته شده است.
AssimilateColonies
این تابع بخش آسیمیلاسیون (Assimilation) یا به عبارت دیگر سیاست جذب را پیاده سازی می کند.
BenchmarkFunction
در این برنامه تعداد زیادی از توابع مطرح استاندارد بهینه سازی قرار داده شده اند. از این توابع می توان جهت تست روشهای مختلف بهینه سازی استفاده نمود. در کنار این توابع، یک مثال عملی از حل یک مسئله کنترل برای طراحی کنترل کننده PID نیز وجود دارد. به احتمال زیاد این بخش مربوط به کار انجام شده در مقاله به عنوان زیر است که در
بخش مقالات انگلیسی فایل کامل آن قابل دانلود است.
Esmaeil Atashpaz Gargari & Caro Lucas, “Designing an optimal PID controller using Colonial Competitive Algorithm”, First Iranian Joint Congress on Intelligent and Fuzzy Systems, September 2007, Mashhad, Iran.
CreateInitialEmpires
با در نظر گرفتن موقعیت و هزینه (عکس قدرت) کشورهای اولیه، امپراطوری های اولیه را با تقسیم مناسب مستعمرات میان آنها شکل می دهد.
DisplayEmpires
اگر توجه کرده باشید، در
فایل راهنمای فارسی الگوریتم رقابت استعماری و نیز در بسیاری از
مقالات فارسی و
انگلیسی شکلهایی برای نشان دادن محل امپراطوری ها وجود دارند. در این شکلها معمولاً هر رنگ نشان دهنده یک امپراطوری است. در هر امپراطوری نیز کشور مرکزی (امپریالیست) با علامت ستاره و مستعمرات با علامت دایره نشان داده می شوند. تابع DisplayEmpires مسئول انجام چنین ترسیماتی است. لازم به ذکر است که این نوع ترسیمات برای برای بهینه سازی های با بعد کمتر یا مساوی 3 معنا دارد. برای ابعاد با تعداد بیشتر این ترسیم را متوقف می کنیم.
GenerateNewCountry
این تابع که بیش از چند خط نیست، یک کشور را با موقعیت تصادفی خلق می کند. کشور با موقعیت تصادفی در بازه ای که قبلاً به عنوان قیود بهینه سازی در برنامه اصلی Main_ImperialistCompetitveAlgorithm داده شده است، ایجاد می شود.
ImperialisticCompetition
انجام رقابت استعماری میان امپراطوری ها جهت جذب مستعمرات همدیگر، توسط این تابع انجام می پذیرد. حذف امپراطوری های ضعیف (از بین رفته) نیز در این تابع گنجانده شده است.
Main_ImperialistCompetitveAlgorithm
تابع اصلی که همه توابع دیگر را به هم پیوند می دهد. تنظیمات اصلی مربوط به الگوریتم، در این تابع قرار دارند. اجرای این برنامه، مسئله بهینه سازی را حل می کند.
فیلم آموزشی ارائه شده تا حد زیادی به بیان جزئیات این برنامه می پردازد.
در این بخش از برنامه تنظیمات مرتبط با مسئله، همانند نام تابع هزینه، تعداد متغیرها (بعد مسئله بهینه سازی)، تعداد کشور های اولیه، تعداد دهه ها و … صورت می پذیرد. توجه شود که برنامه تابع هزینه با آوردن نام آن، شناخته می شود. در حالت پیشفرض، توابع استاندارد موجود همراه فایل ها برای تست اجرای برنامه تنظیم شده اند. پارامتر Costfunction.ExtraPrams شماره تابع استاندارد موجود را تعیین می کند. توجه شود که این پارامتر برای کاربردهای آتی پیش بینی شده است و در حالت استفاده عادی برای اتصال به توابع هزینه نوشته شده توسط شما، باید خالی (تهی []) باشد. راهنمای موجود در مقابل این عبارت که به صورت کامنت نوشته شده است نیز، به خوبی به این موضوع اشاره دارد.
PossesEmpire
تعویض جای مستعمره و استعمارگر در این تابع انجام می پذیرد. اگر مستعمره ای به جای بهتری نسبت به استعمارگر رسید، فوراً کنترل امپراطوری را در دست گرفته و کار را با اعمال سیاست جذب بر روی آنها ادامه می دهد.
RevolveColonies
انقلاب که وزنه اصلی توازن Exploration و Exploitation و به نفع Exploration است، در این تابع انجام می شود. تغییراتی ناگهانی در برخی کشور ها اتفاق افتاده و در برخی موارد به کشف نقاط ناپیدای مینیمم در تابع منجر می شود. لازم به ذکر است که این بخش مهم از الگوریتم رقابت استعماری که از اولین نسخه های این الگوریتم با آن بوده است، متاسفانه در هیچ یک از
مستندات آن از جمله در فایل راهنمای فارسی و
مقالات اولیه مرتبط با الگوریتم مورد بررسی قرار نگرفته است. در نهایت برای اولین بار توضیحات مرتبط با این بخش مهم از الگوریتم در مقاله با عنوان زیر که در
بخش مقالات انگلیسی فایل کامل آن قابل دانلود است، ارائه شده است.
“Solving the Integrated Product Mix-Outsourcing Problem by a Novel Meta-Heuristic Algorithm: Imperialist Competitive Algorithm”, Expert Systems with Application, Elsevier
UniteSimilarEmpires
اتحاد امپراطوری های مشابه توسط این تابع انجام می شود. لازم به ذکر است در برخی نسخه های الگوریتم، این بخش حذف شده و حتی به ادعای تهیه کننده کدها به بهبود برنامه منجر شده است. به عنوان مثال پست زیر را ببینید. البته این موضوع نیاز به بررسی به مراتب بیشتری دارد. در هر صورت این بخش یک قسمت حیاتی از الگوریتم به شمار نمی رود.
دانلود رایگان کد الگوریتم رقابت استعماری در سی شارپ و متلب
Myrandint
این تابع یک یا تعدادی عدد رندم صحیح در بازه دلخواه داده شده به آن ایجاد می کند. در حقیقت متلب تابعی با نام randint دارد که مربوطه به یکی از تولباکس های آن (به احتمال زیاد Communications Toolbox) می باشد. چون ممکن است این تولباکس بر روی خیلی از کامپیوتر ها نباشد (به ویژه خارج از ایران که هزینه تهیه و نصب برنامه متلب بسیار بالا است!!!)، این تابع به عنوان جایگزینی برای آن نوشته شده است.
چگونه ترسیم شکل ها را کنترل کنیم؟
دو نوع ترسیم در کدهای موجود پیش بینی شده اند. ترسیم اول، رسم نمودار موقعیت امپراطوری ها است. این ترسیم تنها برای مسائل با بعد دو یا سه معنی دار می باشد. زیر در این حالت امکان نمایش امپراطوری ها (کشور مرکزی به همراه مستعمرات هر یک) وجود دارد. برای فعال کردن و یا غیر فعال کردن این ترسیم، خط کد زیر را در میان کدها بیابید.
DisplayParams.PlotEmpires = true; % “true” to plot. “false” to cancel ploting.
اگر به جای true در خط کد فوق، عبارت false بنویسید، ترسیم موقعیت امپراطوری ها غیر فعال خواهد شد. true بودن ترسیم امپراطوری ها را فعال می کند.
نوع دوم شکل و ترسیم در این کدها، ترسیم نمودارهای همگرایی تابع هزینه است. از جهت نوع کنترل، ترسیم نمودار های همگرایی هزینه نیز داستان مشابهی دارند، با این تفاوت که این نمودار، هیچ محدودیتی در ابعاد ندارد و برای تمام مسائل قابل ترسیم است و حتی رسم آن توصیه نیز می شود. ترسیم این نمودار را نیز به همان ترتیب بالا با ایجاد تغییر در خط کد زیر در میان کدها می توانید کنترل نمایید.
DisplayParams.PlotCost = true; % “true” to plot. “false”
توجه: در متلب، به جای true و false عددهای 1 و 0 را می توانید به ترتیب استفاده نمایید.
کدها و برنامه رایگان ارائه شده می توانند به عنوان یک پروژه کامل و مجزا در مورد الگوریتم رقابت استعماری (Imperialist Competitive Algorithm) که به اختصار ICA نامیده می شود، مورد استفاده آموزشی نیز قرار بگیرند.
در بخش از متن پایان نامه منشتر شده بر روی وبسایت به یک تولباکس گرافیکی اشاره شده است که کدهای متلب آن را می توانید در لینک زیر دانلود نمایید.
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.
صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.
when you increase the range, the minimum achieved cost value is increased which does not make sense. can you explain this?
@ ناشناس:
در حالت عادی و با شرایط نرمال، نباید این اتفاق بیافتد که با افزایش بازه متغیرها جواب بدتری به دست آید. چون به هر حال فضای جستجو بزرگتر می شود و شامل فضای جستجوی قبلی نیز می باشد.
اما در عمل این پدید می تواند روی دهد. یعنی به این صورت که فرض کنیم جواب بهینه ما در مبداً قرار دارد و ما بازه جستجو را به منفی یک تا یک محدود کرده ایم. اما اگر بازه را بزرگتر بکنیم و به منفی هزار تا مثبت هزار محدود کنیم، در این حالت الگوریتم باید فضای بزرگتری را برای یافتن جواب بگردد و با تعداد کشور (جمعیت) ثابت، این کار را برای هر الگوریتمی سخت می کند.
کلاً می شود گفت که بهتر است که ما تا حد ممکن، بازه را کوچکترین بازه ممکن برای متغیر در نظر بگیریم به گونه ای که جواب را نیز شامل شود.
موفق باشید،
وبسایت محاسبات تکاملی
another question, i tried to use your code for generating PID controller but it is password protected. what is the password?
@ ناشناس
پسورد غالب (تقریباً همه) فایلهای موجود در سایت، عبارت زیر است.
http://www.icasite.info
موفق باشید،
وبسایت محاسبات تکاملی
one more question. is your algorithm suitable for recursive applications? how do you compare it to particle filters? thanks
@ ناشناس
تا جایی که اطلاعات نگارنده پاسخ اجازه می دهد، فیلتر ذره ای یک روش بهینه سازی نیست، با اینکه درونش بهینه سازی وجود دارد. بنابراین اینها در یک ظرف نیستند که مورد مقایسه قرار گیرند.
موفق باشید،
وبسایت محاسبات تکاملی
mmanon az etelate fogholade mofideton.
man barname ICA oo ba PSO compare kardam.ba input yeksan.
khorji PSO behtar az ICA va
hamishe behine tare
chera berim soraghe in alg ICa??
با سلام.
این الگوریتم در نسخه های مختلفی ارائه شده است و هر نوع مقایسه ای باید یک مقایسه جامع باشد. آنچه شما مطرح می کنید، با اصلی No-Free-Lunch در تنقاقض است. اصولاً هیچ الگوریتم نمی تواند از یک الگوریتم دیگر در تمای مسائل بهتر و یا حتی بدتر باشد.
لینک زیر، برخی دلایل استفاده از الگوریتم رقابت استعماری را بیان می کند.
http://www.icasite.info/2011/01/blog-post_13.html