启发式算法解决TSP、0/1背包和电路板问题

1. Las Vegas

题目

设计一个 Las Vegas 随机算法，求解电路板布线问题。将该算法与分支限界算法结合，观察求解效率。

代码

python代码如下：

# -*- coding: utf-8 -*-
"""
@Date    : 2024/1/4 
@Time    : 16:21
@Author  : MainJay
@Desc    : LasVegas算法解决电路问题
"""
import heapq
import randommaps = []
nums = 8for i in range(nums):m = []for j in range(nums):m.append(1 if random.random() < 0.3 else 0)maps.append(m)
b_x = random.randint(0, nums - 1)
b_y = random.randint(0, nums - 1)
e_x = random.randint(0, nums - 1)
e_y = random.randint(0, nums - 1)
while maps[b_x][b_y] == 1:b_x = random.randint(0, nums - 1)b_y = random.randint(0, nums - 1)
while maps[e_x][e_y] == 1:e_x = random.randint(0, nums - 1)e_y = random.randint(0, nums - 1)class Position(object):targetPosition = Nonedef __init__(self, x: int, y: int, length: int = 0):self.x = xself.y = yself.length = lengthdef __lt__(self, other):return self.length + abs(Position.targetPosition.x - self.x) + abs(Position.targetPosition.y - self.y) - (other.length + abs(Position.targetPosition.x - other.x) + abs(Position.targetPosition.y - other.y))class LasVegas(object):def __init__(self, initPosition: Position, targetPosition: Position):self.initPosition = initPositionPosition.targetPosition = targetPositiondef run(self):priority_queue = []heapq.heappush(priority_queue, self.initPosition)directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]flag = False  # 判断是否找到了解print(f"目标位置：{Position.targetPosition.x},{Position.targetPosition.y}")while priority_queue:item = heapq.heappop(priority_queue)print(f"现在位置：{item.x}, {item.y}")if item.x == Position.targetPosition.x and item.y == Position.targetPosition.y:flag = True# 找到解跳出break# 遍历can_position = []for direction in directions:t_x = item.x + direction[0]t_y = item.y + direction[1]if 0 <= t_x < len(maps) and 0 <= t_y < len(maps[0]):if maps[t_x][t_y] == 0:  # 没有标记且没有墙can_position.append(Position(t_x, t_y, item.length + 1))if len(can_position) > 0:# LasVegas算法随机挑选一个放入队列m_position = can_position[random.randint(0, len(can_position) - 1)]# 挑选的这个标记为已经走过maps[m_position.x][m_position.y] = 2heapq.heappush(priority_queue, m_position)return flagbegin = Position(b_x, b_y)
end = Position(e_x, e_y)
l = LasVegas(begin, end)
l.run()

运行结果

[1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 1, 1]
[1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 1, 0]
[1, 0, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 1, 1, 1, 0]
[0, 1, 0, 0, 1, 0, 0, 0]目标位置：5, 6
现在位置：3, 4
现在位置：3, 5
现在位置：4, 5
现在位置：5, 5
现在位置：5, 6

2. 模拟退火算法

题目

上机实现TSP的模拟退火算法，随机生成一定规模的数据或用通用数据集比较其它人的结果，分析算法的性能，摸索实现中技术问题的解决。

代码

python代码如下：

# -*- coding: utf-8 -*-
"""
@Date    : 2024/1/3 
@Time    : 16:15
@Author  : MainJay
@Desc    : 模拟退火算法解决TSP问题
"""
import random
from math import exp
import matplotlib.pyplot as pltdef create_new(ans: list):"""随机产生一个解:param ans: 原解:return: 返回一个解"""random_index1 = random.randint(0, len(ans) - 1)random_index2 = random.randint(0, len(ans) - 1)ans[random_index1], ans[random_index2] = ans[random_index2], ans[random_index1]return ansdef create_distance(nums: int = 25):"""随机生成距离矩阵:param nums: 城市数量:return: 矩阵函数"""distance = []for i in range(nums):d = []for j in range(nums):if i > j:d.append(distance[j][i])elif i == j:d.append(0)else:d.append(random.randint(0, 100) + random.random())distance.append(d)return distanceclass SimulatedAnnealing(object):def __init__(self, distance: list, initialTemperature: float = 100, endTemperature: float = 10, L: int = 5,alpha: float = 0.05):""":param distance: 距离矩阵:param initialTemperature: 初始温度:param endTemperature: 退火温度:param L: 每个温度的迭代次数:param alpha: 每次退火分数"""self.distance = distanceself.temperature = initialTemperatureself.endTemperature = endTemperatureself.L = Lself.result = []  # 记录每次退火过程中的最优解self.t = []  # 记录每次退火过程中的温度，用于画图self.alpha = alphadef temperature_down(self):"""温度退火:return:"""self.temperature = self.temperature * (1 - self.alpha)def cal_ans(self, ans: list):"""计算解的值:param ans: 解:return: 解的权值"""val = 0.00for i in range(0, len(ans) - 1):val += self.distance[ans[i]][ans[i + 1]]val += self.distance[ans[-1]][ans[0]]return valdef annealing(self):"""模拟退火过程:return:"""ans = list(range(len(self.distance)))  # 随机初始化一个解val = self.cal_ans(ans)while self.temperature > self.endTemperature:  # 直到温度降到指定结束温度时结束退火过程for i in range(self.L):  # 在每个温度迭代L次new_ans = create_new(ans)new_val = self.cal_ans(new_ans)df = new_val - valif df < 0:ans, val = new_ans, new_valelif random.uniform(0, 1) < 1 / (exp(df / self.temperature)):ans, val = new_ans, new_valself.result.append(val)self.t.append(self.temperature)self.temperature_down()def plot(self):# 在生成的坐标系下画折线图plt.plot(self.t, self.result)plt.gca().invert_xaxis()# 显示图形plt.show()distance = create_distance()
simulatedAnnealing = SimulatedAnnealing(distance)
simulatedAnnealing.annealing()
simulatedAnnealing.plot()

运行结果

3. 遗传算法

题目

上机实现 0/1 背包问题的遗传算法，分析算法的性能。

代码

python代码如下：

# -*- coding: utf-8 -*-
"""
@Date    : 2024/1/4 
@Time    : 14:45
@Author  : MainJay
@Desc    : 遗传算法解决0/1背包问题
"""
import random
import heapq
import copy
import matplotlib.pyplot as pltnums = 10
weights = []
values = []
W = 400for i in range(nums):weights.append(random.randint(0, 100))values.append(random.randint(0, 100))class GeneticAlgorithm(object):def __init__(self, N: int = 6, Nums: int = 10, Mutation_probability: float = 0.1, iter_num: int = 10):self.N = Nself.Nums = Numsself.iter_num = iter_num# 初始化种群self.population = []self.Mutation_probability = Mutation_probabilityfor i in range(N):p = []for j in range(len(weights)):p.append(random.randint(0, 1))self.population.append(p)def selectNPopulation(self, population: list):"""挑选一个种群:param population: 原始种群:return: 新种群"""nums = 0# 创建一个空的优先队列priority_queue = []for item in population:heapq.heappush(priority_queue, Individual(item))pops = []total_v = 0.00p = []# 优胜虐汰，挑选前Nums满足条件的while priority_queue and nums < self.Nums:item = heapq.heappop(priority_queue)if item.total_weight > W:continuepops.append(item.chromosome)total_v += item.total_valuep.append(total_v)nums += 1p = [item / total_v for item in p]# 根据概率分布随机挑选一个new_pop = []for i in range(self.N):rand = random.random()for j in range(len(p)):if rand <= p[j]:new_pop.append(pops[j])breakreturn new_popdef cross_population(self, population: list):parents = copy.deepcopy(population)for i in range(self.N):mother = parents[random.randint(0, len(parents) - 1)]father = parents[random.randint(0, len(parents) - 1)]threshold = random.randint(0, len(weights) - 1)sun1 = mother[:threshold] + father[threshold:]sun2 = father[:threshold] + mother[threshold:]population.append(sun1)population.append(sun2)return populationdef population_variation(self, population: list):"""种群基因突变:param population: 种群:return: 一个种群"""if random.random() < self.Mutation_probability:rand_pop = random.randint(0, len(population) - 1)rand_index = random.randint(0, len(weights) - 1)population[rand_pop][rand_index] = 1 - population[rand_pop][rand_index]return populationdef genetic(self):x = []y = []for i in range(self.iter_num):print(f"第{i + 1}代")print(f"种群为{self.population}")x.append(i + 1)y.append(Individual(self.population[0]).total_value)s_pop = self.selectNPopulation(self.population)c_pop = self.cross_population(s_pop)p_pop = self.population_variation(c_pop)self.population = p_popself.plot(x, y)def plot(self, x, y):# 在生成的坐标系下画折线图plt.plot(x, y)# 显示图形plt.show()class Individual(object):def __init__(self, chromosome: list):""":param chromosome: 染色体的列表"""self.chromosome = chromosomeself.total_weight = 0.00self.total_value = 0.00for i in range(len(chromosome)):if chromosome[i] == 1:self.total_weight += weights[i]self.total_value += values[i]def __lt__(self, other):return self.total_value > other.total_valueg = GeneticAlgorithm()
g.genetic()

运行结果

第1代
种群为[[0, 0, 1, 1, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 0, 1, 1, 0, 0, 0], [1, 1, 1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 0, 0, 1, 0, 1, 1], [1, 1, 1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 0, 1, 0, 1, 1, 1, 1, 1]]
第2代
种群为[[1, 0, 1, 0, 0, 0, 1, 0, 1, 1], [1, 1, 0, 1, 0, 1, 1, 1, 1, 1], [1, 1, 1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 0, 0, 1, 0, 1, 1], [1, 1, 1, 1, 1, 0, 0, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0, 0, 0, 0], [1, 1, 0, 1, 0, 1, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 1, 0, 0, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 1, 0, 1, 0, 1, 0, 1, 0], [1, 1, 1, 0, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 0, 1, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0, 1, 1, 1, 1], [1, 1, 0, 1, 0, 1, 1, 0, 1, 1]]
第3代
种群为[[1, 1, 1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 0, 1, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 0, 1, 0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0, 1, 0, 0], [1, 0, 1, 1, 1, 0, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1, 0, 1, 1], [1, 1, 0, 1, 0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 1, 0, 1, 1]]
第4代
种群为[[1, 1, 1, 1, 1, 0, 0, 1, 0, 0], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 1, 1, 1, 1], [1, 1, 0, 1, 0, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 1, 0, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 1, 0, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 0, 0, 1, 1, 1, 1], [1, 1, 1, 1, 1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0, 1, 0, 0]]
第5代
种群为[[1, 1, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 0, 0, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 1, 1, 1, 1]]
第6代
种群为[[1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 0, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 0, 0, 1, 1, 1, 1]]
第7代
种群为[[1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1]]
第8代
种群为[[1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 0, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1]]
第9代
种群为[[1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1]]
第10代
种群为[[1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0, 1, 1, 1, 1]]