Computational Complexity Analysis of Evolutionary Algorithms

This work has been partially supported by EPSRC

1. Introduction

Evolutionary algorithms (EAs in short) have been used widely in solving a number of combinatorial optimisation problems. However, few theoretical results exist that analyse the average computation time or time complexity of EAs 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.

2. Mathematical models and analysis tools of EAs

Markov chain model is a widely used model to analyse most of EAs. If the Markov chain associated with an EA is homogeneous, then its expected computation times (mean first hitting times) to the optimal set will satisfy a linear system. But only for some simple evolutionary algorithms and problems, it is possible to obtain an explicit solution to the linear equations for special cases: such as the probability transition matrix of the Markov chain is a tridiagonal matrix or a lower triangular matrix.

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.

3. Fitness landscape classification based on the average computation time of EAs

The classification of fitness landscapes is an important topic both in the theory and application of evolutionary computation. Although there are many attempts to characterise fitness landscapes, e.g. deception, multimodality, fitness distance correlation and epsistasis variance etc., none of them can characterise easy or hard problems very well. Based on the drift analysis, we can introduce a initial landscape classification by the average computation time of EAs. It makes a theoretical distinction between easy and hard landscapes.

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

4. Impact of population on the average computation of EAs

In today, most analyses of time complexity of EAs have been conducted for (1+1) EAs only. Theoretical results on the average computation time of population-based EAs are few. However, the vast majority of applications of EAs use a population size that is greater than one. The use of population brings robustness and efficiency to EAs. It is important to compares (1+1) EAs and population-based EAs theoretically.

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.

5. Impact of genetic operators on the average computation times of EAs

Crossover, mutation and selection are used in many EAs as enhanced search operators, but little theoretical analysis is paid to the their impact on the average computation time of EAs. There are many questions are worth studying here.

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.

6. Analysis of time complexity of EAs for P-class problem

A problem in P-class is not difficult for a problem-specific algorithm, however it is still not clear whether or not an EA can solve it more efficient than its rival, the specific algorithm. We had to analyse the time complexity of EAs on these P-class problems.

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.

7. Analysis of time complexity of EAs for NP-class problem

Although there are a few experimental reports on that EAs have a good performance on some hard problems, it will be very difficult to verify these results rigorously. In theory we had to analyse the time complexity of EAs and find out whether EAs can solve any of NP-class problems efficiently.

Related Links

1. Project Summary of "Computational Complexity Analysis of Evolutionary Algorithms" (EPSRC Grant no. EP/C520696/1)

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. 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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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)

  6. 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.

  7. 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.

  8. 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.

2. Project Summary of "Average Computation Time of Evolutionary Algorithms for Combinatorial Optimisation Problems" (EPSRC Grant no. GR/R52541/01)

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:

  1. 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.

  2. 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 .

  3. Abstract: In spite of many applications of evolutionary algorithms in optimisation, theoretical results on the computation time and time complexity of evolutionary algorithms on different optimisation problems are relatively few. It is still unclear when an evolutionary algorithm is expected to solve an optimisation problem efficiently or otherwise. This paper gives a general analytic framework for analysing first hitting times of evolutionary algorithms. The framework is built on the absorbing Markov chain model of evolutionary algorithms. The first step towards a systematic comparative study among different EAs and their first hitting times has been made in the paper .

  4. 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 .

  5. Abstract: The proof of Theorem 6 in the paper [1] contains a mistake, although the theorem is [2] correct . This note gives a revised proof and theorem. It turns out that the revised theorem is more general than the original one given an evolutionary algorithm with mutation probability $p_m=1/(2n)$, using the same proof method as given in [1].

  6. 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

  7. Abstract: Almost all analyses of time complexity of evolutionary algorithms (EAs) have been conducted for $(1+1)$ EAs only. Theoretical results on the average computation time of population-based EAs are few. However, the vast majority of applications of EAs use a population size that is greater than one. The use of population has been regarded as one of the key features of EAs. It is important to understand in depth what the real utility of population is in terms of the time complexity of EAs, when EAs are applied to combinatorial optimization problems. This paper compares $(1+1)$ EAs and $(N+N)$ EAs theoretically by deriving their first hitting time on the same problems. It is shown that a population can have a drastic impact on an EA's average computation time, changing an exponential time to a polynomial time (in the input size) in some cases. It is also shown that the first hitting probability can be improved by introducing a population. However, the results presented in this paper do not imply that population-based EAs will always be better than $(1+1)$ EAs for all possible problems.

  8. 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.

  9. Abstract: The analysis of time complexity of evolutionary algorithms has always focused on some artificial binary problems. This paper considers the average time complexity of an evolutionary algorithm for maximum cardinality matching in a graph. It is shown that the evolutionary algorithm can produce matchings with nearly maximum cardinality in average polynomial time.

  10. 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.