离散自由搜索算法

doi:10.3724/SP.J.1087.2013.01563

计算机应用 ›› 2013, Vol. 33 ›› Issue (06): 1563-1570.DOI: 10.3724/SP.J.1087.2013.01563

离散自由搜索算法

郭鑫¹,孙丽杰李光明江开忠

1. 上海工程技术大学化学化工学院, 上海 201620
2. 上海工程技术大学基础教学学院, 上海 201620

收稿日期:2012-12-10 修回日期:2013-02-26 出版日期:2013-06-01 发布日期:2013-06-05
通讯作者: 江开忠
作者简介:郭鑫(1990-)，男，山东平邑人，主要研究方向：生物数据挖掘;孙丽杰(1990-)，女，山东诸城人，主要研究方向：医药数据挖掘;李光明(1990-)，男，河南宜阳人，主要研究方向：医药数据挖掘;江开忠(1965-)，男，四川乐至人，副教授，博士，主要研究方向：知识发现、软硬件协同设计、搜索算法。
基金资助:
上海市教委学科建设专项基金资助项目（11XK11）;上海工程技术大学内涵建设项目（nhky-2012-13）

Discrete free search algorithm

GUO Xin¹,SUN LijieLI GuangmingJIANG Kaizhong

1. College of Chemistry and Chemical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
2. College of Fundamental Teaching, Shanghai University of Engineering Science, Shanghai 201620, China

Received:2012-12-10 Revised:2013-02-26 Online:2013-06-05 Published:2013-06-01
Contact: JIANG Kaizhong
Supported by:
Shanghai Municipal Education Commission Discipline Construction Foundation

摘要/Abstract

摘要： 针对离散组合优化问题，给出一个自由搜索的算法。但是仅仅通过自由搜索算法求得的解，往往存在交叉现象，针对这个问题提出将离散自由搜索算法和交叉消除相结合的算法，这样不仅大大地提高了自由搜索算法运算过程的收敛速度，而且较大程度地提升了结果的质量。利用旅行商问题(TSP)标准库中的测试数据对所提算法进行了验证，结果表明该算法比遗传算法性能提高了约1.6%。

关键词: 旅行商问题, 智能算法, 自由搜索, 交叉消除

Abstract: A free search algorithm was proposed for the discrete optimization problem. However，solutions simply got from free search algorithm often have crossover phenomenon. Then, an algorithm free search algorithm combined with cross elimination was put forward, which not only greatly improved the convergence rate of the search process but also enhanced the quality of the results. The experimental results using Traveling Saleman Problem (TSP) standard data show that the performance of the proposed algorithm increases by about 1.6% than that of the genetic algorithm.

Key words: Traveling Saleman Problem (TSP), intelligent algorithm, free search, cross elimination

中图分类号:

TP301

郭鑫孙丽杰李光明江开忠. 离散自由搜索算法[J]. 计算机应用, 2013, 33(06): 1563-1570.

GUO Xin SUN Lijie LI Guangming JIANG Kaizhong. Discrete free search algorithm[J]. Journal of Computer Applications, 2013, 33(06): 1563-1570.

参考文献

[1] TSAI C F,TSAI C W,YANG T. A modified multiple-searching method to genetic algorithms for solving traveling salesman problem［C］// IEEE International Conference on Systems, Man and Cybernetics. Piscataway:IEEE,2002:6-12.

[2] KIRKPATRICK S, GELATF C D,VECCHI M P. Optimization by simulated annealing［J］. Science, 1983,220(4598): 671-680．

[3] TSAI C F, TSAI C W, TSENG C C. A new hybrid heuristic approach for solving large traveling salesman problem［J］. Information Sciences, 2004,166(1): 67-81.

[4] HE Y,QIU Y H,KIU G Y. A Parallel tabu search approach based on genetic crossover operation［C］// Proceedings of the 19th IEEE International Conference Cordon Advanced Information Networking and Applications. Washington, DC：IEEE Computer Society, 2005:1550-1553.

[5] ROSENKRANTZ D J, STEARNS R E, LEWIS P M. An analysis of several heuristics for the traveling salesman problem［J］.SIAM Journal of Computer, 1977，6(1): 563-581.

[6] CROES G A. A method for solving traveling salesman problems［J］. Operations Research, 1958, 6(6)：791-812.

[7] BENTLEY J L. Fast algorithm for geometric traveling salesman problems［J］. ORSA Journal on Computing, 1992, 4(4): 387-411.

[8] LIN S，KERNIGHAN B W. An effective heuristic algorithm for the traveling salesman problem［J］. Operations Research，1973，21(2): 498-516.

[9] PENEV K, LITTLEFAIR G. Free search- a comparative analysis ［J］. Information Sciences, 2005, 172(1/2): 173-l93.

[10] 周晖, 李丹美, 邵世煌,等. 一种新的群集智能算法——自由搜索［J］.东华大学学报:自然科学版,2007, 33(5): 579-583.

[11] 周晖,李丹美, 邵世煌,等. 一种新的群集智能优化及其改进研究［J］. 系统工程与电子技术, 2008, 30(2):337-340.

[12] 周晖, 徐晨, 邵世煌,等. 自适应搜索优化算法［J］.计算机科学,2008,35(10):188-191.

[13] 伍国华, 马满好. 路径交叉检测与消除方法和邻节点置换方法改进TSP的解［J］. 计算机应用研究,2011,28(2):485-487.

[1]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[2]	李克文, 马祥博, 候文艳. 带有自适应合并策略和导向算子的增强型烟花算法[J]. 计算机应用, 2021, 41(1): 81-86.
[3]	李章洪, 梁晓磊, 田梦丹, 周文峰. 求解排列组合问题的解空间动态缩减策略[J]. 计算机应用, 2020, 40(7): 2016-2020.
[4]	杨云亭, 王鹏. 求解旅行商问题的多尺度量子自由粒子优化算法[J]. 计算机应用, 2020, 40(5): 1278-1283.
[5]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[6]	梅伟, 赵云涛, 毛雪松, 李维刚. 基于离散灰狼算法的喷涂机器人路径规划方法[J]. 计算机应用, 2020, 40(11): 3379-3384.
[7]	李贺, 江登英, 黄樟灿, 王占占. 彩色图像颜色量化问题的求解方法[J]. 计算机应用, 2019, 39(9): 2646-2651.
[8]	王东先, 孟学雷, 乔俊, 汤霖, 焦志臻. 基于改进蚁群算法的铁路乘务交路计划的编制[J]. 计算机应用, 2019, 39(9): 2749-2756.
[9]	王东先, 孟学雷, 何国强, 孙慧萍, 王喜栋. 基于改进蚁群算法的铁路乘务排班计划编制[J]. 计算机应用, 2019, 39(12): 3678-3684.
[10]	喻德旷, 杨谊, 钱俊. 云计算资源的动态随机扰动的粒子群优化策略[J]. 计算机应用, 2018, 38(12): 3490-3495.
[11]	翟光明, 李国和, 吴卫江, 洪云峰, 周晓明, 汪静. 基于Spark的人工蜂群改进算法[J]. 计算机应用, 2017, 37(7): 1906-1910.
[12]	乔屾, 吕志民, 张楠. 基于汉明距离的改进粒子群算法求解旅行商问题[J]. 计算机应用, 2017, 37(10): 2767-2772.
[13]	李维鹏, 曾静, 张国良. 基于改进Markov邻域的非线性0-1规划智能算法加速策略[J]. 计算机应用, 2016, 36(9): 2416-2421.
[14]	程毕芸, 鲁海燕, 徐向平, 沈莞蔷. 求解旅行商问题的改进局部搜索混沌离散粒子群优化算法[J]. 计算机应用, 2016, 36(1): 138-142.
[15]	李迅陈明. 密集型多轮廓裁片的刀具空行程路径寻优[J]. 计算机应用, 2014, 34(1): 281-285.

离散自由搜索算法

Discrete free search algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics