首页 | 本学科首页   官方微博 | 高级检索  
     

改进蚁群算法求解单行设施布局问题
引用本文:关健,林耿. 改进蚁群算法求解单行设施布局问题[J]. 吉林大学学报(信息科学版), 2016, 34(4): 528-535. DOI: 10.3969/j.issn.1671-5896.2016.04.012
作者姓名:关健  林耿
作者单位:闽江学院现代教育技术中心,福州,350108;闽江学院数学系,福州,350108
基金项目:国家自然科学基金资助项目(11301255),福建省自然科学基金资助项目(2016J01025;2016J01025),闽江学院科技基金资助项目(MYK15005)
摘    要:针对单行设施布局问题已有算法结构复杂、对算法参数有较大依赖性、求解效果欠佳的问题, 提出一种改进的蚁群算法。该算法采用基于目标函数值的自适应等级划分策略, 实现了信息素增量优胜劣汰、改进信息素的更新规则。通过简化状态转移概率函数, 降低计算量和算法对参数的依赖性, 引入精英候选集, 提高优良设备的选择概率。同时, 采用基于插入式邻域结构的爬山寻优算法作为局部搜索进行深度搜索。仿真结果表明, 求解28 个大规模的测试例子时, 该算法总的平均运行时间分别为混合遗传算法的14%, Lin-Kernighan 算法的5%, 分散搜索算法的50%, 说明该算法可在短时间内较稳定地得到高质量的近优解, 性能优越于其他算法。

关 键 词:单行设施布局  蚁群算法  爬山法  局部搜索
收稿时间:2015-08-27

Improved Ant Algorithm for Single Row Facility Layout Problem
GUAN Jian,LIN Geng. Improved Ant Algorithm for Single Row Facility Layout Problem[J]. Journal of Jilin University:Information Sci Ed, 2016, 34(4): 528-535. DOI: 10.3969/j.issn.1671-5896.2016.04.012
Authors:GUAN Jian  LIN Geng
Affiliation:a. Modern Educational Technology Center; b. Department of Mathematics, Minjiang University, Fuzhou 350108, China
Abstract: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 and 50% 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.
Keywords:single row facility layout problem  ant colony optimization  hill climbing method  local search
本文献已被 万方数据 等数据库收录!
点击此处可从《吉林大学学报(信息科学版)》浏览原始摘要信息
点击此处可从《吉林大学学报(信息科学版)》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号