Simulated Annealing - Notas de Aula sobre Metaheurística para Otimização

Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 13 Métodos metaheurísticos Simulated Annealing SA Simulated Annealing SA O annealing anelamento têmpera recozimento cristalização de certos materiais consiste em submetêlos inicialmente a altas temperaturas e reduzilas gradualmente até atingirem com aumentos e reduções do estado de energia o equilíbrio térmico tornandoos assim consistentes e rígidos A técnica matemática de Simulated Annealing faz uma simulação algorítmica do processo físico da têmpera de materiais A idéia de aplicar este método para resolver problemas de otimização combinatória surgiu com Kirkpatrick et al 1983 e Aragon et al 1984 têmpera simulada ou anelamento simulado aspectos básicos Exemplo 1 Suponha o Problema de Caixeiro Viajante PCV constituído de cinco pontos sendo dada a matriz com as distâncias inteiras mínimas aproximadas entre todos os pares de pontos Determine uma solução ótima ou quase ótima do PCV aplicando a metaheurística Simulated Annealing A B C D E A 0 1 1 4 2 B 1 0 4 1 4 C 1 4 0 5 3 D 4 1 5 0 4 E 2 4 3 4 0 Dados os parâmetros a serem adotados para resolução do problema Nº máximo de iterações M 3 Fator de redução de temperatura α 09 Nº máximo de perturbações por iteração P 3 Limite de sucessos por iteração perturbações aceitas a cada iteração L 3 Adote um número randômico 0 rdn 1 como limite para aceitação ou rejeição de uma solução quando esta causar um aumento de energia no processo Aqui adotaremos aceitar uma solução de piora na energia no caso minimização quando a energia E aumentar quando o Fator de Boltzmann FB for maior ou igual a rdn 05 OBS Caso não tivéssemos dada a matriz com as distâncias mínimas poderíamos obtêla através da aplicação do algoritmo de FLOYD como já foi visto na disciplina de Métodos Heurísticos OBS L P 4 Determinação da estimativa da temperatura inicial T0 A estimativa da temperatura inicial segundo Johnson et al 1987 poderá ser calculada da seguinte forma 1 EDCBA E Energia 4541216 2 ABCDE A Energia 1454216 3 CDEAB C Energia 5421416 4 CAEDB C Energia 1241412 5 CDBEA C Energia 5142113 igual a aproximadamente 08 valor fixo empírico média aritmética para um nº radômico de perturbações das variaçõe s da função objetivo energia E onde obtido experimentalmente 0 ξ A B C D E A 0 1 1 4 2 B 1 0 4 1 4 C 1 4 0 5 3 D 4 1 5 0 4 E 2 4 3 4 0 0 variação 0 variação 4 variação 1 variação 5 68 0 22 25 1 80 ln 25 1 ln 1 25 4 1 4 0 0 ξ0 E T E Logo 0 Exemplo Suponha que através de um processo aleatório obtivemos a seguinte amostra de 5 cinco soluções viáveis Obs Esta temperatura T0 568 deverá ser adotada para toda a 1ª iteração Na sequência ao início de cada iteração esta temperatura sofrerá um decréscimo taxa de resfriamento gradual e controlado conforme será observado no desenvolvimento da solução do problema ln E T 0 0 ξ 4 variações em módulo OBS Existem outras formas de estimar a temperatura inicial T 0 5 Solução do exemplo 1 Solução inicial S0 escolha aleatória de uma solução qualquer S0 CDEAB C Energia E0 5421416 Solução S1 Uma perturbação sobre S0 CDEAB C E0 16 é um processo aleatório Por exemplo Troca entre si as posições de C e A S1 ADECB A E1 4434116 Variação de energia E E1 E0 1616 0 Nem aumentou e nem diminuiu a energia então podemos aceitar a solução S1 Nº de sucessos nº de aceitações L 1 Nº de perturbações executadas P 1 OBS Se E 0 caso de estabilidade ou equilíbrio Neste caso temos duas configurações vizinhas com a mesma energia ou custo coincidência pouco provável de acontecer na prática O novo estado será aceito e o processo continua exploitationprofundidade Inserese uma pequena perturbação ou alteração nas posições de algumas partículas pontos da solução resultando uma variação de energia ou seja uma alteração no valor da função objetivo Isto pode ser feito de três modos 1º modo Trocase entre si as posições de dois ou mais pontos 2º modo Inserese um ponto retirado de sua posição em outra posição 3º modo Podese aplicar os dois modos anteriormente descritos de forma mesclada OBS Conforme a natureza do problema podemos aplicar outras formas de provocar a permutação Atenção Sempre nesta ordem ou seja a energia da nova solução menos a anterior Atenção Atualizações obrigatórias Solução S2 Uma perturbação sobre S1 ADECB A E1 16 Por exemplo Troca entre si as posições de A e B S2 BDECA B E2 1431110 Variação de energia E E2 E1 1016 6 Diminuiu a energia então aceitamos a solução S2 Nº de sucessos nº de aceitações acumuladas L 2 Nº de perturbações executadas acumuladas P 2 A B C D E A 0 1 1 4 2 B 1 0 4 1 4 C 1 4 0 5 3 D 4 1 5 0 4 E 2 4 3 4 0 OBS Se E 0 neste caso houve redução de energia o novo estado é aceito e o processo continua exploitationprofundidade Atenção Sempre nesta ordem ou seja a energia da nova solução menos a anterior Atenção Atualizações obrigatórias 7 A B C D E A 0 1 1 4 2 B 1 0 4 1 4 C 1 4 0 5 3 D 4 1 5 0 4 E 2 4 3 4 0 SoluçãoS3 Uma perturbação sobre S2 BDECA B E2 10 Por exemplo Troca entre si as posições entre B e E S3 EDBCA E E3 41412 12 Variação de energia E E3 E2 12102 Aumentou a energia então iremos aceitar ou rejeitar a solução S3 de acordo com a seguinte probabilidade Fator de BoltzmannFB Nº de sucessos nº de aceitações acumuladas L 3 Nº de perturbações executadas acumuladas P 3 Obs A iteração finaliza quanto atingimos o primeiro valor entre o nº máx perturbaçõesiteração P3 e o nº limite de sucessos iteração L 3 arbitrados no início do problema Número gerado randomicamente e arbitrado no início do problema 2 rdn 05 Estimada antes do início desta primeira iteração 5 68 T 1 T Onde 05 rdn 07 Como FB 0 i Aceitamos a solS 3 070 142 1 272 1 272 272 e FB 035 035 568 2 T ΔE i OBS Se E 0 neste caso houve aumento de energia que no processo físico é útil para permitir uma futura reacomodação das partículas evitando a convergência da função objetivo para mínimos locais indesejáveis exploration diversidadeamplitude A probabilidade de aceitar uma mudança deste tipo E 0 é chamada de critério algoritmo de Metropolis estabelecido a partir do fator de Boltzmann que é dado pela função onde Ti é a temperatura válida para a iteração i em que ocorreu a mudança ou seja estimada antes do início da iteração em curso em andamento Fim da 1ª iteração com a solução S3 EDBCA E E3 12 Atenção Sempre nesta ordem ou seja a energia da nova solução menos a anterior Atenção Atualizações obrigatórias iT ΔE FB e 8 Função de Boltzmann Fluxograma para o algoritmo de Metropolis O algoritmo proposto por Metropolis et al 1953 pertence a classe de métodos estatísticos denominada Métodos de Monte Carlo os quais tem a característica de usar um grande número de amostragens aleatórias rdn 0 rdn 1 ΔE rdn exp ΔE T i Metropolis Algorithm ΔE 0 O resfriamento gradativo de um material a partir de uma alta temperatura inicial leva o material a estados mínimos de energia Informalmente esses estados são caracterizados por uma perfeição estrutural do material resfriado o que não seria obtido caso o resfriamento não tivesse sido gradativo Sob outras condições menos cuidadosas de resfriamento o material se cristalizaria com uma energia localmente mínima apresentando imperfeições estruturais A esse processo cuidadoso de resfriamento dáse o nome de annealing Têmpera ou Anelamento A simulação Simulated Annealing a uma temperatura fixa T consiste em dar um pequeno deslocamento a um dos átomos computando a variação E da energia do sistema 1 Se E 0 o deslocamento é incorporado ao estado do sistema que é então utilizado no passo seguinte 2 Caso contrário se E 0 a aceitação ou não do deslocamento passa a ser uma decisão probabilística segundo a função de Boltzmann já definida anteriormente Comentários Resfriamento rápido amorfo Resfriamento Lento critalino Função de Boltzmann Probabilidade de aceitação de uma transição de maior energia Comentários Probabilidade de aceitação ΔE ΔET A aceitação temporária de soluções piores significa que o método admite caminhar morro acima na esperança de encontrar regiões mais promissoras vales mais profundos exploration procura em amplitude Probabilidade de aceitação exp ET FB i FB e iT ΔE iT ΔE e 1 FB 11 Início da 2ª iteração 511 568 90 T α T T 1 0 1 Solução inicial S0 Solução obtida no final da 1ª iteração ou seja S3 EDBCA E S0 EDBCA E E0 12 Solução S1 Uma perturbação sobre S0 EDBCA E E0 12 é um processo aleatório Por exemplo Troca entre si as posições de B e C S1 EDCBA E E1 4541216 Variação de energia E E1 E0 1612 4 Aumentou a energia então podemos aceitar ou rejeitar a solução S1 de acordo com a seguinte probabilidade Fator de BoltzmannFB Nº de sucessos nº de aceitações acumuladas L 0 Nº de perturbações executadas acumuladas P 1 A B C D E A 0 1 1 4 2 B 1 0 4 1 4 C 1 4 0 5 3 D 4 1 5 0 4 E 2 4 3 4 0 Número gerado randomicamente e arbitrado no início do problema 2 rdn 05 Estimada antes do início desta segunda iteração 511 T 1 T Onde 05 rdn 045 0 45 Como FB 2 72 2 72 e FB 0 i 0 78 511 4 T E i Não aceitamos a soluçãoS 1 Atualização da temperatura Ti Uma das formas de se obter o decréscimo da temperatura proposta por Romeo et al 1985 onde 09 em geral é dada por 1i i α T T 12 Solução S2 Uma perturbação sobre S0 EDBCA E E0 12 é um processo aleatório Por exemplo Troca entre si as posições de A e C S2 EDBAC E E2 4111310 Variação de energia E E2 E0 1012 2 Diminuiu a energia então aceitamos a solução S2 Nº de sucessos nº de aceitações acumuladas L 1 Nº de perturbações executadas acumuladas P2 A B C D E A 0 1 1 4 2 B 1 0 4 1 4 C 1 4 0 5 3 D 4 1 5 0 4 E 2 4 3 4 0 Solução S3 Uma perturbação sobre S2 EDBAC E E2 10 é um processo aleatório Por exemplo Troca entre si as posições de D e C S3 ECBAD E E3 3414416 Variação de energia E E3 E2 1610 6 Aumentou a energia então podemos aceitar ou rejeitar a solução S3 de acordo com a seguinte probabilidade Fator de BoltzmannFB Nº de sucessos nº de aceitações acumuladas L 1 Nº de perturbações executadas acumuladas P 3 Número gerado randomicamente e arbitrado no início do problema 2 rdn 05 Estimada antes do início desta segunda iteração 511 T 1 T Onde 05 rdn 031 0 31 Como FB 2 72 2 72 e FB 1 i 1 17 511 6 T E i aceitamos a soluçãoS 3 Não Fim da 2ª iteração com a solução S2 EDBAC E E2 10 Obs A iteração finaliza quanto atingimos o primeiro valor entre o nº máx perturbaçõesiteração P3 e o nº limite de sucessos iteração L 3 arbitrados no início do problema 13 Solução S1 Uma perturbação sobre S0 EDBAC E E0 10 é um processo aleatório Por exemplo Inserir o E imediatamente antes do A S1 DBEAC D E1 14215 13 Variação de energia E E1 E0 13 10 3 Aumentou a energia então podemos aceitar ou rejeitar a solução S1 de acordo com a seguinte probabilidade Fator de BoltzmannFB Nº de sucessos nº de aceitações acumuladas L 1 Nº de perturbações executadas acumuladas P1 Número gerado randomicamente e arbitrado no início do problema 2 rdn 05 Estimada antes do início desta segunda iteração 4 60 T 1 T Onde 05 rdn 052 0 52 Como FB 2 72 2 72 e FB 2 i 0 65 460 3 T E i a soluçãoS Aceitamos 1 A B C D E A 0 1 1 4 2 B 1 0 4 1 4 C 1 4 0 5 3 D 4 1 5 0 4 E 2 4 3 4 0 Início da 3ª iteração Atualização da temperatura Ti 09 4 60 511 90 T α T T α T T 2 1 2 1i i Solução inicial S0 Solução obtida no final da 2ª iteração ou seja S2 EDBAC E S0 EDBAC E E0 10 Solução S2 Uma perturbação sobre S1 DBEAC D E113 é um processo aleatório Por exemplo Troca entre si as posições de A e E S2 DBAEC D E2 11235 12 Variação de energia E E2 E3 1213 1 Diminuiu a energia então aceitamos a solução S2 Nº de sucessos nº de aceitações acumuladas L 2 Nº de perturbações executadas acumuladas P2 A B C D E A 0 1 1 4 2 B 1 0 4 1 4 C 1 4 0 5 3 D 4 1 5 0 4 E 2 4 3 4 0 Solução S3 Uma perturbação sobre S2 DBAEC D E2 12 é um processo aleatório Por exemplo Inserir o C imediatamente antes do D S3 CDBAE C E3 51123 12 Variação de energia E E3 E2 1212 0 Nem aumentou e nem diminuiu a energia então podemos aceitar a solução S3 Nº de sucessos nº de aceitações acumuladas L 3 Nº de perturbações executadas acumuladas P3 Fim da 3ª iteração com a solução S3 CDBAE C E3 12 Obs1 A iteração finaliza quanto atingimos o primeiro valor entre o nº máx perturbaçõesiteração P3 e o nº limite de sucessos iteração L 3 arbitrados no início do problema 2 Como inicialmente a solução foi limitada em três iterações M3 interrompemos aqui a continuidade da solução Fim Atenção Caso prosseguíssemos com as iterações a solução inicial S0 para próxima iteração seria S0 S3 CDBAE C E3 12 15 Obs No final do processo após várias iterações esperase que o sistema estacione em um estado de energia globalmente mínima por analogia com a física do problema A temperatura se aproxima de zero e soluções de piora não são mais aceitas Assim a melhor solução tende a ser a última obtida da última interação 16 Um exemplo de simulação para minimização Start temperature 25 Temperature step 01 End temperature 0 Iterations 1000000 Animação da aplicação da metaheurística Simulated Annealing buscando a rota de distância próxima da mínima em um Problema do Caixeiro Viajante envolvendo 48 capitais dos EUA 18 Exemplo 2 Dado o seguinte problema de designação determine uma solução ótima ou quase ótima Faça duas iterações completas explicando bem cada passo A Metalúrgica Araucária SA dentro de 60 dias deverá começar a funcionar em sua nova sede localizada na Cidade Industrial de Curitiba CIC O Presidente da Metalúrgica deseja que a distribuição das salas dessa nova instalação seja feita de modo a atender na medida do possível as preferências já manifestadas Em uma pesquisa realizada os Diretores manifestaram as suas preferências sendo que 1 indica a sala de maior preferência e 6 indica a sala de menor preferência conforme tabela Sala Diretor 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 Se você fosse convidado a opinar sobre a distribuição das salas qual seria a sua recomendação de forma a satisfazer ao máximo as preferências dos diretores Dados os parâmetros a serem adotados para resolução do problema Nº máximo de iterações M 2 Fator de redução de temperatura α 09 Nº máximo de perturbações por iteração P 4 Limite de sucessos por iteração perturbações aceitas a cada iteração L 3 Adote um número randômico rdn como limite para aceitação ou rejeição de uma solução quando esta causar um aumento de energia no processo Aqui adotaremos aceitar uma solução de piora na energia no caso minimização quando a energia E aumentar quando o Fator de Boltzmann FB for maior ou igual a rdn 05 19 Sala Diretor 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 Como o número de Diretores 5 é menor que o número de salas 6 toda solução implicará em uma sala vazia cuja designação será feita a um diretor inexistente artificial que representaremos por A Configuração do ex de uma a solução tipo Salas em ordem crescente 1 2 3 4 5 6 Diretores designados ex 2 3 A 5 4 1 Exemplo Suponha que através de um processo aleatório obtivemos a seguinte amostra de cinco soluções viáveis Estimativa da temperatura inicial T0 1ª 23A541 Energia 13066622 2ª 45132A Energia 12323011 3ª 3145A2 Energia 54260219 4ª 12345A Energia 25441016 5ª A54321 Energia 02223615 variação 11 variação 8 variação 3 variação 1 2614 0 22 75 5 80 ln 75 5 ln E T 5 75 4 3 1 11 8 E Logo 0 0 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 E 21 Início da 1ª iteração Solução inicial S0 escolha aleatória de uma sol qq S0 45132A E0 12323011 Solução S1 Uma perturbação sobre S0 45132A E0 11 é um processo aleatório Por exemplo Troca entre si as posições de 4 e 3 S1 35142A E1 52343017 Variação de energia E E1 E0 17116 Aumentou a energia então podemos aceitar ou não a solução S1 Nº de sucessos nº de aceitações L 1 Nº de perturbações executadas P 1 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 Número gerado randomicamente e arbitrado no início do problema 2 rdn 05 Estimada antes do início desta primeira iteração 2614 T 1 T Onde 05 rdn 079 0 79 Como FB 2 72 2 72 e FB 0 i 23 0 2614 6 T E i a soluçãoS Aceitamos 1 Solução S2 Uma perturbação sobre S1 35142A E1 17 é um processo aleatório Por exemplo Troca entre si as posições de 2 e 3 S2 25143A E2 12341011 Variação de energia E E2 E1 11176 Diminuiu a energia então aceitamos a solução S2 Nº de sucessos nº de aceitações L 2 Nº de perturbações executadas P 2 Solução S3 Uma perturbação sobre S2 25143A E2 11 é um processo aleatório Por exemplo Troca entre si as posições de 4 e 5 S3 24153A E3 13361014 Variação de energia E E3 E2 14113 Aumentou a energia então podemos aceitar ou não a solução S3 Nº de sucessos nº de aceitações L 3 Nº de perturbações executadas P 3 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 Número gerado randomicamente e arbitrado no início do problema 2 rdn 05 Estimada antes do início desta primeira iteração 2614 T 1 T Onde 05 rdn 089 0 89 Como FB 2 72 2 72 e FB 0 i 0 11 2614 3 T E i a soluçãoS Aceitamos 3 Fim da 1ª iteração com a solução S3 24153A E3 14 Obs A iteração finaliza quanto atingimos o primeiro valor entre o nº máx perturbaçõesiteração P4 e o nº limite de sucessos iteração L 3 arbitrados no início do problema 23 Início da 2ª iteração Atualização da temperatura Ti 09 2353 2614 90 T α T T α T T 2 1 2 1i i Solução inicial S0 Solução obtida no final da 1ª iteração ou seja S3 24153A S0 24153A E0 14 Solução S1 Uma perturbação sobre S0 24153A E0 14 é um processo aleatório Por exemplo Troca entre si as posições de A e 1 S1 24A531 E1 13061617 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 Variação de energia E E1 E0 17143 Aumentou a energia então podemos aceitar ou rejeitar a solução S1 de acordo com a seguinte probabilidade Fator de BoltzmannFB Nº de sucessos nº de aceitações acumuladas L 1 Nº de perturbações executadas acumuladas P1 Número gerado randomicamente e arbitrado no início do problema 2 rdn 05 Estimada antes do início desta segunda iteração 2353 T 1 T Onde 05 rdn 088 0 88 Como FB 2 72 2 72 e FB 0 i 0 13 2353 3 T E i a soluçãoS Aceitamos 1 24 Solução S2 Uma perturbação sobre S1 24A531 E1 17 é um processo aleatório Por exemplo Troca entre si as posições de 3 e 5 S2 24A351 E2 13021613 Variação de energia E E2 E1 13174 Diminuiu a energia então podemos aceitar a solução S2 Nº de sucessos nº de aceitações acumuladas L 2 Nº de perturbações executadas acumuladas P2 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 Solução S3 Uma perturbação sobre S2 24A351 E2 13 é um processo aleatório Por exemplo Troca entre si as posições de 1 e 2 S3 14A352 E3 23021210 Variação de energia E E3 E2 10133 Diminuiu a energia então podemos aceitar a solução S3 Nº de sucessos nº de aceitações acumuladas L 3 Nº de perturbações executadas acumuladas P3 Obs 1 A iteração finaliza quanto atingimos o primeiro valor entre o nº máx perturbaçõesiteração P 4 e o nº limite de sucessos iteração L 3 arbitrados no início do problema 2 Como inicialmente a solução foi limitada em duas iterações M2 interrompemos aqui a continuidade da solução Fim da 2ª iteração com a solução S3 14A352 E310 Fim Atenção Caso prosseguíssemos com as iterações a solução inicial S0 para próxima iteração seria S0 S3 14A352 E310 25 Fim da 2ª iteração com a solução S3 14A352 E310 Interpretação desta solução Sala Diretor Preferência 1 1 2 2 4 3 3vazia Ainexistente 0 4 3 2 5 5 1 6 2 2 Total10 S D 1 2 3 4 5 6 1 2 4 3 1 5 6 2 1 5 4 6 3 2 3 5 3 4 2 1 6 4 1 3 2 4 6 5 5 3 2 5 6 1 4 A 0 0 0 0 0 0 Lembrete A melhor solução tende a ser a última obtida da última interação Suponha o Problema de Caixeiro Viajante PCV constituído de seis pontos dada a matriz com as distâncias inteiras mínimas aproximadas entre todos os pares de pontos Determine uma solução do PVC aplicando a metaheurística Simulated Annealing 1 2 3 4 5 6 1 0 2 2 4 4 4 2 2 0 1 2 3 2 3 2 1 0 2 2 3 4 4 2 2 0 3 3 5 4 3 2 3 0 5 6 4 2 3 3 5 0 Problema proposto TDE 1 Dados os parâmetros a serem adotados para resolução do problema Nº máximo de iterações M 2 Fator de redução de temperatura α 09 Nº máximo de perturbações por iteração P 4 Limite de sucessos por iteração perturbações aceitas a cada iteração L 3 Adote um número randômico rdn como limite para aceitação ou rejeição de uma solução quando esta causar um aumento de energia no processo Aqui adotaremos aceitar uma solução de piora na energia no caso minimização quando a energia E aumentar quando o Fator de Boltzmann FB for maior ou igual a rdn 05 Alguns Exemplos Adicionais Legenda n nº de nós M Nº máximo de iterações α Fator de redução de temperatura PNº máximo de perturbações por iteração LLimite de sucessos por iteração S0 Solução inicial T0 Temperatura inicial S Solução Final Legenda n nº de nós M Nº máximo de iterações α Fator de redução de temperatura PNº máximo de perturbações por iteração LLimite de sucessos por iteração S0 Solução inicial T0 Temperatura inicial S Solução Final 29 Notas de Aula Prof Edgard 1 GOLDBARG Marco Cesar LUNA Henrique Pacca L Otimização combinatória e programação linear modelos e algoritmos 2 ed rev e atual Rio de Janeiro Campus 2005 2 LOPES Heitor Silvério RODRIGUES Luiz Carlos de Abreu STEINER Maria Teresinha Arns Meta heurísticas em pesquisa operacional Curitiba Omnipax 2013 3 SHIMIZU Tamio Decisão nas organizações introdução aos problemas de decisão encontrados nas organizações e nos sistemas de apoio à decisão São Paulo Atlas 2001 4 ARENALES Marcos Nereu Pesquisa operacional para cursos de engenharia Rio de Janeiro Elsevier 2007 5 HILLIER Frederick S LIEBERMAN Gerald J Introdução à pesquisa operacional Porto Alegre AMGH 2013 6 GOMES Luiz Flavio Autran Monteiro GONZÁLEZ ARAYA Marcela Cecilia CARIGNANO Claudia Tomada de decisões em cenários complexos introdução aos métodos discretos do apoio multicritério à decisão 1 ed São Paulo Cengage Learning 2004 7 DUDA Richard O HART Peter E STORK David G Pattern classification and scene analysis 2nd ed New York J Wiley Sons c2001 8 Bodin L Golden B Assad A and Ball M Routing and Scheduling of veicles and crews Special edition of Computer and Operations Research col 10 n2 1983 9 Bronson R Pesquisa Operacional São Paulo Schaum McGrawHill do Brasil Ltda 1985 10 Murty K Linear and Combinatorial Programming Robert E Krieger Publishing Company Malabar Florida 1985 11 Steiner MT A Notas de Aulas Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Métodos Quantitativos para Tomada de Decisão do curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras