metaheurísticas para el análisis de datos masivos en el...

UNIVERSIDAD POLITECNICA DE MADRID

ESCUELA TECNICA SUPERIOR DE INGENIEROS INFORMATICOS

TESIS DE FIN DE MASTER

Metaheurısticas para el analisis

de datos masivos en el ambito del

transporte por carretera

MASTER UNIVERSITARIO EN INTELIGENCIA ARTIFICIAL

Departamento de Inteligencia Artificial

Julio 2017

Autor

Javier Lopez Ruiz

Directores

Alfonso Mateos Caballero (Universidad Politecnica de Madrid)

Eugenio Jose Fernandez Vicente (Universidad de Alcala)

“La informacion es la gasolina del siglo XXI,

y el analisis de datos, el motor de combustion.”

Peter Sondergaard (Gartner)

Agradecimientos

A mis tutores Alfonso y Eugenio por su confianza durante el desarrollo de la tesis.

Sin el apoyo de mis padres en todas mis decisiones, esta tesis estarıa inconclusa.

A toda la gente que de una forma u otra ha colaborado con mi aprendizaje.

Necesaria la mencion a mi hermana Marıa, por su alegrıa y comprension.

Dedicado a todos mis companeros de la Catedra Planificando.

Recuerdo especial a mis amigos por sus animos continuos.

A todos, gracias por todo.

Javier Lopez

Madrid, julio de 2017

Resumen

En el campo de la Inteligencia Artificial, han surgido multitud de terminos a lo

largo del estudio de los datos por la comunidad academica: descubrimiento de

patrones, minerıa de datos, aprendizaje automatico, aprendizaje profundo, Big

Data, ciencia de los datos... La resolucion de problemas de optimizacion mediante

tecnicas metaheurısticas tambien ha sido investigada de forma extensa.

Esta tesis muestra como es posible realizar un analisis de grandes conjuntos de da-

tos modelizando dicha tarea en un problema de optimizacion. Para ello, se desa-

rrolla un caso practico para una operadora logıstica de transporte en cisterna

especializada en mercancıas peligrosas, principalmente de productos petrolıferos,

que tiene una alta incidencia en el tejido economico espanol, y al mismo tiempo,

tiene unos niveles de seguridad y reglamentacion muy elevados.

Con tal objetivo, se ha elaborado un estado del arte de las diferentes tecnicas de

busquedas metaheurısticas, ası como de aprendizaje automatico no supervisado.

Se ha desarrollado un sistema de clasificacion a partir de datos geo-posicionados,

ası como una posterior validacion de los metodos utilizados.

Palabras clave: metaheurısticas, clustering, aprendizaje automatico, logıstica.

vii

Abstract

In the field of Artificial Intelligence, several terms have originated throughout

the study of data by the academic community: pattern recognition, data mining,

machine learning, deep learning, Big Data, Data Science ... The resolution of op-

timization problems using metaheuristic techniques has also been extensively in-

vestigated.

This thesis shows how it is possible to perform an analysis of large datasets by

modeling this task into an optimization problem. To this end, a case study is

developed for a logistic company specialized in dangerous goods, mainly petroleum

products, that has a high incidence in the Spanish economic fabric, and at the same

time, has very high levels of security and regulation.

With this goal in mind, a state of the art of different metaheuristic search tech-

niques has been elaborated. In addition, unsupervised machine learning is also

studied. It has been developed a classification system from geodata, as well as a

later validation of the methods used.

Keywords: metaheuristics, clustering, machine learning, logistics.

ix

Indice general

Resumen VII

Abstract IX

Indice de figuras XV

Indice de tablas XVII

Indice de algoritmos XIX

Abreviaturas XX

1. Introduccion 1

1.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2. Estructura del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . 4

2. Metaheurısticas 5

2.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2. Conceptos basicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.3. Clasificacion de metaheurısticas . . . . . . . . . . . . . . . . . . . . 8

2.4. Metaheurısticas basadas en una solucion . . . . . . . . . . . . . . . 9

2.4.1. Busqueda en escalada . . . . . . . . . . . . . . . . . . . . . . 10

2.4.2. Recocido simulado . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.3. Busqueda tabu . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4.4. Otros algoritmos . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4.4.1. Busqueda de vecindario variable . . . . . . . . . . . 15

2.4.4.2. Busqueda local guiada . . . . . . . . . . . . . . . . 15

xi

Contenido xii

2.4.4.3. Busqueda local iterativa . . . . . . . . . . . . . . . 16

2.4.4.4. Procedimiento voraz de busqueda aleatorio y adap-tativo . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.5. Metaheurısticas basadas en poblaciones . . . . . . . . . . . . . . . . 17

2.5.1. Computacion evolutiva . . . . . . . . . . . . . . . . . . . . . 18

2.5.1.1. Algoritmos geneticos . . . . . . . . . . . . . . . . . 19

2.5.1.2. Evolucion diferencial . . . . . . . . . . . . . . . . . 21

2.5.1.3. Programacion genetica . . . . . . . . . . . . . . . . 23

2.5.1.4. Algoritmos memeticos . . . . . . . . . . . . . . . . 23

2.5.1.5. Algoritmos de estimacion de la distribucion . . . . 24

2.5.1.6. Busqueda dispersa . . . . . . . . . . . . . . . . . . 24

2.5.2. Inteligencia colectiva . . . . . . . . . . . . . . . . . . . . . . 25

2.5.2.1. Optimizacion por enjambre de partıculas . . . . . . 26

2.5.2.2. Optimizacion por colonia de hormigas . . . . . . . 28

2.6. Multi-objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.6.1. Clasificacion de las metaheurısticas multi-objetivo . . . . . . 30

2.6.1.1. NSGA-II . . . . . . . . . . . . . . . . . . . . . . . 31

2.6.1.2. SPEA2 . . . . . . . . . . . . . . . . . . . . . . . . 31

2.6.1.3. IBEA . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.6.1.4. OMOPSO . . . . . . . . . . . . . . . . . . . . . . . 32

2.6.1.5. GDE3 . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.6.2. Evaluacion del rendimiento . . . . . . . . . . . . . . . . . . . 34

2.6.2.1. Indicadores de convergencia . . . . . . . . . . . . . 35

2.6.2.2. Indicadores de diversidad . . . . . . . . . . . . . . 36

2.6.2.3. Indicadores hıbridos . . . . . . . . . . . . . . . . . 37

3. Analisis de datos con metaheurısticas 39

3.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2. Algoritmos de agrupamiento clasicos . . . . . . . . . . . . . . . . . 40

3.2.1. Metodos particionales . . . . . . . . . . . . . . . . . . . . . 41

3.2.2. Metodos jerarquicos . . . . . . . . . . . . . . . . . . . . . . 42

3.2.3. Metodos basados en densidades . . . . . . . . . . . . . . . . 43

3.3. Agrupamiento con metaheurısticas . . . . . . . . . . . . . . . . . . 44

3.3.1. Evaluacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.3.1.1. Compacidad . . . . . . . . . . . . . . . . . . . . . . 45

3.3.1.2. Separacion . . . . . . . . . . . . . . . . . . . . . . 46

3.3.1.3. Compacidad y separacion . . . . . . . . . . . . . . 48

Contenido xiii

3.3.2. Codificacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.3.2.1. Codificacion binaria . . . . . . . . . . . . . . . . . 50

3.3.2.2. Codificacion entera . . . . . . . . . . . . . . . . . . 50

3.3.2.3. Codificacion real . . . . . . . . . . . . . . . . . . . 51

3.3.3. Seleccion de la solucion final . . . . . . . . . . . . . . . . . . 52

3.3.3.1. Funcion de evaluacion independiente . . . . . . . . 52

3.3.3.2. Punto knee del frente no-dominado . . . . . . . . . 52

3.3.3.3. Conjuntos de clusters . . . . . . . . . . . . . . . . 52

4. Caso practico: Operadora logıstica 53

4.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.2. Definicion del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.3. Experimentacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.4. Resultados y validacion . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.4.1. K-medoides . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.4.2. NSGA-II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.4.3. SPEA2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.4.4. IBEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.4.5. GDE3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.4.6. OMOPSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.4.7. Comparativa y validacion . . . . . . . . . . . . . . . . . . . 71

5. Conclusiones y trabajo futuro 75

5.1. Contribuciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

5.2. Lıneas futuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

A. Generacion de la matriz de distancias 77

B. MOEA Framework 81

C. Implementacion de metricas y diagramas de caja con Python 87

Bibliografıa 95

Indice de figuras

1.1. Ventas de lubricantes en Espana . . . . . . . . . . . . . . . . . . . . 2

2.1. Esquema de metodos de resolucion para problemas de optimizacion 6

2.2. Cronologıa de las metaheurısticas estudiadas basadas en una solucion 9

2.3. Cronologıa de las metaheurısticas estudiadas basadas en poblaciones 17

2.4. Cronologıa de los algoritmos multi-objetivo estudiados . . . . . . . 30

2.5. Indicador de distancia generacional . . . . . . . . . . . . . . . . . . 35

2.6. Indicadores de divergencia multi-objetivo . . . . . . . . . . . . . . . 36

2.7. Indicadores hıbridos multi-objetivo . . . . . . . . . . . . . . . . . . 37

3.1. Tıpico proceso de analisis de grupos . . . . . . . . . . . . . . . . . . 40

3.2. Dendograma de ejemplo del popular conjunto de datos Iris . . . . . 42

4.1. Mapa de calor de los distribuidores de lubricantes . . . . . . . . . . 54

4.2. Proceso de distribucion del producto de lubricantes . . . . . . . . . 54

4.3. Clasificacion original . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.4. Diagramas de cajas de las metricas originales . . . . . . . . . . . . . 56

4.5. Clasificacion por k -medoides . . . . . . . . . . . . . . . . . . . . . . 60

4.6. Diagramas de cajas de metricas de k -medoides . . . . . . . . . . . . 60

4.7. Indicadores de rendimiento de NSGA-II (10 ejecuciones) . . . . . . 61

4.8. Clasificacion por NSGA-II . . . . . . . . . . . . . . . . . . . . . . . 62

4.9. Diagramas de cajas de metricas de NSGA-II . . . . . . . . . . . . . 62

4.10. Indicadores de rendimiento de SPEA2 (10 ejecuciones) . . . . . . . 63

4.11. Clasificacion por SPEA2 . . . . . . . . . . . . . . . . . . . . . . . . 64

4.12. Diagramas de cajas de metricas de SPEA2 . . . . . . . . . . . . . . 64

4.13. Indicadores de rendimiento de IBEA (10 ejecuciones) . . . . . . . . 65

4.14. Clasificacion por IBEA . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.15. Diagramas de cajas de metricas de IBEA . . . . . . . . . . . . . . . 66

4.16. Indicadores de rendimiento de GDE3 (10 ejecuciones) . . . . . . . . 67

xv

Contenido xvi

4.17. Clasificacion por GDE3 . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.18. Diagramas de cajas de metricas de GDE3 . . . . . . . . . . . . . . . 68

4.19. Indicadores de rendimiento de OMOPSO (10 ejecuciones) . . . . . . 69

4.20. Clasificacion por OMOPSO . . . . . . . . . . . . . . . . . . . . . . 70

4.21. Diagramas de cajas de metricas de OMOPSO . . . . . . . . . . . . 70

4.22. Comparativa de indicadores de rendimiento entre metaheurısticas . 72

Indice de tablas

4.1. Clasificacion actual de las zonas de reparto por provincias . . . . . 55

4.2. Hipervolumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.3. Distancia generacional . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.4. Distancia generacional invertida . . . . . . . . . . . . . . . . . . . . 71

4.5. Indicador ε+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.6. Validaciones de compacidad . . . . . . . . . . . . . . . . . . . . . . 73

4.7. Validaciones de separacion . . . . . . . . . . . . . . . . . . . . . . . 73

4.8. Validaciones mixtas de compacidad y separacion . . . . . . . . . . . 73

4.9. Clasificacion final por puntuacion . . . . . . . . . . . . . . . . . . . 73

xvii

Indice de algoritmos

1. Busqueda en escalada basica . . . . . . . . . . . . . . . . . . . . . . 10

2. Recocido simulado . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3. Busqueda tabu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4. Procedimiento general en computacion evolutiva . . . . . . . . . . . 18

5. Evolucion diferencial . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6. Optimizacion por enjambre de partıculas . . . . . . . . . . . . . . . 27

7. Optimizacion por colonia de hormigas . . . . . . . . . . . . . . . . . 28

8. Algoritmo clasico de k -medoides . . . . . . . . . . . . . . . . . . . . 41

xix

Abreviaturas

ACO Ant Colony Optimization

AI Artificial Intelligence

DBSCAN Density-Based Spatial Clustering of Applications with Noise

DE Differential Evolution

DM Data Mining

EC Evolutionary Computation

EDA Estimation of Distribution Algorithms

GA Genetic Algorithms

GDE Generalized Differential Evolution

GLS Guided Local Search

GP Genetic Programming

GRASP Greedy Randomized Adaptive Search Procedure

HC Hill Climbling

IBEA Indicator-Based Evolutionary Algorithm

ILS Iterated Local Search

KDD Knowledge Disvoery in Databases

MA Memetic Algorithms

ML Machine Learning

NSGA Non-Dominated Sorting Genetic Algorithm

xxi

Abreviaturas xxii

OPTICS Ordering Points To Identify the Clustering Structure

OSRM Open Source Routing Machine

PAM Partitioning Around Medoids

PMBGA Probabilistic Model Building Genetic Algorithms

PR Path Relinking

PSO Particle Search Optimization

RCL Restricted Candidated List

SA Simulated Annealing

SI Swarm Intelligence

SPEA Strength Pareto Evolutionary Algorithm

SS Scatter Search

TS Tabu Search

VNS Variable Neighborhood Search

Capıtulo 1

Introduccion

En el mundo empresarial se toman constantemente decisiones de optimizacion enun entorno competitivo y dinamico. Las empresas adoptan diferentes metodologıaspara ello, que van desde procedimientos de prueba-error hasta complejos modelosmatematicos y algoritmos para la resolucion de esta toma de decisiones.

En el sector logıstico, las decisiones de optimizacion son muy frecuentes y cadavez mas complejas debido a los avances tecnologicos actuales. La causa de esteincremento de dificultad viene dado por el aumento del numero de variables a teneren cuenta, ası como la complejidad de las funciones que guıan la optimizacion.

Las aproximaciones con metaheurısticas permiten a aquellas personas que debentomar las decisiones obtener resultados cercanos al optimo dentro de un perıodo detiempo relativamente menor [Talbi, 2009]. Academicamente, estas aproximacionescontribuyen a la literatura cientıfico-tecnologica con el desarrollo de solucionesinnovadoras para el transporte logıstico.

Los problemas del mundo real, modelados como problemas de optimizacion, cons-tan de tres partes: variables que necesitan de una optimizacion, una o varias funcio-nes objetivo que deben ser maximizadas o minimizadas, y una serie de restriccionesy condiciones que limitan dichas funciones [Rao, 2009]. Por lo tanto, el uso de me-taheurısticas para la busqueda de las mejores soluciones es una de las alternativasmas destacadas. En general, las metaheurısticas se definen como procedimientosde busqueda de una solucion casi optima dentro de un espacio de soluciones paraun problema de optimizacion. Los factores que afectan a la calidad de los resulta-dos de busqueda son el tipo de problema, el algoritmo metaheurıstico aplicado, eltamano del espacio de busqueda y la capacidad de computacion.

1

2 CAPITULO 1. INTRODUCCION

Esta tesis surge de entre una de las muchas necesidades basadas en InteligenciaArtificial de una operadora logıstica de transporte en cisterna especializada enmercancıas peligrosas, principalmente de productos petrolıferos, que tiene una altaincidencia en el tejido economico espanol, y al mismo tiempo, tiene unos nivelesde seguridad y reglamentacion muy elevados.

En concreto, el problema a resolver se centra en el reparto de lubricantes por todoel territorio nacional. Segun la Asociacion Espanola de Lubricantes, la demandade lubricantes para turismos y en general, para otros servicios, sigue una senda decrecimiento continuada que se ha venido presentando desde antes del ano 2000. Elpasado ano 2016 significo la confirmacion del proceso de moderada recuperacionen ventas de lubricantes (Figura 1.1).

Figura 1.1: Ventas de lubricantes en Espana1

Por ello, la empresa ve la necesidad de optimizar sus diferentes procesos logısticos.Uno de ellos, la asignacion de los distribuidores finales de lubricantes a cada zona dereparto, era responsabilidad directa de la propia petrolera que vendıa el producto.

1Fuente: Memoria de actividades 2016 de la Asociacion Espanola de Lubricantes (ASELUBE).

1.1. OBJETIVOS 3

Como operadora logıstica, y experta en su negocio, ha adquirido esta competenciay se plantea la hipotesis de mejorar el sistema heredado, el cual se basaba en unaagrupacion por provincias.

A continuacion, se presentan los objetivos de este trabajo y una pequena descrip-cion de los capıtulos que forman este documento.

1.1. Objetivos

Esta tesis tiene multiples objetivos. El objetivo principal es plantear una solucional problema presentando anteriormente, definiendo y desarrollando un sistema quelo resuelva. Para conseguirlo, se plantean los siguientes objetivos especıficos:

1. Conocer tecnicas y metodos de Inteligencia Artificial que permitan abordary solucionar problemas de caracter cientıfico y tecnologico.

2. Aplicar tecnicas existentes de Inteligencia Artificial para la resolucion de unproblema real.

3. Ser capaz de modelizar problemas reales de clasificacion mediante paradig-mas computacionales.

4. Ser capaz de aplicar metaheurısticas para resolver problemas de optimizacionmulti-objetivo.

5. Experimentar con diferentes tecnologıas para la resolucion de problemas deaprendizaje automatico y de busqueda multi-objetivo.

6. Validar los diferentes metodos desarrollados.

7. Difundir metodos desarrollados que se han incorporado a la realidad empre-sarial, originando procesos y soluciones informaticas innovadoras.

8. Publicar y compartir resultados en un congreso internacional.

9. Saber manejar fuentes bibliograficas y valorar su importancia para desarro-llar trabajos que reflejen el estado del arte.

10. Redactar un informe o memoria final con LATEX.

4 CAPITULO 1. INTRODUCCION

1.2. Estructura del trabajo

Con el fin de abordar estos objetivos, este trabajo se divide en varios capıtuloscuyo contenido se describe brevemente a continuacion:

En el Capıtulo 1 se presenta una vision general del trabajo, introduciendolos problemas que intenta resolver, sus objetivos y su estructura interna.

En el Capıtulo 2 se realiza un estado del arte sobre metaheurısticas, realizan-do una clasificacion de ellas y describiendo aquellas mas importantes para elproblema que se plantea. Ademas, se detallan diferentes formas de evaluarsu rendimiento.

En el Capıtulo 3 se realiza un estado del arte sobre aprendizaje automaticono supervisado, mostrando desde algoritmos de agrupamiento tradicionales,hasta como resolver este tipo de problemas con metaheurısticas, definiendotodos los puntos de su diseno, desde la codificacion hasta su evaluacion.

En el Capıtulo 4 se presenta un caso practico que se ha desarrollado para unaoperadora logıstica. Se define el trabajo a realizar, detallando la motivaciondel mismo ası como los objetivos requeridos. Se ha realizado una experimen-tacion con multiples tecnicas, tanto clasicas de aprendizaje no supervisadocomo con metaheurısticas, ası como una validacion sobre cada uno de losmetodos expuestos.

En el Capıtulo 5 se resume el trabajo expuesto en esta memoria, presentandolas principales contribuciones de esta tesis y planteando trabajos futurosderivados.

Por ultimo, los apendices incluyen la descripcion a nivel tecnico de como seha implementado la solucion propuesta.

Capıtulo 2

Metaheurısticas

2.1. Introduccion

Un problema de optimizacion se define por:

Un conjunto de soluciones D que representa el espacio de busqueda.Una funcion de evaluacion f que asocia a cada solucion s un valor represen-tando su calidad.

Un problema de minimizacion se definirıa por la ecuacion 2.1:

mın f(s) | s ∈ D. (2.1)

En funcion del problema, la naturaleza de las soluciones s ∈ D varıa y estarandefinidas por una serie de restricciones, determinado ası cuales de ellas son solu-ciones factibles. En el caso de un conjunto finito de soluciones discretas, se tratarade un problema de optimizacion combinatorio.

La resolucion de un problema de optimizacion combinatorio consta de tres puntosclave:

Definir un conjunto de soluciones factibles.Determinar una funcion de evaluacion a optimizar.Elegir un metodo de optimizacion.

5

6 CAPITULO 2. METAHEURISTICAS

Los dos primeros puntos se basan en el modelado del problema, mientras que eltercero trata con la resolucion del problema. Para definir un conjunto de solucionesfactibles, es necesario determinar el conjunto de restricciones del problema, siendonecesario por tanto un conocimiento del problema y su aplicacion de dominio.De forma similar, la formulacion de la funcion de evaluacion requiere de dichoconocimiento, pues es necesario poder calificar como de buena es una solucion.

La eleccion del metodo de optimizacion depende de la complejidad del problema.Para los problemas de clase P , se puede utilizar un algoritmo de optimizacionpolinomial para encontrar la solucion optima [Rıos et al., 2004]. En el caso delos problemas de clase NP , no es posible encontrar un algoritmo de optimizacionpolinomial, por lo que hay que recurrir a dos aproximaciones de optimizaciondiferentes. Si el tamano del problema es pequeno, se puede encontrar una solucionoptima con un algoritmo exacto, como por ejemplo la programacion dinamica,pero en problemas con un tamano mayor, entre otras complejidades, este tipo deprocedimientos no son eficientes. En estas situaciones, es recomendable hacer usode una aproximacion heurıstica, a pesar de no garantizarse una solucion optima.

Entre estos ultimos metodos, hay heurısticas que han sido desarrolladas para laresolucion de problemas concretos [Russell and Norvig, 2003], y metaheurısticas,que ofrecen un esquema de resolucion generico con el potencial de poder ser adap-tado a cualquier problema de optimizacion. El objetivo de una metaheurıstica esexplorar el espacio de busqueda de forma eficiente, sin tener que enumerar to-das las soluciones. Por tanto, una metaheurıstica tendra exito en un problema deoptimizacion dado si es capaz de encontrar un equilibrio entre su capacidad deexploracion (diversificacion) y de explotacion (intensificacion).

La exploracion es necesaria para identificar el espacio de busqueda con mayorcalidad de soluciones. La explotacion es importante para intensificar la busquedaen dichas regiones. Las mayores diferencias entre las metaheurısticas existentes seencuentran a la hora de como encuentran este equilibrio cada una de ellas.

Metodos de optimizacion

Metodos exactos

Programacion lineal Programacion no lineal

Aproximacion heurıstica

Heurısticas concretas Metaheurısticas

Figura 2.1: Esquema de metodos de resolucion para problemas de optimizacion

2.2. CONCEPTOS BASICOS 7

2.2. Conceptos basicos

En esta seccion se describen los conceptos basicos que se pueden aplicar a cualquiermetaheurıstica. Una descripcion mas detallada puede encontrarse en [Talbi, 2009]y [Gendreau and Potvin, 2010].

Las metaheurısticas son metodos genericos para explorar el espacio de busquedade las soluciones candidatas (factibles o no factibles). Por ello, el diseno de unametaheurıstica requiere una codificacion de estas soluciones. Es un un punto clave,ya que la codificacion juega un papel muy importante en la eficiencia del algoritmo.

La codificacion seleccionada debe verificar algunas propiedades. Primero, cualquiersolucion del espacio de busqueda debe poder ser codificada. Idealmente, una unicacodificacion se corresponde con una unica solucion candidata. Ademas, la codifica-cion debe respetar una propiedad de conexion que se asegure que existe un caminode busqueda entre dos soluciones, para poder llegar a una solucion optima. Existenmultiples tipos de codificaciones: binaria, vectorial con valores discretos, vectoresde numeros reales, grafos, arboles, etc.

Los problemas de optimizacion, y en particular, los combinatorios, se definen porun conjunto de restricciones a respetar. Solo las soluciones candidatas que las cum-plen son factibles. Durante el proceso de busqueda es posible que no se respeten,por lo que existen diversas estrategias para lidiar con este problema:

Descartar las soluciones que no son factibles.

Penalizar las soluciones que no son factibles. De esta forma es posible que apartir de una solucion no factible se llegue a una region donde se encuentreuna solucion optima.

Corregir las soluciones que no son factibles, transformando una solucion nofactible en factible.

La definicion de la funcion de evaluacion que mide la calidad de las solucioneses crucial para el proceso de optimizacion. Esta funcion de evaluacion guiara labusqueda durante la ejecucion del algoritmo. Idealmente, esta funcion asociaraun valor real a cada solucion del espacio de busqueda, pudiendo ası realizar unaordenacion completa de las soluciones:

f : D → R. (2.2)


2.3. Clasificacion de metaheurısticas

Existen multiples taxonomıas para clasificar los algoritmos metaheurısticos basando-se en las caracterısticas que hacen que se diferencien entre ellos [Talbi, 2009].Algunas de ellas son las siguientes:

Si estan basadas en una solucion o en poblaciones

Los metodos basados en una solucion trabajan con una unica solucion du-rante todo el proceso, mientras que aquellos basados en poblaciones trabajancon un conjunto entero de soluciones. En general, las metaheurısticas basadasen una solucion estan orientadas a la explotacion, mientras aquellas basadasen poblaciones tienden a una mayor exploracion del espacio de busqueda.Esta clasificacion es la utilizada en este trabajo.

Si estan inspiradas por la naturaleza

Existen multitud de metaheurısticas inspiradas en los fenomenos de la natu-raleza, como la evolucion o el comportamiento de vuelo de las bandadas depajaros.

Si son iterativas o voraces

Los algoritmos iterativos empiezan con una solucion o un conjunto de ellas,y son manipuladas durante todo el proceso de busqueda. Los algoritmosvoraces comienzan con una solucion vacıa, y en cada etapa, a una variable dedecision se le asigna un valor, siendo este anadido al conjunto de soluciones.

Si tienen memoria o no

Los algoritmos sin memoria solo utilizan la informacion del estado actual dela busqueda, mientras que otros aprovechan toda la informacion generada enel proceso iterativo de la busqueda.

Si la funcion objetivo es estatica o dinamica

Los algoritmos con una funcion objetivo estatica mantienen durante todo elproceso dicha funcion, que vendra dada por la modelizacion del problema;mientras que otras pueden modificarla durante el proceso de busqueda.

Si tiene una o mas estructuras de vecindario

La mayorıa de metaheurısticas utilizan una unica estructura de vecindario,aunque es posible trabajar con un conjunto de multiples estructuras.

2.4. METAHEURISTICAS BASADAS EN UNA SOLUCION 9

2.4. Metaheurısticas basadas en una solucion

Las metaheurısticas basadas en una solucion, estan compuestas tıpicamente de dosfases: un proceso de generacion y otro de reemplazo sobre una unica solucion. Enla fase de generacion, un conjunto de soluciones candidatas es generado a partirde la solucion actual. En la fase de reemplazo, una solucion factible, a partir delconjunto generado, es elegida para reemplazar a la solucion actual. En general,este proceso continua hasta que se cumple una determinada condicion de parada.Otros conceptos principales de las metaheurısticas basadas en una solucion son:

Generacion de la solucion inicial

La solucion inicial puede ser generada de forma aleatoria o utilizando una heurısti-ca voraz. El uso de esta ultima tecnica es mas complejo pero resulta en una con-vergencia mas rapida.

Definicion del concepto de vecindad

La funcion de vecindad N es un mapeo, N : S → 2S, que asigna a cada solucion sdel espacio de busqueda S un conjunto de soluciones,N(s) ⊂ S. El vecindarioN(s)de una solucion s en un dominio continuo es aquel contenido dentro del espacio concentro s y radio igual a r, siendo r > 0. Para un problema de optimizacion discreto,el vecindario N(s) de una solucion s se representa con el conjunto {s′/d(s′, s) ≤ r},siendo d la distancia entre ambas soluciones. A la solucion s′ en el vecindario des(s′ ∈ N(S)), se le conoce como vecino de s. La eleccion de un buen vecindariomejora las posibilidades de encontrar una buena solucion (junto con el incrementodel tiempo de ejecucion del algoritmo).

La Figura 2.2 muestra una cronologıa de las metaheurısticas mas estudiadas en laliteratura y que en las siguientes secciones se van a describir.

1990 2000

1983SA

1989TS

1995GRASP

1999ILS y GLS

1997VNS

Figura 2.2: Cronologıa de las metaheurısticas estudiadas basadas en una solucion.


2.4.1. Busqueda en escalada

La busqueda en escalada, conocida en ingles como Hill Climbing (HC), es la me-taheurıstica mas sencilla [Russell and Norvig, 2003]. Comienza con una solucioninicial, se explora su vecindad y se selecciona la siguiente solucion.

El algoritmo finaliza cuando una condicion de parada es alcanzada (por ejemplo,existe un numero maximo de iteraciones, una cantidad finita de tiempo de ejecu-cion del algoritmo, etc.), o de forma mas habitual, cuando ninguno de los vecinosmejora la solucion actual. En este caso, se ha encontrado un mınimo local, y portanto, la ultima solucion s se convertira en la mejor solucion encontrada durantela busqueda.

Existen multiples implementaciones de este algoritmo. La mas basica de ellas seexpone en el Algoritmo 1. Otras mejoras en la seleccion del vecino de s podrıanser:

Seleccionar el mejor candidato entre todos los del vecindario de la solucionactual. Esta estrategia necesita generar y evaluar todos los vecinos de lasolucion actual de forma exhaustiva (mayor exploracion).

Seleccionar el primer candidato que mejore la solucion actual. Esta estrategiaevita la exploracion absoluta de todo el vecindario (mayor explotacion). Paraintroducir diversidad en la busqueda, se recomienda generar vecinos de formaaleatoria.

Algoritmo 1 Busqueda en escalada basica

1: procedure HC

2: Dado s ∈ D3: while No se cumpla la condicion de parada do4: Seleccionar s′ ∈ N(s)5: if f(s′) < f(s) then6: s← s′

7: end if8: end while9: end procedure


2.4.2. Recocido simulado

El metodo del recocido simulado, conocido en ingles como Simulated Annealing(SA), tiene sus orıgenes en la fısica estadıstica. Fue propuesto por [Kirkpatricket al., 1983], y de forma independiente por [Cerny, 1985]. El recocido simulado esuno de los muchos tipos de algoritmos de optimizacion estocasticos.

Como el recocido simulado tiene su origen en la fısica, la variable que cuantificael grado de adaptacion de una solucion es conocida como energıa. El objetivo delalgoritmo es encontrar una solucion cuya energıa sea mınima. El proceso de encon-trar una buena solucion comienza con una aproximacion, generalmente aleatoria.

Cada posible solucion tiene asociada una energıa, calculada gracias a una funcionde coste. Siendo E0 la energıa correspondiente a esta primera solucion creada. Apartir de esta solucion, se genera otra con su correspondiente energıa E1. Si segenera de forma muy similar, el algoritmo tardara en converger; y si se genera deforma muy dispar, el algoritmo estara siempre explorando. Una vez obtenidos E0

y E1, se calcula la probabilidad de que esta nueva solucion sea aceptada para lasiguiente iteracion:

p(ΔE) = e−ΔET , (2.3)

siendo ΔE = E0 − E1 y T la temperatura actual.

Se utiliza el algoritmo de [Metropolis et al., 1953] para determinar finalmente quehacer con la nueva solucion generada:

r = R(0, 1) =

{r <= p(ΔE) Aceptar la nueva solucionr > p(ΔE) Rechazar la nueva solucion,

(2.4)

donde R(0, 1) es un numero generado aleatoriamente entre 0 y 1.

El rol de la temperatura juega un papel importante en la ecuacion anterior. Amedida que la temperatura va decreciendo, las posibilidades de tomar solucionespeores en cada iteracion tambien decrecen. Generalmente, para hacer decrecer latemperatura, en cada iteracion se multiplica por un factor α < 1 tal que:

Th = αh × T0 (2.5)


siendo Th la temperatura en la iteracion h. La temperatura inicial sera alta al prin-cipio para evitar caer en un optimo local de forma prematura, e ira disminuyendoacercandose progresivamente a 0. Se iterara realizando las operaciones anterioreshasta que se cumpla una o varias condiciones de parada preestablecidas.

Un ejemplo de condicion de parada podrıa ser ser si pasadas L iteraciones ya no semejora la solucion o se alcanza una temperatura mınima. El factor de enfriamientoafecta de forma significativa al rendimiento del algoritmo. Un estudio sobre dichofactor se puede encontrar en [Nourani and Andresen, 1998].

El pseudocodigo 2 define el algoritmo descrito anteriormente. SA puede ser facil-mente implementado para obtener buenas soluciones si se tienen en cuenta ciertasprecauciones. Primero, la temperatura inicial debe ser lo suficientemente alta. Unatemperatura baja puede resultar en la caıda en un mınimo local, y una temperaturademasiado alta provoca que se complique la obtencion de una solucion optima.

Algoritmo 2 Recocido simulado

1: procedure SA

2: Dado s ∈ D3: s∗ ← s /* mejor solucion */4: Inicializar T /* parametro de temperatura */5: while No se cumpla la condicion de parada do6: Seleccionar un vecino s′ ∈ N(s)7: ΔE = f(s)− f(s′)8: if ΔE > 0 then9: s← s′

10: else11: p = e−

ΔET

12: if R(0, 1) ≤ p then13: s← s′

14: end if15: end if16: Actualizar T /* Decrementar T si fuera necesario*/17: end while18: end procedure

SA se ha aplicado de forma exitosa tanto para problemas de optimizacion discretacomo continua. En [Cai and Ma, 2010] se estudia la adaptacion de SA al dominiocontinuo. Una revision extensa del recocido simulado puede encontrarse en [Sumanand Kumar, 2006].


2.4.3. Busqueda tabu

El algoritmo de la busqueda tabu, conocido en ingles como Tabu Search (TS), fuepropuesto por [Glover, 1989]. Este metodo utiliza la informacion obtenida durantelas distintas iteraciones para realizar una busqueda mas eficiente. Como en el casodel SA, tambien acepta soluciones que no mejoran la actual para poder salir delos mınimos locales. Sin embargo, el algoritmo de TS busca dentro del vecindariode forma determinista, al contrario que SA que realiza una busqueda aleatoria.La caracterıstica que identifica el algoritmo de TS es el uso de una memoria quepreviene soluciones ya visitadas.

La busqueda comienza con la seleccion de una solucion inicial aleatoria. Cuando sealcanza un mınimo local, el metodo acepta un vecino que no mejore a la solucionactual. En este caso, es posible que la solucion final no sea la mejor encontrada du-rante la busqueda, por lo que es necesario memorizar la mejor solucion s*. Despuesde seleccionar un vecino que no mejora, puede llegar a ocurrir que la siguiente solu-cion genere un ciclo entre ambas soluciones. Para evitar esta situacion, TS prohıbevisitar soluciones que han sido recientemente obtenidas mediante una memoria.Esta memoria, llamada lista tabu, almacena las ultimas soluciones encontradas.Una solucion de la lista puede ser utilizada si conlleva una mejora de la solucions*. A este mecanismo se le conoce como criterio de aspiracion.

El pseudocodigo 3 define el algoritmo descrito anteriormente.

Algoritmo 3 Busqueda tabu

1: procedure TS

2: Dado s ∈ D3: s∗ ← s /* mejor solucion */4: T ← ∅ /* lista tabu vacıa */5: while No se cumpla la condicion de parada do6: Seleccionar el mejor vecino s′ ∈ N(s), s′ /∈ T7: s← s′

8: Actualizar T9: if f(s) < f(s∗) then10: s∗ ← s11: end if12: end while13: end procedure


La longitud de la lista tabu controla la memoria del proceso de busqueda. Si la lon-gitud es muy pequena, la busqueda se centrara en areas muy pequenas del espaciode busqueda. Por el contrario, si la longitud es muy alta, forzara al algoritmo abuscar en regiones muy extensas. Esta longitud puede variar durante la busqueda,aumentando la robustez del algoritmo. Se pueden introducir estructuras adicio-nales de memoria a plazo intermedio para propiciar movimientos hacia areas masprometedoras dentro del espacio de busqueda (explotacion), ası como estructurasde memoria a largo plazo para fomentar una exploracion mas amplia del espaciode busqueda (exploracion).

El llamado criterio de aspiracion, puede mejorar extremadamente el proceso debusqueda. De hecho, el uso de una lista tabu puede prevenir soluciones atractivas(que conlleven en iteraciones futuras a una mejor solucion), incluso si no hayriesgo de llegar a un ciclo, o puede conllevar a un estancamiento en el procesode busqueda. El criterio de aspiracion es un conjunto de reglas cuyo objetivo esinvalidar las restricciones de la lista tabu para poder evitar estas situaciones.

Una memoria de frecuencias puede ser utilizada como memoria a largo plazo.Esta memoria registra cuantas veces los atributos de cada solucion son evaluados,permitiendo ası evitar aquellas soluciones cuyos atributos se han repetido masveces, o al contrario, aquellos que rara vez aparecen.

La eficacia del algoritmo TS depende de la seleccion apropiada del operador devecindad y del espacio de busqueda. Esto requiere un conocimiento profundo delproblema a tratar. Ademas, la exploracion debe ser aplicada con atencion para evi-tar atascarse en mınimos locales. Igualmente, la lista tabu debe ser cuidadosamenteformulada para hacer la busqueda eficaz, minimizando el tiempo de computaciony la memoria empleada. La mejor caracterıstica de TS es su capacidad para evitarciclos.

Se han propuesto mejoras al esquema original de TS para realizar procesos debusqueda mas efectivos. Una de las variaciones es almacenar los atributos de lassoluciones en vez de las propias soluciones en la busqueda tabu. Esto reduce eltiempo y la memoria necesitada por el algoritmo. Los avances del algoritmo TSse centran en una mejor explotacion de la informacion obtenida, operadores devecindad mas eficientes, mejoras en la generacion de las soluciones iniciales o enla paralelizacion del algoritmo. Una descripcion extensa de dichos avances puedeencontrarse en [Gendreau, 2003]. TS fue disenado inicialmente para la resolucionde problemas de optimizacion combinatorios, pero se han realizado estudios parasu adaptacion al dominio continuo como en [Chelouah and Siarry, 2000].


2.4.4. Otros algoritmos

2.4.4.1. Busqueda de vecindario variable

La busqueda de vecindario variable, conocida en ingles como Variable Neighbor-hood Search (VNS), fue propuesta por [Mladenovic and Hansen, 1997]. Su estra-tegia consiste en la exploracion de vecindarios dinamicos dada una solucion. En lafase de inicializacion, es definido un conjunto de estructuras de vecindario. Estosvecindarios pueden ser seleccionados de forma arbitraria. A continuacion, se gene-ra una solucion inicial, y comienza el ciclo principal de VNS. Este ciclo consiste entres etapas: shaking, busqueda local y seleccion. En la fase de shaking, una solu-cion s′ es seleccionada de forma aleatoria en el vecindario n de la solucion actual s.Entonces, s′ se utiliza como solucion inicial del procedimiento de busqueda local,para generar la solucion s′′. La busqueda local puede utilizar cualquier estructurade vecindario. Al final del proceso de busqueda local, si s′′ es mejor que s, enton-ces s′′ reemplaza a s y comienza el ciclo de nuevo con n = 1. En caso contrario,el algoritmo se mueve al vecindario siguiente n+ 1 y comienza una nueva fase deshaking con este vecindario. Este algoritmo es eficiente si los vecindarios utilizadosson complementarios, por ejemplo si un optimo local en el vecindario Ni no lo espara Nj. Una revision extensa del algoritmo VNS puede encontrarse en [Hansenet al., 2010].

2.4.4.2. Busqueda local guiada

La busqueda local guiada, conocida en ingles como Guided Local Search (GLS),fue propuesta por [Voudouris and Tsang, 1999]. GLS hace uso de una memoriallamada funcion objetivo aumentada. De hecho, GLS cambia de forma dinamicala funcion objetivo a optimizar por la busqueda local, de acuerdo al optimo localencontrado. Primero, un conjunto de atributos se define. Cada atributo define unacaracterıstica de una solucion acorde al problema de optimizacion a resolver. Acontinuacion, un coste ci y un valor de penalizacion pi son asociados con cada atri-buto. Las penalizaciones son inicializadas a 0 y actualizadas cuando la busquedalocal alcanza un optimo local. Cada vez que un optimo local es encontrado, GLSintenta penalizar los atributos menos favorables de dicho optimo (por ejemplo siestos tienen un alto coste). De esta forma, las soluciones que muestran otros atri-butos se vuelven mas atractivas, y la busqueda es capaz de escapar del mınimolocal. Una revision extensa del algoritmo GLS puede encontrarse en [Voudouriset al., 2010].


2.4.4.3. Busqueda local iterativa

La busqueda local iterativa, conocida en ingles como Iterated Local Search (ILS),fue propuesta por [Stutzle, 1999]. ILS es una metaheurıstica basada en una ideasencilla: en vez de aplicar de forma repetida un procedimiento de busqueda locala soluciones iniciales aleatorias, ILS genera la solucion para la siguiente iteracionmediante modificaciones sobre el optimo local encontrado en la iteracion actual.Este mecanismo de modificaciones es clave para ILS: por un lado, una modificacionpequena puede no ser suficiente para escapar de un mınimo local, pero por otrolado, una gran modificacion puede implicar una busqueda aleatoria.

El criterio de aceptacion, combinado con el mecanismo de modificacion, permitecontrolar el equilibrio entre explotacion y exploracion. Por ejemplo, un criterioextremo de aceptacion en terminos de explotacion solo aceptarıa soluciones quemejorasen la actual. Otro criterio extremo en terminos de exploracion serıa aceptarcualquier solucion, sin importar su calidad. Una revision extensa del algoritmo ILSpuede encontrarse en [Lourenco et al., 2010].

2.4.4.4. Procedimiento voraz de busqueda aleatorio y adaptativo

El procedimiento voraz de busqueda aleatorio y adaptativo, conocido en inglescomo Greedy Randomized Adaptive Search Procedure (GRASP) [Feo and Resende,1995], consiste en ejecutar dos fases bien diferenciadas de forma iterativa: la pri-mera construye una solucion factible usando una heurıstica voraz; y la segunda,realiza una busqueda local sobre dicha solucion. Despues de un numero dado deiteraciones, el algoritmo GRASP termina y devuelve la mejor solucion encontrada.

En la heurıstica voraz, una solucion candidata es creada de forma iterativa, porejemplo, en cada iteracion, un elemento es incorporado a una solucion parcialhasta llegar a una solucion completa. Por tanto, dado un determinado problema,se debe definir una solucion como un conjunto de elementos. En cada iteracion dela heurıstica, la lista de elementos candidatos esta formada por todos los elementosque pueden ser incluidos en la solucion parcial, manteniendo la factibilidad. La listaes ordenada respecto a la funcion voraz, que mide el beneficio de seleccionar cadaelemento. A continuacion, el elemento a anadir a la solucion parcial es escogido deforma aleatoria entre los mejores candidatos de la lista. A la lista de los mejorescandidatos se le llama RCL. Esta seleccion aleatoria representa la parte estocasticade GRASP. Una revision extensa del algoritmo GRASP puede encontrarse en[Resende and Ribeiro, 2016].

2.5. METAHEURISTICAS BASADAS EN POBLACIONES 17

2.5. Metaheurısticas basadas en poblaciones

Las metaheurısticas basadas en poblaciones aplican los conceptos de generacion yreemplazo sobre una familia de soluciones repartidas por el espacio de busqueda.Se inicializa un conjunto de soluciones, y a continuacion, se itera y manipula paragenerar un nuevo conjunto. El nuevo conjunto de soluciones es seleccionado apartir del conjunto de soluciones nuevas y existentes, utilizando una estrategia dereemplazo. Este proceso continua hasta que se cumple el criterio de parada. Losprincipales conceptos de estos algoritmos son:

Poblacion inicial: una buena inicializacion de la poblacion implica un algo-ritmo mas eficiente. La inicializacion puede ser aleatoria, secuencial, paralela,mediante una heurıstica...

Criterio de parada: el criterio de parada puede ser un numero fijo deiteraciones, un valor mınimo de la funcion objetivo o un maximo numero deiteraciones sin mejorar...

Los metodos mas estudiados basados en poblaciones estan relacionados con lacomputacion evolutiva (Evolutionary Computation), inspirados por las teorıas evo-lutivas de [Darwin, 1859] y la inteligencia colectiva (Swarm Intelligence), que pro-duce una inteligencia computacional a partir de simples analogıas de las diferentesinteracciones sociales.

1980 1990 2000

1992ACO

1995PSO

1975GA

1997DE

1992GP

1996EDA1977

SS 1997MA

Figura 2.3: Cronologıa de las metaheurısticas estudiadas basadas en poblaciones.


2.5.1. Computacion evolutiva

La computacion evolutiva (EC) es el termino general para los diferentes algoritmosde optimizacion que estan inspirados en los principios Darwinianos, aquellos queexplican la evolucion de lo seres vivos, donde solo los mejores adaptados sobrevi-ven. Generalmente todos los algoritmos agrupados en esta categorıa comparten lamisma idea de simular la evolucion de individuos mediante procesos de seleccion,recombinacion y mutacion, y con ello, produciendo mejores soluciones.

Todos los algoritmos evolutivos siguen en general el Algoritmo 4. Cada iteraciondel algoritmo corresponde con una generacion, donde una poblacion de solucio-nes candidatas para un problema dado de optimizacion, llamados individuos, escapaz de reproducirse y esta sujeta a variaciones geneticas seguidas por la pre-sion del entorno que causa la seleccion natural (supervivencia del mas apto). Secrean nuevas soluciones combinando dos o mas individuos seleccionados (llamadospadres) para generar nuevos individuos (llamados hijos o descendencia), y apli-cando mutacion sobre individuos para incrementar la diversidad de la poblacion.Se evalua la adaptacion de las soluciones (como de buenas son) y se aplica unaestrategia de seleccion para determinar que soluciones pasan a la siguiente gene-racion. Como condicion de parada, generalmente se utiliza un numero predefinidode generaciones (o de evaluaciones) en el proceso evolutivo.

EC se ha aplicado con gran exito a problemas de optimizacion combinatorios[Bianchi et al., 2009]. Una revision extensa de los algoritmos evolutivos multi-objetivo puede encontrarse en [von Lucken et al., 2014]. Tıpicamente tambien sepueden hibridizar estos algoritmos con otros metodos de busqueda [Blum et al.,2011]. En [Martınez et al., 2011] se revisan los metodos que automaticamenteseleccionan sus parametros (self-adaptive).

Algoritmo 4 Procedimiento general en computacion evolutiva

1: procedure EC

2: Generar la poblacion Pi con individuos aleatorios3: while No se cumpla la condicion de parada do4: Seleccionar individuos como padres de Pi

5: Aplicar operadores de busqueda (reproduccion, mutacion)6: Evaluar a los nuevos individuos mediante una funcion objetivo7: Construir una nueva poblacion Pi+1

8: end while9: end procedure


2.5.1.1. Algoritmos geneticos

Los algoritmos geneticos, conocidos en ingles como Genetic Algorithms (GA), fue-ron propuestos inicialmente por [Holland, 1975, Goldberg and Holland, 1988].Inspirados en la teorıa de la evolucion de Darwin, son unas de las tecnicas decomputacion evolutiva mas estudiadas y extendidas.

GA comienza con un conjunto de soluciones o poblacion inicial, que puede sergenerado con multiples tecnicas. Los individuos pueden ser codificados como ca-denas binarias, estructura de arbol, vectores de numeros reales, etc. dependiendodel problema a resolver. A cada solucion codificada se le llama cromosoma, siendocada variable de decision del cromosoma un gen. A partir de la poblacion actual,un conjunto de individuos es seleccionado segun un criterio preestablecido paraser utilizados en la siguiente etapa. Este criterio de seleccion esta basado en unafuncion de evaluacion (como de bueno es cada individuo). Algunos criterios deseleccion pueden ser los siguientes:

Seleccion por ruleta

En este caso, la probabilidad de seleccion de un individuo es directamenteproporcional a su valor en la funcion de evaluacion.

Seleccion ordenada

En esta seleccion, el valor de la funcion de evaluacion es asociado a cadaindividuo y se ordena de peor a mejor. Despues, el operador de seleccion porruleta es aplicado con los valores de aptitud de su orden.

Seleccion por torneo

En esta metodo, un conjunto de individuos son escogidos de forma aleatoriay los mejores entre ellos son seleccionados.

Seleccion elitista

En este esquema, se mantiene un numero fijo de los mejores individuos yla poblacion restante se genera usando cualquiera de los procedimientos deseleccion discutidos anteriormente. Esto ayuda a preservar la mejor solucionen la poblacion.

De los individuos seleccionados, llamados padres, se generaran nuevos individuos,su descendencia. Estas nuevas soluciones se crean aplicando operadores de crucey mutacion sobre los padres :


Operadores de cruce

El operador de cruce se utiliza para generar la descendencia que heredelas caracterısticas de sus padres. La probabilidad de utilizar este tipo deoperador sobre el de mutacion es muy alta. Algunos tipos de tecnicas sonel cruce basado en un punto, en dos puntos, uniforme, BLX, lineal, BLX-α,morfologico... Una revision completa de los diferentes operadores de crucepuede encontrarse en [Umbarkar and Sheth, 2015].

Operador de mutacion

El operador de mutacion se aplica con una probabilidad realmente pequena.Su funcion es realizar pequenos cambios sobre alguno de los individuos selec-cionados, con el fin de ayudar a la exploracion del algoritmo sobre el espaciode busqueda, pues aumenta la diversificacion de la poblacion.

El siguiente paso es generar una nueva poblacion. Para ello, se pueden seguirdiferentes estrategias a la hora de reemplazar la generacion anterior:

Reemplazo generacional

El reemplazo tiene efecto en la totalidad de la poblacion, donde la descen-dencia generada reemplazara sistematicamente a toda la poblacion padre.

Reemplazo steady-state

En cada generacion, unicamente uno de los hijos creados puede que reemplaceal peor individuo de la poblacion.

Reemplazo elitista

Estrategia que combina las dos anteriores, donde se reemplaza parte de lapoblacion, siendo esta una combinacion de padres e hijos.

GA, por su metodologıa, puede paralelizarse facilmente, por lo que es una buenatecnica para resolver problemas complejos de optimizacion. Sin embargo, puedesufrir de convergencia prematura. La eficacia del algoritmo se basa en la seleccionde la funcion de evaluacion, el tamano de la poblacion y la probabilidad de cruce ymutacion. Por lo tanto, estos parametros deben ser cuidadosamente seleccionados.Un tamano de poblacion mayor y un gran numero de generaciones aumentan laprobabilidad de obtener una solucion global optima, pero aumenta sustancialmenteel tiempo de procesamiento. Una revision de GA puede encontrarse en [Lim, 2014].


2.5.1.2. Evolucion diferencial

El algoritmo de Evolucion Diferencial (DE), conocido en ingles como DiferentialEvolution, es uno de los mas populares para la resolucion de problemas de op-timizacion global en espacios continuos. Propuesto inicialmente por [Storn andPrice, 1997] para la resolucion del problema de ajuste de polinomios de Chebys-hev, ha resultado ser un metodo de optimizacion capaz de resolver multiples tareasdiferentes.

DE comienza la busqueda generando una poblacion inicial aleatoria. Cada soluciones un vector de numeros reales, por lo que DE es uno de los algoritmos maspropicios para optimizaciones continuas. En cada generacion, un nuevo conjuntode soluciones candidatas es creado. DE, en vez de utilizar los habituales operadoresde cruce, hace uso de un operador de recombinacion basado en combinacion lineal.La descendencia reemplaza a los padres solo si esta es mejor. Un hijo es creadopor la mutacion de los individuos existentes, escogidos de forma aleatoria entre lapoblacion.

Algoritmo 5 Evolucion diferencial

1: procedure DE

2: Generar la poblacion Pi con individuos aleatorios3: Evaluar cada individuo con la funcion objetivo f(Pi)4:

5: while No se cumpla la condicion de parada do6:

7: Seleccionar 3 padres de forma aleatoria Pa, Pb y Pc

8: for Para cada cromosoma Pi(x) do9: if aleatorio(x) < C then10: P ′

i (x)← Pa(x) + F × (Pb(x)− Pc(x)) /* Cruce binomial */11: else12: P ′

i (x)← Pi(x)13: end if14: end for15:

16: if f(P ′i ) < f(Pi) then

17: Pi ← P ′i

18: end if19: end while20: end procedure


La notacion DE/x/y/z es generalmente utilizada para definir la estrategia delalgoritmo DE [Price et al., 2005], donde x representa una cadena de texto cuyovalor expresa el vector base, es decir, el vector que se esta modificando, el cualpuede ser rand (se selecciona un vector de forma aleatoria de la poblacion) o best(se selecciona el mejor vector de la poblacion gracias a la funcion objetivo); y es elnumero de vectores de diferencia que se emplean a la hora de modificar el vectorbase x ; y z fija el tipo de cruce, que puede ser binomial o exponencial. El primeroes similar al cruce uniforme y el segundo similar al cruce basado en dos puntosde los algoritmos geneticos. El Algoritmo 5 describe la variante DE/rand/1/bin,conocida como la version clasica de DE.

La principal ventaja de la evolucion diferencial consiste en sus pocos parametrosde control. Solo tiene tres parametros de entrada para controlar el proceso debusqueda, el tamano de la poblacion, el factor de escala F, que controla el gradode amplitud de la variacion diferencial, y la constante de cruce C. En el algoritmooriginal DE, los parametros de control se mantienen constantes durante todo elproceso de busqueda. La eleccion de estos parametros depende del problema aresolver. Algunos estudios como [Dragoi and Dafinescu, 2016] han desarrolladoestrategias para hacer el ajuste de los parametros auto-adaptativos acorde a laexperiencia de aprendizaje.

La convergencia del algoritmo DE puede ser controlada cambiando el numero depadres y el factor de escala. Estos parametros pueden ser ajustados para alcanzarel equilibro entre una convergencia rapida y la robustez del algoritmo. Incrementarel numero de padres y reducir el factor de escala hace que la convergencia sea masfacil pero implica un coste computacional mas alto. La constante de cruce C essolo un parametro de ajuste en DE y no tiene un gran impacto en la velocidad ala hora de converger.

DE es actualmente una de las metaheurısticas mas populares para resolver proble-mas de optimizacion en espacios de busqueda continuos. Sin embargo, DE tieneciertas desventajas, como una convergencia lenta o el estancamiento de la pobla-cion. Diversas versiones modificadas de DE estan disponibles en la literatura paramejorar el rendimiento del DE basico. Por ejemplo, se han desarrollado versioneshıbridas, donde se combina DE con otros algoritmos de busqueda. Una revisionextensa de la evolucion diferencial y sus aplicaciones puede encontrarse en [Neriand Tirronen, 2010], [Das and Suganthan, 2011] y [Das et al., 2016].


2.5.1.3. Programacion genetica

La programacion genetica, conocida en ingles como Genetic Programming (GP),fue propuesta por [Koza, 1992]. GP es muy similar a GA, siendo la principaldiferencia que los individuos son programas en sı mismos. La representacion enarbol es utilizada, representando las hojas (terminales) de estos las variables ylas constantes; y los nodos internos, las operaciones aritmeticas (funciones). Portanto, es necesario tener operadores especıficos para gestionar dichos arboles. Losoperadores de cruce intercambian sub-arboles y los de mutacion realizan cambiosaleatorios sobre estos. Una de las mayores dificultades de GP es la longitud variableen la codificacion de los programas.

Los fundamentos teoricos de GP, ası como una revision de las muchas aplicacionesdel mundo real y los avances mas importantes de GP se pueden encontrar en [Mc-kay et al., 2010]. Actualmente GP se utiliza ampliamente en tareas de aprendizajeautomatico y de minerıa de datos, como por ejemplo en prediccion y clasificacion.Tambien hay bastante literatura sobre GP utilizando modelos probabilısticos. En[Kim et al., 2014] se estudia con mas profundidad este area.

2.5.1.4. Algoritmos memeticos

Los algoritmos memeticos, conocidos en ingles como Memetic Algorithms (MA),fueron propuestos por [Moscato, 1989]. La idea principal de los algoritmos memeti-cos es combinar los conceptos evolutivos de GA (supervivencia por el grado deadaptacion y herencia entre padres y descendencia) con la idea de que cada indivi-duo de la poblacion se desarrolle por cuenta propia durante su existencia (busquedalocal).

En MA, los agentes son unidades de procesamiento capaces de contener multiplessoluciones (individuos de GA) y metodos para mejorarlos. Estos agentes interac-cionan entre ellos a traves de metodos de cooperacion y competicion.

MA explota el conocimiento del problema incorporando heurısticas, algoritmos deaproximacion, tecnicas de busqueda local y metodos exactos. Su objetivo es crearun equilibrio entre la capacidad exploratoria de GA y la capacidad de explotacionde los algoritmos de busqueda local. Es muy importante para la eficacia de MAuna correcta codificacion de las soluciones. Una revision extensa de MA puedeencontrarse en [Neri and Cotta, 2012].


2.5.1.5. Algoritmos de estimacion de la distribucion

Los algoritmos de estimacion de la distribucion, conocidos en ingles como Esti-mation of Distribution Algorithms (EDA), fueron introducidos en el campo de lacomputacion evolutiva por primera vez por [Muhlenbein and Paaß, 1996]. Estosalgoritmos estan basados en modelos probabilısticos donde los operadores de cru-ce y mutacion de los algoritmos geneticos cambian por los siguientes pasos: (1)estimar la distribucion de probabilidad de los individuos seleccionados (solucionesprometedoras) y (2) generar una nueva poblacion mediante el muestreo de estadistribucion de probabilidad. Esto significa que la busqueda sera dirigida haciaareas prometedoras del espacio de busqueda. Las nuevas soluciones son incorpora-das a la poblacion original, reemplazando individuos de generaciones pasadas. Eltipo de modelo probabilıstico utilizado por un EDA y los metodos empleados paraaprenderlo puede variar segun las caracterısticas del problema de optimizacion.

Basandose en estas ideas, diferentes aproximaciones de EDA se han desarrolladoen los ultimos anos, done cada aproximacion aprende un modelo probabilıstico enconcreto que condiciona el comportamiento del EDA tanto a nivel de rendimientocomo de complejidad. [Larranaga and Lozano, 2001] realiza una clasificacion entres categorıas segun el nivel de complejidad para obtener las inter-dependenciasentre las variables : EDA univariado, que asume la total independencia entre lasvariables del problema; EDA bivariado, aquel que tienen en cuenta la dependenciaentre pares de variables; y multivariado, al EDA que pueden modelar con precisionel problema, incluso estructuras muy complejas con bloques de construccion multi-variantes que se superponen. Una revision extensa de los algoritmos de estimacionde la distribucion puede encontrarse en [Larranaga et al., 2012].

2.5.1.6. Busqueda dispersa

La busqueda dispersa, conocida en ingles como Scatter Search (SS), junto con sugeneralizacion con Path Relinking (PR), fue propuesto por [Glover, 1997]. Los con-ceptos y principios fundamentales de este metodo fueron introducidos en [Glover,1977] donde se combinaban reglas de decision con restricciones del problema. SSy PR se diferencian de otros algoritmos evolutivos por proporcionar principios deunificacion para juntar soluciones basadas en construcciones de caminos genera-lizados (tanto en espacios euclıdeos como de vecindarios) y por utilizar disenosestrategicos donde otros metodos recurren a la aleatoriedad. Una revision extensade SS y PR puede encontrarse en [Resende et al., 2010].


2.5.2. Inteligencia colectiva

La inteligencia colectiva, conocida en ingles como Swarm Intelligence (SI), es unparadigma innovador para la resolucion de problemas de optimizacion que se ins-pira en el comportamiento colectivo de grupos de colonias de insectos sociales ode otro tipos de sociedades animales.

Los sistemas SI se componen tıpicamente de una poblacion de agentes sencillos(una entidad capaz de realizar determinadas operaciones) que interactuan de formalocal entre ellos y con su entorno. Estas entidades, a pesar de tener una capaci-dad individual muy limitada, pueden conjuntamente de forma cooperativa reali-zar muchas tareas complejas que son necesarias para su supervivencia. Aunqueno hay normalmente una estructura de control centralizada que dirija como de-ben comportarse estos agentes individuales, las interacciones entre dichos agentesgeneralmente implican un comportamiento global y auto-organizado.

Algunos algoritmos inspirados en este tipo de comportamientos pero que no serandescritos en las siguientes secciones son:

Sistemas inmunologicos artificiales [Farmer et al., 1986].

Optimizacion por forraje bacterial [Passino, 2002].

Optimizacion por colonia de abejas [Karaboga, 2005].

Optimizacion basada en bio-geografıas [Simon, 2008].

Busqueda de cuculidos [Yang and Deb, 2009].

Algoritmo de caıda inteligente de gotas de agua [Shah-Hosseini, 2009].

Algoritmo murcielago [Yang, 2010].

Algoritmo luciernaga [Fister et al., 2013].

En [Engelbrecht, 2006] se puede encontrar los modelos matematicos de este com-portamiento colectivo de los insectos sociales y como gracias a ellos se puedenresolver problemas de optimizacion. Una revision mas extensa de este paradigmapuede encontrarse en [Das et al., 2008] y [Kar, 2016].


2.5.2.1. Optimizacion por enjambre de partıculas

La optimizacion por enjambre de partıculas, conocida en ingles como ParticleSwarm Optimization (PSO), es una tecnica estocastica basada en poblacionesdesarrollada por [Kennedy and Eberhart, 1995], inspirada por el comportamientosocial de los bancos de peces o bandadas de pajaros. PSO comparte bastantes simi-litudes con las tecnicas de computacion evolutiva como pueden ser los algoritmosgeneticos. El sistema es inicializado con una poblacion de soluciones aleatoriasy busca la optima mediante una evolucion de las generaciones. Sin embargo, alcontrario que los algoritmos geneticos, PSO no tiene operadores evolutivos comoel cruce o la mutacion. En PSO, las soluciones potenciales, llamadas partıculas,vuelan a traves del espacio de soluciones siguiendo a las partıculas no dominadasdel momento.

Como se ha introducido anteriormente, PSO simula el comportamiento de las ban-dadas de pajaros. Supongase el siguiente escenario: un grupo de pajaros buscandode forma aleatoria comida en un area determinada. Solo hay un sitio concreto delarea de busqueda con comida y todos los pajaros saben como de lejos estan conrespecto de la comida en cada iteracion. ¿Como saber la mejor estrategia paraencontrar la comida? La respuesta correcta es seguir al pajaro que se encuentremas cerca de la comida.

PSO aprende de la situacion anterior y la utiliza para resolver problemas de opti-mizacion. En PSO, cada solucion es un pajaro en el espacio de busqueda. Todaslas partıculas tienen asociado un valor calculado por una funcion de adaptacion,la cual es la que se quiere optimizar, y las velocidades que dirigen el vuelo de laspartıculas. Las partıculas vuelan a traves del espacio de busqueda siguiendo lapartıcula optima actual.

PSO es inicializada con un grupo de partıculas aleatorias (soluciones) y comienzala busqueda mediante la actualizacion de dichas partıculas. En cada iteracion, cadapartıcula es actualizada con los dos tipos de valores. El primero es la mejor solucionencontrada hasta el momento (tambien se guarda este valor de adaptacion) por lapropia partıcula. A este valor le llamaremos pBest. Otro mejor valor del que laspartıculas realizan un seguimiento es el mejor valor obtenido hasta el momentopero de todo el conjunto de la poblacion. A este valor le llamaremos gBest. Cuandouna partıcula forma parte de una poblacion que sigue una topologıa concreta devecindades, este valor sera local y lo llamaremos lBest. Despues de encontrar losdos mejores valores, las partıculas actualizan su velocidad y posiciones con lasecuaciones 2.6 y 2.7.


v[] = v[]+c1∗rand()∗(pBest[]−present[])+c2∗rand()∗(gBest[]−present[]) (2.6)

present[] = present[] + v[](b) (2.7)

Descripcion de las ecuaciones:

v[] es la velocidad de la partıcula.present[] es la partıcula actual (solucion).pBest[] y gBest[] definen lo descrito anteriormenterand() es un numero aleatorio en el intervalo (0, 1).c1 y c2 son factores de aprendizaje, generalmente c1 = c2 = 2.

Algoritmo 6 Optimizacion por enjambre de partıculas

1: procedure PSO

2: Inicializar la poblacion de partıculas con posiciones y velocidades aleatorias3: while No se cumpla la condicion de parada do4: for Cada partıcula i do5: Adaptar la velocidad e la partıcula usando la ecuacion 2.66: Actualizar la posicion de la partıcula usando la ecuacion 2.7

7: Evaluar la adaptacion f(−→X i)

8: if f(−→X i) < f(

−−−→pBesti) then

9:−−−→pBesti ← −→X i

10: end if11: if f(

−→X i) < f(

−−−→gBest) then

12:−−−→gBest← −→X i

13: end if14: end for15: end while16: end procedure

Las velocidades de las partıculas en cada dimension estan sujetas a una velocidadmaxima vMax. Si la suma de las aceleraciones causa que la velocidad en esa di-mension supere vMax, que es un parametro especificado por el usuario, entoncesla velocidad en esa dimension se limita a vMax.

Una revision de la optimizacion por enjambre de partıculas puede encontrarse en[Bonyadi and Michalewicz, 2017].


2.5.2.2. Optimizacion por colonia de hormigas

La optimizacion por colonia de hormigas, conocida en ingles como Ant ColonyOptimization (ACO), se basa en el comportamiento cooperativo de las hormigas[Dorigo, 1992]. Las hormigas son capaces de encontrar el camino mas corto a lacomida siguiendo el rastro de un camino de feromonas que han dejado otras hormi-gas que buscaban comida. El mismo principio se aplica para resolver problemas deoptimizacion. Las hormigas mientras buscan la comida van depositando feromonasa su paso. Como las hormigas que tomaron el camino mas corto empiezan a volverantes al punto de partida, la concentracion de feromonas por ese camino se incre-menta. Este hecho implica que el camino mas corto sera seguido finalmente portodas las hormigas. Este principio sera empleado en los problemas de optimizacionpara encontrar la mejor solucion.

ACO utiliza hormigas artificiales como procedimiento estocastico iterativo para lageneracion de soluciones. El proceso comienza con la generacion de un conjuntoaleatorio de hormigas. La concentracion de feromonas asociada a cada ruta se iraactualizando con el paso de las hormigas en mayor o menor medida segun unafuncion de evaluacion determinada por el problema. Segun vaya mejorando la so-lucion, la concentracion de feromonas aumenta. En funcion de la concentracion deferomonas, los caminos de las hormigas van cambiando. La evaporacion de feromo-nas es necesaria para evitar caer en mınimos locales y evitar ası una convergenciaprematura.

Algoritmo 7 Optimizacion por colonia de hormigas

1: procedure ACO

2: Inicializar el valor de las feromonas3: while No se cumpla la condicion de parada do4: for all Hormigas do5: Construir las soluciones usando el camino de feromonas6: Actualizar el camino de feromonas (evaporacion, refuerzo)7: end for8: end while9: end procedure

Una revision extensa de la optimizacion por colonia de hormigas puede encontrarseen [Dorigo and Stutzle, 2010].

2.6. MULTI-OBJETIVO 29

2.6. Multi-objetivo

Como se ha mencionado anteriormente, las metaheurısticas son una herramientapotente para resolver problemas de optimizacion complejos con un unico objetivo.Sin embargo, la mayorıa de problemas del mundo real tienen dos o mas criteriosde optimizacion, estando en algunos casos en conflicto entre ellos.

Un problema multi-objetivo se define por un conjunto de soluciones D - el espaciode decisiones - y un conjunto de n(n ≥ 2) funciones de evaluacion fi que asocian acada solucion s n valores, generalmente valores reales, que representan su calidaden funcion de diferentes criterios. Este problema se describe como:

optimizar(F (S)) = (f1(s), f2(s), ..., fn(s)) (2.8)

donde la funcion de evaluacion fi debe ser optimizada (maximizada o minimizada).

A diferencia de la optimizacion uni-objetivo, en este tipo de problemas existeun conjunto de soluciones que representan los mejores trade-offs entre todos losobjetivos. Por tanto, es necesario definir un nuevo concepto de optimalidad [Pareto,1896].

A una solucion factible s∗ ∈ D se le llama optimo de Pareto (tambien llamadaeficiente o no-dominada), si, y solo si, no existe otra solucion s ∈ D, tal que sdomine a s∗, donde una solucion s1 domina a una solucion s2, en un contextode minimizacion, si y solo si ∀i ∈ [1...n], fi(s1) ≤ fi(s2) y ∃i ∈ [1...n], tal quefi(s1) < fi(s2).

En este contexto, cualquier solucion del conjunto de optimos de Pareto puede serconsiderada como optima, pues no se puede encontrar una mejora para todas lasfunciones de evaluacion de forma simultanea. Por tanto, una mejora en uno de losvalores de un objetivo supondrıa la degradacion del valor de otro objetivo. Cuandose dibujan los valores de la funcion objetivo correspondiente a las soluciones delconjunto de optimos de Pareto en el espacio objetivo, se obtiene el llamado frentede Pareto.

Por lo tanto, la resolucion de un problema de optimizacion multi-objetivo constarade dos fases: una busqueda de las mejores soluciones no-dominadas repartidas lomejor posible por el espacio de busqueda; y la seleccion de una solucion final.


2.6.1. Clasificacion de las metaheurısticas multi-objetivo

Las metaheurısticas multi-objetivo pueden ser clasificadas en cuatro categorıas[Coello et al., 2010]:

Aproximacion escalar

Transforman el problema en uno o mas problemas con un unico objetivo.Estos metodos requieren un conocimiento a priori del problema para poderdefinir las preferencias entre los objetivos, y generalmente obtiene una unicasolucion por ejecucion.

Basadas en poblaciones

Esta tecnica hace uso de la poblacion empleada en diferentes metaheurısticas(como los algoritmos evolutivos) para combinar de forma escalar diferentesprocedimientos de busqueda en una unica ejecucion. Esta metodologıa con-tradice la nocion de optimalidad de Pareto, por lo que rara vez es utilizada.

Basadas en la optimalidad de Pareto

En esta aproximacion, el mecanismo de seleccion incorpora el concepto deoptimalidad de Pareto. Generalmente se crea una clasificacion con las solu-ciones variando la forma de ordenar las soluciones no-dominadas.

Basadas en indicadores

En este caso, en vez de usar la clasificacion de Pareto, una medida de evalua-cion del rendimiento es utilizada para la seleccion de las soluciones [Zitzleret al., 2003]. En la Seccion 2.6.2 se profundiza mas sobre estas medidas.

2003 2006 2009

2002NSGA-II

2001SPEA2

2004IBEA

2005GDE3

2005OMOPSO

Figura 2.4: Cronologıa de los algoritmos multi-objetivo estudiados.


2.6.1.1. NSGA-II

NSGA-II (Non-dominated Sorting Genetic algorithm II ) fue propuesto por [Debet al., 2002] y es probablemente uno de los algoritmos evolutivos multi-objetivo masusados en la literatura. En cada generacion, las soluciones de la poblacion actualson categorizadas en diferentes clases. Los individuos asociados a los vectores delprimer frente pertenecen al conjunto de las soluciones mas eficientes, los individuosasociados a los vectores del segundo frente pertenecen al conjunto de las segundassoluciones mas eficientes, y ası sucesivamente.

A los miembros de la poblacion se les asigna dos valores. El primero se correspondecon la posicion de la solucion en el ordenamiento de dichos frentes, y representa lacalidad de la solucion en terminos de convergencia. El segundo, llamado distanciade amontonamiento (crowding distance), consiste en una estimacion de la densidadde soluciones que rodean un punto concreto del espacio de busqueda, y representala calidad de la solucion en terminos de diversidad. Una solucion es mejor queotra si tiene un rango de orden mayor, y en caso de igualdad, si la distancia deamontonamiento es mejor. La estrategia de seleccion es por torneo deterministaentre dos soluciones seleccionadas al azar. En la fase de reemplazo, solo los mejoresindividuos sobreviven con respecto al tamano de una poblacion preestablecido.

2.6.1.2. SPEA2

SPEA2 (Strength Pareto Evolutionary Algorithm 2 ) fue propuesto por [Zitzleret al., 2001], como una extension a su predecesor [Zitzler and Thiele, 1999]. Lasprincipales mejoras estan relacionadas con el uso de una estrategia en la asignaciondel valor de la funcion de evaluacion a los individuos mejorada.

SPEA2 maneja un archivo interno de tamano fijo durante la fase de seleccion paragenerar la descendencia. Ademas, utiliza otro archivo externo para almacenar lassoluciones no-dominadas generadas durante todo el proceso de busqueda. En unaiteracion en SPEA2, a cada poblacion y miembro del archivo s se le asigna un valorde fuerza S(s) que indica el numero de soluciones que domina. A continuacion, elgrado de adaptacion f(s) de una solucion s es calculado por la suma de los valoresde fuerza de todos los individuos que la solucion s domina actualmente. Ademas,se sigue una estrategia para preservar la diversidad de la poblacion, basandoseen la tecnica del vecino mas cercano. La fase de seleccion consiste en un torneobinario con reemplazo aplicado solo al archivo interno.


2.6.1.3. IBEA

IBEA (Indicator-Based Evolutionary Algorithm) fue propuesto por [Zitzler andKunzli, 2004] y es un framework que permite a los algoritmos evolutivos multi-objetivo incorporar un mecanismo de seleccion basandose en cualquier indicadorde rendimiento (en la Seccion 2.6.2 se profundiza mas sobre estas medidas).

La principal idea que sustenta IBEA es introducir un orden total entre solucionespor medio de un indicador binario de calidad. La forma de evaluar las solucionesse basa en una comparacion por pares de soluciones de la poblacion actual conrespecto a un indicador arbitrario I. A cada individuo s se le asigna el valor f(s)midiendo la perdida de calidad si s fuera eliminada de la poblacion actual.

Diferentes indicadores pueden ser usados para tal proposito, como el indicadorbinario aditivo Iε+ [Zitzler and Kunzli, 2004] o la diferencia en el hipervolumen[Zitzler and Thiele, 1999]. La fase de seleccion consiste en un torneo binario entredos soluciones seleccionadas al azar. La seleccion por reemplazo consiste en irquitando de forma iterativa la peor solucion de la poblacion actual hasta llegar altamano de poblacion preestablecido, actualizando de forma consecuente el gradode adaptacion del resto de individuos en cada eliminacion.

2.6.1.4. OMOPSO

[Sierra and Coello, 2005] proponen una optimizacion por enjambre de partıculasmulti-objetivo basada en la optimalidad de Pareto y en el uso de un factor deamontonamiento para la seleccion de lıderes. Para cada generacion y para cadapartıcula se selecciona un lıder. La seleccion es por torneo binario basandose enel valor de amontonamiento de los lıderes. Esta propuesta utiliza dos archivosexternos: uno para almacenar los lıderes actuales para realizar el vuelo y otro paraalmacenar las soluciones finales. El factor de amontonamiento es usado para poderfiltrar la lista de lıderes siempre que se supere el lımite maximo establecido. Sololos lıderes con mejores valores se mantienen en dicha lista.

Junto a lo anterior, tambien proponen utilizar dos operadores de mutacion recono-cidos en la literatura de algoritmos evolutivos: la mutacion uniforme y la mutacionno-uniforme. Ademas, emplean el concepto de dominancia-ε para mantener un ta-mano fijo en el archivo externo que contiene las soluciones no-dominadas.


2.6.1.5. GDE3

[Kukkonen and Lampinen, 2005] proponen GDE3 (Generalized Differential Evo-lution 3 ) como una extension del algoritmo tradicional de evolucion diferencialcon numero arbitrario de objetivos y restricciones. En el caso de un problemacon un unico objetivo y sin restricciones, GDE3 se convierte en la version originalde DE. GDE3 mejora sus versiones anteriores proporcionando soluciones mejordistribuidas.

GDE3 modifica a sus versiones antecesoras, utilizando una poblacion creciente yuna ordenacion no-dominada, con el fin de decrementar la poblacion de solucionesno-dominadas mediante el ajuste del tamano de la poblacion al final de cadageneracion, de forma muy similar a la descrita en NSGA-II. Este hecho mejora ladiversidad y hace que el metodo sea mas estable por la variacion de los parametrosde control. El metodo de manejo de restricciones utilizado en GDE reduce elnumero de llamadas a la funcion de evaluacion.

La seleccion en GDE3 se basa en las siguientes reglas:

En el caso de vectores no factibles, el vector de prueba se selecciona si dominadebilmente al vector anterior en el espacio de violacion de restricciones, delo contrario se selecciona el vector anterior.

En el caso de vectores factibles e inviables, se selecciona el vector factible.

Si ambos vectores son factibles, entonces el nuevo vector se selecciona si do-mina debilmente al vector anterior en el espacio de busqueda de solucionesfactibles. Si el vector anterior domina el vector de prueba, entonces se se-lecciona el vector anterior. Si ninguno de los dos vectores se domina en elespacio de busqueda, entonces ambos vectores se seleccionan para la siguientegeneracion.

GDE1 y GDE2 dependıan mucho de los valores de los parametros de control.Los vectores no se ordenaban durante el proceso de optimizacion ni se guardabanlas mejores no-dominadas, ası como tampoco se tenıa en cuenta la densidad desoluciones en el espacio de busqueda.


2.6.2. Evaluacion del rendimiento

Una tarea importante para validar una metaheurıstica multi-objetivo es ser capazde poder evaluar el rendimiento de esta frente a otra. Esta tarea no es trivial,dado que la solucion obtenida final no es un valor unico, si no una aproximacional verdadero frente de Pareto.

Los indicadores de rendimiento pueden ser clasificados acorde a diferentes carac-terısticas [Coello et al., 2010]:

Indicadores unarios/binarios. Los indicadores binarios permiten comparardos aproximaciones del verdadero frente de Pareto directamente, mientrasque los unarios asignan a cada aproximacion un valor escalar.

Requisito de conocer el verdadero frente de Pareto. Algunos indicadores re-quieren que el usuario provea el verdadero frente de Pareto del problema, elcual, en la mayorıa de casos, se desconoce.

Necesidad de informacion adicional. Algunos indicadores de calidad necesi-tan la definicion de diversos valores que son difıciles de obtener en algunoscasos, como por ejemplo, el punto ideal, el punto nadir, el conjunto de solu-ciones de referencia, etc.

Actualmente existen multitud de indicadores, sin embargo, solo unos pocos estanestandarizados. En general, se utiliza mas de un indicador para evaluar el rendi-miento de las metaheurısticas multi-objetivo. Por este motivo existen indicadorescon diferentes propositos:

Indicadores de convergencia. Proveen el grado de cercanıa de la aproximacionobtenida con respecto del frente de Pareto.

Indicadores de diversidad. Proveen la informacion sobre la uniformidad dela distribucion de las soluciones obtenidas a lo largo del frente de Pareto.

Indicadores hıbridos. Intentan combinar, en un unico valor, el rendimientotanto a nivel de convergencia como de diversidad.

A continuacion de describen algunos de los mas importantes. Una revision masextensa sobre indicadores de rendimiento de metaheurısticas multi-objetivo pue-de encontrarse en [Veldhuizen and Lamont, 2000], [Knowles and Corne, 2002] y[Zitzler et al., 2003].


2.6.2.1. Indicadores de convergencia

Distancia generacional

La distancia generacional es la distancia media de cada solucion del conjunto desoluciones aproximado a la solucion mas cercana del conjunto de referencia [Veld-huizen and Lamont, 2000]. Por tanto, es una medida de proximidad al conjuntode referencia.

La distancia generacional por sı misma puede llevar a equıvocos, ya que un conjun-to de soluciones aproximado puede contener una solucion muy proxima al conjuntode referencia produciendo ası una distancia generacional baja, por lo que se suelecombinar con un indicador de diversidad.

La Figura 2.5 muestra el comportamiento de este indicador.

Figura 2.5: Indicador de distancia generacional


2.6.2.2. Indicadores de diversidad

Distancia generacional invertida

La distancia generacional invertida es la inversa de la distancia generacional (ladistancia media de cada solucion del conjunto de soluciones aproximado a la solu-cion mas cercana del conjunto de referencia) [Coello et al., 2006].

La distancia generacional invertida cuantifica la diversidad, ya que se requiere queun conjunto de soluciones aproximado tenga soluciones cercanas al conjunto dereferencia para obtener una medida pequena.

Espaciado

La medida de espaciado cuantifica la uniformidad del espacio entre soluciones delconjunto de soluciones aproximado [Veldhuizen and Lamont, 2000]. Un conjuntoaproximado esta bien separado si no contiene agrupaciones muy densas de solu-ciones separadas por amplias extensiones en el espacio de busqueda.

Ya que para el calculo del espaciado no es necesario el conjunto de referencia, sedebe tener en cuenta que se puede obtener un buen espaciado mientras hay pocaproximidad con el conjunto de referencia. Por tanto, este indicador debe utilizarseen conjunto a otra metrica de proximidad.

(a) Distancia generacional invertida (b) Espaciado

Figura 2.6: Indicadores de divergencia multi-objetivo


2.6.2.3. Indicadores hıbridos

Hipervolumen

La metrica de hipervolumen calcula el volumen del espacio dominado por el con-junto aproximado de soluciones [Zitzler and Thiele, 1999].

Este volumen esta limitado por un punto de referencia, que se suele establecerencontrando el punto nadir del conjunto de referencia (el valor mas desfavorablepara cada objetivo) mas un incremento fijo. Este incremento fijo es necesario parapermitir que los puntos extremos en el conjunto de soluciones aproximado con-tribuyan al hipervolumen. La metrica de hipervolumen es muy significativa en laliteratura ya que es independiente de la escala, intuitiva, y puede reflejar el gradode superacion entre dos conjuntos de soluciones aproximados.

Indicador ε+

El indicador ε+ mide la distancia mas pequena ε para que el conjunto de solucionesaproximado llegue a dominar completamente al conjunto de referencia [Zitzleret al., 2003]. Una buena proximidad y una buena diversidad conllevan valoresbajos de ε. Sin embargo, si hay una region del conjunto de referencia alejada delconjunto de soluciones aproximado, se necesitara un alto valor de ε. Por lo tanto,el indicador ε+ mide la consistencia del conjunto aproximado. Un conjunto desoluciones aproximado debe estar libre de grandes regiones de mala aproximacionpara ser consistente.

(a) HIpervolumen(b) Indicador ε+

Figura 2.7: Indicadores hıbridos multi-objetivo

Capıtulo 3

Analisis de datos conmetaheurısticas

3.1. Introduccion

El aprendizaje automatico es el campo de la ciencia de la computacion que estudialos metodos computacionales que son capaces de aprender a partir de un conjuntode de datos [Witten et al., 2011].

Uno de los principales objetivos del aprendizaje automatico es construir un modeloque sea capaz de predecir el valor desconocido de una variable objetivo (llamadaclase) dado un conjunto de datos como parametro de entrada. Si el modelo esaprendido con datos cuya clase es conocida, se trata de aprendizaje supervisado.Por el contrario, si el modelo ha sido generado con datos sin etiquetar, es decir,sin conocer su clase, se trata de aprendizaje no supervisado.

A continuacion el estudio se centrara en tecnicas de aprendizaje no supervisado.Estudios mas detallados a cerca del aprendizaje automatico y el descubrimiento depatrones pueden encontrarse en [Duda et al., 2001], [Bishop, 2006], [Witten et al.,2011], [Alpaydin, 2014].

39

40 CAPITULO 3. ANALISIS DE DATOS CON METAHEURISTICAS

3.2. Algoritmos de agrupamiento clasicos

El analisis de grupos o agrupamiento (clustering) es una de los metodos mas utili-zados en aprendizaje automatico no supervisado. Se trata de agrupar elementos uobjetos en categorıas significativas. Formalmente, dado un conjunto de n elemen-tos sin etiquetar D = x(1), x(2), ..., x(n) en un espacio de atributos de dimensiond, D se divide en un numero de conjuntos disjuntos Dj, denominados clusters, talque:

D = ∪kj=1Dj, (3.1)

donde Di∩Dj = ∅, i �= j, siendo los puntos de cada subconjunto similares los unosde los otros dado un criterio φ. Una particion se define como π = (D1, D2, ..., Dk)y el problema de agrupamiento se formula como:

π∗ = argminπf(π). (3.2)

Una revision extensa y cuidada de este problema y de las tecnicas clasicas de agru-pado puede encontrarse en [Xu and Wunsch II, 2005]. Muchos de estos metodosse basan en el concepto de disimilitud obtenido a traves de una metrica apropia-da, generalmente de distancia entre dos elementos. La eleccion de esta metricadependera de la forma de los clusters.

Figura 3.1: Tıpico proceso de analisis de grupos

3.2. ALGORITMOS DE AGRUPAMIENTO CLASICOS 41

3.2.1. Metodos particionales

Los metodos particionales tienen por objetivo fraccionar un conjunto de datos enK conjuntos disjuntos de puntos, de tal forma que los puntos de cada conjuntosean lo mas homogeneos posible entre sı. La homogeneidad se calcula usando unafuncion de puntuacion que generalmente se basa en los conceptos de similitudo distancia. El objetivo es minimizar una funcion (media, suma, etc.) sobre ladisimilitud entre cada punto y el centroide del cluster asignado. El centroide de uncluster (o prototipo) puede ser un punto del conjunto o una posicion en el espaciode busqueda.

El algoritmo mas conocido es K -medias propuesto en [MacQueen, 1967]. En suversion mas basica, este algoritmo comienza eligiendo de forma aleatoria un centropara cada uno de los K grupos y etiqueta a cada punto con el centro mas cercano.Una vez que cada punto es etiquetado, un nuevo centro por cluster se calculade acuerdo al centroide de cada cluster. El algoritmo itera hasta que no existancambios en los clusters.

Existen diferentes variantes del algoritmo K -medias en la literatura. Por ejemplo,[Jain and Dubes, 1988] propone usar la mediana en vez de la media (K -medianas);o tambien usar los medoides en vez de la media (K -medoides y PAM) [Kaufman,1987]. Un medoide puede ser definido como el punto de un cluster cuya distanciamedia a todos los puntos del cluster es mınima. El Algoritmo 8 describe estaversion.

Algoritmo 8 Algoritmo clasico de k -medoides

1: procedure K -Medoides

2: Seleccionar k de los n puntos como medoides3: Asociar cada punto pi a su medoide mas cercano mj

4: while Se reduzca la funcion de disimilitud do5: for Cada medoide mj y el resto de puntos pi do6: Intercambiar mj y pi7: Recalcular la funcion de disimilitud con la nueva configuracion8: if El coste de la configuracion se incrementa then9: Deshacer el intercambio realizado10: end if11: end for12: end while13: end procedure


3.2.2. Metodos jerarquicos

Existen dos tipos distintos de metodos jerarquicos: los aglomerativos, que empiezancon clusters con un unico punto, y de forma gradual, se van combinando; y losdivisivos, que empiezan con un unico cluster con todos los puntos, y de formagradual, se va fraccionando en clusters mas pequenos.

Los metodos jerarquicos permiten mostrar de forma grafica la secuencia entera deunion o division de los clusters. Dado que es una estructura en forma de arbol, algrafico resultante se le denomina dendograma.

Para decidir que clusters deben ser combinados, en el caso del aglomerativo, o pordonde un cluster debe ser fraccionado, en el caso de los divisivos, se necesita unamedida de disimilitud entre los diferentes puntos. En la mayorıa de metodos deagrupamiento jerarquico, esto se consigue estableciendo una metrica apropiada,es decir, una medida de distancia entre dos puntos; y un criterio de union paraespecificar la disimilitud de los clusters en funcion de las distancias de los puntos.

Existen multitud de distancias diferentes: Euclıdea, Manhattan, Mahalanobis,Hamming, Levenshtein... ası como de metricas: enlace-sencillo, enlace-completo,enlace-medio, Ward... Un estudio mas extenso de este tipo de metodos jerarquicospuede encontrarse en [Aggarwal and Reddy, 2013].

Figura 3.2: Dendograma de ejemplo del popular conjunto de datos Iris

3.2. ALGORITMOS DE AGRUPAMIENTO CLASICOS 43

3.2.3. Metodos basados en densidades

Los metodos basados en densidades presuponen que todos los puntos que pertene-cen a un cluster siguen una distribucion especıfica de probabilidad. La distribuciongeneral de los datos sera una mixtura de diferentes distribuciones.

El objetivo de estos metodos es identificar los clusters y sus parametros de distri-bucion. Estos metodos estan disenados para descubrir clusters de diferentes formasarbitrarias que no tienen por que ser convexas.

El algoritmo DBSCAN propuesto por [Ester et al., 1996], utiliza el concepto deaccesibilidad por densidad y conectividad por densidad. Se dice que un punto pes accesible por densidad desde un punto q, si la distancia entre p y q es menorque ε, y existe un numero suficiente de vecinos de q a una distancia menor de ε.Un punto p y q estan conectados por densidad, si existe un punto r que tiene unnumero suficiente de vecinos y tanto p como q estan a una distancia ε. Esto es unproceso encadenado desde r. Si q es vecino de r, r es vecino de s, s es vecino de t,que, a su vez, es vecino de p, lo que implica que q es vecino de p.

El algoritmo OPTICS propuesto por [Ankerst et al., 1999], es muy similar a DBS-CAN, pero corrige una de los puntos debiles de DBSCAN, el problema de la de-teccion de clusters significativos en datos con densidad variable. Para conseguirlo,los puntos se ordena de forma lineal de tal forma que los puntos que estan espa-cialmente mas proximos esten tambien proximos en la lista ordenada. Ademas, seguarda una distancia especial para cada punto que representa la densidad que debeaceptarse por un cluster para que ambos puntos pertenezcan al mismo cluster.

El principal inconveniente de DBSCAN y OPTICS es que esperan algun tipo dedisminucion de densidad para detectar los bordes de los clusteres. En conjuntosde datos de, por ejemplo, superposicion de distribuciones gaussianas, los bordesde los clusters generados por estos algoritmos a menudo se ven arbitrarios, porquela densidad del cluster disminuye paulatinamente. En conjuntos de datos que con-sisten en mixutras de gaussianas, estos algoritmos son casi siempre superados pormetodos probabilısticos tales como EM [Dempster et al., 1977], que son capacesde modelar con precision este tipo de datos.

Algunos algoritmos que tratan de superar las dificultades anteriores pueden ser[Bohm et al., 2004, Achtert et al., 2007a, Achtert et al., 2007b].


3.3. Agrupamiento con metaheurısticas

En paralelo a los metodos clasicos de agrupado comentados anteriormente, se haestudiado la resolucion del problema de analisis de grupos con aproximacionesmetaheurısticas. Para ello, es necesario modelar el problema como si se tratara deun problema de optimizacion combinatoria.

Dado un conjunto de n puntos D = {x(1), x(2), ..., x(n)} descrito por m atributos,la finalidad es asignar a cada punto x(i) un unico cluster Ci, tal que D = ∪k

i=1Ci,Ci �= ∅ (cluster no nulo), Ci ∩ Cj = ∅ con i �= j; y que una funcion de evaluacionde la calidad de los clusters sea optimizada. En funcion del problema, el numerok puede ser fijado o encontrado por el metodo de optimizacion.

El numero de combinaciones posibles de asignar a cada punto un cluster puedeser extremadamente grande. Si el numero de clusters es conocido, el numero decombinaciones de asignar n puntos en k clusters se calcula:

S(n, k) =1

k!

k∑i=0

(−1)k−1

(ki

)in, (3.3)

y el tamano del espacio de busqueda de encontrar el numero optimo de clusterses:

B(n) =n∑

k=1

S(n, k). (3.4)

A S se le conoce como numero de Stirling de segundo orden y a B como losnumeros de Bell.

Las metaheurısticas uni-objetivo para problemas de agrupamiento son adecuadaspara agrupar de forma eficiente clusters separables linealmente. Por el contrario,el uso de metaheurısticas multi-objetivo para abordar problemas no linealmenteseparables es cada dıa mayor.

[Das et al., 2009] ofrece una vision general completa de las tecnicas de agrupacionde datos basadas en algoritmos metaheurısticos bio-inspirados.

Una revision mas actualizada puede encontrarse en [Nanda and Panda, 2014],[Mukhopadhyay et al., 2015] y [Jose-Garcıa and Gomez-Flores, 2016].

3.3. AGRUPAMIENTO CON METAHEURISTICAS 45

3.3.1. Evaluacion

Las funciones de evaluacion en el agrupamiento con metaheurısticas suelen sergeneralmente funciones estadıstico-matematicas basadas en los conceptos de simi-litud o distancia entre los diferentes puntos. Tıpicamente consisten en ındices devalidacion interna de los clusters. El objetivo de estas funciones es:

Compacidad : los puntos de un cluster deben ser lo mas similares posible unosde otros.Separacion: los clusters deben estar lo suficientemente bien separados.

El problema del agrupamiento generalmente es bi-objetivo o incluso multi-objetivo.En el agrupado multi-objetivo, el objetivo es descomponer el conjunto de datosen grupos similares maximizando otros objetivos a la vez. Tıpicamente se intentaoptimizar dos medidas: una de compacidad y otra de separacion.

3.3.1.1. Compacidad

Varianza

La funcion de evaluacion de la varianza mide como de lejos un conjunto de datosse extiende [Handl and Knowles, 2012]. Se calcula de la forma:

V ar(C) =∑ck∈C

∑i∈Ck

d(i, ck)2, (3.5)

donde C es un conjunto de clusters, ck es el centro del cluster Ck y d es unafuncion de distancia. La varianza es una funcion de evaluacion a minimizar.

Desviacion

La funcion de evaluacion de la desviacion es casi identica a la varianza, salvo queen este caso, la distancia no es una distancia al cuadrado [Handl and Knowles,2012].

Dev(C) =∑ck∈C

∑i∈Ck

d(i, ck). (3.6)


Conectividad

La funcion de evaluacion de la conectividad evalua el grado en el que los puntosvecinos se encuentran en el mismo cluster [Handl and Knowles, 2012]. Se calculacomo:

Conn(C) =1

N

N∑i=1

(∑hj=1 ωi,nni(j)

h

)(3.7)

donde

ωa,b =

{1, si ∃Ck | a, b ∈ Ck

0, cualquier otro caso(3.8)

con nni(j) siendo j el vecino mas cercano de i, h el numero de vecinos para calcularla conectividad y N el numero total de puntos. El resultado de esta funcion seencuentra entre [0, 1], siendo el objetivo maximizarla.

3.3.1.2. Separacion

Separacion entre centroides

La funcion de evaluacion de separacion entre centroides permite calcular la sumaglobal de la distancia entre los diferentes centroides de los clusters [Handl andKnowles, 2012]. Se calcula como:

SumD(C) =∑

Ck∈C,Cl∈C,l �=k

d(ck, cl), (3.9)

donde ck y cl son los centroides de los clusters Ck y Cl, respectivamente.

El objetivo de esta funcion es maximizarla.


Mınima distancia entre centroides

Otra funcion de evaluacion de separacion descrita en [Handl and Knowles, 2012]donde en este caso se busca maximizar la mınima distancia entre los centroides delos clusters.

Dmin(C) = mınCk∈C,Cl∈C,l �=k

d(ck, cl), (3.10)

donde ck y cl son los centroides de los clusters Ck y Cl, respectivamente.

Enlace completo

La funcion de evaluacion de enlace completo es propuesta en [Hansen and De-lattre, 1978]. Un enlace completo calcula la distancia entre dos clusters. Se definepor la maxima distancia entre dos puntos que no pertenecen al mismo cluster.

CL(Ci, Cj) = maxCi∈C,Cj∈C

d(ci, cj), (3.11)

donde ci y cj son los puntos pertenecientes a los clusters Ci y Cj, respectivamente.

Enlace sencillo

La funcion de evaluacion de enlace sencillo es propuesta en [Hansen and Delattre,1978]. Un enlace sencillo es similar a un enlace completo, define la distancia entredos clusters por la mınima distancia entre dos puntos que no estan en el mismocluster.

SL(Ci, Cj) = mınCi∈C,Cj∈C

d(ci, cj), (3.12)

donde ci y cj son los puntos pertenecientes a los clusters Ci y Cj, respectivamente.


3.3.1.3. Compacidad y separacion

Indice de Dunn

El ındice de Dunn propuesto en [Dunn, 1974], tiene por objetivo identificarun conjunto de clusters que sean compactos, con una varianza pequena entre losmiembros del cluster, y que estos esten bien separados de los miembros de otrosclusters:

Dunn(C) = mın1≤i≤n

{mın

1≤j≤n,i �=j

{d(i, j)

max1≤k≤n d′(k)

}}, (3.13)

donde d(i, j) representa la distancia entre los clusters i y j, y d′(k) mide la distanciadentro del cluster k.

Un valor mas alto en el ındice de Dunn indica una calidad mayor del agrupamiento.El ındice de Dunn tiene un valor en el intervalo (0,+∞), y debe ser lo mas altoposible. Por lo tanto, la distancia entre los miembros de un cluster debe ser lo masbaja posible, y la distancia entre los clusters lo mas alta posible.

Indice de Davies-Bouldin

El ındice de Davies-Bouldin propuesto en [Davies and Bouldin, 1979], calcula lacompacidad estimando la distancia media de los puntos a su respectivo centroide,y para la separacion cuantifica la distancia entre los centroides:

DB(C) =1

N

N∑i=1

maxi �=j

(σi + σj

d(ci, cj)

), (3.14)

donde N es el numero de clusters, cx denota el centroide del cluster x, σx es ladistancia media de todos los elementos del cluster x al centroide cx, y d(ci, cj) esla distancia entre los centroides ci y cj.

La solucion optima es aquella que tiene el ındice de Davies-Bouldin mas bajo.


Indice Silueta

El ındice Silueta propuesto en [Rousseeuw, 1987] se calcula como la media demedias silueta de todos los puntos:

SI(C) =1

K

K∑k=1

(1

Nk

∑i∈Ik

b− a

max{a, b}

), (3.15)

donde a es la distancia media entre el punto y todos los otros puntos del mismocluster, y b es la distancia media entre el punto y todos los otros puntos del clustermas proximo.

Su valor varıa entre -1 y 1. Un valor cercano a 1 para el punto i significa que elpunto se encuentra en el cluster correcto, mientras que un valor cercano a -1 indicaque deberıa estar agrupado en otro cluster.

El objetivo serıa maximizar este ındice.

Indice de Ray-Turi

El ındice de Ray-Turi propuesto en [Ray and Turi, 1999] es un ratio entre laseparacion inter-cluster e intra-cluster. Se calcula como:

RT (C) =1

N

∑Kk=1

∑i∈Ik ‖ d(ci, ck) ‖2

mınk<k′ d(ck, c′k))2, (3.16)

donde el numerador es la media de las distancias al cuadrado de todos los puntoscon respecto a su centroide y el denominador es el mınimo de las distancias alcuadrado entre todos los centroides.

El objetivo serıa minimizar este ındice.


3.3.2. Codificacion

Cualquier metaheurıstica, ya sea uni-objetivo o multi-objetivo, necesita codificarlas soluciones, lo que esta directamente relacionado con la funcion de evaluaciona optimizar. Los esquemas de codificacion juegan un papel muy relevante en laeficiencia y eficacia de la metaheurıstica, y constituye un paso esencial en su diseno.

Los esquemas de codificacion que han sido utilizados en metaheurısticas que inten-tan resolver el problema de agrupamiento se pueden clasificar en: binarios, enterosy reales [Jose-Garcıa and Gomez-Flores, 2016]. Dado que el numero de clusterspuede ser desconocido a priori, el esquema de codificacion debe poder ser disenadopara una cantidad variable de clusters en el rango [Kmin, Kmax], donde Kmin = 2y Kmax = redondear(

√N).

3.3.2.1. Codificacion binaria

Cada solucion es representada por una cadena binaria de longitud igual a N, por loque cada posicion en la cadena binaria se corresponde con un punto del conjunto dedatos. El valor de cada posicion sera un 1 si dicha posicion se corresponde con unprototipo (centroide, medoide...) o 0 en caso contrario. Por ejemplo, de la solucionC = {01000001} se extrae que los puntos 1 y 7 son prototipos. Solo quedarıa pordecodificar el resto de puntos calculando que prototipo es el mas cercano.

3.3.2.2. Codificacion entera

De forma similar a la codificacion binaria, la representacion entera codifica todoslos puntos del conjunto de datos en un array de enteros.

Codificacion basada en etiquetas

Cada punto del conjunto de datos toma un valor entero del alfabeto {1, ..., Kmax}donde Kmax es el maximo numero de posibles clusters. Esta codificacion entera esredundante por naturaleza, pues existen Kmax! codificaciones etiquetadas para lamisma solucion. Por ejemplo, la solucion C = {1721} es la misma que C = {7217}.Por tanto, el tamano del espacio de busqueda explorado es mucho mayor que elespacio de soluciones original.


Codificacion basada en grafos

Cada punto del conjunto de datos puede tomar un unico valor j del conjunto{1, 2, ..., N}. Un valor j asignado a la posicion i significa que hay una conexion en-tre dichos objetos, que estan agrupados en el mismo cluster. Por tanto, la solucionfinal es recuperada identificando todos los puntos conectados del grafo dirigido.

3.3.2.3. Codificacion real

Con codificacion real, una solucion representa la ubicacion del prototipo del clusteren el espacio de atributos de dimension D. Si se considera agrupar un conjunto deN puntos en k clusters, los prototipos de cada cluster estaran codificados comoun vector real de tamano D×K. Esta codificacion es usada generalmente por lasmetaheurısticas basadas en poblaciones.

Codificacion de longitud fija

Todas las soluciones codifican un numero maximo de prototipos Kmax. Por lotanto, todos los miembros de la poblacion mantienen la misma longitud durantetodo el proceso de busqueda, es decir D × Kmax. Ademas, para determinar queprototipos participan en el proceso de agrupamiento en cada iteracion, se sueleutilizar un vector de mascara o un umbral de aceptacion.

Codificacion de longitud variable

Considerandose un conjunto de P soluciones de agrupado C = {Ci | i =1, ..., P}, entonces, la solucion i codifica un numero concreto Ki de prototipos.Por tanto, la longitud del vector es variable, es decir, D×Ki. Las metaheurısticasbasadas en poblaciones que utilicen este esquema deben ajustar los operadores debusqueda para poder tratar con individuos de diferentes tamanos.


3.3.3. Seleccion de la solucion final

Dada la naturaleza de los algoritmos de optimizacion multi-objetivo, cualquieragrupamiento con metaheurısticas multi-objetivo generara un conjunto de solu-ciones no-dominadas. Como ninguno de los objetivos de estas soluciones puedeser mejorado sin empeorar otro objetivo, es necesario definir una estrategia paraobtener una solucion final. [Mukhopadhyay et al., 2014] clasifica estas estrategiasen tres categorıas diferentes.

3.3.3.1. Funcion de evaluacion independiente

La mayorıa de tecnicas de agrupado multi-objetivo hacen uso de esta aproximacion.En esta estrategia, se evaluan todas las soluciones no-dominadas con un ındicede validacion alternativo a los ya optimizados, y aquella solucion con el mejorresultado, se convertira en la solucion final. A pesar de la sencillez de implementaresta estrategia, es posible que la solucion final este sesgada dependiendo del ındicede validacion elegido. Otro punto crıtico sobre esta aproximacion es que ese mismoındice podrıa haber sido optimizado directamente.

3.3.3.2. Punto knee del frente no-dominado

Dado un frente no-dominado, una solucion interesante a este problema es elegiruna en el que el cambio del valor de un objetivo ocasione un cambio maximo enlos otros objetivos. A esta solucion se le denomina knee (rodilla) del frente no-dominado. La tecnica habitual para encontrar dicha solucion es la generacion defrentes de control y compararlos con el no-dominado.

3.3.3.3. Conjuntos de clusters

Los metodos anteriores hacen uso de las propiedades del frente optimo de Paretoo de alguna metrica externa para seleccionar unas solucion del frente no-dominadocomo solucion final. Por el contrario, es muy posible que todas las soluciones delfrente no-dominado ofrezcan algo de informacion sobre la estructura del agrupadodel conjunto de datos. Por tanto, establecer un consenso entre todas las solucionesno-dominadas puede resultar en un mejor agrupado.

Capıtulo 4

Caso practico: Operadoralogıstica

4.1. Introduccion

Se desarrolla el caso practico de una operadora logıstica de transporte en cisternaespecializada en mercancıas peligrosas, principalmente de productos petrolıferos,que tiene una alta incidencia en el tejido economico espanol, y al mismo tiempo,tiene unos niveles de seguridad y reglamentacion muy elevados.

La extrema peligrosidad de este tipo de productos y su manejo, hace que sea devital importancia, tanto desde el punto de vista de seguridad como economico, laadecuada gestion del transporte y distribucion de los mismos.

La Figura 4.1 muestra un mapa de calor de las diferentes zonas donde prestaservicios la operadora logıstica dentro de la penınsula iberica.

En concreto, se va a trabajar con el modelo de transporte de uno de los principalesproductos con los que trabaja la operadora logıstica: lubricantes. La Figura 4.2muestra el proceso desde que se solicita el pedido hasta que se vende a un clientefinal. Actualmente, un grupo empresarial del sector petroquımico y energetico esel encargado de promocionar y vender el producto a terceros. En la siguiente etapadel proceso, se comunica a la operadora logıstica los pedidos que debe cargar yrepartir a los diferentes distribuidores que lo solicitaron.

53

54 CAPITULO 4. CASO PRACTICO: OPERADORA LOGISTICA

Figura 4.1: Mapa de calor de los distribuidores de lubricantes

Figura 4.2: Proceso de distribucion del producto de lubricantes

4.2. DEFINICION DEL TRABAJO 55

4.2. Definicion del trabajo

La metodologıa actual de la planificacion del reparto venıa gestionada por la petro-lera, la cual divide el territorio nacional en 6 zonas, perteneciendo cada provinciade Espana a una de ellas, tal y como se puede ver en la Tabla 4.1. Se reparte cadasemana del ano a dos zonas diferentes, la siguiente a otras dos, y ası sucesivamente.Los distribuidores solicitan los pedidos a la petrolera con antelacion a la semanaque se les ha asignado.

Tabla 4.1: Clasificacion actual de las zonas de reparto por provincias

NOROESTE NORTE CATALUNA LEVANTE SUR CENTRO

ASTURIAS ALAVA BARCELONA ALBACETE CADIZ AVILA

CORUNA BURGOS GERONA ALICANTE BADAJOZ GUADALAJARA

LEON CANTABRIA HUESCA ALMERIA CACERES MADRID

LUGO GUIPUZCOA LERIDA CASTELLON CIUDAD REAL SALAMANCA

ORENSE LA RIOJA TARRAGONA CUENCA CORDOBA SEGOVIAPONTEVEDRA NAVARRA ZARAGOZA MURCIA GRANADA TOLEDO

PALENCIA TERUEL HUELVA VALLADOLID

SORIA VALENCIA JAEN ZAMORA

VIZCAYA MALAGASEVILLA

El objetivo es que, manteniendo el sistema actual de reparto en 6 zonas, sea lapropia operadora logıstica, que es la experta en su trabajo, quien asigne una zo-na a cada distribuidora para intentar optimizar el coste tanto economico comomedioambiental en las tareas de reparto.

Para ello se va desarrollar un sistema, que a partir de los distribuidores ya regis-trados (Figura 4.3), los agrupe en 6 zonas, intentando minimizar la distancia entreellas y manteniendo un volumen de trabajo similar en cada zona. Cada semana, seregistran nuevos distribuidores, por lo que seran asignados a los grupos ya creados,manteniendo estas zonas fijas para no importunar a los distribuidores pasados concambios continuos de zona. Sera a final de ano cuando se valore si es necesarioreajustar el sistema con todos los registros. Los pedidos por cada distribuidor sonmuy pequenos en comparacion a la capacidad de los camiones, por lo que en unmismo viaje se repartira a multiples distribuidores.

Los diagramas de cajas de la Figura 4.4 describen como son las zonas actuales. Seha elegido este tipo de graficos para poder comparar de forma sencilla las diferentesdistribuciones de los grupos. Se puede comprobar que, a nivel de volumen detrabajo, son muy similares, pero en cuanto a nivel de distancias, se puede mejorarpara encontrar un equilibrio y minimizar los kilometros recorridos en el reparto.


Figura 4.3: Clasificacion original

(a) Distancia al medoide (b) Volumen

Figura 4.4: Diagramas de cajas de las metricas originales

4.3. EXPERIMENTACION 57

4.3. Experimentacion

El primer paso ha sido la generacion de una matriz de distancias entre los diferentesdistribuidores para evitar repetir calculos durante toda la experimentacion. Parauna mayor precision en los resultados, no se ha trabajado con la distancia euclıdeaentre los distribuidores, si no con la distancia real existente por carretera. En elapendice A se detalla mas sobre la generacion de esta matriz.

Tenemos 2048 distribuidores de lubricantes diferentes geo-localizados por todo elterritorio nacional, y se quieren agrupar en 6 grupos diferentes. La ecuacion 3.3calcula el numero de combinaciones posibles de asignar a cada punto un cluster,por lo que:

S(2048, 6) ≈ 6× 101590. (4.1)

La cantidad de soluciones en el espacio de busqueda es ingente, por lo que sedescarta usar cualquier metodo analıtico en una fase inicial.

La primera aproximacion para la resolucion del problema de clasificacion, se harealizado con un metodo de agrupado particional. En concreto, se ha elegido k-medoides, descrito en la Seccion 3.2.1. Se ha elegido frente al clasico k-mediasdada la tipologıa del problema. Ademas de que ya se conoce la distancia entrelos diferentes puntos del problema (distribuidores), se podrıa dar el caso de noexistir una ruta por carretera entre el centroide del cluster y un punto. En estecaso, la eleccion de la k es trivial, pues se necesita agrupar en 6 zonas todos losdistribuidores (k = 6).

El Codigo 4.1 describe la implementacion del algoritmo k-medoides con el lenguajede programacion Python.

1 import numpy as np2 import random3

4 def kMedoides(D, k, tmax=100):5 m, n = D.shape6

7 M = np.arange(n)8 np.random.shuffle(M)9 M = np.sort(M[:k])

10

11 Mnew = np.copy(M)12

13 C = {}14


15 for t in xrange(tmax):16 J = np.argmin(D[:,M], axis=1)17

18 for i in range(k):19 C[i] = np.where(J==i)[0]20

21 for i in range(k):22 J = np.mean(D[np.ix_(C[i],C[i])],axis=1)23 j = np.argmin(J)24 Mnew[i] = C[i][j]25

26 np.sort(Mnew)27

28 if np.array_equal(M, Mnew):29 break30

31 M = np.copy(Mnew)32 else:33 J = np.argmin(D[:,M], axis=1)34 for i in range(k):35 C[i] = np.where(J==i)[0]36

37 return M, C

Codigo 4.1: Implementacion de k -medoides con Python

En una segunda aproximacion, se han escogido las siguientes metaheurısticasmulti-objetivo:

NSGA-II, descrito en la Seccion 2.6.1.1.SPEA2, descrito en la Seccion 2.6.1.2.IBEA, descrito en la Seccion 2.6.1.3.OMOPSO, descrito en la Seccion 2.6.1.4.GDE3, descrito en la Seccion 2.6.1.5.

La codificacion de cada individuo consta de 6 numeros enteros, correspondiendocada uno de ellos al medoide de cada uno de los 6 clusters, identificando cadanumero a un distribuidor diferente. De esta forma, el espacio de soluciones se hareducido a:

(20486

)≈ 1017. (4.2)

Se ha formulado el problema de optimizacion con dos objetivos a minimizar: ladesviacion de la distancia al medoide (adaptacion de la funcion 3.3.1.1) y la des-viacion tıpica del volumen por cluster. En el apendice B explica el codigo con laimplementacion de esta aproximacion.

4.4. RESULTADOS Y VALIDACION 59

4.4. Resultados y validacion

Una vez obtenidos los medoides de cada cluster, se ha generado un fichero CSVasignando a cada distribuidor su medoide mas cercano.

La visualizacion de los diferentes clusters resultantes se ha realizado con CARTO.CARTO es una plataforma de computacion en la nube que proporciona herra-mientas de analisis de datos y de visualizacion sobre datos geo-localizados [Lopezet al., 2017].

Para cada una de las aproximaciones, se muestran dos diagramas de cajas, unomostrando la distribucion de las distancias al medoide por cluster y otro con elvolumen. Estos diagramas estan basados en cuartiles y gracias a ellos se puede vi-sualizar la distribucion de los puntos de cada cluster. Estos diagramas suministraninformacion sobre los valores mınimo y maximo, los cuartiles Q1, Q2 o mediana yQ3, y sobre la existencia de valores atıpicos y la simetrıa de la distribucion.

En el caso de las diferentes metaheurısticas implementadas, se han analizado dife-rentes indicadores de rendimiento, tanto de convergencia como de diversidad. Enconcreto:

El tiempo transcurrido de la ejecucion del algoritmo.

La distancia generacional, descrita en la Seccion 2.6.2.1.

La distancia generacional invertida, descrita en la Seccion 2.6.2.2.

El espaciado entre generaciones, descrito en la Seccion 2.6.2.2.

El hipervolumen, descrito en la Seccion 2.6.2.3.

El indicador ε+, descrito en la Seccion 2.6.2.3.


4.4.1. K-medoides

Figura 4.5: Clasificacion por k -medoides


Figura 4.6: Diagramas de cajas de metricas de k -medoides


4.4.2. NSGA-II

(a) Tiempo transcurrido (b) Distancia generacional

(c) Distancia generacional invertida (d) Espaciado

(e) Hipervolumen (f) Indicador ε+

Figura 4.7: Indicadores de rendimiento de NSGA-II (10 ejecuciones)


Figura 4.8: Clasificacion por NSGA-II


Figura 4.9: Diagramas de cajas de metricas de NSGA-II


4.4.3. SPEA2




Figura 4.10: Indicadores de rendimiento de SPEA2 (10 ejecuciones)


Figura 4.11: Clasificacion por SPEA2


Figura 4.12: Diagramas de cajas de metricas de SPEA2


4.4.4. IBEA




Figura 4.13: Indicadores de rendimiento de IBEA (10 ejecuciones)


Figura 4.14: Clasificacion por IBEA


Figura 4.15: Diagramas de cajas de metricas de IBEA


4.4.5. GDE3




Figura 4.16: Indicadores de rendimiento de GDE3 (10 ejecuciones)


Figura 4.17: Clasificacion por GDE3


Figura 4.18: Diagramas de cajas de metricas de GDE3


4.4.6. OMOPSO




Figura 4.19: Indicadores de rendimiento de OMOPSO (10 ejecuciones)


Figura 4.20: Clasificacion por OMOPSO


Figura 4.21: Diagramas de cajas de metricas de OMOPSO


4.4.7. Comparativa y validacion

Se han realizado dos procesos para validar la calidad de los resultados obtenidos:una comparativa de los diferentes indicadores de rendimiento de las metaheurısti-cas; y por otra parte, una evaluacion del modelo de clasificacion generado con lasmedidas descritas en la Seccion 3.3.1.

Tabla 4.2: Hipervolumen

Algoritmo Mınimo Mediana Maximo Indiferente a

NSGAII 0.5561055476 (2) 0.6211437483 (3) 0.7073742793 (4) [IBEA, GDE3, SPEA2]SPEA2 0.5419657505 (4) 0.6431468159 (2) 0.7227542977 (3) [NSGAII, IBEA, GDE3]IBEA 0.5522487831 (3) 0.5966381263 (4) 0.7545343948 (2) [NSGAII, GDE3, SPEA2]GDE3 0.5765209752 (1) 0.6603633747 (1) 0.7632048617 (1) [NSGAII, IBEA, SPEA2]OMOPSO 0.4107793473 (5) 0.4879235108 (5) 0.5559461443 (5) []

Tabla 4.3: Distancia generacional



Tabla 4.4: Distancia generacional invertida


NSGAII 0.0716158767 (4) 0.1008316509 (5) 0.1108745461 (2) [IBEA, SPEA2]SPEA2 0.0614508169 (2) 0.0904230324 (2) 0.1228051246 (4) [NSGAII, GDE3, SPEA2]IBEA 0.0674731364 (3) 0.0985685403 (3) 0.1218949187 (3) [IBEA, SPEA2]GDE3 0.05611109 (1) 0.0766290777 (1) 0.1098077111 (1) []OMOPSO 0.1570799843 (5) 0.1742744304 (4) 0.2133985194 (5) [NSGAII, IBEA, GDE3]

Tabla 4.5: Indicador ε+







Figura 4.22: Comparativa de indicadores de rendimiento entre metaheurısticas


Tabla 4.6: Validaciones de compacidad

Algoritmo Volumen (desviacion tıpica) Distancia (desviacion) Conectividad Distancia TSP Litros por km Puntuacion

Original 363411.987236 (2) 238407.176 (4) 0.9293160723 (4) 50049.1128333 (5) 59.4047629701 (5) 20 (5)K-medoides 915200.976437 (7) 281903.291 (7) 0.9133300781 (7) 54867.2998333 (7) 66.328325454 (7) 35 (7)NSGA-II 438299.574465 (5) 232374.686 (3) 0.9284130859 (5) 49028.3663333 (3) 58.3269123622 (1) 17 (3)SPEA2 469076.241524 (6) 229410.6 (1) 0.9401416016 (2) 48855.5668333 (1) 58.4495495247 (2) 12 (1)IBEA 333689.488679 (1) 239087.936 (5) 0.937578125 (3) 49842.6711667 (4) 59.7623639482 (6) 19 (4)GDE3 423561.180774 (4) 232060.55 (2) 0.9460009766 (1) 48877.3723333 (2) 58.4665719305 (3) 12 (1)OMOPSO 409318.878197 (3) 240634.269 (6) 0.9152001953 (6) 50441.6786667 (6) 58.4670227246 (4) 25 (6)

Tabla 4.7: Validaciones de separacion

Algoritmo Separacion entre medoides Mınima distancia entre medoides Puntuacion

Original 15984.912 (6) 382.813 (2) 8 (4)K-medoides 16239.582 (4) 127.878 (7) 11(6)NSGA-II 17138.612 (2) 382.813 (2) 4 (2)SPEA2 17739.429 (1) 382.813 (2) 3 (1)IBEA 15521.26 (7) 382.813 (2) 9 (5)GDE3 16238.789 (5) 379.244 (6) 11 (6)OMOPSO 16405.09 (3) 385.128 (1) 4 (2)

Tabla 4.8: Validaciones mixtas de compacidad y separacion

Algoritmo Indice Dunn Indice Davies-Bouldin Indice Silhouette Indice Ray-Turi Puntuacion

Original 2.0192823178 (4) 0.5445844322 (4) -0.0109413929 (5) 32.6805084335 (4) 17 (4)K-medoides 0.7065215263 (7) 0.8577549283 (7) -0.0103002798 (4) 543.563043941 (7) 25 (7)NSGA-II 2.05999664 (2) 0.5512475655 (5) -0.004844597 (3) 30.4001419001 (2) 12 (3)SPEA2 2.3113089641 (1) 0.4861348571 (1) -0.0014582096 (1) 29.4660920464 (1) 4 (1)IBEA 1.8927187918 (5) 0.5558499565 (6) -0.0115946661 (6) 33.363824596 (5) 22 (6)GDE3 2.0525216734 (3) 0.5273381348 (2) -0.0015063258 (2) 30.4161907873 (3) 10 (2)OMOPSO 1.8377263415 (6) 0.5440234928 (3) -0.0128039837 (7) 33.4286996056 (6) 22 (5)

Dados los resultados y validaciones anteriores, se puede concluir con la siguienteclasificacion final de las aproximaciones estudiadas, siendo SPEA2 claro vencedor.

Posicion Algoritmo Puntuacion final

1 SPEA2 32 NSGA-II 83 GDE3 94 OMOPSO 134 Original 136 IBEA 157 K -medoides 20

Tabla 4.9: Clasificacion final por puntuacion

Capıtulo 5

Conclusiones y trabajo futuro

Gracias al sistema final propuesto para la operadora logıstica, se ha conseguidoincrementar su competitividad en el mercado actual, reduciendo los costes opera-cionales durante el reparto.

Con la ayuda de este sistema, la distancia recorrida por los camiones cisternaha disminuido en las diferentes zonas de la geografıa nacional con el consecuenteahorro directo en combustible. Otras mejoras indirectas han sido una menor degra-dacion de los componentes de la flota de vehıculos y un impacto medioambientalmenor.

Debido a los resultados obtenidos, la confianza del equipo directivo en el uso deherramientas de Inteligencia Artificial ha crecido, por lo que se esta considerandoampliar el uso de estas tecnicas para la optimizacion de otros procesos.

A continuacion se enumeran las principales contribuciones del trabajo realizado,ası como unas posibles lıneas futuras para extenderlo.

5.1. Contribuciones

Realizacion de un extenso estado del arte sobre metaheurısticas y analisis degrupos.

Combinacion de conceptos e ideas de diferentes ramas de la InteligenciaArtificial.

75

76 CAPITULO 5. CONCLUSIONES Y TRABAJO FUTURO

Desarrollo e incorporacion de un sistema de Inteligencia Artificial al mundoempresarial.

Ponencia Analisis de Datos aplicado al Transporte, en el curso de verano dela UAH Big Data: Tecnologıa y Aplicaciones, disponible en https://goo.gl/JfLN9M.

Artıculo La visualizacion de sistemas cartograficos en dispositivos moviles:problemas, aproximaciones y casos de ejemplo [Lopez et al., 2017].

5.2. Lıneas futuras

Se propone el desarrollo de herramientas tecnologicas para el analisis de los datosdisponibles de la actividad del negocio con el objeto de permitir una mejora enel rendimiento general de la empresa. Las herramientas se desarrollaran bajo lapremisa del analisis de grandes cantidades de datos utilizando tecnicas de Big Data,que agrupan tanto elementos estadısticos clasicos como sistemas de InteligenciaArtificial, que permitan el descubrimiento de nuevo conocimiento de valor para laempresa.

Con el analisis derivado de los resultados obtenidos de las herramientas desarrolla-das se obtendran mejoras operacionales y se abriran nuevas areas de negocio parael uso de los recursos de los que actualmente dispone la empresa, lo que redundaraen una mejora de la eficiencia general de la misma y su competitividad dentro delsector.

Dentro de los modulos a desarrollar para las distintas herramientas, destacarıanlos siguientes:

Creacion de un modulo de adquisicion de datos.

Creacion de un modulo de generacion de rutas alternativas.

Creacion de un modulo de calculo de indicadores individuales automatizados.

Apendice A

Generacion de la matriz dedistancias

El primer paso ha sido generar el fichero CSV A.1 con todos los distribuidorespresentes en una de las bases de datos PostgreSQL de la operadora logıstica. Estabase de datos esta formada por 249 tablas, casi 6000 columnas en total y mas de70 millones de filas en total. Este archivo contiene solo tres atributos: identificadordel distribuidor, latitud y longitud.

Para el calculo de la distancias entre distribuidores, se ha utilizado el proyectoOSRM [Luxen and Vetter, 2011], generando los mapas con un perfil concretopara la casuıstica necesitada (restricciones de velocidad de camiones de mercancıaspeligrosas, restricciones de vıa...). El Codigo A.3 llama al servidor instalado1 ygenera el fichero CSV A.2 con todas las distancias obtenidas (2048 × 2048 =4194304 registros).

Este fichero sera luego importado a la Tabla A.4 en base de datos para un accesomas comodo durante la optimizacion y validacion.

1 4173;41.141183;1.1072162 4174;41.352234;1.7270233 4175;41.1411927;1.2190198

Codigo A.1: Varias lıneas de ejemplo del fichero coordenadas aceites.csv

1El proceso de compilacion e instalacion de OSRM se puede obtener enhttps://github.com/Project-OSRM/osrm-backend/wiki

77

78 APENDICE A. GENERACION DE LA MATRIZ DE DISTANCIAS

1 Origen Destino Duracion Distancia2 4173 4173 0 03 4173 4174 3150 685064 4173 4175 1122 150555 4173 4176 9857 2329436 4173 4177 9807 2428777 4173 4178 7983 1977668 4173 4179 4792 958179 4173 4227 21858 510423

10 4173 4228 10275 25570411 4173 4229 21555 497967

Codigo A.2: Varias lıneas del fichero generado matriz-thesis.csv

1 #include "osrm/match_parameters.hpp"2 #include "osrm/nearest_parameters.hpp"3 #include "osrm/route_parameters.hpp"4 #include "osrm/table_parameters.hpp"5 #include "osrm/trip_parameters.hpp"6

7 #include "osrm/coordinate.hpp"8 #include "osrm/engine_config.hpp"9 #include "osrm/json_container.hpp"

10

11 #include "osrm/osrm.hpp"12 #include "osrm/status.hpp"13

14 #include <exception>15 #include <iostream>16 #include <string>17 #include <utility>18 #include <fstream>19 #include <boost/tokenizer.hpp>20 #include <boost/foreach.hpp>21

22 #include <cstdlib>23

24 using namespace std;25 using namespace boost;26

27 vector<vector<string>> parse_csv(const char *path, const char *delim)28 {29 ifstream input;30 input.open(path);31 string line;32 vector<string> row;33 vector<vector<string>> points;34

35 typedef tokenizer<char_separator<char>> Tokenizer;36 boost::char_separator<char> sep(delim);37

38 while (getline(input, line))39 {40 Tokenizer tok(line, sep);41 row.assign(tok.begin(), tok.end());42

43 if (row.size() < 3)

Apendice A Generacion de la matriz de distancias 79

44 continue;45

46 points.insert(points.end(), row);47 }48

49 input.close();50 return points;51 }52

53 int main(int argc, const char *argv[])54 {55 if (argc < 3)56 {57 cerr << "Uso: " << argv[0] << " data.osrm coordenadas.csv\n";58 return EXIT_FAILURE;59 }60

61 vector<vector<string>> points = parse_csv(argv[2], ";");62

63 using namespace osrm;64

65 EngineConfig config;66 config.storage_config = {argv[1]};67 config.use_shared_memory = false;68

69 ofstream output_file;70 output_file.open ("matriz-generada_thesis.csv");71

72 const OSRM osrm{config};73

74 for (int i = 0; i < points.size(); i++)75 {76 vector<string> row = points[i];77 for (int j = 0; j < points.size(); j++)78 {79 vector<string> row2 = points[j];80

81 double lato = stod(row[1]);82 double lono = stod(row[2]);83 double latd = stod(row2[1]);84 double lond = stod(row2[2]);85

86 RouteParameters params;87

88 params.coordinates.push_back({util::FloatLongitude{lono},util::FloatLatitude{lato}});

89 params.coordinates.push_back({util::FloatLongitude{lond},util::FloatLatitude{latd}});

90 params.geometries = RouteParameters::GeometriesType::Polyline6;91

92 json::Object result;93

94 const auto status = osrm.Route(params, result);95

96 if (status == Status::Ok)97 {98 auto &routes = result.values["routes"].get<json::Array>();99 auto &route = routes.values.at(0).get<json::Object>();

100

80 APENDICE A. GENERACION DE LA MATRIZ DE DISTANCIAS

101 string distance =to_string((int)route.values["distance"].get<json::Number>().value);

102 string duration =to_string((int)route.values["duration"].get<json::Number>().value);

103

104 string output_line = row[0] + "\t";105 output_line += row2[0] + "\t";106 output_line += duration + "\t" + distance;107

108 output_file << output_line << endl;109 }110 else if (status == Status::Error){111 cout << "La ruta " << row[0] << "__" << row2[0] << " no se ha podido

calcular" << endl;112 string output_line = row[0] + "\t";113 output_line += row2[0] + "\t";114 output_line += "NULL\t";115 output_line += "NULL";116 output_file << output_line << endl;117 }118 }119 }120

121 output_file.close();122 }

Codigo A.3: Generacion de la matriz de distancias con OSRM

1 CREATE TABLE matriz_thesis2 (3 origen bigint NOT NULL,4 destino bigint NOT NULL,5 tiempo bigint,6 distancia double precision,7 CONSTRAINT matriz_thesis_pk PRIMARY KEY (origen, destino),8 CONSTRAINT matriz_thesis_destino_fk FOREIGN KEY (destino) REFERENCES "DISTRIBUIDOR"

(cod_distribuidor)9 CONSTRAINT matriz_thesis_origen_fk FOREIGN KEY (origen) REFERENCES "DISTRIBUIDOR"

(cod_distribuidor)10 );

Codigo A.4: Creacion de la tabla que almacena la matriz de distancias

Apendice B

MOEA Framework

MOEA framework es una librerıa de codigo abierto Java que permite desarro-llar y experimentar con algoritmos evolutivos multi-objetivo y otros algoritmos deoptimizacion multi-objetivo genericos. MOEA proporciona las herramientas nece-sarias para disenar, desarrollar, ejecutar los algoritmos creados, y ademas disponede una herramienta de diagnostico que permite probar los algoritmo con un grannumero de problemas definidos, incluyendo las funciones test Zitzler–Deb–Thiele’sfunctions(ZDT) [Zitzler et al., 2000].

A continuacion se adjunta los archivos AceitesProblem.java y Main.java para po-der reproducir la experimentacion realizada.

1 package main;2

3 import org.moeaframework.core.Solution;4 import org.moeaframework.problem.AbstractProblem;5 import org.moeaframework.core.variable.EncodingUtils;6

7 public class AceitesProblem extends AbstractProblem8 {9 private int matrix[][];

10 private int volume[];11 private int meanClusterVolume;12

13 public AceitesProblem()14 {15 super(6, 2);16 }17

18 public void evaluate(Solution solution)19 {20 int distanceDeviation[] = new int[getNumberOfVariables()];21 int totalVolume[] = new int[getNumberOfVariables()];

81

82 APENDICE B. MOEA FRAMEWORK

22

23 for (int point = 0; point < matrix.length; point++)24 {25 int distance = Integer.MAX_VALUE;26 int cluster = 0;27

28 for (int c = 0; c < numberOfVariables; c++)29 {30 int medoid = EncodingUtils.getInt(solution.getVariable(c));31 cluster = matrix[point][medoid] < distance ? c : cluster;32 distance = matrix[point][medoid] < distance ? matrix[point][medoid] :

distance;33 }34

35 distanceDeviation[cluster] += distance;36 totalVolume[cluster] += volume[point];37 }38

39 int clusterizationDeviation = 0;40

41 for (int clusterDeviation : distanceDeviation)42 {43 clusterizationDeviation += clusterDeviation;44 }45

46 double clusterizationVolumeDeviation = 0;47

48 for (int cluster : totalVolume)49 {50 clusterizationVolumeDeviation += Math.pow(cluster - meanClusterVolume, 2);51 }52

53 clusterizationVolumeDeviation = Math.sqrt(clusterizationVolumeDeviation /matrix.length);

54

55 solution.setObjective(0, clusterizationDeviation);56 solution.setObjective(1, clusterizationVolumeDeviation);57 }58

59 public Solution newSolution()60 {61 Solution solution = new Solution(getNumberOfVariables(),

getNumberOfObjectives());62

63 for (int i = 0; i < getNumberOfVariables(); i++)64 {65 solution.setVariable(i, EncodingUtils.newInt(0, matrix.length - 1));66 }67

68 return solution;69 }70

71 public void setMatrix(int matrix[][])72 {73 this.matrix = matrix;74 }75

76 public void setVolume(int volume[])77 {78 this.volume = volume;

Apendice B MOEA Framework 83

79 }80

81 public void setMeanClusterVolume(int meanClusterVolume)82 {83 this.meanClusterVolume = meanClusterVolume;84 }85 }

Codigo B.1: Representacion del problema utilizando MOEA Framework

1 package main;2

3 import java.io.FileWriter;4 import java.io.IOException;5 import java.sql.Connection;6 import java.sql.DriverManager;7 import java.sql.PreparedStatement;8 import java.sql.ResultSet;9 import java.sql.SQLException;

10 import java.util.logging.Level;11 import java.util.logging.Logger;12

13 import org.moeaframework.Executor;14 import org.moeaframework.core.NondominatedPopulation;15 import org.moeaframework.core.Solution;16 import org.moeaframework.core.variable.EncodingUtils;17

18 public class Main19 {20 private static int matrix[][];21 private static int data[]; // matrix index -> cod_distribuidor22 private static int volume[]; // matrix_index -> volumen acumulado23 private static int meanClusterVolume = 0;24

25 private static final Logger LOGGER = Logger.getLogger(Main.class.getName());26

27 public static void extraerDatosDB()28 {29 try30 {31 Connection conn =

DriverManager.getConnection("jdbc:postgresql://127.0.0.1:5432/thesis","postgres", "postgres");

32

33 PreparedStatement st = conn.prepareStatement("SELECT count(DISTINCTdestino) FROM matriz_thesis");

34

35 ResultSet res = st.executeQuery();36 int n = 0;37 while (res.next())38 {39 n = res.getInt("count");40 }41

42 matrix = new int[n][n];43 data = new int[n];44 volume = new int[n];45

84 APENDICE B. MOEA FRAMEWORK

46 st = conn.prepareStatement("SELECT (row_number() OVER () -1) AS index,distancia, origen, destino FROM matriz_thesis ORDER BY origen, destino");

47

48 res = st.executeQuery();49

50 while (res.next())51 {52 int dist = res.getInt("distancia");53 int ind = res.getInt("index");54 matrix[ind / n][ind % n] = dist;55 }56

57 st = conn.prepareStatement("SELECT cod_distribuidor FROM \"DISTRIBUIDOR\"WHERE cod_distribuidor IN (SELECT DISTINCT origen FROM matriz_thesis) ORDER BYcod_distribuidor;");

58

59 res = st.executeQuery();60 int index = 0;61 while (res.next())62 {63 data[index] = res.getInt("cod_distribuidor");64 index++;65 }66

67 st = conn.prepareStatement("SELECT * FROM\"ACEITES_ACUMULADO_VOLUMEN_PEDIDOS\" WHERE cod_distribuidor IN (SELECT DISTINCTorigen FROM matriz_thesis) ORDER BY cod_distribuidor;");

68 res = st.executeQuery();69 index = 0;70 while (res.next())71 {72 volume[index] = res.getInt("volumen");73 index++;74 }75

76 st = conn.prepareStatement("SELECT sum(volumen)/6 as mean FROM\"ACEITES_ACUMULADO_VOLUMEN_PEDIDOS\" WHERE cod_distribuidor IN (SELECT DISTINCTorigen FROM matriz_thesis);");

77 res = st.executeQuery();78 while (res.next())79 {80 meanClusterVolume = res.getInt("mean");81 }82

83 }84 catch (SQLException ex)85 {86 LOGGER.log(Level.SEVERE, ex.getMessage(), ex);87

88 return;89 }90 }91

92 public static void main(String args[])93 {94 extraerDatosDB();95

96 String[] algorithms = { "NSGAII", "GDE3", "OMOPSO", "SPEA2", "IBEA" };97

98 for (String algorithm : algorithms)

Apendice B MOEA Framework 85

99 {100 AceitesProblem aceitesProblem = new AceitesProblem();101 aceitesProblem.setMatrix(matrix);102 aceitesProblem.setVolume(volume);103 aceitesProblem.setMeanClusterVolume(meanClusterVolume);104

105 NondominatedPopulation result = newExecutor().withProblem(aceitesProblem).withProperty("populationSize",100).withAlgorithm(algorithm).withMaxEvaluations(10000).distributeOnAllCores().run();

106

107 int medoids[] = new int[6];108

109 Solution bestSolution = obtenerMejorSolucionIndiceDB(result);110

111 for (int variable = 0; variable < bestSolution.getNumberOfVariables();variable++)

112 {113 medoids[variable] =

EncodingUtils.getInt(bestSolution.getVariable(variable));114 }115

116 try117 {118 FileWriter csv = new FileWriter(algorithm + ".csv");119

120 csv.write("cod_distribuidor;label\n");121

122 for (int point = 0; point < matrix.length; point++)123 {124 int distance = Integer.MAX_VALUE;125 int cluster = 0;126

127 for (int c = 0; c < medoids.length; c++)128 {129 int medoid = medoids[c];130 cluster = matrix[point][medoid] < distance ? c : cluster;131 distance = matrix[point][medoid] < distance ?

matrix[point][medoid] : distance;132 }133

134 csv.write(data[point] + ";" + cluster + "\n");135 }136 csv.close();137 }138 catch (IOException ex)139 {140 LOGGER.log(Level.SEVERE, ex.getMessage(), ex);141 }142 }143 }144 }

Codigo B.2: Ejecucion de los multiples algoritmos

Apendice C

Implementacion de metricas ydiagramas de caja con Python

1 # coding: utf-82 from __future__ import division3 import csv4 import psycopg25 import math6 from tsp_solver.greedy import solve_tsp7 import matplotlib as mpl8 from matplotlib import pyplot9 CLUSTER_SIZE = 6

10

11 def read_clustering(path):12 with open(path, ’r’) as csvfile:13 clustering = [[] for _ in range(CLUSTER_SIZE)]14 rows = csv.reader(csvfile, delimiter=’;’)15 for row in rows:16 try:17 clustering[int(row[1])].append(int(row[0]))18 except:19 continue20 return clustering21

22 def cluster_matrix(cluster, db):23 n = len(cluster)24 matrix = [[0] * n for _ in range(n)]25 cluster_str = ’,’.join(str(p) for p in cluster)26 db.execute("""SELECT distancia FROM matriz_thesis WHERE origen IN ({}) AND

destino IN ({}) ORDER BY origen, destino""".format(cluster_str, cluster_str))27 rows = db.fetchall()28 i = 029 for row in rows:30 matrix[int(i / n)][i % n] = row[0]31 i += 132

33 return matrix

87

88APENDICE C. IMPLEMENTACION DE METRICAS Y DIAGRAMAS DE

CAJA CON PYTHON

34

35 def path_len(path, matrix):36 total_len = 037 previous = 038 for current in xrange(1, len(path)):39 total_len += matrix[previous][current]40 previous += 141 return total_len42

43 def clustering_size(clustering):44 n = 045 for cluster in clustering:46 n += len(cluster)47 return n48

49 def get_cluster_str(cluster):50 return ’,’.join(str(p) for p in cluster)51

52 def get_medoids(clustering, db):53 medoids = []54 for cluster in clustering:55 medoids.append(cluster_medoid(cluster, db))56 return medoids57

58 def get_distance_distribution(clustering, db):59 cluster_distances = []60 distances = []61 for cluster in clustering:62 cluster_str = get_cluster_str(cluster)63 medoid = cluster_medoid(cluster, db)64 db.execute("""select distancia from matriz_thesis where origen = {} and

destino in ({})""".format(medoid, cluster_str))65 res = [float(row[0]) for row in db.fetchall()]66 cluster_distances.append(res)67 distances += res68 return cluster_distances, distances69

70 def cluster_medoid(cluster, db):71 cluster_str = ’,’.join(str(p) for p in cluster)72 db.execute("""SELECT origen, sum(distancia) FROM matriz_thesis WHERE origen IN

({}) and destino in ({}) GROUP BY origen ORDER BY sum""".format(cluster_str,cluster_str))

73 return db.fetchall()[0][0]74

75 def tsp_mean(clustering, db):76 d_total = 077 for cluster in clustering:78 matrix = cluster_matrix(cluster, db)79 path = solve_tsp(matrix)80 dst = path_len(path, matrix)81 d_total += dst82 return d_total/len(clustering)83

84 def distance_deviation(clustering, db):85 values = []86 sum = 087 for cluster in clustering:88 medoid = cluster_medoid(cluster, db)89 cl_values = []90 for inst in cluster:

Apendice C Implementacion de metricas y diagramas de caja con Python 89

91 db.execute("""SELECT distancia FROM matriz_thesis WHERE origen = {} anddestino = {}""".format(inst, medoid))

92 res = db.fetchall()93 if len(res) != 0:94 sum += res[0][0]95 cl_values.append(res[0][0])96 values.append(cl_values)97 return sum, values98

99 def standard_deviation(clustering, db):100 x = 0101 for cluster in clustering:102 cluster_str = get_cluster_str(cluster)103 db.execute("""SELECT sum(volumen) from \"ACEITES_ACUMULADO_VOLUMEN_PEDIDOS\"

WHERE cod_distribuidora IN ({})""".format(cluster_str))104 x += db.fetchall()[0][0]105 x = x / len(clustering)106 sum = 0107 for cluster in clustering:108 cluster_str = ’,’.join(str(p) for p in cluster)109 db.execute("""SELECT sum(volumen) FROM \"ACEITES_ACUMULADO_VOLUMEN_PEDIDOS\"

WHERE cod_distribuidora IN ({})""".format(cluster_str))110 xi = int(db.fetchall()[0][0])111 sum += pow(xi - x, 2)112 return math.sqrt(sum/len(clustering))113

114 def get_volume_distribution(clustering, db):115 volumes = []116 for cluster in clustering:117 cluster_str = get_cluster_str(cluster)118 db.execute(119 """SELECT volumen from \"ACEITES_ACUMULADO_VOLUMEN_PEDIDOS\" WHERE

cod_distribuidora IN ({})""".format(120 cluster_str))121 volumes.append([int(row[0]) for row in db.fetchall()])122 return volumes123

124 def distance(a, b, db):125 db.execute("""SELECT distancia FROM matriz_thesis WHERE origen={} AND destino

={}""".format(a, b))126 res = db.fetchall()127 if len(res) > 0:128 return res[0][0]129

130 def lts_per_klm(clustering, db):131 lk = 0132 for cluster in clustering:133 db.execute("""SELECT sum(volumen) from "ACEITES_ACUMULADO_VOLUMEN_PEDIDOS"

WHERE cod_distribuidora IN ({});""".format(get_cluster_str(cluster)))134 res = db.fetchall()135 lts = res[0][0]136 km = 0137 medoid = cluster_medoid(cluster, db)138 for point in cluster:139 km += float(distance(point, medoid, db)/1000)140 lk += float(lts)/float(km)141 lk = lk / len(clustering)142 return lk143

144 def connectivity_compactness(clustering, db):


CAJA CON PYTHON

145 n = clustering_size(clustering)146 connectivity = 0147 h = 100148 for cluster in clustering:149 for point in cluster:150 point_connectivity = 0151

152 db.execute("""select destino, distancia from matriz_thesis where origen ={} and not destino = {} order by distancia limit {}""".format(point, point, h))

153 res = db.fetchall()154 for nn in res:155 point_connectivity += 1 if nn[0] in cluster else 0156 connectivity += point_connectivity/h157 return float(connectivity) / float(n)158

159 def cluster_separation_sum(clustering, db):160 medoids = get_medoids(clustering, db)161 css = 0162

163 i = 0164 for cluster_i in clustering:165 j = 0166 for cluster_j in clustering:167 if cluster_i is cluster_j:168 continue169 css += distance(medoids[i], medoids[j], db) / 1000170 j += 1171 i += 1172 return css173

174 def min_medoid_distance(clustering, db):175 medoids = get_medoids(clustering, db)176

177 min_d = float(’Inf’)178 for medoid_i in medoids:179 for medoid_j in medoids:180 d = distance(medoid_i, medoid_j, db)181 if d > 0 and d < min_d:182 min_d = d183 return min_d184

185 def turi_index(clustering, db):186 medoids = get_medoids(clustering, db)187 n = clustering_size(clustering)188 # intra189 intra = 0190 for k in range(len(clustering)):191 db.execute("""select sum(distancia) from matriz_thesis where origen = {} and

destino IN ({})""".format(medoids[k], get_cluster_str(clustering[k])))192 intra += pow(db.fetchall()[0][0],2)193 intra = intra / n194 #195 inter = pow(min_medoid_distance(clustering, db),2)196 validity = intra/inter197 return validity198

199 def dunn_index(clustering, db):200 medoids = get_medoids(clustering, db)201 delta_i = 0.0202


203 for c in range(len(clustering)):204 db.execute("""SELECT avg(distancia) from matriz_thesis where origen = {} and

destino in ({})""".format(medoids[c], get_cluster_str(clustering[c])))205 d = db.fetchall()[0][0]206 if d > delta_i:207 delta_i = d208

209 min_d = min_medoid_distance(clustering, db)210 return min_d / delta_i211

212 def dbi(clustering, db):213 medoids = get_medoids(clustering, db)214 dbi = 0215 for i in range(len(medoids)):216 db.execute("""SELECT avg(distancia) from matriz_thesis where origen = {} and

destino in ({})""".format(medoids[i], get_cluster_str(clustering[i])))217 di = 0218 si = db.fetchall()[0][0]219 for j in range(len(medoids)):220 if i == j:221 continue222 db.execute("""SELECT avg(distancia) from matriz_thesis where origen = {}

and destino in ({})""".format(medoids[j], get_cluster_str(clustering[j])))223 sj = db.fetchall()[0][0]224 db.execute("""select distancia from matriz_thesis where origen = {} and

destino = {}""".format(medoids[i], medoids[j]))225 mij = db.fetchall()[0][0]226 rij = (si+sj)/mij227 if rij > di:228 di = rij229 dbi += di230 dbi = dbi/len(clustering)231 return dbi232

233 def silh(clustering, db):234 si = 0235 values = []236 for cluster in clustering:237 for i in cluster:238 db.execute("""select avg(distancia) from matriz_thesis where origen = {}

and destino in ({})""".format(i, get_cluster_str(cluster)))239 ai = db.fetchall()[0][0]240 bi = float(’Inf’)241 for neighbour in clustering:242 db.execute("""select avg(distancia) from matriz_thesis where origen =

{} and destino in ({})""".format(i, get_cluster_str(neighbour)))243 aux_bi = db.fetchall()[0][0]244 if aux_bi < bi:245 bi = aux_bi246 si += (bi - ai)/max(ai, bi)247 values.append((bi - ai)/max(ai, bi))248 n = clustering_size(clustering)249 si = si / n250 return si251

252 if __name__ == ’__main__’:253 conn = psycopg2.connect("dbname=’thesis’ user=’postgres’ host=’localhost’

password=’postgres’")254 cur = conn.cursor()255


CAJA CON PYTHON

256 cl = {}257

258 cl[’original’] = read_clustering(’../datasets/finales/cl_original.csv’)259 cl[’kmedoids’] = read_clustering(’../datasets/finales/cl_kmedoids.csv’)260 cl[’GDE3’] = read_clustering(’../datasets/finales/GDE3.csv’)261 cl[’IBEA’] = read_clustering(’../datasets/finales/IBEA.csv’)262 cl[’NSGAII’] = read_clustering(’../datasets/finales/NSGAII.csv’)263 cl[’OMOPSO’] = read_clustering(’../datasets/finales/OMOPSO.csv’)264 cl[’SPEA2’] = read_clustering(’../datasets/finales/SPEA2.csv’)265

266 columns = []267 columns.append(’Algoritmo’)268 columns.append(’Distancia TSP’)269 columns.append(’Volumen (desviacion tipica)’)270 columns.append(’Distancia (desviacion)’)271 columns.append(’Indice Turi’)272 columns.append(’Conectividad’)273 columns.append(’Indice Silhouette’)274 columns.append(’Litros por Km’)275 columns.append(’Separacion entre medoides’)276 columns.append(’Minima distancia entre medoides’)277 columns.append(’Indice Dunn’)278 columns.append(’Indice Davies-Bouldin’)279 separation = ’\t\t’280 print separation.join(c for c in columns)281

282 for key in cl:283 metrics = []284 metrics.append(key)285 metrics.append(tsp_mean(cl[key], cur) / 1000)286 metrics.append(standard_deviation(cl[key], cur))287 metrics.append(distance_deviation(cl[key], cur) / 1000)288 metrics.append(turi_index(cl[key], cur))289 metrics.append(connectivity_compactness(cl[key], cur))290 metrics.append(silh(cl[key], cur))291 metrics.append(lts_per_klm(cl[key], cur))292 metrics.append(cluster_separation_sum(cl[key], cur))293 metrics.append(min_medoid_distance(cl[key], cur)/1000)294 metrics.append(dunn_index(cl[key], cur))295 metrics.append(dbi(cl[key], cur))296

297 print separation.join(str(m) for m in metrics)298 volume_distribution = get_volume_distribution(cl[key], cur)299 cluster_d_distr, d_distr = get_distance_distribution(cl[key], cur)300

301 fig = pyplot.figure(dpi=200)302 pyplot.boxplot(volume_distribution)303 pyplot.savefig(’../datasets/plots/{}_volume_per_cluster.png’.format(key))304 pyplot.figure(dpi=200)305 pyplot.boxplot(cluster_d_distr)306

pyplot.savefig(’../datasets/plots/{}_cluster_distance_to_medoid.png’.format(key))307

308 data = []309 for key in cl:310 _, d_distr = get_distance_distribution(cl[key], cur)311 data.append(d_distr)312

313 pyplot.figure(dpi=200)314 pyplot.boxplot(data)


315 pyplot.xticks([1, 2, 3, 4, 5, 6, 7], list(cl.keys()))316 pyplot.savefig(’../datasets/plots/global_distance_to_medoid.png’)

Codigo C.1: Generacion de metricas de validacion y diagramas

Bibliografıa

[Achtert et al., 2007a] Achtert, E., Bohm, C., Kriegel, H. P., Kroger, P., and Zi-mek, A. (2007a). On Exploring Complex Relationships of Correlation Clusters.In 19th International Conference on Scientific and Statistical Database Mana-gement (SSDBM 2007), pages 7–7.

[Achtert et al., 2007b] Achtert, E., Bohm, C., Kriegel, H.-P., Kroger, P., Muller-Gorman, I., and Zimek, A. (2007b). Detection and Visualization of SubspaceCluster Hierarchies. In Advances in Databases: Concepts, Systems and Appli-cations, pages 152–163. Springer, Berlin, Heidelberg.

[Aggarwal and Reddy, 2013] Aggarwal, C. C. and Reddy, C. K. (2013). Data Clus-tering. Chapman and Hall/CRC.

[Alpaydin, 2014] Alpaydin, E. (2014). Introduction to Machine Learning. TheMIT Press.

[Ankerst et al., 1999] Ankerst, M., Breunig, M. M., Kriegel, H.-p., and Sander, J.(1999). OPTICS: Ordering Points To Identify the Clustering Structure. pages49–60. ACM Press.

[Bianchi et al., 2009] Bianchi, L., Dorigo, M., Gambardella, L. M., and Gutjahr,W. J. (2009). A survey on metaheuristics for stochastic combinatorial optimi-zation. Natural Computing, 8(2):239–287.

[Bishop, 2006] Bishop, C. (2006). Pattern Recognition and Machine Learning.Springer.

[Blum et al., 2011] Blum, C., Puchinger, J., Raidl, G. R., and Roli, A. (2011).Hybrid metaheuristics in combinatorial optimization: A survey. Applied SoftComputing, 11(6):4135–4151.

95

96 Bibliografıa

[Bonyadi and Michalewicz, 2017] Bonyadi, M. R. and Michalewicz, Z. (2017). Par-ticle Swarm Optimization for Single Objective Continuous Space Problems: AReview. Evolutionary Computation, 25(1):1–54.

[Bohm et al., 2004] Bohm, C., Kailing, K., Kroger, P., and Zimek, A. (2004). Com-puting Clusters of Correlation Connected Objects. In Proceedings of the 2004ACM SIGMOD International Conference on Management of Data, SIGMOD’04, pages 455–466, New York, NY, USA. ACM.

[Cai and Ma, 2010] Cai, W. and Ma, L. (2010). Applications of critical tempera-ture in minimizing functions of continuous variables with simulated annealingalgorithm. Computer Physics Communications, 181(1):11–16.

[Cerny, 1985] Cerny, V. (1985). Thermodynamical approach to the traveling sa-lesman problem: An efficient simulation algorithm. Journal of OptimizationTheory and Applications, 45(1):41–51.

[Chelouah and Siarry, 2000] Chelouah, R. and Siarry, P. (2000). Tabu Searchapplied to global optimization. European Journal of Operational Research,123(2):256–270.

[Coello et al., 2010] Coello, C. A. C., Dhaenens, C., and Jourdan, L. (2010). Multi-Objective Combinatorial Optimization: Problematic and Context. In Coello, C.A. C., Dhaenens, C., and Jourdan, L., editors, Advances in Multi-Objective Na-ture Inspired Computing, number 272 in Studies in Computational Intelligence,pages 1–21. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-11218-8 1.

[Coello et al., 2006] Coello, C. A. C., Lamont, G. B., and Veldhuizen, D. A. V.(2006). Evolutionary Algorithms for Solving Multi-Objective Problems (Geneticand Evolutionary Computation). Springer-Verlag New York, Inc., Secaucus, NJ,USA.

[Darwin, 1859] Darwin, C. (1859). On the Origin of Species by Means of NaturalSelection. Murray, London.

[Das et al., 2008] Das, S., Abraham, A., and Konar, A. (2008). Swarm IntelligenceAlgorithms in Bioinformatics. In Kelemen, A., Abraham, A., and Chen, Y.,editors, Computational Intelligence in Bioinformatics, number 94 in Studies inComputational Intelligence, pages 113–147. Springer Berlin Heidelberg.

[Das et al., 2009] Das, S., Abraham, A., and Konar, A. (2009). MetaheuristicPattern Clustering – An Overview. In Metaheuristic Clustering, number 178 in

Bibliografıa 97

Studies in Computational Intelligence, pages 1–62. Springer Berlin Heidelberg.DOI: 10.1007/978-3-540-93964-1 1.

[Das et al., 2016] Das, S., Mullick, S. S., and Suganthan, P. N. (2016). Recentadvances in differential evolution – An updated survey. Swarm and EvolutionaryComputation, 27:1–30.

[Das and Suganthan, 2011] Das, S. and Suganthan, P. N. (2011). Differential Evo-lution: A Survey of the State-of-the-Art. IEEE Transactions on EvolutionaryComputation, 15(1):4–31.

[Davies and Bouldin, 1979] Davies, D. L. and Bouldin, D. W. (1979). A ClusterSeparation Measure. IEEE Trans. Pattern Anal. Mach. Intell., 1(2):224–227.

[Deb et al., 2002] Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. Trans. Evol.Comp, 6(2):182–197.

[Dempster et al., 1977] Dempster, A. P., Laird, N. M., and Rubin, D. B. (1977).Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal ofthe Royal Statistical Society. Series B (Methodological), 39(1):1–38.

[Dorigo, 1992] Dorigo, M. (1992). Optimization, Learning and Natural Algorithms(in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano,Milan, Italy.

[Dorigo and Stutzle, 2010] Dorigo, M. and Stutzle, T. (2010). Ant Colony Opti-mization: Overview and Recent Advances. In Gendreau, M. and Potvin, J.-Y.,editors, Handbook of Metaheuristics, number 146 in International Series in Ope-rations Research & Management Science, pages 227–263. Springer US. DOI:10.1007/978-1-4419-1665-5 8.

[Dragoi and Dafinescu, 2016] Dragoi, E.-n. and Dafinescu, V. (2016). Parametercontrol and hybridization techniques in differential evolution: a survey. TheArtificial Intelligence Review; Dordrecht, 45(4):447–470.

[Duda et al., 2001] Duda, R. O., Hart, P. E., and Stork, D. G. (2001). PatternClassification (2nd Ed). Wiley.

[Dunn, 1974] Dunn, J. C. (1974). Well-Separated Clusters and Optimal FuzzyPartitions. Journal of Cybernetics, 4(1):95–104.

98 Bibliografıa

[Engelbrecht, 2006] Engelbrecht, A. P. (2006). Fundamentals of ComputationalSwarm Intelligence. John Wiley & Sons.

[Ester et al., 1996] Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. (1996). ADensity-based Algorithm for Discovering Clusters a Density-based Algorithm forDiscovering Clusters in Large Spatial Databases with Noise. In Proceedings ofthe Second International Conference on Knowledge Discovery and Data Mining,KDD’96, pages 226–231, Portland, Oregon. AAAI Press.

[Farmer et al., 1986] Farmer, J. D., Packard, N. H., and Perelson, A. S. (1986).The Immune System, Adaptation, and Machine Learning. Phys. D, 2(1-3):187–204.

[Feo and Resende, 1995] Feo, T. A. and Resende, M. G. C. (1995). Greedy Rando-mized Adaptive Search Procedures. Journal of Global Optimization, 6(2):109–133.

[Fister et al., 2013] Fister, I., Fister, I., Yang, X.-S., and Brest, J. (2013). A com-prehensive review of firefly algorithms. Swarm and Evolutionary Computation,13:34–46.

[Gendreau, 2003] Gendreau, M. (2003). An Introduction to Tabu Search. In Glo-ver, F. and Kochenberger, G. A., editors, Handbook of Metaheuristics, number 57in International Series in Operations Research & Management Science, pages37–54. Springer US. DOI: 10.1007/0-306-48056-5 2.

[Gendreau and Potvin, 2010] Gendreau, M. and Potvin, J.-Y. (2010). Handbookof Metaheuristics. Springer Publishing Company, Incorporated, 2nd edition.

[Glover, 1977] Glover, F. (1977). HEURISTICS FOR INTEGER PROGRAM-MING USING SURROGATE CONSTRAINTS. Decision Sciences, 8(1):156–166.

[Glover, 1989] Glover, F. (1989). Tabu Search—Part I. ORSA Journal on Com-puting, 1(3):190–206.

[Glover, 1997] Glover, F. (1997). A template for scatter search and path relinking.In Artificial Evolution, pages 1–51. Springer, Berlin, Heidelberg.

[Goldberg and Holland, 1988] Goldberg, D. E. and Holland, J. H. (1988). GeneticAlgorithms and Machine Learning. Machine Learning, 3(2-3):95–99.

Bibliografıa 99

[Handl and Knowles, 2012] Handl, J. and Knowles, J. (2012). Clustering Criteriain Multiobjective Data Clustering. In Parallel Problem Solving from Nature -PPSN XII, pages 32–41. Springer, Berlin, Heidelberg.

[Hansen and Delattre, 1978] Hansen, P. and Delattre, M. (1978). Complete-LinkCluster Analysis by Graph Coloring. Journal of the American Statistical Asso-ciation, 73(362):397–403.

[Hansen et al., 2010] Hansen, P., Mladenovic, N., and Moreno perez, J. A. (2010).Variable neighbourhood search: methods and applications. Annals of OperationsResearch; New York, 175(1):367–407.

[Holland, 1975] Holland, J. H. (1975). Adaptation in natural and artificial systems:An introductory analysis with applications to biology, control, and artificial in-telligence. University of Michigan Press. Published: Unknown Binding.

[Jain and Dubes, 1988] Jain, A. K. and Dubes, R. C. (1988). Algorithms for Clus-tering Data. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.

[Jose-Garcıa and Gomez-Flores, 2016] Jose-Garcıa, A. and Gomez-Flores, W.(2016). Automatic clustering using nature-inspired metaheuristics: A survey.Applied Soft Computing, 41:192–213.

[Kar, 2016] Kar, A. K. (2016). Bio inspired computing – A review of algorithmsand scope of applications. Expert Systems with Applications, 59:20–32.

[Karaboga, 2005] Karaboga, D. (2005). An idea based on Honey Bee Swarm forNumerical Optimization. Technical Report TR06, Erciyes University.

[Kaufman, 1987] Kaufman, L. (1987). Clustering by Means of Medoids. Facultyof Mathematics and Informatics.

[Kennedy and Eberhart, 1995] Kennedy, J. and Eberhart, R. (1995). Particleswarm optimization. In Neural Networks, 1995. Proceedings., IEEE Interna-tional Conference on, volume 4, pages 1942–1948 vol.4.

[Kim et al., 2014] Kim, K., Shan, Y., Nguyen, X. H., and Mckay, R. I. (2014). Pro-babilistic Model Building in Genetic Programming: A Critical Review. GeneticProgramming and Evolvable Machines, 15(2):115–167.

[Kirkpatrick et al., 1983] Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983).Optimization by simulated annealing. Science, 220(4598):671–680.

100 Bibliografıa

[Knowles and Corne, 2002] Knowles, J. and Corne, D. (2002). On metrics for com-paring nondominated sets. In Proceedings of the 2002 Congress on EvolutionaryComputation, 2002. CEC ’02, volume 1, pages 711–716.

[Koza, 1992] Koza, J. R. (1992). Genetic Programming: On the Programming ofComputers by Means of Natural Selection. MIT Press, Cambridge, MA, USA.

[Kukkonen and Lampinen, 2005] Kukkonen, S. and Lampinen, J. (2005). GDE3:the third evolution step of generalized differential evolution. In 2005 IEEECongress on Evolutionary Computation, volume 1, pages 443–450 Vol.1.

[Larranaga et al., 2012] Larranaga, P., Karshenas, H., Bielza, C., and Santana, R.(2012). A review on probabilistic graphical models in evolutionary computation.Journal of Heuristics; Boston, 18(5):795–819.

[Larranaga and Lozano, 2001] Larranaga, P. and Lozano, J. A. (2001). Estimationof Distribution Algorithms: A New Tool for Evolutionary Computation. KluwerAcademic Publishers, Norwell, MA, USA.

[Lim, 2014] Lim, T. Y. (2014). Structured population genetic algorithms: a lite-rature survey. The Artificial Intelligence Review; Dordrecht, 41(3):385–399.

[Lourenco et al., 2010] Lourenco, H. R., Martin, O. C., and Stutzle, T. (2010). Ite-rated Local Search: Framework and Applications. In Gendreau, M. and Potvin,J.-Y., editors, Handbook of Metaheuristics, number 146 in International Seriesin Operations Research & Management Science, pages 363–397. Springer US.DOI: 10.1007/978-1-4419-1665-5 12.

[Luxen and Vetter, 2011] Luxen, D. and Vetter, C. (2011). Real-time routing withOpenStreetMap data. In Proceedings of the 19th ACM SIGSPATIAL Interna-tional Conference on Advances in Geographic Information Systems, GIS ’11,pages 513–516, New York, NY, USA. ACM.

[Lopez et al., 2017] Lopez, J., Moratilla, A., and Fernandez, E. (2017). La visua-lizacion de sistemas cartograficos en dispositivos moviles: problemas, aproxima-ciones y casos de ejemplo. In Nuevas tecnologais audiovisuales para nuevas na-rrativas interactivas digitales en la era multidispositivo, pages 55–65. Mc GrawHill.

[MacQueen, 1967] MacQueen, J. B. (1967). Some Methods for Classification andAnalysis of MultiVariate Observations. In Cam, L. M. L. and Neyman, J.,editors, Proc. of the fifth Berkeley Symposium on Mathematical Statistics andProbability, volume 1, pages 281–297. University of California Press.

Bibliografıa 101

[Martınez et al., 2011] Martınez, S. Z., Oropeza, E. G. Y., and Coello, C. A. C.(2011). Self-adaptation Techniques Applied to Multi-Objective EvolutionaryAlgorithms. In Learning and Intelligent Optimization, pages 567–581. Springer,Berlin, Heidelberg.

[Mckay et al., 2010] Mckay, R. I., Hoai, N. X., Whigham, P. A., Shan, Y., andO’Neill, M. (2010). Grammar-based Genetic Programming: A Survey. GeneticProgramming and Evolvable Machines, 11(3-4):365–396.

[Metropolis et al., 1953] Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N.,Teller, A. H., and Teller, E. (1953). Equation of State Calculations by FastComputing Machines. Journal of Chemical Physics, 21:1087–1092.

[Mladenovic and Hansen, 1997] Mladenovic, N. and Hansen, P. (1997). Variableneighborhood search. Computers & Operations Research, 24(11):1097–1100.

[Moscato, 1989] Moscato, P. (1989). On Evolution, Search, Optimization, GeneticAlgorithms and Martial Arts: Towards Memetic Algorithms. Technical ReportC3P Report 826, California Institute of Technology.

[Mukhopadhyay et al., 2015] Mukhopadhyay, A., Maulik, U., and Bandyopadh-yay, S. (2015). A Survey of Multiobjective Evolutionary Clustering. ACMComput. Surv., 47(4):61:1–61:46.

[Mukhopadhyay et al., 2014] Mukhopadhyay, A., Maulik, U., Bandyopadhyay, S.,and Coello, C. A. C. (2014). Survey of Multiobjective Evolutionary Algorithmsfor Data Mining: Part II. IEEE Transactions on Evolutionary Computation,18(1):20–35.

[Muhlenbein and Paaß, 1996] Muhlenbein, H. and Paaß, G. (1996). From recom-bination of genes to the estimation of distributions I. Binary parameters. InParallel Problem Solving from Nature — PPSN IV, pages 178–187. Springer,Berlin, Heidelberg.

[Nanda and Panda, 2014] Nanda, S. J. and Panda, G. (2014). A survey on na-ture inspired metaheuristic algorithms for partitional clustering. Swarm andEvolutionary Computation, 16:1–18.

[Neri and Cotta, 2012] Neri, F. and Cotta, C. (2012). Memetic algorithms andmemetic computing optimization: A literature review. Swarm and EvolutionaryComputation, 2:1–14.

102 Bibliografıa

[Neri and Tirronen, 2010] Neri, F. and Tirronen, V. (2010). Recent advances indifferential evolution: a survey and experimental analysis. The Artificial Inte-lligence Review; Dordrecht, 33(1-2):61–106.

[Nourani and Andresen, 1998] Nourani, Y. and Andresen, B. (1998). A compari-son of simulated annealing cooling strategies. Journal of Physics A Mathema-tical General, 31:8373–8385.

[Pareto, 1896] Pareto, V. (1896). Cours d’Economie Politique. Droz, Geneve.

[Passino, 2002] Passino, K. M. (2002). Biomimicry of bacterial foraging for distri-buted optimization and control. IEEE Control Systems, 22(3):52–67.

[Price et al., 2005] Price, K., Storn, R. M., and Lampinen, J. A. (2005). Differen-tial Evolution: A Practical Approach to Global Optimization (Natural ComputingSeries). Springer-Verlag New York, Inc., Secaucus, NJ, USA.

[Rao, 2009] Rao, S. S. (2009). Engineering Optimization: Theory and Practice:Fourth Edition. John Wiley and Sons. DOI: 10.1002/9780470549124.

[Ray and Turi, 1999] Ray, S. and Turi, R. H. (1999). Determination of number ofclusters in K-means clustering and application in colour segmentation. In The4th International Conference on Advances in Pattern Recognition and DigitalTechniques, pages 137–143.

[Resende and Ribeiro, 2016] Resende, M. G. C. and Ribeiro, C. C. (2016). Opti-mization by GRASP: Greedy Randomized Adaptive Search Procedures. Springer.Google-Books-ID: ao1jDQAAQBAJ.

[Resende et al., 2010] Resende, M. G. C., Ribeiro, C. C., Glover, F., and Martı, R.(2010). Scatter Search and Path-Relinking: Fundamentals, Advances, and Ap-plications. In Gendreau, M. and Potvin, J.-Y., editors, Handbook of Metaheuris-tics, number 146 in International Series in Operations Research & ManagementScience, pages 87–107. Springer US. DOI: 10.1007/978-1-4419-1665-5 4.

[Rousseeuw, 1987] Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to theinterpretation and validation of cluster analysis. Journal of Computational andApplied Mathematics, 20:53–65.

[Russell and Norvig, 2003] Russell, S. J. and Norvig, P. (2003). Artificial Intelli-gence: A Modern Approach. Pearson Education, 2 edition.

Bibliografıa 103

[Rıos et al., 2004] Rıos, S., Mateos, A., Bielza, M. C., and Jimenez, A. (2004).Investigacion operativa: modelos determinısticos y estocasticos. Editorial Uni-versitaria Ramon Areces. Google-Books-ID: sV6nDAAAQBAJ.

[Shah-Hosseini, 2009] Shah-Hosseini, H. (2009). The Intelligent Water Drops Al-gorithm: a Nature-Inspired Swarm-Based Optimization Algorithm. Int. J. Bio-Inspired Comput., 1(1/2):71–79.

[Sierra and Coello, 2005] Sierra, M. R. and Coello, C. A. (2005). ImprovingPSO-Based Multi-objective Optimization Using Crowding, Mutation and $ın$-dominance. In Proceedings of the Third International Conference on Evolutio-nary Multi-Criterion Optimization, EMO’05, pages 505–519, Berlin, Heidelberg.Springer-Verlag.

[Simon, 2008] Simon, D. (2008). Biogeography-Based Optimization. IEEETransactions on Evolutionary Computation, 12(6):702–713.

[Storn and Price, 1997] Storn, R. and Price, K. (1997). Differential Evolution – ASimple and Efficient Heuristic for global Optimization over Continuous Spaces.Journal of Global Optimization, 11(4):341–359.

[Stutzle, 1999] Stutzle, T. G. (1999). Local Search Algorithms for CombinatorialProblems: Analysis, Improvements, and New Applications. Infix. Google-Books-ID: 7R0XAAAACAAJ.

[Suman and Kumar, 2006] Suman, B. and Kumar, P. (2006). A survey of simu-lated annealing as a tool for single and multiobjective optimization. Journal ofthe Operational Research Society, 57(10):1143–1160.

[Talbi, 2009] Talbi, E.-G. (2009). Metaheuristics: From Design to Implementation.Wiley Publishing.

[Umbarkar and Sheth, 2015] Umbarkar, A. J. and Sheth, P. D. (2015). CrossoverOperators in Genetic Algorithms:A Review. ICTACT Journal on Soft Compu-ting, 6(1):1083–1092.

[Veldhuizen and Lamont, 2000] Veldhuizen, D. A. V. and Lamont, G. B. (2000).On measuring multiobjective evolutionary algorithm performance. In Pro-ceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat.No.00TH8512), volume 1, pages 204–211 vol.1.

104 Bibliografıa

[von Lucken et al., 2014] von Lucken, C., Baran, B., and Brizuela, C. (2014). Asurvey on multi-objective evolutionary algorithms for many-objective problems.Computational Optimization and Applications; New York, 58(3):707–756.

[Voudouris and Tsang, 1999] Voudouris, C. and Tsang, E. (1999). Guided localsearch and its application to the traveling salesman problem. European Journalof Operational Research, 113(2):469–499.

[Voudouris et al., 2010] Voudouris, C., Tsang, E. P. K., Alsheddy, A., Cochran,J. J., Cox, L. A., Keskinocak, P., Kharoufeh, J. P., and Smith, J. C. (2010). Gui-ded Local Search. In Wiley Encyclopedia of Operations Research and Manage-ment Science. JohnWiley & Sons, Inc. DOI: 10.1002/9780470400531.eorms0369.

[Witten et al., 2011] Witten, I. H., Frank, E., and Hall, M. A. (2011). Data Mi-ning: Practical Machine Learning Tools and Techniques. Morgan KaufmannPublishers Inc., San Francisco, CA, USA, 3rd edition.

[Xu and Wunsch II, 2005] Xu, R. and Wunsch II, D. (2005). Survey of ClusteringAlgorithms. IEEE Transactions on Neural Networks, 16(3):645–678.

[Yang, 2010] Yang, X.-S. (2010). A New Metaheuristic Bat-Inspired Algorithm.In Gonzalez, J. R., Pelta, D. A., Cruz, C., Terrazas, G., and Krasnogor, N.,editors, Nature Inspired Cooperative Strategies for Optimization (NICSO 2010),number 284 in Studies in Computational Intelligence, pages 65–74. SpringerBerlin Heidelberg. DOI: 10.1007/978-3-642-12538-6 6.

[Yang and Deb, 2009] Yang, X. S. and Deb, S. (2009). Cuckoo Search via Levyflights. In 2009 World Congress on Nature Biologically Inspired Computing(NaBIC), pages 210–214.

[Zitzler et al., 2000] Zitzler, E., Deb, K., and Thiele, L. (2000). Comparison ofMultiobjective Evolutionary Algorithms: Empirical Results. Evol. Comput.,8(2):173–195.

[Zitzler and Kunzli, 2004] Zitzler, E. and Kunzli, S. (2004). Indicator-Based Se-lection in Multiobjective Search. In Parallel Problem Solving from Nature -PPSN VIII, pages 832–842. Springer, Berlin, Heidelberg.

[Zitzler et al., 2001] Zitzler, E., Laumanns, M., and Thiele, L. (2001). SPEA2:Improving the strength pareto evolutionary algorithm for multiobjective op-timization. In Giannakoglou, K. C., Tsahalis, D. T., Periaux, J., Papailiou,K. D., and Fogarty, T., editors, Evolutionary Methods for Design Optimization

Bibliografıa 105

and Control with Applications to Industrial Problems, pages 95–100, Athens,Greece. International Center for Numerical Methods in Engineering.

[Zitzler and Thiele, 1999] Zitzler, E. and Thiele, L. (1999). Multiobjective evolu-tionary algorithms: a comparative case study and the strength Pareto approach.IEEE Transactions on Evolutionary Computation, 3(4):257–271.

[Zitzler et al., 2003] Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., andFonseca, V. G. d. (2003). Performance assessment of multiobjective optimi-zers: an analysis and review. IEEE Transactions on Evolutionary Computation,7(2):117–132.

metaheurísticas para el análisis de datos masivos en el...

Documents