禁忌搜索算法与蚁群算法的混合策略在二次分配问题上的应用

doi:10.3969/j.issn.10062475.2009.10.001

计算机与现代化 ›› 2009, Vol. 1 ›› Issue (10): 1-3.doi: 10.3969/j.issn.10062475.2009.10.001

• 算法分析与设计 • 下一篇

禁忌搜索算法与蚁群算法的混合策略在二次分配问题上的应用

吕聪颖，赵刚彬，王保胜

南阳理工学院计算机科学与技术系,河南南阳 473004

收稿日期:2009-04-16 修回日期:1900-01-01 出版日期:2009-10-15 发布日期:2009-10-15

Application of Hybrid Strategy Based on Tabu Search and Ant Colony Algorithm to Quadratic Assignment Problem

LU Cong-ying,ZHAO Gang-bin，WANG Bao-sheng

Department of Computer Science and Technology, Nanyang Institute of Technology, Nanyang 473004， China

Received:2009-04-16 Revised:1900-01-01 Online:2009-10-15 Published:2009-10-15

摘要/Abstract

摘要： 二次分配问题是一个NPhard问题，它在线路板设计、布局问题以及打字机键盘的设计等现实生活中有许多的应用。使用基本蚁群算法进行搜索时，其全局优化性能的优劣在很大程度上与蒸发系数的选择有关，若选择不合适，易使算法陷入局部最优。为此，本文提出一种新的算法，即将基本蚁群算法与禁忌搜索策略相结合来求解二次分配问题，设计出具体的算法模型，并对标准问题库中的具体实例进行测试，实验结果证实新方法的有效性。

关键词: 二次分配问题, 蚁群算法, 禁忌搜索

Abstract: Quadratic Assignment Problem(QAP) is a NPhard problem and it has numerous real life applications in, for example, school layout, circuit board designing and typewriter keyboard designing. Ant Colony Algorithm (ACA) behaves well in finding local optium, whereas its global search depends on selection of the evaporation coefficient. An unsuitable evaporation coefficient may result in local optium of final solutions. So this paper presents a new Hybrid Ant Colony Algorithm (HACA) to solve quadratic assignment problem. The results obtained show that the new approach is efficient.

Key words: Quadratic Assignment Problem, ant colony algorithm, tabu search

吕聪颖;赵刚彬;王保胜. 禁忌搜索算法与蚁群算法的混合策略在二次分配问题上的应用[J]. 计算机与现代化, 2009, 1(10): 1-3.

LU Cong-ying;ZHAO Gang-bin;WANG Bao-sheng . Application of Hybrid Strategy Based on Tabu Search and Ant Colony Algorithm to Quadratic Assignment Problem[J]. Computer and Modernization, 2009, 1(10): 1-3.

[1]	张雄, 潘大志, . 融合邻域搜索策略蚁群算法求解带时间窗口的车辆路径问题[J]. 计算机与现代化, 2022, 0(03): 98-102.
[2]	曲建波, 孙剑伟. 基于蚁群算法的导航卫星功率增强任务规划[J]. 计算机与现代化, 2021, 0(02): 104-108.
[3]	高月仁, 吴涛, 高峡. 基于蚁群算法优化的路由频率动态择径的研究[J]. 计算机与现代化, 2020, 0(12): 32-37.
[4]	李显良1,2，周庆平2，谭长庚3，谭焱良2，徐则阳2. 基于蚁群算法的城市体育设施优化选址[J]. 计算机与现代化, 2020, 0(03): 33-.
[5]	叶家琪1，符强1，2，贺亦甲1，叶浩1 . 基于聚类集成的蚁群算法求解大规模TSP问题[J]. 计算机与现代化, 2020, 0(02): 31-.
[6]	梁晶亮,黄军胜,白树军,王鹏,李睿. 基于蚁群算法的电力数据网络APT攻击预警模型[J]. 计算机与现代化, 2019, 0(01): 95-.
[7]	付永忠，潘云峰. 基于改进蚁群算法的垂直旋转式贴片机贴装顺序优化[J]. 计算机与现代化, 2017, 0(8): 17-.
[8]	凌云翔1,2,宋志远1,张世海1,马力2. 基于蚁群算法的高原地区车辆运输路径优化问题[J]. 计算机与现代化, 2016, 0(9): 77-82.
[9]	宋琪，敬超. 面向多核系统的蚁群最优化能耗调度算法[J]. 计算机与现代化, 2016, 0(6): 91-96.
[10]	蔡明，左勇安. 基于MapReduce的混合蚁群算法研究[J]. 计算机与现代化, 2016, 0(10): 6-.
[11]	李媛祯，杨群，段汐. 基于均衡更新蚁群算法的飞机排序调度[J]. 计算机与现代化, 2015, 0(2): 57-.
[12]	蔡文哲，王斌君. 一种QoS平面蚁群路由算法的设计与实现[J]. 计算机与现代化, 2015, 0(12): 15-.
[13]	陈曼青1，武子荣1，崔伟宁1，常婷婷2. 改进蚁群算法在装备保障路径选择中的应用[J]. 计算机与现代化, 2015, 0(11): 113-117.
[14]	朱卫宵，祝前旺，陈康. 基于改进蚁群算法的海上编队传感器资源分配模型[J]. 计算机与现代化, 2014, 0(12): 15-18+22.
[15]	刘晓曦;李卓越. 优化蚁群算法的云环境负载均衡[J]. 计算机与现代化, 2013, 1(9): 42-45.

禁忌搜索算法与蚁群算法的混合策略在二次分配问题上的应用

Application of Hybrid Strategy Based on Tabu Search and Ant Colony Algorithm to Quadratic Assignment Problem

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价