M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos evolutivos. Inteligencia colectiva. A. Jim´enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

April 27, 2010

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Descripci´on

1

M´etodos evolutivos

2

Inteligencia colectiva

Algoritmos gen´eticos Colonias de hormigas Problema de agente viajero Clasificaci´ on

Enjambre de part´ıculas Problema de agente viajero

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Descripci´on

1

M´etodos evolutivos

2

Inteligencia colectiva

Algoritmos gen´eticos Colonias de hormigas Problema de agente viajero Clasificaci´ on

Enjambre de part´ıculas Problema de agente viajero

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Descripci´on

1

M´etodos evolutivos

2

Inteligencia colectiva

Algoritmos gen´eticos Colonias de hormigas Problema de agente viajero Clasificaci´ on

Enjambre de part´ıculas Problema de agente viajero

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Descripci´on

1

M´etodos evolutivos

2

Inteligencia colectiva

Algoritmos gen´eticos Colonias de hormigas Problema de agente viajero Clasificaci´ on

Enjambre de part´ıculas Problema de agente viajero

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Descripci´on

1

M´etodos evolutivos

2

Inteligencia colectiva

Algoritmos gen´eticos Colonias de hormigas Problema de agente viajero Clasificaci´ on

Enjambre de part´ıculas Problema de agente viajero

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Descripci´on

1

M´etodos evolutivos

2

Inteligencia colectiva

Algoritmos gen´eticos Colonias de hormigas Problema de agente viajero Clasificaci´ on

Enjambre de part´ıculas Problema de agente viajero

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Descripci´on

1

M´etodos evolutivos

2

Inteligencia colectiva

Algoritmos gen´eticos Colonias de hormigas Problema de agente viajero Clasificaci´ on

Enjambre de part´ıculas Problema de agente viajero

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Descripci´on

1

M´etodos evolutivos

2

Inteligencia colectiva

Algoritmos gen´eticos Colonias de hormigas Problema de agente viajero Clasificaci´ on

Enjambre de part´ıculas Problema de agente viajero

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

Algunos m´etodos de optimizaci´ on est´an basados en fen´omenos naturales: Enfriamiento de materiales Cristalizaci´on de materiales Evoluci´on (mutaci´ on, recombinaci´ on, selecci´ on) Sistemas competitivos / colaborativos Interacciones sociales

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

Algunos m´etodos de optimizaci´ on est´an basados en fen´omenos naturales: Enfriamiento de materiales Cristalizaci´on de materiales Evoluci´on (mutaci´ on, recombinaci´ on, selecci´ on) Sistemas competitivos / colaborativos Interacciones sociales

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

Algunos m´etodos de optimizaci´ on est´an basados en fen´omenos naturales: Enfriamiento de materiales Cristalizaci´on de materiales Evoluci´on (mutaci´ on, recombinaci´ on, selecci´ on) Sistemas competitivos / colaborativos Interacciones sociales

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

Algunos m´etodos de optimizaci´ on est´an basados en fen´omenos naturales: Enfriamiento de materiales Cristalizaci´on de materiales Evoluci´on (mutaci´ on, recombinaci´ on, selecci´ on) Sistemas competitivos / colaborativos Interacciones sociales

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

Algunos m´etodos de optimizaci´ on est´an basados en fen´omenos naturales: Enfriamiento de materiales Cristalizaci´on de materiales Evoluci´on (mutaci´ on, recombinaci´ on, selecci´ on) Sistemas competitivos / colaborativos Interacciones sociales

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

B´ usqueda tab´ u (1986) Random search (600 s) Simulated anealing (600 s) Algoritmos gen´eticos (1975) Redes neuronales

Ant colony optimization (desde 1992) Swarm optimization (desde 1995)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

B´ usqueda tab´ u (1986) Random search (600 s) Simulated anealing (600 s) Algoritmos gen´eticos (1975) Redes neuronales

Ant colony optimization (desde 1992) Swarm optimization (desde 1995)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

B´ usqueda tab´ u (1986) Random search (600 s) Simulated anealing (600 s) Algoritmos gen´eticos (1975) Redes neuronales

Ant colony optimization (desde 1992) Swarm optimization (desde 1995)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

B´ usqueda tab´ u (1986) Random search (600 s) Simulated anealing (600 s) Algoritmos gen´eticos (1975) Redes neuronales

Ant colony optimization (desde 1992) Swarm optimization (desde 1995)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

B´ usqueda tab´ u (1986) Random search (600 s) Simulated anealing (600 s) Algoritmos gen´eticos (1975) Redes neuronales

Ant colony optimization (desde 1992) Swarm optimization (desde 1995)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

B´ usqueda tab´ u (1986) Random search (600 s) Simulated anealing (600 s) Algoritmos gen´eticos (1975) Redes neuronales

Ant colony optimization (desde 1992) Swarm optimization (desde 1995)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

M´etodos de optimizaci´on

B´ usqueda tab´ u (1986) Random search (600 s) Simulated anealing (600 s) Algoritmos gen´eticos (1975) Redes neuronales

Ant colony optimization (desde 1992) Swarm optimization (desde 1995)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

M´etodos evolutivos

Los m´etodos evolutivos est´an basados en poblaciones de soluciones. A diferencia de los m´etodos cl´asicos de mejora basados en seguimiento de trayectorias, en cada iteraci´ on del algoritmo no se tiene una u ´nica soluci´on sino un conjunto de ´estas. Estos m´etodos se basan en generar, seleccionar, combinar y reemplazar un conjunto de soluciones.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

M´etodos evolutivos

Dado que mantienen y manipulan un conjunto en lugar de una u ´nica soluci´on a lo largo de todo el proceso de b´ usqueda suelen presentar tiempos de computaci´ on sensiblemente m´as altos que los de otros m´etodos. Este hecho se puede verse empeorado si la convergencia de la poblaci´on requiere de un gran n´ umero de iteraciones.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

Estructura de un algoritmo evolutivo

1 2 3 4 5 6 7 8 9 10

t = 0; inicializar [P (t)]; evaluar [P (t)]; while no terminar do t = t + 1; seleccionar P (t) de P (t − 1); alterar P (t); evaluar P (t); P 0 (t) = mutacion[P 0 (t)]; evaluar[P 0 (t)];

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

Introducci´on

Entre los m´etodos evolutivos podemos encontrar 1

Algoritmos gen´eticos

2

B´ usqueda dispersa

3

Reencadenamiento de trayectorias

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

Introducci´on

Entre los m´etodos evolutivos podemos encontrar 1

Algoritmos gen´eticos

2

B´ usqueda dispersa

3

Reencadenamiento de trayectorias

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

Introducci´on

Entre los m´etodos evolutivos podemos encontrar 1

Algoritmos gen´eticos

2

B´ usqueda dispersa

3

Reencadenamiento de trayectorias

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

Algoritmos gen´eticos (AG)

Los algoritmos gen´eticos (AG) fueron introducidos por John Holland (1975) inspir´andose en el proceso observado en la evoluci´on natural de los seres vivos. B´asicamente, los AG imitan el proceso de evoluci´ on natural, el principal mecanismo que gu´ıa la aparici´ on de estructuras org´anicas complejas y bien adaptadas.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: producto de evoluci´on

La evoluci´on es el resultado de las relaciones entre la creaci´on de nueva informaci´on gen´etica y los procesos de evaluaci´on + selecci´on. Es la soluci´on al problema que cada individuo se enfrenta cada d´ıa mediante la supervivencia. Cada individuo en una poblaci´ on se ve afectado por el resto de individuos (compitiendo por recursos, emparej´andose para procrear, huyendo de los depredadores, ...) y tambi´en por el entorno (disponibilidad de comida, clima, ...).

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: producto de evoluci´on

Los individuos mejor adaptados son los que tienen mayores posibilidades de vivir m´as tiempo y reproducirse, generando as´ı una progenie con su informaci´ on gen´etica (posiblemente modificada).

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: producto de evoluci´on

A nivel de los genes, el problema de la supervivencia es el de buscar aquellas adaptaciones beneficiosas en un medio hostil y cambiante. Debido en parte a la selecci´ on natural, cada especie gana una cierta cantidad de conocimiento, el cual es incorporado a la informaci´on de sus cromosomas.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: producto de evoluci´on

En el transcurso de la evoluci´ on se generan poblaciones sucesivas con informaci´on gen´etica de los individuos cuya adecuaci´on es superior a la de la media. La naturaleza no determinista de la reproducci´ on provoca una creaci´on permanente de informaci´ on gen´etica nueva, y por tanto la aparici´on de distintos individuos.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: producto de evoluci´on

As´ı pues, la evoluci´on tiene lugar en los cromosomas, en donde est´e codificada la informaci´ on del ser vivo. La informaci´on almacenada en el cromosoma var´ıa de unas generaciones a otras. En el proceso de formaci´ on de un nuevo individuo, se combina la informaci´on cromos´omica de los progenitores.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG

Este modelo neo Darwiniano de la evoluci´ on org´anica se refleja en la estructura de un algoritmo gen´etico. As´ı, los algoritmos gen´eticos establecen una analog´ıa entre el conjunto de soluciones de un problema y el conjunto de individuos de una poblaci´on natural, codificando la informaci´on de cada soluci´on en una cadena (vector binario) a modo de cromosoma.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG

Este cromosoma (´ unico o m´ ultiple) forma junto con su aptitud un individuo sobre el que el algoritmo aplica sus operaciones. En palabras del propio Holland: Se pueden encontrar soluciones aproximadas a problemas de gran complejidad computacional mediante un proceso de evoluci´on simulada

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: ideas fundamentales

Los AG est´an basados en integrar e implementar eficientemente dos ideas fundamentales: Las representaciones simples (genotipos, tales como los vectores binarios) de las soluciones del problema La realizaci´on de transformaciones simples para modificar y mejorar estas representaciones

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: elementos

Para llevar a la pr´actica el esquema anterior y concretarlo en un algoritmo, hay que especificar los siguientes elementos: Una representaci´on cromos´ omica (genotipo) Una poblaci´on inicial Una medida de evaluaci´ on (fitness o adecuaci´on) Un criterio de selecci´ on / reemplazo de individuos Una o varias operaciones de recombinaci´ on Una o varias operaciones de mutaci´ on

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: elementos

Para llevar a la pr´actica el esquema anterior y concretarlo en un algoritmo, hay que especificar los siguientes elementos: Una representaci´on cromos´ omica (genotipo) Una poblaci´on inicial Una medida de evaluaci´ on (fitness o adecuaci´on) Un criterio de selecci´ on / reemplazo de individuos Una o varias operaciones de recombinaci´ on Una o varias operaciones de mutaci´ on

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: elementos

Para llevar a la pr´actica el esquema anterior y concretarlo en un algoritmo, hay que especificar los siguientes elementos: Una representaci´on cromos´ omica (genotipo) Una poblaci´on inicial Una medida de evaluaci´ on (fitness o adecuaci´on) Un criterio de selecci´ on / reemplazo de individuos Una o varias operaciones de recombinaci´ on Una o varias operaciones de mutaci´ on

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: elementos

Para llevar a la pr´actica el esquema anterior y concretarlo en un algoritmo, hay que especificar los siguientes elementos: Una representaci´on cromos´ omica (genotipo) Una poblaci´on inicial Una medida de evaluaci´ on (fitness o adecuaci´on) Un criterio de selecci´ on / reemplazo de individuos Una o varias operaciones de recombinaci´ on Una o varias operaciones de mutaci´ on

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: elementos

Para llevar a la pr´actica el esquema anterior y concretarlo en un algoritmo, hay que especificar los siguientes elementos: Una representaci´on cromos´ omica (genotipo) Una poblaci´on inicial Una medida de evaluaci´ on (fitness o adecuaci´on) Un criterio de selecci´ on / reemplazo de individuos Una o varias operaciones de recombinaci´ on Una o varias operaciones de mutaci´ on

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: elementos

Para llevar a la pr´actica el esquema anterior y concretarlo en un algoritmo, hay que especificar los siguientes elementos: Una representaci´on cromos´ omica (genotipo) Una poblaci´on inicial Una medida de evaluaci´ on (fitness o adecuaci´on) Un criterio de selecci´ on / reemplazo de individuos Una o varias operaciones de recombinaci´ on Una o varias operaciones de mutaci´ on

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: etapas

Podemos observar que se trata de un algoritmo en el que es posible distinguir las tres etapas cl´asicas (Wah y Chang, 1997): Generaci´on de la muestra inicial Paso de optimizaci´ on Comprobaci´on de la condici´ on de parada

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: etapas

Podemos observar que se trata de un algoritmo en el que es posible distinguir las tres etapas cl´asicas (Wah y Chang, 1997): Generaci´on de la muestra inicial Paso de optimizaci´ on Comprobaci´on de la condici´ on de parada

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: etapas

Podemos observar que se trata de un algoritmo en el que es posible distinguir las tres etapas cl´asicas (Wah y Chang, 1997): Generaci´on de la muestra inicial Paso de optimizaci´ on Comprobaci´on de la condici´ on de parada

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

Algoritmo

1 2 3 4 5 6 7 8 9 10

t = 0; inicializar [P (t)]; evaluar [P (t)]; while no terminar do P 0 (t) = seleccionpareja [P (t)]; P 0 (t) = recombinacion [P 0 (t)]; P 0 (t) = mutacion [P 0 (t)]; evaluar [P 0 (t)] ; P (t + 1) = seleccionentorno [P 0 (t) ∪ P (t)] ; t=t+1 ;

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: algoritmo

En el algoritmo anterior, P (t) denota una poblaci´ on de µ individuos en la generaci´ on t. La poblaci´on inicial suele ser generada de forma aleatoria (restringi´endose a soluciones que sean factibles).

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: algoritmo

El algoritmo genera una nueva poblaci´ on P 0 (t) de λ individuos aplicando a P (t) un conjunto de operadores de variaci´on. T´ıpicamente dichos operadores son la selecci´ on y recombinaci´on de parejas junto con la mutaci´ on de los nuevos individuos generados.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: evaluaci´on

La evaluaci´on sirve para asociar un valor de calidad, calculado por la funci´on objetivo f (xk ), para cada soluci´ on xk representada por el individuo k−´esimo de P 0 (t), k = 1, ..., λ. Aunque se suele utilizar la calidad como medida de la bondad seg´ un el valor de la funci´ on objetivo, se puede a˜ nadir un factor de penalizaci´on para controlar la infactibilidad en algunos problemas.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: etapas de selecci´on

El proceso de selecci´on en un AG consta de dos etapas: 1

Decidir qui´enes compiten por la reproducci´ on (emparejamiento)

2

Decidir cu´ales de entre todos los individuos (nuevos y viejos) van a sobrevivir

Simulando as´ı el proceso de selecci´ on del entorno (o ambiental).

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: etapas de selecci´on

El proceso de selecci´on en un AG consta de dos etapas: 1

Decidir qui´enes compiten por la reproducci´ on (emparejamiento)

2

Decidir cu´ales de entre todos los individuos (nuevos y viejos) van a sobrevivir

Simulando as´ı el proceso de selecci´ on del entorno (o ambiental).

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: reemplazo

El reemplazo es elitista, de forma que se asegura la conservaci´on de las k mejores soluciones presentes en la poblaci´on actual cuando se va a generar la siguiente poblaci´ on. Se distingue entre t´ecnicas que usan la poblaci´ on actual de µ individuos m´as la nueva de λ individuos para generar la pr´oxima poblaci´on -algoritmos (µ + λ)- y las que usan los λ nuevos individuos para reemplazar a los µ individuos antiguos -algoritmos (µ, λ)-.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: recombinaci´on

En general, un algoritmo gen´etico es un metaheur´ıstico poblacional en donde se pueden mezclar las ideas de combinaci´on de bloques de construcci´on b´asicos con la modificaci´ on de bloques parcialmente u ´tiles, para avanzar hacia la regi´ on m´as prometedora de la b´ usqueda.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: recombinaci´on

Los operadores de recombinaci´ on se aplican con alta probabilidad y usualmente han utilizado uno o varios puntos de cruce en los individuos para intercambiar las porciones resultantes entre los dos padres. Tambi´en existen variantes que consideran m´as de dos padres en el proceso de recombinaci´ on.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: recombinaci´on Algunos de los operadores de recombinaci´ on mas utilizados son: De un punto: Se elige aleatoriamente un punto de ruptura en los padres y se intercambian sus bits. De 2 puntos: Se eligen dos puntos de ruptura al azar para intercambiar. Uniforme: En cada bit se elige al azar un padre para que contribuya con su bit al del hijo, mientras que el segundo hijo recibe el bit del otro padre. Las mutaciones m´as comunes son las que modifican un bit aleatoriamente (bit flip) a baja probabilidad, o las que utilizan un ruido con distribuci´on normal, en el caso de genotipos flotantes.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: recombinaci´on Algunos de los operadores de recombinaci´ on mas utilizados son: De un punto: Se elige aleatoriamente un punto de ruptura en los padres y se intercambian sus bits. De 2 puntos: Se eligen dos puntos de ruptura al azar para intercambiar. Uniforme: En cada bit se elige al azar un padre para que contribuya con su bit al del hijo, mientras que el segundo hijo recibe el bit del otro padre. Las mutaciones m´as comunes son las que modifican un bit aleatoriamente (bit flip) a baja probabilidad, o las que utilizan un ruido con distribuci´on normal, en el caso de genotipos flotantes.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: recombinaci´on Algunos de los operadores de recombinaci´ on mas utilizados son: De un punto: Se elige aleatoriamente un punto de ruptura en los padres y se intercambian sus bits. De 2 puntos: Se eligen dos puntos de ruptura al azar para intercambiar. Uniforme: En cada bit se elige al azar un padre para que contribuya con su bit al del hijo, mientras que el segundo hijo recibe el bit del otro padre. Las mutaciones m´as comunes son las que modifican un bit aleatoriamente (bit flip) a baja probabilidad, o las que utilizan un ruido con distribuci´on normal, en el caso de genotipos flotantes.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Algoritmos gen´ eticos

AG: convergencia

Dado que el algoritmo gen´etico opera con una poblaci´on en cada iteraci´on, se espera que el m´etodo converja de modo que al final del proceso la poblaci´on sea muy similar, y en el infinito se reduzca a un s´olo individuo.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: definici´on

Desde el punto de vista de la sociolog´ıa Definici´on Es una forma de inteligencia universalmente distribuida, constantemente realzada, coordinada en tiempo real, y resultando en la movilizaci´on efectiva de habilidades. La base y meta de inteligencia colectiva es el reconocimiento mutuo y enriquecimiento de individuos.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: definici´on

Definici´on Grupos de individuos que hacen cosas que parecen colectivamente inteligentes Donde: Colectivo: algo que incluye m´ ultiples entidades que interaccionan Inteligente: Inform´atica: pasa el test de Turing Psicolog´ıa: habilidad para planificar, resolver problemas, pensar de forma abstracta, aprender.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: definici´on

Definici´on Grupos de individuos que hacen cosas que parecen colectivamente inteligentes Donde: Colectivo: algo que incluye m´ ultiples entidades que interaccionan Inteligente: Inform´atica: pasa el test de Turing Psicolog´ıa: habilidad para planificar, resolver problemas, pensar de forma abstracta, aprender.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: definici´on

Observaciones: La complejidad y sofisticaci´ on de la auto-organizaci´on se lleva a cabo sin un lider/jefe de la sociedad Lo que podemos aprender de los insectos sociales lo podemos aplicar al campo del dise˜ no de Sistemas Inteligentes La modelizaci´on de los insectos sociales por medio de la auto-organizaci´on puede ser de ayuda para el dise˜ no de modelos artificiales distribuidos de resoluci´ on de problemas.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: definici´on

Dado que no existe un conjunto de instrucciones sobre c´omo act´ uan estas unidades, la interacci´ on colectiva de los agentes dentro del sistema a menudo conduce a alg´ un tipo de comportamiento colectivo o de inteligencia.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Caracter´ısticas de un enjambre Compuesto de agentes simples (Self-Organized) Descentralizado No hay un u ´nico supervisor No hay un plan global (emergente) Robusto Las actuaciones se completan aunque un individuo falle Flexible Puede responder a cambios externos Percepci´on del entorno (sentidos) No existe un modelo expl´ıcito de entorno/habilidad para cambiarlo A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva

Este tipo de inteligencia artificial se utiliza para explorar. Distribuye la soluci´on de problemas sin tener una estructura de control centralizado. Esto se ve como una mejor alternativa a la centralizada, r´ıgida y de control preprogramado.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Ejemplos de Inteligencia colectiva

Consideraciones: Los individuos de la poblaci´ on interact´ uan de forma social Las decisiones de cada individuo dependen del propio querer y la informaci´on disponible de (algunos de) los dem´as Se ha estudiado varios tipos: Insectos (abejas, termitas, hormigas) Enjambre de part´ıculas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Insectos

Llevan a cabo actuaciones colectivas que no ser´ıan posibles para un u ´nico individuo El repertorio de comportamientos de cada insecto es limitado No existe acceso individual al estado completo de la colonia No pueden hacer una divisi´ on efectiva de la labor a realizar No pueden garantizar el progreso de la colonia

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Insectos: Comportamiento emergente

Las colonias de insectos llevan a cabo actuaciones de nivel complejo de forma inteligente, flexible y fiable, actuaciones que no ser´ıan factibles si tuviesen que ser realizadas por un insecto de forma individual (´estos son no inteligentes, no fiables, simples). Los insectos siguen reglas simples, y utilizan comunicaci´on local simple La estructura global (nido) emerge desde las acciones de los insectos (las cuales son no fiables atendidas individualmente)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Abejas

Cooperaci´on de la colmena Regulan la temperatura de la colmena Eficiencia v´ıa especializaci´ on: divisi´ on de la labor en la colonia Comunicaci´on: Las fuentes de comida son explotadas de acuerdo a la calidad y distancia desde la colmena

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Abejas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Termitas

Nido con forma de cono con paredes externas y conductos de ventilaci´on C´amaras de camadas en el centro de la colmena Rejillas del ventilaci´ on en espirales Columnas de soporte

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Termitas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Hormigas

Organizan autopistas hacia y desde la comida por medio de rastros de feromona

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Hormigas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas

El comportamiento de las colonias de hormigas ha sido uno de los m´as populares de los modelos de comportamiento de enjambre.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas

A trav´es de inteligencia colectiva, las hormigas pueden Determinar el camino m´as corto a una fuente de alimentos. Alimentar a toda la colonia. Construir grandes estructuras. Adaptarse a las situaciones (entorno).

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas

Caracter´ısticas principales: Los individuos dejan rastros (feromonas) en el espacio de b´ usqueda. Desarrollan caminos m´ınimos entre la comida y el hormiguero. Las decisiones se basan en una informaci´ on individual y de las feromonas encontradas. La informaci´on (feromonas) es vol´atil. Las feromonas o el compartamiento estad´ıstico de los individuos define la soluci´ on.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas (PAV) Premisa: Las hormigas prefieren aleatoriamente ciudades conectadas por aristas con alto nivel de feromonas y que sean cercanas. 1

Se colocan m hormigas artificiales en n ciudades aleatorias

2

En cada instante cada hormiga se mueve hacia una nueva ciudad y modifica el nivel de feromonas de la arista. Las feromonas se evaporan.

3

Cuando todas terminan, la hormiga que ha realizado el camino m´as corto modifica las aristas que ha recorrido depositando un nivel de feromona inversamente proporcional a la longitud del camino recorrido. El camino m´as corto recibe m´as feromonas.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas (PAV)

Para cada hormiga, pasar de la ciudad i a la ciudad j en la iteraci´on t del algoritmo depende de: Para cada hormiga se maneja una lista de memoria (lista tab´ u) que aumenta con el tour que realiza. Con ´esta se define para cada hormiga k el conjunto Jik de ciudades que ha visitado cuando est´a en la ciudad i. Se busca que una hormiga evite visitar una ciudad mas de una vez.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas (PAV)

La inversa de la distancia ηij =

1 dij

se llamar´a visibilidad.

Est´a basada en informaci´ on local y representa el deseo de escoger la ciudad j cuando se est´a en la ciudad i. Puede ser usada para dirigir la b´ usqueda de la hormiga. La informaci´on ser´a est´atica, no variar´a durante la soluci´on del problema.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas (PAV)

La cantidad del rastro de feromona virtual τij (t) en el camino que une la ciudad i con la j. Se modifica constantemente y representa el deseo aprendido de ir hacia j cuando se esta en i. Opuesto a la distancia, el rastro de feromona es un tipo de informaci´on global. Su modificaci´ on representa el conocimiento adquirido.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Inteligencia colectiva: Colonia de hormigas (PAV)

La regla de transici´on es la probabilidad de que la hormiga k vaya desde la ciudad i a la ciudad j mientras construye su t-´esimo tour, Es dada por: [τij (t)]α · [ηij ]β pkij (t) = P α β l∈J k [τil (t)] · [ηil ] i

Jjk

Jjk

y 0 si j ∈ / donde α y β son dos par´ametros ajustables Si j ∈ que controlan el peso relativo de la intensidad del rastro y la visibilidad.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Algoritmo para PAV con Colonia de hormigas

1 2 3 4 5 6 7 8 9 10 11

for cada nodo (i, j) do τij = τ0 ; end for k = 1 to m do Ubicar la hormiga k en una ciudad de forma aleatoria; end + T = menor tour encontrado; L+ = longitud de T + ; for t = 1 to tmax do for k = 1 to m do Construir el tour T k (t) aplicando n1 veces el siguiente paso, Escoger la pr´ oxima ciudad j con la [τij (t)]α · [ηij ]β probabilidad, pk donde i es la ciudad actual ij (t) = P α β k [τil (t)] · [ηil ] l∈J

12

i

Iteraciones de actualizaci´ on

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Algoritmo para PAV con Colonia de hormigas

1 2 3 4 5 6 7 8 9 10

Iteraciones de actualizaci´ on; for k = 1 to m do Calcular la longitud Lk (t) del tour T k (t) producido por la hormiga k if se encuentra una mejora al tour then Actualizar T + y L+ for cada nodo (i, j) do e Actualizar el rastro de feromona aplicando la regla: τij = (1 − ρ) · τij (t) + ∆τij (t) + e · ∆τij (t) for cada nodo (i, j) do τij (t + 1) = τij (t) Print: El menor tour es T + con longitud L+

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Algoritmo para PAV con Colonia de hormigas En el algoritmo anterior se utiliz´ o: ∆τij (t) =

m X

∆τijk (t),

k=1

∆τijk (t) = Q/Lk (t) si (i, j) ∈ T k (t) ´o 0 de otro modo y ∆τije (t) = Q/L+ si (i, j) ∈ T + ´o 0 de otro modo Adem´as, los valores de los par´ametros usados son: α = 1, β = 5, ρ = 0.5, m = n, Q = 100, τ0 = 10−6 , e = 5 A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

El objetivo de la clasificaci´ on es hallar grupos homog´eneos de objetos, tal que los objetos similares pertenezcan a una misma clase y sea posible distinguir objetos de distintas clases. El criterio com´ unmente utilizado es el de minimizar la inercia intraclase W . Minimizar W es equivalente a maximizar la inercia interclases B, la suma W + B es la inercia total.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Las colonias de hormigas trabajan con una poblaci´on de M hormigas, cada una asociada a una partici´ on inicial la cual es cambiada mediante el algoritmo usado. La feromona τij entre entre los objetos i, j se aumenta con valores proporcionales a B, en el caso de objetos asociados a una misma clase; la visibilidad β es el inverso multiplicativo de la distancia entre los objetos. Se define una probabilidad p de que un objeto sea transferido a la misma clase de un objeto dado.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Algoritmo para Clasificaci´on con Colonia de hormigas

1 2 3 4 5 6 7 8 9 10

Inicializar M , max iter, τ0 , visibilidad, probabilidad; Inicializar las particiones P1 ,...,PM al azar; Aplicar kmeans en cada Pm a fin de buscar la convergencia a un m´ınimo de W ; for t = 1 to max iter do for m = 1 to M , S veces do escoger al azar un objeto i; escoger un objeto j de acuerdo a la probabilidad pij ; asignar j a la clase de i ; Calcular B(P1 ),...,B(PM ), guardar el mejor valor; Actualizar feromona;

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Se cuenta con 8 paquetes de archivos, cada paquete consta de un archivo de definiciones (.def), un archivo de pesos (.Pes), un archivo de datos (.dat) y un archivo de etiquetas (.Eti). Todos comparten el mismo nombre con la diferencia en su contenido y extensi´on. El formato (patr´ on) del nombre de estos archivos es el siguiente: ABCDEFGHIJKLMN OPQ.*

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Donde, AB: corresponde a las iniciales del nombre de la persona que gener´o el archivo, en este caso AB = ap CDEF: corresponde a la cantidad de individuos utilizados, n. En este caso CDEF = 0105 GH: corresponde a ci si las cardinalidades de las clases son iguales o cd si las cardinalidades de las clases son distintas IJ: indica la cantidad de clases k (ej. si k = 3, IJ=03; si k = 7 IJ=07)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

KL: corresponde a la varianza, ser´a oi si las varianzas son iguales o bien od si las varianzas son distintas MN: corresponde a la cantidad de las variables p, para todos los archivos generados en este caso MN=06 OPQ: indica el n´ umero de experimento que se realiza, en todos los archivos generados en este caso OPQ=e01

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

La siguiente tabla muestra las caracter´ısticas consideradas para la creaci´on de los archivos de definiciones (.def) Archivo .def

Indiv. n

Vbles. p

Clases k

Vza. σ = 1,σ = 3

Cardin. c1 , c2 , ..., ck

ap0105cd03od06 e01 ap0105cd03oi06 e01 ap0105ci03od06 e01 ap0105ci03oi06 e01 ap0105cd07od06 e01 ap0105cd07oi06 e01 ap0105ci07od06 e01 ap0105ci07oi06 e01

105 105 105 105 105 105 105 105

6 6 6 6 6 6 6 6

3 3 3 3 7 7 7 7

v1 = v3 = 1, v2 = 3 v1 = v2 = v3 = 1 v1 = v3 = 1, v2 = 3 v1 = v2 = v3 = 1 v1 , v3 , ..., v7 = 1, v2 = 3 v1 = v2 = v3 = ... = v7 = 1 v1 , v3 , ..., v7 = 1, v2 = 3 v1 = v2 = v3 = ... = v7 = 1

51, 27, 27 51, 27, 27 35, 35, 35 35, 35, 35 51,9,9,9,9,9,9 51,9,9,9,9,9,9 15,15,15,15,15,15,15 15,15,15,15,15,15,15

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Se tienen las siguientes consideraciones: Cantidad de clases (k): Las clases se denotan c1 , c2 , ..., ck . Se utilizaron dos cantidades de clases, previamente asignadas, k=3yk=7 Varianza intraclases: la varianza se utiliz´ o igual en todas las clases (σ = 1) o distinta en una de ellas (σ = 3). En el caso en el que la varianza era distinta, se indic´ o en la segunda clase, tal que v1 = v3 = ... = vk = 1 y v2 = 3

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Cantidad de individuos (n): la cantidad de individuos asignada es n = 105. Esta cantidad fue distribuida en el k X n´ umero clases utilizadas, tal que ci = n i=1

Cardinalidades: las clases se construyeron con cardinalidades iguales, y con una clase de cardinalidad distinta a las dem´as. Si las cardinalidades se desea sean distintas, la forma de distribuirlas debe ser asignando a la primera clase n/2 (parte entera) de los individuos y la otra mitad distribuirla en partes iguales entre las dem´as clases.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on

La clasificaci´on de los datos se realiz´ o con el m´etodo Colonia de Hormigas implementado en el programa ESTOP, utilizando el comando Clasificaci´on Num´erica>Hormigas. Luego de realizar la clasificaci´ on, los archivos resultantes deben ser analizados mediante el comando An´alisis de resultados>Reporte entre un mismo m´etodo.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Se realizaron las clasificaciones en el programa ESTOP 0.7 y se analizaron los resultados en ESTOP-Mayra

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Se tienen ocho grupos de par´ametros todos con los valores en com´ un max iter = 25, M = 105, τ0 = 0.001, q = 0.95 y S = 3; todos con las combinaciones de los valores ρ = 0.9 ´o ρ = 0.7, β = 0.7 ´o β = 0.3 y α = 0.9 ´ o α = 0.7.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas Estas variaciones se describen a continuaci´ on: Grupo 1 2 3 4 5 6 7 8

α 0.9 0.9 0.9 0.9 0.7 0.7 0.7 0.7

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

ρ 0.9 0.9 0.7 0.7 0.9 0.9 0.7 0.7

β 0.3 0.7 0.3 0.7 0.3 0.7 0.3 0.7

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Archivos ap0105cd03od06: Cardinalidades distintas en las 3 clases y varianzas distintas. Los valores obtenidos para todos ˆ = 12.769 y W ∗ = 11.734 los grupos de par´ametros son W con una tasa de atracci´ on del 100% Archivos ap0105cd03oi06: Cardinalidades distintas en las 3 clases y varianzas iguales. Se obtuvo, para todos los grupos de ˆ = 5.007 y W ∗ = 5.007 con una tasa de par´ametros W atracci´on del 100%

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Archivos ap0105ci03od06: Cardinalidades iguales en las 3 clases y varianzas distintas. Los valores obtenidos para todos ˆ = 14.333 y W ∗ = 13.15 con los grupos de par´ametros son W una tasa de atracci´ on del 100% Archivos ap0105ci03oi06: Cardinalidades iguales en las 3 clases y varianzas iguales. Los valores obtenidos para todos ˆ = 5.422 y W ∗ = 5.422 con los grupos de par´ametros son W una tasa de atracci´ on del 100%

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas Archivos ap0105cd07od06: Cardinalidades distintas en las 7 clases y varianzas distintas. Se obtuvo, para todos los grupos ˆ = 8.141 y W ∗ = 7.625 con una tasa de de par´ametros W atracci´on del 100% Archivos ap0105cd07oi06: Cardinalidades distintas en las 7 clases y varianzas iguales. Se obtuvo, para todos los grupos de ˆ = 5.545 y W ∗ = 5.545 con una tasa de par´ametros W atracci´on del 93% para el grupo 1, de un 88% para el grupo 2, de un 86% para el grupo 3, de un 86 % para el grupo 4, un 93% para el grupo 5, un 87% para el grupo 6, un 88% para el grupo 7 y un 89% para el grupo 8.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Archivos ap0105ci07od06: Cardinalidades iguales en las 7 clases y varianzas distintas. Se obtuvo, para todos los grupos ˆ = 11.305 y W ∗ = 9.895 con una tasa de de par´ametros W atracci´on del 100% Archivos ap0105ci07oi06: Cardinalidades iguales en las 7 clases y varianzas iguales. Los valores obtenidos para todos ˆ = 5.202 y W ∗ = 5.146 con los grupos de par´ametros son W una tasa de atracci´ on del 100%

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Varianza Igual Cardinalidad Igual Distinta

n 105 105 105 105

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

k 3 7 3 7

ˆ W 5.422 11.305 5.007 5.545

W∗ 5.422 9.895 5.007 5.545

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Varianza Distinta Cardinalidad Igual Distinta

n 105 105 105 105

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

k 3 7 3 7

ˆ W 14.333 5.202 12.769 8.141

W∗ 13.15 5.146 11.734 7.625

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

Conclusiones: El m´etodo Colonia de Hormigas realiz´ o una exitosa clasificaci´on de los datos. Esto se puede observar en el porcentaje obtenido en la mayor´ıa de los casos (100 %).

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

En el caso de clasificaci´ on de 105 individuos en 7 grupos con cardinalidades distintas con igual varianza, se obtuvo la mayor tasa de atracci´on con el grupo 1 y el grupo 5 de par´ametros, los cuales coinciden en el valor de la visibilidad (0.3) y tasa de evaporaci´on (0.9), variando en la potencia del trazo(0.9 y 0.7 respectivamente); la menor tasa se obtuvo con el grupo 3 y el grupo 4, los cuales tienen el mismo valor de la potencia del trazo (0.9) as´ı como el mismo valor de tasa de evaporaci´on (0.7) y difieren en el valor de la visibilidad (0.3 y 0.7). Comparando estos grupos, seg´ un los resultados obtenidos se puede concluir que un valor mayor en la tasa de evaporaci´on afecta positivamente la correcta clasificaci´ on de datos.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

Colonia de hormigas PAV con Colonias de hormigas Clasificaci´ on, Colonias de Hormigas

Clasificaci´on mediante Colonias de Hormigas

El trabajo para la creaci´ on de las tablas es necesario para asegurar los resultados y sustentar las conclusiones. Es necesario realizar una comparaci´ on con clasificaciones realizadas en conjuntos de mayor cardinalidad, ya que el que se obtengan estos resultados en conjuntos de 105 objetos no es suficiente para asegurar que la escogencia de los par´ametros afecta la efectividad del m´etodo.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

Los enjambres de part´ıculas son un tipo de inteligencia de enjambre inspirado por bandadas de aves y card´ umenes. Este tipo de enjambre de optimizaci´ on tiene agentes individuales dentro del enjambre con la capacidad de cambiar su posici´on en funci´on de su propia inteligencia.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

Esto permite que agentes individuales modifiquen sus rutas en funci´on del ´exito de los otros agentes en la poblaci´on, para encontrar la soluci´on correcta. Este tipo de enjambre de inteligencia se utiliza en aplicaciones pr´acticas como en redes neuronales artificiales y la evoluci´on en los modelos gramaticales.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

Metaheur´ıstica desarrollada por Kennedy y Eberhart. Tal comportamiento social se basa en la transmisi´ on del suceso de cada individuo a los dem´as individuos del grupo, lo cual resulta en un proceso sinerg´etico que permite a los individuos satisfacer, de la mejor manera posible, sus necesidades m´as inmediatas, tales como la localizaci´on de alimentos o de un lugar de cobijo.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

Ha mostrado ser muy eficiente para resolver problemas de optimizaci´on de un s´olo objetivo con r´apidas tasas de convergencia, haciendo atractiva la idea de su aplicaci´on en la resoluci´on problemas de optimizaci´ on de m´ ultiples objetivos. Consiste en un algoritmo iterativo basado en una poblaci´on de individuos denominada enjambre, en la que cada individuo, llamado part´ıcula, se dice que sobrevuela el espacio de decisi´on en busca de soluciones ´optimas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

As´ı, dado un espacio de decisi´ on N −dimensional, cada part´ıcula i del enjambre conoce: Posici´on actual Xi = [xi1 , xi2 , ..., xiN ]. Velocidad Vi = [vi1 , vi2 , ..., viN ] con la cual ha llegado a dicha posici´on. Mejor posici´on P i = [pi1 , pi2 , ..., piN ] en la que se ha encontrado, denominada mejor posici´ on personal. Adem´as, todas las part´ıculas conocen la mejor posici´on encontrada dentro del enjambre G = [g1 , g2 , ..., gN ],denominada mejor global.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

Existe otra variante en la que se definen sobre el enjambre subgrupos de part´ıculas, posiblemente solapados, a los que se denominan vecindades. En tal caso las part´ıculas tambi´en conocen la mejor posici´on encontrada dentro de su vecindad Li = [li1 , li2 , ..., liN ], a la que se denomina mejor local.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

Suponiendo el uso de la informaci´ on proveniente del mejor global, en cada iteraci´on t del algoritmo, cada componente j de la velocidad y la posici´on de cada part´ıcula i del enjambre se actualiza conforme a: t+1 t +C1 ×rand()×(ptij −xtij )+C2 ×rand()×(gjt −xtij ) vij = $ ×vij

con t+1 t xt+1 ij = xij + vij

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

Donde $ es el par´ametro de inercia que regula el impacto de las velocidades anteriores en la nueva velocidad de la part´ıcula, C1 es el par´ametro cognitivo que indica la influencia m´axima de la mejor experiencia individual de la part´ıcula en su nueva velocidad y C2 es el par´ametro social que indica la influencia m´axima de la informaci´on social en el nuevo valor de velocidad de la part´ıcula.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

La funci´on rand() retorna un n´ umero aleatorio en el intervalo [0, 1], mediante el cual se determina la influencia real de las informaciones individual y social en la nueva velocidad para la part´ıcula. T´ıpicamente a $ se le asigna un valor fijo de 0.8 y en otros casos se le asigna un valor inicialmente entre 1 y 1.5 que se hace decrecer durante la ejecuci´ on del algoritmo. A los pesos C1 y C2 generalmente se les asigna el valor 2. (Shi, Beielstein)

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

Cuando se opta por utilizar la informaci´ on local proveniente de las vecindades para actualizar las part´ıculas, de manera a evitar que todas ellas sean influenciadas por una u ´nica mejor posici´on, la ecuaci´on anterior se convierte en: t+1 t t +C1 ×rand()×(ptij −xtij )+C2 ×rand()×(lij −xtij ) vij = $ ×vij

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Algoritmo Enjambre de part´ıculas

1 2 3 4 5 6 7 8 9 10 11 12 13

C1 = 2 /* Par´ ametro cognitivo */ ; C2 = 2 /* Par´ ametro social */ ; $ = 0.8; /* Par´ ametro de inercia */ ; g = 1 /* ´Indice del mejor global */ ; iter = 1 /* Contador de iteraciones */ ; maxiter = 10000 /* N´ umero m´ aximo de iteraciones */; nropart = 20 /* N´ umero de part´ıculas */ ; for i = 1 to nropart do part[i].pos[j] = randompos(); part[i].vel[j] = randomvel(); for j = 1 to N do part[i].pos[j] = randompos(); part[i].vel[j] = randomvel();

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Algoritmo Enjambre de part´ıculas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

while iter ¡= maxiter do for i = 1 to nropart do /* Calcular la funci´ on objetivo */ ; part[i].eval = evaluar(part[i]); /* Guardar mejor posici´ on de la part´ıcula */ ; if part[i].eval ESMEJORQUE mejor[i].eval then mejor[i].pos[] = part[i].pos[]; /* copia vectorial */ ; mejor[i].eval = part[i].eval ; /* Determinar el mejor global */; if part[i].eval ESMEJORQUE mejor[g].eval then g = i; end end end for i = 1 to nropart do for j = 1 to N do part[i].vel[j] = $ * part [i].vel[j]+ C1 * rand() * (mejor[i].pos[j] part[i].pos[j])+ C2*rand()*(mejor[g].pos[j]part[i].pos[j]) ; part[i].pos[j] = part[i].pos[j] + part[i].vel[j]; end end iter = iter + 1 ; end retornar(mejor[g]) ;

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: F´acil de describir F´acil de implementar Pocos par´ametros a ajustar Trabaja con poblaciones peque˜ nas N´ umero de evaluaciones de la funci´ on objetivo suele ser peque˜ na

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: F´acil de describir F´acil de implementar Pocos par´ametros a ajustar Trabaja con poblaciones peque˜ nas N´ umero de evaluaciones de la funci´ on objetivo suele ser peque˜ na

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: F´acil de describir F´acil de implementar Pocos par´ametros a ajustar Trabaja con poblaciones peque˜ nas N´ umero de evaluaciones de la funci´ on objetivo suele ser peque˜ na

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: F´acil de describir F´acil de implementar Pocos par´ametros a ajustar Trabaja con poblaciones peque˜ nas N´ umero de evaluaciones de la funci´ on objetivo suele ser peque˜ na

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: F´acil de describir F´acil de implementar Pocos par´ametros a ajustar Trabaja con poblaciones peque˜ nas N´ umero de evaluaciones de la funci´ on objetivo suele ser peque˜ na

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: Cada individuo se comunica con una vecindad (las vecindades se solapan) Cada individuo mantiene informaci´ on local (mejor soluci´on vista hasta ahora, direcci´ on actual de b´ usqueda, etc.) La vecindad normalmente se mantiene fija Se modifica la informaci´ on local usando la informaci´on de los vecinos (o el mejor de ellos) Se confina posibles cambios para evitar explosiones

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: Cada individuo se comunica con una vecindad (las vecindades se solapan) Cada individuo mantiene informaci´ on local (mejor soluci´on vista hasta ahora, direcci´ on actual de b´ usqueda, etc.) La vecindad normalmente se mantiene fija Se modifica la informaci´ on local usando la informaci´on de los vecinos (o el mejor de ellos) Se confina posibles cambios para evitar explosiones

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: Cada individuo se comunica con una vecindad (las vecindades se solapan) Cada individuo mantiene informaci´ on local (mejor soluci´on vista hasta ahora, direcci´ on actual de b´ usqueda, etc.) La vecindad normalmente se mantiene fija Se modifica la informaci´ on local usando la informaci´on de los vecinos (o el mejor de ellos) Se confina posibles cambios para evitar explosiones

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: Cada individuo se comunica con una vecindad (las vecindades se solapan) Cada individuo mantiene informaci´ on local (mejor soluci´on vista hasta ahora, direcci´ on actual de b´ usqueda, etc.) La vecindad normalmente se mantiene fija Se modifica la informaci´ on local usando la informaci´on de los vecinos (o el mejor de ellos) Se confina posibles cambios para evitar explosiones

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Las caracter´ısticas principales son: Cada individuo se comunica con una vecindad (las vecindades se solapan) Cada individuo mantiene informaci´ on local (mejor soluci´on vista hasta ahora, direcci´ on actual de b´ usqueda, etc.) La vecindad normalmente se mantiene fija Se modifica la informaci´ on local usando la informaci´on de los vecinos (o el mejor de ellos) Se confina posibles cambios para evitar explosiones

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas La convergencia prematura suele ocurrir si todos los individuos se concentran en una regi´ on peque˜ na del espacio de b´ usqueda, para evitarlo debe considerarse: Los individuos en la poblaci´ on deben mantener cierta diversidad Se necesita una funci´ on de similitud Se adaptan din´amicamente los par´ametros del algoritmo para aumentar la diversidad Se usa justamente la diversidad como opci´ on de parada Se obliga diversidad en la poblaci´ on

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas Adaptaci´on de enjambre de part´ıculas para el PAV (Secrest). El espacio de decisi´on se define como el conjunto de todas las permutaciones posibles de los v´ertices del grafo del problema. La posici´on de una part´ıcula corresponde a una permutaci´on y las part´ıculas recorren el espacio de decisi´on pasando de una permutaci´on a otra. Esta adaptaci´on consiste en un algoritmo de construcci´on de soluciones, el cual conserva la idea de que la siguiente posici´on a visitar por una part´ıcula se deduce a partir de su posici´on actual (X) y de las mejores posiciones, espec´ıficamente del mejor global (G) y del mejor local de la part´ıcula (L). A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas Adaptaci´on de enjambre de part´ıculas para el PAV (Secrest). El espacio de decisi´on se define como el conjunto de todas las permutaciones posibles de los v´ertices del grafo del problema. La posici´on de una part´ıcula corresponde a una permutaci´on y las part´ıculas recorren el espacio de decisi´on pasando de una permutaci´on a otra. Esta adaptaci´on consiste en un algoritmo de construcci´on de soluciones, el cual conserva la idea de que la siguiente posici´on a visitar por una part´ıcula se deduce a partir de su posici´on actual (X) y de las mejores posiciones, espec´ıficamente del mejor global (G) y del mejor local de la part´ıcula (L). A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas Adaptaci´on de enjambre de part´ıculas para el PAV (Secrest). El espacio de decisi´on se define como el conjunto de todas las permutaciones posibles de los v´ertices del grafo del problema. La posici´on de una part´ıcula corresponde a una permutaci´on y las part´ıculas recorren el espacio de decisi´on pasando de una permutaci´on a otra. Esta adaptaci´on consiste en un algoritmo de construcci´on de soluciones, el cual conserva la idea de que la siguiente posici´on a visitar por una part´ıcula se deduce a partir de su posici´on actual (X) y de las mejores posiciones, espec´ıficamente del mejor global (G) y del mejor local de la part´ıcula (L). A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de part´ıculas

Los par´ametros cognitivo (C1) y social (C2) se reemplazan por los siguientes factores de influencia: 1

2

3

K1, que indica la probabilidad de seleccionar informaci´on de la posici´ on actual de la part´ıcula K2, que indica la probabilidad de seleccionar informaci´on de la mejor posici´ on en la vecindad de la part´ıcula K3, que indica la probabilidad de seleccionar informaci´on de la mejor posici´ on del enjambre

La suma de estos tres factores debe ser igual a 1 (100%).

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Algoritmo Enjambre de part´ıculas 1 2 3 4 5 6 7 8 9 10 11 12 13

posactual = Leer la posici´ on actual de la part´ıcula ; Leer par´ ametros K1, K2, K3, nrovertices y las mejores posiciones G y L; nuevapos[1] = posactual[nrovertices] /* nueva posici´ on */ ; for i = 2 to nrovertices do r = rand(100); vertelegido = FALSE; if r ¡= K3 then Elegir el v´ ertice j que aparece luego del v´ ertice indicado en nuevapos[i-1] en el mejor global G; if v´ ertice j no est´ a en nuevapos then nuevapos[i] = v´ ertice j; vertelegido = TRUE;

14 15

if r ¡= (K2 + K3) OR vertelegido = FALSE then Elegir el v´ ertice j que aparece luego del v´ ertice indicado en nuevapos[i-1] en la mejor posici´ on local L; if v´ ertice j no est´ a en nuevapos then nuevapos[i] = v´ ertice j; vertelegido = TRUE ;

16 17

if vertelegido = FALSE then nuevapos[i] = ultimo v´ ertice en posactual que no est´ a en nuevapos;

18

retornar(nuevapos);

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Inteligencia colectiva: Enjambres de Part´ıculas

Al observar el algoritmo de Secrest puede notarse que si un v´ertice j aparece luego de un v´ertice i en la mejor posici´ on del enjambre y en la mejor posici´on de la vecindad, este v´ertice j tiene una probabilidad K2 + K3 de aparecer luego del v´ertice i en la nueva posici´on para la part´ıcula. Esta caracter´ıstica es similar a la de los algoritmos de Colonia de Hormigas, en los cuales los caminos m´as utilizados tienen mayor probabilidad de ser empleados nuevamente.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Aplicaciones

Aplicaciones de la Inteligencia Artificial Swarm B´ usqueda de Rutas para una Red de Sat´elites. Se ha demostrado que la optimizaci´ on mediante colonias de hormigas da buenos resultados en la b´ usqueda de rutas en grandes sistemas de telecomunicaciones y redes de ordenadores. Enjambre de part´ıculas tiene aplicaciones en el control descentralizado de los veh´ıculos no tripulados para los militares.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Aplicaciones

Aplicaciones de la Inteligencia Artificial Swarm B´ usqueda de Rutas para una Red de Sat´elites. Se ha demostrado que la optimizaci´ on mediante colonias de hormigas da buenos resultados en la b´ usqueda de rutas en grandes sistemas de telecomunicaciones y redes de ordenadores. Enjambre de part´ıculas tiene aplicaciones en el control descentralizado de los veh´ıculos no tripulados para los militares.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Aplicaciones

El uso de Enjambre de part´ıculas en nanobots m´edicos tambi´en pueden ayudar a combatir el c´ancer. Enjambre de part´ıculas se utiliz´ o en la creaci´ on de la secuencia de v´ıdeo ”Batalla del Abismo de Helm” en la pel´ıcula, El Se˜ nor de los Anillos. Clustering de documentos. Es la operaci´ on de agrupar documentos similares en clases que pueden ser usadas para obtener un an´alisis de su contenido. Algoritmos de Clustering basados en colonias de hormigas catalogan documentos de la WEB en diferentes dominios de inter´es.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Aplicaciones

El uso de Enjambre de part´ıculas en nanobots m´edicos tambi´en pueden ayudar a combatir el c´ancer. Enjambre de part´ıculas se utiliz´ o en la creaci´ on de la secuencia de v´ıdeo ”Batalla del Abismo de Helm” en la pel´ıcula, El Se˜ nor de los Anillos. Clustering de documentos. Es la operaci´ on de agrupar documentos similares en clases que pueden ser usadas para obtener un an´alisis de su contenido. Algoritmos de Clustering basados en colonias de hormigas catalogan documentos de la WEB en diferentes dominios de inter´es.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Aplicaciones

El uso de Enjambre de part´ıculas en nanobots m´edicos tambi´en pueden ayudar a combatir el c´ancer. Enjambre de part´ıculas se utiliz´ o en la creaci´ on de la secuencia de v´ıdeo ”Batalla del Abismo de Helm” en la pel´ıcula, El Se˜ nor de los Anillos. Clustering de documentos. Es la operaci´ on de agrupar documentos similares en clases que pueden ser usadas para obtener un an´alisis de su contenido. Algoritmos de Clustering basados en colonias de hormigas catalogan documentos de la WEB en diferentes dominios de inter´es.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Aplicaciones

Colonia de hormigas: Resuelven problemas que se pueden representar como rutas/caminos entre nodos de un grafo. Enjambres de part´ıculas : Resuelven problemas similares a los resueltos por algoritmos de Computaci´ on Evolutiva.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Aplicaciones

Colonia de hormigas: Resuelven problemas que se pueden representar como rutas/caminos entre nodos de un grafo. Enjambres de part´ıculas : Resuelven problemas similares a los resueltos por algoritmos de Computaci´ on Evolutiva.

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on

M´ etodos evolutivos Inteligencia colectiva Enjambres de Part´ıculas

PAV con Enjambres de Part´ıculas

Bibliograf´ıa

L´ evy, Pierre. Inteligencia Colectiva, Humanidad emergente en el mundo del cyberespacio. T. Beielstein, K. E. Parsopoulos, M.N. Vrahatis. Tuning PSO parameters through sensitivity analysis. Technical Report of the Collaborative Research Center, University of Dortmund, 2002. Y. Shi, R. Eberhart. Parameter Selection in Particle Swarm Optimization. In Proceedings of the Seventh Annual Conference on Evolutionary Programming, pp. 591-601, 1998 B. Secrest. Traveling Salesman Problem for Surveillance Mission Using Particle Swarm Optimization. MS Thesis, AFIT/GCE/ ENG/01M-03, School of Engineering, Air Force Institute of Technology, Wright-Patterson AFB, Ohio, 2001. J. Kennedy, R. C. Eberhart. Particle Swarm Optimization. In Proceedings of the 1995 IEEE International Conference on Neural Networks, pp. 19421948, Piscataway, New Jersey, 1995. J. Kennedy, R. Eberhart. Swarm Intelligence. Morgan Kaufmann Publishers, 2001. E. Bonabeau, M. Dorigo, G. Theraulaz. Swarm Intelligence. Santa Fe Institute Studies in the Sciences of Complexity. New York, Oxford, 1999. Trejos, Javier; Murillo, Alex; Piza, Eduardo. Clustering by Ant Colony Optimization Trejos, Javier; Murillo, Alex; Piza, Eduardo; Pacheco, Alexia. Comparison of Metaheuristics for Partitioning in Cluster Analysis

A. Jim´ enez, A. Murillo, E. Piza, M. Villalobos, J. Trejos.

CIMAT. M´ etodos de reducci´ on de dimensi´ on