Abstract

Author(s): Debdutta Burman, Sandip Sarkar, Anirban Bhar, Sujata Kundu

In the theory of evolutionary algorithms (EAs), computational time complexity is an essential problem. This study reports on the average time complexity of EAs. Researchers have been studying the computational time complexity of evolutionary algorithms since the mid1990s (EAs). The earliest findings were based on toy problems using extremely simple algorithms like the (1+1)-EA. This work resulted in a better knowledge of how EAs perform on various types of fitness landscapes, as well as generic mathematical methods that could be used to analyse increasingly complex EAs on more realistic challenges. In reality, it has been able to study the (1+1)-EA on combinatorial optimization problems with real-world applications, as well as more realistic population-based EAs on structured toy problems in recent years. The results of these two study lines have been surveyed in this report. The most prevalent mathematical procedures are presented, as well as the essential ideas that underpin them and their various applications.