• Categories
• Algoritmo genético
• Evolución
• Gen
• Selección natural
• Cromosoma

Citation preview

UNIVERSIDAD NACIONAL ABIERTA MATEMÁTICA CENTRO LOCAL METROPOLITANO

APLICACIÓN DE LOS ALGORITMOS GENÉTICOS SIMPLES EN LA OPTIMIZACIÓN DE FUNCIONES REALES (presentado para optar al título de Licenciado en Matemática Mención Análisis Numérico)

Raúl Inés Barrera Núñez

Caracas, junio de 2006

UNIVERSIDAD NACIONAL ABIERTA

i

Aprobación del Profesor Tutor

Luego de haber leído detenidamente el presente Trabajo de Grado, le doy mí aprobación tanto en lo referente a forma como a contenido.

______________________ José Ramón Gascón

UNIVERSIDAD NACIONAL ABIERTA

ii

INDICE GENERAL Página

APROBACIÓN DEL PROFESOR TUTOR VEREDICTO DEL JURADO

II

¡ERROR! MARCADOR NO DEFINIDO.

LISTA DE ILUSTRACIONES

V

RESUMEN

VI

GLOSARIO DE TÉRMINOS

VII

INTRODUCCIÓN

IX

CAPÍTULO I

1

LOS ALGORITMOS GENÉTICOS

1

1.1. Breve acercamiento a la biología genética

1

1.2. Historia furtiva 1.2.1. De la teoría de la evolución 1.2.2. De los algoritmos genéticos

4 4 5

1.3. Aspectos básicos de los algoritmos genéticos

7

1.4. Operacionalidad de los algoritmos genéticos simples 1.4.1. Características de los algoritmos genéticos simples 1.4.2. Ejecución del proceso de los algoritmos genéticos simples 1.4.3. Operadores genéticos

9 9 11 13

1.4.4. Ejemplo manual de optimización numérica mediante el AGS

15

1.4.5. Código fuente de un algoritmo genético simple

23

CAPÍTULO II

25

MÉTODOS CLÁSICOS DE OPTIMIZACIÓN NUMÉRICA

25

2.1. Algoritmo del gradiente con paso constante 2.1.1. Ejemplo manual del algoritmo del gradiente con paso constante

UNIVERSIDAD NACIONAL ABIERTA

25 27

iii

2.2. Algoritmo de Newton con paso constante 2.2.1. Ejemplo manual del algoritmo de Newton con paso constante

29 31

CAPÍTULO III

32

ENSAYOS DE APLICACIÓN DEL ALGORITMO GENÉTICO SIMPLE Y DE LOS MÉTODOS CLÁSICOS EN LA OPTIMIZACIÓN NUMÉRICA 32 3.1. Evaluación de la función

Y = x 2 sen 2 (10πx) + 1 en el dominio [0,2]

32

3.1.1. Aplicación del algoritmo genético simple 3.1.2. Aplicación de los métodos clásicos de optimización numérica 3.2. Evaluación de la función Z = 0,5 +

sen 2

(

)

x 2 + y 2 − 0,5

(1 + 0,001(x

2

+ y2

))

2

33 39

, en el dominio [-200, 200] X [-

200, 200] 3.2.1. Aplicación del algoritmo genético simple 3.2.2. Aplicación de los métodos clásicos de optimización numérica

40 41 42

CAPÍTULO IV

43

POSIBLES MODIFICACIONES AL ALGORITMO GENÉTICO SIMPLE Y CONCLUSIONES 43 4.1 Modificaciones sobre los operadores genéticos 4.1.1. Selección (Elitismo) 4.1.2. Cruce (Varios tipos) 4.1.1. Mutación

43 44 45 45

4.2

45

Conclusiones

ANEXO 1 ARTÍCULO DE PRENSA PUBLICADO EN EL CUERPO 4-8 DEL UNIVERSAL, EL 09/04/2006 47 ANEXO 2 CÓDIGO FUENTE DEL ALGORITMO GENÉTICO SIMPLE

50

A.2.1. Para funciones reales de una variable

50

A.2.2. Para funciones reales de dos variables

56

ANEXO 3 HERRAMIENTAS COMPUTACIONALES UTILIZADAS

62

REFERENCIA BIBLIOGRÁFICA

63

UNIVERSIDAD NACIONAL ABIERTA

iv

LISTA DE ILUSTRACIONES GRÁFICO

Página

1.

Diagrama de flujos del proceso del algoritmo genético simple

12

2.

Figura Nº 1 gráfica de la función Y = x 2 sen 2 (10πx) + 1

35

3.

Figura Nº 2 Valores regulares de la función para distintas generaciones

39

4.

Figura Nº 3 Número de mutaciones y cruces para distintas generaciones

40

5.

Figura Nº 4 Función de aptitud acumulada distintas generaciones

40

6.

Figura Nº 5 Valores regulares de la función en la población inicial

41

7.

Figura Nº 6 Valores regulares de la función en la población final

41

8.

Figura Nº 7 gráfica de la función

[-10, 10] X [-10-, 10]

9.

Figura Nº 8 gráficas de la función

[-5, 5] X [0, 2,5]

Z = 0,5 +

⎛ ⎞ sen 2 ⎜⎜ x 2 + y 2 ⎟⎟ − 0,5 ⎝ ⎠ 2 ⎛ ⎛ x 2 + y2 ⎞ ⎞ + 1 0,001 ⎜ ⎜ ⎟⎟ ⎝ ⎠⎠ ⎝

⎛ sen 2 ⎜⎜ x 2 + y 2 ⎝ Z = 0,5 + ⎛ ⎛ 2 ⎜ 1 + 0,001 ⎜ x + ⎝ ⎝

⎞ ⎟ − 0,5 ⎟ ⎠ 2 ⎞ y 2 ⎞⎟ ⎟ ⎠⎠

en el dominio 42

en el dominio 43

TABLAS I.

Tabla N° 1 Resumen de resultados empíricos

UNIVERSIDAD NACIONAL ABIERTA

37

v

RESUMEN El objeto del presente trabajo de grado es utilizar el concepto de algoritmo genético simple aplicado a la optimización de funciones de variable real (una y dos variables), siguiendo como referencia el libro intitulado Genetic Algorithms in Search, Optimization, and Machine Learning, cuyo autor es D. E. Golberg (1989), en cuanto al aspecto conceptual y al uso de las rutinas algorítmicas que en el mencionado texto se describen (modificadas brevemente por el autor). Los resultados de los ensayos experimentales realizados aplicando esta novedosa herramienta se compararon con los obtenidos mediante los métodos tradicionales de optimización numérica permitiendo evidenciar la potencialidad del algoritmo genético simple en un escenario donde las funciones presentan en su dominio de definición: oscilaciones moderadas y la existencia de varios máximos locales. El campo de aplicación de esta herramienta se encuentra en el conjunto de las funciones para las cuales las técnicas tradicionales especializadas fallan o no aplican. El tema de la convergencia del algoritmo genético no fue revisado en ninguno de sus aspectos. Aunque los resultados provenientes del algoritmo genético son incuestionablemente mejores no pretendemos demostrar que el mismo sea siempre más eficiente para resolver problemas de optimización.

Palabras claves: algoritmo, genético, optimización, funciones, reales.

UNIVERSIDAD NACIONAL ABIERTA

vi

GLOSARIO DE TÉRMINOS ADN (ácido desoxirribonucleico):

Es el compuesto contenido en el cromosoma,

responsable de la transmisión del material genético de la célula en el proceso de división celular conducente a la reproducción de un organismo. Alelo: Variantes o formas alternativas de un gen. Algoritmo: Procedimiento iterativo utilizado para resolver un problema matemático. Convergencia: Se dice que un objeto matemático posee la característica de convergencia (o converge), si tiende o se dirige a un objeto (o al mismo objeto) en la medida que sus elementos independientes varían en una dirección y sentido específicos. Cromosoma:

Es una diminuta estructura filiforme compuesta por ácidos nucleicos y

proteínas, presente en todas las células vegetales y animales. Error: Diferencia que existe entre un objeto matemático y otro mediante el cual intentamos representarlo. Evolución:

Consiste en el proceso de transitar, en inmensos lapsos de tiempo, por una

serie progresiva de transformaciones conducentes a una cúspide habitada por mentes supremas. Evolucionismo: Doctrina filosófica o científica basada en la evolución. Evolucionista: Ente partidario del evolucionismo. Fenotipo:

Conjunto de características hereditarias comunes a una determinada especie

vegetal o animal debido a la existencia de genes semejantes. Gen: Cada una de las partículas que en el núcleo de la célula condicionan la transmisión de los caracteres hereditarios. Genética: Es la ciencia que estudia la herencia biológica y la variación, apoyándose en las leyes y principios que gobiernan las semejanzas y diferencias entre los individuos de una misma especie. Genotipo: Conjunto de factores hereditarios legítimos de un individuo o de una especie.

UNIVERSIDAD NACIONAL ABIERTA

vii

Gradiente:

Sea f una función diferenciable sobre un abierto de un espacio vectorial

euclídeo E de dimensión finita. La diferencial de f se identifica a un campo de vectores, →

⎛

⎛→⎞

→⎞

⎝

⎝ ⎠

⎠

llamado gradiente de f y notado grad f, gracias a la relación d → f , h = ⎜ grad f ⎜⎜ x ⎟⎟ / h ⎟ . ⎜ ⎟ x Herencia:

Tendencia de la naturaleza a reproducir en los seres los caracteres de sus

antepasados. Mecánica molecular: Estudio de los movimientos de las moléculas y de sus átomos. Optimización:

Acción y efecto de buscar el objeto de mejor desempeño, calificado

mediante una función de aptitud o métrica. Promedio: Término medio o representante de un conjunto de objetos numéricos.

UNIVERSIDAD NACIONAL ABIERTA

viii

INTRODUCCIÓN El objeto de esta monografía es introducir el concepto de algoritmo genético e ilustrar alguna de sus aplicaciones. El algoritmo genético simple fue desarrollado por John Holland profesor de la Universidad de Michigan en Ann Arbor en los años setenta aunque las ideas de programas que usan técnicas evolutivas fueron desarrolladas en años anteriores. Se trata de un mecanismo de búsqueda de soluciones para diversos problemas basado en las ideas de la evolución de las especies de Darwin. Forma parte de un conjunto de técnicas computacionales que simulan procesos biológicos o naturales, entre estos se encuentran las redes neuronales, el recocido simulado y los propios algoritmos genéticos. Debemos señalar que desarrollamos en este trabajo de grado el algoritmo genético simple tal como aparece explicado en el libro de Goldberg (1989) (ver bibliografía). No nos ocupamos en detalle de la extensa gama de variaciones del algoritmo genético y sólo al final revisamos algunas de las posibilidades. Cabe señalar que actualmente diversas investigaciones se desarrollan en el campo de los algoritmos genéticos pero no vamos a detenernos en ellas. En cambio explicaremos en detalle el algoritmo genético simple y lo aplicaremos en el proceso de optimización de funciones de variable real (una y dos variables); también compararemos nuestros resultados con los que se obtienen con el clásico método del gradiente, el cual asume la regularidad de la función objetivo. La monografía en su capítulo primero, empieza explicando las nociones básicas del mecanismo de la herencia desde el punto de vista de la biología, así como la estructura en detalle del algoritmo genético simple. Una corrida del mismo es realizada prácticamente a mano, para ilustrar los diversos operadores genéticos y su implementación.

UNIVERSIDAD NACIONAL ABIERTA

ix

En el siguiente capítulo se exponen algunos métodos de optimización del análisis numérico, tales como el algoritmo del gradiente con paso constante y el algoritmo de Newton con paso constante. En el capítulo tercero se exponen los resultados numéricos, que arroja el algoritmo genético simple al optimizar funciones de una y dos variables, que oscilan moderadamente y comparamos estos resultados con los que se obtiene aplicando el algoritmo del gradiente con paso constante. Aunque

los

resultados

provenientes

del

algoritmo

genético

simple

son

incuestionablemente mejores, no pretendemos demostrar que el mismo sea siempre más eficiente para resolver problemas de optimización. En el último capítulo exponemos las conclusiones del trabajo y mencionamos brevemente algunas de las posibles modificaciones del algoritmo genético. Debemos señalar que no hemos tocado el problema de la convergencia del algoritmo genético, en particular no presentamos el “Teorema Fundamental” de Holland que carece de rigurosidad matemática y que ha motivado el uso de cadenas de Markov para presentar los aspectos de convergencia con una base sólida (ver Rudolph (1994) en la bibliografía). En una serie de anexos se presenta el código fuente del programa del algoritmo genético simple en lenguaje pascal y las características técnicas del computador y del compilador donde se realizaron los experimentos. Debemos señalar que el programa fue modificado del original del libro de Goldberg (1989), traduciendo al idioma castellano las salidas y declaraciones del mismo e incluyendo la posibilidad de trabajar con varias variables.

Por último, esperamos que este trabajo pueda servir de apoyo a los ingenieros, matemáticos y profesionales en general que busquen en el algoritmo genético una

UNIVERSIDAD NACIONAL ABIERTA

x

herramienta para resolver problemas, presentando una exposición auto contenida y concisa del mismo

UNIVERSIDAD NACIONAL ABIERTA

xi

CAPÍTULO I Los algoritmos genéticos 1.1. Breve acercamiento a la biología genética Se denomina gen la porción o sección particular de un cromosoma 1 que contiene las instrucciones o el material necesario para que un ser vivo presente un rasgo específico (por ejemplo: color del cabello, estatura, color de los pétalos, producción de las proteínas, color de la piel, etc.). Un gen está siempre localizado en la misma parte de un cromosoma determinado, y a este sitio se le denomina locus (del latín “lugar”). Debido a que los cromosomas están ubicados en parejas, en cada uno de los cromosomas homólogos están presentes los mismos genes, pero cada cromosoma puede presentar una variante de estos genes. A cada una de las variantes o formas alternativas de un gen se le llama alelo, y cada alelo se ubica siempre en el mismo locus dentro del cromosoma. La evolución se puede definir como los cambios en el pool o conjunto genético de una población. Según los informáticos evolucionistas, la evolución optimiza a la naturaleza, puesto que va creando seres cada vez más perfectos, cuya cumbre es el hombre. Indicios adicionales de esta optimización se encuentran en el organismo de los animales, desde el tamaño y tasa de ramificación de las arterias, diseñados para maximizar el flujo de sangre, hasta el conjunto de reacciones del metabolismo, diseñado para maximizar la cantidad de energía extraída de los alimentos.

1

Cromosoma: Elemento que existe en el núcleo de las células en el momento de su división o mitosis.

UNIVERSIDAD NACIONAL ABIERTA

1

Los mecanismos de cambio en la evolución alteran la proporción de un tipo determinado de alelos en una población específica, bien sea disminuyendo la variabilidad de los mismos o aumentándola. Los principales mecanismos que disminuyen la variabilidad son los siguientes: Selección natural: Mecanismo mediante el cual los individuos que tengan algún rasgo que los haga menos válidos para realizar su tarea de seres vivos, no llegan a reproducirse, y, por tanto, su patrimonio genético desaparece del pool; incluso algunos de ellos ni siquiera llegan a nacer. Deriva génica: El simple hecho de que un alelo sea más común que otro en la población, causa que la proporción de alelos de esta población vaya aumentando en una población aislada (efecto fundador). Los más importantes mecanismos que aumentan la variabilidad, los cuales suceden generalmente en el ámbito molecular, son los siguientes: Mutación: Es una alteración del código genético que puede suceder por múltiples razones y que se presenta en la naturaleza con una probabilidad muy baja de ocurrencia. Por generar nuevos individuos, es considerada el motor de la evolución. En el proceso de formación del ser humano, la enzima ADN polimerasa es la sustancia motivadora de cambios. Poliploidía: Las células normales poseen dos copias de cada cromosoma (diploide) y las células reproductivas una copia (haploides), sin embargo, puede suceder por accidente que alguna célula reproductiva tenga dos copias cada una, en tal caso, si se lograra combinar con otra célula diploide o haploide dará lugar a un ser vivo con varias copias de cada cromosoma (poliploide). La mayoría de las veces, la poliploidía da lugar a individuos con algún defecto genético (por ejemplo, el tener 3 copias del cromosoma 21 da lugar al Síndrome de Down), aunque en algunos casos se crean individuos viables. Un caso conocido de mutación fue el producido en el mosquito culex pipiens, en el cual se duplicó un gen que generaba una enzima que rompía los organofosfatos, componentes habituales de los insecticidas.

UNIVERSIDAD NACIONAL ABIERTA

2

Recombinación: Cuando dos células sexuales o gametos 2 , una masculina y otra femenina se combinan, los cromosomas de cada una de ellas también lo hacen, intercambiándose genes, que a partir de ese momento pertenecerán a un cromosoma diferente. A veces también se produce traslocación dentro de un cromosoma: una secuencia de código se elimina de un sitio y aparece en otro sitio del cromosoma, o en otro cromosoma. Flujo genético: Es un intercambio de material genético entre seres vivos de diferentes especies que suelen ser virus o bacterias. Normalmente este intercambio se produce a través de un vector mediante el cual incorporan a su material genético genes procedentes de una especie a la que infectan y a su vez cuando infectan a un individuo de otra especie pueden transmitirle sus genes a los tejidos generativos de gametos. De este conjunto de mecanismos, la selección natural actúa sobre el fenotipo y suele disminuir la diversidad, haciendo que sobrevivan sólo los individuos más aptos; los mecanismos que generan diversidad al combinar características actúan habitualmente sobre el genotipo. Aunque los detalles de la evolución no han sido completamente comprendidos, incluso hoy, existen algunas premisas en los que se fundamentan: ♦ La evolución es un problema que opera a nivel de cromosomas, y no a nivel de individuos. Cada individuo es codificado como un conjunto de cromosomas. ♦ La selección natural es el mecanismo mediante el cual los individuos mejor adaptados son los que tienen mayores posibilidades de reproducirse. ♦ El proceso evolutivo tiene lugar en la etapa de la reproducción. Sin embargo, los genetistas y los biólogos evolucionistas afirman que la evolución no sólo optimiza, sino que también adapta localmente en el espacio y en el tiempo; en cierto sentido, evolución significa progreso. Un organismo más evolucionado puede estar en desventaja competitiva con uno de sus antepasados, si se colocan en el ambiente de estos últimos. 2

Gameto: Célula reproductiva, masculina o femenina, cuyo núcleo sólo contiene n cromosomas

UNIVERSIDAD NACIONAL ABIERTA

3

1.2. Historia furtiva 1.2.1. De la teoría de la evolución La hipótesis de la teoría de la evolución, la cual se basa en que pequeños cambios heredables en los seres vivos y la selección natural son los dos hechos que provocan los cambios en la naturaleza y la generación de nuevas especies; fue descrita, aun desconociendo cual era la base de la herencia, por Charles Darwin (1859) en su libro “El Origen de las Especies” y presentada junto con Wallace, quien llegó a las mismas conclusiones de forma independiente. El señor Darwin pensaba que los rasgos de un ser vivo eran como un fluido, y que los elementos de los dos padres se mezclaban de manera continua en la descendencia; la debilidad de esta hipótesis estaba en que al cabo de cierto tiempo una población determinada tendría los mismos rasgos intermedios. En estudio publicado en la revista estadounidense Science (2006), se confirma que la reconstrucción del proceso de evolución de la mecánica molecular por etapas satisface los principios de la teoría de la evolución de Charles Darwin, lo cual demuestra la validez actual de este planteamiento (Véase Anexo 1). Quien descubrió que los caracteres se heredaban en forma discreta, y que se tomaban del padre o de la madre, dependiendo de su carácter dominante o recesivo, fue el monje agustino Gregor Mendel (1864) a través de experimentos realizados con arvejas para intentar responder algunas interrogantes del problema de la herencia. Las teorías de Mendel, quien trabajó en total aislamiento, se olvidaron y no se volvieron a redescubrir hasta principios del siglo XX. En 1902 el norteamericano Walter Sutton y el alemán Theodor Boverí, cada uno por su cuenta, advirtieron que el comportamiento de los cromosomas durante la meiosis 3 tenía una conducta paralela con la de los factores mendelianos en la transmisión de la herencia.

3

Meiosis: División celular mediante la cual una célula reproductora diploide (con cromosomas homólogos) se divide en cuatro células haploides (los cromosomas no tienen parejas y la información genética no está por

UNIVERSIDAD NACIONAL ABIERTA

4

W. Sutton y T. Boverí (1902) concluyeron que los factores hereditarios de que hablaba Mendel se encuentran localizados en los cromosomas, en el interior del núcleo celular. Este es el enunciado fundamental de la teoría cromosómica de la herencia. A partir de este hallazgo, se consideró que los factores hereditarios tenían una localización muy específica en el cromosoma y que al separarse cada uno de los cromosomas homólogos, se estaban separando por consiguiente los dos factores encargados de un rasgo determinado.

1.2.2. De los algoritmos genéticos El inicio de los estudios de lo que hoy podría llamarse algoritmos genéticos se presentó a finales de los años 50 y principios de los 60, en manos de biólogos evolucionistas que buscaban la explicación de los modelos de comportamiento de la evolución natural, mediante la optimización. En 1965; Ingo Rechenberg, profesor de la Universidad Técnica de Berlín, introdujo una técnica que llamó estrategia evolutiva, en la que no había población ni cruzamiento: cada padre mutaba para producir un descendiente y se conservaba el mejor de los dos, convirtiéndose en el padre de la siguiente ronda de mutación. Versiones posteriores de esta técnica introdujeron la idea de población. En 1966; L.J. Fogel, A.J. Owens y M.J. Walsh introdujeron en Norte América una técnica que se llamó programación evolutiva. En este método, las soluciones candidatas para los problemas se representaban como máquinas de estado finito sencillas; y al igual que en la estrategia evolutiva de Rechenberg, el algoritmo funcionaba mutando aleatoriamente dos máquinas simuladas y conservando la mejor de las dos. A finales de la década de los años 60; John Holland, siendo investigador de la Universidad de Michigan, desarrolló una técnica que permitió incorporar la selección natural a un programa. Luego de estudios a través de los cuales comprendió que la evolución es una forma de adaptación más potente que el aprendizaje, tomó Holland la decisión de

duplicado). Durante tal proceso, cada par de cromosomas homólogos presentes originalmente en la célula reproductora se separan y cada célula hija resultante contiene sólo uno de cada dos cromosomas homólogos.

UNIVERSIDAD NACIONAL ABIERTA

5

aplicar sus ideas sobre el tema para desarrollar programas adaptados a un fin específico. En el curso que dictaba en la mencionada universidad, denominado Teoría de Sistemas Adaptativos, con la participación de los estudiantes surgieron las ideas embrionarias de lo que se convertiría definitivamente en los algoritmos genéticos. Los objetivos de la investigación de John Holland fueron los siguientes: a.

Imitar los procesos adaptativos de los sistemas naturales y

b.

Diseñar sistemas artificiales (normalmente programas) que retengan los mecanismos más importantes de los sistemas naturales.

Más tarde David Goldberg (1989), alumno de Holland, fue pionero en tratar de aplicar los algoritmos genéticos a problemas industriales, logrando resultados favorables. El gran objetivo de Holland era lograr que las computadoras aprendieran por sí mismas, técnica que él inventó y denominó originalmente “planes reproductivos”, conocida de manera popular bajo el nombre de “algoritmo genético” después de la publicación de su libro en 1975. Como se observa, el motor de todos los elementos relacionados con los algoritmos genéticos se haya alimentado en la simple y poderosa idea de Charles Darwin: “El azar en la variación, junto con la ley de selección, es una técnica de resolución de problemas de gran complejidad y de aplicación casi ilimitada.” Por último, es importante señalar que los algoritmos genéticos se utilizan para abordar una amplia variedad de problemas en un conjunto de campos sumamente diversos, demostrando claramente su capacidad y potencialidad. Dentro de sus múltiples aplicaciones en diversas áreas, una pequeña muestra de éstas, se encuentra en los siguientes ejemplos: 1)

Diseño de salas de concierto con propiedades acústicas óptimas (Acústica).

2)

Diseño de la forma del ala de un avión supersónico (Ingeniería aeroespacial).

3)

Producción de curvas ajustadas a los datos en el problema de la curva de rotación galáctica (Astronomía y Astrofísica).

4)

Diseños de fármacos, en la llamada química combinatoria (Química).

UNIVERSIDAD NACIONAL ABIERTA

6

5)

Construcción de placas especiales de circuitos reconocedores de voz (Ingeniería eléctrica).

6)

Predicción del rendimiento futuro de acciones (Mercados financieros).

7)

Evolución de redes neuronales que pudieran jugar damas (Juegos).

8)

Utilización para los hipocentros de los terremotos, basándose en datos sismológicos (Geofísica).

9)

Diseño de polímeros conductores de electricidad basados en el carbono, conocidos como polianilinas (Ingeniería de materiales).

10)

Descubrimiento de una regla para el problema de clasificación por mayoría en autómatas celulares de una dimensión (Matemática y algoritmia).

11)

Evolución de planes tácticos para las batallas militares (Ejército y cumplimiento de la ley).

12)

Detección de la presencia de ciertas sustancias en el exterior de la célula o transportarla hacia el interior de ésta (Biología nuclear).

13)

Evolución de un complejo sistema de reconocimiento de patrones con una amplia variedad de usos potenciales (Reconocimiento de patrones y explotación de datos).

14)

Promoción de nuevas tecnologías en el campeonato anual de fútbol entre equipos de robots autónomos (Robótica).

15)

Diseño de horarios de los exámenes universitarios (Diseño de rutas y horarios).

16)

Diseño de molinos eólicos para generar energía eléctrica, mediante tarea multiobjetivos (Ingeniería de sistema).

1.3. Aspectos básicos de los algoritmos genéticos Se presenta en este aparte, un conjunto de factores básicos requeridos para poder abordar la técnica de optimización mediante la aplicación de los algoritmos genéticos, los cuales irán acompañados de ejemplos sencillos que permitan comprender su proceso.

UNIVERSIDAD NACIONAL ABIERTA

7

Los algoritmos genéticos son métodos de búsqueda y optimización basados en la teoría de la evolución de Charles Darwin, los cuales constituyen uno de los focos de mayor atractivo para los investigadores de las diversas ramas del saber. El método de búsqueda está basado en los mecanismos de selección que utiliza la naturaleza para que los individuos más aptos de una población sobrevivan, debido a su capacidad para adaptarse más fácilmente a los cambios que se producen en su entorno. Estos cambios que se efectúan en los genes de un individuo y cuyos atributos son transmitidos a sus descendientes cuando éstos se reproducen sexualmente. John Koza (1992), profesor de la Universidad de Stanford, propone la siguiente definición de algoritmo genético:

“Es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que se destaca la recombinación sexual. Cada uno de estos objetos matemáticos suelen ser una cadena de caracteres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta función matemática que refleja su aptitud.” Los algoritmos genéticos están enmarcados junto con la programación evolutiva, las estrategias evolutivas, los sistemas clasificadores y la programación genética dentro una rama de la computación denominada computación evolutiva. Las bases biológicas de estos algoritmos y sus diferencias se centran en los operadores que utilizan en sus procesos. En la lista siguiente indican de las técnicas mencionadas anteriormente y sus respectivos objetivos: Nombre de la técnica

Objetivo

Algoritmo genético

Individuo óptimo

Programación genética

Programa óptimo

Programación evolutiva

Operador genético óptimo

Estrategia Evolutiva

Aprendizaje óptimo

Sistema clasificador

Población óptima

UNIVERSIDAD NACIONAL ABIERTA

8

1.4. Operacionalidad de los algoritmos genéticos simples 1.4.1. Características de los algoritmos genéticos simples La aplicación más común de los algoritmos genéticos simples (AGS) ha sido la solución de problemas de optimización, donde han mostrado alta eficiencia y gran confiabilidad. Sin embargo no todos los problemas son apropiados para ser resueltos por esta técnica; las siguientes características son fundamentales para su aplicación: ♦ El espacio de búsqueda (sus posibles soluciones) debe estar delimitado dentro de un cierto rango. ♦ Se debe definir una función de aptitud que indique qué tan buena o mala es la adaptación de los individuos. ♦ Las posibles soluciones se codifican utilizando el código binario (0’s y 1’s). El espacio de búsqueda debe ser siempre discreto (aunque sea muy grande). Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, cuando exista un rango relativamente pequeño. La función de aptitud (o alguna modificación de ésta) es la función objetivo del problema de optimización tratado. El resultado que produce ésta es un número real, preferiblemente no negativo que a mayor resultado es mejor la solución. El algoritmo genético únicamente maximiza, pero la minimización puede realizarse fácilmente utilizando el reciproco de la función maximizante, siempre que el mismo esté determinado. Una característica que debe presentar la función es que tiene que ser capaz de castigar a las malas soluciones y de premiar a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez. Dentro del conjunto de ventajas y desventajas manifiestas en la técnica de búsqueda y optimización mediante el uso de los algoritmos genéticos simples, podemos mencionar las siguientes: Ventajas:

UNIVERSIDAD NACIONAL ABIERTA

9

a.

No necesitan conocimientos específicos sobre el problema que intentan resolver, en particular si la función es “regular”.

b.

Operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales.

c.

Cuando se usan para problemas de optimización (maximizar una función objetivo) resultan menos afectadas por los máximos locales (aparentes soluciones) que las técnicas tradicionales.

Esta importante ventaja servirá de plataforma para el desarrollo de las pruebas empíricas, que permitirán demostrar su potencialidad, la cual constituirá el objetivo principal de esta monografía.

d.

Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivamente paralelas.

e.

Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de las otras técnicas.

Desventajas:

a.

Es difícil determinar la velocidad de convergencia (o aún la convergencia), dependiendo en cierta medida de los parámetros que se utilicen (tamaño de la población, número de generaciones, nivel de precisión deseado, etc.).

b.

Pueden converger prematuramente debido a una serie de problemas relacionados con los valores de sus parámetros.

Dado un problema específico a resolver, la entrada del algoritmo genético simple representa un conjunto de soluciones potenciales del mismo, codificadas mediante el alfabeto binario y una métrica llamada función de aptitud que permite evaluar cuantitativamente a cada candidata. Estas candidatas pueden ser soluciones factibles, con el objetivo de que el AGS las mejore, pero se suelen generar aleatoriamente.

UNIVERSIDAD NACIONAL ABIERTA

10

1.4.2. Ejecución del proceso de los algoritmos genéticos simples Los pasos que se ejecutan en el proceso de aplicación de los algoritmos genéticos simples para la simulación sucinta de la evolución natural, se presentan en el siguiente diagrama:

UNIVERSIDAD NACIONAL ABIERTA

11

Diagrama de flujos del proceso del algoritmo genético simple

Codificar el dominio del problema

Generar un conjunto aleatorio de N soluciones factibles

Calificar cada solución factible (aplicar la función de aptitud)

A

Seleccionar dos individuos de acuerdo a su calificación

B

Cruzar o mezclar los códigos genéticos de los dos individuos seleccionados

Mutar algunos elementos del código genético de ciertos individuos

Incluir a los dos nuevos en una nueva población

Condición de finalizar?

si Fin

no A

La nueva Población tiene N individuos?

si

Denominarla población actual

no B

UNIVERSIDAD NACIONAL ABIERTA

12

1.4.3. Operadores genéticos Los operadores genéticos de mayor uso en la aplicación de los algoritmos genéticos simples son descritos brevemente y además utilizados en los casos prácticos a desarrollar el siguiente capítulo. a. Selección Dado el conjunto de individuos de la población actual con una probabilidad proporcional a su calificación, la operación de selección consiste en elegir dentro del mencionado conjunto, a los individuos mejor adaptados al medio en términos del resultado de la función de aptitud. Entre las múltiples formas de selección comúnmente utilizadas cabe mencionar a las siguientes: selección proporcional a la aptitud, selección por rueda de ruleta, selección elitista, selección escalada, selección por torneo, selección por rango, selección generacional, selección por estado estacionario, selección jerárquica. Para el caso del algoritmo genético simple, la selección de mayor popularidad es la selección proporcional a la aptitud equivalente a la selección por rueda de ruleta. b. Cruce Cruzar o mezclar los códigos genéticos de dos individuos seleccionados como padres para generar hijos que posean códigos mixtos. Este operador genético también tiene varias acepciones, debido a que existen muchas formas de hacerlo, sin embargo, para nuestro caso utilizaremos el cruzamiento de un punto (1-point crossover) el cual se escoge al azar. 1.

Mediante el Proceso de Bernoulli 4 (con probabilidad pc de éxito).

2.

Si ocurre un éxito cruzar o mezclar los códigos de los dos individuos seleccionados para formar dos sujetos mixtos, a los que llamaremos nuevos individuos.

4

Un experimento de Bernoulli es aquel en el que pueden ocurrir exclusivamente dos eventos posibles, uno con probabilidad de éxito pc y otro con probabilidad de fracaso 1-pc).

UNIVERSIDAD NACIONAL ABIERTA

13

3.

Si ocurre un fracaso llamamos a los individuos seleccionados nuevos individuos. Gráficamente el operador genético de cruzamiento de un punto (1-point

crossover), con punto de cruce en la tercera posición del cromosoma, es como sigue:

Puntos de Cruce

Padres

1

0

0

1

0

1

0

1

1

1

1

0

0

1

1

1

1

0

Descendientes

1

0

0

0

1

1

1

1

0

1

1

0

1

0

1

0

1

1

c. Mutación Mutar o alterar deliberadamente algunos elementos del código de ciertos individuos, los cuales se seleccionan aleatoriamente, para así generar nuevos individuos ubicados en regiones del problema no exploradas aún. 1.

Por cada bit de cada nuevo individuo, mediante el Proceso de Bernoulli (con probabilidad pm de éxito).

2

Si ocurre un éxito cambiar el bit en turno por su complemento.

3

Si ocurre un fracaso el bit permanece inalterado. Gráficamente el operador genético de mutación como sigue: 1

1

1

0

1

0

1

0

0

1

1

0 Descendiente

1

1

1

0

1

1

1

0

0

1

1

0 Descendiente mutado

Los

gen mutado

parámetros del algoritmo genético que deben ser tomados en cuenta al realizar un ensayo empírico son: los valores de probabilidad para los operadores reproducción, cruce y mutación, el tamaño de la población, el número de generaciones, la precisión deseada y el

UNIVERSIDAD NACIONAL ABIERTA

14

tipo de selección a utilizar. Además, es necesario establecer el rango o el intervalo de búsqueda y la codificación de la función objetivo. Los parámetros empíricos recomendables para el algoritmo genético simple se señalan a continuación: Número de generaciones

57

Tamaño de la población

47

Probabilidad de cruce

0,60

Probabilidad de mutación

0,03

Selección

ruleta

La convergencia del algoritmo genético simple, se apoya en el siguiente enunciado “Siendo que el algoritmo genético simple opera con una población en cada iteración, es de esperarse que el método, al final del proceso, de cómo resultado que la mayoría de los individuos de la población sean muy similares, y que en el infinito todos sean iguales.” La teoría para estudiar la convergencia de estos algoritmos en caso de cadenas binarias, se basa principalmente en considerar que una cadena es un representante de una clase de equivalencia o esquema. John Holland, con el Teorema los Esquemas, intenta dar respuesta a que si existe una manera matemática que indique como se afectará a la siguiente generación en el proceso evolutivo, el cual depende de la selección, cruce y mutación. A partir de los resultados, el Teorema de los Esquemas (Teorema Fundamental), prueba que la población converge a unos esquemas que cada vez son más parecidos, y en el límite a una cadena única. El mencionado teorema ha sido cuestionado por muchos matemáticos, sin embargo el tiempo ha permitido avances importantes al respecto, lo cual da robustez al mismo.

1.4.4. Ejemplo manual de optimización numérica mediante el AGS

UNIVERSIDAD NACIONAL ABIERTA

15

Para la función f ( x ) = x

2

Usando un algoritmo genético simple con probabilidad de cruce pC = 0,60 y probabilidad de mutación pM = 0.03333, para 5 generaciones, con selección por torneo (este mecanismo de selección es distinto al utilizado en el Anexo 2, se indica sólo a manera de ilustración).

Se desea encontrar el valor de x que hace que la función f(x) alcance su valor máximo, siendo el rango de la variable x los valores enteros comprendidos entre 0 y 31. Sabemos que el máximo se alcanza en x = 31, donde f vale 961. Lo primero que debemos hacer es codificar las posibles soluciones (posibles valores de x). Lo haremos con la codificación binaria. Esto es (0,0,0,0,0) equivale a x = 0 y que (1,1,1,1,1) equivale a x = 31. Cada posible valor de la variable x en representación binaria se le denomina individuo. Una colección de individuos constituye lo que se denomina población y el número de individuos que la componen es el tamaño de la población. Una vez que tenemos codificada la solución, debemos escoger un tamaño de población. Para este ejemplo vamos a escoger 6 individuos. Debemos partir de una población inicial. Una manera de generarla aleatoriamente, puede ser lanzando una moneda al aire; si sale cara, la primera componente del primer individuo es un 0 y en caso contrario es un 1. Se repite el lanzamiento de la moneda y tendremos la segunda componente del primer individuo (un 0 si sale cara y un 1 si sale sello). Así hasta 5 veces y se obtendrá el primer individuo. Se repite la secuencia anterior para generar los individuos restantes de la población. En total se realizan 5 * 6 = 30 lanzamientos de la moneda.

Iteración 1

UNIVERSIDAD NACIONAL ABIERTA

16

El siguiente paso es hacer competir a los individuos entre sí. Que utilizaremos en nuestro caso como un proceso de selección. En la tabla 1 se resume este paso. Tabla 1.- SELECCIÓN N° del individuo

Población inicial

Valor de X

Valor de F(x)

Pareja asignada

1

(0,1,1,0,0)

12

144

6

2

(1,0,0,1,0)

18

324

3

3

(0,1,1,1,1)

15

225

2

4

(1,1,0,0,0)

24

576

5

5

(1,1,0,1,0)

26

676

4

6

(0,0,0,0,1)

1

1

1

Como de observa en la tabla precedente, el mejor individuo es el 5 (f(5) = 676). Al Calcular la media de f resulta fmed = 324,33. Ahora bien, una manera de realizar el proceso de selección es mediante un torneo entre dos. A cada individuo de la población se le asigna una pareja y entre ellos se establece un torneo: el mejor genera dos copias y el peor se descarta. En la última columna se indica la pareja asignada a cada individuo, lo cual se ha realizado aleatoriamente. Es importante resaltar, como se dijo anteriormente, que existen muchas variantes de este proceso de selección. Después de realizar el proceso de selección, la población que tenemos es la mostrada en la columna 2 de la tabla 2. Observamos, por ejemplo, que en el torneo entre el individuo 1 y el 6 de la población inicial, el primero de ellos ha recibido dos copias, mientras que el segundo no es tomado en cuenta. Este proceso se repite hasta completar la tabla 2 que sigue:

Tabla 2.- CRUCE N° del individuo

Población 1

Pareja asignada

1

(0,1,1,0,0)

5

2

(1,0,0,1,0)

3

3

(1,0,0,1,0)

2

4

(1,1,0,1,0)

6

5

(1,1,0,1,0)

1

6

(0,1,1,0,0)

4

Tras realizar la selección, se realiza el cruce. Que en este caso lo haremos mediante el cruce de un punto, esto es: se forman parejas entre los individuos aleatoriamente de

UNIVERSIDAD NACIONAL ABIERTA

17

forma similar a la selección. Dados dos individuos pareja, que se van ha cruzar, se establece un punto de cruce aleatorio, que no es más que un número aleatorio entre 1 y 4 (la longitud del individuo menos 1). Por ejemplo, en la pareja 2-3 el punto de cruce es 3, lo que significa que un hijo de la pareja conserva los tres primeros bits de la pareja 2 y hereda los dos últimos de la pareja 3, mientras que el otro hijo de la pareja conserva los tres primeros bits de la pareja 3 y hereda los dos últimos de la pareja 2. La población resultante se muestra en la columna (2) de la tabla 3. Cabe destacar que en el ensayo en todas las parejas se efectuó el cruce y el individuo 2 sufrió una mutación en el bit 3. Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIÓN N° del individuo

Población 1

Valor de X

Valor de F(x)

1

(0,1,1,1,0)

14

196

2

(1,0,1,1,0)

22

484

3

(1,0,0,1,0)

18

324

4

(1,1,0,0,0)

24

576

5

(1,1,0,0,0)

24

576

6

(0,1,1,1,0)

14

196

Ahora el valor máximo de f es 576 (para los individuos 4 y 5), mientras que antes de la selección, el cruce y la mutación era de 676. Aunque el máximo individual disminuyó, se observa que fmed ha escalado de 324,3 a 392, significa que la población después de la selección, el cruce y la mutación es mejor que antes de estas transformaciones. El siguiente paso es volver a realizar la selección, el cruce y la mutación tomando como población inicial la de la tabla 3. Esta manera de proceder se repetirá hasta construir 5 generaciones y como el resultado será la mejor solución de la última iteración, aunque también se puede ir guardando la mejor solución de todas las iteraciones anteriores y al final tomar la mejor solución. En realidad un algoritmo genético no garantiza la obtención del óptimo pero, si está bien construido, proporcionará una solución razonablemente buena. Puede ocurrir también que se obtenga el óptimo, pero el algoritmo no tiene capacidad para, en ese momento, detener el proceso y dar información del resultado. Iteración 2

UNIVERSIDAD NACIONAL ABIERTA

18

Repitiendo todo el proceso indicado para la construcción de la pareja asignada, nos resulta la siguiente tabla poblacional donde aplicaremos el operador de selección tal como se hizo en la iteración 1: Tabla 1.- SELECCIÓN N° del individuo

Población 2

Valor de X

Valor de F(x)

Pareja asignada

1

(0,1,1,1,0)

14

196

3

2

(1,0,1,1,0)

22

484

2

3

(1,0,0,1,0)

18

324

4

4

(1,1,0,0,0)

24

576

5

5

(1,1,0,0,0)

24

576

6

6

(0,1,1,1,0)

14

196

1

Después del proceso de selección tenemos a continuación la tabla de cruce para la iteración 1: Tabla 2.- CRUCE N° del individuo

Población 2

Pareja asignada

1

(1,0,0,1,0)

5

2

(1,0,1,1,0)

6

3

(1,1,0,0,0)

3

4

(1,1,0,0,0)

4

5

(1,1,0,0,0)

1

6

(0,1,1,1,0)

2

Aplicando los operadores genéticos de cruce y mutación, nos resulta la siguiente tabla poblacional. Cabe destacar que en el ensayo en todas las parejas se efectuó el cruce y ningún individuo sufrió una mutación.

Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIÓN N° del individuo

Población 2

Valor de X

Valor de F(x)

1

(1,0,0,0,0)

16

256

2

(1,0,1,1,0)

22

484

3

(1,1,0,1,0)

26

676

4

(1,1,0,0,0)

24

576

5

(1,1,0,1,0)

26

676

6

(0,1,1,1,0)

14

196

Ahora el valor máximo de f es 676 (para los individuos 3 y 5), que era el máximo en la población inicial, se observa que fmed ha aumentado de 392 a 473,33, nuevamente se

UNIVERSIDAD NACIONAL ABIERTA

19

evidencia que la población va mejorando a medida que se le aplican los operadores genéticos a sus individuos. Repitiendo el proceso anterior, los resultados de las iteraciones restantes son los siguientes: Iteración 3 Tabla 1.- SELECCIÓN N° del individuo

Población 3

Valor de X

Valor de F(x)

Pareja asignada

1

(1,0,0,0,0)

16

256

3

2

(1,0,1,1,0)

22

484

6

3

(1,1,0,1,0)

26

676

2

4

(1,1,0,0,0)

24

576

5

5

(1,1,0,1,0)

26

676

4

6

(0,1,1,1,0)

14

196

1

Tabla 2.- CRUCE N° del individuo

Población 3

Pareja asignada

1

(1,1,0,1,0)

5

2

(1,0,1,1,0)

4

3

(1,1,0,1,0)

3

4

(1,1,0,1,0)

2

5

(1,1,0,0,0)

1

6

(1,0,0,0,0)

6

Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIÓN N° del individuo

Población 3

Valor de X

Valor de F(x)

1

(1,1,0,0,0)

24

576

2

(1,0,1,1,0)

20

400

3

(1,1,0,1,0)

26

676

4

(1,1,0,1,0)

24

576

5

(1,1,0,1,0)

26

676

6

(1,0,0,0,0)

16

256

En las parejas 3 y 6 se efectuó el cruce y ningún individuo sufrió una mutación. El valor máximo de f es 676 (individuos 3 y 5) y fmed ha aumentado de 473,33 a 500.

UNIVERSIDAD NACIONAL ABIERTA

20

Iteración 4 Tabla 1.- SELECCIÓN N° del individuo

Población 4

Valor de X

Valor de F(x)

Pareja asignada

1

(1,1,0,0,0)

24

576

2

2

(1,0,1,0,0)

20

400

1

3

(1,1,0,1,0)

26

676

6

4

(1,1,0,0,0)

24

576

5

5

(1,1,0,1,0)

26

676

3

6

(1,0,0,1,0)

18

196

4

Tabla 2.- CRUCE N° del individuo

Población 4

Pareja asignada

1

(1,1,0,0,0)

6

2

(1,1,0,0,0)

4

3

(1,1,0,1,0)

5

4

(1,1,0,1,0)

2

5

(1,1,0,1,0)

3

6

(1,1,0,0,0)

1

Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIÓN N° del individuo

Población 4

Valor de X

Valor de F(x)

1

(1,1,0,0,0)

24

576

2

(1,1,0,0,0)

24

576

3

(1,1,0,1,0)

26

676

4

(1,1,0,0,0)

26

676

5

(1,1,0,1,0)

26

676

6

(1,0,0,1,0)

18

324

En todas las parejas se efectuó el cruce y ningún individuo sufrió una mutación. El valor máximo de f es 676 (individuos 3, 4 y 5) y fmed ha aumentado de 500 a 584. Iteración 5 Tabla 1.- SELECCIÓN N° del individuo

Población 5

UNIVERSIDAD NACIONAL ABIERTA

Valor de X

Valor de F(x)

Pareja asignada

21

1

(1,1,0,0,0)

24

576

5

2

(1,1,0,0,0)

24

576

4

3

(1,1,0,1,0)

26

676

1

4

(1,1,0,0,0)

26

676

3

5

(1,1,0,1,0)

26

676

6

6

(1,0,0,1,0)

18

324

2

Tabla 2.- CRUCE N° del individuo

Población 5

Pareja asignada

1

(1,1,0,1,0)

3

2

(1,1,0,1,0)

6

3

(1,1,0,1,0)

1

4

(1,1,0,1,0)

5

5

(1,1,0,1,0)

4

6

(1,1,0,0,0)

2

Tabla 3.- POBLACION TRAS EL CRUCE Y DE LA MUTACIÓN N° del individuo

Población 5

Valor de X

Valor de F(x)

1

(1,1,0,1,0)

26

676

2

(1,1,0,0,0)

24

576

3

(1,1,0,1,0)

26

676

4

(1,1,0,1,0)

26

676

5

(1,1,0,1,0)

26

676

6

(1,0,1,1,0)

22

484

En todas las parejas se efectuó el cruce y el individuo 6 sufrió una mutación en el bit 3. El valor máximo de f es 676 (individuos 1, 3, 4 y 5) y fmed ha aumentado de 584 a 627,33.

Como la condición del proceso es finalizar en la quinta generación, el algoritmo genético en este caso nos da como resultado que el máximo de la función para el intervalo estudiado es 676; se evidencia la necesidad de seguir iterando, en este caso, porque conocemos el valor máximo de la función. He aquí un problema real del algoritmo, que es la tendencia a la homegeinización de la población, es decir a que todos los individuos de la misma sean idénticos. Esto impide que el algoritmo siga explorando nuevas soluciones, con lo que podemos quedar estancados en un máximo local no muy bueno. Existen técnicas

UNIVERSIDAD NACIONAL ABIERTA

22

para contrarrestar esta situación. El mecanismo más elemental, aunque no siempre suficientemente eficaz, es introducir una mutación tras la selección y el cruce. Una vez que se ha realizado la selección y el cruce se selecciona un número determinado de bits de la población y se alteran aleatoriamente.

1.4.5. Código fuente de un algoritmo genético simple Existen varios paquetes y bibliotecas de algoritmos genéticos en el mercado, sin embargo, de acuerdo a las características específicas de algún problema, se hace necesario reimplementar todo el algoritmo, en vez de emplear algún paquete preexistente. Algunos de esos paquetes son:

•

GALOPPS:

Su

dirección

primaria

en

Internet

es

GARAGe.cps.msu.edu/software/software-index.html, y su dirección para descargarlo vía FTP es garage.cps.msu.edu/pub/GA/galopps/ •

GAGS: Generador de aplicaciones basadas en algoritmos genéticos, escrito en C++. Desarrollado por el grupo de J.J. Melero. Excelente. Su dirección Web es kalel.ugr.es/gags.html, y su dirección para descargarlo vía FTP es kal-el.ugr.es/GAGS/.

•

FORTRAN GA: Desarrollo de algoritmos genéticos para Fortran. Su dirección Web es www.staff.uiuc.edu/~ carroll/ga.html.

•

Galib: Biblioteca de algoritmos genéticos de Matthew. Conjunto de clases en C++ de algoritmos genéticos. Su dirección Web es lancet.mit.edu/ga/, y su dirección para descargarlo

vía

FTP

es

lancet.mit.edu/pub/ga/.

Podemos

registrarlo

en

http://lancet.mit.edu/ga/Register.html. •

GAS: Paquete para desarrollar aplicaciones de algoritmos genéticos en Python. Su dirección Web es starship.skyport.net/crew/gandalf, y su dirección para descargarlo vía FTP es ftp.coe.uga.edu/users/jae/ai.

•

GECO: Conjunto de herramientas para Lisp. Su dirección para descargarlo vía FTP es ftp://ftp.aic.nrl.navy.mil/pub/galist/src/.

UNIVERSIDAD NACIONAL ABIERTA

23

•

GPdata: Para desarrollar algoritmos genéticos en C++. Su dirección para descargarlo vía FTP es ftp.cs.bham.ac.uk/pub/authors/W.B.Langdon/gp-code/, y su documentación -GPdata-icga-95.ps- la podemos encontrar en el site de Internet cs.ucl.ac.uk/genetic/papers/.

•

gpjpp: Bibliotecas de clases para desarrollar algoritmos genéticos en Java Su dirección Web es www.turbopower.com/~ kimk/gpjpp.asp.

•

GP Kernel: Biblioteca de clases para programación genética en C++. Su dirección Web es www.emk.e-technik.th-darmstadt.de/~ thomasw/gp.html.

•

lil-gp: Herramientas para programación genética en C. Su dirección Web es isl.msu.edu/GA/software/lil-gp/index.html, y su dirección para descargarlo vía FTP es isl.cps.msu.edu/pub/GA/lilgp/. Podemos encontrar los parches para Linux en www.cs.umd.edu/users/seanl/patched-gp.

•

PGAPack: Parallel Genetic Algorithm Library. Biblioteca de algoritmos genéticos paralelos. Podemos encontrarlo en la dirección de Internet con un navegador en www.mcs.anl.gov/home/levine/PGAPACK/index.html,

y

su

dirección

para

descargarlo vía FTP es ftp.mcs.anl.gov/pub/pgapack/. •

Sugal: SUnderland Genetic ALgorithm system. Para hacer experimentos con algoritmos genéticos. Podemos encontrarlo en la dirección de Internet con el navegador en www.trajan-software.demon.co.uk/sugal.htm.

•

ADATE: Automatic Design of Algorithms Through Evolution. Programación evolutiva. Su dirección Web es www-ia.hiof.no/~ rolando/adate_intro.html.

•

GPsys: Sistema de programación genética en Java. Podemos encontrarlo en la dirección de Internet www.cs.ucl.ac.uk/staff/A.Qureshi/gpsys.html. En el Anexo 2 de esta monografía, se presenta el código fuente del algoritmo

genético simple, en lenguaje pascal, aplicado a la optimización de las funciones reales de una y dos variables que fueron elegidas para ser estudiadas mediante esta herramienta.

UNIVERSIDAD NACIONAL ABIERTA

24

CAPÍTULO II Métodos clásicos de optimización numérica En el conjunto de métodos clásicos de optimización numérica, existen dos grandes grupos, que lo podemos denominar algoritmos para problemas con restricciones (que requieren los valores de la función objetivo y el conjunto de restricciones) y algoritmos para problemas sin restricciones (que requieren los valores de la función objetivo y los valores de la o las derivadas de la función objetivo); en el primer grupo cabe mencionar el Método Simplex y en el segundo grupo, se ubican el Algoritmo del Gradiente con paso constante y el Algoritmo de Newton con paso constante, éstos, en nuestra opinión, es una buena representación de los métodos de optimización clásicos considerados no heurísticos, debido a que la búsqueda de los puntos óptimos se realiza mediante estrategias que no dependen de eventos aleatorios, lo cual los hace distintos al Algoritmo Genético Simple, en cuanto a sus mecanismos de funcionamiento. Procederemos en las líneas subsiguientes a indicar y a describir brevemente la rutina de los dos métodos antes mencionados, que utilizan los algoritmos para problemas sin restricciones, el cual es el tema que nos ocupa, a fin de tener una panorámica de estas alternativas de optimización numérica para comparar sus resultados con los obtenidos con la aplicación del algoritmo genético simple.

2.1. Algoritmo del gradiente con paso constante Este algoritmo es del tipo:

{

}

Ω = x ∈ IR n / x verifica una condición necesaria de optimalidad , dado

k

x

,

en

la

iteración

k

se

calcula

un

punto

x k +1 = x k + t k d k , donde t k ∈ IR, d k ∈ IR n . Se ha demostrado que si d ∈ IR n , entonces ∇ f (x ), d > 0

UNIVERSIDAD NACIONAL ABIERTA

por

lo

tan to

existe

T > 0 / f (x + td ) > f (x ), 0 < t < T .

25

Visto que el problema matemático consiste en maximizar f(x) para x ∈ IR , con f n

continuamente diferenciable, es natural escoger en cada iteración una dirección

dk

tal

( )

∇f x k , d k > 0 y la manera más sencilla de hacerlo es tomando

que

d k = ∇f (x k ). Los algoritmos del gradiente escogen así dk en cada iteración y por lo tanto difieren entre sí sólo en la manera de determinar el número tk llamado paso, el cual junto con dk define

x k +1 = x k + t k d k .

Para

todos

los

algoritmos

del

gradiente

se

tiene

Ω ={x ∈ IR n / ∇f ( x ) = 0}. Δ

El algoritmo del gradiente con paso constante, es un algoritmo de búsqueda del valor óptimo de una función objetivo, el cual tiene la siguiente estructura: Inicio:

Escoger

x 0 ∈ IR n

tal

que

{

( )}

x0 = x / f ( x ) ≥ f x 0

es

acotado,

β ∈ (0,1) , hacer k=0, ir a la iteración k

Iteración K

paso 1: Calcular

paso 2: Si

∇f (x k )

∇f (x k ) = 0 parar

si no, hacer

(

d k = ∇f (x k ), λ = 1, ir al paso 3

) ( Δ

paso 3: Calcular Δ x , λ = f x + λd

(

k

k

k

) − f (x ) − λ2 k

( )

∇f x k

2

)

paso 4: Si Δ x , λ ≥ 0, hacer t k = λ ir al paso 5 k

si no, hacer

UNIVERSIDAD NACIONAL ABIERTA

λ = βλ

ir al paso 3

26

paso 5: x

k +1

= x k + t k d k , k = k + 1, ir a la iteración k

La siguiente proposición se apoya en un supuesto vital para la operatividad de este algoritmo: Proposición:

Si f es dos veces continuamente diferenciable, si existen M>0, m>0 tales que

− M y ≤ y, H ( x ) y ≤ − m y , 2

2

para todo

y ∈ IR n , para todo x ∈ x0 , donde H es

la matriz hessiana de f, entonces cualquier sucesión infinita generada por el algoritmo a partir

x0

de

converge

( ) ( )

linealmente

( ( ) ( ))

f x − f x ≤q f x − f x , y

*

k

q = 1−

m 2M

k

*

0

hacia

x − x ≤ Cq k

*

un k 2

punto

x*

Ω.

de

Además

1

⎛ Mq ⎞ 2 0 * con C = ⎜ ⎟ x −x ⎝ m ⎠

m⎞ ⎛ ⎜1 + ⎟. ⎝ M⎠

2.1.1. Ejemplo manual del algoritmo del gradiente con paso constante Aplicar el AGPC para obtener algunos términos de la sucesión que converge al valor óptimo de f ( x ) = −

3 x12 x1 x2 x22 + − , con β = 4 2 4 2

y

x 0 = (1,0 ) .

( ) = − 12

Tenemos que f es cóncava y dos veces continuamente diferenciable. Como f x

la curva de nivel

f (x ) = −

1 es una elipse, el conjunto 2

{

0

( )}

X 0 = x / f (x ) ≥ f x 0

convexo y compacto.

1⎤ ⎡ ⎢− 1 4 ⎥ Además H ( x ) = ⎢ ⎥ , los autovalores son -3/4 y -5/4 1 − 1 ⎢ ⎥ ⎣4 ⎦

UNIVERSIDAD NACIONAL ABIERTA

27

y

es

Por lo tanto

de

−

5 2 3 2 y ≤ y, H ( x ) y ≤ − y , se deduce que la sucesión generada a partir 4 4

x 0 = (1,0) converge hacia un punto de Ω .

A continuación se calculan algunos términos de esta sucesión Iteración 0:

⎛ −1 ⎞ ⎛0⎞ ∇f x 0 = ⎜ 1 ⎟ ≠ ⎜⎜ ⎟⎟, d 0 = ∇f x 0 , ⎜ − ⎟ ⎝0⎠ ⎝ 4⎠

( )

λ = 1,

( )

( )

∇f x 0

2

=

( )

17 , 16

f x0 = −

1 2

⎛0⎞ 1 y = x 0 + λd 0 = ⎜ 1 ⎟, f ( y ) = − ⎜ ⎟ 32 ⎝4⎠ 1 1 1 ⎛ 17 ⎞ Δ x 0 ,1 = − + − ⎜ ⎟ < 0 32 2 2 ⎝ 16 ⎠

( )

λ = βλ =

3 , 4

⎛1⎞ ⎜ ⎟ y = x 0 + λd 0 = ⎜ 4 ⎟, ⎜⎜ 3 ⎟⎟ ⎝ 16 ⎠

f ( y ) # 0,037

3⎞ ⎛ Δ⎜ x 0 , ⎟ # 0,065, 4⎠ ⎝

⎛1⎞ ⎜ ⎟ 3 x1 = x 0 + d 0 = ⎜ 4 ⎟ 4 ⎜⎜ 3 ⎟⎟ ⎝ 16 ⎠

Iteración 1:

⎛ 13 ⎞ ⎜ − ⎟ ⎛ 0⎞ 1 ∇f (x ) = ⎜ 64 ⎟ ≠ ⎜⎜ ⎟⎟, d 1 = ∇f (x1 ), ⎜⎜ − 1 ⎟⎟ ⎝ 0 ⎠ ⎝ 8 ⎠ λ = 1,

⎛ 0,047 ⎞ ⎟⎟, y = x1 + λd 1 # ⎜⎜ ⎝ 0,063 ⎠ Δ x1 ,1 # 0,0065

∇f (x1 ) = 0,057 , 2

f (x 0 ) = −

f ( y ) # − 0,002

( )

⎛ 0,047 ⎞ ⎟⎟ x 2 = x1 + d 1 # ⎜⎜ ⎝ 0,063 ⎠ Iteración 2:

UNIVERSIDAD NACIONAL ABIERTA

28

1 2

⎛ − 0,031⎞ ⎛ 0 ⎞ ⎟⎟ ≠ ⎜⎜ ⎟⎟, d 2 = ∇f (x 2 ), ∇f (x 2 ) # ⎜⎜ ⎝ − 0,051⎠ ⎝ 0 ⎠ ⎛ 0,016 ⎞

f (x 2 ) # − 0,002

2

f ( y ) # − 0,00015

⎟⎟ , λ = 1 y = x 2 + d 2 # ⎜⎜ ⎝ 0,012 ⎠

(

∇f (x 2 ) # 0,004 ,

)

Δ x 2 , 1 # − 0,00015 ⎛ 0,024 ⎞ ⎟⎟ , y = x 2 + λd 2 # ⎜⎜ ⎝ 0,025 ⎠

λ ¨= βλ

3⎞ ⎛ Δ⎜ x 2 , ⎟ # 0, 4⎠ ⎝

x3 = x 2 +

La solución es x = (0,

3 2 ⎛ 0,024 ⎞ ⎟⎟ d # ⎜⎜ 4 ⎝ 0,025 ⎠

( )

0 ),

*

f ( y ) # − 0,0005

f x * = 0 . Aunque la sucesión converge rápidamente, se

observa una gran influencia de los errores de redondeo cerca de la solución en la determinación de Δ( x, λ ) .

2.2. Algoritmo de Newton con paso constante Los algoritmos del gradiente consideran la aproximación lineal de la función objetivo para determinar la dirección de desplazamiento. Sin embargo, si estamos cerca del punto solución, es decir si ∇f ( x ) es pequeño o bien si f es estrictamente cóncava, una aproximación cuadrática F(x) en torno a xk representa mejor el comportamiento de f, donde:

( )

( )(

)

F ( x ) = f x k + ∇f x k , x − x k +

( )(

)

1 x − x k , H x k x − x k , siendo H la matriz hessiana 2

de f. Si f es estrictamente cóncava, F lo es también y alcanza su máximo en el punto x tal que

( )

( )(

)

∇f x k + H x k x − x k = 0, o

( )

H xk

sea

es regular ,

( ) ( )

x − x k = − H x k ∇f x k

Por lo tanto en todo punto xk donde H(xk) es definida negativa, un desplazamiento a Δ

partir de xk en la dirección d = − H k

( )

que ∇f x , d k

k

−1

(x )∇f (x ) producirá un crecimiento del valor de f ya k

k

( )

= − H xk d k , d k > 0

UNIVERSIDAD NACIONAL ABIERTA

29

Esta manera de determinar dk caracteriza los algoritmos de Newton, los cuales en cada iteración calculan xk+1 a partir de xk mediante

( ) ( )

Δ

x k +1 = x k + t k d k , con d k =− H −1 x k ∇f x k y sólo difieren entre sí en el método de escoger el paso tk. Para todos los algoritmos de Newton, tenemos:

Ω = {x ∈ IR n / ∇f ( x ) = 0},.bajo el supuesto

que f es al menos dos veces continuamente diferenciable y su matriz hessiana regular. El algoritmo de Newton con paso constante se escribe así:

Inicio:

⎛ ⎝

1⎞ 2⎠

α ∈ ⎜ 0, ⎟, β ∈ (0,1) (es conveniente tomar

x 0 ∈ IR n

Escoger

β ∈ (0,5 , 0,8) , hacer k=0, ir a la iteración k

Iteración K

paso 1: Calcular ∇f

paso 2: Si ∇f

k

paso 3: Calcular Δ

si no, hacer

paso 5

k

(x ) = 0 parar

si no, hacer

paso 4: Si Δ

(x )

d k = − H −1 (x k )∇f (x k ) , hacer λ = 1 , ir al paso 3

(x , λ )= f (x k

(x , λ ) ≥ 0, k

Δ

k

) ( )

( )

+ λd k − f x k − λα ∇f x k , d k ,

hacer t k = λ , ir al paso 5

λ = λβ , ir al paso 3

x k +1 = x k + t k d k , k=k+1 ir a la iteración k

UNIVERSIDAD NACIONAL ABIERTA

30

2.2.1. Ejemplo manual del algoritmo de Newton con paso constante Aplicar el ANPC para obtener algunos términos de la sucesión que converge al valor óptimo

de

f (x ) = −

x12 x1 x2 x22 + − , con β = 0,7 2 4 2

y α = 0,4 .

1⎤ ⎡ ⎢− 1 4 ⎥ En el ejemplo anterior vimos que H ( x ) = ⎢ ⎥ , tiene por autovalores -3/4 y 1 − 1⎥ ⎢ ⎣4 ⎦

x 0 = (1,0) converge.

-5/4, por lo que sucesión generada por el algoritmo a partir de

Iteración 0:

⎛ − 1⎞ ⎛ 0 ⎞ ⎛1⎞ x 0 = ⎜⎜ ⎟⎟, ∇f x 0 = ⎜ 1 ⎟ ≠ ⎜⎜ ⎟⎟, ⎜ ⎟ ⎝ 0⎠ ⎝ 0⎠ ⎝4⎠

( )

⎛ − 1⎞ d 0 = − H −1 (x 0 )∇f (x 0 ) = ⎜⎜ ⎟⎟, ⎝0⎠

λ = 1,

⎛0⎞ y = x 0 + λd 0 = ⎜⎜ ⎟⎟, ⎝0⎠

( )

( )

1 f (x 0 ) = − , 2

⎡ ⎢ −1 x0 = ⎢ 1 ⎢− ⎣ 4

H −1 (

)

1⎤ − ⎥ 4 ⎥ −1⎥ ⎦

( )

∇f x 0 , d 0 = 1

f (y) = 0

( )

Δ x 0 ,1 = f ( y ) − f x 0 − 0,4 ∇f x 0 , d 0 = 0,1 > 0 Por lo tanto

Iteración 1:

⎛ 0⎞ x1 = x 0 + d 0 = ⎜⎜ ⎟⎟ ⎝ 0⎠ ⎛0⎞ ⎛ 0⎞ x1 = ⎜⎜ ⎟⎟, ∇f (x1 ) = ⎜⎜ ⎟⎟, parar. ⎝0⎠ ⎝ 0⎠

UNIVERSIDAD NACIONAL ABIERTA

31

CAPÍTULO III Ensayos de aplicación del algoritmo genético simple y de los métodos clásicos en la optimización numérica y = x 2 sen 2 (10πx) + 1 ,

En este capítulo vamos a maximizar la función

dominio [0, 2] y minimizar la función Z = 0,5 +

sen 2

(

)

x 2 + y 2 − 0,5

(1 + 0,001(x

2

+ y2

))

2

en el

, en el dominio

[-200, 200] X [-200, 200] mediante el algoritmo genético simple, implementado en lenguaje pascal a fin de comentar los resultados obtenidos.

3.1. Evaluación de la función Y = x 2 sen 2 (10πx) + 1 en el dominio [0,2] Iniciaremos el ensayo mencionando algunas características de esta función, cuyo gráfico se muestra en la figura N° 1 que sigue:

y

5 4.5 4 3.5 3 2.5 2 1.5 1 0.5 0

0

0.5

1

1.5

2 x

figura N° 1 gráfica de la función Y = x 2 sen 2 (10πx) + 1

Como se observa, esta función en el dominio de definición, tiene una oscilación moderada con tendencia al aumento y manifiesta un incremento de su amplitud directamente proporcional al incremento de la variable independiente. El máximo global se ubica muy cerca de x = 2 y registra varios máximos locales, que se resaltan a partir de x = 1.

UNIVERSIDAD NACIONAL ABIERTA

32

En el Anexo 3 de este trabajo se detallan las herramientas computacionales utilizadas para el desarrollo de este aparte y de otros donde se hizo necesario el uso de las mismas.

3.1.1. Aplicación del algoritmo genético simple Los parámetros para la corrida de la función que se intenta optimizar mediante el algoritmo genético simple son los que se detallan a continuación: Tamaño del cromosoma: 15

Tamaño de la población: 100

Número de generaciones: 200

Probabilidad de cruce: 0,85

Probabilidad de mutación: 0,013. El tamaño del cromosoma igual 15, significa que los valores de la variable x se codificaron con 15 bits cada uno, resultando que los individuos se representan mediante ristras de 0’s y 1’s de tamaño 15. El tamaño de la población igual 100, significa que para cada una de las 200 generaciones estarán formadas por 100 individuos. Pc = 0,85; quiere decir que en cada generación se modificará probablemente el 85% de la población y en todos los cruces que se aplican, los hijos sustituirán a los padres independientemente de que la aptitud de éstos sea peor que la de los padres. Pm = 0,013, significa que el 10% de la población y el 0,13% de los genes es probable que sean sometidos a mutación, por lo que en este caso como tenemos 100 individuos cada uno codificado con 15 genes se espera que aproximadamente 19 genes sean mutados por cada generación y así los individuos mutados sustituirán a los iniciales independientemente de su aptitud. La tabla N° 1 que se presenta a continuación, contiene un resumen de los resultados empíricos, de los datos que consideramos relevantes, obtenidos mediante la corrida del programa del algoritmo genético simple, con las características paramétricas mencionadas anteriormente, que se encuentra en el Anexo 2 de este trabajo.

UNIVERSIDAD NACIONAL ABIERTA

33

En la misma se observa que una vez realizadas 200 generaciones, el algoritmo genético encontró el valor máximo de la función en estudio que resultó ser igual a 4,8035, el cual se alcanza en el valor de la variable x igual a 1,9504379406.

UNIVERSIDAD NACIONAL ABIERTA

34

Tabla N° 1 Resumen de resultados empíricos

Función de Aptitud Valor de X

Máximo Mínimo Promedio

Número Suma

Mutaciones

Cruces

Generaciones

1,8289132361 3,0797 1,0050

1,5705

157,0515

17

43

1

1,9411603100 4,7886 1,0000

1,6305

163,0526

31

86

2

1,9500106815 4,8025 1,0000

2,0026

200,2616

45

128

3

1,9500106815 4,8025 1,0020

2,2726

227,2647

59

172

4

1,9494613483 4,7993 1,0007

2,7030

270,3016

76

216

5

1,9498275704 4,8017

1,0042

2,8430

284,2982

97

258

6

1,9498215702 4,8016

1,0006

3,2116

321,1613

116

298

7

1,9500106815 4,8025

1,0010

3,4588

345,8796

127

340

8

1,9506177701 4,8028

1,0012

3,7419

374,1892

141

385

9

1,9506177701 4,8028 1,0005

3,9620

396,2000

160

428

10

1,9506177701 4,8028

1,0010

3,9602

396,0231

175

474

11

1,9506177701 4,8028

1,0123

4,1118

411,1769

198

518

12

1,9501937925 4,8031

1,0185

4,1554

415,5434

217

559

13

1,9498275704 4,8017

1,0089

4,1857

418,5693

232

607

14

1,9498275704 4,8017

1,0002

4,1899

418,9862

251

649

15

1,9500106815 4,8025

1,0191

4,1718

417,1812

271

695

16

1,9501937925 4,8031

1,0041

4,2386

423,8643

290

735

17

1,9508651900 4,8032 1,0024

4,2333

423,3294

304

784

18

1,9508651900 4,8032

4,3154

431,5449

325

828

19

1,0018

1,9501937925 4,8031

1,0018

4,3134

431,3423

343

872

20

1,9501937925 4,8031

1,0605

4,3905

439,0480

356

914

21

1,9501937925 4,8031

1,0011

4,4666

446,6635

378

958

22

1,9501327555 4,8030

1,3814

4,2848

428,4767

397

1.003

23

1,9506177701 4,8028

1,0126

4,1757

417,5684

416

1.040

24

1,9506177701 4,8028

1,1804

4,3564

435,6425

429

1.084

25

1,9501937925 4,8031

1,1225

4,3614

436,1446

446

1.131

26

1,9501937925 4,8031

1,0020

4,2147

421,4660

469

1.174

27 28

1,9507431257 4,8033 1,0036

4,2421

424,2080

485

1.218

1,9504379406 4,8035 1,0045

4,1769

417,6861

505

1.264

29

1,9505600146 4,8035 1,0000

4,2572

425,7215

533

1.310

30

1,9505600146 4,8035 1,0084

4,3004

430,0397

555

1.352

31

1,9505600146 4,8035

4,3781

437,8083

577

1.393

32

1,9505600146 4,8035 1,0337

4,3390

433,9004

597

1.436

33

1,9506179856 4,8029

1,0001

4,3258

432,5818

626

1.478

34

1,0916

1,9506177701 4,8028 1,0000

4,0788

407,8834

655

1.518

35

1,9507431257 4,8033

1,0101

4,2195

421,9456

672

1.558

36

1,9507431257 4,8033

1,0101

4,3783

437,8302

690

1.600

37

Continuación de Tabla N° 1 Resumen de resultados empíricos

UNIVERSIDAD NACIONAL ABIERTA

35

Función de Aptitud Valor de X

Máximo Mínimo Promedio

Número Suma

Mutaciones

Cruces

Generaciones

1,9507431257 4,8033 1,0043

4,4152

441,5206

708

1.642

38

1,9507431257 4,8033 1,6957

4,4755

447,5470

731

1.684

39

1,9507431257 4,8033 1,1278

4,4546

445,4580

749

1.725

40

1,9507431257 4,8033 1,0738

4,3399

433,9920

769

1.763

41

1,9509261310 4,8027 1,0129

4,3800

438,0019

780

1.799

42

1,9500106815 4,8025

1,1193

4,3345

433,4524

797

1.839

43

1,9509261310 4,8027 1,0408

4,3470

434,6953

825

1.883

44

1,9509261310 4,8027 1,0013

4,3734

437,3395

846

1.923

45

1,9508651900 4,8032 1,0005

4,2481

424,8061

869

1.967

46

1,9507431257 4,8033 1,0001

4,1711

417,1129

884

2.005

47

1,9501937925 4,8031 1,0000

4,2156

421,5561

896

2.049

48

1,9506177701 4,8028 1,1034

4,4398

443,9789

919

2.089

49

1,9506177701 4,8028 1,2007

4,4719

447,1919

934

2.131

50

1,9506177701 4,8028 1,0096

4,3980

439,7984

956

2.176

51

1,9506177701 4,8028

4,3682

436,8249

973

2.219

52

1,0115

1,9507431257 4,8033 1,0047

4,2965

429,6507

991

2.260

53

1,9506177701 4,8028 1,0002

4,4256

442,5634

1.004

2.307

54

1,9506177701 4,8028 1,2636

4,4005

440,0500

1.034

2.349

55

1,9507431257 4,8033 1,0005

4,4866

448,6561

1.057

2.389

56

1,9506177701 4,8028 1,0120

4,2150

421,5034

1.068

2.433

57

1,9507431257 4,8033 1,0000

4,0684

406,8424

1.093

2.476

58

1,9507431257 4,8033 1,0000

4,2469

424,6913

1.113

2.517

59

1,9507431257 4,8033 1,0001

4,0269

402,6906

1.140

2.559

60

1,9507431257 4,8033 1,0001

4,1717

417,1681

1.157

2.600

61

1,9507431257 4,8033 1,0015

4,2964

429,6375

1.168

2.642

62

1,9507431257 4,8033 1,0015

4,2806

428,0582

1.182

2.689

63

1,9503158660 4,8034 1,4975

4,4106

441,0584

1.198

2.730

64

1,9506820887 4,8034 1,3398

4,3082

430,8227

1.219

2.770

65

1,9506820887 4,8034 1,0005

4,4545

445,4484

1.236

2.811

66

1,9506820887 4,8034 1,0013

4,4024

440,2356

1.259

2.851

67

1,9506820887 4,8034 1,0000

4,3572

433,7153

1.278

2.890

68

1,9506820887 4,8034 1,0000

4,2844

428,4440

1.292

2.935

69

1,9506820887 4,8034 1,0080

4,2389

423,8881

1.305

2.975

70

1,9506820887 4,8034 1,0015

4,5238

452,3835

1.331

3.015

71

1,9506820887 4,8034 1,0000

4,3515

435,1515

1.347

3.054

72

1,9504379406 4,8035 1,0120

4,1643

416,4337

1.370

3.098

73

1,9506820887 4,8034 1,0050 4,4866 448,6623 1,9504379406 4,8035 1,0115 4,4545 445,4520

1.389 3.757

3.138 8.430

74 200

Número promedio de cruces por generación: 42 Número promedio de mutaciones por generación: 19

Las gráficas que se observan a continuación, muestran los resultados empíricos de la población en función al número de generaciones, obtenidos en 74 simulaciones, con las características paramétricas mencionadas anteriormente.

UNIVERSIDAD NACIONAL ABIERTA

36

6

Valores Aptitud

5 4 3 2 1 0 0

10

20

30

40

50

60

70

80

Número de Generaciones

Máximo

Mínimo

Promedio

figura N° 2 Valores regulares de la función para distintas generaciones

Los resultados de los máximos y los mínimos de la función de aptitud (colores verde y azul en la figura N° 2), reflejan mucha estabilidad en la medida que avanzan las generaciones. Ahora bien, el valor promedio de la función aptitud (color naranja en la figura N° 2) muestra cierta variabilidad con tendencia hacia el valor máximo, esto confirma la teoría en cuanto a que las generaciones resultantes tienden, en promedio, a ser más aptas que sus ascendientes. Las dos gráficas (figuras N° 3 y 4) que siguen, muestran elocuentemente la relación directamente proporcional existente entre número de mutaciones, el número de cruces y la estabilización de la función de aptitud acumulada con respecto al número de generaciones producidas en los ensayos.

UNIVERSIDAD NACIONAL ABIERTA

37

3.500 Número de Casos

3.000 2.500 2.000 1.500 1.000 500 0 0

10

20

30

40

50

60

70

80

Número de Generaciones

Mutaciones

Cruces

figura N° 3 Número de mutaciones y cruces para distintas generaciones

Función de aptitud acumulada por cada generación 500 400 300 200 100 0 0

10

20

30

40

50

60

70

80

Número de Generaciones

figura N° 4 Función de aptitud acumulada distintas generaciones

La gráfica (figura N° 5) subsiguiente muestra las posiciones de los valores máximo, mínimo y promedio de la función de aptitud para la distribución inicial de la población.

UNIVERSIDAD NACIONAL ABIERTA

38

y

5 4.5 4 3.5

Máximo

3 2.5

Promedio

2 1.5

Mínimo

1 0.5 0

0

0.5

1

1.5

2 x

figura N° 5 Valores regulares de la función en la población inicial

La figura N° 6 muestra las posiciones de los valores máximo, mínimo y promedio de la función de aptitud para la distribución final de la población después de 200 generaciones, observándose que la línea de posición del valor máximo y mínimo coinciden con el valor máximo y mínimo de la función en estudio.

y

Máximo

5 4.5

Promedio

4 3.5 3 2.5 2 1.5

Mínimo

1 0.5 0

0

0.5

1

1.5

2 x

figura N° 6 Valores regulares de la función en la población final

3.1.2. Aplicación de los métodos clásicos de optimización numérica Se

realizaron

pruebas

(cambiando

el

punto

inicial)

sobre

la

función

y = x 2 sen 2 (10πx) + 1 dirigidas a obtener resultados respecto a la ubicación del máximo global con el software matemático “Maple 8”, consiguiéndose como conducta modal que el mismo detiene la búsqueda, en todo caso, en el primer máximo local que halla después del

UNIVERSIDAD NACIONAL ABIERTA

39

punto inicial y declara tal resultado como el valor máximo global de la función; produciendo así una solución aproximada con un inmenso error.

3.2. Evaluación de la función Z = 0,5 +

sen 2

(

)

x 2 + y 2 − 0,5

(1 + 0,001(x

2

+ y2

))

2

,

en el

dominio [-200, 200] X [-200, 200] Continuando con el proceso de evaluación, la figura N° 7 ilustra la inversa de la función que antecede en el dominio [-10, 10] X [-10, 10], debido a que para el dominio

62.5 z 50 37.5 25 12.5 -10

-5

0

5

10

0 -5 -10

5

10

y

x

figura N° 7 gráfica de la función

Z = 0,5 +

⎞ ⎛ sen 2 ⎜ x 2 + y 2 ⎟ − 0,5 ⎠ ⎝

(1 + 0,001(x

2

+ y2

))

en el domino [-10, 10] X [-10, 10]

2

completo de definición, la función inversa no presenta valores máximos relevantes.

UNIVERSIDAD NACIONAL ABIERTA

40

Como se observa, esta función tiene dos máximos globales en el entorno (-5, 5) X (0, 2,5) y múltiples máximos locales.

100

75

z

50 25 -5 -2.5 0 2.5

0 y

figura N° 7 gráfica de la función

2.5 5

Z = 0,5 +

x

⎞ ⎛ sen 2 ⎜ x 2 + y 2 ⎟ − 0,5 ⎠ ⎝

(1 + 0,001(x

2

+ y2

))

en el domino [-5, 5] X [0, 2,5]

2

3.2.1. Aplicación del algoritmo genético simple Los parámetros para la corrida de la función que se intenta optimizar mediante el algoritmo genético simple son los que se detallan a continuación: Tamaño del cromosoma: 30

Tamaño de la población: 100

Número de generaciones: 200

Probabilidad de cruce: 0,85

Probabilidad de mutación: 0,013. El tamaño del cromosoma igual 30, significa que los valores de las variables x, y se codificaron con 15 bits cada uno, resultando que los individuos se representan mediante ristras de 0’s y 1’s de tamaño 30. Los primeros quince, de izquierda a derecha corresponden a la variable y; las quince posiciones restantes corresponden a la variable x. Los datos que consideramos relevantes, obtenidos mediante la corrida del programa del algoritmo genético simple, con las características paramétricas mencionadas

UNIVERSIDAD NACIONAL ABIERTA

41

anteriormente, el cual se encuentra en el Anexo 2 de esta monografía, refuerzan las conclusiones obtenidas en el caso de la función de una variable. Una vez realizadas las 200 generaciones consideradas, el algoritmo genético encontró dos valores que podemos considerar una buena aproximación a los máximos de la función en estudio que resultaron: 102,9237, el cual se alcanza en el punto (2,7039399396, 1,5930661948) y 102,8904, el cual se alcanza en el punto (-0,81179235200, -3,0335398419).

3.2.2. Aplicación de los métodos clásicos de optimización numérica Los resultados generados, utilizando el mismo software matemático aplicado en el aparte 3.1.2., productos de la evaluación de la función Z = 0,5 +

sen

2

(

)

x 2 + y 2 − 0,5

(1 + 0,001 (x

2

+ y2

))

2

análogos a los arrojados en el aludido aparte.

UNIVERSIDAD NACIONAL ABIERTA

42

son

CAPÍTULO IV Posibles modificaciones al algoritmo genético simple y conclusiones Como se evidenció en el ejemplo manual del capítulo I de esta monografía, el algoritmo genético simple al finalizar la quinta generación, produjo como resultado para el máximo de la función en el intervalo estudiado un valor igual a 676 (siendo su máximo verdadero igual a 961); este escenario comprobó que el mencionado algoritmo no es la panacea ante el problema de optimización, marcando la necesidad de seguir iterando, todo basado en el hecho, siempre imposible, de que se conoce el valor máximo de la función. He aquí un importante problema real de este algoritmo, como lo es la tendencia a la homegeinización de la población, es decir a que todos los individuos de la misma sean idénticos, impidiendo que el algoritmo siga explorando nuevas soluciones con lo que, probablemente, se quede estancado en un máximo local no muy bueno, este evento suele denominarse convergencia prematura en contraposición a la convergencia lenta que en muchos casos se produce. Otro conflicto en el comportamiento del algoritmo genético puede ser la existencia de muchos óptimos locales, además el hecho de que el óptimo global se encuentre muy aislado. Existen muchas técnicas para contrarrestar tales situaciones. Los mecanismos que únicamente mencionaremos en este capítulo tienen que ver con las modificaciones realizadas sobre los operadores genéticos.

4.1

Modificaciones sobre los operadores genéticos Las modificaciones del algoritmo genético simple, en cuanto a sus operadores

genéticos, serán capaces de producir una versión mejorada del mismo, que no es ni se pretende que sea una solución definitiva al problema mencionado. La investigación en el campo de los algoritmos genéticos está centrada en la búsqueda de un algoritmo robusto, eficaz y rápido. En tiempos recientes, se han utilizado

UNIVERSIDAD NACIONAL ABIERTA

43

diferentes parámetros para ensayos prácticos sobre un mismo problema, así mismo se han desarrollado nuevas representaciones para los operadores de selección, cruce y mutación a fin de aumentar la velocidad de los algoritmos genéticos; ya que empíricamente se ha comprobado que la modificación de los parámetros y operadores que los definen pueden impactar vigorosamente sobre el funcionamiento de dicho algoritmo.

4.1.1. Selección (Elitismo) Como antes se ha dicho, para el algoritmo genético simple la selección de mayor popularidad es la selección proporcional a la aptitud equivalente a la selección por rueda de

ruleta, siendo la probabilidad de seleccionar a un individuo

Pi sel =

Fi

, donde:

Np

∑F j =1

j

Fi : es el valor de la función de aptitud del individuo i-ésimo. N p : es el número de individuos de la población y se conoce como el tamaño de la población. Esta manera de escoger como padre a los individuos de la población presenta el inconveniente de la rápida convergencia provocada por los superindividuos. 5 El problema anterior se puede resolver efectuando una selección proporcional al rango del individuo, lo cual produce una repartición más uniforme en la escogencia.

Pi rango =

rango( Fi ) λ (λ + 1) / 2

, donde

λ

es el rango de la función objetivo del mejor individuo.

Existe un modelo de selección elitista donde se obliga a que el mejor individuo de la población anterior sea seleccionado para pasar a la población siguiente. Entre la gran variedad de métodos de refinamiento del modelo de selección proporcional, cabe mencionar al modelo del selección del valor esperado, el esquema de selección que ha proporcionado empíricamente buenos resultados es el muestreo estocástico con reemplazamiento del resto, introducido por Brindle (1991), otros

5

Estos son individuos con valores relativamente elevados en la función de aptitud.

UNIVERSIDAD NACIONAL ABIERTA

44

procedimientos

de

selección

consiste

en

métodos

de

selección

dinámicos

(las

probabilidades de selección varían en cada generación).

4.1.2. Cruce (Varios tipos) En el algoritmo genético simple los individuos seleccionados para desempeñar el papel de padres son recombinados utilizando el cruce basado en un punto. De Jong (1975) ha realizado experimentos con operador de cruce basado en múltiples puntos y ha concluido empíricamente que el cruce basado en dos puntos produce mejoras importantes al algoritmo. Existen otros operadores de cruce son: a) Operador de cruce uniforme, b) Operador de cruce basado en la función objetivo, c) Operador de cruce en el sentido del simulated annealing, etc.

4.1.1. Mutación Este operador es considerado de importancia capital debido a que permite al algoritmo genético explorar sobre todo el espacio de búsqueda. En la mayoría de las implementaciones del algoritmo genético simple la probabilidad de mutación permanece constante en todas las generaciones. La búsqueda del valor óptimo de la mencionada probabilidad ha motivado el desarrollo de muchos trabajos de investigación. Experimentalmente, modificando la probabilidad de mutación se han logrado mejorar los resultados del algoritmo genético simple. Adicionalmente, en algunos casos se ha ensayado con algoritmos genéticos que modifican dinámicamente la probabilidad de mutación (y de cruce).

4.2

Conclusiones

1.

El desarrollo de las pruebas experimentales realizadas en esta monografía, sobre las dos funciones reales elegidas para ser evaluadas mediante el algoritmo genético simple, y la comparación con los resultados que arrojaron los métodos tradicionales de optimización numérica, permitió exponer la potencialidad del algoritmo genético

UNIVERSIDAD NACIONAL ABIERTA

45

simple en un escenario donde las funciones presentan en su dominio de definición: oscilaciones moderadas y la existencia de varios máximos locales. 2.

El campo de aplicación de esta herramienta se encuentra en el conjunto de las funciones para las cuales las técnicas tradicionales especializadas no funcionan o no aplican.

3.

La utilidad del algoritmo genético simple, en el tema de la optimización y búsqueda de elementos relevantes en la ciencia moderna aún está en fase experimental y no se ha logrado todavía definir las características paramétricas (tamaño de la población, método de selección, probabilidad de cruce y de mutación, número de generaciones,

tamaño

del

cromosoma,

etc.)

que

garanticen

resultados

verdaderamente fiables en todos los contextos de aplicación. 4.

Los resultados de esta monografía, producto de numerosas horas de investigación teórica y empírica, corroboran la utilidad de la técnica denominada algoritmo genético simple, estimulando un enorme interés en la investigación y estudio este tipo de herramienta.

5.

A nivel mundial, se vienen realizando importantes desarrollos referidos a la aplicación del algoritmo genético simple en el campo de las matemáticas y la algoritmia. En el ámbito de nuestra Universidad Nacional Abierta (UNA) no existen proyectos de investigación y desarrollo para estas novedosas y prometedoras tecnologías.

6.

Esta breve exposición, servirá de instrumento para divulgar ciertos aspectos de interés sobre el apasionante y productivo tema de la aplicación del algoritmo genético simple en la optimización de funciones reales y estimulará a los estudiantes de

las

carreras

de

Matemática,

Ingeniería,

Administración

y

Educación,

pertenecientes a la comunidad educativa de la UNA, a participar en su necesario e imperioso desarrollo utilizando como plataforma inicial los resultados y conclusiones obtenidos en este trabajo.

UNIVERSIDAD NACIONAL ABIERTA

46

ANEXO 1 Artículo de prensa publicado en el cuerpo 48 del Universal, el 09/04/2006 CIENCIA // El estudio fue publicado en la revista "Science" Demuestran teoría de Darwin a escala molecular Científicos mostraron etapa por etapa el proceso de selección natural Washington.

Puede

resultar a estas alturas obvio, pero no lo es. Así, un grupo

Las Islas Galápagos fueron un reservorio inspirador para Darwin

de científicos mostró por primera vez, etapa por etapa, el proceso por el cual la naturaleza crea una nueva pieza de mecánica molecular modificando los elementos ya existentes, en un estudio publicado el pasado viernes en la revista estadounidense Science que confirma la teoría de la evolución de Charles Darwin.

"Descubrimos que la complejidad molecular evoluciona por transformación, por medio de un proceso de explotación molecular que permite que viejos genes, obligados por la selección a funciones completamente diferentes, a ser reciclados para nuevas funciones", afirmó Joe Thornton, biólogo y principal autor del estudio, reseña AFP.

UNIVERSIDAD NACIONAL ABIERTA

47

"Nuevas técnicas nos permiten ver cómo viejos genes, hoy desaparecidos, evolucionaron hace cientos de millones de años", explicó Thornton, científico de la Universidad de Oregon (noroeste).

"El proceso de evolución de la mecánica molecular por etapa que reconstruimos se conforma completamente a la teoría de Darwin", destacó.

Cambio revolucionario La teoría de Darwin, sobre el origen de las especies, habla sobre el proceso de selección natural y del azar que a partir de la ausencia de recursos para su supervivencia se ven en la obligación de desarrollar habilidades, características o en todo caso variaciones que posteriormente incorporarán las siguientes generaciones, que a su vez seguirán incorporando las variantes necesarias para su subsistencia. Por supuesto, esto no es más que el principio de lo que significó el amplio desarrollo teórico del revolucionario naturalista británico.

La teoría evolucionista de Darwin no tardó en generar severas críticas, no sólo por parte de sus contemporáneos que la pusieron en el banquillo e intentaron resistirse a ella por años. Aún en la actualidad, instituciones de carácter religioso se oponen drásticamente a que se imparta en ciertos colegios. En Estados Unidos, recientemente se libró una batalla legal que ha terminado favoreciendo los conceptos e ideas del científico británico.

Genio observador

UNIVERSIDAD NACIONAL ABIERTA

48

⇒ Nació

en

Inglaterra,

Shrewshury, en

1809.

Fue

Shropshire, el

quinto

descendiente de una familia acomodada.

⇒ Con

credenciales para estudiar Medicina y

posteriormente

hacerse

ministro

de

la

Iglesia, Darwin se relacionó con Adam Sedwick

y

John

Stevens,

geólogo

y

Charles Darwin

naturista, respectivamente, quienes le orientaron finalmente a su profesión definitiva.

⇒ Como naturalista, Darwin tuvo su primera gran oportunidad en 1831 al embarcarse en el "HMS Beagle". A los 22 años, el futuro científico tuvo su contacto con el resto del mundo.

⇒ Tras

su regreso, Darwin inició lo que se conocería como "El origen de las especies". Fue un libro

revolucionario, dado que echaba por tierra la clásica teoría de la catástrofe para profundizar en la capacidad de las diversas especies para evolucionar. Se editó en 1859.

UNIVERSIDAD NACIONAL ABIERTA

49

ANEXO 2 Código fuente del algoritmo genético simple Código fuente del algoritmo genético, en lenguaje pascal, aplicado a la optimización de funciones reales, tomado del libro. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Publishing Company, Inc., Readind, MA. de Goldberg, D. E. (1989). Sobre el código fuente original, se efectuaron las modificaciones que se indican, a fin de ajustarlo al contexto de nuestra monografía: a) Las salidas y las declaraciones del programa se tradujeron al idioma castellano, b) La función objetivo y el coeficiente de normalización se ajustaron de acuerdo a los requerimientos del caso que nos ocupa, c) El programa denominado sga2 es una adaptación de los códigos para funciones de dos variables.

A.2.1. Para funciones reales de una variable program sga1; uses crt; const maxpop = 100; maxstring = 30; coef = 16383.5; type allele = boolean; chromosome = array [1..maxstring] of allele; individual = record chrom: chromosome; x: real; fitness: real; parent1, parent2, xsite: integer; end; population = array [1..maxpop] of individual; var oldpop,newpop: population; popsize, lchrom, gen, maxgen: integer; pcross, pmutation, sumfitness: real; nmutation, ncross: integer; avg, max, min: real; (******************************************************************) function power(x:real):real; begin power:= sqr(x)*sqr(sin(10*pi*x))+1; end;

UNIVERSIDAD NACIONAL ABIERTA

50

function rand: real; begin rand:= random(23767)/23767.0; end; function flip(probability: real): boolean; begin if probability = 1.0 then flip:= true else flip:= (rand max then max:= fitness; if fitness= rand) or (j = popsize); select:= j; end;

UNIVERSIDAD NACIONAL ABIERTA

53

function mutation(alleleval: allele): allele; var mutate: boolean; begin mutate:= flip(pmutation); if mutate then begin nmutation:= nmutation + 1; mutation:= not alleleval; end else mutation:= alleleval; end; procedure crossover(parent1, parent2: chromosome; var child1, child2: chromosome; var jcross: integer); var j: integer; begin if flip(pcross) then begin jcross:= rnd(1,lchrom-1); ncross:= ncross + 1; end else jcross:= lchrom; for j:= 1 to jcross do begin child1[j]:= mutation(parent1[j]); child2[j]:= mutation(parent2[j]); end; if jcross lchrom then begin for j:= jcross+1 to lchrom do begin child1[j]:= mutation(parent2[j]); child2[j]:= mutation(parent1[j]); end; end; end; procedure generation; var j, mate1, mate2, jcross: integer; begin j:= 1; repeat mate1:= select; mate2:= select; crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j].chrom, newpop[j+1].chrom,jcross); with newpop[j] do begin x:= decode(chrom,lchrom); fitness:= objfunc(x); parent1:= mate1; parent2:= mate2; xsite:= jcross; end; with newpop[j+1] do begin x:= decode(chrom,lchrom); fitness:= objfunc(x); parent1:= mate1; parent2:= mate2; xsite:= jcross; end;

UNIVERSIDAD NACIONAL ABIERTA

54

j:= j + 2; until j>=popsize; end; begin gen:= 0; initialize; repeat gen:= gen + 1; generation; statistics(newpop); report; oldpop:= newpop; until (gen>= maxgen); end.

UNIVERSIDAD NACIONAL ABIERTA

55

A.2.2. Para funciones reales de dos variables program sga2; uses crt; const maxpop = 100; maxstring = 30; type allele = boolean; chromosome = array [1..maxstring] of allele; individual = record chrom: chromosome; x: real;y:real; fitness: real; parent1, parent2, xsite, ysite:integer; end; population = array [1..maxpop] of individual; var oldpop,newpop: population; popsize, lchrom, gen, maxgen: integer; pcross, pmutation, sumfitness: real; nmutation, ncross: integer; avg, max, min: real; (******************************************************************) function power(x, y:real):real; begin power:= 1/(0.5+(sqr(sin(sqrt(sqr(x)+sqr(y))))-0.5)/sqr(1+0.001*(sqr(x)+sqr(y)))); end; function rand: real; begin rand:= random(23767)/23767.0; end; function flip(probability: real): boolean; begin if probability = 1.0 then flip:= true else flip:= (rand max then max:= fitness; if fitness= rand) or (j = popsize); select:= j; end; function mutation(alleleval: allele): allele; var mutate: boolean; begin mutate:= flip(pmutation); if mutate then begin nmutation:= nmutation + 1; mutation:= not alleleval; end else mutation:= alleleval; end;

UNIVERSIDAD NACIONAL ABIERTA

59

procedure crossover(parent1, parent2: chromosome; var child1, child2: chromosome; var jcross: integer); var j: integer; begin if flip(pcross) then begin jcross:= rnd(1, lchrom-1); ncross:= ncross + 1; end else jcross:= lchrom; for j:= 1 to jcross do begin child1[j]:= mutation(parent1[j]); child2[j]:= mutation(parent2[j]); end; if jcross lchrom then begin for j:= jcross+1 to lchrom do begin child1[j]:= mutation(parent2[j]); child2[j]:= mutation(parent1[j]); end; end; end;

procedure generation; var j, mate1, mate2, jcross: integer; begin j:= 1; repeat mate1:= select; mate2:= select; crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j].chrom, newpop[j+1].chrom,jcross); with newpop[j] do begin x:= decode(chrom,lchrom div 2); y:= decode1(chrom,lchrom div 2); fitness:= objfunc(x, y); parent1:= mate1; parent2:= mate2; xsite:= jcross; ysite:= jcross; end; with newpop[j+1] do begin x:= decode(chrom,lchrom div 2); y:= decode1(chrom,lchrom div 2); fitness:= objfunc(x, y); parent1:= mate1; parent2:= mate2; xsite:= jcross; ysite:= jcross end; j:= j + 2; until j>=popsize; end; begin gen:= 0; initialize; repeat gen:= gen + 1;

UNIVERSIDAD NACIONAL ABIERTA

60

generation; statistics(newpop); report; oldpop:= newpop; until (gen>= maxgen); end.

UNIVERSIDAD NACIONAL ABIERTA

61

ANEXO 3 Herramientas computacionales utilizadas a.

Microcomputador con procesador intel inside pentium 3.

b.

Compilador Turbo Pascal 7.0 (para la corrida de los programas del algoritmo genético simple para una y dos variables).

c.

Software Office 2003.

d.

Software MuPAD Light Versión 2.5.2 (para graficar las funciones).

e.

Software Maple 8 (para maximizar las funciones aplicando los métodos clásicos de optimización).

UNIVERSIDAD NACIONAL ABIERTA

62

Referencia bibliográfica Camero, A. (2003). Ciencia Explicada, Biología, Editorial Nomos, S.A., Bogotá Colombia. Chambadal, L. (1984). Diccionario de Matemáticas, Ediciones Grijalbo, S.A., México, D.F. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Publishing Company, Inc., Readind, MA. Holland, J. H. (1992). Adaptation in Natural and Artificial System, MIT Press, Second Edition. Ivanovich, A. (1997). El Origen de la Vida, Editorial Panamericana, Santa Fe de Bogotá, Colombia. Juricek, L. y González, J.S. (1987). Programación no Lineal (Optimización no Lineal), Universidad Nacional Abierta (Caracas). Keller, A. M. (1983). Programación en Pascal, Editorial Mc Graw Hill, México D.F. Marczyk, A. (2004). Algoritmos Genéticos y Computación Evolutiva, [Página web en línea]. Disponible en: http://the-geek.org/docs/algen. Martín, M. J. y García, M D. (2005). Seminario: Algoritmos Genéticos, [Página web en línea]. Disponible en: http://kal-el.ugr.es/mg. Melero, J. (2001). Algoritmos Genéticos, [Página web en línea]. Disponible en: http://kalel.ugr.es/. Prendes G., M. B. (2002). Optimización del Diseño y Construcción de Edificios Metálicos en Base a Algoritmos Genéticos (Tesis Doctoral), Universidad de Oviedo,

[Página

web

en

línea].

Disponible

en:

http://www6.uniovi.es/usr/belen/_private/tesis.pdf Rudolph, G. (1994). Convergence Analysis of Canonical Genetic Algorithms, IEEE Transactions on Neural Networks.

UNIVERSIDAD NACIONAL ABIERTA

63