الگوریتم رقابت استعماری

الگوریتم رقابت استعماری

اسلاید 1: عنوان الگوریتم رقابت استعماری Imperialist Competitive Algorithmاستاد: سرکار خانم دکتر زهرا بهشتی تهیه کننده: معین مردانیEmail: moein.network@gmail.comHobby: Network & VOIP …بسم الله الرحمن الرحیم

اسلاید 2: فهرست مطالبمقدمهالگوریتم رقابت استعماریتشکیل امپراتوری های اولیهسیاست جذب انقلابجابجای موقعیت مستعمره و استعمارگرقدرت یک استعمارگررقابت استعماریمدل سازی رقابت استعماریخلاصه الگریتم

اسلاید 3: فاز مشترک در تمامی الگوریتم‌های هوش جمعی جستجوی دقیق محل‌های احتمالی وجود پاسخ مسأله(Exploitation)جستجوی تمامی فضای ممکن (Exploration)بهترین روش جستجوی تصادفی (Random Search )دارا بودن ویژگی همگرایی به بهترین پاسخ یافته شده

اسلاید 4: تاریخچه الگوریتم رقابت استعماریاین الگوریتم توسط مهندس آتش بس و مرحوم پروفسور لوکس در سال 2007 ایجاد شده است که تفاوت معنایی این الگوریتم با الگوریتم های دیگر در:کم نظیر بودن از لحاظ الهام گرفتن از مسائل سیاسی،فرهنگی و اجتماعی برای ایجاد یک الگوریتم بهینه سازی است

اسلاید 5: مراحل کلی الگوریتم رقابت استعماری ایجاد تعداد مورد نیاز از کشورها تشخیص بهترین کشور(ها) به عنوان استعمارگر(EMPERIALIST)جذب مستعمره (COLONY)توسط کشورهای استعمارگر و تشکیل امپراطوریحرکت کشورهای مستعمره به سمت کشور استعمارگر(Assimilation)انجام عمل Revolutionمقایسه مستعمرات با استعمارگر:درصورتی که مستعمره ای بهتر از استعمارگر خود باشد ،جای آن را می گیرد.5

اسلاید 6: 8 . رقابت بین کشورها و امپراطوری ها برای جذب مستعمره (جذب ضعیف ترین مستعمره از ضعیف ترین امپراطوری توسط بقیه امپراطوری ها با توجه به ارزیابی شاخص مربوط به هر امپراطوری)در صورتی که استعمارگری تمام مستعمرات خود را از دست دهد ، ‌خودش نیز به عنوان یک مستعمره به استعمارگر دیگری منتقل می شود .9. بازگشت به مرحله 4 درصورت تحقق نیافتن شرایط خاتمه الگوریتم10. گزارش پاسخ های بهینه یافته شده 11. پایان ۷. ارزیابی ام‍‍‍پراطوری ها (تشخیص ضویف ترین امپراطوری برای گرفتن مستعمرات آن..)مراحل کلی الگوریتم رقابت استعماری

اسلاید 7:

اسلاید 8: مراحل کلی الگوریتم رقابت استعماری ادامه الگوریتم . . .

اسلاید 9: تشکيل امپراطوري هاي اوليهبراي شروع الگوريتم، ابتدا آرايه اي از متغيرهاي بهنيه سازي تشکيل مي دهيم.در حل مساله بهينه سازي، به دنبال بهترين کشور هستيم يعني بهترين دسته پارامترهاي مسئلهفرهنگسياست اقتصاديزبانمذهب…..

اسلاید 10: تشکیل تعداد امپراتوری مورد نیاز

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

اسلاید 12:

اسلاید 13: سیاست جذب (Assimilation)سياست جذب (همگون سازی) با هدف از خود بي خود كردن كشور مستعمره، با از ميان بردن زبان كشور مستعمره و فرهنگ و رسوم آن کشور، صورت می گیرد. کشورهای استعمارگر، برای افزایش نفوذ خود، شروع به ایجاد عمران (ایجاد زیرساخت‌های حمل و نقل، تاسیس دانشگاه و …) می کنند. به عنوان مثال کشورهایی نظیر انگلیس و فرانسه با تعقیب سیاست جذب در مستعمرات خود در فکر ایجاد انگیس نو و فرانسه نو در مستعمرات خویش بودند. با در نظر گرفتن شیوه نمایش یک کشور در حل مسلئه بهینه‌سازی، در حقیقت این حکومت مرکزی با اعمال سیاست جذب سعی داشت تا کشور مستعمره را در راستای ابعاد مختلف اجتماعی سیاسی به خود نزدیک کند. این بخش از فرایند استعمار در الگوریتم بهینه‌سازی، به صورت حرکت مستعمرات به سمت کشور امپریالیست، مدل شده ‌است.

اسلاید 14: رقابت درون گروهی (نحوه حرکت مستعمرات یک امپراطور به سمت آن)10x𝒕𝒙𝒅=𝒕−𝒙 𝒙 ′ 𝑥 ′ =𝑥+𝛽(𝑡−𝑥) (0≤𝛽≤2)Explorationxexploitation𝜃( −𝜋 4 ≤𝜃≤ 𝜋 4 )

اسلاید 15: 11رقابت درون گروهی (نحوه حرکت مستعمرات یک امپراطوری به سمت امپراطور)x 𝜃 1 𝜃 5 𝜃 4 𝜃 3 𝜃 2

اسلاید 16: انقلاب(REVOLUTION)با توجه به تاریخ امپراتوری ها،مستعمره های یک امپراتوری از نظر ویژگی های اجتماعی ،فرهنگی،اقتصادی و سیاسی جذب میشوند.با این حال ممکن است برخی از این مستعمرات در برابر جذب شدن توسط امپریالیست ها مقاومت کنند.در واقع این مستعمرات نوعی از اصلاحات در ویژگی های خود اعمال میکنند.در ICA به این عمل انقلاب گفته میشود.انقلاب تغییرات تصادفی ناگهانی در موقعیت برخی از مستعمرات در فضای جستجو به وجود می آورد.عملیات انقلاب در ICA درمقایسه با عملیات جهش در GA است که باعث افزایش اکتشاف و مانع از همگرایی اولیه کشورها به بهینه محلی می شود.

اسلاید 17:

اسلاید 18: رقابت برون گروهی (رقابت امپراطوری ها برای کسب ضعیفترین مستعمره در ضعیف ترین امپراطوری)

اسلاید 19: مقدار تابع هدف برای هر امپراطوری𝑭(𝒊𝒎𝒑𝒆𝒓𝒊𝒂𝒍𝒊𝒔𝒕)مقدار تابع هدف برای استعمارگر=𝝃.𝒎𝒆𝒂𝒏(𝑭 𝒄𝒐𝒍𝒐𝒏𝒊𝒆𝒔 )میانگین مقادیر تابع هدف برای مستعمرات+فرض کنیم تابع هدف F 𝑿 باشد :𝑭(𝒊𝒎𝒑𝒆𝒓𝒊𝒂𝒍𝒊𝒔𝒕)مقدار تابع هدف برای استعمارگر=𝝃.𝒎𝒆𝒂𝒏(𝑭 𝒄𝒐𝒍𝒐𝒏𝒊𝒆𝒔 )میانگین مقادیر تابع هدف برای مستعمرات+مقایسه ی امپراطوری ها(𝝃=𝟎.𝟏)

اسلاید 20: نحوه ی استعمار ضعیفترین مستعمره از ضعیفترین امپراطوریبه هر یک از امپراطوری ها یک احتمال برای تسخیر ضعیف ترین مستعمره از ضعیف ترین کولونی تخصیص داده میشود که این مقدار احتمال متناسب با مقدار تابع هدف (فرمول گفته شده در اسلاید قبل )آن امپراطوریست. 13

اسلاید 21: نحوه ی استعمار ضعیفترین مستعمره از ضعیفترین امپراطوری

اسلاید 22: 𝒑 𝒑 𝒏 =| 𝑵.𝑻.𝑪. 𝒏 𝒊=𝟏 𝑵 𝒊𝒎𝒑 𝑵.𝑻.𝑪. 𝒊 |𝑷=[ 𝒑 𝒑 𝟏 , 𝒑 𝒑 𝟐 , 𝒑 𝒑 𝟑 ,…, 𝒑 𝒑 𝑵 𝒊𝒎𝒑 ]𝑹= 𝒓 𝟏 , 𝒓 𝟐 , 𝒓 𝟑 ,…, 𝒓 𝑵 𝒊𝒎𝒑 𝑫=𝑷−𝑹= 𝑫 𝟏 , 𝑫 𝟐 , 𝑫 𝟑 ,…, 𝑫 𝑵 𝒊𝒎𝒑 =[ 𝒑 𝒑 𝟏 − 𝒓 𝟏 , 𝒑 𝒑 𝟐 − 𝒓 𝟐 , 𝒑 𝒑 𝟑 − 𝒓 𝟑 ,…, 𝒑 𝒑 𝑵 𝒊𝒎𝒑 − 𝒓 𝑵 𝒊𝒎𝒑 ]14ایجاد یک ماتریس تصادفی به ابعاد ماتریس مقادیر تابع هدف نرمال شدهامپراطور مربوط به بزرگترین درایه این ماتریس،مستعمره را تسخیر می کندنحوه ی استعمار ضعیفترین مستعمره از ضعیفترین امپراطوری

اسلاید 23: تعداد و نوع تخصیص کشورها به امپراطوری هاتعداد کشورها با توجه به نیاز به دستیابی به جواب(های) دقیق تر متفاوت است. هر چه تعداد کشورهای ایجاد شده بیشتر باشد: - احتمال یافتن پاسخ مناسب بیشتر می شود. - زمان اجرای هر تکرار بیشتر می شود. نحوه ی اختصاص کشور ها به امپراطوری ها در ابتدای الگوریتم با توجه به احتمالات متناسب با هر امپراطوری است(چیزی مشابه آنچه که برای تسخیر گفته شد)16

اسلاید 24: تعداد کشورهای اختصاص داده شده به هر امپراتوری 𝑪 𝒏 = 𝒄 𝒏 −𝐦𝐚 𝐱 𝒄 𝒊 𝒑 𝒏 =| 𝑪 𝒏 𝒊=𝟏 𝑵 𝒊𝒎𝒑 𝑪 𝒊 | 𝑵.𝑪. 𝒏 =round{ 𝒑 𝒏 . 𝑵 𝒄𝒐𝒍 } 17مقدار تابع هدف نرمال شده ی هر امپراطورقدرت نرمال شده هر امپراطورتعداد مستعمره اختصاص داده شده به هر امپراطورتعداد کل کشورهای مستعمره

اسلاید 25: شرایط خاتمهرسیدن به هدف از پیش تعیین شده.رسیدن به زمان،تعداد تکرار یا تعداد فراخوانی تابع هدف(NFE) مشخص.ثابت ماندن یت عدم مشاهده ی بهبود طی زمان،تعداد تکرار یا تعداد فراخوانی تابع هدف(NFE) مشخص.18

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

اسلاید 27: خلاصه الگریتم

اسلاید 28: منابعSolving Euclidean minimal spanning tree problem using a new meta-heuristic approach: Imperialist Competitive algorithm (ICA)S. M. HosseiniDepartment of Industrial and Systems Engineering, Mississippi State University, Mississippi State, USAwww.Matlabsite.com