基于引力搜索和分布估计的混合离散优化算法

doi:10.11772/j.issn.1001-9081.2014.07.2074

计算机应用 ›› 2014, Vol. 34 ›› Issue (7): 2074-2079.DOI: 10.11772/j.issn.1001-9081.2014.07.2074

基于引力搜索和分布估计的混合离散优化算法

蒋悦¹,沈冬梅²,赵彦¹,高尚策³

1. 江苏信息职业技术学院物联网工程系, 江苏无锡 214153
2. 东华大学信息科学与技术学院，上海 201620
3. 东华大学信息科学与技术学院，上海 201620

收稿日期:2013-12-31 修回日期:2014-02-24 出版日期:2014-07-01 发布日期:2014-08-01
通讯作者: 高尚策
作者简介:蒋悦(1983-),男，江苏宜兴人,助教,硕士, 主要研究方向：计算智能;沈冬梅(1988-)，女，山东泰安人,硕士研究生，主要研究方向：进化算法；赵彦(1981-),女,河南开封人,讲师，硕士,主要研究方向：软件技术;高尚策(1983-),男, 江苏泰州人,副教授，博士,主要研究方向：计算智能。
基金资助:
国家自然科学基金资助项目;上海市晨光计划项目;教育部博士点新教师基金资助项目

Hybrid discrete optimization algorithm based on gravity search and estimation of distribution

JIANG Yue¹,SHEN Dongmei²,ZHAO Yan¹,GAO Shangce²

1. Department of Internet of Things, Jiangsu College of Information Technology, Wuxi Jiangsu 214153, China;
2. College of Information Sciences and Technology, Donghua University, Shanghai 201620, China

Received:2013-12-31 Revised:2014-02-24 Online:2014-07-01 Published:2014-08-01
Contact: GAO Shangce
Supported by:
;Ph.D. Program Foundation of Ministry of Education of China

摘要/Abstract

摘要：

针对传统离散引力搜索算法(GSA)容易陷入局部最小解的问题，提出了一种引力搜索和分布估计的混合离散算法GSEDA。通过有效地利用个体在引力搜索的历史统计信息，结合分布估计建立的概率分布模型，生成新的具有全局统计意义的优良解，继而更新搜索群体，使算法搜索更加平衡了空间的开发和探索能力，从而使得算法具有更强的跳出局部最优解的能力。仿真实验结果表明提出的新算法比传统算法具有更好的优化性能和鲁棒性。

Abstract:

According to the problem of the traditional Gravitational Search Algorithm (GSA) such as falling into the local minimum point easily, a hybrid algorithm based on Estimation of Distribution (ED) and gravitational search (GSEDA) was proposed. By characterizing the distribution of current solutions found by GSA, ED was used to generate promising solutions based on the constructed probability matrix, thus guiding the search to new solution areas. The proposed GSEDA was able to balance the exploration and exploitation of the search, therefore possessing a better local optima jumping capacity. The experimental results based on the traveling salesman problem indicate that GSEDA performs better than traditional algorithms in terms of solution quality and robustness.

中图分类号:

TP391.4

蒋悦沈冬梅赵彦高尚策. 基于引力搜索和分布估计的混合离散优化算法[J]. 计算机应用, 2014, 34(7): 2074-2079.

JIANG Yue SHEN Dongmei ZHAO Yan GAO Shangce. Hybrid discrete optimization algorithm based on gravity search and estimation of distribution[J]. Journal of Computer Applications, 2014, 34(7): 2074-2079.

参考文献

[1]RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA: A gravitational search algorithm［J］. Information Science, 2009, 179(13): 2232-2248.
[2]RASHIDI E, NEZAMABADI-POUR H, SARYAZDI S. BGSA: Binary gravitational search algorithm ［J］. Natural Computing, 2010, 3(9): 727-745.
[3]KAMEYAMA K. Particle swarm optimization-A survey［J］. IEICE Transactions on Information and Systems, 2009, 7(92):1354-1361.
[4]FORMATO A. Central force optimization: A new nature inspired computational framework for multidimensional search and optimization［J］. Studies in Computational Intelligence, 2008, 129:221-238.
[5]JIN L, LI J, WEI P, et al. Maximal gravitation optimization algorithm for function optimization［J］. Pattern Recognition and Artificial Intelligence, 2010, 23(5): 653-662.(金林鹏，李均利，魏平，等．用于函数优化的最大引力优化算法［J］. 模式识别与人工智能, 2010, 23(5): 653-662.)
[6]LI C, ZHOU J, FU B, et al. T-S fuzzy model identification with gravitational search based hyper-plane clustering algorithm［J］. IEEE Transactions on Fuzzy Systems, 2011, 19(6):1-12.
[7]LOPEZ-MOLINA C, BUSTINCE H, FERNANDEZ J, et al. A gravitational approach to edge detection based on triangular norms［J］. Pattern Recognition, 2010, 43(11):3730-3741.
[8]BEHRANG M, ASSAREH E, GHALAMBAZ M, et al. Forecasting future oil demand in Iran using GSA (Gravitational Search Algorithm) ［J］. Energy, 2011, 36(9):5649-5654.
[9]LI P, DUAN H. Gravitation search algorithm based on improved UAV route planning [J]. Chinese Science：Technology and Science，2012，42(10)：1130-1136.(李沛，段海滨. 基于改进万有引力搜索算法的无人机航路规划［J］. 中国科学：技术科学， 2012， 42(10): 1130-1136.)
[10]GANESAN T, ELAMVAZUTHI I, SHAARI K, et al. Swarm intelligence and gravitational search algorithm for multi-objective optimization of synthesis gas production［J］. Applied Energy, 2013, 103:368-374.
[11]RADU-CODRUT D, RADU-EMIL P, EMIL P, et al. Gravitational search algorithm-based design of fuzzy control system with a reduced parametric sensitivity［J］. Information Science, 2013, 247:154-173.
[12]XU Y, WANG S. Improved gravitational search algorithm[J]. Computer Engineering and Applications, 2011, 47(35): 188-192.(徐遥，王士同. 引力搜索算法的改进［J］. 计算机工程与应用，2011,47(35):188-192.)
[13]SARAFRAZI S, NEZAMABADI-POUR H, SARYAZDI S. Disruption: A new operator in gravitational search algorithm ［J］. Scientia Iranica D, 2011, 18(3): 539-548.
[14]SHAMSUDIN H, IRAWAN A, IBRAHIM Z, et al. A fast discrete gravitational search algorithm［C］// Proceedings of the 4th International Conference on Computational Intelligence, Modelling and Simulation. Washington, DC: IEEE Computer Society, 2012:24-28.
[15]SAEIDI-KHABISI F, RASHEDI E. Fuzzy gravitational search algorithm［C］// Proceedings of the 2nd International eConference on Computer and Knowledge Engineering. Piscataway: IEEE, 2012:156-160.
[16]DORAGHINEJAD M, NEZAMABADI-POUR H, SADEGHIAN A, et al. A hybrid algorithm based on gravitational search algorithm for unimodal optimization［C］// Proceedings of the 2nd International eConference on Computer and Knowledge Engineering. Piscataway: IEEE, 2012:129-132.
[17]YIN M, HU Y, YANG F, et al. A novel hybrid K-harmonic means and gravitational search algorithm approach for clustering［J］. Expert Systems with Applications, 2011, 38(8):9319-9324.
[18]ZHANG Y, WU L, ZHANG Y, et al. Immune gravitation inspired optimization algorithm［C］// Proceedings of the 7th International Conference on Advanced Intelligent Computing. Berlin: Springer-Verlag, 2012:178-185.
[19]SARAFRAZI S, NEZAMABADI-POUR H. Facing the classification of binary problems with a GSA-SVM hybrid system［J］. Mathematical and Computer Modelling, 2013,57(1):270-278.
[20]LI C, ZHOU J, XIAO J, et al. Parameters identification of chaotic system by chaotic gravitational search algorithm［J］. Chaos, Solutions and Fractals,2012, 45(4):539-547.
[21]HAUSCHILD M, PELIKAN M. An introduction and survey of estimation of distribution algorithms［J］. Swarm and Evolutionary Computation, 2011, 1(3):111-128.
[22]CREPINSEK M, LIU S, MERNIK M. Exploration and exploitation in evolutionary algorithms: a survey ［J］. ACM Computing Surveys, 2013, 45(3):1-35.
[23]GAO S, TANG Z. Solving combinatorial optimization problems by a discrete gravitational search algorithm［J］. ICIC Express Letters, 2011, 5(7):2119-2127.
[24]del VALLE Y, VENAYAGAMOORTHY G, MOHAGHEGHI S, et al. Particle swarm optimization: basic concepts, variants and applications in power systems ［J］. IEEE Transactions on Evolutionary Computation, 2008, 12(2): 171-195.
[25]ZHOU Y, WANG J, YIN J. An optimization algorithm based on estimation of distribution of discrete particle swarm [J]. Acta Electronica Sinica, 2008,36(6): 1242-1248.(周雅兰，王甲海，印鉴. 一种基于分布估计的离散粒子群优化算法［J］. 电子学报, 2008, 36(6): 1242-1248.)
[26]ZHANG Q, MUHLENBEIN H. On the convergence of a class of estimation of distribution algorithms［J］. IEEE Transactions on Evolutionary Computation, 2004, 8(2):127-136.
[27]ZHOU S, SUN Z. Estimation of distribution algorithms summary [J]. Acta Automatica Sinica, 2007,32(2):113-124.(周树德，孙增圻. 分布估计算法综述［J］. 自动化学报，2007, 32(2):113-124.)
[28]WANG X, CHENG Y, HAO M. Estimation of distribution algorithm based on bacterial foraging and its application in predictive control[J]. Acta Electronica Sinica, 2010, 38(2)：333-339.(王雪松，程玉虎，郝名林. 基于细菌觅食行为的分布估计算法在预测控制中的应用［J］. 电子学报, 2010, 38(2):333-339.)
[29]IVVAN VALDEZ S, HERNANDEZ A, BOTELLO S. A Boltzmann based estimation of distribution algorithm［J］. Information Science, 2013, 236(1):126-137.
[30]SIMONCINI D, ZHANG K. Efficient sampling in fragment-based protein structure prediction using an estimation of distribution algorithm［J］. PLoS One, 2013, 8(7): e689547.
[31]SHIM V, TAN K, CHIA J, et al. Multi-objective optimization with estimation of distribution algorithm in a noisy environment ［J］. Evolutionary Computation, 2013, 21(1): 149-177.
[32]WANG L, FANG C, MU C, et al. A Pareto-archived estimation-of-distribution algorithm for multiobjective resource-constrained project scheduling problem［J］. IEEE Transactions on Engineering Management, 2013, 60(3): 617-626.
[33]CHO D, ZHANG B. Evolutionary continuous optimization by distribution estimation with variational Bayesian independent component analyzers mixture model［C］// Parallel Problem Solving from Nature 2004, LNCS 3242. Berlin: Springer-Verlag, 2004:212-221.
[34]SUN J, ZHANG Q, TSANG E. DE/EDA: a new evolutionary algorithm for global optimization［J］. Information Science, 2005, 169(3/4):249-262.
[35]REN A, WANG Y, JIA F. A hybrid estimation of distribution algorithm and Nelder-Mead simplex method for solving a class of nonlinear programming problems［J］. Journal of Applied Mathematics, 2013: No. 378568.
[36]RONALD S. More distance functions for order-based encodings［C］// Proceedings of the 1998 IEEE International Conference on Evolutionary Computation. Piscataway: IEEE, 1998: 558-563.
[37]LARRANAGE P, LOZANO J. Estimation of distribution algorithms: a new tool for evolutionary computation［M］. Hingham: Kluwer Academic Publishers, 2002.

基于引力搜索和分布估计的混合离散优化算法

Hybrid discrete optimization algorithm based on gravity search and estimation of distribution

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	罗圣钦陈金怡李洪均. 基于注意力机制的多尺度残差UNet实现乳腺癌灶分割[J]. 计算机应用, 0, (): 0-0.
[2]	杨鼎康黄帅王顺利翟鹏李一丹张立华. 基于对抗生成网络和网络集成的面部表情识别方法EE-GAN[J]. 计算机应用, 0, (): 0-0.
[3]	秦庭威赵鹏程秦品乐曾建朝柴锐黄永琦. 基于残差注意力机制的点云配准算法[J]. 计算机应用, 0, (): 0-0.
[4]	鲁永帅唐英杰马鑫然. 基于深度特征融合的无纺布低对比度浆丝缺陷检测方法[J]. 计算机应用, 0, (): 0-0.
[5]	裴仪瑶, 郭会明, 张丹普, 陈文博. 基于定位不确定性的鲁棒3D目标检测方法[J]. 计算机应用, 2021, 41(10): 2979-2984.
[6]	许学斌, 张佳达, 刘伟, 路龙宾, 赵雨晴. 融合空间和通道特征的高精度乳腺癌分类方法[J]. 计算机应用, 2021, 41(10): 3025-3032.
[7]	汪虹余, 张彧, 杨恒, 穆楠. 基于蚁群优化算法的弱光图像显著性目标检测[J]. 计算机应用, 2021, 41(10): 2970-2978.
[8]	魏淳武, 赵涓涓, 唐笑先, 强彦. 基于多时期蒸馏网络的随访数据知识提取方法[J]. 计算机应用, 2021, 41(10): 2871-2878.
[9]	韩建栋, 李晓宇. 基于多尺度特征融合的行人重识别方法[J]. 计算机应用, 2021, 41(10): 2991-2996.
[10]	张凯悦, 张鸿. 基于注意力机制网络的航运监控图像识别模型[J]. 计算机应用, 2021, 41(10): 3010-3016.
[11]	李自强, 王正勇, 陈洪刚, 李林怡, 何小海. 基于外观和动作特征双预测模型的视频异常行为检测[J]. 计算机应用, 2021, 41(10): 2997-3003.
[12]	高世伟, 张长柱, 王祝萍. 基于可分离金字塔的轻量级实时语义分割算法[J]. 计算机应用, 2021, 41(10): 2937-2944.
[13]	卓禹心, 韩素雅, 张榆锋, 李支尧, 董毅峰. 基于超声谐波包络Nakagami参数图像的微波消融区域自动分割方法[J]. 计算机应用, 2021, 41(10): 3089-3096.
[14]	李敬虎邢前国郑向阳李琳王丽丽. 基于深度学习的无人机影像夜光藻赤潮提取方法[J]. 计算机应用, 0, (): 0-0.
[15]	任炜白鹤翔. 基于全局与局部的多标签图像分类方法[J]. 计算机应用, 0, (): 0-0.