نحوه پیاده سازی عملی عملگر جذب (Assimilation) در الگوریتم رقابت استعماری - Artificial Intelligence

**Astaraki** · ۱۰-۲۰-۱۳۸۹, ۰۸:۰۷ قبل از ظهر

نحوه پیاده سازی عملی عملگر جذب (Assimilation) در الگوریتم رقابت استعماری

پرسش: من کد متلب ICA را قبلا دانلود کرده ام. اما به نظر می رسد، از AssimilationAngleCoefficient که مربوط به زاویه است، استفاده نشده است. میخواهم بدانم از زاویه تتا (theta) به چه صورت در یک مسئله چند بعدی می شود استفاده کرد؟ از نظر شکلی زاویه قابل درک است ولی در عمل چطور اعمال می شود؟

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

نقش تتا (theta) ایجاد انحراف در مسیر حرکت مستعمره است (شکلهای موجود در متن آموزشی (+) را ببینید). فرض کنید، می خواهیم در دو بعد از نقطه (0,0)، محل مستعمره به سمت نقطه (2,2)، موقعیت استعمارگر حرکت کنیم. فاصله بین این دو نقطه برابر خواهد بود با:

كد:

D = sqrt(4+4) = sqrt(8);

حال با فرض قرار دادن بتا مساوی 2، خواهیم داشت:

كد:

x ~ U(0,Beta*D) ~ U(0,2*sqrt(8))

یعنی x با توزیع یکنواخت در بازه زیر می باشد.

كد:

[0 , 2*sqrt(8)]

داریم:

كد:

2*sqrt(8) = 5.66

حال یک عدد تصادفی بین 0 و 5.66، برای ایجاد x، تولید می کنیم. مثلاً می شود (x=3، به خاطر رند بودن این x در نظر گرفته می شود). اگر زاویه تصادفی "تتا" مطرح نبود، موقعیت جدید مستعمره برابر بود با:

كد:

new_position = (0 , 0) + ((2,2) - (0,0)) / sqrt(8) * 3 = (2.12,2.12);

توجه کنید که ما قرار بود x واحد در جهت بردار متصل کننده مستعمره به امپریالیست حرکت کنیم. در حقیقت ابتدا بردار از مستعمره به استعمار گر (2i+2j) را بر طولش (sqrt(8)) تقسیم می کنیم تا اندازه آن واحد شود. سپس ضرب در x می کنیم تا اندازه اش x واحد و در نهایت مقدار بدست آمده را با موقعیت اولیه مستعمره (0,0)، جمع می کنیم تا موقعیت جدید به دست آید.

شكل: شماي کلي حرکت مستعمرات به سمت امپرياليست.

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

شكل ‏3 6: حرکت واقعي مستعمرات به سمت امپرياليست

آنچه ما می خواهیم بررسی کنیم، نمایش دیگری از دوران است که در پیاده سازی عملی الگوریتم رقابت استعماری پیچیدگی ضرب ماتریس دوران و ... را ندارد و به سادگی قابل تعمیم به ابعاد بالاتر است. بردار زیر را در نظر بگیرید.

كد:

a1 = sqrt(2) * i + sqrt(2) * j;

دوران 45 درجه این بردار در جهت پادساعتگرد برابر خواهد بود با:

كد:

a2 = 0 * i + 2 * j;

دوران 45 درجه این بردار، در جهت ساعتگرد برابر خواهد بود با:

كد:

a3 = 2 * i + 0 * j;

همانگونه که می بینیم، دوران یک بردار تنها کاری که انجام می دهد، این است که بردار جدیدی تولید می کند که اندازه اش، به همان اندازه قبلی است ولی ضرایب i و j تغییر کرده اند. بنابراین به جای ایجاد دوران تصادفی در یک بردار می توان مقادیر مولفه های آن را به صورت تصادفی تغییر داد. این همان کاری است که در اغلب کدهای پیاده سازه شده "الگوریتم رقابت استعماری" که بر روی وب موجود است، استفاده می شود. بدین منظور در یکی از روشها، تک تک مولفه های بردار در اعداد تصادفی مختلف با توزیع یکنواخت در بازه زیر ضرب می شوند.

كد:

R = U(1-gama  ,  1+gama)

این گاما دقیقاً همان گامای قبلی نیست ولی نسبت مستقیمی با آن دارد. اگر گاما صفر باشد، بازه ما می شود [1 , 1]. که عدد تصادفی تولید شده در این بازه نیز قطعاً، 1، می شود. یعنی هیچ کدام از مولفه ها تغییر نمی یابد. با افزایش گاما، میزان دوران نیز افزایش می یابد. اگر مثلاً، گاما را کمی افزایش دهیم و مثلا بکنیم، 0.1، اعدای تصادفی در بازه (1.1 , 0.9) تولید می شوند. مثلاً در حالت دوبعدی دو عدد تولید می کنیم. مثلاً یکی می شود، 0.95 و دیگری می شود، 1.05 در این حالت برداری، مثل بردار زیر

كد:

a4 = 2 * i + 2 * j;

تبدیل خواهد شد به بردار زیر:

كد:

a5 = 2 * 0.95 * i + 2 * 1.05 * j = 1.9 * i + 2.1 * j;

جهت بردار جدید با بردار قبلی یکی نیست و اندازه آنها نیز تقریباً برابرند. بنابراین بردار جدید را می توان دوران بردار قدیم در نظر گرفت. چون جهت آن تغییر یافته و اندازه نیز تقریباً ثابت است. شاید عبارت تقریباً در مساوی بودن اندازه دو بردار، کمی ایجاد سوال کند. ولی به دو دلیل این موضوع خیلی مهم نیست:

برداری که می خواهیم دوران دهیم، خودش حاصل یک پروسه تصادفی است. چون حاصل حرکت مستقیم در راستای مستعمره به سمت امپریالیت با "اندازه تصادفی" است. بنابراین اگر کمی تغییر در اندازه آن به وجود آید که با احتمالات مساوی در جهت افزایش یا کاهش اندازه آن عمل خواهد کرد؛ خیلی اتفاق مهم و ناخواسته ای نیفتاده است. البته اگر اندازه به صورت معنی داری تغییر نکند.
اگر اندازه خیلی تغییر پیدا کند، نیز باز مهم نیست. ما می خواستیم برداری را دوران دهیم که در تغییر جهت آن (دوران) به هدف خود رسیده ایم. حال اگر اندازه آن، آنگونه که ما می خواهیم نیست، باز هم کار بسیار ساده است. بردار جدید (با جهت جدید و با اندازه احتمالاً کمی تغییر یافته) را با بردار قبلی، هم اندازه می کنیم. این هم که بسیار ساده و یک خط کد نویسی به کار اضافه می کند. همین! مثلاً اگر بخواهیم a5 که جهتش با a4 متفاوت است، اندازه اش با آن کاملاً یکی باشد، می نویسیم:

كد:

a6 = (a5 / |a5|) * |a4| = (1.9 * i + 2.1 * j) / sqrt(1.9^2+2.1^2) * sqrt(8) =  (1.9 * i + 2.1 * j) * 0.998752339 = 1.89762944 * i + 2.09737991 * j;

که تقریباً همان بردار قبلی است. اما این بردار دیگر مشکل اندازه متفاوت با بردار اولیه را ندارد. دوران یافته آن هست و اندازه اش هم با آن برابر است.

روند بالا به سادگی قابل تعمیم به هر بعدی است. مستقل از بعد، ما اعداد تصادفی خود را تولید می کنیم و در تک تک مولفه ضرب می کنیم و ....

میزان گاما (gama)، میزان انحراف و دوران را تنظیم می کند. هرچه گاما بیشتر باشد، میزان انحراف بیشتر است و بر عکس. تنظیم مناسب گاما، برای یک مسئله و یا دسته ای از مسائل نیاز به بررسی بیشتری دارد و حتی مستقلاً می تواند، موضوع یک کار پژوهشی مجزا باشد.

منبع :نحوه پیاده سازی عملی عملگر جذب (Assimilation) در الگوریتم رقابت استعماری - پرسش و پاسخ