الگوریتم رقابت استعماری در مقابل دیگر روش های تکاملی

/
/
/

الگوریتم های بهینه‌سازی الهام گرفته از طبیعت به عنوان روشهای هوشمند بهینه‌سازی در کنار روش‌های کلاسیک موفقیت خوبی از خود نشان داده‌اند. از جمله این روش‌ها می‌توان به الگوریتم‌های ژنتیک (الهام گرفته از تکامل بیولوژیکی انسان و سایر موجودات)، بهینه‌سازی کلونی مورچه‌ها (بر مبنای حرکت بهینه مورچه‌ها) و روش بازپخت شبیه‌سازی شده (با الهام‌گیری از فرایند تبرید فلزات) اشاره نمود. الگوریتم‌های بهینه‌سازی معرفی شده، به طور عمده الهام گرفته از فرایند‌های طبیعی می‌باشند و در ارائه این الگوریتم‌ها به سایر نمودهای تکامل انسانی توجهی نشده است. الگوریتم جدیدی برای بهینه‌سازی مطرح شده به نام الگوریتم رقابت استعماری ( Chaotic Imperialist Competitive Algorithm)که نه از یک پدیده طبیعی، بلکه از یک پدیده اجتماعی – انسانی الهام گرفته است. بطور ویژه این الگوریتم به فرایند استعمار، به عنوان مرحله‌ای از تکامل اجتماعی – سیاسی بشر نگریسته و با مدل‌سازی ریاضی این پدیده تاریخی، از آن به عنوان منشأ الهام یک الگوریتم قدرتمند در زمینه بهینه‌سازی بهره می‌گیرد. از آن برای حل مسائل بسیاری در حوزه بهینه‌سازی استفاده شده است.
جهت انتخاب استراتژی مناسب برای حل مسائل بهینه سازی باید شناخت مناسبی از آن داشته باشیم. اگر تابع هزینه مسئله بهینه سازی تابعی از زمان نباشد، با یک مسئله بهینه سازی ایستا سر و کار داریم. ولی اگر زمان نیز وارد تابع هزینه شود مسئله بهینه سازی پویا می شود. به عنوان مثال حرکت از یک نقطه شهر به نقطه دیگر با انتخاب کوتاهترین مسیر یک مسئله بهینه سازی ایستا می باشد. اما اگر پارامترهای دیگری همچون ترافیک که تابعی از زمان است را وارد تابع هزینه بکنیم، با یک مسئله بهینه سازی پویا سر و کار داریم.  اگر متغیر های مسئله بهینه سازی به بازه (و یا قید) خاصی محدود باشند، با یک مسئله بهینه سازی مقید (Constrained Optimization) سروکار داریم و در غیر این صورد مسئله بهینه سازی نا مقید است.  الگوریتم رقابت استعماری با موفقیت بسیاری جهت حل مسائل بهینه سازی مقید مورد استفاده قرار گرفته است . یک مسئله بهینه سازی گسسته مسئله ای است که در آن متغییر های مسئله در یک بازه معین تغییرات گسسته دارند. در حالی که در یک مسئله پیوسته مغییرها در بازه معین تغییرات گسسته دارند. الگوریتم رقابت استعماری در نسخه های اولیه خود تنها برای حل مسائل بهینه سازی پیوسته معرفی شده بود. اما هم اکنون این الگوریتم در نسخه های تغییر یافته خود، به خوبی جهت حل مسائل گسسته نیز مورد استفاده قرار می گیرد.
الگوريتم رقابت استعماری همانند ساير روش هاي بهينه سازي تكاملي، با تعدادي جمعيت اوليه شروع مي شود. در اين الگوريتم، هر عنصر جمعيت، يك كشور ناميده ميشود. كشور ها به دو دسته مستعمره و استعمار گر تقسيم  ميشوند. هر استعمارگر، بسته به قدرت خود، تعدادي از كشورهاي مستعمره را تحت سلطه خود درآورده و آنها را كنترل مي كند. سياست جذب و رقابت استعماري، هسته اصلي اين الگوريتم را تشكيل مي دهند. در الگوریتم رقابت استعماری سياست جذب با حركت دادن مستعمرات يك امپراطوري، مطابق يك رابطه خاص صورت مي پذيرد. اگر در حين حركت، يك مستعمره، نسبت به استعمارگر، به موقعيت بهتري برسد، جاي آن دو با هم عوض مي شوند. در ضمن، قدرت كل يك امپراطوري به صورت مجموع قدرت كشور استعمارگر به اضافه درصدي از قدرت ميانگين مستعمرات آن تعريف مي شود. رقابت استعماري، بخش مهم ديگري از اين الگوريتم را تشكيل مي دهد. در طي رقابت استعماري، امپراطوريهاي ضعيف، به تدريج قدرت خود را از دست داده و به مرور زمان با تضعيف شدن از بين مي روند. رقابت استعماري باعث مي شود كه به مرور زمان، به حالتي برسيم كه در آن تنها يك امپراطوري در دنيا وجود دارد كه آن را اداره مي كند. اين حالت زماني است كه الگوريتم رقابت استعماري با رسيدن به نقطه بهينه تابع هدف، متوقف مي شود.

مزاياي این الگوريتم
الگوريتم رقابت استعماری در وهله اول با داشتن يك ديدگاه كاملاً نو به مبحث بهينه سازي، پيوندي جديد ميان علوم انساني و اجتماعي از يك سو و علوم فني و رياضي از سوي ديگر، برقرار مي كند. الگوريتم رقابت استعماری ، نقطه ي قوت علوم انساني و اجتماعي، يعني كلي نگري و وسعت ديد آن را به خدمت رياضيات درآورده و از آن به عنوان ابزاري براي درك بهتر رياضيات و حل بهتر مسائل رياضي استفاده مي كند.
مزاياي الگوريتم رقابت استعماری را مي توان به صورت زير خلاصه كرد:
–  نو بودن ايده ي پايه اي الگوريتم: به عنوان اولين الگوريتم بهينه سازي مبتني بر يك فراينداجتماعي- سياسي
– توانايي بهينه سازي هم تراز و حتي بالاتر در مقايسه با الگوريتم هاي مختلف بهينه سازي، درمواجهه با انواع مسائل بهينه سازي
–  سرعت مناسب يافتن جواب بهينه
در الگوریتم رقابت استعماری كشورها در حقيقت جوابهاي ممكن مساله هستند و معادل كروموزوم در الگوريتم ژنتيك و ذره در بهينه سازي ازدحامی ذرات هستند. همه ي كشورها، به دو دسته تقسيم مي شوند: امپرياليست و مستعمره
كشورهاي استعمارگر با اعمال سياست جذب (همگون سازي) در راستاي محورهاي مختلف بهينه سازي، كشورهاي مستعمره را به سمت خود مي شكند. رقابت امپرياليستي در كنار سياست همگون سازي، هسته اصلي اين الگوريتم را تشكيل مي دهد و باعث مي شود كه كشورها به سمت مينيمم مطلق تابع حركت كنند.  مستعمره در نتيجه سياست همگون سازي از يك ناحيه مينيمم خارج شده و وارد يك ناحيه مينيمم ديگر مي شود كه در آن وضعيت بهتري را دارا مي باشد. ادامه اين حركت مي تواند به جذب كامل كشور مستعمره در كشور استعمارگر بينجامد. بقاي يك امپراطوري، وابسته به قدرت آن در جذب مستعمرات امپراطوري هاي رقيب و به سيطره در آوردن آنها خواهد بود. در نتيجه، در جريان رقابت هاي امپرياليستي، به تدريج بر قدرت امپراطوري هاي بزرگتر افزوده شده و امپراطوري هاي ضعيف تر، حذف خواهند شد. امپراطوري ها براي افزايش قدرت خود، مجبور خواهند شد تا مستعمرات خود را نيز پيشرفت دهند. با گذشت زمان، مستعمرات، از لحاظ قدرت به امپراطوري ها نزديك تر خواهند شد و شاهد يك نوع همگرايي خواهيم بود. حد نهايي رقابت استعماري، زماني است كه يك امپراطوري واحد در دنيا داشته باشيم، با مستعمراتي كه از لحاظ موقعيت، به خود كشور امپرياليست، خيلي نزديك هستند. در بهينه سازي، هدف يافتن يك جواب بهينه بر حسب متغير هاي مسئله، است. ما يك آرايه از متغير هاي مسئله را كه بايد بهينه شوند، ايجاد مي كنيم. در الگوريتم ژنتيك اين آرايه، كروكوزوم  ناميده مي شود. در اينجا نيز آن را يك كشور مي ناميم. در يك مسئله ي بهينه سازي Nvar بعدی يك كشور، يك آرايه ي ۱X Nvar است. اين آرايه به صورت زير تعريف مي شود:
مقادير متغيره ها در يك كشور، به صورت اعداد اعشاري نمايش داده مي شوند. از ديدگاه تاريخي  فرهنگي، اجزاي تشكيل دهنده يك كشور را مي توان ويژگي هاي اجتماعي– سياسي آن كشور، همچون فرهنگ، زبان، ساختار اقتصادي و ساير ويژگيها در نظر گرفت. در حقيقت در حل يك مسئله بهينه سازي توسط الگوريتم رقابت استعماری، ما به دنبال بهترين كشور (كشوري با بهترين ويژگي هاي اجتماعي  سياسي) هستيم. يافتن اين كشور در حقيقت معادل يافتن بهترين پارامتهاي مسئله است كه كمترين مقدار تابع هزينه را توليد مي كنند.
براي شروع الگوريتم بايد تعدادي از اين كشورها (به تعداد كشورهاي اوليه الگوريتم) ايجاد شوند. بنابراين ماتريس كل كشورها به صورت تصادفي اوليه تشكيل مي شود. براي تقسيم مستعمرات اوليه بين امپريالست ها، به هر امپرياليست، تعدادي از مستعمرات را كه اين تعداد، متناسب با قدرت آن است، مي دهيم. براي انجام اين كار، با داشتن هزينه همه امپرياليست ها، هزينه نرماليزه آن هارا در نظر مي گيريم. هر امپرياليستي كه دراي هزينه بيشتري باشد (امپرياليست ضعيفتري باشد)، داراي هزينه نرماليزه كمتري خواهد بود. با داشتن هزينه نرماليزه، قدرت نسبي نرماليزه هر امپرياليست، محاسبه شده و بر مبناي آن، كشورهاي مستعمره، بين امپريالسيت ها تقسيم مي شوند. با بررسي تاريخي پديده همگون سازي، يك حقيقت آشكار در اين زمينه اين است كه علي رغم اينكه كشوهاي استعمارگر بطور جدي پيگير سياست جذب بودند، اما وقايع بطور كامل مطابق سياست اعمال شده آنها پيش نمي رفت و انحرافاتي در نتيجه كار وجود داشت. در الگوريتم معرفي شده، اين انحراف احتمالي با افزودن يك زاويه تصادفي به مسير جذب مستعمرات، انجام مي گيرد. بدين منظور، در حركت مستعمرات به سمت استعمارگر، كمي زاويه تصادفي نيز به جهت حركت مستعمره، اضافه مي كنيم.
تولید x، با توزیع یکنواخت در بازه بین صفر و بتا ضربدر d انجام می گیرد. که در ان d فاصله میان مستعمره و امپریالیست است. بتا را نیز معمولاً حدود ۲ در نظر می گیریم. وجود ضریب بتا بزرگتر از یک باعث مي‌شود تا کشور مستعمره در حين حرکت به سمت کشور استعمارگر، از جهت‌هاي مختلف به آن نزديک شود. مستعمرات کاملاً تصادفی انتخاب می شوند و هیچ اولویتی بین آنها نیست. در الگوريتم معرفي شده، با افزودن يک زاويه تصادفي به مسير جذب مستعمرات، انحرافی در مسیر حرکت انجام مي‌گيرد. بدين منظور، در حرکت مستعمرات به سمت استعمارگر، کمي زاويه تصادفي نيز به جهت حرکت مستعمره، اضافه مي‌کنيم. بدين منظور اين‌بار به جاي حرکت به اندازه x، به سمت کشور استعمارگر و در جهت بردار واصل مستعمره به استعمارگر، به همان ميزان، ولي با انحراف theta در مسير، به حرکت خود ادامه مي‌دهيم.  thetaرا به صورت تصادفي و با توزيع يکنواخت در نظر مي‌گيريم (اما هر توزيع دلخواه و مناسب ديگر نيز مي‌تواند استفاده شود).
در حين حركت مستعمرات به سمت كشور استعمارگر، ممكن بعضي از اين مستعمرات به موقعيتي بهتر از امپرياليست برسند (به نقاطي در تابع هزينه برسند كه هزينه كمتري را نسبت به مقدار تابع هزينه در موقعيت امپرياليست، توليد مي كنند). در اين حالت، كشور استعمارگر و كشور مستعمره، جاي خود را با همديگر عوض كرده و الگوريتم با كشور استعمارگر در موقعيت جديدادامه يافته و اين بار اين كشور امپرياليست جديد است كه شروع به اعمال سياست همگون سازي بر مستعمرات خود مي كند.
هر امپراطوري اي كه نتواند بر قدرت خود بيفزايد و قدرت رقابت خود را از دست بدهد، در جريان رقابت هاي امپرياليستي، حذف خواهد شد. اين حذف شدن، به صورت تدريجي صورت مي پذيرد. بدين معني كه به مرور زمان، امپراطوري هاي ضعيف، مستعمرات خود را از دست داده و امپراطور يهاي قويتر، اين مستعمرات را تصاحب كرده و بر قدرت خويش مي افزايند. در جريان رقابت هاي امپرياليستي، خواه ناخواه، امپراطوريهاي ضعيف به تدريج سقوط كرده و مستعمراتشان به دست امپراطوري هاي قوي تر مي افتد. شروط متفاوتي را ميتوان براي سقوط يك امپراطوري در نظر گرفت. الگوريتم مورد نظر تا برآورده شدن يك شرط همگرايي، و يا تا اتمام تعداد كل تكرارها، ادامه مي يابد. پس از مدتي، همه امپراطوري ها، سقوط كرده و تنها يك امپراطوري خواهيم داشت و بقيه كشورها تحت كنترل اين امپراطوري واحد، قرار مي گيرند. در اين دنياي ايده آل جديد، همه مستعمرات، توسط يك امپراطوري واحد اداره مي شوند و موقعيت ها و هزينه هاي مستعمرات، برابر با موقعيت و هزينه كشور امپرياليست است. در اين دنياي جديد، تفاوتي، نه تنها، ميان مستعمرات، بلكه ميان مستعمرات و كشور امپرياليست، وجود ندارد. به عبارت ديگر، همه ي كشورها، در عين حال، هم مستعمره و هم استعمارگرند. در چنين موقعيتي رقابت امپرياليستي به پايان رسيده و به عنوان يكي از شروط توقف الگوريتم متوقف مي شود.
الگوریتم رقابت استعماری يك الگوريتم بهينه سازي جدید بر مبناي مدلسازي رياضي فرايند اجتماعي سياسي پديده استعمار است. روش هاي مختلفي براي حل مسائل بهينه سازي معرفي شده اند. بعضي از اين روشها به صورت تكراري و بر مبناي گراديان، نقطه بهينه تابع هزينه را پيدا مي كنند. اين روش ها معمولاً سرعت بالايي دارند ولي درعوض مشكل افتادن در دام بهينه محلي را با خود حمل مي كنند. در نقطه مقابل روش هايي وجود دارند كه به جستجوي نقطه بهينه مطلق تابع مي پردازند. الگوريتم هاي ژنتيك و بهينه سازي گروه ذرات نمونه هايي از اين روش ها هستند. نكته قابل توجه در مورد اكثر روش هاي بهنيه سازي تكاملي مطرح شده، اين است كه اين روش ها معمولاً برگرفته از تكامل زيستي و مدلسازي پديده هاي طبيعي هستند و معمولاً جنبه هايي از تكامل كه مدل شناخته شده اي از آن وجود ندارد، در حاشيه تحقيقاتي قرار گرفته است. در حقيقت انگيزه اصلي الگوریتم های رقابت استعماری پاسخ منفي به این سوال است که: آيا تكامل موجودات و به ويژه انسان، تنها به تكامل زيستي او محدود مي شود؟ و همچنین یافتن پاسخ برای این سوال که آيا جوانب ديگر تكامل انساني مي توانند به عنوان منبع الهام يك الگوريتم بهينه سازي مورد استفاده قرار بگيرند؟ که با توجه به کاربردهای رقابت استعماری متوجه شدیم که پاسخ این سوال مثبت است.
نتايج آزمايش الگوریتم استعماری بر روي توابع هزينه مختلف نشان ميدهد كه الگوريتم معرفي شده در يافتن نقطه بهينه اين توابع كاملاً موفق عمل مي كند. همچنين مسائل مختلف كاربردي حل شده با اين الگوريتم نشان مي دهند كه استراتژي بهينه سازي مطرح شده مي تواند با موفقيت كامل در كنار ساير روش هاي مطرح بهينه سازي همچون الگوريتم ژنتيك و گروه ذرات، به حل مسائل كاربردي و مهندسي كمك كند. مقايسه نتايج حاصله توسط الگوريتم مطرح شده با روش هاي رايج بهينه سازي نيز از برتري نسبي اين الگوريتم حكايت دارد.
مقایسه دو الگوریتم بهینه سازی، به بررسی های زیادی نیاز دارد. در ضمن هر الگوریتمی در دسته خاصی از مسائل خوب جواب خواهد داد. پیدا کردن این دسته برای هر الگوریتم نیز به بررسی زیادی نیاز دارد. البته نتیجه گیریهایی در حد کلی در مورد آنها می توان داشت ولی در نهایت بررسی را به مسئله مورد نظر باید محدود کرد. حتی مسائلی وجود دارند که در آنها جستجوی غیر هوشمند رندم، جوابی بهتر از الگوریتمهای هوشمند و روشهای بهینه سازی تکاملی می دهد. غالب مقالات منتشر شده در مورد الگوریتم رقابت استعماری، حاکی از موفقیت آن در حوزه های مختلف بوده اند. برخی نیز موفقیت آن را در مسائل با بعد بالا گزارش کرده اند. در حالی که در مسائل با بعد پایین خیلی ابراز رضایتی در کار نبوده است.  یکی از مهمترین مزایایی که علاقه مندان حوزه بهینه سازی تکاملی را به سمت استفاده از الگوریتم رقابت استعماری سوق می دهد، جدید و نوپا بودن این الگوریتم و وجود پتانسیل بالاتر تحقیقاتی و انجام کار جدیدتر پژوهشی در آن است.

مراجع
توسعه الگوريتم بهينه سازي اجتماعي و بررسي كارايي آن، دانشگاه تهران، پايان نامه كارشناسي ارشد، اسماعيل آتش پز گرگري
http://artificial.ir/intelligence/thread2117.html
http://www.icasite.info/2010/05/imperialist-competitive-algorithm.html

2 نظرات

  1. سلام مطلب بسیار جامع و کاربردی بودف ممنون بابت وقتی که گذاشتین، الگوریتم رقابت استعماری روز به روز پیشرفت بیشتری می کنه، بنده الگوریتم اصلاح شده رقابت استعماری رو بررسی کردم، این الگوریتم مربوط به مقاله A wide area synchrophasor-based load shedding scheme to prevent voltage collapse است که توی ژورنال Electrical Power and Energy Systems 78 (2016) 248–۲۵۷ چاپ شده و مطمئنم برای دوستان جالبه خواهد بود:
    yon.ir/0mhUQ

نظر بدهید

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

It is main inner container footer text