Estabilidad

A L G O RIT MO S E VOL U T I VO S A V AN ZA D O S

5.1. INTRODUCCIÓN
En este capítulo se presentan algunas modificaciones al diseño de un algoritmo evolutivo para mejorar su performance. El hecho de innovar en alguna de las características de los algoritmos evolutivos, a fin de acrecentar su calidad y aplicabilidad, los transforman en algoritmos evolutivos avanzados. Estas

modificacionespueden afectar tanto a los operadores genéticos como al mecanismo de selección y tienen por objetivo balancear la explotación y la exploración a fin de evitar la convergencia prematura durante el proceso de búsqueda. En los siguientes apartados se presentan tres técnicas que combinadas minimizan el riesgo de la convergencia prematura, a lo cual se le suma que la población final se encuentre centradaalrededor de la solución óptima al problema en cuestión. Las técnicas son: ' ' ' Múltiples padres. Múltiples crossovers. Prevención de incesto.

5.2. ALGORITMOS EVOLUTIVOS AVANZADOS CON MÚLTIPLES PADRES Y MÚLTIPLES CROSSOVERS
En la evolución simulada, es decir con algoritmos evolutivos, muchas características técnicas se inspiran por los mecanismos naturales. En particular, variantesabstractas de la reproducción sexual y asexual se implementan como operadores de búsqueda. Algunas técnicas evolutivas, por ejemplo programación evolutiva, trabajan

exclusivamente con mutación (es decir, implementan una simplificación de la reproducción asexual), mientras otras, por ejemplo algoritmos genéticos y estrategias

MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING

evolutivas, usanrecombinación (implementan una simplificación de la reproducción sexual) y mutación. Hay varios trabajos que investigan las ventajas y desventajas de la mutación con respecto al crossover [41, 60, 63, 86, 125,131]. Técnicamente, la cuestión se centra en la aridad de los operadores de reproducción. La mutación y el crossover tienen aridad uno y dos, respectivamente, y la pregunta es si los operadores unarioso binarios son preferibles para instancias típicas de problemas de optimización de relevancia práctica. Desde el punto de vista técnico, no hay necesidad de restringir la aridad de los operadores de reproducción en uno o dos. En general, un operador de reproducción puede tener una aridad desde uno al tamaño de la población (o aún más, si se permite la repetición entre los padres). Durante eldesarrollo de la computación evolutiva se han propuesto varios operadores de recombinación, algunos alrededor de los sesenta [19]. En estrategias evolutivas, la recombinación global puede mezclar información proveniente de más de dos padres en un hijo [8, 126]. En algoritmos genéticos, la recombinación p-sexual voting de Mühlenbein [106], scanning crossover y diagonal crossover [37] y recombinacióngene-pool [107, 141] son ejemplos de operadores multi-parents.

5.2.1. EVOLUCIÓN DE LA OPCIÓN MULTIPARENT Un proceso de evolución mantiene una población de cromosomas a efectos de buscar a través del espacio de búsqueda de soluciones potenciales. Se debe lograr un balance entre [18]: la explotación de la mejor solución y la exploración del espacio de búsqueda. Un factor a tener en cuenta, a lahora de mantener un buen balance, es el efecto causado por los mecanismos de selección: una fuerte presión selectiva puede producir una convergencia prematura a un óptimo local, mientras que una presión selectiva suave puede llevar a que la búsqueda se vuelva inefectiva. El crossover contribuye en gran medida al intercambio de material genético durante la ejecución de un algoritmo evolutivo. Esteoperador combina las características de dos cromosomas para formar dos hijos similares al intercambiar los segmentos correspondientes de los padres. La idea detrás de la aplicación del operador de crossover es el intercambio de información entre diferentes soluciones potenciales. Muchos investigadores estudiaron el efecto de distintos tipos de crossover para mejorar la 62

MÉTODOS DE SOLUCIÓN...