Una Introducción a la Optimización Usando Algoritmos de Hormigas y sus Aplicaciones
Parte A
Jesús A. LópezUniversidad del ValleCali, Colombia
CIIC2007Universidad NacionalBogotá, ColombiaSeptiembre 5 – 7 de 2007
Agenda
� Introducción.� Inteligencia de Enjambres.� Algoritmos de Hormigas.� Algoritmos de hormigas para la solución de problemas de enrutamiento.
� Algoritmos de hormigas� Búsqueda de alimento � Optimización y enrutamiento� Agrupamiento y categorización� División de labores� Transporte cooperativo
Introducción (I)
La Inteligencia Artificial se divide en dos escuelas dependiendo de como se diseña un Agente Inteligente. La primera que se ha denominado Inteligencia Artificial Convencional y una emergente llamada Inteligencia Computacional
Inteligencia Artificial
Inteligencia Artificial Convencional
Inteligencia Computacional
Introducción (II)
Inteligencia Artificial Convencional
Búsquedas en Espacios de Estado Planeamiento Automático
Búsqueda Combinatoria Sistemas Expertos
Sistemas Basados en Comportamiento Redes Bayesianas
Inteligencia Computacional
Redes Neuronales Sistemas Difusos Computación Evolutiva
Introducción (III)
ComputaciónEvolutiva
AlgoritmosEvolutivos
Inteligenciade Enjambres
AlgoritmosGenéticos
EstrategiasEvolutivas
ProgramaciónGenética
ProgramaciónEvolutiva
Optimización porColonia deHormigas
Optimización porEnjambre dePartículas
Optimización porEnjambre deBacterias
Búsqueda por Difusión
Estocástica
Introducción (IV)
Inteligencia de Enjambres (I)
Una simple hormiga o abeja no es muy lista, pero sus colonias lo son. El estudio de la inteligencia de enjambres esta proporcionando ideas que pueden ayudar a los humanos a manejar sistemas complejos, desde enrutamiento de camiones hasta robots militares
� Técnicas computacionales que estudian el comportamiento colectivo en grupos descentralizados y autoorganizados
� Características:� No existe una estructura de control central
� No existe un modelo explicito del entorno
� Hay un método de percepción del entorno
� El agente puede realizar cambios sobre el entorno
Inteligencia de Enjambres (II)
Inteligencia de Enjambres (III)
Cualquier intento de desarrollar algoritmos y mecanismos de solución distribuida de un problema inspirados por el comportamiento colectivo de colonias de insectos sociales y otras sociedades de animales.
Bonabeau,Dorigo,Theraulaz, Swarm Intelligence, 1999
Algoritmo Basados en Colmenas de Abajes
� Algoritmos que imitan el comportamiento de las abejas en el proceso de búsqueda y recolección de Néctar. Básicamente realiza las siguientes funciones:� Distingue clases y categorías de individuos que conforman la colmena.
� Algunos agentes tienen la tarea de ubicar fuentes de alimento suficientemente provechosas e informar, en la colmena, a los otros individuos sobre la ubicación relativa de dicha fuente a través de “danzas”.
� Dependiendo de la duración de las danzas, indica la ubicación y provecho de la fuente.
Optimización de la función Peaks (I)
Optimización de la función Peaks (II)
Optimización por Enjambre de Partículas
� Desarrollada por J. Kennedy y R. Eberhart(1995)
� Basada en los movimientos de bandadas y cardúmenes
� Combina un modelo individual con un modelo social
( ) ( ) ( ) ( )idgdidididid xpRandcxprandctvwtv −⋅⋅+−⋅⋅+⋅=+
211
( ) ( ) ( )11 ++=+ tvtxtx idid
Optimización por Enjambre de Bacterias
( ) ( ) ( ) ( )tiCtt ii ψθθ ⋅+=+1
� Desarrollado por K. Passino(2000)
� Basado en el comportamiento Quimiotáctico de las bacterias
� Considera el espacio de búsqueda como un ambiente con concentraciones variables de nutrientes
Optimización por Enjambre de Bacterias
�Optimización de Funciones
-2
0
2
-2
0
2
-5
0
5
x
Peaks
y
Algoritmos Basados en Colonias de Hormigas
� Inicialmente desarrollados por M. Dorigo (1991)
� Basados en diferentes comportamientos observados en las colonias de hormigas:� Búsqueda de alimento� Organización de cadáveres� División de labores� Construcción de nidos
� Comunicación por estigmergia
� Estigmergia =Las acciones de un insecto son determinadas o influenciadas por las consecuencias de las acciones previas de los otros insectos.� Agrupación de los insectos muertos de la colonia� Construcción de nidos� Búsqueda de alimento
Estigmergia
Los algoritmos de hormigas están basados en comportamientos exhibidos por las hormigas reales:� Búsqueda de alimento � Optimización y enrutamiento� Agrupamiento y categorización� División de labores� Transporte cooperativo
Algoritmos de Hormigasde Hormigas
� Las hormigas son capaces de encontrar el camino más corto hasta donde está el alimento
� La clave esta en la ruta de feromonas que ellas dejan.
� La feromona en el camino mas corto se refuerza haciendo que más hormigas usen dicho camino.
� Luego de un tiempo las hormigas han definido una ruta a seguir
Cómo las Hormigas Buscan Alimento?
� El problema de los dos puentes
Cómo las Hormigas Buscan Alimento?
� Esto ayuda a descartar las fuentes de alimento menos adecuadas
Evaporación de Feromona
� La idea es usar una colonia de hormigas artificiales para resolver problemas de optimización.
Optimización Basada en Colonias de Hormigas (AntColony Optimization –ACO-)
� Las hormigas son depositadas randómicamenteen las diferentes ciudades.
� Cada hormiga busca una ruta usando una regla probabilística
� Cada hormiga va depositando feromona a medida que construye una ruta
� En los nuevos recorridos la regla probabilística que define las ciudades a visitar estáinfluenciada por la cantidad de feromona depositada
� Luego de un cierto número de iteraciones, una buena solución es encontrada
ACO para el Problema del Viajante
ACO para el Problema del Viajante
� Ejemplo básico
ACO para el Problema del Viajante
Otras Aplicaciones
� Tráfico en una red de comunicaciones
� Programación de trabajos
� Programación de rutas para vehículos
Otras Aplicaciones
� AntNet
Optimización de Funciones (I)
( ) ( ) ( ) 620sin30sin52.05.0 ++= − θθθ θθ
eeJ ( ) ( )2
2
221
2
1
4
1
2
12144
3
11.24, θθθθθθθθθ +−++
+−=J
CESIN SCB
Optimización de Funciones (II)
0 10 20 30 40 50 60 70 80 90 100-2
-1
0
1
2
Min
imum
and A
vera
ge C
ost
0 10 20 30 40 50 60 70 80 90 1000
0.5
1
1.5
Cost
Devia
tion
epochs
Costo Mínimo, Promedio y Desviación de la Población
Desplazamiento de los agentes sobre el espacio de
búsqueda
Optimización de Funciones (III)
� Comparación de diferentes técnicas
SCB
8.11E-03-1.0241-1.0316AACA
5.02E-04-1.0312-1.0316BSFO
1.48E-07-1.0316-1.0316PSO
σJavgJminAlgoritmo
CESIN
2.52E-021.33951.3286AACA
1.98E-011.43951.2693BSFO
6.68E-021.32431.2573PSO
σJavgJminAlgoritmo
Sintonización de un PID (I)
� Control de Temperatura en reactor de agitación continua
� Variable de entrada: Porcentaje de apertura de la válvula de vapor
� Disturbios: Flujo de sustancia y Temperatura de Sustancia
� Se considera la saturación de todas las variables y cuantificación en los niveles de apertura.
� Puntos de operación:� T = 65.5°C� Ti = 37.7 °C� F = 425 l/s
� Bajo las mismas condiciones de diseño, obtener un controlador con desempeño similar al obtenido con AG y CD.� Bajo esfuerzo de control� Buen rechazo a perturbaciones� Rápido establecimiento
Sintonización de un PID (II)
( ) ( ) ( ) ( ) ( )zEz
KzEzKzEKzU idp ⋅
−⋅+⋅−⋅+⋅= −
1
11
1
( ) ( )( ) ( ) ( )( )∑∑==
−−−
+−=N
k
N
k
kukuN
KkykrN
KJ1
2
2
0
2
11
1
11
Sintonización de un PID (III)
0 1000 2000 3000 4000 50000
50
100
Tiempo (min)
Tem
pera
tura
(°C
)0 1000 2000 3000 4000 5000
0
50
100
Tiempo (min)
Porc
enta
je d
e A
pert
ura
FUZZY PIDAG PIDPSO PIDBSFO PIDACO
MSE 2.23E+01 1.81E+01 1.74E+01 3.52E+01 1.63E+01
MTSE 8.46E+04 6.66E+04 6.80E+04 1.43E+05 6.00E+04
CAA 1.49E+02 1.49E+02 1.49E+02 1.49E+02 1.49E+02
CAS 2.45E+00 4.17E+00 3.73E+00 1.16E+00 5.32E+00
ACO
� Comparación de diferentes técnicas
Control Indirecto Adaptativo (I)
( )( )
( ) ( ) ( )( )111
1−−−
−= khkkr
kku α
β
� Control de Nivel en Tanque con sección variable
� Se usa un modelo estimado de la planta y un controlador por equivalencia
( ) ( )( ) ( )
( )tubtha
c
btha
tghd
dt
tdh
++
+
−=
2
Control Indirecto Adaptativo (II)
El sistema de identificación corresponde al algoritmo
de enjambres
0 10 20 30 40 50 60 70 80 90 1000
5
10
15
Liq
uid
heig
ht,
h
10 20 30 40 50 60 70 80 90 100-50
0
50
Time, k
Contr
ol A
ction,
u
Plataforma de Experimentación en un Sistema de TemperaturaMultizona
Cómo Controlar la Plataforma?
I1
I2
I16
Disturbios delAmbiente
S1
S2
S25
MODELO?CONTROL?
RESTRICCIONES?
Basada en Hormigas – Un Agente
Basada en Hormigas – Dos Agente
Basada en Hormigas – Cuatro Agentes
Algoritmo de Hormigas para Agrupamiento� Algunas especies de hormigas agrupan los cadáveres de las hormigas muertas
Aplicaciones
� Agrupamiento de objetos usando robots� Se recoge el objeto con una alta probabilidad si se perciben pocos objetos cerca
� Se deposita el objeto con alta probabilidad si se perciben muchos objetos cerca
División de Labores
� Unas de las claves del éxito de los insectos sociales es su especialización morfológica y funcional:� Las reinas son reproductoras
� Soldados y obreros estériles
� Obreros especializados en cuidad y alimentar las larvas
� Obreros especializados en buscar comida
� Soldados especializados en cuidar el nido
División de LaboresAsignación Adaptativa de Tareas ATAA
AL
GO
RIT
MO
AT
AA
Inicio
Aparece una tarea
a realizarse
Tarea X
Cubierta?
Agente
disponible?
NO
NO
Se decrementa la
demanda de XSI
FinSI
distancia = 0;
Distancia 0
X = X – 0;
X = X – ;
_X= X + ;NO
SI
NO
SI
Asignación Adaptativa de TareasEjemplo
Transporte Cooperativo
Emular el comportamiento de las hormigas para transportar cooperativamente objetos que están por encima de la capacidad de un individuo
Aplicaciones
�Transporte cooperativo en robótica
Algunos Enlaces
Ant Colony Optimization
http://www.aco-metaheuristic.org/
The Swarm-Intelligent Systems (SWIS)
http://swis.epfl.ch/
Swarm Intelligence resources
http://staff.washington.edu/paymana/swarm/
Ants Viewer 1.0
http://www.rennard.org/alife/english/antsgb.html
TSPLIB is a library of sample instances for the TSP
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
Generic simulated flocking creatures boids.
http://www.red3d.com/cwr/boids/
Design and implementation of self-organizing and self-assembling
artifacts.
http://www.swarm-bots.org/
Top Related