Page 154 - 《软件学报》2020年第9期

蔺一帅 等:智能仓储货位规划与 AGV 路径规划协同优化算法 2775

4. fit←fit_val(P k ) /*计算适应值*/
5. Best_fit←fit /*初始化最佳个体*/
6. for k to Max_Gerenation
7. selectoperator /*选择算子*/
8. crossings /*交叉操作*/
9. variation /*变异操作*/
10. P k ←Rebuild(P k ) /*再次优化路径*/
11. if Best_fit<fit_val(P k ) /*判断是否为最佳个体*/
12. then Best_fit←fit_val(P k ) /*代替最佳个体*/
13. end if
14. end for
15. return P Best
16. end funcation
具体来说,在遗传算法计算过程中,首先对目标结果进行编码,路径编码方式为排列编码.例如,[1,2,5,6,7,8]
表示从 1 号点出发,途径 2,5~7 这些点,最终到达 8 号点.路径坐标点序号作为基因参与算法运算.根据起始点到
目标点序号,生成随机可行的路径序列,称为初始种群.
然后对此种群进行适应值计算,如公式(7)所示:
1
fit = (7)
⎛ ⎛ 1 ⎞ ⎞
⎜ path length ⎜ *1+ ⎟ ⎟
⎜ ⎜ node − 1 ⎟ ⎟
⎝ ⎝ num ⎠ ⎠
其中:path length 参数与 fit 适应度值成反比,表示路径越短,适应度值越优秀,选择出来的路线也越贴近最优解.适应
值越大,意味着这个个体越优秀.node num 表示转弯次数,取值大于等于 1.node num 参数的添加,是考虑到转弯因素
对路径规划的影响,1+ 1 系数对 path length 参数的微调,使算法在路径选择中尽可能避免选择拐弯次数
node − 1
num
过多的路线.经过实验验证:node num 的加入,有效地减少了算法选择转弯次数过多的路线.将基于该公式计算出
的初始种群中所有个体的适应值记录下来,再对此种群进行交叉和变异操作.
本文基于轮盘赌法对交叉和变异操作的对象进行选取,以使得适应度越大的个体被选中的概率越大.轮盘
赌选算子可以根据个体适应值在群体中所占比例,结合该算子被选中的累积概率,再取一个 0 到 1 之间的随机
值,比较子代个体的适应度比例和随机值大小,选取子代适应值高的个体参与到遗传运算中,进一步提高整个种
群的适应值,从而取得更优的最终结果,或者让该种群向更优的结果发展.具体来说,我们先计算该种群的适应
值总和 fit_sum,然后,计算每个个体的适应值占比 rfit=fit/it_sum 和各部分累积概率 cfit(如公式(8)所示):
cfit = cfit + rfit (8)
popnext i popnext i− 1 popnext i
其中,i≤popsize(种群大小),popnext i 为第 i 代种群,popcurrent i 为第 i 代种群的副本.
随后遍历种群副本 popcurrent i ,而后生成一个 0-1 之间的随机数 p.比较子代个体的 cfit 和 p 的值,直到 cfit
比 p 大时,该个体代替 popcurrent i 中此位置的个体.最后,将 popcurrent i 的所有值赋给 popnext i .
在交叉操作的实现中,交叉次数是路径点总数的 1/4,具体计算出的次数向下取整.每次交叉操作方法相同.
首先,随机选取此种群中的某一条路径,在此路径上找到一个随机点设为交叉点 q,然后寻找另一条也通过此点
的基因.设 p1,p2 为原选出基因.将 p1 中 q 点以后的点被 p2 中 q 点以后的点代替生成新的基因 p1,再将 p2 中 q
点以后的点由 p1 中 q 点以后的点代替生成新的基因 p2.对 p1 和 p2 进行路径再优化,然后计算并更新 p1 和 p2
的适应值、路径长度和转弯次数,完成交叉操作.
在变异操作中,首先判定是否发生变异.基于预设变异几率(mutationRate),根据 random=Math.random(⋅)*
(1.0/mutationRate)计算变异率(Math.random(⋅)为随机数生成函数).此时,若 random 为 0,则执行变异.变异时,先随