ventajas y desventajas de los AG

Reseña Histórica

Los algoritmos genéticos (AG), fueron inventados en 1975 por John Holland, de la Universidad de Michigan. Los AG son, simplificando, algoritmos de optimización, es decir, tratan de encontrar la mejor solución a un problema dado entre un conjunto de soluciones posibles. Los mecanismos de los que se valen los AG para llevar a cabo esa búsqueda pueden verse como una metáfora de los procesos de evolución biológica. 

John Holland desde pequeño, se preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos. No sabía la respuesta, pero tenía una cierta idea de como hallarla: tratando de hacer pequeños modelos de la naturaleza, que tuvieran alguna de sus características, y ver cómo funcionaban, para luego extrapolar sus conclusiones a la totalidad.

Fue a principios de los 60, en la Universidad de Michigan en Ann Arbor, donde, dentro del grupo Logic of Computers, sus ideas comenzaron a desarrollarse y a dar frutos. Y fue, además, leyendo un libro escrito por un biólogo evolucionista, R. A. Fisher, titulado La teoría genética de la selección natural, como comenzó a descubrir los medios de llevar a cabo sus propósitos de comprensión de la naturaleza. De ese libro aprendió que la evolución era una forma de adaptación más potente que el simple aprendizaje, y tomó la decisión de aplicar estas ideas para desarrollar programas bien adaptados para un fin determinado.

En esa universidad, Holland impartía un curso titulado Teoría de sistemas adaptativos. Dentro de este curso, y con una participación activa por parte de sus estudiantes, fue donde se crearon las ideas que más tarde se convertirían en los AG. Por tanto, cuando Holland se enfrentó a los AG, los objetivos de su investigación fueron dos:

• imitar los procesos adaptativos de los sistemas naturales
• diseñar sistemas artificiales (normalmente programas) que retengan los mecanismos importantes de los sistemas naturales.

Unos 15 años más adelante, David Goldberg, actual delfín de los AG, conoció a Holland, y se convirtió en su estudiante. Goldberg era un ingeniero industrial trabajando en diseño de pipelines, y fue uno de los primeros que trató de aplicar los AG a problemas industriales. Aunque Holland trató de disuadirle, porque pensaba que el problema era excesivamente complicado como para aplicarle AG, Goldberg consiguió lo que quería, escribiendo un AG en un ordenador personal Apple II. Estas y otras aplicaciones creadas por estudiantes de Holland convirtieron a los AG en un campo con bases suficientemente aceptables como para celebrar la primera conferencia en 1985, ICGA´85.

¿Que son los Algoritmos Genéticos?

Los AG son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los mas fuertes, postulados por Darwin (1859). Por imitación de este proceso, los AG son

capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. En la naturaleza los individuos de una población compiten entre si en la búsqueda de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la búsqueda de un compañero. Aquellos individuos que tienen mas éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de generar un gran numero de descendientes. Por el contrario individuos poco dotados producirán un menor numero de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagaran en sucesivas generaciones hacia un número de individuos creciente. La combinación de buenas características provenientes de diferentes ancestros, puede a veces producir descendientes "superindividuos", cuya adaptación es mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando unas características cada vez mejor adaptadas al entorno en el que viven. El poder de los AG proviene del hecho de que se trata de una técnica robusta, y pueden tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el AG encuentre la solución optima del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria. En el caso de que existan técnicas especializadas para resolver un determinado problema, lo mas probable es que superen al AG, tanto en rapidez como en eficacia. El gran campo de aplicación de los AG se relaciona con aquellos problemas para los cuales no existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibridandolas con los AG.

¿Por qué utilizar Algoritmos Genéticos en la Optimización?

La razón del creciente interés por los AG es que estos son un método global y robusto de búsqueda de las soluciones de problemas. La principal ventaja de estas características es el equilibrio alcanzado entre la eficiencia y eficacia para resolver diferentes y muy complejos problemas de grandes dimensiones.

Lo que aventaja a los AG frente a otros algoritmos tradicionales de búsqueda es que se diferencian de estos en los siguientes aspectos:

• Trabajan con una codificación de un conjunto de parámetros, no con los parámetros mismos.
• Trabajan con un conjunto de puntos, no con un único punto y su entorno (su técnica de búsqueda es global.) Utilizan un subconjunto del espacio total, para obtener información sobre el universo de búsqueda, a través de las evaluaciones de la función a optimizar. Esas evaluaciones se emplean de forma eficiente para clasificar los subconjuntos de acuerdo con su idoneidad.
• No necesitan conocimientos específicos sobre el problema a resolver; es decir, no están sujetos a restricciones. Por ejemplo, se pueden aplicar a funciones no continuas, lo cual les abre un amplio campo de aplicaciones que no podrían ser tratadas por los métodos tradicionales.
• Utilizan operadores probabilísticos, en vez de los tipicos operadores determinísticos de las técnicas tradicionales.
• Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivas en paralelo.
• Cuando se usan para problemas de optimización, resultan menos afectados por los máximos locales que las técnicas tradicionales (i.e., son métodos robustos).

Ahora bien; un esquema del funcionamiento general de un algoritmo genético podría ser el siguiente:

Algoritmo Genético:

- Generar una población inicial.

- Iterar hasta un criterio de parada.

- Evaluar cada individuo de la población.

- Seleccionar los progenitores.

- Aplicar el operador de cruce y mutación a estos progenitores.

- Incluir la nueva descendencia para formar una nueva generación.

Ventajas

• El primer y más importante punto es que los AG son intrínsecamente paralelos. La mayoría de los otros algoritmos son en serie y sólo pueden explorar el espacio de soluciones hacia una solución en una dirección al mismo tiempo, y si la solución que descubren resulta subóptima, no se puede hacer otra cosa que abandonar todo el trabajo hecho y empezar de nuevo. Sin embargo, ya que los AG tienen descendencia múltiple, pueden explorar el espacio de soluciones en múltiples direcciones a la vez. Si un camino resulta ser un callejón sin salida, pueden eliminarlo fácilmente y continuar el trabajo en avenidas más prometedoras, dándoles una mayor probabilidad en cada ejecución de encontrar la solución. Sin embargo, la ventaja del paralelismo va más allá de esto. Considere lo siguiente: todas las cadenas binarias (cadenas de ceros y unos) de 8 dígitos forman un espacio de búsqueda, que puede representarse como ******** (donde * significa “o 0 o 1”). La cadena 01101010 es un miembro de este espacio. Sin embargo, también es un miembro del espacio 0*******, del espacio 01******, del espacio 0******0, del espacio 0*1*1*1*, del espacio 10*01**0, etc. Evaluando la aptitud de esta cadena particular, un AG estaría sondeando cada uno de los espacios a los que pertenece. Tras muchas evaluaciones, iría obteniendo un valor cada vez más preciso de la aptitud media de cada uno de estos espacios, cada uno de los cuales contiene muchos miembros. Por tanto, un AG que evalúe explícitamente un número pequeño de individuos está evaluando implícitamente un grupo de individuos mucho más grande -de la misma manera que un encuestador que le hace preguntas a un cierto miembro de un grupo étnico, religioso o social espera aprender algo acerca de las opiniones de todos los miembros de ese grupo, y por tanto puede predecir con fiabilidad la opinión nacional sondeando sólo un pequeño porcentaje de la población. De la misma manera, el AG puede dirigirse hacia el espacio con los individuos más aptos y encontrar el mejor de ese grupo. En el contexto de los algoritmos evolutivos, esto se conoce como teorema del esquema, y es la ventaja principal de los AG sobre otros métodos de resolución de problemas.

• Debido al paralelismo que les permite evaluar implícitamente muchos esquemas a la vez, los AG funcionan particularmente bien resolviendo problemas cuyo espacio de soluciones potenciales es realmente grande -demasiado vasto para hacer una búsqueda exhaustiva en un tiempo razonable. La mayoría de los problemas que caen en esta categoría se conocen como “no lineales”. En un problema lineal, la aptitud de cada componente es independiente, por lo que cualquier mejora en alguna parte dará como resultado una mejora en el sistema completo. No es necesario decir que hay pocos problemas como éste en la vida real. La no linealidad es la norma, donde cambiar un componente puede tener efectos en cadena en todo el sistema, y donde cambios múltiples que, individualmente, son perjudiciales, en combinación pueden conducir hacia mejoras en la aptitud mucho mayores. La no linealidad produce una explosión combinatoria: el espacio de cadenas binarias de 1.000 dígitos puede examinarse exhaustivamente evaluando sólo 2.000 posibilidades si el problema es lineal, mientras que si no es lineal, una búsqueda exhaustiva requiere evaluar 21.000 posibilidades -un número que, escrito, ocuparía más de 300 dígitos.Afortunadamente, el paralelismo implícito de los AG les permite superar incluso este enorme número de posibilidades, y encontrar con éxito resultados óptimos o muy buenos en un corto periodo de tiempo, tras muestrear directamente sólo regiones pequeñas del vasto paisaje adaptativo. Por ejemplo, un AG desarrollado en común por ingenieros de General Electric y el Rensselaer Polytechnic Institute produjo el diseño de la turbina de un motor a reacción de altas prestaciones que era tres veces mejor que la configuración diseñada por humanos, y un 50 % mejor que una configuración diseñada por un sistema experto que recorrió con éxito un espacio de soluciones que contenía más de 10.387 posibilidades. Los métodos convencionales para diseñar estas turbinas son una parte fundamental de proyectos de ingeniería que pueden durar hasta cinco años y costar más de 2.000 millones de dólares; el AG descubrió esta solución en dos días, en una estación de trabajo de escritorio típica en ingeniería.

• Otra ventaja notable de los AG es que se desenvuelven bien en problemas con un paisaje adaptativo complejo -aquéllos en los que la función objetivo es discontinua, ruidosa, cambia con el tiempo, o tiene muchos óptimos locales. La mayoría de los problemas prácticos tienen un espacio de soluciones enorme, imposible de explorar exhaustivamente; el reto se convierte entonces en cómo evitar los óptimos locales soluciones que son mejores que todas las que son similares a ella, pero que no son mejores que otras soluciones distintas situadas en algún otro lugar del espacio de soluciones. Muchos algoritmos de búsqueda pueden quedar atrapados en los óptimos locales: si llegan a lo alto de una colina del paisaje adaptativo, descubrirán que no existen soluciones mejores en las cercanías y concluirán que han alcanzado la mejor de todas, aunque existan picos más altos en algún otro lugar del mapa.Los algoritmos evolutivos, por otro lado, han demostrado su efectividad al escapar de los óptimos locales y descubrir el óptimo global incluso en paisajes adaptativos muy escabrosos y complejos. (Debe decirse que, en la realidad, a menudo no hay manera de decir si una cierta solución a un problema es el óptimo global o sólo un óptimo local muy alto. Sin embargo, aunque un AG no devuelva siempre una solución perfecta y demostrable a un problema, casi siempre puede devolver al menos una muy buena solución). Todos los cuatro componentes principales de los AG -paralelismo, selección, mutación y cruzamiento- trabajan juntos para conseguir esto. Al principio, el AG genera una población inicial diversa, lanzando una “red” sobre el paisaje adaptativo. (Koza 2003[42], p. 506) compara esto con un ejército de paracaidistas cayendo sobre el paisaje del espacio de búsqueda de un problema, cada uno de ellos con órdenes de buscar el pico más alto). Pequeñas mutaciones permiten a cada individuo explorar sus proximidades, mientras que la selección enfoca el progreso, guiando a la descendencia del algoritmo cuesta arriba hacia zonas más prometedoras del espacio de soluciones. Sin embargo, el cruzamiento es el elemento clave que distingue a los AG de los otros métodos como los trepacolinas y el recocido simulado. Sin el cruzamiento, cada solución individual va por su cuenta, explorando el espacio de búsqueda en sus inmediaciones sin referencia de lo que el resto de individuos puedan haber descubierto. Sin embargo, con el cruzamiento en juego, hay una transferencia de información entre los candidatos prósperos los individuos pueden beneficiarse de lo que otros han aprendido, y los esquemas pueden mezclarse y combinarse, con el potencial de producir una descendencia que tenga las virtudes de sus dos padres y ninguna de sus debilidades. Este punto está ilustrado en Koza et al. 1999[41], p. 486, donde los autores analizan el problema de sintetizar un filtro de paso bajo utilizando programación genética. En una generación se seleccionaron dos circuitos progenitores para llevar a cabo el cruzamiento; un padre tenía una buena topología (componentes como inductores y condensadores colocados en el sitio correcto) pero malos tamaños (valores demasiado bajos de inductancia y capacidad para los componentes). El otro padre tenía mala topología pero buenos tamaños. El resultado de aparearlos mediante cruzamiento fue una descendencia con la buena topología de un padre y los buenos tamaños del otro, dando como resultado una mejora sustancial de la aptitud sobre sus dos padres.El problema de encontrar el óptimo global en un espacio con muchos óptimos locales también se conoce como el dilema de la exploración versus explotación, “un problema clásico de todos los sistemas que pueden adaptarse y aprender”. Una vez que un algoritmo (o un diseñador humano) ha encontrado una estrategia para resolver problemas que parece funcionar satisfactoriamente, ¿debería centrarse en hacer el mejor uso de esa estrategia, o buscar otras? Abandonar una estrategia de probada solvencia para buscar otras nuevas casi garantiza que supondrá una pérdida y degradación del rendimiento, al menos a corto plazo. Pero si uno se queda con una estrategia particular excluyendo a todas las demás, corre el riesgo de no descubrir estrategias mejores que existen pero no se han encontrado. De nuevo, los AG han demostrado ser muy buenos en dar con este equilibrio y descubrir buenas soluciones en un tiempo y esfuerzo computacional razonables.

• Otra área en el que destacan los AG es su habilidad para manipular muchos parámetros simultáneamente. Muchos problemas de la vida real no pueden definirse en términos de un único valor que hay que minimizar o maximizar, sino que deben expresarse en términos de múltiples objetivos, a menudo involucrando contrapartidas: uno sólo puede mejorar a expensas de otro. Los AG son muy buenos resolviendo estos problemas: en particular, su uso del paralelismo les permite producir múltiples soluciones, igualmente buenas, al mismo problema, donde posiblemente una solución candidata optimiza un parámetro y otra candidata optimiza uno distinto y luego un supervisor humano puede seleccionar una de esas candidatas para su utilización. Si una solución particular a un problema con múltiples objetivos optimiza un parámetro hasta el punto en el que ese parámetro no puede mejorarse más sin causar una correspondiente pérdida de calidad en algún otro parámetro, esa solución se llama óptimo paretiano o no dominada.

• Finalmente, una de las cualidades de los AG que, a primera vista, puede parecer un desastre, resulta ser una de sus ventajas: a saber, los AG no saben nada de los problemas que deben resolver. En lugar de utilizar información específica conocida a priori para guiar cada paso y realizar cambios con un ojo puesto en el mejoramiento, como hacen los diseñadores humanos, son “relojeros ciegos”; realizan cambios aleatorios en sus soluciones candidatas y luego utilizan la función objetivo para determinar si esos cambios producen una mejora. La virtud de esta técnica es que permite a los AG comenzar con una mente abierta, por así decirlo. Como sus decisiones están basadas en la aleatoriedad, todos los caminos de búsqueda posibles están abiertos teóricamente a un AG; en contraste, cualquier estrategia de resolución de problemas que dependa de un conocimiento previo, debe inevitablemente comenzar descartando muchos caminos a priori, perdiendo así cualquier solución novedosa que pueda existir. Los AG, al carecer de ideas preconcebidas basadas en creencias establecidas sobre “cómo deben hacerse las cosas” o sobre lo que “de ninguna manera podría funcionar”, los AG no tienen este problema. De manera similar, cualquier técnica que dependa de conocimiento previo fracasará cuando no esté disponible tal conocimiento, pero, de nuevo, los AG no se ven afectados negativamente por la ignorancia. Mediante sus componentes de paralelismo, cruzamiento y mutación, pueden viajar extensamente por el paisaje adaptativo, explorando regiones que algoritmos producidos con inteligencia podrían no haber tenido en cuenta, y revelando potencialmente soluciones de asombrosa e inesperada creatividad que podrían no habérseles ocurrido nunca a los diseñadores humanos. Un ejemplo muy gráfico de esto es el redescubrimiento, mediante la programación genética, del concepto de retroalimentación negativa -un principio crucial para muchos componentes electrónicos importantes de hoy en día, pero un concepto que, cuando fue descubierto en primera instancia, se le denegó una patente de nueve años porque el concepto era demasiado contrario a las creencias establecidas. Por supuesto, los algoritmos evolutivos no están enterados ni preocupados de si una solución va en contra de las creencias establecidas -sólo de si funciona.

Desventajas

Aunque los AG han demostrado su eficiencia y potencia como estrategia de resolución de problemas, no son la panacea. Los AG tienen ciertas limitaciones; sin embargo, se demostrará que todas ellas pueden superarse y que ninguna de ellas afecta a la validez de la evolución biológica.

• La primera y más importante consideración al crear un AG es definir una representación del problema. El lenguaje utilizado para especificar soluciones candidatas debe ser robusto; es decir, debe ser capaz de tolerar cambios aleatorios que no produzcan constantemente errores fatales o resultados sin sentido. Hay dos maneras principales para conseguir esto. La primera, utilizada por la mayoría de los AG, es definir a los individuos como listas de números binarios, enteros o reales- donde cada número representa algún aspecto de la solución candidata. Si los individuos son cadenas binarias, un 0 o 1 podría significar la ausencia o presencia de una cierta característica. Si son listas de números, estos números podrían representar muchas cosas distintas: los pesos de las conexiones en una red neuronal, el orden de las ciudades visitadas en un recorrido dado, la situación espacial de componentes electrónicos, los valores con los que se alimenta a un controlador, los ángulos de torsión de los enlaces péptidos de una proteína, etc. Así, la mutación implica cambiar estos números, cambiar bits o sumar o restar valores aleatorios. En este caso, el propio código del programa no cambia; el código es lo que dirige la simulación y hace un seguimiento de los individuos, evaluando sus aptitudes y quizá asegurando que sólo se producen valores realistas y posibles para el problema dado. En otro método, la programación genética, el propio código del programa sí cambia. Como ya se dijo en la sección “Métodos de representación”, la PG representa a los individuos como árboles de código ejecutables que pueden mutar cambiando o intercambiando subárboles. Ambos métodos producen representaciones robustas ante la mutación, y pueden representar muchos tipos diferentes de problemas y, como se dice en la sección “Algunos ejemplos específicos”, ambas han tenido un éxito considerable. El problema de representar a las soluciones candidatas de manera robusta no surge en la naturaleza, porque el método de representación utilizado por la evolución, a saber, el código genético, es inherentemente robusto: con muy pocas excepciones, como una cadena de codones de parada, no existe una secuencia de bases de ADN que no pueda traducirse en una proteína. Por lo tanto, virtualmente, cualquier cambio en los genes de un individuo siempre producirá un resultado inteligible, y por tanto las mutaciones en la evolución tienen mayor probabilidad de producir una mejora. Esto entra encontraste con los lenguajes creados por el hombre como el inglés, donde el número de palabras con significado es pequeño comparado con el número total de formas en las que se pueden combinar las letras del alfabeto, y por tanto, es probable que un cambio aleatorio en una frase en inglés produzca un sinsentido

• El problema de cómo escribir la función objetivo debe considerarse cuidadosamente para que se pueda alcanzar una mayor aptitud y verdaderamente signifique una solución mejor para el problema dado. Si se elige mal una función objetivo o se define de manera inexacta, puede que el AG sea incapaz de encontrar una solución al problema, o puede acabar resolviendo el problema equivocado. (Esta última situación se describe a veces como la tendencia del AG a “engañar”, aunque en realidad lo que está pasando es que el AG está haciendo lo que se le pidió hacer, no lo que sus creadores pretendían que hiciera). Como por ejemplo: unos investigadores utilizaron un algoritmo evolutivo en conjunción con una serie de chips reprogramables, haciendo que la función objetivo recompensara al circuito en evolución por dar como salida una señal oscilatoria. Al final del experimento, se producía efectivamente una señal oscilatoria -pero en lugar de actuar como un oscilador, como pretendían los investigadores, ¡descubrieron que el circuito se había convertido en un receptor de radio que estaba recibiendo y retransmitiendo una señal oscilatoria de un componente electrónico cercano! Sin embargo, esto no es un problema en la naturaleza. En el laboratorio de la evolución biológica, sólo hay una función objetivo que es igual para todos los seres vivos -la carrera por sobrevivir y reproducirse, sin importar qué adaptaciones hagan esto posible. Los organismos que se reproducen con más abundancia que sus competidores están más adaptados; los que fracasan en reproducirse no están adaptados.

• Además de elegir bien la función objetivo, también deben elegirse cuidadosamente los otros parámetros de un AG -el tamaño de la población, el ritmo de mutación y cruzamiento, el tipo y fuerza de la selección. Si el tamaño de la población es demasiado pequeño, puede que el AG no explore suficientemente el espacio de soluciones para encontrar buenas soluciones consistentemente. Si el ritmo de cambio genético es demasiado alto o el sistema de selección se escoge inadecuadamente, puede alterarse el desarrollo de esquemas beneficiosos y la población puede entrar en catástrofe de errores, al cambiar demasiado rápido para que la selección llegue a producir convergencia. Los seres vivos también se enfrentan a dificultades similares, y la evolución se ha encargado de ellas. Es cierto que si el tamaño de una población cae hacia un valor muy bajo, los ritmos de mutación son muy altos o la presión selectiva es demasiado fuerte (una situación así podría ser resultado de un cambio ambiental drástico), entonces la especie puede extinguirse. La solución ha sido “la evolución de la evolutividad” -las adaptaciones que alteran la habilidad de una especie para adaptarse. Un ejemplo. La mayoría de los seres vivos han evolucionado una elaborada maquinaria celular que comprueba y corrigue errores durante el proceso de replicación del ADN, manteniendo su ritmo de mutación a unos niveles aceptablemente bajos; a la inversa, en tiempos de fuerte presión ambiental, algunas especies de bacterias entran en un estado de hipermutación en el que el ritmo de errores en la replicación del ADN aumenta bruscamente, aumentando la probabilidad de que se descubrirá una mutación compensatoria. Por supuesto, no pueden eludirse todas las catástrofes, pero la enorme diversidad y las adaptaciones altamente complejas de los seres vivos actuales muestran que, en general, la evolución es una estrategia exitosa. Igualmente, las aplicaciones diversas y los impresionantes resultados de los AG demuestran que son un campo de estudio poderoso y que merece la pena.

• Un problema con el que los AG tienen dificultades son los problemas con las funciones objetivo ”engañosas”, en las que la situación de los puntos mejorados ofrecen información engañosa sobre dónde se encuentra probablemente el óptimo global. Por ejemplo: imagine un problema en el que el espacio de búsqueda esté compuesto por todas las cadenas binarias de ocho caracteres, y en el que la aptitud de cada individuo sea directamente proporcional al número de unos en él es decir, 00000001 sería menos apto que 00000011, que sería menos apto que 00000111, etcétera -, con dos excepciones: la cadena 11111111 resulta tener una aptitud muy baja, y la cadena 00000000 resulta tener una aptitud muy alta. En este problema, un AG (al igual que la mayoría de los algoritmos) no tendría más probabilidad de encontrar un óptimo global que una búsqueda aleatoria. La solución a este problema es la misma para los AG y la evolución biológica: la evolución no es un proceso que deba encontrar siempre el óptimo global. Puede funcionar casi igual de bien alcanzando la cima de un óptimo local alto y, para la mayoría de las situaciones, eso será suficiente, incluso aunque el óptimo global no pueda alcanzarse fácilmente desde ese punto. La evolución es como un “satisfactor” -un algoritmo que entrega una solución “suficientemente buena”, aunque no necesariamente la mejor solución posible, dada una cantidad razonable de tiempo y esfuerzo invertidos en la búsqueda. La “FAQ de la evidencia de diseño improvisado en la naturaleza” proporciona ejemplos de la naturaleza con estos resultados. (También hay que tener en cuenta que pocos o ningún problema real es tan engañoso como el ejemplo algo forzado dado arriba. Normalmente, la situación de las mejoras locales proporciona alguna información sobre la situación del óptimo global).

• Un problema muy conocido que puede surgir con un AG se conoce como convergencia prematura. Si un individuo que es más apto que la mayoría de sus competidores emerge muy pronto en el curso de la ejecución, se puede reproducir tan abundantemente que merme la diversidad de la población demasiado pronto, provocando que el algoritmo converja hacia el óptimo local que representa ese individuo, en lugar de rastrear el paisaje adaptativo lo bastante a fondo para encontrar el óptimo global. Esto es un problema especialmente común en las poblaciones pequeñas, donde incluso una variación aleatoria en el ritmo de reproducción puede provocar que un genotipo se haga dominante sobre los otros. Los métodos más comunes implementados por los investigadores en AG para solucionar este problema implican controlar la fuerza selectiva, para no proporcionar tanta ventaja a los individuos excesivamente aptos. La selección escalada, por rango y por torneo, discutidas anteriormente, son tres de los métodos principales para conseguir esto; algunos métodos de selección escalada son el escalado sigma, en el que la reproducción se basa en una comparación estadística de la aptitud media de la población, y la selección de Boltzmann, en la que la fuerza selectiva aumenta durante la ejecución de manera similar a la variable “temperatura” en el recocido simulado. La convergencia prematura ocurre en la naturaleza (los biólogos la llaman deriva genética). Esto no debe sorprender; como ya se dijo arriba, la evolución, como estrategia de resolución de problemas, no está obligada a encontrar la mejor solución, sólo una que sea lo bastante buena. Sin embargo, en la naturaleza, la convergencia prematura es menos común, ya que la mayoría de las mutaciones beneficiosas en los seres vivos sólo producen mejoras en la aptitud pequeñas e incrementales; son raras las mutaciones que producen una ganancia de aptitud tan grande que otorgue a sus poseedores una drástica ventaja reproductiva.

• Finalmente, varios investigadores aconsejan no utilizar AG en problemas resolubles de manera analítica. No es que los AG no puedan encontrar soluciones buenas para estos problemas; simplemente es que los métodos analíticos tradicionales consumen mucho menos tiempo y potencia computacional que los AG y, a diferencia de los AG, a menudo está demostrado matemáticamente que ofrecen la única solución exacta. Por supuesto, como no existe una solución matemática perfecta para ningún problema de adaptación biológica, este problema no aparece en la naturaleza.

¿Cómo Saber si es Posible usar un Algoritmo Genético?

La aplicación más común de los AG ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla:

• Su espacio de búsqueda (i.e., sus posibles soluciones) debe de estar delimitado dentro de un cierto rango.
• Debe permitir definir una función de aptitud que nos indique que tan buena o mala es una cierta respuesta.
• Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en el computador.

El primer punto es muy importante, y lo más recomendable es intentar resolver problemas que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero preferiblemente cuando exista un rango de soluciones relativamente pequeño.

Algunas Aplicaciones de los Algoritmos Genéticos

Como hemos podido observar, el área de aplicación de los AG es muy amplia, y en general sus aplicaciones se pueden implementar a muchos de los problemas de la vida cotidiana, de igual forma, se hayan aplicado a diversos problemas y modelos en ingeniaría, y en la ciencia en general cabe destacar entre ellos:

Optimización: Se trata de un campo especialmente abonado para el uso de los AG, por las características intrínsecas de estos problemas. No en vano fueron la fuente de inspiración para los creadores estos algoritmos. Los AG 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 AG 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 AG 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 neuronal, las reglas para sistemas de clasificación de aprendizaje o sistemas de producción simbólica, y los sensores para robots.

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 coevolució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 gene para la recombinación?".

Evolución y aprendizaje: Los AG 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.

Aunque esta lista no es, en modo alguno, exhaustiva, sí transmite la idea de la variedad de aplicaciones que tienen los AG. Gracias al éxito en estas y otras áreas, los AG han llegado a ser un campo puntero en la investigación actual.

AQUI PODRA ENCONTRAR MAS INFORMACION DE ALGORITMOS GENETICOS

http://www.monografias.com/trabajos-pdf/algoritmos-geneticos/algoritmos-geneticos.pdf