SI: Swarm Intelligence

مفهوم اکتشاف و بهره وری در الگوریتم های جستجوی تکاملی

مفهوم اکتشاف(Exploration) و بهره وری (Exploitation) در الگوریتم های جستجوی تکاملی

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

به Exploration یک جستجوی تصادفی هم گفته می شود چون از کل فضای جواب به طور تصادفی یک جواب یا مجموعه ای جواب را انتخاب می کند. تصادفی بودن جستجو در اکتشاف، الگوریتم را قادر به خروج از بهینه محلی به منظور کاوش در سطح جهانی فضای جستجو می سازد. به Exploitation جستجوی همسایگی هم گفته می شود چرا که در هر تکرار بهترین جواب در همسایگی جواب بهینه جاری که امکان بهبود دارد یافت می شود.(شکل 1)

شکل 1: نحوه عملکرد فاکتورهای اکتشاف و استخراج در فضای جواب مسئله

 

انواع جستجو در الگوریتم های بهینه سازی

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

الگوریتم های فراابتکاری از نظر جواب به دو دسته مبتنی بر یک جواب و مبتنی بر جمعیت تقسیم می شود. براساس تعداد جواب الگوریتم ها و انواع جستجوی یعنی محلی بودن یا تصادفی بودن در شکل 2 یک فضای الگوریتم فراابتکاری طراحی گردیده است که تنوع راه حل ها به دلیل اکتشاف بالا در قسمت چپ نمودار می باشد و از طرفی تشدید و بهبود راه حل ها در سمت راست نمودار به دلیل استخراج بالا و داشتن جستجوی محلی رخ می دهد.

منظور از Diversification یا تنوع تولید راه حل های گوناگون به منظور کاوش فضای جستجو در مقیاس جهانی می باشد. در حالی که Intensification یا تشدید به معنی تمرکز بر جستجو در یک ناحیه محلی می باشد که این کار به وسیله استخراج اطلاعات برای رسیدن به یک راه حل خوب فعلی در این ناحیه صورت می گیرد.

شکل 2: طراحی فضای جستجوی الگوریتم های فراابتکاری

اکتشاف یا استخراج؟

دو راهی اکتشاف یا استخراج نشان می دهد که هر دو به طور انحصاری بکاربرده شوند با شکست مواجه خواهند شد. بدین منظور بسیاری از الگوریتم ها به طور ترکیبی عمل می کنند. به عنوان مثال در جدول 1 الگوریتم ژنتیک و جستجوی محلی از نظر اکتشاف و استخراج مقایسه شده است.  که نشان دهنده این است که ترکیب این دو الگوریتم یعنی ممتیک از نظر اکتشاف و استخراج وضعیت مناسبی دارد.

نحوه رفتار  همگرائی و کارائی در اکتشاف و استخراج

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

بررسی عملکرد چند الگوریتم تکاملی از حیث اکتشاف ، استخراج و نرخ همگرائی

الگوریتم ژنتیک در کل همگرائی کمی دارد چون میزان اکتشاف آن قوی می باشد و باید در کل فضای جواب مسئله جستجو انجام شود به همین دلیل رسیدن به جواب بهینه سراسری به دلیل تنوع بیشتر جواب ها زمان برتر خواهد بود.الگوریتم تکامل تفاضلی یا DE وضعیت اکتشاف بالائی دارد ولی از نظر استخراج ضعیف عمل می کند. به عبارت دیگر در استخراج راه حل مسئله کند عمل می کند. الگوریتم BBO از قابلیت استخراج بالائی برخوردار است ولی در بحث اکتشاف ضعیف عمل می کند. به موجب اینکه عملگر مهاجرت در BBO در هر بار روی یک ژن اعمال می گردد به همین دلیل سرعت همگرائی آن پایین می باشد. به همین دلیل مقالات متعددی روی عملگر مهاجرت آن کار کرده اند و به صورت ترکیبی با دیگر الگوریتم های تکاملی آن را بهبود داده اند و موجب افزایش سرعت همگرائی آن شده است.

جدول 1: مقایسه الگوریتم های ژنتیک و جستجوی محلی از نظر مفاهیم استخراج و اکتشاف

نام الگوریتم

اکتشاف

استخراج

سرعت همگرائی

الگوریتم ژنتیک

زیاد

کم

پایین

جستجوی محلی

کم

زیاد

بالا

الگوریتم تکامل تفاضلی

زیاد

کم

پالا

الگوریتم BBO

کم

زیاد

پایین

الگوریتم ممتیک

زیاد

زیاد

متوسط

 

[1] http://cdn.persiangig.com/download/M5foYS1rhQ/9182_0_YangDebFong_meta.pdf/dl

[2] http://cdn.persiangig.com/download/6ZDpC6mNJD/07550912.pdf/dl.