基于遗传算法配用电通信网最优路径选择的方法

摘要

本发明公开了一种基于遗传算法的配用电电信网最优路径选择的方法，其特征是按如下步骤进行：1建立单向拓扑网络；2采用二进制编码初始化种群；3设定迭代次数；4选择运算；5交叉运算；6变异运算；7判断；8输出最优路径。本发明能在满足约束条件的基础上，高效地寻找出最优路径，从而能够提高搜索效率，降低搜索复杂度。

主权项

一种基于遗传算法的配用电通信网最优路径选择的方法，所述配用电电信网是以n个光纤交接箱作为网络节点并通过光纤连接而成的单向拓扑网络，其特征是按如下步骤进行：步骤1、建立单向拓扑网络设定所述单向拓扑网络中从第1个网络节点到第n个网络节点有M条路径，则所述单向拓扑网络的模型和最优路径函数分别如式(1)和式(2)所示：L＝Min(A₁,A₂,…,A_k,…,A_M)   (2)并有：$A_k=\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{l}_{\mathrm{ij}}\mathrm{sign}(i,j,k),(k=\mathrm{1,2},...,M)---\left(3\right)$式(3)中，l_ij表示网络节点i到网络节点j的光纤长度；若网络节点i与网络节点j之间没有光纤到达，则l_ij＝∞；设置网络节点i与自身的网络节点i的光纤长度l_ii＝0；步骤2、采用二进制编码初始化种群：设置种群大小为N＝2n、种群个体集合Y＝{Y₁,Y₂,…,Y_p,…,Y_N}1≤p≤N；Y_p表示任意一个种群个体，以任意一个种群个体代表从第1个网络节点到第n个网络节点的任意一条路径，N≤M；所述种群个体Y_p＝{X₁,X₂,…,X_q,…,X_n}，2≤q≤n‑1；X_q表示任一个体染色体；以任一个体染色体代表所述单向拓扑网络中任意一个网络节点；令X₁＝1和X_n＝1，表示任意一条路径必须经过第1个网络节点和第n个网络节点；X_q的值利用随机函数Rand()取[0,1]之间随机数，若随机数大于等于0.5，则X_q＝1，表示任意一条路径经过网络节点q；否则，X_q＝0，表示任意一条路径未经过网络节点q；设定X_t＝1，表示任意一条路径中必须经过网络节点t；X_r＝0，表示任意一条路径中不能经过网络节点r；2≤t,r≤n‑1；步骤3、设定迭代次数I∈[30,200]；设定初始迭代I_init＝0；步骤4、选择运算：步骤4.1、利用式(4)获得任意一个种群个体的自适应度函数Fit(k)，从而获得所有种群个体的适应度函数：$\mathrm{Fit}\left(k\right)=D_{\max }-\underset{i=1}{\overset{n}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{l}_{\mathrm{ij}}\mathrm{sign}(i,j,k),1\le k\le N---\left(4\right)$式(4)中，D_max表示所述单向拓扑网络中从第1个网络节点到第n个网络节点的所经过的路径长度之和的最大值；步骤4.2、采用精英选择方法从N个种群个体的适应度函数中选择一个最大的适应度函数值所对应的种群个体作为交叉运算的一个种群个体；步骤4.3、采用如式(5)所示的轮盘赌选择方法计算任意一个种群个体的选择概率F_k，从而获得N‑1个种群个体的选择概率：$F_k=\frac{\mathrm{Fit}\left(k\right)}{\underset{k=1}{\overset{N-1}{\Sigma }}\mathrm{Fit}\left(k\right)}---\left(5\right)$步骤4.4、将N‑1个种群个体的选择概率所表示的概率区域组成一个轮盘，则N‑1个种群个体的选择概率之和为1；在[0,1]之间产生N‑1个随机数，以所述随机数在轮盘中所匹配的概率区域来选择与所述概率区域相对应的种群个体；以所述选中的种群个体作为交叉运算的N‑1个种群个体；由所述交叉运算的一个种群个体和交叉运算的N‑1个种群个体构成交叉种群个体；步骤5、交叉运算：步骤5.1、从所述交叉种群个体中任意取两个种群个体并按照步骤5.2进行匹配，直到完成N/2次配对，从而获得N个变异种群个体；步骤5.2、对所任意两个种群个体中的每一个个体以交叉点位置进行交换，所述交叉点位置是在[2,n‑1]中取随机整数α；若随机整数α＝t或α＝r，则不进行交换；步骤6、变异运算：步骤6.1、从N个变异种群个体中任意取一个种群个体，在[2,n‑1]中取一个随机整数β；以所述随机整数β作为基因变异位置对所述种群个体中相应的个体按照步骤6.2进行变异运算，直到N个变异种群个体完成变异运算，从而获得N个下一代种群个体；若随机整数β＝t或β＝r，则不进行变异运算；步骤6.2、设定变异运算的概率为P_m，P_m∈[0.001,0.2]；在[0,1]中取一个随机数Q，当P_m≤Q时，对所述种群个体中第β个基因变异位置的个体染色体进行取反；步骤7、将I_init+1赋值给I_init；步骤8、判断I_init≤I是否成立，若成立，则以所述N个下一代种群个体作为新的种群个体，并返回步骤4执行，否则执行步骤9；步骤9、输出最优路径：利用式(4)获得所述N个下一代种群个体中的每个个体的适应度函数；选择适应度函数值最大的个体为最优个体；以所述最优个体作为最优路径。