متن آموزشی: فصل 3 – بخش 3-3 — الگوريتم رقابت استعماری

شکل 3-2 فلوچارت الگوريتم پيشنهادي را نشان مي‌دهد. همانند ديگر الگوريتم‌هاي تکاملي، اين الگوريتم، نيز با تعدادي جمعيت اوليه تصادفي که هر کدام از آنها يک “کشور” ناميده مي‌شوند؛ شروع مي‌شود. تعدادي از بهترين عناصر جمعيت (معادل نخبه‌ها در الگوريتم ژنتيک) به عنوان امپرياليست انتخاب مي‌شوند. باقيمانده جمعيت نيز به عنوان مستعمره ، در نظر گرفته مي‌شوند. استعمارگران بسته به قدرتشان، اين مستعمرات را با يک روند خاص که در ادامه مي‌آيد؛ به سمت خود مي‌کشند. قدرت کل هر امپراطوري، به هر دو بخش تشکيل دهنده آن يعني کشور امپرياليست (به عنوان هسته مرکزي) و مستعمرات آن، بستگي دارد. در حالت رياضي، اين وابستگي با تعريف قدرت امپراطوري به صورت مجوع قدرت کشور امپرياليست، به اضافه در صدي از ميانگين قدرت مستعمرات آن، مدل شده است.

استفاده از این پست از وبسایت محاسبات تکاملی و الگوریتم رقابت استعماری با ذکر منبع آن بلا اشکال است. بطور ویژه استفاده از مطالب این پست در ویکی پدیا فارسی در مورد الگوریتم رقابت استعماری (در این اینک) تحت لیسانس GNU بلامانع می باشد.

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

شكل ‏3 2: فلوچارت الگوريتم پيشنهادي

با گذشت زمان، مستعمرات، از لحاظ قدرت به امپراطوري‌ها نزديک‌تر خواهند شد و شاهد يک نوع همگرايي خواهيم بود. حد نهايي رقابت استعماري، زماني است که يک امپراطوري واحد در دنيا داشته باشيم، با مستمراتي که از لحاظ موقعيت، به خود کشور امپرياليست، خيلي نزديک هستند.

در ادامه مباحث اين فصل، بخش‌هاي مختلف الگوريتم، مورد بررسي قرار مي‌گيرند.

3-3-1 شکل دهي امپراطوري‌هاي اوليه
در بهينه‌سازي، هدف يافتن يک جواب بهينه بر حسب متغير‌هاي مسئله، است. ما يک آرايه از متغير‌هاي مسئله را که بايد بهينه‌ شوند، ايجاد مي‌کنيم. در الگوريتم ژنتيک اين آرايه، کروکوزوم ناميده مي‌شود. در اينجا نيز آن را يک کشور مي‌ناميم. در يک مسئله‌ي بهينه‌سازي ${N_{var}}$ بعدي، يک کشور، يک آرايه‌ي $1 \times {N_{var}}$ است. اين آرايه به صورت زير تعريف مي‌شود.

$country\, = \,[{p_1},\,{p_2},\,{p_3},\,...,\,{p_{{N_{var}}}}]\,$

مقادير متغيره‌ها در يک کشور، به صورت اعداد اعشاري نمايش داده مي‌شوند. از ديدگاه تاريخي‌ـ‌فرهنگي، اجزاي تشکيل دهنده يک کشور را مي‌توان ويژگي هاي اجتماعي– سياسي آن کشور، همچون فرهنگ، زبان، ساختار اقتصادي و ساير ويژگي‌ها در نظر گرفت. شکل 3-3 اين مسئله را به خوبي نشان مي‌دهد. مطابق اين شکل متغيرهاي مجهول تابع هزينه که ما در طي فرايند بهينه‌سازي به دنبال انها مي‌گرديم، در نگاه اجتماعي‌ـ‌سياسي ويژگي‌هاي تاريخي و فرهنگي‌اي هستند که يک کشور را به نقطه مينيمم تابع هزينه رهنمون مي‌سازند. در حقيقت در حل يک مسئله بهينه‌سازي توسط الگوريتم معرفي شده، ما به دنبال بهترين کشور (کشوري با بهترين ويژگي هاي اجتماعي‌ـ‌سياسي) هستيم. يافتن اين کشور در حقيقت معادل يافتن بهترين پارامتهاي مسئله است که کمترين مقدار تابع هزينه را توليد مي‌کنند.

شكل ‏3 3: اجزاي اجتماعي سياسي تشکيل دهنده يک کشور

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

$countr{y_i}\, = \,[K{P_i},\,K{I_i},\,K{D_i}]\,$

براي شروع الگوريتم بايد تعدادي از اين کشورها (به تعداد کشورهاي اوليه الگوريتم) ايجاد شوند. بنابراين ماتريس کل کشورها به صورت تصادفي اوليه تشکيل مي‌شود.

هزينه‌ي يک کشور با ارزيابي تابع f در متغير‌هاي $({p_1},\,{p_2},\,{p_3},\,...,\,{p_{{N_{{{\rm var}} }}}})$ يافته مي‌شود. بنابراين

$cos{t_i}\, = \,\,f(countr{y_i})\, = \,f({p_1},\,{p_2},\,{p_3},\,...,\,{p_{{N_{{{\rm var}} }}}})$

در مسئله طراحي کنترل کننده، با هدف در نظر گرفته شده، اين تابع به صورت زير خواهد بود.

F = w1×MaxOvershoot + w2× IAE

که در آن MaxOvershoot ماکزيمم فراجهش و IAE انتگرال قدر مطلق خطا است. w1 و w2 نيز وزنهايي هستند که ميزان اهميت هر يک از هدف‌ها را نشان مي‌دهند. بنابراين کاري که براي بدست آوردن هزينه يک کشور (دسته پارامتهاي کنترل کننده PID) بايد انجام شود، اين است که هر دسته از اين ضرايب به عنوان کنترل کننده در نظر گرفته شده و پاسخ پله سيستم براي اين کنترلر بدست مي‌آيد. در نهايت با محاسبه ماکزيمم فراجهش و انتگرال قدر مطلق خطا، مجموع آنها را به عنوان هزينه اين کشور (ضرايب کنترل کننده) محاسبه مي‌شود. ما به دنبال بهترين کشور (بهترين دسته ضرايب کنترل کننده) مي‌گرديم. الگوريتم معرفي شده در اين نوشتار، با توليد يک دسته اوليه از اين ضرايب و دسته بندي آنها در قالب امپراطوري‌ها و اعمال سياست جذب از طرف استعمارگران به روي مستعمرات و همچنين با ايجاد رقابت استعماري ميان امپراطوريها به جستجوي بهترين کشور مي‌پردازد.

براي شروع الگوريتم، تعداد ${N_{country}}$ کشور اوليه را ايجاد مي‌کنيم. ${N_{imp}}$ تا از بهترين اعضاي اين جمعيت (کشورهاي داراي کمترين مقدار تابع هزينه) را به عنوان امپرياليست انتخاب مي‌کنيم. باقيمانده ${N_{imp}}$ تا از کشورها، مستعمراتي را تشکيل مي‌دهند که هرکدام به يک امپراطوري تعلق دارند. براي تقسيم مستعمرات اوليه بين امپريالست‌ها، به هر امپرياليست، تعدادي از مستعمرات را که اين تعداد، متناسب با قدرت آن است، مي‌دهيم. براي انجام اين کار، با داشتن هزينه همه امپرياليست‌ها، هزينه نرماليزه آن‌ها را به صورت زير در نظر مي‌گيريم.

${C_n}\, = \, {\max }\limits_i \{ {c_i}\} \, - \,{c_n}$

که در آن ${c_n}$ ، هزينه امپريالست nام، ${\max }\limits_i \{ {c_i}\}$ بيشترين هزينه ميان امپرياليست‌ها و ${C_n}$ ، هزينه نرماليزه شده اين امپرياليست، مي‌باشد. هر امپرياليستي که دراي هزينه بيشتري باشد (امپرياليست ضعيفتري باشد)، داراي هزينه نرماليزه کمتري خواهد بود. با داشتن هزينه نرماليزه، قدرت نسبي نرماليزه‌ي هر امپرياليست، به صورت زير محاسبه شده و بر مبناي آن، کشورهاي مستعمره، بين امپريالسيت‌ها تقسيم مي‌شوند.

${p_n}\, = \,\left| {\frac{{{C_n}}}{{\sum\limits_{i = 1}^{{N_{imp}}} {{C_i}} }}} \right|$

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

$N.C{._n}\, = \,round\{ {p_n}\,.\,({N_{col}})\}$

که در آن $N.C{._n}$ ، تعداد اوليه مستعمرات يک امپراطوري و ${N_{col}}$ نيز تعداد کل کشورهاي مستعمره موجود در جمعيت کشورهاي اوليه است. round نيز تابعي است که نزديک‌ترين عدد صحيح به يک عدد اعشاري را مي‌دهد. با در نظر گرفتن N.C. براي هر امپراطوري، به اين تعداد از کشورهاي مستعمره اوليه را به صورت تصادفي انتخاب کرده و به امپرياليست nام مي‌دهيم. با داشتن حالت اوليه تمام امپراطوري‌ها، الگوريتم رقابت استعماري شروع مي‌شود. روند تکامل در يک حلقه قرار دارد که تا برآورده شدن يک شرط توقف، ادامه مي‌يابد.

شکل 3-4 چگونگي شکل‌گيري امپراطوري‌هاي اوليه را نشان مي‌دهد. همانگونه که در اين شکل نشان داده شده است. امپراطوري‌هاي بزرگتر، تعداد بيشتري مستعمره دارند. در اين شکل، امپريالست شماره 1 قوي‌ترين امپراطوري را ايجاد کرده است و بيش‌ترين تعداد مستعمرات را دارد.

شكل ‏3 4: چگونگي شکل‌گيري امپراطوري‌هاي اوليه.

3-3-2 مدل‌سازي سياست جذب: حرکت مستعمره‌ها به سمت امپرياليست
سياست همگون‌سازي (جذب) با هدف تحليل فرهنگ و ساختار اجتماعي مستعمرات در فرهنگ حکومت مرکزي انجام مي‌گرفت. همانگونه که قبلاً نيز بيان شد، کشورهاي استعمارگر، براي افزايش نفوذ خود، شروع به ايجاد عمران (ايجاد زيرساخت‌هاي حمل و نقل، تاسيس دانشگاه و …) کردند. به عنوان مثال کشورهايي نظير انگليس و فرانسه با تعقيب سياست همگون‌سازي در مستعمرات خود در فکر ايجاد انگيس نو و فرانسه نو در مستعمرات خويش بودند. با در نظر گرفتن شيوه نمايش يک کشور در حل مسلئه بهينه‌سازي، در حقيقت اين حکومت مرکزي با اعمال سياست جذب سعي داشت تا کشور مستعمره را در راستاي ابعاد مختلف اجتماعي سياسي به خود نزديک کند. اين بخش از فرايند استعمار در الگوريتم بهينه‌سازي، به صورت حرکت مستعمرات به سمت کشور امپرياليست، مدل شده است. شکل 3-5، شماي کلي اين حرکت را نشان مي‌دهد.

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

مطابق اين شکل کشور امپرياليست کشور مستعمره را در راستاي محورهاي فرهنگ و زبان به سمت خود جذب مي‌کند. همانگونه که در اين شکل نشان داده شده است، کشور مستعمره (Colony)، به اندازه x واحد در جهت خط واصل مستعمره به استعمارگر (Imperialist)، حرکت کرده و به موقعيت جديد (New Position of Colony)، کشانده مي‌شود. در اين شکل، فاصله ميان استعمارگر و مستعمره با d نشان داده شده است. x نيز عددي تصادفي با توزيع يکنواخت (و يا هر توزيع مناسب ديگر) مي‌باشد. يعني براي x داريم.

$x\, \sim \,U(0\,\,,\,\,\beta \times d)$

که در آن $\beta$ عددي بزرگتر از يک و نزديک به 2 مي‌باشد. يک انتخاب مناسب مي‌تواند $\beta \, = \,2$ باشد. وجود ضریب بتا بزرگتر از یک باعث مي‌شود تا کشور مستعمره در حين حرکت به سمت کشور استعمارگر، از جهت‌هاي مختلف به آن نزديک شود.

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

با بررسي تاريخي پديده همگون‌سازي، يک حقيقت آشکار در اين زمينه اين است که علي رغم اينکه کشوهاي استعمارگر بطور جدي پيگير سياست جذب بودند، اما وقايع بطور کامل مطابق سياست اعمال شده آنها پيش نمي‌رفت و انحرافاتي در نتيجه کار وجود داشت. در الگوريتم معرفي شده، اين انحراف احتمالي با افزودن يک زاويه تصادفي به مسير جذب مستعمرات، انجام مي‌گيرد. بدين منظور، در حرکت مستعمرات به سمت استعمارگر، کمي زاويه تصادفي نيز به جهت حرکت مستعمره، اضافه مي‌کنيم. شکل 3-6 اين حالت را نشان مي‌دهد. بدين منظور اين‌بار به جاي حرکت به اندازه x، به سمت کشور استعمارگر و در جهت بردار واصل مستعمره به استعمارگر، به همان ميزان، ولي با انحراف $\theta$ در مسير، به حرکت خود ادامه مي‌دهيم. $\theta$ را به صورت تصادفي و با توزيع يکنواخت در نظر مي‌گيريم (اما هر توزيع دلخواه و مناسب ديگر نيز مي‌تواند استفاده شود). پس

$\theta \,\, \sim \,\,U( - \gamma \,,\,\,\gamma )$

در اين رابطه، $\gamma$ پارامتري دلخواه مي‌باشد که افزايش آن باعث افزايش جستجوي اطراف امپرياليست شده و کاهش آن نيز باعث مي‌شود تا مستعمرات تا حد ممکن، به بردار واصل مستعمره به استعمارگر، نزديک حرکت کنند. با در نظر گرفتن واحد راديان براي $\theta$ ، عددي نزديک به π/4، در اکثر پياده‌سازي ها، انتخاب مناسبي بوده است.

3-3-3 جابجايي موقعيت مستعمره و امپرياليست
سياست جذب در عين نابودي ساختارهاي اجتماعي سياسي کشور مستعمره در بعضي موارد نتايج مثبتي را نيز براي آانها در پي داشت. بعضي از کشور در نتيجه اعمال اين سياست به نوعي از خودباوري عمومي دست يافتند و پس از مدتي همان تحصيلکرده‌گان (به عبارت ديگر جذب شدگان فرهنگ استعماري) بودند که به رهبري ملت خود براي رهايي از چنگال استعمار پرداختند. نمونه هاي فراواني از اين موارد را مي‌توان در مستعمرات انگليس و فرانسه يافت. از سوي ديگر نگاهي به فراز و نشيب چرخش قدرت در کشور‌ها به خوبي نشان مي‌دهد که کشور هايي که زماني در اوج قدرت سياسي – نظامي بودند، پس از مدتي سقوط کردند و در مقابل کشورهايي سکان قدرت را در دست گرفتند که زماني هيچ قدرتي در دست نداشنتد. در مدلسازي اين واقعه تاريخي در الگوريتم معرفي شده به اين صورت عمل شده است که در حين حرکت مستعمرات به سمت کشور استعمارگر، ممکن بعضي از اين مستعمرات به موقعيتي بهتر از امپرياليست برسند (به نقاطي در تابع هزينه برسند که هزينه کمتري را نسبت به مقدار تابع هزينه در موقعيت امپرياليست، توليد مي‌کنند.) در اين حالت، کشور استعمارگر و کشور مستعمره، جاي خود را با همديگر عوض کرده و الگوريتم با کشور استعمارگر در موقعيت جديد ادامه يافته و اين اين بار اين کشور امپرياليست جديد است که شروع به اعمال سياست همگون‌سازي بر مستعمرات خود مي‌کند. تغيير جاي استعمارگر و مستعمره، در شکل 3-7 نشان داده شده است. در اين شکل، بهترين مستعمره‌ي امپراطوري، که هزينه‌اي کمتر از خود امپرياليست دارد، به رنگ تيره‌تر، نشان داده شده است. شکل 3-8، کل امپراطوري را پس از تغيير موقعيت‌ها، نشان مي‌دهد.

شكل ‏3 7: تغيير جاي استعمارگر و مستعمره

شكل ‏3 8: کل امپراطوري، پس از تغيير موقعيت‌ها

3-3-4 قدرت کل يک امپراطوري

قدرت يک امپراطوري برابر است با قدرت کشور استعمارگر، به اضافه درصدي از قدرت کل مستعمرات آن. بدين ترتيب براي هزينه کل يک امپراطوري داريم.

$T.C{._n}\, = \,Cost(imperialis{t_n})\, + \xi \,mean\{ Cost(colonies\,of\,empir{e_n})\}$

که در آن $T.C{._n}$ هزينه کل امپراطوري nام و $\xi$ عددي مثبت است که معمولاً بين صفر و يک و نزديک به صفر در نظر گرفته مي‌شود. کوچک در نظر گرفتن $\xi$ ، باعث مي‌شود که هزينه کل يک امپراطوري، تقريباً برابر با هزينه حکومت مرکزي آن (کشور امپرياليست)، شود و افزايش $\xi$ نيز باعث افزايش تاثير ميزان هزينه مستعمرات يک امپراطوري در تعيين هزينه کل آن مي‌شود. در حالت نوعي $\xi \, = \,0.05$ در اکثر پياده‌سازي به جوابهاي مطلوبي منجر شده است.

3-3-5 رقابت استعماري
همانگونه که قبلاً نيز بيان شد، هر امپراطوري‌اي که نتواند بر قدرت خود بيفزايد و قدرت رقابت خود را از دست بدهد، در جريان رقابت‌هاي امپرياليستي، حذف خواهد شد. اين حذف شدن، به صورت تدريجي صورت مي‌پذيرد. بدين معني که به مرور زمان، امپراطوري‌هاي ضعيف، مستعمرات خود را از دست داده و امپراطوري‌هاي قويتر، اين مستعمرات را تصاحب کرده و بر قدرت خويش مي‌افزايند. براي مدل کردن اين واقعيت‌، فرض مي‌کنيم که امپراطوري در حال حذف، ضعيف‌ترين امپراطوري موجود است. بدين ترتيب، در تکرار الگوريتم، يکي يا چند تا از ضعيف‌ترين مستعمرات ضعيف‌ترين امپراطوري را برداشته و براي تصاحب اين مستعمرات، رقابتي را ميان کليه امپراطوري‌ها ايجاد مي‌کنيم. مستعمرات مذکور، لزوماً توسط قويترين امپراطوري، تصاحب نخواهند شد، بلکه امپراطوري‌هاي قويتر، احتمال تصاحب بيشتري دارند. شکل 3-9 شماي کلي اين بخش از الگوريتم را نشان مي‌دهد.

شكل ‏3 9: شماي کلي رقابت استعماري: امپراطوري‌هاي بزرگ‌تر، با احتمال بيشتري، مستعمرات امپراطوري‌هاي ديگر را تصاحب مي‌کنند.

در اين شکل امپراطوري شماره 1 به عنوان ضعيف‌ترين امپراطوري در نظر گرفته شده و يکي از مستعمرات آن در معرض رقابت امپرياليستي قرار گرفته است و امپراطوريهاي 2 تا N براي تصاحب آان با هم رقابت مي‌کنند. براي مدل‌سازي رقابت ميان امپراطوري‌ها براي تصاحب اين مستعمرات، ابتدا احتمال تصاحب هر امپراطوري (که متناسب با قدرت آن امپراطوري مي‌باشد)، را با در نظر گرفتن هزينه کل امپراطوري، به ترتيب زير محاسبه مي‌کنيم. ابتدا از روي هزينه کل امپراطوري، هزينه کل نرماليزه شده آن را تعيين مي‌کنيم.

$N.T.C{._n}\, = \, {\max }\limits_i \{ T.C{._i}\} \, - \,T.C{._n}$

در اين رابطه $T.C{._n}$ ، هزينه کل امپراطوري nام و $N.T.C{._n}$ نيز، هزينه کل نرماليزه شده آن امپراطوري مي‌باشد. هر امپراطوري‌ که $T.C{._n}$ کمتري داشته باشد $N.T.C{._n}$ بيشتري خواهد داشت. در حقيقت $T.C{._n}$ معادل هزينه کل يک امپراطوري و $N.T.C{._n}$ معادل قدرت کل آن مي‌باشد. امپراطوري با کمترين هزينه، داراي بيشترين قدرت است. با داشتن هزينه کل نرماليزه شده، احتمال (قدرت) تصاحب مستعمره رقابت، توسط هر امپراطوري، به صورت زير محاسبه مي‌شود.

${p_{{p_n}}}\, = \,\left| {\frac{{N.T.C{._n}}}{{\sum\limits_{i = 1}^{{N_{imp}}} {N.T.C{._i}} }}} \right|$

با داشتن احتمال تصاحب هر امپراطوري، مکانيزمي همانند چرخه رولت در الگوريتم ژنتيک مورد نياز است تا مستعمره مورد رقابت را با احتمال متناسب با قدرت امپراطوريها در اختيار يکي از آنها قرار دهد. در کنار امکان استفاده از چرخ رولت موجود، در اين نوشتار مکانيزم جديدي براي پياده‌سازي اين فرايند معرفي شده است که نسبت به چرخه رولت داراي هزينه محاسباتي بسيار کمتري مي‌باشد. زيرا عمليات نسبتاً زياد مربوط به محاسبه تابع توزيع جمعي احتمال را که در چرخه رولت مورد نياز است را حذف مي‌کند و فقط به داشتن تابع چگالي احتمال نياز دارد. در ادامه مکانيزم مطرح شده براي اختصاص متناسب با احتمال مستعمره مورد رقابت به امپراطوري هاي رقيب توضيح داده مي‌شود.

با داشتن احتمال تصاحب هر امپراطوري، براي اينکه مستعمرات مذکور را به صورت تصادفي، ولي با احتمال وابسته به احتمال تصاحب هر امپراطوري، بين امپراطوري‌ها تقسيم کنيم؛ بردار P را از روي مقادير احتمال فوق، به صورت زير تشکيل ميدهيم.

${\bf{P}}\, = \,\left[ {{p_{{p_1}}},\,{p_{{p_2}}},\,{p_{{p_3}}},\,...,\,{p_{{p_{{N_{imp}}}}}}} \right]$

بردار P داراي سايز 1*Nimp مي‌باشد و از مقادير احتمال تصاحب امپراطوري‌ها تشکيل شده است. سپس بردار R تصادفي ، همسايز با بردار را تشکيل مي‌دهيم. آرايه‌هاي اين بردار، اعدادي تصادفي با توزيع يکنواخت در بازه [0,1] مي‌باشند.

${\bf{R}} = \,\left[ {{r_1},\,{r_2},\,{r_3},\,...,\,{r_{{N_{imp}}}}} \right]$

${r_1},\,{r_2},\,{r_3},\,...,\,{r_{{N_{imp}}}}\, \sim \,\,U(0,1)$

سپس بردار D را به صورت زير تشکيل مي‌دهيم.

${\bf{D}}\,{\bf{ = }}\,{\bf{P}}\,{\bf{ - }}\,{\bf{R}}\, = \,\left[ {{D_1},\,{D_2},\,{D_3},\,...,\,{D_{{N_{imp}}}}} \right]$

${\bf{ = }}\,\,\left[ {{p_{{p_1}}} - {r_1},{p_{{p_2}}} - {r_2},\,{p_{{p_3}}} - {r_3},...,{p_{{p_{{N_{imp}}}}}} - {r_{{N_{imp}}}}} \right]$

با داشتن بردار D، مستعمرات مذکور را به امپراطوري‌اي مي‌دهيم که انديس مربوط به آن در بردار D بزرگتر از بقيه مي‌باشد. امپراطوري‌اي که بيشترين احتمال تصاحب را داشته باشد، با احتمال بيشتري انديس مربوط به آن در بردار D، بيشترين مقدار را خواهد داشت. عدم نياز به محاسبه CDF باعث مي‌شود که اين مکانيزم نسبت به چرخه رولت با سرعت به مراتب بيشتري عمل کند. مکانيزم جديد مطرح شده نه تنها مي‌تواند در اختصاص مستعمره به امپراطوري بر حسب احتمال تصاحب آنها مفيد باشد، بلکه به عنوان يک مکانيزم انتخاب بر حسب احتمال مي‌تواند جايگزين چرخه رولت در الگوريتم ژنتيک براي انتخاب والدين شود و سرعت اجراي عمليات در آن را تا حد زيادي افزايش دهد.

با تصاحب مستعمره توسط يکي از امپراطوري ها، عمليات اين مرحله از الگوريتم نيز به پايان مي‌رسد.

3-3-6 سقوط امپراطوري‌هاي ضعيف
همانگونه که بيان شد، در جريان رقابت‌هاي امپرياليستي، خواه ناخواه، امپراطوريهاي ضعيف به تدريج سقوط کرده و مستعمراتشان به دست امپراطوري‌هاي قوي‌تر مي‌افتد. شروط متفاوتي را مي‌توان براي سقوط يک امپراطوري در نظر گرفت. در الگوريتم پيشنهاد شده، يک امپراطوري زماني حذف شده تلقي مي‌شود که مستعمرات خود را از دست داده باشد. شکل 3-10 اين مسئله را به خوبي نشان مي‌دهد. در اين شکل، امپراطوري شماره 4 به علت از دست دادن کليه مستعمراتش، ديگر قدرتي براي رقابت ندارد و بايد از ميان بقيه امپراطوري‌ها حذف شود.

3-3-7 همگرايي
الگوريتم مورد نظر تا برآورده شدن يک شرط همگرايي، و يا تا اتمام تعداد کل تکرارها، ادامه مي‌يابد. پس از مدتي، همه امپراطوري‌ها، سقوط کرده و تنها يک امپراطوري خواهيم داشت و بقيه کشورها تحت کنترل اين امپراطوري واحد، قرار مي‌گيرند. در اين دنياي ايده‌آل جديد، همه‌ي مستعمرات، توسط يک امپراطوري واحد اداره مي‌شوند و موقعيت‌ها و هزينه‌هاي مستعمرات، برابر با موقعيت و هزينه کشور امپرياليست است. در اين دنياي جديد، تفاوتي، نه تنها، ميان مستعمرات، بلکه ميان مستعمرات و کشور امپرياليست، وجود ندارد. به عبارت ديگر، همه‌ي کشورها، در عين حال، هم مستعمره و هم استعمارگرند. در چنين موقعيتي رقابت امپرياليستي به پايان رسيده و به عنوان يکي از شروط توقف الگوريتم متوقف مي‌شود. شبه کد مربوط به الگوريتم پيشنهادي در شکل 3-11، نشان داده شده است.

شكل ‏3 10: سقوط امپراطوري‌ ضعيف؛ امپراطوري شماره 4، به علت از دست دادن کليه مستعمراتش، ديگر قدرتي براي رقابت ندارد و بايد از ميان بقيه امپراطوري‌ها حذف شود.

شكل ‏3 11: شبه کد مربوط به الگوريتم رقابت استعماري

شماي کلي الگوريتم به صورت گرافيکي در شکل 3-12 نيز نشان داده شده است. مطابق اين شکل، الگوريتم با جمعيت اوليه تصادفي و تشکيل امپراطوري هاي اوليه آغاز شده و در يک چرخه سياست جذب و زقابت امپرياليستي تکرار مي‌شوند.

شكل ‏3 12: شماي کلي الگوريتم توسعه داده شده

_______________________________________________

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

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

چکیده

فصل 1 مقدمه
1-1 هدف و اهميت مسئله
1-2 الگوريتم توسعه داده شده
1-3 مزاياي الگوريتم توسعه داده شده
1-4 ساختار نوشتار

فصل 2 بهينه‌سازي و روشهاي موجود
2-1 انواع مسائل بهينه‌سازي
2-2 روش‌هاي بهينه‌سازي کمينه‌جو
2-2-1 بهينه‌سازي تحليلي
2-2-2 جستجوي خط
2-2-3 روش‌هاي نيوتوني
2-2-4 روش کاهشي نِلدِر ـ ‌ميد با اشکال غير مرکب
2-3 الگوريتم‌ ژنتيک
2-4 الگوريتم بازپخت شبيه‌سازي شده
2-5 بهينه‌سازي گروه ذرات
2-6 کلوني مورچه‌ها
2-7 برنامه‌ريزي ژنتيک

فصل 3 استراتژي بهينه‌سازي مبتني بر تکامل اجتماعي‌ـ‌سياسي
3-1 مقدمه
3-2 مروري تاريخي بر پديده استعمار
3-2-1 هند
3-2-2 مالزي
3-2-3 هندوچين فرانسه
3-2-4 هند شرقي (اندونزي)
3-3 الگوريتم پيشنهادي
3-3-1 شکل دهي امپراطوري‌هاي اوليه
3-3-2 مدل‌سازي سياست جذب: حرکت مستعمره‌ها به سمت امپرياليست
3-3-3 جابجايي موقعيت مستعمره و امپرياليست
3-3-4 قدرت کل يک امپراطوري
3-3-5 رقابت استعماري
3-3-6 سقوط امپراطوري‌هاي ضعيف
3-3-7 همگرايي
3-4 مثال کاربردي
3-5 نتيجه‌گيری
3-6 توابع هزينه مورد استفاده

فصل 4 پياده‌سازي هاي انجام شده
4-1 استفاده از الگوريتم معرفي شده براي طراحي يک کنترل‌کننده PID بهينه
4-1-1 کنترل‌کننده PID
4-1-2 طراحي کنترل‌کننده PID بهينه توسط الگوريتم رقابت استعماري
4-1-3 نتيجه‌گيري
4-2 استفاده از الگوريتم رقابت امپرياليستي براي طراحي کنترل‌کننده PID چند متغيره براي سيستم صنعتي ستون تقطير
4-2-1 مقدمه
4-2-2 کنترل‌کننده PID براي فرايند چند متغيره
4-2-3 نتايج شبيه‌سازي
4-2-4 نتيجه‌گيري
4-3 الگوريتم رقابت استعماري؛ ابزاري براي يافتن نقطه تعادل نش
4-3-1 يک بازي غير خطي استاتيک ساده
4-3-2 يک بازي با پيچيدگي بيشتر
4-4 طراحي بهينه آنتهاي آرايه‌اي
4-5 استفاده از الگوريتم رقابت استعماري براي شناسايي ويژگي مواد از آزمون فرورفتگي
4-5-1 مقدمه
4-5-2 توصيف مسئله معکوس
4-5-3 حل مسئله معکوس توسط الگوريتم رقابت استعماري
4-5-4 نتيجه‌گيری
4-6 کنترل فازي اتومبيل
4-6-1 مدل اتومبيل
4-6-2 نتايج

فصل 5 خلاصه، نتيجه‌گيري و پيشنهادات

فصل 6 مراجع

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

نکته دیگر قابل ذکر این است که الگوریتم رقابت استعماری در حال حاضر در نسخه های مختلف و با تغییراتی نسبت به نسخه اولیه آن توسط دانشجویان و محققین حوزه بهینه سازی مورد استفاده قرار می گیرد. متن آموزشی ارائه شده بر روی سایت ورژن اولیه و نسخه ابتدایی الگوریتم رقابت استعماری می باشد. برای آشنایی با نسخه های جدیدتر الگوریتم می توانید به برخی از مقالات ارائه شده بر روی سایت مراجعه نمایید.

_____________________________________________

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

صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.

____________________________________

فیلم های آموزشی در زمینه هوش مصنوعی و برنامه نویسی متلب

متن آموزشی: فصل 3 – بخش 3-3 — الگوريتم رقابت استعماری

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

دیدگاهتان را بنویسید لغو پاسخ

لینک های جالب

صفحات

دسته ها

بایگانی