**This work has been partially supported by EPSRC
**

- Grant no. EP/C520696/1 on "Computational Complexity Analysis of Evolutionary Algorithms", and
- Grant no. GR/R52541/01 on "Average Computation Time of Evolutionary Algorithms for Combinatorial Optimisation Problems").

The analysis of time complexity of EAs can be traced to early 1990s, at that time the analysis is rather simple, where only a (1+1) EA was studied on a toy problem, the ONE-MAX problem. Recently, this topic has being attracted more interests from researchers in both theoretical computer science and evolutionary computation. Some initial steps have been made to understand the time complexity of EAs. But the study is just a start, and there are many open questions existing in the field.

Here we give a short introduction to our research interests in this topic.

In most cases, the above linear system is too complex to obtain any explicit solution. It is important to estimate the bounds on the average computational time.

Martingale model is an alternative model for analysing EAs, which was used to study the convergence of non-elitism EAs. Although it is not as common as the Markov chain model, it is a useful model in estimating the time complexity of EAs. Based on this a supermartingale, the drift analysis has been set up better drift conditions.

The main question here is to build a uniformly mathematical model of EAs to analyse the average computation time.

The main interesting question is to study the characteristics of easy and hard landscapes by the average computation time.

The main question is to compared the average computation time of (1+1) EAs and (N+N) EAs, and analyse in which case t the population will shorten the average computation time.

There are many different mutation operators, we should compare the average computation times of EAs using different mutations.

We had to compare the average computation time of EAs with and without crossover and show that for what kind of problems, the crossover will shorten the average computation time.

We also had to analysed different selection schemes used in the EAs and show how they influence the average computation time of EAs.

Maximum matching may be one of the hardest problems among the easy combinatorial optimisation problems. So it is a good problem to test the performance of EAs on easy problems. It is proven that the some EA needs at least exponential average time to find the exact maximum matching for a family of bipartite graphs. However, the EA can find a near maximum matching for any graph in polynomial time.

In this project, we will analyse the computational time complexity of different evolutionary algorithms (EAs) in order to gain a deeper understanding of when an EA is expected to work well (or poorly) for a given problem and why. EAs have been applied widely to solve various combinatorial optimisation problems in many scientific and engineering fields. Although some EA theories exist, EA's computational complexity is still far from being understood in depth. It is still unclear how powerful theoretically EAs are in solving combinatorial optimisation problems, and where the real theoretical power of EAs is in comparison with more traditional deterministic algorithms. A computational complexity theory for EAs will provide not only a solid foundation for EAs, but also insights and guidance in designing more efficient EAs in practice. We will produce two types of results. One is the computational complexity results of realistic EAs, not (1+1) EAs, on selected well-known combinatorial optimisation problems. The other is the complexity classes we will build. Such complexity classes enable us to characterise problems from the EA's point of view and reveal what problems are hard (or easy) for which kind of EAs. Because EAs are often used to find good approximate solutions in practice, this project will use some of the ideas and tools in analysing approximate algorithms to study theoretically the relationship between the quality of the solutions found by an EA and the EA's computation time. Experimental studies will be carried out to validate and complement our theoretical analysis. The expected outcomes of this project will not only deepen our understanding of how and when EAs work, but also guide the design of more efficient EAs in practice.

**Publications produced from this project:**

**Refereed Journal Papers:**

- T. Chen, K. Tang, G. Chen and
**X. Yao**, ``Analysis of Computational Time of Simple Estimation of Distribution Algorithms,''*IEEE Transactions on Evolutionary Computation*,**14**(1):1-22, February 2010.

Also available here. - T. Chen, J. He, G. Chen and
**X. Yao**, ``Choosing Selection Pressure for Wide-gap Problems,''*Theoretical Computer Science*,**411**(6):926-934, February 2010.

Also available here. - T. Chen, J. He, G. Sun, G. Chen and
**X. Yao**, ``A New Approach to Analyzing Average Time Complexity of Population-based Evolutionary Algorithms on Unimodal Problems,''*IEEE Transactions on Systems, Man, and Cybernetics: Part B*,**39**(5):1092-1106, October 2009.

Also available here. - P. Oliveto, J. He and
**X. Yao**, "Analysis of the (1+1)-EA for Finding Approximate Solutions to Vertex Cover Problems,"*IEEE Transactions on Evolutionary Computation*,**13**(5):1006-1029, October 2009.

Also available here. - P. K. Lehre and
**X. Yao**, "Runtime Analysis of Search Heuristics on Software Engineering Problems,"*Frontiers of Computer Science in China*,**3**(1):64-72, March 2009. - T. Friedrich, J. He, N. Hebbinghaus, F. Neumann and C. Witt, ``Analyses
of Simple Hybrid Algorithms for the Vertex Cover Problem,"
*Evolutionary Computation*,**17**(1):3-19, Spring 2009. - T. Friedrich, J. He, N. Hebbinghaus, F. Neumann and C. Witt,
"Approximating Covering Problems by Randomized Search Heuristics using
Multi-Objective Models," Accepted by
*Evolutionary Computation*, 2008. - Y. Zhou, J. He and Q. Nie, "A comparative runtime analysis of heuristic
algorithms for satisfiability problems,"
*Artificial Intelligence*,**173**(2):240-257, February 2009. - Y. Zhou and J. He, "A runtime analysis of evolutionary algorithms for
constrained optimization problems,"
*IEEE Transactions on Evolutionary Computation*,**11**(5):608-619, 2007. - J. He, C. Reeves, C. Witt and
**X. Yao**, ``A Note on Problem Difficulty Measures in Black-Box Optimization: Classification, Realizations and Predictability,''*Evolutionary Computation*,**15**(4):435-443, Winter 2007.

Available as a PDF file here. - P. S. Oliveto, J. He and
**X. Yao**, ``Time Complexity of Evolutionary Algorithms for Combinatorial Optimization: A Decade of Results,''*International Journal of Automation and Computing*,**4**(3):281-293, 2007.

**Refereed Conference Papers:**

- T. Chen, P. K. Lehre, K. Tang and
**X. Yao**, ``When Is an Estimation of Distribution Algorithm Better than an Evolutionary Algorithm?''*Proceedings of the 2009 IEEE Congress on Evolutionary Computation (CEC2009)*, Trondheim, Norway, 18-21 May 2009, IEEE Press, pp.1470-1477.

Also available here. - T. Chen, K. Tang, G. Chen and
**X. Yao**, ``Rigorous Time Complexity Analysis of Univariate Marginal Distribution Algorithm with Margins,''*Proceedings of the 2009 IEEE Congress on Evolutionary Computation (CEC2009)*, Trondheim, Norway, 18-21 May 2009, IEEE Press, pp.2157-2164.

Also available here. - P. K. Lehre and
**X. Yao**, ``Crossover can be constructive when computing unique input output sequences,''*Proceedings of the Seventh International Conference on Simulated Evolution And Learning (SEAL'2008)*, Lecture Notes in Computer Science, Volume 5361, Springer-Verlag, Berlin, December 2008, pp.595-604. - P. S. Oliveto, J. He and
**X. Yao**, ``Analysis of Population-Based Evolutionary Algorithms for the Vertex Cover Problem,''*Proceedings of the 2008 IEEE Congress on Evolutionary Computation (CEC2008)*, Hongkong, China, June 2008, IEEE Press, pp.1563-1570. - A. Arcuri, P. K. Lehre and
**X. Yao**, "Theoretical Runtime Analyses of Search Algorithms on the Test Data Generation for the Triangle Classification Problem,"*Proc. of the 1st International Workshop on Search-Based Software Testing (SBST'08)*, 9-11 April 2008. Lillehammer, Norway. (Won the Best PhD Student Paper Prize) - T. Chen, K. Tang, G. L. Chen and
**X. Yao**, ``On the Analysis of Average Time Complexity of Estimation of Distribution Algorithms,''*Proc. of the 2007 IEEE Congress on Evolutionary Computation (CEC'07)*, Singapore, 25-28 September 2007. pp.453-460. - P. S. Oliveto, J. He and
**X. Yao**, ``Evolutionary Algorithms and the Vertex Cover Problem,''*Proc. of the 2007 IEEE Congress on Evolutionary Computation (CEC'07)*, Singapore, 25-28 September 2007. pp.1870-1877. - J. He and
**X. Yao**, ``Analysis of Scalable Parallel Evolutionary Algorithms,''*Proc. of the 2006 IEEE Congress on Evolutionary Computation (CEC'06)*, Vancouver, Canada, 16-21 July 2006. pp.427-434, IEEE Press, USA.

Evolutionary algorithms (EAs) have been used widely in solving a number of combinatorial optimisation problems, e.g., VLSI cell placement, routing, job-shop scheduling, cutting stocks, timetabling, etc. There have been many reported successes for some combinatorial optimisation applications. However, few theoretical results exist that analyse the average computation time of EAs for combinatorial optimisation problems. It is unclear where the EA's real power is theoretically in solving combinatorial optimisation problems. Current theoretical work on EAs are mainly centered around schema theorems, EA's convergence and convergence rate, and dynamical system models of EAs. Average computation time of EAs has only been derived for some simple artificial problems, e.g., the one-max problem. In this project, we will study the average computation time of EAs for two combinatorial optimisation problems and analyse conditions under which an EA will take at least an exponential amount of time (in problem size) to find an optimal solution and those under which it takes no more than a polynomial amount of time. Through our analytical work, we hope to develop a set of techniques that can be used to analyse a wide range of EAs for other combinatorial optimisation problems. In the analysis of algorithms, computational time complexity is an active and important area of research. This does not appear to be the case for EAs, probably due to difficulties in analysing such stochastic search algorithms. The proposed project tries to fill in this gap.

The Final IGR Report for EPSRC Grant (GR/R52541/01):
Average Computation Time of Evolutionary Algorithms for Combinatorial
Optimisation Problems.

**Publications produced from this project:**

- J. He and
**X. Yao**, ``Time Complexity Analysis of an Evolutionary Algorithm for Finding Nearly Maximum Cardinality Matching,'' Journal of Computer Science and Technology,**19**(4):450-458, July 2004. - J. He and X. Yao, ``Towards an analytic framework for analysing
the computation time of evolutionary algorithms,''
*Artificial Intelligence*,**145**(1-2):59-97, April 2003. Available from Elsevier as a PDF file . - J. He and X. Yao, ``Erratum to: Drift analysis and average time complexity
of evolutionary algorithms: : [Artificial Intelligence 127 (2001) 57-85],''
*Artificial Intelligence*,**140**(1):245-248, September 2002. Available from Elsevier as a PDF file . - J. He and X. Yao, ``From an Individual to a Population: An Analysis
of the First Hitting Time of Population-Based Evolutionary Algorithms,''
*IEEE Transactions on Evolutionary Computation*,**6**(5):495-511, October 2002. Available from IEEE Xplore as a PDF file - J. He and X. Yao, ``Maximum Cardinality Matching by Evolutionary
Algorithms,''
*Proc. of the 2002 UK Workshop on Computational Intelligence (UKCI'02)*, J. A. Bullinaria (ed.), Birmingham, UK, September 2002, pp.53-60. - J. He and X. Yao, ``Drift Analysis and Average Time Complexity of
Evolutionary Algorithms,''
*Artificial Intelligence*,**127**(1):57-85, March 2001. Available from Elsevier as a PDF file .

**Abstract:***The computational time complexity is an important topic in the theory of evolutionary algorithms (EAs). This paper reports some new results on the average time complexity of EAs. Based on drift analysis, some useful drift conditions for deriving the time complexity of EAs are studied, including conditions under which an EA will take no more than polynomial time (in problem size) to solve a problem and conditions under which an EA will take at least exponential time (in problem size) to solve a problem. The paper first presents the general results, and then uses several problems as examples to illustrate how these general results can be applied to concrete problems in analysing the average time complexity of EAs. While previous work only considered $(1+1)$ EAs without any crossover, the EAs considered in this paper are fairly general, which use a finite population, crossover, mutation, and selection.*

Page maintained by Xin Yao.