Combining Mutation and Recombination to Improve a Distributed Model of Adaptive Operator Selection

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9554
• 期：1
• 页码：97-108
• 全文大小：523 KB
• 参考文献：1.Araujo, L., Guervós, J.J.M., Mora, A., Cotta, C.: Genotypic differences and migration policies in an island model. In: GECCO, pp. 1331–1338 (2009)
  2.Burke, E.K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Qu, R.: Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. (JORS) 64(12), 1695–1724 (2013)CrossRef
  3.Candan, C., Goëffon, A., Lardeux, F., Saubion, F.: A dynamic island model for adaptive operator selection. In: Genetic and Evolutionary Computation Conference (GECCO 2012), pp. 1253–1260 (2012)
  4.DaCosta, L., Fialho, A., Schoenauer, M., Sebag, M.: Adaptive operator selection with dynamic multi-armed bandits. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 913–920. ACM (2008)
  5.Fialho, Á., Da Costa, L., Schoenauer, M., Sebag, M.: Extreme value based adaptive operator selection. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 175–184. Springer, Heidelberg (2008)CrossRef
  6.Gustafson, S., Burke, E.K.: The speciating island model: an alternative parallel evolutionary algorithm. J. Parallel Distrib. Comput. 66(8), 1025–1036 (2006)CrossRef MATH
  7.Lardeux, F., Goëffon, A.: A dynamic island-based genetic algorithms framework. In: Deb, K., Bhattacharya, A., Chakraborti, N., Chakroborty, P., Das, S., Dutta, J., Gupta, S.K., Jain, A., Aggarwal, V., Branke, J., Louis, S.J., Tan, K.C. (eds.) SEAL 2010. LNCS, vol. 6457, pp. 156–165. Springer, Heidelberg (2010)CrossRef
  8.Lässig, J., Sudholt, D.: Design and analysis of migration in parallel evolutionary algorithms. Soft Comput. 17(7), 1121–1144 (2013)CrossRef MATH
  9.Luque, G., Alba, E.: Selection pressure and takeover time of distributed evolutionary algorithms. In: Pelikan, M., Branke, J. (eds.) Genetic and Evolutionary Computation Conference, GECCO 2010, pp. 1083–1088. ACM (2010)
  10.Maturana, J., Saubion, F.: On the design of adaptive control strategies for evolutionary algorithms. In: Monmarché, N., Talbi, E.-G., Collet, P., Schoenauer, M., Lutton, E. (eds.) EA 2007. LNCS, vol. 4926, pp. 303–315. Springer, Heidelberg (2008)CrossRef
  11.McCollum, B., Schaerf, A., Paechter, B., McMullan, P., Lewis, R., Parkes, A.J., Gaspero, L.D., Qu, R., Burke, E.K.: Setting the research agenda in automated timetabling: the second international timetabling competition. INFORMS J. Comput. 22(1), 120–130 (2010)CrossRef MATH
  12.Ochoa, G., Hyde, M., Curtois, T., Vazquez-Rodriguez, J.A., Walker, J., Gendreau, M., Kendall, G., McCollum, B., Parkes, A.J., Petrovic, S., Burke, E.K.: HyFlex: a benchmark framework for cross-domain heuristic search. In: Hao, J.-K., Middendorf, M. (eds.) EvoCOP 2012. LNCS, vol. 7245, pp. 136–147. Springer, Heidelberg (2012)CrossRef
  13.Ochoa, G., Harvey, I., Buxton, H.: On recombination and optimal mutation rates. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO), pp. 488–495. Morgan Kaufmann (1999)
  14.Rucinski, M., Izzo, D., Biscani, F.: On the impact of the migration topology on the island model. CoRR abs/1004.4541 (2010)
  15.Skolicki, Z., Jong, K.D.: The influence of migration sizes and intervals on island models. In: GECCO, pp. 1295–1302 (2005)
  16.Soria-Alcaraz, J., Martin, C., Héctor, P., Hugo, T.M., Laura, C.R.: Methodology of design: a novel generic approach applied to the course timetabling problem. In: Melin, P., Castillo, O. (eds.) Soft Computing Applications in Optimization, Control, and Recognition. Studies in Fuzziness and Soft Computing, vol. 294, pp. 287–319. Springer, Heidelberg (2013)CrossRef
  17.Soria-Alcaraz, J.A., Ochoa, G., Swan, J., Carpio, M., Puga, H., Burke, E.K.: Effective learning hyper-heuristics for the course timetabling problem. Eur. J. Oper. Res. 238(1), 77–86 (2014)MathSciNet CrossRef
  18.Whitley, D., Rana, S., Heckendorn, R.: The island model genetic algorithm: on separability, population size and convergence. J. Comput. Inf. Technol. 7, 33–47 (1998)
  
• 作者单位：Jorge A. Soria-Alcaraz (18)
  Gabriela Ochoa (19)
  Adrien Göeffon (20)
  Frédéric Lardeux (20)
  Frédéric Saubion (20)
  
  18. Depto de Estudios Organizacionales, Universidad de Guanajuato-División de Ciencias Económico-Administrativas, Guanajuato, Mexico
  19. University of Stirling, Stirling, UK
  20. University of Angers, Angers, France
  
• 丛书名：Artificial Evolution
• ISBN：978-3-319-31471-6
• 刊物类别：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

文摘

We present evidence indicating that adding a crossover island greatly improves the performance of a Dynamic Island Model for Adaptive Operator Selection. Two combinatorial optimisation problems are considered: the Onemax benchmark, to prove the concept; and a real-world formulation of the course timetabling problem to test practical relevance. Crossover is added to the recently proposed dynamic island adaptive model for operator selection which considered mutation only. When comparing the models with and without a recombination, we found that having a crossover island significantly improves the performance. Our experiments also provide compelling evidence of the dynamic role of crossover during search: it is a useful operator across the whole search process. The idea of combining different type of operators in a distributed adaptive search model is worth further investigation.