یک معیار جدید جهت ایجاد تعادل بین جستجوی عمومی و محلی در الگوریتم‌های ممتیکی یک معیار جدید جهت ایجاد تعادل بین جستجوی عمومی و محلی در الگوریتم‌های ممتیکی
الموضوعات :
مهدی رضاپور میرصالح
1
(دانشگاه صنعتی امیرکبیر)
محمدرضا میبدی
2
(دانشگاه صنعتی امیرکبیر)
الکلمات المفتاحية: اتوماتاي يادگير الگوريتم ممتيک جستجوي عمومي جستجوي محلي مم,
ملخص المقالة :
یکی از مشکلات الگوریتم‌های ژنتیک سنتی، مشکل همگرایی زودرس است که باعث ناتوانی آنها در جستجوی جواب‌های مناسب می‌شود. یک الگوریتم ممتیک از جستجوی محلی برای افزایش سرعت کشف جواب‌های مناسبی که پیداکردن آنها به وسیله جستجوی عمومی تنها به طول می‌انجامد یا قابل دسترس نباشند، استفاده می‌کند. در این مقاله یک الگوریتم ممتیک مبتنی بر اتوماتای یادگیر به نام LA-MA ارائه شده که از دو بخش ژنتيکي و ممتيکي تشکيل شده است. تکامل يا جستجوي عمومي در بخش ژنتیکی و بهره‌برداری یا جستجوی محلی در بخش ممتیکی انجام می‌شوند. در بخش ممتيکي، احتمال موفقيت جستجوي محلي تخمين زده شده و در صورتي که انجام جستجوي محلي نسبت به جستجوي عمومي مقرون به صرفه باشد، بهره‌برداري انجام مي‌شود. تخمين صحيح احتمال موفقيت جستجوي محلي، باعث ايجاد تعادل بين جستجوي عمومي و محلي شده و کارايي الگوريتم ممتيک را بالا مي‌برد. در این مقاله از دو مسأله بيشينه‌سازي يك‌ها و تناظر گراف جهت ارزيابي كارايي الگوريتم پيشنهادي استفاده شده است. نتايج آزمايش‌ها نشان مي‌دهد كه الگوريتم پيشنهادي از نظر كيفيت جواب‌هاي به دست آمده و نرخ همگرايي نسبت به ساير الگوريتم‌ها عملكرد بهتري دارد.
[1] H. Ishibuchi, S. Kaige, and K. Narukawa, "Comparison between Lamarckian and Baldwinian repair on multiobjective 0/1 knapsack problems," in Evolutionary Multi-Criterion Optimization, C. A. C. Coello, A. H. Aguirre, and Eckart Zitzler, Eds., Springer, 2005, pp. 370-385.
[2] H. Wang, D. Wang, and S. Yang, "A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems," Soft Computing-A Fusion of Foundations, Methodologies, and Applications, vol. 13, no. 8, pp. 763-780, Aug. 2009.
[3] M. Syrjakov and H. Szczerbicka, "Combination of direct global and local optimization methods," in Proc., IEEE Int. Conf. on Evolutionary Computation, vol. 1, pp. 326-333, Dec. 1995.
[4] D. Whitley, V. Gordon, and K. Mathias, "Lamarckian evolution, the Baldwin effect and function optimization," Parallel Problem Solving from Nature-PPSN III, vol. 866, pp. 5-15, Jan. 1994.
[5] D. Molina, M. Lozano, and F. Herrera, "MA-SW-Chains: Memetic algorithm based on local search chains for large scale continuous global optimization," in Proc. IEEE Congress on Evolutionary Computation, CEC'10, 8 pp., 18-23 Jul. 2010.
[6] N. Q. Huy, O. Y. Soon, L. M. Hiot, and N. Krasnogor, "Adaptive cellular memetic algorithms," Evolutionary Computation, vol. 17, no. 2, pp. 231-256, Summer 2009.
[7] W. E. Hart and R. K. Belew, "Optimization with genetic algorithm hybrids that use local searches," in Adaptive Individuals in Evolving Populations, R. K. Belew and M. Mitchell, Ed., Boston: Addison-Wesley Longman Publishing Co., pp. 483-496, 1996.
[8] M. Rezapoor and M. R. Meybodi, "LA-MA: a new memetic model based on learning automata," in Proc. of 18th National Conf. of Computer Society of Iran, 6 pp., Tehran, Iran, 14-16 Mar. 2013.
[9] M. A. Wiering and H. van Hasselt, "Ensemble algorithms in reinforcement learning," IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 38, no. 4, pp. 930-936, Aug. 2008.
[10] K. Najim and A. S. Poznyak, Learning Automata: Theory and Applications, Pergamon Press, Inc., 1994.
[11] M. A. L. Thathachar and P. S. Sastry, Networks of Learning Automata: Techniques for Online Stochastic Optimization, Kluwer Academic Publishers, 2004.
[12] P. Foggia, C. Sansone, and M. Vento, "A database of graphs for isomorphism and sub-graph isomorphism benchmarking," in Proc. of the 3rd Int. Workshop on Graph-Based Representations, pp. 176-187, May 2001.
[13] W. Yuan-Kai, F. Kuo-Chin, and H. Jorng-Tzong, "Genetic-based search for error-correcting graph isomorphism," IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 27, no. 4, pp. 588-597, Aug. 1997.
[14] J. R. Ullmann, "An algorithm for subgraph isomorphism," J. ACM, vol. 23, no. 1, pp. 31-42, Jan. 1976.
[15] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, "A (sub) graph isomorphism algorithm for matching large graphs," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-1372, Oct. 2004.
