Heurísticas y Ciencias de la Vida
J. Marcos Moreno Vega
Grupo de Computación Inteligente
Dpto. de E.I.O. y Computación
Escuela Técnica Superior de Ingeniería Informática
Universidad de La Laguna
[email protected]
webpages.ull.es/users/jmmoreno
Universidad de La Laguna | Adeje 2005
1
 Heurísticas y Ciencias de la Vida
 Heurísticas
 Algoritmos Genéticos
 Optimización basada en Colonias de Hormigas
Universidad de La Laguna | Adeje 2005
2
HEURÍSTICAS | CIENCIAS DE LA VIDA
Heurísticas
Las Heurísticas
se han
empleado para
resolver
problemas que
aparecen en
las Ciencias de
la Vida
Medicina
Sociología
Zoología
Biología
El estudio de
ciertos
Sistemas
Biológicos
permite diseñar
nuevas
Heurísticas
…
Universidad de La Laguna | Adeje 2005
3
HEURÍSTICAS | CIENCIAS DE LA VIDA
 Supervivencia del más adaptado
 Trabajo en grupo
 Comunicación entre los miembros del grupo
Universidad de La Laguna | Adeje 2005
4
HEURÍSTICAS
 Origen
 Interpretaciones del término
 Campos de aplicación
 Clasificación
 Importancia
Universidad de La Laguna | Adeje 2005
5
HEURÍSTICAS | Origen
 Heurística proviene del griego Heuriskein que puede traducirse por
hallar, descubrir, encontrar
 Arquímedes salió corriendo desnudo por la calle gritando Eureka (lo
encontré), cuando descubrió el principio de flotación mientras estaba
en el baño
 Definición: arte de inventar o descubrir hechos valiéndose de
hipótesis o principios que, aun no siendo verdaderos, estimulan la
investigación
Universidad de La Laguna | Adeje 2005
6
HEURÍSTICAS | Interpretaciones
 Primera interpretación:
 reglas con las que la gente gestiona el conocimiento común
 Segunda interpretación:
 procedimiento de resolución de problemas
 Tercera interpretación:
 función que permite evaluar la bondad de un movimiento, estado,
elemento o solución
Universidad de La Laguna | Adeje 2005
7
HEURÍSTICAS | Primera Interpretación
 Buscar un problema parecido que haya sido resuelto
 Determinar cuáles fueron la técnica empleada para su resolución y
la solución obtenida.
 Si es posible, usar la técnica y/o solución anteriores para resolver el
problema original.
Universidad de La Laguna | Adeje 2005
8
HEURÍSTICAS | Primera Interpretación | Ejemplo
u dv = uv -  v du
 3x cosx dx = 3x sinx -  sinx 3 dx = 3x sinx – 3  sinx dx =
3x sinx + 3 cosx + C
u dv = uv -  v du
 4x sinx dx = - 4x cosx +  cosx 4 dx = - 4x cosx + 4  cosx dx =
- 4x cosx + 4 sinx + C
Universidad de La Laguna | Adeje 2005
9
HEURÍSTICAS | Segunda Interpretación
 Un método heurístico (también llamado un algoritmo aproximado, un
procedimiento inexacto, o, simplemente, una heurística) es un
conjunto bien conocido de pasos para identificar rápidamente una
solución de alta calidad para un problema dado.
Barr, Golden, Kelly, Resende, Stewart
Universidad de La Laguna | Adeje 2005
10
HEURÍSTICAS | Segunda Interpretación | Ejemplo
Heurística: desde el bar
actual nos movernos al
bar más cercano que no
hayamos visitado
Universidad de La Laguna | Adeje 2005
11
HEURÍSTICAS | Tercera Interpretación
 Una función heurística es una correspondencia entre las
descripciones de estados del problema hacia alguna medida de
deseabilidad, normalmente representada por números. Los aspectos
del problema que se consideran, cómo se evalúan estos aspectos y
los pesos que se dan a los aspectos individuales, se eligen de forma
que el valor que la función da a un nodo en el proceso de búsqueda
sea una estimación tan buena como sea posible para ver si ese nodo
pertenece a la ruta que conduce a la solución.
Elaine Rich, Kevin Knight
Universidad de La Laguna | Adeje 2005
12
HEURÍSTICAS | Tercera Interpretación | Ejemplo
1
2
3
1
2
3
1
2
3
O
4
5
6
4
X
7
8
5
6
O
4
5
X
9
7
8
6
X
9
7
8
9
X
Función heurística: número de filas, columnas o diagonales en las que se puede ganar
fx(1) = 3
fO(1) = 2
fX(1) = 2
fx(2) = 2
fO(2) = 1
fX(2) = 1
fx(3) = 3
fO(3) = 2
fx(4) = 2
fO(4) = 1
fX(4) = 2
fx(6) = 2
fO(6) = 1
fX(6) = 1
fx(7) = 3
fO(7) = 2
fX(7) = 2
fx(8) = 2
fO(8) = 1
fX(8) = 2
fx(9) = 3
fO(9) = 2
fX(9) = 2
fx(5) = 4
Universidad de La Laguna | Adeje 2005
13
HEURÍSTICAS
Algunos métodos de resolución de problemas emplean funciones
heurísticas, para evaluar determinados movimientos o elementos.
Además, las funciones heurísticas usadas intentan representar el
conocimiento que emplean los expertos para resolver los
problemas.
Universidad de La Laguna | Adeje 2005
14
HEURÍSTICAS | Campos de aplicación
Métodos para resolver problemas
Planificación y
secuenciación de tareas
Reconocimiento de formas
Bioinformática
Determinación automática de las
trayectorias de un robot
Sistemas de Búsqueda en Internet
Logística
Minería de datos
Seguridad Informática
Universidad de La Laguna | Adeje 2005
15
HEURÍSTICAS | Clasificación
 Métodos constructivos
 G.R.A.S.P.
 Métodos de búsqueda




Búsquedas Locales
Búsquedas Multiarranque
Simulated Annealing
VNS
 Scatter Search
 Métodos basados en el comportamiento de Sistemas
Biológicos
 Algoritmos Genéticos
 Optimización basada en Colonias de Hormigas
Universidad de La Laguna | Adeje 2005
16
HEURÍSTICAS | Importancia | Asociaciones
Metaheuristics Network web site
Universidad de La Laguna | Adeje 2005
17
HEURÍSTICAS | Importancia | Congresos
7th International Conference on Artificial Evolution
EvoCOP2005
5th European Conference on Evolutionary Computation in
Combinatorial Optimization
Universidad de La Laguna | Adeje 2005
18
HEURÍSTICAS | Importancia | Empresas
hestley
Universidad de La Laguna | Adeje 2005
19
HEURÍSTICAS | Importancia
 Las Heurísticas no son sólo la línea de investigación de algunos
(muchos) investigadores.
 Son el núcleo de sistemas informáticos que resuelven importantes
problemas prácticos.
Universidad de La Laguna | Adeje 2005
20
ALGORITMOS GENÉTICOS
 Un poco de historia
 Evolución natural de las especies
 Proceso evolutivo en la resolución de problemas
 Buscando el máximo de una función
Universidad de La Laguna | Adeje 2005
21
ALGORITMOS GENÉTICOS | Un poco de historia
Evolución natural
Charles Robert Darwin
Gregor Johann Mendel
Universidad de La Laguna | Adeje 2005
Hugo De Vries
22
ALGORITMOS GENÉTICOS | Un poco de historia | Darwin
 Charles Robert Darwin: El 27 de diciembre de 1831 zarpa de Davenport
(Inglaterra) el Beagle, buque al mando del capitán Fitz-Roy, con varios objetivos
científicos: completar el estudio de las costas de la Patagonia y Tierra del
Fuego, realizar la cartografía de las costas de Chile, Perú y algunas islas del
Pacífico y realizar varias observaciones cronométricas alrededor del mundo. A
bordo viaja el joven naturalista de 22 años, Charles Robert Darwin (1809-1882).
El 6 de enero de 1832 el Beagle fondea frente a las costas de Tenerife. Sin
embargo, las autoridades obligan a la tripulación a permanecer a bordo del
buque por miedo a que padezca el cólera. La larga travesía del Beagle, que
atraca el 2 de octubre en Falmouth, sirve a Darwin para enunciar su teoría
acerca del origen y evolución de las especies. Uno de los elementos claves en
la teoría de Darwin es que la evolución se debe a la selección natural. Es decir,
aquellos individuos más adaptados al medio tienen mayor probabilidad de
sobrevivir y, de esta forma, las características que les hacen mejores se
propagan entre la descendencia. De esta forma, y de manera gradual, surgen
las diversas especies.
Universidad de La Laguna | Adeje 2005
23
ALGORITMOS GENÉTICOS | Un poco de historia | Mendel
 Gregor Johann Mendel: El monje agustino austriaco Johann Mendel (18221884) se interesó por los principios que rigen la herencia de características en
las especies. En 1843 se ordenó sacerdote y diez años más tarde fue
nombrado profesor suplente de la escuela moderna de Brno, lugar donde pasó
la mayor parte de su vida. En el jardín del mencionado convento cultivó algunas
variedades de guisantes. Escogió algunas características con alternativas
claras. Por ejemplo, semillas redondas o rugosas. Seleccionó variedades de
guisantes que producían descendencias homogéneas para estas
características y estudió sus sucesivas descendencias. De esta forma, pudo
enunciar sus leyes acerca de la herencia. Estas muestran en que proporción se
manifiestan las alternativas de cada característica. Para explicar las
proporciones observadas, Mendel enunció la hipótesis de que la primera
generación de guisantes contenía elementos hereditarios para ambas
alternativas del carácter. Sus trabajos pueden considerarse como la base de la
genética
Universidad de La Laguna | Adeje 2005
24
ALGORITMOS GENÉTICOS | Un poco de historia | De Vries
 Hugo De Vries: El botánico holandés Hugo De Vries (1848-1935) introdujo el
concepto de mutación. Creía que las especies no surgían de manera gradual,
sino a través de mutaciones de especies conocidas. Si estas mutaciones
derivan en características beneficiosas, las mismas se propagan entre la
descendencia. Fue responsable de que los trabajos de Mendel viesen la luz, ya
que en 1900, dieciséis años después de la muerte de Mendel, encontró dichos
trabajos y los dio a conocer.
Universidad de La Laguna | Adeje 2005
25
ALGORITMOS GENÉTICOS | Evolución natural de las especies (i)
 La evolución se produce por dos procesos: la selección y la alteración
genética de los cromosomas que almacenan las características de la especie.
La alteración genética tiene lugar durante la reproducción de los individuos, o
cuando éstos sufren algún tipo de mutación. En el proceso de selección,
aquellos individuos más adaptados o adecuados al medio sobreviven; en la
reproducción, los individuos intercambian material cromosómico; y en la
mutación, se altera parte de la información de los cromosomas.
En la naturaleza, estos procesos ocurren sobre una generación, y luego sobre
su descendencia, y a continuación sobre la descendencia de ésta, y así
sucesivamente. Después de cada ciclo, la generación actual será (o al menos
así se desea) mejor que las anteriores. Esto es, los individuos estarán más
evolucionados y adaptados al medio.
Universidad de La Laguna | Adeje 2005
26
ALGORITMOS GENÉTICOS | Evolución natural de las especies (ii)
Población inicial
Selección
Cruce
Mutación
Universidad de La Laguna | Adeje 2005
27
ALGORITMOS GENÉTICOS | Proceso evolutivo en la
resolución de problemas
 En 1975, John Holland defendió su tesis doctoral Adaptation in Natural and
Artificial Systems (Adaptación en Sistemas Naturales y Artificiales) en la
Universidad de Michigan. En ella, se proponía por primera vez una clase de
métodos, llamados Algoritmos Genéticos, para la resolución de problemas.
La idea que subyace en los algoritmos genéticos es que es posible
implementar, en un ordenador, un programa que, guiado por los principios de
la herencia y la evolución de las especies, suministre la solución de un
problema.
Universidad de La Laguna | Adeje 2005
28
ALGORITMOS GENÉTICOS | Proceso evolutivo en la
resolución de problemas
Para usar las ventajas del modelo del proceso evolutivo en la resolución de un
problema, se deben establecer las siguientes correspondencias:
1.
Una apropiada codificación de las posibles soluciones del problema
representará a éstas de la misma forma que el cromosoma representa a los
individuos de la especie. Dada esta unívoca relación, se usarán
indistintamente los términos solución, codificación, cromosoma o individuo.
2.
La adecuación de cada solución será una medida del comportamiento de
ésta en el problema particular considerado. Normalmente, es el valor objetivo
de la solución. Así, una solución está más adecuada a un problema cuanto
mejor sea su valor objetivo.
3.
Se definirán unos operadores genéticos que, al actuar sobre una o varias
soluciones, suministren una o más soluciones al alterar genéticamente los
cromosomas. Juegan el papel del cruce y la mutación en el proceso evolutivo
natural.
Universidad de La Laguna | Adeje 2005
29
ALGORITMOS GENÉTICOS | Proceso evolutivo en la
resolución de problemas
Con las consideraciones anteriores, el Algoritmo Genético trabaja como sigue:
1. Generar una población inicial de soluciones.
2. Seleccionar, de la población actual, las soluciones mejor adaptadas al
medio.
3. Cruzar algunas soluciones para obtener su descendencia.
4. Mutar algunas soluciones para obtener las soluciones mutadas.
5. Si se alcanza el número máximo de generaciones, parar; en otro caso,
volver al paso 2.
Al finalizar los pasos anteriores, la mejor solución de la población es la que se
propone como solución del problema.
Universidad de La Laguna | Adeje 2005
30
ALGORITMOS GENÉTICOS | Buscando el máximo de una función
Encontrar el máximo global de la función real de una variable f(x) = – x2 + 5x +3
sobre el intervalo (0, 4) con una precisión de 3 dígitos tras el punto decimal.
9.25
7
Máximo en x = 2.5, con valor 9.25
3
2.5
4
Universidad de La Laguna | Adeje 2005
31
ALGORITMOS GENÉTICOS | Buscando el máximo de una función |
Representando las soluciones
Para representar de forma apropiada las soluciones de este problema
usamos la representación binaria. Representamos cada número real del
intervalo (0,4) en base 2 con una precisión de 10-3.
Puesto que 4 = 1002 y 0’00000000012 = 2-10 < 10-3 será suficiente con tomar
como soluciones posibles de nuestro problema a los números reales
representados en forma binaria por dos cifras antes de la coma y 10 detrás.
Cromosoma
(10’0101110000)
(01’1000111010)
Número real
2’359375000
1’546640625
Universidad de La Laguna | Adeje 2005
32
ALGORITMOS GENÉTICOS | Buscando el máximo de una función |
Población inicial
Una forma sencilla de construir una población inicial de tamaño n para el
problema planteado consiste en generar, aleatoriamente, n cadenas binarias
de tamaño 12.
Para n = 5, en la tabla siguiente se muestra una de tales poblaciones iniciales.
En dicha tabla se recoge la cadena binaria, el número real que representa y el
valor de dicha cadena.
Cromosoma
x1 = (10’0101110000)
x2 = (01’1000111010)
x3 = (11’1100101010)
x4 = (10’0000111010)
x5 = (00’0001111010)
Número real (xi)
2’359375000
1’546640625
3’791015625
2’056640600
0’119140600
Suma de los valores de la función
Valor de la función (f(xi))
9’2302
8’3411
7’5831
9’0534
3’5815
 f(x) = 37‘7893
Universidad de La Laguna | Adeje 2005
33
ALGORITMOS GENÉTICOS | Buscando el máximo de una función |
Selección (i)
Durante esta fase, debe obtenerse una nueva población desde la población anterior.
El procedimiento debe ser tal que los individuos más adaptados, es decir, las
soluciones, x, con mayor valor de la función f(x), tengan mayor probabilidad de ser
elegidos.
Para ello, emplearemos el conocido como método de la rueda de hilar. En este
método se asigna a cada solución, x, de la población un segmento del intervalo [0,1]
proporcional al valor relativo de la función f:
f (x)
 f (x)
x1 f(x1) = 9’2302
f(x1)/f(x) = 9’2302/37‘7893 = 0’244
x2 f(x2) = 8’3411
f(x2)/f(x) = 8’3411/37‘7893 = 0’221
x1
x2
x3
x4
x5
0
1
0.244
0.465
0.665
0.905
Figura 1. Rueda de hilar
Universidad de La Laguna | Adeje 2005
34
ALGORITMOS GENÉTICOS | Buscando el máximo de una función |
Selección (ii)
Cromosoma
x1 = (10’0101110000)
x2 = (01’1000111010)
x3 = (11’1100101010)
x4 = (10’0000111010)
x5 = (00’0001111010)
Número real (xi)
2’359375000
1’546640625
3’791015625
2’056640600
0’119140600
Suma de los valores de la función
Valor de la función (f(xi))
9’2302
8’3411
7’5831
9’0534
3’5815
 f(x) = 37‘7893
0’125, 0’750, 0’1875, 0’3125, 0’8125
Cromosoma
x1 = (10’0101110000)
x4 = (10’0000111010)
x1 = (10’0101110000)
x2 = (01’1000111010)
x4 = (10’0000111010)
Número real (xi)
2’359375000
2’056640600
2’359375000
1’546640625
2’056640600
Suma de los valores de la función
Valor de la función (f(xi))
9’2302
9’0534
9’2302
8’3411
9’0534
 f(x) = 44‘9073
Universidad de La Laguna | Adeje 2005
35
ALGORITMOS GENÉTICOS | Buscando el máximo de una función |
Cruce (i)
 Formar aleatoriamente parejas para el cruce
 Aplicar el operador de cruce a cada pareja
Operador de cruce para cadenas binarias: seleccionar una posición de cruce al
azar e intercambiar las subcadenas de la derecha.
(10’01011|10000)
(11’01001|10101)
(10’01011|10101)
(11’01001|10000)
Universidad de La Laguna | Adeje 2005
36
ALGORITMOS GENÉTICOS | Buscando el máximo de una función |
Cruce (ii)
Cromosoma
x1 = (10’0101110000)
x4 = (10’0000111010)
x1 = (10’0101110000)
x2 = (01’1000111010)
x4 = (10’0000111010)
Número real (xi)
2’359375000
2’056640600
2’359375000
1’546640625
2’056640600
Suma de los valores de la función
Valor de la función (f(xi))
9’2302
9’0534
9’2302
8’3411
9’0534
 f(x) = 44‘9073
x1, x4
Cromosoma
x’1 = (10’0101111010)
x4 = (10’0000111010)
x1 = (10’0101110000)
x2 = (01’1000111010)
x’4 = (10’0000110000)
Número real (xi)
2’369140625
2’056640600
2’359375000
1’546640625
2’046875000
Suma de los valores de la función
Valor de la función (f(xi))
9’2329
9’0534
9’2302
8’3411
9’0447
 f(x) = 44‘9023
Universidad de La Laguna | Adeje 2005
37
ALGORITMOS GENÉTICOS | Buscando el máximo de una función |
Mutación (i)
 Para cada bit del cromosoma decidir aleatoriamente si éste muta o no.
 Aplicar el operador de mutación a los correspondientes bits
Operador de mutación para cadenas binarias: sustituir el valor del bit por su
complementario (0 por 1, 1 por 0)
(10’0101110000)
(10’0001110010)
Universidad de La Laguna | Adeje 2005
38
ALGORITMOS GENÉTICOS | Buscando el máximo de una función |
Mutación (ii)
Cromosoma
x’1 = (10’0101111010)
x4 = (10’0000111010)
x1 = (10’0101110000)
x2 = (01’1000111010)
x’4 = (10’0000110000)
Número real (xi)
2’369140625
2’056640600
2’359375000
1’546640625
2’046875000
Suma de los valores de la función
Valor de la función (f(xi))
9’2329
9’0534
9’2302
8’3411
9’0447
 f(x) = 44‘9023
Muta el quinto bit de la solución x’1
Cromosoma
x’’1 = (10’0111111010)
x4 = (10’0000111010)
x1 = (10’0101110000)
x2 = (01’1000111010)
x’4 = (10’0000110000)
Número real (xi)
2’494140625
2’056640600
2’359375000
1’546640625
2’046875000
Suma de los valores de la función
Valor de la función (f(xi))
9’2500
9’0534
9’2302
8’3411
9’0447
 f(x) = 44‘9194
Universidad de La Laguna | Adeje 2005
39
ALGORITMOS GENÉTICOS | Buscando el máximo de una función |
Finaliza un ciclo evolutivo
 De esta forma finaliza un ciclo evolutivo.
 La mejor solución encontrada en esta etapa es
x’’1 = (10’0111111010)
2’494140625
9’2500
 El proceso continúa hasta que se decida parar (en general, se finaliza
cuando cuando se alcanza un número máximo de generaciones).
Universidad de La Laguna | Adeje 2005
40
OPTIMIZACIÓN BASADA EN
COLONIAS DE HORMIGAS
 Hormigas reales
 Explicamos su comportamiento
 ¿Cómo usar lo anterior?
 Etapas del procedimiento
Universidad de La Laguna | Adeje 2005
41
OPTIMIZACIÓN BASADA EN COLONIAS DE HORMIGAS
La estrategia empleada por las Colonias de Hormigas para descubrir fuentes
de alimentación, establecer el camino más corto entre éstas y el hormiguero
y transmitir esta información al resto de sus compañeras inspiró a los
investigadores Marco Dorigo, Vittorio Maniezzo y Alberto Colorni. Éstos,
emulando dicha estrategia, propusieron un nuevo procedimiento de
resolución de problemas que supone actualmente uno de los tópicos en los
que más se investiga.
Universidad de La Laguna | Adeje 2005
42
HORMIGAS REALES
O
B
S
T
Á
C
U
L
O
O
B
S
T
Á
C
U
L
O
Universidad de La Laguna | Adeje 2005
43
HORMIGAS REALES | Algunas observaciones
 Si no encuentran un rastro de feromona, se mueven aleatoriamente.
 Las hormigas construyen iterativamente soluciones al problema que se les
plantea e intercambian información sobre éstas para construir mejores
soluciones.
 La atracción que sienten por un determinado camino es proporcional a la
intensidad del rastro de feromona sobre el mismo.
Universidad de La Laguna | Adeje 2005
44
EXPLICAMOS SU COMPORTAMIENTO | Características de las
hormigas artificiales
 Tendrán memoria
 No serán completamente ciegas.
 Vivirán en un entorno discreto.
 Se moverán a razón de una unidad de espacio por unidad de tiempo.
Universidad de La Laguna | Adeje 2005
45
EXPLICAMOS SU COMPORTAMIENTO | Simulación
E
E
E
30
1
D
A
15
0.5
A
D
30
10
15
A
A
D
20
 = 15
A
A
 = 30
1
B
0.5
15
15
B
10
30
A
Inicio
A
t=0
Universidad de La Laguna | Adeje 2005
20
B
30
A
t=1
46
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio
Sistema Hormiga: Colocar una hormiga en cada ciudad.
 Cada hormiga escoge la ciudad a la que ir con una probabilidad que
depende de la distancia a dicha ciudad, y del rastro de feromona
presente en la arista que conecta la ciudad de origen con la ciudad
destino.
 Empleando la memoria de que están dotadas, las hormigas
construyen circuitos legales evitando repetir ciudades previamente
visitadas.
 Cuando se completa un circuito, las hormigas (todas o algunas)
segregan feromona sobre las aristas que han sido atravesadas.
 La feromona segregada, y la que estaba presente en las aristas, se
usa para actualizar el rastro de feromona en la siguiente iteración.
Universidad de La Laguna | Adeje 2005
47
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio |
Elementos
dij
distancia entre las ciudades i y j
ij = 1/ dij inversa de la distancia entre las ciudades i y j
Sk(i)
conjunto de ciudades alcanzables por la k-ésima hormiga desde la ciudad i
ij
intensidad del rastro de feromona de la arista (i,j)
ijk
incremento de feromona de la arista (i,j) debido a la aportación de la k-ésima
hormiga
ij
incremento de feromona de la arista (i,j) debido a la aportación de todas las
hormigas
Lk
longitud del circuito construido por la k-ésima hormiga
c
rastro inicial de cada arista (constante fijada por el usuario)
Q
constante fijada por el usuario; el rastro que recibe una arista depende de
este valor

parámetro fijado por el usuario; (1- ) representa la cantidad de feromona
que desaparece de una arista por efecto de la evaporación
Universidad de La Laguna | Adeje 2005
48
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio
j
(ij , ij)
?
(im , im)
i
m
.
.
(ir , ir)
.
r
Universidad de La Laguna | Adeje 2005
49
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio |
Pseudocódigo
Procedure Sistema Hormiga;
begin
Inicialización
repeat
for k := 1 to n do
begin
i := k;
repeat
Escoge j  Sk(i);
i := j;
until Solución Factible;
Calcula incremento del rastro;
end;
Actualiza(Rastro);
Almacena(Mejor Solución);
until (criterio de parada);
end.
Universidad de La Laguna | Adeje 2005
ij = c
(ij , ij)
ijk
ij
Lk
ijk
50
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio |
Incremento y actualización del rastro
Incremento debido a la k-ésima hormiga
 ij
k
Q
L
 k

 0


si la arista (i,j) pertenece a la solución construida por la k-ésima
hormiga
en otro caso
Incremento total
 ij 
Actualización
n
 
k 1
k
ij
 ij   ij   ij
Universidad de La Laguna | Adeje 2005
51
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio |
Probabilidad de transición
  ij  ij 







 ir ir
 r
S (i)

k
pij  

0





si j  Sk(i)
k
en otro caso
Universidad de La Laguna | Adeje 2005
52
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio |
Un ejemplo
Matriz de distancias
5
4
6
3




D





0
1
5
1
0
2
5
5
2
2
2
5
2
0
2
5
5
2
2
5
5
2
0
1
5
1
0
3
5
2
2

5

3

5

2
0 
Matriz de visibilidad
1
2
 

 1
 0.447

 0.447

0.5

 0.707

1
0.447
0.447
0.5

0.707
0.5
0.447
0.707

0.707
0.447
0.5
0.707

1
0.447
0.447
1

0.447
0.333
0.447
0.707
Universidad de La Laguna | Adeje 2005
0.707 

0.447 
0.333 

0.447 

0.707

 
53
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio |
Un ejemplo
Matriz de feromona inicial
0

10
10
 
10

10

10

10 10 10 10 10 

0 10 10 10 10 
10 0 10 10 10 

10 10 0 10 10 

10 10 10 0 10

10 10 10 10 0 
Matriz de probabilidad de transición


 100
 44.7


  
 44.7

50

 70.7

100
44.7
44.7
50
70.7
50
44.7
70.7
44.7
70.7
50
70.7
44.7
44.7
100
44.7
33.3
44.7
Universidad de La Laguna | Adeje 2005
100
70.7
70.7 

44.7 
33.3 

44.7 

70.7



54
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio |
Un ejemplo
Probabilidades de transición
1
2
3
4
5
6
Aleat.
Solución
0.322
0.144
0.144
0.161
0.227
0.000
(1 2_ _ _ _)
0.336
0.237
0.212
0.212
0.031
(1 2 3 _ _ _)
3
0.475
0.300
0.223
0.673
(1 2 3 5 _ _)
5
0.585
0.414
0.842
(1 2 3 5 6 _)
6
1.00
1
2
(1 2 3 5 6 4)
Incremento del rastro
1

1

12
9.496
23
9.496
5
1

1

35
9.496
56
9.496
1

64
9.496
1

41
9.496
Q
Valor objetivo
100
10.53
4
Hormiga 1
6
3
1
2
Universidad de La Laguna | Adeje 2005
55
¿CÓMO USAR LO ANTERIOR? | Problema del Viajante de Comercio |
Un ejemplo
0

10
10
 
10

10

10

10 10 10 10 10 

0 10 10 10 10 
10 0 10 10 10 

10 10 0 10 10 

10 10 10 0 10

10 10 10 10 0 
 0

 45.58
 13.99
 
 23.99

25.23

 33.73

Matriz de feromona inicial
45.58
13.99
23.99
25.23
0
35.03
33.73
5
35.03
0
24.74
52.72
33.73
24.74
0
35.03
5
52.72
35.03
0
23.18
16.04
35.03
79.54
33.73 

23.18 
16.04 

35.03 

79.54

0 
Matriz de feromona tras una iteración
Universidad de La Laguna | Adeje 2005
56
ETAPAS DEL PROCEDIMIENTO
1. Inicialización: Se fija el rastro inicial
2. Fase constructiva. Se construyen soluciones al problema empleando la
información que suministra el rastro de feromona y alguna función heurística de
lo apropiado de una elección.
3. Cálculo del incremento del rastro. Se calcula el incremento en la intensidad del
rastro.
4. Actualizar el rastro de feromona. Se calcula el nuevo rastro de feromona.
5. Criterio de parada. Si el criterio de parada se cumple, finalizar la búsqueda. En
caso contrario, volver al paso 2.
Universidad de La Laguna | Adeje 2005
57
ALGUNAS NOTICIAS | Sistemas hormigas
Etología e inteligencia artificial:
hay hormigas en las redes.
Artificial ants solve
network problems
Insect Power
Software that imitates the behaviour of ants could make
highway and telecom traffic more efficient
Universidad de La Laguna | Adeje 2005
58
ALGUNAS NOTICIAS | Algoritmos Genéticos
Natural defences
Guardian Unlimited Life Natural defences.htmThe Pentagon is turning biologists'
knowledge of evolution into a computer program to
predict terrorist threats. Andrew Parker is helping them see the Cambrian explosion as
an arms race
Thursday November 18, 2004
The Guardian
Universidad de La Laguna | Adeje 2005
59
Descargar

Diapositiva 1