计算机应用 ›› 2016, Vol. 36 ›› Issue (9): 2416-2421.DOI: 10.11772/j.issn.1001-9081.2016.09.2416
收稿日期:
2016-02-17
修回日期:
2016-03-18
出版日期:
2016-09-10
发布日期:
2016-09-08
通讯作者:
李维鹏
作者简介:
李维鹏(1992-),男,湖北武汉人,硕士研究生,主要研究方向:最优估计、移动机器人基于视觉的同时定位与地图创建;曾静(1973-),女,四川金堂人,副教授,博士,主要研究方向:最优估计、运筹学;张国良(1970-),男,四川金堂人,教授,博士,主要研究方向:智能机器人、先进控制、组合导航。
LI Weipeng, ZENG Jing, ZHANG Guoliang
Received:
2016-02-17
Revised:
2016-03-18
Online:
2016-09-10
Published:
2016-09-08
摘要: 大规模非线性0-1规划问题求解时间较长,通过分析非线性0-1规划问题特点及算法寻优的Markov过程,提出一种基于改进Markov邻域的智能算法加速策略。首先,根据0-1规划问题解特点给出了非线性0-1规划问题的改写模型;随后,基于该模型给出了改进的Markov邻域,并推导和证明了改进邻域下任意两个状态之间的可达概率及其条件;最后,通过进一步分析非线性0-1规划模型并融合所提出的改进邻域,设计了采用Markov过程的智能算法的约束条件和目标函数递推更新策略对算法进行加速。采用不同算例进行多次测试,结果表明,在保持加速算法与原算法寻优效果相当的前提下,该策略对多种智能算法的寻优效率均有不同程度的提升。
中图分类号:
李维鹏, 曾静, 张国良. 基于改进Markov邻域的非线性0-1规划智能算法加速策略[J]. 计算机应用, 2016, 36(9): 2416-2421.
LI Weipeng, ZENG Jing, ZHANG Guoliang. Intelligent algorithm acceleration strategy for nonlinear 0-1 programming based on improved Markov neighborhood[J]. Journal of Computer Applications, 2016, 36(9): 2416-2421.
[1] MATSUI T, SAKAWA M, KATO K. Particle swarm optimization for nonlinear 0-1 programming problems [C]// Proceedings of the 2008 IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ: IEEE, 2008: 168-173. [2] 梁艳春,吴春国,石小虎,等.群智能优化算法理论与应用[M].北京:科学出版社,2009:100-135.(LIANG Y C, WU C G,SHI X H, et al. Theory and Application of Swarm Intelligence Optimization Algorithms [M]. Beijing: Science Press, 2009:100-135.) [3] 李春梅,马良.非线性0-1规划问题的人工鱼群算法[J].计算机应用研究,2011,28(7):2449-2451.(LI C M, MA L. Artificial fish-swarm algorithm for nonlinear 0-1 programming problem [J]. Application Research of Computers, 2011, 28(7): 2449-2451.) [4] 刘勇,马良.非线性0-1规划的元胞蚁群算法[J].系统管理学报,2010,19(3):351-355.(LIU Y, MA L. Solving nonlinear 0-1 programming by cellular ant algorithm [J]. Journal of Systems and Management, 2010, 19(3): 351-355.) [5] 韩燕燕,马良,赵小强.非线性0-1规划问题的蜂群算法[J].数学的实践与认识,2011,41(23):147-152. (HAN Y Y, MA L, ZHAO X Q. Bees algorithm for nonlinear 0-1 programming problem [J]. Journal of Mathematics in Practice and Theory, 2011, 41(23): 147-152.) [6] 张盛意,蔡之华,占志刚.基于改进模拟退火的遗传算法求解0-1背包问题[J].微电子学与计算机,2011,28(2):61-64. (ZHANG S Y, CAI Z H, ZHAN Z G. Solving 0-1 Knapsack problem based on genetic algorithm with improved simulated annealing [J]. Microelectronics and Computer, 2011, 28(2): 61-64.) [7] 许智宏,宋勃,董建波.用蚂蚁算法和模拟退火算法解大规模TSP问题的研究[J].计算机工程与科学,2008,30(10):43-44.(XU Z, SONG B, DONG J. Research on using the ant algorithm and the simulated annealing algorithm to solve the large-scale traveling salesman problem [J]. Computer Engineering and Science, 2008, 30(10): 43-44.) [8] 管屏,朱刚,马良,等.求解0-1规划的生长竞争蚁群算法[J].计算机工程与科学,2012,34(3):128-131.(GUAN P, ZHU G, MA L, et al. A growing competitive ant algorithm for the 0-1 programming problem[J]. Computer Engineering and Science, 2012, 34(3): 128-131.) [9] 周康,覃磊,同小军,等.0-1规划问题的闭环DNA算法 [J].系统工程与电子技术,2009,31(4):947-951.(ZHOU K, QIN J, TONG X J, et al. Closed circle DNA algorithm of 0-1 planning problem [J]. Systems Engineering and Electronics, 2009, 31(4): 947-951.) [10] 李芳芳,王靖.一种基于模拟退火算法的无线传感器网络最优簇类求解方案[J].传感技术学报,2011,24(6):900-904.(LI F F, WANG J. A best clustering scheme based on simulated annealing algorithm in wireless sensor networks [J]. Chinese Journal of Sensors and Actuators, 2011, 24(6): 900-904.) |
[1] | 雷鹰, 郑万波, 魏嵬, 夏云霓, 李晓波, 刘诚武, 谢洪. 基于概率性能感知演化博弈策略的“云+边”混合环境中任务卸载方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3302-3308. |
[2] | 乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103. |
[3] | 平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301. |
[4] | 邹复民, 罗思杰, 陈志辉, 廖律超. 基于轨迹数据的出租车交接班时空分布识别方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3376-3384. |
[5] | 肖智豪 胡志华 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 0, (): 0-0. |
[6] | 沙林秀,聂凡,高倩,孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 计算机应用, 0, (): 0-0. |
[7] | 董永峰 孙跃华 高立超 韩鹏 季海鹏. 基于改进一维卷积和双向长短期记忆神经网络的故障诊断方法[J]. 计算机应用, 0, (): 0-0. |
[8] | 李大海 刘庆腾 艾志刚 王振东. 基于动态D向分割和混沌扰动的阴阳对算法[J]. 计算机应用, 0, (): 0-0. |
[9] | 朱诚 潘旭华 张勇. 基于趋化校正的哈里斯鹰优化算法[J]. 计算机应用, 0, (): 0-0. |
[10] | 杨杰 张名扬 芮晓彬 王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 0, (): 0-0. |
[11] | 汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272. |
[12] | 李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417. |
[13] | 张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257. |
[14] | 张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018. |
[15] | 张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||