ALGORITMOS GENETICOS

INTRODUCCION:
La capacidad del ser humano para predecir el comportamiento de su entorno, se ha ido
incrementando con el paso del tiempo. De igual modo, ha comprendido que, si bien era capaz de
controlar muchos aspectos de su vida, y su interacción con lo que le rodeaba, no lo era para otros
tantos.
La inteligencia artificial es responsable de muchos de esos logros. Los pioneros de esta ciencia
estaban tan interesados en la electrónica, como en la biología, y por eso sus aplicaciones iban
desde calcular trayectorias de misiles, a tratar de modelizar el cerebro, de imitar el proceso de
aprendizaje humano, y de simular la evolución biológica.

Los años ochenta (en el siglo pasado) marcan el florecimiento del interés de la comunidad
científica por estos temas computacionales inspirados en la biología, que han visto como su
desarrollo les llevaba a cotas inimaginables, primero en el campo de las Redes Neuronales, luego
en el del Aprendizaje, y por último en lo que ahora se conoce como "computación evolutiva", de
la que los algoritmos genéticos constituyen su máximo exponente.

MARCO TEORICO Y RESEÑA HISTORICA:

El origen de lo que se conoce como computación evolutiva hay que buscarlo en su razón de ser:
los conocimientos sobre evolución se pueden aplicar en la resolución de problemas de
optimización. Fue en las décadas de 1950 y 1960 cuando varios científicos, de modo
independiente, comenzaron a estudiar los sistemas evolutivos, guiados por la intuición de que se
podrían emplear como herramienta en problemas de optimización en ingeniería. La idea era
"evolucionar" una población de candidatos a ser solución de un problema conocido, utilizando
operadores inspirados en la selección natural y la variación genética natural.
Centrémonos en los Algoritmos Genéticos. La primera mención del término, y la primera
publicación sobre una aplicación del mismo, se deben a Bagley (1967), que diseñó algoritmos
genéticos para buscar conjuntos de parámetros en funciones de evaluación de juegos, y los
comparó con los algoritmos de correlación, procedimientos de aprendizaje modelizados después
de los algoritmos de pesos variantes de ese periodo.

En estos últimos años se ha generado una amplia interacción entre los investigadores de varios
métodos de computación evolutiva, rompiéndose las fronteras entre algoritmos genéticos,
estrategias evolutivas y programación evolutiva. Como consecuencia, en la actualidad, el término
"algoritmo genético" se utiliza para designar un concepto mucho más amplio del que concibió
Holland.

¿QUÉ SON LOS ALGORITMOS GENÉTICOS?

Los objetivos que perseguían John Holland y sus colegas de la Universidad de Michigan cuando
concibieron los algoritmos genéticos, eran dos: abstraer y explicar rigurosamente el proceso
adaptativo de los sistemas naturales, y diseñar sistemas artificiales que retuvieran los mecanismos
más importantes de los sistemas naturales. En este sentido, podemos decir que los algoritmos
genéticos son Algoritmos de búsqueda basados en los mecanismos de selección natural y genética
natural. Combinan la supervivencia de los más compatibles entre las estructuras de cadenas, con
una estructura de información ya aleatorizada, intercambiada para construir un algoritmo de
búsqueda con algunas de las capacidades de innovación de la búsqueda humana. Básicamente, el
Algoritmo Genético funciona como sigue: en cada generación, se crea un conjunto nuevo de
"criaturas artificiales" (cadenas) utilizando bits y partes más adecuadas del progenitor. Esto
involucra un proceso aleatorio que no es, en absoluto, simple. La novedad que introducen los
Algoritmos Genéticos es que explotan eficientemente la información histórica para especular
sobre nuevos puntos de búsqueda, esperando un funcionamiento mejorado.

ELEMENTOS DE UN ALGORITMO GENÉTICO Y SU TRADUCCIÓN

BIOLÓGICA.
Todos los organismos que conocemos están compuestos por una o más células, cada una de las
cuales contiene a su vez uno o más cromosomas (esto es, cadenas de ADN), que tienen la función
de ser una especie de "anteproyecto" del organismo del que forman parte. Un cromosoma se puede
dividir, conceptualmente, en genes, bloques funcionales de ADN que codifican una determinada
proteína. Solemos pensar en los genes, aunque en una visión muy superficial, como los
responsables de determinar los rasgos del individuo, tales como el color de los ojos, o del cabello.
Las diferentes posibilidades de escoger un rasgo (ojos azules, marrones o verdes, por ejemplo)
reciben el nombre de alelos. Cada gene está localizado en una determinada
posición (lugar) dentro del cromosoma que integra. Muchos organismos tienen varios
cromosomas en cada célula. El genoma del organismo es la colección completa del material
genético. Lo que se conoce como genotipo, es el conjunto de genes contenido en un genoma. El
genotipo dará lugar, tras el desarrollo fetal, al fenotipo del organismo, esto es, a sus características
físicas y mentales, tales como el color de ojos, la estatura, o la inteligencia.

La mayoría de las especies reproductoras sexualmente que habitan nuestro planeta, almacenan
sus cromosomas por parejas (son diploides; se llaman haploides en caso contrario). En el caso del
ser humano, cada célula somática (no germen) de su cuerpo contiene 23 pares de cromosomas.
Durante la reproducción sexual se produce una recombinación o cruce: en cada padre, se
intercambian los genes entre cada par de cromosomas, para formar un gameto (un cromosoma
único), y entonces, los gametos de los dos padres se emparejan para constituir un conjunto
completo de cromosomas diploides. En el caso de la reproducción haploide, los genes se
intercambian entre dos padres con una sola rama de cromosomas. La descendencia está sujeta
a mutaciones, donde se produce un cambio en algún nucleótido (bits elementales de ADN) de
padre a hijo; esas modificaciones son resultado habitualmente de "errores de copia".
La capacidad del organismo se define como la probabilidad de que el organismo viva para
reproducirse (viabilidad) o como una función del número de descendencia que tenga ese
organismo (fertilidad).Traslademos estos conceptos a la "vida artificial": en los algoritmos
genéticos, el término cromosoma se refiere a un candidato a solución del problema, que a menudo
se codifica como una cadena de bits. Los genes son tanto un bit como bloques cortos de bits
adyacentes que codifican un elemento particular del candidato a solución (por ejemplo, en el caso
de la optimización de una función multiparamétrica, los bits que codifican un parámetro
particular, se considera un gene). Un alelo en una cadena de bits será un 0 o un 1 (para alfabetos
largos cada lugar puede tener más alelos).
El cruce consiste, normalmente, como en su espejo biológico, en un intercambio de material
genético entre dos cromosomas de dos padres haploides. La mutación es una permutación en un
bit en un lugar aleatorio (o, en el caso de alfabetos largos, remplazar el símbolo de un lugar
escogido aleatoriamente con un símbolo nuevo escogido también aleatoriamente).
En la mayoría de las aplicaciones de los algoritmos genéticos nos encontraremos con individuos
haploides, concretamente, de cromosomas únicos. El genotipo de un individuo en un algoritmo
genético que emplea cadenas de bits es, simplemente, la configuración de bits del cromosoma de
ese individuo. La noción de fenotipo no aparece en el contexto de los algoritmos genéticos,
aunque avances recientes en la materia trabajan con algoritmos que poseen un nivel "genotípico"
y uno "fenotípico" (por ejemplo, la cadena de bits que codifica una red neuronal, y la red en sí
misma).
Según hemos visto, podemos considerar que los algoritmos genéticos tienen, al menos, estos
elementos en común: poblaciones de cromosomas, selección en base a su capacidad, cruces para
producir descendencia nueva, y mutación aleatoria de la nueva descendencia. La inversión - el
cuarto elemento de los algoritmos genéticos tal y como los concibió Holland - se usa raramente
en las implementaciones actuales, y sus ventajas, si las tiene, no están del todo establecidas. Se
puede pensar en cada cromosoma de un algoritmo genético como en un punto en el espacio de
búsqueda de candidatos a soluciones.
El algoritmo genético procesa poblaciones de cromosomas, remplazando sucesivamente cada
población por otra. El algoritmo suele requerir una función de capacidad o potencial que asigna
una puntuación (la capacidad) a cada cromosoma de la población actual. La capacidad o el
potencial de un cromosoma depende de cómo resuelva ese cromosoma el problema a tratar4. Un
concepto relacionado es el del "paisaje del potencial". Definido originalmente por Sewell Wright
(1931) en el contexto de la genética de poblaciones, el paisaje de un potencial es la representación
del espacio de todos los posibles genotipos junto con sus capacidades.
De este modo, los operadores de cruce y mutación pueden verse como modos de mover una
población en el paisaje definido por su función de capacidad, y un algoritmo genético como un
método de búsqueda de ese paisaje para cadenas altamente cualificadas. La forma más simple de
algoritmo genético utiliza ocho tipos de operadores: inicialización, evaluación, condición de
término, selección, cruce, mutación y reemplazo.
ALGORITMO GENÉTICO
En el algoritmo vemos los siguientes pasos: i Inicialización, f(X): evaluación?: condición de
término, Se: selección, Cr: cruzamiento, Mu: mutación, Re: reemplazo, X*: ' solución

 Selección o reproducción: Este operador escoge cromosomas entre la población para

efectuar la reproducción. Cuanto más capaz sea el cromosoma, más veces será
seleccionado para reproducirse.
 Cruce: Se trata de un operador cuya labor es elegir un lugar, y cambiar las secuencias
antes y después de esa posición entre dos cromosomas, para crear nueva descendencia
(por ejemplo, las cadenas 10010011 y 1111010 pueden cruzarse después del tercer lugar
para producir la descendencia 10011010 y 11110011). Imita la recombinación biológica
entre dos organismos haploides.
 Mutación: Este operador produce variaciones de modo aleatorio en un cromosoma (por
ejemplo, la cadena 00101101 puede mutar en una posición para dar lugar a la cadena
00111101). La mutación puede darse en cada posición de un bit en una cadena, con una
probabilidad, normalmente muy pequeña (por ejemplo 0.001).
 Reemplazo una vez aplicados los operadores genéticos, se seleccionan los mejores
individuos para conformar la población de la generación siguiente.

Como se ve, los Algoritmos Genéticos difieren de los métodos tradicionales de búsqueda y
optimización, en cuatro cuestiones esenciales:
 1. Trabajan con un código del conjunto de parámetros, no con el conjunto mismo (necesitan
que el conjunto de parámetros del problema de optimización esté codificado en cadenas
finitas sobre un determinado alfabeto). Por trabajar a nivel de código, y no con las
funciones y sus variables de control, como los otros métodos, son más difíciles de
"engañar".
2. Buscan una población de puntos, no un único punto. Manteniendo una población de
puntos muestrales bien adaptados, se reduce la probabilidad de caer en una cima falsa
3. Emplean la función objetivo, no necesitan derivadas ni otra información complementaria,
tan difícil a veces de conseguir. De este modo ganan en eficiencia y en generalidad.
4. Se valen de reglas de transición estocásticas no deterministas. Los Algoritmos Genéticos
se valen de operadores aleatorios para guiar la búsqueda de los mejores puntos; puede
parecer extraño, pero la Naturaleza está llena de precedentes al respecto.

APLICACIONES DE LOGARITMOS GENETICOS

Se han aplicado a diversos problemas y modelos en ingeniaría, y en la ciencia en genera. Cabe
destacar entre ellos:
 Optimización: Se trata de un campo especialmente abonado para el uso de los
Algoritmos Genéticos, por las características intrínsecas de estos problemas. No en
vano fueron la fuente de inspiración para los creadores estos algoritmos. Los
Algoritmos Genéticos se han utilizado en numerosas tareas de optimización,
incluyendo la optimización numérica, y los problemas de optimización combinatoria.
 Programación automática: Los Algoritmos Genéticos se han empleado para
desarrollar programas para tareas específicas, y para diseñar otras estructuras
computacionales tales como el autómata celular, y las redes de clasificación.
 Aprendizaje máquina: Los algoritmos genéticos se han utilizado también en muchas
de estas aplicaciones, tales como la predicción del tiempo o la estructura de una
proteína. Han servido asimismo para desarrollar determinados aspectos de sistemas
particulares de aprendizaje, como pueda ser el de los pesos en una red.
 Economía: En este caso, se ha hecho uso de estos Algoritmos para modelizar
procesos de innovación, el desarrollo estrategias de puja, y la aparición de mercados
económicos.
 Sistemas inmunes: A la hora de modelizar varios aspectos de los sistemas inmunes
naturales, incluyendo la mutación somática durante la vida de un individuo y el
descubrimiento de familias de genes múltiples en tiempo evolutivo, ha resultado útil
el empleo de esta técnica.
 Ecología: En la modelización de fenómenos ecológicos tales como las carreras de
armamento biológico, la co-evolución de parásito-huesped, la simbiosis, y el flujo de
recursos.
 Genética de poblaciones: En el estudio de preguntas del tipo "¿Bajo qué condiciones
será viable evolutivamente un gen para la recombinación?"
 Evolución y aprendizaje: Los Algoritmos Genéticos se han utilizado en el estudio
de las relaciones entre el aprendizaje individual y la evolución de la especie.
 Sistemas sociales: En el estudio de aspectos evolutivos de los sistemas sociales, tales
como la evolución del comportamiento social en colonias de insectos, y la evolución
de la cooperación y la comunicación en sistemas multi-agentes.
La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de
optimización, en donde han mostrado ser muy eficientes. Sin embargo, no todos los problemas
pudieran ser apropiados para esta técnica. Se recomienda en general tomar en cuenta las siguientes
características del mismo antes de intentar usarla:
 Su espacio de búsqueda debe estar
delimitado dentro de un cierto
rango.
 Debe poderse definir una función
de aptitud que nos indique qué tan
buena o mala es una cierta
respuesta.
 Las soluciones deben codificarse
de una forma que resulte
relativamente fácil de implementar
en la computadora.
Dentro de los distintos problemas de optimización podemos encontrar unas áreas de aplicación:
• Diseño por computadora de nuevos materiales que cumplan múltiples objetivos.
• Optimización del la carga de containers.
• Asignación de procesos en topologías de redes con procesamiento distribuido.
• Ubicación de archivos en sistemas de almacenamiento distribuido.
• Diseño de circuitos integrados.
• Optimización de la infraestructura de telefonía celular.
• Ingeniería Aeroespacial.
• Juegos.
• Robótica

EJEMPLO
El problema del agente viajero, también denominado TSP (Travelling Salesman Problem),
consiste en, dada una colección de ciudades, determinar el recorrido de coste mínimo, visitando
cada ciudad exactamente una vez y volviendo al punto de partida. Más precisamente, dado un
número entero n ≥ 3 y dada una matriz
C = (cij) є M(n, n), con elementos cij
enteros no negativos, se trata de
encontrar la permutación cíclica Π de
los enteros de 1 a n que minimiza n ∑ c
Π(i),Π(i+1) con Π(n+1)=1 i=1 A lo
largo de los años el problema del agente
viajero ha ocupado la mente de
numerosos investigadores. Los motivos
son varios. En primer lugar, el TSP es
un problema muy sencillo de enunciar,
pero muy difícil de resolver. En
segundo lugar, el TSP es aplicable a una
gran variedad de problemas de planificación. Finalmente, se ha convertido en una especie de
problema test, es decir los nuevos métodos de optimización combinatoria son a menudo aplicados
al TSP con objeto de tener una idea de sus potencialidades.
Los Algoritmos Genéticos han llegado a ser u n campo puntero en la investigación actual.

En esta página se encuentra un applet de Java en el que se muestra un relieve de un determinado

paisaje generado de forma aleatoria. Se puede elegir la población inicial. Al ejecutar el programa,
el algoritmo trata de buscar la máxima altura a la que podemos ascender.
CONCLUSIONES
 Se dice que la evolución cultural humana ha reemplazado a la biológica que nosotros,
como especie, hemos llegado a un punto en el que somos capaces de controlar
conscientemente nuestra sociedad, nuestro entorno y hasta nuestros genes al nivel
suficiente para hacer que el proceso evolutivo sea irrelevante
 Pero en otro sentido, nada podría estar más lejos de la verdad. La evolución es un proceso
de resolución de problemas cuyo poder sólo comenzamos a comprender y explotar; a
pesar de esto, ya está funcionando por todas partes, moldeando nuestra tecnología y
mejorando nuestras vidas.
 En el futuro, estos usos no harán sino multiplicarse. Sin un conocimiento detallado del
proceso evolutivo no habrían sido posibles ninguno de los incontables avances que le
debemos a los algoritmos genéticos. Aquí hay una lección que deben aprender los que
niegan el poder de la evolución y los que niegan que el conocimiento de ella tenga
beneficios prácticos. Por increíble que pueda parecer, la evolución funciona. Como lo
expresa el poeta Lord Byron: "Es extraño pero cierto; porque la verdad siempre es
extraña, más extraña que la ficción. ‘‘
 Los algoritmos genéticos son actualmente una fuerte fuente de resolución de problemas
complejos al realizar su ejecución en paralelo pudiendo así obtener diferentes soluciones
al problema. Sin embargo, como se ha podido observar, no hay ninguna estrategia que
sea siempre invencible, sino que hay un conjunto de estrategias que suelen dar buenos
resultados. Así pues, habrá que ajustar los parámetros de acción en función de cada
problema a modelar para obtener una solución que se adapte mejor a unas determinadas
condiciones. Sin embargo, en una situación real puede suceder que no se conozcan los
parámetros iniciales o que no se sepa la duración del algoritmo. Por lo tanto habrá que
elegir con sumo cuidado los parámetros iniciales. Un crossover elevado es recomendable
para la mayoría de los problemas aunque hay situaciones en las que un crossover menor
dará mejores resultados.
 La población a elegir debe atender a un valor óptimo (no por tener una población mayor,
se va a tener una solución mejor), la codificación dependerá del problema a resolver como
se ha visto con anterioridad y por último el método de selección más utilizado es el de
selección por rueda de ruleta, aunque como se ha comentado, dependerá de la cuestión
que nos trate.
 Por último, se pretende que estos algoritmos se parezcan lo más posible a lo que en
realidad sucede en la naturaleza. Por ejemplo, cuando una población queda aislada en la
naturaleza, como sucede, por ejemplo, con los linces de Doñana, se pierde diversidad al
haber un grupo reducido que se reproduce entre si constantemente perdiéndose esa tan
necesaria diversidad para sobrevivir. De hecho se ha comprobado que no evolucionan y
que su adaptación a las condiciones no mejora en función del cambio de éstas.