En los algoritmos genéticos , un cromosoma (también llamado a veces genotipo ) es un conjunto de parámetros que definen una solución propuesta al problema que el algoritmo genético está tratando de resolver. El conjunto de todas las soluciones se conoce como población . [1] El cromosoma a menudo se representa como una cadena binaria , aunque también se utiliza una amplia variedad de otras estructuras de datos .
Diseño de cromosomas
El diseño del cromosoma y sus parámetros es necesariamente específico del problema a resolver. Tradicionalmente, los cromosomas se representan en binario como cadenas de 0 y 1, sin embargo, también son posibles otras codificaciones; [2] se puede utilizar casi cualquier representación que permita representar la solución como una cadena de longitud finita. [3] Encontrar una representación adecuada del dominio del problema para un cromosoma es una consideración importante, ya que una buena representación facilitará la búsqueda al limitar el espacio de búsqueda; de manera similar, una representación más pobre permitirá un espacio de búsqueda más grande. [4] El operador de mutación y el operador de cruce empleados por el algoritmo genético también deben tener en cuenta el diseño del cromosoma.
Ejemplo 1: representación binaria
Suponga que el problema es encontrar el valor entero de entre 0 y 255 que proporciona el resultado máximo para . Las posibles soluciones para este problema son los números enteros de 0 a 255, que pueden representarse como cadenas binarias de 8 dígitos. Por lo tanto, podríamos usar una cadena binaria de 8 dígitos como nuestro cromosoma. Si un cromosoma dado en la población representa el valor 155, su cromosoma sería 10011011
.
Tenga en cuenta que este no es el tipo de problema que normalmente se resuelve mediante un algoritmo genético, ya que puede resolverse trivialmente utilizando métodos numéricos; solo se usa para servir como un ejemplo simple.
Ejemplo 2: representación de cadena
Un problema más realista que podríamos querer resolver es el problema del viajante . En este problema, buscamos una lista ordenada de ciudades que resulte en el viaje más corto para que viaje el vendedor. Supongamos que hay seis ciudades, a las que llamaremos A, B, C, D, E y F. Un buen diseño para nuestro cromosoma podría ser la lista ordenada que queremos probar. Un ejemplo de cromosoma que podríamos encontrar en la población podría ser DFABEC
.
Selección, cruce y mutación
En cada generación del algoritmo genético, se seleccionan dos cromosomas parentales en función de sus valores de aptitud; estos cromosomas son utilizados por los operadores de mutación y cruzamiento para producir dos cromosomas descendientes para la nueva población. [3]
Referencias
- ^ "Introducción a los algoritmos genéticos: IV. Algoritmo genético" . Consultado el 12 de agosto de 2015 .
- ^ Whitley, Darrell (junio de 1994). "Tutorial de un algoritmo genético". Estadística y Computación . 4 (2). CiteSeerX 10.1.1.184.3999 . doi : 10.1007 / BF00175354 . S2CID 3447126 .
- ^ a b "¿Qué son los algoritmos genéticos?" . Consultado el 12 de agosto de 2015 .
- ^ "Algoritmos genéticos" . Consultado el 12 de agosto de 2015 .