广义最小生成树的遗传算法求解及应用概要.doc

广义最小生成树的遗传算法求解及应用纲要
广义最小生成树的遗传算法求解及应用纲要
1/13
广义最小生成树的遗传算法求解及应用纲要
2004年3月第26卷 第3期
系统工程与电子技术
S
=min
T
∑
eij
∈T
ij
(2
MST是一种抽象的数学模型,它能够详细化为电力网络、通讯网络、交通
道路等实质对象,此时MST的物理含义就是系统的最小距离、最小花费或许最小
消耗等指标。所以
MST问题的求解,在工程设计规划中,拥有较高的适用价值。
以上模型并无波及节点度的问题。所谓节点的度 (以
dj表示,是指与该节点相连的边的数目。在 n节点的生成
树中,度的理论最大值为 n-1,可是在实质工程中,节点的度是不可以随意选用
的。比如,在通讯网络的规划设计中 ,为防备节点故障惹起的网络的柔弱性 ,对节点
的度有所限制。为认识决这一矛盾 ,文件[1]提出了度拘束最小生成树 ,即在
广义最小生成树的遗传算法求解及应用纲要
广义最小生成树的遗传算法求解及应用纲要
5/13
广义最小生成树的遗传算法求解及应用纲要
式(1的基础上,增添拘束条件
dj ≤bj,j=1, ,n
(3
度拘束最小生成树仍旧是一种理想化的模型 ,因为它不过简单的给出了度的限
制。
为了使问题进一步靠近于实质应用 ,本文提出了广义最
小生成树(generalizedminimumspanningtree,GMST。GMST的
不一样之处在于
,它以为节点度的存在是有代价的 ,而且对这类代价进行了量化。定义度的权值
为
ξ=ξ(d,d=1, -1 ,n
(4
往常状况下ξ是对于d的单一非减函数。此时 GMST能够描绘为
T
3
广义最小生成树的遗传算法求解及应用纲要
广义最小生成树的遗传算法求解及应用纲要
6/13
广义最小生成树的遗传算法求解及应用纲要
=minT
广义最小生成树的遗传算法求解及应用纲要
广义最小生成树的遗传算法求解及应用纲要
13/13
广义最小生成树的遗传算法求解及应用纲要
(
∑
eij
∈T
wij
+
∑
n
k=1
(dk
(5
能够以为,度拘束最小生成树其实是 GMST的一个特例。
MST的扩展一般是NP难问题,不存在多项式时间解法。
依据图论计算中的 Cayley定理,在一个n节点的完整图中,有n
(n-2
个不一样的树。对于 30个节点的完整图,总合有
×
个生成树,搜寻空间巨大。有些研究者 [1,2]
广义最小生成树的遗传算法求解及应用纲要
广义最小生成树的遗传算法求解及应用纲要
8/13
广义最小生成树的遗传算法求解及应用纲要
用
广义最小生成树的遗传算法求解及应用纲要
广义最小生成树的遗传算法求解及应用纲要
13/13
广义最小生成树的遗传算法求解及应用纲要
遗传算法和进化规划来求解该问题 ,获得了比较好的结果。本文相同采纳遗传
算法来求解GMST问题。
改良的遗传算法
遗传算法是模拟自然界生物进化过程的计算模型。与传统的优化算法对比 ,遗
传算法是一种高度并行、随机、自适应的全局搜寻算法码的个体空间 ,其实不需要梯
度等高阶条件,组合优化一类的问题搜寻算法 ,,堕入局部最优,,使算法能更为有效
地求解
GMST问题。
限制父代个体保存数目的混淆选择策略 :第一定义合格个体的判断函数
Qua(T=
1,若Fit(T> μFitavg0,
其他
(6
式中:μ≥———合格系数,Fitavg———今世种群的均匀适应值。
当种群中有几个适应值显然大于其他个体的“超级个体”存在时,若采纳传统的“轮盘赌”选择方式,会