摘要
科学技术日益表现出交叉和渗透的特征,特别是计算机科学技术改变了人类生产与生活方式。然而,现有计算机的计算能力并非无所不能,它在某些具有不确定性、动态性、非线形或多态(Multi-modal)问题上常常不能满足人们的要求,因此人们对于高效计算技术的探索从未停止。
近50年来元启发式优化算法得到了广泛研究,如遗传算法、模拟退火等,这类算法均通过模拟自然现象(Nature-Inspired)为解决复杂问题提供了新的思路和手段。本论文中主要介绍了两大类元启发式优化算法,第一类是群体智能(Swarm Intelligence)算法,包括蚁群优化(Ant Colony Optimization)和粒子群优化(Particle Swarm Optimization)两种算法,这两种都是基于种群策略的仿生算法;第二类是微正则退火(Microcanonocal Annealing)算法,它是来自于对物理学的借鉴。本文中主要通过仿真手段,研究了这两类元启发式优化算法的几种改进策略及应用。
全文主要由九章构成,主要内容如下:
第一章介绍了论文的研究背景,对群体智能优化和微正则优化的研究现状做了简要综述,并概括了本文的研究内容和创新点。
第二章阐述了元启发式算法的相关概念,并将典型的元启发式算法的优化模式划分为两类,第一类是基于单一解形式,第二类是基于种群策略,后者又根据个体间的交互程度细分为强交互类型和弱交互类型。
第三章是对蚁群优化的综述,重点介绍了蚁群优化的算法背景、基本算法和著名的改进形式,并对处理连续性问题、收敛性理论分析及其应用做了简要总结。
第四章是对粒子群优化的综述,以算法背景、基本算法及改进参数、著名的改进形式和处理离散问题的研究为主,最后也简述了粒子群优化己知的实际应用。
第五章介绍了微正则退火的基本原理,通过对经典TSP实例的仿真,发现微正则退火的能量下降速度明显快于模拟退火。尽管两种算法的搜索性能基本持平,但微正则退火搜索到最优解或局部最优解的时间性能要优于模拟退火,这使得它在某些大计算量优化问题上具有显著优势。仿真中还发现,该算法提出者Creutz所声称的“妖的能量上限初始值只要大于最大可能遇到的能量差”并不准确,该初始值实际上存在一个最优区间,过大的初始值会降低搜索到最优解的机会。同时仿真中也揭示出,妖的能量上限的下降系数取一个较大的值时算法表现出了强鲁棒性。尤其观察到即便该系数等于1,即能量上限保持恒定时,只要初始值选择得当,算法依旧能产生优良的搜索性能。本章提出了三种改进策略,第一种是状态回溯机制,保存最近的若干优良状态,若系统状态长期无法改善,则强迫回溯到某个优良状态上,试验发现只要相关参数选择得当,该策略能提高脱离局部极值点的能力。第二种是能量奖励策略,在拒绝状态时对妖的能量进行一定程度的奖励。观察了有上界约束和无上界约束两种方式下的搜索性能,并提出了无上界约束时降低加快收敛速度的方法。第三种是能量收缩策略,当妖的能量超过门槛水平后,执行小幅缩减操作以达到加快收敛的目的。本章最后将微正则退火应用到固定频率分配问题上,仿真发现该算法在频点资源紧张时明显优于模拟退火算法。
第六章介绍了增强型参考位置的粒子群优化算法,这种改进策略在速度迭代公式中同时考虑邻居中最佳粒子以及种群中最佳粒子的吸引作用,相当于基本算法Gbest与Lbest的融合形式。对于速度迭代公式中的三项偏差,设计了确定性的参数配置和具有随机扰动的参数配置方式,仿真发现,当对种群最佳粒子的权重做随机扰动时,改进算法在搜索成功率和目标平均评价次数上都要优于Lbest算法,而且对于其他两个参数的相对大小并不敏感。
第七章将基于共享适应值的小生境技术应用到粒子群优化中,小生境技术的特征是仿照生态系统,限制相似个体过分聚集。本章构建了固定邻居结构的F-ShPSO算法和动态选择邻居的D-ShPSO算法两种形式,对经典函数的仿真表明,F-ShPSO的搜索成功率不低于Lbest算法,但迭代次数波动较小,且对邻居规模不敏感,而D-ShPSO性能比较差,表明在这种改进策略中动态邻居机制并不可行。
第八章介绍了粒子群优化的一种两阶段实施策略,该策略本质上是先对种群进行分群操作,然后对由“群首”构成的临时群执行再迭代,而具体的粒子状态更新机制可灵活选择。对比试验中揭示,该策略能提高搜索到多态函数最优解的成功率,且降低了基本算法对两项偏差权重的敏感度。试验结果也验证了对于最优子群数量的估计,该数量宜选择适中数值以综合考虑计算效率与效果。
第九章对全文的研究内容做了简要的回顾,并指出了研究内容的不足和今后可能的研究方向。
Computer science and technology has penetrated all walks of life and changed human societies from industry to daily life. However the current computer, especially the personal computer, is not powerful enough. It requires the computing task to be well-defined, fairly predictable, and computable in reasonable time. It generates unsatisfied performance on uncertain, dynamic, nonlinear, or multi-modal problems. So the human beings never cease to explore alternative computing techniques with high performance.
Meta-heuristic optimization algorithms are one of the alternatives which have caught comprehensive attentions in these years. Meta-heuristic optimization algorithm refers to a general-purpose heuristic algorithm that can be used on different types of problems, including genetic algorithm, simulated annealing and some others. They are also called nature-inspired algorithms and have provided novel approaches for attacking complicated problems as mentioned above. In this dissertation two kinds of meta-heuristic optimization algorithms have been discussed. One is swarm intelligence technique including ant colony optimization (ACO) and particle swarm optimization (PSO). These two are both bio-inspired population-based algorithms. The other is microcanonical annealing (MA) algorithm which comes from physics. In the dissertation, several improved strategies about these algorithms are introduced by means of simulations. The whole paper consists of nine chapters listed as follows:
Chapter 1 introduces the background of this work and presents brief reviews on swarm intelligence and microcanonical annealing. The main research contents and corresponding contributions are summarized in the end of this chapter.
Chapter 2 provides relevant concepts of meta-heuristic optimization algorithm and divides it into two categories, the first searches the target space by a single solution, the second seeks optimal solution in a population-based way. The latter is also divided into two styles, one utilizes interaction among the population and the other works on interaction between individual and environment.
Chapter 3 presents reviews on ant colony optimization. The main contents are made up of the algorithm background, basic paradigms and notable improvements, attempts of tackling continuous function, convergence researches and its applications.
Chapter 4 gives surveys on particle swarm optimization. This section consists of biology background, canonical algorithms, well-known improvements and attempts of attacking discrete problem. Industry applications of particle swarm optimization are also listed in a short summary.
Chapter 5 explains the theory background of microcanonical annealing and its implementation process on optimization. The simulations on benchmark show that this new annealing approach is faster than simulated annealing with comparative success rate. Microcanonical annealing requires fewer evaluations in success trials, so it will be a competitive algorithm in the circumstances attaching much importance to computing efficiency. The simulations also reveal that there is an optimal range for the initial upper bound (Emax) of demon's energy(E_D) and too large value will decrease the possibility of finding optimal solution. This observation is not consistent with Creutz who just claimed that the start value of Emax be considerably larger than the largest energy gap normally encountered. The decreasing coefficient should be a large value in order to provide high success rate, further more the simulations show that even if the coefficient is set to 1 the algorithm can also provide good performance as long as Emax be specified to an appropriate start value. Three improvements are proposed in this chapter, the first one called a history state conserving mechanism is designed to save a number of good states. Once the current state cannot be improved for certain iterations, the algorithm will sample a random state in the conserved queues and transfer to it. Simulations indicate this mechanism can accelerate the convergence process of microcanonical annealing if relevant parameters be set a proper value. The second one named energy enhancement strategy is to increase E_D to some extent when the optimization stagnates. Two kinds of energy enhancements are investigated including enhancement with upper bound and without upper bound. An approach to decrease the evaluation times under the improvement is also proposed. The last one is called energy shrinking which is combinded with a decreasing operation on E_D when E_D exceeds the threshold. At the end of this chapter, an application on frequency assignment problem by means of microcanonical annealing has demonstrated its promising future in network optimization.
Chapter 6 discusses an extended particle swarm optimization which combines Gbest and Lbest to consider both global best particle and local best neighbor in the updating formula of velocity. Two kinds of weight assignment rules in the formula are proposed, the first one fixes the weight for each part but the performance is not outstanding, the second* one specifies a random weight for one of the parts. The simulations show that if the weight for global best part is a random value, the new algorithm outperforms Lbest in both success rate and evaluation times and is not sensitive to the other two weights on the benchmark.
Chapter 7 applies a niche technique called sharing fitness to particle swarm optimization. Niche technique comes from bionomics and prevents similar individuals from gathering around a single individual. Two versions of this algorithm are proposed, one fixes the neighborhood structure (F-ShPSO) and the other constructs the neighborhood dynamically (D-ShPSO). The simulations on benchmark show that F-ShPSO provides a comparative success rate than Lbest with a lower fluctuating on the evaluation times. Furthermore it is not much sensitive to neighborhood size. D-ShPSO exhibits bad performance in the comparison and this result indicates the dynamic strategy in this context is not feasible.
Chapter 8 introduces a two-stage implementation strategy for particle swarm optimization. The essence of this method is to divide the whole population into several subpopulations and an updating process is performed on the temporary colony composed of global best individual in each subpopulations. The updating formula of individual is not specified in the current approach. Simulations on multi-modal function reveal that it can enhance the success rate and decrease the sensitivity of weights in the traditional updating formula. The experiments demonstrate that the amount of subpopulations should be in an appropriate range to balance success rate and computation cost.
Chapter 9 gives a summary of the whole dissertation and points out the limitations and potential directions in future research.
引文
1 http://www.micro.caltech.edu/Courses/FE150/dungeon
2 系综是统计物理学中的一个假想的概念,表示由大量系统所组成的集合。系综做了两点假设:宏观量是相应微观量的时间平均,而时间平均等价于系统平均;平衡孤立系统的一切可达微观态出现的概率相等。当系统达到宏观平衡态时,宏观性质不随时间变化,相应的系综是稳定系综。根据不同的宏观条件,将稳定系综分为三种类型:由孤立系统组成的微正则系综、由恒温封闭系统组成的正则系综和由开放系统组成的巨正则系综。优化中的模拟退火算法是建立在正则系综理论之上的。
3 以投稿日期为准,此说法来自段海滨博士的专著《蚁群算法原理及其应用》
5 http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
14 普克动物世界网站,空间的气味标记,http://www.pupk.com/zt/data/487.htm, 2005
15 新华网,蚂蚁识图利用几何学,http://news.xinhuanet.com/st/2004-12/29/content_2390018.htm, 2005
18 具体TSP数据可参考本论文参考文献王凌编著的《智能优化算法及其应用》的附录部分
21 随机数种了分别为10,18,52,68,120,这些数值足随机选择的。
[1]. Colorni A, Dorigo M, Maniezzo V. Ant system:an autocatalytic optimizing process. 1991, Politecnico di Milano.
[2]. Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. in Proceedings of the First European Conference on Artificial Life. Paris, France: Elsevie Publishing. 1991, 134-142.
[3]. Colorni A, Dorigo M, Maniezzo V. An investigation of some properties of an ant algorithm, in Proceedings of the Parallel Problem Solving from Nature Conference(PPSN'92). Brussels, Belgium: Elsevier Publishing. 1992, 509-520.
[4]. Kennedy J, Eberhart R. Particle Swarm Optimization. in Proceedings of IEEE International Conference on Neural Networks: IEEE Service Center, Piscataway, NJ. 1995, 1942-1948.
[5]. Bonabeau E, Dorigo M, Theraulaz G. Swarm Intelligence: From Natural to Articial Systems. 1999, NY: Oxford Univ. Press.
[6].李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法.系统工程理论与实践,2002,22(11):32-38.
[7]. Flikkema P G, Leid J G. Bacterial communities: a microbiological model for swarm intelligence, in Proceedings 2005 IEEE Swarm Intelligence Symposium. 2005, 416-419.
[8]. Creutz M. Microcanonical Monte Carlo Simulation. Physical Review Letters, 1983, 50(19): 1411-1414.
[9].张纪会,高齐圣.自适应蚁群算法.控制理论与应用,2000,17(1):1-3.
[10].吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法.计算机研究与发展,1999.36(10):1240-1245.
[11].覃刚力,杨家本.自适应调整信息素的蚁群算法.信息与控制,2002.31(3):198-201.
[12].郝晋,石立宝.求解复杂TSP问题的随机扰动蚁群算法.系统工程理论与实践,2002.22(9):88-91.
[13].陈峻,沈洁等.基于分布均匀度的自适应蚁群算法.软件学报,2003.14(8):1379-1387.
[14].吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法.计算机学报,2001.24(12):1328-1333.
[15].马良,蒋馥度.限制最小树的蚂蚁算法.系统工程学报,1999.14(3):211-214.
[16].林锦,朱文兴.凸整数规划问题的混合蚁群算法.福州大学学报(自然科学版),1999.27(6):5-9.
[17].高玮,郑颖人.蚁群算法及其在R群施工优化中的应用.岩石力学与工程学报,2002.21(4):471-474.
[18].王志刚,杨丽徙等.基于蚁群算法的配电网网架优化规划方法.电力系统及其 自动化学报,2002.14(6):73-76.
[19].孙新宇,万筱宁等.蚁群算法在混流装配线调度问题中的应用.信息与控制,2002.31(6):486-490.
[20].张素兵,石国英,刘泽民,周正.基于蚂蚁算法的QOS路由调度算法.电路与系统学报,2000.5(1):1-5.
[21].丁亚平,吴庆生等.一种新的化学计量学方法一一蚁群算法.化学通报,2002.65(4):257-260.
[22].侯云鹤,熊信良等.基于广义蚁群算法的电力系统经济负荷分配.中国电机工程学报,2003.23(3):59-64.
[23].庄昌文,范明饪,李春辉,虞厥邦.采用面向Agent技术的并行布线系统.计算机研究与发展,1999.36(12):1442-1447.
[24].周登勇,戴汝为.一个基于多主体的仿真工具系统COMPLEXITY.模式识别与人工智能,2000.13(3):241-247
[25].王颖,谢剑英.一种自适应蚁群算法及其仿真研究.系统仿真学报,2002.14(1):32-33.
[26].徐海,刘石,马勇,蓝鸿翔.基于改进粒子群游优化的模糊逻辑系统自学习算法.计算机工程与应用,2000,(07):62-63.
[27].夏永明,付子义,袁世鹰,程志平.粒子群优化算法在直线感应电机优化设计中的应用.中小型电机,2002.29(6):14-16.
[28].董颖,唐加福,许宝栋,汪定伟.一种求解非线性规划问题的混合粒子群优化算法.东北大学学报(自然科学版),2003.24(12):1141-1144.
[29].黄岚,王康平,周春光,庞巍,董龙江,彭利.粒子群优化算法求解旅行商问题.吉林大学学报(理学版),2003.41(04):477-480.
[30].王岁花,冯乃勤,李爱国.基于粒子群优化的BP网络学习算法.计算机应用与软件,2003(10):74-76.
[31].高尚,杨静宇,吴小俊.求解指派问题的交叉粒子群优化算法.计算机工程与应用,2004(08):54-55.
[32].吕振肃,侯志荣.自适应变异的粒子群优化算法.电子学报,2004.32(03):416-420.
[33].李智,郑晓.粒子群算法在农业工程优化设计中的应用.农业工程学报,2004.20(03):15-18.
[34].张利彪,周春光,马铭,刘小华.基于粒子群算法求解多目标优化问题.计算机研究与发展,2004.41(7):1286-1291.
[35].刘靖明,韩丽川,侯立文.基于粒子群的K均值聚类算法.系统工程理论与实践,2006(6):54-58.
[36].秦绪伟,范玉顺,尹朝万.整车物流网络规划问题的混合粒子群算法研究.系统工程理论与实践,2006(7):47-53.
[37].吴斌.群体智能的研究及其在知识发现中的应用.2002,中国科学院研究生院.
[38].李智,郑晓.基于蚂蚁算法的时序电路测试生成研究.2002,电子科技大学.
[39].程军盛.仿生智能计算.2002,安徽大学.
[40].李有梅.仿生优化算法研究及其应用.2003,西安交通大学.
[41].郑岩.数据聚类及其应用研究.2003,吉林大学.
[42].卜天明.蚁群优化算法若干问题研究.2003,上海大学.
[43].胡小兵.蚁群优化原理、理论及其应用研究.2004,重庆大学.
[44].李炳宇.群体智能模型算法的研究与应用.2004,同济大学.
[45].陈红洲.群体智能若干算法研究.2004,哈尔滨工程大学.
[46].彭宇.群智能优化算法及理论研究.2004,哈尔滨工业大学.
[47].邵巍.加强信息利用率的改进蚁群算法—解决路由选择优化问题.2004,北京科技大学.
[48].高海兵.粒子群优化算法及其若干工程应用研究.2004,华中科技大学.
[49].孙骏.基于蚁群优化算法的TSP问题研究.2005,武汉理工大学.
[50].康琦.微粒群优化算法的研究与应用.2005,同济大学.
[51].曾建潮,介婧,崔志华.微粒群算法.2002,北京:科学出版社.
[52].段海滨.蚁群算法原理及其应用.2005,北京:科学出版社.
[53].高尚,杨静宇.群智能算法及其应用.2006,北京:中国水利水电出版社.
[54]. Barnard S T. STEREO MATCHING BY HIERARCHICAL, MICROCANONICAL ANNEALING. in Proc. of the Tenth International Joint Conference on. Artificial Intelligence. 1987 832-835.
[55]. Bhandarkar Suchendra M, Zhang Hum. Image Segmentation Using Evolutionary Computation. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 1999. 3(1): 1-21.
[56]. Laurent Herault, Radu Horaud. Figure-Ground Discrimination: A Combinatorial Optimization Approach. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1993. 15(9): 899-914.
[57].王凌.智能优化算法及其应用.2001,北京:清华大学出版社.
[58].邢文训 谢金星.现代优化计算方法(第2版).2005,北京:清华大学出版社.
[59]. Reeves C R. Modern heuristic techniques for combinatorial problems. 1993, Oxford: Blackwell Scientific Publications.
[60].徐宗本.计算智能(第一册)模拟进化计算2004,北京:高等教育出版社.
[61]. Denebourg J L, Pasteels J M, Verhaeghe ] C. Probabilistic Behaviour in Ants: a Strategy of Errors? Journal of Theoretical Biology, 1983(105): 259-271.
[62]. Denebourg J L, Goss S. Collective patterns and decision-making. Ethology, Ecology & Evolution, 1989(1): 295-311.
[63]. Goss S, Beckers R, Denebourg J L, Aron S, Pasteels J M. How Trail Laying and Trail Following Can Solve Foraging Problems for Ant Colonies. in Behavioural Mechanisms of Food Selection. Berlin: Springer-Verlag. 1990 661-678.
[64]. Dorigo M, Maniezzo V, Colorni A. The Ant System: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics-Part B, 1996. 26(1): 29-41.
[65]. Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997. 1(1): 53-66.
[66]. Deneubourg J L, Aron S, Goss S, Pasteels J M. The self-organizing exploratory pattern of the argentine ant. Journal of Insect Behavior, 1990(3): 159-168.
[67]. Holland O E, Melhuish C E. Stigmergy, se]f-organisation and sorting in co]lective robotics. Artificial Life, 1999. 5(2): 173-202.
[68]. Holland O E, Beckers R. The varieties of stigmergy: indirect interaction as a control strategy for collective robotics. Robotica, 1996.
[69]. Dorigo M, Di Caro G. Ant colony optimization a new meta-heuristic, in Proceedings of the 1999 Congress on Evolutionary Computation. 1999 1470-1477.
[70]. Dorigo M, Di Caro G, Gambardella LM. Ant algorithms for discrete optimization. Artif. Life, 1999. 5(2): 137-172.
[71]. Subrmanian D, Druschel P, Chen J. Ants and reinforcement learning: A case study in routing in dynamic networks, in Proceedings of IJCAI-97, International Joint Conference on Artificial Intelligence: Morgan Kaufmann. 1997 832-838.
[72].卢辉斌,贾兴伟,范庆辉.基本蚂蚁算法中参数的讨论与改进.计算机工程,2005.31(20):175-179.
[73]. Colorni A, Dorigo M, Maffio]i F, Maniezzo V, Righini G, Trubian M. Heuristics from Nature for Hard Combinatorial Problems. International Transactions in Operational Research, 1996. 3(1): 1-21.
[74]. Gambardella L M, Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies, in Proceedings of the IEEE Conference on Evolutionary Computation, ICEC96: IEEE Press. ]996 622-627.
[75]. Dorigo M, Gambardella L M. The Ant Colony Optimization Metaheuristic: Algorithms, Applications and Advances. in Handbook of Metaheuristics. Norwell, MA: Kluwer Academic Publishers. 2002 251-285.
[76]. Maniezzo V. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. 1998, C. L. In Scienze dell' Informazione, Universita di Bologna: sede di Cesena, Italy.
[77]. Gambardella L M, Dorigo M. Ant-Q:a reinforcement learning approach to the traveling salesman problem, in Proceedings of the 12th International Conference on Machine Learning. Tahoe City: Morgan Kaufmann. 1995 252-260.
[78]. Dorigo M, Gambardella L M. A study of some properties of Ant-Q. in Proceedings of PPSN-IV, Fourth International Conference on Parallel Problem Solving From Nature. Berlin: Springer-Verlag. 1996 656-665.
[79]. Stutzle T, Hoos H. The MAX-MIN ant system and local search for the traveling salesman problem, in Proceedings of IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference 1997: IEEE Press. 1997 309-314.
[80]. Bullnheimer B, Hartl R F, Strauss S. A new rank-based version of the ant system: a computational study. 1997, Institute of Management Science, University of Vienna.
[81]. Watkins C. Learning with delayed rewards, in Psychology Department. 1989, University of Cambridge, England.
[82].赵文彬,孙志毅.蚁群算法在一般函数优化求解中的应用.太原科技大学学报,2005.26(3):210-212.
[83].孙学勤,刘丽,付萍等.一种连续空间优化问题的蚁群算法及应用.计算机工程与应用,2005(34):217-230.
[84]. Gutjahr W J. A generalized convergence result for the graph-based ant system metaheuristic. 1999, Dept. Statistics and Decision Support Systems, Univ. Vienna, Austria.
[85]. Gutjahr W J. ACO algorithms with guaranteed convergence to the optimal solution. Info. Processing Lett., 2002. 182(3): 145-153.
[86]. Gutjahr W J. A graph-based Ant System and its convergence. Future Generation Computer Systems, 2000. 16(8): 873-888.
[87]. Meuleau N, Dorigo M. Ant colony optimization and stochastic gradient descent. ArtifLife, 2002. 8(2): 103-121.
[88]. Staezle T, Dorigo M. A short convergence proof for a class of ant colony optimization algorithms. IEEE Transactions on Evolutionary Computation, 2002. 6(4): 358-365.
[89]. Yoo J H, La R J, Makowski A M. Convergence results for ant routing. 2003, Institute for Systems Research, University of Maryland, College Park(MD).
[90].丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法融合的马尔可夫收敛性分析.自动化学报,2004.30(4):659-664.
[91]. Hou Y H, Wu Y W, Lu L J, et al. Generalized ant colony optimization for economic dispatch of power systems, in Proceedings of the 2002 International Conference on Power System Technology. 2002 225-229.
[92]. Bonabeau E, Dorigo M, Theraulaz G. Inspiration for optimization from social insect behaviour. Nature, 2000. 406(6): 39-42.
[93]. Maniezzo V, Colorni A, Dorigo M. The ant system applied to the quadratic assignment problem. 1994, Universite Libre de Bruxelles: Belgium.
[94]. Maniezzo V, Colorni A. The ant system applied to the quadratic assignment problem. IEEE Trans. Knowledge Data Engin., 1999(11): 769-778.
[95]. Stutzle T, Hoos H. MAX-MIN Ant system and local search for combinatorial optimization problems, in Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Kluwer, Boston. 1998 137-154.
[96]. Stutzle T, Dorigo M. ACO algorithms for the quadratic assignment problem, in New Ideas in Optimisation., D.M. Come D, Glover F, Editor. 1999, McGraw-Hill: New York. 33-50.
[97]. Colorni A, Dorigo M, Maniezzo V, Trubian M. Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL), 1994. 34: 39-53.
[98]. Bullnheimer B, Hartl R F, Strauss C. An improved ant system algorithm for the vehicle routing problem. 1997, Institute of Management Science, University of Vienna.
[99]. Bullnheimer B, Hartl R F, Strauss C. Applying the ant system to the vehicle routing problem, in Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. 1998, Kluwer Academics. 109-120.
[100]. Gambardella L M, Taillard E, Agazzi G. Macs-vrptw: A multiple ant colony system for vehicle routing problems with time windows, in New Ideas in Optimisation. 1999, McGraw-Hill. 63-76.
[101]. Michel R, Middendorf M. An island model based ant system with lookahead for the shortest supersequence problem, in Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature: Springer-Verlag. 1998 692-701.
[102]. Costa D, Hertz A. Ants can colour graphs. Journal of the Operational Research Society, 1997(48): 295-305.
[103]. Monmarche N. On data clustering with artificial ants. in Data Mining with Evolutionary from the AAAI Workshop: CA: AAAI Press. 1999 23-26.
[104]. Parepinelli R S, Lopes H S, Freitas A. An Ant Colony Algorithm for Classification Rule Discovery, in Data Mining: Heuristic Approach. 2002, Idea Group Publishing: Lonton. 192-208.
[105]. Bo Liu, Hussein A, Bob M. Density_based Heuristic for Rule Discovery with Ant_Miner. in The 6th Australia-Japan Joint Workshop on Intelligent and Evolutionary System. 2002 180-184.
[106]. Holden N, Freitas A. Web page classification with an ant colony algorithm. in 8th International Conference on Parallel Problem Solving from Nature, LNCS 3242. 2004 1092-1102.
[107]. Oakes M P. Ant Colony optimisation for stylometry: the Federalist papers. in Proceedings Of the 5th international Conference on Recent Advances In Soft computing: Nottingham Trent University. 2004 86-91.
[108]. YONG FENG, ZHONG-FU WU, KAI-GUI WU, ZHONG-YANG XIONG, YING ZHOU. AN UNSUPERVISED ANOMALY INTRUSION DETECTION ALGORITHM BASED ON SWARM INTELLIGENCE. in Proceedings of the Fourth International Conference on Machine Learning and Cybernetics. Guangzhou. 2005 3965-3969.
[109]. Merkle D, Middendorf M. An Ant Algorithm with a New Pheromone Evaluation Rule for Total Tardiness Problems, in Real-World Applications of Evolutionary Computing, EvoWorkshops 2000. 2000, Springer-Verlag: London. 287-296.
[110]. SOLNON C. Solving Permutation Constraint Satisfaction Problems with Artificial Ants. in 14th European Conference on Artificial Intelligence (ECAI'2000): IOS Press. 2000 118-122.
[111]. Solnon C. Ants Can Solve Constraint Satisfaction Problems. IEEE Transactions on Evolutionary Computation, 2002. 4(6): 347-357.
[112]. den Besten M, Stutzle T, Dorigo M. Ant colony optimization for the total weighted tardiness problem, in Proceedings of Sixth International Conference on Parallel Problem Solving from Nature, LNCS 1917. Berlin, Germany: Springer Verlag. 2000 611-620.
[113]. Ramalhinho H, Lourenco D, Serra. Adaptive approach heuristics for the generalized assignment problem. 1998, Universitat Pompeu Fabra, Dept. of Economics and Management: Barcelona, Spain.
[114]. Leguizamon G, Michalewicz Z. A new version of Ant System for subset problems, in Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press. 1999 1459-1464.
[115]. Alexandrov D A, Kochetov Y A. The behavior of the ant colony algorithm for the set covering problem, in Operations Research Proceedings 1999: Springer Verlag. 2000 255-260.
[116]. Hadji R, Rahoual M, Talbi E, Bachelet V. Ant colonies for the set covering problem, in Abstract proceedings of ANTS2000: Universit'e hibre de Bruxelles. 2000 63-66.
[117]. TKindt V, Monmarche N, haugt D, et al. Combining Ants Colony Optimization and Simulated Annealing to solve a 2-machine flowshop bicriteria scheduling problem. European Journal of Operational Research, 2002. 142(2): 250-257.
[118]. Renbin Xiao, Zhenwu Tao. A Swarm Intelligence Approach to Path Synthesis of Mechanism. in Ninth International Conference on Computer Aided Design and Computer Graphics. 2005 1-6.
[119]. Schoonderwoerd R, Holland O, Bruten J, Rothkrantz L. Ant-based load balancing in telecommunications networks. Adaptive Behavior, 1996. 5(2): 169-207.
[120]. Schoonderwoerd R, Holland O, Bruten J, Rothkrantz L. Ant-like agents for load balancing in telecommunications networks, in Proceedings of the First International Conference on Autonomous Agents: ACM Press. 1997 209-216.
[121]. Bonabeau E, Henaux F, Guerin S, Snyers D, Kuntz P, Theraulaz G. Routing in telecommunication networks with "Smart" ant-like agents. Lectures Notes in AI, 1998. 1437.
[122]. White T, Pagurek B, Oppacher F. Connection management using adaptive mobile agents, in Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'98): CSREA Press. 1998 802-809.
[123]. Di Caro G, Oorigo M. AntNet: A mobile agents approach to adaptive routing. 1997, Universite Libre de Bruxelles: IRIDIA.
[124]. Di Caro G, Dorigo M. Mobile agents for adaptive routing, in Proceedings of the 31st International Conference on System Sciences (HICSS-31): IEEE Computer Society Press. 1998 74-83.
[125]. Di Caro G, Dorigo M. AntNet: Distributed stigmergetic control for communications networks. Journal of Artificial Intelligence Research (JAIR), 1998(9): 317-365.
[126]. Di Caro G, Dorigo M. Ant colonies for adaptive routing in packet-switched communications networks, in Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature: Springer-Verlag. 1998 673-682.
[127]. Di Caro G, Dorigo M. An adaptive multi-agent routing algorithm inspired by ants behavior, in Proceedings of PART98-5th Annual Australasian Conference on Parallel and Real-Time Systems: Springer-Verlag. 1998 261-272.
[128]. Di Caro G, Dorigo M. Two ant colony algorithms for best-effort routing in datagram networks in Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS'98): IASTED/ACTA Press. 1998 541-546.
[129]. Di Caro G, Dorigo M. Extending AntNet for best effort quality-of-service routing, in Proc. ANTS'98-First International Workshop on Ant Colony Optimization. Brussels, Belgium. 1998 15-16.
[130]. Heusse M, Guerin S, Snyers D, Kuntz P. Adaptive agent-driven routing and load balancing in communication networks. 1998, Department Intelligence Artificielle et Sciences Cognitives, ENST Bretagne.
[131]. van der Put R. Routing in the faxfactory using mobile agents. 1998, KPN Research.
[132]. Gianni Di Caro, Frederick Ducatelle, Luca Maria Gambardella. SWARM INTELLIGENCE FOR ROUTING IN MOBILE AD HOC NETWORKS. in Proceedings 2005 IEEE Swarm Intelligence Symposium. 2005 76-83.
[133]. P Janacik O Kao, U Rerrer. A routing approach using swarm-intelligence for resource sharing in wireless ad hoc networks, in Joint IST Workshop on Mobile Future, SympoTIC'04. 2004 170-174.
[134]. Eberhart R C, Shi Y. Guest Editorial: Special Issue on Particle Swarm Optimization. IEEE Trans. on Evolutionary Computation, 2004. 8(3): 201-203.
[135]. Eberhart R C, Kennedy J. A new optimizer using particle swarm theory in Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Nagoya, Japan. 1995 39-43.
[136]. Kennedy J, Eberhart R. Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance, in Proceedings of the 1999 Congress on Evolutionary Computation. Washington, DC, USA. 1999 1931-1938.
[137]. Kennedy J, Mendes R. Population structure and particle swarm performance. in Proceedings of the 2002 Congress on Evolutionary Computation. Honolulu, HI, USA,. 2002 1671-1676.
[138]. Mendes R, Kennedy J, Neves J. Watch thy neighbor or how the swarm can learn from its environment, in Proceedings of the 2003 IEEE of Swarm Intelligence Symposium. Indianapolis: IEEE Computer Society. 2003 88-94.
[139]. Kennedy J, Eberhart R. The particle swarm: social adaptation of knowledge, in Proceedings of IEEE International Conference on Evolutionary Computation. Indianapolis. 1997 303-308.
[140]. XU Junjie, YUE Xin, XIN Zhanhong. A real application of extended particle swarm optimizer. in Fifth International Conference on Information, Communication and Signal Processing. Thailand, Bangkok: IEEE Press. 2005 46-49.
[141]. Jun-jie Xu, Zhan-hong Xin. An Extended Particle Swarm Optimizer. in 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) Workshop on NIDISC. Denver, Colorado. 2005 193a.
[142]. Carlisle A, Dozier G. An off-the-shelf PSO. in Proceedings of the Workshop on Particle Swarm Optimization. Purdue School of Engineering and Technology, Indianapolis. 2001 1-6.
[143]. Shi Y, Eberhart R C. A modified particle swarm optimizer, in Proceedings of the IEEE International Conference on Evolutionary Computation: IEEE Press. 1998 69-73.
[144]. Shi Y, Eberhart R C. Parameter selection in particle swarm optimization. in Proceedings of the Seventh Annual Conference on Evolutionary Programming. New York:: Springer-Verlag. 1998 591-600.
[145]. Shi Y, Eberhart R C. Empirical study of particle swarm optimization. in Proceedings of the 1999 Congress on Evolutionary Computation. Washington, DC, USA. 1999 1945-1950.
[146]. Shi Y, Eberhart R C. Fuzzy Adaptive Particle Swarm Optimization. in Proceedings Congress on Evolutionary Computation. Seoul, Korea. 2001 101-106.
[147]. Clerc M. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization, in Proceedings of the 1999 Congress of Evolutionary Computation: IEEE Press. 1999 1951-1957.
[148]. Maurice Clerc, James Kennedy. The Particle Swarm-Explosion, Stability, and Convergence in a Multidimensional Complex Space. IEEE Transactions on evolutionary computation, 2002. 6(1): 58-73.
[149]. Eberhart R, Shi Y. Comparing inertia weights and constriction factors in particle swarm optimization, in Proceedings of the 2000 Congress on Evolutionary Computation[La Jolla, CA, USA. 2000 84-88.
[150]. Angeline P J. Using selection to improve particle swarm optimization. in Proceedings of the 1998 International Conference on Evolutionary Computation. Anchorage, Alaska. 1998 84-89.
[151]. Angeline P J. Evolutionary optimization versus particle swarm optimization: philosophy and performance difference, in Proc. 7th Annual Conf. on Evolutionary Programming: Berlin, Springer. 1998 601-610.
[152]. Lovbjerg M, Rasmussen Tk, Krink T. Hybrid Particle Swarm Optimiser with Breeding and Subpopulation. in Proceedings of the Genetic and Evolutionary Computation Conference 2001. 2001 469-476.
[153]. Kennedy J, Mendes R. Neighborhood topologies in fully-informed and best-of-neighborhood particle swarms, in Proceedings of the 2003 IEEE International Workshop on Soft Computing in Industrial Applications. 2003 45-50.
[154]. Kennedy J, Eberhart R. Bare bones particle swarms, in Proceedings of the 2003 IEEE Swarm Intelligence Symposium. Indianapolis, Indiana. 2003 80-87.
[155]. Riget J, Vesterstroem J S. A Diversity Guided Particle Swarm Optimizer-the ARPSO. 2002, University of Aarhus, EVALife.
[156]. van den Bergh, Engelbrecht A. A new locally convergent particle swarm optimizer, in Proc. IEEE Conf. Systems, Man, Cybern. Tunisia. 2002 96-101.
[157]. Peer E S, van den Bergh, Engelbrecht A P. Using neighborhoods with the guaranteed convergence PSO. in Proceedings of the IEEE Swarm Intelligence Symposium 2003 (SIS 2003). Indianapolis, Indiana, USA. 2003 235-242.
[158]. Asanga Ratnaweera, Saman K, Halgamuge, Harry C. Watson. Self-Organizing Hierarchical Particle Swarm Optimizer With Time-Varying Acceleration Coefficients. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2004. 8(3): 240-255.
[159]. Voss M S. Principal Component Particle Swarm Optimization: A Step Towards Topological Swarm Intelligence. in The 2005 IEEE Congress on Evolutionary Computation. 2005 298-305.
[160]. Weiwu Li, Hui Wang, Zhijun Zou. Function optimization Method Based on bacterial Co]ony Chemotaxis. Journal of Circuits and Systems, 2005. 10(1): 58-63.
[161]. S Miiller, J Marchette, S Airraght, et al. Optimization Based on Bacterial Chemotaxis. IEEE Transactions on Evolutionary Computation, 2002. 6(1): 17-19.
[162]. S Miiller, S Airaghi, J Marchelo, et al. Optimization algorithms based on a model of bacterial Chemotaxis. in Proceedings of SAB 2000. 2000 375-384.
[163].曹黎侠,张建科.细菌趋药性算法研究及应用研究进展.计算机工程与应用,2006.1:44-46.
[164]. Kennedy J, Eberhart R. A Discrete Binary Version of the Particle Swarm Algorithm. in IEEE International Conference on Computational Cybernetics and Simulation: IEEE Service Center. 1997 4104-4108.
[165]. Kennedy J, Spears W. Matching Algorithms to Problems: An Experimental Test of the Particle Swarm and Some Genetic Algorithms on the Multimodal Prob]em Generator. in IEEE International Conference on Evolutionary Computation. Anchorage, Alaska, USA. 1998 78-83.
[166].徐俊杰,忻展红.粒子群优化在0/l背包问题中的应用.in中国运筹学会第七届学术交流会论文集:Global-Link出版社(香港).2004 131-135.
[167].Thierens D. Adaptive mutation rate control schemes in genetic algorithms. in Proceedings of the 2002 Congress on Evolutionary Computation. Honolulu, HI USA. 2002 980-985.
[168]. Fukuyama Y, Takayama S, Nakanishi Y, Yoshida H. A particle swarm optimization for reactive power and voltage control in electric power systems, in Proceedings of the Genetic-and Evolutionary Computation Conference 1999 (GECCO 1999). Orlando, Florida, USA. 1999 1523-1528.
[169]. Fukuyama Y, Yoshida H A. Particle swarm optimization for reactive power and voltage control in electric power systems, in Proceedings of Congress on Evolution Computation. Seoul, Korea. 2001 89-93.
[170]. Clerc M. Discrete particle swarm optimization illustrated by the traveling salesman problem, 2000, http://www.mauriceclerc.net
[171]. Wang K P, Huang L, Zhou C G, Pang W. Particle swarm optimization for traveling salesman problem, in Proceedings of International Conference on Machine Learning and Cybernetics 2003. Xi'an. 2003 1583-1585.
[172]. Hu X, Eberhart R C, Shi Y. Swarm Intelligence for Permutation Optimization: A Case Study of n-Queens Prob]em. in IEEE 2003 Swarm Intelligence Symposium. Indianapolis (IN), USA. 2003 243-246.
[173]. 杨淑媛.量子进化算法的研究及其应用.2003,西安电子科技大学:西安.
[174]. Hu X, Eberhart R C, Shi Y. Multiobjective optimization using dynamic neighborhood particle swarm optimization, in Proceedings of the IEEE Congress on Evolutionary Computation. Honolulu, Hawaii USA. 2002 1677-1681.
[175]. Xiaohui Hu, Eberhart R, Yuhui Shi. Particle swarm with extended memory for multiobjective optimization, in Proceedings of the 2003 IEEE Swarm Intelligence Symposium. Indianapolis, IN, USA. 2003 193-197.
[176]. Parsopoulos K E, Vrahatis M N. Particle swarm optimization method in multiobjective problems, in Proc. 2002 ACM Symp. Applied Computing (SAC'2002) Madrid. Spain. 2002 603-607.
[177]. He Z, Wei C, Yang L, et al. Extraction Rules from Fuzzy Neural Network by Particle Swarm Optimization. in IEEE International Conference on Evolutionary Computation. Anchorage, Alaska, USA, . 1998 74-77.
[178]. Eberhart R, Hu X. Human tremor analysis using particle swarm optimization, in Proceedings of the IEEE Congress on Evolutionary Computation. Washington DC. 1999 1927-1930.
[179]. Eberhart R, Yuhui Shi. Particle swarm optimization:developments, applications and resources, in Proceedings of the 2001 Congress on Evolutionary Computation. Seoul, South Korea. 2001 81-86.
[180]. ZHANG Yang-yang, JI Chun-lin, YVAN Ping, et al. Particle Swarm Optimization for Base Station Placement in Mobile Communication. in Proceedings of the 2004 IEEE International Conference on Networking, Sensing & Control. Taipei, Taiwan. 2004 428-432.
[181]. JI Chun-lin, ZHANG Yang-yang, GAO Shi-xing, et al. Particle Swarm Optimization for Mobile Ad Hoc Networks Clustering. in Proceedings of the 2004 IEEE International Conference on Networking, Sensing & Control. Taipei, Taiwan. 2004 372-375.
[182]. Hardin C T, Usher J S. FACILITY LAYOUT USING SWARM INTELLIGENCE. in Proceedings 2005 IEEE Swarm Intelligence Symposium. 2005 424-427.
[183]. A Di Franco, K S Narendra. A SIMPLE NEAREST-NEIGHBOR FLOCKING RULE. in Proceedings 2005 IEEE Swarm Intelligence Symposium. 2005 409-411.
[184].刘金洋,郭茂祖,邓超.基于雁群启示的粒子群优化算法.计算机科学,2006.33(11):166-168.
[185].徐俊杰,忻展红.基于微正则退火的频率分配方法.北京邮电大学学报(自然版),2007.30(2):67-70.
[186].忻展红.系统建模与计算机模拟(教材).1997,北京:北京邮电大学.
[187]. Hale W K. Frequency assignment: theory and applications. Proceedings of IEEE, 1980. 68(12): 1497-1514.
[188]. Karen I, Aardal Start P M. van Hoesel, Arie M C A, Koster, et al, Models and Solution Techniques for Frequency Assignment Problems. 2001.
[189]. Costa D, Hertz A. On the use of some known methods for t-colorings of graphs. Annals of Operations Research, 1993. 41: 343-358.
[190]. Beckmann D, Killat U. Frequency Planning with respect to interference minimization in cellular radio networks. 1999: Vienna, Austria.
[191]. Duque-Antdn M, Kunz D, Ruber B. Channel assignment for cellular radio using simulated annealing. IEEE Transactions on Vehicular Technology, 1993. 42(1): 14-21.
[192]. Valenzuela C, Hurley S, Smith D H. A permutation based genetic algorithm for minimum span frequency assignment. LNCS 1998. 1498: 907-916.
[193]. Caste]ino D J, Hurley S, Stephens N M. A tabu search algorithm for frequency assignment. Anna]s of Operations Research, 1996. 63: 301-319.
[194].许良凤.蜂窝移动通信中基于遗传退火的固定频率分配.安徽农业大学学报,2004.31(4):508-510.
[195]. De Jong K A. An analysis of the behavior of a class of genetic adaptive systems. 1975, University of Michigan, Ann Arbor.
[196]. Mahfoud S W. Crowding and preselection revisited, in Proc 2nd Conf Parallel Problem Solving from Nature. Amsterdam: Elsevier. 1992 27-36.
[197]. Mengshoel O J, Goldberg D E. Probabilistic crowding: deterministic crowding with probabilistic replacement, in Proceedings of the Genetic and Evolutionary Computation Conference 1999 (GECCO-99). San Fransisco, CA: Morgan Kaufmann. 1999 173-179.
[198]. Holland J H. Adaptation in natural and artificial systems. 1975, Ann Arbor: University of Michigan Press.
[199]. Goldberg D E, Richardson J. Genetic algorithms with sharing for multimodal Function Optimization. in Proceedings of the Second International Conferenceon Genetic Algorithms. Hillsdale: Lawrence Erlbaum Associates. 1987 41-49.
[200]. Miller B L, Shaw M J. Genetic algorithms with dynamic niche sharing for multimodal function optimization, in IEEE International Conference on Evolutionary Computation. Piscataway NJ: IEEE Press. 1996 786-791.
[201]. Beasley D, Bull D R, Martin R R. A sequential niche technique for multimodal function optimization. Evolutionary Computation, 1993. 1(2): 101-125.
[202]. Potts J C, Giddens T D, Yadav S B. The development and evaluation of an improved genetic algorithms based on migration and artificial selection. IEEE Transaction on System, Man and Cybernetics, 1994. 24(1): 73-86.
[203]. Harik G. Finding multi-modal solutions using restricted tournament selection, in Proceedings of the Sixth International Conference on Genetic Algorithms (ICGA6). San Francisco, CA: Morgan Kaufmann. 1995 24-31.
[204]. Brits R, Engelbrecht A P, van den Bergh F. A niching particle swarm optimizer, in Proceedings of the Conference on Simulated Evolution and Learning. Singapore. 2002 692-696.
[205]. Parsopoulos K E, Vrahatis M N. Modification of the particle swarm optimizer for locating all the global minima, in Artificial Neural Networks and Genetic Algorithms: Springer. 2001 324-327.
[206]. Brits R, Engelbrecht A P, van den Bergh F. Solving systems of unconstrained equations using particle swarm optimizers, in Proceedings of IEEE Conference on Systems, Man, and Cybernetics 2002(SMC 2002). Hammamet, Tunisa. 2002 102-107.
[207].徐俊杰,忻展红.基于两阶段策略的粒子群优化.北京邮电大学学报(自然版),2007.30(1):136-139.