JOHN HOLLAND

El autor de las ideas fundamentales de los algoritmos genéticos es John Holland, quien los presentó en Adaptation in Natural and Artificial Systems, Univ. of Michigan Press (1975).

En los años 1970, de la mano de John Holland, surgió una de las líneas más prometedoras de la inteligencia artificial, la de los algoritmos genéticos.

Un algoritmo genético (AG) es uno de los métodos heuristicos utilizados para hallar soluciones aproximadas a problemas NP-completos inspirado en los principios darwinianos de la evolución de las especies. Estos algoritmos son un caso particular de algoritmos evolucionarios y emplean técnicas propias de la Genética, tales como: herencia, mutación, selección natural y recombinación (o crossover).

Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.

Los algoritmos genéticos forman parte de una familia denominada algoritmos evolutivos, que incluye las estrategias de evolución, la programación evolutiva y la programación genética. Dentro de esta última se han logrado avances curiosos:

En 1999, por primera vez en la historia, se concedió una patente a un invento no realizado directamente por un ser humano: se trata de una antena de forma extraña, pero que funciona perfectamente en las condiciones a las que estaba destinada. No hay, sin embargo, nada injusto en el hecho de que el autor del algoritmo genético del que salió la forma de la antena se haya atribuido la autoría de la patente, pues él escribió el programa e ideó el criterio de selección que condujo al diseño patentado.

Un algoritmo genético es un método de búsqueda dirigida basada en probabilidad. Bajo una condición muy débil (que el algoritmo mantenga elitismo, es decir, guarde siempre al mejor elemento de la población sin hacerle ningún cambio) se puede demostrar que el algoritmo converge en probabilidad al óptimo. En otras palabras, al aumentar el número de iteraciones, la probabilidad de tener el óptimo en la población tiende a 1 (uno).

1.     Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas, que representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones para tener una representación de la mayor parte de la población posible o al menos evitar la convergencia prematura.

2.     A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber qué tan "buena" es la solución que se está codificando.

3.     Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación.

4.     Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.

5.     El cruzamiento es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.

6.     El AG se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población.

7.     El problema de selección de variables se puede ver como un problema de optimización, ya que si se quiere encontrar, bajo alguna heurística, el subconjunto de variables que potencialicen la diferenciación y las semejanzas de objetos de clases diferentes y de la misma clase respectivamente.

1.     Inicializar aleatoriamente una población de soluciones a un problema, representadas por una estructura de datos adecuada.

2.     Evaluar cada una de las soluciones, y asignarle una puntuación o fitness según lo bien que lo hayan hecho.

3.     Escoger de la población la parte que tenga una puntuación mayor

4.     Mutar (cambiar) y entrecruzar (combinar) las diferentes soluciones de esa parte escogida, para reconstruir la población.

5.     Repetir un número determinado de veces, o hasta que se haya encontrado la solución deseada.