Simulated Annealing para Resolução de Problema de Partição de Números no Python

Prévia do material em texto

IDLE_tmp_wh2mzl53
#Simulated Annealing para Resolução do Problema de Partição de Números
#Acadêmicos: Henrique Alves de Lima e Thiago Ferri Lemos
#Disciplina: Tópicos Avançados em Métodos Matemáticos
#Última atualização 04/07/2019
import array
import random
import math
import time
va = [] #Vetor Sequência inicial
n = int (input ("Deseja resolver o problema para quantos números?\n"))
fo = 0 #Função objetivo a qual iremos tentar minimizarfo = 0 #Função objetivo a qual iremos tentar minimizar
vms = [] #Vetor Melhor Solução
for i in range (n): #Criação do vetor melhor solução inicial
 print("Digite o " , i+1 , "º número")
 ai = float(input())
 va.append(ai)
 conj = [-1,1]
 si = random.choice(conj)
 vms.append(si*va[i])
 fo = fo + vms[i]
print (va)
print (vms)
print ("Função objetivo inicial: ", abs (fo)) 
ti = float(input("Qual a temperatura inicial?\n"))
t = ti*(abs(fo))
na = int(input("Qual o número de 'aceites' por temperatura?\n"))
nmit = int(input("Qual o número máximo de iterações por temperatura?\n"))
beta = float(input("Qual a taxa de resfriamento? Digite um valor entre 0.5 e 
0.99\n"))
vs = vms #Vetor Solução Incumbente
v1 = [] #Vetor partição 1
v2 = [] #Vetor partição 2v2 = [] #Vetor partição 2
itc = 0 #Quantidade de iterações calculadas
while (t > 10**-10): #Altere para aumentar ou diminuir a máxima temperatura 
mínima possível
 print (t)
 it = 1 #Iteração na temperatura
 ia = 0 #Iterações aceitas
 while (ia < na): 
 print ("Iteração: " ,it, "\nTemperatura: ", t)
 it = it + 1
 fn = 0 #Função objetivo nova
 fa = 0 #Função objetivo ótima
 fs = 0 #Funçao objetivo incumbente
 vv = [] #Vetor de vizinhança
 for i in range (n): #Criação do vetor vizinho aleatório
 conj = [-1,1]
 si = random.choice(conj)
 vv.append(si*vs[i])
 fn = fn + vv[i]
 fa = fa + vms[i]
 fs = fs + vs[i]
 delta_f = (abs(fn) - abs(fs)) #Variação da função objetivo delta_f = (abs(fn) - abs(fs)) #Variação da função objetivo
 print ("Vizinho: ", vv)
 print ("Função objetivo atual: ", abs(fn))
 print ("Função objetivo referencial: ", abs(fs))
 print ("Variação", delta_f)
 if (delta_f < 0): #Melhoria da solução incumbente
 vs = vv
 ia = ia + 1
 print ("Solução melhorada: ", vs)
 if (abs(fn) < abs(fa)): #Critério de aceite para melhor solução 
atual
 vms = vv
 fa = fn
Página 1
IDLE_tmp_wh2mzl53
 else: #Critério de aceite pelo palpiteiro
 x = random.uniform(0,1)
 palp = -float(delta_f)/t
 r = math.exp(palp)
 if (x < r):
 vs = vv
 ia = ia + 1
 print ("Melhor solução no momento", vms)
 print ("Solução atual", vs)
 itc = itc + 1
 if (fa == 0) or (fn == 0): #Critério de parada caso alguma função 
objetivo resulte em 0
 vms = vv
 break break
 if it > nmit: #Critério de troca de temperatura
 ia = na
 if (fa == 0) or (fn == 0): #Critério de parada caso alguma função objetivo 
resulte em 0
 vms = vv
 break
 t = beta * t #Para atualizar a temperatura
 it = 0
for i in range (n): #Para separar em conjunto positivo ou negativo
 if vms[i] >= 0:
 v1.append(vms[i])
 else:
 v2.append(vms[i])
print("Melhor resultado final: " , vms)
print("Conjunto positivo: ", v1, "\nConjunto negativo: ", v2)
print("Função objetivo final: ", fa)
print("Neste processo foram calculadas ", itc, " iterações")
time.sleep(60)
#Copie ou melhore, mas não retire os créditos!
Página 2