进化算法的收敛性与时间复杂度分析的若干研究
|
摘要
进化算法（EvolutionaryAlgorithms，简称EAs）是受进化论中“物竞天择，适者生存”的思想启发而产生的一大类随机启发式搜索算法。这类算法主要用于求解传统计算方法难以处理的复杂优化问题，在工程优化中得到了广泛的应用，并取得了巨大的成功。当前，有关进化算法的研究大都集中于仿真实验和实际应用，相对而言，其理论基础研究的成果还不多。造成这一局面的主要原因在于进化算法运行的随机性本质，此类算法复杂的随机行为导致对其严格的理论分析很困难。收敛性与时间复杂度分析是进化算法理论基础研究的热点和难点，通过研究进化算法的收敛性与时间复杂性，可以深入了解这类算法的运行机理，从而设计出更高效的进化算法。针对进化算法复杂的随机行为，本文以随机过程理论为基础，对进化算法的收敛性与时间复杂度分析展开了研究。主要研究内容如下：
（1）采用新的理论工具分析了二元进化策略的全局收敛和早熟收敛性。离散状态马尔科夫链理论已经广泛应用于进化算法的收敛性和时间复杂度分析中，而连续状态马尔科夫过程理论目前应用还不多。本文引入连续状态马尔科夫过程理论，以测度论为工具，借助公理化的条件数学期望理论推导出关键的转移概率的计算公式，分析了以(1+1)ES为代表的连续型进化算法的收敛性，从理论上证明若采用常变异算子，包括正态分布、柯西分布在内的一大类常用变异分布可使(1+1)ES依概率收敛到全局最优解的ε-邻域；而某些自适应变异算子即使以正态分布、柯西分布为变异分布也会导致(1+1)ES在某些问题求解上陷入早熟收敛，这说明自适应调整机制并非总是有效的。通过数值试验验证了理论分析。
（2）对漂移分析进行了严格化。漂移分析（Drift analysis）是分析进化算法时间复杂性的一个强有力工具，由Jun He和Xin Yao于2001年首先引入（见ArtificialIntelligence127(1)(2001)57-85），其后得到了广泛的应用。但是原始文献的核心定理仍存在缺陷：条件过严、证明有误且不够严格等，而这些缺陷一直未见指出。鉴于该定理是漂移分析的理论基础，很有必要加以严格化。本文指出了该定理的不足之处，以测度论为工具，对该定理做了适当的修正与改进，并且给出了一个新的严格的证明。
（3）提出了基于停时理论的进化算法首达时间分析模型。漂移分析虽然理论上适用于离散型和连续型进化算法的时间复杂度分析，但是实际上到目前为止，几乎所有应用漂移分析的研究都是针对离散的组合优化问题实例进行的且其理论基础仍有待进一步严格化。本文引入停时理论作为数学工具，将进化算法的首达时间视为停时，借助时齐马氏过程的性质，提出了分析进化算法首达时间的一个新方法，在此框架下，Level-reaching Estimation Technique作为特例得到了严格的证明。为展示如何用该理论方法分析具体问题，以(1+λ)EA求解LeadingOnes函数、PEAK函数和(1+λ)ES求解倾斜平面问题为实例，分析了平均首达时间。结果表明，本文所提出的方法不但适用于离散优化问题也适用于连续优化问题，具有通用性。
（4）对若干具有现实背景的组合优化问题分析了进化算法求解的时间复杂性。分析进化算法在具有实际背景的组合优化问题上的时间复杂度是当前的一个研究难点。本文通过设计新的变异算子，用(1+1)EA求解了两个组合优化问题实例——TSP和指派问题，并分析了时间复杂度；针对带约束的组合优化问题，分析了(1+λ)EA在一个0-1背包问题实例上的时间复杂度。这些工作拓展了进化算法计算时间分析的范围，充实了进化算法在具有现实背景的组合优化问题上的时间复杂度研究。
Evolutionary Algorithms(EAs) are a wide class of randomized search heuristics inspired bythe idea of “natural selection and survival of the fittest” in the Theory of Evolution. Thesealgorithms are mainly applied to solve the complicated optimization problems which aredifficult for traditional computing methods to tackle. They have been applied widely inengineering optimization and achieved great success. At present, the researches onevolutionary algorithms are mostly focused on simulation experiments and practicalapplications, relatively speaking, the theoretical foundation researches of EAs are still few.The main reason for this situation lies in the essence of randomness in the running of EAs.Convergence and time complexity analyses are the hot topic and difficult point of thetheoretical foundation researches about EAs, we can get a deep insight into the runningprinciple of EAs through the research of their convergence and time complexity, thus workout more efficient EAs. Aiming at the complicated random behavior of EAs, this dissertationcarried out researches on the convergence and time complexity analysis of EAs based onstochastic process. The main innovations are listed as below:
(1) Theory of discrete state markov chain has been applied widely to the convergence andtime complexity analysis of EAs, while theory of continuous state markov chain does notreceive sufficient and systematic application due to its sophistication. This dissertationintroduces the theory of continuous state markov chain, uses measure theory as a tool,deduces a key formula of transition probability with the help of axiomatic theory ofconditional mathematical expectation. We analyze the convergence of the continuous EAsrepresented by (1+1)ES, prove theoretically that a wide class of common mutationdistribution including normal distribution and Cauchy distribution can make (1+1)ESconverge in probability to the ε-vicinity of the global optimum if the constant mutationoperator is adopted; While some self-adaptive mutation operators can lead (1+1)ES topremature convergence even if use the normal distribution and Cauchy distribution asmutation distribution, these results show that self-adaptive adjustment is not always effective.The theoretical analysis is validated by numerical experiments.
(2) Drift analysis is a powerful tool in the time complexity analysis of EAs, which wasintroduced by Jun He and Xin Yao in2001(see Artificial Intelligence127(1)(2001)57-85),and was applied widely later. However, the core theorem in the original paper—theorem1remained defective: the conditions were too strict, the proof contained errors and was notrigorous, etc, and these defects have not been pointed out. It is necessary to make the theorem more rigorous considering the theorem is the core and theoretical foundation of drift analysis.This dissertation points out the defects in the original theorem, uses measure theory as tool toamend and improve the theorem and presents a new and rigorous proof.
(3) This dissertation introduces the stopping time theory as a mathematical tool, regard thefirst hitting time of EAs as a stopping time, proposes a novel approach for the analysis of thefirst hitting time of EAs with the help of the properties of homogeneous markov chain, underthis framework, the Level-reaching Estimation Technique is proven rigorously as a specialcase. To illustrate how the proposed method can be applied to concrete problems in analyzingthe expected first hitting time of EAs, we analyze the runtime of (1+λ)EA on LeadingOnesproblem, PEAK function and (1+λ)ES on inclined plane problem. The results show that theproposed method has generality, it is not only suitable for discrete optimization but alsosuitable for continuous optimization.
(4) Analyzing the runtime of EAs on the real-world combinatorial optimization problems isa difficult point in the current research. This dissertation applies the theoretical method ininnovation point No.3to analyze the time complexity of (1+1)EA on two combinatorialoptimization instances—TSP and Assignment Problem; Aiming at constrained combinatorialoptimization problem, we analyze the runtime of (1+λ)EA on a0-1knapsack probleminstance. These work extend the scope of the time complexity analysis of EAs, enrich the timecomplexity research of EAs on real-world combinatorial optimization problems.
（1）采用新的理论工具分析了二元进化策略的全局收敛和早熟收敛性。离散状态马尔科夫链理论已经广泛应用于进化算法的收敛性和时间复杂度分析中，而连续状态马尔科夫过程理论目前应用还不多。本文引入连续状态马尔科夫过程理论，以测度论为工具，借助公理化的条件数学期望理论推导出关键的转移概率的计算公式，分析了以(1+1)ES为代表的连续型进化算法的收敛性，从理论上证明若采用常变异算子，包括正态分布、柯西分布在内的一大类常用变异分布可使(1+1)ES依概率收敛到全局最优解的ε-邻域；而某些自适应变异算子即使以正态分布、柯西分布为变异分布也会导致(1+1)ES在某些问题求解上陷入早熟收敛，这说明自适应调整机制并非总是有效的。通过数值试验验证了理论分析。
（2）对漂移分析进行了严格化。漂移分析（Drift analysis）是分析进化算法时间复杂性的一个强有力工具，由Jun He和Xin Yao于2001年首先引入（见ArtificialIntelligence127(1)(2001)57-85），其后得到了广泛的应用。但是原始文献的核心定理仍存在缺陷：条件过严、证明有误且不够严格等，而这些缺陷一直未见指出。鉴于该定理是漂移分析的理论基础，很有必要加以严格化。本文指出了该定理的不足之处，以测度论为工具，对该定理做了适当的修正与改进，并且给出了一个新的严格的证明。
（3）提出了基于停时理论的进化算法首达时间分析模型。漂移分析虽然理论上适用于离散型和连续型进化算法的时间复杂度分析，但是实际上到目前为止，几乎所有应用漂移分析的研究都是针对离散的组合优化问题实例进行的且其理论基础仍有待进一步严格化。本文引入停时理论作为数学工具，将进化算法的首达时间视为停时，借助时齐马氏过程的性质，提出了分析进化算法首达时间的一个新方法，在此框架下，Level-reaching Estimation Technique作为特例得到了严格的证明。为展示如何用该理论方法分析具体问题，以(1+λ)EA求解LeadingOnes函数、PEAK函数和(1+λ)ES求解倾斜平面问题为实例，分析了平均首达时间。结果表明，本文所提出的方法不但适用于离散优化问题也适用于连续优化问题，具有通用性。
（4）对若干具有现实背景的组合优化问题分析了进化算法求解的时间复杂性。分析进化算法在具有实际背景的组合优化问题上的时间复杂度是当前的一个研究难点。本文通过设计新的变异算子，用(1+1)EA求解了两个组合优化问题实例——TSP和指派问题，并分析了时间复杂度；针对带约束的组合优化问题，分析了(1+λ)EA在一个0-1背包问题实例上的时间复杂度。这些工作拓展了进化算法计算时间分析的范围，充实了进化算法在具有现实背景的组合优化问题上的时间复杂度研究。
Evolutionary Algorithms(EAs) are a wide class of randomized search heuristics inspired bythe idea of “natural selection and survival of the fittest” in the Theory of Evolution. Thesealgorithms are mainly applied to solve the complicated optimization problems which aredifficult for traditional computing methods to tackle. They have been applied widely inengineering optimization and achieved great success. At present, the researches onevolutionary algorithms are mostly focused on simulation experiments and practicalapplications, relatively speaking, the theoretical foundation researches of EAs are still few.The main reason for this situation lies in the essence of randomness in the running of EAs.Convergence and time complexity analyses are the hot topic and difficult point of thetheoretical foundation researches about EAs, we can get a deep insight into the runningprinciple of EAs through the research of their convergence and time complexity, thus workout more efficient EAs. Aiming at the complicated random behavior of EAs, this dissertationcarried out researches on the convergence and time complexity analysis of EAs based onstochastic process. The main innovations are listed as below:
(1) Theory of discrete state markov chain has been applied widely to the convergence andtime complexity analysis of EAs, while theory of continuous state markov chain does notreceive sufficient and systematic application due to its sophistication. This dissertationintroduces the theory of continuous state markov chain, uses measure theory as a tool,deduces a key formula of transition probability with the help of axiomatic theory ofconditional mathematical expectation. We analyze the convergence of the continuous EAsrepresented by (1+1)ES, prove theoretically that a wide class of common mutationdistribution including normal distribution and Cauchy distribution can make (1+1)ESconverge in probability to the ε-vicinity of the global optimum if the constant mutationoperator is adopted; While some self-adaptive mutation operators can lead (1+1)ES topremature convergence even if use the normal distribution and Cauchy distribution asmutation distribution, these results show that self-adaptive adjustment is not always effective.The theoretical analysis is validated by numerical experiments.
(2) Drift analysis is a powerful tool in the time complexity analysis of EAs, which wasintroduced by Jun He and Xin Yao in2001(see Artificial Intelligence127(1)(2001)57-85),and was applied widely later. However, the core theorem in the original paper—theorem1remained defective: the conditions were too strict, the proof contained errors and was notrigorous, etc, and these defects have not been pointed out. It is necessary to make the theorem more rigorous considering the theorem is the core and theoretical foundation of drift analysis.This dissertation points out the defects in the original theorem, uses measure theory as tool toamend and improve the theorem and presents a new and rigorous proof.
(3) This dissertation introduces the stopping time theory as a mathematical tool, regard thefirst hitting time of EAs as a stopping time, proposes a novel approach for the analysis of thefirst hitting time of EAs with the help of the properties of homogeneous markov chain, underthis framework, the Level-reaching Estimation Technique is proven rigorously as a specialcase. To illustrate how the proposed method can be applied to concrete problems in analyzingthe expected first hitting time of EAs, we analyze the runtime of (1+λ)EA on LeadingOnesproblem, PEAK function and (1+λ)ES on inclined plane problem. The results show that theproposed method has generality, it is not only suitable for discrete optimization but alsosuitable for continuous optimization.
(4) Analyzing the runtime of EAs on the real-world combinatorial optimization problems isa difficult point in the current research. This dissertation applies the theoretical method ininnovation point No.3to analyze the time complexity of (1+1)EA on two combinatorialoptimization instances—TSP and Assignment Problem; Aiming at constrained combinatorialoptimization problem, we analyze the runtime of (1+λ)EA on a0-1knapsack probleminstance. These work extend the scope of the time complexity analysis of EAs, enrich the timecomplexity research of EAs on real-world combinatorial optimization problems.
引文
[1]Poole D., Mackworth A., Goebel R.. Computational Intelligence: A Logical Approach[M].Oxford: Oxford University Press,1997
[2]张军，詹志辉，陈伟能，等．计算智能[M].北京:清华大学出版社,2009
[3]Holland J. H.. Adaptation in Natural and Artificial Systems[M]. Ann Arbor: The Universityof Michigan Press,1975
[4]Fogel L. J., Owens A. J., Walsh M. J.. Artificial Intelligence through SimulatedEvolution[M]. New York: Wiley,1996
[5]Rechenberg I.. Evolutions Strategie: Optimierung Technischer Systeme nach Prinzipien derBiologischen Evolution[M]. Stuttgart: Frommann-Holzboog,1973
[6]Koza J. R.. Genetic Programming: A Paradigm for Genetically Breeding Populations ofComputer Programs to Solve Problems[R]. CA, USA: Stanford University,1990
[7]Oliveto P. S., He J., Yao X.. Time complexity of evolutionary algorithms forcombinatorial optimization: a decade of results[J]. International Journal of Automation andComputing,2007,4(3):281-293
[8]Yao X.. Unpacking and understanding evolutionary algorithms[J]. Lecture Notes inComputer Science,2012,7311:60-76
[9]Torn A., Zilinskas A.. Global Optimization[M]. Berlin: Springer-Verlag,1989
[10]李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用[M].北京:科学出版社,2002
[11]徐宗本,张讲社,郑亚林.计算智能中的仿生学:理论与算法[M].北京:科学出版社,2003
[12]Droste S., Jansen T., Wegener I.. On the analysis of the (1+1) evolutionary algorithm[J].Theoretical Computer Science,2002,276(1-2):51-81
[13]Eiben A. E., Hinterding R., Michalewicz Z.. Parameter control in evolutionaryalgorithms[J]. IEEE Transactions on Evolutionary Computation,1999,3(2):124-141
[14]Neumann F., Witt C.. Bioinspired Computation in Combinatorial Optimization–Algorithms and Their Computational Complexity[M]. NY: Springer-Verlag,2010
[15]Rudolph G.. Convergence Properties of Evolutionary Algorithms [M]. Hamburg: VerlagDr. Kovac,1997
[16]Rudolph G.. Convergence properties of canonical genetic algorithms [J]. IEEETransaction on Neural Networks,1994,5(1):96-101
[17]Rudolph G.. Finite markov chain results in evolutionary computation: a tour d’horizon[J].Fundamenta Informaticae,1998,35(1-4):67-89
[18]Zhang Q. F.. On the convergence of a class of estimation of distribution algorithms[J].IEEE Transactions on Evolutionary Computation,2004,8(2):127-136
[19]B ck T., Fogel D. B., Michalewicz Z.. Handbook of Evolutionary Computation[M].Bristol: IOP Publishing Ltd.,1997
[20]Dasgupta S., Papadimitriou C., Vazirani U.. Algorithms[M]. The McGraw-HillCompanies, Inc.,2008
[21]He J., Yao X.. Drift analysis and average time complexity of evolutionary algorithms[J].Artificial Intelligence,2001,127(1):57–85
[22]He J., Yao X.. Towards an analytic framework for analysing the computation time ofevolutionary algorithms[J]. Artificial Intelligence,2003,145(1-2):59–97
[23]He J., Yao X.. From an individual to a population: an analysis of the first hitting time ofpopulation-based evolutionary algorithms[J]. IEEE Transactions on EvolutionaryComputation,2002,6(5):495-511
[24]Goldberg D. E.. Genetic Algorithms for Search, Optimization, and Machine Learning[M].USA: Addison-Wesley,1989
[25]Holland J. H.. Adaptation in Natural and Artificial Systems: An Introductory Analysiswith Applications to Biology, Control and Artificial Intelligence[M]. Cambridge, MA: MITPress,1992
[26]Deb K., Goldberg D. E.. Analyzing deception in trap functions[A]. Proc. of FOGA’92[C].Vail, Colorado: Morgan Kaufmann,1993:93-108
[27]Rudolph G.. Convergence of non-elitist strategies[A]. Proc. of CEC’94, vol.1[C].Piscataway: IEEE Press,1994:63-66
[28]Rudolph G.. Convergence of evolutionary algorithms in general search space[A]. Proc. ofCEC’96[C]. Piscataway: IEEE Press,1996:50~54
[29]He J., Yu X. H.. Conditions for the convergence of evolutionary algorithms[J]. Journal ofSystems Architecture,2001,47:601-612
[30]徐宗本,高勇.遗传算法过早收敛现象的特征分析及其预防[J].中国科学(E辑),1996,26(4):364-375
[31]张讲社,徐宗本,梁怡．整体退火遗传算法及其收敛充要条件[J]．中国科学(E辑),1997,27(2):154-164
[32]梁艳春,周春光,王在申．基于扩展串的等价遗传算法的收敛性[J]．计算机学报，1997,20(8):686-694
[33]彭宏,王兴华．具有Elitist选择的遗传算法的收敛速度估计[J]．科学通报，1997,42(2):144-146
[34]徐宗本,聂赞坎,张文修．遗传算法的几乎必然强收敛性——鞅方法[J]．计算机学报,2002,25(8):785-793
[35]周育人,闵华清,许孝元,李元香．多目标演化算法的收敛性研究[J]．计算机学报,2004,27(10):1415-1421
[36]周育人,岳喜顺,周继香．演化算法的收敛速率与效率分析[J]．计算机学报,2004,27(11):1485-1491
[37]王宇平,刘大莲．基于平滑技术和一维搜索的全局优化进化算法及其收敛性[J]．计算机学报,2006,29(4):670-675
[38]王宇平,李英华．求解TSP的量子遗传算法[J]．计算机学报,2007,35(5):747-755
[39]刘淳安,王宇平．动态多目标优化的进化算法及其收敛性分析[J]．电子学报,2007,35(6):1118-1121
[40]Rudolph G.. Self-adaptive mutations may lead to premature convergence[J]. IEEETransactions on Evolutionary Computation,2001,5(4):410-414
[41]阎岭,蒋静坪.进化学习策略收敛性和逃逸能力的研究[J].自动化学报,2005,31(6):873-880
[42]Agapie A., Agapie M.. Transition functions for evolutionary algorithms on continuousstate-space[J]. Journal of Mathematical Modeling and Algorithms,2007,6:297-315
[43]Agapie A., Agapie M., Zbaganu G.. Evolutionary algorithms for continuous-spaceoptimization[J]. International Journal of Systems Science,2011:1-11.(DOI:10.1080/00207721.2011.605963)
[44]Agapie A., Rudolph G.. Theoretical analysis of continuous evolutionary algorithms,TR11-2-001[R]. Dortmund: Faculty of Computer Science, TU Dortmund,2011
[45]黄翰,林智勇,郝志峰，张宇山，李学强.基于关系模型的进化算法收敛性分析与对比[J].计算机学报，2011,34(5):801-811
[46]Muszyńskia J., Varrettea S., Bouvrya P., et al.. Convergence analysis of evolutionaryalgorithms in the presence of crash-faults and cheaters[J]. Computers&Mathematics withApplications,2012,64(12):3805–3819
[47]Wegener I.. Methods for the Analysis of Evolutionary Algorithms on Pseudo-BooleanFunctions[A]. Evolutionary Optimization, R. Sarker, M. Mohammadian, X. Yao (eds.)[M].Norwell, MA: Kluwer Academic Publishers,2002
[48]Wegener I.. Theoretical aspects of evolutionary algorithms[A]. Proc. of the28thInternational Colloquium on Automata, Languages and Programming[C]. London,2001:64-78
[49]Rudolph G.. How mutation and selection solve long path problems in polynomialexpected time[J]. Evolutionary Computation,1996,4(2):195-205
[50]Droste S., Jansen T., Wegener I.. A rigorous complexity analysis of the (1+1) evolutionaryalgorithm for separable functions with boolean inputs[J]. Evolutionary Computation,1998,6(2):185-196
[51]Doerr B., Jansen T., Sudholt D., et al.. Optimizing monotone functions can be difficult[J].Lecture Notes in Computer Science,2011,6238:42-51
[52]Jansen T., Wegener I.. Evolutionary algorithms: how to cope with plateaus of constantfitness and when to reject strings of the same fitness[J]. IEEE Transactions on EvolutionaryComputation,2001,5(6):589-599
[53]Garnier J., Kallel L., Schoenauer M.. Rigorous hitting times for binary mutations[J].Evolutionary Computation,1999,7(2):167-203
[54]Garnier J., Kallel L.. Statistical distribution of the convergence time of evolutionaryalgorithms for long-path problems[J]. IEEE Trans. Evol. Comp.,2000,4(1):16-30
[55]Chen T., Tang K., et al.. A large population size can be unhelpful in evolutionaryalgorithms[J]. Theoretical Computer Science,2012,436:54-70
[56]Borisovsky P. A., Eremeev A. V.. Comparing evolutionary algorithms to the (1+1)-EA[J].Theoretical Computer Science,2008,403:33-41
[57]Suzuki J..A markov chain analysis on simple genetic algorithms[J]. IEEE Transactions onSystems, Man and Cybernetics,1995,25(4):655-659
[58]Suzuki J.. A further result on the markov chain model of genetic algorithms and itsapplication to a simulated annealing-like strategy[J]. IEEE Transactions on Systems, Man andCybernetics, Part B,1998,28(l):95-102
[59]Yu Y., Zhou Z. H. A new approach to estimating the expected first hitting time ofevolutionary algorithms[J]. Artificial Intelligence,2008,172:1809–1832
[60]Hajek B.. Hitting time and occupation time bounds implied by drift analysis withapplications[J]. Adv. Appl. Probab.,1982,14:502-525
[61]Sasaki G. H., Hajek B.. The time complexity of maximum matching by simulatedannealing[J]. J. ACM,1988,35(2):387-403
[62]He J., Yao X.. Drift analysis in studying the convergence and hitting times ofEvolutionary algorithms：an overview[J]. Wuhan University Journal of Natural Sciences,20038(1B):143-154
[63]He J., Yao X.. A study of drift analysis for estimating computation time of evolutionaryalgorithms[J]. Natural Computing: An International Journal,2004,3(1):21-35
[64]Oliveto P. S., Witt C.. Simplified drift analysis for proving lower bounds in evolutionarycomputation[J]. Algorithmica,2011,59(3):369-386
[65]J gersküpper J.. Combining Markov-chain analysis and drift analysis: The (1+1)evolutionary algorithm on linear functions reloaded[J]. Algorithmica,2011,59(3):409-424
[66]周育人,赖鑫生.关于漂移分析的注记[J].计算机工程与应用,2012,48(8):21-23
[67]Doerr B., Johannsen D., Schmidt M.. Runtime analysis of the (1+1) evolutionaryalgorithm on strings over finite alphabets[A]. Proc. of FOGA’2011[C]. NY: ACM,2011:119-126
[68]Giel O., Wegener I.. Evolutionary algorithms and the maximum matching problem[J].Lecture Notes in Computer Science,2003,2607:415-426
[69]Scharnow J., Tinnefeld K., Wegener I.. Fitness landscapes based on sorting and shortestpaths problems[J]. Lecture Notes in Computer Science,2002,2439:54-63
[70]Baswana S., Biswas S., Doerr B., et al.. Computing single source shortest paths usingsingle-objective fitness[A]. Proc. of FOGA’09[C]. NY: ACM,2009:59-66
[71]Neumann F.. Expected runtimes of evolutionary algorithms for the Eulerian cycleproblem[J]. Computers&Operations Research,2008,35(9):2750-2759
[72]Neumann F., Wegener I.. Randomized local search, evolutionary algorithms, and theminimum spanning tree problem[J]. Theoretical Computer Science,2007,378:32–40
[73]Oliveto P. S., He J., Yao X.. Analysis of the (1+1)-EA for finding approximate solutionsto vertex cover problems[J]. IEEE Transactions on Evolutionary Computation,2009,13(5):1006-1029
[74]Zhou Y. R., He J.. A runtime analysis of evolutionary algorithms for constrainedoptimization problems[J]. IEEE Transactions on Evolutionary Computation,2007,11(5):608-619
[75]Lehre P. K., Yao X.. Runtime analysis of the (1+1) EA on computing unique input outputsequences[J]. Information Sciences.2010(DOI:10.1016/j.ins.2010.01.031)
[76]Jansen T., Wegener I.. On the utility of populations in evolutionary algorithms[A]. Proc.of GECCO’01[C]. Morgan Kaufmann,2001:1034-1041
[77]Witt C.. Runtime analysis of the (μ+1) EA on simple Pseudo-Boolean functions[J].Evolutionary Computation,2006,14(1):65-86
[78]Jansen T., Wegener I.. Real royal road functions—where crossover provably isessential[J]. Discrete Applied Mathematics,2005,149(1-3):111-125
[79]Witt C.. Population size versus runtime of a simple evolutionary algorithm[J]. TheoreticalComputer Science,2008,403:104–120
[80]Oliveto P. S., He J., Yao X.. Analysis of population-based evolutionary algorithms for thevertex cover problem[A]. Proc. of CEC’08[C]. IEEE,2008:1563-1570
[81]Jansen T., Jong K. A. D., Wegener I.. On the choice of the offspring population size inevolutionary algorithms[J]. Evolutionary Computation,2005,13(4):413-440
[82]Chen T., He J., Sun G., et al.. A new approach for analyzing average time complexity ofpopulation-based evolutionary algorithms on unimodal problems[J]. IEEE Transactions onSystem, Man, and Cybernetics—Part B: Cybernetics,2009,39(5):1092-1106
[83]J gersküpper J.. Analysis of a simple evolutionary algorithm for minimization inEuclidean spaces[J]. Lecture Notes in Computer Science,2003,2719:1068-1079
[84]J gersküpper J.. Algorithmic analysis of a basic evolutionary algorithm for continuousoptimization[J]. Theoretical Computer Science,2007,379:329-347
[85]J gersküpper J.. How the (1+1) ES using isotropic mutations minimises positive definitequadratic forms[J]. Theoretical Computer Science,2006,361:38–56
[86]J gersküpper J., Witt C.. Rigorous runtime analysis of a (μ+1) ES for the spherefunction[A]. Proc. of GECCO’05[C]. Washington: ACM,2005:849-856
[87]J gersküpper J.. Probabilistic runtime analysis of (1+λ)ES using isotropic mutations[A].Proc. of GECCO’06[C]. NY: ACM,2006:461-468
[88]黄翰，郝志峰，秦勇.进化规划算法的时间复杂度分析[J].计算机研究与发展,2008,45(11):1850-1857
[89]Hao Z. F., Huang H., Lin Z. Y., Zhang Y. S.. Running time analysis of evolutionaryprogramming[J]. SCIENCE CHINA (Information Sciences),2013, to appear
[90]Witt C.. Rigorous runtime analysis of Swarm Intelligence Algorithms-An overview[A].Swarm Intel. For Multi-objective Prob., SCI, C. A. Coello Coello et al.(Eds)[C]. Berlin:Springer,2009:157-177
[91]Hao Z. F., Huang Han., Zhang X., et al.. A time complexity analysis of ACO for linearfunctions[J]. Lecture Notes in Computer Science,2006,4247:513–520
[92]Gutjahr W. J.. Mathematical runtime analysis of ACO algorithms: Survey on an emergingissue[J]. Swarm Intelligence,2007,l (1):59–79
[93]黄翰，郝志峰，吴春国，秦勇.蚁群算法的收敛速度分析[J].计算机学报,2007,30(8):1343-1353
[94]Neumann F., Witt C.. Runtime analysis of a simple ant colony optimization algorithm[J].Algorithmica,2009,54:243–255
[95]Gutjahr W. J.. First steps to the runtime complexity analysis of ant colony optimization[J].Computers and Operations Research,2008,35:2711-2727
[96]Huang H., Wu C. G., Hao Z. F.. A pheromone-rate-based analysis on the convergence timeof ACO algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B,2009,39（4）:910-923
[97]Zhou Y. R., Runtime analysis of ant colony optimization algorithm for TSP instances[J].IEEE Transactions on Evolutionary Computation,2009,13(5):1083-1092
[98]Neumann F., Witt C.. Ant colony optimization and the minimum spanning treeproblem[A]. LION2007II. LNCS5313[C]. Berlin: Springer,2008:153-166
[99]Gutjahr W. J., Sebastiani G.. Runtime analysis of ant colony optimization with best-so-farreinforcement[J]. Methodology and Computing in Applied Probability,2008,10:409-433
[100]Trelea I. C.. The particle swarm optimization algorithm: convergence analysis andparameter selection[J]. Information Processing Letters,2003,85:317-325
[101]Jiang M., Luo Y. P.. Stochastic convergence analysis and parameter selection of thestandard PSO algorithm[J]. Information Processing Letters,2007,102:8-16
[102]Clerc M., Kennedy J.. The particle swarm-explosion, stability, and convergence in amultidimensional complex space[J]. IEEE Transactions on Evolutionary Computation,2002,6:58-73
[103]Rapai′c M. R., Kanovic Z.. Time-varying PSO—convergence analysis,convergence-related parameterization and new parameter adjustment schemes[J]. InformationProcessing Letters,2009,109:548–552
[104]Witt C.. Why standard Particle Swarm Optimisers elude a theoretical runtimeanalysis[A]. Proc. of FOGA’09[C]. Orlando, Florida: ACM,2009:13-19
[105]Sudholt D., Witt C.. Runtime analysis of a binary particle swarm optimizer[J].Theoretical Computer Science,2010,411(21):2084-2100
[106]Chen T., Tang K., Chen G., Yao X.. Analysis of computational time of simple estimationof distribution algorithms[J]. IEEE Transactions on Evolutionary Computation,2010,14(1):1-22
[107]Yao X., Xu Y.. Recent advances in evolutionary computation[J]. Journal of ComputerScience and Technology.2006,21(1):1-18
[108]程士宏.高等概率论[M].北京：北京大学出版社，1996
[109]严士健，王隽骧，刘秀芳.概率论基础[M].2版.北京：科学出版社，2009
[110]缪柏其.概率论教程[M].合肥：中国科学技术大学出版社,1998
[111]Zhang Y. S., Hao Z. F., Huang H., et al.. Runtime analysis of (1+1) evolutionaryalgorithm for two combinatorial optimization instances[J]. Journal of Information&Computational Science,2011,8(15):3497-3506
[112]王宇平.进化计算的理论和方法[M].北京：科学出版社，2011
[113]林元烈.应用随机过程[M].北京：清华大学出版社，2002
[114]Pentico D. W.. Assignment problems: a golden anniversary survey[J]. European Journalof Operational Research,2007,176:774-793
[115]He S., Wu Q. H., Saunders J. R.. Group search optimizer: an optimization algorithminspired by animal searching behavior[J]. IEEE Transactions on Evolutionary Computation,2009,13(5):973-990
[116]Oliveto P. S., Witt C..Erratum: Simplied drift analysis for proving lower bounds inevolutionary computation[DB/OL]. arXiv:1211.7184v1,2012
[117]Sudholt D., Rowe J.. The choice of the offspring population size in the (1,λ) EA[A].Proc. of GECCO '12[C]. NY: ACM Press,2012:1349-1356
[118]Doerr B., Goldberg L. A.. Adaptive drift analysis[J]. Algorithmica,2013,65(1):224-250
[119]Witt C.. Tight bounds on the optimization time of a randomized search heuristic onlinear functions[J]. Combinatorics, Probability and Computing,2013,22(02):294-318
[120]Sudholt D.. A new method for lower bounds on the running time of evolutionaryalgorithms[J]. IEEE Transactions on Evolutionary Computation,2012(DOI:10.1109/TEVC.2012.2202241)
[121]He J., Chen T.. A general analysis of evolutionary algorithms for hard and easy fitnessfunctions[DB/OL]. arXiv:1203.6286v1,2012
[122]Chen T., Chen Y., Tang K., et al.. The impact of mutation rate on the computation timeof evolutionary dynamic optimization[DB/OL]. arXiv:1106.0566v1,2011
[123]Doerr B., Neumann F., Sudholt D., et al.. Runtime analysis of the1-ANT ant colonyoptimizer[J].Theoretical Computer Science,2011,412(17):1629-1644
[124]Sudholt D., Thyssen C.. Running time analysis of ant colony optimization for shortestpath problems[J].Journal of Discrete Algorithms,2012,10:165-180
[125]Lehre P. K., Yao X.. Crossover can be constructive when computing unique input-outputsequences[J]. Soft Computing,2011,15:1675–1687
[2]张军，詹志辉，陈伟能，等．计算智能[M].北京:清华大学出版社,2009
[3]Holland J. H.. Adaptation in Natural and Artificial Systems[M]. Ann Arbor: The Universityof Michigan Press,1975
[4]Fogel L. J., Owens A. J., Walsh M. J.. Artificial Intelligence through SimulatedEvolution[M]. New York: Wiley,1996
[5]Rechenberg I.. Evolutions Strategie: Optimierung Technischer Systeme nach Prinzipien derBiologischen Evolution[M]. Stuttgart: Frommann-Holzboog,1973
[6]Koza J. R.. Genetic Programming: A Paradigm for Genetically Breeding Populations ofComputer Programs to Solve Problems[R]. CA, USA: Stanford University,1990
[7]Oliveto P. S., He J., Yao X.. Time complexity of evolutionary algorithms forcombinatorial optimization: a decade of results[J]. International Journal of Automation andComputing,2007,4(3):281-293
[8]Yao X.. Unpacking and understanding evolutionary algorithms[J]. Lecture Notes inComputer Science,2012,7311:60-76
[9]Torn A., Zilinskas A.. Global Optimization[M]. Berlin: Springer-Verlag,1989
[10]李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用[M].北京:科学出版社,2002
[11]徐宗本,张讲社,郑亚林.计算智能中的仿生学:理论与算法[M].北京:科学出版社,2003
[12]Droste S., Jansen T., Wegener I.. On the analysis of the (1+1) evolutionary algorithm[J].Theoretical Computer Science,2002,276(1-2):51-81
[13]Eiben A. E., Hinterding R., Michalewicz Z.. Parameter control in evolutionaryalgorithms[J]. IEEE Transactions on Evolutionary Computation,1999,3(2):124-141
[14]Neumann F., Witt C.. Bioinspired Computation in Combinatorial Optimization–Algorithms and Their Computational Complexity[M]. NY: Springer-Verlag,2010
[15]Rudolph G.. Convergence Properties of Evolutionary Algorithms [M]. Hamburg: VerlagDr. Kovac,1997
[16]Rudolph G.. Convergence properties of canonical genetic algorithms [J]. IEEETransaction on Neural Networks,1994,5(1):96-101
[17]Rudolph G.. Finite markov chain results in evolutionary computation: a tour d’horizon[J].Fundamenta Informaticae,1998,35(1-4):67-89
[18]Zhang Q. F.. On the convergence of a class of estimation of distribution algorithms[J].IEEE Transactions on Evolutionary Computation,2004,8(2):127-136
[19]B ck T., Fogel D. B., Michalewicz Z.. Handbook of Evolutionary Computation[M].Bristol: IOP Publishing Ltd.,1997
[20]Dasgupta S., Papadimitriou C., Vazirani U.. Algorithms[M]. The McGraw-HillCompanies, Inc.,2008
[21]He J., Yao X.. Drift analysis and average time complexity of evolutionary algorithms[J].Artificial Intelligence,2001,127(1):57–85
[22]He J., Yao X.. Towards an analytic framework for analysing the computation time ofevolutionary algorithms[J]. Artificial Intelligence,2003,145(1-2):59–97
[23]He J., Yao X.. From an individual to a population: an analysis of the first hitting time ofpopulation-based evolutionary algorithms[J]. IEEE Transactions on EvolutionaryComputation,2002,6(5):495-511
[24]Goldberg D. E.. Genetic Algorithms for Search, Optimization, and Machine Learning[M].USA: Addison-Wesley,1989
[25]Holland J. H.. Adaptation in Natural and Artificial Systems: An Introductory Analysiswith Applications to Biology, Control and Artificial Intelligence[M]. Cambridge, MA: MITPress,1992
[26]Deb K., Goldberg D. E.. Analyzing deception in trap functions[A]. Proc. of FOGA’92[C].Vail, Colorado: Morgan Kaufmann,1993:93-108
[27]Rudolph G.. Convergence of non-elitist strategies[A]. Proc. of CEC’94, vol.1[C].Piscataway: IEEE Press,1994:63-66
[28]Rudolph G.. Convergence of evolutionary algorithms in general search space[A]. Proc. ofCEC’96[C]. Piscataway: IEEE Press,1996:50~54
[29]He J., Yu X. H.. Conditions for the convergence of evolutionary algorithms[J]. Journal ofSystems Architecture,2001,47:601-612
[30]徐宗本,高勇.遗传算法过早收敛现象的特征分析及其预防[J].中国科学(E辑),1996,26(4):364-375
[31]张讲社,徐宗本,梁怡．整体退火遗传算法及其收敛充要条件[J]．中国科学(E辑),1997,27(2):154-164
[32]梁艳春,周春光,王在申．基于扩展串的等价遗传算法的收敛性[J]．计算机学报，1997,20(8):686-694
[33]彭宏,王兴华．具有Elitist选择的遗传算法的收敛速度估计[J]．科学通报，1997,42(2):144-146
[34]徐宗本,聂赞坎,张文修．遗传算法的几乎必然强收敛性——鞅方法[J]．计算机学报,2002,25(8):785-793
[35]周育人,闵华清,许孝元,李元香．多目标演化算法的收敛性研究[J]．计算机学报,2004,27(10):1415-1421
[36]周育人,岳喜顺,周继香．演化算法的收敛速率与效率分析[J]．计算机学报,2004,27(11):1485-1491
[37]王宇平,刘大莲．基于平滑技术和一维搜索的全局优化进化算法及其收敛性[J]．计算机学报,2006,29(4):670-675
[38]王宇平,李英华．求解TSP的量子遗传算法[J]．计算机学报,2007,35(5):747-755
[39]刘淳安,王宇平．动态多目标优化的进化算法及其收敛性分析[J]．电子学报,2007,35(6):1118-1121
[40]Rudolph G.. Self-adaptive mutations may lead to premature convergence[J]. IEEETransactions on Evolutionary Computation,2001,5(4):410-414
[41]阎岭,蒋静坪.进化学习策略收敛性和逃逸能力的研究[J].自动化学报,2005,31(6):873-880
[42]Agapie A., Agapie M.. Transition functions for evolutionary algorithms on continuousstate-space[J]. Journal of Mathematical Modeling and Algorithms,2007,6:297-315
[43]Agapie A., Agapie M., Zbaganu G.. Evolutionary algorithms for continuous-spaceoptimization[J]. International Journal of Systems Science,2011:1-11.(DOI:10.1080/00207721.2011.605963)
[44]Agapie A., Rudolph G.. Theoretical analysis of continuous evolutionary algorithms,TR11-2-001[R]. Dortmund: Faculty of Computer Science, TU Dortmund,2011
[45]黄翰,林智勇,郝志峰，张宇山，李学强.基于关系模型的进化算法收敛性分析与对比[J].计算机学报，2011,34(5):801-811
[46]Muszyńskia J., Varrettea S., Bouvrya P., et al.. Convergence analysis of evolutionaryalgorithms in the presence of crash-faults and cheaters[J]. Computers&Mathematics withApplications,2012,64(12):3805–3819
[47]Wegener I.. Methods for the Analysis of Evolutionary Algorithms on Pseudo-BooleanFunctions[A]. Evolutionary Optimization, R. Sarker, M. Mohammadian, X. Yao (eds.)[M].Norwell, MA: Kluwer Academic Publishers,2002
[48]Wegener I.. Theoretical aspects of evolutionary algorithms[A]. Proc. of the28thInternational Colloquium on Automata, Languages and Programming[C]. London,2001:64-78
[49]Rudolph G.. How mutation and selection solve long path problems in polynomialexpected time[J]. Evolutionary Computation,1996,4(2):195-205
[50]Droste S., Jansen T., Wegener I.. A rigorous complexity analysis of the (1+1) evolutionaryalgorithm for separable functions with boolean inputs[J]. Evolutionary Computation,1998,6(2):185-196
[51]Doerr B., Jansen T., Sudholt D., et al.. Optimizing monotone functions can be difficult[J].Lecture Notes in Computer Science,2011,6238:42-51
[52]Jansen T., Wegener I.. Evolutionary algorithms: how to cope with plateaus of constantfitness and when to reject strings of the same fitness[J]. IEEE Transactions on EvolutionaryComputation,2001,5(6):589-599
[53]Garnier J., Kallel L., Schoenauer M.. Rigorous hitting times for binary mutations[J].Evolutionary Computation,1999,7(2):167-203
[54]Garnier J., Kallel L.. Statistical distribution of the convergence time of evolutionaryalgorithms for long-path problems[J]. IEEE Trans. Evol. Comp.,2000,4(1):16-30
[55]Chen T., Tang K., et al.. A large population size can be unhelpful in evolutionaryalgorithms[J]. Theoretical Computer Science,2012,436:54-70
[56]Borisovsky P. A., Eremeev A. V.. Comparing evolutionary algorithms to the (1+1)-EA[J].Theoretical Computer Science,2008,403:33-41
[57]Suzuki J..A markov chain analysis on simple genetic algorithms[J]. IEEE Transactions onSystems, Man and Cybernetics,1995,25(4):655-659
[58]Suzuki J.. A further result on the markov chain model of genetic algorithms and itsapplication to a simulated annealing-like strategy[J]. IEEE Transactions on Systems, Man andCybernetics, Part B,1998,28(l):95-102
[59]Yu Y., Zhou Z. H. A new approach to estimating the expected first hitting time ofevolutionary algorithms[J]. Artificial Intelligence,2008,172:1809–1832
[60]Hajek B.. Hitting time and occupation time bounds implied by drift analysis withapplications[J]. Adv. Appl. Probab.,1982,14:502-525
[61]Sasaki G. H., Hajek B.. The time complexity of maximum matching by simulatedannealing[J]. J. ACM,1988,35(2):387-403
[62]He J., Yao X.. Drift analysis in studying the convergence and hitting times ofEvolutionary algorithms：an overview[J]. Wuhan University Journal of Natural Sciences,20038(1B):143-154
[63]He J., Yao X.. A study of drift analysis for estimating computation time of evolutionaryalgorithms[J]. Natural Computing: An International Journal,2004,3(1):21-35
[64]Oliveto P. S., Witt C.. Simplified drift analysis for proving lower bounds in evolutionarycomputation[J]. Algorithmica,2011,59(3):369-386
[65]J gersküpper J.. Combining Markov-chain analysis and drift analysis: The (1+1)evolutionary algorithm on linear functions reloaded[J]. Algorithmica,2011,59(3):409-424
[66]周育人,赖鑫生.关于漂移分析的注记[J].计算机工程与应用,2012,48(8):21-23
[67]Doerr B., Johannsen D., Schmidt M.. Runtime analysis of the (1+1) evolutionaryalgorithm on strings over finite alphabets[A]. Proc. of FOGA’2011[C]. NY: ACM,2011:119-126
[68]Giel O., Wegener I.. Evolutionary algorithms and the maximum matching problem[J].Lecture Notes in Computer Science,2003,2607:415-426
[69]Scharnow J., Tinnefeld K., Wegener I.. Fitness landscapes based on sorting and shortestpaths problems[J]. Lecture Notes in Computer Science,2002,2439:54-63
[70]Baswana S., Biswas S., Doerr B., et al.. Computing single source shortest paths usingsingle-objective fitness[A]. Proc. of FOGA’09[C]. NY: ACM,2009:59-66
[71]Neumann F.. Expected runtimes of evolutionary algorithms for the Eulerian cycleproblem[J]. Computers&Operations Research,2008,35(9):2750-2759
[72]Neumann F., Wegener I.. Randomized local search, evolutionary algorithms, and theminimum spanning tree problem[J]. Theoretical Computer Science,2007,378:32–40
[73]Oliveto P. S., He J., Yao X.. Analysis of the (1+1)-EA for finding approximate solutionsto vertex cover problems[J]. IEEE Transactions on Evolutionary Computation,2009,13(5):1006-1029
[74]Zhou Y. R., He J.. A runtime analysis of evolutionary algorithms for constrainedoptimization problems[J]. IEEE Transactions on Evolutionary Computation,2007,11(5):608-619
[75]Lehre P. K., Yao X.. Runtime analysis of the (1+1) EA on computing unique input outputsequences[J]. Information Sciences.2010(DOI:10.1016/j.ins.2010.01.031)
[76]Jansen T., Wegener I.. On the utility of populations in evolutionary algorithms[A]. Proc.of GECCO’01[C]. Morgan Kaufmann,2001:1034-1041
[77]Witt C.. Runtime analysis of the (μ+1) EA on simple Pseudo-Boolean functions[J].Evolutionary Computation,2006,14(1):65-86
[78]Jansen T., Wegener I.. Real royal road functions—where crossover provably isessential[J]. Discrete Applied Mathematics,2005,149(1-3):111-125
[79]Witt C.. Population size versus runtime of a simple evolutionary algorithm[J]. TheoreticalComputer Science,2008,403:104–120
[80]Oliveto P. S., He J., Yao X.. Analysis of population-based evolutionary algorithms for thevertex cover problem[A]. Proc. of CEC’08[C]. IEEE,2008:1563-1570
[81]Jansen T., Jong K. A. D., Wegener I.. On the choice of the offspring population size inevolutionary algorithms[J]. Evolutionary Computation,2005,13(4):413-440
[82]Chen T., He J., Sun G., et al.. A new approach for analyzing average time complexity ofpopulation-based evolutionary algorithms on unimodal problems[J]. IEEE Transactions onSystem, Man, and Cybernetics—Part B: Cybernetics,2009,39(5):1092-1106
[83]J gersküpper J.. Analysis of a simple evolutionary algorithm for minimization inEuclidean spaces[J]. Lecture Notes in Computer Science,2003,2719:1068-1079
[84]J gersküpper J.. Algorithmic analysis of a basic evolutionary algorithm for continuousoptimization[J]. Theoretical Computer Science,2007,379:329-347
[85]J gersküpper J.. How the (1+1) ES using isotropic mutations minimises positive definitequadratic forms[J]. Theoretical Computer Science,2006,361:38–56
[86]J gersküpper J., Witt C.. Rigorous runtime analysis of a (μ+1) ES for the spherefunction[A]. Proc. of GECCO’05[C]. Washington: ACM,2005:849-856
[87]J gersküpper J.. Probabilistic runtime analysis of (1+λ)ES using isotropic mutations[A].Proc. of GECCO’06[C]. NY: ACM,2006:461-468
[88]黄翰，郝志峰，秦勇.进化规划算法的时间复杂度分析[J].计算机研究与发展,2008,45(11):1850-1857
[89]Hao Z. F., Huang H., Lin Z. Y., Zhang Y. S.. Running time analysis of evolutionaryprogramming[J]. SCIENCE CHINA (Information Sciences),2013, to appear
[90]Witt C.. Rigorous runtime analysis of Swarm Intelligence Algorithms-An overview[A].Swarm Intel. For Multi-objective Prob., SCI, C. A. Coello Coello et al.(Eds)[C]. Berlin:Springer,2009:157-177
[91]Hao Z. F., Huang Han., Zhang X., et al.. A time complexity analysis of ACO for linearfunctions[J]. Lecture Notes in Computer Science,2006,4247:513–520
[92]Gutjahr W. J.. Mathematical runtime analysis of ACO algorithms: Survey on an emergingissue[J]. Swarm Intelligence,2007,l (1):59–79
[93]黄翰，郝志峰，吴春国，秦勇.蚁群算法的收敛速度分析[J].计算机学报,2007,30(8):1343-1353
[94]Neumann F., Witt C.. Runtime analysis of a simple ant colony optimization algorithm[J].Algorithmica,2009,54:243–255
[95]Gutjahr W. J.. First steps to the runtime complexity analysis of ant colony optimization[J].Computers and Operations Research,2008,35:2711-2727
[96]Huang H., Wu C. G., Hao Z. F.. A pheromone-rate-based analysis on the convergence timeof ACO algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B,2009,39（4）:910-923
[97]Zhou Y. R., Runtime analysis of ant colony optimization algorithm for TSP instances[J].IEEE Transactions on Evolutionary Computation,2009,13(5):1083-1092
[98]Neumann F., Witt C.. Ant colony optimization and the minimum spanning treeproblem[A]. LION2007II. LNCS5313[C]. Berlin: Springer,2008:153-166
[99]Gutjahr W. J., Sebastiani G.. Runtime analysis of ant colony optimization with best-so-farreinforcement[J]. Methodology and Computing in Applied Probability,2008,10:409-433
[100]Trelea I. C.. The particle swarm optimization algorithm: convergence analysis andparameter selection[J]. Information Processing Letters,2003,85:317-325
[101]Jiang M., Luo Y. P.. Stochastic convergence analysis and parameter selection of thestandard PSO algorithm[J]. Information Processing Letters,2007,102:8-16
[102]Clerc M., Kennedy J.. The particle swarm-explosion, stability, and convergence in amultidimensional complex space[J]. IEEE Transactions on Evolutionary Computation,2002,6:58-73
[103]Rapai′c M. R., Kanovic Z.. Time-varying PSO—convergence analysis,convergence-related parameterization and new parameter adjustment schemes[J]. InformationProcessing Letters,2009,109:548–552
[104]Witt C.. Why standard Particle Swarm Optimisers elude a theoretical runtimeanalysis[A]. Proc. of FOGA’09[C]. Orlando, Florida: ACM,2009:13-19
[105]Sudholt D., Witt C.. Runtime analysis of a binary particle swarm optimizer[J].Theoretical Computer Science,2010,411(21):2084-2100
[106]Chen T., Tang K., Chen G., Yao X.. Analysis of computational time of simple estimationof distribution algorithms[J]. IEEE Transactions on Evolutionary Computation,2010,14(1):1-22
[107]Yao X., Xu Y.. Recent advances in evolutionary computation[J]. Journal of ComputerScience and Technology.2006,21(1):1-18
[108]程士宏.高等概率论[M].北京：北京大学出版社，1996
[109]严士健，王隽骧，刘秀芳.概率论基础[M].2版.北京：科学出版社，2009
[110]缪柏其.概率论教程[M].合肥：中国科学技术大学出版社,1998
[111]Zhang Y. S., Hao Z. F., Huang H., et al.. Runtime analysis of (1+1) evolutionaryalgorithm for two combinatorial optimization instances[J]. Journal of Information&Computational Science,2011,8(15):3497-3506
[112]王宇平.进化计算的理论和方法[M].北京：科学出版社，2011
[113]林元烈.应用随机过程[M].北京：清华大学出版社，2002
[114]Pentico D. W.. Assignment problems: a golden anniversary survey[J]. European Journalof Operational Research,2007,176:774-793
[115]He S., Wu Q. H., Saunders J. R.. Group search optimizer: an optimization algorithminspired by animal searching behavior[J]. IEEE Transactions on Evolutionary Computation,2009,13(5):973-990
[116]Oliveto P. S., Witt C..Erratum: Simplied drift analysis for proving lower bounds inevolutionary computation[DB/OL]. arXiv:1211.7184v1,2012
[117]Sudholt D., Rowe J.. The choice of the offspring population size in the (1,λ) EA[A].Proc. of GECCO '12[C]. NY: ACM Press,2012:1349-1356
[118]Doerr B., Goldberg L. A.. Adaptive drift analysis[J]. Algorithmica,2013,65(1):224-250
[119]Witt C.. Tight bounds on the optimization time of a randomized search heuristic onlinear functions[J]. Combinatorics, Probability and Computing,2013,22(02):294-318
[120]Sudholt D.. A new method for lower bounds on the running time of evolutionaryalgorithms[J]. IEEE Transactions on Evolutionary Computation,2012(DOI:10.1109/TEVC.2012.2202241)
[121]He J., Chen T.. A general analysis of evolutionary algorithms for hard and easy fitnessfunctions[DB/OL]. arXiv:1203.6286v1,2012
[122]Chen T., Chen Y., Tang K., et al.. The impact of mutation rate on the computation timeof evolutionary dynamic optimization[DB/OL]. arXiv:1106.0566v1,2011
[123]Doerr B., Neumann F., Sudholt D., et al.. Runtime analysis of the1-ANT ant colonyoptimizer[J].Theoretical Computer Science,2011,412(17):1629-1644
[124]Sudholt D., Thyssen C.. Running time analysis of ant colony optimization for shortestpath problems[J].Journal of Discrete Algorithms,2012,10:165-180
[125]Lehre P. K., Yao X.. Crossover can be constructive when computing unique input-outputsequences[J]. Soft Computing,2011,15:1675–1687