Some metaheuristics prove their superior performance in some kind of problems. Some of them are continuous optimization problems and others in discrete or binary optimization problems.
When dealing with problems where a candidate solution is a string of bits, a classical genetic algorithm (GA) should work reasonably well :-)
It depends on the structure of the constraints, the size of the solution space and also your aim (optimize 5 minutes for medium good solutions or 6 hours for really getting one of the best). If you have a good concept of "neighbouring solution" (i.e. by swapping two binary variables), have a look at Tabu Search or Simulated Annealing. In the second case, setting high temperature explores more of the solution space, setting low temperature lets you quickly find sensible solutions.
If you really want to explore large parts of the search space and time is not such a large issue, have a look at genetic algorithms. A prerequisite for that is the existence of a proper "crossing procedure", i.e. it must be possible to take some well-defined part of a solution and plug it into another one.
Most of the other metaheurstics are close cousins of the ones described above (except for Ant Colony Optimization, which I have not tried yet), although they might have very different description or naming.
#J. Fabian Meier ,#Alberto i understood that :
- The evolutionnary algorithm and specially the GA are more apropriate for binary discret problems.
But my question is :
- Is the fact that GA is more appropriate for binary problem by it's naturally discrete representation of the individual .is this fact make that the swarm based metaheuristic less appropriate for binary optimization problem than the GA?
It's a good question. Note that my answer was "GA should work well", not "GA should work better than PSO". There are many parameters to fix, such as population size, probability of mutation/crossover, etc., and the same holds for other algorithms.
Even the algorithm that is theoretically "better suited" for a problem might perform poorly, if we choose the parameters unwisely. To be honest, I don't know enough about all other techniques to give you a full comparison :-)
Maybe you should give more information about the kind of problem you want to tackle, especially if there are a lot of constraints that are difficult to fufil simultaniously (e.g. timetabling) or if it is easy to construct feasible solutions (and neighbours) and the cost function is more involved (e.g. vehicle routing).
Metaheuristics are by definition problem-dependent. There is no answer to your question until you narrow down the kind of problem structure you are facing. You might end up in well known problem or which specialized heuristics are known, or you must design one on your own.
Most of the heuristics, despite their exotic names, can be somehow traced back to the Variable Neighbour Search of Hansen and Mladenovic. Many of them are just equivalent, a mere renaming and slight modification of the parameter choice/update.
If I were you, I first would work on the problem definition/structure. Then define my aims, as correctly pointed out by Fabian. Only at that point I would start search the enormous literature you can find online.
#Andrea Cassioli ,#J. Fabian Meier,#Alberto Tonda :
- My problem is a tipically binary decision problem (0 or 1) .......
i mostly use Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) for this..
@Dahi: hmmm, I am not sure I understood correctly. Your genome is a string of bits (so, every gene can assume the value of 0/1), right? How long is the string? And, after evaluation, your fitness function is a single floating point number?
Dear Dahi,
The essence of any heuristic is to begin with an initial solution and try improve it. Good heuristics combine elements of diversification (exploration of search space) and intensification (explotation of promissing regions of search space).
If you design a constructive algorithm to generate an initial (and feasible) solution and if you design a good local search for improve this solution, you will be in the right way.
I agree with Alberto about Genetic Algorithms. For historical reasons, we know that a binary optimization problem is an invitation for a GA. It is easy to implement and the schema theorem provides a theretical background for the achievement of good building blocks.
However, the nature of the problem logically affects the design of your algorithm. If your problem has hard constraints, a classical GA will be weak. You will need of a inteligent strategy (not simply random) for generate an initial population and you will need of efficient operators of crossover and mutation. Such type of GA usually iscalled Hybrid GA.
Independently of the metaheuristic, I advise everyone to avoid unfeasible solutions.
True GA is appropriate. However you shall be faced with the problem of constraint violation of newky generated candidate solutions. Look at the paper dealing with task scheduling of Atidrl Hadj-Alouane and Katta Murty. In general look at the work of hadj-Alouane and Bean dealing with GA and generating random keys. Good luck.
I think that metaheuristics are not problem-dependent. On the contrary, they can be applied to various problems by changing the subordinate heuristic.
The performance of metaheuristics for solving a discrete optimization problem varies in each problem. As an example, for VRP (vehicle routing problem) Tabu Search may perform better than GA but in UFLP (uncapacitated facility location problem) GA may perform better. Also, different variations of metaheuristics sometimes perform totally different in one problem. As an instance, using different crossover strategies in GA can completely change the results.
In total, although it is not possible to accept a metaheuristic as the absolute best one in a domain, it is not advised to use the ones that are structurally designed for continuous problems in binary problems. Two examples of metaheuristics which are designed for continuous problems include particle swarm optimization and harmony search.
I am quite sure metaheuristics do not apply/are useful for general zero-one/combinatorial problems. I don't see how one can design a metaheuristic for problems, where it is (NP-)hard just to find a single solution. How does one design a metaheuristic for the set partitioning problem, for instance? Hardness may also be hidden in sub-constraints in practical problems, so it is not just for very structured problems, where hardness is an issue for finding just a single solution. In fact, I believe set partitioning constraints are also often part of a practical problem.
#Edson LF Senne#Kent Høj Andersen#Ehsan Ardjmand
Thank you so much for your answers.
- In conclusion i understand that the hardness of optimisation problems makes that there is no metaheuristic apropriate for a given problem.
But :
- Ehsan Ardjmand :
you said : it is not advised to use the ones that are structurally designed for continuous problems in binary problems.
But in the literature there is many adaptation of swarm based metaheuristic for binary problems , in fact they 've showed high performances against other non-swarm based metaheuristic .
The most powerfull approach to create an efficient meta-heuristic for 0-1 optimization problem is to formulate your problem in terms of pseudo-Boolean functions (see for details the publications by E. Boros, P.L. Hammer and more recent by Goldengorin et al.
Any metaheuristic optimization algorithm can be tuned for solving binary type of variables.
Even GA which is available in MATLAB may be good as no need to do coding.
https://www.researchgate.net/publication/297245624_Particle_Swarm_Optimization_Algorithm_and_its_Codes_in_MATLAB
Research Particle Swarm Optimization: Algorithm and its Codes in MATLAB
https://www.researchgate.net/publication/296636431_Codes_in_MATLAB_for_Particle_Swarm_Optimization
Code Codes in MATLAB for Particle Swarm Optimization
Since it is difficult to predice which algorithm is appropiate to a certain problema I suggest to try with the most popular metaheuristic methods first
Ant colony(ACO), Genetic Algorithm(GA), ICA , SA, Tabu, PSO, and some of continuos change to descrite is GWO and more for TSP.
Simply look at this research:
N. K. T. El-Omari, "Sea Lion Optimization Algorithm for Solving the Maximum Flow Problem", International Journal of Computer Science and Network Security (IJCSNS), e-ISSN: 1738-7906, DOI: 10.22937/IJCSNS.2020.20.08.5, 20(8):30-68, 2020.
It has a complete discussion about your question.
Or refer to the same paper at the following address:
https://www.researchgate.net/publication/344324283_Sea_Lion_Optimization_Algorithm_for_Solving_the_Maximum_Flow_Problem
- Badges
- Science topic