پایان نامه – بهبود الگوریتم رقابت استعماري از طریق ادغام با الگوریتم تکاملی

 

خانم فاطمه رمضانی در پایان نامه کارشناسی ارشد خود زیر نظر دکتر شهریار لطفی، بر روی ترکیب الگوریتم رقابت استعماری با الگویتم تکاملی کار کرده اند. حاصل این کار در قالب مقاله ای با عنوان “Social-Based Algorithm – SBA” در ژورنال Applied Soft Computing به چاپ رسیده است.

در ادامه مطلب می تواند متن کامل پایان نامه مرتبط با این کار ارزشمند و نیز مقاله منتشر شده بر مبنای آن را دانلود کرده و مطالعه نمایید.

چكيده

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

انبوه کارهای صورت گرفته روز دنيا حاکي از رشد روزافزون کاربرد اين الگوريتم‌ها در مسائل بهينه‌سازي است. به همین دلیل الگوریتم‌های فرامکاشفه‌ای مختلفی در سال‌های اخیر ارائه شده‌اند. بسياري از اين ايده‌ها از ملاحظه و بررسي موجودات گوناگون طبيعت پيرامون الهام مي‌گيرند. براي مثال حرکت جمعي و گروهي ماهيان يا پرندگان منجر به طرح الگوريتم گروه ذارت گرديد. برخي ديگر مانند الگوریتم زنبور از زندگی اجتماعی زنبورها در کنار هم الهام می‌گیرند.

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

واژه‌های كليدي: بهينه‌سازي، غير چند جمله‌اي-سخت، الگوریتم تکاملی، الگوریتم تکاملی غیر خویشاوندی، الگوریتم رقابت استعماری و الگوریتم مبتنی بر اجتماع

فصل اول – مقدمه

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

مسائل بهينه‌سازي بر اساس پيوسته يا گسسته بودن متغيرها به دو دسته کلي تقسيم مي‌شوند. يکي از شاخه‌هاي بهينه‌سازي که با متغيرهاي گسسته سروکار دارد «بهينه‌سازي ترکيبي » است. اين مسائل به دنبال يافتن عنصري از مجموعه متناهي و يا نامتناهي شمارش‌پذير هستند که مي‌تواند عدد صحيح، جايگشت، زيرمجموعه و يا ساختار گراف باشد. بسياري از اين مسائل در دسته مسائل غير چند جمله‌اي-سخت قرار دارند. اين مسائل، مسائلي هستند که هيچ تضميني وجود ندارد که بتوان در زمان قابل قبولي، جواب بهينه را يافت. ساليان زيادي است که محققان به دنبال کشف بهترين الگوريتم‌ها براي حل اين مسائل هستند.

یافتن راه‌حل‌های ممکن مسائل با توجه به ماهیت مختلف ایشان نیازمند روش‌های مختلفی می‌باشند بنابراین الگوریتم‌های گوناگون و متنوعی در دهه‌های اخیر ارائه شده است. بیشتر روش‌های شناخته شده محاسبات تکاملی، به پیاده‌سازی و شبیه‌سازی فرآیندهای زیستی و طبیعی محیط پیرامون می‌پردازند. با نگاهی دقیق‌تر و ریزبینانه‌تر به محیط اطراف می‌توان مصادیق بیشتری را یافت. بنابراین ترکیب دو ایده کاربردی دنیای بهینه‌سازی یعنی ایده تکامل ژنتیکی-زیستی که منجر به پیدایش «الگوریتم تکاملی » و ایده تکامل اجتماعی-سیاسی که منجر به پیدایش «الگوریتم رقابت استعماری » گردید زمینه ایجاد الگوریتمی جدید تحت عنوان «الگوریتم مبتنی بر اجتماع » را فراهم می‌آورد.

بهبودهایی مختلفی در مورد هر دو الگوریتم پایه تکاملی و رقابت استعماری به منظور پیاده‌سازی واقعی‌تر در دنیای پیرامون ارائه می‌شوند. از جمله بهبودهای صورت گرفته در زمینه الگوریتم رقابت استعماری استفاده از مقداردهی‌های اولیه مختلف است. برای مثال ایده تقسیم اولیه قورباغه‌‌ها در «الگوريتم ترکيبي جهش قورباغه » مورد استفاده قرار گرفته است. از ایده گونه‌های مختلف انتخاب رهبر مانند انتخاب ریاست جمهوری در کشورهای جمهوری در دنیای واقعی نیز استفاده شده است و سعی شده است تا به وسیله این ایده الگوریتم رقابت استعماری را بهبود داد.

در الگوریتم تکاملی نیز ایده جفت‌گیری  ایده‌ای قدیمی‌ می‌باشد. عمل جفت‌گیری دو جنسیتی می‌باشد. افراد مختلفی در زمینه جفت‌گزینی‌ بر اساس جنسیت کار نموده‌اند. از طرف دیگر سن نیز عاملی مؤثری در تکامل می‌شود. بنابراین برای هر یک از عامل‌ها جنسیت نر یا ماده و سن تخصیص داده می‌شود. جنسیت به صورت تصادفی با احتمال مساوی تعیین می‌شود. در مورد سن‌گذاری نیز مقدار تابع هدف ارزیابی شده در سن عامل تأثیرگذار است.

علاوه استفاده از ایده‌های اشاره شده، ایده جفت‌گیری گزینشی بر اساس روابط غیر خویشاوندی ارائه شده است که منجر به طراحی «الگوریتم تکاملی غیر خویشاوندی » گردیده است. این ایده از ازدواج در جوامع مذهبی الهام می‌گیرد که افراد اجازه ازدواج با خویشاوندان خود مانند پدر، عمو و خاله را ندارند.

علاوه بر بهبودهای ارائه شده برای هر کدام از الگوریتم‌های تکاملی و رقابت استعماری، ایده اصلی مطرح شده ترکیب این دو می‌باشد. محققان مختلفی سعی در ترکیب این دو روش با هم نموده‌اند اما هیچ‌کدام به ایده زندگی اجتماعی انسان‌ها در دنیای واقعیت نپرداخته‌اند و به صورت جزئی به آن نگاه ننموده‌اند. با توجه به ‌این‌که هر کدام از روش‌های تکاملی و رقابت استعماری جایگاه خاص خودشان را در حل مسائل بهینه‌سازی دارند، ترکیب این دو الگوریتم توانسته است به جواب «نزدیک به ‌بهینه » دست یابد؛ زیرا روش ترکیبی‌ با در نظر گرفتن تکامل فردی و اجتماعی-سیاسی افراد می‌باشد. هر دو الگوریتم مورد بررسی جایگاه مهم و پرکاربردی را بین روش‌های مختلف بهینه‌سازی موجود دارند. بنابراین روش ارائه شده جواب‌های بهتری را از لحاظ کیفیت و پایداری تولید نماید و می‌تواند با سایر روش‌ها به رقابت بپردازد.

در نهایت «الگوریتم غیر خویشاوندی » حاصل به کارگیری تمامی ایده‌های مطرح شده می‌باشد. برای نشان دادن کارآیی الگوریتم‌های ارائه شده، توابع محک مختلفی مورد استفاده قرار گرفته‌اند. هم‌چنین در حل مسائل دنیای واقعی روندیابی سیلاب در رودخانه از آن‌ها استفاده شده است که نتایج نشان دهنده کارآیی بالایی آن‌ها می‌باشد.

فصل دوم شرحی از مسأله مطرح شده، ارائه الگوریتم بهینه‌سازی مبتنی بر اجتماع داده خواهد شد. سپس در فصل سوم به بررسی مفاهیم پایه‌ای مربوط به الگوریتم تکاملی و رقابت استعماری پرداخته خواهد شد. کارهای صورت گرفته به وسیله افراد مختلف از جمله ترکیباتی که در زمینه الگوریتم رقابت استعماری و تکاملی در فصل چهارم آورده خواهد شد. همچنین در این فصل راه‌کارهای ارائه شده برای بهبود الگوریتم‌های رقابت استعماری و تکاملی بررسی می‌شوند. در ادامه این فصل کارهایی که در زمینه  ترکیب دو الگوریتم صورت گرفته‌اند نیز آورده می‌شوند. سپس در فصل پنجم جزئيات و نحوه پياده‌سازي بهبودهای ارائه شده برای این دو الگوریتم و الگوريتم‌های پیشنهادی مبتنی بر اجتماع و غیر خویشاوندی مورد بررسي قرار مي‌گيرند. در فصل ششم نيز نمونه‌اي از مسائل حل شده به وسیله الگوريتم مبتنی بر اجتماع و کارآیی آن در حل توابع محک مختلف بررسی خواهد شد و در نهايت در فصل هفتم، نتيجه‌‌گيري و پيشنهاداتی براي ادامه کار در این زمینه آورده خواهد شد.