最小生成树问题的分析与研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇最小生成树问题的分析与研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

引言

组合优化研究的是具有有限个可行解的优化问题。其中最具挑战性的问题就是组合爆炸。近年来，遗传算法在组合优化学界里日益受到重视，并在许多工业工程实验与实际应用中取得了良好的成果，特别是在解决组合优化领域中的最小生成树问题MST中，显示了它的巨大潜力。

一、问题的描述

考虑一个连通的无向图G=(V,E)，其中,V={ν1,ν2,…,νn}是代表终端或通信站的有线的端点集。 E={eij|eij=(νi,νj),νi,νj∈V}是代表终端或站间连线的有限边集。每条边由一个记为W={wij|wij=w(νi,νj),wij＞0,νi,νj∈V}的正实数的权重，代表距离、价格等。生成树是连接V中所有端点的来自E的最小边集，因此对于图G至少可找到一棵生成树。最小生成树记为T*，是边的权重和最小的生成树。其描述如下:，其中,T为图G的生成树的集合。

在一些实际问题中，端点的度不是可任意选取的。通信网络中为防止节点故障带来的脆弱性，对节点的度也有限制。即确定极小化总的边权的生成树时，往往要求端点νi的度di不大于一个给定值bi。令T*dc是图G的所有树中满足度约束的最小生成树，则问题可描述为:。为方便起见，这里仅讨论完全图上的对称问题，即，wij=wji,且bi=b对所有νi∈V。

二、染色体表达

dc-MST问题是MST问题加上度约束的扩展，所以染色体表达中应含有显式的或隐式的各个端点的度信息。在几种树的编码中，只有Prufer数编码含有显式端点的度的信息，在Prufer数编码中度为d的端点正好出现d-1次。因此，通常采用Prufer数编码。

三、交叉和变异

Prufer数编码任意交叉和变异后仍代表一棵树。简单的采用单点交叉，变异则可随机的变为1和n中的一个整数。由于存在度约束，无论是出始终群众随机产生的染色体，还是交叉或变异产生的后代都可能不满足度约束，即为非法的。因此需要改进染色体中的非法端点，采用Prufer数编码则容易做到。令是染色体中未做度检查的端点集。如一个端点违反度约束，即编码中该端点出现的次数大于d-1，那么将多出的端点随机的替换为的其他端点就可减少该端点的度。

四、评估与选择

评估过程由两步组成:转换染色体为树;计算树的总权。

令P为染色体是合格端点集。适值可以按权系数矩阵W=[wij]计算。

五、dc-MST算法

和传统的遗传算法相比，该算法的主要特点是为满足度约束在简单遗传算法中嵌入了度改进步骤。整个dc-MST计算步骤如下:

begin

t0; 初始化P(t); 改进P(t)的度; 评估P(t);

while不满足终止条件 do

重组P(t)获得C(t); 改进C(t)的度; 评估C(t)； 从P(t)和C(t)中选择P(t+1);

tt+1;

end

end

六、数值例子

以下例子是Savelsbergh和Volgenant给出的，它们用分支定界法求得的最优解的值为225。这是一个9节点的完全图，下为9节点dc-MST问题的边权重。

遗传算法的参数设定如下:种群大小pop=size=50,交叉率pc=0.5，变异率pm=0.01，最大代数max_gen=500，所有端点的限定度b=3，运行30次。

用该GA算法，多数运行都能达到最优值2256。这表明，GA法不用启发式或问题的专门性质，就能通过表达解的染色体的繁殖过程以高的概率达到最优解。

七、结论

比较两种选择策略。具体数据为:

说明了两种方法都能获得最优解，但采用混合选择策略的GA比转轮法的平均目标值和相对误差都要好一些。

组合优化研究的是具有有限个可行解的优化问题。在日常生活中，特别是在工程设计中，有许多这样的问题。其中一个重要而广阔的应用领域就是如何有效的利用不充足的资源以提高生产效益。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。