Optimización combinatorial aplicada a la
solución de algunos problemas de ingeniería
Mauricio Granada Echeverri
Universidad Tecnológica de Pereira
Grupo de Desarrollo en Investigación de operaciones - DINOP
Grupo de Investigación en Planeamiento Eléctrico - GP
Contenido
1. Breve Historia
2. Problemas del mundo real (optimización)
3. Técnicas de Solución
4. Aplicaciones
4. Preguntas
Breve Historia
 El Grupo de Investigación en Planeamiento
de Sistemas Eléctricos se creó en el año
1999, para soportar la investigación aplicada
a los Sistemas Eléctricos, en la UTP.
 Actualmente es un grupo de investigación
reconocido por COLCIENCIAS y clasificado
como tipo A
Breve Historia
Áreas de investigación:

Planeamiento de sistemas de transmisión y distribución de energía
eléctrica

Calidad de la energía eléctrica

Mercado de energía

Confiabilidad de sistemas eléctricos

Investigación de operaciones y optimización matemática aplicada

Despacho hidrotérmico
Breve Historia
 El grupo DINOP es creado en el año 2002
como resultado del fortalecimiento, por más de
3 años, de una de las líneas de investigación
desarrolladas en la maestría del programa de
ingeniería eléctrica de la Universidad
Tecnológica de Pereira.
Breve Historia
Áreas de investigación:








PLANEACIÒN Y GESTIÒN OPTIMA DE PROCESOS
ANÁLISIS DE RIESGOS
ANÁLISIS DE DATOS
OPTIMIZACIÓN COMBINATORIA Y EXACTA
PROGRAMACIÓN LINEAL, ENTERA Y DINÁMICA
PROGRAMACIÓN NO LINEAL
MODELOS DE REDES
MODELOS PROBABILISTICOS
PROBLEMAS DEL MUNDO REAL (optimización)
 La optimización es el procedimiento de
encontrar y comparar soluciones factibles
hasta que no se pueda encontrar una
mejor solución.
 La optimización se refiere a encontrar una
o más soluciones factibles las cuales
corresponden a valores extremos de uno
o más objetivos
PROBLEMAS DEL MUNDO REAL (optimización)
Problemas del
Mundo Real
Problemas con unas buenas
soluciones
Conjunto de Herramientas 1
Conjunto de Herramientas 2
Técnicas de IA
Problemas con
soluciones Exactas
Existe cierto grado de independencia entre los problemas
propios de la IA y las técnicas de solución propias de la IA
PROBLEMAS DEL MUNDO REAL (optimización)
PROBLEMA DE ASIGNACIÓN GENERALIZADA
TAREA 1
TAREA 2
TAREA 3
TAREA 4
COSTO RECURSO COSTO RECURSO COSTO RECURSO COSTO RECURSO
JUAN
PEDRO
$ 1 3 HORAS
$ 2 2 HORAS
$ 2 1 HORA
$ 1 3 HORAS
$ 5 4 HORAS
$ 3 4 HORAS
RECURSOS
$ 6 4 HORAS
$ 10 2 HORAS
COSTO
TAREA 1
TAREA 2
TAREA 3
TAREA 4
JUAN
PEDRO
JUAN
JUAN
JUAN
JUAN
12 HORAS
0 HORAS
$ 14
INFACTIBLE
JUAN
JUAN
JUAN
JUAN
JUAN
PEDRO
PEDRO
JUAN
8 HORAS
8 HORAS
2 HORAS
4 HORAS
$ 18
$ 12
FACTIBLE
FACTIBLE
JUAN
JUAN
PEDRO
PEDRO
4 HORAS
6 HORAS
$ 16
FACTIBLE
JUAN
JUAN
PEDRO
PEDRO
JUAN
JUAN
JUAN
PEDRO
11 HORAS
7 HORAS
3 HORAS
5 HORAS
$ 13
$ 17
INFACTIBLE
FACTIBLE
JUAN
PEDRO
PEDRO
JUAN
7 HORAS
7 HORAS
$ 10
FACTIBLE
JUAN
PEDRO
PEDRO
PEDRO
3 HORAS
9 HORAS
$ 15
INFACTIBLE
PEDRO
JUAN
JUAN
JUAN
9 HORAS
2 HORAS
$ 15
INFACTIBLE
PEDRO
JUAN
JUAN
PEDRO
5 HORAS
4 HORAS
$ 15
FACTIBLE
PEDRO
JUAN
PEDRO
JUAN
5 HORAS
6 HORAS
$ 13
FACTIBLE
PEDRO
JUAN
PEDRO
PEDRO
1 HORA
8 HORAS
$ 17
FACTIBLE
PEDRO
PEDRO
JUAN
JUAN
8 HORAS
5 HORAS
$ 14
FACTIBLE
PEDRO
PEDRO
JUAN
PEDRO
4 HORAS
7 HORAS
$ 14
FACTIBLE
PEDRO
PEDRO
PEDRO
PEDRO
PEDRO
PEDRO
JUAN
PEDRO
4 HORAS
0 HORAS
9 HORAS
11 HORAS
$ 12
$ 16
INFACTIBLE
INFACTIBLE
PROBLEMAS DEL MUNDO REAL (optimización)
PROBLEMA DE ASIGNACIÓN GENERALIZADA
Combinaciones = Agentes ^ Tareas
100
5
 7.88 E 69
Si se realizan 1.000.000.000.000 operaciones
por segundo, entonces en un año se tendrán
3.15E19 operaciones
2.16 E50 AÑOS
EDAD DEL UNIVERSO =
20  10
9
AÑOS
PROBLEMAS DEL MUNDO REAL (optimización)
 Programación óptima de horarios de clase
 Empaquetamiento óptimo
 Ubicación y dimensionamiento óptimo de
capacitores
 Reconfiguración óptima de alimentadores
 Balance óptimo de fases
 Diseño óptimo de circuitos impresos
 Diseño óptimo de mallas de puesta a
tierra
Técnicas de solución
COLONIA DE HORMIGAS: HORMIGAS REALES
•Iridomyrmex humilis
•Linepithema humile
•Lasius niger
Comportamiento basado en
comunicación directa mediada por
FEROMONAS
EXPERIMENTOS REALIZADOS POR Deneubourg, & Pasteels, 1989
Técnicas de solución
COLONIA DE HORMIGAS: HORMIGAS REALES
LAS HORMIGAS COORDINAN SUS ACTIVIDADES
EXPLOTANDO LA COMUNICACIÒN INDIRECTA
MEDIADA POR MODIFICACIONES DEL AMBIENTE EN
EL CUAL SE MUEVEN = COMUNICACIÓN STIGMERGY
Técnicas de solución
COLONIA DE HORMIGAS: HORMIGAS REALES
PROCESO AUTOCATALITICO DONDE LA HORMIGA
REALIZA UNA ACTIVIDAD MICROSCOPICA QUE
GENERA UN PATRON DE COMPORTAMIENTO
MACROSCOPICO
Técnicas de solución
COLONIA DE HORMIGAS: HORMIGAS REALES
Técnicas de solución
COLONIA DE HORMIGAS: MODELO ESTOCÁSTICO
ESTOCASTICO: QUE DEPENDE DEL AZAR
DeneubourG y colegas, 1990.
 :
Flujo de hormigas por segundo a través de uno de los caminos
v : Velocidad constante a la que se desplaza una hormiga cm
s
La hormiga deposita una unidad de feromona cada vez que pasa sobre un
camino
l s , ll : Longitud del camino corto y del camino largo respectivamente
ts 
ls
tl 
ll
v
l
ts
: Tiempo en el que se recorre el camino corto
: Tiempo en el que se recorre el camino largo
cm
Técnicas de solución
COLONIA DE HORMIGAS: MODELO ESTOCÁSTICO
La probabilidad p ia (t ) que una hormiga llegue al
punto de decisión i  1,2 y seleccione la rama
a  s, l es función de la cantidad total de feromona
 ia (t ) la cual es proporcional a la cantidad de
hormigas que usen la rama durante un tiempo
t .
Técnicas de solución
COLONIA DE HORMIGAS: MODELO ESTOCÁSTICO
Este modelo no considera la evaporación de la feromona
Variación instantánea de la feromona en las ramas
Técnicas de solución
COLONIA DE HORMIGAS: HORMIGAS ARTIFICIALES
LOS EXPERIMENTOS ANTERIORES MUESTRAN
CLARAMENTE QUE LAS COLONIAS DE HORMIGAS
TIENEN
CAPACIDAD
DE
REALIZAR
UNA
OPTIMIZACION CONSTRUCTIVA
Para modelar las hormigas artificiales se deben seguir los
siguientes pasos:
Técnicas de solución
COLONIA DE HORMIGAS: MODELO






Rutas
Tiempo
Rastros de Feromona
Toma de decisiones
Actualización de los rastros de feromona
Evaporación
Técnicas de solución
COLONIA DE HORMIGAS: MODELO
RUTAS
Técnicas de solución
COLONIA DE HORMIGAS: MODELO
TIEMPO
 El tiempo se asume discreto (t=1,2,…) y
cada hormiga se mueve a un nodo vecino
a una velocidad constante de una unidad
de longitud por unidad de tiempo
Técnicas de solución
COLONIA DE HORMIGAS: MODELO
RASTROS DE FEROMONA
 Cada hormiga suma una unidad de
feromona al arco que usó para moverse a
un nodo vecino.
 La adición de feromona se realiza en los
dos sentidos
Técnicas de solución
COLONIA DE HORMIGAS: MODELO
TOMA DE DECISIONES Y ACTUALIZACION DE
RASTROS DE FEROMONA
Técnicas de solución
COLONIA DE HORMIGAS: MODELO
MODELO DISCRETO
 Considera el comportamiento promedio de
todo el sistema y no el comportamiento
estocástico de una hormiga en particular
 Es un modelo discreto que evita el uso de
ecuaciones diferenciales.
 No se tiene en cuenta la evaporación
Técnicas de solución
COLONIA DE HORMIGAS: RUTEO A COSTO MINIMO
1
0.5
Codificación del problema
1
3
1
1
0.5
2
1
G  ( N , A)
1.5
1
1
1
1
2
1
1
El modelo discreto presenta alta probabilidad de formación
de lazos
Algoritmo S-ACO Este algoritmo busca poder resolver problemas
más complejos
Técnicas de solución
COLONIA DE HORMIGAS: Construcción de una
alternativa (forward)
 Construcción de una solución
1
0.
probabilística basada en los
5 1
rastros de feromona (sin
3
1
actualización de feromona).
1 0.5
2
La probabilidad cobija todas
1
1.5
las rutas vecinas excepto la
1 1
1
ruta anterior (esto no aplica a
1
1
callejones sin salida
2
1
 Las hormigas trabajan en 2
modos (forward y backward)

Qué es una hormiga ?

 ij
k



p    l  N ik il

0
k
ij
si
j  Ni
si
j  Ni
k
Técnicas de solución
COLONIA DE HORMIGAS: Regreso y deposito de
feromona (backward)
 Se eliminan los lazos
Existe un lazo
1
0
2
0.5
1
3
1
2
5
1
1
1
1
1
6
Dirección de escaneo
7
1.5
1
2
0.5
0-5-6-7-2-5-6-7-11
Fuente
Destino
1
1
Resultado de la ruta de regreso eliminando
los lazos
11
0-5-6-7-11
 Se actualizan los rastros de feromona del camino recorrido en la
etapa forward basándose en la calidad de la solución
 ij   ij   
k
Beckers(1993)
Técnicas de solución
COLONIA DE HORMIGAS: EVAPORACION DE
FEROMONA
 La evaporación es efectuada aplicando
una regla adecuada. Por ejemplo,
decaimiento a una tasa constante.
Deneubourg 1990
 ij   1     ij ,
   0,1 
 (i, j )  A
Técnicas de solución
COLONIA DE HORMIGAS: CRITERIOS DE PARADA
 Numero de iteraciones (tiempo)
 Cuando todas las hormigas usan la misma
ruta
APLICACIONES
COLONIA DE HORMIGAS: RUTA DE COSTO MÍNIMO
5
4
6
3
7
12
2
FUENTE
1
8
13
11
10
15
14
16
17
19
18
9
DESTINO
APLICACIONES
COLONIA DE HORMIGAS: RESULTADOS DEL EJEMPLO
Tabla 1 Porcentaje de ensayos en los cuales S-ACO convergió al camino largo (100 ensayos
independientes variando los valores de m, con   2 y   0
m
Actualización
de feromona
sin tener en
cuenta la
longitud de la
ruta
Actualización
de feromona
teniendo en
cuenta la
longitud de la
ruta
1
2
4
8
16
32
64
128
256
512
50
42
26
29
24
18
3
2
1
0
18
14
8
0
0
0
0
0
0
0
APLICACIONES
COLONIA DE HORMIGAS: PROBLEMA DE ASIGNACIÓN
GENERALIZADA
1. Se propone una metodología consistente en la evaluación de parámetros
de sensibilidad para la conformación de la población inicial de alternativas
2. Para posibilitar que el algoritmo de solución se desplace a través de la
frontera llevando en cuenta soluciones factibles e infactibles se modificó
el modelo matemático del problema a través de un procedimiento
semejante a la relajación Lagrangeana usando factores de penalización
3. Para fines comparativos se toman como referencia resultados obtenidos
usando algoritmos genéticos
APLICACIONES
COLONIA DE HORMIGAS: PROBLEMA DE ASIGNACIÓN
GENERALIZADA
Caso
Mejor respuesta
ACO
Iteraciones
conocida
A_5_100
1698
1698
18
B_10_200
2831
2831
62
C_10_200
2814
2814
141
D_10_200
12601
12634
521
Preguntas
Descargar

01_02_03 - Universitaria de Investigación y Desarrollo