| Time Complexity of Evolutionary Algorithms for Combinatorial Optimization： A Decade of Results |
| |
| 作者姓名： | Pietro S. Oliveto Jun He Xin Yao |
| |
| 作者单位： | The Center |
| |
| 基金项目： | 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.
|
| 关 键 词： | 进化算法 计算复杂性 最优化 计算机理论 |
| 收稿时间： | 5 March 2007 |
| 修稿时间： | 2007-03-052007-05-31 |
Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results |
| |
| Pietro S. Oliveto Jun He Xin Yao.Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results[J].International Journal of Automation and computing,2007,4(3):281-293. |
| |
| Authors: | Pietro S Oliveto Jun He Xin Yao |
| |
| 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. |
| |
| Keywords: | Evolutionary algorithms computational complexity combinatorial optimization evolutionary computation theory |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《国际自动化与计算杂志》浏览原始摘要信息 |
|
点击此处可从《国际自动化与计算杂志》下载全文 |
