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

/0 دیدگاه /در , , , , , , /توسط
سوال زیر در رابطه با نحوه پیاده سازی بخش رقابت استعماری در الگوریتم رقابت استعماری مطرح شده است. به دلیل عمومی بودن این سوال، پاسخ آن در قالب یک پست عمومی بر روی سایت قرار می گیرد.
“با درود فراوان،بابت تمامی اطلاعاتی که در مورد 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 بار را برده اند. شما هم با اجرای این برنامه باید، نتایج تقریباً مشابهی بگیرید.
شکل: شمای کلی بخش رقابت استعماری در ICA
روند فوق دقیقاً همان روندی است که در بخش “رقابت استعماری” یا (Imperialistic Competition) در الگوریتم رقابت استعماری انجام می شود (شکل را ببینید). در این بخش مستعمره ضعیف به مانند جایزه و هر استعمارگر به مانند سرمایه گذار در مسئله بالا عمل می کند. در نهایت هر امپراطوری بسته به قدرت (معکوس هزینه خود) احتمالی برای انتخاب این جایزه دارد و مطابق روند بالا قرعه کشی برای تقدیم این جایزه انجام می شود و کشور با قدرت بیشتر نه همیشه ولی در بارهای بیشتری برنده این قرعه کشی (و شاید نزاع خونین) خواهد بود.
این روش را با چرخه رولت (Roulette Wheel) در الگوریتم ژنتیک (Genetic Algorithms) مقایسه کنید. به نظر شما نقطه ضعف و برتری هر روش چیست؟ شما کدام روش را برای استفاده در یک الگوریتم تکاملی مناسب تر می دانید؟ در بخش نظرات، پیشنهادات خود را برای دیگر دوستان مطالعه کننده این پست بیان کرده و تجربیات خود را با آنها به اشتراک بگذارید.
نحوه امتیاز دهی و محاسبه احتمال تصاحب در الگوریتم ICA چگونه است؟
در فصل 3 از متن آموزشی (+) این مورد بطور کامل توضیح داده شده است. فرض کنید 3 امپریالیست داریم با هزینه های کل T.C.i که به ترتیب 10 و 20 و 30 هستند. چگونه مقادیر احتمال را شکل دهیم. ما می خواهیم امراطوری با هزینه کمتر  (قدرت بیشتر) احتمال برنده شدن بیشتری داشته باشد. هزینه نرمالیزه به صورت زیر تعریف می شود.
N.T.C.n = T.C.n  – max{T.C.i}
در مثال بالا می توان نوشت:
T.C.1 = 10
T.C.2 = 20
T.C.3 = 30
برای مقدار max خواهیم داشت:
max{T.C.i} = max{10 , 20 , 30} = 30;
پس هزینه نرمالیزه خواهد بود.
N.T.C.1 = T.C.1 – max{T.C.i} = 10 – 30 = -20
N.T.C.2 = T.C.2 – max{T.C.i} = 20 – 30 = -10
N.T.C.3 = T.C.3 – max{T.C.i} = 30 – 30 =0
حال احتمال تصاحب را تقسیم مقدار قدرمطلق هر N.T.C.n به میزان مجموع قدر مطلق ها حساب می کنیم.
P.p.1 = |-20| / (|-20|+|-10|+|0|) = 20 / 30 = 2/3
P.p.2 = |-10| / (|-10|+|-10|+|0|) = 10 / 30 = 1/3
P.p.3 = |0| / (|-20|+|-10|+|0|) = 0 / 30 = 0/3 = 0
می بینیم که امپراطوری با هزینه پایین تر (شماره یک) به همان میزان احتمال تصاحب بیشتری دارد. ضعیف ترین امپراطوری نیز با احتمال تصاحب صفر، هیچ شانسی برای حفظ مستعمره خود که در معرض رقابت استعماری قرار گرفته است، ندارد. این احتمالات در روند رقابت استعماری (مثال قرعه کشی) که در بالا توضیح داده شد، قرار گرفته و برحسب این مقادیر رقابت برای تصاحب مستعمره مورد مناقشه انجام می شود.
_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.
صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.
0 پاسخ

دیدگاه خود را ثبت کنید

تمایل دارید در گفتگوها شرکت کنید؟
در گفتگو ها شرکت کنید.

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

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