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

مفهوم اکتشاف(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.

الگوریتم ژنتیک برای حل مسئله تساوی ساده ریاضی

الگوریتم ژنتیک برای حل مسئله تساوی ساده ریاضی

چکیده

در این مقاله الگوریتم ژنتیک برای افراد مبتدی شرح داده شده است. سپس گام به گام محاسبات عددی الگوریتم ژنتیک برای حل مسئله تساوی ساده ریاضی به طور مختصر توضیح داده شده است.

فلسفه اصلی

الگوریتم ژنتیک به وسیله گلدبرگ که از تئوری تکامل داروین الهام گرفته شده است توسعه یافته است. باقی ماندن یک کروموزوم بستگی به قانون "افراد شایسته تر زنده بمانند" دارد. داروین همچنین اظهار داشت که بقای یک کروموزوم می تواند از طریق تولید مثل، تقاطع و جهش انجام شود.

مثال عددی

فرض کنید تساوی a+2b+3c+4d=30 وجود داشته باشد با استفاده از الگوریتم ژنتیک مقادیر a,b,c,d را به گونه ای یافت شود که تساوی برقرار باشد. در ابتدا باید تابع هدف فرمول بندی شود. که در این مثال هدف مینیم کردن تابع f(x)=a+2b+3c+4d-30 می باشد. چون چهار متغیر در معادله وجود دارد می توان کروموزوم را به شکل 1 ایجاد کرد. 

مقایسه الگوریتم ژنتیک و ممتیک

مقایسه الگوریتم ژنتیک و ممتیک

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

الگوریتم ممتیک با کمک گرفتن از ایده "مم" و پیاده کردن این مفهوم در جستجوهای محلی در ارائه جواب های فعلی در هر نسل سعی بر بهبود محلی این جواب ها می نماید حاصل این عملیات سرعت و کارائی بهتر در فرآیند جستجو می باشد. یکی از ایرادات الگوریتم های تکاملی بدون جستجوی محلی عدم بکارگیری دانش در فرآیند جستجو می باشد. الگوریتم های ترکیبی از جمله ممتیک این ویژگی را دارند که فرآیند جستجوی محلی آنها همراه با دانش می باشد.

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