Monografías
Publicar | Monografías por Categorías | Directorio de Sitios | Software Educativo | Juegos Educativos | Cursos On-Line Gratis

 

Algoritmos genéticos parte 2 - Monografía



 
DESCARGA ESTA MONOGRAFÍA EN TU PC
Esta monografía en formato html para que puedas guardarla en tu pc e imprimirla.



Vínculo Patrocinado




Aquí te dejamos la descarga gratuita
Nota: para poder abrir archivos html solo necesitas tener instalado internet explorer u otro navegador web.




3.4 ALGORITMO GENÉTICO PROPIAMENTE DICHO


Para comenzar la competición, se generan aleatoriamente una serie de cromosomas. El algoritmo genético procede de la forma siguiente:

ALGORITMO GENÉTICO


- Evaluar la puntuación (fitness) de cada uno de los genes.
- Permitir a cada uno de los individuos reproducirse, de acuerdo con su puntuación.
- Emparejar los individuos de la nueva población, haciendo que cada uno de los pasos consiste en una actuación sobre las cadenas de bits, es decir, la aplicación de un operador a una cadena binaria. Se les denominan, por razones obvias, operadores genéticos, y hay tres principales: selección, crossover o recombinación y mutación; aparte de otros operadores genéticos no tan comunes, todos ellos se verán a continuación.
Un algoritmo genético tiene también una serie de parámetros que se tienen que fijar para cada ejecución, como los siguientes:

TAMAÑO DE LA POBLACIÓN:



debe de ser suficiente para garantizar la diversidad de las soluciones, y, además, tiene que crecer más o menos con el número de bits del cromosoma, aunque nadie ha aclarado cómo tiene que hacerlo. Por supuesto, depende también del ordenador en el que se esté ejecutando.

CONDICIÓN DE TERMINACIÓN:



lo más habitual es que la condición de terminación sea la convergencia del algoritmo genético o un número prefijado de generaciones.

3.5 EVALUACIÓN Y SELECCIÓN


Durante la evaluación, se decodifica el gen, convirtiéndose en una serie de parámetros de un problema, se halla la solución del problema a partir de esos parámetros, y se le da una puntuación a esa solución en función de lo cerca que esté de la mejor solución. A esta puntuación se le llama fitness.
Por ejemplo, supongamos que queremos hallar el máximo de la función f(x), una parábola invertida con el máximo en x=1. En este caso, el único parámetro del problema es la variable x. La optimización consiste en hallar un x tal que F(x) sea máximo. Crearemos, pues, una población de cromosomas, cada uno de los cuales contiene una codificación binaria del parámetro x. Lo haremos de la forma siguiente: cada byte, cuyo valor está comprendido entre 0 y 255, se transformará para ajustarse al intervalo   [-1,1], donde queremos hallar el máximo de la función.

2681.gif

El fitness determina siempre los cromosomas que se van a reproducir, y aquellos que se van a eliminar, pero hay varias formas de considerarlo para seleccionar la población de la siguiente generación:
Usar el orden, o rango, y hacer depender la probabilidad de permanencia o evaluación de la posición en el orden.
- Aplicar una operación al fitness para escalarlo; como por ejemplo el escalado sigma. En este esquema el fitness se escala
- En algunos casos, el fitness no es una sola cantidad, sino diversos números, que tienen diferente consideración. Basta con que tal fitness forme un orden parcial, es decir, que se puedan comparar dos individuos y decir cuál de ellos es mejor. Esto suele suceder cuando se necesitan optimizar varios objetivos.
Una vez evaluado el fitness, se tiene que crear la nueva población teniendo en cuenta que los buenos rasgos de los mejores se transmitan a ésta. Para ello, hay que seleccionar a una serie de individuos encargados de tan ardua tarea. Y esta selección, y la consiguiente reproducción, se puede hacer de dos formas principales:


BASADO EN EL RANGO:


En este esquema se mantiene un porcentaje de la población, generalmente la mayoría, para la siguiente generación. Se coloca toda la población por orden de fitness, y los M menos dignos son eliminados y sustituidos por la descendencia de alguno de los M mejores con algún otro individuo de la población.
A este esquema se le pueden aplicar otros criterios; por ejemplo, se crea la descendencia de uno de los paladines/amazonas, y esta sustituye al más parecido entre los perdedores. Esto se denomina crowding, y fue introducido por DeJong.
Una variante de este es el muestreado estocástico universal, que trata de evitar que los individuos con más fitness copen la población dando más posibilidades al resto de la población; de esta forma, la distribución estadística de descendientes en la nueva población es más parecida a la real.

RUEDA DE RULETA:



se crea un conjunto genético formado por cromosomas de la generación actual, en una cantidad proporcional a su fitness. Si la proporción hace que un individuo domine la población, se le aplica alguna operación de escalado. Dentro de este conjunto, se cogen parejas aleatorias de cromosomas y se emparejan, sin importar incluso que sean del mismo progenitor (para eso están otros operadores, como la mutación). Hay otras variantes: por ejemplo, en la nueva generación se puede incluir el mejor representante de la generación actual. En este caso, se denomina método elitista.

SELECCIÓN DE TORNEO:


se escogen aleatoriamente un número T de individuos de la población, y el que tiene puntuación mayor se reproduce, sustituyendo su descendencia al que tiene menor puntuación.


3.6 CROSSOVER


Consiste en el intercambio de material genético entre dos cromosomas (a veces más, como el operador orgía propuesto por Eiben et al.). El crossover es el principal operador genético, hasta el punto que se puede decir que no es un algoritmo genético si no tiene crossover, y, sin embargo, puede serlo perfectamente sin mutación, según descubrió Holland. El teorema de los esquemas confía en él para hallar la mejor solución a un problema, combinando soluciones parciales.
Para aplicar el crossover, entrecruzamiento o recombinación, se escogen aleatoriamente dos miembros de la población. No pasa nada si se emparejan dos descendiente de los mismos padres; ello garantiza la perpetuación de un individuo con buena puntuación (y, además, algo parecido ocurre en la realidad; es una práctica utilizada, por ejemplo, en la cría de ganado, llamada inbreeding, y destinada a potenciar ciertas características frente a otras). Sin embargo, si esto sucede demasiado a menudo, puede crear problemas: toda la población puede aparecer dominada por los descendientes de algún gen, que, además, puede tener caracteres no deseados. Esto se suele denominar en otros métodos de optimización atranque en un mínimo local, y es uno de los principales problemas con los que se enfrentan los que aplican algoritmos genéticos.
En cuanto al teorema de los esquemas, se basa en la noción de bloques de construcción. Una buena solución a un problema está constituida por unos buenos bloques, igual que una buena máquina está hecha por buenas piezas. El crossover es el encargado de mezclar bloques buenos que se encuentren en los diversos progenitores, y que serán los que den a los mismos una buena puntuación. La presión selectiva se encarga de que sólo los buenos bloques se perpetúen, y poco a poco vayan formando una buena solución. El teorema de los esquemas viene a decir que la cantidad de buenos bloques se va incrementando con el tiempo de ejecución de un algoritmo genético, y es el resultado teórico más importante en algoritmos genéticos.
El intercambio genético se puede llevar a cabo de muchas formas, pero hay dos grupos principales

CROSSOVER N-PUNTOS:



Los dos cromosomas se cortan por n puntos, y el material genético situado entre ellos se intercambia. Lo más habitual es un crossover de un punto o de dos puntos.

Padre

2682.gif

Madre

2683.gif

Hijo

2684.gif

CROSSOVER UNIFORME:


Se genera un patrón aleatorio de 1s y 0s, y se intercambian los bits de los dos cromosomas que coincidan donde hay un 1 en el patrón. O bien se genera un número aleatorio para cada bit, y si supera una determinada probabilidad se intercambia ese bit entre los dos cromosomas.

Padre

2785.gif
Madre

2786.gif

Hijo

2787.gif

CROSSOVER ESPECIALIZADOS:


En algunos problemas, aplicar aleatoriamente el crossover da lugar a cromosomas que codifican soluciones inválidas; en este caso hay que aplicar el crossover de forma que genere siempre soluciones válidas. Un ejemplo de estos son los operadores de crossover usados en el problema del viajante.

3.7 MUTACIÓN


En la Evolución, una mutación es un suceso bastante poco común (sucede aproximadamente una de cada mil replicaciones), como ya se ha visto anteriormente. En la mayoría de los casos las mutaciones son letales, pero en promedio, contribuyen a la diversidad genética de la especie. En un algoritmo genético tendrán el mismo papel, y la misma frecuencia (es decir, muy baja).
Una vez establecida la frecuencia de mutación, por ejemplo, uno por mil, se examina cada bit de cada cadena cuando se vaya a crear la nueva criatura a partir de sus padres (normalmente se hace de forma simultánea al crossover). Si un número generado aleatoriamente está por debajo de esa probabilidad, se cambiará el bit (es decir, de 0 a 1 o de 1 a 0). Si no, se dejará como está. Dependiendo del número de individuos que haya y del número de bits por individuo, puede resultar que las mutaciones sean extremadamente raras en una sola generación.
No hace falta decir que no conviene abusar de la mutación. Es cierto que es un mecanismo generador de diversidad, y, por tanto, la solución cuando un algoritmo genético está estancado, pero también es cierto que reduce el algoritmo genético a una búsqueda aleatoria. Siempre es más conveniente usar otros mecanismos de generación de diversidad, como aumentar el tamaño de la población, o garantizar la aleatoriedad de la población inicial.
Este operador, junto con la anterior y el método de selección de ruleta, constituyen un algoritmo genético simple, sga, introducido por Goldberg en su libro.

3.8 OTROS OPERADORES



No se usan en todos los problemas, sino sólo en algunos, y en principio su variedad es infinita. Generalmente son operadores que exploran el espacio de soluciones de una forma más ordenada, y que actúan más en las últimas fases de la búsqueda, en la cuál se pasa de soluciones “casi buenas” a “buenas” soluciones.

3.8.1 CROMOSOMAS DE LONGITUD VARIABLE



Hasta ahora se han descrito cromosomas de longitud fija, donde se conoce de antemano el número de parámetros de un problema. Pero hay problemas en los que esto no sucede. Por ejemplo, en un problema de clasificación, donde dado un vector de entrada, queremos agruparlo en una serie de clases, podemos no saber siquiera cuántas clases hay. O en diseño de redes neuronales, puede que no se sepa (de hecho, nunca se sabe) cuántas neuronas se van a necesitar. Por ejemplo, en un perceptrón hay reglas que dicen cuantas neuronas se deben de utilizar en la capa oculta; pero en un problema determinado puede que no haya ninguna regla heurística aplicable; tendremos que utilizar los algoritmos genéticos para hallar el número óptimo de neuronas.

En estos casos, necesitamos dos operadores más: añadir y eliminar. Estos operadores se utilizan para añadir un gen, o eliminar un gen del cromosoma. La forma más habitual de añadir un locus es duplicar uno ya existente, el cuál sufre mutación y se añade al lado del anterior. En este caso, los operadores del algoritmo genético simple (selección, mutación, crossover) funcionarán de la forma habitual, salvo, claro está, que sólo se hará crossover en la zona del cromosoma de menor longitud.

3.8.2 OPERADORES DE NICHO (ECOLÓGICO)


Otros operadores importantes son los operadores de nicho. Estos operadores están encaminados a mantener la diversidad genética de la población, de forma que cromosomas similares sustituyan sólo a cromosomas similares, y son especialmente útiles en problemas con muchas soluciones; un algoritmo genético con estos operadores es capaz de hallar todos los máximos, dedicándose cada especie a un máximo. Más que operadores genéticos, son formas de enfocar la selección y la evaluación de la población.
Uno de las formas de llevar esto a cabo ya ha sido nombrada, la introducción del crowding (apiñamiento). Otra forma es introducir una función de compartición o sharing, que indica cuán similar es un cromosoma al resto de la población. La puntuación de cada individuo se dividirá por esta función de compartición, de forma que se facilita la diversidad genética y la aparición de individuos diferentes.
También se pueden restringir los emparejamientos, por ejemplo, a aquellos cromosomas que sean similares. Para evitar las malas consecuencias del inbreeding (destinado a potenciar ciertas características frente a otras) que suele aparecer en poblaciones pequeñas, estos periodos se intercalan con otros periodos en los cuáles el emparejamiento es libre.


3.8.3 OPERADORES ESPECIALIZADOS


En una serie de problemas hay que restringir las nuevas soluciones generadas por los operadores genéticos, pues no todas las soluciones generadas van a ser válidas, sobre todo en los problemas con restricciones. Por ello, se aplican operadores que mantengan la estructura del problema. Otros operadores son simplemente generadores de diversidad, pero la generan de una forma determinada:

ZAP:


En vez de cambiar un solo bit de un cromosoma, cambia un gen completo de un cromosoma.

CREEP:


Este operador aumenta o disminuye en 1 el valor de un gen; sirve para cambiar suavemente y de forma controlada los valores de los genes.

TRANSPOSICIÓN:


Similar al crossover y a la recombinación genética, pero dentro de un solo cromosoma; dos genes intercambian sus valores, sin afectar al resto del cromosoma. Similar a este es el operador de eliminación-reinserción, en el que un gen cambia de posición con respecto a los demás.

3.8.4 APLICANDO OPERADORES GENÉTICOS


En toda ejecución de un algoritmo genético hay que decidir con qué frecuencia se va a aplicar cada uno de los algoritmos genéticos; en algunos casos, como en la mutación o el crossover uniforme, se debe de añadir algún parámetro adicional, que indique con qué frecuencia se va a aplicar dentro de cada gen del cromosoma. La frecuencia de aplicación de cada operador estará en función del problema; teniendo en cuenta los efectos de cada operador, tendrá que aplicarse con cierta frecuencia o no. Generalmente, la mutación y otros operadores que generen diversidad se suele aplicar con poca frecuencia; la recombinación se suele aplicar con frecuencia alta.
En general, la frecuencia de los operadores no varía durante la ejecución del algoritmo, pero hay que tener en cuenta que cada operador es más efectivo en un momento de la ejecución. Por ejemplo, al principio, en la fase denominada de exploración, los más eficaces son la mutación y la recombinación; posteriormente, cuando la población ha convergido en parte, la recombinación no es útil, pues se está trabajando con individuos bastante similares, y es poca la información que se intercambia. Sin embargo, si se produce un estancamiento, la mutación tampoco es útil, pues está reduciendo el algoritmo genético a una búsqueda aleatoria; y hay que aplicar otros operadores. En todo caso, se pueden usar operadores especializados.
Por ejemplo, en el algoritmo genético para jugar al MasterMind, se usan varios operadores genéticos: transposición, mutación y entrecruzamiento. Sin embargo, la mutación y el crossover dejan de ser efectivos en el momento que la combinación que se ha jugado tiene los colores correctos, y en cualquier caso la tasa de mutación tendrá que ser mayor cuantos menos colores haya averiguados; por eso las tasas varían durante la ejecución, convirtiéndose eventualmente en 0.

EJEMPLO SIMPLE DE ALGORITMOS GENÉTICO:


Supongamos que hemos de calcular el máximo de una función f(x) en un intervalo [a,b]. Pues bien, sencillo, derivamos e igualamos a cero, ¿no?. Pues no. Se me olvidaba decir que no conocemos f(x), aunque sí podemos calcular o estimar su valor en cualquier punto.
He aquí los pasos a seguir:
- Estimamos con qué resolución queremos trabajar. Es decir, elegimos el número de puntos que vamos a examinar dentro de ese intervalo. Si, por ejemplo, el intervalo es el [0,100] y ponemos una resolución de 0.5, pues tendremos 200 puntos en el intervalo.
- Generamos una población inicial de n individuos; que serán -no podía ser menos- n números (elegidos al azar). Es decir, ya tenemos x1, x2, … ,xn. Todos ellos, entre a y b, los límites de nuestro intervalo.
- Ahora hemos de dar mayor capacidad de reproducción a los mejor dotados. Si estamos buscando el máximo, pues el mejor dotado será aquel cuyo valor de f(xi) sea mayor. Hasta aquí, todo de lo más normal.
Pues de los n individuos que tenemos, vamos a crear una población intermedia, que será los que se van a recombinar. Calculamos la frecuencia de cada uno de los n genotipos en la primera población .
Bueno, tenemos que calcular esas probabilidades: p(xi)=f(xi)/suma_total. Les he llamado probabilidades, aunque en realidad son frecuencias, por aquello de no confundir la notación. Siguiendo con esta tónica, definimos P(xi) como la función de distribución: P(xj) es la suma, desde cero hasta j, de los p(xi).
Creo que es necesario un breve ejemplo para aclarar las cosas (aunque también está el mail). Supongamos que nuestro n sea igual a 4, y que, por ejemplo, tenemos:
f(x0)=10
f(x1)=40
f(x2)=30
f(x3)=20

Por lo tanto,

p(x0)=0.1
p(x1)=0.4
p(x2)=0.3
p(x3)=0.2
y también

P(x0)=0.1
P(x1)=0.5
P(x2)=0.8
P(x3)=1.0
Esta claro que los p(xi) suman 1. A continuación generamos n números aleatorios entre 0 y 1. Cada uno de esos números -por ejemplo, t- estará relacionado con un individuo de nuestra generación intermedia; de la siguiente forma:
si t está entre P(xi) y P(xi+1) escogemos xi+1)
Seguimos con el ejemplo: Si nuestros cuatro números aleatorios son 0.359, 0.188, 0.654 y 0.399, entonces nuestra generación intermedia será:
2788.gif

Como se ve, está claro que, pese al azar el individuo mejor dotado es el más favorecido.
- El siguiente paso es la recombinación. Se puede hacer de la forma que nos parezca más adecuada. En primer lugar hay que buscar las parejas. Se trata de obtener una nueva generación como mezcla de esta con la que estamos trabajando. Una vez que tenemos las parejas, hemos de hacer la recombinación. Una alternativa: media aritmética;(1) otra: media geométrica(2). Otra, la más usada: cortar los dos números “papás” por un lugar al azar (3) y conseguir los “hijos” intercambiando partes. Por si este último punto no ha quedado demasiado claro, digamos que, si los individuos son 456 y 123, elegimos al azar un número entre 1 y 2 (ya que hay tres cifras). Si, por ejemplo, nos sale el 1, pues un posible hijo podría ser el 4-23 y otro 1-56. Aunque hay que decir que lo más habitual es trabajar en base 2 (al menos, los números serán más largos).
- En este momento ya tenemos una nueva generación. Generalmente, mejor dotada que la inicial. Lo que se hace ahora es volver al tercer punto (cálculo de una población intermedia). Por supuesto, el algoritmo se para cuando queramos. Por ejemplo, cuando llevemos un número de iteraciones determinado, o cuando la población no mejore demasiado.
- Una variante posible es permitir la existencia de mutaciones (por ejemplo, introducir cada cierto número de generaciones alguna variación en una cifra en busca de mejores soluciones. Esto es interesante debido a que, por ejemplo, si estamos dando vueltas en torno a un máximo local, la variación introducida podría llevarnos hacia un genotipo mejor dotado.
- Otra variante es la elitista, consistente en que los mejores genotipos no se recombinen, sino que pasen directamente -tal cual- a la siguiente generación.


EJEMPLO COMPLETO DE UN ALGORITMO GENÉTICO


La finalidad de este ejemplo es construir un planeador de rutas, capaz de encontrar la ruta más corta a la salida más cercana, para cada una de las “n” personas que se encuentran en un cuarto.

Este cuarto contiene obstáculos estáticos y varias salidas. La ruta encontrada para la persona “x” no debe llevarla a chocar con algún obstáculo ni con otra persona que a su vez se está moviendo en el cuarto.
2789.gif

La interface del programa tiene la siguiente simbología:
Cubos de colores y mas pequeños :        Personas
Cubos azules:                                        Obstáculos
Cuadros rojos:                                        Salidas

Los pasos de un algoritmo genético son los siguientes:

1.- INICIALIZACIÓN:



En este primer paso se crea aleatoriamente un conjunto de individuos (que están sobre el espacio S).

Inicialmente tenemos 20 individuos. Los individuos se representan como un vector, cuyos valores van del 0-7, y que significan lo siguiente:

0    -> Camina un paso a la izquierda
1    -> Camina un paso a la derecha
2    -> Camina un paso adelante
3    -> Camina un paso atrás
-> Camina en diagonal izquierda hacia arriba
-> Camina en diagonal izquierda hacia abajo
-> Camina en diagonal derecha hacia abajo
-> Camina en diagonal derecha hacia arriba
8    -> Quédate en tu lugar

Éstos serían dos ejemplos de individuos:

1)  2 - 1 - 2 - 0 - 7 - 4 - 3 - 6 - 3 - 3 - 3 - 0 - 5 - 0 - 3 - 3 - 3 - 1 - 1 - 1 - 3 - 5 - 1 - 4 - 7 - 4 - 3 - 1 - 6 - 1 - 2 -

2)  0 - 4 - 1 - 7 - 5 - 3 - 1 - 1 - 3 - 3 - 3 - 7 - 5 - 1 - 2 - 5 - 6 - 4 -

Después el algoritmo itera en los siguientes pasos hasta que se cumpla alguna condición.
En este caso dicha condición es que evolucionen 6 generaciones.

2.- EVALUACIÓN:



La Función F es computada para cada individuo, ordenando la población del mejor individuo al peor. En el ejemplo, la función a optimizar es la longitud de los individuos. Es decir deseamos obtener un individuo con longitud mínima. Por ello, se ordenan en base a su longitud y en orden ascendente.

3.- SELECCIÓN:



Se selecciona con la regla de selección - explicada a continuación - una pareja de individuos. La regla utilizada es roulette wheel selection, que elige en base a probabilidad proporcional a su calificación:

1.-    Se genera un número aleatorio r E [0,1].
2.-    Se multiplica r por la suma de las calificaciones de la población (S), obteniéndose c = rS.
3.-    Se establece la calificación acumulada (Ca) y el índice en cero: Ca = 0, i=0
4.-    A la calificación acumulada se le suma la calificación del i-ésimo individuo:
Ca = Ca + calif(i)
5.-    Si Ca > c entonces el i-esimo individuo es seleccionado.
6.-    Si no, entonces se incrementa i y se regresa al paso 4.

Esta selección es con reemplazo, es decir, un mismo individuo puede ser seleccionado varias veces. Así que cada vez que se selecciona un individuo no se quita de la población de la que se está seleccionando, permanece en ella para que pueda ser elegido nuevamente.

4.- REPRODUCCIÓN:



Se generan nuevos individuos a partir de la pareja seleccionada en el paso 3.

El algoritmo de reproducción que se ha utilizado es el siguiente:
- Una vez seleccionados 2 individuos p1 y p2 (llamados padres) se procede a cruzarlos.
- Generamos un número aleatorio entre 1 y  (longitud de p1)/2, llamado n1.
- Generamos un número aleatorio entre (longitud de p2)/2 y longitud de p2, llamado n2.
- Calculamos la posición en la que se encuentra p1 al dar n1 pasos, y la llamamos pasosp1.
- Calculamos la posición en la que se encuentra p2 al dar (longitud de p2)/2 pasos, y la llamamos pasosp2.
- Generamos un camino aleatorio de pasosp1 a pasosp2, llamado camino_intermedio. Este camino aleatorio verifica que no choque con ningún obstáculo predefinido (estático).
- Copiamos los primeros n1 pasos de p1 en el nuevo individuo ni1.
- Copiamos camino_intermedio a ni1.
==>    Copiamos los pasos de p2 de n2 a longitud p2.
Y de la misma manera generamos el segundo nuevo individuo, sólo que ahora tomamos el inicio de p2 y el  final de p1.
Esta cruza nos garantiza que obtengamos individuos válidos, es decir que nos van a dar un camino que inicie en la posición original de la persona y finalice en alguna salida. Y que además no choque con ningún obstáculo.

Después de repetir 6 veces los pasos del 2 al 4, se obtiene una población final.

El algoritmo además de estos pasos, incorpora un quinto paso al que llamamos entrenamiento.

5.- ENTRENAMIENTO:



Repite los pasos del 1 al 4 n veces. El primer algoritmo genético  coloca en la población inicial del segundo algoritmo genético, a su mejor individuo (lo coloca 2 veces, para asegurarse de que va a preservarse en las siguientes generaciones), el segundo hace lo mismo con el tercero, y así sucesivamente hasta n.
Los algoritmos genéticos tienen una característica peculiar, que es que cada  vez que se ejecuta nos da (muy probablemente) respuestas diferentes, y esto es porque la población inicial se genera aleatoriamente.

Estos entrenamientos nos permiten tomar el mejor individuo evolucionado del algoritmo genético anterior, y a su vez generar nuevos individuos. Esto es conocido también como elitismo. Con esto generamos n veces poblaciones aleatorias y (n-1) veces la población inicial al menos tiene un buen individuo. Este nuevo individuo al cruzarlo con algún otro buen individuo generado aleatoriamente puede ser que nos dé uno aún mejor.

Parámetros que deben ser especificados en el programa:

Nº de generaciones: cantidad de veces que se produce una nueva generación de individuos, utilizando las reglas anteriormente explicadas. Por lógica, cuantas más generaciones produzcamos, obtendremos mejores individuos.

Nº de individuos por generación: en este ejemplo, la cantidad de individuos de una generación a otra es constante, no varía.

Nº de entrenamientos: cantidad de veces que se lleva a cabo un entrenamiento entre diferentes generaciones de individuos.

CONCLUSIÓN DEL  TRABAJO:


Como hemos podido observar, la principal ventaja de los algoritmos genéticos radica en su sencillez. Se requiere poca información sobre el espacio de búsqueda ya que se trabaja sobre un conjunto de soluciones o parámetros codificados (hipótesis o individuos). Se busca una solución por aproximación de la población, en lugar de una aproximación punto a punto. Con un control adecuado podemos mejorar la aptitud promedio de la población, obteniendo nuevos y mejores individuos y, por lo tanto, mejores soluciones.
Se consigue un equilibrio entre la eficacia y la eficiencia. Este equilibrio es configurable mediante los parámetros y operaciones usados en el algoritmo. Así, por ejemplo, bajando el valor del umbral conseguiremos una rápida solución a cambio de perder en “calidad”. Si aumentamos dicho valor, tendremos una mejor solución a cambio de un mayor tiempo consumido en la búsqueda. Es decir, obtenemos una buena relación entre la calidad de la solución y el costo.
Quizás el punto más delicado de todo se encuentra en la definición de la función de evaluación, y de su eficacia depende el obtener buenos resultados. El resto del proceso es siempre el mismo para todos los casos.
La programación mediante algoritmos genéticos suponen un nuevo enfoque que permite abarcar todas aquellas áreas de aplicación donde no sepamos como resolver un problema:

APLICACIONES DE BÚSQUEDA Y OPTIMIZACIÓN :



Desde aplicaciones evidentes, como la biología o la medicina, hasta otros campos como la industria (clasificación de piezas en cadenas de montaje). Los algoritmos genéticos poseen un importante papel en este ámbito.

APRENDIZAJE AUTOMÁTICO:


La capacidad que poseen para favorecer a los individuos que  se acercan al objetivo, a costa de los que no lo hacen, consigue una nueva generación con mejores reglas y, por lo tanto el sistema será capaz de ir aprendiendo a conseguir mejores resultados. Es aquí donde encuentran un estupendo marco de trabajo los GA.


DIRECCIONES  DE  CONSULTA:


- http://geneura.ugr.es/~jmerelo/ie/ags.htm
- http://www.geocities.com/waguilar_2000/ALGORITMOS_GENETICOS
- http://kal-el.ugr.es/mastermind
- http://www.cinefantastico.com/nexus7/ia/ageneticos.htm
- http://www.fortunecity.com/underworld/fifa/613/xxx.html
- http://www.geocities.com/krousky/Espanol/AlgEv001.htm
- http://orchid.lsi.upc.es/~iea/transpas/9_geneticos/sld001.htm
- http://kal-el.ugr.es/~jmerelo

Autor:

Cols





Creative Commons License
Estos contenidos son Copyleft bajo una Licencia de Creative Commons.
Pueden ser distribuidos o reproducidos, mencionando su autor.
Siempre que no sea para un uso económico o comercial.
No se pueden alterar o transformar, para generar unos nuevos.

 
TodoMonografías.com © 2006 - Términos y Condiciones - Esta obra está bajo una licencia de Creative Commons. Creative Commons License