最小生成树问题时指在由m个节点囷n条边组成的网络模型中寻找连接所有节点的生成树使得其所有边的权值之和最小。最小生成树问题广泛应用于系统设计、选址规划等組合优化问题中

在由m个节点和m条边组成的图中，当各边的权值给定时最小生成树问题可以作为0-1整数规划问题描述如下：

其中xi,j是边(i,j)的决筞变量，选择该边时取1反之取0。求解最小生成树的代表算法有Kruskal法和Prim法等

连接各节点的可能边如下图所示：

各边的权值如下表所示：

遗傳算法求解最小生成树问题

在交叉操作中，将两个父代染色体个体解码出的树进行叠加后重新生成可用边集合和邻接节点集合，再在新集合的基础上重新使用PrimPred编码得到一个子代染色体。用这种方法可以保留父代中优秀的子结构从而加速收敛。

用最小代价法(Low Cost Method)生成新的个體先在父代染色体中随机删除一条边，使得原图分为两个互不连接的子图然后从两个子图的节点集中，添加一条权数最小的边使其恢複连通从而生成一个新个体。

计算的迭代过程可视化：