Un algoritmo basado en la colonia arti(cid:28)cial de abejas con bœsqueda local para resolver problemas de optimizaci(cid:243)n con restricciones TESIS DE MAESTR˝A AdÆn Enrique Aguilar Justo FACULTAD DE F˝SICA E INTELIGENCIA ARTIFICIAL DEPARTAMENTO DE INTELIGENCIA ARTIFICIAL "Maestr(cid:237)a en Inteligencia Arti(cid:28)cial" Fecha: 07 de agosto de 2014 i Documento maquetado con TEX S v.1.0+. Un algoritmo basado en la colonia arti(cid:28)cial de abejas con bœsqueda local para resolver problemas de optimizaci(cid:243)n con restricciones Tesis para obtener el grado de Maestro en Inteligencia Arti(cid:28)cial Maestr(cid:237)a en Inteligencia Arti(cid:28)cial Dirigida por el Doctor EfrØn Mezura Montes FACULTAD DE F˝SICA E INTELIGENCIA ARTIFICIAL DEPARTAMENTO DE INTELIGENCIA ARTIFICIAL "Maestr(cid:237)a en Inteligencia Arti(cid:28)cial" Fecha: 07 de agosto de 2014 Agradecimientos Puedes censurar a un amigo en con(cid:28)anza, pero debes alabarlo delante de los demÆs. Leonardo Da Vinci Agradezco a el CONACYT por el apoyo econ(cid:243)mico brindado durante la realizaci(cid:243)n de este proyecto. Agradezco a la Universidad Veracruzana, esta instituci(cid:243)n de enorme calidad, que me brind(cid:243) todo el apoyo durante mi estancia. Agradezco a mi asesor el Dr. EfrØn Mezura Montes, todo su apoyo, conocimientos y compromiso con el proyecto que fueron parte funda- mental para que Øste trabajo llegara a su termino en tiempo y forma. Agradezco al Dr. Carlos Artemio Coello Coello, el haber compartido su conocimiento y sus aportes al trabajo. Agradezco a todos mis compaæeros de la Maestr(cid:237)a y del Doctorado en Inteligencia Arti(cid:28)cial quienes me aportaron comentarios y criticas valiosas que me ayudaron a mejorar mi trabajo. En especial agradezco a mis padres, que siguen siendo un soporte fun- damental en mi vida, quienes me han dado las mejores enseæanzas de la vida. v Resumen El rendirse a la ignorancia y llamarla dios siempre ha sido prematuro y sigue siØndolo hoy d(cid:237)a. Issac Asimov El algoritmo de colonia arti(cid:28)cial de abejas (ABC por sus siglas en ingles Arti(cid:28)cial Bee Colony) originalmente fue planteado como un algoritmo para resolver problemas de optimizaci(cid:243)n sin restricciones, con el paso del tiem- po se le han incorporado mejoras y modi(cid:28)caciones para resolver problemas restringidos. En la presente tesis se describe una propuesta de algoritmo memØtico basado ABC para problemas de optimizaci(cid:243)n con restricciones. El algorit- mo propuesto es probado con dos mØtodos de bœsqueda local, Hooke-Jeeves y Complex, estos son incorporados dentro del ciclo de evolutivo de ABC, particularmente despuØs de la fase de abejas observadoras. Se ha utilizado una mØtrica basada en la aptitud de la poblaci(cid:243)n actual para determinar el momento de aplicar la bœsqueda local. El algoritmo propuesto fue probado en los conjuntos de funciones de prueba del congreso de Computaci(cid:243)n Evolutiva (CEC) de la IEEE en sus versiones del CEC2006 y CEC2010. Los resultados fueron comparados con losobtenidospordosalgoritmosdelestadodelarte.Losresultadosmuestran que la propuesta es competitiva resolviendo este tipo de problemas respecto a los del estado del arte. vii ˝ndice Agradecimientos v Resumen vii 1. Introducci(cid:243)n 1 1.1. Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. De(cid:28)nici(cid:243)n del problema . . . . . . . . . . . . . . . . . . . . . 2 1.3. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.1. Objetivo general . . . . . . . . . . . . . . . . . . . . . 3 1.3.2. Objetivos espec(cid:237)(cid:28)cos . . . . . . . . . . . . . . . . . . . 3 1.4. Contribuci(cid:243)n . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5. Hip(cid:243)tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.6. Justi(cid:28)caci(cid:243)n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.7. Organizaci(cid:243)n del documento de tesis . . . . . . . . . . . . . . 4 2. Inteligencia colectiva y C(cid:243)mputo memØtico 5 2.1. Inteligencia Colectiva (Swarm Intelligence) . . . . . . . . . . . 5 2.2. C(cid:243)mputo memØtico . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3. Algoritmos memØticos . . . . . . . . . . . . . . . . . . . . . . 8 2.4. Diseæo de un algoritmo memØtico . . . . . . . . . . . . . . . . 8 2.4.1. Algoritmo Lamarckniano . . . . . . . . . . . . . . . . . 9 2.4.2. Algoritmo Baldwiniano . . . . . . . . . . . . . . . . . 9 3. Algoritmo de Colonia Arti(cid:28)cial de Abejas 11 3.1. Modelo Biol(cid:243)gico . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2. Algoritmo bÆsico . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3. ABC para problemas con restricciones . . . . . . . . . . . . . 14 3.3.1. Propuesta de Karaboga y Akay (2011) . . . . . . . . . 14 4. Algoritmo Propuesto CMABC 17 4.1. Buscadores locales . . . . . . . . . . . . . . . . . . . . . . . . 17 4.1.1. Hooke-Jeeves . . . . . . . . . . . . . . . . . . . . . . . 18 ix x ˝ndice 4.1.2. Complex . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2. Abeja empleada basada en Evoluci(cid:243)n Diferencial . . . . . . . 21 4.3. ε-constrained . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.4. Convergencia basada en aptitud . . . . . . . . . . . . . . . . . 22 4.5. Algoritmo Completo . . . . . . . . . . . . . . . . . . . . . . . 23 5. Resultados y discusi(cid:243)n 25 5.1. Diseæo del experimento. . . . . . . . . . . . . . . . . . . . . . 25 5.1.1. ParÆmetros de los algoritmos . . . . . . . . . . . . . . 26 5.2. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.3. Discusi(cid:243)n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.3.1. Resultados CEC2006 . . . . . . . . . . . . . . . . . . . 28 5.3.2. Resultados CEC2010 . . . . . . . . . . . . . . . . . . . 29 6. Conclusiones y trabajo futuro 45 6.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.2. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . 46 I ApØndices 47 A. ApØndice 49 A.1. Pruebas de Wilcoxon . . . . . . . . . . . . . . . . . . . . . . . 49 B. ApØndice 53 B.1. GrÆ(cid:28)cas de convergencia CEC2006 . . . . . . . . . . . . . . . 53 B.2. GrÆ(cid:28)cas de convergencia CEC2010 dimensi(cid:243)n 10 . . . . . . . 66 B.3. GrÆ(cid:28)cas de convergencia CEC2010 dimensi(cid:243)n 30 . . . . . . . 76 C. ApØndice 85 C.1. Detalle de las funciones del CEC2006 . . . . . . . . . . . . . . 85 C.2. Detalle de las funciones del CEC2010 . . . . . . . . . . . . . . 97 Referencias 105