Volume 4 Number 3
July 2007
Article Contents
Pietro S. Oliveto, Jun He and Xin Yao. Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results. International Journal of Automation and Computing, vol. 4, no. 3, pp. 281-293, 2007. doi: 10.1007/s11633-007-0281-3
Cite as: Pietro S. Oliveto, Jun He and Xin Yao. Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results. International Journal of Automation and Computing, vol. 4, no. 3, pp. 281-293, 2007. doi: 10.1007/s11633-007-0281-3

Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results

  • Received: 2007-03-05
Fund Project:

This work was supported by an EPSRC grant (No.EP/C520696/1).

  • Computational time complexity analyzes of evolutionary algorithms (EAs) have been performed since the mid-nineties. The first results were related to very simple algorithms,such as the (1+1)-EA,on toy problems.These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems.In fact,in recent years,it has been possible to analyze the (1+1)-EA on combinatorial optimization problems with practical applications and more realistic population-baeed EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines.The most common mathematical techniques are introduced,the basic ideas behind them are discussed and their elective applications are highlighted.Solved problems that were still open are enumerated as are those still awaiting for a solution.New questions and problems arisen in the meantime are also considered.
  • 加载中
  • [1] R.Sarker,M.Mohammadian,X.Yao.Evolutionary Optimization,Kluwer Academic Publishers,Norwell,MA,USA,2002.
    [2] D.E.Goldberg.Genetic Algorithms for Search,Optimization,and Machine Learning,Addison-Wesley,USA,1989.
    [3] J.H.Holland.Adaptation in Natural and Artificial Systems,2nd ed.,MIT Press,Cambridge,MA,1992.
    [4] A.E.Eiben,G.Rudolph.Theory of Evolutionary Algorithms:A Bird's Eye View.Theoretical Computer Science,vol.229,no.1-2,pp.3-9,1999.
    [5] T.Back,D.B.Fogel,Z.Michalewicz.Handbook of Evolutionary Computation,IOP Publishing Ltd,Bristol,UK,1997.
    [6] G.Rudolph.Convergence Analysis of Canonical Genetic Algorithms.IEEE Transactions on Neural Networks,vol.5,no.l,pp.96-101,1994.
    [7] G.Rudolph.Finite Markov Chain Results in Evolutionary Computation:A Tour d'Horizon.Fundamenta Informati-cae,vol.35,no.1-4,pp.67-89,1998.
    [8] H.Aytug,G.J.Koehler.Stopping Criteria for Finite Length Genetic Algorithms.ORSA Journal on Computing,vol.8,no.2,pp.183-191,1996.
    [9] D.Greenhalgh,S.Marshall.Convergence Criteria for Genetic Algorithms.SIAM Journal on Computing,vol.30,no.l,pp.269-282,2000.
    [10] M.Safe,J.A.Carballido,I.Ponzoni,N.B.Brignole.On Stopping Criteria for Genetic Algorithms,In 17th Brazilian Symposium on Artificial Intelligence,Lecture Notes in Artificial Intelligence,Springe-Verlag,vol.3171,pp.405-413,2004.
    [11] S.Droste,T.Jansen,I.Wegener.On the Analysis of the (1+ 1) Evolutionary Algorithm.Theoretical Computer Science,vol.276,no.1-2,pp.51-81,2002.
    [12] X.Yao.An Overview of Evolutionary Computation.Chinese Journal of Advanced Software Research,vol.3,no.1,pp.12-29,1996.
    [13] H.G.Beyer,H.G.Schwefel,I.Wegener.How to Analyse Evolutionary Algorithms.Theoretical Computer Science,vol.287,no.1,pp.101-130,2002.
    [14] I.Wegener.Methods for the Analysis of Evolutionary Algorithms on Pseudo-Boolean Functions.In Evolutionary Optimization,R.Sarker,M.Mohammadian,X.Yao (eds.),Kluwer Academic Publishers,Norwell,MA,USA,2002.
    [15] S.Droste,T.Jansen,I.Wegener.A Rigorous Complexity Analysis of the (1+1) Evolutionary Algorithm for Separable Functions with Boolean Inputs.Evolutionary Computation,vol.6,no.2,pp.185-196,1998.
    [16] I.Wegener.On the Design and Analysis of Evolutionary Algorithms.In Proceedings of the Workshop on Algorithm Engineering as a New Paradigm,Kyoto University,Japan,pp.37-47,2000.
    [17] T.Jansen,I.Wegener.Evolutionary Algorithms:How to Cope with Plateaus of Constant Fitness and When to Reject Strings of the Same Fitness.IEEE Transactions on Evolutionary Computation,vol.5,no.6,pp.589-599,2000.
    [18] M.Motwani,P.Raghavan.Randomized Algorithms,Cambridge University Press,UK,1995.
    [19] T.Back.Optimal Mutation Rates in Genetic Search.In Proceedings of the 5th International Conference on Genetic Algorithms,Morgan-Kaufman,pp.2-8,1993.
    [20] V.Cutello,G.Nicosia,P.S.Oliveto,M.Romeo.On the Convergence of Immune Algorithms.In Proceedings of the 1st IEEE Symposium on Foundations of Computational Intelligence,Honolulu,Hawaii,USA,2007.
    [21] J.He,X.Yao.Towards an Analytic Framework for Analyzing the Computation Time of Evolutionary Algorithms.Artificial Intelligence,vol.145,no.1-2 pp.59-97,2003.
    [22] M.losifescu.Finite Markov Processes and Their Applications,John Wiley & Sons,1980.
    [23] D.L.Isaacson,R.W.Madsen.Markov Chains:Theory and Applications,John Wiley & Sons,1976.
    [24] J.He,X.Yao.From an Individual to a Population:An Analysis of the 1st Hitting Time of Population-based Evolutionary Algorithms.IEEE Transactions Evolutionary Computation,vol.6,no.5,pp.495-511,2002.
    [25] W.Feller.An Introduction to Probability Theory and Its Applications,vol.1,John Wiley & Sons,1968.
    [26] I.Wegener.Theoretical Aspects of Evolutionary Algorithms.In Proceedings of the 28th International Colloquium on Automata,Languages and Programming,London,UK,pp.64-78,2001.
    [27] S.Droste,T.Jansen,I.Wegener.On the Optimization of Unimodal Functions with the (1 + 1) Evolutionary Algorithm.In Proceedings of the Parallel Problem Solving from Nature Conference,Lecture Notes in Computer Science,Springer-Verlag,vol.1498,pp.13-22,1998.
    [28] O.Giel,I.Wegener.Evolutionary Algorithms and the Maximum Matching Problem.In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science,Speringer-Verlag,pp.415-426,2003.
    [29] P.S.Oliveto,J.He,X.Yao.Evolutionary Algorithms and the Vertex Cover Problem.In Proceedings of the Congress on Evolutionary Computation,to be published.
    [30] C.Witt.Runtime Analysis of the (/i+1) EA on Simple pseudo-Boolean Functions.In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation,Seattle,Washington,USA,pp.651-658,2006.
    [31] T.Jansen,I.Wegener.On the Analysis of Evolutionary Algorithms-A Proof that Crossover Really Can Help.In Proceedings of the 7th Annual European Symposium on Algorithms,Springer-Verlag,pp.184-193,1999.
    [32] J.He.Study on the Foundation of Evolutionary Computation.Technical Report,Department of Computer Science,Harbin Institute of Technology,China,1998 (in Chinese).
    [33] J.He,X.Yao.Drift Analysis and Average Time Complexity of Evolutionary Algorithms.Artificial Intelligence,vol.127,no.1,pp.57-85,2001.
    [34] J.He,X.Yao.A Study of Drift Analysis for Estimating Computation Time of Evolutionary Algorithms.Natural Computing:An International Journal,vol.3,no.1,pp.21-35,2004.
    [35] T.Jansen,I.Wegener.On the Utility of Populations in Evolutionary Algorithms.In Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation,IEEE,pp.1034-1041,2001.
    [36] T.Jansen,I.Wegener.Real Royal Road Functions:Where Crossover Provably is Essential.Discrete Applied Mathematics,vol.149,no.1-3,pp.111-125,2005.
    [37] C.Witt.Population Size vs.Runtime of a Simple EA.In Proceedings of the Congress on Evolutionary Computation,Canberra,pp.1996-2003,2003.
    [38] T.Storch.Real Royal Road Functions for Constant Population Size.Theoretical Computer Science,vol.320,no.1,pp.123-134,2004.
    [39] T.Jansen,K.A.De Jong,I.Wegener.On the Choice of the Offspring Population Size in Evolutionary Algorithms.Evolutionary Computation,vol.13,no.4,pp.413-440,2005.
    [40] J.Jagerskupper,T.Storch.When the Plus Strategy Outperforms the Comma Strategy and When Not.In Proceedings of the 1st IEEE Symposium on Foundations of Computational Intelligence,Hawaii,USA,pp.25-32,2007.
    [41] M.R.Garey,D.S.Johnson.Computers and Intractability a Guide to the Theory of 1VP-Completeness,W.H.Freeman and Company,New York,1979.
    [42] J.Scharnow,K.Tinnefeld,I.Wegener.Fitness Landscapes Based on Sorting and Shortest Path Problems.In Proceedings of 7th Conference on Parallel Problem Solving from Nature Conference,pp.54-63,2002.
    [43] F.Neumann,I.Wegener.Minimum Spanning Trees Made Easier Via Multi-objective Optimization.Natural Computing,vol.5,no.3,pp.305-319,2006.
    [44] T.Friedrich,J.He,N.Hebbinghaus,F.Neumann,C.Witt.Approximating Covering Problems by Randomized Search Heuristics Using Multi-objective Models.In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation,2007,to be published.
    [45] F.Neumann.Expected Run-times of Evolutionary Algorithms for the Eulerian Cycle Problem.In Proceedings of the Congress on Evolutionary Computation,IEEE,pp.904-910,2004.
    [46] B.Doerr,N.Hebbinghaus,F.Neumann.Speeding Up Evolutionary Algorithms through Restricted Mutation Operators.In Proceedings of the 9th Parallel Problem Solving from Nature Conference,Leture Notes in Computer Science,Springer-Verlag,Reykjavik,Iceland,vol.4193,pp.978-987,2006.
    [47] B.Doerr,C.Klein,T.Storch.Faster Evolutionary Algorithms by Superior Graph Representation.In Proceedings of the 1st IEEE Symposium on Foundations of Computational Intelligence,Hawaii,USA,pp.245-250,2007.
    [48] B.Doerr,D.Johannsen.Adjacency List Matchings-An Ideal Genotype for Cycle Covers.In Proceedings of the Annual Conference on Genetic and Evolutionary Computation,2007,to be published.
    [49] F.Neumann,I.Wegener.Randomized Local Search,Evolutionary Algorithms,and the Minimum Spanning Tree Problem.In Proceedings of Genetic and Evolutionary Computation Conference,Leture Notes in Computer Science,Springer-Verlag,Seattle,Washington,USA,vol.3102,pp.713-724,2004.
    [50] C.Witt.Worst-case and Average-case Approximations by Simple Randomized Search Heuristics.In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science,Lectures Notes in Computer Science,Springer-Verlag,Stuttgart,Germany,vol.3404,pp.44-56,2005.
    [51] D.S.Hochbaum.Approximation Algorithms for NP-Hard Problems,Wadsworth Publishing Company,USA,1996.
    [52] T.Storch.How randomized search heuristics find maximum cliques in planar graphs.In Proceedings of the Annuai Conference on Genetic and EvoJutionary Computation,Seattle,Washington,USA,pp.567-574,2006.
    [53] T.Storch.Finding Large Cliques in Sparse Semi-random Graphs by Simple Randomised Search Heuristics,Technical Report No.CI-211/06,Fachbereich Informatik,Universitat Dortmund,2006.
    [54] G.H.Sasaki,B.Hajek.The Time Complexity of Maximum Matching by Simulated Annealing.Journai of the Association of Computing Machinery,vol.35,no.2,pp.387-403,1988.
  • 加载中
  • [1] Ziheng Chen, Hongshik Ahn. Item Response Theory Based Ensemble in Machine Learning . International Journal of Automation and Computing, 2020, 17(5): 621-636.  doi: 10.1007/s11633-020-1239-y
    [2] Farzam Matinfar. A Computational Model for Measuring Trust in Mobile Social Networks Using Fuzzy Logic . International Journal of Automation and Computing, 2020, 17(): 1-10.  doi: 10.1007/s11633-020-1232-5
    [3] Ting Liu, Yuan-Hua Wang, Dai-Zhan Cheng. Dynamics and Stability of Potential Hyper-networked Evolutionary Games . International Journal of Automation and Computing, 2017, 14(2): 229-238.  doi: 10.1007/s11633-017-1056-0
    [4] Liu-Lan Lin,  Yu-Jie Lu,  Ming-Lun Fang. Computational Modeling of the Fluid Mechanical Environment of Regular and Irregular Scaffolds . International Journal of Automation and Computing, 2015, 12(5): 529-539.  doi: 10.1007/s11633-014-0873-7
    [5] Khalid Jebari, Abdelaziz Bouroumi, Aziz Ettouhami. Fuzzy Genetic Sharing for Dynamic Optimization . International Journal of Automation and Computing, 2012, 9(6): 616-626 .  doi: 10.1007/s11633-012-0687-4
    [6] R. Saravanan, S. Ramabalan, C. Balamurugan, A. Subash. Evolutionary Trajectory Planning for an Industrial Robot . International Journal of Automation and Computing, 2010, 7(2): 190-198.  doi: 10.1007/s11633-010-0190-8
    [7] Warit Silpsrikul,  Suchin Arunsawatwong. Computation of Peak Output for Inputs Restricted in L2 and L Norms Using Finite Difference Schemes and Convex Optimization . International Journal of Automation and Computing, 2009, 6(1): 7-13.  doi: 10.1007/s11633-009-0007-9
    [8] Charlotte Bean, Chandra Kambhampati. Autonomous Clustering Using Rough Set Theory . International Journal of Automation and Computing, 2008, 5(1): 90-102.  doi: 10.1007/s11633-008-0090-3
    [9] Employing Computational Intelligence to Generate More Intelligent and Energy Efficient Living Spaces . International Journal of Automation and Computing, 2008, 5(1): 1-9.  doi: 10.1007/s11633-008-0001-7
    [10] Computational Intelligence and Games:Challenges and Opportunities . International Journal of Automation and Computing, 2008, 5(1): 45-57.  doi: 10.1007/s11633-008-0045-8
    [11] Computational Intelligence Determines Effective Rationality . International Journal of Automation and Computing, 2008, 5(1): 63-66.  doi: 10.1007/s11633-008-0063-6
    [12] Francisco Flórez-Revuelta, José Manuel Casado-Díaz, Lucas Martínez-Bernabeu. An Evolutionary Approach to the Delineation of Functional Areas Based on Travel-to-work Flows . International Journal of Automation and Computing, 2008, 5(1): 10-21.  doi: 10.1007/s11633-008-0010-6
    [13] S. C. Chiam,  K. C. Tan,  A. Al Mamum. Evolutionary Multi-objective Portfolio Optimization in Practical Context . International Journal of Automation and Computing, 2008, 5(1): 67-80.  doi: 10.1007/s11633-008-0067-2
    [14] K. Krishna Mohan, A. Srividya, Ravikumar Gedela. Computational Analysis of Performance for Heterogeneous Integrated System with Test Automation . International Journal of Automation and Computing, 2007, 4(4): 353-358.  doi: 10.1007/s11633-007-0353-4
    [15] Shengxiang Yang, Renato Tinós. A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments . International Journal of Automation and Computing, 2007, 4(3): 243-254.  doi: 10.1007/s11633-007-0243-9
    [16] Qingfu Zhang, Jianyong Sun, Edward Tsang. Combinations of Estimation of Distribution Algorithms and Other Techniques . International Journal of Automation and Computing, 2007, 4(3): 273-280.  doi: 10.1007/s11633-007-0273-3
    [17] Min Wu, Bei He, Jin-Hua She. A Fast LDL-factorization Approach for Large Sparse Positive Definite System and Its Application to One-to-one Marketing Optimization Computation . International Journal of Automation and Computing, 2007, 4(1): 88-94.  doi: 10.1007/s11633-007-0088-2
    [18] Siddhartha Shakya, John McCall. Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields . International Journal of Automation and Computing, 2007, 4(3): 262-272.  doi: 10.1007/s11633-007-0262-6
    [19] James F. Whidborne, John McKernan, Da-Wei Gu. Kolmogorov-Chaitin Complexity of Digital Controller Implementations . International Journal of Automation and Computing, 2006, 3(3): 314-322.  doi: 10.1007/s11633-006-0314-3
    [20] Yun Li, Kiam Heong Ang, Gregory C.Y. Chong, Wenyuan Feng, Kay Chen Tan, Hiroshi Kashiwagi. CAutoCSD-Evolutionary Search and Optimisation Enabled Computer Automated Control System Design . International Journal of Automation and Computing, 2004, 1(1): 76-88.  doi: 10.1007/s11633-004-0076-8
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Abstract Views (3867) PDF downloads (2070) Citations (0)

Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results

Fund Project:

This work was supported by an EPSRC grant (No.EP/C520696/1).

Abstract: Computational time complexity analyzes of evolutionary algorithms (EAs) have been performed since the mid-nineties. The first results were related to very simple algorithms,such as the (1+1)-EA,on toy problems.These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems.In fact,in recent years,it has been possible to analyze the (1+1)-EA on combinatorial optimization problems with practical applications and more realistic population-baeed EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines.The most common mathematical techniques are introduced,the basic ideas behind them are discussed and their elective applications are highlighted.Solved problems that were still open are enumerated as are those still awaiting for a solution.New questions and problems arisen in the meantime are also considered.

Pietro S. Oliveto, Jun He and Xin Yao. Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results. International Journal of Automation and Computing, vol. 4, no. 3, pp. 281-293, 2007. doi: 10.1007/s11633-007-0281-3
Citation: Pietro S. Oliveto, Jun He and Xin Yao. Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results. International Journal of Automation and Computing, vol. 4, no. 3, pp. 281-293, 2007. doi: 10.1007/s11633-007-0281-3
Reference (54)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return