遗传算法生成最小生成树实践
最小生成树问题描述
最小生成树问题时指在由m个节点和n条边组成的网络模型中寻找连接所有节点的生成树，使得其所有边的权值之和最小。最小生成树问题广泛应用于系统设计、选址规划等组合优化问题中。
在由m个节点和m条边组成的图中，当各边的权值给定时，最小生成树问题可以作为0-1整数规划问题描述如下：
其中xi,j是边(i,j)的决策变量，选择该边时取1，反之取0。求解最小生成树的代表算法有Kruskal法和Prim法等。
最小生成树问题示例
连接各节点的可能边如下图所示：
各边的权值如下表所示：
遗传算法求解最小生成树问题
个体编码
解码
交叉操作
在交叉操作中，将两个父代染色体个体解码出的树进行叠加后，重新生成可用边集合和邻接节点集合，再在新集合的基础上重新使用PrimPred编码，得到一个子代染色体。用这种方法可以保留父代中优秀的子结构，从而加速收敛。
突变操作
用最小代价法(Low Cost Method)生成新的个体，先在父代染色体中随机删除一条边，使得原图分为两个互不连接的子图，然后从两个子图的节点集中，添加一条权数最小的边使其恢复连通，从而生成一个新个体。
代码示例
完整代码如下：
计算的迭代过程可视化：
生成的最小生成树为：