بخش رقابت استعماری در ica چگونه مدل می شود؟ - Artificial Intelligence

**Astaraki** · ۰۷-۱۲-۱۳۸۹, ۰۲:۳۴ بعد از ظهر

بخش رقابت استعماری در ICA چگونه مدل می شود؟

سوال:
"با درود فراوان،بابت تمامی اطلاعاتی که در مورد ICA بر روی سایت(محاسبات تکاملی) گذاشته اید، متشکرم. من می‌خوام این ترم ICA را در واحد سمینارم ارائه کنم. تمامی موارد را تقریباً متوجه شدم. ولی‌ در قسمت "رقابت استعماری" اشکال دارم. اینکه بردار P تعریف می‌شه و بعد بردار (رندم) R تعریف می‌شه و در نهایت داریم: D = P - R
اینجاهارو متوجه نمیشم. در صورت امکان لطفاً بنده را در این مورد راهنمایی کنید."

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

فرض کنیم که 4 نفر در بانکی سرمایه گذاری کرده اند و می خواهیم جایزه سفر به دور دنیا را به یکی از آنها بدهیم. هر بانکی برای خود سیاست قرعه کشی خاصی دارد. مثلاً بانکی می گوید "بشتابید! هر پنجاه هزار ریال در هر روز یک امتیاز". بانک دیگر می گوید، "هر 10 هزار ریال در هر ماه یک امتیاز". یا اصلاً بانک دیگر می گوید: "موجودی حساب مهم نیست. موجودی بالای 10 هزار ریال هر چقدر باشد، یک امتیاز". هر یک از سیاست های قرعه کشی فوق به نفع قشر خاصی هستند. مثلاً روش اول برای افراد با سرمایه بالا ولی با حساب متغیر، روش دوم برای افراد با سرمایه بالا ولی با حساب سپرده ثابت و روش آخر هم برای افراد آسیب پذیر و قشر پابرهنه جامعه خوب است و من خودم ترجیح می دهم در چنین قرعه کشی باشم چون با همه سرمایه دارها یک امتیاز خواهم داشت.

از بحث قرعه کشی خارج شویم. بدون توجه به ماهیت روش امتیاز دهی فوق، فرض کنیم 4 نفر به ترتیب امتیاز های زیر را کسب کرده اند.

كد:

Point = [1 2 3 4];

می توان احتمال برنده شدن زیر را به آنها اختصاص داد. توجه کنید که مجموع امتیاز های فوق 10 است. پس امتیازها را تقسیم بر مجموع امتیاز ها می کنیم.

كد:

Probability = [1 2 3 4] / 10 = [0.1  0.2  0.3  0.4];

حال یک بردار تصادفی (رندم) ایجاد می کنیم. این کار را با دکمه rnd در ماشین حساب و یا درستور rand در متلب انجام می دهیم. من با تولید این بردار تصادفی در متلب به نتیجه زیر رسیدم (مطمئن باشید تقلبی در کار نیست!).

كد:

R = 0.82    0.96    0.13    0.91];

حال بیاید R را از P کم کنیم و اندیس ماکزیمم را پیدا کنیم.

كد:

Probability - R = [0.1  0.2  0.3  0.4] - [0.82    0.96    0.13    0.91] = [ -0.71   -0.71    0.17   -0.51];

بیشترین عدد در بردار بالا برابر 0.17 و مربوط به سرمایه گذار سوم است. تکرار بارهای مختلف قرعه کشی با همان احتمالات برنده شدن بالا، نتیجه برنده متفاوتی خواهد داشت. اما ببینیم اگر قرعه کشی 10000 بار تکرار شود، هر سرمایه گذار به ترتیب چند بار برنده می شود؟ یعنی آیا قرعه کشی منصفانه (Fair) است؟ اینگونه نباشد که فردی با سرمایه گذاری بیشتر، در تعداد کمتری برنده شود؟!! برای تست روش قرعه کشی برنامه زیر را در متلب نوشتیم.

كد:

IndexeMat = zeros(1,4);
P = [.1 .2 .3 .4];
for ii = 1:10000
    R = rand(1,4);
    D = P - R;
    Index = find(D == max(D));
    IndexeMat(Index) = IndexeMat(Index) + 1;
end
IndexeMat = IndexeMat

نتیجه یک بار اجرای برنامه (تعداد برنده شدن) در زیر آمده است.

كد:

IndexeMat = [986        1743        2853        4418]

همانطور که می بینید، افراد به ترتیب بسته به امتیازشان (احتمالشان)، تعدادی از این 10000 بار را برده اند. شما هم با اجرای این برنامه باید، نتایج تقریباً مشابهی بگیرید.

روند فوق دقیقاً همان روندی است که در بخش "رقابت استعماری" یا (Imperialistic Competition) در الگوریتم رقابت استعماری انجام می شود. در این بخش مستعمره ضعیف به مانند جایزه و هر استعمارگر به مانند سرمایه گذار در مسئله بالا عمل می کند. در نهایت هر امپراطوری بسته به قدرت (معکوس هزینه خود) احتمالی برای انتخاب این جایزه دارد و مطابق روند بالا قرعه کشی برای تقدیم این جایزه انجام می شود و کشور با قدرت بیشتر نه همیشه ولی در بارهای بیشتری برنده این قرعه کشی (و شاید نزاع خونین) خواهد بود.

این روش را با چرخه رولت (Roulette Wheel) در الگوریتم ژنتیک (Genetic Algorithms) مقایسه کنید. به نظر شما نقطه ضعف و برتری هر روش چیست؟ شما کدام روش را برای استفاده در یک الگوریتم تکاملی مناسب تر می دانید؟

منبع : بخش رقابت استعماری در ica چگونه مدل می شود؟