Algoritmos genéticos

Publicado por

Los algoritmos genéticos forman parte del conjunto de algoritmos evolutivos, estos son llamados así porque basan su funcionamiento en el proceso de la evolución natural. Este tipo de algoritmos parten de un conjunto de soluciones del problema al cual se le llama población inicial, otra de sus características notables es el intercambio de información que existe entre los individuos de esa población. Estos algoritmos se utilizan para encontrar soluciones a problemas de optimización y de búsqueda.

La idea de John Henry Holland el creador de los algoritmos genéticos- era desarrollar un algoritmo que pudiera inspirarse en la evolución biológica de los seres vivos, tal como Darwin lo había postulado en el libro El origen de las especies”:

  • Existen diferencias en los rasgos de los individuos de cada especie.
  • Algunos de estos rasgos son heredados.
  • Solamente los individuos más aptos sobreviven lo suficiente para reproducirse.

Como es de esperarse, al ser un algoritmo inspirado en la evolución,  los nombres que se usan para cada una de sus partes son precisamente tomados de los conceptos de la propia genética.

  • Fenotipo: conjunto de soluciones de un problema (población inicial).
  • Cromosoma: cadena que codifica la información de cada solución al problema.

    Cromosoma representado como cadena de dígitos binarios.
    Cromosoma representado como cadena de dígitos binarios.
  • Genes: símbolos que forman la cadena (cromosoma).
  • Genotipo: cromosomas representados con cadenas de dígitos binarios.
  • Generaciones: iteraciones para que los cromosomas evolucionen.
  • Función de aptitud: forma de evaluar las soluciones representadas por los cromosomas.
  • Operadores genéticos: función que se emplea para mantener la diversidad genética de la población (selección, cruzamiento y mutación).
  • Selección: una vez que se aplica la función de aptitud a cada cromosoma, se eligen los más aptos para ser cruzados con la nueva generación.
  • Cruzamiento: este operador es el más importante, combina dos cromosomas para generar dos hijos que comparten las características de los padres.
    Representación de cruza de dos cromosomas.
    Representación de cruza de dos cromosomas.

    Se obtienen los descendientes:

Resultado de la cruza de dos cromosomas.
Resultado de la cruza de dos cromosomas.
  • Mutación: este operador tiene como objetivo modificar al azar algunas partes del cromosoma, para así expandir la búsqueda en espacios que no estaban contemplados por los individuos iniciales.
Mutación de un cromosoma.
Mutación de un cromosoma.

Algoritmo genético simple

Funcionamiento

Como ya mencioné, en los algoritmos genéticos se debe emplear una población inicial construida a partir de un conjunto de soluciones del problema, esta población es primordial para la implementación del algoritmo, ya que a ella se le aplican los operadores genéticos para encontrar la mejor solución. La razón de la búsqueda consiste en explorar el espacio alrededor de la mejor solución encontrada y además buscar en otras secciones del espacio que no han sido explorados, con la intención de encontrar la más apta.

Algoritmo genético.
Algoritmo genético.

Se puede decir que un algoritmo genético consiste en: codificar el problema en una cadena binaria, generar una población inicial de cadenas binarias y finalmente aplicar los operadores genéticos hasta que se cumpla una condición o se llegue al número de iteraciones establecidas, es decir, hasta que se obtenga la mejor solución posible.

Pseudocódigo

El siguiente pseudocódigo explica la forma más simple de implementar un algoritmo genético.

 
Comienza
  población inicial
  evaluación de los cromosomas de la población inicial
  repite
    comienza
      selección de los cromosomas más aptos en la nueva población
      cruzamiento a los cromosomas de la población
      mutación a los cromosomas de la población
      evaluación a los cromosomas de la población
   termina
  hasta que se cumpla la condición de terminación
  regresa la mejor solución (la más apta) en la población
termina

Concluyendo

Los algoritmos genéticos permiten explorar partes del espacio de soluciones que pueden resultar óptimas para resolver un problema, en lugar de explorar todas las posibles soluciones, que en muchos casos puede llegar a ser extremadamente tardado o imposible. Algunas de las áreas en las que se aplican estos algoritmos son: optimización, teoría de juegos, aprendizaje maquinal, bioinformática, diseño de redes, redes neuronales, entre otros.

Algoritmo genético

3 comments

  1. Interesante; quisiera implementar este tema en un campo de la Ing. Civil. Por favor donde puedo encontrar más información, libros, tesis, revistas, etc.

    1. Hola, me alegra que sea de tu interés.

      Algunas referencias:

      – Altenberg L., (1995), The Schema Theorem and Price’s Theorem, in foundations of Genetic Algorithms 3, ed. Darrell Whitley and MIchael Vose, Moevrgan Kaufmann, San Francisco. pp. 23-49.

      – Goldberg D.E., (1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Professional.

      – Kuijpers C. M. H., Murga R. H., Inza I. and Dizdarevic S., (1999), Genetic algorithms for travelling salesman problem: A review of representations an operators, Artificial Intelligence Review, Volume 13, Issue 2, pp. 129-170.

      -Michalewicz Z., (1998), Genetic Algorithms + Data Structures = Evolutions Programs, Springer, 3ra ed.

      Espero te sean útiles. Saludos.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *