Suppose that we use a meta-heuristic algorithm to find the global optimal solution in a discrete space problem. Is the time complexity of meta-heuristic algorithms determined? As an example, in algorithms such as Genetic Algorithm, PSO and TLBO, how many percents of the total space is searched on average to get the answer? Is it possible to find the optimal point in a discrete problem whose number of solutions is 2^200?
1. Even assuming that meta-heuristic algorithm found the global optimal solution, he will never know about it, if the global solution was not known in advance or the lower boundary was not obtained, which turned out to be equal to the found heuristic solution.
2. Time complexity of meta-heuristic algorithms for searching the global optimal solution can not be determined, because these algorithms do not guarantee the finding of the global optimal solution within a given time limit.
3. "how many percents of the total space is on average to get the answer?". In my opinion, this depends on the individual task
4. "Is it possible to find the optimal point in a discrete problem?
Yes, it is possible, if the heuristic solution turns out to be equal to the lower boundary, which must be found. It is guaranteed to find the optimal point only with the use of an exact algorithm, for example "branch & bound", however the decision time can not be predicted, since it depends on the individual combinatorial model and the nature of the initial data.
this is a recurring question in Researchgate, please check the following link:
https://www.researchgate.net/post/What_are_the_time_complexity_and_space_complexity_of_PSO_ACO_FA_ABC_GSO_IWD_and_how_might_I_find_them
In particular, Mahboobeh Parsapoor shares an interesting paper about this issue.
Hi
see this:
https://www.researchgate.net/post/Compare_the_complexity_of_metaheuristic_algorithms
can someone give reference is that time complexity can't applied or hard to applied in metaheuristic algorithm ?
I need it for my research background ,,,
- Badges
- Science topic
- Similar topics
- Engineering
- Petroleum Engineering
- Gas