PDF de programación - ALGORITMOS GENÉTICOS

ALGORITMOS GENÉTICOS

Arranz de la Peña, Jorge

Universidad Carlos III

[email protected]

Parra Truyol, Antonio

Universidad Carlos III

[email protected]



En este documento se pretende analizar los algoritmos genéticos
descubriendo su funcionamiento y sus secretos.

1. INTRODUCCION
Cuando hablamos de algoritmos genéticos, hay que hablar de
John Holland que en 1962 asienta las bases para sus posteriores
desarrollos hasta llegar a lo que se conoce hoy por algoritmos
genéticos.
Un algoritmo genético es un método de búsqueda que imita la
teoría de la evolución biológica de Darwin para la resolución de
problemas. Para ello, se parte de una población inicial de la cual
se seleccionan
individuos más capacitados para luego
reproducirlos y mutarlos para finalmente obtener la siguiente
generación de individuos que estarán más adaptados que la
anterior generación.

los

2. ESQUEMA BÁSICO
En la naturaleza todo el proceso de evolución biológica se hace de
forma natural pero para aplicar el algoritmo genético al campo de
la resolución de problemas habrá que seguir una serie de pasos.
Una premisa es conseguir que el tamaño de la población sea lo
suficientemente grande para garantizar
la diversidad de
soluciones. Se aconseja que la población sea generada de forma
aleatoria para obtener dicha diversidad. En caso de que la
población no sea generada de forma aleatoria habrá que tener en
cuenta que se garantice una cierta diversidad en la población
generada. Los pasos básicos de un algoritmo genético son:

los que

Evaluar la puntuación de cada uno de los cromosomas
generados.
Permitir la reproducción de los cromosomas siendo los
más aptos
tengan más probabilidad de
reproducirse.
Con cierta probabilidad de mutación, mutar un gen del
nuevo individuo generado.
Organizar la nueva población.

Estos pasos se repetirán hasta que se de una condición de
terminación. Se puede fijar un número máximo de iteraciones
antes de finalizar el algoritmo genético o detenerlo cuando no se
produzcan más cambios en la población (convergencia del
algoritmo). Esta última opción suele ser la más habitual.
Veamos el esquema general de un algoritmo genético simple:

ESTRUCTURA DE UN ALGORITMO

GENÉTICO SIMPLE (AGS)

Codificación
Codificación

Soluciones

Cromosomas
1100101010
1011101110
0011011001
1100110001

Selección
Selección

110010

1010

101110

1110

1100101110

Cruce
Cruce

0011011001
0011011001

0011001001
0011001001

1100101110
1100101110

1011101010
1011101010
0011001001
0011001001

Mutación
Mutación

Evaluación
Evaluación

Cálculo Aptitud
Cálculo Aptitud

Rueda de la Ruleta
Rueda de la Ruleta

Decodificación
Decodificación

Soluciones
Soluciones



Figura1. Esquema de un algoritmo genético simple.

3. PARÁMETROS DE LOS ALGORITMOS
GENÉTICOS.
Para el estudio de los algoritmos genéticos hay que tener en
cuenta una serie de parámetros:
3.1 Tamaño de la Población
Este parámetro nos indica el número de cromosomas que tenemos
en nuestra población para una generación determinada. En caso de
que esta medida sea insuficiente, el algoritmo genético tiene pocas
posibilidades de realizar reproducciones con lo que se realizaría
una búsqueda de soluciones escasa y poco óptima. Por otro lado si
la población es excesiva, el algoritmo genético será excesivamente
lento. De hecho estudios revelan que hay un límite a partir del
cual es ineficiente elevar el tamaño de la población puesto que no
se consigue una mayor velocidad en la resolución del problema.
3.2 Probabilidad de Cruce
Indica la frecuencia con la que se producen cruces entre los
cromosomas padre es decir, que haya probabilidad de
reproducción entre ellos. En caso de que no exista probabilidad de
reproducción, los hijos serán copias exactas se los padres. En caso
de haberla, los hijos tendrán partes de los cromosomas de los
padres. Si la probabilidad de cruce es del 100% el hijo se crea
totalmente por cruce, no por partes.
3.3 Probabilidad de Mutación
Nos indica la frecuencia con la que los genes de un cromosoma
son mutados. Si no hay mutación, los descendientes son los
mismos que había tras la reproducción. En caso de que haya
mutaciones, parte del cromosoma descendiente es modificado y si
la probabilidad de mutación es del 100%, la totalidad del
cromosoma se cambia. En este caso, no se cambian simplemente
unos bits del cromosoma sino que se cambian todos, lo que





significa que se produce una inversión en el cromosoma y no una
mutación por lo que la población degenera muy rápidamente.
4. OPERACIONES DE LOS ALGORITMOS
GENÉTICOS.
Tras parametrizar el problema en una serie de variables, se
codifican en un cromosoma. Todos los operadores utilizados por
un algoritmo genético se aplicarán sobre estos cromosomas, o
sobre poblaciones de ellos. En el algoritmo genético va implícito
el método para resolver el problema. Hay que tener en cuenta que
un algoritmo genético es independiente del problema, lo cual lo
hace un algoritmo robusto, al resultar útil en cualquier ámbito de
acción, pero a la vez débil, pues no está especializado en ninguno.
Las soluciones codificadas en un cromosoma compiten para ver
cuál constituye la mejor solución (aunque no necesariamente la
mejor de todas las soluciones posibles). El ambiente, constituido
por las otras soluciones, ejercerá una presión selectiva sobre la
población, de forma que sólo los mejor adaptados (aquellos que
resuelvan mejor el problema) sobrevivan o leguen su material
genético a las siguientes generaciones, igual que en la evolución
de las especies. La diversidad genética se introduce mediante
mutaciones y reproducción sexual.
Por lo tanto, un algoritmo genético consiste en hallar de qué
parámetros depende el problema, codificarlos en un cromosoma, y
aplicar los métodos de la evolución: selección y reproducción
sexual con intercambio de información y mutaciones que generen
diversidad.

4.1 Codificación de las Variables
Los cromosomas de alguna manera deberán contener información
acerca de la solución que representa. La codificación se puede
realizar de varias formas. La más utilizada es mediante una cadena
de números binarios (1s o 0s). Pero también se puede realizar la
codificación mediante números enteros o incluso cadenas de
palabras.
La elección de la codificación dependerá también del problema a
resolver pues puede darse la situación en la que la resolución de
un caso sea más óptimo el uso de una codificación basada en
números reales mientras que esa codificación complique la
solución en otro caso. Así pues hay que estudiar la codificación
más óptima según el caso que se esté estudiando.

4.1.1 Codificación Binaria
Es la codificación más extendida debido a que los primeros
algoritmos genéticos utilizaron este tipo de codificación. En este
caso, cada cromosoma es una cadena de bits (0 o 1). A su favor
tiene que puede abarcar muchos cromosomas incluso con un
número reducido de genes. Sin embargo por otro lado esta opción
no es la idónea para muchos problemas y en algunas ocasiones es
necesario realizar correcciones después de la reproducción y/o
mutación.
Este tipo de codificación se utiliza por ejemplo en el problema de
la mochila. En este problema tenemos una mochila con una cierta
capacidad y una serie de objetos que queremos introducir. Estos
objetos tendrán un peso y un beneficio o un valor para nosotros.
La capacidad de la mochila es inferior a la suma del peso de todos
los objetos. El objetivo es conseguir que la suma de los beneficios

o valores sea máxima y que la suma de los pesos no supere el de
la capacidad de la mochila.

4.1.2 Codificación Numérica
En este tipo de codificación se utilizan cadenas de números que
representan un número en una secuencia. Se utiliza en problemas
en los que hay que ordenar algo, donde resulta muy útil. En
algunos casos también es necesario como en el caso anterior
realizar correcciones tras relaciones o mutaciones.
Un ejemplo clásico de este tipo de codificación es el problema del
viajante de comercio. En este caso tenemos una serie de ciudades
por las que el comerciante debe pasar y las distancias entre ellas.
El objetivo es que el comerciante, partiendo de una ciudad origen,
recorra todas las ciudades y vuelva al punto de partida pero
recorriendo el menor número de kilómetros, por lo que habrá que
localizar la combinación de ciudades que minimice dicho
recorrido.

Figura 2. Esquema del problema del viajante

4.1.3 Codificación por Valor Directo
Este tipo de codificación será el utilizado en caso de resolución de
problemas en el que se requiera del uso de valores de cifrado
complicado como podría ser en el uso de números reales, cuya
codificación con números binarios sería muy complejo. En
codificación por valor directo cada cromosoma es una cadena de
valores relacionados con el problema a estudiar, pudiendo ser
desde números decimales, cadenas de caracteres o incluso una
combinación de varios de ellos. Su aplicación es muy buena en
ciertos problemas concretos. Por el contrario para la utilización de
esta codificación, normalmente es necesario desarrollar nuevas
técnicas de reproducción y mutación especificas hacia
la
resolución del problema.
Una aplicación de esta codificación se da en la resolución de
problemas para la búsqueda de pesos para las redes neuronales.
En este asunto se trata de encontrar el peso de las neuronas para
ciertas entradas y así entrenar a la red para obten