An optimization algorithm inspired by musical composition in constrained optimization problems

• Mora-Gutiérrez, Roman Anselmo ^[1] ; Rincón-García, Eric Alfredo ^[1] ; Ramírez Rodríguez, Javier ^[1] ; Ponsich, Antonin ^[1] ; Herrera-Alcántara, Oscar ^[1] ; Lara Velázquez, Pedro ^[1]
  1. [1] Universidad Autónoma Metropolitana

     Universidad Autónoma Metropolitana

     México

     
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 20, Nº. 2, 2013, págs. 183-202
• Idioma: inglés
• DOI: 10.15517/rmta.v20i2.11658
• Títulos paralelos:
  • Un algoritmo de optimización inspirado en composición musical para el problema de optimización con restricciones
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    Muchos de los problemas reales se pueden expresar como una instancia del problema de optimización no lineal con restricciones (CNOP). Este problema tiene un conjunto de restricciones, el cual especifica el espacio de soluciones factibles. En los últimos años se han propuesto y desarrollado varios algoritmos para resolver el CNOP. En este trabajo, se presenta un algoritmo cultural para optimización con restricciones, el cual es una adaptación del “ Método de Composición Musical” o MCM, propuesto en [33] por Mora et al., para resolver instancias del CNOP. La adaptación propuesta del MCM se aplicó a cinco instancias de prueba del CNOP a fin de evaluar y analizar su comportamiento. Los resultados experimentales del MCM se compararon con los resultados obtenidos por algoritmo evolutivo basado en homomorfismo [23] , Sistema Inmune Artificial [9] y el algoritmo de anti-cultural [39]. Los resultados experimentales muestran que el MCM genera resultados significativamente mejores que los obtenidos por las otras metaheurísticas probadas en algunos de los problemas de referencia.

  • English

    Many real-world problems can be expressed as an instance of the constrained nonlinear optimization problem (CNOP). This problem has a set of constraints specifies the feasible solution space. In the last years several algorithms have been proposed and developed for tackling CNOP. In this paper, we present a cultural algorithm for constrained optimization, which is an adaptation of “Musical Composition Method” or MCM, which was proposed in [33] by Mora et al. We evaluated and analyzed the performance of MCM on five test cases benchmark of the CNOP. Numerical results were compared to evolutionary algorithm based on homomorphous mapping [23], Artificial Immune System [9] and anti-culture population algorithm [39]. The experimental results demonstrate that MCM significantly improves the global performances of the other tested metaheuristics on same of benchmark functions.

• Referencias bibliográficas
  • Biles, J.A. (1994) “GenJam: A genetic algorithm for generating jazz solos”, International Computer Music Conference. Aarhus, Denmark: International....
  • Bekrar, A.; Chaabane, S.; Trentesaux, S.; Bornschlegell, A.; Pellé, J.; Harmand, S. (2011) “Hybrid PSO-tabu search for constrained non-linear...
  • Cai, Z.; Wang, Y.A. (2006) “Multiobjective optimization based evolutionary algorithm for constrained optimization”. IEEE Transactions on evolutionary...
  • Chung, C.J.; Reynolds, R.G. (1996) “A testbed for solving optimization problems using cultural algorithms”, Proceedings of the Fifth Annual...
  • Coello, C.A.C.; Becerra, R.L. (2002) “Constrained optimization using an evolutionary programming-based cultural algorithm”. Adaptive Computing...
  • Coello, C.A.C.; Becerra, R.L. (2003) “Evolutionary multiobjective optimization using a cultural algorithm”, Swarm Intelligence Symposium,...
  • Cope, D. (2000) The Algorithmic Composer. A-R Editions Inc. Wisconsin USA.
  • Cope, D. (2005) Computer Model of Musical Creativity. MIT Press, Cambridge MA.
  • Cruz Cortés, N. (2004) Sistema Inmune Artificial para Solucionar Problemas de Optimización. Doctoral Thesis, CINVESTAV-Instituto Politécnico...
  • de Bono, E. (1991) El Pensamiento Lateral: Manual de Creatividad. Espsa libros S.L.U.
  • Dorigo, M.; Maniezzo, V.; Colorni, A. (1996) “Ant system: optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man,...
  • Geem, Z.W. (2009) Recent Advances in Harmony Search Algorithm. Springer, New York.
  • Geem, Z.W. (2010) Music-Inspired Harmony Search Algorithm. Springer, New York.
  • Geem, Z.W., Kim J.-H., Loganathan G.V. (2001) “A new heuristic optimization algorithm: harmony search”, Simulation 76(2): 60–68.
  • Gessler, N. (2003) “Evolving cultural things-that-think”, Computational Synthesis: From Basic Building Blocks to High Level Functionality,...
  • Gould N., Orban D., Toint P.L. (2001) “ CUTTEr a Constrained and Unconstrained Testing Environment, revisited”, in: http://www.cuter.rl.ac.uk/problems.html,...
  • Horner, A.; Goldberg, D.E. (1991) “Genetic algorithms and computer assisted music composition”, Music Composition. ICMC9́1 Proceedings, International...
  • Hu, X.; Eberhart, R.(2002) “Solving constrained nonlinear optimization problems with particle swarm optimization”, in: 6th World Multiconference...
  • Jacob B.L. (1996) “Algorithmic composition as a model of creativity”, Organised Sound, Cambridge University Press: 157–165.
  • Jacob B.L. (1995) “Composing with genetic algorithms”, International Computer Music Association: 452–455.
  • Jin, X.; Reynolds, R.G. (1999) “Using knowledge based evolutionary computation to solve nonlinear constraint optimization problems: a cultural...
  • Kennedy, J., Eberhart, R.C. (1995) “Particle swarm optimization”, International Conference Neuronal Networks : 1942–1948.
  • Koziel, S.; Michalewicz, Z. (1999) “Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization”, Evolutionary...
  • Landa Becerra, R.; Coello Coello, C.A. (2005) “Optimization with constraints using a cultured differential evolution approach”, in: Proceedings...
  • Lee, K.S.; Geem, Z.W. (2004) “A new structural optimization method based on the harmony search algorithm”, Computers & Structures 82:...
  • Leyffer, S.; Mahajan, A.; Cochran, J.J.; Cox, L.A.; Keskinocak, P.; Kharoufeh, J.P.; Smith J.C. (2010) Software for Nonlinearly Constrained...
  • Liu Y.T. (2000) “Creativity or novelty?: Cognitive-computational versus social-cultural”, Design Studies : 261–276.
  • McDonnell, J.; Reynolds, R.; Fogel, D.(1995) “Using cultural algorithms for constraint handling in GENOCOP”, Evolutionary Programming IV:...
  • Michalewicz, Z. (1995) “Genetic algorithms, numerical optimization, and constraints”, Proceedings of the 6th International Conference on Genetic...
  • Michalewicz, Z.; Janikow, C.Z. (1996) “Genocop: a genetic algorithm for numerical optimization problems with linear constraints”. Communications...
  • Michalewicz, Z.; Fogel, D.B. (1998) How to Solve it: Modern Heuristics. Springer, New York.
  • Michalewicz, Z.; Deb, K.; Schmidtz, M.; Stidsenx, T. (2000) “Test-case generator for nonlinear continuous parameter optimization techniques”,...
  • Mora-Gutiérrez, R.; Ramı́rez-Rodríguez, J.; Rincón-García, E.(2012) “ An optimization algorithm inspired by musical composition”, Artificial...
  • Mora-Gutiérrez, R.; Ramı́rez- Rodríguez, J.; Rincón-García, E.; Ponsich, A.; Herrera O. (2012) “An optimization algorithm inspired by social...
  • Mora-Gutiérrez, R. (2013) Diseño y desarrollo de un método heurístico basado en un sitema socio-cultural de creatividad para la resolución...
  • Ray, T.; Kang, T.; Chye, S.K. (2000) “An evolutionary algorithm for constrained optimization”, GECCO-00 : 771–777.
  • Ray, T.; Liew, K.M. (2003) “Society and civilitation: an optimization algorithm based on the simulation of social behavior”. IEEE Transaction...
  • Reynolds, R.G. (1994) “An introduction to cultural algorithms”. Proceedings of the 3rd Annual Conference on Evolutionary Programming, World...
  • Tang, W.; Li, Y. (2008) “Constrained optimization using triple spaces cultured genetic algorithm”. International Conference on Natural Computation...