Upload
trinhhuong
View
215
Download
0
Embed Size (px)
Citation preview
1
1
FACULTAD DE INGENIERÍA
ESCUELA DE INGENIERÍA DE SISTEMAS
Optimización Numérica mediante Algoritmos Genéticos
Autor: José Federico Jacobi Tutor: Jorge Portilla
Caracas, Septiembre 2004
2
2
Derecho de autor
Quien suscribe, en condición de autor del trabajo titulado “Optimización Numérica mediante Algoritmos Genéticos”, declara que: Cedo a título gratuito, y en forma pura y simple, ilimitada e irrevocable a la Universidad Metropolitana, los derechos de autor de contenido patrimonial que me corresponden sobre el presente trabajo. Conforme a lo anterior, esta cesión patrimonial sólo comprenderá el derecho para la Universidad de comunicar públicamente la obra, divulgarla, publicarla o reproducirla en la oportunidad que ella así lo estime conveniente, así como, la de salvaguardar mis intereses y derechos que me corresponden como autor de la obra antes señalada. La Universidad en todo momento deberá indicar que la autoría o creación del trabajo corresponde a mi persona, salvo los créditos que se deban hacer al tutor o a cualquier tercero que haya colaborado o fuere hecho posible la realización de la presente obra.
Autor: Jose Federico Jacobi Stockhammer
C.I:. 10532524
En la ciudad de Caracas, a los 15 días del mes de Septiembre del año 2004
3
3
Aprobación
Considero que el Trabajo Final titulado
Optimización Numérica mediante Algoritmos Genéticos
elaborado por el ciudadano
José Federico Jacobi para optar al título de
Ingeniero de Sistemas
reúne los requisitos exigidos por la Escuela de Sistemas de la Universidad Metropolitana, y tiene méritos suficientes como para ser sometido a la presentación y evaluación exhaustiva por parte del jurado examinador que se designe.
En la ciudad de Caracas, a los 15 días del mes de Noviembre del año 2004
______________________ Jorge Portilla
4
4
Acta de veredicto
Nosotros, los abajo firmantes, constituidos como jurado examinador y reunidos en Caracas, el día 15 de Noviembre del 2004, con el propósito de evaluar el Trabajo Final titulado
“Optimización Numérica mediante Algoritmos Genéticos”
presentado por el ciudadano
José Federico Jacobi
para optar al título de
Ingeniero de Sistemas
emitimos el siguiente veredicto:
Reprobado ___ Aprobado ___ Notable ___ Sobresaliente ___
Observaciones:
__________________ __________________ ______________________ Yurayh Velasquez Jorge Portilla Lida Niño
5
5
AGRADECIMIENTOS
Quiero agradecerle al Profesor Jorge Portilla por todo el apoyo prestado durante la
realización de este trabajo.
6
6
DEDICATORIA
A liebe MO…
¡Gracias por el Knuth!
7
7
TABLA DE CONTENIDO
DERECHO DE AUTOR_______________________________________________II
APROBACION______________________________________________________III
ACTA DE VEREDICTO______________________________________________IV
AGRADECIMIENTOS________________________________________________V
DEDICATORIA______________________________________________________VI
TABLA DE CONTENIDO____________________________________________VII
RESUMEN___________________________________________________________X
INTRODUCCION_____________________________________________________1
I TEMA DE INVESTIGACION________________________________________4
I.1 Planteamiento del problema______________________________________ 4
I.2 Objetivos de la investigación______________________________________5
I.2.1 Objetivo General____________________________________________ 5
I.2.2 Objetivos Específicos_________________________________________5
II MARCO TEORICO________________________________________________6
II.1 El problema de la optimización numérica___________________________7
II.2 Métodos de optimización clásica___________________________________8
II.2.1 Métodos de búsqueda exhaustiva______________________________ 8
II.2.2 Métodos de optimización unidimensional__________________8
II.2.3 Métodos de optimización no restringida basados en gradientes_____ 9
II.2.4 Métodos de optimización restringida__________________________12
II.3 Algoritmos genéticos___________________________________________16
II.3.1 Codificación de cromosomas_________________________________17
II.3.2 Selección y evolución_______________________________________18
II.3.3 Criterios de parada_________________________________________22
8
8
II.3.4 Ejemplo sencillo de aplicación del algoritmo genético____________ 23
II.3.5 Fundamentos teóricos de los algoritmos genéticos_______________ 26
II.3.6 Codificación binaria versus codificación continua_______________ 32
II.4 Algoritmos genéticos como métodos de optimización convexa__________35
II.4.1 Propiedades de las regiones convexas_________________________ 36
II.4.2 Eliminación de ecuaciones lineales____________________________ 37
II.4.3 Población inicial___________________________________________ 42
II.4.4 Cruzamiento y mutación____________________________________ 43
II.4.4.1 Mutación uniforme_________________________________ 43
II.4.4.2 Mutación en frontera_______________________________ 44
II.4.4.3 Mutación no uniforme______________________________ 44
II.4.4.4 Cruzamiento aritmético_____________________________ 45
II.4.4.5 Cruzamiento simple_________________________________46
II.4.4.6 Cruzamiento heuristico______________________________47
II.4.5 Restricciones no lineales____________________________________ 48
III DESARROLLO____________________________________________________50
III.1 Metodología del desarrollo______________________________________51
III.1.1 Levantamiento de la información_______________________________ 51
III.1.2 Análisis de la información_____________________________________ 52
III.1.3 Establecimiento de soluciones alternativas_______________________ 52
III.1.4 Diseño y desarrollo___________________________________________ 53
III.1.5 Pruebas____________________________________________________ 58
IV RESULTADOS____________________________________________________ 80
V CONCLUSIONES_________________________________________________ 90
VI RECOMENDACIONES_____________________________________________93
9
9
BIBLIOGRAFIA_____________________________________________________ 94
APÉNDICE A________________________________________________________96
APENDICE B_______________________________________________________101
10
10
LISTA DE FIGURAS
Figura 1: Ejemplo de función multimodal_________________________________11 Figura 2: Ilustración del cruzamiento simple______________________________ 20 Figura 3: Modelo general de algoritmo genético____________________________21 Figura 4: Función multimodal__________________________________________ 23 Figura 5: Ejemplo de codificación de un cromosoma _______________________ 24 Figura 6: Menú principal______________________________________________ 61 Figura 7: Módulo de definición de problemas_____________________________ 63 Figura 8: Opción de editar y eliminar una función objetivo__________________ 63 Figura 9: Opción de editar y eliminar un conjunto de restricciones___________ 64 Figura 10: Módulo de optimización de funciones___________________________65 Figura 11: Reporte del proceso de optimización____________________________67 Figura 12: Ventana de gestión de parámetros______________________________68 Figura 13: Módulo de parámetros_______________________________________ 69 Figura 14: Módulo de administración de problemas________________________ 70 Figura 15: Definición de una función cuadrática de dos variables_____________ 71 Figura 16: Especificación de las restricciones lineales_______________________ 72 Figura 17: Detalle del modulo de optimización con la solución del ejemplo 1____ 72 Figura 18: Definición de la función objetivo mediante asignaciones___________ 74 Figura 19: Ejemplo de uso de un “alias”__________________________________ 74 Figura 20: Definición del problema del ejemplo 2___________________________75 Figura 21: Solución del ejemplo 2________________________________________75 Figura 22: Ejemplo de función a trozos___________________________________ 76 Figura 23: Solución del ejemplo 3________________________________________76 Figura 24: Ejemplo de la sentencia MIENTRAS FIN_MIENTRAS___________ 78
11
11
Figura 25: Definición de la función gama_________________________________ 78 Figura 26: Mínimo de la función gama___________________________________ 79
12
12
RESUMEN Optimización numérica mediante algoritmos genéticos. Autor: José Federico Jacobi Stockhammer Tutor: Prof. Jorge Portilla Caracas, Julio, 2004 Los problemas de optimización linealmente restringidos tienen aplicación en muchas áreas como por ejemplo, la investigación de operaciones. Existen diversos métodos de solución muy eficientes para esta categoría de problemas. Sin embargo, la solución de estos problemas se complica cuando se introducen elementos no lineales en la formulación del modelo. Una alternativa en estos casos es la aplicación de algoritmos genéticos como métodos de optimización numérica. El objetivo de este trabajo es el desarrollo de una herramienta que permita optimizar funciones no lineales sujetas a restricciones lineales mediante el uso de algoritmos genéticos. Estos son métodos que no usan información alguna sobre las características del problema y únicamente se basan en la evaluación de la función objetivo para explorar la región factible. Los algoritmos genéticos funcionan recombinando soluciones candidatas para producir nuevas soluciones candidatas mejores que las iniciales. La herramienta resultante es un algoritmo genético especialmente adaptado para resolver problemas de optimización convexa donde la región factible esta definida por un conjunto de restricciones lineales dadas. La herramienta es lo suficientemente robusta para permitir algunos elementos no lineales en la formulación del modelo. Estos pueden ser, por ejemplo: una función objetivo no diferenciable o inclusive discontinua y algunas restricciones no lineales. La herramienta desarrollada se basa en dos aspectos claves: La reformulación del modelo original suprimiendo las restricciones en forma de ecuaciones lineales y la definición de ciertas operaciones (operadores genéticos) entre soluciones factibles de manera que estas preserven su factibilidad.
13
13
INTRODUCCIÓN
A menudo, en muchas áreas de la investigación científica y la ingeniería, surgen muchas
situaciones las cuales se modelan como problemas de optimización numérica. Se han
desarrollado métodos de solución muy eficientes para este tipo de problemas. Sin
embargo, si se modifica ligeramente la formulación del modelo, probablemente resulte
necesario cambiar drásticamente el procedimiento de solución. También, puede ocurrir
que tales modificaciones conviertan el problema original en un problema difícil o
imposible de resolver mediante técnicas convencionales. Esta situación motiva la
búsqueda de métodos lo suficientemente robustos para producir soluciones
razonablemente buenas en una amplia variedad de contextos. Una alternativa a los
métodos convencionales son los algoritmos genéticos. Estos, han sido utilizados como
métodos de optimización en varios problemas para los cuales no se conocen
procedimientos eficientes de solución. Dos ejemplos bien conocidos son el dilema del
prisionero y el problema del agente viajero. La experiencia práctica indica que aún en
problemas difíciles como estos, los algoritmos genéticos obtienen soluciones muy
cercanas a la óptima. Un tipo de problema, muy importante en áreas como la
investigación de operaciones, es el de la optimización numérica. En este caso, los
algoritmos genéticos son aplicables en algunos problemas donde los métodos
tradicionales de optimización numérica no lo son.
Este trabajo tiene como objetivo desarrollar una herramienta que facilite la solución de
problemas de optimización numérica mediante algoritmos genéticos. El cumplimiento
de este objetivo requiere implementar un algoritmo genético especialmente adaptado
para problemas de optimización numérica.
14
14
El trabajo especial de grado esta estructurado en cinco capítulos:
El capitulo I expone el tema de investigación, planteamiento del problema y objetivos
de la investigación.
El capitulo II comienza con una breve reseña sobre los métodos clásicos de
optimización. Seguidamente, describe que son los algoritmos genéticos y cuales son sus
fundamentos teóricos. El capitulo finaliza considerando todos los aspectos necesarios
para adaptar un algoritmo genético para la solución de problemas de optimización
linealmente restringidos.
El capitulo III describen la metodología empleada durante el desarrollo de la
herramienta. También se presenta un recorrido por todas sus opciones, explicando la
funcionalidad de los módulos que la componen.
El capitulo IV presenta las diversas pruebas realizadas para evaluar la herramienta. Las
pruebas incluyeron varios problemas escogidos de la literatura existente en el área de la
optimización numérica.
15
15
Capitulo I: Tema de Investigación
16
16
I TEMA DE INVESTIGACION
I.1 Planteamiento del Problema
Los métodos de optimización convencionales usan información sobre las características
del modelo que tratan de resolver. El método Simplex por ejemplo, requiere que las
restricciones del modelo sean lineales de manera que la región factible resulte convexa.
Otro ejemplo son los métodos basados en gradientes usados en modelos no lineales,
estos requieren que la función objetivo sea diferenciable. Sin embargo, existen modelos
para los cuales, hipótesis como las anteriores no siempre se cumplen. La función
objetivo puede no resultar diferenciable e inclusive discontinua. También, puede ocurrir
que la región factible no resulte convexa debido a que alguna de las restricciones del
modelo no sea lineal. En estos casos la determinación del punto óptimo se convierte en
un problema difícil y a veces sin solución. Una alternativa para modelos como los
anteriores son los algoritmos genéticos (también conocidos como algoritmos
evolutivos). Estos no usan información alguna sobre las características del problema
como por ejemplo diferenciabilidad o continuidad y únicamente se basan en la
evaluación de la función objetivo para explorar la región factible y así encontrar el
punto óptimo. Estos algoritmos funcionan sometiendo puntos dentro de la región
factible a un proceso evolutivo haciendo que estos compitan entre si. Los puntos
ganadores se reproducen entre ellos para obtener nuevos puntos factibles mejores que
los iniciales. Al final del proceso evolutivo la solución resultante es cuasi-óptima y en
muchos casos óptima.
17
17
I.2 Objetivos de la investigación
1.2.1 Objetivo General
Diseñar una herramienta que permita trabajar con problemas de optimización de
funciones de varias variables reales sujetas a restricciones lineales usando algoritmos
genéticos.
1.2.2 Objetivos Específicos
• Identificar los distintos elementos que componen un algoritmo genético y
analizar sus funciones. Esto requiere el estudio de los distintos tipos de
codificación para cromosomas, funciones de adaptación (funciones de fitness),
operadores genéticos más comunes (cruzamiento, mutación) y distintos
mecanismos de selección.
• Definir una codificación apropiada de los cromosomas y adaptar los operadores
genéticos necesarios para implementar un algoritmo genético que permita
trabajar con problemas de optimización numérica.
• Desarrollar métodos híbridos que combinen características de los algoritmos
genéticos y los métodos convencionales de optimización numérica.
• Desarrollar una interfaz fácil de usar que permita especificar problemas de
optimización numérica, así como también distintas configuraciones para el
algoritmo genético.
• Explorar la posibilidad de extender el método genético desarrollado en los
puntos anteriores para resolver problemas con restricciones no lineales.
18
18
Capitulo II: Marco Teórico
19
19
II.1 El problema de la optimización Numérica
El problema general de la programación no lineal puede enunciarse de la siguiente
manera:
Optimizar )(xf , sujeto a Ω∈x
donde f es una función real y Ω, el conjunto factible, es un subconjunto de Rn . Si Ω=Rn,
entonces se dice que el problema de optimización es no restringido. Si por el contrario,
Ω es un subconjunto de Rn entonces se dice que se trata de un problema de optimización
restringido. A menudo se define Ω mediante un conjunto de restricciones de la
siguiente forma:
0)( =xic donde nn Rxxxx ∈= ),....,,( 21 para pmi −= ,....,2,1
0)( ≤xic donde nn Rxxxx ∈= ),....,,( 21 para pi ,....,2,1=
No existe un método conocido para resolver el problema general de optimización no
lineal. Solo si la función objetivo f y las funciones ci satisface ciertas propiedades el
óptimo global puede a veces ser encontrado. Se han desarrollado para estos casos
particulares, algoritmos que permiten aproximar la solución del problema. El método de
solución depende del tipo de problema. Por ejemplo, en problemas no restringidos se
pueden usar métodos de búsqueda directos o métodos basados en gradientes. En el caso
de problemas restringidos los métodos usados se clasifican como métodos indirectos y
métodos directos. Los métodos indirectos atacan el problema extrayendo uno o más
problemas de programación lineal del problema original, mientras que los métodos
directos intentan determinar una sucesión de puntos de búsqueda.
20
20
Generalmente, esto se hace convirtiendo el problema original en uno no restringido al
cual puede aplicársele los métodos basados en gradientes.
Antes de analizar el problema de la optimización numérica mediante algoritmos
genéticos es conveniente hacer una breve reseña sobre los métodos mencionados
anteriormente. Una referencia mucho mas detallada de los métodos que se describen a
continuación puede encontrarse en (Luegenberger, 1989).
II.2 Métodos de optimización clásica
II.2.1 Métodos de búsqueda exhaustiva
La técnica más básica y menos recomendada de todas es la búsqueda exhaustiva. La
región factible se divide en un conjunto finito de puntos equidistantes entre ellos. El
mínimo (o máximo) se obtiene evaluando la función objetivo en cada uno de los puntos.
La principal desventaja de este método es que puede requerir un tiempo
extremadamente largo.
II.2.2 Métodos de optimización unidimensionales
En esencia, existen dos tipos de métodos dentro de esta categoría. El primer tipo
consiste en interpolar la función objetivo mediante otra función conocida que puede ser
analizada para hallar el óptimo. Por lo general, para interpolar la función objetivo se
suele usar un polinomio cuadrático cuyo mínimo es fácil de encontrar analíticamente.
El segundo tipo de método esta compuesto por los llamados métodos de búsqueda.
Estos son métodos que no asumen la existencia de derivadas. Dos ejemplos muy
conocidos en esta categoría son el método de Fibonacci y el método de la sección
áurea.
21
21
Estos métodos funcionan reduciendo el intervalo que contiene el óptimo mediante la
evaluación de la función objetivo en puntos cuidadosamente seleccionados. La idea
básica es que la reducción del intervalo que contiene el optimo sea máxima con la
menor cantidad posible de evaluaciones en los puntos de prueba.
II.2.3 Métodos de optimización no restringida basados en gradientes
Estos métodos se basan en el cálculo diferencial en varias variables. Uno de los métodos
mas conocido es sin duda, el de Cauchy. La idea es comenzar en un punto inicial y
minimizar la función objetivo a lo largo de la dirección del gradiente. Este proceso de
minimización unidimensional produce un nuevo punto donde la función objetivo mejora
su valor. La sucesión de puntos obtenidos se puede describir mediante la siguiente
formula:
)(1 nnnn f xxx ∇−=+ γ
En la expresión anterior γn es un escalar no negativo que minimiza la función f en la
dirección del gradiente. La escogencia del punto inicial determina si la sucesión xn
converge hacia un mínimo local o hacia un mínimo global. Esta es una de las
desventajas más importantes del método de Cauchy. El método puede terminar en un
óptimo local si el punto inicial no se encuentra lo suficientemente próximo del óptimo
global.
Otro método muy importante dentro de esta categoría son los derivados del método de
Newton. Estos se basan en aplicar el método de Newton para resolver sistemas de
ecuaciones no lineales al sistema dado por:
0=∇f
22
22
El método de Newton cuando converge lo hace muy rápidamente (orden cuadrático).
Sin embargo presenta algunas desventajas. Al igual que el método de Cauchy, el
método de Newton puede terminar en un óptimo local si la aproximación inicial no es
suficientemente buena. Más aun, el método podría no converger dependiendo de
características de la función objetivo. Es decir, el método no es globalmente
convergente. Otra desventaja es que el método requiere del cálculo de matrices
hessianas que a veces pueden estar mal condicionadas. En la práctica se aplican
variantes modificadas del método de Newton.
A continuación se describe un ejemplo que ilustra las limitaciones de los métodos
anteriores:
Considerese el siguiente problema de optimización en dos dimensiones
minimizar )2(1.1)4(),( yysenxxsenyxf +=
sujeto a 100 ≤≤ x y 100 ≤≤ y
23
23
La función objetivo f en este caso es una función multimodal. En la figura 1 puede
observarse que la función consiste de múltiples valles y cimas. Ninguno de los métodos
comentados anteriormente produciría una respuesta correcta a menos que la
aproximación inicial fuese muy cercana al óptimo global. La razón es que los métodos
basados en gradientes solo usan información local para explorar la región factible y por
lo tanto, fácilmente pueden converger hacia óptimos locales.
Figura 1: Ejemplo de función multimodal (Fuente propia)
24
24
II.2.4 Métodos de optimización restringida
En esta categoría se encuentran el método Simplex. Este método es el más usado para
resolver problemas lineales de la forma:
Optimizar: nn xcxcxc +++ .....2211
sujeto a: Ax = b y x≥0
donde
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
mnmm
n
n
aaa
aaaaaa
............
..
..
21
22221
11211
A ,
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
nx
xx
.
.2
1
x y
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
nb
bb
.
.2
1
b
El método Simplex funciona visitando soluciones “básicas”. Estas, se calculan fijando
un numero suficiente de variables a sus respectivos limites para reducir las restricciones
Ax = b a un sistema con igual número de ecuaciones e incógnitas que puede ser resuelto
de manera única para las variables restantes. Las soluciones básicas representan puntos
en la frontera del conjunto factible definido por las restricciones Ax = b y x≥0. El
método, por lo tanto, explora puntos en los bordes de la región factible hasta que la
función objetivo no mejore más su valor en esos puntos. Para garantizar que el método
sea correcto hace falta un resultado fundamental en la programación lineal. Este
asegura, que si la función objetivo alcanza su valor óptimo dentro de la región factible,
entonces también lo alcanza en una solución básica. Este resultado es necesario para
concluir que el método siempre terminara con el valor óptimo de la función objetivo,
siempre y cuando el óptimo exista.
25
25
Otro método importante de optimización restringida es el método aproximación lineal
secuencial de Frank-Wolfe. Este método es aplicable para los problemas donde las
restricciones son lineales pero la función objetivo no es lineal.
El método sustituye la función objetivo no lineal f por una sucesión de aproximaciones
lineales. Para problemas de optimización linealmente restringidos, estas aproximaciones
permiten la aplicación repetida de Simplex. Por lo tanto, este método resulta adecuado
para restricciones lineales del tipo Ax = b y x≥0. La idea es combinar aproximaciones
lineales de la función objetivo (que permiten usar el método Simplex) con
procedimientos de búsqueda unidimensionales (como cualquiera de los mencionados
con anterioridad). En líneas generales, el método se puede describir como sigue: Dada
una solución factible x0 para del conjunto Ax = b y x≥0, se utiliza una aproximación
lineal de la función objetivo f(x) dada por la expansión de primer orden del polinomio
de Taylor de f(x) alrededor de x0. Es decir, f(x) se aproxima mediante la siguiente
expresión,
∑=
−∇+=−∂
∂+≈
n
jj
j
ffxxx
fxff
1000
00 ))(()()(
)()()( xxxx
xx
Como f(x) y 00 )( xxf∇ tienen valores fijos, se pueden eliminar para obtener una función
objetivo lineal equivalente,
∑=
=∇=n
jjj xcfg
10 )()( xxx donde
jj x
fc
∂∂
=)( 0x
26
26
Después se aplica el método Simplex al problema de programación lineal que resulta
(maximizar g(x) sujeta a Ax = b y x≥0) a fin de obtener su solución optima xLP. La
función objetivo se incrementara a lo largo del segmento rectilíneo desde xLP hasta x0.
Sin embargo, la aproximación lineal puede no ser buena para una x lejana de x0, por lo
que quizá la función objetivo no lineal puede no continuar creciendo durante toda la
trayectoria del segmento desde xLP hasta x0. Así, en lugar de aceptar xLP como la
siguiente solución de prueba, se elige el punto sobre este segmento de recta que
maximiza la función objetivo no lineal. Este punto se puede encontrar realizando una
búsqueda unidimensional con los procedimientos descritos anteriormente. La única
variable para los propósitos de esta búsqueda es la fracción de la distancia total de xLP
hasta x0. El punto obtenido de esta búsqueda se convierte entonces en una nueva
solución de prueba para iniciar la siguiente iteración del algoritmo, como se acaba de
describir. La sucesión de soluciones prueba generadas por las iteraciones converge a
una solución optima para el problema original, de manera que el algoritmo se detiene
cuando las soluciones prueba están los suficientemente cerca entre sí como para poder
concluir que se llegó a esta solución optima.
27
27
Uno de los primeros métodos usados para resolver problemas no lineales fue la técnica
secuencial de minimización no restringida o mejor conocido como SUMT (Sequential
Unconstrained Minimization Technique) desarrollado por Fiacco y McCormick en
1968. Los problemas de optimización que SUMT puede resolver son problemas no
lineales de la forma
Optimizar: )(xf sujeto a: 0xg =)( y 0xh ≥)(
donde RRf n →: , mn RR →:g y pn RR →:g
La idea detrás del método es sustituir el problema original por una sucesión de
problemas de optimización no restringida, cuyas soluciones convergen a una solución
del problema original. La ventaja de este enfoque es que resulta más fácil resolver un
problema de optimización no restringida usando cualquiera de los métodos
mencionados en la sección anterior que resolver un problema restringido. En SUMT las
restricciones del problema se usan para construir una función de penalización P(x).
Esta, a su vez es usada para reemplazar la función objetivo por una nueva función
objetivo de la forma f(x)-rP(x) donde r es un valor que disminuye a medida que el
método avanza. SUMT es aplicable a problemas no lineales restringidos. Sin embargo,
se ha observado que SUMT es propenso a la inestabilidad numérica. Esta particularidad
limita el uso del método a problemas no lineales de solo unas cuantas decenas de
variables o inclusive menos, dependiendo del problema.
28
28
III.3 Algoritmos Genéticos
Los algoritmos genéticos son métodos radicalmente distintos de los métodos clásicos de
optimización. Por ejemplo, los algoritmos genéticos no recurren al uso de gradientes o
hessianos. Consecuentemente, son aplicables a clase mucho más amplia de problemas.
Un algoritmo genético es una técnica de búsqueda probabilística que se fundamenta en
los principios de la genética. Los algoritmos genéticos fueron inventados por John
Holland en la década de 1960 y fueron desarrollados por él, sus estudiantes y colegas de
la universidad de Michigan entre 1960 y 1970. Desde sus inicios, los algoritmos
genéticos han sido usados como una herramienta en inteligencia artificial, optimización,
entrenamiento de redes neurales y muchas otras áreas.
Considérese nuevamente el problema de optimización:
Optimizar )(xf , sujeto a Ω∈x
La idea general de los algoritmos genéticos consiste en comenzar con conjunto inicial
de puntos de Ω, que se denotara por P(0) conocido como población inicial. La función
objetivo f es entonces evaluada en cada punto de P(0). Mediante estas evaluaciones se
crea una nuevo conjunto de puntos P(1). La creación de P(1) involucra ciertas
operaciones sobre los puntos de P(0). Estas operaciones se conocen como cruzamiento
y mutación. El propósito de estas operaciones es crear una nueva población donde el
valor promedio de la función objetivo sea mejor que el de la población anterior. El
procedimiento anterior se repite generando poblaciones P(2), P(3)…, hasta que un
29
29
criterio de parada previamente escogido se satisfaga. Un algoritmo genético, en esencia,
procesa poblaciones, reemplazando sucesivamente cada población con otra.
II.3.1 Codificación de cromosomas
Una diferencia importante de los métodos tradicionales de optimización con los
algoritmos genéticos, es que estos no operan directamente sobre los puntos de Ω, sino
con una codificación de Ω. Esta codificación se realiza estableciendo una
correspondencia entre los puntos de Ω y un conjunto de cadenas de símbolos, todas de
la misma longitud. Estas cadenas de símbolos se les conocen comúnmente con el
nombre de cromosomas. Cada cromosoma consiste de elementos que pertenecen a un
conjunto de símbolos, llamado, el alfabeto. Por ejemplo, un alfabeto muy usado es el
conjunto 0,1. En este caso, los cromosomas son simplemente cadenas de dígitos
binarios. En general, si Σ denota el alfabeto usado, entonces una codificación es una
función h tal que h: Ω → Σ L donde L es la longitud de las cadenas de símbolos (o
cromosomas).
A cada cromosoma le corresponde un valor asociado a la función objetivo, conocido
como aptitud (o fitness en ingles). La notación para la función de aptitud es como sigue:
Para cada cromosoma x, su aptitud esta dada por f(x). Por conveniencia se usa la misma
letra que denota a la función objetivo f. Quedara claro del contexto, si se esta evaluando
la función objetivo en un punto de la región factible o si se esta evaluando la aptitud de
un cromosoma.
La escogencia de la codificación de los cromosomas y la función de aptitud se conocen
como la representación del problema. Ambos elementos están íntimamente relacionados
con el problema en cuestión. Por lo tanto, constituyen un requisito esencial para la
aplicación de un algoritmo genético a cualquier problema de optimización.
30
30
Una vez que la representación del problema ha sido establecida el algoritmo genético
puede aplicarse.
El primer paso es inicializar la primera población de cromosomas, P(0). Esto por lo
general, se realiza de manera aleatoria. Después de haber inicializado la primera
población, se seleccionan y recombinan los cromosomas mediante las operaciones de
mutación y cruzamiento. Este proceso se repite por un número de iteraciones hasta que
una condición de parada previamente definida se cumpla. Cada iteración del proceso se
efectúa en dos etapas conocidas como selección y evolución
II.3.2 Selección y evolución.
Durante la primera etapa, se aplica una operación llamada selección, donde se forma un
conjunto M(k) con el mismo número de elementos de P(k). El número de elementos
presentes en P(k) es un parámetro importante de los algoritmos genéticos y se conoce
como el tamaño de la población. En adelante, el tamaño de la población se denotara por
N. El conjunto M(k) se obtiene a partir de P(k) usando el procedimiento aleatorio que se
describe a continuación: Cada miembro m(k) de M(k) es igual a un miembro x(k) de P(k)
con probabilidad
∑ )()()(
)(
k
k
ff
xx
En la expresión anterior, la suma se toma sobre todos los cromosomas miembros x(k) de
la población P(k).
En otras palabras, los cromosomas son seleccionados de P(k) para formar parte de M(k)
con probabilidad proporcional a su aptitud. El proceso de selección anterior se conoce
como muestreo por ruleta.
31
31
La razón es la siguiente: Considérese una ruleta con distintos números en donde la
cantidad de números asociados a cada cromosoma esta en proporción a su aptitud. A los
cromosomas más aptos se les asignan más números de la ruleta que a los menos aptos.
El proceso de selección de un cromosoma es equivalente a que la ruleta gire resultando
seleccionado el cromosoma con el número ganador. Los cromosomas mas aptos serán
los que mas chance tienen de resultar ganadores, debido a que les corresponden mas
números de la ruleta que a los demás. El cromosoma ganador pasa a formar parte de la
población M(k). Este proceso se repite N veces donde N es el tamaño de la población.
Al final, la población M(k) contendrá N cromosomas al igual que P(k). La selección
mediante muestreo por ruleta es uno de los mecanismos de selección mas conocidos.
Sin embargo, no es el único. Un mecanismo alternativo es la selección por torneo que
procede como sigue: Primero se seleccionan aleatoriamente un par de cromosomas de
P(k). Luego, se comparan sus aptitudes y se selecciona el cromosoma mas apto de los
dos para formar parte de M(k). Esta operación se repite hasta que la población M(k)
contenga N cromosomas.
Durante la segunda etapa conocida como evolución se aplican las operaciones de
cruzamiento y mutación. La operación de cruzamiento requiere dos cromosomas,
llamados cromosomas “padres“. El cruzamiento produce dos descendientes de los
cromosomas padres y se realiza de manera probabilística. Es decir, un cromosoma se
cruza con otro con una probabilidad dada pc. Esta probabilidad se conoce como
probabilidad de cruzamiento.
Esto implica que el cruzamiento en un algoritmo genético se implementa como un
evento aleatorio cuya probabilidad esta dada por un parámetro pc. Esta probabilidad pc
debe ser igual para cualquier cromosoma presente en M(k). Existen varias maneras de
escoger los cromosomas que se cruzaran.
32
32
Por ejemplo, se puede escoger cualquier par de cromosomas aleatoriamente de la
población M(k). Estos se cruzaran si al lanzar una moneda sesgada con probabilidad pc
sale cara. En caso de salir sello, estos no se cruzan.
El cruzamiento más elemental es el simple. En este tipo de cruzamiento se escoge
aleatoriamente un numero entero entre 1 y L-1 (donde L es la longitud de los
cromosomas) de acuerdo a una distribución uniforme. Este número se conoce como el
punto de cruzamiento. El cruzamiento se realiza intercambiando las subcadenas de los
cromosomas padres que se encuentran separadas por el punto de cruzamiento como lo
muestra la figura 2.
Figura 2: Ilustración del cruzamiento simple (Fuente propia)
Después de la operación de cruzamiento, los cromosomas hijos son agregados a una
población inicialmente vacía D(k) . Los cruzamientos se efectúan hasta que la población
D(k) tenga la misma cantidad de cromosomas que M(k)
Finalmente, la operación de mutación se aplica a cada cromosoma miembro de D(k)
para formar P(k+1). La operación de mutación cambia aleatoriamente un símbolo de
cada cromosoma de D(k) con una probabilidad dada pm. Esta probabilidad se conoce
como probabilidad de mutación. En el caso del alfabeto binario, este cambio
corresponde a invertir un digito binario aleatoriamente escogido. Si el alfabeto contiene
más símbolos, entonces el cambio requiere la sustitución arbitraria de cualquier
símbolo con otro símbolo del alfabeto.
33
33
Típicamente, el valor de la probabilidad de mutación pm es muy pequeño. (Por ejemplo,
0.01) De manera que pocos cromosomas sufrirán algún cambio debido a la operación de
mutación.
Se habrá notado que el procesamiento de los cromosomas partiendo de una población
P(k) para obtener una nueva población P(k+1) requiere dos poblaciones intermedias
M(k) y D(k). Sin embargo, estas no son necesarias. Solo se consideraron con la
finalidad de que la descripción resultase más sencilla. En realidad, es posible obtener
P(k+1) directamente de P(k) sin pasar por poblaciones intermedias. A continuación se
presenta un modelo general de algoritmo donde se muestra que no es necesario
considerar poblaciones intermedias.
1) Generar aleatoriamente una población de cromosomas de tamaño N. 2) Calcular la función de aptitud para cada cromosoma en la población. 3) Repetir los siguientes pasos hasta que se hayan creado N cromosomas nuevos.
a) Seleccionar un par de cromosomas de la población actual. En este paso la probabilidad de selección para cualquier cromosoma es directamente proporcional a su aptitud. Un cromosoma puede ser seleccionado más de una vez.
b) Cruzar los cromosomas seleccionados sobre un punto aleatoriamente escogido con probabilidad pc (Probabilidad de cruzamiento) c) Mutar los nuevos descendientes en cada posición con probabilidad pm.
4) Reemplazar la población actual con la nueva población. 5) Ir al paso 2)
Figura 3: Modelo general de algoritmo genético. Fuente: (Mitchell,1996)
Una vez que el algoritmo finaliza, el cromosoma mas apto obtenido durante todo el
proceso será la solución candidata para el problema. Por lo tanto, será necesario
registrar el cromosoma con mayor aptitud obtenido a lo largo de la ejecución del
algoritmo. Después de cada iteración este cromosoma servirá como la solución
candidata para el problema original.
34
34
Existen muchas variantes y mejoras del algoritmo genético presentado anteriormente.
Por ejemplo, en vez de registrar un único cromosoma en cada iteración, se puede
registrar los mejores cromosomas de la población actual y copiarlos en la nueva
población. Esta práctica se conoce como elitismo. La estrategia elitista puede resultar en
una población dominada por súper-cromosomas. Sin embargo, la experiencia práctica
sugiere que el elitismo a menudo mejora el desempeño de los algoritmos genéticos.
II.3.3 Criterio de parada
Otro aspecto importante del algoritmo genético es el criterio de parada. En general, no
existe un criterio que permita verificar la convergencia de las soluciones obtenidas
mediante un algoritmo genético. Así que por lo general, el criterio de convergencia se
implementa usando las siguientes alternativas:
• Criterio de no mejoría: Si el cromosoma más apto no mejora en un número
prefijado de generaciones la evolución termina.
• Criterio estadístico: Si la media y la desviación estándar de la adaptación de
la población alcanzan un cierto valor entonces la evolución termina.
• Criterio del número de iteraciones: Si el algoritmo no se detiene debido a
ninguno de los criterios anteriores se ha cumplido entonces la evolución
termina después de un número de iteraciones prefijado.
35
35
II.3.4 Ejemplo sencillo de aplicación de algoritmo genético
Hasta ahora, la descripción sobre los algoritmos genéticos ha sido bastante genérica. El
siguiente ejemplo muestra como se puede aplicar un algoritmo genético para resolver un
problema de optimización específico. Considérese el siguiente problema de
optimización no lineal (Chong & Zak, 2001):
Maximizar la función f:R2→R dada por,
3)
5(10)1(3),(
222222
)1(53)1(2
yxyxyx eeyxxexyxf
−+−−−+−− −−−−−=
donde,
33,33/],[ 2 ≤≤−≤≤−∈=Ω yxRyx
El comportamiento de la función objetivo f de esta función puede observarse en la
figura 4.
Figura 4: Función multimodal (Fuente propia)
36
36
Para aplicar el algoritmo genético descrito con anterioridad es necesario primero definir
una codificación apropiada para el problema. Una codificación apropiada para este caso
(debido a que se trata de un problema bastante pequeño) es usar un esquema de
representación binaria de 32 bits para los cromosomas. Los primeros 16 bits codifican la
variable x y los últimos 16 bits codifican para la variable y. Sin embargo, las variables x
y y se encuentran en el intervalo [-3,3]. Lo cual implica que es necesario definir una
correspondencia entre el intervalo [-3,3] y el intervalo [0,216-1]. Esto puede hacerse
mediante una simple traslación y escalado, utilizando la siguiente transformación:
)3(6
1216
+−
→ tt donde 33 ≤≤− t
Finalmente, los enteros en el intervalo [0,216-1] son representados como cadenas de 16
dígitos binarios. Esto se hace usando la representación binaria sin signo de cada entero
en el intervalo [0,216-1]. Esta representación define la codificación de las variables x y y
del problema original. Un cromosoma, en este caso, es simplemente la concatenación de
las cadenas de dígitos binarios correspondientes a las variables x y y. Por ejemplo, el
punto (-1,3) es codificado como se muestra en la figura 5.
Después de haber definido una codificación adecuada para el problema, es necesario
definir la función de aptitud. En este caso, la función de aptitud puede, simplemente
definirse como la función objetivo f evaluada en la representación real de cada
cromosoma. Esto implica que es necesario decodificar cada cromosoma para poder
calcular su aptitud.
Figura 5: Ejemplo de codificación de un cromosoma (Fuente propia)
37
37
Una vez que la codificación y la aptitud han sido definidas es posible aplicar el
algoritmo genético de la figura 3. Para este ejemplo en particular, se decidió adaptar el
programa en lenguaje PASCAL que aparece en (Goldberg, 1989) usando la misma
codificación y función de aptitud definidas anteriormente. En el apéndice B se
encuentra el código completo del programa utilizado. Los parámetros usados fueron:
• Tamaño de la población (N): 20
• Probabilidad de cruzamiento (pc): 0.75
• Probabilidad de mutación (pm): 0.0075
• Numero de iteraciones : 50
El óptimo encontrado por el algoritmo genético fue (0.0615, 1.5827). El valor de la
función objetivo en este punto es 8.1013.
Resulta interesante notar que este ejemplo puede también atacarse usando algunos de
los métodos tradicionales de optimización. La función FMINUNC del software
numérico MATLAB es una implementación muy optimizada de un algoritmo de
optimización basado en gradientes.
El óptimo encontrado mediante FMINUNC fue (-0.0093,1.5814). El valor de la función
objetivo para este punto es 8.1062.
Puede observarse que el valor de la función objetivo encontrado mediante MATLAB es
mejor que el valor obtenido por el algoritmo genético. Nótese, sin embargo, que no es
mucho mejor. De hecho, ambos valores coinciden con precisión de hasta una centésima.
El ejemplo anterior muestra que la aplicación de un algoritmo genético depende
fundamentalmente de la codificación y la función de aptitud que se hayan definido para
el problema en cuestión. Esta característica permite que los algoritmos genéticos sean
aplicables a una gran variedad de situaciones y problemas.
38
38
III.3.5 Fundamentos teóricos de los algoritmos genéticos
A pesar de que los algoritmos genéticos son fáciles de describir y de implementar, su
comportamiento puede ser complicado. En esta sección se describen los fundamentos
teóricos de los algoritmos genéticos. La teoría tradicional sobre los algoritmos genéticos
fue primeramente formulada por Holland en 1975. (Véase [Holland,1975] también
[Goldberg, 1989]). Holland plantea que los algoritmos genéticos funcionan
descubriendo, reforzando y recombinando “bloques constructivos” operando de manera
paralela. La idea es que las mejores soluciones tienden a estar constituidas por buenos
bloques constructivos. Estos bloques constructivos son combinaciones específicas de
dígitos binarios que le confieren a los cromosomas en los que están presentes una alta
aptitud.
En 1975, Holland introdujo la noción de esquemas para formalizar el concepto intuitivo
de “bloque constructivo”. Un esquema es una cadenas de ceros, unos y asteriscos donde
los asteriscos representan comodines. Por ejemplo, el esquema H=1****1 representa el
conjunto de cadenas de seis dígitos binarios que comienzan y terminan con 1. Las
cadenas que cumplen con un determinado esquema H se conocen como instancias de H.
Nótese que no es posible describir cualquier subconjunto de cadenas de longitud l
mediante esquemas. Existen 2l cadenas distintas de longitud l y por lo tanto l22 posibles
subconjuntos de cadenas de longitud l, pero solo existen 3l esquemas. Sin embargo, la
teoría asegura que los esquemas son los bloques constructivos que los algoritmos
genéticos procesan mediante los operadores de cruzamiento y mutación.
Los esquemas son procesados de la manera siguiente: Cualquier cadena de longitud l es
una instancia de 2l esquemas.
39
39
Por lo tanto, cualquier población de cromosomas de tamaño n debe contener instancias
de entre 2l y ln2 esquemas diferentes. Si por ejemplo, todas las cadenas son idénticas,
entonces existen instancias de 2l esquemas distintos. En caso contrario, el número de
esquemas es menor o igual que ln2 . Esto significa, que mientras un algoritmo genético
esta evaluando la aptitud de n cadenas en una población, en realidad, esta
implícitamente estimando la aptitud promedio de un número mayor de esquemas. En
este análisis, se define la aptitud promedio de un esquema como el promedio de las
aptitudes de todas las posibles instancias de dicho esquema. Por ejemplo, en una
población aleatoriamente generada de n cromosomas, aproximadamente n/2 de estos
serán instancias del esquema 1***…..* y los otros n/2 serán instancias del esquema
0***…..*. La evaluación de los n/2 cromosomas que son instancias de 1***…..*1
proporciona un estimado de la aptitud promedio de este esquema. Necesariamente, se
trata de un estimado, debido a que las instancias evaluadas en una población de tamaño
típico son en realidad una muestra muy pequeña de todas las posibles instancias de un
esquema en particular. De la misma manera en que un algoritmo genético no representa
explícitamente los esquemas presentes en una población, tampoco evalúa explícitamente
la aptitud promedio de estos esquemas. Sin embargo, como se demostrara mas adelante,
el comportamiento de un algoritmo genético, en términos del incremento o decremento
del número de instancias de un esquema dado en una población, puede ser descrito
como si el algoritmo en verdad estuviese explícitamente evaluando los promedios de
estas aptitudes.
40
40
La dinámica de los incrementos y decrementos de las instancias de un esquema dado
puede explicarse de la siguiente manera.
Sea H un esquema con por lo menos una instancia en la población en la iteración t y sea
m(H,t) el número de instancias presentes en la población en la iteración t y sea u(H,t) la
aptitud promedio observada de H en t (es decir, el promedio de las aptitudes de las
instancias de H presentes en la población en la iteración t). Denótese por E(m(H,t+1))
el número esperado de instancias de H en la iteración t+1. Asumiendo que el
mecanismo de selección por ruleta se aplica tal como se explico anteriormente, el
número esperado de descendientes de una cadena particular x será igual a
∧
)(
)(
tf
f x
En la expresión anterior )(xf es la aptitud de la cadena x y ∧
)(tf es la aptitud promedio
de la población en la iteración t. Entonces, si adicionalmente se supone que H∈x y que
x aparece en la población en la iteración t se cumplirá que,
∧∈
∧ ==+ ∑)(
),(),(
)(
)())1,((tf
tHmtHu
tf
xftHmEHx
(Expresión 1)
La expresión anterior debe ser cierta, ya que por definición:
),(
)()1,(
tHm
xftHu Hx
∑∈=+ para todo x perteneciente a la población en la iteración t.
Las expresiones anteriores se dedujeron ignorando los efectos de los operadores de
mutación y cruzamiento. Estas operaciones pueden destruir o crear instancias de H. Por
simplicidad, considérese solamente el efecto destructivo del cruzamiento y la mutación
en la población. Claramente, el efecto destructivo debe ser responsable del decremento
de las instancias de los esquemas H de la población. La inclusión de estos efectos
requiere modificar la expresión 1 para determinar una cota inferior de E(m(H,t+1)).
41
41
Sea pc la probabilidad de cruzamiento, y supóngase que una instancia de H haya sido
escogida para ser padre. En este caso, se dice que el esquema H sobrevive bajo el
cruzamiento si uno de sus descendientes es también una instancia del esquema H. En
caso contrario, se dice que el cruzamiento destruye el esquema H. Una cota inferior para
la probabilidad de supervivencia del esquema H bajo cruzamiento (denotada por Sc(H))
esta dada por,
⎟⎠⎞
⎜⎝⎛
−−≥
1)(1)(
lHdpHS cc (Expresión 2)
En la expresión anterior d(H) es la distancia del esquema y se define como la distancia
entre el primero y ultimo digito binario en el esquema cuyos valores sean 1 o 0. (es
decir, que no sean asteriscos) .Por ejemplo, d(1****1)=5 y d(****1**0**10**)=7. De
acuerdo a la definición de d(H) la fracción de cruzamientos destructivos para el
esquema H será d(H)/(l-1).
Como pc es la probabilidad de cruzamiento para cualquier instancia de H, entonces la
probabilidad de que el esquema H resulte destruido será a lo sumo pcd(H)/(l-1). Es
importante observar que este análisis se aplica para deducir una cota superior para la
probabilidad de que un cruzamiento resulte destructivo. Esto se debe, a que puede
ocurrir que algunos cruzamientos no resulten destructivos. Por ejemplo, si un
cromosoma perteneciente al esquema H se cruza consigo mismo este cruzamiento no
será destructivo (independientemente de la posición del punto de cruzamiento). Por lo
tanto, 1-pcd(H)/(l-1) será una cota inferior de la probabilidad de aquellos cruzamientos
que no resulten destructivos para el esquema H. Esto implica que la probabilidad de
supervivencia del esquema H, Sc(H) necesariamente debe satisfacer la expresión 2.
Todavía resta considerar el efecto destructivo del operador de mutación sobre un
esquema H. Sin embargo, para facilitar el análisis es conveniente introducir una
notación adicional.
42
42
El orden de un esquema H es la cantidad de dígitos binarios que participan en la
definición de H y se denota por o(H). Es decir, el orden de un esquema es la cantidad de
0’s y 1’s que lo componen. Por ejemplo, o(1****1)=2. Esta notación es necesaria
puesto que el efecto destructivo del operador de mutación sobre el esquema H depende
del orden de H. Si pm es la probabilidad de mutación entonces la probabilidad de que el
esquema H sobreviva al operador de mutación es (1-pm)o(H). La razón es que para cada
digito binario, la probabilidad de que no sea mutado es 1-pm. Por lo tanto, la
probabilidad de que ninguno de los dígitos binarios que participan en la definición del
esquema H sea mutado es simplemente (1-pm)o(H).
Finalmente, si el efecto destructivo del cruzamiento y la mutación sobre un esquema H
se incorpora a la expresión 1, se obtiene la siguiente expresión:
( ))()1(1)(1
)(
),(),())1,(( Homc p
lHdp
tf
tHmtHutHmE −⎟⎠⎞
⎜⎝⎛
−−≥+ ∧
La expresión anterior se conoce como el teorema del esquema y apareció publicado por
primera vez en [Holland, 1975]. La derivación del teorema presentada aquí se puede
encontrar en [Mitchell, 2002]. También puede encontrarse un argumento similar en
[Goldberg,1989].
El teorema del esquema describe el crecimiento de un esquema de una generación a la
siguiente. A menudo, el teorema del esquema se interpreta como sigue: Esquemas
cortos de bajo orden cuya aptitud promedio se encuentre sobre la media de la aptitud de
la población, se incrementaran de manera exponencial durante todo el proceso
evolutivo.
43
43
La expresión que describe el teorema del esquema, es en realidad una cota inferior, ya
que solo toma en cuenta los efectos destructivos del cruzamiento y de la mutación. Sin
embargo, en la actualidad se cree que el cruzamiento es el operador que convierte a los
algoritmos genéticos en una herramienta tan poderosa. El operador de cruzamiento tiene
la habilidad de recombinar instancias de esquemas buenos para formar instancias de
esquemas aun mejores. La suposición de que esto es lo que hace que los algoritmos
genéticos funcionen recibe el nombre de “hipótesis de los bloques constructivos” (Ver
capitulo II en [Goldberg,1989] )
El teorema del esquema y la hipótesis de los bloques constructivos se ocupan
principalmente de los roles que ocupan la selección y el cruzamiento. ¿Cuál es el papel
de la mutación? Holland propuso que la mutación ayuda a prevenir la perdida de
diversidad de la población en una posición dada de los cromosomas. Esto puede
ilustrarse mediante un ejemplo. Supóngase que algún momento dado de la ejecución de
un algoritmo genético el primer digito binario de cada cromosoma es 1. Sin mutación,
seria imposible obtener un cromosoma cuyo primer digito binario fuese 0.
El operador de mutación provee una póliza de seguridad para que este tipo de
situaciones nunca ocurran.
44
44
II.3.6 Codificación binaria versus codificación continua
Hasta los momentos el estudio realizado sobre los algoritmos genéticos permite concluir
que estos difieren de los métodos de optimización tradicionales en los siguientes puntos:
• Usan una codificación del conjunto factible en vez del conjunto mismo
• Buscan el óptimo a partir de un conjunto de puntos factibles en vez de un único
punto en cada iteración.
• No requieren diferenciabilidad de la función objetivo.
• Son probabilísticos.
El primer punto de la lista anterior resulta crucial. El análisis hasta ahora se ha basado
principalmente en la codificación binaria de los puntos pertenecientes a la región
factible. Históricamente, la codificación binaria tiene importancia por que le permitió a
Holland estudiar los algoritmos genéticos mediante el teorema del esquema. Sin
embargo, la codificación binaria presenta algunas desventajas. En muchas aplicaciones
prácticas como la optimización numérica, la codificación binaria limita severamente el
tamaño de los problemas que pueden resolverse. Puede ilustrarse este punto de la
siguiente manera. Supóngase que g:0,1L→Ω representa la función de decodificación
binaria. Es decir, si x es un cromosoma compuesto por una secuencia de dígitos binarios
entonces g(x)∈Ω donde Ω es la región factible. Por lo tanto, la función objetivo que el
algoritmo genético trata de maximizar no es en realidad f sino mas bien la composición
de la función objetivo f con la función de decodificación g.
45
45
En otras palabras, el problema de optimización resuelto por el algoritmo genético es en
realidad:
Optimizar: ))(( xgf
sujeto a: )(:1,0 Ω∈∈∈ yyx gL
El problema de optimización anterior es por lo general más complejo que el original.
Por ejemplo, supóngase un problema de optimización pequeño de dos variables. Si se
usan 32 bits para cada variable entonces en la expresión anterior L=64. El tamaño del
problema resultante es de 264. Se trata de un número gigante (aproximadamente 16
trillones). Si f es complicada entonces el problema resulta intratable para cualquier
técnica de búsqueda que se intente.
La discusión anterior motiva la consideración de un algoritmo que opere directamente
sobre la región factible. Esto puede lograrse mediante un nuevo tipo de codificación
conocida como codificación continua. Esta es, en realidad, la más natural para
problemas de optimización numérica de acuerdo a algunos autores (ver [Michalewicz,
1996], [Radcliff,1991] y [Patton & Liu,1994]). La codificación continua consiste en la
representación real de las variables del problema de acuerdo al estándar de punto
flotante de la máquina particular que se este usando. La mayoría de las arquitecturas
actuales se basan en el estándar IEEE 754. Esta consiste en un bit de signo, 7 bits de
exponente y 23 bits para la mantisa (son 32 bits en total). En este caso, cada cromosoma
contiene la representación de las variables del problema original en punto flotante de 32
bits. Es decir, si cada cromosoma se escribe como [ ]nxxxxcromosoma .,,.........,, 321=
entonces, los elementos xi no son secuencias de dígitos binarios sino, representaciones
en punto flotante de las variables xi.
46
46
Esta codificación contrasta radicalmente con la binaria usada originalmente por Holland
y Goldberg. Sin embargo, presenta grandes ventajas para resolver problemas de
optimización numérica que serán estudiadas mas adelante.
47
47
II.4 Algoritmos genéticos como métodos de optimización convexa
La resolución de problemas de optimización numérica plantea modificaciones
necesarias en algunos elementos del modelo de algoritmo genético planteado hasta
ahora. La primera cuestión relevante, es la manera de cruzar y mutar puntos de la región
factible preservando la factibilidad de estos. Existen varias soluciones a este problema.
Algunas de estas, son adaptaciones de los métodos clásicos de optimización. En un
primer enfoque, conviene suponer que el conjunto factible del problema de
optimización puede describirse mediante una serie de ecuaciones e inecuaciones
lineales, es decir, el conjunto Ω esta dado por inecuaciones de la forma dCx ≤
donde
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
mnmm
n
n
ccc
cccccc
............
..
..
21
22221
11211
C ,
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
nx
xx
.
.2
1
x y
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
nd
dd
.
.2
1
d
Adicionalmente la definición de Ω puede incluir restricciones en forma de ecuaciones,
es decir,
Ecuaciones de la forma bAx =
donde
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
mnmm
n
n
aaa
aaaaaa
............
..
..
21
22221
11211
A ,
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
nx
xx
.
.2
1
x y
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
nb
bb
.
.2
1
b
48
48
Finalmente, el conjunto Ω también puede contener restricciones de dominio, es decir,
inecuaciones de la forma,
iii rxl ≤≤ para ni ,...2,1=
Las restricciones de dominio indican que las variable xi solo pueden variar en el rango
[li,ri] donde li y ri son constantes.
Esta formulación de Ω es lo suficientemente genérica para incluir una gran cantidad de
problemas de investigación de operaciones, para los cuales la función objetivo f puede
presentar un comportamiento complicado (Por ejemplo, no lineal, no diferenciable, etc)
II.4.1 Propiedades de las regiones convexas
La primera característica que se evidencia de la definición Ω es su convexidad. Esta será
muy útil en la definición de las nuevas operaciones de cruzamiento y mutación.
Una propiedad muy importante de Ω es la siguiente. Supóngase que x es un punto
factible, es decir, Ω∈= ),....,,( 21 nxxxx . Entonces, debido a la convexidad de Ω, se
cumplirá que si se fijan n-1 variables cualesquiera, entonces debe existir un rango
donde la variable restante puede variar. Es decir, supóngase que si
Ω∈= ),....,,.....,,( 21 nk xxxxx , entonces se cumplirá que,
],[ kk rly∈ si y solo si Ω∈+− ),........,,,,.......,( 111 nkk xxyxx
donde todas las variables ix permanecen constantes para nkki ,...1,1,........,1 +−= .
49
49
Por ejemplo, supóngase que Ω esta definido por,
33 1 ≤≤− x
80 2 ≤≤ x
41221 +≤≤ xxx
Entonces, para el punto Ω∈)5,2( se cumplirá que,
51 1 ≤≤ x si y solo si 52 =x
64 2 ≤≤ x si y solo si 21 =x
Esta propiedad es la base de todos los operadores de mutación. La razón es que si xk es
una variable que será mutada, entonces su rango de mutación será [li,ri]. Por lo tanto, un
cromosoma mutado de esta manera será siempre factible.
II.4.2 Eliminación de ecuaciones lineales
Otra característica de la definición de Ω es la presencia de ecuaciones lineales. En
problemas de programación lineal las restricciones en forma de ecuaciones lineales no
presentan mayor problema. La razón es que en caso de que el óptimo exista, este debe
estar situado en la superficie del conjunto convexo. En cambio, las inecuaciones son
convertidas en ecuaciones mediante la adición de variables de holgura. Luego de haber
convertido todas las restricciones en igualdades, el procedimiento de solución va
visitando los vértices de la superficie del conjunto convexo. Esta es la técnica utilizada
por el método Simplex. (Ver reseña sobre el método Simplex en la sección II.2.4)
50
50
Sin embargo, resulta difícil adaptarla para utilizarla en un algoritmo genético. La
solución, es por lo tanto, proceder de manera contraria. Todas las restricciones deben ser
convertidas en inecuaciones. Esto implica eliminar las restricciones en forma de
ecuaciones (si estuvieran presentes). Este enfoque permite aplicar los operadores
genéticos que se definirán mas adelante con mucha facilidad. La razón, como se vera, es
que la convexidad del espacio garantiza que no es necesario verificar la factibilidad las
soluciones que se obtienen al recombinar las soluciones factibles. A continuación se
muestra como funciona el procedimiento para eliminar las ecuaciones lineales de las
restricciones que definen Ω.
Supóngase que las restricciones lineales usando notación matricial se expresan de la
manera siguiente: bAx = donde la dimensión de la matriz A es de m filas y n columnas
y el rango de A es m. Adicionalmente se supone que m<n.
El caso donde el rango de A es menor que m no tiene interés alguno. Este caso implica
que algunas de las ecuaciones son redundantes y simplemente pueden ser eliminadas del
problema sin alterar la solución en modo alguno.
Dado que el rango de la matriz es igual al número de filas, es valido suponer que existen
m variables, miii xxx ,.....,,
21las cuales pueden ser expresadas en términos de las n-m
variables restantes. Estas variables pueden ser eliminadas de la formulación del
problema como se explica a continuación:
51
51
La matriz A se particiona en dos submatrices A1 y A2. tales que la j-esima columna de A
pertenece a A1, si y solo si, ,.....,, 21 miiij∈ . Una consecuencia inmediata de la
definición de A1 es que 11A − existe. Similarmente, la matriz C y el vector x se
particionan de acuerdo al orden impuesto por A1. Es decir, x=(x1,x2) donde
),.....,,(21 miii xxx=1x
Entonces, el sistema bAx = es equivalente a,
bxAxA =+ 2211
Por lo tanto,
221
11
11 xAAbAx −− −=
Antes de continuar, es conveniente definir dos vectores, que permiten expresar las
restricciones de dominio para las componentes del vector x1. Sean l1 y u1 vectores tales
que componente a componente cumplen,
1uxl 11 ≤≤
La expresión anterior es consecuencia de las restricciones de dominio presentes en el
problema original. Por lo tanto, sustituyendo x1 en la expresión anterior se obtiene,
1221
11
11 uxAAbAl ≤−≤ −−
Similarmente, en el caso de las inecuaciones de la forma dCx ≤ , se obtiene que
dxCxC 2211 ≤+
Nuevamente sustituyendo x1 en la expresión anterior se obtiene,
dxC)xAAb(AC 22221
11
11 ≤+− −−
El proceso anterior constituye una etapa preliminar a la ejecución del algoritmo
genético. Al final del proceso las variables miii xxx ,.....,,
21no aparecen.
52
52
De la misma manera, las restricciones en forma de igualdad tampoco aparecen. El
nuevo conjunto de restricciones que define a Ω, esta dado por,
• Restricciones de dominio originales: 222 uxl ≤≤
• Nuevas inecuaciones: 1221
11
11 uxAAbAl ≤−≤ −−
• Inecuaciones originales: bACd)xAAC(C 11122
1112
−− −≤−
A continuación, se ilustra mediante un ejemplo el proceso anterior. Supóngase que se
desea optimizar la siguiente función objetivo de seis variables,
Optimizar ),,,,,( 654321 xxxxxxf
sujeto a las restricciones:
62 321 =++ xxx
103 653 =−+ xxx
34 41 =+ xx
12052 ≤+ xx
2040 1 ≤≤− x , 7550 2 ≤≤ x , 100 3 ≤≤ x
155 4 ≤≤ x , 200 5 ≤≤ x , 55 6 ≤≤− x
53
53
En este problema, se puede despejar las primeras tres variables en función de las
variables restantes obteniendo,
41 3 xx −=
6542 3810 xxxx −++−=
653 310 xxx +−=
La nueva función objetivo, es por lo tanto, una función de solo tres variables,
),,),310(),3810(),43((),,( 654656544654 xxxxxxxxxfxxxg +−−++−−=
Las nuevas restricciones serían:
12032810 654 ≤−++− xxx (restricción original 12052 ≤+ xx )
204340 4 ≤−≤− x (restricción original 2040 1 ≤≤− x )
75381050 654 ≤−++−≤ xxx (restricción original 7550 2 ≤≤ x )
103100 65 ≤+−≤ xx (restricción original 100 3 ≤≤ x )
155 4 ≤≤ x (restricción original)
200 5 ≤≤ x (restricción original)
55 6 ≤≤− x (restricción original)
En el ejemplo, puede observarse que el problema resultante esta definido, solo en
términos de inecuaciones. Las restricciones en forma de ecuaciones no aparecen en el
problema resultante.
54
54
II.4.3 Población inicial
La sección anterior describió una transformación preliminar del problema original que
resulta convenirte antes de la aplicación de un algoritmo genético. Esta primera
transformación prepara el problema para la aplicación del algoritmo. El siguiente paso,
de acuerdo al modelo general del algoritmo genético (ver figura 3), consiste en hallar
una población inicial de cromosomas factibles (es decir, de soluciones factibles). En la
mayoría de los algoritmos genéticos esto se realiza mediante un muestreo aleatorio de la
región factible. Sin embargo, en problemas muy restringidos, el muestreo puede fallar
después de un número finito de intentos. Si el muestreo falla, una alternativa para hallar
soluciones factibles es Simplex. Debe observarse que la región factible es convexa, por
lo tanto, Simplex es aplicable en este caso. La solución factible se encuentra
considerando una función objetivo artificial de la forma
∑=
=Φm
iim yyyy
121 ),...,(
donde las variables 0≥iy son variables artificiales. Al aplicar Simplex al conjunto de
restricciones modificado usando la función objetivo artificial Φ, se obtendrá una
solución factible para el conjunto Ω. Esto ocurrirá, siempre y cuando Ω sea un conjunto
no vacío. Este procedimiento es equivalente a la primera fase del método de las dos
fases utilizado en programación lineal. La solución factible hallada mediante Simplex
sirve para inicializar la población inicial de cromosomas con copias de esta solución. Se
utilizaran tantas copias de la solución factible como sea necesaria hasta completar el
tamaño de la población. Como se vera a continuación, los operadores de cruzamiento y
mutación se encargaran de introducir diversidad y variedad en la población inicial.
55
55
II.4.4 Cruzamiento y mutación
En esta sección se describen los operadores de cruzamiento y mutación para
codificación continua. Estos operadores explotan el hecho de que la región factible Ω es
convexa. Antes de pasar a la descripción de los distintos operadores, conviene recordar
la propiedad de convexidad estudiada en la sección II.4.1. Esta propiedad es necesaria
para la comprensión de los distintos operadores de mutación. En líneas generales, la
propiedad asegura de que si Ω∈= ),.....,,.....,,( 21 nk xxxxx , entonces al fijar n-1
componentes del vector, la componente restante solo puede variar en un rango
determinado [ak,bk]. Mas aún, este rango, puede ser determinado fácilmente (ver el
ejemplo de la sección II.4.1).
II.4.4.1 Mutación uniforme
Este operador requiere un único cromosoma padre x y produce solo un cromosoma
descendiente x’. El operador funciona seleccionando una componente aleatoria xk del
vector ),.....,,.....,,( 21 nk xxxx=x para producir, ),.....,,.....,,( '21
'nk xxxx=x donde '
kx es
un valor uniformemente distribuido en el rango [ak,bk]. La convexidad del conjunto
factible Ω garantiza la existencia de este rango. Este operador juega un papel
importante, en las etapas tempranas del proceso evolutivo. En particular, este operador
resulta esencial cuando la población inicial consiste de múltiples copias del mismo
punto factible. Como se comento anteriormente, esto puede ocurrir si el muestreo de la
región factible falla. Esta situación puede ocurrir en el caso de problemas muy
restringidos. Otra ventaja, del operador de mutación uniforme, es que le permite al
algoritmo alejarse de óptimos locales mientras durante el proceso evolutivo. La
definición de este operador aparece en (Michalewicz, 1996)
56
56
II.4.4.2 Mutación en frontera
Este operador, al igual que el anterior, requiere un único cromosoma padre x y genera
solo un cromosoma descendiente x’. Este operador es una variante del operador anterior
donde 'kx es ak o bk con igual probabilidad. Este operador es importante en problemas
donde el óptimo se encuentre en la frontera de la región factible. La definición de este
operador aparece en (Michalewicz, 1996)
II.4.4.3 Mutación no uniforme
Este operador se define como sigue: Sea ),.....,,.....,,( 21 nk xxxx=x un cromosoma
padre y supóngase que la componente xk resulta seleccionada para ser mutada. Entonces
el cromosoma mutado será,
),.....,,.....,,( '21
'nk xxxx=x
donde
),('kkkk xbtxx −Δ+= si un digito binario aleatorio es 0
),('kkkk axtxx −Δ+= si un digito binario aleatorio es 1
La función Δ(t,y) devuelve valores en el rango [0,y] tales que la probabilidad de Δ(t,y)
de estar cerca de 0 aumenta a medida que t aumenta (t es el numero de iteración). Este
operador causa que la mutación tenga un efecto significativo al principio de la
evolución pero vaya disminuyendo a medida que esta avance. Esto es deseable, ya que
al inicio del proceso evolutivo lo ideal es muestrear la región factible tanto como sea
posible.
57
57
Sin embargo, al final de la evolución el proceso debe converger y por lo tanto, el efecto
de la mutación debe ser pequeño. Una escogencia para la función Δ(t,y) con este efecto
es la siguiente,
b
Ttyryt ⎟⎠⎞
⎜⎝⎛ −=Δ 1),(
En la expresión anterior r, es un generador de números aleatorios uniformemente
distribuido en el intervalo [0,1], T es el numero máximo de iteraciones del algoritmo
(este número es prefijado) y b es un parámetro para el grado de no-uniformidad (b=1 es
razonable para la mayoría de los casos). La definición de este operador aparece en
(Michalewicz, 1996)
II.4.4.4 Cruzamiento aritmético
Este operador requiere dos cromosomas padres x y y para producir dos cromosomas
hijos. El cruzamiento aritmético se basa en una propiedad de las regiones convexas que
no se ha mencionado mucho hasta ahora. La propiedad garantiza que si x y y son puntos
de Ω, entonces la combinación lineal convexa de x y y pertenece a Ω. Es decir,
Ω∈−+= yxz )1(1 αα para todo ]1,0[∈α
Ω∈+−= yxz αα )1(2 para todo ]1,0[∈α
Por lo tanto, el cruzamiento aritmético se define como la combinación lineal convexa de
los cromosomas padres donde α es un número aleatorio uniformemente distribuido entre
0 y 1. La definición de este operador aparece en (Michalewicz, 1996), (Patton & Liu,
1994) y (RadCliff, 1991)
58
58
II.4.4.5 Cruzamiento simple
Al igual que el cruzamiento aritmético se trata de un operador binario porque requiere
dos cromosomas padres ),....,,( 21 nxxx=1x y ),....,,( 212 nyyy=x para producir dos
cromosomas hijos '1x y '
2x dados por,
),.....,,,....,,( 121 nkk yyxxx +='1x
),.....,,,....,,( 1212 nkk xxyyy +='x
El inconveniente del cruzamiento simple es que los cromosomas hijos '1x y '
2x pueden
resultar no factibles. Para evitar este inconveniente la definición de cruzamiento simple
se basa en la siguiente propiedad de los conjuntos convexos. La propiedad establece que
existe un número ]1,0[∈a tal que,
Ω∈−+−+= ++ ))1(),...,1(,,...,( 111'1 axayaxayxxx nnkkk
Ω∈−+−+= ++ ))1(),...,1(,,...,( 111'2 ayaxayaxyyx nnkkk
La única cuestión que queda por resolver es como determinar el valor a que hace que las
expresiones anteriores se cumplan. El método mas simple es comenzar con a=1 y, si
algunos de los cromosomas hijos no es factible, el valor a se decrementa en un valor
1/k. Después de k intentos, se tendrá que a=0 y los cromosomas hijos serán factibles
puesto que en este caso serán idénticos a sus padres. La definición de este operador
aparece en (Michalewicz, 1996)
59
59
II.4.4.6 Cruzamiento heuristico
El último tipo de cruzamiento contrasta con los anteriores debido a las siguientes
razones,
• Utiliza la función objetivo para determinar la dirección de búsqueda.
• Produce un solo descendiente
• Puede ocurrir que no produzca descendiente alguno.
El cruzamiento heuristico requiere dos cromosomas padres 1x y 2x para producir un
cromosoma hijo x3 de acuerdo a la siguiente regla,
2123 )( xxxx +−= r
En la expresión anterior, r es un número aleatorio uniformemente distribuido entre 0 y
1. Adicionalmente debe cumplirse que el cromosoma padre 2x sea mas apto que el
cromosoma hijo 1x , es decir,
)()( 12 xx ff ≥ para problemas de maximización
)()( 21 xx ff ≥ para problemas de minimización
Este operador puede generar cromosomas no factibles. En ese caso, se genera un valor
aleatorio nuevamente para crear un nuevo descendiente. Si después de w intentos
ninguno de los cromosomas descendientes es factible, entonces el operador no produce
descendiente alguno.(w es un parámetro prefijado) La definición de este operador
aparece en (Michalewicz, 1996)
60
60
II.4.5 Restricciones no lineales
En esta sección se considera el problema de cómo manejar las restricciones no lineales.
Hasta los momentos, solo se ha considerado el caso donde todas las restricciones son
lineales. Las restricciones no lineales plantean una nueva dificultad. Esta se debe, a que
en este caso, ya no es posible explotar la convexidad del conjunto factible. Las
restricciones no lineales pueden definir un conjunto que no es convexo. Por lo tanto, es
posible que después de aplicar cruzamiento o mutación a los cromosomas de la
población, estos no representen puntos dentro de la región factible del problema
original. Es decir, los descendientes de los cromosomas originales representan puntos
que se encuentran fuera de la región factible. Una manera de solventar este problema es
usando funciones de penalización. Esta idea proviene en realidad, de los métodos
clásicos de optimización (para un ejemplo, ver reseña sobre SUMT, en la sección
II.2.4).
La idea básica de las funciones de penalización consiste en transformar un problema de
optimización restringida en uno no restringido. Existen varias maneras de lograr esto.
Una manera sencilla se describe a continuación. Supóngase que en el problema original,
las restricciones no lineales g1, g2,……,gm se encuentran presentes. Entonces, el
problema de optimización original se puede expresar del siguiente modo,
Optimizar ),.......,,,( 321 nxxxxf sujeto a las restricciones no lineales:
0),....,,( 211 ≥nxxxg 0),....,,( 212 ≥nxxxg
. .
0),....,,( 21 ≥nm xxxg
y sujeto a Ω∈),......,,( 21 nxxx
61
61
La idea es transformar el problema anterior en el siguiente problema de optimización
linealmente restringido,
Optimizar: )),.......,,,((),.......,,,( 3211
321 n
m
iin xxxxgrxxxxf ∑
=
Φ+
sujeto a Ω∈),......,,( 21 nxxx
En la expresión anterior Φ se conoce como función de penalización y r como constante
de penalización (un valor arbitrariamente grande). Existen varias alternativas para Φ. En
(Goldberg, 1989) se sugiere la siguiente función de penalización para problemas de
minimización (el caso de maximización es similar):
∑=
=Φm
iim gggg
1
221 )0),(min())(),.....,(),(( xxxx donde x es el vector ),.....,,( 21 nxxx=x
El razonamiento que sustenta las funciones de penalización es que bajo ciertas
condiciones las soluciones del problema penalizado tienden a las mismas soluciones del
problema original a medida que la constante de penalización se acerca al infinito. Por lo
general, en problemas muy restringidos, es decir, con muchas restricciones es necesario
introducir varias constantes de penalización. En estos casos se introduce una constante
de penalización por cada restricción. La idea es castigar a cada restricción de manera
proporcional a la violación de la región factible. Como se menciono anteriormente,
existen varias alternativas para la función de penalización. Se puede encontrar un
capitulo completo dedicado al tema en (Luegenberger,1989).
62
62
Capitulo III: Desarrollo del sistema
63
63
III.1 Metodología del desarrollo
La metodología escogida es una combinación del método científico aplicado a la
investigación de operaciones y la metodología tradicional de ciclo de vida básico para el
diseño y desarrollo de sistemas (Hernández, 1999). La metodología comprende las
siguientes etapas:
1. Levantamiento de la información
2. Análisis de la información
3. Establecimiento de soluciones alternativas.
4. Diseño y desarrollo de la herramienta
5. Pruebas
A continuación se explica en que consistió cada una de estas etapas.
III.1.1 Levantamiento de la información.
Esta etapa consistió en la obtención de información necesaria para el desarrollo de la
herramienta. La información fue recopilada primordialmente en bibliotecas
universitarias e incluyo múltiples fuentes bibliográficas, trabajos especiales de grado
relacionados con el tema de los algoritmos genéticos como métodos de optimización.
64
64
III.1.2 Análisis de la información
El análisis contempló el estudio de los distintos elementos que integran un algoritmo
genético. Se estudiaron los distintos tipos de operadores genéticos que existen, además
del papel que estos juegan. También se revisaron los mecanismos de selección mas
conocidos. El análisis se concentro en la identificación y adaptación de los elementos
estudiados a problemas de optimización numérica. Los algoritmos genéticos, son en si
mismos, métodos de optimización muy generales. Por lo tanto, se requiere del
conocimiento de las particularidades de cada problema para poderlos implementar de
manera eficiente. En el caso de la optimización numérica se identificaron dificultades al
adaptar el modelo clásico del algoritmo genético de Holland-Goldberg. La dificultad
principal consistió en el esquema de codificación comúnmente usado por este modelo.
La codificación binaria usada por el modelo clásico es solo adecuada para problemas de
optimización pequeños (de pocas variables). Otro elemento analizado fue la definición
de la función de aptitud en el caso de regiones no convexas. En estos casos, se
determino que resulta conveniente definir una función objetivo penalizada para eliminar
las restricciones no lineales del modelo. De esta manera el problema penalizado es
linealmente restringido y puede tratarse como un problema convexo.
III.1.3 Establecimiento de soluciones alternativas
Después de identificar las desventajas de la codificación binaria durante la etapa
anterior, se procedió a buscar soluciones alternativas. La alternativa identificada fue
modificar el algoritmo genético para que opere directamente con los puntos factibles del
problema. Esto requirió definir nuevos operadores de cruzamiento y mutación.
65
65
Estos operadores se basan en un diseño cuidadoso que garantiza la factibilidad de los
nuevos cromosomas. El nuevo algoritmo constituye un método especialmente adaptado
para problemas de optimización convexa.
III.1.4 Diseño y desarrollo
Una metodología de ingeniería del software es un proceso para producir software de
forma organizada, empleando una colección de técnicas y convenciones de notación
predefinidas La metodología empleada en este caso se basa en el análisis estructurado
de Yourdon (Yourdon,1993) y comprende las siguientes fases:
Diseño conceptual: El diseño conceptual es una descripción de la estructura
del sistema mediante diagramas de flujo de datos. (DFD) Un DFD es una
herramienta de modelado de procesos que representa el flujo de datos a
través del sistema y las tareas o procesos llevados a cabo por el mismo. Cabe
destacar que los DFD’s sugieren que hace el sistema, pero no como. Los
DFD constituyen representaciones jerárquicas de los procesos, en el sentido
de que un proceso perteneciente a un DFD puede requerir otro DFD
completamente distinto para describirlo. Se dice en estos casos que el primer
DFD es de un nivel superior que el último. Los DFD realizados están
orientados a cubrir las especificaciones más importantes de la herramienta.
66
66
A continuación se enumeran y describen brevemente los diagramas
realizados durante esta etapa del diseño.
• Diagrama de contexto (DFD Nivel 0): Refleja los límites o el ámbito del
sistema. El diagrama de contexto realizado muestra de manera
conceptual los distintos flujos de datos entre el usuario y la herramienta.
(El diagrama de contexto se puede encontrar en el apéndice A)
• Diagrama de flujo de datos (DFD Nivel 1): Define las funciones más
importantes de la herramienta. También muestra los principales
almacenes de datos y como estos interactúan con los procesos. (El DFD
Nivel 1 se puede encontrar en el apéndice A)
• Diagrama de flujo de datos (DFD Nivel 2): Para la realización de este
diagrama se decidió expandir el proceso más complejo del nivel 1. Este
proceso corresponde al algoritmo genético. El DFD del algoritmo
genético muestra de manera esquemática como interactúan los
operadores genéticos y los mecanismos de selección estudiados en el
marco teórico. (El DFD Nivel 2 se puede encontrar en el apéndice A)
Diseño lógico: Este diseño permite describir la estructura lógica de la
herramienta mediante diagramas de entidad-relación. (DER) Los DER
modelan el almacenamiento de los datos en el sistema al igual que la
relación entre estos. (El DER realizado, se puede encontrar en el apéndice A)
67
67
Diseño físico: El diseño físico comprendió la especificación de todos los
procesos identificados en las etapas anteriores. Estas especificaciones se
realizaron como descripciones algorítmicas de los procesos más básicos de
los diagramas de flujo de datos. Adicionalmente, el diseño físico también
incluyo la definición de las tablas para la base de datos de la herramienta. La
base de datos se diseñó siguiendo las relaciones establecidas en el DER.
El proceso de diseño permitió identificar la estructura modular de la herramienta. Los
módulos identificados fueron:
• Módulo de optimización: Permite al usuario optimizar una función
objetivo previamente definida, usando un algoritmo genético,
especialmente adaptado para este fin. Este módulo permite seleccionar la
función objetivo, el conjunto de restricciones y los parámetros que serán
utilizados por el algoritmo.
• Módulo de restricciones: Permite definir y administrar distintos
conjuntos de restricciones. El usuario, después de definir las restricciones
que necesitara, puede guardarlas en la base de datos de la herramienta.
El modulo permite administrar varios conjuntos de restricciones.
• Módulo de parámetros: Permite definir y administrar distintos conjuntos
de parámetros para ser utilizados posteriormente. Los parámetros
utilizados para un problema en particular no necesariamente, son los
mejores para otro problema. Por lo tanto, este modulo facilita la tarea de
mantener distintos conjuntos de parámetros cuando el usuario decide
trabajar con varios problemas de optimización diferentes.
68
68
• Módulo de reportes: Los algoritmos genéticos generan abundante
información después de haberse ejecutado. Este módulo sirve para
generar un reporte que incluye la solución encontrada por el algoritmo,
así como también, información adicional sobre la ejecución de este. El
usuario puede guardar el reporte para su posterior uso o distribución.
• Modulo de problemas: Este modulo permite asociar una función objetivo
previamente definida por el usuario con un conjunto de restricciones y
parámetros existentes en la base de datos. La herramienta maneja la
asociación resultante como un problema de optimización. El usuario no
necesita especificar ninguno otro dato. Este permite generar múltiples
problemas de optimización con el mismo conjunto de parámetros y
restricciones existentes.
Desarrollo
Después de concluir el diseño del sistema, se procedió a la implementación de todos los
procesos en un lenguaje de programación. Un aspecto importante de esta etapa fue la
escogencia del lenguaje. Esta tuvo como base los siguientes criterios:
• El problema que se esta tratando de resolver.
• Los requerimientos que se han determinado.
• La metodología empleada para el desarrollo del proyecto.
• Facilidades para el manejo de expresiones matemáticas.
• Facilidades para el manejo de bases de datos.
• Facilidades para el manejo de gráficos.
69
69
La selección definitiva fue el entorno de programación Microsoft Visual Basic 6.0 y
como manejador de base de datos se escogió Microsoft Access 2000. Ambos productos
cumplen razonablemente bien con los criterios anteriores.
Además de la programación, se procedió a identificar algunos problemas de
optimización que pudieran ser codificados en la herramienta. Estos problemas sirvieron
como una base de pruebas durante la siguiente etapa del proyecto.
El resultado obtenido en esta etapa, fue una herramienta que apoya la resolución de
problemas de optimización convexa.
A la herramienta resultante se le denomino como Optimizador Evolutivo.
70
70
III.1.5 Pruebas:
De acuerdo a la metodología del análisis estructurado las pruebas tienen como objetivo
descubrir errores en el software. Para cumplir con esta finalidad, se ejecutaron pruebas
de unidad, pruebas de integración y pruebas de validación, las cuales se describen a
continuación.
Prueba de unidad: Las pruebas de unidad están centradas sobre los módulos
desarrollados. Para cada módulo descrito en la fase de diseño de la herramienta
se procedió de la siguiente manera:
• Comprobar la validez de los datos de entrada al nivel de la interfaz del
modulo. Por ejemplo, el coeficiente de una restricción lineal solo puede ser
valor numérico. En el caso de que el usuario ingrese cualquier otro tipo de
entrada, el sistema indicará que el campo ingresado no es valido y
permanecerá en espera, hasta que el usuario ingrese el coeficiente
correctamente.
• Examinar las estructuras de datos locales, tales como arreglos dimensionales,
con el fin probar la integridad de los datos durante la ejecución del modulo.
• Realizar pruebas a las condiciones limite, para asegurar que el modulo
funciona correctamente cuando se satisfacen estas condiciones. Por ejemplo,
se siguió detenidamente el procesamiento de los arreglos cuando estos
alcanzaban sus elementos limites (primero y ultimo elementos).
71
71
Prueba de integración: Una vez aplicada la prueba de unidad sobre los distintos
módulos, se procedió a integrarlos. La prueba de integración tiene como
finalidad la detección de errores asociados con la integración de los módulos. La
integración de los módulos se realizo en forma descendente, es decir, la
integración se realizó desde el modulo principal de optimización hacia los
demás.
Pruebas de validación: Las pruebas de validación se centran en los requisitos
funcionales de la herramienta. Es decir, se ejecutan pruebas para comprobar que
los resultados proporcionados por la herramienta sean consistentes con los
resultados esperados. Para comprobar que los resultados obtenidos por el
optimizador evolutivo fuesen consistentes, se buscaron problemas de
optimización en la literatura existente sobre el tema y se compararon estos
resultados con los obtenidos mediante el optimizador evolutivo. La coincidencia
entre ambos fue satisfactoria y por lo tanto, se concluyó que el algoritmo
genético de la herramienta está bien implementado. Estas pruebas son
presentadas en el capitulo IV.
A continuación se hace un recorrido a través de la herramienta Optimizador Evolutivo,
describiendo la funcionalidad de cada uno de los módulos que lo componen.
72
72
El Optimizador Evolutivo es una herramienta para optimizar funciones no lineales,
linealmente restringidas. Su funcionamiento se basa en los principios de los algoritmos
genéticos. La herramienta esta pensada para que resulte fácil de usar, inclusive para
aquellos usuarios que nunca hayan trabajado con algoritmos genéticos.
El Optimizador Evolutivo comprende los módulos que a continuación se describen:
• Módulo de optimización: El usuario puede optimizar una función objetivo
previamente definida, usando un algoritmo genético, especialmente adaptado
para este fin. Este módulo permite seleccionar la función objetivo, el conjunto
de restricciones y los parámetros que será utilizados por el algoritmo.
Adicionalmente, el usuario puede visualizar de manera resumida toda la
información resultante de la ejecución del algoritmo. Esto incluye un reporte
con la solución encontrada y diversas estadísticas.
• Módulo de definición de problemas: Permite definir y manejar distintos
conjuntos de restricciones lineales. Igualmente, se pueden especificar funciones
objetivo de diversas características. Estas definiciones se especifican usando la
notación algebraica comúnmente usada en matemáticas. Sin embargo, el usuario
debe observar algunas convenciones a la hora de definir sus restricciones y sus
funciones objetivo. Estas convenciones se explican al final del presente
documento donde también se proporcionan algunos ejemplos.
• Módulo de parámetros: El usuario puede definir y administrar distintos
conjuntos de parámetros que desee utilizar posteriormente. Los parámetros
utilizados para un problema no necesariamente, son los mejores para otro
problema. Por lo tanto, este modulo facilita la tarea de mantener distintos
conjuntos de parámetros cuando el usuario decide trabajar con varios problemas
de optimización diferentes.
73
73
• Módulo de problemas: Este módulo permite asociar una función objetivo con un
conjunto de restricciones y parámetros previamente definidos por el usuario. La
herramienta maneja la asociación resultante como un problema de optimización.
El usuario no necesita especificar ningún otro dato. Esto permite generar
múltiples problemas de optimización con el mismo conjunto de parámetros y
restricciones existentes
Seguidamente se presenta una descripción mas detallada de la funcionalidad de los
distintos módulos del Optimizador Evolutivo. Al final se muestran algunos ejemplos
que ilustran las capacidades de la herramienta.
Módulo principal
La figura número 6 muestra el menú principal de la herramienta. Desde el inicio
mostrado en la figura, el usuario puede escoger el modulo con el cual trabajará.
Figura 6: Menú principal
A continuación se describe el primer módulo de la herramienta: El módulo de definición
de problemas.
74
74
Módulo de definición de problemas
El propósito principal de este módulo es permitirle al usuario especificar el problema
que este desea resolver. Un problema de optimización se compone de dos partes: La
función objetivo y el conjunto de restricciones. Los dos paneles superiores mostrados en
la figura 7 sirven para especificar la función objetivo (panel superior) y el conjunto de
restricciones (panel inferior). El usuario especifica su problema utilizando la notación
algebraica comúnmente usada en formulas matemáticas. Sin embargo, debido a que las
formulas deben ser introducidas como caracteres alfanuméricos deben observarse
algunas convenciones fáciles de seguir. Estas convenciones serán explicadas
posteriormente con algunos ejemplos. Es importante mencionar que la definición de las
restricciones es opcional. Es decir, si solo se especifica la función objetivo, la
herramienta intenta resolver un problema de optimización no restringido. Sin embargo,
como se menciono anteriormente, el usuario debe introducir obligatoriamente una
función objetivo en el primer panel. Una vez que se ha especificado la función objetivo
y opcionalmente el conjunto de restricciones, el usuario puede pulsar el botón de
“maximización” o de “minimización” según sea su caso. Ambos botones pueden
detallarse en la figura 7.
Otra facilidad de este módulo es que permite guardar y editar funciones o restricciones
con los botones de “guardar” (ver figura 7) . Si el usuario desea guardar, debe
especificar un nombre para la función objetivo y un nombre para el conjunto de
restricciones. Se pueden guardar funciones objetivos y conjuntos de restricciones de
manera independiente.
Una opción práctica de este modulo es que permite ver y editar funciones objetivo y
restricciones previamente guardadas. Si el usuario esta interesado en ver la definición de
una función objetivo debe oprimir el botón “objetivo”. Al oprimir este botón en la parte
inferior del primer panel la herramienta despliega una lista de funciones objetivo. El
usuario puede, desde esta lista (ver figura 8) consultar, editar o eliminar funciones
objetivos previamente guardadas. Similarmente, en el segundo panel, el botón
“restricciones” despliega una lista de conjuntos de restricciones previamente definidos.
Estos también pueden ser consultados, editados o eliminados (ver figura 9). Es
importante recordar que los conjuntos de restricciones únicamente pueden incluir
restricciones en forma de ecuaciones o inecuaciones lineales.
75
75
Figura 7: Módulo de definición de problemas
Figura 8: Opción de editar y eliminar una función objetivo
76
76
Figura 9: Opción de editar y eliminar conjuntos de restricciones
Una vez que el problema de optimización ha sido definido, la herramienta esta lista para
optimizar. Esta funcionalidad se describe a continuación.
77
77
Modulo de optimización de problemas
Mediante este módulo el usuario puede resolver un problema de optimización
previamente definido. La figura 10 muestra la ventana correspondiente a este modulo.
Figura 10: Módulo de optimización de funciones
El primer panel de la figura 10 muestra un histórico del proceso de optimización . En el
histórico puede observarse los valores de las variables de la solución candidata así como
su valor objetivo. Solo se muestran aquellas generaciones donde la función objetivo
mejora su valor (de lo contrario el histórico sería demasiado largo para mostrarlo por
completo).
78
78
El panel inferior izquierdo muestra la mejor solución encontrada. El panel inferior
derecho muestra una gráfica del histórico. Esta gráfica le permite al usuario decidir
rápidamente si el proceso convergió o si por el contrario es necesario intentar
nuevamente con un conjunto de parámetros distinto (La siguiente sección describe
como modificar el conjunto de parámetros). El usuario puede realizar distintas
optimizaciones con distintos conjuntos de parámetros. El cuarto panel permite escoger
los conjuntos de parámetros de una lista. Igualmente pueden escogerse diversas
funciones objetivos y distintos conjuntos de restricciones de las listas desplegables que
se encuentran en el cuarto panel (Ver figura 10). El usuario puede optimizar cualquier
combinación de funciones objetivos, conjuntos de restricciones y conjuntos de
parámetros que decida seleccionar de las tres listas desplegables que se encuentran en
este panel. Es importante mencionar que para usar este módulo el usuario debe haber
especificado previamente el problema de optimización (función objetivo y restricciones)
así como el conjunto de parámetros (ver próxima sección).
La ultima funcionalidad que proporciona el modulo de optimización es un reporte
completo del proceso de optimización. El reporte incluye:
• Fecha y hora
• Definición del problema de optimización (función objetivo y restricciones)
• Parámetros utilizados
• Valores de la solución inicial (así como el método empleado para encontrarla)
• Histórico de la simulación (solo incluye las generaciones donde hubo mejoría)
• Número de la última generación donde la función objetivo presento mejoría
• Mejor solución encontrada (valores de las variables y valor objetivo)
• Población final de soluciones candidatas
• Tiempo de ejecución requerido.
El reporte se genera como un archivo de texto lo que permite su fácil distribución por
cualquier medio (correo electrónico, etc). La figura 11 muestra un ejemplo del reporte
79
79
Figura 11: Reporte del proceso de optimización
Modulo de parámetros
El modulo de parámetros permite modificar la configuración del algoritmo genético
utilizado durante el proceso de optimización. La figura 13 muestra las distintas opciones
de este módulo. Los parámetros que pueden modificarse incluyen:
• Frecuencia de mutación uniforme
• Frecuencia de mutación en frontera
• Frecuencia de mutación no uniforme y grado de no uniformidad
• Frecuencia de cruzamiento simple y grado de intercambio
• Frecuencia de cruzamiento aritmético
• Frecuencia de cruzamiento heurístico
80
80
Lista de parámetros que pueden ser modificados (continuación de la página anterior)
• Tamaño de la población
• Número máximo de iteraciones
• Mecanismo de selección
• Tipo de problema (Minimización o Maximización)
• Generación de la población inicial (Muestreo aleatorio o Método SIMPLEX)
Nota: Las frecuencias de los operadores se refieren al número de veces que estos son
aplicados en cada iteración del algoritmo.
Adicionalmente a todos los parámetros anteriormente mencionados el usuario debe
especificar una breve descripción para cada conjunto de parámetros que este decida
definir para su posterior utilización. Los conjuntos de parámetros que se vayan
definiendo pueden accederse oprimiendo el botón de “Parámetros existentes” mostrado
en la figura 13. Al activar esta opción se despliega la ventana mostrada en la figura 12.
Desde esta ventana el usuario puede ver, modificar y eliminar conjuntos de parámetros
previamente definidos.
Figura 12: Ventana de gestión de parámetros
81
81
Figura 13: Módulo de parámetros
Módulo de administración de problemas
Un problema, en este contexto, es una asociación entre un conjunto de restricciones, un
conjunto de parámetros y una función objetivo previamente definidos por el usuario.
Este módulo permite crear y manejar estas asociaciones. La figura 14 muestra como el
usuario puede crear un problema seleccionando los distintos elementos del problema de
sus correspondientes listas desplegables. La ventaja de este módulo es comodidad. Por
ejemplo, este módulo le evita al usuario tener que recordar que restricciones o
parámetros le corresponde a cada función objetivo. Mas aún, el usuario puede utilizar el
mismo conjunto de restricciones con varias funciones objetivo distintas.
82
82
Lo único que debe hacer, es crear varios problemas con el mismo conjunto de
restricciones y tantas funciones objetivo como desee. Luego, en el modulo de
optimización, puede optimizar los distintos problemas que haya definido.
Figura 14: Módulo de administración de problemas
A continuación se presentan algunos ejemplos que muestran las capacidades de la
herramienta.
Algunos ejemplos
El modulo de definición de problemas (ver figura 7) es uno de los módulos mas
versátiles de la herramienta. Su función principal es traducir un problema de
optimización especificado en notación algebraica por el usuario para que el algoritmo
genético de la herramienta pueda optimizarlo.
83
83
Debido a la flexibilidad de la notación algebraica que comúnmente se usa en
matemáticas es necesario definir algunas convenciones que el usuario debe seguir a la
hora de especificar un problema.
La primera convención es que las variables a ser optimizadas deben ser x1,,x2,x3,...,xn.
Adicionalmente, la función objetivo debe obligatoriamente denotarse por f. El siguiente
ejemplo ilustra el uso correcto de esta convenciones,
Ejemplo 1: Minimizando una función cuadrática
Considérese el siguiente problema de optimización (Ver [Luegenberger,1989],página
460)
Minimizar xyxyx 322 −+−
Sujeto a
x≤0
y≤0
4≤+ yx
Bajo las convenciones descritas anteriormente el problema debe ser escrito como,
Minimizar 12221
21 3xxxxxf −+−=
Sujeto a
10 x≤
20 x≤
421 ≤+ xx
Sin embargo, la herramienta no puede manejar caracteres con índices subscritos, por lo
tanto, la ultima convención que el usuario debe recordar es que las variables del
problema x1 y x2 deben escribirse como X[1] y X[2]. La figura 15 muestra como sería
descrito el problema
Figura 15:Definición de una función cuadrática de dos variables
84
84
En este punto, solo faltarían especificar las restricciones. Estas siguen las mismas
convenciones explicadas anteriormente. La figura 16 muestra como especificar las
restricciones del problema
Figura 16: Especificación de las restricciones lineales
Los paneles mostrados en las figuras 15 y 16 pertenecen modulo de definición de
problemas mostrado en la figura 7.
Finalmente el usuario, solo necesita oprimir el botón “minimizar” (ver figura 15) para
iniciar el proceso de optimización. La solución de este problema se puede observar en la
figura 17,
Figura 17: Detalle del módulo de optimización con la solución del ejemplo 1
Por lo tanto, es razonable concluir que la solución del problema de optimización es
1,2 21 == xx y 3),( 21 −=xxf
85
85
Ejemplo 2: Maximizando una función multimodal
El ejemplo anterior contiene exponentes muy pequeños. Esta, definitivamente, no es
una ventaja en muchos problemas de optimización. En este ejemplo se muestra como
trabajar con exponentes mayores.
Sin embargo, antes de introducir el siguiente ejemplo, es primero conveniente comentar
una característica del traductor de formulas que usa el módulo de definición de
problemas. Se trata de la sentencia de asignación ‘=’. Mediante esta sentencia el usuario
puede asignar a una variable cualquier valor que este desee. Esta variable, puede
inclusive estar en función de otras variables. Por ejemplo la siguiente secuencia de
asignaciones es valida,
A=3
B=4
F=A+B
Esta secuencia de asignaciones seria equivalente a definir la función objetivo
“constante” que sigue a continuación,
F=7
Esta característica de la asignación, puede usarse para crear un “alias” entre las
variables X[1], X[2],X[3].... y las variables que se deseen, por ejemplo: a,b,c... El
siguiente problema (ver [Chong & Zak,2001], página 242) sirve para aclarar las ideas
anteriores,
Maximizar la función,
3)
5(10)1(3),(
222222
)1(53)1(2
yxyxyx eeyxxexyxf
−+−−−+−− −−−−−=
donde las variables x y y están sujetas a,
33 ≤≤− x
33 ≤≤− y
86
86
La función objetivo se podría definir utilizando las sentencias de asignación de la
siguiente manera (ver figura 18),
Figura 18: Definición de la función objetivo mediante asignaciones
Nótese la utilización de la función potencia en este ejemplo. La función potencia
permite trabajar con cualquier exponente de manera muy flexible. Su definición es
como sigue, yxyxpotencia =),( donde 0>x
Anteriormente se menciono que es posible crear un “alias” entre las variables del
problema X[1] y X[2] y cualesquiera otras variables que el usuario decida escoger. Los
“alias” se crean usando asignaciones y permiten mejorar la legibilidad del problema. La
figura 19 muestra la especificación de la función objetivo anterior mediante el uso de
“alias”
Figura 19: Ejemplo de uso de un “alias”
Las definiciones mostradas en la figura 18 y 19 son completamente equivalentes. La
única razón para preferir el tipo de definición utilizada en la figura 19 (mediante “alias”)
es por “comodidad tipográfica” y legibilidad.
A=3*(1-X[1]*X[1])*(1-X[1]*X[1])*exp(-1*X[1]*X[1]-potencia(X[2]+1,2)) B=-10*(X[1]/5-potencia(X[1],3)-potencia(X[2],5)) D=exp(-1*X[1]*X[1]-X[2]*X[2]) C=(1/3)*exp(-1*potencia(X[1]+1,2)-potencia(X[2],2)) F=A+B*D-C
87
87
Finalmente, para concluir este ejemplo solo resta definir las restricciones lineales. Estas
no representan problema alguno. La definición completa del problema aparece en la
figura 20,
Figura 20: Definición del problema del ejemplo 2 (Ver [Chong & Zak,2001])
El usuario puede iniciar la optimización que desee. En este caso, solo necesita oprimir el
botón de “maximizar”. La solución del problema se muestra en la figura 21,
Figura 21: Solución del ejemplo 2
88
88
Ejemplo 3: Minimizando una función discontinua
Los dos ejemplos anteriores mostraron ejemplos de la sentencia de asignación. Esta es
suficiente para especificar la mayoría de los problemas de optimización que surgen en la
práctica. Sin embargo, existen problemas como el que se presenta a continuación donde
la sentencia de asignación no es suficiente,
Minimizar h(x) donde 13)( 3 +−= xxxh si 1−<x y 32)( += xxh si 1−>x .
Este ejemplo, permite describir un nuevo tipo de sentencia distinta de la sentencia de
asignación. Se trata de la sentencia condicional. La forma general de la sentencia
condicional es
SI <condicion> ENTONCES
<cualquier cosa>
FIN_SI
Usando la sentencia condicional puede especificarse con facilidad la función objetivo h.
La definición de la función h se muestra en la figura 22.
Figura 22: Ejemplo de función a “trozos”
La solución de este problema se muestra en la figura 23,
Figura 23: Solución del ejemplo 3
89
89
Ejemplo 4: Minimizando la función Gama
Considérese el siguiente problema de optimización (ver [Knuth, 1973],Vol I, página 48)
Minimizar )(xΓ sujeto a 0>x
La función gama aparece un muchas áreas como la estadística, la simulación, los
procesos estocásticos, etc... En este ejemplo se describe como hallar el mínimo de la
función gama utilizando el optimizador evolutivo. La primera dificultad que hay que
resolver es que la función gama esta definida como una integral impropia, es decir,
∫∞ −−=Γ0
1)( dtetx tx
Por lo tanto, es necesario especificar de alguna manera, la integral anterior en el módulo
de definición de problemas. Una manera simple de hacerlo (aunque no muy precisa) es
utilizar técnicas de integración numérica para evaluar Γ(x). La técnica escogida para
este ejemplo es la regla de Simpson (también conocida como regla parabólica). Sin
embargo, implementar la regla de Simpson utilizando sentencias de asignación y
sentencias condicionales sería tremendamente engorroso. Para ello, el traductor de
formulas del optimizador evolutivo proporciona un tipo distinto de sentencia. Se trata de
la sentencia MIENTRAS..FIN_MIENTRAS. La estructura de esta sentencia es,
MIENTRAS <condición>
<cualquier cosa>
FIN_MIENTRAS
Este tipo de construcción permite que el bloque <cualquier cosa> se ejecute
repetidamente mientras que <condición> se cumpla. Con este mecanismo resulta
sencillo implementar la regla de Simpson. Sin embargo, la función Γ requiere evaluar
una integral impropia donde el limite de integración superior es infinito. Lo mejor que
puede hacerse en este caso, es escoger un limite de integración grande a fin de tratar de
aproximar el valor de la integral lo mejor posible. La figura 24 muestra como utilizar la
sentencia MIENTRAS..FIN_MIENTRAS para evaluar el valor aproximado de
∫ −−≈Γ20
0
1)( dtetx tx mediante la regla de Simpson.
90
90
Figura 24: Ejemplo de la sentencia MIENTRAS..FIN_MIENTRAS
La figura 25 muestra un detalle de la definición de la función gama en el módulo de
definición de problemas,
Figura 25: Definición de la función gama
Se habrá notado en la figura 25, la presencia de dos restricciones (O.1<=X[1] y
X[1]<=5). Estas restricciones no pertenecen al problema original. Sin embargo, fue
necesario agregarlas por dos buenas razones. La primera restricción (0.1<=X[1]) evita
que el optimizador evolutivo evalué el integrando de la función gama en una
singularidad (lo que causa un error en la aritmética de punto flotante).
x=X[1] N=2000.0 A=0.0 B=20.0 DELTA=(B-A)/N I=1.0 INTEGRAL=0.0 MIENTRAS I<=N U1=potencia((I-1)*DELTA,x-1)*exp(-1*(I-1)*DELTA) U2=potencia(I*DELTA-DELTA/2,x-1)*exp(-1*(I*DELTA-DELTA/2)) U3=potencia(I*DELTA,x-1)*exp(-1*I*DELTA) INTEGRAL=INTEGRAL+DELTA*(U1+4*U2+U3)/6 I=I+1 FIN_MIENTRAS F=INTEGRAL
91
91
La segunda restricción (X[1]<=5) es necesaria debido a una interesante propiedad de la
función gama. Según esta propiedad la función gama interpola los números factoriales.
Es decir, Γ(n+1)=n! para n entero positivo. Esta propiedad hace que el optimizador
evolutivo produzca errores de desbordamiento cuando por ejemplo, intenta evaluar la
función gama para valores como 1001. La razón es que Γ(1001)=1000! y 1000! rebasa
con facilidad los limites de la aritmética de punto flotante de 32 bits (en realidad, 1000!
rebasa con facilidad los limites de la aritmética de punto flotante de cualquier máquina).
Estas observaciones permiten agregar las dos restricciones anteriormente mencionadas
sin alterar la solución del problema. El mínimo buscado, puede observarse en la
siguiente figura (Figura 26 )
Figura 26:Mínimo de la función gama
Resulta interesante comparar los valores de la figura 26 con el valor reportado en
[Knuth,1973]. Los valores son exactos hasta el cuarto digito, lo cual resulta
sorprendente tomando en cuenta el método rudimentario que se utilizo en este ejemplo.
Los cuatro ejemplos anteriores permiten mostrar la versatilidad del optimizador
evolutivo como herramienta de optimización numérica. Estos ejemplos incluyeron
funciones de los siguientes tipos: cuadrática, multimodal, discontinua y unimodal. Sin
embargo, es importante mencionar que los cuatro ejemplos se escogieron para explicar
el uso del módulo de definición de problemas. En sí, los cuatro ejemplos no representan
problemas difíciles de optimización numérica. En la siguiente sección se describen
algunos mas complejos.
92
92
Capitulo IV: Resultados
93
93
Resultados
En esta sección se presentan y discuten los resultados obtenidos por el optimizador
evolutivo aplicado a un conjunto de problemas escogidos para medir su eficacia en la
solución de distintos problemas de optimización numérica. El conjunto de ocho
problemas incluyen funciones cuadráticas, no lineales y discontinuas sujetas a varias
restricciones. Todos los experimentos se realizaron en una estación de trabajo HP
Vectra con un procesador de 800 MHz, 128 Mb de RAM y el sistema operativo
Windows XP instalado. Los parámetros utilizados para el optimizador evolutivo fueron,
• Tamaño de la población: 70
• Probabilidad de cruzamiento: 0.7
• Probabilidad de mutación: 0.01
• Numero máximo de iteraciones: 10000
94
94
Problema número 1: (Michalewicz, 1996)
Minimizar ∑=
−−−−−−−=5
1
254321 5.0105.15.25.35.75.10),(
iixyxxxxxyf x
sujeto a: 5.62336 54321 ≤++++ xxxxx 201010 31 ≤++ yxx 10 ≤≤ ix y≤0
La solución global es )20,1,1,0,1,0(),( ** =yx y su valor objetivo es 213),( ** −=yxf .
El optimizador evolutivo logro conseguir soluciones muy cercanas a la óptima en diez
ejecuciones distintas. Una solución típica reportada por el optimizador evolutivo fue,
)000000.20,000000.1,999999.0,000000.0,000000.1,000000.0(
El valor de la función objetivo para esta solución es -213.0. El tiempo de ejecución para
esta solución en particular fue de 35 segundos para un total de 1500 iteraciones.
95
95
Problema número 2: (Hock & Schittkowski, 1981)
Minimizar ∑=
⎟⎟⎠
⎞⎜⎜⎝
⎛++
+=10
1 101 .....ln)(
j
jjj xx
xcxxf
sujeto a: 222 106321 =++++ xxxxx
12 109873 =++++ xxxxx 12 7654 =+++ xxxx
000001.0≥ix , )10....1( =i 914.5,054.34,164.17,089.6 4321 −=−=−=−= cccc
708.10,100.24,986.14,721.24 8765 −=−=−=−= cccc
La mejor solución reportada en (Hock & Schittkowski, 1981) para este problema es,
)05269826,.01984929,.007765639,.01727298,.0004335469,.4907851.,0007233256,.8825646,.08200180,.01773548(.* =x
La función objetivo en este punto es 707579.47)* −=(xf
Se realizaron diez ejecuciones distintas y todas generaron mejores soluciones que la
solución anterior. De las diez soluciones encontradas por el optimizador evolutivo la
mejor solución fue la siguiente,
)10128126,.03849563,.01849179,.02826479,.00068965,.48468539.,00167479,.77497089,.15386976,.04034785(.* =x
El valor de la función objetivo para este punto es 760765.47)( * −=xf . El número de
iteraciones de para cada ejecución fue de 1000 y en promedio cada ejecución requirió
unos 55 segundos.
96
96
Problema número 3: (Floudos & Pardalo, 1992)
Minimizar ∑∑==
−−+++=9
1
4
1
24321 55555),(
ii
ii yxxxxxf yx
sujeto a:
1022 7621 ≤+++ yyxx 1022 8732 ≤+++ yyxx
08 72 ≤+− yx 02 614 ≤+−− yyx 02 854 ≤+−− yyy
1022 8631 ≤+++ yyxx 08 61 ≤+− yx 08 83 ≤+− yx
02 732 ≤+−− yyy 10 ≤≤ ix , 4,3,2,1=i 10 ≤≤ iy , 9,5,4,3,2,1=i
iy≤0 , 8,7,6=i
La solución global es )1,3,3,3,1,1,1,1,1,1,1,1,1(),( ** =yx y su valor objetivo es
15),( ** −=yxf . El optimizador evolutivo consiguió el óptimo en todas las diez
ejecuciones que se realizaron. Una solución típica reportada por el optimizador
evolutivo fue,
)999999.0,999995.2,999995.2,999984.2,000000.1,000000.1,999999.0,000000.1,999995.0,000000.1,000000.1,000000.1,000000.1,000000.1(
El valor de la función objetivo para esta solución es -14.999965. El tiempo de ejecución
para esta solución en particular fue de 82 segundos para un total de 2500 iteraciones.
97
97
Problema número 4: (Floudos & Pardalo, 1987)
Maximizar
321
321
321
321
3724
28.023
)(xxxxxx
xxxxxx
f−++−
++−+−+
=x
sujeto a:
1321 ≤−+ xxx 8.3412512 321 ≤++ xxx
1.46 321 −≤++− xxx 1321 −≤−+− xxx
1.2971212 321 ≤++ xxx
ix≤0 , 3,2,1=i
La solución global es )0,0,1(* =x y su valor objetivo es 471428.2)( * =xf . El
optimizador evolutivo consiguió el óptimo en todas las diez ejecuciones que se
realizaron. Cada ejecución requirió en promedio 18 segundos y 500 iteraciones.
98
98
Problema número 5: (Floudos & Pardalo, 1992)
Minimizar
4316.0
26.0
1 346)( xxxxxxf +−−+=
sujeto a:
033 321 =−+− xxx 42 42 ≤+ xx
14 ≤x 42 31 ≤+ xx
31 ≤x
ix≤0 , 4,3,2,1=i
La solución a este problema reportada en (Floudos & Pardalo, 1992) es ⎟⎠⎞
⎜⎝⎛= 0,0,4,
34*x .
El valor de la función objetivo en ese punto es 5142.4)( * −=xf . El optimizador
evolutivo consiguió este punto en todas las diez ejecuciones que se realizaron. Cada
ejecución requirió en promedio 18 segundos y 500 iteraciones.
99
99
Problema número 6: (Colville, 1968)
Minimizar
)1)(1(8.19))1()1((1.10)1()(90)1()(100)(
42
24
22
23
2234
21
2212
−−+−+−+−+−+−+−=
xxxxxxxxxxf x
sujeto a: 1010 ≤≤− ix , 4,3,2,1=i
La solución global es )1,1,1,1(* =x y su valor objetivo es 0)( * =xf .
El optimizador evolutivo logro conseguir soluciones muy cercanas a la óptima en diez
ejecuciones distintas. Una solución típica reportada por el optimizador evolutivo fue,
)999909.0,999954.0,000087.1,000044.1(
El valor de la función objetivo para esta solución es 0.00000001. El tiempo de ejecución
para esta solución en particular fue de 358 segundos para un total de 10000 iteraciones.
100
100
Problema número 7: (Floudos & Pardalo, 1992)
Minimizar
543212 2325.05.6),( yyyyyxxxf −−−−−−=y
sujeto a:
165382 54321 ≤+++++ yyyyyx
142248 54321 −≤−++−−− yyyyyx
24432.05.02 54321 ≤−−−++ yyyyyx
122241.022.0 54321 ≤++−++ yyyyyx
335525.01.0 54321 ≤+−++−− yyyyyx
13 ≤y , 14 ≤y , 25 ≤y
0≥x , 0≥iy , 5,4,3,2,1=i
La solución global es )0,1,1,0,6,0(),( ** =yx y su valor objetivo es 11),( ** −=yxf .
El optimizador evolutivo consiguió este punto en todas las diez ejecuciones que se
realizaron. Cada ejecución requirió en promedio 37 segundos y 1000 iteraciones.
101
101
Problema número 8: (Hock & Schittkowski, 1981)
Minimizar )(xf
donde
0.1)(10)( 212
52 −−+= − xxxf x , si 20 1 <≤ x
( ) 32
21 9)3(
3271)( xxf −−=x , si 42 1 <≤ x
311)2(
31)( 2
31 −+−= xxf x si 64 1 ≤≤ x
sujeto a
03/ 21 ≥− xx
063 21 ≥+−− xx
60 1 ≤≤ x , 02 ≥x
La función objetivo f tiene tres soluciones globales. Estos son:
)0,0(*1 =x , )3,3(*
2 =x , )0,4(*3 =x
En todos los casos 1)( * −=if x , para todo 3,2,1=i
El optimizador evolutivo consiguió siempre el mismo punto )0,0(*1 =x en todas las diez
ejecuciones que se realizaron. Cada ejecución requirió en promedio 18 segundos y 500
iteraciones.
102
102
CONCLUSIONES
A lo largo de este trabajo se describió el desarrollo y la implementación de una
herramienta para resolver problemas de optimización no lineales, linealmente
restringidos basada en algoritmos genéticos. Las situaciones para las cuales esta
herramienta es aplicable incluyen una amplia categoría de problemas en investigación
de operaciones. La aplicación desarrollada intenta apoyar el proceso de solución de
problemas difíciles, para los cuales, los métodos convencionales de optimización
puedan resultar insuficientes. A continuación se mencionan algunas ventajas y
desventajas de dicha aplicación. Los aspectos positivos pueden resumirse en los
siguientes puntos,
• Robustez: La herramienta es aplicable a una gran variedad de problemas
distintos. Estos incluyen funciones no diferenciables, funciones discontinuas,
funciones multimodales, etc….
• Extensible: La herramienta puede extenderse a algunos problemas de
optimización no convexos mediante el uso de funciones de penalización.
• Configurable: Es posible combinar distintos conjuntos de parámetros o
conjuntos de restricciones con una misma función objetivo. La herramienta
puede guardar tantas configuraciones como se desee. Por ejemplo, el usuario
puede experimentar con distintas combinaciones de operadores genéticos y
mecanismos de selección hasta conseguir un juego de parámetros óptimo para
un problema en particular.
103
103
• La implementación de los operadores genéticos especialmente diseñados para
problemas de optimización convexa convierten al optimizador evolutivo en una
herramienta útil en problemas donde los métodos tradicionales no son
aplicables. Por otra parte, la mayoría de las implementaciones de algoritmos
genéticos no están adaptadas para este tipo de problemas y por lo tanto, no
sirven para explorar regiones convexas definidas por varias restricciones
lineales. El optimizador evolutivo, sin embargo, logra obtener la solución óptima
en muchos casos, y en otros tantos, obtiene una solución cuasi-optima.
Sin embargo, la herramienta presenta algunas desventajas las cuales son inherentes al
modo de funcionamiento de los algoritmos genéticos. El inconveniente principal es la
ausencia de criterios teóricos que establezcan condiciones que garanticen la
optimalidad de las soluciones halladas por el algoritmo. Esto implica que, en general, no
es posible saber si una solución obtenida por el algoritmo genético es óptima, aunque
esta realmente lo sea.
Sin embargo, en un contexto donde la optimalidad de una solución no sea un requisito
esencial el optimizador evolutivo puede ser una herramienta útil proporcionando
soluciones cuasi-optimas.
Otro inconveniente, es lo específico del diseño del algoritmo. Es decir, resultaría muy
difícil adaptar el algoritmo genético implementado en el optimizador evolutivo para
resolver problemas que sean de otra naturaleza. En contraste, el algoritmo genético de
Holland-Goldberg (Ver Figura 3) es aplicable a muchas situaciones distintas
(incluyendo la optimización numérica, aunque no con la misma eficacia). Sin embargo,
es importante mencionar que actualmente existe una tendencia a diseñar los algoritmos
genéticos para que sean más dependientes del problema en cuestión.
104
104
El optimizador evolutivo, es un buen ejemplo de esta corriente. El diseño de sus
operadores genéticos obedece primordialmente a las características del espacio de
soluciones que este debe explorar (regiones convexas).
105
105
RECOMENDACIONES
El optimizador evolutivo es una herramienta aplicable a muchos problemas de
optimización. Sin embargo, un aspecto que podría mejorar en buena medida el
desempeño de la herramienta, es la codificación de esta en un lenguaje más idóneo para
realizar procesamiento numérico. Visual Basic es mejor para aplicaciones empresariales
que incluyen trabajo con bases de datos, comunicación en redes, etc. Una aplicación
para optimización numérica es preferible implementarla en otro lenguaje como por
ejemplo C o en C++.
Finalmente una recomendación útil para aplicaciones de optimización numérica es que
se debe recurrir a un algoritmo genético cuando realmente sea necesario. Cualquier
método de optimización convencional es mucho mejor para el problema que fue
diseñado que un algoritmo genético. Los algoritmos genéticos son y deben ser utilizados
como métodos de último recurso. Es decir, su aplicación tiene sentido, solo cuando los
métodos clásicos no son aplicables.
106
106
BIBLIOGRAFIA
• Chong, E., Zak S.,(2001) An introduction to Optimization, 2nd edition, USA, John Wiley & Sons, Inc.
• Colville, A.R. A comparative Study on Nonlinear Programming Codes, IBM
Scientific Center Report,320-2949, NewYork,1968
• Floudos, C.A.; Pardalos, P.M., (1992) Recent Advances in Global Optimization, Princeton Series in Computer Science, Princeton University, Princeton, NJ.
• Floudos, C.A.; Pardalos, P.M., (1987) A collection of test problems for
Constrained Global Optimization Algorithms, Lecture Notes in Computer Science,Vol. 455, Springer Verlag
• Goldberg, D.E., (1989), Genetic Algorithms in Search, Optimization and
Machine Learning, Addison-Wesley. • Goldberg, D. E., Deb, K. (1991), Foundations of Genetic Algorithms, Morgan
Kauffman
• Hernandez R., José G.; García G. María J.; Jeannette Y. Pereira S.; Martha L. (1999) Programación dinámica a través del ordenador. Primer Simposio Ibérico de Informática Educativa.
• Hock, W.; Schittkowski K., (1981) Test examples for Nonlinear Programming
Codes, Lecture Notes in Economics and Mathematical Systems, Vol. 187, Springer Verlag.
• Holland, J. H., (1975), Adaptation in Natural and Artificial Systems, 2da
Edición, Michigan, MIT Press
• Knuth, D. E. (1973) The Art of Computer Programming. Volume 1: Fundamental Algorithms, Addison-Wesley
• Michalewicz, Z. (1996), Genetic Algorithms + Data Structures = Evolution
Programs, 3ra. Edición, New York: Springer
• Mitchell, M., (1996), An Introduction to Genetic Algorithms, Cambridge, MA: The MIT Press.
• Luenberger, D. (1989), Programación lineal y no lineal, México, D.F.,
Addison-Wesley Iberoamericana, S.A.
• Patton, R.J., Liu, G.P. (Mayo, 1994), Robust control design via eigenstructure assignment, genetic algorithms and gradient-based optimisation, IEEE Proceedings Control Theory, vol. 141, No 3, páginas 202-208
107
107
• Radcliff, N.J., (1991), Forma analysis and random respectful recombination, Proceedings of the Fourth International Conference on Genetic Algorithms, San Mateo, California, Morgan Kauffman.
• Yourdon, E (1993), Análisis Estructurado Moderno, Prentice Hall, México
108
108
Apéndice A
109
109
Optimizador Evolutivo
Diagrama de contexto
Par
ámet
ros
Niv
el 0
: Dia
gram
a de
con
text
o
Frecuencias de los operadores
Tamaño de la población
Mecanismo de selección
No. máximo de iteraciones
Restricciones lineales
Función objetivo
Solución óptima o cuasi-óptima
Frecuencias para todos los operadores: 4Número máximo de iteraciónes:10000Mecanismo de selección: Muestreo por ruletaTamaño de la población:70Numero de padres por cada generación:28
Usuario Optimizador evolutivo
Valores por defecto(Para mayores detalles sobre estos parámetros consultar el marco teorico)
110
110
Optimizador Evolutivo
Diagrama de flujo de datos
Niv
el 1
: Dia
gram
a de
fluj
o
Parámetros validados Parámetros
Parámetrosguardados
Parámetros de ejecución
Función objetivo Parámetros validados
Usuario
Soluciones optimas o cuasi-
optimas
Guardar parámetros
Proceso de compilación
Restaurarparámetros
Nota: El proceso de compilación requiere herramientas no incluidas en el optimizador evolutivo
Algoritmo genético
Validación de parametros
Configuracion del problema
Configuración del problema
Archivohistorico (log)
Función de aptitud
Número decaso
Incluye:* Restricciones lineales* Parámetros del algoritmo genetico*Número de caso
111
111
Algortimo genetico
Optimizador EvolutivoN
ivel
2: D
iagr
ama
de fl
ujo
Crearpoblación
InicialProblema original
con menos variables
Poblacion de soluciones factibles
Cromosomasfactibles
Condicion deparada satisfecha
Mecanismo de selección
No
Cromosomaspadres
Máximo de iteraciones
Mutación uniforme
Mutación no uniforme
Mutación en frontera
Configuracióndel problema
Iteracion=1
Cruzamientoaritmético
Cruzamientosimple
Eliminacion de ecuaciones
Cruzamientosimple
Cromosomas hijos
Solución optima osub-óptimaSi
Parametros
Iteracion =N
Archivo histórico (log) Si
112
112
Optimizador Evolutivo
Diagrama de entidad-relación
DER
Parámetros
ProblemaLibreriaFunciónobjetivo
Histórico de ejecución
(Archivo log)
con
Corresponde a
tiene Restricciones
Apéndice B
II
II
El siguiente fragmento de código es la rutina principal del programa. program sga; A Simple Genetic Algorithm - SGA - v1.0 (c) David Edward Goldberg 1986 All Rights Reserved uses crt; const maxpop = 100; maxstring = 32; type allele = boolean; Allele = bit position chromosome = array[1..maxstring] of allele; String of bits individual = record chrom:chromosome; Genotype = bit string x,y:real; Phenotype = unsigned integer fitness:real; Objective function value parent1, parent2, xsite:integer; parents & cross pt end; population = array[1..maxpop] of individual; var oldpop, newpop:population; Two non-overlapping populations popsize, lchrom, gen, maxgen:integer; Integer global variables pcross, pmutation, sumfitness:real; Real global variables nmutation, ncross:integer; Integer statistics avg, max, min:real; Real statistics rep_file: text; report file Include utility procedures and functions $I utility.sga %INCLUDE ./utility.sga Include pseudo-random number generator and random utilities $I random.apb %INCLUDE ./random.apb Include interface routines: decode and objfunc $I interfac.sga %INCLUDE ./interfac.sga Include statistics calculations: statistics $I stats.sga %INCLUDE ./stats.sga Include init. routines: initialize, initdata, initpop, initreport $I initial.sga %INCLUDE ./initial.sga Include report routines: report, writechrom $I report.sga %INCLUDE ./report.sga Include the 3 operators: select (reproduction), crossover, mutation $I triops.sga %INCLUDE ./triops.sga Include new population generation routine: generation $I generate.sga %INCLUDE ./generate.sga begin Main program gen := 0; Set things up initialize; repeat Main iterative loop gen := gen + 1; generation; statistics(popsize, max, avg, min, sumfitness, newpop); report(gen); oldpop := newpop; advance the generation until (gen >= maxgen) end. End main program
III
III
Rutinas de decodificación. (Rutinas de autoría propia) Las siguientes rutinas han sido especialmente implementadas para el ejemplo de la sección XX. Es decir, solo sirven para la decodificación de cromosomas compuestos por la concatenación de dos secuencias de 16 dígitos binarios, correspondientes a las variables X y Y del problema original. (Consultar sección XX para más detalles) interfac.sga: contains objfunc, decode Function decode1 (chrom:chromosome:integer):real Var j: integer; Acum,potencia:real; Begin acum:=0.0; potencia=1 Forj:=1 to 16 Begin If chrom[j] then acum:=acum+potencia potencia=potencia*2 End decode1:=(6*acum.)/(power(2,16)-1)-3; End; Function decode2 (chrom:chromosome:integer):real Var j: integer; Acum,potencia:real; Begin acum:=0.0; potencia=1 Forj:=17 to 32 Begin If chrom[j] then acum:=acum+potencia potencia=potencia*2 End decode2:= (6*acum.)/(power(2,16)-1)-3; End; Rutina para calcular la función de aptitud. (Rutina de autoría propia) En este caso, la aptitud de un cromosoma es igual a la función objetivo del ejemplo de la sección XX. Sin embargo, la manera como el muestreo por ruleta se encuentra implementado en este programa, obliga a que la función de aptitud sea positiva. Por lo tanto, se le suma un constante muy grande para lograr que esto se cumpla (por ejemplo: 1000, 10000 o cualquier valor grande). Finalmente, se multiplica el resultado por -1, por tratarse de un problema de minimización. (Consultar sección XX para más detalles) interfac.sga: contains objfunc, decode function objfunc(x,y:real):real; var a,b,c,coef: real; begin a:= 3*power(1-x,2)*exp(-1*power(x,2)-power(y+1,2)); b:=-10*((x/5)-power(x,3)-power(y,5))*exp(-1*power(x,2)-power(y,2)); c:=(-1/3)*exp(-1*power(x+1,2)-power(y,2)); objfunc :=-1*(a+b+c+10000) end;
IV
IV
Las siguientes rutinas determinan las siguientes estadísticas para una población dada: la aptitud promedio, la aptitud mínima y la aptitud máxima. stats.sga procedure statistics(popsize:integer; var max,avg,min,sumfitness:real; var pop:population); Calculate population statistics var j:integer; begin Initialize sumfitness := pop[1].fitness; min := pop[1].fitness; max := pop[1].fitness; Loop for max, min, sumfitness for j := 2 to popsize do with pop[j] do begin sumfitness := sumfitness + fitness; Accumulate fitness sum if fitness>max then max := fitness; New max if fitness<min then min := fitness; New min end; Calculate average avg := sumfitness/popsize; end; Rutinas para imprimir reportes report.sga: contains writechrom, report procedure writechrom(var out:text; chrom:chromosome; lchrom:integer); Write a chromosome as a string of 1's (true's) and 0's (false's) var j:integer; begin for j := lchrom downto 1 do if chrom[j] then write(out,'1') else write(out,'0'); end; procedure report(gen:integer); Write the population report const linelength = 132; var j:integer; begin repchar(rep_file,'-',linelength); writeln(rep_file); repchar(rep_file,' ',50); writeln(rep_file,'Population Report'); repchar(rep_file,' ',23); write(rep_file,'Generation ',gen-1:2); repchar(rep_file,' ',57); writeln(rep_file,'Generation ',gen:2); writeln(rep_file); write(rep_file,' # string x fitness'); write(rep_file,' # parents xsite'); writeln(rep_file, ' string x fitness'); repchar(rep_file,'-',linelength); writeln(rep_file); for j := 1 to popsize do begin write(rep_file,j:2, ') '); Old string with oldpop[j] do begin writechrom(rep_file,chrom,lchrom); write(rep_file,' ', x:10, ' ', fitness:6:4, ' |'); end; New string with newpop[j] do begin write(rep_file,' ', j:2, ') (', parent1:2, ',', parent2:2, ') ', xsite:2,' '); writechrom(rep_file,chrom,lchrom); writeln(rep_file, ' ',x:10,' ', fitness:6:4); end; end; repchar(rep_file,'-',linelength); writeln(rep_file); Generation statistics and accumulated values writeln(rep_file,' Note: Generation ', gen:2, ' & Accumulated Statistics: ' ,' max=', max:6:4,', min=', min:6:4, ', avg=', avg:6:4, ', sum=' ,sumfitness:6:4, ', nmutation=', nmutation:1, ', ncross= ', ncross:1); repchar(rep_file,'-',linelength); writeln(rep_file); page(rep_file); end;
V
V
Rutinas de inicialización (Población inicial, distintos contadores, etc) initial.sga: contains initdata, initpop, initreport, initialize procedure initdata; var ch, dummy:char; j:integer; begin rewrite(rep_file, 'NAME = report.txt' ); Set up for list device clrscr; Clear screen skip(output,9); repchar(output,' ',25); writeln('--------------------------------'); repchar(output,' ',25); writeln('A Simple Genetic Algorithm - SGA'); repchar(output,' ',25); writeln(' (c) David Edward Goldberg 1986'); repchar(output,' ',25); writeln(' All Rights Reserved '); repchar(output,' ',25); writeln('--------------------------------'); writeln('******** SGA Data Entry and Initialization ************'); writeln; write('Enter population size ------- > '); readln(popsize); write('Enter chromosome length ----- > '); readln(lchrom); write('Enter max. generations ------ > '); readln(maxgen); write('Enter crossover probability - > '); readln(pcross); write('Enter mutation probability -- > '); readln(pmutation); pause(5); clrscr; Initialize random number generator randomize; pause(2); clrscr; Initialize counters nmutation := 0; ncross := 0; end; procedure initreport; Initial report begin writeln(rep_file,'----------------------------------------------------'); writeln(rep_file,'| A Simple Genetic Algorithm - SGA - v1.0 |'); writeln(rep_file,'| (c) David Edward Goldberg 1986 |'); writeln(rep_file,'| All Rights Reserved |'); writeln(rep_file,'----------------------------------------------------'); skip(rep_file,5); writeln(rep_file,' SGA Parameters'); writeln(rep_file,' --------------'); writeln(rep_file); writeln(rep_file,' Population size (popsize) = ',popsize); writeln(rep_file,' Chromosome length (lchrom) = ',lchrom); writeln(rep_file,' Maximum # of generation (maxgen) = ',maxgen); writeln(rep_file,' Crossover probability (pcross) = ',pcross); writeln(rep_file,' Mutation probability (pmutation) = ',pmutation); skip(rep_file,8); writeln(rep_file,' Initial Generation Statistics'); writeln(rep_file,' -----------------------------'); writeln(rep_file); writeln(rep_file,' Initial population maximum fitness = ',max); writeln(rep_file,' Initial population average fitness = ',avg); writeln(rep_file,' Initial population minimum fitness = ',min); writeln(rep_file,' Initial population sum of fitness = ',sumfitness); page(rep_file); New page end; procedure initpop; Initialize a population at random var j, j1:integer; begin for j := 1 to popsize do with oldpop[j] do begin for j1 := 1 to lchrom do chrom[j1] := flip(0.5); A fair coin toss x := decode(chrom,lchrom); Decode the string fitness := objfunc(x); Evaluate inital fitness parent1 := 0; parent2 := 0; xsite := 0; Initialize printout vars end; end; procedure initialize; Initialization Coordinator begin initdata; initpop; statistics(popsize, max, avg, min, sumfitness, oldpop); initreport; end;
VI
VI
Rutinas para implementar muestreo por ruleta, cruzamiento y mutación triops.sga 3-operators: Reproduction (select), Crossover (crossover), & Mutation (mutation) function select(popsize:integer; sumfitness:real; var pop:population):integer; Select a single individual via roulette wheel selection var rand, partsum:real; Random point on wheel, partial sum j:integer; population index begin partsum := 0.0; j := 0; Zero out counter and accumulator rand := random * sumfitness; Wheel point calc. uses random number [0,1] repeat Find wheel slot j := j + 1; partsum := partsum + pop[j].fitness; until (partsum >= rand) or (j = popsize); Return individual number select := j; end; function mutation(alleleval:allele; pmutation:real; var nmutation:integer):allele; Mutate an allele w/ pmutation, count number of mutations var mutate:boolean; begin mutate := flip(pmutation); Flip the biased coin if mutate then begin nmutation := nmutation + 1; mutation := not alleleval; Change bit value end else mutation := alleleval; No change end; procedure crossover(var parent1, parent2, child1, child2:chromosome; var lchrom, ncross, nmutation, jcross:integer; var pcross, pmutation:real); Cross 2 parent strings, place in 2 child strings var j:integer; begin if flip(pcross) then begin Do crossover with p(cross) jcross := rnd(1,lchrom-1); Cross between 1 and l-1 ncross := ncross + 1; Increment crossover counter end else Otherwise set cross site to force mutation jcross := lchrom; 1st exchange, 1 to 1 and 2 to 2 for j := 1 to jcross do begin child1[j] := mutation(parent1[j], pmutation, nmutation); child2[j] := mutation(parent2[j], pmutation, nmutation); end; 2nd exchange, 1 to 2 and 2 to 1 ] if jcross<>lchrom then Skip if cross site is lchrom--no crossover for j := jcross+1 to lchrom do begin child1[j] := mutation(parent2[j], pmutation, nmutation); child2[j] := mutation(parent1[j], pmutation, nmutation); end; end;
VII
VII
La siguiente rutina procesa la siguiente generación a partir de la actual. generate.sga procedure generation; Create a new generation through select, crossover, and mutation Note: generation assumes an even-numbered popsize var j, mate1, mate2, jcross:integer; begin j := 1; repeat select, crossover, and mutation until newpop is filled mate1 := select(popsize, sumfitness, oldpop); pick pair of mates mate2 := select(popsize, sumfitness, oldpop); Crossover and mutation - mutation embedded within crossover crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j ].chrom, newpop[j + 1].chrom, lchrom, ncross, nmutation, jcross, pcross, pmutation); Decode string, evaluate fitness, & record parentage date on both children with newpop[j ] do begin x := decode1(chrom, lchrom); y := decode2(chrom, lchrom); fitness := objfunc(x,y); parent1 := mate1; parent2 := mate2; xsite := jcross; end; with newpop[j+1] do begin x := decode(chrom, lchrom); y := decode2(chrom, lchrom); fitness := objfunc(x,y); parent1 := mate1; parent2 := mate2; xsite := jcross; end; Increment population index j := j + 2; until j>popsize end; Rutinas de generación para números aleatorios. Nota: La función “random” depende del compilador utilizado. El código siguiente asume que “random” produce un número aleatorio entre 0 y 1. Sin embargo, en Turbo Pascal habría que sustituir “random” por “random(256)/256” (o algo parecido). random.apb: contains random number generator and related utilities including advance_random, warmup_random, random, randomize, flip, rnd function flip(probability:real):boolean; Flip a biased coin - true if heads begin if probability = 1.0 then flip := true else flip := (random <= probability); end; function rnd(low,high:integer):integer; Pick a random integer between low and high var i:integer; begin if low >= high then i := low else begin i := trunc( random * (high-low+1) + low); if i > high then i := high; end; rnd := i; end;
VIII
VIII
Distintas funciones de utilidad para formatear cadenas de caracteres. utility.sga: contains pause, page, repchar, skip, power procedure pause(pauselength:integer); Pause a while const maxpause = 2500; var j,j1:integer; x:real; begin for j := 1 to pauselength do for j1 := 1 to maxpause do x := 0.0 + 1.0; end; procedure page(var out:text); Issue form feed to device or file begin write(out,chr(12)) end; procedure repchar(var out:text; ch:char; repcount:integer); Repeatedly write a character to an output device var j:integer; begin for j := 1 to repcount do write(out,ch) end; procedure skip(var out:text; skipcount:integer); Skip skipcount lines on device out var j:integer; begin for j := 1 to skipcount do writeln(out) end; function power(x,y:real):real; Raise x to the yth power begin power := exp( y*ln(x) ) end; procedure clrscr; begin end;