I want to know that how to search the paper about the algorithm complexity. such as Genetic Programming, Kalman filter, Particle filter and so on. I can't search the paper about it. Thx.
I can answer the Genetic Programming part.
Say we have a GP working on populations size of p, for n generations. Lets say the worst case complexity of applying the fitness function to one individual is X.
For each generation, the fitness function is applied to each individual, thus the complexity is:
O(X*p*n)
You might also want to add factor for the cost of crossover and mutation. In particular, for mutation one needs to iterate over an individual. If the individual has length k then we have:
O(X*p*n*k)
hi, in Google Scholar type the key words such as Genetic Programming, Kalman filter, Particle filter. It will bring papers related to those key words.
Given the usual choices (point mutation, one point crossover, roulette wheel selection) a Genetic Algorithms complexity is O(g(nm + nm + n)) with g the number of generations, n the population size and m the size of the individuals. Therefore the complexity is on the order of O(gnm))
https://pdfs.semanticscholar.org/7453/3e303ffdfa9f32f1da9cbfbd9394c5e6a3c7.pdf
http://www.tandfonline.com/doi/abs/10.1080/03772063.1998.11416038
http://liu.diva-portal.org/smash/get/diva2:316745/FULLTEXT01.pdf
Hi,Jack McKay Fletcher .your answer is very detailed. I still want to know the paper about complexity of GP. Thank you
The algorithm complexity in GP needs to establish whether the complexity of evaluation, reproductive operators are taken into account. The complexity of GP can vary in my opinion, if you are evaluating more than once the encoded algorithm....
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms