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/