Combinatorial optimization problems are difficult to solve especially if the possible combinations are high and there are constraints involved. Are PSO, GA, ACO, etc. suitable for it.
As far as I know, the best ones are those who follow the 'competent GA design'; see for instance http://dl.acm.org/citation.cfm?id=2008638 and http://www.amazon.com/OmeGA-Permutation-Scheduling-Evolutionary-Computation/dp/0792374606
Definitely avoid PSO (or any other technique designed for real-continuous spaces).
GA is good enough, however it depends on your combinatorial problem.
http://dl.acm.org/citation.cfm?id=1453265.1453526&coll=DL&dl=GUIDE&CFID=338516199&CFTOKEN=65856394
Definitively, hybrid proposals. Use a population based algorithm as a basis GA, ACO, EDA, and combine it with an intensification procedure LS, TS, VNS... But as other researchers highlighted, it depends on the combinatorial problem
Thanksto all for your responses
Mahboobeh; Could you mention a related paper for ICA
Often, the success depends more from the modelling and formulation of the problem than from the technique selected. The technique must be selected and adapted for the problem and not the reverse. From my experience, I can confirm that algorithms based on genetics are powerful. I agree with some previous answers.
Many evolutionary algorithms, such as GAs and ACOAs are well suited to combinatorial optimization problems, as they are designed to work with discrete variables.
If you can model your solution as binary string (like binary coded chromosome in GA), Quantum-Inspired Evolutionary Algorithm (QEA) will find global optima very quickly than GA by adjusting probability of applying variation operator (Q-gate).
According to the No-Free-Lunch theorems, none of them is better than any other in average in general.
In other words, you are advised to investigate the characteristic of your problems and choose accordingly.
Then, choosing a suitable algorithm (and setting a set of suitable parameters), also known as algorithm selection (and parameter optimization), is a higher level of optimization, i.e., a tricky mapping from solution space to algorithm space.
If you are interested in this algorithm space, hyper-heuristics might be a recent methodology to answer your question.
Have considered algorithms like stable marriage algorithm namely gale and shapely algorithm.
GA is an excellent I have tried it before .
I agree with Fan Xue. First, you need to understand the characteristics of the problem and choose the algorithm accordingly. However, hybrid version of those algorithms may outperform over the non-hybrid version.
In my view, the choice of a metaheuristic for a combinatorial optimisation problem depends on two things: (i) whether you can think of a natural neighbourhood (or several neighborhoods) and (ii) whether you can think of a natural representation of feasible solutions as strings (or other more complicated data structures). If you can think of a natural neighbourhood, then you can just use a local-search based metaheuristic, such as simulated annealing or tabu search. If you can't think of a natural neighbourhood, but there is a natural string representation, then simple evolutionary metaheuristics, such as genetic algorithms, may work well. If you have both (a natural neighborhood and a natural string representation), then you can use a hyrbid metaheuristic, such as a memetic algorithm (which combines both local search and genetic algorithms in a single scheme).
I would also consider exact methods, such as branch-and-cut and branch-and-price. They can perform surprisingly well for some problems.
- Badges
- Science topic