PDF de programación - Resumen Algoritmos Genéticos

Resumen Histórico



La primera mención del término Algoritmos Genéticos, y la primera publicación
sobre una aplicación del mismo, se deben a Bargley en 1967, que diseño un Algoritmo
Genético para buscar parámetros que evaluaran juegos. Pero es otro científico el
considerado como creador de los Algoritmos Genéticos: John Holland, que los desarrollo
junto a sus alumnos y colegas durante 1960 y 1970. El propósito de Holland era el de
estudiar de un modo formal, el fenómeno de la adaptación tal y como ocurre en la
naturaleza y desarrollar vías de extrapolar esos mecanismos de adaptación natural a los
sistemas computacionales.


Fue a principios de los 60, en la Universidad de Michigan, donde Holland impartía
un curso titulado Teoría de Sistemas Adaptativos y con la participación de sus alumnos fue
donde se crearon las ideas que mas tarde se convertirían en los algoritmos genéticos.


El algoritmo genético es una técnica de búsqueda basada en la teoría de la evolución
de Darwin, de acuerdo a la cual los individuos mas aptos de una población son los que
sobreviven, al adaptarse mas fácilmente a los cambios que se producen en su entrono.


Los algoritmos genéticos forman parte de lo que hoy se conoce como la

Computación Evolutiva.


Fue en las décadas de 1950 y 1960 cuando varios científicos, de manera
independiente, comenzaron a estudiar los sistemas evolutivos, guiados por la intuición de
que 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 de la
genética natural.

Conceptos y Definiciones

Algoritmos Geneticos.-Son métodos sistemáticos para la resolución de problemas de
búsqueda y optimización

Operador Genetico.- Consiste en una serie de pasos estructurados que se aplican a los
cromosomas y forman resultados concretos , al igual que las operaciones matemáticas y
lógicas


? Crossover (apareamiento) – Este operado trata de sacar ventaja de la reproducción

de dos cromosomas

por otro.

? Mutation (mutación) - La mutación consiste en el cambio de valor de uno a mas bits

? Clonación Es la duplicación de un cromosoma
?

Inversión = inverso de clonación – Consisite en el cambio de valor de un bit o de
todo el cromosoma

? Reverción - Cambia el cromosoma por sí mismo ordenado de atrás para adelante

? Anulación o Pavlov – Anula algunos bits del cromosoma.


DESCRIPCION.

Pasos de un Algoritmo Genético.

? Generar una población de n genes aleatorios.
? Evaluar a todos los individuos según la función de aptitud.
? Generar nuevos individuos utilizando operadores genéticos.
? Seleccionar a los individuos que formarán la próxima generación.
? Volver al punto 2 hasta que se encuentre un valor predefinido o se hallan cumplido una

cantidad predeterminada de iteraciones.



Diagrama de flujo a seguir para la optimización de ideas, procesos, etc.

CARACTERISTICAS.

Algunas de las características de los algoritmos genéticos son:



? Son algoritmos estocásticos. Dos ejecuciones distintas pueden dar dos soluciones
distintas. Esto es útil por el hecho de que hay gran cantidad de soluciones válidas,
por lo que es interesante que distintas ejecuciones nos puedan dar resultados
distintos.

? Son algoritmos de búsqueda múltiple, luego dan varias soluciones. Aunque
habitualmente las energías de los individuos de la población final son similares, los
individuos suelen ser distintos entre sí. Con el modelo de paralelización empleado -
genético multipoblacional- la probabilidad de obtener muchas soluciones distintas
es más alta todavía. Por ello, nos podemos quedar con la solución que más nos
convenga según la naturaleza del problema. Por lo comentado en el punto anterior,
esto supone una ventaja en nuestro problema.

? Son los algoritmos que hacen una barrida mayor al subespacio de posibles
soluciones válidas, y con diferencia. De hecho, se considera que, de todos los
algoritmos de optimización estocásticos, los algoritmos genéticos son de los más
exploratorios disponibles.

? A diferencia de los otros algoritmos comentados, cuya convergencia y resultado
final son fuertemente dependientes de la posición inicial, en los algoritmos
genéticos -salvo poblaciones iniciales realmente degeneradas, en los que el operador
de mutación va a tener mucho trabajo- la convergencia del algoritmo es poco
sensible a la población inicial si esta se escoge de forma aleatoria y es lo
suficientemente grande.

? Por su grado de penetración casi nulo, la curva de convergencia asociada al
algoritmo presenta una convergencia excepcionalmente rápida al principio, que casi
enseguida se bloquea. Esto de debe a que el algoritmo genético es excelente
descartando subespacios realmente malos. Cada cierto tiempo, la población vuelve
dar el salto evolutivo, y se produce un incremento en la velocidad de convergencia
excepcional. La razón de esto es que algunas veces aparece una mutación altamente
beneficiosa, o un
individuo excepcional, que propaga algún conjunto de
cromosomas excepcional al resto de la población.

? La optimización es función de la representación de los datos. Este es el concepto
clave dentro de los algoritmos genéticos, ya que una buena codificación puede hacer
la programación y la resolución muy sencillas, mientras que una codificación errada
nos va a obligar a estudiar que el nuevo genoma cumple las restricciones del
problema, y en muchos problemas tendremos que abortar los que no cumplan las
restricciones, por ser estas demasiado complejas. Además, la velocidad de
convergencia va a estar fuertemente influenciada por la representación.

? Es una búsqueda paramétricamente robusta. Eso quiere decir que hemos de escoger
realmente mal los parámetros del algoritmo para que no converja. Con tasas
razonables, va a converger -mejor o peor- en una solución razonablemente buena si
la representación es la adecuada. Esto es muy importante por la naturaleza de
nuestra búsqueda. Nosotros no podemos hacer comparativas buscando los mejores
números mágicos para que nuestro algoritmo converja, ya que el objetivo de nuestro
grupo de investigación es llegar a la solución de un problema que ya de por sí es
muy complejo.

? Por último, los algoritmos genéticos son intrínsecamente paralelos. Esto significa
que, independientemente de que lo hayamos implementado de forma paralela o no,
buscan en distintos puntos del espacio de soluciones de forma paralela. Ese
paralelismo intrínseco permite que sean fácilmente paralelizables, es decir, que sea

fácil modificar el código para que se ejecute simultáneamente en varios
procesadores. Esto nos ha ayudado a desarrollar rápidamente una solución paralela.


Ventajas de los Algoritmos Genéticos

Lo más sorprendente y útil de los AG’s es que no es necesario disponer de un
conocimiento profundo del problema a resolver, sino que se parte de estructuras simples
que interactúan, dejando que sea la evolución quien haga el trabajo. Un AG es un método
de programación opuesto al habitual: en vez de descomponer un problema en sub-
problemas, creamos los sub-problemas más sencillos que podamos imaginar y dejamos que
se combinen entre sí.
Únicamente basta con ser capaces de identificar cualitativamente en qué casos las
cadenas se acercan o se alejan de la solución buscada, para que el sistema se perfeccione
automáticamente.
Otra gran ventaja de los AG’s es que son adaptativos: son capaces de solucionar
problemas que cambian en el tiempo.
La gran sencillez de los AG’s los hace muy atractivos para los programadores, pero
existen casos en los que puede ser difícil, imposible o poco práctico aplicarlos. Se podría
hablar del problema de la variedad, el problema de la reproducción y el problema de la
selección, para los que se van a proponer algunas soluciones.

Aplicaciones de los algoritmos genéticos.


Las tecnicas de la inteligencia computacional han sido empleadas con éxito en el
desarrollo de sistemas inteligentes de prevensión, soporte a desición, control,
optimización, modelado, clasificación y reconocimiento de patrones en general
aplicados en diversos sectores: Energía, Industrial, Económico, Financiero,
Comercial, medio ambiente entre otros.



Así también los algoritmos genéticos han sido aplicados con éxito en muchos
problemas, actuando como un proceso computacional que emula la evolución genética y
opera sobre una población de individuos que representan las soluciones potenciales de
determinado problema.


“Los algoritmos son herramientas para optimizar casi cualquier problema, ya que
estos pueden trabajar con base en la descripción del medio ambiente, la cual permite
resolver muchos problemas de optimización”, Dr. Kuri.


Una de las areas de aplicación es en el aprendizaje automático, o como es conocido
en IA (Inteligencia Artificial) sistemas expertos, que son programas para la resolución
problemas a los que se les cuestiona sobre lo que hay que hacer y estos dan respuestas,
existen estos tipos de sistemas en areas como a medicina, abogacía, etc. la mayor parte no
inc