遗传算法求解TSP问题实验指导书
大约 7 分钟人工智能人工智能
一、实验项目概述
旅行商问题（TSP）是经典的NP难组合优化问题，目标是找到遍历所有城市且仅访问一次的最短路径。遗传算法是模拟生物进化的启发式搜索算法，通过选择、交叉、变异等操作迭代优化种群，是求解TSP问题的常用方法。本实验将通过Python实现遗传算法，探究不同参数和策略对TSP问题求解效果的影响。
二、实验目标
- 理解遗传算法的核心原理、流程和编码策略，掌握其求解TSP问题的完整步骤。
- 测试城市规模、种群规模、交叉概率、变异概率对算法求解结果（适应度、运行时间）的影响。
- 对比不同变异策略和个体选择概率分配策略对同一TSP问题求解性能的差异。
- 学会分析实验数据，总结算法性能规律，形成完整的实验报告。
三、实验要求
1. 基础任务：不同规模TSP问题求解
- 编程实现遗传算法，分别求解10个城市、20个城市、100个城市的TSP问题。
- 运行算法多次（建议≥5次），记录每次的最佳适应度、最差适应度、平均适应度、运行时间，计算平均值后填入下表：
| 城市规模 | 最佳适应度 | 最差适应度 | 平均适应度 | 平均运行时间（s） |
|---|---|---|---|---|
| 10 | ||||
| 20 | ||||
| 100 |
2. 参数敏感性分析任务
针对10个城市的TSP问题，设置不同参数组合，运行算法并记录结果：
| 种群规模 | 交叉概率 | 变异概率 | 最佳适应度 | 最差适应度 | 平均适应度 | 平均运行时间（s） |
|---|---|---|---|---|---|---|
| 10 | 0.85 | 0.15 | ||||
| 20 | 0.85 | 0.15 | ||||
| 100 | 0.85 | 0.15 | ||||
| 100 | 0 | 0.15 | ||||
| 100 | 0.5 | 0.15 | ||||
| 100 | 1 | 0.15 | ||||
| 100 | 0.85 | 0 | ||||
| 100 | 0.85 | 0.5 | ||||
| 100 | 0.85 | 1 |
3. 策略对比任务
固定参数：种群规模=100，交叉概率=0.85，变异概率=0.15，针对10个城市的TSP问题，新增以下策略并记录结果：
- 变异策略：相邻两点互换变异、逆转变异、插入变异（至少选择1种新增策略）自行查阅资料
- 个体选择概率分配策略：线性排序分配、非线性排序分配（至少选择1种新增策略）自行查阅资料
| 变异策略 | 个体选择概率分配 | 最佳适应度 | 最差适应度 | 平均适应度 | 平均运行时间（s） |
|---|---|---|---|---|---|
| 基础逆序变异 | 轮盘赌分配 | ||||
| 相邻互换变异 | 线性排序分配 | ||||
| 插入变异 | 非线性排序分配 |
4. 实验报告要求
- 画出遗传算法求解TSP问题的流程图（包含编码、初始化种群、适应度计算、选择、交叉、变异、迭代终止等步骤）。 可以在电脑上画完后，拍照贴到报告中
- 分析不同城市规模下算法的性能变化规律（适应度和运行时间的变化趋势）。
- 分析种群规模、交叉概率、变异概率对算法结果的影响。
- 对比不同变异策略和个体选择策略对算法结果的影响。
- 总结实验心得体会。
四、实验步骤提示（代码参考
1. 环境准备
- 安装Python环境和依赖库：
pip install numpy matplotlib - 准备城市坐标数据：可随机生成二维坐标（如
(x,y)，范围0-100），或使用公开TSP数据集。
2. 核心代码实现
# 导入需要的工具库
import random
import time
import numpy as np
# -------------------------- 函数1：生成城市坐标 --------------------------
# 功能：随机生成指定数量的城市坐标(x,y)
def generate_cities(city_num):
np.random.seed(1) # 固定随机种子，保证每次运行结果一致
return [(random.randint(0, 50), random.randint(0, 50)) for _ in range(city_num)]
# -------------------------- 函数2：计算一条路径的总长度 --------------------------
# 功能：计算一条路径走完所有城市并回到起点的总距离
def path_length(path, cities):
dis = 0
n = len(path)
for i in range(n):
x1, y1 = cities[path[i]]
x2, y2 = cities[path[(i + 1) % n]]
dis += np.hypot(x1 - x2, y1 - y2) # 计算两点距离
return dis
# -------------------------- 函数3：计算适应度 --------------------------
# 功能：适应度 = 1 / 路径长度，路径越短，适应度越高
def fitness(path, cities):
return 1 / path_length(path, cities)
# -------------------------- 函数4：初始化种群 --------------------------
# 功能：生成初始种群，每个个体是一条随机访问路径
def init_pop(pop_size, n):
pop = []
for _ in range(pop_size):
p = list(range(n))
random.shuffle(p) # 随机打乱城市顺序
pop.append(p)
return pop
# -------------------------- 【选择策略：3种】 --------------------------
# 选择1：精英选择（原来的，不变）
def select(pop, fits):
idx = np.argsort(fits)[-len(pop):]
return [pop[i] for i in idx]
# 选择2：线性排序选择
def select_linear(pop, fits):
idx = np.argsort(fits)
return [pop[i] for i in idx[-len(pop):]]
# 选择3：非线性排序选择
def select_nonlinear(pop, fits):
idx = np.argsort(fits)[::-1]
return [pop[i] for i in idx[:len(pop)]]
# -------------------------- 函数6：交叉操作 --------------------------
# 功能：两个父代交换基因，产生新子代
def cross(p1, p2):
n = len(p1)
a, b = random.sample(range(n), 2)
if a > b:
a, b = b, a
c1, c2 = p1.copy(), p2.copy()
c1[a:b], c2[a:b] = c2[a:b], c1[a:b] # 交换中间片段
return c1, c2
# -------------------------- 【变异策略：3种】 --------------------------
# 变异1：原来的交换变异（不变）
def mutate_swap(path, rate):
if random.random() < rate:
i, j = random.sample(range(len(path)), 2)
path[i], path[j] = path[j], path[i]
return path
# 变异2：逆序变异
def mutate_inversion(path, rate):
if random.random() < rate:
i, j = sorted(random.sample(range(len(path)), 2))
path[i:j] = path[i:j][::-1]
return path
# 变异3：插入变异
def mutate_insert(path, rate):
if random.random() < rate:
i, j = random.sample(range(len(path)), 2)
val = path.pop(i)
path.insert(j, val)
return path
# -------------------------- 主函数：整合版 --------------------------
# 支持：
# pop_size 种群规模
# cross_rate 交叉概率
# mutate_rate 变异概率
# gen 迭代次数
# select_func 选择策略函数
# mutate_func 变异策略函数
def ga_tsp(
cities,
pop_size=50,
cross_rate=0.8,
mutate_rate=0.1,
gen=50,
select_func=select, # 选择策略
mutate_func=mutate_swap # 变异策略
):
n = len(cities)
pop = init_pop(pop_size, n) # 初始化种群
best_fit = 0
best_path = []
start = time.time()
# 开始迭代进化
for _ in range(gen):
# 计算所有个体的适应度
fits = [fitness(p, cities) for p in pop]
# 更新最优解
for i in range(len(pop)):
if fits[i] > best_fit:
best_fit = fits[i]
best_path = pop[i].copy()
# 选择操作（可切换策略）
pop = select_func(pop, fits)
# 交叉 + 变异，生成新种群
new_pop = []
while len(new_pop) < pop_size:
p1 = random.choice(pop)
p2 = random.choice(pop)
# 交叉概率
if random.random() < cross_rate:
c1, c2 = cross(p1, p2)
else:
c1, c2 = p1.copy(), p2.copy()
# 变异（可切换策略）
c1 = mutate_func(c1, mutate_rate)
c2 = mutate_func(c2, mutate_rate)
new_pop.append(c1)
new_pop.append(c2)
pop = new_pop[:pop_size]
end = time.time()
return best_fit, best_path, end - start
# ===================== 主程序：可自由设置参数 =====================
if __name__ == "__main__":
numcity = 10 # 城市数量：10 / 20 / 100
# ========== 你可以自由修改下面这4个参数 ==========
种群规模 = 100
交叉概率 = 0.85 # 可改为 0 / 0.5 / 0.85 / 1
变异概率 = 1 # 可改为 0 / 0.15 / 0.5 / 1
迭代次数 = 50
# 生成城市
cities = generate_cities(numcity)
# 运行算法
best_fit, best_path, t = ga_tsp(
cities,
pop_size=种群规模,
cross_rate=交叉概率,
mutate_rate=变异概率,
gen=迭代次数
)
# 输出结果
print("✅ 运行成功！")
print(f"城市数量：{numcity}")
print(f"种群规模：{种群规模}")
print(f"交叉概率：{交叉概率}")
print(f"变异概率：{变异概率}")
print(f"最佳适应度：{best_fit:.6f}")
print(f"运行时间：{t:.2f} 秒")3. 实验执行与数据记录
- 传入不同城市规模、参数组合，多次运行取平均值。
- 将结果填入对应的附表，注意单位统一（运行时间保留2位小数，适应度保留5位小数）。
第三表格的代码，上述参考代码已经包含，可以手动调用。
五、思考问题
- 为什么城市规模越大，平均运行时间越长，平均适应度越低？
- 交叉概率为0或1时，为什么求解效果不如0.5-0.85？
- 变异概率为0时，算法容易陷入什么问题？
- 哪种变异策略和选择策略的组合在本实验中表现最好？为什么？