Embed Size (px)
Citation preview
Algoritmo Memético Autoadaptativo Para
Solución De Problemas Combinatorios
YURI CRISTIAN BERNAL PEÑA
Director
Alvaro Enrique Ortiz Dávila
Revisores
Guillermo Enrique Real Flórez
Javier Joaquín Mesa
UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS
Facultad de Ingeniería
Maestría en Ingeniería Industrial
Énfasis en (Sistemas productivos y logísticos
Bogotá D.C.
2017
2
CONTENIDO I. INDICE DE ACRÓNIMOS ............................................................................................... 4
II. INTRODUCCION ........................................................................................................... 5
III. OBJETIVOS .................................................................................................................. 8
IV. PREGUNTA DE INVESTIGACION ............................................................................... 9
V. HIPÓTESIS ................................................................................................................... 9
1. MARCO TEORICO ................................................................................................... 10
1.1. PROBLEMAS DE OPTIMIZACION COMBINATORIA Y COMPLEJIDAD .............. 10
1.2. METAHEURISTICAS ............................................................................................. 11
1.3. ALGORITMOS EVOLUTIVOS ............................................................................... 12
1.4. ALGORITMOS GENETICOS ................................................................................. 14
1.5. ALGORITMOS MEMETICOS ................................................................................ 17
1.6. MA: BUSQUEDA LOCAL EN DOMINIOS COMBINATORIOS ............................... 19
1.7. AUTOADAPTACIÓN ............................................................................................. 21
1.8. DIVERSIDAD POBLACIONAL Y EFICIENCIA ....................................................... 23
2. DESARROLLO METODOLÓGICO DE LOS OBJETIVOS ......................................... 26
2.1. OBJETIVO GENERAL ........................................................................................... 26
2.2. OBJETIVOS ESPECIFICOS .................................................................................. 26
2.2.1. OBJETIVO ESPECIFICO 1 ............................................................................. 26
CASO DE ESTUDIO ESCOGIDO (PROBLEMA DE LA MOCHILA) .......................... 26
CODIFICACION DEL PROBLEMA ........................................................................... 27
2.2.2. OBJETIVO ESPECIFICO 2 ............................................................................. 27
ALGORÍTMO GENÉTICO DE BASE Y PARA COMPARACIÓN ............................... 28
2.2.3. OBJETIVO ESPECIFICO 3 ............................................................................. 28
ALGORITMO MEMETICO BASICO .......................................................................... 28
ALGORITMO DE BUSQUEDA LOCAL (Hill Climbing Voraz) .................................... 29
2.2.4. OBJETIVO ESPECIFICO 4 ............................................................................. 30
2.2.4.1. ADAPTACIÓN BASADA EN INDICADOR FITNESS COMPLEMENTARIO EN
EL OPERADOR DE EVALUACIÓN: ......................................................................... 31
2.2.4.2. ADAPTACIÓN BASADA EN INDICADOR HAMMING PARA DIVERSIDAD
POBLACIONAL ......................................................................................................... 34
2.2.5. OBJETIVO ESPECIFICO 5 ............................................................................. 36
3
MA AUTO-ADAPTATIVO PROPUESTO ................................................................... 36
3. RESULTADOS .......................................................................................................... 40
3.1. RESPONDIENDO LA PREGUNTA DE INVESTIGACION ..................................... 40
3.2.1. PRUEBAS HILL CLIMBING GRADO 2 Y GRADO 1 ........................................... 41
3.3. REPONDIENDO A LA HIPÓTESIS ....................................................................... 45
3.3.1. ALGORITMO MA ADAPTATIVO vs LOS BASICOS ........................................... 45
4. CONCLUSIONES ..................................................................................................... 49
REFERENCIAS ............................................................................................................... 51
4
I. INDICE DE ACRÓNIMOS
AI: Inteligencia Artificial
COP: Problemas de Optimización Combinatoria
EA: Algoritmos Evolutivos
EC: Computación Evolutiva
GA: Algoritmos Genéticos
HC: Algoritmo Ascenso de Colina (Hill Climbing)
HC1: Hill Climbing de un grado de exploración por nivel nodal
HC2: Hill Climbing de dos grados de exploración por nivel nodal
LS: (Local Search) Búsqueda Local
MA: Algoritmo Memético
MMA: Algoritmos MúltiMeméticos
NFLT: Teorema de No Free Lunch.
NP-Hard:(Non-Deterministic Polynomial-Time Hard) Problemas de NO solución en tiempo
polinomial
SA: Algoritmo Recocido simulado (Simulated Annealing)
SP: Presión Selectiva.
TS: Algoritmo Búsqueda Tabú (Tabú Search).
5
II. INTRODUCCION
En los problemas de optimización compleja los algoritmos evolutivos han sido la mejor
herramienta por lo que están presentes en variadas disciplinas; por ejemplo en la
administración de producción para encontrar cuál es la secuencia de trabajos para
maximizar la eficiencia de la planta de manufactura, en bioquímica para evaluar el
desempeño de fármacos con él análisis secuencial de proteínas, en electrónica
encontrando la forma óptima de una antena emisora-receptora, o en el desarrollo de
controladores.
La flexibilidad de las metaheurísticas evolutivas permite su uso en aquellos problemas
dónde tener una heurística especializada es muy difícil. Es por esto que las innovaciones
metodológicas en esta área son relevantes, pues trascienden la teoría incidiendo en forma
directa sobre la aplicación tecnológica.
Dentro de la evolución natural de las especies, el proceso bioquímico de la recombinación
de los cromosomas de individuos, con una muy esporádica mutación del mismo, y sumando
la presión selectiva del entorno, ha hecho que durante eones los seres vivos se adapten a
su entorno, sufriendo "optimizaciones" en su genoma, so pena de desaparecer. El biólogo
Richard Dawkins (Dawkins, 1976) resumió en forma brillante que la esencia de la vida es la
de persistir a ultranza a través de su material genético, lo que llamó el gen egoísta. Así
mismo planteo un concepto muy profundo: Los seres inteligentes superan esa barrera de
la evolución genética, y afrontan la dura selección natural utilizando un concepto nuevo para
las especies, el intercambio de información usando la comunicación. Esta nueva
herramienta de adaptación, “el conocimiento”, se conforma de ideas o como Dawkins las
denominó memes por su analogía con los genes: las buenas ideas se comunican,
permanecen y se mejoran, mientras que las malas son olvidadas, en una selección parecida
a la de los genes.
Los algoritmos meméticos recogen ese concepto, y agregan al proceso evolutivo un
proceso adicional de mejoramiento de la población; en forma análoga a como el
conocimiento compuesto por memes, es comunicado entre individuos sobrepasando las
generaciones, el proceso memético en un algoritmo de optimización busca la mejor
6
adaptación de los individuos más allá de los procesos de cooperación y competición
netamente evolutiva. Esta es una etapa de mejoramiento individual.
El objetivo del presente trabajo fue el innovar en la técnica del proceso memético, de forma
que aportara nuevas ideas en procura de su eficiencia. Se propone un Algorítmo Memético
que ajuste durante la exploración su método y parámetros de Búsqueda Local dependiendo
de la diversidad poblacional, así como en dicho ajuste innovar realizando también
exploraciones por el espacio infactible de soluciones. Se pone a prueba utilizando el
problema de la mochila o knapsack.
En el segundo capítulo se abordan los conceptos básicos que serán de utilidad para la
comprensión de la propuesta. Aquí se exponen los elementos esenciales de un algoritmo
evolutivo, la selección, el cruce, la mutación y la diversidad. Y es que la diversidad, como
ocurre en la naturaleza, permite alcanzar un mayor rango de soluciones, incrementando las
posibilidades de éxito. El hecho de que el algoritmo sea cambiante acorde a su diversidad
poblacional, nos introduce en otro concepto actualmente en estudio: la autoadaptación de
los algoritmos. También los conceptos sobre algoritmos meméticos, la búsqueda local y la
autoadaptación son tratados aquí.
En el tercer capítulo se plantea el desarrollo metodológico de los objetivos: Se argumenta
la escogencia del problema para las pruebas experimentales: la mochila, big packing o
KnapSack problema (objetivo específico 1). Se plantea el tipo de AG (Algoritmo Genético)
básico que servirá como primera capa del algoritmo final, así como base de comparación
para la hipótesis (objetivo específico 2). Se explica el desarrollo metodológico del MA
(Algoritmo Memético) base (objetivo específico 3), el cual emplea como LS (búsqueda
local) la heurística Hill Climbing tipo Greedy. También sirve como segunda capa del
algoritmo final y base de contrastación de la hipótesis. Se plantea como mejora propuesta
a los operadores de selección y búsqueda local, una exploración por el espacio infactible;
así mismo se plantea como indicador para ajuste de la exploración local la distancia
Hamming ligada a la diversidad poblacional y los nichos (objetivo específico 4).
Finalmente se propone el MA Autoadaptativo basado en los planteamientos anteriores; se
mide la eficiencia de aplicar una búsqueda local suave (Hill Climbing de un nivel) o más
intensa (Hill Climbing de dos niveles) a nichos poblacionales, basándose en la cercanía a
la mejor solución hasta ahora encontrada (objetivo específico 4).
7
En el cuarto capítulo se presentan los resultados, se da respuesta a la pregunta de
investigación al verificar en qué medida deben ajustarse los parámetros y operadores del
MA Autoadaptativo para logar mayor eficiencia con base en la dispersión poblacional. Así
mismo se responde la hipótesis poniendo a prueba la eficiencia y eficacia del algoritmo MA
Autoadaptativo desarrollado versus los básicos.
En el quinto capítulo se realizan las conclusiones finales y se propone una posible
investigación futura tendiente a la mejora del algoritmo final desarrollado.
8
III. OBJETIVOS
OBJETIVO GENERAL
Proponer un Algoritmo Memético autoadaptativo que ajuste operadores y/o parámetros de
exploración local en tiempo de ejecución, con base en la retroalimentación obtenida de las
soluciones parciales que se van generando durante la ejecución del algoritmo.
OBJETIVOS ESPECÍFICOS
1. Escoger el problema combinatorio representativo adecuado que permita realizar
comparaciones:
2. Desarrollar el Algoritmo Genético base para el MA, con los operadores y parámetros que
según la teoría dan el mejor tiempo de búsqueda (eficiencia), conservando la calidad de las
soluciones encontradas (efectividad):
3. Desarrollar el Algoritmo Memético estándar, con un método de búsqueda local adecuado,
que esté basado en el GA ya elaborado.
4. Proponer indicadores de eficiencia en la aplicación de la búsqueda local orientada a
nichos, de forma tal que permitan una auto-adaptación del algoritmo en tiempo de
ejecución. Dichos indicadores darán la retroalimentación para ajustar los operadores y/o
parámetros del algoritmo.
5. Desarrollar el Algoritmo Memético auto-adaptativo basado en los indicadores para
adaptación y ajuste propuestos, que muestre mejoras respecto al GA y MA básicos.
9
IV. PREGUNTA DE INVESTIGACION
¿Qué operadores y/o parámetros en el MA podemos variar dinámicamente y en forma auto-
adaptativa durante la ejecución de la exploración, así como también sobre que agentes
aplicamos dicha auto-adaptación, para mejorar los resultados obtenidos de dicha búsqueda
y/o mejorar su eficiencia?
V. HIPÓTESIS
En el algoritmo Memético, la búsqueda autoadaptativa que ajusta operadores y/o
parámetros de exploración, tenderá a disminuir el tiempo de búsqueda, encontrando
soluciones tan buenas o mejores que los GA’s y MA’s básicos, a pesar del recurso
computacional extra que dicha autoadaptación pueda implicar.
10
1. MARCO TEORICO
1.1. PROBLEMAS DE OPTIMIZACION COMBINATORIA Y COMPLEJIDAD
La resolución de problemas de optimización combinatoria (COP) pertenece al campo de la
matemática aplicada y las ciencias de la computación que abarcan áreas como la
investigación de operaciones y la teoría de la complejidad. En estos problemas el objetivo
es encontrar el máximo o el mínimo de una función sobre un conjunto finito de soluciones;
no se exige ninguna condición o propiedad sobre la función objetivo o la definición del
conjunto de soluciones (Martí, 2003); las variables han de ser discretas por lo que el
conjunto de soluciones se restringe en su dominio a una serie finita de valores.
Habitualmente, el número de elementos solución es muy elevado, haciendo impracticable
la evaluación de para determinar el óptimo. Básicamente se puede reducir un problema
combinatorio de optimización a aquellos donde se desea encontrar un orden específico
sobre un conjunto de elementos discretos (Aarts & Lenstra, 2003) (Sait & H., 1999).
En los problemas de optimización podemos de manera audaz preguntarnos si es fácil o
difícil de resolver. Esta simple pregunta abarca un campo de investigación que partir de la
década de los setenta los investigadores abordaron con el nombre de teoría de la
complejidad computacional, la cual determina si un problema es fácil o no de acuerdo con
los algoritmos conocidos para resolverlo.
Un conjunto ordenado y finito de operaciones que permiten solucionar un problema, o lo
que podemos denominar un algoritmo de búsqueda, empleará un número de operaciones
aritméticas durante su ejecución, lo que le hará emplear tiempo como recurso
computacional. Para la teoría de la complejidad computacional, un problema es fácil si
existe un algoritmo que lo resuelve en tiempo polinomial; o sea, si el número de operaciones
necesarias para que el algoritmo resuelva el problema es una función polinomial del tamaño
del problema. Si no lo es, se dice que el algoritmo es no polinomial y el problema se
considera difícil, lo cual se denomina NP-Hard (non-deterministic polynomial-time hard)
(Papadimitriou, 1994) (Klein & Young., 2009). Si un problema se puede resolver en tiempo
polinomial quiere decir que es posible encontrar la solución óptima en unos cuantos
segundos o minutos; por el contrario, si es no polinomial, podrían necesitarse años o incluso
11
siglos para hacerlo, por lo que surge la necesidad de desarrollar estrategias para encontrar
soluciones buenas a un costo computacional razonable.
En los COP entran muy a menudo como mínimo en la categoría de complejidad
computacional NP-Hard (Leeuwen, 1998) (Lawler, Lenstra, & Rinnooy, 1985), ya que el
número de posibles combinaciones de elementos del problema (siendo cada combinación
de elementos una posible solución) puede ser muy grande, lo que dificulta, e incluso en
ocasiones imposibilita alcanzar el óptimo en un tiempo finito, y si lo hace, no hay manera
de asegurar que sea la solución óptima.
1.2. METAHEURISTICAS
Para entender el significado de los métodos metaheurísticos debemos comenzar por
examinar el significado de los métodos heurísticos; una buena definición es la siguiente:
“Un método heurístico es un procedimiento para resolver un problema de optimización bien
definido mediante una aproximación intuitiva, en la que la estructura del problema se utiliza
de forma inteligente para obtener una buena solución” (Díaz, y otros, 1996).
Los métodos heurísticos a diferencia de los métodos exactos, no encuentran una solución
óptima del problema; por el contrario, se limitan a proporcionar una buena solución, aunque
no necesariamente sea óptima. En un problema catalogable como difícil, el tiempo invertido
por un método exacto puede ser enorme, por lo que puede ser inaplicable. Un método
heurístico puede simplificar la solución del problema acercándose al óptimo en forma
razonable.
Dentro del desarrollo de los algoritmos de aproximación Fred Glover en 1986 acuña el
término Metaheurísticas para aquellos métodos que sofistican y generalizan los algoritmos
empleando las heurísticas existentes, ubicándose por encima de los métodos heurísticos
en el sentido que guían el diseño de estos. Una definición apropiada la encontramos en
(Osman, 1996):
“Los procedimientos metaheurísticos son una clase de métodos aproximados que están
diseñados para resolver problemas difíciles de optimización combinatoria, en los que los
heurísticos clásicos no son efectivos. Los metaheurísticos proporcionan un marco general
12
para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la
inteligencia artificial, la evolución biológica y los mecanismos estadísticos.”
Entre los metaheurísticos más exitosos se encuentran el recocido simulado (simulated
annealing), la búsqueda tabú (tabu search), las redes neuronales artificiales (artificial neural
networks),optimización por colonias de hormigas (ant collony optimization), la búsqueda
local iterativa (iterated local search), la computación evolutiva (evolutionary computing) y
los algoritmos genéticos (genetic algorithms); estos últimos al hibridarse con heurísticas de
búsqueda local dieron luz a los algoritmos meméticos, base para la presente investigación.
1.3. ALGORITMOS EVOLUTIVOS
Los Algoritmos Evolutivos (EA) o Computación Evolutiva (EC) trata de aprender y usar los
procesos aprendidos de la Naturaleza para aplicarlos a la resolución de diversos problemas
de optimización. Es por esto que los EA son un conjunto de técnicas de optimización
metaheurísticas de tipo poblacional y de propósito general cuyo funcionamiento se basa en
los procesos biológicos evolutivos (Back, Fogel, & Michalewicz, Handbook of Evolutionary
Computation, 1997). Alrededor de los años 60, algunos investigadores coincidieron (de
forma independiente) en la idea de implementar algoritmos basados en el modelo de
evolución biológica, con el objetivo de resolver tareas de optimización duras mediante el
uso de computadores; inicialmente, las ideas de estos científicos pioneros en este campo
eran estrictamente académicas, tratando de ampliar el horizonte de la Inteligencia Artificial
(AI) hacia nuevas áreas, pero a partir de los años 80’s los EA comienzan a aplicarse en
problemas de diversos ámbitos como la ingeniería, la medicina o la economía. Aunque los
EA utilizan las ideas de la Teoría de la Evolución de las Especies, no pretenden seguir un
proceso estricto de simulación de la misma, sino, por el contrario, en la actualidad
incorporan ideas innovadoras en aras de mejorar la eficiencia y eficacia de los mismos.
En los EA esencialmente deben tener los siguientes elementos:
Una representación de las soluciones: El dominio del problema debe codificar las
soluciones de manera adecuada al problema. Cada solución es considerada un individuo.
13
Una o varias poblaciones: Conjunto de soluciones candidatas que representan la población
de individuos del problema.
Una función de aptitud o fitness: Determina el puntaje o la calidad de las soluciones
candidatas.
Procedimientos u operadores de selección y reemplazo: Basados en la función de aptitud.
Mecanismo u operador de transformación: Convierte soluciones candidatas en otras
nuevas, es decir, procedimiento que construye nuevas soluciones a partir de las existentes.
La figura 1.1 Representa el diagrama de Flujo de un Algoritmo Evolutivo
Fuente: El autor.
14
1.4. ALGORITMOS GENETICOS
Dentro de las metaheurísticas de los EA encontramos los algoritmos genéticos (GA), los
cuales son métodos de búsqueda y optimización basados e inspirados en la adaptación
natural a través de procesos genéticos. La evolución se fundamenta en la selección natural
y la supervivencia de los más fuertes postuladas por Darwin en 1859.
Los principios básicos fueron establecidos por John Holland (Holland, 1975), pero fueron
(Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, 1989),
(Davis, 1991), (Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs,
1992), quienes posteriormente los aplicaron exitosamente.
Los GA trabajan con una población de individuos, cada uno de los cuales representa una
solución factible del problema. A cada individuo se le asigna un valor o puntuación (fitness),
relacionado con la bondad de dicha solución. Cuanto mayor sea la adaptación de un
individuo al problema (mayor fitness), mayor será la probabilidad de que el mismo sea
seleccionado para reproducirse, cruzando su material genético con otro individuo
seleccionado de igual forma. Este cruce producirá nuevos individuos descendientes de los
anteriores, los cuales comparten algunas de las características de sus padres. Cuanto
menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo
sea seleccionado para la reproducción, y por tanto de que su material genético se propague
en sucesivas generaciones.
De esta manera se produce una nueva población de posibles soluciones, la cual
reemplazará a la población precedente y contendrá una mayor proporción de buenas
características en comparación con la población anterior. Así a lo largo de las generaciones
las buenas características se propagan dentro de la población, favoreciendo en el cruce de
individuos a los mejor adaptados, garantizando la exploración de zonas más prometedoras
del espacio de búsqueda; de todos modos, para evitar quedar atrapados en óptimos locales
es necesario mutar eventualmente algunos individuos, saltando así a nuevas zonas de
búsqueda. Si el GA ha sido bien diseñado, la población tenderá a converger en una solución
óptima del problema.
Por lo tanto, podemos exponer como principales conceptos de los GA los siguientes:
15
Codificación: La representación de los individuos de la población debe ser homogénea de
forma que permita su posterior cruce. Dicha información por lo general se representa en
una cadena, generalmente binaria, llamada cromosoma; también se pueden emplear
números enteros y decimales en la codificación. Los símbolos que forman la cadena son
llamados los genes y la representación con cadenas de dígitos se le conoce como genotipo.
Operadores: Estos son procesos que permiten el cambio en los individuos, generando
nuevas poblaciones a través de procesos de cooperación y competición (Araujo, 2009).
Operador de selección: La selección es proceso competitivo; es aquí donde se marcan
aquellos individuos que deben donar su material genético a las nuevas generaciones,
llamados elite, así como aquellos que deben desaparecer de la población para dar paso a
mejores individuos. La selección de individuos a reemplazar se puede realizar en forma
aleatoria, entre un porcentaje de la población de los individuos no elite. A esto se le llama
selección por ruleta o Montecarlo. Si se reemplazan estrictamente los peores individuos
comparando las aptitudes de toda la población, será una selección por torneo.
Operador de Cruce, el cual representa la recombinación genética de los individuos más
adaptados. Una sección del cromosoma se intercambia entre individuos para generar así
un nuevo individuo. Normalmente el operador de cruce no se aplica a todos los pares de
individuos que han sido seleccionados para emparejarse, sino que se aplica de manera
aleatoria, habitualmente con una probabilidad comprendida entre 0.5 y 1.0.
Si se escoge un punto aleatoriamente de la cadena cromosómica y a partir de ahí se realiza
el intercambio con otro cromosoma, será un cruce monopunto. Si se escogen segmento por
separado de la cadena cromosómica para intercambiar, será un cruce multipunto. En caso
en que el operador de cruce no se aplique, la descendencia se obtendrá simplemente
duplicando los padres.
Figura 1.2 Operador de cruce mono punto
16
Mutación: Un proceso muy importante y también existente en la evolución biológica de las
especies es el operador de mutación; con una probabilidad establecida, mutaremos cada
nueva generación en algún gen o bit del cromosoma de la posible solución o individuo.
Dicha probabilidad influye fuertemente en la calidad de las soluciones encontradas, pues
evita en cierta medida estancarnos en zonas de óptimos locales. El inconveniente es que
tiende a desmejorar al individuo mutado.
Figura 1.3 Operador de Mutación
Presión selectiva: El grado de favorecimiento a los individuos más adaptados en el proceso
de selección se denomina presión selectiva (SP). Demasiada SP disminuye la diversidad
poblacional, conllevando a convergencias prematuras, con una búsqueda miope que no
sobrepase más que un óptimo local; y poca SP puede hacer que el algoritmo evolucione
lentamente, con lo cual aumentará el tiempo de procesamiento.
Fitness: La función de aptitud o fitness es la que permite valorar la aptitud de los individuos;
tomará siempre valores positivos. Suele ser igual a la función de evaluación objetivo, pero
puede ser que la función objetivo sea muy compleja, tome valores negativos, o no
proporcione un valor numérico y, por lo tanto, sea necesario definir una función de aptitud
diferente.
Básicamente un algoritmo genético ejecuta sus procesos en la siguiente secuencia:
• Definir tamaño de población.
17
• Representación genética de los individuos (codificación de soluciones del
problema).
• Procedimiento para generar una población inicial.
• Función de evaluación de individuos en términos de adaptación con base en las
reglas de la evolución.
• Función de cruce (creación de la descendencia durante la reproducción).
• Función de mutación (probabilidad de la misma)
• Criterio de parada.
Figura 1.4 Diagrama de Flujo de un AG
Fuente: El autor.
1.5. ALGORITMOS MEMETICOS
Los Algoritmos Meméticos (MA) son meta-heurísticas que intentan unificar conceptos de
diferentes técnicas de resolución, como lo son algoritmos evolutivos (EA) y algoritmos de
búsqueda local (LS). El adjetivo memético viene del termino ingles meme, acuñado por
(Dawkins, 1976) para designar al análogo del gen en el contexto de la evolución cultural.
El empleo de esta terminología representa la difuminación de la inspiración puramente
biológica, para optar modelos más genéricos en los que se manipula, se aprende y se
transmite información. En relación con este concepto, pueden encontrarse diversos trabajos
que hacen uso de nombre alternativos para referirse a estos (EA híbridos o Lamarckianos),
18
o que aun usando el propio termino MA, hacen una interpretación muy restringida del
mismo.
Entre las primeras publicaciones que trataron el tema destaca la realizada por Brady (Brady,
1985), pero no fue hasta que Moscato profundizo en sus clasificaciones y aplicaciones que
despegaron en el mundo de la optimización (Moscato, On Evolution, Search, Optimization,
Genetic Algorithms and Martial Arts: Towards Memetic Algorithms, 1989).
La razón de la hibridación de la búsqueda evolutiva (de los cuales hacen parte los GA) con
algoritmos de búsqueda local (LS), radica en que los primeros son buenos en exploración
global, garantizando mayor diversificación y evitando enfrascarse en óptimos, mientras que
los segundos son buenos optimizadores locales (algunos lo llaman explotación local),
aumentando la probabilidad de llegar a un óptimo en poco tiempo.
Figura 1.5 Exploración GA y LS
Fuente: El autor.
En los MA los individuos pueden estar compuestos de determinadas unidades de
información adicional sobre el estado de las soluciones del problema, por lo que se les suele
llamar agentes ( Cotta C. , 2007); el llamarlos agentes implica la existencia de un
comportamiento activo, mientras que un individuo denota un ente pasivo que está sujeto
sólo a los procesos y reglas evolutivas; los agentes facilitan el ser “conscientes” del
problema los operadores que emplea el MA, basando así su funcionamiento en el
conocimiento que incorporan sobre el problema; de esta forma los mismos agentes orientan
la búsqueda con base en las unidades de información que determinan si una solución es
19
buena, prometedora o no para seguir explorándola. Estos agentes cooperan entre sí vía
recombinación, compiten vía selección y se auto-mejoran vía LS.
Figura 1.6 Diagrama de Flujo de un MA
Fuente: El autor.
En el área de Investigación de Operaciones, y en general en los métodos de optimización,
los MA han aportado ideas y técnicas revolucionarias, directamente en problemas como el
scheduling o secuenciación de trabajos, diseño de redes de distribución y centros de
distribución, diseño de rutas, y en general a en problemas de optimización discreta y
continua muy comunes en la administración de operaciones (Vélez & Montoya, 2007).
1.6. MA: BUSQUEDA LOCAL EN DOMINIOS COMBINATORIOS
La búsqueda local (LS) es esencial en el desarrollo del MA, ya que es esta la que orienta la
exploración basándose en el conocimiento del problema, es el proceso de aprendizaje
individual; la LS debe ayudar a nutrir la población de agentes de mayor calidad,
perjudicando lo menos posible la diversidad. Se considera que para que un algoritmo
híbrido sea considerado MA, la búsqueda Local siempre debe aplicarse dentro del proceso
evolutivo (Moscato & Cotta, An Introduction to Memetic Algorithms, 2003).
20
Una heurística LS puede ser cualquiera que realice una exploración de nodos (individuos o
agentes) basándose en la adyacencia y el puntaje o fitness entre los mismos. En su forma
básica explorará la vecindad de las soluciones sobre las que se aplica.
Podemos clasificar los algoritmos LS aplicados al MA dela siguiente forma (Neri, Cotta, &
Moscato, 2012):
1. De acuerdo con la naturaleza lógica de la búsqueda:
• Estocástica: La generación de la solución de prueba se produce en forma aleatoria.
• Determinística: la generación de la solución de prueba es determinística.
2. De acuerdo con la cantidad de soluciones involucradas:
• Simple Solución: El algoritmo procesa y modifica una sola solución.
• Múltiple Solución: El algoritmo procesa más de una solución, las cuáles se emplean para
interactuar y generar conjuntamente otras soluciones prueba.
3. De acuerdo con la regla de pivote:
• Pendiente más empinada (Steepest Descent): El algoritmo genera un conjunto de
soluciones y selecciona las más prometedoras sólo después de explorar todas las
posibilidades.
• Voraz (Greedy): El algoritmo realiza el reemplazo tan pronto como detecta una solución
que supera a la actual mejor y comienza de nuevo.
Entre las heurísticas para búsqueda local básicas (a partir de las cuales tienden a salir
otras) tenemos las siguientes:
Hill Climbing (HC): Heurística ascenso de colinas. Esta técnica de optimización matemática
consiste en ubicarse en una solución (un vértice en espacios discretos) e irse desplazando
a soluciones aledañas de mejor calidad en un proceso iterativo. Como con este método se
dirige siempre a una solución mejor que la actual, terminará cuando ningún punto adyacente
sea mejor, o cuando se alcance un número predefinido de iteraciones. En su forma básica
el HC se encamina a óptimos locales, por lo que debe acompañarse operadores que ayuden
a ampliar la diversidad de espacios de búsqueda.
Puede haber varias variantes del algoritmo dependiendo, por ejemplo, de la regla de pivote
como se menciona en el punto 3 anterior. En algunos casos el vecindario es muy grande y
21
no es posible una exploración completa (al menos usando el esquema simple de HC), por
lo que procedimientos locales de ramificación y poda permitan explorar zonas grandes
(Fischetti & Lodi, 2003).
Simulated Annealing (SA): Heurística Recocido Simulado. Se inspira en el proceso de
recocido del acero y cerámicas, técnica que consiste en calentar y luego enfriar lentamente
el material para variar sus propiedades físicas a través del reordenamiento molecular para
optimizar su resistencia (Cerny, 1985). SA realiza la búsqueda de nuevas soluciones de
acuerdo a la lógica de la heurística HC, pero puede pasar a una solución peor con una
cierta probabilidad que depende de la diferencia en calidad entre ambas soluciones y de la
temperatura actual del sistema T. Dicha probabilidad va disminuyendo en forma asintótica
a medida que disminuye la temperatura del sistema. La temperatura se representa con un
parámetro de control que disminuye en forma inversa al número de iteraciones.
Tabú Search (TS). HeurísticaBúsqueda Tabú. Búsqueda basada en memoria (Glover &
Laguna, 1997) con capacidad de optimización global. Se puede considerar como una
extensión sofisticada de una heurística básica HC, en la cual se explora en el vecindario,
pero permite moverse a una solución que no sea tan buena como la actual, pudiendo así
escapar de óptimos locales. Se considera Glover como su creador en 1989, quién trató de
dotar de “inteligencia” a los algoritmos de búsqueda local, tomando de la Inteligencia
Artificial el concepto de memoria. Aquí se crea un listado de soluciones “tabú”, el cuál puede
ser dinámico, permitiendo así evadir soluciones ya exploradas. En este sentido puede
decirse que hay un cierto aprendizaje y que la búsqueda es inteligente.
La lista tabú (linked list) puede contener: Soluciones visitadas recientemente, movimientos
realizados recientemente, atributos o características que tenían las soluciones visitadas.
1.7. AUTOADAPTACIÓN
La búsqueda del mejor algoritmo de propósito general de optimización fue un reto constante
en la segunda mitad del siglo veinte, pero perdió sentido a finales de la década de los
noventa cuando se demostró el Teorema No Free Lunch (NFLT) (Wolpert & Macredy, 1997).
Dicho teorema demuestra que los algoritmos de optimización presentarán un mejor
22
rendimiento para unos problemas determinados, pero esto conlleva que serán peores para
otro tipo de problemas, concluyendo así que todos los algoritmos de optimización tienen
finalmente la misma eficiencia promedio. Esto implica que la búsqueda de un super
algoritmo de propósito general desde el punto de vista teórico pierde piso.
Sin embargo, los algoritmos los algoritmos que son capaces de aprender y ajustar sus
estrategias de búsqueda sobre la marcha dan cierta esperanza de lograr algoritmos mucho
más extensivos. Sumado a esto, intuitivamente las metaheurísticas evolutivas, a pesar del
NFLT, dan visos de comportarse mejor que otras técnicas cuando el conocimiento del
problema es limitado.
Podemos clasificar las estrategias metodológicas en la configuración de parámetros dentro
de los GA en tres categorías (Eiben, Hinterding, & Michalewicz, 1999):
Mecanismos determinísticos: Dónde los valores delos parámetros estratégicos, o sea,
aquellos valores paramétricos de los operadores que más influyen en la búsqueda, son
controlados por reglas determinísticas sin ninguna retroalimentación dentro de la búsqueda.
Mecanismos adaptativos: Dónde existe alguna forma de retroalimentación durante el
proceso de búsqueda, que permite reconfigurar parámetros estratégicos.
Mecanismos de auto-adaptación: Dónde el parámetro estratégico es codificado e
incorporado al cromosoma, por lo que es afectado por los operadores genéticos.
Dentro de los primeros GA adaptativos que incorporan la flexibilidad de parámetros y
operadores, se investigaron la adaptación de la recombinación (crossover) y la mutación
durante el proceso de exploración (Fogel & Angeline, 1995). Así mismo, se han realizado
estudios para observar el comportamiento de los GA cuando se modifican sus operadores
con base en el grado de convergencia que presente la población durante la exploración, a
lo que se le llamó “meta-learning” (Smith & Fogarty, 1997).
En los Algoritmos Meméticos, (MA) también se ha estudiado la adaptación, pero enfocada
en la búsqueda local; se ha propuesto incorporar diferentes métodos LS al proceso de
competición (selección) y cooperación (cruce), aumentando la probabilidad de aplicar a los
agentes aquellos métodos que han tenido mejores resultados durante la exploración. A esta
23
técnica se le denomina Aprendizaje Meta-Lamarckiano (Ong & Keane, Meta Lamarckian
Lerning in Memetics algorithms, 2004).
La incorporación de los memes al cromosoma de los individuos para que hagan parte del
proceso evolutivo, entendiendo como meme cualquier procedimiento para el aprendizaje
de soluciones, y pudiendo ser parte del cromosoma una secuencia de heurísticas a aplicar
en el agente, es una técnica a la que se denomina Algoritmos Multi-Meméticos (MMA)
(Krasnogor, 2002).La codificación de los memes tiene una ventaja importante y es que
permite que estos evolucionen de forma dinámica durante la ejecución del MA. Los MMA
se están trabajando actualmente en diversos campos de la Inteligencia Artificial (AI) (Neri,
Toivanen, Cascella, & Ong, 2007).
Las más reciente investigaciones tratan de incorporar los conceptos dela programación
autónoma a los MMA, utilizando las propiedades de control self de sistemas autónomos
como la auto-reparación y auto-configuración en los procesos de cooperación, competición,
mejora individual, e incluso en la topología de búsqueda (Nogueras & Cotta, 2015).
1.8. DIVERSIDAD POBLACIONAL Y EFICIENCIA La diversidad poblacional es importante para evitar que dicha población converja
prematuramente a óptimos locales. En el estado de convergencia, los agentes tienen gran
similitud entre sí, y es algo que puede ser cuantificado, empleando por ejemplo medidas
clásicas de Teoría de la Información como la entropía de Shannon (Davidor & Ben-Kiki,
1992). Su funcionamiento consiste básicamente en comparar en toda la población, o a
través de muestreo, la similaridad entre individuos o la insuficiente variedad
genética/memetica para que el proceso de búsqueda pueda continuar avanzando,
considerando un umbral mínimo a partir del cual se puede considerar esta convergencia
como un hecho. También se han empleado técnicas estableciendo una probabilidad de
aproximación para decidir si la población ha convergido, como el método de aproximación
Bayesiana (Hulin, 1997). Cuando sucede la convergencia poblacional, existen varias
posibilidades, desde medidas pasivas como analizar el algoritmo (se podría incluir este
24
hecho en la condición de terminación del bucle correspondiente al ciclo de vida) u otras
activas como puede ser reinicializar la población (o parte de ella) para introducir nueva
variedad genética/memetica. Así mismo la diversidad poblacional se puede medir a través
del concepto de nichos de soluciones (Pétrowski, 1996)
Existen algoritmos genéticos que enfocan su eficiencia en el mantenimiento de la diversidad
poblacional, ejemplo de esto son:
Sharing fitness: Divide el espacio de búsqueda en subregiones o nichos con una distancia
limite predeterminada. Se exploran dentro de este radio, y si hay muchas soluciones en su
nicho, el valor de la función de modificación será elevado y, por ello su calidad será
altamente penalizada, frente a otras soluciones en cuyo nicho haya pocas o ninguna
solución, por lo que este último tendrá más posibilidades de ser analizado en el proceso de
búsqueda.
Continuously updated sharing: La diferencia con el método sharing simple es que, en lugar
de penalizar la aptitud de los individuos en áreas con sobrepoblación, se van penalizando
la selección de padres en las áreas con sobre población. Así, la calidad de una zona en la
que ya haya varios padres seleccionados se penaliza limitando la posibilidad de que sus
individuos sean elegidos para la población de padres.
Clearing: El algoritmo de Clearing básico preserva el fitness del individuo dominante,
mientras que degrada el fitness de todos los otros individuos de la misma subpoblación
acero. También es posible permitir más de un individuo dominante (fitness diferente de
cero) por subpoblación. Un individuo pertenece a una subpoblación dada, si su medida de
disimilitud con el dominante de dicha subpoblación es menor que un determinado valor
denominado radio del clearing.
Para dividir la población en nichos, base de lo anteriormente expuesto, se hace necesario
medir la distancia entre individuos, lo que indicara su grado de disimilitud. Podemos hacer
esto con el método normalizado de Hamming (Wang, Wang, & Yang, 2009), el cual calcula
la distancia entre individuos xi = (xi1, . . . , xin) y xj = (xj1, . . . , xjn) así:
25
1.1)�������, ���) = ���� − ��������
Y también determina el promedio de la dispersión respecto del mejor individuo (ε) como
medida de diversidad:
1.2)����� = ���∗, ��)���_������
���_� !"
Donde x* es el mejor individuo de la población. Por lo tanto (ε) nos muestra el grado de
convergencia de la población vía distancia Hamming. Si este indicador disminuye, quiere
decir que la población ha perdido diversidad.
26
2. DESARROLLO METODOLÓGICO DE LOS OBJETIVOS
2.1. OBJETIVO GENERAL
Proponer un Algoritmo Memético autoadaptativo que ajuste operadores y/o
parámetros de exploración local en tiempo de ejecución, con base en la
retroalimentación obtenida de las soluciones parciales que se van generando durante
la ejecución del algoritmo.
2.2. OBJETIVOS ESPECIFICOS
2.2.1. OBJETIVO ESPECIFICO 1
Escoger el problema combinatorio representativo adecuado que permita realizar
comparaciones:
CASO DE ESTUDIO ESCOGIDO (PROBLEMA DE LA MOCHILA)
El problema de la mochila o Knapsack Problem, es uno de los problemas NP-completos
catalogado así por el informático teórico Richard Karp (Karp, 1972). Ha sido estudiado
desde que fue planteado formalmente a finales del siglo XIX. Su fama se debe a lo sencillo
de su planteamiento, pero lo complejo que es para resolver. Como todos los problemas
estructurados representativos, las técnicas para su resolución pueden extrapolarse a
problemas de optimización de diversas ramas del conocimiento.
En su forma básica consiste en llenar una mochila que soporta como máximo un peso
determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor
específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder
el peso máximo.
27
Elementos: xi i ∈�{1..n}
Pesos: wi i ∈�{1..n}
Valores: vi i ∈�{1..n}
Capacidad Máxima: W
2.1)����$á� & !'(� ) ��*��
��
S.A.
) ��+� ≤ -�∀� ∈ {1. . �}��
��
��� ∈ {0,1}
CODIFICACION DEL PROBLEMA
Cada agente representará una solución con la siguiente información:
Cromosoma: Cada posición del cromosoma (gen) será binaria, y representará la inclusión
(1) o no inclusión (0) de un elemento xi en la mochila.
2.2.2. OBJETIVO ESPECIFICO 2
Desarrollar el Algoritmo Genético base para el MA, con los operadores y parámetros
que según la teoría dan el mejor tiempo de búsqueda (eficiencia), conservando la
calidad de las soluciones encontradas (efectividad):
28
ALGORÍTMO GENÉTICO DE BASE Y PARA COMPARACIÓN
Método del GA para Selección, Cruce y Mutación:
El siguiente es el Algoritmo Genético base (primera capa) para la elaboración del Algoritmo
Memético básico (Segunda Capa), y el Algoritmo Memético Autoadaptativo (tercera capa).
En el desarrollo del GA básico, para los procesos de selección, cruce y mutación se
tomaron los valores y procesos estándar de los GA (ver Marco Teórico Sección 2.3)
principalmente los recomendados por (Araujo, 2009). El método de selección utilizado fue
ruleta. La probabilidad de selección usada en todas las pruebas fue de 0.4 con un
porcentaje de población elite de 2%. Para el operador de cruce se empleó la técnica
monopunto con punto de inicio aleatorio. La probabilidad de mutación es de 0.001.
Aptitud o Fitness: Valor de la solución será 0 en caso de que la solución sea infactible.
Probabilidad de selección: Relación entre el puntaje de adaptación del agente y la suma
total de puntajes de toda la población. �2�3)
2�3)
Probabilidad de selección acumulada: Suma acumulada de la probabilidad de selección de
todos los agentes anteriores hasta el actual. Para el último agente de la población deberá
sumar 1.
Elite: Estado booleano que indica si el agente pertenece a la élite o no en la actual
generación.
2.2.3. OBJETIVO ESPECIFICO 3
Desarrollar el Algoritmo Memético estándar, con un método de búsqueda local
adecuado, que esté basado en el GA ya elaborado.
ALGORITMO MEMETICO BASICO
El MA básico desarrollado utiliza los elementos estándar de los Algoritmos Genéticos para
los procesos de cooperación y competencia entre agentes. El método de Búsqueda Local
que utiliza es el Hill Climbing tipo Greedy, (ver Marco Teórico sección 1.6), el cuál es
recomendado por (Neri, Cotta, & Moscato, 2012) para este tipo de problemas; se emplea
29
en el presente estudio una capacidad de búsqueda por nivel nodal de uno y dos grados o
dimensiones de combinación en profundidad.
ALGORITMO DE BUSQUEDA LOCAL (Hill Climbing Voraz)
El algoritmo usado como operador de mejoramiento local individual o LS es el Hill Climbing
o ascendiendo la colina, tipo greedy o voraz. Consiste en encontrar a la mejor solución o
individuo vecino, y si este tiene un fitness o mejor adaptación que el actual nos desplazamos
para allá. Este proceso continuará hasta que no encontremos un vecino mejor, lo que
significa que estaremos en un óptimo local, o con suerte, el óptimo global.
Para pasar a una solución vecina lo que se hace es cambiar un solo gen del cromosoma, y
verificar la nueva adaptación. Esto se hace en forma exhaustiva para todas las
combinaciones posibles, lo que denominamos combinación de un grado por nivel nodal.
Esto supone que el número de combinaciones exploradas por nivel es de (l), o longitud del
cromosoma.
Figura 2.1 Hill Climbing de combinación de un grado por nivel nodal (HC1)
Fuente: El autor.
El método realiza en algunos de los agentes una exploración de mayor profundidad, en la
que se cambian dos genes para pasar a una solución vecina a dos dimensiones o grados
de distancia. A esto lo denominamos combinación de dos grados por nivel nodal. Sigue
explorándose aquella rama que presenta la mayor mejoría, y termina cuando no se
30
encuentre una mejor rama. Esto supone que el número de combinaciones exploradas por
nivel es de (l2), o el cuadrado de la longitud del cromosoma.
Debido al consumo de recurso computacional que requiere esta exploración, se debe ser
cuidadoso con el número de individuos o agentes a los que se le aplica, pues de lo contrario
el algoritmo puede llegar a perder eficiencia en tiempo. En el método propuesto se planteó
aplicar la exploración de dos grados a un porcentaje de individuos con los mejores puntajes,
pero dependiendo de su separación respecto del mejor, con el objetivo de explorar en zonas
dispersas, incentivando la diversidad poblacional. Análisis más adelante.
Figura 2.2 Hill Climbing de combinación de dos grados por nivel nodal (HC2)
Fuente: El autor.
2.2.4. OBJETIVO ESPECIFICO 4
Proponer indicadores de eficiencia en la aplicación de la búsqueda local orientada a
nichos, de forma tal que permitan una auto-adaptación del algoritmo en tiempo de
ejecución. Dichos indicadores darán la retroalimentación para ajustar los operadores
y/o parámetros del algoritmo.
Dentro de la exploración de la búsqueda local se proponen como indicador y orientador de
la búsqueda adaptativa un parámetro de puntaje o fitness2 alternativo como complemento
al puntaje “real”; este fitness2 dará un valor diferente de cero a soluciones infactibles
31
utilizando un método de ajuste propuesto, el cual tiene inspiración en la metodología de
(Olsen, 1994). Dicho parámetro se ajustará dentro del operador de evaluación.
También se propone como indicador del estado de búsqueda la distancia Hamming (Wang,
Wang, & Yang, 2009) , poblacional promedio de los agentes o soluciones con respecto al
individuo u agente de mayor puntaje o fitness, como forma de diferenciación de nichos en
la población (ver Marco Teórico sección 2.7). Con base en este indicador se ejecutara una
búsqueda local de mayor o menor profundidad.
2.2.4.1. ADAPTACIÓN BASADA EN INDICADOR FITNESS COMPLEMENTARIO EN EL
OPERADOR DE EVALUACIÓN:
En los GA el operador de evaluación se encarga de calcular la aptitud o fitness del individuo
mediante una función de adaptación; también se calcula la probabilidad de selección y
probabilidad acumulada de selección, información que será utilizada por el operador de
selección. La evaluación en el presente algoritmo va más allá de calcular el valor generado
por el cromosoma del individuo.
En el algoritmo propuesto se evalúa un puntaje de adaptación adicional o fitness2 para
agentes de cromosoma no factible. También se calcula la distancia del cromosoma del
agente respecto del mejor agente, dato que ayuda a estimar la diversidad poblacional.
Adaptación de agentes de solución no factible: Normalmente dentro de los GA y los MA a
los individuos infactibles se les asigna como puntaje de penalización 0 (cero). Esto implica
que la exploración estará limitada al espacio factible, por lo que la aproximación contará
con una desventaja natural. Algunos autores han propuesto no penalizar en extremo a las
soluciones infactibles, e incluso se han realizado estudios comparativos de dichas técnicas
(Alfonso, Bermúdez, & Stark, 2001).
Una de los métodos de penalización de mayor efectividad mostrada es el de Olsen, el cuál
no sólo penaliza a los individuos que violan restricciones, sino también a aquellos que
“desperdician” el espacio de la mochila (Olsen, 1994). El cálculo de fitness que propuso se
calcula así:
32
2.2)���4*'5��) = �) ��+��
��∗ 6"���)
�2.3)���6"���) = 1 − 8 +��� − -��� 89
2.4)����9 = min�{-, >) +��� − -�
��>}
En (Michalewicz & Dasgupta, Evolutionary algorithms for constrained engineering problems,
1996) se propuso como penalización al fitness: �1)�4*'5��) = � ��+���� − 6"���) donde
Pen(x) puede ser una función lineal, cuadrática o logarítmica, y cuyo valor será cero en
individuos factibles.
Como ya se ha mencionado, el comportamiento de los algoritmos evolutivos actuales
ranquea las soluciones factibles por encima de las infactibles en su totalidad, por lo que
realizan una aproximación por los límites factibles del espacio de búsqueda. Se han
realizado trabajos en los que una fracción de la población deberá estar conformada por
soluciones infactibles, manteniendo la población separada en dos grupos, el factible y el
infactible. Esta innovación opera en la fase de cooperación, ya que soluciones de dichos
grupos pueden combinarse generando nuevos individuos, tanto factibles como infactibles,
aproximándose así al óptimo (Singh, Isaacs, Ray, & Smith, 2008).
Tratamiento a soluciones no factibles propuesto: Para mantener la filosofía de realizar la
búsqueda por los espacios tanto factibles como infactibles, es necesario dar un puntaje
diferente de cero a las soluciones infactibles, pero en un fitness alterno; para esto se
propone el siguiente razonamiento. Establecemos cuantas unidades promedio el
cromosoma infactible se pasa del límite de peso (Fig 2.2) estimando así el sobrepaso.
2.5)���@" = +� − -AB3A�� CDEDFG
�
33
Siendo ue el número de unidades en exceso de la solución actual, calculado como la
relación entre la diferencia entre el peso de las m unidades w de la solución y el peso
máximo Wmax, sobre el peso promedio de una unidad del total de n unidades.
Figura 2.3 Unidades promedio en exceso
El valor promedio del exceso ve se calcula multiplicando las unidades promedio de exceso
por el valor promedio por unidad (Suma de los valore v sobre el número de unidades n):
2.6)���*" = @" ∗ *�����
El fitness2, que es el que nos interesa como indicador de aptitud, se calcula restándole al
fitness que tendría la solución si fuera factible (al ser infactible su aptitud real será cero) el
valor promedio de exceso:
2.7)���J K�"��2 = J K�"�� − *"
En esencia, el fitness2 representa la potencial aptitud que podría tener el individuo si
eliminara las unidades que posee en exceso. Este valor no es utilizado por el algoritmo
propuesto durante el proceso de selección, sino, durante el proceso de mejoramiento
individual, o búsqueda local (ver sección 3.5.), con el objetivo de aproximar también por el
espacio infactible.
34
Figura 2.4 La búsqueda por espacio infactible puede mejorar la eficiencia
2.2.4.2. ADAPTACIÓN BASADA EN INDICADOR HAMMING PARA DIVERSIDAD
POBLACIONAL
Es sustancial para la eficiencia del algoritmo de búsqueda local, utilizar una heurística
adecuada con conocimiento del problema (Hart & Krasnogor, Recent Advances in Memetic
Algorithms., 2004) (Ong, Lim, & Zhu, Classification of adaptive memetic algorithms: A
comparative study, 2006), pero aún igual o más importante, escoger correctamente en que
momento y a que individuos o agentes se le debe aplicar la mejora por LS en el proceso de
exploración.
No usar en toda la población la búsqueda local, sino únicamente sobre algunas soluciones
seleccionadas aleatoriamente, o en función de su calidad, o bien según algún otro criterio,
es lo que se conoce como lamarckismo parcial (Cotta C. , 2005) (Houck, Joines, Kay, &
Wilson, 1997). También cuenta la intensidad del aprendizaje, o sea durante cuánto tiempo
o que complejidad debe tener la fase de aprendizaje individual (Sudholt, 2012).
Como ya se expuso en la sección 1.8, la diversidad poblacional es clave para que la
búsqueda local aumente su efectividad, las soluciones sobre las que se aplique deben
pertenecer en lo posible en diferentes zonas del espacio de soluciones, así como tener una
calidad razonable. Es por eso que se han realizado propuestas como el Algoritmo Memético
Equilibrado con Diversificación Voraz (AMEDV), el cuál añade diversidad a la población en
35
caso de que sea necesario, sustituyendo aquellas soluciones que verifiquen determinado
criterio de semejanza con otras de la población por nuevos cromosomas generados por un
algoritmo voraz aleatorizado (Herrera & Herrera, 2015).
Por lo tanto, en los MA la diversidad poblacional se puede utilizar como medida para
seleccionar y activar los memes más apropiados (Caponio, Cascella, Neri, & Salvatore,
2007), coordinando los memes para que exista un balance entre diversidad y convergencia
local.
En concordancia con lo anterior, el algoritmo desarrollado busca propender por la búsqueda
en diferentes sectores del espacio de soluciones, por lo que se experimentó su aplicación
con la búsqueda local (LS) de la siguiente forma:
En el operador de evaluación (ver sección 2.4.1.), se calcula previamente para todos los
agentes de la población, la distancia Hamming ya vista en la sección 1.8. En esencia su
aplicación es igual para cromosomas binarios, enteros o reales, pero para cromosomas
binarios se aplica contabilizando el número de genes diferentes por posición entre los dos
cromosomas a comparar. De este modo, entre el cromosoma 01010101 y 00001111 hay
una distancia de 4 bits, genes o unidades (Fig 2.4). Este dato es guardado por el agente.
Figura 2.5 Distancia Hamming entre cromosomas
36
Posteriormente, la exploración LS Hill Climbings de un grado de profundidad por nivel nodal
se aplica a toda la población, mejorando en los agentes factibles el fitness y en los
infactibles el fitness2 (ver sección 2.4.1). El hecho de incluir a los no factibles de la población
incentiva la diversidad.
2.2.5. OBJETIVO ESPECIFICO 5
Desarrollar el Algoritmo Memético auto-adaptativo basado en los indicadores para
adaptación y ajuste propuestos, que muestre mejoras respecto al GA y MA básicos.
MA AUTO-ADAPTATIVO PROPUESTO
DESCRIPCIÓN GENERAL DEL ALGORITMO
El Algoritmo Memético propuesto utiliza los elementos estándar de los Algoritmos Genéticos
para los procesos de cooperación y competencia entre agentes. El método de Búsqueda
Local que utiliza es el Hill Climbing tipo Greedy, nombrado en la sección 1.5., con capacidad
de búsqueda por nivel nodal de uno y dos grados o dimensiones de combinación en
profundidad. La aplicación de dicho LS sobre los agentes se realiza en forma adaptativa
teniendo como variable de control el nivel de diversidad poblacional usando como indicador
la distancia promedio al agente de mejor aptitud o fitness.
37
Figura 2.6 Diagrama de Flujo del MA propuesto
Fuente: El autor.
Operador para generación de la Población Inicial
Para la población inicial de un MA normalmente se intenta utilizar soluciones de alta calidad
como punto de partida. Esto puede hacerse utilizando un mecanismo sofisticado (por
ejemplo, una heurística constructiva) para inyectar buenas soluciones en la población inicial
(Surry & Radcliffe, 1996). También suele usarse un procedimiento de búsqueda local para
mejorar las soluciones iniciales, las cuales se generan aleatoriamente (Back & Hoffmeister,
Adaptive search by evolutionary algorithms, 1991).
Dentro de las pruebas algorítmicas realizadas se evidencio la importancia de generar por
lo menos dos o tres agentes de configuración cromosómica factible en la población inicial,
ya que esto evita el degeneramiento prematuro de la población en individuos infactibles
incapaces de generar nuevos individuos factibles. Así mismo, también se verificó la
38
importancia de mejorar a los agentes factibles a insertar en la población inicial, como lo
sugirieron los anteriores autores citados, y otros (Diaz & Hougen, 2007).
Debido al tiempo de ejecución extra que mostró el generar soluciones factibles para la
primera población, se decide utilizar una ventaja propuesta para el operador de búsqueda
local en el presente trabajo: fitness2 o puntaje complementario, utilizándolo en las
soluciones infactibles durante el proceso u operador de selección (ver sección 2.2.4.1.),
pero sólo para las poblaciones iniciales, de modo tal que dicho método ayude a la población
a evolucionar a soluciones factibles rápidamente. Es de recordar que dicho indicador
fitness2 es utilizado exclusivamente por el operador de búsqueda local (ya no por el
operador de selección), después de que la población alcanza soluciones factibles.
El tamaño de la población empleado es como mínimo de diez veces la longitud del
cromosoma (10l), según lo estima la teoría (Alander, 1992).
Operadores de Selección, Cruce y Mutación:
Los procesos de selección, cruce y mutación utilizados serán los mismos usados en el GA
básico (ver sección 2.2.2). El método de selección utilizado fue por ruleta. La probabilidad
de selección usada en todas las pruebas fue de 0.4 con un porcentaje de población elite de
2%. Para el operador de cruce se empleó la técnica monopunto con punto de inicio
aleatorio. La probabilidad de mutación se varió respecto al GA básico y se incrementó a
0.01 de ocurrencia (lo habitual es 0.001). La razón es que el algoritmo LS utilizado incide
también sobre la población infactible como ya se mencionó en la sección 2.2.4.1., lo que
aliviana el degeneramiento poblacional ocasionado por la mutación y permite incrementar
la diversidad poblacional.
Operadores de Búsqueda Local:
La aplicación del LS sobre los agentes se realiza en forma adaptativa teniendo como
variable de control el nivel de diversidad poblacional; para cuantificar este nivel se usa como
indicador la distancia Hamming promedio poblacional al agente de mejor aptitud o fitness;
39
En los agentes infactibles dicha distancia se calcula con base en el fitness2 o
complementario de la sección 2.2.4.1.
La exploración LS Hill Climbing de un grado de profundidad por nivel nodal se aplica a toda
la población en cada nueva generación, mejorando en los agentes factibles el fitness y en
los infactibles el fitness2. El hecho de incluir a los no factibles de la población incentiva la
diversidad.
El método Hill Climbing a dos grados de profundidad por nivel nodal se aplica a los agentes
o individuos clave (de importancia en la eficiencia como ya se mencionó); para esto se
aplica dicho LS sobre los mejores ε*cl, siendo ε la distancia promedio al mejor agente
o individuo en la respectiva generación (ver ecuación 1.2) y cl o coeficiente de longitud,
que es un coeficiente para calcular el número de individuos seleccionados; se experimentó
seleccionando individuos que adicional a cumplir con la condición anterior, también tuviesen
una distancia Hamming al mejor individuo mínimo de ε*cr, siendo cr un coeficiente radial;
se aplica con agentes o individuos factibles e infactibles, de forma tal que se favorezca la
búsqueda en zonas lejanas a la zona de la mejor solución actual, o sea espacios con baja
probabilidad de explorarse en la etapa evolutiva.
Figura 2.7 Espacio de candidatos a mejora HC2 dos grados de profundidad nodal.
40
3. RESULTADOS
3.1. RESPONDIENDO LA PREGUNTA DE INVESTIGACION
¿Qué operadores y/o parámetros en el MA podemos variar dinámicamente y en forma
auto-adaptativa durante la ejecución de la exploración, así como también sobre que
agentes aplicamos dicha auto-adaptación, para mejorar los resultados obtenidos de
dicha búsqueda y/o mejorar su eficiencia?
Las variaciones propuestas en el operador de búsqueda y sus parámetros (ver sección
2.2.5), específicamente el nicho de agentes o individuos a quienes se les aplica la búsqueda
local LS, así como el tipo de LS a aplicar, profundo con HC2 o superficial con HC1, se ponen
a prueba con el Algoritmo Memético autoadaptativo.
Se varía dinámicamente el número de agentes o individuos a quienes se les aplica la
búsqueda intensiva o HC de dos grados de profundidad nodal, ya que aplicarla a muchos
agentes tiende a incrementar el recurso computacional, pero por otra parte aplicarla a pocos
tiende a perder capacidad de exploración; para esto se les aplica como parámetro en cada
generación la multiplicación de la distancia haming promedio al mejor agente (ε) por un
coeficiente radial (cr) de variación de 0 a 1, para establecer el radio de espacio de acción
de individuos o agentes a quiénes se les aplica la LS o búsqueda intensiva o HC2 de dos
grados de profundidad nodal; dicha búsqueda se aplica a agentes tanto factibles como
infactibles que estén por fuera de esta distancia. A los agentes por dentro de este radio sólo
se les aplica una búsqueda HC1 de un grado de profundidad nodal. La razón es que
aquellos agentes o individuos que estén más alejados del mejor agente, tenderán a estar
más alejados del óptimo local actual, por lo que podría valer la pena explorar dichas
regiones con otros posibles óptimos locales.
No sólo se experimenta con aplicar búsqueda profunda a nichos basados en la distancia al
mejor actual, sino también se varía el porcentaje de agentes a quienes se les aplica la
búsqueda profunda o HC2 utilizando un coeficiente de longitud cl; Este coeficiente se varía
entre 0,2 y 1,2. Dicha búsqueda HC2 se les aplicará a los ε*cl agentes más prometedores,
por lo que en generaciones más tempranas cuando hay poca convergencia en la distancia
41
promedia al mejor o ε, o sea mayor dispersión de la población, la búsqueda profunda se le
aplicará a un mayor número de agentes prometedores, número que disminuirá con cada
nueva generación.
Por último, se experimenta con las variaciones anteriores aplicando el HC1 a toda la
población en cada nueva generación, y sin aplicar el HC1 a agente alguno en ninguna de
las generaciones, sólo realizando las respectivas búsquedas HC2.
En todas las mediciones que se realizan en las corridas del MA autoadaptativo se
implementa la inclusión del fitness2 como indicador adicional para infactibles durante la LS
o Búsqueda Local, lo cual se convirtió en núcleo de la búsqueda autoadaptativa del presente
trabajo.
3.2.1. PRUEBAS HILL CLIMBING GRADO 2 Y GRADO 1
El problema de prueba es el de la mochila con 120 grados de libertad. El método de
aplicación de los dos tipos de HC debe escoger a cuáles y cuantos individuos se les
aplicara. Los coeficientes previamente expuestos nos permiten esto. Para verificar cuáles
son los coeficientes más apropiados, se realizaron las pruebas combinando los posibles
coeficientes para el número de elementos a aplicar el HC2 (grado dos por nivel de
profundidad), el radio mínimo de distancia al mejor para aplicar el HC2; y si se aplica o no
HC1 (grado uno por nivel de profundidad) a toda la población:
42
Tabla 3.1 Se probaron todas las combinaciones (242 posibles) de los tres parámetros
Por ejemplo una combinación sería: Se aplica HC1 + Cr: 0,05 + Cl: 0,4.
El número de muestras tomadas (corridas) para cada una de las combinaciones es de 52.
Se calcula utilizando la prueba estadística paramétrica asumiendo distribución normal con
un nivel de confianza del 95% y un error máximo permitido de 5%. Se utiliza el promedio
de las mismas para el análisis de los datos.
Gráfico 3.1 Los coeficientes más bajos (radio tiende a cero) dieron menores tiempos
Se aplicó HC1 a toda la población
Coeficiente Cr
Para distancia mínima al mejor
0,01 0,05 0,1 0,15 0,2 0,25 0,3 0,35 0,4 0,45 0,5
Coeficiente Cl
Para número de individuos
seleccionados 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 1,1 1,2
SI NO
0
50000
100000
150000
200000
250000
300000
350000
400000
450000
500000
0 0,1 0,2 0,3 0,4 0,5 0,6
Dispersión cr vs tiempo
43
Gráfico 3.2 El incluir un radio mínimo de aplicación no parece influir en la diversidad
Gráfico 3.3. El coeficiente cl =0.4 dio los menores tiempos de ejecución
0
10.000.000
20.000.000
30.000.000
40.000.000
50.000.000
60.000.000
70.000.000
0 0,1 0,2 0,3 0,4 0,5 0,6
Dispersión cr vs ε
0
50000
100000
150000
200000
250000
300000
350000
400000
450000
500000
0 0,2 0,4 0,6 0,8 1 1,2 1,4
Dispersión cl vs tiempo
44
Gráfico 3.4. La aplicación de HC1 a toda la población es más consistente
Respondiendo a la pregunta de investigación:
Se concluye que el algoritmo NO debe incluir como parámetro un radio mínimo dinámico
respecto al mejor individuo (cr) para selección de candidatos a HC2, pues esto no garantiza
diversidad, y si empeora la eficiencia.
Se concluye que el parámetro coeficiente a multiplicar por el promedio dinámico de
diversidad poblacional (ε*cl) para el número de seleccionados para el HC2 por generación
es conveniente introducirlo y con valor de 0.4, lo que mostró los mejores resultados.
Se concluye que aplicar HC1 a toda la población en cada generación mejora la eficiencia.
El seudocódigo del MA Autoadaptativo quedaría así: EvaluarPoblación(poblacion); //Fitness –Fitness2 - ε
for 1 to totalpoblacion do MejoraLocal HC1(Individuo); end selecciona_individuos(0.4*ε); //Selecciona los 0.4*ε mejores de la población
for 1 to 0.4* ε do
MejoraLocal HC2(Individuo); end
0
50000
100000
150000
200000
250000
300000
350000
400000
450000
500000
0 0,2 0,4 0,6 0,8 1 1,2
1- Se aplica 0-No se aplica
45
3.3. REPONDIENDO A LA HIPÓTESIS
En el Algoritmo Memético (MA), la búsqueda autoadaptativa que ajusta operadores
y/o parámetros en la exploración, tenderá a disminuir el tiempo de búsqueda
encontrando soluciones tan buenas o mejores que los GA’s y MA’s básicos, a pesar
del recurso computacional extra que dicha autoadaptación pueda implicar.
3.3.1. ALGORITMO MA ADAPTATIVO vs LOS BASICOS
El algoritmo MA autoadaptativo se puso a prueba frente a los siguientes algoritmos básicos:
• Algoritmo Genético simple.
• Algoritmo Memético Hill Climbing grado 1 a toda la población con aproximación
exclusiva por espacio factible.
• Algoritmo Memético Hill Climbing grado 1 a toda la población con aproximación por
espacio factible e infactible.
El problema de prueba es el de la mochila con 120 grados de libertad. La muestra o número
de corridas utilizadas para todos los algoritmos fue de 47. Para estimar el número de
corridas necesarias para cada algoritmo se empleó la prueba estadística paramétrica
asumiendo distribución normal, con un nivel de confianza del 95% y un error máximo
permitido de 5%. Los resultados son los siguientes:
Gráfico 3.5. Algoritmo GA simple. Le tomó 300 generaciones y 75.441 miliseg promedio.
Óptimo promedio alcanzado: 17.949.
0
5000
10000
15000
20000
0 50 100 150 200 250 300 350
Algoritmo Genético Simple
46
Gráfico 3.6. Algoritmo MA simple. Le tomó 300 generaciones y 446.707 miliseg promedio.
Óptimo promedio 18.605.
Gráfico 3.7. Algoritmo MA HC grado uno con aproximación sólo por espacio factible
0
2000
4000
6000
8000
10000
12000
14000
16000
18000
20000
0 50 100 150 200 250 300 350
Algoritmo Memético Simple
0
2000
4000
6000
8000
10000
12000
14000
16000
18000
20000
0 2 4 6 8 10 12 14
Algoritmo MA HC1
47
Tabla 3.2 El MA con HC1 Alcanza el óptimo global en 13 generaciones promedio.
Generaciones Generaciones
sin cambios
Distancia
Promedio al
mejor: ε
Fitness Tiempo en
milisegundos
1 0 61.876667 12859 36.862
2 0 43.721561 18411 37.518
3 1 43.683102 18411 38.875
4 2 42.821404 18411 40.185
5 3 40.624016 18411 41.698
6 4 37.913853 18411 43.180
7 5 33.722427 18411 44.694
8 6 28.995602 18411 46.285
9 0 24.504997 18414 47.907
10 1 22.447086 18414 49.592
11 2 18.553705 18414 51.417
12 0 16.701296 18430 53.055
13 0 13.368917 18432 54.709
Gráfico 3.8. Algoritmo MA HC grado uno con aproximación por espacio factible e infactible
0
2000
4000
6000
8000
10000
12000
14000
16000
18000
20000
0 2 4 6 8 10 12 14
Algoritmo MA con aproximacion por espacio
infactible
48
Tabla 3.2 El MA autoadaptativo alcanza el óptimo global en 5 generaciones promedio.
Generaciones Generaciones
sin cambios
Distancia
Promedio
al mejor: ε
Fitness Tiempo en
milisegundos
1 0 58.953335 17920 36.987
2 1 4.152461 17920 38.173
3 0 13.120127 18411 39.998
4 1 12.954267 18411 42.260
5 0 12.772462 18432 44.163
Gráfico 3.8. Algoritmo MA autoadaptativo con HC grados uno y dos.
Respondiendo la hipótesis de investigación:
Los algoritmos en orden de eficiencia (velocidad de respuesta y calidad de la misma) de
mayor a menor rendimiento quedan así:
Algoritmo MA autoadaptativo con aproximación por espacio factible e infactible.
Algoritmo MA HC grado uno con aproximación por espacio factible e infactible.
Algoritmo MA HC grado uno con aproximación sólo por espacio factible.
Algoritmo GA simple.
17600
17700
17800
17900
18000
18100
18200
18300
18400
18500
1 2 3 4 5
Algoritmo MA autoadaptativo
49
4. CONCLUSIONES
La expectativa de la presente investigación se centraba en la capacidad de auto-adaptarse
del algoritmo memético como técnica que lo hiciera más eficiente; sin embargo la
innovación más importante resulto ser la creación de un segundo fitness o aptitud para los
agentes; un puntaje adaptativo que indica para las soluciones no factibles cuál sería su
valor si se convirtiera en una solución factible. Esta segunda aptitud permite el
mejoramiento de estos agentes sin ignorarlos como suele pasar con la gran mayoría de
métodos, pero sin entorpecer el mejoramiento de los factibles como ocurre cuando se
unifican en un solo valor fitness para factibles e infactibles. Este aporte permite el
aproximarnos por el espacio factible e infactible al óptimo, mejorando en buena medida la
eficiencia.
En cuanto a la autoadaptación, se investigó el efecto de la aplicación de una exploración
más profunda con Hill Climbing de dos grados de exploración por nivel nodal (HC2) con el
número de individuos y el tipo variando adaptativamente respecto al grado de convergencia
de la población. Se observó que seleccionar los mejores individuos más lejanos con una
distancia mínima al individuo óptimo, no contribuye a la diversidad poblacional, y además
termina siendo ineficiente en la búsqueda convergente.
También se observó que la cantidad de individuos seleccionados para aplicar HC2 puede
ajustarse a un factor de 0.4 veces la distancia promedio de la población respecto al mejor
individuo, o 0.4ε. Si se aumenta este factor en exceso se incrementarán los cálculos
necesarios para la búsqueda aumentando así el tiempo de ejecución; pero al disminuirlo,
baja el nivel de exploración, lo que resiente la calidad de la búsqueda. Por lo tanto, el
número de individuos a explorarse es adaptativo a la diversidad poblacional.
Es importante plantear la posibilidad para futuros trabajos la inclusión de tablas hash o
estructuras de datos de matriz asociativa, las cuales permiten referenciar aquellas
soluciones que ya se han explorado en profundidad para no perder tiempo computacional
re-explorándolas (Joyanes & Zahonero, 2004). En dichas tablas la ubicación de soluciones
ya exploradas debe ser un proceso mucho más rápido que el proceso de exploración nodal
para búsqueda local, de esta manera mejorando la eficiencia global del algoritmo. Esto se
50
puede lograr mediante el uso de la aptitud de la respectiva solución como llave para su
referenciación en la tabla hash, con pocas colisiones esperadas.
51
REFERENCIAS
Cotta, C. (2007). Una Visión General de los Algoritmos Meméticos. University of Málaga, 1-
21.
Aarts, E., & Lenstra, J. K. (2003). Local search in combinatorial optimization. Eindhoven y
Atlanta: Princeton University Press., 1-137.
Alander, J. (1992). On optimal population size of genetic algorithms. Proceedings
CompEuro, Computer Systems and Software Engineering, 6th Annual, (págs. 65-
70).
Alfonso, H., Bermúdez, C., & Stark, N. (2001). Análisis Comparativo de Diferentes
Soluciones Alternativas para el Problema de la Mochila. Universidad Nacional de La
Plata, Argentina.
Araujo, L. &. (2009). Algoritmos evolutivos: un enfoque práctico. Madrid, España: RA - MA.
Back, T., & Hoffmeister, F. (1991). Adaptive search by evolutionary algorithms. Models of
Self-organization in Complex Systems. Mathematical Research. Akademie-Verlag,
17–21.
Back, T., & Schutz, M. (1996). Intelligent mutation rate control in canonical genetic
algorithms. (págs. 158-167). Zakopane, Polonia: in Proc. 9th Int. Symp. (ISMIS ’96).
Back, T., Fogel, D., & Michalewicz, Z. (1997). Handbook of Evolutionary Computation (Vol.
64). Oxford: University Press.
Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and
conceptual comparison. ACM Computing Surveys(35 (3)), 268-308.
Brady, R. (1985). Optimization Strategies Gleaned from Biological Evolution. (317), 804-
806.
Caponio, A., Cascella, G., Neri, F., & Salvatore, N. (2007). Afast adaptative memetic
algorithm for on_line control design of pmsm drives. IEEE Transactions on Systems
Man and Cybernetics Part B, Special Issue onMemetic Algorithms, 37(1), 28-47.
Cerny, V. (1985). A thermodynamical aprroach to the traveling salesman problem. ournal of
Optimization, theory and Application, 45(1), 41–51.
Cortez, A. (2004). Teoría de la complejidad computacional y teoría de la computabilidad. .
Rev. investig. sist. inform. Universidad Nacional Mayor de San Marcos, 102-105.
52
Cotta, C. (2005). Memetic algorithms with partial lamarckism for the shortest common super-
sequence problem. Artificial Intelligence and KnowledgeEngineering Applications: a
Bioinspired Approach, 84-91.
Davidor, Y., & Ben-Kiki, O. (1992). The interplay among the genetic algorithm operators:
Information theory tools used in a holistic way. ParallelProblem Solving From Nature
II, Amsterdam, Elsevier Science Publishers B.V., 75-84.
Davis, L. (1991). Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold.
Dawkins, R. (1976). The Selfish Gene. Oxford: Clarendon Press.
Deb, K., & Goldberg, D. (1989). An investigation of niche and species formation in genetic
function optimization. (págs. 42-50). San Mateo, CA: Proc. 3rd Int. Conf. Genetic
Algorithms.
Díaz, A., Glover, F., Ghaziri, H., Gonzalez, J., Laguna, M., Moscato, P., & Tseng, F. (1996).
Optimización Heurística y Redes Neuronales. Madrid: Paraninfo.
Diaz, P., & Hougen, D. (2007). Initial Population for Genetic Algorithms: A Metric Approach.
School of Computer Science University of Oklahoma Norman USA.
Eiben, A., Hinterding, R., & Michalewicz, Z. (1999). Parameter control in evolutionary
algorithms. . IEEE Trans Evol Comput 3(2), 124–141.
Fischetti, M., & Lodi, A. (2003). Local branching. Mathematical Programmming 98 , 23–47.
Fogel, L., & Angeline, P. (1995). A preliminary investigation on extending evolutionary
programming to include self-adaptation on finite state machines. Informatica, 18,
387-398.
Glover, F., & Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers.
Goldberg, D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning.
MA: Addison-Wesley.
Goldberg, D., & Richardson, J. (1987). Genetic algorithms with sharing for multimodal
function optimization. (págs. 41-49). SecondInternational Conference on Genetic
Algorithms and Their Applications.
Hart, W. (1994). Adaptative Global Optimization with Local Search. San Diego: Ph.D.
dissertation, Univ. California.
Hart, W., & Krasnogor, N. (2004). Recent Advances in Memetic Algorithms. Heidelberg:
Springer-Verlag.
53
Herrera, A., & Herrera, F. (2015). Algoritmo genéticoequilibrado condiversificaciónvoraz.
Congreso de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados MAEB, 10,
págs. 9-18. España.
Holland, J. (1975). Adaptation in Natural and Artificial Systems. University of Michigan
Press.
Houck, C., Joines, J., Kay, M., & Wilson, J. (1997). Empirical investigation of the benefitsof
partial lamarckianism. Evolutionary Computation 5, 31-60.
Hulin, M. (1997). An optimal stop criteria for genetic algorithms: A Bayesian approach.
Proceedings of the Seventh International Conference on Genetic Algorithms, (págs.
135–143). San Mateo, CA. USA.
Joyanes, L., & Zahonero, I. (2004). Algoritmos y estructuras de datos. Madrid: McGraw-Hill.
Karp, R. (1972). Reducibility Among Combinatorial Problems. Complexity of Computer
Computations. Nueva York: Plenum, 85-103.
Klein, P., & Young., N. (2009). Algorithms and theory of computation handbook. Tomo 1,
cap. 34. Londres: Chapman & Hall/CRC.
Krasnogor, N. (2002). Studies on the Theory and Design Space of Memetic Algorithms.
Bristol, U.K.: Ph.D. dissertion, Faculty Comput., Math. Eng., Univ.West.
Lawler, E. L., Lenstra, J. K., & Rinnooy, A. H. (1985). The Traveling Salesman Problem: A
Guided Tour of Combinatorial Optimization. John Wiley & Sons.
Leeuwen, J. v. (1998). Handbook of Theoretical Computer Science. Vol. A, Algorithms and
complexity. Amsterdam: Elsevier.
Magyar, G., Johnsson, M., & Nevalainen, O. (2000). An adaptive hybrid genetic algorithm
for the three-matching problem. 4.
Martí, R. (2003). Procedimientos Metaheurísticos en Optimización Combinatoria. Valencia,
España.: Universidad de Valencia.
Michalewicz, Z. (1992). Genetic Algorithms + Data Structures = Evolution Programs. Berlin:
Springer-Verlag.
Michalewicz, Z., & Dasgupta, D. (1996). Evolutionary algorithms for constrained engineering
problems. Computers & Industrial Engineering, 30(4), 851-870.
Michalewicz, Z., & Janikow, H. C. (1991). Constraints in Genetic Algorithms. Fourth
International Conference on Genetic Algorithms, (págs. 151 - 157).
Moscato, P. (1989). On Evolution, Search, Optimization, Genetic Algorithms and Martial
Arts: Towards Memetic Algorithms.
54
Moscato, P., & Cotta, C. (2003). An Introduction to Memetic Algorithms. (19), 131-148.
Neri, F., Cotta, C., & Moscato, P. (2012). Handbook of Memetics Algorithms. Berlin:
Springer-Verlag.
Neri, F., Toivanen, J., Cascella, G., & Ong, Y. (2007). An adaptive multimeme algorithm for
designing HIV multidrug therapies. IEEE/ACM Transactions on Computational
Biology and Bioinformatics, 4(2), 264–278.
Nogueras, R., & Cotta, C. (2015). Algoritmos Meméticos con Propiedades Self-* para la
Optimización de Problemas Complejos. Malaga: Tesis Doctoral. Universidad de
Málaga.
Olsen, A. (1994). Penalty Functions and the Knapsack Problem. IEEE First Conference on
Evolutionary Computation, (págs. 554-558). Orlando.
Ong, Y., & Keane, A. (2004). Meta Lamarckian Lerning in Memetics algorithms. IEEE
Transactions on Evolutionary Computation, 8, 99-110.
Ong, Y., Lim, M., & Zhu, N. (2006). Classification of adaptive memetic algorithms: A
comparative study. IEEE Trans. Syst.,Man, Cybern. B, Cybern.36, no. 1, 141-152.
Osman, I. &. (1996). Meta - Heuristics: Theory and Applications. Boston: Kluwer Academic.
Papadimitriou, C. (1994). Computational Complexity. Addison-Wesley.
Pétrowski, A. (1996). A clearing procedure as a niching method for genetic algorithms.
(págs. 798-803). Japan: In Proc. IEEE International conference on evolutionary
computation.
Rafael , M., & Laguna, M. (2005). Scatter Search: Diseño Básico y Estrategias Avanzadas.
Rosas, M., & Leiva, H. (2000). Técnicas de Niching: Estrategias Evolutivas vs. Algoritmos
Genéticos. Universidad Nacional de San Luis. Argentína.
Sait, S. M., & H., Y. (1999). Iterative computer algorithms with applications in engineering:
Solving combinatorial optimization problems. . IEEE Computer Society Press, 1-248.
Sareni, B., & Laurent, K. (1998). Fitness Sharing and Niching Methods Revisited. 2(3).
Singh, H. K., Isaacs, A., Ray, T., & Smith, W. (2008). Infeasibility Driven Evolutionary
Algorithm (IDEA) for Engineering Design Optimization. 21st Joint Australiasian
Conference on Artificial Intelligence AI-08, (págs. 104–115). Australia.
Smith, J., & Fogarty, T. (1997). Operator and parameter adaptation in genetic algorithms.
Soft Computing, 1(2), 81–87.
55
Sudholt, D. (2012). Parametrization and balancing local and global search. En F. Neri, C.
Cotta, & P. Moscato, Handbook of Memetic Algorithms ,tomo 379 de Studies in
Computational Intelligence (págs. 55-72). Berlin: Springer-Verlag.
Surry, P., & Radcliffe, N. (1996). Inoculation to initialise evolutionary search. In: Fogarty,
T.C. (ed.) AISB-WS. LNCS, Springer, Heidelberg, 1143, 269-285.
Tovey, C. A. (2002). Tutorial on computational complexity. . Interfaces, vol. 32 No. 3, 30-61.
Vélez, M., & Montoya, J. (2007). Metaheurísticos: una alternativa para la solución de
problemas combinatorios en administración de operaciones. Escuela de Ingeniería
de Antioquia(8), 99-115.
Wang, H., Wang, D., & Yang, S. (2009). A memetic algorithm with adaptive hill climbing
strategy for dynamic optimization problems. Soft Comput, 13, 763–780.
Wolpert, D., & Macredy, W. (1997). No Free Lunch Theorems for Optimization. IEEE
Transactions on Evolutionary Computation, 1, 67-82.
56
ANEXO: CODIGO C++ Algoritmo Memético Autoadaptativo
//Problema de la mochila //Carga la información de un archivo datos.txt con datos separados con coma //Cargará tantos datos como génes (lcrom) para pesos y utilidades /***********************************************/ //ALGORITMO MEMETICO //Utiliza la aptitud2 para mejorar las primeras poblaciones durante la selección //Local Search HILL CLIMBING de uno y dos grado de profundidad por nivel en forma selectiva //Incorpora la distancia Hamming en cada individuo respecto al actual mejor //Utiliza la aptitud2 durante la búsqueda local HC1 y HC2 /***********************************************/ #include <iostream> #include <time.h> using namespace std; //Variables Globales int lcrom; //Largo del cromosoma int tam_pob; //Tamaño de la población int peso_max; //Peso máximo en una solución factible int* vec_peso; //Vector de pesos int* vec_utilidad; //Vector de utilidades float prob_cruce; //Probabilidad de cruce float prob_mut; //Probabilidad de mutación float pesoprom; //Peso promedio de una unidad float utilprom; //Utilidad o valor promedio de una unidad int sumapesos; //Peso total de las unidades int sumautilidades; //Utilidad total de las unidades int generaciones; //Contador de generaciones float mejoractual; //Valor o fitness del mejor individuo en la actual generación float mejoranterior; //Valor o fitness del mejor individuo en la anterior generación float cl; //coeficiente (cl) * promedio distancia al mejor = número de individuos seleccionados para HC2 //Estructura de cada solución, agente o individuo struct TIndividuo { int genes[120];//NUMERO DE GENES float peso; float aptitud; //Funcion de evaluacion float aptitud2; //Aptitud o fitness alternativo float puntuacion; // Puntuación relativa:fitness/sumfitness float punt_acu; // Puntuacion acumulada para sorteos bool elite; // Indicador de pertenecer a la elite int distalmejor; //Distancia al actual mejor individuo }; //Imprime los genes del individuo void imprimegenes(struct TIndividuo * individuo) { for(int i=0; i < lcrom; i++) printf("%i",individuo->genes[i]); } //Imprime los genes del individuo en un archivo void imprimegenesenfile(struct TIndividuo * individuo,FILE *pResultados) { for(int i=0; i < lcrom; i++) fprintf(pResultados,"%i",individuo->genes[i]);
57
} //Imprime la población (uso opcional) void imprimepoblacion(struct TIndividuo * pob) { for(int i=0; i < tam_pob; i++) { printf("%.0f\t",pob[i].aptitud); printf("%.0f\t",pob[i].aptitud2); printf("%.2f\t",pob[i].puntuacion); printf("%.2f\t",pob[i].punt_acu); printf("%i ",pob[i].distalmejor); printf("%i\n",pob[i].elite); } } //Imprime la población en un archivo (uso opcional) void imprimepoblacionfile(struct TIndividuo * pob,FILE * pResultados) { for(int i=0; i < tam_pob; i++) { //cout<<i<<". ";imprimegenes(&pob[i],lcrom); imprimegenesenfile(&pob[i],pResultados); fprintf(pResultados,"\t%i apt:%.0f\t",i,pob[i].aptitud); fprintf(pResultados,"\napt2:%.0f\t",pob[i].aptitud2); fprintf(pResultados,"punt:%.2f\t",pob[i].puntuacion);// punt. relativa:fitness/sumfitness fprintf(pResultados,"punt_acu:%.2f\t",pob[i].punt_acu); ///printf("%i\t",pob[i].mutado); fprintf(pResultados,"dist:%i ",pob[i].distalmejor); fprintf(pResultados,"elite:%i\n",pob[i].elite); } } //Retorna distancia Hamming entre dos soluciones(cromosomas) int distanciacromosomas(struct TIndividuo * indiv1,struct TIndividuo * indiv2) { int cont=0; for(int i=0; i < lcrom; i++) if(indiv1->genes[i]!=indiv2->genes[i]) cont++; return cont; } /*************************************/ /*Adaptacion */ /*Evalua la calidad de un individuo */ /*************************************/ float adaptacion(struct TIndividuo * individuo) { float fitness=0; // Aptitud (Utilidad de la solución) float fitness2=0; //Aptitud relativa (No importa factibilidad) float peso=0; // Peso total de los elementos del individuo float ngenesdemas; //Número aproximado de genes de sobrepaso for(int i=0; i < lcrom; i++) { peso=peso+ (individuo->genes[i]*vec_peso[i]); //Peso de la solución fitness=fitness+individuo->genes[i]*vec_utilidad[i]; //Fitness de la solución } fitness2=fitness; if(peso>peso_max) //Si no es factible la solución (agente) { ngenesdemas= (peso-peso_max)/pesoprom; fitness2 = fitness - (utilprom*ngenesdemas)*(sumapesos/peso_max);//Calcula fitness alterno fitness = 0; }
58
individuo->aptitud2 = fitness2; individuo->peso = peso; return fitness; } /*********************************************/ /*Genera un individuo para poblacion inicial */ /*********************************************/ void genera_indiv(struct TIndividuo * indiv) { int i; int gen; for(i=lcrom-1; i >=0 ; i--) { if (rand() < RAND_MAX / 2) gen = 0; else gen = 1; indiv->genes[i]=gen; }; indiv->aptitud = adaptacion(indiv); } /**********************************************/ /*Genera poblacion inicial aleatoria */ /**********************************************/ void poblacion_inicial(struct TIndividuo * pob) { for(int i=0; i < tam_pob; i++) { genera_indiv(&pob[i]); } } /*********************************/ /*Cruce: monopunto */ /*Aplica el operador de cruce */ /*********************************/ void cruce(struct TIndividuo * padrel, struct TIndividuo * padre2, struct TIndividuo * hijo1, struct TIndividuo * hijo2, int punto_cruce) { for(int i=0; i<lcrom; i++) { hijo1->genes[i]=0; hijo2->genes[i]=0; } //primera parte del intercambio: 1 a 1 y 2 a 2 int i; for(i=0; i < punto_cruce; i++) { hijo1->genes[i]=padrel->genes[i]; hijo2->genes[i]=padre2->genes[i]; } //segunda parte: 1 a 2 y 2 a 1 for(i=punto_cruce; i < lcrom; i++) { hijo1->genes[i]=padre2->genes[i]; hijo2->genes[i]=padrel->genes[i]; } //se evalúan hijo1->aptitud = adaptacion(hijo1); hijo2->aptitud = adaptacion(hijo2); }
59
/*********************************************/ /*Reproducción */ /*Selecciona los individuos a reproducirse y */ /*aplica el operador de cruce */ /*********************************************/ void reproduccion(struct TIndividuo * pob) { int* sel_cruce; //seleccionados para reproducirse sel_cruce = new int[tam_pob]; int num_sel_cruce=0; //num de individuos seleccionados a cruzar float prob; int punto_cruce; struct TIndividuo hijo1; struct TIndividuo hijo2; int i; //se eligen los individuos a cruzar for (i=0; i < tam_pob; i++) { //se generan tam_pob numeros aleatorios a_i en [o l) prob = (rand()/(RAND_MAX+1.0)); //se eligen para el cruce los individuos de las posiciones i con a_i < prob_cruce if (prob < prob_cruce) { sel_cruce[num_sel_cruce] = i; num_sel_cruce++; } } //el número de selecionados se hace par if ((num_sel_cruce % 2) == 1) num_sel_cruce--; //se cruzan los individuos elegidos en un punto al azar punto_cruce = (int)(rand() * (lcrom+1) / (RAND_MAX + 1.0)) + 1; for (i=0; i < num_sel_cruce; i=i+2) { cruce(&pob[sel_cruce[i]], &pob[sel_cruce[i+1]], &hijo1, &hijo2, punto_cruce); //los nuevos individuos sustituyen a sus progenitores respetando la élite if((hijo1.aptitud < adaptacion(&pob[sel_cruce[i]])) || (!pob[sel_cruce[i]].elite)) //ELITISMO pob[sel_cruce[i]] = hijo1; if((hijo2.aptitud < adaptacion(&pob[sel_cruce[i+1]])) || (!pob[sel_cruce[i+1]].elite)) pob[sel_cruce[i+1]] = hijo2; } delete [] sel_cruce; } /***********************************************************/ /*Seleccion */ /*Selecciona un unico individuo por el metodo de la ruleta */ /***********************************************************/ void seleccion(struct TIndividuo * pob) { struct TIndividuo * pob_aux; pob_aux = new struct TIndividuo[tam_pob]; float prob,f; // probabilidad de selección int pos_super; // posición del superviviente int i,j; int TAM_ELITE = tam_pob* 2 /100; int* sel_super; // seleccionados para sobrevivir int* sel_elite; sel_super = new int[tam_pob]; sel_elite = new int[TAM_ELITE]; //----------------------- //se selecciona la elite
60
//----------------------- for (i=0; i < TAM_ELITE; i++) { sel_elite[i] = 0; } for (i=0; i < tam_pob; i++) { pob[i].elite = false; j = 0; while ( (j < TAM_ELITE) && (pob[sel_elite[j]].aptitud >= pob[i].aptitud)) { j++; } if (j < TAM_ELITE) { sel_elite[j] = i; } } for (i=0; i < TAM_ELITE; i++) { pob[sel_elite[i]].elite = true; } //se seleccionan tam_pob individuos para reproducirse //se generan números aleatorios entre 0 y 1, //seleccionan individuos de acuerdo con su puntuación acumulada for (i=0; i < tam_pob; i++) { if (pob[i].elite == true) //ELITISMO sel_super[i] = i; else { f = rand(); prob = (f/(RAND_MAX+1.0)); pos_super = 0; while ((prob>pob[pos_super].punt_acu)&&(pos_super < tam_pob)) pos_super++; if (pos_super < tam_pob) sel_super[i] = pos_super; else sel_super[i] = pos_super-1; } } //se genera la población intermedia for (i=0; i < tam_pob; i++) pob_aux[i]= pob[sel_super[i]]; for (i=0; i < tam_pob; i++) pob[i]=pob_aux[i]; delete [] sel_super; delete [] sel_elite; delete [] pob_aux; } /*****************************************************/ /*Evaluacion */ /*Calcula y actualiza as estadisticas de la poblacion*/ /*****************************************************/ void evaluacion(struct TIndividuo * pob, int& pos_mejor, float * distprom, float * cai) { float punt_acu = 0; // puntación acumulada de los individuos float aptitud_mejor = 0;// mejor aptitud
61
int i, nfactibles=0; //Número de individuos factibles float sumaptitud = 0; // suma de la aptitud for (i=0; i< tam_pob; i++) { if(pob[i].aptitud > 0) { nfactibles ++; sumaptitud = sumaptitud + pob[i].aptitud; } else sumaptitud = sumaptitud + pob[i].aptitud2*(*cai); //Tiene en cuenta el segundo puntaje if (pob[i].aptitud > aptitud_mejor)//Si es factible { pos_mejor = i; aptitud_mejor = pob[i].aptitud; } if (pob[i].aptitud2 > aptitud_mejor && *cai>0)//Si NO es factible y está en la fase que computa factibles { pos_mejor = i; aptitud_mejor = pob[i].aptitud2; } } for (i=0; i< tam_pob; i++) { if(pob[i].aptitud > 0)//Si es factible { pob[i].puntuacion = pob[i].aptitud / sumaptitud; pob[i].punt_acu = pob[i].puntuacion + punt_acu; } else if(*cai>0)//Si NO es factible pero está en la fase que computa infactibles { pob[i].puntuacion = *cai * pob[i].aptitud2/ sumaptitud; pob[i].punt_acu = pob[i].puntuacion + punt_acu; } else //Si NO es factible y NO está en la fase que computa infactibles la aptitud computda es 0 { pob[i].puntuacion = pob[i].aptitud / sumaptitud; pob[i].punt_acu = pob[i].puntuacion + punt_acu; } punt_acu = punt_acu + pob[i].puntuacion; pob[i].distalmejor = distanciacromosomas(&pob[i],&pob[pos_mejor]); *distprom+=pob[i].distalmejor; } *distprom/=tam_pob; //Distancia promedio de todos los individuos repecto al mejor mejoranterior=mejoractual; mejoractual=pob[pos_mejor].aptitud; //Actualiza mejor en variable global //printf("factibles:%i-v",nfactibles); *cai= 1-(30*nfactibles/tam_pob); //El valor de selección de los infactibles disminuye con el numero de factibles if (*cai<0) *cai=0; //El coeficiente de adaptación de Infactibles se activa o no } /************************************************/ /*Mutacion */ /*Aplica el operador de mutacion a la poblacion */ /************************************************/ void mutacion(struct TIndividuo * pob) { bool mutado; int i,j; float prob; for (i=0; i < tam_pob; i++) {
62
mutado = false; for (j=0; j < lcrom; j++) { //se genera un número aleatorio en [o l) prob = (rand()/(RAND_MAX+1.0)); //se mutan aquellos genes con prob < que prob_mut if ((prob < prob_mut) && (!pob[i].elite)) //ELITISMO { pob[i].genes[j] = !(bool)( pob[i].genes[j]); mutado = true; } if (mutado==true) pob[i].aptitud = adaptacion(&pob[i]); } ///if(mutado==true)pob[i].mutado=true; } } /**********************************************/ /*Busqueda Local */ /*Exploración Hill Climb cambia 1 gen por vez */ /**********************************************/ void hillclimbing(struct TIndividuo * individuo, int profundidad) { //Hill Climbing profundidad 1 if(profundidad ==1) { bool mejorindiv = false;//El mejor individuo es el actual parámetro int mejori; double mejorpuntaje=adaptacion(individuo); double mejorpuntaje2=individuo->aptitud2; for(int i=0;i<lcrom;i++) { individuo->genes[i]=1-(individuo->genes[i]*1); //Invierte gen individuo->aptitud = adaptacion(individuo); if(individuo->aptitud > mejorpuntaje)//Si el nuevo agente es mejor guardo su posición { mejorindiv = true; mejori=i; mejorpuntaje=individuo->aptitud; } //Si el individuo es infactible se mejora a través de la segundo aptitud if(individuo->aptitud == 0 && mejorpuntaje == 0 && individuo->aptitud2 > mejorpuntaje2) { mejorindiv = true; mejori=i; mejorpuntaje2=individuo->aptitud2; } individuo->genes[i]=1-(individuo->genes[i]*1);//Revierte gen } if (mejorindiv==true ) //Si alterando un gen hubo mejores individuos { individuo->genes[mejori]=1-(individuo->genes[mejori]*1); individuo->aptitud = adaptacion(individuo); //imprimegenes(individuo,lcrom);cout <<" Aptitud= "<<individuo->aptitud<<endl; hillclimbing(individuo,profundidad); } else individuo->aptitud = adaptacion(individuo); } //Hill Climbing profundidad 2 if(profundidad==2) { bool mejorindiv = false;//El mejor individuo es el actual parámetro int mejori=-1; int mejorj=-1; double mejorpuntaje=adaptacion(individuo); double mejorpuntaje2=individuo->aptitud2; for(int i=0;i<lcrom;i++) {
63
individuo->genes[i]=1-(individuo->genes[i]*1); //Invierte gen for(int j=0;j<lcrom;j++) { if(j!=i) individuo->genes[j]=1-(individuo->genes[j]*1); //Invierte gen individuo->aptitud = adaptacion(individuo); if(individuo->aptitud > mejorpuntaje)//Si el nuevo agente es mejor guardo su posición { mejorindiv = true; mejori=i; mejorj=j; mejorpuntaje=individuo->aptitud; } if(individuo->aptitud == 0 && mejorpuntaje == 0 && individuo->aptitud2 > mejorpuntaje2) { mejorindiv = true; mejori=i; mejorj=j; mejorpuntaje2=individuo->aptitud2; } if(j!=i) individuo->genes[j]=1-(individuo->genes[j]*1); } individuo->genes[i]=1-(individuo->genes[i]*1); } if (mejorindiv==true ) //Si alterando un gen hubo mejores individuos { individuo->genes[mejori]=1-(individuo->genes[mejori]*1); if(mejorj!=mejori) individuo->genes[mejorj]=1-(individuo->genes[mejorj]*1); individuo->aptitud = adaptacion(individuo); hillclimbing(individuo, profundidad); } else individuo->aptitud = adaptacion(individuo); } } //Aplicación de la Búsqueda Local void localsearch(struct TIndividuo * pob, float * distprom, int pos_mejor) { //Hill Climbing de un grado de profundidad para toda la población (HC1) for (int i=0; i< tam_pob; i++) { hillclimbing(&pob[i], 1); } //Selecciona los primeros -tam_mejores- mejores según aptitud2 para aplicarles HC2 int tam_mejores = *(distprom) * cl;//coeficiente * promedio distancia al mejor = número de individuos selectos para HC2 //int radio = *(distprom) * param3; //coeficiente * promedio distancia al mejor = radio de acción mínimo para aplicar HC2 int* sel_mejores; sel_mejores = new int[lcrom]; int mayor=0; int mayor_ant=0; int pos_mayor; int cont=0; bool copio; //selecciona en el arreglo de sel_mejores de tamaño [tam_mejores] los E*cl o (*(distprom) * cl) mejores agentes de aptitud2 for(int i=0; i<tam_mejores;i++) { mayor=0; copio=false; for (int j=0; j < tam_pob; j++) { if(i==0) if(pob[j].aptitud+pob[j].aptitud2 > mayor) { mayor=pob[j].aptitud+pob[j].aptitud2;
64
pos_mayor= j; mayor_ant=mayor; copio=true; } if(i>0) if(pob[j].aptitud+pob[j].aptitud2 > mayor && pob[j].aptitud+pob[j].aptitud2 < mayor_ant) { mayor=pob[j].aptitud+pob[j].aptitud2; pos_mayor= j; copio=true; } } if(copio==true) { sel_mejores[i]=pos_mayor; mayor_ant=mayor; cont++; } } tam_mejores=cont;//cout<<"tam_mejores: "<<tam_mejores<<" "; //Aplicación del Hill Climbing de dos grados de profundidad (HC2) a los E*cl mejores if(generaciones>3) //Aplica sólo apartir de la tercera generación for (int i=0; i< tam_mejores; i++) { hillclimbing(&pob[sel_mejores[i]], 2); } delete [] sel_mejores; } //Carga los datos del archivo .txt void carga_datos() { FILE *pArchivo; pArchivo=fopen("datos.txt","r"); for(int i=0;i<lcrom;i++) { fscanf(pArchivo,"%i,",&vec_peso[i]);printf("%i,",vec_peso[i]); } cout<<endl; for(int i=0;i<lcrom;i++) { fscanf(pArchivo,"%i,",&vec_utilidad[i]);printf("%i,",vec_utilidad[i]); } cout<<endl; } int main() { //Habilitando archivo de resultados FILE *pResultados; pResultados=fopen("resultados.txt","a"); //inicialización de semilla de números aleatorios srand(time(NULL)); //Inicializando variables cl=0.4; //Coeficiente de longitud para No. de agentes a los que se aplica HC2 lcrom=120; // LONGITUD DEL INDIVIDUO (No.CROMOSOMAS) tam_pob=1000; // tamaño de población prob_cruce=0.4; // Probabilidad de cruce prob_mut=0.01; // Probabilidad de mutación int num_gen_max=100; // número de generaciones peso_max = 8000;//Peso máximo de la mochila float distprom =0; //Distancia promedio de la población al mejor individuo float cai=1; //Coeficiente de Adaptación para selección de Infactibles
65
float tiempo_min;//Tiempo de generación de la mejor aptitud int pos_mejor; // Posición del mejor individuo vec_peso = new int[lcrom]; vec_utilidad = new int[lcrom]; printf("Cargando %i datos...\n",lcrom); fprintf(pResultados,"Cargando %i datos...\n",lcrom); carga_datos(); //Carga los datos del archivo .txt sumapesos=0; sumautilidades=0; //Totalizando pesos y utilidades for(int i=0;i<lcrom;i++) { sumapesos+=vec_peso[i]; sumautilidades+= vec_utilidad[i]; } pesoprom = sumapesos/lcrom; //Peso promedio de cada objeto utilprom = sumautilidades/lcrom; //Utilidad promedio de cada objeto //Crea la población de individuos; struct TIndividuo * pob; pob = new struct TIndividuo[tam_pob]; //Iniciando conteo de tiempo clock_t start = clock(); printf("Iniciando...\n"); //se genera la población inicial poblacion_inicial(pob); evaluacion(pob, pos_mejor, &distprom, &cai); float adaptacion_anterior=0; // posición del mejor individuo anterior int gener_sincambios=0; printf("Generaciones\tDiversidad\tFitness\tFitness2\tPeso\tTiempo\n"); fprintf(pResultados,"Generaciones\tDiversidad\tFitness\tFitness2\tPeso\tTiempo\n"); //Bucle de evolución for (generaciones=1; gener_sincambios < 5 ; generaciones++) { seleccion(pob); reproduccion(pob); mutacion(pob); evaluacion(pob, pos_mejor, &distprom, &cai); //Contabiliza generaciones sin cambiar el mejor if(adaptacion_anterior < adaptacion(&pob[pos_mejor])) { gener_sincambios=0; tiempo_min=(float)clock() - start;} if(adaptacion_anterior == adaptacion(&pob[pos_mejor])) gener_sincambios++; adaptacion_anterior = adaptacion(&pob[pos_mejor]); localsearch(pob, &distprom, pos_mejor); printf("%i\t%i\t%f\t%.0f\t%0.f\t\t%.0f\t",generaciones,gener_sincambios,distprom,pob[pos_mejor].aptitud,pob[pos_mejor].aptitud2,pob[pos_mejor].peso); fprintf(pResultados,"%i\t%i\t%f\t%.0f\t%0.f\t\t%.0f\t",generaciones,gener_sincambios,distprom,pob[pos_mejor].aptitud,pob[pos_mejor].aptitud2,pob[pos_mejor].peso); printf("%.0f\n",((float)clock() - start)); fprintf(pResultados,";%.0f\n",((float)clock() - start)); } printf("Generaciones: %i\n",generaciones); printf("%Distancia promedio al mejor (diversidad): %f\n",distprom); printf("Aptitud mejor solución %.0f\n",pob[pos_mejor].aptitud);
66
printf("Aptitud2 mejor solución %.0f\n",pob[pos_mejor].aptitud2); fprintf(pResultados,"Generaciones: %i\n",generaciones); fprintf(pResultados,"%Distancia promedio al mejor (diversidad): %f\n",distprom); fprintf(pResultados,"Aptitud mejor solución %.0f\n",pob[pos_mejor].aptitud); fprintf(pResultados,"Aptitud2 mejor solución %.0f\n",pob[pos_mejor].aptitud2); imprimegenes(&pob[pos_mejor]); imprimegenesenfile(&pob[pos_mejor], pResultados); fprintf(pResultados,"\n"); printf("\n"); printf("Tiempo mínimo (seg):%.2f\n",tiempo_min/1000); fprintf(pResultados,"Tiempo mínimo (seg): %.2f\n",tiempo_min/1000); delete [] pob; fclose(pResultados); system("pause"); }
