ارائه يک مدل جديد ممتيکي مبتني بر اتوماتاي يادگير ساختار ثابت
محورهای موضوعی : مهندسی برق و کامپیوتر
مهدي رضاپور ميرصالح
1
(دانشگاه پیام نور تهران)
محمدرضا میبدی
2
(دانشگاه صنعتی امیرکبیر)
کلید واژه: الگوريتم ممتيک مم جستجوي محليجستجوي عمومياتوماتاي يادگيراتوماتاي مهاجرت اشيا,
چکیده مقاله :
الگوريتم ممتيک يکی از انواع الگوريتم‌هاي تکاملي است که با استفاده از جستجوي عمومي و جستجوي محلي فضاي حل مسأله را به صورت بهينه جستجو مي‌نمايد. تعادل بين جستجوي عمومي و محلي، همواره يکی از مسايل مهم در اين دسته از الگوريتم‌ها است. در اين مقاله يک مدل جديد ممتيکي با نام 2GALA ارائه شده است. اين مدل از ترکيب الگوريتم ژنتيک و اتوماتاي مهاجرت اشيا که نوع خاصي از اتوماتاي يادگير ساختار ثابت می‌باشد، تشکيل شده است. در مدل ارائه‌شده جستجوي عمومي توسط الگوريتم ژنتيک و يادگيري محلي به وسيله اتوماتاي يادگير انجام مي‌شود. در اين مدل جهت افزايش سرعت همگرايي و فرار از همگرايي زودرس، به طور هم‌زمان از دو مدل يادگيري لامارکي و بالدويني استفاده شده است. در اين مدل تکاملي، جهت استفاده توأم از اثرات مثبت تکامل و يادگيري محلي، کروموزم‌ها به وسيله اتوماتاي مهاجرت اشيا بازنمايي شده‌اند. جهت نمایش برتری مدل ارائه‌شده نسبت به سایر روش‌های موجود، از این مدل برای حل مسأله تناظر گراف استفاده گردیده است.
Memetic algorithm (MA) is a kind of evolutionary algorithms (EAs) that searches the problem solving space using local search and global search. The balance between global search and local search is one of the key issues in this algorithm. In this paper a new model is proposed, called GALA2. This model is combined of genetic algorithm (GA) and object migration automata (OMA), which is a kind of fixed-structure learning automaton. In the proposed model, global search is performed by genetic algorithm and local learning is performed by learning automata. In this model, the Lamarckian and Baldwinian learning models have been used to increase the convergence rate and avoidance of premature convergence, simultaneously. In this evolutionary model, chromosomes are represented by object migration automata for the purpose of using positive effects of evolution and local learning. In order to show the superiority of the proposed model, GALA2 is used to solve the graph isomorphism problem.
[1] C. Xianshun, O. Yew-Soon, L. Meng-Hiot, and T. Kay Chen, "A multi-facet survey on memetic computation," IEEE Trans. on Evolutionary Computation, ,vol. 15, no. 5, pp. 591-607, Oct. 2011.
[2] Q. H. Nguyen, Y. S. Ong, and N. Krasnogor, "A study on the design issues of memetic algorithm," in Proc. CEC IEEE Congress on Evolutionary Computation, pp. 2390-2397, Singapore, Singapore, 25-28 Sept.. 2007.
[3] N. Krasnogor and J. Smith, "A tutorial for competent memetic algorithms: model, taxonomy, and design issues," IEEE Trans. on Evolutionary Computation, vol. 9, no. 5, pp. 474-488, Oct. 2005.
[4] J. Hong and V. Prabhu, "Distributed reinforcement learning control for batch sequencing and sizing in just-in-time manufacturing systems," Applied Intelligence, vol. 20, no. 1, pp. 71-87, Jan. 2004.
[5] 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.
[6] K. S. Narendra and M. A. L. Thathachar, Learning Automata: an Introduction, Prentice-Hall, Inc., 1989.
[7] M. A. L. Thathachar and P. S. Sastry, "Varieties of learning automata: an overview," IEEE Trans. on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 32, no. 6, pp. 711-722, Dec. 2002.
[8] K. Najim and A. S. Poznyak, Learning Automata: Theory and Applications, Pergamon Press, Inc., 1994.
[9] M. A. L. Thathachar and P. S. Sastry, Networks of Learning Automata: Techniques for Online Stochastic Optimization, Kluwer Academic Publishers, 2004.
[10] M. Rezapoor Mirsaleh and M. R. Meybodi, "A hybrid algorithm for solving graph isomorphism problem," in Proc. of the 2nd Int. Conf. on Information and Knowledge Technology, IKT'05, 13 pp., Tehran, Iran, 24-26 May 2005.
[11] M. Rezapoor Mirsaleh and M. R. Meybodi, "A learning automata-based memetic algorithm," Genetic Programming and Evolvable Machines, vol. 16, no. 4, pp. 399-453, Dec. 2015.
[12] M. Rezapoor Mirsaleh and M. R. Meybodi, "Balancing exploration and exploitation in memetic algorithms: a learning automata approach," Computational Intelligence, vol. 34, no. 1, pp. 282-309, Feb. 2018.
[13] A. Rezvanian and M. R. Meybodi, "A new learning automata‐based sampling algorithm for social networks," International J. of Communication Systems, vol. 3, no. 5, pp. 1-21, Mar. 2015.
[14] M. Ghavipour and M. R. Meybodi, "Irregular cellular learning automata-based algorithm for sampling social networks," Engineering Applications of Artificial Intelligence, vol. 59, pp. 244-259, Mar. 2017.
[15] M. Rezapoor Mirsaleh and M. R. Meybodi, "A michigan memetic algorithm for solving the community detection problem in complex network," Neurocomputing, vol. 214, pp. 535-545, 19 Nov. 2016.
[16] B. Moradabadi and M. R. Meybodi, "Link prediction based on temporal similarity metrics using continuous action set learning automata," Physica A: Statistical Mechanics and its Applications, vol. 160, no. 2, pp. 361-373, Feb. 2016.
[17] M. Rezapoor Mirsaleh and M. R. Meybodi, "A new memetic algorithm based on cellular learning automata for solving the vertex coloring problem," Memetic Computing, vol. 8, no. 3, pp. 211-222, Sept. 2016.
[18] M. Rezapoor Mirsaleh and M. R. Meybodi, "A michigan memetic algorithm for solving the vertex coloring problem," J. of Computational Science, vol. 24, no. 2, pp. 389-401, Oct. 2017.
[19] S. M. Vahidipour, M. R. Meybodi, and M. Esnaashari, "Finding the shortest path in stochastic graphs using learning automata and adaptive stochastic petri nets," International J. of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 25, no. 3, pp. 427-455, Jan. 2017.
[20] S. M. Vahidipour, M. R. Meybodi, and M. Esnaashari, "Cellular adaptive petri net based on learning automata and its application to the vertex coloring problem," Discrete Event Dynamic Systems, vol. 27, no. 4, pp. 609-640, May. 2017.
[21] A. M. Saghiri and M. R. Meybodi, "A self-adaptive algorithm for topology matching in unstructured peer-to-peer networks," J. of Network and Systems Management, vol. 24, no. 2, pp. 393-426, Apr. 2016.
[22] A. M. Saghiri and M. R. Meybodi, "An approach for designing cognitive engines in cognitive peer-to-peer networks," J. of Network and Computer Applications, vol. 70, pp. 17-40, Jul. 2016.
[23] M. Ghavipour and M. R. Meybodi, "An adaptive fuzzy recommender system based on learning automata," Electronic Commerce Research and Applications, vol. 20, pp. 105-115, Nov./Dec. 2016.
[24] B. J. Oommen and D. C. Y. Ma, "Deterministic learning automata solutions to the equipartitioning problem," IEEE Trans. on Computers, vol. 37, no. 1, pp. 2-13, Jan. 1988.
[25] M. Rezapoor Mirsaleh and M. R. Meybodi, "Improving GA+LA algorithm for solving graph isomorphic problem," in Proc. of the 11th Annual CSI Computer Conf. of Iran, pp. 474-483, Tehran, Iran, Jan. 2006.
[26] K. Asghari, A. Safari Mamaghani, and M. R. Meybodi, "An evolutionary approach for query optimization problem in database," in Proc. of Int. Joint Conf. on Computers, Information and System Sciences, and Engineering, CISSE'07, University of Bridgeport, England, 9 pp., Dec. 2007.
[27] A. Safari Mamaghani, K. Asgari, M. R. Meybodi, and F. Mahmoodi, "A new method based on genetic algorithm for minimizing join operations cost in data base," in Proc. of 13th Annual CSI Computer Conf. of Iran,6 pp., Kish Island, Iran, Mar. 2008.
[28] A. Safari Mamaghani, K. Asghari, F. Mahmoudi, and M. R. Meybodi, "A novel hybrid algorithm for joint ordering problem in database queries," in Proc. of 6th WSEAS Int. Conf. on Computational Intelligence, Man-Machine Systems and Cybernetics, pp. 104-109, Tenerife, Spain, 14-16 Dec. 2007.
[29] K. Asghari, A. Safari Mamaghani, F. Mahmoudi, and M. R. Meybodi, "A relational databases query optimization using hybrid evolutionary algorithm," J. of Computer and Robotics, vol. 1, no. 1, pp. 28-39, Jan. 2008.
[30] B. Zaree and M. R. Meybodi, "A hybrid method for sorting problem," in Proc. of the 3rd Int. Conf. on Information and Knowledge Technology, IKT'07, 8 pp., Mashhad, Iran, 26-28 Nov. 2007.
[31] B. Zaree and M. R. Meybodi, "An evolutionary method for solving symmetric TSP," in Proc. of the 3rd Int. Conf. on Information and Knowledge Technology, IKT'07, 8 pp., Mashhad, Iran, 26-28 Nov. 2007.
[32] B. Zaree and M. R. Meybodi, "A hybrid method for solving traveling salesman problem," in Proc. of the 6th IEEE/ACIS Int. Conf. on Computer and Information Science, ICIS'07, pp. 394-399, Melbourne, Australia, 11-13 Jul. 2007.
[33] B. Zaree, K. Asghari, and M. R. Meybodi, "A hybrid method based on clustering for solving large traveling salesman problem," in Proc. of 13th Annual CSI Computer Conf. of Iran, 6 pp., Kish Island, Iran, 9-11 Mar. 2008.
[34] K. Asghari and M. R. Meybodi, "Searching for hamiltonian cycles in graphs using evolutionary methods," in Proc. of the 2nd Joint Congress on Fuzzy and Intelligent Systems, pp. 132-143, Tehran, Iran, 28-30 Oct. 2008.
[35] A. Safari Mamaghani and M. R. Meybodi, "Hybrid algorithms (learning automata + genetic algorithm) for solving graph bandwidth minimization problem," in Proc. of the 2nd Joint Congress on Fuzzy and Intelligent Systems, 1 pp., Tehran, Iran, 28-30 Oct. 2008.
[36] A. S. Mamaghani and M. R. Meybodi, "A learning automaton based approach to solve the graph bandwidth minimization problem," in Proc. 5th Int. Conf. on Application of Information and Communication Technologies, AICT'11, 5 pp., Baku, Azerbaijan 12-14 Oct. 2011.
[37] A. Isazadeh, H. Izadkhah, and A. Mokarram, "A learning based evolutionary approach for minimization of matrix bandwidth problem," Appl. Math, vol. 6, no. 1, pp. 51-57, Apr. 2012.
[38] A. Safari Mamaghani and M. R. Meybodi, "Hybrid evolutionary algorithms for solving software clustering problem," in Proc. of the 2nd Joint Congress on Fuzzy and Intelligent Systems, pp. 464-473, Tehran, Iran, Oct. 2008.
[39] K. Asghari and M. R. Meybodi, "Solving single machine total weighted tardiness scheduling problem using learning automata and genetic algorithm," in Proc. of the 3rd Iran Data Mining Conf., IDMC'09, Tehran, Iran, 16 pp., Dec. 2009.
[40] A. S. Mamaghani, M. Mahi, and M. R. Meybodi, "A learning automaton based approach for data fragments allocation in distributed database systems," in Proc. IEEE 10th Int. Conf. on Computer and Information Technology, CIT'10, pp. 8-12, Jun. 2010.
[41] A. S. Mamaghani, M. Mahi, M. R. Meybodi, and M. H. Moghaddam, "A novel evolutionary algorithm for solving static data allocation problem in distributed database systems," in Proc. 2nd Int. Conf. on Network Applications Protocols and Services, NETAPPS'10, pp. 14-19, Kedah, Malaysia, 22-23 Sept. 2010.
[42] V. Majid Nezhad, H. Motee Gader, and E. Efimov, "A novel hybrid algorithm for task graph scheduling," IJCSI International J. of Computer Science Issues, vol. 8, no. 1, pp. 32-38, Nov. 2011.
[43] A. Bansal and R. Kaur, "Task graph scheduling on multiprocessor system using genetic algorithm," International J. of Engineering Research & Technology, vol. 1, no. 5, pp. 1-5, Jan. 2012.
[44] P. Foggia, C. Sansone, and M. Vento, "A database of graphs for isomorphism and sub-graph isomorphism benchmarking," in Proc. of the 3rd IAPR TC-15 Int. Workshop on Graph-Based Representations, pp. 176-187, May 2001.
[45] 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.
[46] J. R. Ullmann, "An algorithm for subgraph isomorphism," J. ACM, vol. 23, no. 1, pp. 31-42, Jan. 1976.
[47] 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.