摘要
蚁群算法是在20世纪90年代早期提出的一种群智能随机优化算法,其优越的分布式搜索模式在组合优化问题的求解中取得了成功,引起了许多学者的极大关注。蚁群算法本质上是离散的,在求解连续域优化问题时,往往存在收敛速度慢、易陷入局部最优等缺点。如何对蚁群算法在连续空间的寻优方式进行改进,以提高其优化性能,这正是本文研究的主要内容。
在分析总结了用于连续域优化的蚁群算法的基础上,对蚂蚁构建解的过程和在保持种群多样性上进行了改进,提出了一种新的含维变异算子的连续域改进蚁群算法(DMCACO)。该算法采用动态随机抽取策略来确定目标个体,引导蚁群进行全局的快速搜索;当前最优蚂蚁在邻域内以模式探测的方式进行小步长的局部精细搜索。同时,引入了不同于传统变异方式的维变异算子,且变异保持的策略使变异可以更为充分和均匀。对测试函数的仿真结果表明,该算法具有较好的优化性能。
接着,结合改进的约束处理机制,将本文提出的连续域蚁群算法扩展到用于求解约束优化问题。通过引入目标满意度函数和惩罚满意度函数的概念,构建了基于惩罚函数法的新的适应度函数,其中的系数随种群的可行解比例动态自适应变化,不会过大或过小。另外,采取了当前最优不可行解向最优可行解转移的搜索策略,有效利用了约束边界附近不可解的信息。然后通过13个标准测试函数验证了算法的有效性。
最后,将改进的连续域蚁群算法用于求解多元线性回归模型和非线性Logistic回归模型的参数估计问题。通过算例仿真结果可知,本文所提算法为求解回归模型的参数估计问题提供了一条有效的途径。
The ant colony algorithm was put forward in early 1990s, which is a kind of intelligent stochastic optimization algorithm. Its predominant dis-tributed search pattern achieves success in solving combinational prob-lems, and brings great attention of many scholars. Ant colony algorithm is discrete in nature and always has defects such as slow convergence rate and easily plunging into the local optimum when solving the continuous optimization problem. So, It's the major work of this thesis that how to improve the searching way of ant colony algorithm in continuous space and advance its optimal performance.
Based on the analysis of the ant colony algorithms have being used in continuous domains, a novel continuous domains Ant colony algorithm with dimension mutation operator(DMACO) is presented. Mainly, it im-proves the process of ant solution construction and the way of keeping the diversity of ant population. In this algorithm, target individuals which lead the ant colony to do global rapid search are determined by the way of dynamic and stochastic extraction, and the current optimal ant searches subtly in small step with pattern detection nearly. At the same time, the dimension mutation operator is introduced in this algorithm, which is dif-ferent from traditional mutation means. And the mutation is more suffi-cient and homogeneous owing to the strategy of mutation-keeping. Simulating to the test functions, the result demonstrates that the optimal performance of the algorithm is better.
Then, the continuous domains ACO presented is expanded to solve constrained optimization problem, combined with advanced constraint processing mechanism. Based on penalty function method, the author structures a new fitness function by introducing the concept of target sat-isfaction function and penalty satisfaction function. The coefficient in this method is changed dynamically and self-adaptively following the propor-tion of feasible solution, no too large or too small. In addition, the search-ing strategy and the present optimal infeasible solution transferring to the present optimal feasible solution, is adopted to make use of the message about infeasible solution near the constraint boundary effectively. Then the effectiveness of the algorithm is tested on 13 benchmark functions. Finally, the advanced continuous domains ACO is used to solve the pa-rameter estimation problem of multi-linear regression model and nonlin-ear Logistic regression model. From the simulation result of examples, we can know that the algorithm presented is an efficient way to solve the parameter estimation problem of regression model.
引文
[1]高尚,杨靖宇.群智能算法及其应用[M].北京:国水利水电出版社,2006
[2]Bonabeau E,Dorigo M,Theraulaz G. Inspiration for optimization from social insect behavior.2000,406(6):39-42
[3]Colorni A, Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies [C]. Proceedings of the 1st European Conference on Artificial Life,1991:134~142
[4]Marco Dorigo,Thomas Stutzle. Ant Colony Optimization.2004,The MIT Press.Ca-mbridge, Masschusetts London, England
[5]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005
[6]Dorigo M, Maniezzo V, Colorni A. Ant System:Optimization by a Colony of Cooperating Agents[J]. IEEE transactions on systems, man, and cybernetics-part B:cybernetics,1996,26(1):29~41
[7]Bonabeau E, Dorigo M, Theraulaz G. Inspiration for optimization'from social insect behavior.Nature,2000,406(6):39~42
[8]Thomas S,Holger H H. MAX-MIN ant system. Future Generation Computer System,2000,16(8):889~914
[9]Vlachogiannis JG, Hatziargyriou ND,Lee KY. Ant colony system-based algorithm for constrained load flow problem[J].Power System, IEEE Transaction on.2005,20(3):1241~11249
[10]Andrew Lim, Jing Lin, et al. Ant colony optimization with hill climbing for the bandwidth minimization problem.Applied Soft Computing,2006,6(3):180~188
[11]Bilchev,G.and Parmee,I.C.The ant colony metaphor for searching continuous design spaces.Lecture Notes in Computer Science 1993,(1995):25~39
[12]Jun L.Y.and Jun,W.T. An adaptive ant colony system algorithm for continuous space optimization problems. Journal of Zhejiang University Science,2003,4(1): 40~46
[13]Socha K, Dorigo M. Ant colony optimization for continuous domains[J]. Europe-an Journal of Operational Research,2008,185:1155~1173
[14]Tfaili W, Siarry P. A new charged ant colony algorithm for continuous dynamic optimization[J]. Applied Mathematics and Computation,2008,197:604~613
[15]Hossein M N, Nima T. New robust efficient ant colony algorithms:Using new interpretation of local updating process[J]. Expert Systems with Applications, 2009,36:252~260
[16]张纪会,徐心和.一种新的进化算法—蚁群算法[J].系统工程理论与实践,1999,19(3):84-87
[17]Marco Dorigo,Tommas Stiitzle. Ant Colony Optimization[M]. MIT Press,2004
[18]王颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报,2002,14(1):31-33
[19]岳风,刘希玉.自适应调整挥发系数的逆向蚁群算法[J].计算机工程与应用,2008,44(3):105-107
[20]邵晓魏,邵长胜,赵长安.利用信息量留存的蚁群遗传算法[J].控制与决策,2004,19(10):1187-1189
[21]高尚,钟娟,莫述军.连续优化问题的蚁群算法研究[J].微机发展,2003,13(1):21-22
[22]熊伟清,魏平.二进制蚁群进化算法[J].自动化学报,2007,33(3):259-264
[23]段海滨,马冠军,王道波等.一种求解连续空间优化问题的改进蚁群算法[J].系统仿真学报,2007,19(5):974-977
[24]马卫,朱庆保.求解函数优化问题的快速连续蚁群算法[J].电子学报,2008,36(11):2121-2124
[25]赵云涛,王京,荆丰伟.用于连续域优化的蚁群算法及其收敛性研究[J].系统仿真学报,2008,20(15):4021-4024
[26]Wu Z L, Zhao N, Ren G H. Population declining ant colony optimization and its applications[J]. Expert Systems with Applications,2009,36:6276~6281
[27]周新建,杨卫东,李掌.求解连续函数优化问题的改进蚁群算法及仿真[J].系统仿真学报,2009,21(6):1685-1688
[28]Gutjahr W J. A graph-based ant system and its convergence[J]. Future Generation Computer Systems,2000,16(8):873~888
[29]Gutjahr W J. ACO algorithms with guaranteed convergence to the optimal solution[J]. Information Processing Letters,2002,82(3):145~153
[30]Gutjahr W J. First steps to the runtime complexity analysis of ant colony optimization[J]. Computers and Operations Research,2008,35:2711~2727
[31]Stutzle T, Dorigo M. A short convergence proof for a class of ant colony optimization algorithms [J]. IEEE Transactions on Evolutionary Computation, 2002,6(4):358~365
[32]Badr A, Fahmy A. A proof of convergence for ant algorithms [J]. Intenational Jou-rnal of Intelligent Computing and Information,2003,3(1):22~32
[33]段海滨,王道波.蚁群算法的全局收敛性研究及改进[J].系统工程与电子技术,2004,26(10):1506-1509
[34]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析[J].自动化学报,2004,30(4):659-664
[35]S Goss,S.Aron,J.L Deneubourg et al.Self-organized shortcuts in the Argentime ant[J].Naturwissenschaften,1989(76):579~581
[36]段海滨.蚁群算法及其在高性能电动仿真转台参数优化中的研究:[博士学位论文].南京:南京航空航天大学,2005
[37]俞云新,王更生.基于粒子群的蚁群算法参数最优组合研究[J].华东交通大学学报,2010,27(1):47-51
[38]Maniezzo V, Colorni A. The Ant System Applied to the quadratic assignment problem[J]. IEEE Transactions on Data and Knowledge Engineering.1999, 11(5):769~778
[39]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001
[40]Colorni A, Dorigo M, Maniezzo V, et al. Ant System for job-shop scheduling[J]. Belgian Journal of Operations Research, Statistics and Computer Science.1994, 34:39~53
[41]Bullnheimer B, Hartl R. F, Strauss C.An improved ant system algorithm for the vehicle routing problem[J]. Annals of Operations Research,1999,89:319-328
[42]Costa D, Hertz A. Ants can color graphs[J]. Journal of the Operational Research Society.1997,48:295~305
[43]Caro Di, Dorigo M. Exending AntNet for best-effort quality-of-service routing [C]. Proceedings of the 1st International Workshop on Ant Colony Optimization, 1998,304~317
[44]Findova S.3D protein folding problem using ant algorithm[C]. In Proceedings of BioPS international conference, Sofia, Bulgaria,2006,19~26
[45]Nezamabadi-pour H, Saryazdi S, Rashedi E. Edge detection using ant algorithms[J]. Soft Computing,2006,10:623~628
[46]Duan H B, Wang D B, Zhu J Q, et al. Parameter identification of LuGre friction model for flight simulation ant colony optimization[J]. Transactions of Nanjing University of Aeronautics & Astronautics,2004,21(3):179~183
[47]Jensen R, Shen Q. Fuzzy-rough data reduction with ant colony optimization[J]. Fuzzy Sets and Systems,2005,149(1):5-20
[48]Tfaili W, Siarry P. A new charged ant colony algorithm for continuous dynamic optimization[J]. Applied Mathematics and Computation,2008,197:604~613
[49]汪定伟,王俊伟,王洪峰等.智能优化算法[M].北京:高等教育出版社,2007
[50]杨勇,宋晓峰,王建飞等.蚁群算法求解连续空间优化问题[J].控制与决策,2003,18(5):573-576
[51]李秋云,朱庆保,马卫.用于连续域寻优的分组蚁群算法[J].计算机工程与应用,2010,46(30):46-49
[52]Dreo J, Siarry P. Continuous interacting ant colony algorithm based on dense heterarchy[J]. Future Generation Computer Systems,2004,20(5):841~856
[53]程志刚,陈德钊,吴晓华.基于信息素正态分布的连续蚁群优化系统[J].系统工程与电子技术,2006,28(3):458-462
[54]陈宝林.最优化理论与算法[M].北京:清华大学出版社,2005
[55]梁昔明,李朝辉,龙文等.含维变异算子的连续域蚁群算法[J].计算机应用,2010,30(12):3204-3206
[56]付国江,王少梅,刘舒燕.含维变异算子的粒子群算法[J].武汉大学学报(工学版),2005,38(4):79-83
[57]江巧永,高岳林.融合差分进化和倒序变异扩展蚁群算法[J].计算机应用,2010,30(9):2283-2285
[58]李向丽,杨慧中,魏丽霞.基于退火的蚁群算法在连续空间优化中的应用[J].计算机工程与应用,2007,43(25):74-76
[59]刘喜恩.用于连续空问寻优的一种蚁群算法[J].计算机应用,2009,29(10):2744-2747
[60]Monmarch eN, Venturini G, Slimane M. On how Pachycondyla apicalis ants suggest a new search algorithm[J]. Future Generation Computer Systems,2000, 16(8):937~946
[61]王凌,何锲,金以慧.智能约束处理技术综述[J].化工自动化及仪表,2008,35(1):1-7
[62]Gary G. Yen. Constraint Handling in Genetic Algorithm for Optimization[J]. ADVANCES IN COMPUTATIONAL INTELLIGENCE:Theory and Applications,2006,5:145~170
[63]Coello C A C. Theoretical and numerical constraint-handing techniques used with evolutionary algorithms:a survey of the state of the art[J]. Computer methods in Applied Mechanics and Engineering,2002,191(11-12):1245~1287
[64]J. Joines and C. Houck, "On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GA's," Proc. Cong. Evol. Comput, Orlando, FL, June 1994:579~584.
[65]Runarsson T P, Yao X. Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactiong on Evolutionary Computation,2000,4(3): 284~294
[66]Deb K. An efficient constraint handling method for genetic algorithms[J]. Computer Methods in Applied Mechanics and Engineering,2000,186:311~338
[67]Coello C A C,Montes E M. Constraint-handing in Genetic Algorithms through the Use of Dominance-based Toumament Selection[J].Advanced Engineering Informatics,2002,16(3):193~203
[68]CAI Z X,WANG Y. A Multiobjective Optimization based on Evolutionary Algorithm for Constrained Optimization[J]. IEEE Trans on Evolutionary Computation(S1089-778X),2006,10(3):658~575
[69]Mathur M, Karale S B, Priye S,et al. Ant Colony Approach to Continuous Function Optimization[J]. Industrial and Engineering Chemistry Research,2000, 39:3814~3822
[70]贺益君,陈德钊.连续约束蚁群优化算法的构建及其在丁烯烷化过程中的应用[J].化工学报,2005,56(9):1708-1713
[71]刘利强,于飞,谭佳琳.一种求解约束优化问题的连续域蚁群算法[J].系统仿真学报,2008,20(13):3404-3407
[72]原思聪,刘道华,江祥奎等.基于蚁群算法的多维有约束函数优化研究[J].计算机应用研究,2008,25(6):1682-1684
[73]胡一波,王宇平.解约束优化问题的一种新的罚函数模型[J].计算机科学,2009,36(7):240-243
[74]甘敏,彭辉.一种新的自适应惩罚函数算法求解约束优化问题[J].信息与控制,2009,38(1):24-28
[75]林丹,李敏强,寇纪凇.基于遗传算法求解约束优化问题的一种算法[J].软件学报,2001,12(4):628-632
[76]张利彪,周春光,刘小华,马铭.求解约束.优化问题的一种新的进化算法.吉林大学学报,2004,42(4):534-540
[77]R. Farmani and J. Wright, "Self-adaptive fitness formulation for constrained optimization," IEEE Trans. Evol. Comput,2003(7):445~455
[78]陈金山,韦刚.一种线性回归模型参数估计的混合基因算法[J].电子与信息学报,2001,23(8):819-822
[79]方开泰,张金廷.非线性回归参数估计的一个新算法[J].应用力学学报,1993,16(3):366-377
[80]郑国庆,张国权.基于模拟退火算法的半参数线性回归模型的参数估计[J].华 南农业大学学报,2006,4,115-117
[81]董伟,李建东,吕卓等.IMMO系统联合参数估计[J].西安电子科技大学学报(自然科学版),2008,35(2):189-195
[82]吴新杰,李媛,张丹等.PSO算法在多元线性回归分析问题中的应用[J].辽宁大学学报,2007,34(1):18-20
[83]陈渝光,李山,廖仕利等.基于遗传算法的发动机多元回归控制模型[J].农业机械学报,2006,37(6):9-12
[84]梅长林,范金城.数据分析方法[M].北京:高等教育出版社,2006
[85]王新洲.非线性模型参数估计理论与应用[M].武汉:武汉大学出版社,2002
[86]郭朝有,贺国.遗传算法在非线性回归模型辩识中的应用[J].海军工程大学报,2003,4:70-73.
[87]陈伟,张从海.混合模拟退火—遗传算法在参数估计中的应用[J].空间地理信息,2007,5(2):99-10
[88]刘锦萍,郁金祥等.基于粒子群算法的Logistic回归模型参数估计[J].计算机工程与应用,2009,45(33):42-44
[89]王济川,郭志刚Logistic回归模型—方法与应用[M].北京:高等教育出版社,2001,09