Algoritmos Geneticos
-
Upload
steven-luis-maiz-cespedes -
Category
Documents
-
view
220 -
download
5
description
Transcript of Algoritmos Geneticos
-
UNIVERSIDAD NACIONAL ABIERTA
MATEMTICA CENTRO LOCAL METROPOLITANO
APLICACIN DE LOS ALGORITMOS GENTICOS SIMPLES EN LA OPTIMIZACIN DE FUNCIONES REALES
(presentado para optar al ttulo de Licenciado en Matemtica Mencin Anlisis Numrico)
Ral Ins Barrera Nez
Caracas, junio de 2006
UNIVERSIDAD NACIONAL ABIERTA i
-
UNIVERSIDAD NACIONAL ABIERTA ii
Aprobacin del Profesor Tutor
Luego de haber ledo detenidamente el presente Trabajo de
Grado, le doy m aprobacin tanto en lo referente a forma como a
contenido.
______________________
Jos Ramn Gascn
-
UNIVERSIDAD NACIONAL ABIERTA iii
INDICE GENERAL Pgina
APROBACIN DEL PROFESOR TUTOR II
VEREDICTO DEL JURADO ERROR! MARCADOR NO DEFINIDO.
LISTA DE ILUSTRACIONES V
RESUMEN VI
GLOSARIO DE TRMINOS VII
INTRODUCCIN IX
CAPTULO I 1
LOS ALGORITMOS GENTICOS 1
1.1. Breve acercamiento a la biologa gentica 1
1.2. Historia furtiva 4 1.2.1. De la teora de la evolucin 4 1.2.2. De los algoritmos genticos 5
1.3. Aspectos bsicos de los algoritmos genticos 7
1.4. Operacionalidad de los algoritmos genticos simples 9 1.4.1. Caractersticas de los algoritmos genticos simples 9 1.4.2. Ejecucin del proceso de los algoritmos genticos simples 11 1.4.3. Operadores genticos 13
1.4.4. Ejemplo manual de optimizacin numrica mediante el AGS 15
1.4.5. Cdigo fuente de un algoritmo gentico simple 23
CAPTULO II 25
MTODOS CLSICOS DE OPTIMIZACIN NUMRICA 25
2.1. Algoritmo del gradiente con paso constante 25 2.1.1. Ejemplo manual del algoritmo del gradiente con paso constante 27
-
2.2. Algoritmo de Newton con paso constante 29 2.2.1. Ejemplo manual del algoritmo de Newton con paso constante 31
CAPTULO III 32
ENSAYOS DE APLICACIN DEL ALGORITMO GENTICO SIMPLE Y DE LOS MTODOS CLSICOS EN LA OPTIMIZACIN NUMRICA 32
3.1. Evaluacin de la funcin 1)10(22 += xsenxY en el dominio [0,2] 32 3.1.1. Aplicacin del algoritmo gentico simple 33 3.1.2. Aplicacin de los mtodos clsicos de optimizacin numrica 39
3.2. Evaluacin de la funcin ( )
(( ))222222
yx0,0011
0,5yxsen0,5Z ++
++= , en el dominio [-200, 200] X [-200, 200] 40
3.2.1. Aplicacin del algoritmo gentico simple 41 3.2.2. Aplicacin de los mtodos clsicos de optimizacin numrica 42
CAPTULO IV 43
POSIBLES MODIFICACIONES AL ALGORITMO GENTICO SIMPLE Y CONCLUSIONES 43
4.1 Modificaciones sobre los operadores genticos 43 4.1.1. Seleccin (Elitismo) 44 4.1.2. Cruce (Varios tipos) 45 4.1.1. Mutacin 45
4.2 Conclusiones 45
ANEXO 1 ARTCULO DE PRENSA PUBLICADO EN EL CUERPO 4-8 DEL UNIVERSAL, EL 09/04/2006 47
ANEXO 2 CDIGO FUENTE DEL ALGORITMO GENTICO SIMPLE 50
A.2.1. Para funciones reales de una variable 50
A.2.2. Para funciones reales de dos variables 56
ANEXO 3 HERRAMIENTAS COMPUTACIONALES UTILIZADAS 62
REFERENCIA BIBLIOGRFICA 63
UNIVERSIDAD NACIONAL ABIERTA iv
-
UNIVERSIDAD NACIONAL ABIERTA v
LISTA DE ILUSTRACIONES
GRFICO Pgina
1. Diagrama de flujos del proceso del algoritmo gentico simple 12
2. Figura N 1 grfica de la funcin 35
3. Figura N 2 Valores regulares de la funcin para distintas generaciones 39
4. Figura N neraciones 40
6. Figura N 5 Valores regulares de la funcin en la poblacin inicial 41
7. Figura N 6 Valores regulares de la funcin en la poblacin final 41
inio
e inio
ABL
I. Tabla N 1 Resumen de resultados empricos 37
1)10(22 += xsenxY
3 Nmero de mutaciones y cruces para distintas ge
5. Figura N 4 Funcin de aptitud acumulada distintas generaciones 40
8. Figura N 7 grfica de la funcin en el dom222
0,52y2x2sen
0,5Z
++=
[-10, 10] X [-10-, 10] 42 yx0,0011 ++
9. Figura N 8 grficas de la funcin n el dom2
22
0,52y2x2sen
0,5Z
++=
[-5, 5] X [0, 2,5] 43 yx0,0011 ++
T AS
-
UNIVERSIDAD NACIONAL ABIERTA vi
RESUMEN
El objeto del presente trabajo de grado es utilizar el concepto de algoritmo gentico
simple aplicado a la optimizacin de funciones de variable real (una y dos variables),
siguiendo como referencia el libro intitulado Genetic Algorithms in Search, Optimization, and
Machine Learning, cuyo autor es D. E. Golberg (1989), en cuanto al aspecto conceptual y al
uso de las rutinas algortmicas que en el mencionado texto se describen (modificadas
brevemente por el autor). Los resultados de los ensayos experimentales realizados
aplicando esta novedosa herramienta se compararon con los obtenidos mediante los
mtodos tradicionales de optimizacin numrica permitiendo evidenciar la potencialidad del
algoritmo gentico simple en un escenario donde las funciones presentan en su dominio de
definicin: oscilaciones moderadas y la existencia de varios mximos locales. El campo de
aplicacin de esta herramienta se encuentra en el conjunto de las funciones para las cuales
las tcnicas tradicionales especializadas fallan o no aplican. El tema de la convergencia del
algoritmo gentico no fue revisado en ninguno de sus aspectos. Aunque los resultados
provenientes del algoritmo gentico son incuestionablemente mejores no pretendemos
demostrar que el mismo sea siempre ms eficiente para resolver problemas de optimizacin.
Palabras claves: algoritmo, gentico, optimizacin, funciones, reales.
-
UNIVERSIDAD NACIONAL ABIERTA vii
GLOSARIO DE TRMINOS
ADN (cido desoxirribonucleico): Es el compuesto contenido en el cromosoma,
responsable de la transmisin del material gentico de la clula en el proceso de divisin
celular conducente a la reproduccin de un organismo.
Alelo: Variantes o formas alternativas de un gen.
Algoritmo: Procedimiento iterativo utilizado para resolver un problema matemtico.
Convergencia: Se dice que un objeto matemtico posee la caracterstica de convergencia
(o converge), si tiende o se dirige a un objeto (o al mismo objeto) en la medida que sus
elementos independientes varan en una direccin y sentido especficos.
Cromosoma: Es una diminuta estructura filiforme compuesta por cidos nucleicos y
protenas, presente en todas las clulas vegetales y animales.
Error: Diferencia que existe entre un objeto matemtico y otro mediante el cual intentamos
representarlo.
Evolucin: Consiste en el proceso de transitar, en inmensos lapsos de tiempo, por una
serie progresiva de transformaciones conducentes a una cspide habitada por mentes
supremas.
Evolucionismo: Doctrina filosfica o cientfica basada en la evolucin.
Evolucionista: Ente partidario del evolucionismo.
Fenotipo: Conjunto de caractersticas hereditarias comunes a una determinada especie
vegetal o animal debido a la existencia de genes semejantes.
Gen: Cada una de las partculas que en el ncleo de la clula condicionan la transmisin
de los caracteres hereditarios.
Gentica: Es la ciencia que estudia la herencia biolgica y la variacin, apoyndose en las
leyes y principios que gobiernan las semejanzas y diferencias entre los individuos de una
misma especie.
Genotipo: Conjunto de factores hereditarios legtimos de un individuo o de una especie.
-
Gradiente: Sea f una funcin diferenciable sobre un abierto de un espacio vectorial
eucldeo E de dimensin finita. La diferencial de f se identifica a un campo de vectores,
llamado gradiente de f y notado grad f, gracias a la relacin
= hxfgradhfd
x/, .
Herencia: Tendencia de la naturaleza a reproducir en los seres los caracteres de sus
antepasados.
Mecnica molecular: Estudio de los movimientos de las molculas y de sus tomos.
Optimizacin: Accin y efecto de buscar el objeto de mejor desempeo, calificado
mediante una funcin de aptitud o mtrica.
Promedio: Trmino medio o representante de un conjunto de objetos numricos.
UNIVERSIDAD NACIONAL ABIERTA viii
-
UNIVERSIDAD NACIONAL ABIERTA ix
INTRODUCCIN
El objeto de esta monografa es introducir el concepto de algoritmo gentico e
ilustrar alguna de sus aplicaciones.
El algoritmo gentico simple fue desarrollado por John Holland profesor de la
Universidad de Michigan en Ann Arbor en los aos setenta aunque las ideas de programas
que usan tcnicas evolutivas fueron desarrolladas en aos anteriores.
Se trata de un mecanismo de bsqueda de soluciones para diversos problemas
basado en las ideas de la evolucin de las especies de Darwin. Forma parte de un conjunto
de tcnicas computacionales que simulan procesos biolgicos o naturales, entre estos se
encuentran las redes neuronales, el recocido simulado y los propios algoritmos genticos.
Debemos sealar que desarrollamos en este trabajo de grado el algoritmo gentico
simple tal como aparece explicado en el libro de Goldberg (1989) (ver bibliografa). No nos
ocupamos en detalle de la extensa gama de variaciones del algoritmo gentico y slo al final
revisamos algunas de las posibilidades.
Cabe sealar que actualmente diversas investigaciones se desarrollan en el campo
de los algoritmos genticos pero no vamos a detenernos en ellas. En cambio explicaremos
en detalle el algoritmo gentico simple y lo aplicaremos en el proceso de optimizacin de
funciones de variable real (una y dos variables); tambin compararemos nuestros resultados
con los que se obtienen con el clsico mtodo del gradiente, el cual asume la regularidad de
la funcin objetivo.
La monografa en su captulo primero, empieza explicando las nociones bsicas del
mecanismo de la herencia desde el punto de vista de la biologa, as como la estructura en
detalle del algoritmo gentico simple. Una corrida del mismo es realizada prcticamente a
mano, para ilustrar los diversos operadores genticos y su implementacin.
-
UNIVERSIDAD NACIONAL ABIERTA x
En el siguiente captulo se exponen algunos mtodos de optimizacin del anlisis
numrico, tales como el algoritmo del gradiente con paso constante y el algoritmo de Newton
con paso constante.
En el captulo tercero se exponen los resultados numricos, que arroja el algoritmo
gentico simple al optimizar funciones de una y dos variables, que oscilan moderadamente y
comparamos estos resultados con los que se obtiene aplicando el algoritmo del gradiente
con paso constante.
Aunque los resultados provenientes del algoritmo gentico simple son
incuestionablemente mejores, no pretendemos demostrar que el mismo sea siempre ms
eficiente para resolver problemas de optimizacin.
En el ltimo captulo exponemos las conclusiones del trabajo y mencionamos
brevemente algunas de las posibles modificaciones del algoritmo gentico.
Debemos sealar que no hemos tocado el problema de la convergencia del
algoritmo gentico, en particular no presentamos el Teorema Fundamental de Holland que
carece de rigurosidad matemtica y que ha motivado el uso de cadenas de Markov para
presentar los aspectos de convergencia con una base slida (ver Rudolph (1994) en la
bibliografa).
En una serie de anexos se presenta el cdigo fuente del programa del algoritmo
gentico simple en lenguaje pascal y las caractersticas tcnicas del computador y del
compilador donde se realizaron los experimentos. Debemos sealar que el programa fue
modificado del original del libro de Goldberg (1989), traduciendo al idioma castellano las
salidas y declaraciones del mismo e incluyendo la posibilidad de trabajar con varias
variables.
Por ltimo, esperamos que este trabajo pueda servir de apoyo a los ingenieros,
matemticos y profesionales en general que busquen en el algoritmo gentico una
-
UNIVERSIDAD NACIONAL ABIERTA xi
herramienta para resolver problemas, presentando una exposicin auto contenida y
concisa del mismo
-
UNIVERSIDAD NACIONAL ABIERTA 1
CAPTULO I
Los algoritmos genticos
1.1. Breve acercamiento a la biologa gentica
Se denomina gen la porcin o seccin particular de un cromosoma1 que contiene las
instrucciones o el material necesario para que un ser vivo presente un rasgo especfico (por
ejemplo: color del cabello, estatura, color de los ptalos, produccin de las protenas, color
de la piel, etc.). Un gen est siempre localizado en la misma parte de un cromosoma
determinado, y a este sitio se le denomina locus (del latn lugar).
Debido a que los cromosomas estn ubicados en parejas, en cada uno de los
cromosomas homlogos estn presentes los mismos genes, pero cada cromosoma puede
presentar una variante de estos genes. A cada una de las variantes o formas alternativas de
un gen se le llama alelo, y cada alelo se ubica siempre en el mismo locus dentro del
cromosoma.
La evolucin se puede definir como los cambios en el pool o conjunto gentico de
una poblacin. Segn los informticos evolucionistas, la evolucin optimiza a la naturaleza,
puesto que va creando seres cada vez ms perfectos, cuya cumbre es el hombre. Indicios
adicionales de esta optimizacin se encuentran en el organismo de los animales, desde el
tamao y tasa de ramificacin de las arterias, diseados para maximizar el flujo de sangre,
hasta el conjunto de reacciones del metabolismo, diseado para maximizar la cantidad de
energa extrada de los alimentos.
1 Cromosoma: Elemento que existe en el ncleo de las clulas en el momento de su divisin o mitosis.
-
UNIVERSIDAD NACIONAL ABIERTA 2
Los mecanismos de cambio en la evolucin alteran la proporcin de un tipo
determinado de alelos en una poblacin especfica, bien sea disminuyendo la variabilidad de
los mismos o aumentndola.
Los principales mecanismos que disminuyen la variabilidad son los siguientes:
Seleccin natural: Mecanismo mediante el cual los individuos que tengan algn
rasgo que los haga menos vlidos para realizar su tarea de seres vivos, no llegan a
reproducirse, y, por tanto, su patrimonio gentico desaparece del pool; incluso algunos de
ellos ni siquiera llegan a nacer.
Deriva gnica: El simple hecho de que un alelo sea ms comn que otro en la
poblacin, causa que la proporcin de alelos de esta poblacin vaya aumentando en una
poblacin aislada (efecto fundador).
Los ms importantes mecanismos que aumentan la variabilidad, los cuales suceden
generalmente en el mbito molecular, son los siguientes:
Mutacin: Es una alteracin del cdigo gentico que puede suceder por mltiples
razones y que se presenta en la naturaleza con una probabilidad muy baja de ocurrencia.
Por generar nuevos individuos, es considerada el motor de la evolucin. En el proceso de
formacin del ser humano, la enzima ADN polimerasa es la sustancia motivadora de
cambios.
Poliploida: Las clulas normales poseen dos copias de cada cromosoma (diploide)
y las clulas reproductivas una copia (haploides), sin embargo, puede suceder por accidente
que alguna clula reproductiva tenga dos copias cada una, en tal caso, si se lograra
combinar con otra clula diploide o haploide dar lugar a un ser vivo con varias copias de
cada cromosoma (poliploide). La mayora de las veces, la poliploida da lugar a individuos
con algn defecto gentico (por ejemplo, el tener 3 copias del cromosoma 21 da lugar al
Sndrome de Down), aunque en algunos casos se crean individuos viables. Un caso
conocido de mutacin fue el producido en el mosquito culex pipiens, en el cual se duplic un
gen que generaba una enzima que rompa los organofosfatos, componentes habituales de
los insecticidas.
-
UNIVERSIDAD NACIONAL ABIERTA 3
Recombinacin: Cuando dos clulas sexuales o gametos2, una masculina y otra
femenina se combinan, los cromosomas de cada una de ellas tambin lo hacen,
intercambindose genes, que a partir de ese momento pertenecern a un cromosoma
diferente. A veces tambin se produce traslocacin dentro de un cromosoma: una secuencia
de cdigo se elimina de un sitio y aparece en otro sitio del cromosoma, o en otro
cromosoma.
Flujo gentico: Es un intercambio de material gentico entre seres vivos de
diferentes especies que suelen ser virus o bacterias. Normalmente este intercambio se
produce a travs de un vector mediante el cual incorporan a su material gentico genes
procedentes de una especie a la que infectan y a su vez cuando infectan a un individuo de
otra especie pueden transmitirle sus genes a los tejidos generativos de gametos.
De este conjunto de mecanismos, la seleccin natural acta sobre el fenotipo y suele
disminuir la diversidad, haciendo que sobrevivan slo los individuos ms aptos; los
mecanismos que generan diversidad al combinar caractersticas actan habitualmente sobre
el genotipo.
Aunque los detalles de la evolucin no han sido completamente comprendidos,
incluso hoy, existen algunas premisas en los que se fundamentan:
La evolucin es un problema que opera a nivel de cromosomas, y no a nivel de individuos. Cada individuo es codificado como un conjunto de cromosomas.
La seleccin natural es el mecanismo mediante el cual los individuos mejor adaptados son los que tienen mayores posibilidades de reproducirse.
El proceso evolutivo tiene lugar en la etapa de la reproduccin. Sin embargo, los genetistas y los bilogos evolucionistas afirman que la evolucin no
slo optimiza, sino que tambin adapta localmente en el espacio y en el tiempo; en cierto
sentido, evolucin significa progreso. Un organismo ms evolucionado puede estar en
desventaja competitiva con uno de sus antepasados, si se colocan en el ambiente de estos
ltimos.
2 Gameto: Clula reproductiva, masculina o femenina, cuyo ncleo slo contiene n cromosomas
-
UNIVERSIDAD NACIONAL ABIERTA 4
1.2. Historia furtiva
1.2.1. De la teora de la evolucin
La hiptesis de la teora de la evolucin, la cual se basa en que pequeos cambios
heredables en los seres vivos y la seleccin natural son los dos hechos que provocan los
cambios en la naturaleza y la generacin de nuevas especies; fue descrita, aun
desconociendo cual era la base de la herencia, por Charles Darwin (1859) en su libro El
Origen de las Especies y presentada junto con Wallace, quien lleg a las mismas
conclusiones de forma independiente.
El seor Darwin pensaba que los rasgos de un ser vivo eran como un fluido, y que
los elementos de los dos padres se mezclaban de manera continua en la descendencia; la
debilidad de esta hiptesis estaba en que al cabo de cierto tiempo una poblacin
determinada tendra los mismos rasgos intermedios.
En estudio publicado en la revista estadounidense Science (2006), se confirma que
la reconstruccin del proceso de evolucin de la mecnica molecular por etapas satisface los
principios de la teora de la evolucin de Charles Darwin, lo cual demuestra la validez actual
de este planteamiento (Vase Anexo 1).
Quien descubri que los caracteres se heredaban en forma discreta, y que se
tomaban del padre o de la madre, dependiendo de su carcter dominante o recesivo, fue el
monje agustino Gregor Mendel (1864) a travs de experimentos realizados con arvejas para
intentar responder algunas interrogantes del problema de la herencia.
Las teoras de Mendel, quien trabaj en total aislamiento, se olvidaron y no se
volvieron a redescubrir hasta principios del siglo XX. En 1902 el norteamericano Walter
Sutton y el alemn Theodor Bover, cada uno por su cuenta, advirtieron que el
comportamiento de los cromosomas durante la meiosis3 tena una conducta paralela con la
de los factores mendelianos en la transmisin de la herencia.
3 Meiosis: Divisin celular mediante la cual una clula reproductora diploide (con cromosomas homlogos) se divide en cuatro clulas haploides (los cromosomas no tienen parejas y la informacin gentica no est por
-
UNIVERSIDAD NACIONAL ABIERTA 5
W. Sutton y T. Bover (1902) concluyeron que los factores hereditarios de que
hablaba Mendel se encuentran localizados en los cromosomas, en el interior del ncleo
celular. Este es el enunciado fundamental de la teora cromosmica de la herencia.
A partir de este hallazgo, se consider que los factores hereditarios tenan una
localizacin muy especfica en el cromosoma y que al separarse cada uno de los
cromosomas homlogos, se estaban separando por consiguiente los dos factores
encargados de un rasgo determinado.
1.2.2. De los algoritmos genticos
El inicio de los estudios de lo que hoy podra llamarse algoritmos genticos se
present a finales de los aos 50 y principios de los 60, en manos de bilogos evolucionistas
que buscaban la explicacin de los modelos de comportamiento de la evolucin natural,
mediante la optimizacin.
En 1965; Ingo Rechenberg, profesor de la Universidad Tcnica de Berln, introdujo
una tcnica que llam estrategia evolutiva, en la que no haba poblacin ni cruzamiento:
cada padre mutaba para producir un descendiente y se conservaba el mejor de los dos,
convirtindose en el padre de la siguiente ronda de mutacin. Versiones posteriores de esta
tcnica introdujeron la idea de poblacin.
En 1966; L.J. Fogel, A.J. Owens y M.J. Walsh introdujeron en Norte Amrica una
tcnica que se llam programacin evolutiva. En este mtodo, las soluciones candidatas
para los problemas se representaban como mquinas de estado finito sencillas; y al igual
que en la estrategia evolutiva de Rechenberg, el algoritmo funcionaba mutando
aleatoriamente dos mquinas simuladas y conservando la mejor de las dos.
A finales de la dcada de los aos 60; John Holland, siendo investigador de la
Universidad de Michigan, desarroll una tcnica que permiti incorporar la seleccin natural
a un programa. Luego de estudios a travs de los cuales comprendi que la evolucin es
una forma de adaptacin ms potente que el aprendizaje, tom Holland la decisin de
duplicado). Durante tal proceso, cada par de cromosomas homlogos presentes originalmente en la clula reproductora se separan y cada clula hija resultante contiene slo uno de cada dos cromosomas homlogos.
-
UNIVERSIDAD NACIONAL ABIERTA 6
aplicar sus ideas sobre el tema para desarrollar programas adaptados a un fin especfico. En
el curso que dictaba en la mencionada universidad, denominado Teora de Sistemas
Adaptativos, con la participacin de los estudiantes surgieron las ideas embrionarias de lo
que se convertira definitivamente en los algoritmos genticos.
Los objetivos de la investigacin de John Holland fueron los siguientes:
a. Imitar los procesos adaptativos de los sistemas naturales y
b. Disear sistemas artificiales (normalmente programas) que retengan los
mecanismos ms importantes de los sistemas naturales.
Ms tarde David Goldberg (1989), alumno de Holland, fue pionero en tratar de
aplicar los algoritmos genticos a problemas industriales, logrando resultados favorables.
El gran objetivo de Holland era lograr que las computadoras aprendieran por s
mismas, tcnica que l invent y denomin originalmente planes reproductivos, conocida
de manera popular bajo el nombre de algoritmo gentico despus de la publicacin de su
libro en 1975.
Como se observa, el motor de todos los elementos relacionados con los algoritmos
genticos se haya alimentado en la simple y poderosa idea de Charles Darwin: El azar en la
variacin, junto con la ley de seleccin, es una tcnica de resolucin de problemas de gran
complejidad y de aplicacin casi ilimitada.
Por ltimo, es importante sealar que los algoritmos genticos se utilizan para
abordar una amplia variedad de problemas en un conjunto de campos sumamente diversos,
demostrando claramente su capacidad y potencialidad. Dentro de sus mltiples aplicaciones
en diversas reas, una pequea muestra de stas, se encuentra en los siguientes ejemplos:
1) Diseo de salas de concierto con propiedades acsticas ptimas (Acstica).
2) Diseo de la forma del ala de un avin supersnico (Ingeniera
aeroespacial).
3) Produccin de curvas ajustadas a los datos en el problema de la curva de
rotacin galctica (Astronoma y Astrofsica).
4) Diseos de frmacos, en la llamada qumica combinatoria (Qumica).
-
UNIVERSIDAD NACIONAL ABIERTA 7
5) Construccin de placas especiales de circuitos reconocedores de voz
(Ingeniera elctrica).
6) Prediccin del rendimiento futuro de acciones (Mercados financieros).
7) Evolucin de redes neuronales que pudieran jugar damas (Juegos).
8) Utilizacin para los hipocentros de los terremotos, basndose en datos
sismolgicos (Geofsica).
9) Diseo de polmeros conductores de electricidad basados en el carbono,
conocidos como polianilinas (Ingeniera de materiales).
10) Descubrimiento de una regla para el problema de clasificacin por mayora
en autmatas celulares de una dimensin (Matemtica y algoritmia).
11) Evolucin de planes tcticos para las batallas militares (Ejrcito y
cumplimiento de la ley).
12) Deteccin de la presencia de ciertas sustancias en el exterior de la clula o
transportarla hacia el interior de sta (Biologa nuclear).
13) Evolucin de un complejo sistema de reconocimiento de patrones con una
amplia variedad de usos potenciales (Reconocimiento de patrones y
explotacin de datos).
14) Promocin de nuevas tecnologas en el campeonato anual de ftbol entre
equipos de robots autnomos (Robtica).
15) Diseo de horarios de los exmenes universitarios (Diseo de rutas y
horarios).
16) Diseo de molinos elicos para generar energa elctrica, mediante tarea
multiobjetivos (Ingeniera de sistema).
1.3. Aspectos bsicos de los algoritmos genticos
Se presenta en este aparte, un conjunto de factores bsicos requeridos para poder
abordar la tcnica de optimizacin mediante la aplicacin de los algoritmos genticos, los
cuales irn acompaados de ejemplos sencillos que permitan comprender su proceso.
-
UNIVERSIDAD NACIONAL ABIERTA 8
Los algoritmos genticos son mtodos de bsqueda y optimizacin basados en la
teora de la evolucin de Charles Darwin, los cuales constituyen uno de los focos de mayor
atractivo para los investigadores de las diversas ramas del saber.
El mtodo de bsqueda est basado en los mecanismos de seleccin que utiliza la
naturaleza para que los individuos ms aptos de una poblacin sobrevivan, debido a su
capacidad para adaptarse ms fcilmente a los cambios que se producen en su entorno.
Estos cambios que se efectan en los genes de un individuo y cuyos atributos son
transmitidos a sus descendientes cuando stos se reproducen sexualmente.
John Koza (1992), profesor de la Universidad de Stanford, propone la siguiente
definicin de algoritmo gentico:
Es un algoritmo matemtico altamente paralelo que transforma un conjunto de objetos matemticos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproduccin y supervivencia del ms apto, y tras haberse presentado de forma natural una serie de operaciones genticas de entre las que se destaca la recombinacin sexual. Cada uno de estos objetos matemticos suelen ser una cadena de caracteres (letras o nmeros) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta funcin matemtica que refleja su aptitud. Los algoritmos genticos estn enmarcados junto con la programacin evolutiva, las
estrategias evolutivas, los sistemas clasificadores y la programacin gentica dentro una
rama de la computacin denominada computacin evolutiva. Las bases biolgicas de estos
algoritmos y sus diferencias se centran en los operadores que utilizan en sus procesos.
En la lista siguiente indican de las tcnicas mencionadas anteriormente y sus
respectivos objetivos:
Nombre de la tcnica Objetivo
Algoritmo gentico Individuo ptimo
Programacin gentica Programa ptimo
Programacin evolutiva Operador gentico ptimo
Estrategia Evolutiva Aprendizaje ptimo
Sistema clasificador Poblacin ptima
-
UNIVERSIDAD NACIONAL ABIERTA 9
1.4. Operacionalidad de los algoritmos genticos simples
1.4.1. Caractersticas de los algoritmos genticos simples
La aplicacin ms comn de los algoritmos genticos simples (AGS) ha sido la
solucin de problemas de optimizacin, donde han mostrado alta eficiencia y gran
confiabilidad. Sin embargo no todos los problemas son apropiados para ser resueltos por
esta tcnica; las siguientes caractersticas son fundamentales para su aplicacin:
El espacio de bsqueda (sus posibles soluciones) debe estar delimitado dentro de un cierto rango.
Se debe definir una funcin de aptitud que indique qu tan buena o mala es la adaptacin de los individuos.
Las posibles soluciones se codifican utilizando el cdigo binario (0s y 1s).
El espacio de bsqueda debe ser siempre discreto (aunque sea muy grande). Sin
embargo, tambin podr intentarse usar la tcnica con espacios de bsqueda continuos,
cuando exista un rango relativamente pequeo.
La funcin de aptitud (o alguna modificacin de sta) es la funcin objetivo del
problema de optimizacin tratado. El resultado que produce sta es un nmero real,
preferiblemente no negativo que a mayor resultado es mejor la solucin. El algoritmo
gentico nicamente maximiza, pero la minimizacin puede realizarse fcilmente utilizando
el reciproco de la funcin maximizante, siempre que el mismo est determinado. Una
caracterstica que debe presentar la funcin es que tiene que ser capaz de castigar a las
malas soluciones y de premiar a las buenas, de forma que sean estas ltimas las que se
propaguen con mayor rapidez.
Dentro del conjunto de ventajas y desventajas manifiestas en la tcnica de bsqueda
y optimizacin mediante el uso de los algoritmos genticos simples, podemos mencionar las
siguientes:
Ventajas:
-
UNIVERSIDAD NACIONAL ABIERTA 10
a. No necesitan conocimientos especficos sobre el problema que intentan
resolver, en particular si la funcin es regular.
b. Operan de forma simultnea con varias soluciones, en vez de trabajar de
forma secuencial como las tcnicas tradicionales.
c. Cuando se usan para problemas de optimizacin (maximizar una funcin
objetivo) resultan menos afectadas por los mximos locales (aparentes
soluciones) que las tcnicas tradicionales.
Esta importante ventaja servir de plataforma para el desarrollo de las pruebas
empricas, que permitirn demostrar su potencialidad, la cual constituir el objetivo
principal de esta monografa.
d. Resulta sumamente fcil ejecutarlos en las modernas arquitecturas
masivamente paralelas.
e. Usan operadores probabilsticos, en vez de los tpicos operadores
determinsticos de las otras tcnicas.
Desventajas:
a. Es difcil determinar la velocidad de convergencia (o an la convergencia),
dependiendo en cierta medida de los parmetros que se utilicen (tamao de
la poblacin, nmero de generaciones, nivel de precisin deseado, etc.).
b. Pueden converger prematuramente debido a una serie de problemas
relacionados con los valores de sus parmetros.
Dado un problema especfico a resolver, la entrada del algoritmo gentico simple
representa un conjunto de soluciones potenciales del mismo, codificadas mediante el
alfabeto binario y una mtrica llamada funcin de aptitud que permite evaluar
cuantitativamente a cada candidata. Estas candidatas pueden ser soluciones factibles, con
el objetivo de que el AGS las mejore, pero se suelen generar aleatoriamente.
-
UNIVERSIDAD NACIONAL ABIERTA 11
1.4.2. Ejecucin del proceso de los algoritmos genticos simples
Los pasos que se ejecutan en el proceso de aplicacin de los algoritmos genticos
simples para la simulacin sucinta de la evolucin natural, se presentan en el siguiente
diagrama:
-
Diagrama de flujos del proceso del algoritmo gentico simple
UNIVERSIDAD NACIONAL ABIERTA 12
si
no
si
no
Generar un conjunto aleatorio de N soluciones factibles
Calificar cada solucin factible (aplicar la funcin de aptitud)
Seleccionar dos individuos de acuerdo a su calificacin
Cruzar o mezclar los cdigos genticos de los dos individuos seleccionados
Mutar algunos elementos del cdigo gentico de ciertos individuos
Incluir a los dos nuevos en una nueva poblacin
Condicin de finalizar?
La nueva Poblacin tiene N individuos?
A
Denominarla poblacin actual
Fin
B
B
A
Codificar el dominio del problema
-
UNIVERSIDAD NACIONAL ABIERTA 13
1.4.3. Operadores genticos
Los operadores genticos de mayor uso en la aplicacin de los algoritmos genticos
simples son descritos brevemente y adems utilizados en los casos prcticos a desarrollar el
siguiente captulo.
a. Seleccin
Dado el conjunto de individuos de la poblacin actual con una probabilidad
proporcional a su calificacin, la operacin de seleccin consiste en elegir dentro del
mencionado conjunto, a los individuos mejor adaptados al medio en trminos del resultado
de la funcin de aptitud.
Entre las mltiples formas de seleccin comnmente utilizadas cabe mencionar a las
siguientes: seleccin proporcional a la aptitud, seleccin por rueda de ruleta, seleccin
elitista, seleccin escalada, seleccin por torneo, seleccin por rango, seleccin
generacional, seleccin por estado estacionario, seleccin jerrquica.
Para el caso del algoritmo gentico simple, la seleccin de mayor popularidad es la
seleccin proporcional a la aptitud equivalente a la seleccin por rueda de ruleta.
b. Cruce
Cruzar o mezclar los cdigos genticos de dos individuos seleccionados como
padres para generar hijos que posean cdigos mixtos.
Este operador gentico tambin tiene varias acepciones, debido a que existen
muchas formas de hacerlo, sin embargo, para nuestro caso utilizaremos el cruzamiento de
un punto (1-point crossover) el cual se escoge al azar.
1. Mediante el Proceso de Bernoulli4 (con probabilidad pc de xito).
2. Si ocurre un xito cruzar o mezclar los cdigos de los dos individuos
seleccionados para formar dos sujetos mixtos, a los que llamaremos nuevos
individuos.
4 Un experimento de Bernoulli es aquel en el que pueden ocurrir exclusivamente dos eventos posibles, uno con probabilidad de xito pc y otro con probabilidad de fracaso 1-pc).
-
3. Si ocurre un fracaso llamamos a los individuos seleccionados nuevos
individuos.
Grficamente el operador gentico de cruzamiento de un punto (1-point
crossover), con punto de cruce en la tercera posicin del cromosoma, es como sigue:
Puntos de Cruce
Padres 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0
Descendientes 1 0 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 1
c. Mutacin Mutar o alterar deliberadamente algunos elementos del cdigo de ciertos individuos,
los cuales se seleccionan aleatoriamente, para as generar nuevos individuos ubicados en
regiones del problema no exploradas an.
1. Por cada bit de cada nuevo individuo, mediante el Proceso de Bernoulli (con
probabilidad pm de xito).
2 Si ocurre un xito cambiar el bit en turno por su complemento.
3 Si ocurre un fracaso el bit permanece inalterado.
Grficamente el operador gentico de mutacin como sigue:
UNIVERSIDAD NACIONAL ABIERTA 14
Los
parmetros del algoritmo gentico que deben ser tomados en cuenta al realizar un ensayo
emprico son: los valores de probabilidad para los operadores reproduccin, cruce y
mutacin, el tamao de la poblacin, el nmero de generaciones, la precisin deseada y el
1 1 1 0 1 0 1 0 0 1 1 0 Descendiente
1 1 1 0 1 1 1 0 0 1 1 0 Descendiente mutado
gen mutado
-
UNIVERSIDAD NACIONAL ABIERTA 15
tipo de seleccin a utilizar. Adems, es necesario establecer el rango o el intervalo de
bsqueda y la codificacin de la funcin objetivo.
Los parmetros empricos recomendables para el algoritmo gentico simple se
sealan a continuacin:
Nmero de generaciones 57
Tamao de la poblacin 47
Probabilidad de cruce 0,60
Probabilidad de mutacin 0,03
Seleccin ruleta
La convergencia del algoritmo gentico simple, se apoya en el siguiente enunciado
Siendo que el algoritmo gentico simple opera con una poblacin en cada iteracin, es de
esperarse que el mtodo, al final del proceso, de cmo resultado que la mayora de los
individuos de la poblacin sean muy similares, y que en el infinito todos sean iguales.
La teora para estudiar la convergencia de estos algoritmos en caso de cadenas
binarias, se basa principalmente en considerar que una cadena es un representante de una
clase de equivalencia o esquema.
John Holland, con el Teorema los Esquemas, intenta dar respuesta a que si existe
una manera matemtica que indique como se afectar a la siguiente generacin en el
proceso evolutivo, el cual depende de la seleccin, cruce y mutacin. A partir de los
resultados, el Teorema de los Esquemas (Teorema Fundamental), prueba que la poblacin
converge a unos esquemas que cada vez son ms parecidos, y en el lmite a una cadena
nica.
El mencionado teorema ha sido cuestionado por muchos matemticos, sin embargo
el tiempo ha permitido avances importantes al respecto, lo cual da robustez al mismo.
1.4.4. Ejemplo manual de optimizacin numrica mediante el AGS
-
Para la funcin ( ) 2xxf =
Usando un algoritmo gentico simple con probabilidad de cruce pC = 0,60 y
probabilidad de mutacin pM = 0.03333, para 5 generaciones, con seleccin por torneo (este
mecanismo de seleccin es distinto al utilizado en el Anexo 2, se indica slo a manera de
ilustracin).
Se desea encontrar el valor de x que hace que la funcin f(x) alcance su valor
mximo, siendo el rango de la variable x los valores enteros comprendidos entre 0 y 31.
Sabemos que el mximo se alcanza en x = 31, donde f vale 961.
Lo primero que debemos hacer es codificar las posibles soluciones (posibles valores
de x). Lo haremos con la codificacin binaria. Esto es (0,0,0,0,0) equivale a x = 0 y que
(1,1,1,1,1) equivale a x = 31.
Cada posible valor de la variable x en representacin binaria se le denomina
individuo. Una coleccin de individuos constituye lo que se denomina poblacin y el nmero
de individuos que la componen es el tamao de la poblacin. Una vez que tenemos
codificada la solucin, debemos escoger un tamao de poblacin. Para este ejemplo vamos
a escoger 6 individuos.
Debemos partir de una poblacin inicial. Una manera de generarla aleatoriamente,
puede ser lanzando una moneda al aire; si sale cara, la primera componente del primer
individuo es un 0 y en caso contrario es un 1. Se repite el lanzamiento de la moneda y
tendremos la segunda componente del primer individuo (un 0 si sale cara y un 1 si sale
sello). As hasta 5 veces y se obtendr el primer individuo. Se repite la secuencia anterior
para generar los individuos restantes de la poblacin. En total se realizan 5 * 6 = 30
lanzamientos de la moneda.
Iteracin 1
UNIVERSIDAD NACIONAL ABIERTA 16
-
UNIVERSIDAD NACIONAL ABIERTA 17
El siguiente paso es hacer competir a los individuos entre s. Que utilizaremos en
nuestro caso como un proceso de seleccin. En la tabla 1 se resume este paso.
Tabla 1.- SELECCIN N del individuo Poblacin inicial Valor de X Valor de F(x) Pareja asignada
1 (0,1,1,0,0) 12 144 6
2 (1,0,0,1,0) 18 324 3
3 (0,1,1,1,1) 15 225 2
4 (1,1,0,0,0) 24 576 5
5 (1,1,0,1,0) 26 676 4
6 (0,0,0,0,1) 1 1 1
Como de observa en la tabla precedente, el mejor individuo es el 5 (f(5) = 676). Al
Calcular la media de f resulta fmed = 324,33. Ahora bien, una manera de realizar el proceso
de seleccin es mediante un torneo entre dos. A cada individuo de la poblacin se le asigna
una pareja y entre ellos se establece un torneo: el mejor genera dos copias y el peor se
descarta. En la ltima columna se indica la pareja asignada a cada individuo, lo cual se ha
realizado aleatoriamente. Es importante resaltar, como se dijo anteriormente, que existen
muchas variantes de este proceso de seleccin.
Despus de realizar el proceso de seleccin, la poblacin que tenemos es la
mostrada en la columna 2 de la tabla 2. Observamos, por ejemplo, que en el torneo entre el
individuo 1 y el 6 de la poblacin inicial, el primero de ellos ha recibido dos copias, mientras
que el segundo no es tomado en cuenta. Este proceso se repite hasta completar la tabla 2
que sigue:
Tabla 2.- CRUCE N del individuo Poblacin 1 Pareja asignada
1 (0,1,1,0,0) 5
2 (1,0,0,1,0) 3
3 (1,0,0,1,0) 2
4 (1,1,0,1,0) 6
5 (1,1,0,1,0) 1
6 (0,1,1,0,0) 4
Tras realizar la seleccin, se realiza el cruce. Que en este caso lo haremos mediante
el cruce de un punto, esto es: se forman parejas entre los individuos aleatoriamente de
-
UNIVERSIDAD NACIONAL ABIERTA 18
forma similar a la seleccin. Dados dos individuos pareja, que se van ha cruzar, se establece
un punto de cruce aleatorio, que no es ms que un nmero aleatorio entre 1 y 4 (la longitud
del individuo menos 1). Por ejemplo, en la pareja 2-3 el punto de cruce es 3, lo que significa
que un hijo de la pareja conserva los tres primeros bits de la pareja 2 y hereda los dos
ltimos de la pareja 3, mientras que el otro hijo de la pareja conserva los tres primeros bits
de la pareja 3 y hereda los dos ltimos de la pareja 2. La poblacin resultante se muestra en
la columna (2) de la tabla 3. Cabe destacar que en el ensayo en todas las parejas se efectu
el cruce y el individuo 2 sufri una mutacin en el bit 3.
Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIN N del individuo Poblacin 1 Valor de X Valor de F(x)
1 (0,1,1,1,0) 14 196
2 (1,0,1,1,0) 22 484
3 (1,0,0,1,0) 18 324
4 (1,1,0,0,0) 24 576
5 (1,1,0,0,0) 24 576
6 (0,1,1,1,0) 14 196
Ahora el valor mximo de f es 576 (para los individuos 4 y 5), mientras que antes de
la seleccin, el cruce y la mutacin era de 676. Aunque el mximo individual disminuy, se
observa que fmed ha escalado de 324,3 a 392, significa que la poblacin despus de la
seleccin, el cruce y la mutacin es mejor que antes de estas transformaciones.
El siguiente paso es volver a realizar la seleccin, el cruce y la mutacin tomando
como poblacin inicial la de la tabla 3. Esta manera de proceder se repetir hasta construir 5
generaciones y como el resultado ser la mejor solucin de la ltima iteracin, aunque
tambin se puede ir guardando la mejor solucin de todas las iteraciones anteriores y al final
tomar la mejor solucin. En realidad un algoritmo gentico no garantiza la obtencin del
ptimo pero, si est bien construido, proporcionar una solucin razonablemente buena.
Puede ocurrir tambin que se obtenga el ptimo, pero el algoritmo no tiene capacidad para,
en ese momento, detener el proceso y dar informacin del resultado.
Iteracin 2
-
UNIVERSIDAD NACIONAL ABIERTA 19
Repitiendo todo el proceso indicado para la construccin de la pareja asignada, nos
resulta la siguiente tabla poblacional donde aplicaremos el operador de seleccin tal como
se hizo en la iteracin 1:
Tabla 1.- SELECCIN N del individuo Poblacin 2 Valor de X Valor de F(x) Pareja asignada
1 (0,1,1,1,0) 14 196 3
2 (1,0,1,1,0) 22 484 2
3 (1,0,0,1,0) 18 324 4
4 (1,1,0,0,0) 24 576 5
5 (1,1,0,0,0) 24 576 6
6 (0,1,1,1,0) 14 196 1
Despus del proceso de seleccin tenemos a continuacin la tabla de cruce para la
iteracin 1:
Tabla 2.- CRUCE N del individuo Poblacin 2 Pareja asignada
1 (1,0,0,1,0) 5
2 (1,0,1,1,0) 6
3 (1,1,0,0,0) 3
4 (1,1,0,0,0) 4
5 (1,1,0,0,0) 1
6 (0,1,1,1,0) 2
Aplicando los operadores genticos de cruce y mutacin, nos resulta la siguiente
tabla poblacional. Cabe destacar que en el ensayo en todas las parejas se efectu el cruce y
ningn individuo sufri una mutacin.
Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIN
N del individuo Poblacin 2 Valor de X Valor de F(x)
1 (1,0,0,0,0) 16 256
2 (1,0,1,1,0) 22 484
3 (1,1,0,1,0) 26 676
4 (1,1,0,0,0) 24 576
5 (1,1,0,1,0) 26 676
6 (0,1,1,1,0) 14 196
Ahora el valor mximo de f es 676 (para los individuos 3 y 5), que era el mximo en
la poblacin inicial, se observa que fmed ha aumentado de 392 a 473,33, nuevamente se
-
UNIVERSIDAD NACIONAL ABIERTA 20
evidencia que la poblacin va mejorando a medida que se le aplican los operadores
genticos a sus individuos.
Repitiendo el proceso anterior, los resultados de las iteraciones restantes son los
siguientes:
Iteracin 3
Tabla 1.- SELECCIN N del individuo Poblacin 3 Valor de X Valor de F(x) Pareja asignada
1 (1,0,0,0,0) 16 256 3
2 (1,0,1,1,0) 22 484 6
3 (1,1,0,1,0) 26 676 2
4 (1,1,0,0,0) 24 576 5
5 (1,1,0,1,0) 26 676 4
6 (0,1,1,1,0) 14 196 1
Tabla 2.- CRUCE N del individuo Poblacin 3 Pareja asignada
1 (1,1,0,1,0) 5
2 (1,0,1,1,0) 4
3 (1,1,0,1,0) 3
4 (1,1,0,1,0) 2
5 (1,1,0,0,0) 1
6 (1,0,0,0,0) 6
Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIN
N del individuo Poblacin 3 Valor de X Valor de F(x)
1 (1,1,0,0,0) 24 576
2 (1,0,1,1,0) 20 400
3 (1,1,0,1,0) 26 676
4 (1,1,0,1,0) 24 576
5 (1,1,0,1,0) 26 676
6 (1,0,0,0,0) 16 256
En las parejas 3 y 6 se efectu el cruce y ningn individuo sufri una mutacin.
El valor mximo de f es 676 (individuos 3 y 5) y fmed ha aumentado de 473,33 a
500.
-
UNIVERSIDAD NACIONAL ABIERTA 21
Iteracin 4
Tabla 1.- SELECCIN N del individuo Poblacin 4 Valor de X Valor de F(x) Pareja asignada
1 (1,1,0,0,0) 24 576 2
2 (1,0,1,0,0) 20 400 1
3 (1,1,0,1,0) 26 676 6
4 (1,1,0,0,0) 24 576 5
5 (1,1,0,1,0) 26 676 3
6 (1,0,0,1,0) 18 196 4
Tabla 2.- CRUCE
N del individuo Poblacin 4 Pareja asignada
1 (1,1,0,0,0) 6
2 (1,1,0,0,0) 4
3 (1,1,0,1,0) 5
4 (1,1,0,1,0) 2
5 (1,1,0,1,0) 3
6 (1,1,0,0,0) 1
Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIN
N del individuo Poblacin 4 Valor de X Valor de F(x)
1 (1,1,0,0,0) 24 576
2 (1,1,0,0,0) 24 576
3 (1,1,0,1,0) 26 676
4 (1,1,0,0,0) 26 676
5 (1,1,0,1,0) 26 676
6 (1,0,0,1,0) 18 324
En todas las parejas se efectu el cruce y ningn individuo sufri una mutacin.
El valor mximo de f es 676 (individuos 3, 4 y 5) y fmed ha aumentado de 500 a 584.
Iteracin 5
Tabla 1.- SELECCIN N del individuo Poblacin 5 Valor de X Valor de F(x) Pareja asignada
-
UNIVERSIDAD NACIONAL ABIERTA 22
1 (1,1,0,0,0) 24 576 5
2 (1,1,0,0,0) 24 576 4
3 (1,1,0,1,0) 26 676 1
4 (1,1,0,0,0) 26 676 3
5 (1,1,0,1,0) 26 676 6
6 (1,0,0,1,0) 18 324 2
Tabla 2.- CRUCE N del individuo Poblacin 5 Pareja asignada
1 (1,1,0,1,0) 3
2 (1,1,0,1,0) 6
3 (1,1,0,1,0) 1
4 (1,1,0,1,0) 5
5 (1,1,0,1,0) 4
6 (1,1,0,0,0) 2
Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIN N del individuo Poblacin 5 Valor de X Valor de F(x)
1 (1,1,0,1,0) 26 676
2 (1,1,0,0,0) 24 576
3 (1,1,0,1,0) 26 676
4 (1,1,0,1,0) 26 676
5 (1,1,0,1,0) 26 676
6 (1,0,1,1,0) 22 484
En todas las parejas se efectu el cruce y el individuo 6 sufri una mutacin en el bit
3.
El valor mximo de f es 676 (individuos 1, 3, 4 y 5) y fmed ha aumentado de 584 a
627,33.
Como la condicin del proceso es finalizar en la quinta generacin, el algoritmo
gentico en este caso nos da como resultado que el mximo de la funcin para el intervalo
estudiado es 676; se evidencia la necesidad de seguir iterando, en este caso, porque
conocemos el valor mximo de la funcin. He aqu un problema real del algoritmo, que es la
tendencia a la homegeinizacin de la poblacin, es decir a que todos los individuos de la
misma sean idnticos. Esto impide que el algoritmo siga explorando nuevas soluciones, con
lo que podemos quedar estancados en un mximo local no muy bueno. Existen tcnicas
-
UNIVERSIDAD NACIONAL ABIERTA 23
para contrarrestar esta situacin. El mecanismo ms elemental, aunque no siempre
suficientemente eficaz, es introducir una mutacin tras la seleccin y el cruce. Una vez que
se ha realizado la seleccin y el cruce se selecciona un nmero determinado de bits de la
poblacin y se alteran aleatoriamente.
1.4.5. Cdigo fuente de un algoritmo gentico simple
Existen varios paquetes y bibliotecas de algoritmos genticos en el mercado, sin
embargo, de acuerdo a las caractersticas especficas de algn problema, se hace necesario
reimplementar todo el algoritmo, en vez de emplear algn paquete preexistente. Algunos de
esos paquetes son:
GALOPPS: Su direccin primaria en Internet es GARAGe.cps.msu.edu/software/software-index.html, y su direccin para descargarlo
va FTP es garage.cps.msu.edu/pub/GA/galopps/
GAGS: Generador de aplicaciones basadas en algoritmos genticos, escrito en C++. Desarrollado por el grupo de J.J. Melero. Excelente. Su direccin Web es kal-
el.ugr.es/gags.html, y su direccin para descargarlo va FTP es kal-el.ugr.es/GAGS/.
FORTRAN GA: Desarrollo de algoritmos genticos para Fortran. Su direccin Web es www.staff.uiuc.edu/~ carroll/ga.html.
Galib: Biblioteca de algoritmos genticos de Matthew. Conjunto de clases en C++ de algoritmos genticos. Su direccin Web es lancet.mit.edu/ga/, y su direccin para
descargarlo va FTP es lancet.mit.edu/pub/ga/. Podemos registrarlo en
http://lancet.mit.edu/ga/Register.html.
GAS: Paquete para desarrollar aplicaciones de algoritmos genticos en Python. Su direccin Web es starship.skyport.net/crew/gandalf, y su direccin para descargarlo
va FTP es ftp.coe.uga.edu/users/jae/ai.
GECO: Conjunto de herramientas para Lisp. Su direccin para descargarlo va FTP es ftp://ftp.aic.nrl.navy.mil/pub/galist/src/.
-
UNIVERSIDAD NACIONAL ABIERTA 24
GPdata: Para desarrollar algoritmos genticos en C++. Su direccin para descargarlo va FTP es ftp.cs.bham.ac.uk/pub/authors/W.B.Langdon/gp-code/, y su
documentacin -GPdata-icga-95.ps- la podemos encontrar en el site de Internet
cs.ucl.ac.uk/genetic/papers/.
gpjpp: Bibliotecas de clases para desarrollar algoritmos genticos en Java Su direccin Web es www.turbopower.com/~ kimk/gpjpp.asp.
GP Kernel: Biblioteca de clases para programacin gentica en C++. Su direccin Web es www.emk.e-technik.th-darmstadt.de/~ thomasw/gp.html.
lil-gp: Herramientas para programacin gentica en C. Su direccin Web es isl.msu.edu/GA/software/lil-gp/index.html, y su direccin para descargarlo va FTP es
isl.cps.msu.edu/pub/GA/lilgp/. Podemos encontrar los parches para Linux en
www.cs.umd.edu/users/seanl/patched-gp.
PGAPack: Parallel Genetic Algorithm Library. Biblioteca de algoritmos genticos paralelos. Podemos encontrarlo en la direccin de Internet con un navegador en
www.mcs.anl.gov/home/levine/PGAPACK/index.html, y su direccin para
descargarlo va FTP es ftp.mcs.anl.gov/pub/pgapack/.
Sugal: SUnderland Genetic ALgorithm system. Para hacer experimentos con algoritmos genticos. Podemos encontrarlo en la direccin de Internet con el
navegador en www.trajan-software.demon.co.uk/sugal.htm.
ADATE: Automatic Design of Algorithms Through Evolution. Programacin evolutiva. Su direccin Web es www-ia.hiof.no/~ rolando/adate_intro.html.
GPsys: Sistema de programacin gentica en Java. Podemos encontrarlo en la direccin de Internet www.cs.ucl.ac.uk/staff/A.Qureshi/gpsys.html.
En el Anexo 2 de esta monografa, se presenta el cdigo fuente del algoritmo
gentico simple, en lenguaje pascal, aplicado a la optimizacin de las funciones reales
de una y dos variables que fueron elegidas para ser estudiadas mediante esta
herramienta.
-
CAPTULO II
Mtodos clsicos de optimizacin numrica En el conjunto de mtodos clsicos de optimizacin numrica, existen dos grandes
grupos, que lo podemos denominar algoritmos para problemas con restricciones (que
requieren los valores de la funcin objetivo y el conjunto de restricciones) y algoritmos para
problemas sin restricciones (que requieren los valores de la funcin objetivo y los valores de
la o las derivadas de la funcin objetivo); en el primer grupo cabe mencionar el Mtodo
Simplex y en el segundo grupo, se ubican el Algoritmo del Gradiente con paso constante y el
Algoritmo de Newton con paso constante, stos, en nuestra opinin, es una buena
representacin de los mtodos de optimizacin clsicos considerados no heursticos, debido
a que la bsqueda de los puntos ptimos se realiza mediante estrategias que no dependen
de eventos aleatorios, lo cual los hace distintos al Algoritmo Gentico Simple, en cuanto a
sus mecanismos de funcionamiento.
Procederemos en las lneas subsiguientes a indicar y a describir brevemente la
rutina de los dos mtodos antes mencionados, que utilizan los algoritmos para problemas sin
restricciones, el cual es el tema que nos ocupa, a fin de tener una panormica de estas
alternativas de optimizacin numrica para comparar sus resultados con los obtenidos con la
aplicacin del algoritmo gentico simple.
2.1. Algoritmo del gradiente con paso constante
Este algoritmo es del tipo:
{ },/ doptimalidadenecesariacondicinunaverificaxIRx n=xk , en la iteracin k se calcula un punto
nkk
kk
k
dado
.
Se ha demostrado que si
k IRdIRtdondedtxx +=+ ,,1
( ) ( ) ( ) .0,/0tan0,, TtxftdxfTexistetolopordxfentoncesIRd n >
UNIVERSIDAD NACIONAL ABIERTA 25
-
Visto que el problema matemtico consiste en maximizar f(x) para , con f
continuamente diferenciable, es natural escoger en cada iteracin una direccin
nIRx
( ) 0, > kkk dxfquetald y la manera ms sencilla de hacerlo es tomando ( )kk xfd = .
Los algoritmos del gradiente escogen as dk en cada iteracin y por lo tanto difieren
entre s slo en la manera de determinar el nmero tk llamado paso, el cual junto con dk
define . Para todos los algoritmos del gradiente se tiene
kk
kk dtxx +=+1
( ){ }.0/ == xfIRx nEl algoritmo del gradiente con paso constante, es un algoritmo de bsqueda del valor
ptimo de una funcin objetivo, el cual tiene la siguiente estructura:
{ ( )}( )Inicio: Escoger 000 / xfxfxxquetalIRx n =)
es acotado,
( 1,0 , hacer k=0, ir a la iteracin k
Iteracin K paso 1: Calcular ( )kxf
paso 2: Si ( ) 0= kxf parar
si no, hacer ( ) ,1, == kk xfd ir al paso 3
paso 3: Calcular ( ) ( ) ( ) ( ) 22
, kkkkk xfxfdxfx +=
paso 4: Si ( ) ,0, kx hacer =kt ir al paso 5
si no, hacer = ir al paso 3
UNIVERSIDAD NACIONAL ABIERTA 26
-
paso 5: ir a la iteracin k ,1,1 +=+=+ kkdtxx kkkk
La siguiente proposicin se apoya en un supuesto vital para la operatividad de este
algoritmo:
Proposicin: Si f es dos veces continuamente diferenciable, si existen M>0, m>0 tales que
( ) nIRytodoparaymyxHyyM ,, 22 , para todo , donde H es la matriz hessiana de f, entonces cualquier sucesin infinita generada por el algoritmo a
partir de x
0xx
0 converge linealmente hacia un punto x* de . Adems
( ) ( ) ( ) ( )( ).1
21
, *0x21
2*0**
+=
=
Mm
Mmqy
xmMqCconCqxxxfxfqxfxf
kkkk
2.1.1. Ejemplo manual del algoritmo del gradiente con paso constante
Aplicar el AGPC para obtener algunos trminos de la sucesin que converge al valor ptimo
de ( )242
2221
21 xxxxxf += , con ( )0,1
43 0 == xy .
Tenemos que f es cncava y dos veces continuamente diferenciable. Como ( )210 =xf y
la curva de nivel ( )21=xf es una elipse, el conjunto ( ) ( ){ }00 / xfxfxX = es
convexo y compacto.
Adems ( )
=1
41
411
xH , los autovalores son -3/4 y -5/4
UNIVERSIDAD NACIONAL ABIERTA 27
-
UNIVERSIDAD NACIONAL ABIERTA 28
Por lo tanto ( ) 22 3,5 yyxHyy 44
, se deduce que la sucesin generada a partir
de converge hacia un punto de ( )0,10 =x . A continuacin se calculan algunos trminos de esta sucesin
Iteracin 0:
( ) ( ) ( ) ( )21,
1617,,
00
411
020000 ===
= xfxfxfdxf
( )
( ) 01617
21
21
3211,
321,
410
,1
0
00
-
( ) ( ) ( ) ( ) 002,0#,004,0#,,00
051,0031,0
# 222222 =
xfxfxfdxf
( )( )
( ) 0005,0#,025,0024,0
#
00015,0#1,
00015,0#,012,0016,0
#1
22
2
22
+==
+==
yfdxy
x
yfdxy
025,04
,0#43,2x
La solucin es
+= 024,0#3 223 dxx
( ) ( ) 0,0,0 ** == xfx . Aunque la sucesin converge rpidamente, se observa una gran influencia de los errores de redondeo cerca de la solucin en la
determinacin de ( ),x .
2.2. Algoritmo de Newton con paso constante
Los algoritmos del gradiente consideran la aproximacin lineal de la funcin objetivo
para determinar la direccin de desplazamiento. Sin embargo, si estamos cerca del punto
solucin, es decir si es pequeo o bien si f es estrictamente cncava, una
aproximacin cuadrti en torno a xk representa mejor el comportamiento de f, donde:
( )xfca F(x)
( ) ( ) ( ) ( ) ( )( )kkkkkk xxxHxxxxxfxfxF ++= ,2
, siendo H la matriz hessiana 1,
de f.
Si f es estrictamente cncava, F lo es tambin y alcanza su mximo en el punto x tal que
( ) ( )( ) ( ) ( ) ( )kkkkkkk xfxHxxregularesxHseaoxxxHxf ==+ ,,0 Por lo tanto en todo punto xk donde H(xk) es definida negativa, un desplazamiento a
partir de xk en la direccin ( ) ( )kkk xfxHd = 1 producir un crecimiento del valor de f ya que ( ) ( ) 0,, >= kkkkk ddxHdxf
UNIVERSIDAD NACIONAL ABIERTA 29
-
UNIVERSIDAD NACIONAL ABIERTA 30
Esta manera de determinar dk caracteriza lo
cada iteracin calculan xk+1 a partir de xk mediante
s algoritmos de Newton, los cuales en
( ) ( )kkkkk xfxHdcondtxx =+= , el mtodo de escoger el paso t
kk + 11 y slo difieren entre s en
ara to
k.
P dos los algoritmos de Newton, tenemos: ({ }) 0=x ,.bajo el supuesto ue f es al menos dos veces continuamente diferenciable y su matriz hessiana regular.
wton con paso constante se escribe as:
Inicio: Escoger
/= fIRx n
q
El algoritmo de Ne
nIRx 0 ( )1,0,21,0
(es conveniente tomar
( )8,0,5,0 , hacer k=0, ir a la r n ite aci k
cular
( )kxf Iteracin K paso 1: Cal
paso 2: Si ( ) 0= kxf parar si no, hacer ( ) ( )kkk xfxHd = 1 , hacer 1= , ir al paso 3
cula paso 3: Cal r ( ) ( ) ( ) ( ) kkkkkk dxfxfdxfx ,, += ,
paso 4: Si ( ) ,,0, k hacerx = kt ir al paso 5
si no, hacer = , ir a
paso 5 , k=k+1 ir a la iteracin k
l paso 3
kkkk dtxx +=+1
-
2.2.1. Ejemplo manual del algoritmo de Newton con paso constante Aplicar el ANPC para obtener algunos trminos de la sucesin que converge al valor ptimo
de ( )242
2221
21 xxxxxf += , con 4,07,0 == y .
En el ejemplo anterior vimos que ( )
=1
41
411
xH , tiene por autovalores -3/4 y
-5/4, por lo que sucesin generada por el algoritmo a partir de ( )0,10 =x converge.
Iteracin 0: ( ) ( )
=
=
=
141
411
,00
411
,01 0100 xHxfx
( ) ( ) ( ) ( )
UNIVERSIDAD NACIONAL ABIERTA 31
1,,21,
01 0000010 ==
== dxfxfxfxHd
( ) 0,00
,1 00 =
=+== yfdxy
( ) ( ) ( ) ( ) 01,0,4,01, 0000 >== dxfxfyfx Por lo tanto
=+=00001 dxx
Iteracin 1: parar. ( ) ,00
,00 11
=
= xfx
-
CAPTULO III
Ensayos de aplicacin del algoritmo gentico simple y de los mtodos clsicos en la optimizacin numrica
En este captulo vamos a maximizar la funcin 1)10(22 += xsenxy , en el
dominio [0, 2] y minimizar la funcin ( )
( )( )222222
001,01
5,05,0
yx
yxsenZ ++
++= , en el dominio
[-200, 200] X [-200, 200] mediante el algoritmo gentico simple, implementado en lenguaje
pascal a fin de comentar los resultados obtenidos.
3.1. Evaluacin de la funcin 1)10(22 += xsenxY en el dominio [0,2]
Iniciaremos el ensayo mencionando algunas caractersticas de esta funcin, cuyo
grfico se muestra en la figura N 1 que sigue:
5
UNIVERSIDAD NACIONAL ABIERTA 32
21.510.50
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
x
y
x
y
figura N 1 grfica de la funcin 1)10(22 += xsenxY Como se observa, esta funcin en el dominio de definicin, tiene una oscilacin
moderada con tendencia al aumento y manifiesta un incremento de su amplitud directamente
proporcional al incremento de la variable independiente. El mximo global se ubica muy
cerca de x = 2 y registra varios mximos locales, que se resaltan a partir de x = 1.
-
UNIVERSIDAD NACIONAL ABIERTA 33
En el Anexo 3 de este trabajo se detallan las herramientas computacionales
utilizadas para el desarrollo de este aparte y de otros donde se hizo necesario el uso de las
mismas.
3.1.1. Aplicacin del algoritmo gentico simple
Los parmetros para la corrida de la funcin que se intenta optimizar mediante el
algoritmo gentico simple son los que se detallan a continuacin:
Tamao del cromosoma: 15 Tamao de la poblacin: 100
Nmero de generaciones: 200 Probabilidad de cruce: 0,85
Probabilidad de mutacin: 0,013.
El tamao del cromosoma igual 15, significa que los valores de la variable x se
codificaron con 15 bits cada uno, resultando que los individuos se representan mediante
ristras de 0s y 1s de tamao 15.
El tamao de la poblacin igual 100, significa que para cada una de las 200
generaciones estarn formadas por 100 individuos.
Pc = 0,85; quiere decir que en cada generacin se modificar probablemente el 85%
de la poblacin y en todos los cruces que se aplican, los hijos sustituirn a los padres
independientemente de que la aptitud de stos sea peor que la de los padres.
Pm = 0,013, significa que el 10% de la poblacin y el 0,13% de los genes es probable
que sean sometidos a mutacin, por lo que en este caso como tenemos 100 individuos cada
uno codificado con 15 genes se espera que aproximadamente 19 genes sean mutados por
cada generacin y as los individuos mutados sustituirn a los iniciales independientemente
de su aptitud.
La tabla N 1 que se presenta a continuacin, contiene un resumen de los resultados
empricos, de los datos que consideramos relevantes, obtenidos mediante la corrida del
programa del algoritmo gentico simple, con las caractersticas paramtricas mencionadas
anteriormente, que se encuentra en el Anexo 2 de este trabajo.
-
UNIVERSIDAD NACIONAL ABIERTA 34
En la misma se observa que una vez realizadas 200 generaciones, el algoritmo
gentico encontr el valor mximo de la funcin en estudio que result ser igual a 4,8035, el
cual se alcanza en el valor de la variable x igual a 1,9504379406.
-
Tabla N 1 Resumen de resultados empricos
UNIVERSIDAD NACIONAL ABIERTA 35
Valor de X Mximo Mnimo Promedio Suma Mutaciones Cruces Generaciones1,8289132361 3,0797 1,0050 1,5705 157,0515 17 43 11,9411603100 4,7886 1,0000 1,6305 163,0526 31 86 21,9500106815 4,8025 1,0000 2,0026 200,2616 45 128 31,9500106815 4,8025 1,0020 2,2726 227,2647 59 172 41,9494613483 4,7993 1,0007 2,7030 270,3016 76 216 51,9498275704 4,8017 1,0042 2,8430 284,2982 97 258 61,9498215702 4,8016 1,0006 3,2116 321,1613 116 298 71,9500106815 4,8025 1,0010 3,4588 345,8796 127 340 81,9506177701 4,8028 1,0012 3,7419 374,1892 141 385 91,9506177701 4,8028 1,0005 3,9620 396,2000 160 428 101,9506177701 4,8028 1,0010 3,9602 396,0231 175 474 111,9506177701 4,8028 1,0123 4,1118 411,1769 198 518 121,9501937925 4,8031 1,0185 4,1554 415,5434 217 559 131,9498275704 4,8017 1,0089 4,1857 418,5693 232 607 141,9498275704 4,8017 1,0002 4,1899 418,9862 251 649 151,9500106815 4,8025 1,0191 4,1718 417,1812 271 695 161,9501937925 4,8031 1,0041 4,2386 423,8643 290 735 171,9508651900 4,8032 1,0024 4,2333 423,3294 304 784 181,9508651900 4,8032 1,0018 4,3154 431,5449 325 828 191,9501937925 4,8031 1,0018 4,3134 431,3423 343 872 201,9501937925 4,8031 1,0605 4,3905 439,0480 356 914 211,9501937925 4,8031 1,0011 4,4666 446,6635 378 958 221,9501327555 4,8030 1,3814 4,2848 428,4767 397 1.003 231,9506177701 4,8028 1,0126 4,1757 417,5684 416 1.040 241,9506177701 4,8028 1,1804 4,3564 435,6425 429 1.084 251,9501937925 4,8031 1,1225 4,3614 436,1446 446 1.131 261,9501937925 4,8031 1,0020 4,2147 421,4660 469 1.174 271,9507431257 4,8033 1,0036 4,2421 424,2080 485 1.218 281,9504379406 4,8035 1,0045 4,1769 417,6861 505 1.264 291,9505600146 4,8035 1,0000 4,2572 425,7215 533 1.310 301,9505600146 4,8035 1,0084 4,3004 430,0397 555 1.352 311,9505600146 4,8035 1,0916 4,3781 437,8083 577 1.393 321,9505600146 4,8035 1,0337 4,3390 433,9004 597 1.436 331,9506179856 4,8029 1,0001 4,3258 432,5818 626 1.478 341,9506177701 4,8028 1,0000 4,0788 407,8834 655 1.518 351,9507431257 4,8033 1,0101 4,2195 421,9456 672 1.558 361,9507431257 4,8033 1,0101 4,3783 437,8302 690 1.600 37
Funcin de Aptitud Nmero
Continuacin de Tabla N 1 Resumen de resultados empricos
-
UNIVERSIDAD NACIONAL ABIERTA 36
Valor de X Mximo Mnimo Promedio Suma Mutaciones Cruces Generaciones1,9507431257 4,8033 1,0043 4,4152 441,5206 708 1.642 381,9507431257 4,8033 1,6957 4,4755 447,5470 731 1.684 391,9507431257 4,8033 1,1278 4,4546 445,4580 749 1.725 401,9507431257 4,8033 1,0738 4,3399 433,9920 769 1.763 411,9509261310 4,8027 1,0129 4,3800 438,0019 780 1.799 421,9500106815 4,8025 1,1193 4,3345 433,4524 797 1.839 431,9509261310 4,8027 1,0408 4,3470 434,6953 825 1.883 441,9509261310 4,8027 1,0013 4,3734 437,3395 846 1.923 451,9508651900 4,8032 1,0005 4,2481 424,8061 869 1.967 461,9507431257 4,8033 1,0001 4,1711 417,1129 884 2.005 471,9501937925 4,8031 1,0000 4,2156 421,5561 896 2.049 481,9506177701 4,8028 1,1034 4,4398 443,9789 919 2.089 491,9506177701 4,8028 1,2007 4,4719 447,1919 934 2.131 501,9506177701 4,8028 1,0096 4,3980 439,7984 956 2.176 511,9506177701 4,8028 1,0115 4,3682 436,8249 973 2.219 521,9507431257 4,8033 1,0047 4,2965 429,6507 991 2.260 531,9506177701 4,8028 1,0002 4,4256 442,5634 1.004 2.307 541,9506177701 4,8028 1,2636 4,4005 440,0500 1.034 2.349 551,9507431257 4,8033 1,0005 4,4866 448,6561 1.057 2.389 561,9506177701 4,8028 1,0120 4,2150 421,5034 1.068 2.433 571,9507431257 4,8033 1,0000 4,0684 406,8424 1.093 2.476 581,9507431257 4,8033 1,0000 4,2469 424,6913 1.113 2.517 591,9507431257 4,8033 1,0001 4,0269 402,6906 1.140 2.559 601,9507431257 4,8033 1,0001 4,1717 417,1681 1.157 2.600 611,9507431257 4,8033 1,0015 4,2964 429,6375 1.168 2.642 621,9507431257 4,8033 1,0015 4,2806 428,0582 1.182 2.689 631,9503158660 4,8034 1,4975 4,4106 441,0584 1.198 2.730 641,9506820887 4,8034 1,3398 4,3082 430,8227 1.219 2.770 651,9506820887 4,8034 1,0005 4,4545 445,4484 1.236 2.811 661,9506820887 4,8034 1,0013 4,4024 440,2356 1.259 2.851 671,9506820887 4,8034 1,0000 4,3572 433,7153 1.278 2.890 681,9506820887 4,8034 1,0000 4,2844 428,4440 1.292 2.935 691,9506820887 4,8034 1,0080 4,2389 423,8881 1.305 2.975 701,9506820887 4,8034 1,0015 4,5238 452,3835 1.331 3.015 711,9506820887 4,8034 1,0000 4,3515 435,1515 1.347 3.054 721,9504379406 4,8035 1,0120 4,1643 416,4337 1.370 3.098 731,9506820887 4,8034 1,0050 4,4866 448,6623 1.389 3.138 741,9504379406 4,8035 1,0115 4,4545 445,4520 3.757 8.430 200Nmero promedio de cruces por generacin: 42Nmero promedio de mutaciones por generacin: 19
Funcin de Aptitud Nmero
Las grficas que se observan a continuacin, muestran los resultados empricos de
la poblacin en funcin al nmero de generaciones, obtenidos en 74 simulaciones, con las
caractersticas paramtricas mencionadas anteriormente.
-
0
1
2
3
4
5
6
0 10 20 30 40 50 60 70 80
Nmero de Generaciones
Valo
res
Apt
itud
Mximo Mnimo Promedio
figura N 2 Valores regulares de la funcin para distintas generaciones
Los resultados de los mximos y los mnimos de la funcin de aptitud (colores verde
y azul en la figura N 2), reflejan mucha estabilidad en la medida que avanzan las
generac la figura
N 2) m
e la funcin de aptitud acumulada con respecto al nmero de generaciones
produci
iones. Ahora bien, el valor promedio de la funcin aptitud (color naranja en
uestra cierta variabilidad con tendencia hacia el valor mximo, esto confirma la teora
en cuanto a que las generaciones resultantes tienden, en promedio, a ser ms aptas que sus
ascendientes.
Las dos grficas (figuras N 3 y 4) que siguen, muestran elocuentemente la relacin
directamente proporcional existente entre nmero de mutaciones, el nmero de cruces y la
estabilizacin d
das en los ensayos.
UNIVERSIDAD NACIONAL ABIERTA 37
-
0
500
1.000
1.500
2.000
2.500
3.000
3.500
0 10 20 30 40 50 60 70 80
Nmero de Generaciones
Nm
ero
de C
asos
Mutaciones Cruces
figura N 3 Nmero de mutaciones y cruces para distintas generaciones
Funcin de aptitud acumulada por cada generacin
0
100
200
300
400
500
0 10 20 30 40 50 60 70 80
Nmero de Generaciones
figura N 4 Funcin de aptitud acumulada distintas generaciones
La grfica (figura N 5) subsiguiente muestra las posiciones de los valores mximo,
mnimo y promedio de la funcin de aptitud para la distribucin inicial de la poblacin.
UNIVERSIDAD NACIONAL ABIERTA 38
-
21.510.50
5
4.5
4
3.5
3
2.5
2
UNIVERSIDAD NACIONAL ABIERTA 39
1.5
1
0.5
0
x
y
x
y
figura N 5 Valores regulares de la funcin en la poblacin inicial
La figura N 6 muestra las posiciones de los valores mximo, mnimo y promedio de
la funcin de aptitud para la distribucin final de la poblacin despus de 200 generaciones,
observndose que la lnea de posicin del valor mximo y mnimo coinciden con el valor
mximo y mnimo de la funcin en estudio.
21.510.50
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
x
y
x
y
Promedio
Mnimo
Mximo
Promedio
Mnimo
Mximo
figura N 6 Valores regulares de la funcin en la poblacin final
3.1.2. Aplicacin de los mtodos clsicos de optimizacin numrica
Se realizaron pruebas (cambiando el punto inicial) sobre la funcin
1)10(22 += xsenxy dirigidas a obtener resultados respecto a la ubicacin del mximo global con el software matemtico Maple 8, consiguindose como conducta modal que el
mismo detiene la bsqueda, en todo caso, en el primer mximo local que halla despus del
-
punto inicial y declara tal resultado como el valor mximo global de la funcin; produciendo
as una solucin aproximada con un inmenso error.
3.2. Evaluacin de la funcin ( )(( )) 222222
yx0,0011
0,5yxsen0,5Z ++
++= , en el dominio [-200, 200] X [-200, 200]
Continuando con el proceso de evaluacin, la figura N 7 ilustra la inversa de la
funcin que antecede en el dominio [-10, 10] X [-10, 10], debido a que para el dominio
62.5
50
37.5
25
105
0-5-10 -5 0 -105 10
12.5
x
y
z
figura N 7 grfica de la funcin en el domino [-10, 10] X [-10, 10]( )( )222222
yx0,0011
0,5yxsen0,5Z
++
++=
completo de definicin, la funcin inversa no presenta valores mximos relevantes.
UNIVERSIDAD NACIONAL ABIERTA 40
-
Como se observa, esta funcin tiene dos mximos globales en el entorno
(-5, 5) X (0, 2,5) y mltiples mximos locales.
100
75
50
-5-2.5
0
UNIVERSIDAD NACIONAL ABIERTA 41
figura N 7 grfica de la funcin en el domino [-5, 5] X [0, 2,5]( )( )222222
yx0,0011
0,5yxsen0,5Z
++
++=
3.2.1. Aplicacin del algoritmo gentico simple Los parmetros para la corrida de la funcin que se intenta optimizar mediante el
algoritmo gentico simple son los que se detallan a continuacin:
Tamao del cromosoma: 30 Tamao de la poblacin: 100
Nmero de generaciones: 200 Probabilidad de cruce: 0,85
Probabilidad de mutacin: 0,013.
El tamao del cromosoma igual 30, significa que los valores de las variables x, y se
codificaron con 15 bits cada uno, resultando que los individuos se representan mediante
ristras de 0s y 1s de tamao 30. Los primeros quince, de izquierda a derecha corresponden
a la variable y; las quince posiciones restantes corresponden a la variable x.
Los datos que consideramos relevantes, obtenidos mediante la corrida del programa
del algoritmo gentico simple, con las caractersticas paramtricas mencionadas
52.50
2.5
25
xy
z
-
anteriormente, el cual se encuentra en el Anexo 2 de esta monografa, refuerzan las
conclusiones obtenidas en el caso de la funcin de una variable. Una vez realizadas las 200
generaciones consideradas, el algoritmo gentico encontr dos valores que podemos
considerar una buena aproximacin a los mximos de la funcin en estudio que resultaron:
102,9237, el cual se alcanza en el punto (2,7039399396, 1,5930661948) y 102,8904, el cual
se alcanza en el punto (-0,81179235200, -3,0335398419).
3.2.2. Aplicacin de los mtodos clsicos de optimizacin numrica
Los resultados generados, utilizando el mismo software matemtico aplicado en el
aparte 3.1.2., productos de la evaluacin de la funcin ( )( )( )222222
yx0,0011
0,5yxsen0,5Z ++
++= son
anlogos a los arrojados en el aludido aparte.
UNIVERSIDAD NACIONAL ABIERTA 42
-
UNIVERSIDAD NACIONAL ABIERTA 43
CAPTULO IV
Posibles modificaciones al algoritmo gentico simple y conclusiones
Como se evidenci en el ejemplo manual del captulo I de esta monografa, el
algoritmo gentico simple al finalizar la quinta generacin, produjo como resultado para el
mximo de la funcin en el intervalo estudiado un valor igual a 676 (siendo su mximo
verdadero igual a 961); este escenario comprob que el mencionado algoritmo no es la
panacea ante el problema de optimizacin, marcando la necesidad de seguir iterando, todo
basado en el hecho, siempre imposible, de que se conoce el valor mximo de la funcin. He
aqu un importante problema real de este algoritmo, como lo es la tendencia a la
homegeinizacin de la poblacin, es decir a que todos los individuos de la misma sean
idnticos, impidiendo que el algoritmo siga explorando nuevas soluciones con lo que,
probablemente, se quede estancado en un mximo local no muy bueno, este evento suele
denominarse convergencia prematura en contraposicin a la convergencia lenta que en
muchos casos se produce.
Otro conflicto en el comportamiento del algoritmo gentico puede ser la existencia de
muchos ptimos locales, adems el hecho de que el ptimo global se encuentre muy
aislado.
Existen muchas tcnicas para contrarrestar tales situaciones. Los mecanismos que
nicamente mencionaremos en este captulo tienen que ver con las modificaciones
realizadas sobre los operadores genticos.
4.1 Modificaciones sobre los operadores genticos
Las modificaciones del algoritmo gentico simple, en cuanto a sus operadores
genticos, sern capaces de producir una versin mejorada del mismo, que no es ni se
pretende que sea una solucin definitiva al problema mencionado.
La investigacin en el campo de los algoritmos genticos est centrada en la
bsqueda de un algoritmo robusto, eficaz y rpido. En tiempos recientes, se han utilizado
-
diferentes parmetros para ensayos prcticos sobre un mismo problema, as mismo se han
desarrollado nuevas representaciones para los operadores de seleccin, cruce y mutacin a
fin de aumentar la velocidad de los algoritmos genticos; ya que empricamente se ha
comprobado que la modificacin de los parmetros y operadores que los definen pueden
impactar vigorosamente sobre el funcionamiento de dicho algoritmo.
4.1.1. Seleccin (Elitismo) Como antes se ha dicho, para el algoritmo gentico simple la seleccin de mayor
popularidad es la seleccin proporcional a la aptitud equivalente a la seleccin por rueda de
ruleta, siendo la probabilidad de seleccionar a un individuo
=
=pN
jj
iseli
F
FP
1
, donde:
iF : es el valor de la funcin de aptitud del individuo i-simo.
pN : es el nmero de individuos de la poblacin y se conoce como el tamao de la
poblacin.
Esta manera de escoger como padre a los individuos de la poblacin presenta el
inconveniente de la rpida convergencia provocada por los superindividuos.5
El problema anterior se puede resolver efectuando una seleccin proporcional al
rango del individuo, lo cual produce una reparticin ms uniforme en la escogencia.
( ) 2/1)(
+= irango
i
FrangoP , donde es el rango de la funcin objetivo del mejor individuo. Existe un modelo de seleccin elitista donde se obliga a que el mejor individuo de la
poblacin anterior sea seleccionado para pasar a la poblacin siguiente.
Entre la gran variedad de mtodos de refinamiento del modelo de seleccin
proporcional, cabe mencionar al modelo del seleccin del valor esperado, el esquema de
seleccin que ha proporcionado empricamente buenos resultados es el muestreo
estocstico con reemplazamiento del resto, introducido por Brindle (1991), otros
5 Estos son individuos con valores relativamente elevados en la funcin de aptitud.
UNIVERSIDAD NACIONAL ABIERTA 44
-
UNIVERSIDAD NACIONAL ABIERTA 45
procedimientos de seleccin consiste en mtodos de seleccin dinmicos (las
probabilidades de seleccin varan en cada generacin).
4.1.2. Cruce (Varios tipos) En el algoritmo gentico simple los individuos seleccionados para desempear el
papel de padres son recombinados utilizando el cruce basado en un punto. De Jong (1975)
ha realizado experimentos con operador de cruce basado en mltiples puntos y ha concluido
empricamente que el cruce basado en dos puntos produce mejoras importantes al
algoritmo.
Existen otros operadores de cruce son: a) Operador de cruce uniforme, b) Operador
de cruce basado en la funcin objetivo, c) Operador de cruce en el sentido del simulated
annealing, etc.
4.1.1. Mutacin Este operador es considerado de importancia capital debido a que permite al
algoritmo gentico explorar sobre todo el espacio de bsqueda. En la mayora de las
implementaciones del algoritmo gentico simple la probabilidad de mutacin permanece
constante en todas las generaciones. La bsqueda del valor ptimo de la mencionada
probabilidad ha motivado el desarrollo de muchos trabajos de investigacin.
Experimentalmente, modificando la probabilidad de mutacin se han logrado mejorar
los resultados del algoritmo gentico simple. Adicionalmente, en algunos casos se ha
ensayado con algoritmos genticos que modifican dinmicamente la probabilidad de
mutacin (y de cruce).
4.2 Conclusiones
1. El desarrollo de las pruebas experimentales realizadas en esta monografa, sobre
las dos funciones reales elegidas para ser evaluadas mediante el algoritmo gentico
simple, y la comparacin con los resultados que arrojaron los mtodos tradicionales
de optimizacin numrica, permiti exponer la potencialidad del algoritmo gentico
-
UNIVERSIDAD NACIONAL ABIERTA