企业官网建设流程全解析

scikit-opt 遗传算法进阶实战：整数规划、TSP 固定起终点与自定义初始种群

【免费下载链接】scikit-optGenetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Ant Colony Optimization Algorithm,Immune Algorithm, Artificial Fish Swarm Algorithm, Differential Evolution and TSP(Traveling salesman)项目地址: https://gitcode.com/GitHub_Trending/sci/scikit-opt

本篇技术指南聚焦 scikit-opt 中遗传算法（GA）的三个高频进阶场景：通过precision整数设定实现整数规划、在GA_TSP中固定路径起点与终点、以及为 GA/DE/SA/PSO 各算法手动注入初始点或初始种群。读完本文，你将掌握这三类需求的标准写法、底层编码机制，以及可直接复制运行的完整示例代码。

一、用遗传算法做整数规划（Integer Programming）

1.1 核心机制：把precision设为整数

在 scikit-opt 中，GA使用二进制编码（Gray Code）表示解。默认情况下precision=1e-7，每个变量按高精度浮点数搜索；当某个变量对应的precision被设置为整数时，该变量会自动进入整数规划模式，只在整数点上取值。

例如，我们希望目标函数demo_func的三个变量中，前两个是整数（间隔分别为 2 和 1），第三个是浮点数，则设置precision=[2, 1, 1e-7]：

from sko.GA import GA demo_func = lambda x: (x[0] - 1) ** 2 + (x[1] - 0.05) ** 2 + x[2] ** 2 ga = GA(func=demo_func, n_dim=3, max_iter=500, lb=[-1, -1, -1], ub=[5, 1, 1], precision=[2, 1, 1e-7]) best_x, best_y = ga.run() print('best_x:', best_x, '\n', 'best_y:', best_y)

• lb/ub为各维度的下界与上界（标量或等长数组均可）；
• max_iter=500为最大迭代代数；
• 输出best_x为最优解向量，best_y为最优目标函数值。

1.2 源码原理：整数规划是怎么实现的

从 sko/GA.py 的实现可以看到，precision会被广播为与n_dim等长的数组，随后按以下逻辑计算每个变量所需的基因段长度：

Lind_raw = np.log2((self.ub - self.lb) / self.precision + 1) self.Lind = np.ceil(Lind_raw).astype(int)

即每个变量对应的二进制基因位数Lind由取值范围与精度共同决定。整数规划模式的关键判定在 sko/GA.py：

self.int_mode_ = (self.precision % 1 == 0) & (Lind_raw % 1 != 0) self.int_mode = np.any(self.int_mode_) if self.int_mode: self.ub_extend = np.where(self.int_mode_ , self.lb + (np.exp2(self.Lind) - 1) * self.precision , self.ub)

• precision % 1 == 0：该维度 precision 为整数，进入整数规划模式；
• Lind_raw % 1 != 0：该维度可能取值个数不是 $2^n$（此时按ceil取整会多出一些冗余编码位）；
• 此时GA会将上界临时扩展到ub_extend，使可能取值恰好覆盖 $2^n$ 个，并在解码阶段（sko/GA.py）用np.where(X > self.ub, self.ub, X)将超出原始上界的取值钳制回ub，从而保证结果仍落在用户声明的区间内。

1.3 使用注意事项

• 取值个数最好是 $2^n$：当整数变量的可能取值个数为 $2^n$（如 4、8、16 个）时，编码利用率最高，收敛速度与最终效果最佳；即便不是 $2^n$，算法依然可以正常工作，只是会通过上述ub_extend扩展机制容纳冗余编码。
• 非整数precision不会触发整数模式：例如希望变量步长为0.5，直接把precision=0.5并不会进入整数规划。此时可以做一个变量代换：把原变量乘以2得到新变量，新变量的precision即为整数1，优化完成后再把结果除以2还原，效果等价且实现简单。
• 若同时使用了大量等式约束constraint_eq与不等式约束constraint_ueq，罚函数法叠加后可能影响收敛性能，此时更推荐先在模型外手动做变量变换，规避取值个数非 $2^n$ 的情况。

1.4 参考示例

基础的GA用法可参考 examples/demo_ga.py，其中使用 Schaffer 函数（具有大量局部极小值）演示了precision=1e-7下的浮点优化与收敛曲线绘制，是理解整数规划模式默认行为的对照样例。

二、遗传 TSP：如何固定起点和终点

2.1 思路说明

GA_TSP解决的是旅行商问题（TSP），默认把路径视为闭合回路，起点与终点由算法自由决定。如果你需要固定起点和终点（即路径是开放的，不再闭合），可以这样处理：

• 起点和终点不参与优化：假设共有n+2个点（含起点、终点），遗传算法只优化中间n个点的访问顺序，因此n_dim=n；
• 目标函数按实际路径长度编写：把固定的起点、终点拼接进每次评估的路径序列中，累计各段欧氏距离。

2.2 构建目标函数

import numpy as np from scipy import spatial import matplotlib.pyplot as plt num_points = 20 points_coordinate = np.random.rand(num_points, 2) # generate coordinate of points start_point=[[0,0]] end_point=[[1,1]] points_coordinate=np.concatenate([points_coordinate,start_point,end_point]) distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean') def cal_total_distance(routine): '''The objective function. input routine, return total distance. cal_total_distance(np.arange(num_points)) ''' num_points, = routine.shape routine = np.concatenate([[num_points], routine, [num_points+1]]) return sum([distance_matrix[routine[i], routine[i + 1]] for i in range(num_points+2-1)])

关键点解析：

• points_coordinate原本是 20 个随机点，通过np.concatenate追加起点[0,0]与终点[1,1]，最终坐标矩阵共 22 行，起点/终点分别位于索引20和21；
• cal_total_distance接收的是长度为num_points=20的访问顺序数组（即中间 20 个点的排列），函数内部先拼接[num_points]（起点索引）与[num_points+1]（终点索引），再对相邻点对累加distance_matrix中的欧氏距离；
• 这样既保证起点、终点固定，又让遗传算法自由搜索中间 20 个点的最优排列。

2.3 运行并可视化

from sko.GA import GA_TSP ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1) best_points, best_distance = ga_tsp.run() fig, ax = plt.subplots(1, 2) best_points_ = np.concatenate([[num_points],best_points, [num_points+1]]) best_points_coordinate = points_coordinate[best_points_, :] ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r') ax[1].plot(ga_tsp.generation_best_Y) plt.show()

• 左图绘制最优路径：best_points_coordinate已按“起点 → 中间点 → 终点”的顺序重排坐标，o-r表示红色圆点加线段；
• 右图绘制ga_tsp.generation_best_Y，即每一代最优总距离的下降曲线，用于观察收敛过程；
• prob_mut=1表示每个个体都执行变异，配合 TSP 的逆转变异算子，有助于在大规模排列空间中维持多样性（该参数为0~1的概率值）。

2.4 源码佐证：GA_TSP 的编码与算子

从 sko/GA.py 可以看到GA_TSP与普通GA的差异：

• 初始种群不再使用 0/1 二进制串，而是用tmp.argsort(axis=1)生成每条染色体为一个全排列（sko/GA.py），天然保证每个点恰好访问一次；
• chrom2x直接返回染色体本身，crossover使用部分匹配交叉crossover_pmx，mutation使用逆转变异mutation_reverse（sko/GA.py）；
• 每代结束后，GA_TSP.run()会把父代与子代合并，按目标值排序后截取前size_pop个个体（精英保留策略），从而保证种群质量单调不退化。

对照示例 examples/demo_ga_tsp.py 可以进一步理解闭合回路 TSP 的写法（其目标函数用routine[i % num_points]回绕形成闭环），与本文的开放路径写法互为参照。此外，若你面对的是非闭合图（如普通有向图最短路），则无需做上述固定起终点的处理，直接用标准GA_TSP即可。

三、如何设定初始点或初始种群

在实际工程中，我们经常希望把优化起点放在经验解附近，或直接注入一组已知的候选解。scikit-opt 各算法开放了底层状态属性，支持在实例化之后手动覆盖初始种群：

3.1 GA：直接赋值Chrom

GA在实例化时通过crtbp()随机生成二进制染色体（sko/GA.py）。实例化之后可以手动覆盖初始种群：

ga = GA(func=demo_func, n_dim=3, max_iter=500, lb=[-1, -1, -1], ub=[5, 1, 1], precision=[2, 1, 1e-7]) ga.Chrom = np.random.randint(0, 2, size=(80, 20)) # 手动设定初始种群：80 个个体，每条染色体 20 个基因位 best_x, best_y = ga.run()

注意染色体的形状必须为(size_pop, len_chrom)，其中len_chrom = sum(Lind)是各变量基因段长度之和（可通过ga.len_chrom读取），基因取值只能是0或1。设置后ga.run()会从这一初始种群开始迭代。

3.2 DE：设置de.X

差分进化算法DE在crtbp()中用均匀分布初始化实值种群（sko/DE.py）：

de.X = np.random.uniform(low=-1, high=1, size=(50, 3)) # 手动设定初始 X，形状为 (size_pop, n_dim)

de.X直接保存实值解向量，赋值后运行de.run()即可从指定初始种群开始进化。

3.3 SA：使用构造参数x0

模拟退火是单点搜索算法，其初始解直接通过构造参数x0传入，这也是它与其他算法最大的不同：

from sko.SA import SA sa = SA(func=demo_func, x0=[0, 0, 0], T_max=100, T_min=1e-7, L=300, max_stay_counter=150) best_x, best_y = sa.run()

在 sko/SA.py 中，x0（shape 为n_dim）会同时被用作初始解best_x并立即计算初始目标值best_y；n_dim也由len(x0)自动推导。T_max、T_min、L、max_stay_counter分别控制初始温度、终止温度、每个温度下的链长与冷却停判次数。

3.4 PSO：设置pso.X并刷新历史最优

粒子群算法PSO在初始化时会随机生成位置矩阵X，并同时初始化个体最优pbest_x与全局最优gbest_x（sko/PSO.py）。若手动覆盖pso.X，必须手动同步更新最优记录，否则后续迭代会基于错误的pbest/gbest演化：

pso.X = np.random.uniform(low=-1, high=1, size=(40, 3)) # 手动设定初始 X，形状为 (pop, n_dim) pso.cal_y() # 重新计算每个粒子的目标值 Y（PSO.py 中 cal_y 会调用 func(self.X)） pso.update_gbest() # 更新全局最优 pso.update_pbest() # 更新每个粒子的个体最优

这三个调用分别对应 sko/PSO.py、sko/PSO.py 与 sko/PSO.py 的实现：cal_y计算适应值矩阵，update_pbest依据pbest_y > Y决定是否更新个体最优（并做不等式约束可行性校验），update_gbest取个体最优中的最小值更新全局最优。完成这三步后，pso.run()即可从自定义初始位置出发正常迭代。

3.5 各算法初始设置方式速查

四、小结

本文围绕 scikit-opt 遗传算法的三个进阶需求给出了完整方案：

1. 整数规划：将对应维度的precision设为整数即自动启用整数模式，底层通过ub_extend扩展编码空间并钳制回原始上界，建议可能取值个数为 $2^n$ 以获得最佳收敛性能；
2. TSP 固定起终点：将起点终点附加在坐标矩阵末尾（索引n与n+1），目标函数在评估排列时把它们拼接进路径，GA_TSP会以n_dim=n优化中间点顺序；
3. 自定义初始种群：GA 赋值Chrom、DE 赋值X、SA 传x0、PSO 赋值X后还需刷新cal_y/update_gbest/update_pbest，即可把先验知识注入优化过程，显著加速收敛。

这些能力对应的源码实现分布于 sko/GA.py、sko/DE.py、sko/SA.py 与 sko/PSO.py，配合 examples/demo_ga.py 与 examples/demo_ga_tsp.py 中的完整示例，可以直接作为实战模板复用。

【免费下载链接】scikit-optGenetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Ant Colony Optimization Algorithm,Immune Algorithm, Artificial Fish Swarm Algorithm, Differential Evolution and TSP(Traveling salesman)项目地址: https://gitcode.com/GitHub_Trending/sci/scikit-opt