پرسش و پاسخ – چند سوال در مورد الگوریتم و کدها به همراه پاسخ

http://www.icasite.info/icasite/post_i/ques_ans.png
دو نفر از دوستان سوالاتی در مورد کدها و نیز خود الگوریتم مطرح کرده اند که به دلیل اینکه به نظر رسید که این سوالات ممکن است برای دیگر دوستان نیز مطرح شود آنها را در قالب یک پست عمومی به همراه پاسخ آنها منتشر می کنیم.
سوالات – بخش یک
“با سلام
  1. در متن آموزشی منتشر شده در مورد الگوریتم در فصل 3 در نموداری که برای سیاسیت جذب (assimilation plicy) رسم شده، محورهای افقی و عمودی متغیرهای ما هستند؟ چرا فقط 2 متغیر وجود دارند. آیا الگوریتم محدود به مسائل با دو متغیر است؟
  2. نسل‌های ۱۰، ۳۰، ۳۳ که در قسمت مثال کاربردی در فصل 3 متن آموزشی آمده اند به چه چیزی اشاره می کنند؟ (آیا نسل ۱۰ یعنی‌ اینکه الگوریتم ۱۰ بار تکرار شده است؟)
  3. منظور از واژهٔ (همگرایی) چیست؟ (مثلاً همگرایی در مثال کاربردی فصل 3 در نسل ۳۳ همگرایی به چه معنی است؟)
  4. تفاوت میان هزینه متوسط یا هزینه میانگین (Mean Cost) و هزینه مینیمم (Minimum Cost) در نمودارها چیست؟

با تشکر”

پاسخ به این سوالات را در ادامه می بینیم. 

http://www.icasite.info/icasite/post_i/ica_conf-715366.jpg

  1. نمودار نشان داده شده در فصل سه برای سیاست جذب، صرفاً به منظور نشان دادن نحوه انجام این بخش از الگوریتم است و همین عملگر به راحتی برای ابعاد بالاتر نیز انجام می شود. همانگونه که در مثالهای فصل چهار و همچنین در اغلب مقالات منتشر شده مشاهده می شود (+)، الگوریتم رقابت استعماری با موفقیت به مسائل بسیاری با ابعاد بسیار بالا اعمال شده و در مقایسه با دیگر روشها نتایج بسیار خوبی از خود نشان داده است.
  2. عبارت “نسل ها” که برگرفته از واژه generations در الگوریتم ژنتیک هستند، همان تعداد تکرار های یک چرخه کامل از الگوریتم را نشان می دهند. مثلاً نسل 10 یعنی اینکه الگوریتم 10 بار سیاستهای جذب، انقلاب و رقابت استعماری و … را طی کرده است. لازم به ذکر است که در متون جدید منتشر شده در مورد الگوریتم رقابت استعماری مشاهده می شود که عبارت “دهه” (Decade) که ارتباط معنایی بیشتری با ماهیت این الگوریتم دارد، به جای “نسل” مورد استفاده قرار می گیرد.
  3. همگرایی در یک الگوریتم می تواند به گونه های مختلفی تعریف شود. مثلاً
    1. رسیدن به تعداد معینی از فراخوانی تابع هزینه. مثلاً پس از 10000 بار فراخوانی تابع هزینه الگوریتم را متوقف می کنیم.
    2. رسیدن به یک جواب معین و راضی کنند. مثلاً رسیدن به هزینه 0.001
    3. داشتن تعداد معینی تکرار بدون بهبود جواب به دست آمده. مثلاً تعیین می کنیم اگر الگوریتم 20 تکرار داشت و اگر نتوانست بیش از 0.00001 هزینه را کمتر کند، متوقف شود.
    4. معیارهای وابسته به الگوریتم. مثلاً هر موقع هزینه میانگین و هزینه مینیمم در الگوریتم ژنتیک با هم برابر شدند. یا سقوط تمام امپراطوری ها در الگوریتم رقابت استعماری. این حالت در نسخه های اولیه این الگوریتم اعمال می شد ولی در نسخه های جدید معمولاً از شرط یک به عنوان شرط توقف این الگوریتم استفاده می شود. استفاده از حالت یک، مقایسه میان دو الگوریتم را راحت تر می کند. برای کسب اطلاعات بیشتر پستی که در مورد نحوه مقایسه دو الگوریتم تکاملی نوشته شده است (+)، را مطالعه نمائید.
  4. در الگوریتم های تکاملی، هزینه متوسط در هر تکرار، میانگین هزینه (Cost) تک تک جوابهای جمعیت است. هزینه مینیمم نیز، کمترین هزینه (بهترین جواب) تا حال حاضر می باشد. نمودار های هزینه میانگین و مینیمم بر حسب تعداد تکرارهای الگوریتم مهم می باشند. بطور ویژه نمودار هزینه مینیمم بر حسب تعداد تکرار میزان موفقیت الگوریتم را گزارش می کند. از روی این نمودارها می توان دو الگوریتم را در توانایی رسیدن به جواب با هم مقایسه نمود. برای کسب اطلاعات بیشتر پستی که در مورد نحوه مقایسه دو الگوریتم تکاملی نوشته شده است (+)، را مطالعه نمائید.
 http://www.icasite.info/icasite/post_i/fig_4_12_l.png
سوالات – بخش دو
“با سلام و تشکر از در اختیار گذاشتن کد ICA،
1) با توجه به مطلبی که در مقاله آمده در ابتدا بعد از تعیین امپریالیستها میبایست بصورت تصادفی مابقی کشورها بین آنها توزیع شوند ولی در کد C# به هر امپریالست متناسب با تعدادی که میتواند colony داشته باشد مستعمره گرفته اما آن امپریایست قوی تر مستعمره ها ی قویتر را دارد اخذ میکند که مسلما کل هزینه اش کمتر از مابقی امپراطوری ها شده. آیا منطقی تر نیست که بار اول کشور ها بصورت تصادفی در مقداردهی اولیه توزیع شوند؟
کد سی شارپ به صورت زیر است.
int j0 = 0;
        for (int i = 0; i < nImp; i++)
{
for (int l = 0; l < N[i]; l++)
{
imp[i].AddColony(col[j0]);
j0++;
            }
        }
2) همچنین متشکر میشوم مرا راجع به درک قطعه کد زیر در کد متلب ICA راهنمایی کنید (قسمتهای رنگی مربوط به تابع زیر)
function Empires = CreateInitialEmpires(InitialCountries,InitialCost,AlgorithmParams, ProblemParams))
 ….

AllImperialistNumOfColonies = round(AllImperialistsPower/sum(AllImperialistsPower) * AlgorithmParams.NumOfAllColonies);

AllImperialistNumOfColonies(end) = AlgorithmParams.NumOfAllColonies – sum(AllImperialistNumOfColonies(1:end-1));

RandomIndex = randperm(AlgorithmParams.NumOfAllColonies);

Empires(AlgorithmParams.NumOfInitialImperialists).ImperialistPosition = 0;

for ii = 1:AlgorithmParams.NumOfInitialImperialists
    Empires(ii).ImperialistPosition = AllImperialistsPosition(ii,:);
    Empires(ii).ImperialistCost = AllImperialistsCost(ii,:);
    R = RandomIndex(1:AllImperialistNumOfColonies(ii)); 

    RandomIndex(AllImperialistNumOfColonies(ii)+1:end);
    Empires(ii).ColoniesPosition = AllColoniesPosition(R,:);
    Empires(ii).ColoniesCost = AllColoniesCost(R,:);
Empires(ii).TotalCost = Empires(ii).ImperialistCost + AlgorithmParams.Zeta * mean(Empires(ii).ColoniesCost);
end for ii = 1:numel(Empires)
    if numel(Empires(ii).ColoniesPosition) == 0
        Empires(ii).ColoniesPosition = GenerateNewCountry(1,ProblemParams);                 %
        Empires.ColoniesCost = feval(ProblemParams.FunctionName,Empires.ColoniesPosition);

    end
end
با تشکرفراوان
پاسخ به این سوالات را در ادامه می بینیم.
1) هزینه (معکوس قدرت) کل یک امپراطوری، برابر هزینه (معکوس قدرت) کشور مرکزی (امپریالیست) به علاوه درصدی (مثلاً یک در صد) از میانگین هزینه مستعمرات آن می باشد. از آنجا که هزینه (معکوس قدرت) امپریالیست تا حد زیادی متفاوت از میانگین هزینه (معکوس قدرت) مستعمرات می باشد و نیز از انجا که فقط در صدر کوچکی در نظر گرفته می شود، بنابراین تاثثر نهایی در قدرت کل را هزینه کشور مرکزی می گذارد. مثلاً اگر هزینه امپریالیست 3 باشد و میانگین هزینه کشور 20 باشد. خواهیم داشت.
TotalCost = 3 + 0.01 * 20 = 3.2
که بسیار به 3 نزدیک است. در برخی موارد حتی این ضریب صفر در نظر گرفته می شود. بنابراین اختصاص قویتر ها به قویترین امپراطوری خیلی در روند کار تاثیر (مثبت یا منفی) نخواهد داشت. البته در نسخه کدهای متلب، اختصاص کشور ها در ابتدای کار به صورت کاملاً تصادفی انجام می شود.
2) تابعی که سوال در مورد آن مطرح شده است، مربوط به ایجاد امپراطوری های اولیه است. این تابع در ابتدای کار یکبار فراخوانی شده و پس از تشکیل امپراطوریهای دیگر فراخوانی نمی شود. کدهای الگوریتم در این لینک موجود هستند.
دستور randperm در متلب، جایگشتهای تصادفی ایجاد می کند. مثلاً 3 بار اجرای دستور randperm برای تعیین جایگشت 5 عدد از 1 تا 5 به صورت زیر در می آید.
>> randperm(5)
ans =
     3     5     1     2     4>> randperm(5)
ans =
     2     4     5     3     1

>> randperm(5)
ans =
     1     3     5     4     2

می بینیم که هر بار ترتیبی تصادفی از اعداد 1 تا 5 تولید شده است. این دستور بهترین انتخاب برای مسائل انتخاب تصادفی و قرعه کشی است. فرض کنیم می خواهیم 5 مستعمره را بین 2 امرپیالیست بصورت تصادفی تقسیم کنیم و به امپریالیستهای اول و دوم به ترتیب 2 و 3 مستعمره بدهیم. یکبار دستور بالا را اجرا می کنیم. سپس 3 اندیس اول را به امپریالیست اول و 2 تای بعدی را به امپریالیست دوم می دهیم. بنابراین در اولین خط قرمز بالا، RandomIndex اندیسهای تصادفی به تعداد مستعمرات موجود هستند.
در بخش بعدی در قسمت نارنجی از روی اندیسهای تصادفی ایجاد شده، تقسیم مستعمرات صورت می گیرد. بطور ویژه خط زیر اندیسهایی را از کل اندیسهای تصادفی ایجاد شده به میزان تعداد مورد نیاز جدا می کند.
R = RandomIndex(1:AllImperialistNumOfColonies(ii));
در ادامه در دو خط زیر می بینیم که مستعمرات یک امپرایالیست از میان کل موجود بر حسب اندیس R فوق انتخاب می شوند.
Empires(ii).ColoniesPosition = AllColoniesPosition(R,:);
Empires(ii).ColoniesCost = AllColoniesCost(R,:);
لازم به ذکز است که در حین بررسی اشتباه کوچک و غیر مهمی دیده شد که اصلاح آن خالی از لطف نخواهد بود. خط کد زیر
RandomIndex(AllImperialistNumOfColonies(ii)+1:end);
باید به خط زیر تغییر یابد.
    RandomIndex = RandomIndex(AllImperialistNumOfColonies(ii)+1:end);
با این کار اندیسهایی که استفاده شده اند، حذف شده و از استفاده دوباره آنها جلوگیری می شود. البته در نهایت همانگونه که در توضیح کدهای سی شارپ عرض شد، این تابع به دلیل اینکه یک بار در اول برنامه فراخوانی می شود و دیگر کاری با آن نداریم، عملاً تاثیر خیلی حاد در روند برنامه نمی گذارد. حتی اگر اشتباهی کوچک در این مرحله اتفاق بیافتد، به شرط کامل بودن براحل بعدی، الگوریتم می توان انتظار جواب مناسب را از آن داشت.
در مورد خط کدهای نشان داده شده با رنگ بنفش، نیز باید این نکته را در نظر گرفت که در بعضی موارد خیلی خاص به ضعیفترین امپریالیست، هیچ مستعمره ای تعلق نمی گرفت (زمانی که هزینه ضعیفترین امپریالیست بسیار بسیار بدتر از هزینه سایر امپریالیست ها بود). این کار باعث می شود تا در ادامه کار برنامه اختلال ایجاد شود. برای جلوگیری از این خطای بسیار نادر ولی مختل کننده، در خطوط بنفش به امپرالیستی که هیچ مستعمره ای نگرفته است، یک مستعمره ایجاد می کنیم تا کدها ادامه یابند. به احتمال زیاد این امپراطوری به دلیل ضعف، در اولین قدم بعد از ایجاد حذف خواهد شد و تاثیر چندانی در روند کار الگوریتم نخواهد داشت.پایان

شما نیز سوالات خود را از طریق بخش تماس با ما (+)، مطرح کنید. اعضای سایت، در زمان مناسب به سوالات شما در مورد الگوریتم رقابت استعماری و نحوه استفاده از آن، در حد بضاعت علمی و زمانی خود، پاسخ خواهند داد.
_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.
صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.



0 پاسخ

ارسال یک پاسخ

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *