در این پست یک نسخه از کدهای مربوط به الگوریتم رقابت استعماری (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
تابع اصلی که همه توابع دیگر را به هم پیوند می دهد. تنظیمات اصلی مربوط به الگوریتم، در این تابع قرار دارند. اجرای این تابع مسئله بهینه سازی را حل می کند. فیلم آموزشی ارائه شده تا حد زیادی به بیان جزئیات این برنامه می پردازد.
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) می باشد. چون ممکن است این تولباکس بر روی خیلی از کامپیوتر ها نباشد (به ویژه خارج از ایران که هزینه تهیه و نصب برنامه متلب بسیار بالا است!!!)، این تابع به عنوان جایگزینی برای آن نوشته شده است.
در ضمن نسخه های دیگری از الگوریتم رقابت استعماری به ویژه در زبانهای برنامه نویسی دیگر در حال تهیه بوده و به زودی منتشر می شوند. همچنین کدهای مربوط به روشهای دیگر بهینه سازی همانند الگوریتم های ژنتیک (Genetic Algorithms)، الگوریتم پرندگان (Particle Swarm Optimization) و بهینه سازی کلونی موچگان (Ant Colony Optimization) نیز به مرور زمان بر روی سایت قرار خواهند گرفت. البته متلبسایت مرجع کاربران و برنامه نویسان متلب و هوش مصنوعی ایران تا به حال مطالب بسیاری را در این موضوعات منتشر کرده است.
کدها و برنامه رایگان ارائه شده می توانند به عنوان یک پروژه کامل و مجزا در مورد الگوریتم رقابت استعماری (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?
پاسخحذف@ ناشناس
پاسخحذفپسورد غالب (تقریباً همه) فایلهای موجود در سایت، عبارت زیر است.
www.icasite.info
موفق باشید،
وبسایت محاسبات تکاملی
one more question. is your algorithm suitable for recursive applications? how do you compare it to particle filters? thanks
پاسخحذف@ ناشناس
پاسخحذفتا جایی که اطلاعات نگارنده پاسخ اجازه می دهد، فیلتر ذره ای یک روش بهینه سازی نیست، با اینکه درونش بهینه سازی وجود دارد. بنابراین اینها در یک ظرف نیستند که مورد مقایسه قرار گیرند.
موفق باشید،
وبسایت محاسبات تکاملی