Slides Hill Climbing-2022 1

Hill-Climbing Componentes do Hill-Climbing Para desenvolver um algoritmo Hill-Climbing, precisamos pensar nos seguintes componentes: ● Forma de representação de uma solução qualquer ● Método para geração de soluções aleatórias ● Método de avaliação da qualidade da solução ● Mecanismo de exploração da vizinhança ● Critério de parada do algoritmo Nas aulas anteriores discutimos como aplicar o Hill-Climbing ao TSP. Nesta aula vamos aplicar o Hill-Climbing ao Problema de Designação Problema de Designação Visão Geral do Problema Considere um conjunto de m recursos que precisam realizar n tarefas. Há um custo (ou um lucro) caso cada recurso realize cada tarefa, denotado como uma matriz de custos cij (ou lucros pij) O objetivo é designar recursos às tarefas de forma a minimizar os custos totais (ou maximizar os lucros totais) Cada recurso só pode fazer uma tarefa e cada tarefa só pode ser realizada por um recurso! Problema de Designação Exemplo Uma empresa precisa designar projetos às equipes de trabalho disponíveis. Os custos para realizar cada projeto variam de acordo com a equipe. A tabela a seguir mostra um exemplo de instância do problema: Projetos Equipes P1 P2 P3 P4 E1 2250 4040 4028 2700 E2 2700 4752 4150 3600 E3 2650 3960 3610 3000 E4 2958 5720 5286 3978 E5 2805 4708 4473 3234 E6 2760 4464 4606 3924 Problema de Designação Representação da Solução Vamos representar a solução como um vetor em que a posição do vetor representa o Projeto e o conteúdo representa a Equipe designada: Se houver mais equipes que projetos, nem todas as equipes aparecerão no vetor. Se houver mais projetos que equipes, usaremos o número 0 (zero) para representar que o projeto não possui equipe designada. Posição 0 1 2 3 Projeto P1 P2 P3 P4 Solução 2 3 5 4 Problema de Designação Geração de Soluções Iniciais Se a quantidade de equipes for maior ou igual à quantidade de projetos: 1. Ordenar aleatoriamente um vetor com os índices das equipes 2. Designar projetos às equipes nessa ordem, até que acabem os projetos Se a quantidade de equipes for menor que a quantidade de projetos: 1) Criar um vetor com os códigos das equipes 2) Complementar o vetor com zeros, de forma que o vetor de equipes tenha o mesmo tamanho que a quantidade de projetos 3) Ordenar aleatoriamente o vetor de equipes e designar os projetos às equipes nessa ordem Problema de Designação Avaliação da Solução Dada uma solução, sua avaliação será feita calculando o custo total da solução utilizando a matriz de custos: A soma total dos custos da designação é 15.111, sendo esta a avaliação da solução. Projeto P1 P2 P3 P4 Solução 2 3 5 4 Custo 2700 3960 4473 3978 Total 15111 Problema de Designação Estrutura de Vizinhança Neste problema podemos usar várias estruturas de vizinhança. Por exemplo, poderíamos usar a estrutura de vizinhança que troca todos os pares de valores no vetor de solução: Solução 2 3 5 4 Vizinhança 3 2 5 4 5 3 3 4 4 3 5 2 2 5 3 4 2 4 5 3 2 3 4 5 Problema de Designação Estrutura de Vizinhança – Remoção/Inserção Outro tipo de vizinhança comumente usado em problemas de otimização combinatória é a “Remoção” de um ponto e “Inserção” em outra posição Exemplo: Considere a solução candidata abaixo Um dos possíveis vizinhos poderia ser a remoção do ponto 1 e inserção na posição 4, que resultaria no seguinte vizinho: Candidata A B C D E F Candidata B C D A E F O ponto na posição 1 foi removido e inserido na posição 4 Vizinhança completa Tira Insere Vizinho 1 2 B A C D E F 1 3 B C A D E F 1 4 B C D A E F 1 5 B C D E A F 1 6 B C D E F A 2 1 B A C D E F 2 3 A C B D E F 2 4 A C D B E F 2 5 A C D E B F 2 6 A C D E F B 3 1 C A B D E F 3 2 A C B D E F 3 4 A B D C E F 3 5 A B D E C F 3 6 A B D E F C Tira Insere Vizinho 4 1 D A B C E F 4 2 A D B C E F 4 3 A B D C E F 4 5 A B C E D F 4 6 A B C E F D 5 1 E A B C D F 5 2 A E B C D F 5 3 A B E C D F 5 4 A B C E D F 5 6 A B C D F E 6 1 F A B C D E 6 2 A F B C D E 6 3 A B F C D E 6 4 A B C F D E 6 5 A B C D F E Problema de Designação Best-Improvement (Maior Melhoria) Até o momento, sempre usamos a estratégia best-improvement, pois geramos todos os vizinhos e retornamos o melhor First-Improvement (Primeira Melhoria) Neste algoritmo vamos implementar a versão first-improvement da troca de todos os pares Com esta abordagem, a geração de vizinhos é finalizada assim que um vizinho melhor que a solução candidata é encontrada Isso ajuda a reduzir a quantidade de vizinhos gerados e torna o algoritmo mais rápido! Hill Climbing Revisão do Conceito O algoritmo Hill-Climbing parte de uma solução inicial e utiliza estruturas de vizinhança para encontrar soluções melhores Isso é feito até que um ótimo local seja encontrado, ou seja, quando a estrutura de vizinhança parar de gerar soluções melhores Após encontrar o ótimo local, uma nova solução inicial é gerada e o processo é reiniciado Após diveras iterações (geração de soluções iniciais e buscas pelos ótimos locais), a melhor solução de todas é retornada Exemplo de Iteração do Hill Climbing Uma solução inicial é gerada aleatoriamente. A busca pela vizinhança consiste na geração dos vizinhos e a escolha do melhor dentre todos os vizinhos. Obs: Problema de minimização! Vizinhança Melhor Vizinho Solução inicial Exemplo de Iteração do Hill Climbing Uma solução inicial é gerada aleatoriamente. A busca pela vizinhança consiste na geração dos vizinhos e a escolha do melhor dentre todos os vizinhos. Obs: Problema de minimização! Vizinhança Melhor Vizinho Exemplo de Iteração do Hill Climbing A iteração do Hill-Climbing é finalizada quando chegamos ao ótimo local. O ótimo local é uma solução cuja vizinhança não contém nenhuma solução melhor que ela mesma. Obs: Problema de minimização! Vizinhança Melhor Vizinho Ótimo local, pois não há vizinhos melhores! Hill Climbing Componentes do Hill-Climbing Para desenvolver um algoritmo Hill-Climbing, precisamos pensar nos seguintes componentes: ● Forma de representação de uma solução qualquer ● Método para geração de soluções aleatórias ● Método de avaliação da qualidade da solução ● Mecanismo de exploração da vizinhança ● Critério de parada do algoritmo Lembre-se que na aula passada já fizemos um algoritmo Hill-Climbing, mas ele não deu resultados muito bons; hoje vamos melhorá-lo! Hill Climbing Representação de uma Solução Para o TSP, vamos representar uma solução como uma permutação dos pontos a serem visitados. Por exemplo, para um problems de 8 pontos: Geração de Soluções Aleatórias Na aula passada geramos soluções aleatórias escolhendo, de forma totalmente randomizada, a ordem dos pontos Esse método foi uma das razões de nosso algoritmo ter obtido maus resultados! 3 – 8 – 1 – 5 – 7 – 2 – 4 – 6 Hill Climbing Novo Algoritmo para Geração de Soluções Aleatórias Neste novo algoritmo (VMP Estocástico) vamos construir soluções aleatórias, porém dando maiores probabilidades aos pontos mais promissores: // Gera uma solução aleatória pelo VMP Estocástico Função GeraSolucaoVMPEstocastico (P) solucao(1) = Escolhe aleatoriamente um ponto em P Para i = 2 até qtdPontos(P) vetProb = CalculaVetProb(P, solução(i-1)) r = Número aleatório entre 0 e 1 solução(i) = EscolhePonto(vetPtob, r) Fim Retorna solucao Fim Hill Climbing Cálculo do Vetor de Probabilidades Vamos considerar a seguinte matriz de distâncias em nosso exemplo: De/Para 1 2 3 4 5 6 7 8 9 10 1 0 877 1015 201 971 647 202 175 857 802 2 877 0 215 689 145 231 789 749 91 210 3 1015 215 0 843 296 397 892 866 303 425 4 201 689 843 0 775 459 248 182 663 602 5 971 145 296 775 0 337 904 859 115 197 6 647 231 397 459 337 0 567 523 223 226 7 202 789 892 248 904 567 0 67 789 762 8 175 749 866 182 859 523 67 0 743 709 9 857 91 303 663 115 223 789 743 0 123 10 802 210 425 602 197 226 762 709 123 0 Hill Climbing Cálculo do Vetor de Probabilidades O VMP estocástico escolhe constrói uma solução escolhendo o próximo ponto aleatoriamente, mas dando probabilidades maiores de escolha aos pontos mais próximos do último ponto adicionado à solução Exemplo: Considere que estamos construindo uma solução e iniciamos pelo Ponto 4. A seguir temos a distância do Ponto 4 a todos os demais pontos: Como podemos dividir a probabilidade de escolha entre todos os pontos? De/Para 1 2 3 4 5 6 7 8 9 10 4 201 689 843 0 775 459 248 182 663 602 Hill Climbing Cálculo do Vetor de Probabilidades Vamos avaliar a qualidade de cada alternativa como o quadrado da diferença entre a distância máxima e a distância até a alternativa e elevar essa diferença ao quadrado De/Para 1 2 3 4 5 6 7 8 9 10 4 412164 23716 0 0 4624 147456 354025 436921 32400 58081 Distância Máxima = 843 Distância até o Ponto 7 = 248 Qualidade do Ponto 7 = (843-248)2 = 354025 De/Para 1 2 3 4 5 6 7 8 9 10 4 201 689 843 0 775 459 248 182 663 602 Hill Climbing Cálculo do Vetor de Probabilidades Agora basta somarmos todos os valores e a probabilidade será a divisão de cada valor individual pela soma dos valores: Para sortearmos o próximo ponto a ser adicionado à solução, precisamos do vetor de probabilidades cumulativas: De/Para 1 2 3 4 5 6 7 8 9 10 4 0,280501 0,01614 0 0 0,003147 0,100352 0,240934 0,297349 0,02205 0,039527 De/Para 1 2 3 4 5 6 7 8 9 10 4 0,280501 0,296641 0,296641 0,296641 0,299788 0,40014 0,641073 0,938423 0,960473 1 Hill Climbing Escolha do Próximo Ponto na Solução Para isso, precisamos sortear um número aleatório entre 0 e 1 e usar esse número para definir qual vizinho foi sorteado Exemplo: Suponha que o número 0,587 tenha sido sorteado De/Para 1 2 3 4 5 6 7 8 9 10 4 0,280501 0,296641 0,296641 0,296641 0,299788 0,40014 0,641073 0,938423 0,960473 1 O Ponto 7 deve ser escolhido Estes passos devem ser repetidos até que a solução completa tenha sido construída Hill Climbing Estruturas de Vizinhança Na aula passada usamos uma estrutura de vizinhança que troca todos os pontos adjacentes da solução candidata: Lembrem-se que esta vizinhança é pobre e não gera bons resultados, pois não permite um bom aprofundamento na busca local Candidata 5 2 3 4 1 6 Vizinhança 2 5 3 4 1 6 5 3 2 4 1 6 5 2 4 3 1 6 5 2 3 1 4 6 5 2 3 4 6 1 6 2 3 4 1 5 Hill Climbing Estruturas de Vizinhança Uma alternativa seria gerar todas as trocas possíveis de dois pontos (não apenas os adjacentes) Esta vizinhança geraria uma maior diversidade de vizinhos e permitiria encontrar melhores soluções Cuidado: o custo computacional é maior, pois aumenta o tamanho da vizinhança! Vizinhança 5 2 3 4 1 6 2 5 3 4 1 6 3 2 5 4 1 6 4 2 3 5 1 6 1 2 3 4 5 6 6 2 3 4 1 5 5 3 2 4 1 6 5 4 3 2 1 6 5 1 3 4 2 6 5 6 3 4 1 2 5 2 4 3 1 6 5 2 1 4 3 6 5 2 6 4 1 3 5 2 3 1 4 6 5 2 3 6 1 4 5 2 3 4 6 1 Hill Climbing Desempenho da Nova Vizinhança Vamos rodar os dois tipos de vizinhança usando 6 instâncias do TSP com as seguintes características: Instância Tamanho tsp_00 8 (aula TSP) tsp_01 10 (aula TSP) tsp_02 10 tsp_03 15 tsp_04 25 tsp_05 50 Hill Climbing Vizinhança 2-Opt A estrutura de vizinhança 2-Opt é muito usada para o problema TSP pois consegue eliminar a maioria dos cruzamentos nos circuitos O algoritmo 2-Opt remove duas arestas de uma solução e reconecta o circuito Após testar todas as formas possíveis de retirar duas arestas e reconectar a solução, temos o melhor vizinho da solução original O procedimento é feito até a solução parar de melhorar (ótimo local) Cuidado: O algoritmo 2-Opt consome muito mais tempo computacional que o método que usamos na aula passada de trocar todos os vizinhos consecutivos Hill Climbing Vizinhança 2-Opt A seguir temos um exemplo de como o algoritmo 2-Opt remove cruzamentos em um circuito: 1 2 8 7 6 3 5 4 Hill Climbing Vizinhança 2-Opt Em algum momento as ligações 2-3 e 7-6 seriam desfeitas: 1 2 8 7 6 3 5 4 Hill Climbing Vizinhança 2-Opt Após isso, a única forma de reconectá-las é dada abaixo: 1 2 8 7 6 3 5 4 Hill Climbing Vizinhança 2-Opt Vamos analisar o que realmente aconteceu neste exemplo: 1 2 3 4 5 6 7 8 Solução Original Corte Corte 1 2 6 5 4 3 7 8 Solução Reconectada Corte Corte Hill Climbing Vizinhança 2-Opt Dados dois pontos de corte, a solução resultante pode ser obtida executando o procedimento a seguir: ● Da origem ao ponto de corte 1, manter a mesma ordem de visita dos pontos ● Entre os pontos de corte 1 e 2, inverter a ordem de visita ● Do ponto de corte 2 até o final da solução original, manter a mesma ordem de visita dos pontos Na prática, a estrutura 2-Opt testa todas as inversões possíveis de subtrechos na solução original e retorna a melhor delas! Hill Climbing Desempenho da Nova Vizinhança Vamos rodar os dois tipos de vizinhança usando 6 instâncias do TSP com as seguintes características: Instância Tamanho VMP HC1 HC2 HC3 tsp_00 8 3014 3014 3014 3014 tsp_01 10 2764 2575 2575 2575 tsp_02 10 3386 3083 3083 3083 tsp_03 15 2694 3421 2694 2694 tsp_04 25 4577 6924 4337 4216 tsp_05 50 6607 14443 7010 5800 Observação: Os algoritmos HC são estocásticos e podem retornar valores diferentes cada vez que são executados Complexidade do TSP Por que o TSP é tão difícil? A quantidade de soluções possíveis do TSP cresce exponencialmente em função do tamanho do problema sendo solucionado Note que qualquer solução do TSP pode ser expressa como uma permutação dos pontos que precisam ser visitados Exemplo: Um TSP com 6 pontos possui 720 soluções possíveis: 1 2 3 4 5 6 2 1 3 4 5 6 2 3 1 4 5 6 Todas as permutações possíveis dos pontos são soluções do problema! n!=6!=720 Soluções possíveis Complexidade do TSP Explosão Combinatória Problemas como o TSP são exemplos de problemas cujos espaços de solução crescem exponencialmente Instâncias pequenas são fáceis de solucionar, mas pequenos aumentos no tamanho da instância podem tornar o espaço de soluções intratável Tamanho Soluções 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 11 39916800 12 479001600 13 6227020800 14 87178291200 15 1,307674E+12 Complexidade do TSP Explosão Combinatória: Abaixo podemos ver o crescimento exponencial do tamanho do espaço de soluções Tamanho Soluções 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 11 39916800 12 479001600 13 6227020800 14 87178291200 15 1,307674E+12 3 5 7 9 11 13 15 17 0,00E+00 2,00E+11 4,00E+11 6,00E+11 8,00E+11 1,00E+12 1,20E+12 1,40E+12 Tamanho da Instância Tamanho do Espaço de Soluções Complexidade do TSP Métodos de Resolução do TSP A seguir são listadas algumas técnicas para solucionar o TSP: ● Enumeração de todas as soluções possíveis: só funciona para instâncias muito pequenas devido ao aumento do tamanho do espaço de soluções ● Heurísticas como o VMP, AMC e Nearest Insertion: obtém soluções de qualidade média, porém muito rapidamente, mesmo para instâncias muito grandes ● Modelagem com Programação Linear: obtém a solução ótima, mas o tempo de resolução é alto, sendo indicado para problemas com no máximo 30 pontos ● Metaheurísticas: algoritmos de busca e melhoria das soluções; se bem projetados, podem encontrar soluções próximas da ótima mesmo para problemas muito grandes Metaheurísticas O que são metaheurísticas? ● Heurísticas são procedimentos específicos para um problema que tiram vantagem de alguma de suas particularidades para obterem soluções boas em um curto período de tempo ● Metaheurísticas são técnicas mais amplas, que independem do problema sendo tratado. As metaheurísticas são procedimentos de nível mais alto, que coordenam a execução heurísticas na busca por soluções ● Algumas metaheurísticas aceitam uma piora momentânea na solução com o objetivo de sair de ótimos locais e visitar outras regiões do espaço de soluções Metaheurísticas Determinismo vs Não Determinismo ● Em geral, as heurísticas são métodos determinísticos, ou seja, dada uma mesma entrada, o resultado da aplicação da heurística sempre será o mesmo ● Por outro lado, as metaheurísticas são não determinísticas. Por isso, cada vez que são executadas, mesmo que para uma mesma entrada, o resultado provavelmente será diferente ● O caráter não determinístico das metaheurísticas ajuda a fugir dos ótimos locais, possibilitando a busca pelo ótimo global Metaheurísticas Exemplos de Metaheurísticas Algoritmos de Busca Local: ● Hill-Climbing ● Iterated Local Search (ILS) ● Variable Neighborhood Search (VNS) ● Simulated Annealing ● Tabu Search, etc... Algoritmos Bioinspirados: ● Algoritmos Genéticos ● Colônias de Formigas ● Algoritmo dos Morcegos, etc... Ótimos Locais vs Ótimos Globais Os espaços de solução são imensos e cheios de picos e vales, logo nunca sabemos onde está a solução ótima global. Em geral, nos deparamos com soluções que são ótimas apenas localmente Solução atual do Problema Se continuarmos a busca no sentido do crescimento da função, cairemos num ótimo local Sentido do crescimento da função Obs: considere o problema de maximização Obs: Problema de maximização Ótimos Locais vs Ótimos Globais Para evitar ótimos locais e termos a chance de encontrar o ótimo global, temos que aceitar uma piora temporária na solução para explorar outras regiões do espaço de soluções Sentido do crescimento da função Sentido da redução da função Esta solução não seria encontrada se seguíssemos apenas o sentido do crescimento Obs: Problema de maximização Conceito de Vizinhança Dada uma solução qualquer, a vizinhança dessa solução é o conjunto de soluções próximas dela segundo algum critério Geralmente obtemos a vizinhança de uma solução realizando pequenas alterações em sua estrutura Vizinhança Sc V (Sc) V (Sc) Lembre-se: a vizinhança de uma solução é um conjunto de outras soluções que podem ser obtidas a partir da solução original seguindo uma regra ou método pré-definido Solução Atual Metaheurísticas Exemplos de Estrutura de Vizinhança Dada uma solução qualquer, a vizinhança dessa solução será composta por todas as soluções possíveis que invertem exatamente um par de pontos consecutivos na solução original (troca adjacentes) Solução original : 3 – 5 – 1 – 2 – 4 – 6 Vizinhança : 5 – 3 – 1 – 2 – 4 – 6 3 – 1 – 5 – 2 – 4 – 6 3 – 5 – 2 – 1 – 4 – 6 6 – 5 – 1 – 2 – 4 – 3 ... Hill-Climbing Visão Geral do Algoritmo Hill-Climbing ● O Hill-Climbing (subida do morro) é um método iterativo de busca por soluções que decide o próximo passo analisando as soluções existentes na vizinhança da solução atual ● Para cada iteração, partimos da solução atual Sc e avaliamos todas as soluções pertencentes a sua vizinhança V(S) ● Seja S* a melhor solução em V(Sc). Se S* for melhor que Sc, então atribuímos Sc ← S* e continuamos a busca local ● Por outro lado, se S* não for melhor que Sc, então chegamos a um ótimo local e Sc já é a melhor solução que podemos obter nessa região do espaço de soluções Hill-Climbing Inicialização Randômica Múltipla ● Pela descrição anterior, é fácil perceber que o algoritmo Hill- Climbing irá parar em um ótimo local ● Para sair dos ótimos locais e explorar outras regiões do espaço de solução, podemos reiniciar o Hill-Climbing múltiplas vezes, cada uma com uma nova solução escolhida aleatoriamente ● Deve haver um critério de parada para o algoritmo. Em geral se limita o número total de iterações // Algoritmo Hill-Climbing com inicialização randômica múltipla Função HillClimbing (P, TMAX) T = 0 Selecionar uma solução “sol_candidata” aleatoriamente do problema melhor_sol = sol_candidata Repita Local = FALSE Repita Produza o conjunto V(sol_candidata) com todos os vizinhos de sol_candidata Escolha a solução melhor_vizinho (melhor solução em V(sol_candidata)) Se Avaliação(melhor_vizinho) melhor que Avaliação(sol_candidata) Então sol_candidata = melhor_vizinho Senão Local = TRUE Fim Se Até Local = TRUE T = T + 1 Se Avaliação(sol_candidata) melhor que Avaliação(melhor_sol) Então melhor_sol = sol_candidata Fim Se Selecionar uma nova solução “sol_candidata” aleatoriamente do problema Até T = TMAX Fim Hill-Climbing Exemplo: Vamos realizar uma iteração do algoritmo Hill-Climbing para o TSP usando o critério de vizinhança descrito anteriormente nesta aula Vamos considerar a seguinte solução randômica escolhida a partir do espaço de soluções (indexada em zero) Vamos avaliar toda a vizinhança desta solução e verificar se ela possui um vizinho melhor que ela mesma. Depois vamos repetir isso até chegarmos ao ótimo local. Solução inicial: 6 – 4 – 1 – 3 – 2 – 0 – 8 – 9 – 7 – 5 Custo: 6375 Hill-Climbing Outras Instâncias Nesta aula estamos usando, ao todo, 6 instâncias: Instância Pontos Solução VMP tsp_01 8 3014 tsp_02 10 2764 tsp_03 10 3386 tsp_04 15 2694 tsp_05 25 4577 tsp_06 50 6607 Será que nosso algoritmo Hill-Climbing consegue ser melhor que o VMP? Hill-Climbing Desempenho do nosso Hill-Climbing Note que a nossa implementação do HC não é muito boa Instância Pontos Solução VMP Hill-Climbing Tempo (s) tsp_01 8 3014 3014 0,066 tsp_02 10 2764 2575 0,092 tsp_03 10 3386 3083 0,093 tsp_04 15 2694 2985 0,189 tsp_05 25 4577 6902 0,529 tsp_06 50 6607 14912 3,658 Obs: Soluções do Hill-Climbing obtidas com 1.000 iterações