Representaciones básicas

Abstract

La adaptación de de parámetros y operadores es una de las más improtantes y promisorias áreas de investigación en la computación evolutiva. La idea es ajustar el algoritmo al problema mientras se resuelve el mismo. En los algoritmos genéticos (AGs) no solo es necesario elegir la representación y los operadores para el problema, sino que también debemos elegir valores de parámetros y probabilidades de operadores del (AG) de manera tal que éste encuentre la solución y de manera eficiente. El proceso de encontrar 'a mano' valores apropiados de parámetros y probabilidades de operadores para un AG que afecten la performance del algoritmo de una manera significativa, es una tarea que implica consumo de tiempo y esfuerzo considerable. Ello ha motivado la automatización de dicho proceso. En los (AGs), las soluciones tentativas del espacio de búsqueda son codificadas o representadas tradicionalmente por medio de cadenas binarias, el Gray coding es una representación alternativa a la codificación estándar de potencias de 2. Bajo esta codificación los puntos adyacentes difieren en sólo un bit. Como uno de los principales operadores genéticos, el crossover permite que dos individuos con alto valor de fitness o adaptabilidad puedan combinar las mejores características de cada uno. Los nuevos individuos se crean por crossover alineando los padres escogidos y creando dos nuevos individuos por intercambio de subcadenas detemiinadas en un punto aleatorio de corte (one-point crossover). Otra alternativa es seleccionar 2 o más puntos de corte (two-point y multi-point crossover). También es de uso corriente el uniform crossover que intercambia aleatoriamente bits entre ambos padres. En el presente trabajo se analiza la relación. entre las representaciones de los individuos y los métodos de crossover a los cuales son sometidos, partiendo de una población inicial en la que a cada individuo se le asocia aleatoriamente una probabilidad de cruzamiento. A medida que evoluciona el (AG), las probabilidades que heredan los individuos hijos se adaptan dinámicamente en función de una regla determinística. De esta manera no solo se logra una evolución en el fitness de los individuos sino también en las probabilidades de cruzamiento.