混合离散粒子群算法求解机器人装配线平衡问题

Hybrid discrete particle swarm algorithm for robotic assembly line balancing problem

以最小化总成本为目标,将一组工序和机器人分配至工作站上的问题称为面向成本的机器人装配线平衡问题(cRALBP),为了解决此NP难问题,提出一种混合离散粒子群优化(HDPSO)算法.首先,对于给定工序,设计动态规划方法直接获取工序对应的最优机器人分配方案,从而缩小搜索空间,提高算法的全局寻优能力.然后,提出一种新的算法框架,其通过融合路径重连加强算法的局部搜索能力,并通过汉明距离评估解之间的差异,选择采用多片段交叉算子或者片段变异算子进行粒子更新,取代随机选择算子的方法,从而实现算法全局搜索和局部搜索的平衡.将所提出的HDPSO算法与最新的粒子群、人工鱼群算法在144个算例上进行对比,验证了HDPSO算法的有效性和优越性.

The problem of assigning a group of tasks and robots to workstations with the objective of minimizing the total cost is called the cost-oriented robotic assembly line balancing problem(cRALBP).To solve the NP-hard problem,a hybrid discrete particle swarm optimization(HDPSO)algorithm is proposed.First,for a given task permutation,the dynamic programming is designed to directly obtain the optimal robot allocation corresponding to the task permutation,so as to reduce the search space and improve the global search ability.Then,a novel algorithm framework is proposed,which employs the path-relinking to strengthen the local search ability,and uses Hamming distance for evaluating the differences between solutions instead of the random operator selection method to decide whether to choose multi-fragment crossover operator or fragment mutation operator for updating,and thus the balance between global search and local search of the algorithm is achieved.The HDPSO algorithm is compared with the latest PSOs and the artificial fish swarm algorithm on 144 cases to verify the effectiveness and superiority of HDPSO algorithm.