Algoritmo memético
Los algoritmos meméticos son técnicas de optimización que combinan sinérgicamente conceptos tomados de otras metaheurísticas, tales como la búsqueda basada en poblaciones (como en los algoritmos evolutivos), y la mejora local (como en las técnicas de seguimiento del gradiente).[1]
Orígenes
[editar]Los orígenes de los algoritmos meméticos (MA) se remontan a finales de los años ochenta a pesar de que algunos trabajos en décadas anteriores también tienen características similares. En aquella época, el campo de la computación evolutiva estaba comenzando afianzarse sólidamente, una vez que el choque conceptual que había causado la introducción de estas técnicas al mundo de la optimización se iba atenuando.[2]
Cabe resaltar que el origen de los algoritmos meméticos se encuentra bastante ligado a los más conocidos algoritmos genéticos (GA), puesto que los MA toman como base la anatomía de los GA e incorporan en muchos de los casos procedimientos heurísticos de búsqueda local que incrementan el desempeño del algoritmo general.
Por otra parte, la denominación de "memético" surge del término inglés "meme", acuñado por R. Dawkins como el análogo del gen en el contexto de la evolución cultural, ejemplos de ellos son melodías, modas, ideas, dichos, metodologías, etc.[3]
Algoritmo general
[editar]Los MA son metaheurísticas basadas en población, esto quiere decir que mantienen un conjunto de soluciones candidatas para el problema considerado. De acuerdo a la jerga utilizada en los algortimos evolutivos, a cada una de estas soluciones tentativas se les conoce como individuos. Ahora bien en el caso de los MA, el término individuo denota un ente más pasivo, por lo que en la literatura se le ha denominado de mejor forma como agente. Un agente implica un comportamiento más activo, ya que una de las premisas de los MA es buscar mejoras individuales de las soluciones en cada uno de los agentes junto con procesos de cooperación.[4]
A continuación se puede apreciar una plantilla general de un MA[4]:
Entrada: una instancia I de un problema P.
Salida: una solución sol.
// generar población inicial
1 : para j ← 1:popsize hacer
2 : sea ind ← GenerarSolucionHeuristica (I)
3 : sea pop[j] ← MejoraLocal (ind, I)
4 : finpara
5 : repetir // bucle generacional
// Selección
6 : sea criadores ← SeleccionarDePoblacion (pop)
// Reproducción segmentada
7 : sea auxpop[0] ← pop
8 : para j ← 1:#op hacer
9 : sea auxpop[j] ← AplicarOperador (op[j], auxpop[j ¡ 1], I)
10 : finnpara
11 : sea newpop ← auxpop[#op]
// Reemplazo
12 : sea pop ← ActualizarProblacion (pop, newpop)
// Comprobar convergencia
13 : si Convergencia (pop) entonces
14 : sea pop ← RefrescarPoblacion (pop, I)
15 : finsi
16 : hasta CriterioTerminacion (pop, I)
17 : devolver Mejor (pop, I)
Aplicaciones
[editar]Actualmente existen cientos de aplicaciones de los MA en el ámbito de la optimización combinatoria. Esto no es sorprendente si consideramos que existen miles de problemas de optimización pertenecientes a la clase NP, donde los MA han mostrado gran valor.[1]
Para ver la amplia cobertura que han tenido los MA resolviendo esta clase de problemas, se muestra a continuación una lista con las aplicaciones de mayor importancia:
- Problema del viajante de comercio[5]
- Problemas de particionado de grafos[6]
- Partición de números[7]
- Conjunto Independiente de cardinalidad máxima[8]
- Coloreado de grafos[9]
- Recubrimiento de conjuntos[10]
- Planificación de tareas en una máquina con tiempos de "set-up" y fechas de entrega[11]
- Planificación de tareas en varias máquinas[12]
- Problemas de asignación generalizados[13]
- Problemas de mochila multidimensional[14]
- Programación entera no-lineal[15]
- Asignación cuadrática[16]
Referencias
[editar]- ↑ a b Moscato, Pablo; Cotta, Carlos (2003). Handbook of Metaheuristics. International Series in Operations Research & Management Science (en inglés). Springer, Boston, MA. pp. 105-144. ISBN 9781402072635. doi:10.1007/0-306-48056-5_5. Consultado el 19 de abril de 2018.
- ↑ Moscato, Pablo; Cotta, Carlos (2010). Handbook of Metaheuristics. International Series in Operations Research & Management Science (en inglés). Springer, Boston, MA. pp. 141-183. ISBN 9781441916631. doi:10.1007/978-1-4419-1665-5_6. Consultado el 19 de abril de 2018.
- ↑ Dawkins, R. (1976). The selfish gene Oxford university press. New York, New York, USA.
- ↑ a b Cotta, C. (2007). Una visión general de los algoritmos meméticos. Rect, 3, 139-166.
- ↑ Holstein, D., & Moscato, P. (1999, January). Memetic algorithms using guided local search: A case study. In New ideas in optimization (pp. 235-244). McGraw-Hill Ltd., UK.
- ↑ Merz, Peter; Freisleben, Bernd (13 de marzo de 2006). «Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning». Evolutionary Computation (en inglés) 8 (1): 61-91. doi:10.1162/106365600568103. Consultado el 19 de abril de 2018.
- ↑ Berretta, R., & Moscato, P. (1999, January). The number partitioning problem: An open challenge for evolutionary computation?. In New ideas in optimization (pp. 261-278). McGraw-Hill Ltd., UK.
- ↑ Hifi, M. (1 de junio de 1997). «A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems». Journal of the Operational Research Society (en inglés) 48 (6): 612-622. ISSN 0160-5682. doi:10.1057/palgrave.jors.2600405. Consultado el 19 de abril de 2018.
- ↑ Costa, Daniel; Hertz, Alain; Dubuis, Clivier (1 de septiembre de 1995). «Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs». Journal of Heuristics (en inglés) 1 (1): 105-128. ISSN 1381-1231. doi:10.1007/BF02430368. Consultado el 19 de abril de 2018.
- ↑ Beasley, J.E; Chu, P.C. «A genetic algorithm for the set covering problem». European Journal of Operational Research 94 (2): 392-404. doi:10.1016/0377-2217(95)00159-x. Consultado el 19 de abril de 2018.
- ↑ França, P. M., Mendes, A. S., & Moscato, P. (1999, July). Memetic algorithms to minimize tardiness on a single machine with sequence-dependent setup times. In Proceedings of the 5th International Conference of the Decision Sciences Institute, Athens, Greece (pp. 1708-1710).
- ↑ Cheng, R.; Gen, M. «Parallel machine scheduling problems using memetic algorithms». 1996 IEEE International Conference on Systems, Man and Cybernetics. Information Intelligence and Systems (Cat. No.96CH35929) (en inglés estadounidense). doi:10.1109/icsmc.1996.561355. Consultado el 19 de abril de 2018.
- ↑ Chu, P.C.; Beasley, J.E. «A genetic algorithm for the generalised assignment problem». Computers & Operations Research 24 (1): 17-23. doi:10.1016/s0305-0548(96)00032-9. Consultado el 19 de abril de 2018.
- ↑ Chu, P. C.; Beasley, J. E. (1 de junio de 1998). «A Genetic Algorithm for the Multidimensional Knapsack Problem». Journal of Heuristics (en inglés) 4 (1): 63-86. ISSN 1381-1231. doi:10.1023/A:1009642405419. Consultado el 19 de abril de 2018.
- ↑ Taguchi, Takeaki; Yokota, Takao; Gen, Mitsuo. «Reliability optimal design problem with interval coefficients using Hybrid Genetic Algorithms». Computers & Industrial Engineering 35 (1-2): 373-376. doi:10.1016/s0360-8352(98)00097-7. Consultado el 19 de abril de 2018.
- ↑ Carrizo, J., Tinetti, F. G., & Moscato, P. (1992, August). A computational ecology for the quadratic assignment problem. In Proceedings of the 21st Meeting on Informatics and Operations Research.
Bibliografía
[editar]- Carmona, Enrique J.; Fernández, Severino (2020). Fundamentos de la Computación Evolutiva. Marcombo. ISBN 978-8426727558.
Datos: Q324793