Algoritmos evolutivos híbridos para coloreo de grafos
-
Upload
rama-powell -
Category
Documents
-
view
28 -
download
1
description
Transcript of Algoritmos evolutivos híbridos para coloreo de grafos
![Page 1: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/1.jpg)
Algoritmos evolutivos híbridos para coloreo de grafos
Ivo Koch
Metaheurísticas1er cuatrimestre 2009
![Page 2: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/2.jpg)
Introducción
P. Galinier, J. Hao (1999). Hybrid evolutionary algorithms for graph coloring Journal of Combinatorial Optimization, vol. 3, no. 4, pp. 379-397.
P. Galinier, J. Hao (1999). Hybrid evolutionary algorithms for graph coloring Journal of Combinatorial Optimization, vol. 3, no. 4, pp. 379-397.
Porumbel, J.-K. Hao, P. Kuntz (2009).
Diversity control and multi-parent recombination for evolutionary graph coloring algorithms9th European Conference on Evolutionary Computation in Combinatorial Optimisation
Porumbel, J.-K. Hao, P. Kuntz (2009).
Diversity control and multi-parent recombination for evolutionary graph coloring algorithms9th European Conference on Evolutionary Computation in Combinatorial Optimisation
HCAHCA
EVOCOLEVOCOL
AlgoritmosResultadosConclusiones
Papers ElegidosEspecificación del problema
![Page 3: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/3.jpg)
IntroducciónAlgoritmosResultados
Papers Elegidos
Conclusiones
Especificación del problema
Considerar el problema de encontrar un k-coloreo para un grafo G(V, E), para k fijo.
Dada una instancia (G, k) del problema, lo trataremos como un problema de optimización (Ω, f).
El espacio de búsqueda Ω : s Ω es una partición s = {V1, V2, ..., Vk} de V en k subconjuntos.
La función objetivo f : s Ω, f(s) = | {e E : ambos vértices de e están en el mismo Vi s }|
![Page 4: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/4.jpg)
Introducción Esquema general de EVOCOL y HCA
•Input: Grafo G(V, E), entero k•Output: La mejor configuración encontrada•Procedimiento:
Pob = InitPopulation()
while not Stop-Condition() do
for i = i to ch hacer //ch es cantidad de hijos
repetir
(I1, I2, ..., In) = SelectParents(Pob, n)
Hi = CrossOver(I1, I2, ..., In)
Hi = LocalSearch(Hi, maxIter)
hasta AcceptOffspring(Pob, Hi)
end for
Pob = UpdatePopulation(Pob, H1, H2,...Hch)
end while
•Input: Grafo G(V, E), entero k•Output: La mejor configuración encontrada•Procedimiento:
Pob = InitPopulation()
while not Stop-Condition() do
for i = i to ch hacer //ch es cantidad de hijos
repetir
(I1, I2, ..., In) = SelectParents(Pob, n)
Hi = CrossOver(I1, I2, ..., In)
Hi = LocalSearch(Hi, maxIter)
hasta AcceptOffspring(Pob, Hi)
end for
Pob = UpdatePopulation(Pob, H1, H2,...Hch)
end while
Esquema general de EVOCOL y HCA
AlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
![Page 5: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/5.jpg)
Para i = 1 hasta n Crear la configuración Ci, con k clases color vacías, V1 = V2 ... = Vk = Mientras sea posible Elegir vV tq v tiene el mínimo número de clases permitidas Elegir de las clases permitidas Vi para v la que tenga índice más chico. Fin mientras Si quedaron vértices sin asignar a una clase, colocarlo al azar en alguna. Aplicar Tabu Search a Ci
fin para
Para i = 1 hasta n Crear la configuración Ci, con k clases color vacías, V1 = V2 ... = Vk = Mientras sea posible Elegir vV tq v tiene el mínimo número de clases permitidas Elegir de las clases permitidas Vi para v la que tenga índice más chico. Fin mientras Si quedaron vértices sin asignar a una clase, colocarlo al azar en alguna. Aplicar Tabu Search a Ci
fin para
InitPopulation HCA
Introducción Esquema general de EVOCOL y HCAAlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
![Page 6: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/6.jpg)
2 parent Crossover HCA
•Input: Dos configuraciones C1 y C2•Output: Una configuración hija Ch•Procedimiento:Para i = 1 hasta k Si i es impar, Cactual = C1, sino Cactual = C2
Elegir de Cactual la clase color Vj con la máxima cardinalidad Agregar a Ch la clase Vj Eliminar los vértices de Vj de C1 y C2Fin para Asignar al azar clases color de Ch a los vértices que quedaron.
•Input: Dos configuraciones C1 y C2•Output: Una configuración hija Ch•Procedimiento:Para i = 1 hasta k Si i es impar, Cactual = C1, sino Cactual = C2
Elegir de Cactual la clase color Vj con la máxima cardinalidad Agregar a Ch la clase Vj Eliminar los vértices de Vj de C1 y C2Fin para Asignar al azar clases color de Ch a los vértices que quedaron.
Introducción Esquema general de EVOCOL y HCAAlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
![Page 7: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/7.jpg)
•Input: Varias configuraciones padre C1, ... Cn•Output: Una configuración hija Ch•Procedimiento:Ch =empty For currentColor= 1 To k Foreach padre Ci {C1,C2, . . . , Cn} Foreach color class Vji en Ci Quitar de Vji todos los vértices que ya están en Ch conflicts = |{(v1, v2) Vji × Vji : (v1, v2) E}| classSize = |Vji| score[Vji ] = conflicts×|V|-classSize
Elegir la clase color Vmejor con score mínimo
Foreach v Vmejor
Ch[v] = currentColorForeach unassigned v Ch O[v] =un color que genera el menor número de conflictos
•Input: Varias configuraciones padre C1, ... Cn•Output: Una configuración hija Ch•Procedimiento:Ch =empty For currentColor= 1 To k Foreach padre Ci {C1,C2, . . . , Cn} Foreach color class Vji en Ci Quitar de Vji todos los vértices que ya están en Ch conflicts = |{(v1, v2) Vji × Vji : (v1, v2) E}| classSize = |Vji| score[Vji ] = conflicts×|V|-classSize
Elegir la clase color Vmejor con score mínimo
Foreach v Vmejor
Ch[v] = currentColorForeach unassigned v Ch O[v] =un color que genera el menor número de conflictos
Multiparent Crossover EVOCOL
Introducción Esquema general de EVOCOL y HCAAlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
![Page 8: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/8.jpg)
Ambos algoritmos utilizan para esta fase el algoritmo de Tabu Search aplicado a graph coloring:
A. Hertz and D. Werra
Using tabu search techniques for graph coloringComputing, 39(4):345–351, 1987.
A. Hertz and D. Werra
Using tabu search techniques for graph coloringComputing, 39(4):345–351, 1987.
Introducción Esquema general de EVOCOL y HCAAlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
![Page 9: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/9.jpg)
Buscamos un algoritmo para decidir si el nuevo hijo es 'demasiado parecido' a algun individuo de la población.
Dadas dos configuraciones Ca y Cb, la distancia entre Ca y Cb es el mínimo número de vértices que deben moverse entre clases color de Ca para que Ca = Cb.Notación : d(Ca, Cb)
También podemos definir la distancia como el 'complemento' de la similitud entre dos configuraciones Ca y Cb. La similitud es el máximo número de elementos que NO necesitan cambiar su clase color en la transformación de Ca en Cb.Notación : Similitud s(Ca, Cb)
d(Ca, Cb) = |V| - s(Ca, Cb)d(Ca, Cb) = |V| - s(Ca, Cb)
Introducción Esquema general de EVOCOL y HCAAlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
![Page 10: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/10.jpg)
Si tenemos un algoritmo para computar la similitud s(Ca, Cb), ya está:
Dado un hijo Ch, calculamos la similitud con todos los individuos de la población, y sólo lo aceptamos si supera un 'umbral de diversidad'.
Dados Ca y Cb, definir una matriz S de k x k, con elementos Sij = |Via ∩ Vjb|. El problema puede transformarse en el de elegir un assignment (selección elem. de S tq no hay elems. en la misma fila ni columna) tal que la suma de los elem. seleccionados sea máxima. Este problema es conocido y se llama assignment problem
2 0 0
1 1 0
0 1 1
Ejemplo
Ca = {A, B}{C, D}{E,F}
Cb = {A, B,C}{D,E}{F} Ca
Cb
Introducción Esquema general de EVOCOL y HCAAlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
![Page 11: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/11.jpg)
•Input: population Pop = (C1, C2, . . . , C|Pop|)•Output: La configuración a ser eliminada•Procedimiento:
Repeat Ca1 = RandomIndividual(Pop)Until AcceptCandidate(Ca1) (fitness-based acceptance)
minDist = maximum possible integerForeach C Pop − {Ca1} If d(I,Ca1) <minDist If AcceptCandidate(C) minDist = d(C,C1) Ca2 = CIf f(Ca1) < f(Ca2) Return Ca2Else Return Ca1
•Input: population Pop = (C1, C2, . . . , C|Pop|)•Output: La configuración a ser eliminada•Procedimiento:
Repeat Ca1 = RandomIndividual(Pop)Until AcceptCandidate(Ca1) (fitness-based acceptance)
minDist = maximum possible integerForeach C Pop − {Ca1} If d(I,Ca1) <minDist If AcceptCandidate(C) minDist = d(C,C1) Ca2 = CIf f(Ca1) < f(Ca2) Return Ca2Else Return Ca1
Eliminate() Elección del individuo a eliminar de la población
Introducción Esquema general de EVOCOL y HCAAlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
![Page 12: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/12.jpg)
AcceptCandidate (Es el individuo un candidato para ser eliminado?)
C tq. f(C) < fm
fm = mediana de f(C), C P
C tq. f(C) > fm
Se acepta siempre para ser eliminado
Se acepta para ser eliminado con una probabilidad de 1/2
No se acepta nunca para ser eliminado
C tq. f(C) es la mejor encontrada
Introducción Esquema general de EVOCOL y HCAAlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
![Page 13: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/13.jpg)
Tamaño de la población
Cant. máxima de iteraciones del TabuSearch
Valor fijado (empíricamente)
10
500-16000
Parámetros que determinan tamaño de lista Tabu
Cantidad de hijos por generación
Cantidad de padres de cada hijo
Umbral de rechazo de un hijo por (escasa) diversidad 10%|V|
HCAHCA EVOCOLEVOCOL
Introducción Esquema general de EVOCOL y HCAAlgoritmosResultadosConclusiones
InitPopulation HCA2 parent Crossover HCAMultiparent Crossover EVOCOL
Local SearchAccept Offspring EVOCOLUpdatePopulation EVOCOLParámetros de los algoritmos
3
15
1000000
3-7
Tl = α * f(C) + random(A) + floor(M / Mmax)
A = 10, α = 0.6,Mmax = 1000
A = 10, α = 0.6
![Page 14: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/14.jpg)
Fuente de los grafos benchmark: 2nd DIMACS Implementation Challenge (http://dimacs.rutgers.edu/)
Introducción HCA vs Tabu SearchAlgoritmosResultadosConclusiones
HCA + EVOCOL + Estado del arte
![Page 15: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/15.jpg)
20
T[s] *
EVOCOL
T[s] **
HCA
928
142818044688
13251848756903152
44
99564591
110494508
32520
79
EVOCOL HCA
1608
13550
327118
8827
* Implementación en C++ compilado con opción –O3 de optimización, ejecutado en Xeon 2.8Ghz.
** Implementación en C++ compilado sin optimizar, ejecutado en UltraSparc-IIi 333Mhz con 132Mb RAM
Introducción HCA vs Tabu SearchAlgoritmosResultadosConclusiones
HCA + EVOCOL + Estado del arte
![Page 16: Algoritmos evolutivos híbridos para coloreo de grafos](https://reader036.fdocumento.com/reader036/viewer/2022082611/568136d1550346895d9e6f5e/html5/thumbnails/16.jpg)
Agregar características evolutivas a Tabu Search mejora notablemente los resultados en el problema de coloreo de grafos.
Es fundamental para el buen funcionamiento de estos algoritmos:a.- El mantenimiento (explícito) de una población diversa.b.- El diseño de un 'buen' operador de crossover, basado en particiones de vértices en clases color (y NO en asignación de
colores a vértices)
IntroducciónAlgoritmosResultadosConclusiones
Conclusiones