改进蚁群算法求解单行设施布局问题

Improved Ant Algorithm for Single Row Facility Layout Problem

针对单行设施布局问题已有算法结构复杂、对算法参数有较大依赖性、求解效果欠佳的问题,提出一种改进的蚁群算法。该算法采用基于目标函数值的自适应等级划分策略,实现了信息素增量优胜劣汰、改进信息素的更新规则。通过简化状态转移概率函数,降低计算量和算法对参数的依赖性,引入精英候选集,提高优良设备的选择概率。同时,采用基于插入式邻域结构的爬山寻优算法作为局部搜索进行深度搜索。仿真结果表明,求解28个大规模的测试例子时,该算法总的平均运行时间分别为混合遗传算法的14%,Lin-Kernighan算法的5%,分散搜索算法的50%,说明该算法可在短时间内较稳定地得到高质量的近优解,性能优越于其他算法。

We proposed an improved ant colony optimization algorithm to solve the problem that the structure of proposed algorithms are complicated,parameters of the algorithms are depended on and effect of the algorithms is not well about the single row facility layout problem. A strategy based on the adaptive classification of objective function value was designed to implement the survival of the fittest for pheromone increment,improving the pheromone updating rule. By simplifying the transition probability,the calculation complexity and dependence on the parameters were reduced. Elite candidates were introduced to increase the probability of selecting good facilities. And a hill climbing method based on insertion neighborhood structure was introduced into the ant algorithm for local optimization. The simulation results show that as to the total average time of 28 large instances,the proposed algorithm is just 14% of Hybrid Genetic Algorithm,5% of Lin-Kernighan Heuristic and50% of Scatter Search Algorithm. So the algorithm can converge to optimal solutions speedily and stably. The performance of the proposed algorithm is better than other algorithms.