algoritmo genetico

Universidad Nacional del Altiplano

PRESENTACIÓN

Este documento contiene un extracto del trabajo de graduación titulado

“Elaboración de pronósticos con algoritmos genéticos” realizado por Samuel David

Orozco Orozco, estudiante de la carrera de Ingeniería en Ciencias y Sistemas de

la Universidad de San Carlos de Guatemala.

Se ha creado este documento con el propósito de servir de apoyo a los

estudiantes del curso de Inteligencia Artificial en el estudio de los algoritmos

genéticos. Este documento incluye teoría general sobre algoritmos genéticos y un

ejemplo sencillo de su aplicación.

Al final del documento se incluye una lista de las fuentes de información que

fueron consultadas para su elaboración, que pueden revisarse si se desea

profundizar más en el tema.

También en el presente trabajo se pone en conocimiento todo acerca de lo

que es:

Historia de los Algoritmos Genéticos.

Conceptos de los Algoritmos Genéticos.

Características de los Algoritmos Genéticos.

Ventajas y Desventajas de los Algoritmos Genéticos.

Y una Aplicación de un Algoritmos Genéticos.

BIOINFORMÁTICA 1


DEDICATORIA

El presente trabajo es

dedicado a DIOS por su infinita

Misericordia y Amor hacia la

humanidad entera.

A cada uno de los que hacen

posible nuestra formación

profesional y académica: docentes,

administrativos e ingenieros de la

especialidad por su sabia

enseñanza, su compresión y su

apoyo mutuo

Muy especialmente con profundo

cariño a nuestros padres quienes son

directos participes y colaboradores de ese

apoyo incondicional que nos brindan día a

día para nuestra formación profesional.

Alumnos del V-S

BIOINFORMÁTICA 2


AGRADECIMIENTO

En el presente trabajo de

investigación de los estudiantes; se

agradece por la acertada dirección de la

UNIVERSIDAD NACIONAL DEL

ALTIPLANO – PUNO, por habernos

brindado sus puertas y su escuela

profesional.

Así mismo agradezco a nuestros

docentes y a nuestros compañeros y

compañeras por habernos brindado su

apoyo moral en todo momento.

Los Estudiantes

RESUMEN

BIOINFORMÁTICA 3


En este trabajo se presenta un algoritmo genético para la resolución de

problemas de Programación por Metas Entera. Este tipo de problemas presentan

en general un gran número de dificultades para su resolución utilizando algoritmos

tradicionales de Programación Entera, siendo en la mayoría de los casos de

problemas reales demasiado costosa computacionalmente para afrontarla con

garantías.

Sin embargo, se mostrará cómo este nuevo tipo de algoritmos, los

algoritmos genéticos, permiten resolver eficientemente problemas de este tipo con

un coste computacional reducido. Como ejemplo, se resuelve en este trabajo un

problema del comportamiento genético, con un modelo de Programación por

Metas Entera aplicando un algoritmo genético y un algoritmo tradicional. Para

estas resoluciones se analiza el coste computacional de ambos tipos de resolución

para poner de manifiesto las ventajas que puede suponer un algoritmo genético

para la resolución de problemas reales complejos.

INDICE GENERAL

BIOINFORMÁTICA 4


CAPITULO I: Introducción de los Algoritmos Genéticos .

1.1.-Historia de los Algoritmos Genéticos.

El desarrollo de los Algoritmos Genéticos se debe a gran medida a John Holland, investigador de la Universidad de Michigan. A finales de la década de los 60 desarrolló una técnica que imitaba en su funcionamiento a la selección natural. Aunque originalmente esta técnica que imitaba en su funcionamiento a la selección natural.

Finales de los 59 y principios de los 60.- Algoritmos Genéticos programados en computadoras por biólogos evolutivos que buscaban explícitamente realizar modelos de aspectos de la evolución natural. En 1962, investigadores como G.E.P. Box, G.J. Friedman, W.W. Bledsoe y H.J. Bremermann habían desarrollado independientemente algoritmos inspirados en la evolución para optimización de funciones y aprendizaje automático, pero sus trabajos generaron poca reacción.En 1965 surgió un desarrollo más exitoso, cuando Ingo Rechenberg, entonces de la Universidad Técnica de Berlín, introdujo una técnica que llamó estrategia evolutiva. En 1975 apareció el trabajo fundamental en el campo de los algoritmos genéticos con la publicación del libro “Adaptación en Sistemas Naturales y Artificiales” de John Holland'.A finales de 1980s la General Electric comenzó a vender el primer producto de Algoritmo Genético para solucionar problemas de procesos industriales. En 1989 se creó el producto Evolver que fue el primer producto de Algoritmo Genético para Computadoras personales.

CAPITULO II: Que son los Algoritmos Genéticos .

BIOINFORMÁTICA 5


Los Algoritmos Genéticos (AGs) 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 más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos 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.

Un algoritmo genético consiste en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuales de ellos deben generar descendencia para la nueva generación.

Versiones más complejas de algoritmos genéticos generan un ciclo iterativo que

directamente toma a la especie (el total de los ejemplares) y crea una nueva

generación que reemplaza a la antigua una cantidad de veces determinada por su

propio diseño. Una de sus características principales es la de ir perfeccionando su

propia heurística en el proceso de ejecución, por lo que no requiere largos

períodos de entrenamiento especializado por parte del ser humano, principal

defecto de otros métodos para solucionar problemas, como los Sistemas Expertos

En el caso de que existan técnicas especializadas para resolver un determinado problema, lo más 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 hibridándolas con los AG.

Cuando el AG es implementado, se hace de forma que involucre el siguiente ciclo:

1. Generación de una población inicial de manera aleatoria.2. Evaluar el desempeño de todos los individuos de la población, tomando en

cuenta alguna función objetivo.3. Crear una nueva población mediante la ejecución de operaciones como el

crossover y mutación sobre individuos cuyo desempeño haya sido evaluado.

4. Descartar la población vieja e iterar usando la nueva, hasta que el número de generaciones alcanza al criterio de terminación.

BIOINFORMÁTICA 6


Una iteración de este ciclo constituye una generación. Este comportamiento puntual no se observa como un todo dentro de las poblaciones en la naturaleza pero si representa un modelo de implementación conveniente.

BIOINFORMÁTICA 7

Inserción del mutante en la nueva población

Ejecución Mutación

Individuo seleccionado en base a su desempeño

Mutación

Individuos=Individuos+1

Cruce

Individuos=Individuos+2

Inserción de 2 individuos en la nueva población

Ejecución Crossover

2 Individuos seleccionados en base a su

desempeño

NO

SI

NO

SI

Selección de la operación

Generacion++ Individuos=M?

Evaluación de cada individuo en la población

Fin

Resultado PropuestoCriterio de terminación

Población Inicial Aleatoria

Generacion=0


La primera generación (generación 0) de este proceso opera sobre una población de individuos generados aleatoriamente. Desde entonces las operaciones genéticas en conjunto con la medida del desempeño trabajan para mejorar la población.

Estructura

Tipos de Representación

Durante los primeros años el tipo de representación utilizado era siempre binario, debido a que se adapta perfectamente al tipo de operaciones y el tipo de operadores que se utilizan en un AG. Sin embargo, las representaciones binarias no son siempre efectivas por lo que se empezaron a utilizar otro tipo de representaciones.

En general, una representación debe identificar las características constituyentes del conjunto a estudiar, de forma que distintas representaciones dan lugar a distintas perspectivas y por tanto distintas soluciones.

Tipos básicos de representaciones:Representación binaria: Cada gen es un valor 1 ó 0.Representación entera: Cada gen es un valor entero.Representación real: Cada gen es un valor real.

Tamaño de la población

Una cuestión que se puede plantear es la relacionada con el tamaño idóneo de la población. Parece intuitivo que las poblaciones pequeñas corren el riesgo de no cubrir adecuadamente el espacio de búsqueda, mientras que el trabajar con poblaciones de gran tamaño puede acarrear problemas relacionados con el excesivo costo computacional.

Población Inicial

Habitualmente la población inicial se escoge al azar. Si los individuos de la población inicial se obtuviesen como resultado de alguna técnica heurística o de optimización local puede suceder que se acelere la convergencia del AG. Sin embargo en algunos casos la desventaja resulta ser la prematura convergencia del algoritmo, queriendo indicar con esto la convergencia hacia óptimos locales.

Función Objetivo

El resultado al cual se desea llegar.

Operador de Selección

BIOINFORMÁTICA 8


El operador de Selección es el encargado de transmitir y conservar aquellas características de las soluciones que se consideran valiosas a lo largo de las generaciones. El principal medio para que la información útil se transmita es que aquellos individuos mejor adaptados tengan más probabilidades de reproducirse. Sin embargo, es necesario también incluir un factor aleatorio que permita reproducirse a individuos que aunque no estén muy bien adaptados, puedan contener alguna información útil para posteriores generaciones, con el objeto de mantener así también cierta diversidad en cada población.

Operador de Cruce

El operador de Cruce permite realizar una exploración de toda la información almacenada hasta el momento en la población y combinarla para crear mejores individuos.

Operador de Mutación

La mutación se considera un operador básico, que proporciona un pequeño elemento de aleatoriedad en el entorno de los individuos de la población. Si bien el operador de cruce es el responsable de efectuar la búsqueda a lo largo del espacio de posibles soluciones, el operador de mutación va ganando en importancia a medida que la población de individuos va convergiendo.

El objetivo del operador de mutación es producir nuevas soluciones a partir de la modificación de cierto número de genes de una solución existente, con la intención de fomentar la variabilidad dentro de la población. Existen muy diversas formas de realizar la mutación, desde la más sencilla (puntual), donde cada gen muta aleatoriamente con independencia del resto de genes, hasta configuraciones más complejas donde se tienen en cuanta la estructura del problema y la relación entre los distintos genes.

CAPITULO III. Características de los algoritmos genéticos.

BIOINFORMÁTICA 9


OROZCO (2007)1Algunas de las características de los algoritmos genéticos

son:

• Son algoritmos estocásticos. Dos ejecuciones distintas pueden dar dos

soluciones distintas.

• Son algoritmos de búsqueda múltiple, por lo tanto 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í.

• Son los algoritmos que hacen una barrida amplia 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.

• 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 se 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. Una buena

codificación puede hacer la programación y resolución muy sencillas, mientras que

una codificación errada obligará a estudiar que los individuos cumplan las

restricciones del problema. Además, la velocidad de convergencia va a estar

fuertemente influenciada por la representación.

1 Dr. Samuel Orozco-Universidad de San Carlos de Guatemala-Facultad de Ingeniera-Escuela de Ingeniería en Ciencias y Sistemas; Guatemala, Febrero del 2007.

BIOINFORMÁTICA 10


• Es una búsqueda para métricamente robusta. Eso quiere decir que los

parámetros del algoritmo escogidos deben ser realmente malos para que no

converja.

• Los algoritmos genéticos son intrínsecamente paralelos. Esto significa que,

independientemente de que se hayan implementado de forma paralela o no,

buscan en distintos puntos del espacio de soluciones de forma paralela.

CAPITULO III: Objetivos de los algoritmos genéticos.

3.1.- Aplicaciones de los algoritmos genéticos.

Son las siguientes aplicaciones:

2.2.- Limitaciones de los algoritmos genéticos.

El poder de los Algoritmos Genéticos 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 Algoritmo Genético encuentre la solución óptima, 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 más probable es que superen al Algoritmo Genético, tanto en rapidez como en eficacia. El gran campo de aplicación de los Algoritmos Genéticos 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 hibridándolas con los Algoritmos Genéticos.

CAPITULO IV: PROYECTOS Y LOGROS DE LA BIOINFORMÁTICA.

5.1.-Proyectos:

Microsatellites in Phytophtora ESTs: Survey, transferabilliity and

associiatiion wiith pathogenesiis rellated genes.

5.2.-Logros:

Predicción de Genes.

Predicción de promotores y elementos reguladores.

Predicción de Genes.

BIOINFORMÁTICA 11


CAPITULO VI: CONCLUSIONES.

Con este trabajo se pretende poner de manifiesto la eficiencia y las ventajas

que un algoritmo genético puede presentar a la hora de resolver un problema

complejo de Programación Multiobjetivo. Así, se ha resuelto un problema real

complejo de Programación por Metas Entera con un método exacto tradicional (el

método de Ramificación y Acotación), utilizando unas de las librerías más

eficientes en este campo, las librerías de Windows.h. Posteriormente se ha

diseñado e implementado un sencillo algoritmo genético para resolver este

problema, obteniendo la misma solución que la resolución exacta, pero con un

ahorro de tiempo de computación de más del 90%.

Este es un ejemplo, por tanto, en el que se pone de manifiesto que, a la hora de

resolver un problema de Programación Multiobjetivo complejo y costoso

computacionalmente, la utilización de un algoritmo genético puede ser una opción

eficiente en cuanto a tiempo de computación y en cuanto a calidad de las

soluciones como alternativa a los métodos tradicionales.

CAPITULO VII: RECOMENDACIONES.

Del presente trabajo se recomienda lo siguiente:

Se recomienda tener un amplio conocimiento de conceptos básicos de la

Biología y Genética.

Conocimientos en desarrollo de Programas.

Amplio desarrollo de software.

Trabajar en equipo de diferentes especialidades.

Mantener una documentación diaria.

BIOINFORMÁTICA 12


BIBLIOGRAFIA

BIBLIOGRAFIA WEB

http://www.uv.es/~marti/genet.html.

http://www.fciencias.unam.mx/revista/soluciones/N17/Coello2.html.

http://www.geocities.com/SiliconValley/Vista/7491/index.html.

ANEXOS

GLOSARIO BASICO

BIOINFORMÁTICA 13

http://www.geocities.com/SiliconValley/Vista/7491/index.html

http://www.fciencias.unam.mx/revista/soluciones/N17/Coello2.html

http://www.uv.es/~marti/genet.html

algoritmo genetico

Documents