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

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

4-3-1 يک بازي غير خطي استاتيک ساده

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

يک بازي با دو بازيکن با توابع هزينه معرفي شده زير را در نظر بگيريد.

${f_1}({x_1},{x_2}) = {({x_1} - 1)^2} + {({x_1} - {x_2})^2}$

${f_2}({x_1},{x_2}) = {({x_2} - 3)^2} + {({x_1} - {x_2})^2}$

با استفاده از روش تحليلي، نقطه تعادل نش اين بازي به صورت زير بدست مي‌آيد.

${\rm{ }} \Rightarrow {\rm{ }}\left\{ {\begin{matrix} {x_1^* = \frac{5}{3} = 1.6667} \\ {x_2^* = \frac{7}{3} = 2.3333} \\ \end{matrix}} \right.$ $\Rightarrow {\rm{ }}\left\{ {\begin{matrix} {{x_2} = 2{x_1} - 1} \\ {{x_2} = \frac{{{x_1} + 3}}{2}} \\ \end{matrix}} \right.$ $\left\{ {\begin{matrix} {\frac{{\partial {f_1}({x_1},{x_2})}}{{\partial {x_1}}} = 0} \\ {\frac{{\partial {f_2}({x_1},{x_2})}}{{\partial {x_2}}} = 0} \\ \end{matrix}} \right.{\rm{ }}$

بنابراين نقطه تعادل نش اين گيم ساده (x*1,x*2) = (1.6667,2.3333) با مقادير ارزش تبادل (0.88889, 0.88889) مي‌باشد. اين مقادير براي ارزيابي نتايج حاصل از اعمال الگوريتم ژنتيک و الگوريتم رقابت استعماري مورد استفاده قرار خواهند گرفت. براي الگوريتم ژنتيک در اين مساله از جمعيت اوليه برابر با 20 و نرخ جهش 2/0 و نرخ توليد 5/0 استفاده شده است و الگوريتم معرفي شده نيز با 20 کشور اوليه که 5 تا از آنها به عنوان امپرياليست انتخاب شده اند، بهينه‌سازي مساله را انجام داده است.

شكل ‏4 15: شماي کلي الگوريتم رقابت استعماري، اعمال شده به مسئله تعيين نقطه تعادل نش. ناحيه داخل خط‌چين مربوط به الگوريتم و بقيه مربوط به مسئله مي‌باشد.

شکل 4-15 شماي کلي اعمال الگوريتم معرفي شده به مسئله تعيين نقطه تعادل نش را نشان مي‌دهد. بخش آبي رنگ داخل خط چين، مروبط به الگوريتم مي‌باشد. شکلهاي 4-16 و 4-17 نيز همگرايي هزينه براي الگوريتم ژنتيک و الگوريتم استعماري را نشان مي‌دهند. همانگونه که از دياگرامهاي همگرايي نشان داده شده بر مي‌آيد، الگوريتم رقابت استعماري به نزديک و حتي نسبتاً بهتري نسبت به الگوريتم ژنتيک رسيده است. هر دو الگوريتم توانسته اند به همان جواب تحليلي مساله برسند. البته مساله در نظر گرفته شده فقط براي نشان دادن شيوه اعمال الگوريتم معرفي شده در زمينه نظريه بازي‌ها بود و مساله بسيار ساده‌اي بوده و براي به چالش کشيدن دو الگوريتم موفق بهينه‌سازي مناسب نمي‌باشد.

شكل ‏4 16: همگرايي هزينه براي الگوريتم ژنتيک

شكل ‏4 17: همگرايي هزينه براي الگوريتم رقابتي استعماري

4-3-2 يک بازي با پيچيدگي بيشتر

دو تابع معيار زير را در نظر مي‌گيريم.

${f_1}({x_1}) = 4{x_1}$

${f_2}({x_1},{x_2}) = g({x_2}).h({f_1}({x_1}),g({x_2}))$

که در آن

$h({f_1},g) = \left\{ {\begin{matrix} {1 - {{(\frac{{{f_1}}}{g})}^\alpha }{\rm{ if }}{f_1} \le g} \\ {0{\rm{ otherwise}}} \\ \end{matrix}} \right.$

$\alpha = 0.25 + 3.75(g({x_2}) - 1)$

x1 و x2 استراتژي بازي هستند. در اين بخش مي‌خواهيم با استفاده از الگوريتم معرفي شده، نقطه تعادل نش اين توابع را بيابيم. بررسي دقيقتر اين مسئله بهينه‌سازي 2 هدفه نشان مي‌دهد که اين مسئله داراي يک مجموعه پرتو عام محدب و يک مجموعه پرتو محلي مقعر است. شکل 4-18 نحوه پخش را براي 50000 جفت نقاط تصادفي (x1,x2) در بازه [0 , 1] نشان مي‌دهد.

شكل ‏4 18: نحوه پخش (f1,f2) براي 50000 نقطه تصادفي

حال هر دو روش الگوريتم ژنتيک و الگوريتم معرفي شده (ICA) را به مساله فوق اعمال مي‌کنيم. با همان تنظيمات قبلي براي الگوريتم هاي فوق، هيچ کدام نتوانستند به نقطه تعادل نش برسند. بنابران تعداد جمعيت اوليه الگوريتم ژنتيک و تعداد کشورهاي اوليه الگوريتم استعماري افزايش داده شدند. اما همانگونه که در شکل‌هاي زير نشان داده شده است، با افزايش جمعيت تا 200 به همراه افزايش تعداد تکرارها، الگوريتم ژنتيک نتوانست به نقطه تعادل نش سيستم دست پيدا کند. اين در حالي است که الگوريتم رقابت استعماري در تعداد کشور اوليه 35 توانست به نقطه تعادل (x*1, x*2)=(0, 0.20002) با توابع معيار (0,1) دست پيدا کند که اين مقدار بر روي منحني پرتو قرار دارد. شکل هاي زير همگرايي الگوريتم ژنتيک و الگوريتم رقابت استعماري را نشان مي‌دهد.

شكل ‏4 19: همگرايي الگوريتم ژنتيک

شكل ‏4 20: همگرايي الگوريتم معرفي شده

4-4 طراحي بهينه آنتهاي آرايه‌اي

شکل زير سيستم آنتن آرايه‌اي را نشان ميدهد. در اين آنتنها هدف، نتظيم وزنهاي w با هدف داشتن بيشترين SINR مي‌باشد.

شكل ‏4 21: شماي کلي يک آنتن آرايه اي

در اين پياده‌سازي از الگوريتم معرفي شده و نيز الگوريتم ژنتيک، جهت تعيين بهينه وزنهاي آنتن استفاده شده است. پارامترهاي الگوريتم ژنتيک و الگوريتم رقابت استعماري مطابق جداول 4-4 و 4-5 زير مي‌باشند.

جدول ‏4 4: پارامتهاي مورد استفاده در الگوريتم رقابت استعماري

جدول ‏4 5: پارامتهاي مورد استفاده در الگوريتم ژنتيک

نمودار همگرايي اين دو الگوريتم نيز در زير نشان داده شده اند.

شكل ‏4 22: نمودار همگرايي الگوريتم رقابت استعماري و الگوريتم ژنتيک

شکلهاي زير نيز نتايج مقايسه الگوهاي آنتن شکل يافته را توسط الگوريتم رقابت استعماري، الگوريتم ژنتيک و يک الگوريتم کلاسيک موسوم به LMS را نشان مي‌دهند.

شكل ‏4 23: مقايسه LMS با الگوريتم ژنتيک

شكل ‏4 24: مقايسه الگوي الگوريتم ژنتيک و الگوريتم معرفي شده

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

_______________________________________________

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

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

چکیده

فصل 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 را نیز مطالعه نمایید.

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

_____________________________________________

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

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

____________________________________

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

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

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

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

لینک های جالب

صفحات

دسته ها

بایگانی