Desarrollo de Algoritmos Genticos en Lenguaje C
aplicados a la resolucin de problemas de
optimizacin
Luis Marco Gimnez
UNED - 2005
2
Genetic Algorithms
Implementation in C Language
applied to the resolution of
optimization's problems
Resumen
Los Algoritmos Genticos, como paradigma principal de la computacin evolu-
tiva, presentan una alternativa a los procedimientos tradicionales de bsqueda y
optimizacin como mtodos sistemticos para la resolucin de estos problemas. En
concreto, y en el mbito de este trabajo, los algoritmos genticos se han aplicado
con buenos resultados en problemas de optimizacin en los que se desea localizar
los mximos o mnimos de una funcin matemtica determinada. La herramienta
desarrollada para este proyecto n de carrera, SIGENOF -Sistema Gentico pa-
ra la Optimizacin de Funciones-, consiste en la implementacin de un algoritmo
gentico para la optimizacin de una amplia variedad de funciones matemticas de
las que se desea localizar sus mximos globales. La principal aportacin de esta
herramienta frente a otras implementaciones genticas es la incorporacin de un
sencillo e intuitivo interfaz grco de usuario que permite, entre otras funcionalida-
des, la introduccin de la funcin a optimizar junto con los parmetros que guiarn
la ejecucin del algoritmo gentico, representacin grca de las mejores soluciones
localizadas por la herramienta, as como la generacin de cheros con los resul-
tados de la ejecucin que permiten realizar un anlisis posterior de las soluciones
encontradas.
i
ii
Abstract
Genetic Algorithms, as a major main paradigm of evolutional computation, pre-
sent a good alternative to traditional procedures of searching and optimizing as
systematic methods for the resolution of this kind of problems. Genetic algorithms
have been applied with good results in optimizing problems where the objective
is to obtain the maximus or minimus about a mathematical function. The imple-
mented tool in this degree work, SIGENOF -Sistema Gentico para la Optimi-
zacin de Funciones- (Genetic System for the Optimization Functions), consist in
the implementation of a genetic algorithm for the optimization of a wide variety
of mathematical functions of which we want to obtain their local maximums. The
main contribution of this tool compared to other genetic implementations is its easy
and intuitive graphical user interface allowing, among others functions, the input
of the function to be optimized, the parameters of the genetic algorithm that will
guide its execution, a graphical representation of the best solutions founded by the
tool, and a generation of les within the execution's results that will allow a further
analysis of the founded solutions.
iii
iv
Lista de palabras clave
Algoritmo Gentico, Aptitud, Bsqueda ciega, Bsqueda estocstica, Computa-
cin Evolutiva, Cromosoma, Cruce, Elitismo, Evolucin biolgica, Gen, Individuo,
Maximizacin, Mutacin, Optimizacin, Poblacin, Reproduccin, Seleccin, Solu-
cin.
1
2
Keywords
Genetic Algorithm, Fitness, Blind search, Stocastic search, Evolutionary Com-
putation, Chromosome, Crossover, Elitism, Biological evolution, Gen, Individual,
Maximization, Mutation, Optimization, Population, Reproduction, Selection, Solu-
tion.
3
4
Siglas, Abreviaturas y
Acrnimos
AG: Algoritmo Gentico
ASCII: American Standard Code for Information Interchange
GIMP: GNU Image Manipulation Program
GNU: GNU's Not Unix
GPL: General Public License
GTK: GIMP Toolkit
GUI: Interfaz Grco de Usuario
SIGENOF: Sistema Gentico para la Optimizacin de Funciones
5
6
ndice general
Lista de palabras clave 1
Siglas, Abreviaturas y Acrnimos 5
1. Introduccin 15
1.1. Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2. Computacin Evolutiva . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3. Algoritmos Genticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4. Caractersticas de los AG como mtodos de bsqueda . . . . . . . . 18
1.5. Mtodos de Optimizacin y Bsqueda tradicionales . . . . . . . . . . 19
1.6. Diferencias de los AG con los mtodos de bsqueda y optimizacin
tradicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.7. Funcionamiento de un AG bsico . . . . . . . . . . . . . . . . . . . . 20
1.8. Herramientas software actuales que implementan AG . . . . . . . . . 23
1.9. Herramienta SIGENOF . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.10. Problemas de optimizacin que resuelve SIGENOF . . . . . . . . . . 25
1.11. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . 26
2. Algoritmo Gentico implementado en SIGENOF 29
2.1. Lenguaje de implementacin utilizado . . . . . . . . . . . . . . . . . 29
2.2. Estructuras de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3. Sintaxis para la denicin de funciones J . . . . . . . . . . . . . . . 33
2.3.1. Variables y Constantes: . . . . . . . . . . . . . . . . . . . . . 34
2.3.2. Operadores disponibles: . . . . . . . . . . . . . . . . . . . . . 34
2.3.3. Funciones predeterminadas: . . . . . . . . . . . . . . . . . . . 35
7
8 NDICE GENERAL
2.3.4. Reglas de precedencia: . . . . . . . . . . . . . . . . . . . . . . 36
2.4. Algoritmo gentico implementado . . . . . . . . . . . . . . . . . . . . 37
2.4.1. Paso 1. Inicializacin . . . . . . . . . . . . . . . . . . . . . . . 37
2.4.2. Paso 2. Evaluacin . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4.3. Paso 3. Mantener al mejor individuo . . . . . . . . . . . . . . 39
2.4.4. Paso 4. Bucle de ejecucin del AG hasta MAXGENS . . . . . 40
2.4.5. Paso 5. Terminacin del AG . . . . . . . . . . . . . . . . . . . 45
3. Interfaz Grco de Usuario de SIGENOF 47
3.1. Librera grca utilizada . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2. Visin general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3. Funcionalidades del GUI . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.1. Panel 1: Parmetros Poblacionales . . . . . . . . . . . . . . . 50
3.3.2. Panel 2: Parmetros Naturales . . . . . . . . . . . . . . . . . 50
3.3.3. Panel 3: Otros Parmetros del AG . . . . . . . . . . . . . . . 50
3.3.4. Panel 4: Ventana de Resultados . . . . . . . . . . . . . . . . . 51
3.3.5. Panel 5: Funcin J a Optimizar . . . . . . . . . . . . . . . . . 52
3.3.6. Panel 6: Grco de Soluciones generacionales . . . . . . . . . 55
3.3.7. Panel 7: Datos estadsticos y Tiempo de ejecucin . . . . . . 55
3.3.8. Panel 8: Progreso y Control del proceso . . . . . . . . . . . . 55
3.4. Ejemplo de uso del GUI . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4.1. Paso 1. Iniciar SIGENOF . . . . . . . . . . . . . . . . . . . . 57
3.4.2. Paso 2. Denir la funcin J a optimizar . . . . . . . . . . . . 58
3.4.3. Paso 3. Establecer el espacio S . . . . . . . . . . . . . . . . . 59
3.4.4. Paso 4. Grabar la funcin J y su espacio S denido. . . . . . 60
3.4.5. Paso 5. Establecer los parmetros poblacionales . . . . . . . . 61
3.4.6. Paso 6. Establecer los parmetros naturales del AG . . . . . . 62
3.4.7. Paso 7. Establecer otros parmetros del AG . . . . . . . . . . 63
3.4.8. Paso 8. Seleccionar el tipo de visualizacin grca . . . . . . 63
3.4.9. Paso 9. Comenzar con la ejecucin . . . . . . . . . . . . . . . 64
3.4.10. Paso 10. Evaluacin de las soluciones obtenidas . . . . . . . . 64
NDICE GENERAL 9
4. Ejemplos de aplicacin de SIGENOF 67
4.1. Caso particular 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2. Caso particular 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3. Caso particular 3. Funcin de Ackley . . . . . . . . . . . . . . . . . . 69
4.4. Caso particular 4. Funcin de Shaer . . . . . . . . . . . . . . . . . . 70
4.5. Caso particular 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.6. Caso particular 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.7. Ejecucin con variantes . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.7.1. Sin variacin de parmetros (Ejecucin 1) . . . . . . . . . . . 75
4.7.2. Variacin de la probabilidad de mutacin (Ejecucin 2) . . . 75
4.7.3. Variacin de las probabilidades de cruce y mutacin (Ejecu-
cin 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.7.4. Variacin del tamao de la poblacin a un valor pequeo (Eje-
cucin 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.7.5. Variacin del n
o
de generaciones a un tamao pequeo (Eje-
cucin 5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.7.6. Variacin del n
o
de generaciones a un tamao grande (Ejecu-
cin 6) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.7.7. Variacin del tamao de la poblacin a un valor grande (Eje-
cucin 7) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.7.8. Variacin de la probabilidad de mutacin y del tamao de la
poblacin a un valor grande (Ejecucin 8) . . . . . . . . . . . 83
5. Conclusiones 85
A. Gramtica para Funciones J en SIGENOF 87
B. Funcin ran2 89
B.1. Fichero aleatorio.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
B.2. Fichero aleatorio.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
C. Cdigo del AG de SIGENOF 93
C.1. Fichero ag.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
C.2. Fichero ag.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
10 NDICE GENERAL
D. Ficheros de salida de SIGENOF 111
D.1. Descripcin de las salidas . . . . . . . . . . . . . . . . . . . . . . . . 111
D.2. Fichero salida_ag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
D.3. Fichero soluciones_ag . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Referencias Bibliogrcas 115
ndice de guras
1.1. Codicacin de Soluciones en los Cromosomas . . . . . . . . . . . . 18
1.2. Esquema de funcionamiento de un AG bsico . . . . . . . . . . . . . 21
1.3. Estructura genrica del bucle bsico de ejecucin de un AG . . . . . 22
2.1. Esquema de un algoritmo gentico bsico . . . . . . . . . . . . . . . . 37
2.2. Generacin de 1000 nmeros reales aleatorios . . . . . . . . . . . . . 38
2.3. Generacin de 5000 nmeros reales aleatorios . . . . . . . . . . . . . 39
2.4. Mtodo de la Ruleta . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5. Cruce en un solo punto . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.6. Cruce en un solo punto en SIGENOF . . . . . . . . . . . . . . . . . 43
3.1. GUI de SIGENOF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2. Funcin de ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3. Inicio de SIGENOF . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4. Denicin de la funcin J y del espacio S . . . . . . . . . . . . . . . 60
3.5. Grabacin de la funcin J y espacio S . . . . . . . . . . . . . . . . . 61
3.6. Parmetros poblacionales . . . . . . . . . . . . . . . . . . . . . . . . 62
3.7. Parmetros naturales . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.8. Otros parmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.9. Tipo de visualizacin grca . . . . . . . . . . . . . . . . . . . . . . . 64
3.10. Soluciones obtenidas por SIGENOF para el ejemplo propuesto . . . . 64
3.11. Resultados estadsticos para el ejemplo propuesto . . . . . . . . . . . 64
3.12.Mximo para el ejemplo propuesto . . . . . . . . . . . . . . . . . . . 65
4.1. Caso Particular 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
11
12 NDICE DE FIGURAS
4.2. Caso Particular 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.3. Caso Particular 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.4. Caso Particular 5 (vista 1) . . . . . . . . . . . . . . . . . . . . . . . 72
4.5. Caso Particular 5 (vista 2) . . . . . . . . . . . . . . . . . . . . . . . 72
4.6. Caso Particular 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.7. Caso inicial - Generacin 1 . . . . . . . . . . . . . . . . . . . . . . . 76
4.8. Variacin probabilidad de mutacin . . . . . . . . . . . . . . . . . . . 77
4.9. Variacin probabilidades de cruce y mutacin . . . . . . . . . . . . . 78
4.10. Variacin a un tamao de la poblacin pequeo . . . . . . . . . . . . 79
4.11. Variacin a un n
o
de generaciones pequeo . . . . . . . . . . . . . . 81
4.12. Variacin a un n
o
de generaciones grande . . . . . . . . . . . . . . . 82
4.13. Variacin a un tamao de la poblacin grande . . . . . . . . . . . . 83
4.14. Variacin tamao poblacin y probabilidad mutacin a valores grandes 84
ndice de cuadros
2.1. Denicin del cromosoma . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2. Denicin de la funcin J a optimizar . . . . . . . . . . . . . . . . . 32
2.3. Sintaxis para la denicin de funciones J . . . . . . . . . . . . . . . 33
2.4. Denicin de una funcin J . . . . . . . . . . . . . . . . . . . . . . . 37
4.1. Parmetros del AG utilizados en los ejemplos . . . . . . . . . . . . . 67
13
14 NDICE DE CUADROS
Captulo 1
Introduccin
1.1. Preliminares
Para la correcta comprensin de esta memoria a continuacin se van a denir una
serie de conceptos bsicos necesarios para la lectura del mismo y que se enmarcan
dentro del contexto de los Algoritmos Genticos.
Algoritmo Gentico: Tcnica de programacin que imita la evolucin bio-
lgica como estrategia para resolver problemas.
Poblacin : Conjunto de candidatos que representan soluciones potenciales
con las que el Algoritmo Gentico trabajar para resolver un determinado
problema.
Cromosoma : Codicacin de las soluciones potenciales del problema de for-
ma que una computadora pueda procesarlas. Un enfoque comn es codicar
estos candidatos, o soluciones, como cadenas binarias donde cada valor de bit
representa el valor de algn aspecto de la solucin. Un mtodo alternativo
consiste en codicar las soluciones como nmeros enteros o reales, donde cada
posicin representa algn aspecto particular de la solucin.
Gen : Elemento de informacin atmica que compone una parte de la posible
solucin que es codicada en un cromosoma.
Aptitud : Mtrica que permite evaluar cuantitativamente a cada candidato
15
16 1.2. Computacin Evolutiva
con respecto al problema que se desea resolver.
Seleccin : Proceso por el cual se eligen a los candidatos que representan una
mayor aptitud al problema a resolver para su posterior cruce y reproduccin.
Cruce : Procedimiento por el que los candidatos seleccionados para su repro-
duccin intercambian segmentos de informacin gentica, para producir pos-
teriormente una descendencia articial cuyos individuos sean combinaciones
de sus padres. Este proceso pretende simular el proceso anlogo a la recombi-
nacin que se da en los cromosomas durante la reproduccin sexual.
Reproduccin : Proceso por el cual se producen copias de los candidatos pre-
viamente seleccionados y que pasarn a formar parte de una nueva poblacin
de candidatos.
Mutacin : Cambios aleatorios que se producen durante el proceso de copia
en algunos cromosomas para producir diversidad en la poblacin.
Generacin : Acervo de soluciones candidatas producidas por la aplicacin
sucesiva de los mecanismos de seleccin, cruce, reproduccin y mutacin en-
tre los candidatos de una poblacin, y que produce una nueva poblacin de
candidatos.
Solucin del Algoritmo Gentico: Mejor solucin obtenida por el algorit-
mo, de entre todas las soluciones candidatas que componen la poblacin, en
el momento de haber iterado un nmero determinado de generaciones.
Era : Sucesivas ejecuciones del Algoritmo Gentico que proporcionan diferen-
tes mejores soluciones.
1.2. Computacin Evolutiva
La Computacin Evolutiva presenta un enfoque alternativo a los algoritmos tra-
dicionales para abordar problemas complejos de bsqueda y aprendizaje a travs de
modelos computaciones de procesos evolutivos, cuyo principal objetivo consiste en
guiar una bsqueda estocstica haciendo evolucionar a un conjunto de estructuras,
y seleccionando, de modo iterativo, las ms adecuadas.
1. Introduccin 17
Son cuatro los paradigmas fundamentales de la computacin evolutiva:
Los Algoritmos Genticos [Holl92]. Hacen evolucionar a una poblacin de
enteros binarios sometindolos a transformaciones unitarias y binarias gen-
ricas, junto a un proceso de seleccin.
Los Programas Evolutivos [Mich99]. Hacen evolucionar a una poblacin de
estructuras de datos sometindolas a una serie de transformaciones especcas
y a un proceso de seleccin.
Las Estrategias Evolutivas. Hacen evolucionar a una poblacin de nmeros
reales que codican las posibles soluciones de un problema numrico y los
tamaos de salto. La seleccin es implcita.
La Programacin Evolutiva . Hacen evolucionar a una poblacin de m-
quinas de estados nitos sometindolas a transformaciones unitarias.
1.3. Algoritmos Genticos
Desarrollados por John Holland, junto a su equipo de investigacin, en la Uni-
versidad de Michigan en la dcada de 1970, los algoritmos genticos representan el
paradigma principal de la computacin evolutiva. Son mtodos sistemticos para la
resolucin de problemas de bsqueda y optimizacin que aplican a estos los mismos
mtodos de la evolucin biolgica: seleccin basada en la poblacin, reproduccin
sexual y mutacin, combinando las nociones de supervivencia del individuo ms
apto con un intercambio estructurado y aleatorio de caractersticas entre individuos
de una poblacin de posibles soluciones, conformando un algoritmo de bsqueda
que puede aplicarse para resolver problemas de optimizacin en diversos campos.
Estos algoritmos de optimizacin tratan de obtener el vector de parmetros
(x1, x2 . . . , xn) que genera el mximo o el mnimo global de una cierta funcin
F (x1, x2 . . . , xn).
En un algoritmo gentico el problema se parametriza en un conjunto de varia-
bles (x1, x2 . . . , xn) que a su vez se codican en cromosomas, formando el conjunto
de estos ltimos poblaciones, y, a diferencia de otros mtodos de bsqueda, en los
algoritmos genticos el mtodo de bsqueda est implcito en l, por tanto se puede
18 1.4. Caractersticas de los AG como mtodos de bsqueda
armar que los algoritmos genticos son independientes del problema que se de-
sea resolver, lo cual por un lado los hacen robustos por su utilidad ante cualquier
problema, pero por otro lado los hacen dbiles al no estar especializados en ninguno.
Figura 1.1: Codicacin de Soluciones en los Cromosomas
Como se puede apreciar en la gura 1.1, las soluciones, codicadas en los cro-
mosomas (C1, C2, ..., Cn), compiten para ver cul de ellos constituye la mejor
solucin al problema (S1 , S2, ..., Sn), de forma que nicamente los cromosomas
mejor adaptados sobrevivirn, dando lugar, en las siguientes generaciones, a cromo-
somas ms fuertes, y por tanto a mejores soluciones, las cuales legarn su material
gentico a las siguientes generaciones. Este escenario de competicin y legado es
anlogo al de la naturaleza, en el que la presin de la seleccin natural provoca que
sean los mejores individuos aquellos que sobrevivan frente a los ms dbiles, siendo
estos los que se reproducirn y crearn nuevos individuos. La diversidad gentica,
de forma anloga al escenario natural, se introducir mediante mutaciones y cruces.
1.4. Caractersticas de los AG como mtodos de
bsqueda
Adems de la caracterstica de seleccin natural, se pueden citar otras caracte-
rsticas inherentes a los algoritmos genticos como mtodos de bsqueda [Perez96]:
1. Introduccin 19
Ciega, es decir, no se dispone de ningn conocimiento especco del problema,
de manera que la bsqueda se basa exclusivamente en los valores de la funcin
objetivo.
Codicada, puesto que no se trabaja directamente sobre el dominio del pro-
blema, sino sobre representaciones de sus elementos.
Mltiple, ya que se busca simultneamente entre un conjunto de candidatos.
Estocstica, referida tanto a las fases de seleccin como a las de transforma-
cin. Ello proporciona control sobre el factor de penetracin de la bsqueda.
Todas las caractersticas enumeradas se introducen deliberadamente para propor-
cionar ms robustez a la bsqueda.
1.5. Mtodos de Optimizacin y Bsqueda tradicio-
nales
Los mtodos de optimizacin y bsqueda tradicionales se pueden clasicar en
tres tipos principales: basados en el clculo innitesimal, de enumeracin y aleatorios
[Gold89].
1. Mtodos de clculo basados en el clculo innitesimal: Estos mtodos
se dividen a su vez en dos tipos: Directos e Indirectos
Mtodos Indirectos: Buscan un extremo local mediante la resolucin de
un conjunto de ecuaciones no lineales que aparecen tras igualar el gra-
diente de la funcin objetivo a cero. Dada una funcin sin restricciones
y suave, buscando un posible pico empezando por restringir la bsqueda
a aquellos puntos que poseen pendiente cero en todas las direcciones.
Mtodos Directos: Buscan puntos locales ptimos movindose en una
direccin relativa al gradiente local.
2. Tcnicas de enumeracin: Consisten en ir probando uno a uno todos los
puntos de un espacio de bsqueda restringido, ya sea un espacio nito o uno
20
1.6. Diferencias de los AG con los mtodos de bsqueda y optimizacin
tradicionales
innito discretizado. Presentan el problema de ser poco ecientes ya que re-
quieren un tiempo excesivo de clculo cuando el espacio de bsqueda es grande.
3. Algoritmos de bsqueda aleatoria: Consisten en probar con distintos va-
lores de manera aleatoria. Se puede armar que no actan peor que las tcnicas
de enumeracin.
Estas tcnicas se caracterizan por no ser robustas, aunque esto no signica que no
sean tiles.
1.6. Diferencias de los AG con los mtodos de bs-
queda y optimizacin tradicionales
Las diferencias de los AG con los algoritmos de bsqueda y optimizacin tradi-
cionales se pueden resumir en las siguientes [Gold89]:
1. Los AG trabajan con una codicacin de un conjunto de parmetros no con
los parmetros directamente.
2. Los AG no se limitan a buscar en las cercanas de un punto, sino que utilizan
una poblacin de puntos.
3. Los AG utilizan nicamente la informacin que les proporciona la funcin de
coste, sin necesidad de ninguna otra informacin. Por lo tanto no requieren
calcular derivadas.
4. Los AG utilizan reglas de transicin probabilsticas para guiar su bsqueda
en lugar de las reglas deterministas que otros mtodos tradicionales suelen
utilizar.
Estas cuatro propiedades contribuyen a que los AG sean ms robustos que los
mtodos tradicionalmente usados.
1.7. Funcionamiento de un AG bsico
La gura 1.2 representa el esquema de funcionamiento de un algoritmo genti-
co bsico. En este algoritmo bsico, el proceso comienza seleccionando un nmero
1. Introduccin 21
de cromosomas que conformarn la poblacin inicial. A continuacin se evala la
funcin de adaptacin para estos individuos. Esta funcin de adaptacin proporcio-
na una medida de la aptitud de cada cromosoma para sobrevivir en su entorno, y
debe estar denida de tal forma que los cromosomas que representen las mejores
soluciones obtengan valores ms altos de adaptacin; de este modo, los individuos
ms aptos se seleccionan en parejas para reproducirse. La reproduccin genera nue-
vos cromosomas que combinarn caractersticas de ambos padres. Estos nuevos
cromosomas reemplazarn a los individuos con menores valores de adaptacin. A
continuacin algunos cromosomas son seleccionados al azar para ser mutados. La
mutacin consiste en aplicar un cambio aleatorio en su estructura. Posteriormente,
los nuevos cromosomas se incorporarn a la poblacin reemplazando a cromoso-
mas ya existentes. Para realizar esta sustitucin existen varios criterios que pueden
utilizarse para elegir a los cromosomas que sern reemplazados.
Figura 1.2: Esquema de funcionamiento de un AG bsico
El ciclo de seleccin, reproduccin y mutacin se repetir hasta que se cumpla
el criterio de terminacin del algoritmo gentico, momento en el cual el cromosoma
mejor adaptado se devolver como la mejor solucin.
22 1.7. Funcionamiento de un AG bsico
Los criterios de terminacin empleados en implementaciones de AGs son bsi-
camente dos [Mich99]:
1. La condicin de terminacin ms simple es aquella que va comprobando el n-
mero actual de generacin g; la bsqueda se termina si el nmero total de gene-
raciones excede un valor constante predenido, es decir si g MAXGENS.
2. Como la condicin de terminacin anterior supone el conocimiento del usuario
de las caractersticas de la funcin, lo cual inuye en la longitud de la bs-
queda, parece ms conveniente que el algoritmo nalice la bsqueda cuando
la probabilidad de una mejora signicativa entre sucesivas generaciones sea
muy pequea, es decir que el valor de la funcin de coste entre generaciones
no mejore por encima de un cierto umbral .
En el algoritmo gentico programado, SIGENOF
1
, se han implementado ambas con-
diciones de terminacin, siendo la primera el criterio por defecto, mientras que el
segundo criterio se puede utilizar de forma discrecional por el usuario de la herra-
mienta.
La estructura genrica del bucle bsico de ejecucin de un algoritmo gentico se
puede sintetizar en el diagrama mostrado en la gura 1.3 [Perez96]:
Figura 1.3: Estructura genrica del bucle bsico de ejecucin de un AG
Como puede observarse en la gura anterior, una poblacin Pop, que consta
1
Sistema Gentico para la Optimizacin de Funciones
1. Introduccin 23
de n miembros, se somete a un proceso de seleccin para constituir una poblacin
intermedia AuxPop de n miembros. De dicha poblacin intermedia se extraer un
grupo reducido de individuos llamados progenitores, que son los que efectivamente
se van a reproducir. Sirvindose de los operadores genticos, los progenitores son
sometidos a ciertas transformaciones de alteracin y recombinacin en la fase de
reproduccin, en virtud de las cuales se generan s nuevos individuos que constituyen
la descendencia. Para formar la nueva poblacin Pop[t + 1], se deben seleccionar n
supervivientes de entre los n + s de la poblacin auxiliar y la descendencia; esto se
realizar en la fase de reemplazo.
Todo el procedimiento de bsqueda estar guiado exclusivamente por una fun-
cin de aptitud u(x), la cual se obtiene directamente a partir de la funcin de
evaluacin f(x) del problema.
1.8. Herramientas software actuales que implemen-
tan AG
Se pueden encontrar una gran variedad de herramientas que implementan AG y
que son usadas para diferentes propsitos en diversidad de campos, entre los que se
encuentran la acstica, ingeniera aeroespacial, astronoma y astrofsica, qumica,
ingeniera elctrica, los mercados nancieros, juegos, geofsica, ingeniera de ma-
teriales, matemtica y algoritmia, diseo de rutas y horarios, biologa molecular,
reconocimiento de patrones y robtica, entre otros.
Muchas de estas herramientas presentan unas limitaciones que se pueden resumir
en las siguientes:
La mayora no implementan ningn GUI que permita la interaccin con la
herramienta por parte del usuario de manera sencilla e intuitiva. Sus salidas
se suelen realizar mediante consola o a travs de cheros de texto.
No son fcilmente parametrizables, es decir, suele ser difcil cambiar el objetivo
del problema que resuelven. Por ejemplo, muchas herramientas que optimizan
funciones buscando mximo o mnimos necesitan ser compiladas cada vez que
la funcin objetivo, o algunos de sus parmetros, vara.
24 1.9. Herramienta SIGENOF
En muchas ocasiones el cambio de los parmetros del AG, tales como el tama-
o de la poblacin, la probabilidad de cruce, etc., resulta complejo al tener que
realizar cambios en el programa o, en el mejor de los casos, en algunos che-
ros de conguracin de la herramienta. Frecuentemente el programa necesita
volver a compilarse para hacer efectivos dichos cambios.
Los lenguajes utilizados en su desarrollo son bastante heterogneos, encon-
trndose herramientas programadas en C/C++, Perl, Java, LISP, Fortran,
etc. En muchos casos estas herramientas son portables, es decir se pueden eje-
cutar en distintas computadoras, como por ejemplo las que se desarrollan en
Java (Java application o Java applet), sin embargo en otros casos, sobretodo
cuando incorporan un GUI, son dependientes del sistema operativo para el
cual se han desarrollado.
1.9. Herramienta SIGENOF
SIGENOF, se ha desarrollado con el objetivo de suplir algunas de las limitacio-
nes que otras herramientas presentan, sobretodo en lo referente a la capacidad de
interactividad del usuario con sta.
Las caractersticas ms destacables que aporta SIGENOF con respecto a otras
herramientas se pueden resumir en las siguientes:
1. Proporciona un entorno grco sencillo e intuitivo que permite:
Introducir fcilmente diferentes parmetros al AG como tamao de la po-
blacin, nmero de generaciones, nmero de eras, probabilidad de cruce
y de mutacin, etc.
Denir dinmicamente, sin necesidad de volver a compilar el programa, la
expresin de la funcin matemtica que se desea optimizar, as como los
valores mximos y mnimos que sus variables de incertidumbre pueden
tomar.
Interactuar en tiempo de ejecucin con la herramienta pudiendo iniciar
o cancelar la ejecucin a peticin del usuario, o denir el tipo de visua-
lizacin grca que mejor convenga.
1. Introduccin 25
Representacin grca de las mejores soluciones obtenidas por el AG en
cada generacin / era.
Posibilidad de pausar la ejecucin tras nalizar una era para poder obser-
var con detenimiento el grco de las mejores soluciones obtenidas antes
de pasar a la siguiente era.
2. Portabilidad frente a distintas plataformas hardware y software. La herramien-
ta se ha desarrollado en un lenguaje portable, en lenguaje C, que permite la
compilacin en cualquier sistema operativo que disponga de un compilador de
ANSI C. Para la implementacin del GUI se han utilizado las libreras gr-
cas GTK+ distribuidas bajo licencia GNU GPL. Estas libreras requieren
la instalacin del framework GTK+, distribuido tambin bajo licencia GNU
GPL y que puede descargarse gratuitamente desde Internet.
3. Fcil instalacin y distribucin ya que nicamente se requiere la distribucin
del framework GTK+ y del chero ejecutable de la herramienta.
4. Generacin de cheros log con los resultados de cada ejecucin.
5. La herramienta ha sido desarrollada bajo licencia GNU GPL, lo que permite
su libre distribucin.
1.10. Problemas de optimizacin que resuelve SI-
GENOF
SIGENOF, se utiliza de forma eciente para resolver problemas de optimizacin
como el que se describe a continuacin.
Se dene el vector de parmetros :
= [x1, . . . , xn]
Donde los elementos xi son nmeros reales acotados dentro de un cierto espacio
S.
S = {x1 [xmin1 , xmax1 ], x2 [xmin2 , xmax2 ], . . . , xn [xminn , xmaxn ]}
26 1.11. Estructura de la memoria
Es decir, el valor que puede tomar cada elemento xi se encuentra acotado dentro
de un cierto valor mnimo xmini y de un cierto valor mximo xmaxi .
Sea la funcin de coste J : Rn R
J = f()
Se verica la condicin de que J > 0 para cualquier considerado.
El problema que resuelve el algoritmo gentico, por tanto, es el de obtener el
vector de parmetros ptimo opt S que genera el valor mximo Jopt de la funcinde coste J .
Jopt = J(opt) = maxS(J())
1.11. Estructura de la memoria
Esta memoria se ha dividido en cinco captulos. En el captulo 1 se exponen los
conceptos bsicos que envuelven a los AG como uno de los paradigmas de la Compu-
tacin Evolutiva, presentndose estos como un enfoque alternativo a los algoritmos
tradicionales usados en problemas de bsqueda y optimizacin de soluciones. Asi-
mismo se enumeran las caractersticas de los AG como mtodos de bsqueda y se
comparan con los mtodos tradicionales, se expone el funcionamiento de un AG bsi-
co y se hace un breve estudio de las herramientas software actuales que implementan
AG. Por ltimo se proporciona una visin general de la herramienta implementada
para este proyecto, SIGENOF, as como los problemas de optimizacin que sta
resuelve.
En el captulo 2 se describen los detalles de implementacin de SIGENOF, tales
como el lenguaje utilizado para su escritura, las estructuras de datos relevantes para
el AG programado (Cromosomas, Funciones a optimizar, Parmetros de ejecucin,
etc.), la sintaxis para la denicin de las funciones J a optimizar, y el detalle pro-
cedimental de los principales pasos que realiza la herramienta en la implementacin
de su AG.
En el captulo 3 se justica, en primer lugar, la librera grca con la que se
ha implementado el GUI de SIGENOF, las GTK+. A continuacin se realiza un
anlisis de todas y cada una de las funciones que la herramienta proporciona a
1. Introduccin 27
travs de su GUI, describiendo, paso a paso y a modo de manual de usuario, la
ejecucin de la herramienta con un ejemplo.
El captulo 4 muestra algunos de los ejemplos utilizados para vericar el fun-
cionamiento de SIGENOF como herramienta para la optimizacin de funciones
matemticas. En cada uno de estos ejemplos se describe el problema a resolver y se
muestra la solucin grca en la que se puede observar el valor ptimo de la funcin;
posteriormente se compara la solucin encontrada por SIGENOF frente a la solu-
cin real de forma que se pueda ponderar la calidad de la solucin proporcionada
por la herramienta. Asimismo se explica cmo se comporta la herramienta en la
optimizacin de un caso particular con diferentes variaciones de los parmetros del
AG, tales como el tamao de la poblacin, la probabilidad de cruce y/o mutacin,
entre otros.
En el captulo 5 se describen algunas de las conclusiones a las que he llegado
tras la implementacin de SIGENOF.
Al nal de la memoria se incluyen, como apndices, informacin relativa a di-
versos aspectos clave en la implementacin del AG de SIGENOF, as como de los
cheros de salida (cheros LOG) generados por la herramienta.
28 1.11. Estructura de la memoria
Captulo 2
Algoritmo Gentico
implementado en SIGENOF
2.1. Lenguaje de implementacin utilizado
El lenguaje de programacin de alto nivel utilizado para implementar el AG que
usa SIGENOF ha sido el lenguaje C, puesto que presenta las siguientes ventajas:
El lenguaje C es adecuado para la programacin a bajo nivel cubriendo as el
vaco entre el lenguaje mquina y los lenguajes de alto nivel ms convencio-
nales.
Permite la redaccin de programas fuentes muy concisos debido, en parte, al
gran nmero de operadores que incluye en lenguaje.
Tiene un repertorio de instrucciones bsicas relativamente pequeo, aunque
incluye numerosas funciones de biblioteca que mejoran las instrucciones bsi-
cas. Adems los usuarios pueden escribir bibliotecas adicionales para su propio
uso.
Los compiladores de C son, frecuentemente, compactos y generan programas
objeto pequeos y ecientes.
Los programas escritos en C son muy portables. La razn de esto es que C
deja en manos de las funciones de biblioteca la mayora de las caractersticas
29
30 2.2. Estructuras de datos
dependientes de la computadora. De esta forma, la mayora de los progra-
mas escritos en C se pueden compilar y ejecutar en muchas computadoras
diferentes, con muy pocas o ninguna modicacin.
2.2. Estructuras de datos
Los cromosomas poblacionales se han denido como estructuras que contienen
los siguientes datos:
Un vector de parmetros o variables x de la funcin J que se desea optimizar,
particular para el cromosoma. Este vector de parmetros representa una solu-
cin particular al problema. Estos parmetros, tambin denominados genes,
estn acotados al espacio S de posibles valores que pueden tomar, y que han
sido denidos para la funcin J.
Un valor que representa el tness o grado de adaptacin del cromosoma a la
funcin J que se desea optimizar.
Un valor p que indica la probabilidad de seleccin del cromosoma para su
reproduccin.
Un valor q que representa la probabilidad acumulada del cromosoma con
respecto a los dems cromosomas de la poblacin, decisivo para su seleccin
para el cruce con otro cromosoma.
Un valor booleano que indica que el cromosoma ha sido seleccionado para su
cruce y reproduccin.
La denicin del cromosoma se ha realizado como se muestra en el cuadro 2.1.
2. Algoritmo Gentico implementado en SIGENOF 31
Estructura CROMOSOMA
typedef struct CROMOSOMA
{
long *x;
float fitness;
float p;
float q;
int seleccionado;
}
Tipo_cromosoma;
Cuadro 2.1: Denicin del cromosoma
De esta forma, la poblacin se ha establecido como un conjunto de pop_size cro-
mosomas denidos como un vector de pop_size elementos de tipo Tipo_cromosoma.
La funcin J que se desea optimizar se ha denido como una estructura que
contiene los siguientes datos:
Una cadena de caracteres que contiene la descripcin aritmtica de la funcin
J a optimizar, ajustada a la sintaxis denida en el cuadro 2.3. Esta represen-
tacin proporciona una gran exibilidad ya que permite optimizar diferentes
funciones J sin necesidad de volver a compilar el programa cada vez que sta
vare. La gramtica denida para las expresiones aritmticas de las funciones
J se describe en el Apndice A.
Un valor entero que indica el nmero de parmetros o variables xi que contiene
la funcin, con 0 i numero_parametros 1.
Un vector de valores de coma otante que establece el valor mnimo que cada
variable xi puede tomar como extremo inferior xmindel espacio S de la funcin
J.
Un vector de valores de coma otante que establece el valor mximo que cada
variable xi puede tomar como extremo superior xmaxdel espacio S de la
funcin J.
La denicin de la funcin J se ha realizado como se muestra en el cuadro 2.2.
32 2.2. Estructuras de datos
Estructura FUNCIN
typedef struct DEF_FUNCION
{
char *funcion;
int numero_parametros;
float *valor_min_parametro;
float *valor_max_parametro;
}
Tipo_funcion;
Cuadro 2.2: Denicin de la funcin J a optimizar
Como se puede observar en el cuadro 2.1, se ha denido el tipo del vector de
parmetros x como entero largo (long *x), cuyo rango de posibles valores que
puede representar se encuentra en el intervalo [2.147.483.648 . . . 2.147.483.647], sinembargo los posibles valores que dichos parmetros pueden tomar se han denido
en la tabla 2.2 como valores de coma otante (float *valor_min_parametro y
float *valor_max_parametro). Este cambio en el tipo de datos para el vector de
parmetros se ha realizado con el n de optimizar el tiempo de ejecucin del AG
as como su tamao en memoria, ya que los clculos con enteros son sensiblemente
ms rpidos que con nmeros en coma otante. Estos parmetros, tratados como
valores en coma otante, son redondeados, por defecto, a tres cifras decimales
1
y
almacenados posteriormente en el cromosoma como valores enteros largos. Cuando
se desea operar con estas variables, como sucede cuando se realiza la evaluacin
del cromosoma segn la funcin de coste J para determinar su adaptacin o tness
a dicha funcin, se realiza el proceso inverso convirtiendo los valores enteros a su
correspondiente valor en coma otante.
Otras variables que se han considerado en la implementacin del AG son:
Tamao de la poblacin (POP_SIZE), es decir, el nmero de cromosomas
de que consta la poblacin.
Nmero mximo de generaciones (MAXGENS) en las que se ejecutar el
bucle bsico del AG para dar por nalizada una era.
1
Aunque el nmero de cifras decimales es un valor que, como se ver posteriormente, puede ser
denido por el usuario de la herramienta.
2. Algoritmo Gentico implementado en SIGENOF 33
Nmero de eras (ERAS); establece el nmero de ejecuciones completas e
independientes entre s del AG.
Probabilidad de cruce de los cromosomas (pc). Es un nmero real com-
prendido en el intervalo [0, 1] que dene la probabilidad que cada cromosoma
tendr de ser seleccionado para su cruce y reproduccin con otro cromosoma.
Probabilidad de mutacin de los cromosomas (pm). Nmero real compren-
dido en el intervalo [0, 1] que dene la probabilidad que cada cromosoma
tendr de sufrir una mutacin en sus genes.
2.3. Sintaxis para la denicin de funciones J
La sintaxis que permite denir diferentes funciones J se muestra en el cuadro
2.3.
SINTAXIS PARA LA DEFINICIN DE FUNCIONES
1. VARIABLES Y CONSTANTES:
Variables de funcin x[0], x[1], ..., x[j]
Constantes pi, e
Constantes Numricas enteras, Punto Flotante o Expresiones Exponenciales
2. OPERADORES DISPONIBLES:
suma(+) resta/negacin(-) producto(*) div(/) potencia(/\)
3. FUNCIONES PREDEFINIDAS:
sin, cos, tan, asin, acos, atan, hsin, hcos, htan, sqrt, exp, ln, log, abs
4. REGLAS DE PRECEDENCIA (de mayor a menor):
1
o
Parntesis
2
o
Negacin unaria
3
o
Potencia, Producto y Divisin
4
o
Suma y Resta
Cuadro 2.3: Sintaxis para la denicin de funciones J
A continuacin se detallan, de manera individual, los diferentes elementos que
componen dicha sintaxis.
34 2.3. Sintaxis para la denicin de funciones J
2.3.1. Variables y Constantes:
Variables de incertidumbre de la funcin (x[j]): Dada una determina-
da funcin f con n variables de incertidumbre, es decir f(x1, x2, ..., xn), las
variables xi de la funcin se denirn como variables x[j], donde j = i 1 y0 j n 1. Con esta sintaxis las variables x1, x2, ..., xn, se denirn comox[0], x[1], ..., x[n1]. As en la expresin de una funcin f(x1, x2) aparecerannicamente las variables x[0] y x[1], junto con los operadores necesarios, fun-
ciones predenidas y las constantes numricas necesarias para su denicin
completa.
Constantes predenidas:
1. Constante pi (pi): Establece el valor del nmero pi el cual se dene de
manera aproximada como 3,14159265358979. Una expresin en la que se haga
uso de la constante pi como 2pi se redene como 2 pi.2.Constante e de Euler (e): Establece el valor del nmero e el cual se dene
de manera aproximada como 2,718282. Una expresin en la que se haga uso
de la constante e como ocurre en 2e se redene como 2 e.
Constantes numricas:
1. Constantes Enteras: Como por ejemplo las constantes 2, -5 125. Se
redenen en la expresin de la misma forma.
2. Constantes de Punto Flotante: Como por ejemplo las constantes 2.25
-48,002. En este caso se redenen en la expresin de la misma forma pu-
dindose sustituir el punto decimal por una coma decimal o viceversa, como
mejor convenga, quedando redenidos como 2,25 2.25 y -48,002 -48.002.
3. Expresiones Exponenciales: Expresiones como 2 103 2.05 105 sepueden redenir en notacin exponencial como 2E + 3, 2E3 y 2.05E 5.
2.3.2. Operadores disponibles:
Operador suma (+): Suma dos trminos a y b. Una expresin como x+ y
se redene como x[0] + x[1].
Operador resta (): Obtiene la diferencia de dos trminos a y b. Unaexpresin como x (y z) se redene como x[0] (x[1] x[2]).
2. Algoritmo Gentico implementado en SIGENOF 35
Operador producto (*): Multiplica dos trminos a y b. Una expresin como
2 x se redene como 2 x[0].
Operador divisin (/): Divide dos trminos a y b. Una expresin como y/x
se redene como x[1]/x[0].
Operador potencia (^): Realiza el clculo a elevado al exponente b. Una
expresin como x3 se redene como x[0]^3.
Operador negacin unaria (-): Realiza el complemento de signo del tr-
mino al que antecede. Una expresin como 5y se redene como 5 x[1].
2.3.3. Funciones predeterminadas:
Funciones trigonomtricas:
1. seno, coseno y tangente (sin(a), cos(a), tan(a)): Obtiene el valor de
expresiones trigonomtricas como seno(2.5), coseno(x) y tangente(1 z) re-denindose stas como sin(2, 5), cos(x[0]) y tan(1 x[2]).2. arcoseno, arcocoseno y arcotangente (asin(a), acos(a), atan(a)): Ob-
tiene el valor de expresiones trigonomtricas como arcoseno(2.5), arcocoseno(x)
y arcotangente(1z), redenindose stas como asin(2, 5), acos(x[0]) y atan(1x[2]).
3. seno, coseno y tangente hiperblica (hsin(a), hcos(a), htan(a)): Obtie-
ne el valor de expresiones trigonomtricas hiperblicas como senoHiperbolico(2.5),
cosenoHiperbolico(x) y tangenteHiperbolica(1 z), redenindose stas co-mo hsin(2, 5), hcos(x[0]) y htan(1 x[2]).
Funcin raz cuadrada (sqrt(a)): Realiza clculos del tipo2, redenin-
dose mediante esta sintaxis como sqrt(2).
Funcin exponencial (exp(a)): Realiza clculos del tipo ex, donde e es la
constante de Euler y x es el argumento a. Estas expresiones se redenen como
exp(x[0]). Alternativamente esta expresin tambin se podra redenir como
e^x[0].
Funciones logartmicas:
1. Logaritmo en base 10 (log(a)): Obtiene el logaritmo en base 10 del
36 2.3. Sintaxis para la denicin de funciones J
argumento a. Una expresin como log(yx) se redene como log(x[1]x[0]).2. Logaritmo natural (ln(a)): Obtiene el logaritmo natural del argumento
a. Una expresin como ln e se redene como ln(e).
Valor absoluto (abs(a)): Obtiene el valor absoluto del argumento a. Una
expresin como | x | se redene como abs(x[0]).
2.3.4. Reglas de precedencia:
Una expresin en la que existan diversos operadores juntos puede resultar ambi-
gua. Para resolver estas situaciones se han denido unas sencillas reglas de preceden-
cia, las cuales aplican los diferentes operadores en el orden denido a continuacin,
considerando en este caso al factor Parntesis como un elemento de mayor prece-
dencia que los operadores Suma y Resta. Los operadores que aparecen agrupados en
esta enumeracin, como Potencia, Producto y Divisin, tienen la misma precedencia
cuando aparecen en una expresin; en este caso se resolver la expresin mediante
un anlisis sintctico de izquierda a derecha.
1
o
Parntesis.
2
o
Negacin unaria.
3
o
Potencia, Producto y Divisin.
4
o
Suma y Resta.
As, una funcin J denida como,
f(x1, x2) = 21.5 + x1 sin(4pix1) + x2 sin(4pix2)S = {x1 [3.0, 12.1], x2 [4.1, 5.8]}
segn la sintaxis establecida para el AG, en el cuadro 2.3 y la gramtica descrita
en el Apndice A, se dene como se muestra en el cuadro 2.4.
2. Algoritmo Gentico implementado en SIGENOF 37
Funcin: 21.5 + x[0] * sin(4*pi*x[0]) + x[1] * sin(4*pi*x[1])
Nmero de parmetros: 2
Valor mnimo parmetro x[0]: -3.0, x[1]: 4.1
Valor mximo parmetros x[0]: 12.1, x[1]: 5.8
Cuadro 2.4: Denicin de una funcin J
2.4. Algoritmo gentico implementado
El AG implementado se ha realizado siguiendo el esquema bsico de algoritmo
gentico propuesto por Michalewicz [Mich99], y mostrado en la gura 2.1.
Figura 2.1: Esquema de un algoritmo gentico bsico
Se detalla a continuacin la implementacin de los diferentes pasos del AG:
2.4.1. Paso 1. Inicializacin
Este primer paso es uno de los ms crticos, en lo que a resultados del AG
se reere, ya que es el responsable de generar aleatoriamente la poblacin inicial
38 2.4. Algoritmo gentico implementado
de individuos con la que el AG empezar a operar. Es especialmente importante
que el generador de nmeros aleatorios, o ms concretamente pseudoaleatorios
2
sea
lo sucientemente bueno y capaz para generar individuos de forma verdaderamente
aleatoria. Para ello se ha utilizado la implementacin que se da en el texto [Recip88]
como ran2, una funcin que produce nmeros aleatorios de manera perfecta, consi-
derando la denicin de funcin perfecta la que los autores describen en el texto: ...
pagaremos $1000 al primer lector que nos convenza de lo contrario. En las guras
2.2 y 2.3 se muestra la distribucin de varios nmeros aleatorios generados con dicha
implementacin; en el primer grco se generaron 1000 nmeros reales aleatorios
comprendidos en el intervalo [0, 100], mientras que en la segunda se generaron 5000
nmeros reales aleatorios en el intervalo [1000, 1000]. Se puede observar en ellascmo los distintos nmeros generados se distribuyen de forma aleatoria a lo largo
del espacio de posibles valores que pueden tomar. El cdigo fuente de la funcin
ran2 se muestra en el Apndice B.
Figura 2.2: Generacin de 1000 nmeros reales aleatorios
2
El concepto de aleatorio se suele reservar a la generacin mediante fenmenos fsicos, tales
como el tiempo transcurrido entre sucesivos clicks de un contador Geiger situado cerca de una
muestra radiactiva.
2. Algoritmo Gentico implementado en SIGENOF 39
Figura 2.3: Generacin de 5000 nmeros reales aleatorios
2.4.2. Paso 2. Evaluacin
En este paso se evala cada individuo o cromosoma i de la poblacin inicial de
tamao POP_SIZE sobre la funcin de coste J del problema a resolver, obteniendo
su tness o adaptacin al problema.
2.4.3. Paso 3. Mantener al mejor individuo
Se identica y se selecciona el mejor individuo de la generacin actual para
conservar su informacin gentica para la siguiente generacin. Esta seleccin se
realiza en funcin del grado de adaptacin del individuo a la funcin de coste J que
se est optimizando. En este caso su adaptacin vendr determinada por el valor
que hace mximo la funcin de coste J en la generacin actual. El AG guarda al
mejor individuo de la generacin en una variable de tipo Tipo_cromosoma llamada
mejor_cromosoma.
40 2.4. Algoritmo gentico implementado
2.4.4. Paso 4. Bucle de ejecucin del AG hasta MAXGENS
Este cuarto paso se subdivide a su vez en los siguientes seis subpasos:
Paso 4.1. Incremento del contador de generaciones
En este paso nicamente se actualiza un contador de generaciones para controlar
el bucle de ejecucin del AG.
Paso 4.2. Aplicacin del operador de Seleccin
El propsito de la seleccin de padres es dar ms oportunidades de reproduccin
a aquellos individuos de una poblacin que son los que mejor se ajustan tras haber
sido evaluados por la funcin de evaluacin. Con este propsito, el operador de
Seleccin aplica, en este AG, el Mtodo de la Ruleta para establecer la probabilidad
de seleccin de cada cromosoma de la poblacin actual.
El algoritmo que describe el Mtodo de la Ruleta se detalla como:
1. Se suman los tness de todos los individuos de la poblacin J
i
. A esta suma
se le denominar F, denindose como:
F =
POP_SIZEJi
i=1
2. Se calcula la probabilidad de seleccin p
i
para cada cromosoma de la poblacin
como:
pi =JiF
3. Se calcula la probabilidad acumulada q
i
para cada cromosoma de la poblacin
como:
qi =
POP_SIZEpk
k=1
4. Se gira la ruleta POP_SIZE veces. Cada vez que se gira la ruleta se realiza lo
siguiente:
2. Algoritmo Gentico implementado en SIGENOF 41
Se genera un nmero real aleatorio r dentro del rango [0, 1].
Si r < q1 se selecciona el cromosoma C1
, en caso contrario se selecciona el
cromosoma i-simo C
i
(2 i POP_SIZE), tal que qi1 < r qi para unanueva poblacin.
Tras haber girado la ruleta POP_SIZE veces, se habrn seleccionado POP_SIZE cro-
mosomas para formar parte de la nueva poblacin.
Se muestra grcamente el proceso de seleccin de cromosomas con el mtodo
de la ruleta en la gura 2.4.
Figura 2.4: Mtodo de la Ruleta
42 2.4. Algoritmo gentico implementado
Paso 4.3. Aplicacin del operador de Cruce en un solo punto
La probabilidad de cruce vendr determinada por el valor de probabilidad pc [0, 1], siendo ste un parmetro congurable por el usuario que ejecuta el AG.
Teniendo en cuenta este parmetro pc, el operador de cruce en un solo punto se
ha implementado de la siguiente forma:
1. En primer lugar se seleccionan los individuos de la nueva poblacin de POP_SIZE
individuos para reproducirse. Para ello para cada individuo se genera un n-
mero real aleatorio r comprendido en el rango [0, 1]. Si r < pc, entonces el
cromosoma i es seleccionado para reproducirse.
Como el operador de cruce en un solo punto opera con parejas de individuos, si
tras nalizar la seleccin de cromosomas para su reproduccin se observa que
este nmero es impar, se procede a la seleccin de un cromosoma adicional de
forma aleatoria, de forma que el conjunto nal de cromosomas seleccionados
sea un nmero par.
2. Se realiza la operacin de cruce en un solo punto entre parejas de individuos
seleccionados para reproduccin. El punto de cruce para el intercambio de
informacin entre genes se selecciona, en este caso, de forma aleatoria. Se
puede observar esta operacin grcamente en la gura 2.5.
Tras la seleccin de parejas de cromosomas y cruce en un solo punto, se obten-
drn dos nuevos cromosomas hijos que reemplazarn a los cromosomas padre en la
poblacin de individuos.
En el AG implementado, al contener el cromosoma un nmero de variables de
genes determinado por la variable nGenes, y sta a su vez condicionada por el nme-
ro n de variables de la funcin J que se desea optimizar (xi, . . . , xn), el intercambio
de informacin gentica se realiza seleccionando un nmero entero aleatorio com-
prendido en el intervalo [0, n 1] que indicar la posicin del parmetro xi
(gen
i) a partir del cual se intercambiar la informacin gentica, codicada como va-
lores enteros que representan valores reales, entre la pareja de cromosomas. Este
funcionamiento puede apreciarse en la gura 2.6.
2. Algoritmo Gentico implementado en SIGENOF 43
Figura 2.5: Cruce en un solo punto
Figura 2.6: Cruce en un solo punto en SIGENOF
Paso 4.4. Aplicacin del operador de Mutacin Uniforme
El operador de mutacin se aplica a todos los individuos de la poblacin, aunque
su efecto estar condicionado por el valor de probabilidad pm [0, 1] que el usuario
44 2.4. Algoritmo gentico implementado
que ejecuta el AG haya establecido para una ejecucin concreta.
Este operador se ha implementado de forma que para cada gen xk de cada
uno de los POP_SIZE cromosomas de la poblacin se genera un nmero aleatorio r
comprendido entre [0, 1], de forma que si r < pm el cromosoma xk ser mutado.
La mutacin consiste, en este caso, en el reemplazo del valor xk por un nuevo
valor real aleatorio comprendido dentro del rango de posibles valores denidos para
dicho gen entre [xmink , xmaxk ].
Paso 4.5. Evaluacin de la nueva poblacin actual
Este paso se realiza sobre la nueva poblacin de individuos tal y como se describi
en el Paso 2.
Paso 4.6. Mecanismos de Elitismo
Puede suceder que el mejor miembro de una poblacin falle en la reproduccin
de descendientes para la siguiente generacin. Por este motivo se ha optado por
la inclusin de una estrategia elitista en el AG de forma que se resuelva esta po-
sible debilidad copiando los mejores individuos de una generacin en la siguiente
generacin, de forma incondicional.
Se ha implementado la estrategia de elitismo de la siguiente forma:
1. Se busca el mejor cromosoma de la poblacin actual de POP_SIZE individuos
y se almacena en la variable mejor_actual.
2. Se busca el peor cromosoma de la poblacin actual de POP_SIZE individuos y
se almacena en la variable peor_actual.
3. Se compara el valor del tness del mejor cromosoma de la poblacin actual
(mejor_actual) con el mejor cromosoma de las generaciones anteriores (me-
jor_cromosoma).
Si el mejor cromosoma de la poblacin actual (mejor_actual) es mejor que
el mejor cromosoma de las generaciones anteriores, es decir, tiene un tness
mayor, se guarda como mejor cromosoma el de la poblacin actual. Es decir,
mejor_cromosoma = mejor_actual.
2. Algoritmo Gentico implementado en SIGENOF 45
En caso contrario, se sustituye el peor cromosoma de la poblacin actual
(peor_actual) por el mejor cromosoma de las generaciones anteriores. Es decir,
peor_actual = mejor_cromosoma.
2.4.5. Paso 5. Terminacin del AG
El AG implementado naliza, de forma normal, su bucle de ejecucin cuando el
contador generacin alcanza el valor denido en la variable MAXGENS por el usuario
que ejecuta el AG. Otra forma alternativa de nalizar el AG es a travs de la
interaccin del usuario con el Interfaz Grco de forma explcita. Este algoritmo se
ejecuta tantas veces como ERAS han sido denidas por el usuario de la herramienta.
Tras la nalizacin del AG se habrn generado dos chero log de salida con los
nombres ./salida_ag_DD.MM.AAAA_HH.MM.SS.txt y ./soluciones_ag_DD.MM.AAAA
_HH.MM.SS.txt respectivamente, donde DD, MM y AAAA corresponden al da, mes y
ao de la ejecucin respectivamente, mientras que HH, MM y SS a la hora, minutos y
segundos.
El contenido del primer chero de salida (salida_ag) se organiza en cuatro
secciones precedidas por un encabezamiento:
1. Encabezamiento que muestra el nombre de la herramienta, SIGENOF, junto
con la fecha y la hora de ejecucin.
2. Seccin que describe la funcin J que se ha optimizado. En ella se muestra la
descripcin aritmtica de la funcin, as como los valores [xmink , xmaxk ] denidos
para cada variable xk de la funcin.
3. Seccin que muestra los parmetros introducidos para la ejecucin del AG:
nmero de eras ejecutadas (ERAS), nmero de generaciones para cada una de
las eras (MAXGENS), nmero de individuos de la poblacin (POP_SIZE), proba-
bilidad de cruce (pc) y probabilidad de mutacin (pm).
4. Seccin de soluciones, en las que se muestran las mejores soluciones encontra-
das por el AG en cada era.
5. Seccin resumen del proceso, en la que se detallan los resultados de la ejecu-
cin. Se muestran datos como el tiempo de ejecucin empleado por el AG para
46 2.4. Algoritmo gentico implementado
llegar a las soluciones, as como el valor mximo, medio y desviacin estndar
de las soluciones encontradas en todas las eras de la ejecucin del AG.
El contenido del segundo chero de salida (soluciones_ag) es ms sencillo y se
organiza en una nica seccin precedida, al igual que el chero anterior, por un
encabezamiento:
1. Encabezamiento que muestra el nombre de la herramienta, SIGENOF, junto
con la fecha y la hora de ejecucin.
2. Seccin con los mejores valores de la funcin de adaptacin para cada una de
las generaciones de las que consta cada era.
Se incluye en el Apndice D un listado de los dos chero log obtenidos por SIGENOF
para una determinada ejecucin.
Captulo 3
Interfaz Grco de Usuario de
SIGENOF
3.1. Librera grca utilizada
Para la implementacin del Interfaz Grco de Usuario, GUI en lo sucesivo,
se ha empleado la librera grca GTK+
1
, la cual se integra perfectamente con el
lenguaje de programacin elegido para la implementacin del AG, el lenguaje C.
Esta librera, bsicamente, proporciona un conjunto de componentes tiles en el
diseo de GUIs que permiten el desarrollo de aplicaciones que podrn ejecutarse
en distintas plataformas software. Los aspectos decisivos que han condicionado la
eleccin de esta librera para la implementacin del GUI han sido:
GTK+ es software libre y parte del proyecto GNU
2
.
Permite el desarrollo de aplicaciones grcas multiplataforma.
Proporciona un abanico amplio de componentes grcos.
Existen editores grcos, como GLADE
3
, que tambin es software libre, que
facilitan la labor de diseo del GUI.
1
www.gtk.org
2
www.gnu.org
3
glade.gnome.org y gladewin32.sourceforge.net (para MS-Windows)
47
48 3.2. Visin general
3.2. Visin general
La herramienta implementada, SIGENOF, dispone de un sencillo, cmodo e
intuitivo GUI, que sirve como front-end al AG para proporcionar interactividad con
el usuario que lo ejecuta. Este GUI permite, entre otras funcionalidades, introducir
los parmetros poblacionales bsicos del AG como el nmero de eras en las que se
va a ejecutar el algoritmo, el nmero de generaciones para cada una de estas eras y
el nmero de individuos de que constar la poblacin de cromosomas; parmetros
naturales tales como la probabilidad de cruce entre cromosomas y la probabilidad
de mutacin natural, as como el detalle de la funcin matemtica que el algoritmo
deber optimizar. Esta funcin se podr introducir de forma manual o desde un
chero almacenado con anterioridad por la propia herramienta en formato texto.
Adems se facilitan una serie de controles y visualizaciones que permitirn al usuario
pausar la ejecucin entre eras o cancelar el proceso en una era determinada, as
como observar grcamente cmo las sucesivas generaciones de soluciones varan. El
GUI tambin mostrar resultados de la ejecucin en trminos de tiempo empleado,
soluciones encontradas en cada una de las eras y valor mximo, medio y desviacin
estndar de las soluciones. Por ltimo, para que el usuario que ejecuta la herramienta
tenga una visn estimada del tiempo restante de ejecucin del AG, se visualiza en
la parte inferior del GUI una barra de progreso que avanza conforme la ejecucin
del algoritmo tambin lo hace.
3.3. Funcionalidades del GUI
Para describir todas las funcionalidades que proporciona el GUI, se ha optado
por clasicar en paneles las diferentes partes que ste aporta tal y como se puede
observar en la gura 3.1.
En total se identican los ocho paneles siguientes:
1. Panel de parmetros poblacionales.
2. Panel de parmetros naturales.
3. Panel de otros parmetros de aplicacin para el funcionamiento del AG.
4. Panel de visualizacin textual de las mejores soluciones entre eras.
3. Interfaz Grco de Usuario de SIGENOF 49
Figura 3.1: GUI de SIGENOF
5. Panel para denir, guardar o recuperar la funcin J a optimizar por la herra-
mienta.
6. Panel de visualizacin grca de las mejores soluciones para la funcin de
adaptacin en cada generacin para cada era.
7. Panel estadstico y de tiempo de ejecucin.
8. Panel de control y visualizacin del avance del proceso.
A continuacin se detallarn las funcionalidades aportadas por cada uno de los ocho
paneles anteriormente enumerados.
50 3.3. Funcionalidades del GUI
3.3.1. Panel 1: Parmetros Poblacionales
Este panel permite introducir tres parmetros que afectan a la poblacin con la
que el AG trabajar. En concreto el nmero de Eras que correr el algoritmo, el
nmero de Generaciones que cada era contendr, y el nmero de individuos de la
poblacin.
Se proporciona un botn Ayuda al usuario que informa del signicado de estos
parmetros.
Se realiza una comprobacin de que los valores introducidos son los correctos,
es decir que son nmeros positivos mayores que cero dentro del rango de posibles
valores permitidos para cada uno de los parmetros:
Nmero de Eras [1, 999]
Nmero de Generaciones [1, 99999]
Nmero de Individuos [1, 999999]
3.3.2. Panel 2: Parmetros Naturales
Permite la especicacin de dos parmetros que afectan al proceso de selec-
cin de cromosomas, reproduccin y mutacin gentica. Estos parmetros son la
Probabilidad de Cruce y la Probabilidad de Mutacin.
Se proporciona un botn Ayuda al usuario que informa del signicado de estos
parmetros.
De la misma manera que en el panel anterior, se realiza una comprobacin de
que los valores introducidos son los correctos, es decir que son nmeros positivos
mayores que cero dentro del rango de posibles valores permitidos para cada uno de
los parmetros:
Probabilidad de Cruce [0.001, 0.999]
Probabilidad de Mutacin [0.00001, 0.99999]
3.3.3. Panel 3: Otros Parmetros del AG
En este panel se pueden introducir tres parmetros adicionales que condicionarn
el comportamiento del AG de diferentes formas. Estos parmetros son: el nmero
3. Interfaz Grco de Usuario de SIGENOF 51
de cifras decimales con las que el AG trabajar internamente para la representacin
de las soluciones, un criterio adicional de terminacin (criterio psilon) y la opcin
de seleccin del mecanismo de elitismo.
Cifras decimales de precisin del AG: Nmero de cifras decimales con las que
el AG trabajar para representar las soluciones.
Criterio adicional de terminacin (psilon): Se dene un umbral a partir del
cual el AG nalizar cuando la diferencia entre el valor J de la generacin
(k+1 ) y el de la generacin (k) sea menor o igual a dicho , aunque no se
haya alcanzado el nmero mximo de generaciones indicado, es decir cuan-
do | Jk+1 Jk | . Cuando no se desee aplicar dicho criterio adicional determinacin, este parmetro se deber dejar sin contenido.
Elitismo: Esta opcin se marcar si se desea aplicar en el AG el mecanismo
de elitismo. En caso contrario se deber dejar sin marcar.
Se proporciona un botn Ayuda al usuario que informa del signicado de estos
parmetros.
De la misma manera que en los paneles anteriores, se realiza una comprobacin
de que los valores introducidos son los correctos, es decir que son nmeros positivos
mayores que cero dentro del rango de posibles valores permitidos para cada uno de
los parmetros:
Cifras decimales de precisin del AG [1, 6]
Epsilon [0, 000001, 99999999]
3.3.4. Panel 4: Ventana de Resultados
Este panel muestra, para cada una de las eras, la mejor solucin encontrada. La
informacin que se visualiza es la siguiente:
Informacin del nmero de era.
Valor mximo obtenido para la funcin J, junto con los valores xk que la
maximizan.
52 3.3. Funcionalidades del GUI
Si se ha establecido un valor como criterio de terminacin adicional, se
muestra la informacin de la generacin en la que se ha alcanzado dicho umbral
para cada una de las eras.
Si el proceso ha sido cancelado por el usuario antes de la nalizacin del AG,
se muestra dicha informacin en este panel.
A continuacin se muestra la salida del AG en la ventana de resultados para una
ejecucin determinada:
ERA 1: MEJOR SOLUCION (11,180 5,627) = 35,739 :: (epsilon en generacion 4)
ERA 2: MEJOR SOLUCION (9,598 4,609) = 35,067 :: (epsilon en generacion 4)
ERA 3: MEJOR SOLUCION (10,633 5,609) = 37,575 :: (epsilon en generacion 7)
ERA 4: MEJOR SOLUCION (11,572 5,641) = 36,126 :: (epsilon en generacion 6)
*** Proceso cancelado por el usuario ***
3.3.5. Panel 5: Funcin J a Optimizar
Es en este panel donde se deber expresar aritmticamente la funcin que el
AG deber maximizar, mediante una sintaxis previamente denida y que se puede
consultar a travs del botn Pregunta. Este panel se divide, a su vez, en tres
subpaneles:
Subpanel 5.1: Barra de herramientas
Muestra tres botones, Abrir, Guardar y Pregunta.
Botn Abrir. Recupera desde un archivo una funcin previamente almacena-
da por la herramienta. Este botn despliega un dilogo que permite navegar
a travs del sistema de cheros local o remoto para localizar de forma sencilla
el chero buscado. El dilogo de seleccin de chero permite, incluso, aadir
accesos a carpetas favoritas para localizar posteriores cheros en esa ruta con
rapidez.
BotnGuardar. Permite guardar a disco la denicin de una funcin denida
en la herramienta, as como los valores [xmink , xmaxk ] establecidos para cada
variable xk de la funcin. El dilogo que se muestra para denir el nombre
del chero que se desea almacenar, as como su ubicacin que puede ser local
3. Interfaz Grco de Usuario de SIGENOF 53
o remota, permite aadir tambin carpetas favoritas de la misma manera a
como lo realiza el dilogo Abrir. Estas ubicaciones favoritas son compartidas
entre ambos dilogos.
Botn Pregunta. Muestra una ventana con los operadores disponibles en la
denicin de la funcin a optimizar (suma, resta, producto...), las funciones
(sin, cos, ...) y constantes que se pueden usar (e, pi, nmeros enteros, ...),
la forma de escribir las diferentes variables xk que componen la funcin (x[0],
..., x[n]), as como las reglas de precedencia que regirn la interpretacin de
la funcin.
El nombre y extensin de los cheros que almacenan las funciones que la herramienta
guarda y recupera se deja a eleccin del usuario, aunque su formato interno debe
ajustarse al denido por la herramienta segn el siguiente esquema:
Lnea de denicin sintctica de la funcin: #FUN: , ajustada a la sintaxis
denida en la seccin 2.3.
Lnea del valor mnimo que puede tomar el parmetro x1 de la funcin:
#X0_MIN: , y as sucesivamente hasta el parmetro x10.
Lnea del valor mximo que puede tomar el parmetro x1 de la funcin:
#X0_MAX: , y as sucesivamente hasta el parmetro x10.
Cuando en la denicin de la funcin nicamente se requieren n parmetros
x, de forma que n 10, no es necesario declarar las diez variables #Xi_MINy #Xi_MAX, aunque s es aconsejable hacerlo con valores cero para denir,
de manera explcita, que estas variables no tienen contenido y que no son
necesarias en la funcin denida en la lnea #FUN:. Este es el criterio seguido
por SIGENOF.
El orden de estas lneas es irrelevante, aunque para facilitar la lectura y edicin
de estos cheros la herramienta los almacena en el mismo orden en el que aqu
se han descrito.
El contenido ntegro del chero se almacena en formato ASCII, de manera
que puede ser editado externamente desde cualquier editor de textos.
54 3.3. Funcionalidades del GUI
Un ejemplo del contenido de un chero de este tipo es el siguiente:
#FUN:21.5 + x[0] * sin(4 * pi * x[0]) + x[1] * sin(4 * pi * x[1])
#X0_MIN:-3,00
#X0_MAX:12,10
#X1_MIN: 4,10
#X1_MAX: 5,80
#X2_MIN: 0,00
#X2_MAX: 0,00
#X3_MIN: 0,00
#X3_MAX: 0,00
#X4_MIN: 0,00
#X4_MAX: 0,00
#X5_MIN: 0,00
#X5_MAX: 0,00
#X6_MIN: 0,00
#X6_MAX: 0,00
#X7_MIN: 0,00
#X7_MAX: 0,00
#X8_MIN: 0,00
#X8_MAX: 0,00
#X9_MIN: 0,00
#X9_MAX: 0,00
Subpanel 5.2: rea de denicin de la funcin
Se compone de un rea de texto en el que se puede escribir la expresin que
denir la funcin a optimizar, o donde se mostrar la funcin tras recuperarla
desde un archivo.
Subpanel 5.3: rea de denicin de las variables xk
Permitir, a travs de la lista desplegable Variable de la Funcin, as como
de los campos Valor Mn. y Valor Mx., denir el rango de valores que las
diferentes variables xk (x[k]) podrn tomar. Se permite especicar los valores de
hasta diez variables xk.
3. Interfaz Grco de Usuario de SIGENOF 55
3.3.6. Panel 6: Grco de Soluciones generacionales
Las diferentes soluciones encontradas para la funcin J en cada una de las sucesi-
vas generaciones de una era particular, son visualizadas grcamente en este panel.
En el eje horizontal del grco se muestran las generaciones, mientras que en el
eje vertical se muestran las mejores soluciones obtenidas para cada generacin. Los
datos se muestran, por defecto, como barras. Esta visualizacin puede cambiarse de
forma que las soluciones se muestren como puntos seleccionando al pie del grco
el botn de radio Grfico de Puntos. Para volver de nuevo a la visualizacin de
barras se puede seleccionar el botn de radio Grfico de Barras.
Como este grco muestra las mejores soluciones obtenidas para la funcin de
adaptacin en cada generacin de una cierta era, cuando el AG cambia de era el gr-
co tambin cambia los valores mostrados. Debido a que estos cambios, en muchas
ocasiones, se realizarn rpidamente, el usuario dispone de la posibilidad de realizar
pausas entre eras para que, de este modo, se pueda observar con detenimiento el
grco de mejores soluciones antes del cambio de era, accin que se realiza pulsando
el botn Continuar.
3.3.7. Panel 7: Datos estadsticos y Tiempo de ejecucin
En este panel se muestra el tiempo de ejecucin consumido por el AG en formato
MM:SS, donde MM y SS representan los minutos y segundos respectivamente, junto
con algunos datos estadsticos del resultado de la ejecucin entre las sucesivas eras.
En concreto se muestra el Mximo Valor encontrado para J, su Media Aritmtica
y, al nalizar el algoritmo, la Desviacin Estndar entre soluciones.
3.3.8. Panel 8: Progreso y Control del proceso
Este ltimo panel proporciona una barra de progreso que muestra de forma
visual el tiempo de ejecucin del proceso, junto con tres botones adicionales, de los
cuales dos de ellos permiten el control del proceso. Estos botones son:
Botn Empezar. Valida los datos introducidos en el GUI y, en caso de estar
completos y correctos, empieza la ejecucin del AG.
56 3.4. Ejemplo de uso del GUI
Figura 3.2: Funcin de ejemplo
Botn Cancelar. Permite terminar el AG tras nalizar la ejecucin de la era
en curso.
Botn Acerca De. Proporciona informacin de la herramienta y del autor.
3.4. Ejemplo de uso del GUI
A continuacin se va a describir el uso del GUI siguiendo un caso prctico. Para
ello se ha denido la funcin de ejemplo f(x1, x2) en el espacio S tal y como se
muestra seguidamente.
f(x1, x2) =sin(
x21+x
22)
x21+x22
S = {x1 [12, 12.01], x2 [12, 12.01]}
Se presenta grcamente la funcin f(x1, x2) en S propuesta como ejemplo en
la gura 3.2.
En dicha representacin grca se puede observar que el mximo de esta funcin
para el espacio S denido se encuentra en el punto (0, 0) con un valor mximo para
3. Interfaz Grco de Usuario de SIGENOF 57
f(x1, x2) = 1. Comprobaremos al nalizar el ejemplo cmo SIGENOF se aproxima
a la solucin alrededor de dicho punto.
Se va a describir la realizacin del caso prctico en diferentes pasos, los cuales
se enumeran como:
Paso 1. Iniciar SIGENOF
Paso 2. Denir la funcin J a optimizar
Paso 3. Establecer el espacio S
Paso 4. Grabar la funcin J y su espacio S denido
Paso 5. Establecer los parmetros poblacionales
Paso 6. Establecer los parmetros naturales del AG
Paso 7. Establecer otros parmetros del AG
Paso 8. Seleccionar el tipo de visualizacin grca
Paso 9. Comenzar con la ejecucin
Paso 10. Evaluacin de las soluciones obtenidas
Es importante destacar que los pasos 1 a 8 se pueden realizar en cualquier orden
sin afectar al resultado nal del proceso.
A continuacin se describen de forma detallada las acciones a realizar para com-
pletar cada uno de los pasos anteriormente enumerados.
3.4.1. Paso 1. Iniciar SIGENOF
Se procede a ejecutar el archivo binario sigenof . En plataformas MS-Windows
el archivo binario ser sigenof.exe.
La apariencia del GUI ser como la mostrada en la gura 3.3. Los parmetros del
AG mostrarn los valores por defecto que se pueden observar en la gura, mientras
que la funcin a optimizar se encontrar en este paso sin contenido alguno a la espera
de que el usuario que ejecuta la herramienta decida qu funcin desea optimizar,
as como qu parmetros desea establecer para la ejecucin del AG.
58 3.4. Ejemplo de uso del GUI
Figura 3.3: Inicio de SIGENOF
3.4.2. Paso 2. Denir la funcin J a optimizar
La funcin J propuesta anteriormente para seguir este ejemplo fue:
f(x1, x2) =sin(
x21+x
22)
x21+x22
Esta funcin J se escribir en el rea de texto del rea Funcin J a opti-
mizar del GUI de SIGENOF, segn la sintaxis descrita en el cuadro 2.3, con la
siguiente expresin:
sin( sqrt( x[0]^2 + x[1]^2 ) ) / sqrt( x[0]^2 + x[1]^2 )
Se puede observar esta accin en la gura 3.4.
3. Interfaz Grco de Usuario de SIGENOF 59
3.4.3. Paso 3. Establecer el espacio S
El espacio S para la funcin f(x1, x2) se dene como:
S = {x1 [12, 12.01], x2 [12, 12.01]}
Este espacio de posibles valores para las variables de incertidumbre de la funcin
J que se desea optimizar se denir en el rea Variable de la Funcin.
En este rea existen tres elementos para la denicin de los distintos valores que
componen el espacio S para cada uno de las variables xk de la funcin:
Lista desplegable para establecer las distintas variables xk. A travs de esta
lista se permite denir valores para hasta diez variables xk (desde x[0] hasta
x[9]).
Valor Mnimo de S para cada xk. Para cada x[k] se indicar el valor mnimo
que la variable puede tomar.
Valor Mximo de S para cada xk. Para cada x[k] se indicar el valor mximo
que la variable puede tomar.
En nuestro caso se denirn los siguientes valores para las variable x1 y x2 de la
funcin:
Variable x1
Variable x[0] en la lista desplegable.
Valor Mn: -12,00
Valor Mx: 12,01
Variable x2
Variable x[1] en la lista desplegable.
Valor Mn: -12,00
Valor Mx: 12,01
Se puede observar el procedimiento de denicin de S en la gura 3.4.
60 3.4. Ejemplo de uso del GUI
Figura 3.4: Denicin de la funcin J y del espacio S
3.4.4. Paso 4. Grabar la funcin J y su espacio S denido.
Llegados a este punto, la funcin J y su espacio S se encuentran completamente
denidos. En este momento es conveniente guardar dichas deniciones en un che-
ro para poder recuperarlas en cualquier otro momento y poder utilizarlas con la
herramienta. Para ello pulsaremos el icono Guardar situado en la barra de he-
rramientas superior del rea Funcin J a optimizar, tal y como se muestra en
la gura 3.5.
En el dilogo para guardar la funcin, que aparece en la parte central del GUI
de la gura como dilogo Guardar Funcin, se deber introducir el nombre del
chero que almacenar los datos introducidos en pantalla, as como su ubicacin
en el sistema de archivos, que puede ser local o remoto. Para buscar carpetas en
ubicaciones remotas o en distintos lugares del sistema de archivos local, se podr
3. Interfaz Grco de Usuario de SIGENOF 61
Figura 3.5: Grabacin de la funcin J y espacio S
desplegar la opcin Buscar otras carpetas de este dilogo para ampliar, de esta
forma, su funcionalidad. Este dilogo extendido es el que se muestra en la gura
3.5.
Mediante el botn + Aadir del dilogo Guardar Funcin, se pueden
denir rutas favoritas, es decir rutas a las que se acceden con frecuencia en ope-
raciones de guardado o recuperacin de funciones.
Una funcin guardada se podr recuperar en cualquier momento pulsando el
icono Abrir de la barra de herramientas y seleccionando su ubicacin de manera
similar a como se ha realizado con el dilogo Guardar Funcin.
3.4.5. Paso 5. Establecer los parmetros poblacionales
Para este ejemplo se denieron los siguientes parmetros:
62 3.4. Ejemplo de uso del GUI
Figura 3.6: Parmetros poblacionales
Nmero de Eras: Se establecieron tres eras.
Nmero de Generaciones: Para el ejemplo se establecieron doscientas ge-
neraciones para cada una de las tres eras denidas en el parmetro anterior.
Nmero de Individuos: Se denieron cien individuos para la poblacin del
ejemplo.
Se puede observar la introduccin de estos parmetros en la gura 3.6.
3.4.6. Paso 6. Establecer los parmetros naturales del AG
En el ejemplo se denieron estos parmetros como:
Probabilidad de cruce: Se estableci una probabilidad de cruce entre pare-
jas de individuos equivalente a un 70%, es decir con un valor de 0,7.
Probabilidad de mutacin: Se deni para la ejecucin una probabilidad
de mutacin gentica para cada individuo equivalente a un 0,5%, es decir con
un valor de 0,005.
Se pueden observar estos parmetros en la gura 3.7.
Figura 3.7: Parmetros naturales
3. Interfaz Grco de Usuario de SIGENOF 63
Figura 3.8: Otros parmetros
3.4.7. Paso 7. Establecer otros parmetros del AG
Otros parmetros que se denieron para esta ejecucin fueron:
Cifras decimales de precisin del AG: Se opt por dejar el valor de este
parmetro al que por defecto la herramienta propone, tres decimales.
Criterio de terminacin adicional (epsilon): Para este ejemplo se deci-
di no aplicar el criterio de terminacin adicional epsilon, as que se dej sin
contenido el campo.
Utilizar ELITISMO en el AG: En este caso s se deseaba aplicar el me-
canismo de elitismo y, por tanto, se marc dicha casilla.
Los parmetros introducidos en este caso se pueden observar en la gura 3.8.
3.4.8. Paso 8. Seleccionar el tipo de visualizacin grca
Se seleccion como tipo de grco Grco de Barras. Esta seleccin se
realiza pulsando el botn de radio que aparece al pie del espacio reservado para la
visualizacin grca, tal y como se puede observar en la gura 3.9.
Para observar con detenimiento la grca de las mejores soluciones encontradas
por la herramienta, se decidi marcar la casilla Pausa entre Eras, de forma
que al nalizar una era su ejecucin, quede sta suspendida hasta que el usuario
pulse el botn Continuar, momento en el cual comenzar la siguiente era, y as
sucesivamente hasta la nalizacin del proceso.
64 3.4. Ejemplo de uso del GUI
Figura 3.9: Tipo de visualizacin grca
3.4.9. Paso 9. Comenzar con la ejecucin
En este ltimo paso nicamente resta pulsar el botn Empezar para que SI-
GENOF comience su ejecucin y obtenga las soluciones para el problema propuesto.
3.4.10. Paso 10. Evaluacin de las soluciones obtenidas
Tras nalizar la ejecucin de todas las eras, el AG implementado en SIGENOF
obtuvo las soluciones que se observan en la gura 3.10, as como los valores estads-
ticos de la gura 3.11.
Figura 3.10: Soluciones obtenidas por SIGENOF para el ejemplo propuesto
Figura 3.11: Resultados estadsticos para el ejemplo propuesto
3. Interfaz Grco de Usuario de SIGENOF 65
Figura 3.12: Mximo para el ejemplo propuesto
Se observa que la herramienta encontr en las tres eras similares soluciones en
las cercanas de (0, 0), con un valor mximo para J = 1, 0.
Si ahora examinamos de nuevo la forma grca de la funcin J denida para este
ejemplo, observaremos claramente cmo el valor mximo efectivamente se encuentra
en el punto (0, 0) con una cota de 1 para el espacio S denido en nuestro ejemplo.
Se muestra este mximo en la gura 3.12.
Esta solucin, a la que podramos haber llegado fcilmente mediante tcnicas
analticas convencionales, se ha alcanzado satisfactoriamente mediante una imple-
mentacin de AG. En este caso la solucin obtenida tiene una precisin muy alta
con respecto a la solucin real.
66 3.4. Ejemplo de uso del GUI
Captulo 4
Ejemplos de aplicacin de
SIGENOF
Se detallan a continuacin algunos casos particulares que describen diversas fun-
ciones matemticas con las que se ha vericado el buen funcionamiento del algoritmo
gentico implementado.
En la ejecucin de todos los casos particulares que se describen, se han empleado
los parmetros que se muestran en el cuadro 4.1:
Parmetro Valor establecido
Nmero de Eras 5
Nmero de Generaciones 100
Tamao de la Poblacin 100
Nmero de decimales de precisin 3
Criterio de terminacin epsilon NO
Uso de mecanismo de Elitismo S
Probabilidad de Cruce 80% (0,8)
Probabilidad de Mutacin 0,5% (0,005)
Cuadro 4.1: Parmetros del AG utilizados en los ejemplos
4.1. Caso particular 1
La funcin objetivo a optimizar se describe como:
67
68 4.2. Caso particular 2
Figura 4.1: Caso Particular 1
f(x1, x2) = 21.5 + x1 sin(4pix1) + x2 sin(4pix2)S = {x1 [3.0, 12.1], x2 [4.1, 5.8]}
Se representa la funcin f(x1, x2) en S en la gura 4.1.
En ella se puede observar que el valor mximo para la funcin se encuentra
entorno al punto x1 = 12 y x2 = 5.6, con un valor para f prximo a 39.
SIGENOF obtuvo como mejores soluciones las cercanas al punto x1 = 11.6 y
x2 = 5.629, con un valor para f de 38.682.
4.2. Caso particular 2
La funcin objetivo a optimizar se describe como:
f(x1, x2, x3, x4, x5, x6) = 100 (x21 + x22 + x23 + x24 + x25 + x26)
S =
x1 [3.0, 5.1], x2 [2.1, 7.8], x3 [10.1, 20.3],x4 [3.3, 4.2], x5 [15.3, 70.1], x6 [0.25, 0.35]
4. Ejemplos de aplicacin de SIGENOF 69
Fcilmente se puede comprobar que el mximo de esta funcin se encuentra en
el punto xi = 0, con 1 i 6, con una cota para f de 100.Para este caso particular, la probabilidad de mutacin se vari hasta un valor
de 2,5% (0,025) para que el algoritmo pudiera converger a la solucin con mayor
precisin. De esta forma SIGENOF coincidi con la solucin r