انتخاب تعداد مناسب کشورهای اولیه و شرط توقف در الگوریتم رقابت استعماری – پرسش و پاسخ

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

• درطی فرآیند بهینه سازی در الگوریتم رقابت استعماری، از تعداد کشورها کاسته شود، بهتر است یا تا پایان بهینه سازی تعداد کشورها ثابت باشد؟

• آیا شرایط دیگری را هم می شود برای سقوط امپراطوری و همچنین شرایط همگرائی در نظر گرفت؟

• برای مسئله ای که تعداد کشورهای اولیه آن در حدود 300 تا 500 می باشد؛ چه تعداد امپراطوری اولیه برای الگوریتم مناسب می باشد؟

• انتخاب کمتر کشور و بیشتر تکرار ها بهتر هست یا برعکس؟ اگر مثلا تعداد کشورهای اولیه را 40  و تکرار را 100 در نظر بگیریم، بهتر هست یا اینکه تعداد کشورها را 50 و تعداد تکرار را 60 بگیرم؟

• چگونه می توان در متلب، اعداد تصادفی را به گونه ای ایجاد کرد که دارای میانگین و واریانس مشخصی باشند؟ 
  

• درطی فرآیند بهینه سازی در الگوریتم رقابت استعماری، از تعداد کشورها کاسته شود، بهتر است یا تا پایان بهینه سازی تعداد کشورها ثابت باشد؟

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

• آیا شرایط دیگری را هم می شود برای سقوط امپراطوری و همچنین شرایط همگرائی در نظر گرفت؟

بله. همانند هر الگوریتم دیگری استفاده از هر شرط منطقی برای الگوریتم که وابسته به کاربرد معین است، موجه خواهد بود. شرط توقف به مسئله بهینه سازی بستگی دارد نه الگوریتم. مثلاً در کاربردی ممکن است رسیدن به هزینه 0.0001 کافی باشد. بنابراین شرط توقف را رسیدن به این جواب قرار می دهیم.

• برای مسئله ای که تعداد کشورهای اولیه آن در حدود 300 تا 500 می باشد؛ چه تعداد امپراطوری اولیه برای الگوریتم مناسب می باشد؟

شاید استفاده از 30 تا 50 امپراطوری کافی باشد. تعیین تعداد امپراطوری ها، به صورت یک دهم تعداد کشور ها، معمولاً مناسب خواهد بود. اما ذکر این نکته ضروری است که تعداد امپراطوری های اولیه با اینکه، یکی از پارامترهای آزاد الگوریتم می باشد، اما جزو پارامترهای اساسی آن به حساب نمی آید. سعی و خطا انتخاب یک دهم تعداد کشورهای اولیه را به عنوان تعداد مناسب امپراطوری ها پیشنهاد داده است.

• انتخاب کمتر کشور و بیشتر تکرار ها بهتر هست یا برعکس؟ اگر مثلا تعداد کشورهای اولیه را 40  و تکرار را 100 در نظر بگیریم، بهتر هست یا اینکه تعداد کشورها را 50 و تعداد تکرار را 60 بگیرم؟

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

http://www.icasite.info/2010/08/blog-post_5653.html

تعداد فراخوانی تابع هزینه در الگوریتم رقابت استعماری تقریباً برابر است با تعداد کشورهای اولیه ضرب در تعداد دهه ها (تکرارها). در الگوریتم های ژنتیک نیز این تعداد برابر است با تعداد جمعیت اولیه، ضرب در تعداد نسل ها (تعداد تکرارها). هرچه تعداد فراخوانی تابع هزینه را افزایش دهیم، اصولاً باید به جواب بهتری برسیم. اما این امر به افزایش زمان رسیدن به جواب نیز منجر می شود. بنابراین مستقل از هر گونه تحلیلی، با در نظر گرفتن صورت مسئله مطرح شده در بالا، به احتمال زیاد، در مورد سوال شما، حالت اول (تعداد کشورهای اولیه 40  و تکرار 100، مجموعاً 400 فراخوانی) به جواب بهتری نسبت به حالت دوم (تعداد کشورها 50 و تعداد تکرار 60، مجموعاً 300 فراخوانی) خواهد رسید. اما زمان رسیدن به جواب بیشتر طول می کشد. البته این پیش بینی از قطعیت برخودار نیست و ممکن است بر عکس آن نیز اتفاق بیافتد. آنچه بیان شد، به احتمال زیاد اتفاق می افتد، نه با قطعیت.

اما حال فرض کنیم که حالت های اول و دوم به گونه ای هستند که، مجموع تعداد فراخوانی تابع هزینه در هر دو حالت یکی است. مثلاً دو حالت زیر

1. تعداد کشورها 30 و تعداد تکرار 80
2. تعداد کشورها 80 و تعداد تکرار 30

در چنین حالتی، به قطع نمی شود در مورد کارایی الگوریتم در هر یک از حالات فوق قضاوت کرد. برای یافتن پاسخ باید، چندین بار الگوریتم را اجرا کرد و به دقت به پاسخ ها و نمودارهای همگرایی نگاه کرد. مثلاً اگر در نمودار همگرایی می بینیم که در حالت اول بعد از تکرار 40 ام، دیگر بهبودی در عملکرد الگوریتم با چند بار اجرا کردن حاصل نمی شود، می توانیم به صورت تقریبی به این نتیجه برسیم که این تعداد تکرار (80) برای این حالت زیاد بوده و به نوعی اتلاف انرژی الگوریتم هست. بنابراین تعداد تکرار را کمتر کرده و به همان نسبت تعداد کشور ها را بیشتر می کنیم. بر عکس این کار نیز می تواند اتفاق بیافتد. مثلاً در حالت 2 بالا، ممکن است که ببینیم که نمودار همگرایی الگوریتم به خوبی به صورت نزولی ادامه پیدا می کرد، اما به دلیل رسیدن به 30 تکرار متوقف شد. در چنین حالتی، این نشان دهنده این هست که این تعداد تکرار کم بوده است. بنابراین اگر محدودیت زمان و منابع محاسباتی اجازه داد، با حفظ همان تعداد کشورها (80) تعداد تکرارها را افزایش (به بیشتر از 30) می دهیم. اما اگر منابع محاسباتی ما را محدود کردند، ما نیز با افزایش تعداد تکرارها، تعداد کشورها را کم می کنیم تا در نهایت تعداد فراخوانی تابع هزینه خیلی افزایش پیدا نکند.

در نهایت بعد از مدتی کار کردن با الگوریتم، ممکن است به حسی از میزان مناسب پارامترهای آن برسیم. اما در نهایت باید بدانیم که این پارامترها، اکسیری برای همه مسائل نیستند و ممکن است برای مسائل متفاوت به پارامترهای کاملاً متفاوتی برسیم.

• چگونه می توان در متلب، اعداد تصادفی را به گونه ای ایجاد کرد که دارای میانگین و واریانس مشخصی باشند؟  

ویژگی هایی که گفتید، به توزیع یکتایی نمی رسند. مثلاً با همان ویژگی ها ما می توانیم هم توزیع یکنواخت تولید کنیم و هم توزیع نرمال و هم هر توزیع دیگری. مثلاً

1. برای تولید عدد تصادفی با توزیع یکنواخت از تابع rand استفاده کنید.
2. برای تولید عدد تصادفی با توزیع نرمال از تابع randn استفاده کنید.

برای اینکه عدد تولیدی شما، دارای میانگین M و دارای واریانس V باشد، در هر دو حالت به ترتیب زیر عمل نمایید.

1. >> Number = randn * sqrt(V) + M;
2. >> Number = (rand-0.5) * sqrt(12*V) + M;

برای کسب اطلاعات بیشتر در مورد دلیل دستورات فوق، اطلاعات مرتبط با هر توزیع را در ویکی پدیا ببینید.

برای تست نتیجه، دستور زیر را در متلب اجرا می کنیم.

>> var(a)
ans =
3.9990