یک معیار جدید جهت ایجاد تعادل بین جستجوی عمومی و محلی در الگوریتم‌های ممتیکی یک معیار جدید جهت ایجاد تعادل بین جستجوی عمومی و محلی در الگوریتم‌های ممتیکی
محورهای موضوعی : مهندسی برق و کامپیوترمهدی رضاپور میرصالح 1 , محمدرضا میبدی 2
1 - دانشگاه صنعتی امیرکبیر
2 - دانشگاه صنعتی امیرکبیر
کلید واژه: اتوماتاي يادگير الگوريتم ممتيک جستجوي عمومي جستجوي محلي مم,
چکیده مقاله :
یکی از مشکلات الگوریتم‌های ژنتیک سنتی، مشکل همگرایی زودرس است که باعث ناتوانی آنها در جستجوی جواب‌های مناسب می‌شود. یک الگوریتم ممتیک از جستجوی محلی برای افزایش سرعت کشف جواب‌های مناسبی که پیداکردن آنها به وسیله جستجوی عمومی تنها به طول می‌انجامد یا قابل دسترس نباشند، استفاده می‌کند. در این مقاله یک الگوریتم ممتیک مبتنی بر اتوماتای یادگیر به نام LA-MA ارائه شده که از دو بخش ژنتيکي و ممتيکي تشکيل شده است. تکامل يا جستجوي عمومي در بخش ژنتیکی و بهره‌برداری یا جستجوی محلی در بخش ممتیکی انجام می‌شوند. در بخش ممتيکي، احتمال موفقيت جستجوي محلي تخمين زده شده و در صورتي که انجام جستجوي محلي نسبت به جستجوي عمومي مقرون به صرفه باشد، بهره‌برداري انجام مي‌شود. تخمين صحيح احتمال موفقيت جستجوي محلي، باعث ايجاد تعادل بين جستجوي عمومي و محلي شده و کارايي الگوريتم ممتيک را بالا مي‌برد. در این مقاله از دو مسأله بيشينه‌سازي يك‌ها و تناظر گراف جهت ارزيابي كارايي الگوريتم پيشنهادي استفاده شده است. نتايج آزمايش‌ها نشان مي‌دهد كه الگوريتم پيشنهادي از نظر كيفيت جواب‌هاي به دست آمده و نرخ همگرايي نسبت به ساير الگوريتم‌ها عملكرد بهتري دارد.
One of the problems with traditional genetic algorithms is its premature convergence that makes them incapable of searching good solutions of the problem. A memetic algorithm (MA) which is an extension of the traditional genetic algorithm uses a local search method to either accelerate the discovery of good solutions, for which evolution alone would take too long to discover, or to reach solutions that would otherwise be unreachable by evolution or a local search method alone. In this paper, a memetic algorithm based on learning automata (LA) and memetic algorithm, called LA-MA, is introduced. This algorithm is composed of two parts, genetic section and memetic section. Evolution is performed in genetic section and local search is performed in memetic section. The basic idea of LA-MA is to use learning automata during the process of searching for solutions in order to create a balance between exploration performed by evolution and exploitation performed by local search. To evaluate the efficiency of LA-MA, it has been used to solve two optimization problems: OneMax and graph isomorphism problems. The results of computer experimentations have shown that different versions of LA-MA outperform the others in terms of quality of solution and rate of convergence.