1 引言
最小生成树问题是构造一个带权图的最小代价生成树， 在网络优化中具有重要的最用。在日常生活中已经广泛的 应用。经典的 Prim 算法［1］ 和 Kruskal 算法［2］ 都能解决一般 的线性的问题，但是在现实生活中的许多的问题往往不是线 性的，像是比较常见的公路建设问题，要充分考虑多方面的 因素，像是电网的构建，也是要考虑许多的问题，不但要考虑 地形导致的架设难度，还要考虑延时带来的不稳定性等等， 从上面的这些问题中就可以看到传统的算法根本不能解决 这些，并且对于搜索算法的复杂度要求又甚高［3］。
令，x = （ x1，2 x1，3 ． ． ． xi，j ． ． ． xn － 1，n ） ，
{ xi，j = 1， if ei，j = 1 被选中
（ 4）
0， otherwise
其中，i = 1，2，． ． ． ，n － 1； j = i + 1，． ． ． ，n 表示图 G 的一棵生
成树。X 为所有 x 的集合，那么多目标最小生成树问题描述 如下［4］：
的数替换 Prüfer 数编码串中的某一位，这样使得单点变异也 可以很大程度上保留了原染色体的性质［9］。提出的这种不
是直接累加目标权值的好处在于可以很好的体现每个个体
的目标优势，而 不 会 忽 视 任 何 一 个 个 体 在 某 一 个 方 面 的 优
势，非常适用于各自现实的问题。
第 29 卷 第 2 期 文章编号： 1006 － 9348（ 2012） 02 － 0213 － 03
计算机仿真
2012 年 2 月
基于改进的遗传算法的多目标优化问题研究
孔德剑
（ 曲靖师范学院计算机科学与工程学院，云南 曲靖 655011） 摘要：研究多目标优化算法问题，针对传统的多目标优化算法由于计算复杂度非常高，难以获得令人满意的解等问题，在图 论和遗传算法基础上，提出了一种改进的遗传算法求解多目标优化方法。首先采用二进制编码表示最小树问题，然后采用 深度优先搜索算法进行图的连通性判断，给出了一种新的适应度函数，以提高算法执行速度和进化效率。最后仿真结果表 明，与经典的 Prim 算法和 Kruskal 算法相比，新算法复杂度较低，并能在第一次遗传进化过程中获得一批最小生成树，适合 于解决不同类型的多目标最小树问题。 关键词：遗传算法； 最小生成树； 多目标； 图论 中图分类号：TP391 文献标识码：A
3） ，T 有 | N | － 1 条边； 4） ，T 是割边； 5） ，T 的任意两个点之
间只有唯一的路相连；
假设有一无向图：
G = （ N，E，W）
（ 1）
∑ 其中 ，W = we 表示为权函数，如果树 T = （ N，ET ，WT ） 包 e∈E
含了图 G 的所有顶点，那么树 T 是 G 的一个生成树，其中，WT
（ 2）
{ ei，j = 1， vi ，vj 之间有边
（ 3）
0，otherwise
其中，（ i = 1，2，． ． ． ，n － 1； j = i + 1，． ． ． ，n） 表示为图 G 的边的
集合，如果边 ei，j 存在，那么该边有 m 个值为正数的属性与之 对应，用 wi，j = ｛ w1i，j ，w2i，j ，． ． ． ，wmi，j ｝ 来表示，实际问题中 wki，j （ k = 1，2，． ． ． ，m） 可以是距离或者代价。
— 214 —
用的算法。
定义估价函数［8］：
∑ g （ x）为? Nhomakorabeai
k =1
（
min［i］ × fi（ x）
100）
2
」
（ 6）
上述公式中，在目标 i 上的当前染色体的费用情况用 fi （ x） 表
示，截止到上一代为止的当前的最小费用 min［i］表示。本文
采用的是小片段等位交叉算子，即随机生成一个 1 到 n 之间
Multi － objective Minimum Spanning Tree Algorithms Based on Genetic Algorithms
KONG De － jian1
（ Qujing Normal University，Qujing Yunnan 655011，China）
ABSTRACT： Solve the problem of minimum spanning tree． The traditional algorithm for solving multi － objective minimum spanning tree problem is of high computational complexity，and difficult to obtain satisfactory solutions． Based on graph theory and genetic algorithm，a improved genetic algorithm was proposed based on multi － objective minimum spanning tree methods． The algorithm used binary code to express minimum trees，and then used depth － first search algorithm to determine the connectivity of the graph． A new fitness function was given to improve the algorithm execution speed and evolutionary efficiency． The simulation results show that compared with the classical Prim algorithm and Kruskal algorithm，the new algorithm is of low complexity，can obtain the minimum spanning tree in the first genetic evolution process，and is suitable for solving different types of problems of multi － objective minimum trees． KEYWORDS： Genetic algorithms； Minimum spanning tree； Multi － objective； Graph theory
首先，对待解决问题进行编码，t： = 0。 第二，随机初始化群体 X（ 0） ： = （ x1 ，x2 ，…，xn ） ； 第三，对当前群体 X（ t） 中每个染色体 xi 计算其适应度 F（ xi ） ，适应度表示了该个体对环境的适应能力，并决定他们 在遗传操作中被抽取到的概率； 第四，对 X（ t） 根据预定概率应用各种遗传算子，产生新 一代群体 X（ t + 1） ，这些算子的目的在于扩展有限个体的覆 盖面，体现全局搜索的思想； 第五，t： = t + 1 新生成的一代群体替换上一代群体； 如 果没有达到预定终止条件则继续第三。 3． 2 遗传算法求解多目标最小生成树 假定有一个完全图设为 G，设有 n 个顶点，从 1 开始编 号，那么就有 nn － 2 棵树，那么在这些编号中间任意取为 n － 2， 并且这些与唯一的生成树相对应。在本文，对生成树的编码 采用 Prüfer 数编码机制［7］，下面就具体给出编码过程和解码 过程，下面分别来一一阐述一下： 编码过程如下： 假设存在一个 空 串，作 为 编 码 串，从 中 找 到 编 号 值 最 小 的节点，并设为 j，然后向其相邻的点设为 i，并放置在右端， 然后逐步开 始 去 除 两 个 点 之 间 的 连 线，一 直 到 只 剩 下 一 条 边，那么这个时候得到的编码串就符合相对应的树的 Prüfer 编码。 解码过程如下： 在编码过程中得到的编码串用 P 表示，那么其余没有表 示的用 P珔来表示，分别在 P珔和 P 找到值最小的点分别设为 i， j，然后分别取出这两个点加到树上去，一直重复上述的步骤， 知道 P 为空。此时 P珔中只剩下两个顶点，最后将这两个顶点 连接起来加入到树中，最终得到树与刚开始的 P 相对应。 图 1 所示是一个生成树，图 2 所示的是一个与树相对用 的 Prüfer 编码图。由下面两幅图我们可以看到生成树一个 比较通俗的表示方式就是 Prüfer 编码，并且 Prüfer 编码的每 个信息量非常的适宜遗传系统。
自然界中进化算法的重要组成部分，主要应用在自然研究领 域和具有自适应特征的系统中。遗传算法的突出的特征在
于在群体中能够搜索到最优解，并且各个个体之间也能相互 的交换信息，是一个找寻全局最优化的解，它能够从总体的 角度出发，通 过 一 些 列 的 变 化 和 操 作，得 到 总 体 上 的 最 优。 近年来，由于遗传算法的特征优势在各个方面的成功应用， 得到了越来越多的关注。
较而言是目标函数不是一个，并且各个目标函数之间可以是
相互的对立，导致无法需求最小生成树来的算法，但将这么
多的目标逐步单一的去解决的话 ，也相当于只是寻找其中
的一个解，根本达不到多目标最小生成树的目的，所以针对
上述问题，想要解决有一定的难度。
3 遗传算法求解多目标优化
3． 1 遗传算法基本原理 John Holland 提出 的 遗 传 算 法［5］ （ Genetic Algorithm） 是
基金项目： 曲靖师范学院专项基金项目（ 2008ZX003） 收稿日期： 2011 － 07 － 17 修回日期： 2011 － 09 － 30
针对以上问题，本文提出了一种改进的遗传算法求解最 小生成树算法。遗传算法是一种模拟自然进化过程的随机 搜索算法，该算法能够在较短的时间内以非常高的概率获取 一组 最 小 生 成 树，实 验 结 果 表 明，与 经 典 的 Prim 算 法 和 Kruskal 算法相比，新算法复杂度较低，并能在第一次遗传进 化过程中获得一批最小生成树，适合于解决不同类型的多目 标最小树问题。特别的本文主要难点技术问题在于采用的 改进的遗传算法的交叉变异操作来优化多目标生成树，这样 就大大的降低了算法的复杂性。