Python——模拟退火在背包问题上的运用（详细代码）

一、模拟退火简介

二、详细代码

import math
import random
import matplotlib.pyplot as plt

def init_population(n):  
    '''生成一个种群，个体为全排列的随机排列'''
    population = []
    indivdul = 100  #个体数为100
    for i in range(indivdul):
        cs = [i for i in range(1,n+1)]
        random.shuffle(cs) #打乱
        population.append(cs)
    return population



def ff_popu(population,n,v1,v2):  
    '''传入一个种群，返回一个函数值列表'''
    ys = []
    for i in population:
        cost_sum = 0
        location  = i
        for j in range(n):
            for k in range(n):
                loca1 = location.index(j+1)
                loca2 = location.index(k+1)
                cost = v2[j][k]*v1[loca1][loca2]  #核心计算函数
                cost_sum = cost_sum + cost
        ys.append(cost_sum)
        index = ys.index(min(ys))
        #best = population[index]
    return ys

def ff_indivdul(i,n,v1,v2):
    '''传入一个个体，返回一个值'''
    cost_sum = 0
    location  = i
    for j in range(n):
        for k in range(n):
            loca1 = location.index(j+1)
            loca2 = location.index(k+1)
            cost = v2[j][k]*v1[loca1][loca2]  #核心计算函数
            cost_sum = cost_sum + cost
    return cost_sum



def neig(population,n,T,v1,v2):
    '''
    传入一个种群
    对种群中的每个个体产生邻域
    根据退火原理来判断是否接受这个新解
    返回一个新的种群
    '''
    popu_new = []
    for i in population:
        #随机生成两个数，让个体中这两个交换
        r1 = random.randint(0,len(i)-1)
        r2 = random.randint(0,len(i)-1)
        
        i_after = i[:]
        i_after[r1] = i[r2]
        i_after[r2] = i[r1]
        #分别计算初始值和邻域值
        y = ff_indivdul(i, n, v1, v2)
        y_after = ff_indivdul(i_after, n, v1, v2)
        E = y_after - y 
        if E < 0:
            i = i_after
        else:
            proba = random.random()
            f = math.exp(-(E/T))
            if proba <= f:
                i = i_after
        popu_new.append(i)
    return popu_new
        
def read():
    with open('D:/学习文件/大三上/科研课堂/qap-problems/QAP32.dat','r',encoding='utf-8') as f:   
        comments = f.read().splitlines()
    n = eval(comments[0])
    v11 = comments[2:2+n]
    v22 = comments[3+n:3+n+n]
    v1 = []
    v2 = []
    for i in v11:
        int_list = list(map(int, i.split()))
        v1.append(int_list)
    for i in v22:
        int_list = list(map(int, i.split()))
        v2.append(int_list)
    return v1,v2,n

def main():
    v1,v2,n = read()
    population = init_population(n)
    #evolution = 1000
    print(min(ff_popu(population,n,v1,v2)))
    T = 30  #这个是初始温度
    plt_y = []
    while (T > 2):
        population = neig(population,n,T,v1,v2)
        print(min(ff_popu(population,n,v1,v2)))
        plt_y.append(min(ff_popu(population,n,v1,v2)))
        T = T - 0.1  #每次温度减去0.1
    plt.plot(plt_y)
        
main()