بخشی از مقاله
بررسی الگوریتم های بهینه سازی مبتنی بر هوش گروهی
چکیده
بهینه سازی، یکی از حوزه های تحقیقاتی مهم در دهه های اخیر بوده است که نتیجه آن طراحی انواع مختلفی از الگوریتم ها بوده است. در بسیاری از مسائل مهندسی معمولاً با تابع هدفی روبه رو هستیم که میخواهیم آن را بهینه کنیم. در روشهای گروهی، عاملها با هم همکاری مینمایند و رفتار جمعی تمام عاملها باعث یک همگرایی میشود. حال روش های گوناگونی برای رسیدن به این نقطه بهینه وجود دارد که مسلما هر کدام از این روش ها معایبی دارند. در این مقاله الگوریتم های هوش گروهی مانند الگوریتم کلونی مورچه ها، الگوریتم کرم شب تاب و غیره مورد مقایسه قرار گرفته است.
واژه کلیدی: بهینه سازی – هوش گروهی – الگوریتم کلونی مورچه ها
.1 مقدمه
مفهوم بهینه سازیٌ بدین صورت است که در بین پارامترهای یک تابع به دنبال مقادیری باشیم که تابع را کمینه یا بیشینه نماید.کلیه مقادیر مناسب جهت این امر را، راه حل های ممکن و بهترین مقدار از این مقادیر را، راه حل بهینه می نامند. الگوریتم های بهینه سازی هر دو نوع مسائل بیشینه سازی و کمینه سازی را پوشش می دهند. بهینه سازی کاربرد های زیادی در زمینه تخصیص منابع، زمان بندی ها، تصمیم گیری ها و ... را دارد. بهینه سازی همواره با مشکلات فراوانی همراه بوده است. شیوه های سابق برای حل کردن مشکلات بهینه سازی، مستلزم تلاش های محاسباتی بیشماری می باشد. الگوریتم هایی از جمله الگوریتم های هوش جمعیٍ تا حدی این مشکل را حل نموده اند. توسط این الگوریتم ها راه حل هایی پیدا می شوند که تقریبا به جواب نزدیکند.[1] هوش جمعی نوعی روش هوش مصنوعیَ، مبتنی بر رفتار های جمعی می باشد. عامل ها، به طور محلی با یکدیگر و با محیط خود در تعامل هستند. موفق ترین روش های هوش جمعی که تاکنون به وجود آمده اند، روش بهینه سازی کلونی مورچهُ ها ، روش بهینه سازی اجتماع ذراتِ ، روش بهینه سازی زنبور عسلّ و روش بهینه سازی کرم شب تابْ می باشد.
بیشتر الگوریتم های تکاملی الهام خود را از طبیعت دریافت می کنند تا روابط پیچیده، را از شرایط اولیه و ساده درک نمایند. طبیعت مثال کامل و مطلوبی برای بهینه سازی است. هر الگوریتم با ایجاد یک جمعیت اولیه از راه حل های کاربردی آغاز می گردد و به صورت مکرر از نسلی به نسلی دیگر در جهت بهترین راه حل حرکت می کند. در تکرار های موفق الگوریتم، انتخاب در مجموعه ای از راه حل ها انجام می گیرد.[2] این مقاله در 10 بخش، بازبینی و تحقیق در مورد الگوریتم های بهینه سازی، در راستای حوزه های کاربردی مربوطه را ارائه می نماید. در بخش های 2 و3 و4 این مقاله الگوریتم های تکاملی و بخش های 5 تا 9 برخی از الگوریتم های هوش جمعی ارائه شده است. بخش 10 این مقاله نیز نتیجه گیری می باشد.
.2 الگوریتم های ژنتیک َ
ژنتیک یک الگوریتم بهینه سازی احتمالی، با یک پتانسیل جستجوی سراسری می باشد که در سال 1975 توسط Holland ارائه شده است. الگوریتم های ژنتیک جزو موفق ترین دسته از الگوریتم های تکاملی می باشند. از الگوریتم ژنتیک به عنوان یک بهینه ساز تابع یاد شده است. این الگوریتم با مقداردهی اولیه یک مجموعه راه حل (کروموزوم)ُ آغاز می شود. شامل ارائه مجدد مشکل و معمولاً به شکل یک بردار کوچک می باشد. سپس به ازای هر کروموزوم، تناسب را با استفاده از یک تابع برای مشکل ارزیابی می کنند. بر این اساس، بهترین کروموزوم ها در استخر جفتگیری انتخاب می شوند، در آنجا آنها دچار برخورد شده و جهش صورت می گیرد، سپس مجموعه جدیدی از راه حل ها ارائه می شوند. (زاد و ولد)..
الگوریتم های ژنتیک در فضاهایی که جستجو تا حد زیادی پیچیده و ناشناخته می باشند مفید و موثر می باشد. حال اگر تابع تناسب به خوبی تعریف نشده باشد، ممکن است الگوریتم ژنتیک، ماکزیمم محلی را به جای ماکزیمم سراسری انتخاب نماید. در این الگوریتم عملیات بر اساس مجموعه داده های پویا دشوار می باشد و در بعضی موارد الگوریتم های ساده تر بهتر از ژنتیک به جواب دست پیدا می کنند.[1]
.3 الگوریتم استراتژی تکاملیًٌ
یک نمونه دیگر در خانواده الگوریتم های تکاملی، الگوریتم استراتژی تکاملی (DE) می باشد که توسط Storn و Price در سال 1995 ارائه شد. این الگوریتم مشابه ژنتیک می باشد زیرا از جمعیت های افراد برای جستجو به دنبال یک راه حل بهینه استفاده می شود. تفاوت اصلی میان ژنتیک و استراتژی تکاملی، این است که در ژنتیک جهش نتیجه اختلالات کوچکی در ژن های یک فرد می باشد، درحالیکه در تکاملی، جهش نتیجه جفت گیری های حسابی افراد می باشد. در ابتدای فرآیند تکامل، عملگر جهش الگوریتم تکاملی، تمایل به پویش دارد. زمانیکه تکامل پیشرفت می کند، عملگر جهش به بهره کشی تمایل دارد. بنابراین، این الگوریتم به صورت خودکار ترقی های جهش به بهترین مقدار مبتنی بر مرحله فرآیند تکاملی را می پذیرد. جهش در الگوریتم های تکاملی، مبتنی بر یک تابع چگالی احتمال از پیش تعریف شده نمی باشد. این الگوریتم تکاملی ساده اما دقیق می باشد. در این الگوریتم کاربر باید، بهترین مقادیر را برای پارامترهای کنترل وابسته به مشکل بیابد و این یک وظیفه زمانبر می باشد و جزء عیوب این الگوریتم به حساب می آید.[4]
.4 الگوریتم شالیزار برنجٌٌ
الگوریتم شالیزار برنج (PFA) در سال 2009 توسط Premaratne و سایرین ارائه شد که بر طبق یک اصل نزدیکی به راه حل اصلی را عمل می کند. برخلاف الگوریتم تکاملی، دربرگیرنده رفتار مرکب و تقاطع میان افراد نمی باشد و در عوض از گرده افشانی و پراکنده سازی استفاده می کند. این الگوریتم شامل پنج گام اصلی می باشد.
