﻿ 面向堆垛机路径优化的局部搜索自适应遗传算法
 计算机系统应用  2020, Vol. 29 Issue (8): 230-235 PDF

1. 中国科学院大学, 北京 100049;
2. 中国科学院 沈阳计算技术研究所, 沈阳 110168

Local Search Adaptive Genetic Algorithm for Stacker Path Optimization
SHI Qin-Zheng1,2, WANG Song2, LI Dong-Mei2, GAO Cen2, TIAN Yue2
1. University of Chinese Academy of Sciences, Beijing 100049, China;
2. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China
Abstract: In order to improve the operation efficiency of the three-dimensional warehouse, aiming at stacker path scheduling problem, a stacking machine scheduling optimization model is established based on the time, energy consumption, and operation efficiency, and an Improved Multi-Objective Genetic Algorithm (IMOGA) is proposed. In IMOGA, genetic operator is improved based on NSGA-Ⅱ, crossover and mutation operations are designed for this model, adaptive genetic operator is introduced, and a local random search strategy based on the simulated annealing is added. The IMOGA is validated through the stacker scheduling situation in a spandex factory warehouse. The results show that convergence speed of IMOGA is faster, the quality of the solution set is higher, and it has higher applicability in stacker scheduling.
Key words: adaptive genetic algorithm     stacker scheduling     local random search     Pareto front

1 堆垛机调度模型 1.1 问题描述

 图 1 自动化无人仓库部分示意图

1.2 模型建立

 $\left\{ \begin{array}{l} \min T = \displaystyle\sum\limits_{i = 1}^{m - 1} {{t_{i(i + 1)}}} \\ \min E = \displaystyle\sum\limits_{i = 1}^{m - 1} {{e_{i(i + 1)}}} \\ \min Eff = \displaystyle\sum\limits_{i = 1}^m {{t_{0i}}} \frac{1}{{{f_i}}} \\ \end{array} \right.$ (1)

 ${e_{ij}} = {e_x}\left| {{x_i} - {x_j}} \right| + {e_y}\left| {{y_i} - {y_j}} \right|$ (2)
 ${t_{ij}} = \max \left(\dfrac{{\left| {{x_i} - {x_j}} \right|L}}{{V(x)}},\dfrac{{\left| {{y_i} - {y_j}} \right|H}}{{V(y)}}\right)$ (3)

2 基于局部随机策略的自适应遗传算法

2.1 染色体编码

2.2 自适应遗传算子

 图 2 货位示意图

 图 3 改进后的交叉操作

 图 4 改进后的变异操作

 ${P_c} = \left\{ \begin{array}{l} {P_{c\min }} + \dfrac{{{P_{c\max }} - {P_{c\min }}}}{{1 + \exp [A\dfrac{{2({f^{'}} - {f_{\rm avg}})}}{{{f_{\max }} - {f_{\rm avg}}}}]}},\;\;\;\;{f^{'}} \ge {f_{\rm avg}} \\ {P_{c\max }},\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{f^{'}} < {f_{\rm avg}} \\ \end{array} \right.$ (4)
 ${P_m} = \left\{ \begin{array}{l} {P_{m\min }} + \dfrac{{{P_{m\max }} - {P_{m\min }}}}{{1 + \exp [A\dfrac{{2(f - {f_{\rm avg}})}}{{{f_{\max }} - {f_{\rm avg}}}}]}},\;\;\;\;f \ge {f_{\rm avg}} \\ {P_{m\max }},\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f < {f_{\rm avg}} \\ \end{array} \right.$ (5)

2.3 基于模拟退火算法的局部随机搜索策略

 $p = \left\{ \begin{array}{l} \exp ( - \dfrac{{f({x_1}) - f({x_0})}}{{kT}}),\;\;\;\;\;f({x_1}) \ge f({x_0}) \\ 1,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f({x_1}) < f({x_0}) \\ \end{array} \right.$ (6)

 $T(t) = \dfrac{{{T_0}}}{{\log (1 + t)}}$ (7)

Step 1. 设置初始参数: 初始状态温度 ${T_0}$ , 迭代次数上限n, 邻域内搜索次数m, 邻域内搜索上限M次.

Step 2. 遗传算法进化得到非劣解集 $S$ , 非劣解集 $S$ 中解用 ${x_i}$ 表示.

Step 3. 若在解 ${x_i}$ 的一定邻近范围内随机搜索得到新解 ${y_i}$ , 计算 $\Delta E = f({y_i}) - f({x_i})$ , 若 $\Delta E < 0$ , 则接受新解 ${y_i}$ 取代 ${x_i}$ , 跳至Step6; 若 $\Delta E \ge 0$ , 则随机生成概率r, 跳至Step 4.

Step 4. 按照新解接受概率公式, 若 $r < \exp ( - \Delta E/kT)$ , 则接受新解 ${y_i}$ , m=0并跳至Step 6, 否则, m++.

Step 5. 若m<M, 跳至Step3.

Step 6. 更新温度T, 迭代次数若超过最大次数, 终止. 否则, 返回Step 2.

3 实验分析

 $\begin{split} D =& [(10,10);(5,2);(17,2);(20,19);(7,5);(15,2);\\ & (9,9);(19,14);(13,2);(23,9);(16,8);(1,5);\\ & (16,19);(8,10);(22,16)] \end{split}$

 图 5 时间原则算法迭代过程

 图 6 能耗原则算法迭代过程

 图 7 作业效率原则算法迭代过程

 图 8 初始序列路径图

 图 9 Pareto解1路径图

 图 10 Pareto解2路径图

 图 11 Pareto解3路径图

 ${D_{IR}}({S_j}) = \dfrac{1}{{\left| {{S^*}} \right|}}\displaystyle\sum\limits_{y \in {S^*}} {\min \left\{ {{d_{xy}}|x \in {S_j}} \right\}}$ (8)

 ${d_{xy}} = \sqrt {\displaystyle\sum\limits_{i = 1}^N {{{(f_i^*(y) - f_i^*(x))}^2}} }$ (9)

4 结语

 [1] 任为. 立体仓库货位优化与仿真研究[硕士学位论文]. 徐州: 中国矿业大学, 2015. [2] 韩红艳. 基于Pareto支配的高维多目标进化算法研究[硕士学位论文]. 大连: 大连理工大学, 2016. [3] 关榆君, 和淼. 基于猫群算法的立体车库调度优化. 华北理工大学学报:自然科学版, 2018, 40(4): 94-99. [4] Deb K, Agrawal S, Pratap A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. Proceedings of the 6th International Conference on Parallel Problem Solving from Nature. France. 2000. 849–858. [5] 路艳雪. NSGA-Ⅱ多目标优化算法的改进及应用研究[硕士学位论文]. 太原: 太原理工大学, 2017. [6] 魏冰. NSGA-Ⅱ算法的改进及在机组组合优化中的应用[硕士学位论文]. 北京: 华北电力大学, 2019. [7] 曲志坚, 张先伟, 曹雁锋, 等. 基于自适应机制的遗传算法研究. 计算机应用研究, 2015, 32(11): 3222-3225, 3229. DOI:10.3969/j.issn.1001-3695.2015.11.004 [8] 缪朝炜, 苏瑞泽, 张杰. 越库配送车辆调度问题的自适应遗传算法研究. 管理工程学报, 2016, 30(4): 166-172. [9] 何庆, 吴意乐, 徐同伟. 改进遗传模拟退火算法在TSP优化中的应用. 控制与决策, 2018, 33(2): 219-225. [10] Knowles J, Corne D. On metrics for comparing nondominated sets. Proceedings of 2002 Congress on Evolutionary Computation. Honolulu, HI, USA. 2002. 711–716.