超启发式三维EDA求解绿色双边装配线平衡问题

Hyper-heuristic Three Dimensional EDA for Solving Green Two-Sided Assembly Line Balancing Problem

针对绿色机器人的第Ⅰ类双边装配线平衡问题(green robotic two-sided assembly line balancing problem of type-Ⅰ, GRTALBP-Ⅰ),建立问题模型并提出一种超启发式三维分布估计算法(hyperheuristic three dimensional estimation of distribution algorithm, HH3DEDA)进行求解。在HH3DEDA中,结合问题特征,设计基于工序选择因子的组合编码,进而设计高低分层结构的HH3DEDA。在高层,采用三维概率矩阵学习优质高层个体中块结构及其分布信息,后通过采样该矩阵以生成新的高层个体,其中高层个体由结合问题特点设计的12种启发式操作的排列构成;在低层,将高层每个个体所确定启发式操作排列作为一种新的启发式算法对GRTALBP-Ⅰ解空间执行较深入搜索。同时,引入机器人开关机节能策略,进一步提升所获取非支配解的质量。通过仿真对比实验,验证了所提算法的有效性。

This paper establishes a model for green robotic two-sided assembly line balancing problem of type-I,and a hyper-heuristic three dimensional estimation of distribution algorithm(HH3DEDA)is proposed for solving this problem.In HH3DEDA,a combinatorial encoding rule based on process selectors is designed via considering the characteristics of the problem.Then,HH3DEDA with a high and low layered structure is proposed.In the upper layer,the three-dimensional probability matrix is utilized to learn high-quality high individual block structure and its distribution information,and then the matrix is sampled to generate new high level individuals.Each high individual is composed by 12 heuristic operations,which are designed via considering the characteristics of the problem.In the lower layer,the high individual determined heuristic operation permutation is used as a new heuristic to perform a deep search for the GRTALBP-I solution space.Meanwhile,the energy saving strategy of robot switching machine is utilized to enhance the quality of obtaining the non-dominated individuals.Simulation experiments demonstrate the effectiveness of the proposed algorithm.