PublicouNatan Cantos Alterado mais de 4 anos atrás
1 Inteligência Computacional para Otimização Marcone Jamilson Freitas Souza Departamento de Computação Universidade Federal de Ouro Preto http://www.iceb.ufop.br/prof/marcone Aula 06
2 Roteiro Simulated Annealing Fundamentação Funcionamento do método Prescrições para o resfriamento Prescrições para determinar temperatura inicial Considerações gerais
3 Fundamentação do método Proposto por Kirkpatrick et al. (1983) Simula o processo de recozimento de metais; Resfriamento rápido conduz a produtos meta-estáveis, de maior energia interna; Resfriamento lento conduz a produtos mais estáveis, estruturalmente fortes, de menor energia; Durante o recozimento o material passa por vários estados possíveis
4 Fundamentação do método Analogia com um problema combinatorial: Os estados possíveis de um metal correspondem a soluções do espaço de busca; A energia em cada estado corresponde ao valor da função objetivo; A energia mínima corresponde ao valor da solução ótima.
5 Fundamentação do método A cada iteração do método, um novo estado é gerado a partir do estado corrente por uma modificação aleatória neste; Se o novo estado é de energia menor que o estado corrente, esse novo estado passa a ser o estado corrente; Se o novo estado tem uma energia maior que o estado corrente em unidades, a probabilidade de se mudar do estado corrente para o novo estado é: e - /(kT), onde k = constante de Boltzmann e T = temperatura corrente; Este procedimento é repetido até se atingir o equilíbrio térmico (passo de Metropolis)
6 Probabilidade de aceitação de um movimento de piora Baseada na fórmula: P(aceitação) = e - /T = variação de custo; T = temperatura Temperatura Probabilidade de aceitação
7 Fundamentação do método A probabilidade de um dado estado com energia f i ser o estado corrente é: e -fi/(kT) / j e -fj/(kT) (Densidade de Boltzmann) A altas temperaturas, cada estado tem (praticamente) a mesma chance de ser o estado corrente; A baixas temperaturas, somente estados com baixa energia têm alta probabilidade de se tornar o estado corrente; Atingido o equilíbrio térmico em uma dada temperatura, esta é diminuída e aplica-se novamente o passo de Metropolis. O método termina quando a temperatura se aproxima de zero.
8 Fundamentação do método No início do processo, a temperatura é elevada e a probabilidade de se aceitar soluções de piora é maior; As soluções de piora são aceitas para escapar de ótimos locais; A probabilidade de se aceitar uma solução de piora depende de um parâmetro, chamado temperatura; Quanto menor a temperatura, menor a probabilidade de se aceitar soluções de piora;
9 Fundamentação do método Atingido o equilíbrio térmico, a temperatura é diminuída; A taxa de aceitação de movimentos de piora é, portanto, diminuída com o decorrer das iterações; No final do processo, praticamente não se aceita movimentos de piora e o método se comporta como o método da descida/subida; O final do processo se dá quando a temperatura se aproxima de zero e nenhuma solução de piora é mais aceita, evidenciando o encontro de um ótimo local.
10 Algoritmo Simulated Annealing
11 Prescrições para o resfriamento
12 Prescrições para determinar a temperatura inicial
13 Determinação da temperatura inicial por simulação
14 Considerações Gerais Número máximo de iterações em uma dada temperatura calculado com base na dimensão do problema; Temperatura de congelamento do sistema: quando se atingir, p.ex., T = 0,001 ou quando a taxa de aceitação de movimentos cair abaixo de um valor predeterminado; Os parâmetros mais adequados para uma dada aplicação só podem ser obtidos por experimentação.