Meta-huristica

The Traveling Salesman Problem (TSP)
Presentación del curso
2 ¿Por qué necesitamos (Meta) heurística
El problema del vendedor viajero
La programación de máquinas paralelas Problema
El problema de la ubicación de almacenes
3 Una introducción muy rápida de algoritmos
4 Introducción Heurística
Introducción
Construcción y Mejoramiento
Limitaciones de la "simple" heurística
5 Introducción aMetaheurísticas
Etimología y Aspectos históricos
Evaluación de Metaheurísticas

Varios libros útiles, por ejemplo:
Manual de Metaheurísticas, Fred Glover y Gary A.
Kochenberger, International Series Kluwer, ISBN
1-4020-7263-5
Buscar estocástico Local, Fundaciones y Aplicaciones, Holger
H. Thomas & Hoos utzle St ¨, Elsevier, ISBN 1-55860-872-9
Buscar Metodologías, Tutoriales deintroducción en la optimización
y técnicas de apoyo a las decisiones, Edmund Burke y K.
Kendall Graham, Springer, ISBN 0-387-23460-8

Presentación del curso
2 ¿Por qué necesitamos (Meta) heurística
El problema del vendedor viajero
La programación de máquinas paralelas Problema
El problema de la ubicación de almacenes
3 Una introducción muy rápida de algoritmos
4 Introducción HeurísticaIntroducción
Construcción y Mejoramiento
Limitaciones de la "simple" heurística
5 Introducción a Metaheurísticas
Etimología y Aspectos históricos
Evaluación de Metaheurísticas

Imagine un problema con. . .
Algunas limitaciones operativas
Ejemplo: visita todos los clientes
Por lo menos una solución óptima
Optimizar = Minimizar o Maximizar una función objetivo
(Alias Fitness)
Ejemplo:Reducir al mínimo la suma de los costes operativos
Tal que encontrar la solución óptima es muy difícil. . .
Incluso con el mejor programador del mundo
Incluso con el mejor lenguaje de programación
Incluso con el mejor sistema operativo
Incluso con el ordenador más rápido
Incluso 20 años en el futuro
Estos problemas existen!
31
Un viaje Saleman quiere vender sus productos a los clientes. . .Teniendo en cuenta los datos: distancias utilizando la red de carreteras
Limitaciones: a partir de un depósito dado, visita todos los clientes n
Decisión: elegir para visitar
Objetivo: minimizar la distancia total
Un ejemplo! Planteamiento básico: enumerar todos
32
Un viaje Saleman quiere vender sus productos a los clientes. . .
Teniendo en cuenta los datos: distancias utilizando la redde carreteras
Limitaciones: a partir de un depósito dado, visita todos los clientes n
Decisión: elegir para visitar
Objetivo: minimizar la distancia total
Hasta que el tamaño de una computadora puede enumerar todas las soluciones?
43
Ejercicio: ¿De cuántas maneras puede visitar n clientes?
Una solución es una permutación!
Número de soluciones = número de permutaciones = n!
(N!
2 silas distancias son simétricas)
Supongamos que nuestro equipo puede procesar los últimos 100.000 soluciones por
segundos. . .
10 clientes: 36 s
12 clientes: 1 h 20
15 clientes: 5 meses
20 clientes: 770.940 años
99 clientes: 2,96 · 10143 años! (Universo es de 5 · 109 y.o.)
Ahora bien, supongamos que tenemos un ordenador de un millón de veces más rápido:
46
Ejercicio: ¿De cuántas maneraspuede visitar n clientes?
Una solución es una permutación!
Número de soluciones = número de permutaciones = n!
(N!
2 si las distancias son simétricas)
Supongamos que nuestro equipo puede procesar los últimos 100.000 soluciones por
segundos. . .
10 clientes: 36 s
12 clientes: 1 h 20
15 clientes: 5 meses
20 clientes: 770.940 años
99 clientes: 2,96 · 10143 años! (Universo es de 5 · 109 y.o.)22 customers: 356 years
25 customers: 5 · 106 years
53

El problema de programación de máquinas paralelas (P | | C max)
Queremos realizar trabajos de producción n, tenemos m "paralelo"
máquinas idénticas. . .
Teniendo en cuenta los datos: para cada trabajo, su duración
Restricción: realizar todos los trabajos
Decisión: asignar trabajos a máquinas
Objetivo: poner fin al último...