Algoritmo Genetico

Republica Bolivariana de Venezuela

Ministerio del poder Popular Para La Educación Superior

Universidad Bicentenaria de Aragua

Sede San Fernando

Algoritmo Genético

Profesor: Participante:

Lamuño, Freddys Escobar, Yuritza

Biruaca, Julio de 2012

Bases Fundamentales de los Algoritmos Genéticos

Bases Fundamentales de 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: (1) abstraer y explicar rigurosamente el proceso adaptativo de los sistemas naturales, y (2) 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.

El tema central en las investigaciones sobre algoritmos genéticos,, ha sido la robustez, el equilibrio necesario entre la eficiencia y la eficacia suficiente para la supervivencia en entornos diferentes. Las implicaciones que tiene la robustez en los sistemas artificiales son variadas. Si se puede conseguir que un sistema artificial sea más robusto, se podrán reducir, e incluso eliminar, los costes por rediseños. Y si se es capaz de lograr niveles altos de adaptación, los sistemas podrán desarrollar sus funciones mejor y durante más tiempo. Sin embargo, ante la robustez, eficiencia y flexibilidad de los sistemas biológicos, sólo podemos sentarnos a contemplar, y maravillarnos; mentiríamos si dijéramos que somos capaces de igualarlos.

Pero, ¿por qué basarse en nuestros conocimientos sobre la evolución biológica? La respuesta la encontramos si observamos una constante que se repite en muchos problemas:

La búsqueda de soluciones entre una cantidad ingente de candidatos. Tómese, por ejemplo, el cálculo de un conjunto de reglas (ecuaciones) capaz de regir las subidas y bajadas de un mercado financiero. El modo de llegar a la mejor solución en estas situaciones, pasa por ser capaz de obtener rendimiento de un uso eficaz del paralelismo, que permita explorar diferentes posibilidades de modo simultáneo. Para ello, se precisa, tanto paralelismo computacional (contar con varios procesadores computando al mismo tiempo), como una estrategia adecuada de búsqueda.

Por otro lado, muchos problemas computacionales, precisan de un programa adaptativo, capaz de comportarse bien ante cambios en el entorno. Además, la mayoría de estos problemas tienen soluciones complejas, muy difíciles de programar a mano. Entre las técnicas que han surgido al tratar de resolver estas cuestiones, encontramos el

“conexionismo” (el estudio de programas computacionales inspirados en sistemas neuronales, de los que ya se ha hablado en otras Jornadas) , y la “computación evolutiva”. Si en la primera las reglas pasaban por umbrales neuronales, propagación de la activación, y refuerzo o no de las conexiones., en la segunda son la selección natural, con variaciones debidas a cruces y/o mutaciones, y su objetivo es el diseño de soluciones de alta calidad para problemas de elevado grado de complejidad, y la habilidad de adaptar esas soluciones de cara a cambios en el entorno.

La evolución, tal y como la conocemos, es básicamente un método de búsqueda

entre un número enorme de posibles “soluciones”. En biología las posibilidades están formadas por un conjunto de secuencias genéticas posibles, y las soluciones deseadas, por organismos capaces de sobrevivir y reproducirse en sus entornos. La evolución puede verse, asimismo, como un modo de “diseñar” soluciones a problemas complejos, con la capacidad de innovar. Estos son los motivos de que los mecanismos evolutivos sean una fuente de inspiración para los algoritmos de búsqueda. Por supuesto, el buen funcionamiento de un organismo biológico depende de muchos criterios, que además varían a medida que el organismo evoluciona, de modo que la evolución está “buscando” continuamente entre un conjunto cambiante de posibilidades. Por ello, podemos considerarla como un método de búsqueda masivamente paralelo, ya que evalúa y cambia millones de especies en paralelo. Para terminar, las reglas de la evolución, aunque de alto nivel, son simples: las especies evolucionan mediante variaciones aleatorias (vía mutaciones, recombinaciones, etc.) seguidas por la selección natural, donde el mejor tiende a sobrevivir y reproducirse, propagando así su material genético a posteriores generaciones.

Algunas

...