Addressing High Dimensional Multi-objective Optimization Problems by Coevolutionary Islands with Overlapping Search Spaces

详细信息    查看全文

• 关键词：Multi ; objective algorithms ; NSGA ; II ; Island model ; Distributed evolutionary algorithms
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9598
• 期：1
• 页码：107-117
• 全文大小：1,281 KB
• 参考文献：1.Alba, E., Luque, G., Nesmachnow, S.: Parallel metaheuristics: recent advances and new trends. Int. Trans. Oper. Res. 20(1), 1–48 (2013)CrossRef MATH
  2.Luna, F., Alba, E.: Parallel multiobjective evolutionary algorithms. In: Kacprzyk, J., Pedrycz, W. (eds.) Springer Handbook of Computational Intelligence, pp. 1017–1031. Springer, Berlin (2015)CrossRef
  3.Branke, J., Schmeck, H., Deb, K., Maheshwar, R.S.: Parallelizing multi-objective evolutionary algorithms: cone separation. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2004, pp. 1952–1957, Portland, OR, USA. IEEE, 19–23 June 2004
  4.Folino, G., Pizzuti, C., Spezzano, G.: A scalable cellular implementation of parallel genetic programming. IEEE Trans. Evol. Comput. 7(1), 37–53 (2003)CrossRef MATH
  5.Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Trans. Evol. Comput. 6(5), 443–462 (2002)CrossRef
  6.Mukhopadhyay, A., Maulik, U., Bandyopadhyay, S., Coello, C.A.C.: A survey of multiobjective evolutionary algorithms for data mining: part I. IEEE Trans. Evol. Comput. 18(1), 4–19 (2014)CrossRef
  7.Gong, Y., Chen, W., Zhan, Z., Zhang, J., Li, Y., Zhang, Q., Li, J.: Distributed evolutionary algorithms and their models: a survey of the state-of-the-art. Appl. Soft Comput. 34, 286–300 (2015)CrossRef
  8.Kimovski, D., Ortega, J., Ortiz, A., Baños, R.: Parallel alternatives for evolutionary multi-objective optimization in unsupervised feature selection. Expert Syst. Appl. 42(9), 4239–4252 (2015)CrossRef
  9.Dorronsoro, B., Danoy, G., Nebro, A.J., Bouvry, P.: Achieving super-linear performance in parallel multi-objective evolutionary algorithms by means of cooperative coevolution. Comput. OR 40(6), 1552–1563 (2013)MathSciNet CrossRef
  10.Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast elitist non-dominated sorting genetic algorithm for multi-objective optimisation: NSGA-II. In: Deb, K., Rudolph, G., Lutton, E., Merelo, J.J., Schoenauer, M., Schwefel, H.-P., Yao, X. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 849–858. Springer, Heidelberg (2000)CrossRef
  11.Talbi, E.-G., Mostaghim, S., Okabe, T., Ishibuchi, H., Rudolph, G., Coello Coello, C.A.: Parallel approaches for multiobjective optimization. In: Branke, J., Deb, K., Miettinen, K., Słowiński, R. (eds.) Multiobjective Optimization. LNCS, vol. 5252, pp. 349–372. Springer, Heidelberg (2008)CrossRef
  12.Nebro, A.J., Durillo, J.J.: A study of the parallelization of the multi-objective metaheuristic MOEA/D. In: Blum, C., Battiti, R. (eds.) LION 4. LNCS, vol. 6073, pp. 303–317. Springer, Heidelberg (2010)CrossRef
  13.Hiroyasu, T., Yoshii, K., Miki, M.: Discussion of parallel model of multi-objective genetic algorithms on heterogeneous computational resources. In: Lipson, H. (ed.) Genetic and Evolutionary Computation Conference, GECCO 2007, Proceedings, p. 904, London, England, UK. ACM, 7–11 July 2007
  14.Deb, K., Zope, P., Jain, S.: Distributed computing of pareto-optimal solutions with evolutionary algorithms. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 534–549. Springer, Heidelberg (2003)CrossRef
  15.Xiao, N., Armstrong, M.P.: A specialized island model and its application in multi-objective. In: Cantú-Paz, E., Foster, J.A., Deb, K., Davis, L., Roy, R., O’Reilly, U.-M., Beyer, H.-G., Kendall, G., Wilson, S.W., Harman, M., Wegener, J., Dasgupta, D., Potter, M.A., Schultz, A., Dowsland, K.A., Jonoska, N., Miller, J., Standish, R.K. (eds.) GECCO 2003. LNCS, vol. 2724, pp. 1530–1540. Springer, Heidelberg (2003)CrossRef
  16.Zhi-xin, W., Ju, G.: A parallel genetic algorithm in multi-objective optimization. In: Control and Decision Conference, CCDC 2009, pp. 3497–3501, Chinese (2009)
  17.Märtens, M., Izzo, D.: The asynchronous island model and NSGA-II: study of a new migration operator and its performance. In: Blum, C., Alba, E. (eds.) Genetic and Evolutionary Computation Conference, GECCO 2013, pp. 1173–1180, Amsterdam, The Netherlands. ACM, 6–10 July 2013
  18.Cheng, R., Jin, Y., Narukawa, K.: Adaptive reference vector generation for inverse model based evolutionary multiobjective optimization with degenerate and disconnected pareto fronts. In: Gaspar-Cunha, A., Henggeler Antunes, C., Coello, C.C. (eds.) EMO 2015. LNCS, vol. 9018, pp. 127–140. Springer, Heidelberg (2015)
  19.Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: empirical results. Evol. Comput. 8(2), 173–195 (2000)CrossRef
  20.Luke, S., et al.: ECJ: a Java-based Evolutionary Computation and Genetic Programming Research System (2009). http://​www.​cs.​umd.​edu/​projects/​plus/​ec/​ecj
  
• 作者单位：Pablo García-Sánchez (15)
  Julio Ortega (15)
  Jesús González (15)
  Pedro A. Castillo (15)
  Juan J. Merelo (15)
  
  15. Department of Computer Architecture and Technology, University of Granada, Granada, Spain
  
• 丛书名：Applications of Evolutionary Computation
• ISBN：978-3-319-31153-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Large-scale multi-objective optimization problems with many decision variables have recently attracted the attention of researchers as many data mining applications involving high dimensional patterns can be leveraged using them. Current parallel and distributed computer architectures can provide the required computing capabilities to cope with these problems once efficient procedures are available. In this paper we propose a cooperative coevolutionary island-model procedure based on the parallel execution of sub-populations, whose individuals explore different domains of the decision variables space. More specifically, the individuals belonging to the same sub-population (island) explore the same subset of decision variables. Two alternatives to distribute the decision variables among the different sub-populations have been considered and compared here. In the first approach, individuals in different sub-population explore disjoint subsets of decision variables (i.e. the chromosomes are divided into disjoints subsets). Otherwise, in the second alternative there are some overlapping among the variables explored by individuals in different sub-populations. The analysis of the obtained experimental results, by using different metrics, shows that coevolutionary approaches provide statistically significant improvements with respect to the base algorithm, being the relation of the number of islands (subpopulations) to the length of the chromosome (number of decision variables) a relevant factor to determine the most efficient alternative to distribute the decision variables.