Memorias de la Escuela de Cómputo Evolutivo

Document downloaded from: Repositorio Documental de la Universidad de Valladolid (https://uvadoc.uva.es/) This chapter must be cited as: J.M. Cruz Duarte, I. Martin-Diaz, I. Cruz Aceves, Cuckoo Search y su implementacion práctica, en Memorias de la Escuela de Cómputo Evolutivo 2017, ISBN: 978-84-947311-9-8 This publication is available at: https://www.cimat.mx/producto/memorias-de-la-escuela-de-computo-evolutivo-2017/ ISBN: 978-84-947311-9-8 Pr´ ologo La escuela de c´ omputo evolutivo del CIMAT surge con el af´ an de fomentar el inter´ es existente en M´ exico por el campo del c´ omputo evolutivo, y de manera m´ as general, por el campo de optimizaci´ on con m´ etodos estoc´ asticos. En el a˜ no 2016 se dio inicio a la Primera Escuela de C´ omputo Evolutivo que se ha celebrado en CIMAT. Por ser su primera edici´ on, se decidi´ o realizar un evento peque˜ no, de dos d´ ıas, que tuvo una muy buena aceptaci´ on cubri´ endose todas las plazas reservadas. A ra´ ız de esto, se decidi´ o dar continuidad a este evento y que este creciera, por lo que en esta segunda edici´ on se increment´ o la duraci´ on de la escuela, se incluy´ o una sesi´ on de p´ osteres para que hubiera m´ as interacci´ on entre los participantes, y se tom´ o la decisi´ on de publicar un libro en el que de manera did´ actica se expusieran los principales temas tratados en la escuela, as´ ı como la informaci´ on de los p´ osteres presentados. El objetivo de este libro, no es tanto profundizar en los diferentes temas, sino introducir diferentes t´ opicos, as´ ı como presentar de forma resumida algunos de los trabajos que est´ an desarrollando muchos tesistas que est´ an trabajando en este campo a lo largo de todo M´ exico. Con esto esperamos atraer a m´ as estudiantes y fomentar las colaboraciones, pues siempre es bueno que se difundan los diferentes trabajos que se est´ an realizando y los temas en los que se est´ a investigando. El libro est´ a organizado en dos partes. La primera parte est´ a constituida por un conjunto de cap´ ıtulos escritos por los ponentes de la escuela. Se trata de cap´ ıtulos introductorios, orientados a quienes se inician en este apasionante campo. La segunda parte est´ a constituida por cap´ ıtulos cuyos autores principales son los estudiantes que presentaron sus p´ osteres en la Escuela, durante la cual recibieron retroalimentaci´ on para poder mejorar y hacer m´ as accesibles sus trabajos. Se realiz´ o un esfuerzo por revisar todos estos cap´ ıtulos y se seleccionaron s´ olo aquellos cuyos revisores dieron la recomendaci´ on oportuna para su publicaci´ on. Dada la gran aceptaci´ on de la Escuela, y el nivel de los ponentes que se ha conseguido atraer a la misma, esperamos seguir organizando est´ a escuela (la edici´ on 2018 ya est´ a en camino), y seguir fomentando que se realice investigaci´ on y trabajos de calidad. Dr. Carlos Segura Coordinador del Comit´ e Organizador de la Escuela de C´ omputo Evolutivo 2017 1 ´ Indice general Parte 1 – Cap´ ıtulos de los Expositores Historia y Filosof´ ıa del C´ omputo Evolutivo Carlos Segura, Gara Miranda y Carlos A. Coello Coello 1:1–1:21 Resultados Recientes y Problemas Abiertos en Optimizaci´ on Evolutiva Multi-Objetivo Carlos A. Coello Coello 2:1–2:16 Una Breve Introducci´ on a Optimizaci´ on por Enjambre de Part´ ıculas ´ Angel Arturo Rojas Garc´ ıa, Arturo Hern´ andez Aguirre y S. Ivvan Valdez 3:1–3:15 Programaci´ on Gen´ etica con B´ usqueda Local Leonardo Trujillo, Perla Ju´ arez Smith, Cesar Bernal, Antonin Ponsich y Juan J. Tapia 4:1–4:14 Estimaci´ on de par´ ametros para un modelo semi-emp´ ırico de una celda de combustible usando un Algoritmo de Estimaci´ on de Distribuci´ on Luis Blanco Cocom, Salvador Botello Rionda y S. Ivvan Valdez 5:1–5:11 Brev´ ısima Gu´ ıa de Optimizaci´ on Num´ erica Ricardo Landa y Jos´ e Virgilio Trevi˜ no 6:1–6:11 Algoritmos Evolutivos y Creatividad Katya Rodr´ ıguez V´ azquez 7:1–7:8 Parte 2 – P´ osteres de la Escuela de C´ omputo Evolutivo Una propuesta de topolog´ ıa din´ amica para el algoritmo de enjambre de part´ ıculas (PSO) Nancy Arlette Mej´ ıa Ju´ arez y Arturo Hern´ andez-Aguirre 8:1–8:22 Mecanismo de Gesti´ on de Diversidad Aplicado al Problema de Ordenaci´ on Lineal Nayeli Angel P´ erez, Darnes Vilari˜ no Ayala y Carlos Segura 9:1–9:11 Algoritmo Multi-Objetivo Basado en Descomposici´ on con Control de Diversidad en el Espacio de las Variables Joel Chac´ on Castillo, Carlos Segura, Arturo Hern´ andez Aguirre, Gara Miranda y Coromoto Le´ on 10:1–10:11 Algoritmo Mem´ etico con Cruce basado en el Algoritmo H´ ungaro y Control de Diversidad Emmanuel Romero Ruiz y Carlos Segura 11:1–11:15 Cuckoo Search y su implementaci´ on pr´ actica Jorge Mario Cruz Duarte, Ignacio Mart´ ın D´ ıaz e Ivan Cruz Aceves 12:1–12:8 Optimizaci´ on del Control de un Robot B´ ıpedo con Pies utilizando Metaheur´ ısticas J. Emmanuel Estrada, Carlos Segura, H´ ector M. Becerra y S. Ivvan Valdez 13:1–13:13 Un algoritmo Mem´ etico para el problema del ruteo de veh´ ıculos con capacidad y ventanas de tiempo Oscar M. Gonz´ alez, Carlos Segura, S. Ivvan Valdez y Coromoto Le´ on 14:1–14:14 Una aproximaci´ on al mejoramiento de im´ agenes en exteriores mediante redes neuronales Sebasti´ an Salazar Colores, Ivan Cruz Aveces, Cesar Ort´ ız Echeverri y Juan Manuel Ramos Arreguin 15:1–15:7 Parametrizaci´ on de neat-GP con F-Race Iterada Ernesto Norberto Alvarez Gonzalez, Juan J. Tapia y Leonardo Trujillo 16:1–16:9 Evoluci´ on Diferencial en la Segmentaci´ on Autom´ atica de Arterias Coronarias en Angiogramas de Rayos-X Fernando Cervantes S´ anchez, Ivan Cruz Aceves y Arturo Hern´ andez Aguirre 17:1–17:8 .9 12 Cuckoo Search y su implementación práctica JORGE MARIO CRUZ–DUARTE, DICIS, Universidad de Guanajuato (UG), México IGNACIO MARTÍN–DÍAZ, DICIS, Universidad de Guanajuato (UG), México IVÁN CRUZ–ACEVES, CONACYT, Centro de Investigación en Matemáticas (CIMAT), A.C., México Resumen En la actualidad existe una amplia cantidad de algoritmos inspirados en la naturaleza para resolver todo tipo de problemas, algunos de ellos se enfocan en los bien conocidos problemas de optimización. Entre éstos se pueden destacar los métodos de enjambre de partículas, algoritmos genéticos, recocido simulado y evolución diferencial. La lista es extensa y serían necesarias más páginas para llegar a mencionarlos todos. Sin embargo, en este artículo se revisa la, relativamente reciente, técnica metaheurística conocida como Cuckoo Search (CS). Para ello se hace una breve introducción al método, luego se detalla su procedimiento y, posteriormente, se describe su implementación incorporando algunas pruebas preliminares. 1. INTRODUCCIÓN Cuckoo Search (CS) fue propuesto por Xin–She Yang y Suash Deb en el año 2009 [ 9 ], quienes además son conocidos por otros métodos como Firefly Algorithm [ 10 ], Bat Algorithm [ 11 ], y Flower Pollination Algorithm [ 13 ]. CS es un algoritmo metaheurístico inspirado en el comportamiento de más de 100 especies de cucúlidos (familia: Cuculidae y subfamilia: Cuculinae). Los cucos se pueden encontrar casi en cualquier lugar del mundo con diferentes nombres locales, por ejemplo, en México se les llaman correcaminos, cuclillos, garrapateros, entre otros [ 2 ]. Particularmente, estas aves se caracterizan por emplear como estrategia de supervivencia el parasitismo de puesta (o de nido), que consiste en colocar a su descendencia en nidos ajenos para que sean empollados y criados por otras aves [ 3 ]. Para ello, las hembras de cuco han desarrollado como mecanismo biológico la puesta de 16 a 22 huevos de diferentes colores, con el objetivo de engañar a la madre huésped. Además de este esquema de supervivencia, CS incluye una estrategia de búsqueda basada en una caminata aleatoria descrita por la distribución de Lévy, también conocida como vuelo de Lévy (o Lévy’s flight) [ 8 ]. Este comportamiento ha sido observado en diversos seres vivos como microorganismos, abejas, moscas, albatros, tiburones y humanos [6]. 2. DESCRIPCIÓN DEL MÉTODO El proceso de búsqueda de CS tiene como objetivo encontrar el mejor nido, relacionado con la mejor solución de un problema de optimización. Para ello, se identifican aleatoriamente un número definido de nidos dentro de la región factible, en donde cada uno representa un candidato a la solución del problema. Seguidamente, los cucos esconden sus huevos en los nidos, siendo cada huevo un elemento para medir la calidad de la solución. Si un huevo posee una excelente calidad (logra engañar al ave huésped), éste eclosionará y sobrevivirá para ser parte de la siguiente generación de cucos. Si lo anterior no sucede, el huevo perecerá o el nido será abandonado. Así, los nidos de baja calidad serán reemplazados por otros en cada nueva generación. Lo anterior se puede resumir en tres reglas simples: 1. Cada cuco elige aleatoriamente un nido para depositar uno o varios huevos. 2. Los huevos mejor camuflados en un nido serán parte de la nueva generación de cucos. Autores: Jorge Mario Cruz–Duarte, DICIS, Universidad de Guanajuato (UG), Salamanca, Guanajuato, 36885, México, [email protected]; Ignacio Martín–Díaz, DICIS, Universidad de Guanajuato (UG), Salamanca, Guanajuato, 36885, México, [email protected]; Iván Cruz–Aceves, CONACYT, Centro de Investigación en Matemáticas (CIMAT), A.C., Guanajuato, Guanajuato, 36000, México, [email protected]. 12:2 Cruz–Duarte et al. 3. Las aves huéspedes descubren a los demás huevos con una probabilidad pDdada. Por simplicidad, la probabilidad pD se asume como la porción de nidos a ser reemplazados, luego pD=NA/NT, siendo NAla cantidad de nidos abandonados y NTel total de nidos. Ahora bien, se procede a describir detalladamente los pasos del método Cuckoo Search, necesarios para especificar su algoritmo y realizar su implementación. 2.1. Definición del problema Un problema de optimización se define comúnmente de la siguiente manera: ®x∗=arg m´ ın ®x∈Ω{f(®x)},(1) en donde se dice que ®x∗ minimiza a f(®x) , siendo f(®x) : RD→R la función objetivo (o de costo en problemas de minimización), y Ω⊆RD la región factible. En los problemas sencillos Ω se define por restricciones simples, como: Ω={®x∈RD:®xinf ≼ ®x≼ ®xsup}(2) siendo ®xinf y ®xsup respectivamente los límites inferiores y superiores de las restricciones. Con esta información es posible implementar cualquier algoritmo de optimización, en este caso, un método iterativo como lo es Cuckoo Search. Adicionalmente, estos métodos requieren de, por lo menos, un criterio de parada, como lo es el número máximo de generaciones (M). 2.2. Inicialización de las variables Una vez que es definido el problema, se procede a identificar el primer conjunto de N nidos (o de candidatos a solución), definido como X0={®x0 1,®x0 2, . . . , ®x0 N} . La manera más sencilla de realizar esto consiste en distribuir los puntos ( ®x0 k ) aleatoriamente dentro del espacio de búsqueda Ω , de acuerdo con: ®x0 k=®xinf +®u◦(®xsup − ®xinf ),(3) donde k∈ { 1 , 2 , . . . , N} , ®xinf y ®xsup son las fronteras inferiores y superiores de Ω , y ®u es un vector de elementos aleatorios e independientes con distribución uniforme entre cero y uno. El operador ◦es la multiplicación vectorial elemento–a–elemento. Además de inicializar los agentes de búsqueda, se deben definir los parámetros propios del método como: la probabilidad de que un huevo sea descubierto ( pD ), el número de nidos por generación (N), y el número de generaciones de cucos (M). 2.3. Identificación de la mejor solución Para cualquier generación t, el conjunto de huevos escondidos en los nidos (Xt) es evaluado en la función objetivo f(®x) , f(Xt)={f(®xt 1),f(®xt 2), . . . , f(®xt N)} , con lo que es posible identificar la mejor solución (®xt ∗) de la generación, como, ®xt ∗=arg m´ ın ®xt k{f(Xt)} :f(®xt k) ≤ f(®xt j),j∈ {1,2, . . . N}\k.(4) En otras palabras, ®xt ∗ corresponde a la posición que evaluada en f(®x) entrega el menor valor, comparado con los valores generados por las otras N−1posiciones. 2.4. Determinación de la nueva generación Para hallar la nueva generación de cucos, Xt+1 , cada nuevo candidato ®xt+1 k∈Xt+1 debe cumplir que f(®xt+1 k) ≤ f(®xt k) . El conjunto de nuevos candidatos se determina con las estrategias propias Escuela de Cómputo Evolutivo 2017, Centro de Investigación en Matemáticas, A.C. View publication stats