Operadores en algoritmos genéticos

Los algoritmos genéticos son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin en el año 1859. Por imitación de este proceso, los algoritmos genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Los principios básicos de los algoritmos genéticos fueron establecidos por John Holland, en el libro publicado el año 1975 titulado “Adaptación en sistemas naturales y artificiales”, y se encuentran descritos en varios textos, de los cuales resalta el libro de David Goldberg publicado el año 1989 titulado “Algoritmos genéticos en la búsqueda, optimización y aprendizaje automático; en este libro se menciona que los principales operadores genéticos son los operadores de selección, apareamiento y mutación.

Según David Golderg, en el libro citado en párrafo precedente, el objetivo de la selección es elegir las mejores soluciones y desplazar fuera de la población aquellas cuya aptitud sea inferior. Una característica importante del operador selección es que, no depende del tipo de representación elegida para codificar los individuos, tan solo se tiene en cuenta el valor de la adaptabilidad. La presión que este operador ejerce en el proceso de búsqueda es muy importante ya que, si es elevada, la búsqueda termina prematuramente. Por el contrario, si es insuficiente, el algoritmo evoluciona muy lentamente. La selección de los individuos que van a reproducirse de la población a partir de la antigua se realiza mediante un operador de selección. El operador de selección hace la elección basándose en los valores de adaptación de los individuos.

En palabras de Miller y Goldberg, en el artículo escrito el año 1995 titulado “Algoritmos genéticos, esquemas de selección y los efectos variables del ruido”, existen distintos operadores de selección que pueden utilizarse, los más significativos son: (1) Muestreo aleatorio simple. Es el mecanismo clásico que propuso John Holland el año 1975, en este modelo se calcula la probabilidad de selección de forma proporcional al valor de la función de adaptación. Este método llamado también el de la ruleta consiste en crear una ruleta en la que cada cromosoma tiene asignada una fracción proporcional a su adaptabilidad. Esta ruleta se gira varias veces para determinar qué individuos se seleccionarán. Debido a que, a los individuos más aptos se les asigna un área mayor de la ruleta, se espera que sean seleccionados más veces que los menos aptos. (2) Muestreo universal estocástico. El método se basa en el empleo de la misma ruleta considerada en el muestreo aleatorio simple, con un número de marcas igualmente espaciadas, equivalente a la longitud de la población. Este tipo de muestreo llamado “muestreo universal estocástico”, tiene en cuenta la ruleta sesgada, pero en lugar de realizar varios giros; utiliza un único giro para seleccionar todos los individuos. Para ello dispone de un sistema de marcadores igualmente espaciados cuya posición se elige aleatoriamente. (3) Selección por torneo. Constituye un procedimiento de selección de padres muy extendido. La idea consiste en escoger al azar un número de individuos de la población, determinar el mejor tamaño del torneo, con o sin reemplazamiento, seleccionar el mejor individuo de este grupo, y repetir el proceso hasta que el número de individuos seleccionados coincida con el tamaño de la población. Habitualmente el tamaño del torneo es dos, denominado “torneo binario”, que es el que proporciona mayor diversidad y menor presión selectiva. Así, en este método se baraja la población y después se hace competir a los cromosomas que la integran en grupos de tamaño predefinido en un torneo del que resultarán ganadores aquéllos que tengan valores de adaptabilidad más altos. Si se efectúa un torneo binario se utiliza una versión probabilística en la cual se permite la selección de individuos sin que necesariamente sean los mejores.