Clustering Search - Laboratório Associado de Computação e ...

CAP 254CAP 254Otimização CombinatóriaProfessor: Dr. L.A.N. LorenaAssunto: MetaheurísticasAntonio Augusto Chaves

ConteúdoC01 – Simulated Annealing (20/11/07).C02 – Busca Tabu (22/11/07).C03 – Colônia de Formigas (27/11/07).C04 - GRASP e VNS (29/11/07).C05 – Metaheurísticas Híbridas – CS (04/12/07).

Metaheurísticas Híbridas

Introdução• Metaheurísticas têm provado ser uma ferramenta poderosa para resolver deforma aproximada problemas de otimização combinatória na prática.• O termo metaheurística se refere a uma larga classe de algoritmos paraotimização e resolução de problemas.• Existem várias definições para metaheurística:– A metaheuristic is an iterative master process that guides and modifies the operations ofsubordinate heuristics to efficiently produce high quality solutions. It may manipulate acomplete (or incomplete) single solution or a collection of solutions at each iteration. Thesubordinate heuristics may be high (or low) level procedures, or a simple local search, orjust a construction method. [Voβ et al., 1999]– . . . these methods have over time also come to include any procedure for problem solvingthat employs a strategy for overcoming the trap of local optimality in complex solutionspaces, especially those procedures that utilize one or more neighborhood structures as ameans of defining admissible moves to transition from one solution to another, or to build ordestroy solutions in constructive and destructive processes. [Glover e Kochenberger, 2003]

Introdução• Simulated annealing, tabu search, algoritmos evolutivos (algoritmo genético,estratégia evolutiva, etc), ant colony optimization, scatter search, pathrelinking, greedy randomized adaptive search procedure (GRASP), multi-startand iterated local search, variable neighborhood search (VNS) são geralmentelistados como exemplos de metaheurísticas clássicas, possuindo seuspróprios históricos e seguindo diferentes paradigmas e filosofias.• Especialmente nos últimos anos um grande número de algoritmos reportadosna literatura não seguem puramente os conceitos de uma únicametaheurística clássica, mas combinam várias idéias, algumas vezes até forado campo das metaheurísticas. Essas abordagens são tradicionalmentereferenciadas como metaheurísticas híbridas.

Motivação• A motivação por trás da hibridização de diferentes metaheurísticasnormalmente é obter sistemas com performance melhor que explorem e unamvantagens das estratégias puras aplicadas individualmente.• Prova do sucesso das metaheurísticas híbridas são as inúmeras aplicaçõesencontradas na literatura e também vários eventos específicos na área:– International Workshop on Hybrid Metaheuristics– Hybrid Metaheuristics: International Workshop– International Workshop on Hybrid Artificial Intelligence Systems• Qual a melhor metaheurística?Não existe até hoje uma estratégia de otimização a qual seja globalmentemelhor que todas as outras.• Na realidade, hoje parece que escolher uma abordagem híbrida adequada édeterminante para alcançar o melhor desempenho na resolução da maioriados problemas difíceis.

Algoritmos de OtimizaçãoAlgoritmos de OtimizaçãoAlgoritmosExatosHeurísticasBranch andboundProgramaçãoDinâmica A*HeurísticasespecíficasMetaheurísticasAlgoritmoGenéticoSimulatedAnnealingBusca Tabu•Metaheurísticas:– Solução única: Simulated Annealing, Busca Tabu (Tabu Search), GRASP, VNS...– População: Algoritmos Evolutivos, Scartter Search, Colônia de Formigas

Metaheurísticas Híbridas• O que hibridizar, ou seja, quais tipos de algoritmos?• Podemos combinar:(a) Diferentes metaheurísticas(b) Metaheurísticas com algoritmos específicos para o problema em foco(c) Metaheurísticas com outras técnicas de Pesquisa Operacional e/ou InteligênciaArtificial• As metaheurísticas híbridas podem ser classificadas de acordo com algumascaracterísticas [Raidl, 2006]• Nível de hibridização:– High-level: mantém a identidade individual dos algoritmos originais que cooperampor meio de uma interface bem definida;– Low-level: algoritmos dependem fortemente um do outro – os componentesindividuais dos algoritmos são trocados;

Metaheurísticas Híbridas• Ordem de execução:– Seqüencial: um algoritmo é executado depois o outro, e só é passada informaçãoem uma direção;– Intercalado: a cada iteração de um algoritmo, o outro é executado;– Paralelo: os algoritmos são executados em paralelo e a informação pode serpassada em qualquer direção.• Estratégia de Controle:– Integrada: um algoritmo é considerado um subordinado, ou seja, componenteembutido de um outro algoritmo;– Colaborada: algoritmos trocam informação, mas não são partes um do outro.• Importante: Quando aplicar um método de intensificação no processo debusca?

Clustering Search (CS)

Clustering Search (CS)• Evolutionary Clustering Search (ECS)Proposto por A.C.M. Oliveira e L.A.N. Lorena em 2004• Principais Referências:A. C. M. Oliveira and L. A. N. Lorena. Detecting promising areasby evolutionary clustering search. Advances in Artificial Intelligence.Springer Lecture Notes in Artificial Intelligence Series, p. 385–394(2004).A. C. M. Oliveira. Algoritmos Evolutivos Híbridos com Detecção deRegiões Promissoras em Espaços de Busca Contínuos e Discretos.Tese de Doutorado, INPE (2004).A.C.M. Oliveira and L.A.N. Lorena: Hybrid evolutionary algorithms andclustering search. In Grosan, C., Abraham, A., Ishibuchi, H., eds.:Hybrid Evolutionary Systems - Studies in Computational Intelligence.Springer SCI Series (2007) 81–102

Clustering Search (CS)• Metaheurística Híbridametaheurísticametaheurística +métodos de busca localmétodos exatos• Diferencial do CS:aplicar busca local somente em regiões supostamente promissoras,detectadas por meio de um processo de agrupamento de soluções.• Objetivo do CS:melhorar o processo de convergência associado a uma diminuição no esforçocomputacional em virtude do emprego mais racional dos métodos busca local.

Clustering Search (CS)BeginClustering ProcessCreateClusterscenter ofclustersLSSimSMpromising cluster?Stop criterion?ICAMEndLegend:CS flowClusters update flowSM – search metaheuristicIC – iterative clusteringAM – analyser moduleLS – local search


Clustering Search (CS)• Criar Clusters:– Aleatoriamente– Problema da Diversidade MáximaDado um conjunto N com n elementos, selecionar um subconjunto M ⊂ N de formatal que os elementos de M possuam a maior diversidade possível entre eles1) Gerar um número grande de soluções iniciais aleatoriamente2) Determinar quais serão os NC centros de clusters do CS



Clustering Search (CS)• Processo de Assimilação:– Assimilação Simples– Assimilação por Caminho– Assimilação por Recombinação



Clustering Search (CS)procedimento CSCriar os clusters iniciais aleatoriamente//componente SMenquanto (critério de parada não satisfeito) façagerar uma solução através da metaheurística escolhida//componente ICcalcular a distância da solução para cada um dos clustersse (solução NÃO for similar a algum cluster e número de clusters < NC) façagerar um novo clusteratribuir a solução ao centro do novo clustersenãoinserir a solução no cluster similar mais recentecausar uma perturbação no centro do cluster ativado (assimilação)//componente AManalisar a densidade dos clusters, descobrindo possíveis clusters promissoresse (existir clusters que não estejam sendo ativados) façaeliminar clusters não ativos//componente LSaplicar um método de busca local nos centros dos clusters promissoresfim-enquantofim-procedimento

Aplicações do CS

TSPP• Problema do Caixeiro Viajante (Traveling Salesman Problem – TSP)– otimizar a seqüência de visitas a clientes– todos clientes precisam ser visitados• Problemas do Caixeiro Viajante com Lucros (Traveling SalesmanProblem with Profits – TSPP)– para cada vértice existe associado um prêmio quando a visita acontecer– cada aresta possui um custo de deslocamento– objetivo: determinar um circuito elementar, levando em consideração o prêmiocoletado e os custos de deslocamento– os diferentes problemas que formam os TSPP surgem das diferentes maneiras queexistem para tratar os dois objetivos. tratar separadamente combinar na função objetivo definir o custo de deslocamento como uma restrição definir prêmio como uma restrição

TSPP• PCV com Coleta de Prêmios (Prize-Collecting TSP – PCTSP)min∑∑v ∈Vv ∈Vijcv vijxv vij+∑v ∈Viγvi(1 −yvi),sujeito à∑v ∈Vipviyvi≥pminγ ip i

TSPP• Problema de Rotas com Lucro (Profitable Tour Problem – PTP)min∑∑v ∈Vv ∈Vij∑c x + γ (1 − y )v vijv vijv ∈Viviviγ i

TSPP• Problema do Caixeiro Viajante com Quota (Quota TSP – QTSP)min∑ ∑v ∈Vv ∈Vijcv vijxv vij,sujeito à∑v ∈Vipviyvi≥pminp i

CS aplicado aos TSPP – componente SMFase de ConstruçãoFase de Busca Local (VNS)procedimento GRASP/VNSpara (número de iterações não satisfeito) faças = ∅enquanto (solução não construída) façaproduzir Lista de Candidatos (C) v(k)= cij+ γkLCR = C * αe = selecionar elemento aleatoriamente(LCR)s = s ∪ {e}atualizar lista de Candidatos(C)fim-enquantok max= número de vizinhançasenquanto (critério de parada não satisfeito ) façak ← 1enquanto (k ≤ k max)gerar um vizinho s‘ qualquer na vizinhança N k (s)s'' = Aplicar VND em s'se (s'' for melhor que s) faças ← s''k ← 1senãok ← k + 1fim-enquantofim-enquantofim-parafim-GRASP/VNS− cik− ckj

CS aplicado aos TSPP – componente SMFase de ConstruçãoFase de Busca Local (VNS)procedimento GRASP/VNSpara (número de iterações não satisfeito) faças = ∅enquanto (solução não construída) façaproduzir Lista de Candidatos (C) v(k)= cij+ γkLCR = C * αe = selecionar elemento aleatoriamente(LCR)s = s ∪ {e}atualizar lista de Candidatos(C)fim-enquantok max= número de vizinhançasenquanto (critério de parada não satisfeito ) façak ← 1enquanto (k ≤ k max)gerar um vizinho s‘ qualquer na vizinhança N k (s)s'' = Aplicar VND em s'se (s'' for melhor que s) faças ← s''k ← 1senãok ← k + 1fim-enquantofim-enquantofim-parafim-GRASP/VNS− cik− ckj1. Inserir um vértice2. Retirar um vértice3. Trocar dois vértices4. Inserir dois vértice5. Retirar dois vértice6. Trocar quatro vértices7. Inserir três vértice8. Retirar três vértice9. Trocar seis vértices

CS aplicado aos TSPP – componente SMFase de ConstruçãoFase de Busca Local (VNS)procedimento GRASP/VNSpara (número de iterações não satisfeito) faças = ∅enquanto (solução não construída) façaproduzir Lista de Candidatos (C) v(k)= cij+ γkLCR = C * αe = selecionar elemento aleatoriamente(LCR)s = s ∪ {e}atualizar lista de Candidatos(C)fim-enquantok max= número de vizinhançasenquanto (critério de parada não satisfeito ) façak ← 1enquanto (k ≤ k max)gerar um vizinho s‘ qualquer na vizinhança N k (s)s'' = Aplicar VND em s'se (s'' for melhor que s) faça 1. SeqAdds ← s''2. AddDropk ← 13. SeqDropsenãok ← k + 1fim-enquantofim-enquantofim-parafim-GRASP/VNS− cik− ckj

CS aplicado aos TSPP – componente SMFase de ConstruçãoFase de Busca Local (VNS)procedimento GRASP/VNSpara (número de iterações não satisfeito) faças = ∅enquanto (solução não construída) façaproduzir Lista de Candidatos (C)LCR = C * αe = selecionar elemento aleatoriamente(LCR)s = s ∪ {e}atualizar lista de Candidatos(C)fim-enquantok max= número de vizinhançasenquanto (critério de parada não satisfeito ) façak ← 1enquanto (k ≤ k max)gerar um vizinho s‘ qualquer na vizinhança N k (s)s'' = Aplicar VND em s'se (s'' for melhor que s) faças ← s''k ← 1senãok ← k + 1fim-enquantofim-enquantofim-parafim-GRASP/VNSv(k)= c + γ − cijkik− ckjSolução s’’ é enviadapara o componente AI

CS aplicado aos TSPP – componente IC• Medida de distância entre a solução gerada pelo GRASP/VNS e o centro do cluster:– Número de arestas diferentes• Processo de assimilação por caminho: path-relinking0 -4 1 3 -20 -4 2 3 1-4 -1 0 3 -21 -4 0 3 -2-4 -1 2 3 00 1 2 3 -4 0 -1 2 3 -4(inicial) 1 -4 2 3 0(guia)1 0 2 3 -40 -1 2 3 -41 -2 0 3 -4

CS aplicado aos TSPP – componente AM• É executado toda vez que uma solução for atribuída a um cluster• Função: verificar se o cluster já pode ser considerado promissor• Cluster Populoso:NSλt≥ PD.Ct• Outras funções:– Esfriamento de todos os clusters que foram ativados– Eliminar os clusters pouco populosos

CS aplicado aos TSPP – componente LS• Heurística 2-Opt• Objetivo: realizar uma busca local no centro dos clusters consideradospromissores1 2 3 4 5 611 2 5 4 3 61626253534 4

Resultados Computacionais TSPP• Ambiente computacional– Linguagem C++ (C++ Builder 6.0)– PC Pentium 4 3.02 GHZ e memória de 512 MB• Não existe uma biblioteca pública de instâncias para os TSPP.• Instâncias geradas aleatoriamente com distribuição uniforme:– distância entre os vértices: c ij∈[50, 1000]– prêmio associado à cada vértice: p i∈[1, 100]– penalidade associada à cada vértice: γ i∈[1,750]– prêmio mínimo a ser coletado: 0,75* ∑i∈Vp i

Resultados Computacionais (PCTSP)CPLEXProb. n MS TE (s) MS SM TE (s) MS SM TE (s)v10 11 1765 0,11 1765 1765 0,02 1765 1765 0,05v20 21 2302 2,65 2302 2302 0,35 2355 2403 0,27v30a 31 3582 4,89 3582 3582 0,82 3734 3899 6,00v30b 31 2515 6,18 2515 2515 3,14 2647 2771 5,93v30c 31 3236 20,24 3236 3242 1,54 3301 3356 6,04v50a 51 4328 1032,79 4328 4335 9,78 4752 4900 13,41v50b 51 3872 634,01 3872 3878 6,40 4097 4383 35,90v100a 101 6762 86390,66 6785 6822 108,55 8302 8476 52,69v100b 101 6760 85002,51 6782 6844 216,16 7890 8367 87,78v250a 251 - - 14483 14483 713,12 18306 18510 364,16v250b 251 - - 14078 14078 701,58 17871 18191 393,47v500a 501 - - 27189 27230 2880,03 34437 34771 463,02v500b 501 - - 28133 28334 2080,89 34841 35296 529,72CSGRASP/VNS

Resultados Computacionais (QTSP)CPLEXProb. n MS TE (s) MS SM TE (s) MS SM TE (s)v10 11 1755 0,96 1755 1755 0,01 1755 1755 0,07v20 21 1439 5,13 1439 1439 1,33 1439 1469 1,24v30a 31 2074 29,56 2074 2075 3,09 2182 2268 5,65v30b 31 1552 15,40 1552 1552 6,62 1553 1772 4,01v30c 31 1966 30,23 1966 2004 2,49 2086 2177 6,20v50a 51 2438 372,09 2438 2046 17,76 2912 2956 11,31v50b 51 2192 1231,20 2192 2218 35,90 2548 2600 24,06v100a 101 3770 46331,41 3862 3930 84,94 4777 4811 68,15v100b 101 3935 45615,01 4030 4092 126,07 5092 5191 44,58v250a 251 - - 8253 8342 518,82 10309 10626 295,34v250b 251 - - 8336 8508 549,76 10701 10865 313,50v500a 501 - - 15367 15780 2207,11 19510 19717 799,72v500b 501 - - 15211 15757 1526,38 19494 19567 750,24CSGRASP/VNS

Resultados Computacionais (PTP)CPLEXProb. n MS TE (s) MS SM TE (s) MS SM TE (s)v10 11 1558 0,29 1558 1558 0,001 1558 1558 0,00v20 21 2302 2,22 2302 2302 0,94 2302 2369 2,24v30a 31 3582 3,94 3582 3582 1,89 3695 3871 9,48v30b 31 2515 6,08 2515 2515 1,92 2571 2617 10,09v30c 31 3236 16,30 3236 3242 2,22 3345 3408 6,55v50a 51 4328 1261,03 4328 4338 22,97 4739 4852 19,33v50b 51 3872 910,37 3872 3877 12,62 4219 4371 18,51v100a 101 6762 197783,19 6784 6799 125,96 8191 8344 69,78v100b 101 6760 55953,18 6826 6864 150,05 8212 8342 55,91v250a 251 - - 14493 14584 1124,62 17970 18432 733,19v250b 251 - - 14055 14119 901,94 17302 17786 637,00v500a 501 - - 27316 27564 2387,02 33727 34157 1401,86v500b 501 - - 27890 27944 2345,02 34757 35044 1220,97CSGRASP/VNS

CPMP• Problemas de localização de facilidades:– Problemas de cobertura– Problemas de localização de medianas• Problema de p-Medianas– Localizar p medianas em um dado espaço, satisfazendo n pontos de demanda detal forma que a soma total das distâncias entre cada ponto de demanda e suamediana mais próxima seja minimizada• Problema de p-Medianas Capacitado (Capacitated p-Median Problem -CPMP)– Generalização do Problema de p-Mediana– Define-se uma capacidade fixa para cada mediana candidata e uma demandapara cada ponto de atendimento, sendo que, a soma das demandas de todos ospontos alocados a uma mediana não pode exceder sua capacidade– Problema NP-difícil

CPMPEXEMPLO DE UMA SOLUÇÃO DO CPMP

CS aplicado ao CPMP – componente SMprocedimento SACriar Solução Inicial(sol)IterT = 0α = 0,95T = T 0enquanto (T > 0.0001)enquanto (IterT < SAmax)IterT = IterT + 1Gerar um vizinho (sol’) aleatoriamente na vizinhança N k (sol)∆ = f (sol’) – f (sol)se (∆ < 0)sol = sol’senãoseja x ∈ [0,1]se (x < e -∆/T )sol = sol’fim-enquantoT = T x αIterT = 0fim-enquantofim-procedimento

CS aplicado ao CPMP – componente SMprocedimento SACriar Solução Inicial(sol)IterT = 0atendido por elaα = 0,95T = T 0enquanto (T > 0.0001)enquanto (IterT < SAmax)qualquerIterT = IterT + 1Gerar um vizinho (sol’) aleatoriamente na vizinhança N k (sol)∆ = f (sol’) – f (sol)se (∆ < 0)sol = sol’senãoseja x ∈ [0,1]se (x < e -∆/T )sol = sol’fim-enquantoT = T x αIterT = 0fim-enquantofim-procedimento1) Trocar a alocação de dois pontos2) Trocar uma mediana por um ponto3) Retirar um ponto de uma medianae adicionar em outra mediana4) Trocar uma mediana por um ponto

CS aplicado ao CPMP – componente SMprocedimento SACriar Solução Inicial(sol)IterT = 0α = 0,95T = T 0enquanto (T > 0.0001)enquanto (IterT < SAmax)IterT = IterT + 1Gerar um vizinho (sol’) aleatoriamente na vizinhança N k (sol)∆ = f (sol’) – f (sol)se (∆ < 0)sol = sol’senãoseja x ∈ [0,1]se (x < e -∆/T )sol = sol’fim-enquantoT = T x αIterT = 0fim-enquantofim-procedimentoA cada 100 vizinhosgerados, a solução sol’é enviada para ocomponente AI

CS aplicado aos CPMP – componente IC• Medida de distância entre a solução gerada pelo SA e o centro do cluster:– número de pontos atribuídos para medianas diferentes• Processo de assimilação por caminho: path-relinking20 7 3 11 420 7 13 11 4Medianas15 2 3 11 415 7 3 11 4 15 2 13 11 420 7 13 11 9 20 11 2 13 9(inicial) 15 7 13 11 4(guia)Medianas15 7 3 11 915 7 13 11 915 2 13 11 9

CS aplicado aos CPMP – componente AA• É executado toda vez que uma solução for atribuída a um cluster• Função: verificar se o cluster já pode ser considerado promissor• Cluster Populoso:NSλt≥ PD.Ct• Outras funções:– Esfriamento de todos os clusters que foram ativados– Eliminar os clusters pouco populosos

CS aplicado aos CPMP – componente AO• Heurística de Localização-Alocação (LA)• Objetivo: realizar uma busca local no centro dos clusters consideradospromissores

CS aplicado aos CPMP – componente AOmediana ponto de demandaLA – Passo 2Centro do clusterLA – Passo 3LA – Passo 1

Resultados Computacionais CPMP• Ambiente computacional– Linguagem C++ (C++ Builder 6.0)– PC Pentium 4 3.02 GHZ e memória de 512 MB• Foram utilizados dois conjuntos de instâncias– Osman e Christofides: 10 problemas (n = 50 e p = 5)10 problemas (n = 100 e p = 10)– Lorena e Senne: problemas com dados reais coletados na cidade de São José dosCampos (6 problemas)

Resultados Computacionais CPMPCSSAID Melhor sol* Tempo* sol Tempo sol* sol Tempo DRp1 713 713 0,02 713,00 2,24 713 721,60 1,56 1,21p2 740 740 0,01 740,00 2,34 740 740,00 1,59 0,00p3 751 751 0,08 751,00 2,29 751 751,60 1,46 0,08p4 651 651 0,03 651,00 2,24 651 651,20 1,52 0,03p5 664 664 0,03 664,00 2,35 664 664,40 1,51 0,06p6 778 778 0,01 778,00 2,35 778 778,00 1,57 0,00p7 787 787 0,01 787,00 2,34 787 788,60 1,55 0,20p8 820 820 0,08 820,00 2,38 821 825,80 1,60 0,71p9 715 715 0,02 715,00 2,36 715 717,80 1,46 0,39p10 829 829 2,09 829,00 2,36 829 833,80 1,58 0,58p11 1006 1006 7,97 1006,00 35,24 1007 1015,40 10,11 0,93p12 966 966 0,05 966,00 49,39 968 970,20 12,74 0,43p13 1026 1026 0,06 1026,00 41,05 1026 1028,80 10,00 0,27p14 982 982 19,80 982,80 39,14 985 997,20 10,35 1,47p15 1091 1091 1,30 1091,00 44,98 1092 1102,60 12,15 1,06p16 954 954 15,94 954,00 36,03 957 960,40 10,37 0,67p17 1034 1034 19,50 1034,20 48,18 1037 1043,00 12,24 0,85p18 1043 1043 18,62 1044,60 46,39 1045 1048,20 11,41 0,34p19 1031 1031 10,17 1031,80 38,56 1034 1042,80 10,09 1,07p20 1005 1005 5,41 1005,40 48,77 1009 1015,20 12,45 0,97sjc1 17288,99 17288,99 0,23 17288,99 22,80 17288,99 17343,96 10,43 0,32sjc2 33270,94 33270,94 13,25 33275,43 120,40 33372,98 33491,75 25,70 0,65sjc3a 45335,16 45335,16 405,50 45337,34 859,09 46746,68 47110,93 52,51 3,91sjc3b 40635,90 40635,90 1626,52 40643,67 1649,41 41551,34 41888,14 54,01 3,06sjc4a 61925,51 61928,72 938,45 62017,51 2601,81 63710,71 64574,92 77,19 4,10sjc4b 52469,96 52531,27 1402,25 52540,67 7233,59 53789,61 54716,58 92,05 4,14

Resultados Computacionais CPMPSS-PR VNS CSID Melhor sol* Tempo sol* Tempo sol* Tempop1 713 713 6 713 0,17 713 2,24p2 740 740 6 740 0,05 740 2,34p3 751 751 6 751 0,19 751 2,29p4 651 651 6 651 0,11 651 2,24p5 664 664 6 664 0,27 664 2,35p6 778 778 6 778 0,11 778 2,35p7 787 787 6 787 0,31 787 2,34p8 820 820 6 820 0,92 820 2,38p9 715 715 6 715 0,13 715 2,36p10 829 829 6 829 0,75 829 2,36p11 1006 1006 60 1006 7,91 1006 35,24p12 966 966 60 966 4,81 966 49,39p13 1026 1026 60 1026 2,17 1026 41,05p14 982 982 60 982 10,33 982 39,14p15 1091 1091 60 1091 10,23 1091 44,98p16 954 954 60 954 4,20 954 36,03p17 1034 1034 60 1034 5,50 1034 48,18p18 1043 1043 60 1043 9,06 1043 46,39p19 1031 1031 60 1031 8,64 1031 38,56p20 1005 1005 60 1005 27,34 1005 48,77sjc1 17288,99 17288,99 60 17288,99 50,50 17288,99 22,72sjc2 33270,94 33293,40 600 33270,94 44,08 33270,94 112,81sjc3a 45335,16 45338,02 2307 45335,16 8580,30 45335,16 940,75sjc3b 40635,90 40635,90 2308 40635,90 2292,86 40635,90 1887,97sjc4a 61925,51 61925,52 6109 61925,51 4221,47 61928,72 2885,11sjc4b 52469,96 52531,46 6106 52469,96 3471,44 52531,27 7626,33

ALWABP• Centros de Trabalho para Deficientes (Sheltered Work Centres for Disabled – SWD)• Simple Assembly Line Balancing Problem (SALBP)– Problema de balanceamento de uma linha de montagem– Conjunto finito de tarefas, cada uma tendo um tempo de execução fixo (independente dotrabalhador que a executa)– Conjunto de relações de precedência, as quais especificam a ordem de execução das tarefas– Todo trabalhador é atribuído para somente uma estação de trabalho– Toda tarefa é atribuída para somente uma estação de trabalho• Assembly Line Worker Assigment and Balancing Problem (ALWABP)(Problema de Atribuição de Trabalhadores e Balanceamento da Linha de Montagem)– Tempo de execução das tarefas pode ser diferente dependendo de qual dos trabalhadoresexecuta a tarefa– Trabalhadores podem ser muito lentos, ou até incapazes, de executar algumas tarefas, masmuito eficientes quando executam outras tarefas– ALWABP-I: minimizar o número de estações de trabalho– ALWABP-II: maximizar a taxa de produção da linha (ou minimizar o tempo de ciclo) para umdado número de estações

ALWABPEstações? ? ? ? ?Rede de Precedência das TarefasTarefa1h145h2-h357h445h5382 3621210111181737101291544450405250562314231815101512151245810 1178121225-12121512201299-121212-108-20814113024293535Tabela de Tempos tarefa/trabalhador

ALWABPRede de Precedência das TarefasEstaçõesTarefa1h145h2-h357h445h538h1=57 h2=602 3h3=49623412744101050111240119528155017h5=35562314231815101512151245810 1178121225-121215122012991011-83012-2412202912835-1435Tempo de Ciclo (C) = 221h4=20Tabela de Tempos tarefa/trabalhador

CS aplicado ao ALWABP – componente SMprocedimento SACriar Solução Inicial(sol)IterT = 0α = 0,95T = T 0enquanto (T > 0.0001)enquanto (IterT < SAmax)IterT = IterT + 1Gerar um vizinho (sol’) aleatoriamente na vizinhança N k (sol)∆ = f (sol’) – f (sol)se (∆ < 0)sol = sol’senãoseja x ∈ [0,1]se (x < e -∆/T )sol = sol’fim-enquantoT = T x αIterT = 0fim-enquantofim-procedimento

CS aplicado ao ALWABP – componente SMprocedimento SACriar Solução Inicial(sol)IterT = 0α = 0,95T = T 0enquanto (T > 0.0001)enquanto (IterT < SAmax)IterT = IterT + 1Gerar um vizinho (sol’) aleatoriamente na vizinhança N k (sol)∆ = f (sol’) – f (sol)se (∆ < 0)sol = sol’senãoseja x ∈ [0,1]se (x < e -∆/T )sol = sol’fim-enquantoT = T x αIterT = 0fim-enquantofim-procedimento1) Trocar dois trabalhadores de estação2) Trocar duas tarefas de estação3) Retirar uma tarefa de uma estaçãoe adicionar em outra estação

CS aplicado ao ALWABP – componente SMprocedimento SACriar Solução Inicial(sol)IterT = 0α = 0,95T = T 0enquanto (T > 0.0001)enquanto (IterT < SAmax)IterT = IterT + 1Gerar um vizinho (sol’) aleatoriamente na vizinhança N k (sol)∆ = f (sol’) – f (sol)se (∆ < 0)sol = sol’senãoseja x ∈ [0,1]se (x < e -∆/T )sol = sol’fim-enquantoT = T x αIterT = 0fim-enquantofim-procedimentoA cada 100 vizinhosgerados, a solução sol’é enviada para ocomponente AI

CS aplicado ao ALWABP – componente IC• Medida de distância entre a solução gerada pelo SA e o centro do cluster:– número de tarefas atribuídas para estações diferentes• Processo de assimilação por caminho: path-relinking1 3 4 5 21 3 2 5 4TrabalhadorEstação3 4 1 5 21 2 3 4 5 1 2 3 4 5 Trabalhador3 1 4 5 23 4 2 5 11 4 2 5 3 1 4 2 5 3 Estação(inicial) 3 1 2 5 4(guia)4 1 2 5 34 1 2 5 32 1 4 5 3

CS aplicado ao ALWABP – componente AM• É executado toda vez que uma solução for atribuída a um cluster• Função: verificar se o cluster já pode ser considerado promissor• Cluster Populoso:NSλt≥ PD.Ct• Outras funções:– Esfriamento de todos os clusters que foram ativados– Eliminar os clusters pouco populosos

CS aplicado ao ALWABP – componente LS• Objetivo: realizar uma busca local no centro dos clusters consideradospromissores• Heurística SWAP– examinar todos as possíveis trocas de duas tarefas que estão atribuídas àdiferentes estações. A melhor troca é realizada e o processo é repetidonovamente até que não ocorra mais melhora• Heurística SHIFT– examinar todas as relações de tarefas e estações, removendo uma tarefade uma estação e inserindo esta em uma outra estação. O melhormovimento é realizado e todo o processo é repetido novamente até nãoocorrer mais melhora

Resultados Computacionais ALWABP• Ambiente computacional– Linguagem C++ (C++ Builder 6.0)– PC Pentium 4 3.02 GHZ e memória de 512 MB• Foram utilizados quatro conjuntos de instânciasTamanhoOrder StrengthHesk ia LOW (28 tarefas) LOW (OS=22.49)Roszieg LOW (25 tarefas) HIGH (OS=71.67)Wee-Mag HIGH (75 tarefas) LOW (OS=22.67)Tonge HIGH (70 tarefas) HIGH (OS=59.42)• Para cada instância varia-se:– Relação entre número de tarefas e trabalhadores (tamanho da matriz tarefatrabalhador)– Variabilidade dos tempos de execução das tarefas para cada trabalhador (L1 e H3)– Porcentagem de incompatibilidade tarefa-trabalhador (I10 e I20)

Resultados Computacionais ALWABPRosziegHeskiaCPLEXCSNrT Var Inc Sol Tempo Sol Tempo4647L1H3L1H3L1H3L1H3I10 20,1 4,72 20,1 3,76I20 31,5 3,77 31,5 3,76I10 28,1 5,46 28,1 3,93I20 28,0 4,27 28,0 4,29I10 9,7 332,21 9,7 4,68I20 11,0 281,03 11,0 4,83I10 16,0 390,07 16,0 4,75I20 15,1 686,75 15,1 4,70I10 102,3 6,56 102,3 4,63I20 122,6 5,78 122,6 4,67I10 172,5 6,70 172,5 4,81I20 171,2 7,30 171,2 4,81I10 34,9 177,36 34,9 5,55I20 42,6 216,38 42,6 5,29I10 75,2 260,93 75,2 5,53I20 67,2 341,83 67,2 5,73

Publicações1) CORREA, F. A.; CHAVES, A. A.; LORENA, L. A. N. - Hybrid Heuristics for the Probabilistic Maximal CoveringLocation-Allocation Problem. Operational Research: An International Journal, 2007.2) CHAVES, A. A.; CORREA, F. A.; LORENA, L. A. N. - Clustering Search Heuristic for the Capacitated p-MedianProblem. Advances in Soft Computing, v. 44, p. 136-143, 2007.3) CHAVES, A. A.; CORREA, F. A.; LORENA, L. A. N. - Clustering Search Heuristic for the Capacitated p-MedianProblem. In: HAIS 07 2nd International Workshop on Hybrid Artificial Intelligence Systems, 2007, Salamanca.Proceedings of HAIS, 2007.4) CHAVES, A. A.; Cristobal, M.; LORENA, L. A. N. - Clustering Search Approach for the Assembly Line WorkerAssignment and Balancing Problem. In: ICC&IE'2007 37th International Conference on Computers and IndustrialEngineering, 2007, Alexandria. Computers and Industrial Engineering, 2007.5) CORREA, F. A.; CHAVES, A. A.; LORENA, L. A. N. - Heurística Híbrida com Detecção de RegiõesPromissoras Aplicada ao Problema Probabilístico de Localização-Alocação de Máxima Cobertura. In: XXXIXSBPO Simpósio Brasileiro de Pesquisa Operacional, 2007, Fortaleza. Anais do SBPO, 2007.6) CHAVES, A. A.; LORENA, L. A. N. - Aplicação do Algoritmo Clustering Search aos Traveling SalesmanProblems with Profits. In: XXXIX SBPO Simpósio Brasileiro de Pesquisa Operacional, 2007, Fortaleza. Anais doSBPO, 2007.7) CHAVES, A. A.; LORENA, L. A. N. - A Preprocessing Phase for the Evolutionary Clustering Search. In: IWorkshop on Computational Intelligence (WCI), 2006, Ribeirão Preto. In International Joint Conference 2006, 2006.8) CHAVES, A. A.; LORENA, L. A. N. - Hybrid Algorithms with Detection of Promising Areas for the PrizeCollecting Travelling Salesman Problem. In: HIS'05 Fifth International Conference on Hybrid Intelligent Systems,2005, Rio de Janeiro. HIS 2005. California : IEEE Computer Society, 2005. p. 49-54.9) CHAVES, A. A.; LORENA, L. A. N. - Algoritmos Híbridos para uma Generalização do Problema do CaixeiroViajante. In: Simpósio de Pesquisa Operacional e Logística da Marinha (SPOLM), 2005, Rio de Janeiro. Anais doSPOLM, 2005.

Outras Aplicações do CS• Oliveira A. C. M. and Lorena, L. A. N.Pattern Sequencing Problems by Clustering Search. Jaime Simão Sichman, Helder Coelhoand Solange Oliveira Rezende (Eds.). Springer Lecture Notes in Artificial Intelligence Series vol.4140, pp. 218 - 227, 2006• Ribeiro Filho, G.; Nagano, M. S. and Lorena, L. A. N.Evolutionary Clustering Search for Flowtime Minimization in Permutation Flow Shop. T.Bartz-Beielstein et al. (Eds.): HM 2007, LNCS-Lecture Notes in Computer Science. 4771,Springer, pp. 69–81, 2007• Ribeiro Filho, G.; Nagano, M. S. and Lorena, L. A. N.Hybrid Evolutionary Algorithm for Flowtime Minimisation in No-Wait Flowshop Scheduling.A. Gelbukh and A.F. Kuri Morales (Eds.): MICAI 2007, LNAI 4827, pp. 1099–1109, 2007. Springer-Verlag Berlin Heidelberg 2007• Biajoli, F. L. and Lorena, L. A. N.Clustering Search Approach for the TravelingTournament Problem. A. Gelbukh and A.F. KuriMorales (Eds.): MICAI 2007, LNAI 4827, pp. 83-93, 2007. Springer-Verlag Berlin Heidelberg 2007• Correa, F. A.; Chaves, A. A. and Lorena, L. A. N.Hybrid heuristics for the probabilistic maximal covering location-allocation problem.Operational Research Journal, 2007

Considerações Finais• Clustering Search (CS): uma nova maneira de combinar metaheurísticas emétodos de busca local de forma eficiente• Os resultados obtidos mostram o potencial do CS para resolução deproblemas de Otimização Combinatória• Objetivo:– Colocar a disposição uma nova técnica para resolução de problemas de otimizaçãoque necessitem ser resolvidos de forma aproximada e em um tempo computacionalcompetitivo

Referências• Voß S., Martello, S., Osman, I.H., Roucairo, C.: Meta-Heuristics: Andvancesand Trends in Local Search Paradigms for Optimization. Kluwer, Boston(1999)• Glover, F., Kochenberger, G.A.: Handbook of Metaheuristics. Kluwer (2003)• Raidl, G.L.: A Unified View on Hybrid Metaheuristics. Lecture Notes inComputer Science, Book: Hybrid Metaheuristics, volume 4030, pages 1-12(2006)

ConteúdoC01 – Simulated Annealing (20/11/07).C02 – Busca Tabu (22/11/07).C03 – Colônia de Formigas (27/11/07).C04 - GRASP e VNS (29/11/07).C05 – Metaheurísticas Híbridas – CS (04/12/07).

Clustering Search - Laboratório Associado de Computação e ...

Transforme seus PDFs em revista digital e aumente sua receita!

Delete template?

Save as template ?