Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
How do you determine the Time Complexity of a Genetic Algorithm(in general)? If possible.
I have been thinking about this a lot, and all of the teaching I have had is related to determining the Time Complexity of problems that are much less stochastic in nature.
Genetic algorithms are a metaheuristic and as such there is no general analysis that applies to all genetic algorithms at once (without being super loose). In general, when you are searching for information on the run-time of genetic algorithms, you will have more luck if you use the terms "convergence time", since that is the more common terminology. A good start on some formal techniques:
Y. Rabinovich, A. Wigderson. Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999.
For more resources on formal treatments, consider the cstheory question: Provable statements about genetic algorithms.
I agree with the previous answers, and I also add the following.
We usually dont care about the time complexity of a genetic algorithm. We usually care how good are the results in comparison to some benchmark, and about the convergence rate.
You can see however that genetic algorithms runs in iterations. Initially, a set of solutions $S$ are generated randomly ($S$ is called a population). The costs of the solutions of $S$ are computed. Some operations are done over the the solutions of $S$ in each iterations such as crossover, mutation etc ... . The best $k$ solutions in $k$ are kept in $S$ and we continue as previous. After the last iteration, we output the best solution we found.
You can note here that the time cost of an iteration depends on the inner operations (e.g. crossovers, mutation and others, finding best $k$ distinct solutions, generate random solutions, calculate cost of the solutions of $S$ etc .. ) which are usually simple to implement, and also problem-dependent. In general, they depend on the size of a solution.
The execution time of a genetic algorithm also depends on the number of iterations (obviously !). Typically, we want to stop when we converge to a solution that is hardly improved. How to find the number of iterations that guarantee this ? there are some probabilistic analyses to find the average convergence time. See for example [1] (quite interesting results). But you will note that we did not reach yet the level of analyzing the complex problems where genetic algorithms are used. Therefore, in many cases, the number of iterations in a genetic algorithm is decided experimentally.
[1] Oliveto, Pietro S., Jun He, and Xin Yao. "Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results." International Journal of Automation and Computing 4.3 (2007): 281-293.
