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

广义最小生成树的遗传算法求解及应用纲要
广义最小生成树的遗传算法求解及应用纲要
1/13
广义最小生成树的遗传算法求解及应用纲要
2004年3月第26卷第3期
系统工程与电子技术
Sy
∑
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———今世种群的平均适应值。
当种群中有几个适应值显然大于其余个体的“超级个体”存在时,若采用传统的“轮盘赌”选择方式,会致使这些个体快速繁殖,经过几次迭代后占满了种群的地点,
使种群的多样性急剧下