PDF de programación - Aplicación de las materias de Ingeniería de Computadores en la mejora de los Algoritmos Meméticos y Metaheurísticas en general

Aplicación de las materias de Ingeniería de 
Computadores en la mejora de los Algoritmos 

Meméticos y Metaheurísticas en general 

Fernando Palacios López​,​, Jorge Chamorro Padial 

Estudiantes del Grado en Ingeniería Informática 

 

 

{ferpalacios, jorgechp​}@correo.ugr.es 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 

la

 
 

aplicación de
 

artículo analizamos

Resumen. En el presente
 
los
 
 
conocimientos adquiridos en las diferentes asignaturas relacionadas con la
 
 
Ingeniería de Computadores que componen el Grado en Ingeniería Informática
 
con el uso de metaheurísticas que se imparten en la especialidad de
 
 
Computación y Sistemas Inteligentes, haciendo especial enfoque en los
 
Algoritmos Evolutivos. Nos centraremos en los Algoritmos Meméticos,
 
comparando su rendimiento frente a los Algoritmos Genéticos. Finalmente, se
comprobará la mejora del rendimiento de una metaheurística cuando se aplica
 
 
Programación Paralela. 
Palabras Clave: ​computación, metaheurísticas, algoritmos meméticos  

 
 

 
 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 

 
 

 
 

 
 
 

Abstract. In this paper, we analyze how to apply the content of many subjects
 
of Computer Engineering to those metaheuristic that are imparted in Computing
 
and Intelligent Systems mention of Computing Engineering degree. The
 
purpose of this analysis is to make emphasis on the importance of applying
 
 
Computer Engineering techniques as a transversal knowledge of the degree. We
focus on Evolutionary Algorithms, analyzing Memetic Algorithms and
 
comparing their perfomance against Genetic Algorithms. 
Keywords: ​computing, metaheuristics, memetic algorithms 

 
   
 

 
 
 

 
 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1   Introducción 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
Metaheurísticas es una asignatura del tercer curso del grado Grado en Ingeniería
Informática, enmarcada en la especialidad de Computación y Sistemas Inteligentes,
 
 
siendo obligatoria para obtener la especialidad. 

 
La asignatura, como su propio nombre indica, estudia diferentes metaheurísticas
 
utilizadas en el ámbito de la Inteligencia Artificial para resolver problemas de diversa
 
índole. El temario se estructura por temas, y en cada uno de estos temas se estudian
 
diferentes algoritmos, según se expone a continuación [1]. 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Enseñanza y Aprendizaje de Ingeniería de Computadores. Número 5, 2015127  

 

 

 

 

 

 

 

 

● Algoritmos de Búsqueda Local Básicos [2]: Basan su estrategia en un estudio
 
 
local del espacio de búsqueda, es decir, analizan las soluciones incluidas en el
 
entorno de la solución actual. Dichas soluciones son denominadas soluciones
 
vecinas. 
Estos algoritmos presentan el inconveniente de ofrecer como solución óptimos
 
locales, que pueden llegar a estar muy alejados del óptimo global del problema. 

 
 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

● Enfriamiento Simulado [3]: ​Basados en la termodinámica, los algoritmos de
 
 
Enfriamiento Simulado realizan una búsqueda por entornos en la que permiten
 
 
movimientos a soluciones peores, con el fin de evitar finalizar en un óptimo
local. Estos “movimientos de empeoramiento” se realizan de un modo
 
controlado según un criterio probabilístico. 

 
 
 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 

 
 

 
 

● Búsqueda Tabú [4]: ​Los algoritmos de Búsqueda Tabú generan entornos
 
restringidos para evitar la exploración de zonas del espacio de búsqueda
 
previamente visitadas. Además, implementan mecanismos de reinicialización
 
 
para intensificar la búsqueda sobre zonas prometedoras y diversificar la
búsqueda, visitando nuevas zonas. También permiten movimientos de
 
 
empeoramiento para escapar de óptimos locales. 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

● Métodos Basados en Trayectorias Múltiples [5]: ​El funcionamiento de ​los
 
 
algoritmos de este bloque consiste en la generación de una solución inicial y
 
posteriormente en una etapa de mejora de dicha solución. Los algoritmos
 
principales son GRASP, ILS y VNS. 

 
 
 

 
 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

● Metaheurísticas Basadas
 

se
 
 
encuentran dentro de la rama de la computación evolutiva, que recrea los
mecanismos de la evolución biológica para obtener
la solución a los
 
 
problemas. Podemos destacar en esta clase los Algoritmos Genéticos, los
Algoritmos Evolutivos
la Evolución
 
Diferencial y la Programación Genética [7].   

en Poblaciones: Estas metaheurísticas
 
 
 

[6] para optimización contínua,

 
 
 
 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

● Metaheurísticas Basadas
 
 

[8]: Simulan el
 
 
comportamiento colectivo de una sociedad para la resolución de problemas.
Destacan los Algoritmos de Optimización Basados en Colonias de Hormigas y
 
 
la Optimización Basada en Nubes de Partículas. 

en Adaptación Social

 
 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 

● Metaheurísticas Híbridas: ​Como su nombre indica, estas metaheurísticas
 
combinan varios tipos de algoritmos. Podemos encontrar los Algoritmos
 
Meméticos [9], que combinan Algoritmos Evolutivos con algoritmos de
 
Búsqueda Local, y los algoritmos de Búsqueda Dispersa [10], un método
 
evolutivo que también suele utilizar la Búsqueda Local como método de
 
mejora de la solución actual. 

 
 

 
 

 
 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Enseñanza y Aprendizaje de Ingeniería de Computadores. Número 5, 2015128  

 

● Metaheurísticas Paralelas [11]: Dado que las Metaheurísticas suelen realizar
 
un cálculo intensivo, llega a ser necesario utilizar paralelismo para reducir el
 
tiempo de ejecución. Este tema está centrado en el uso del paralelismo aplicado
 
a metaheurísticas previamente estudiadas. 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 

 
 

 
 

 
 

 
 

 
 
En este artículo, los autores nos proponemos aplicar el aprendizaje adquirido a lo
 
 
largo de nuestra formación en las diferentes asignaturas de Ingeniería de Computadores
(Arquitectura de Computadores, Ingeniería de Servidores, Estructura de Computadores
 
y Tecnología y Organización de Computadores) a la implementación de metaheurísticas
 
 
 
estudiadas en Computación y Sistemas Inteligentes, nuestra especialidad. 

 
 
 

 
Para este fin, nos hemos decantado por la implementación y el análisis de un
 

 
algoritmo memético y su aplicación a un problema de optimización. 
 
La elección de un algoritmo memético en este artículo se debe a la cantidad de
 
 
algoritmos que, de forma indirecta, van incluidos en él. Nos referimos a algoritmos de
 
búsqueda local y Basados en Poblaciones. Entendemos que esta es la forma más efectiva
 
 
de abarcar el mayor contenido de la asignatura Metaheurísticas en este artículo. 

   

 
 

 
 

 
 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2   Características de los algoritmos meméticos 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Los algoritmos meméticos son algoritmos basados en poblaciones y derivan de los
 
genéticos. Estos algoritmos se basan en el concepto de ​meme​. En la Antropología, un
 
meme es la unidad mínima de información cultural que un individuo puede transferir a
   
otro permitiendo así la preservación cultural entre generaciones. 

 
El concepto de meme va asociado al de información. Los algoritmos meméticos
 
tratan de utilizar el Dominio de conocimiento de un problema y preservarlo durante la
 
búsqueda de una solución aceptable. 

 
 
En los algoritmos genéticos, se generaban nuevas poblaciones a partir de las actuales,
utilizando diferentes operadores (cruce, recombinación…) y posteriormente aplicando
 
una mutación con una determinada probabilidad. Estas transformaciones no utilizan
 
información del dominio de conocimiento para generar nuevos individuos. 

 
 
Los algoritmos meméticos, en cambio, utilizan operadores que trabajan con
información del dominio del problema. Estos operadores reciben el nombre de ​híbridos
 
y traspasan atributos entre generaciones de individuos de una población. 

 
A continuación, aclararemos el concepto de ​traspaso de información del dominio del
 
 
 
problema entre individuos. En primer lugar, los algoritmos evolutivos son algoritmos
 
que se han mostrado eficientes a la hora de explorar la diversidad en un espacio de
 
soluciones. Esto nos permite tener algoritmos que hayan explorado diferentes zonas del
 

 
 
 

 
 
 

   

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Enseñanza y Aprendizaje de Ingeniería de Computadores. Número 5, 2015129  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

universo de soluciones. Sin embargo, los algoritmos evolutivos no se comportan
 
adecuadamente a la hora