Since the early 90’s, metaheuristic algorithms have been continually improved in order to solve a wider class of optimization problems. To do so, different techniques such as hybridized algorithms have been introduced in the literature. I would be appreciate if someone can help me to find some of the most important techniques used in these algorithms.
- Hybridization
- Orthogonal learning
- Algorithms with dynamic population
Dear Hojjat Rakhshani
Parameters tuning also play big role in improving performance of metaheuristic algorithms significantly. Also, varying population size may boost the performance of metaheuristics.
Hi,
A very good book on evolutionary computing: Computational intelligence : an introduction by Andries P. Engelbrecht. In each chapter, one evolutionary approach is described and the relevant extensions/heuristics are discussed.
(Take a look at p30download!)
Hi,
Concerning the hybridization of metaheuristics, I would advise you to read the following papers:
-C. Blum and A. Roli. Hybrid metaheuristics : An introduction. Studies in
Computational Intelligence (SCI), page 1–30, 2008.
-C. Cotta, E.-G.Talbi, and E. Alba. Parallel hybrid metaheuristics. In Parallel
Metaheuristics : A New Class of Algorithms. John Wiley & Sons, 2005.
-E.-G Talbi. A taxonomy of hybrid metaheuristics. Journal of Heuristics,
8 :541–564, 2002.
They summarize fairly well the latest advances in that field of study.
I hope this helped,
Kind regards,
Imène.
Dear Hojjat Rakhshani
Parameters tuning also play big role in improving performance of metaheuristic algorithms significantly. Also, varying population size may boost the performance of metaheuristics.
I agree with Dr. Alam. Proper parameter tuning is the key boost the performance of the meta heuristic algorithm. It is also important to know the nature of the problem and the characteristics of the fitness function. With bit of experience,one should be able to do that. There are also some generic guidelines for parameter tuning.
Dear Hojjat Rakhshani
For the concrete case of evolutionary algorithms an important role plays the initial population's of solutions quality and the interval of variation of the studied problem variables.Best wishes,
Dr. Jose Arzola
Dear Hojjat,
let me list the following strategies:
- hybridization with local search techniques aiming to inprove the exploitation phase.
- Using constructive heuristics or despatching methods to generate part of the initial population
- Arranging a good calibration of the control paramters on the basis of a proper statistical analysis
- In case of constrained issues, founding the best trade-off between penalty functions or repairing strategies, conforming to the kind of problem to be optimized.
I hope it is useful..
Good luck!
Antonio
Thank you so much for your responses. I found some promising techniques that have been successfully used to improve performance of the conventional algorithms. If there are more effective techniques please post them here.
Metaheuristics with:
- social learning structures
- self-adaptive parameters
- orthogonal learning
- quantum based strategy
- heterogeneous topology
- rank based strategy
- fuzzy adaptive parameters
- information sharing mechanism
- superior guided strategy
- opposite learning strategy
- hierarchical topology
- chaos enhanced strategy
- elitism based strategy
- comprehensive learning
- dynamic neighborhood
- multi population strategy
- island population model
- migration based strategy
I would advise you to read the following paper and books:
- Ş. Gülcü, H. Kodaz, A novel parallel multi-swarm algorithm based on comprehensive learning particle swarm optimization, Engineering Applications of Artificial Intelligence, 45 (2015) 33-45.
- El-Ghazali Talbi, Metaheuristics: From Design to Implementation, John Wiley & Sons, 2009.
- Alba, Enrique,Parallel Metaheuristics : A New Class of Algorithms, John Wiley&Sons, 2005
I hope it is useful..
Good luck!
What does "conventional" mean? If all of the above, then here is an unconventional (?) one:
https://www.researchgate.net/publication/270516923_Problem_dependent_optimization_PDO
It does not need adjusting of parameters (although there is a couple of parameters one can play with, if tempted). For those who are going to look into it and try to run an implementation, I have three minor technical remarks/improvements regarding the heuristic that virtually eliminate the possibility of worsening the performance even in very long runs:
1) Keep the most recent value of f(c(B)) as a real number, and so remove the ceilings in formula (1), but take the nearest integer larger than or equal to f(c(B)) for the run before the next update of the (real) value of f(c(B)).
2) Another suggestion (also based on some very long searches) is to use a default value 3 or slightly higher for the parameter m.
3) The formula (1) can be rewritten in a slightly more computationally friendly way (avoiding multiplication of large numbers) by adding and subtracting jdc(c(B)) in the numerator.
Each of these three items could have some feasible effect only in very long runs.
IB
Article Problem dependent optimization (PDO)
I would advise you to use the models applied by Rechenberg and Eiben to "learn" your parameters. However, nowadays generative hyper-heuristics could also be an option. New meta-heuristics or heuristics could be generated and may solve more effectively your problem. I would recommend you to read Pappa et al 2014 on this subject.
Dear Patricia Ryser-Welch,
Thank you so much for your helpful response. The adaptive models applied by Rechenberg and Eiben are of great importance. In the case of hyper-heuristics; however, the process of selecting, combining, generating or adapting several simpler heuristics is very time consuming.
Article Generic Parameter Control for Evolutionary Algorithms
In evolutionary algorithms, the search for global optimum starts from the randomly generated initial population. As a result, initializing the algorithm with a better initial population will results in faster convergence and in global optimal solution.
A metaheuristic explore the search space smart enough to find great solutions, but it's not a exact algorithm. To improve the performance of your algo, maybe you can use some exact algorithms to restrict your search space. For example, in Genetic Algorithms you can use the Dijkstra's algorithm to generate the initial population. Therefore, you'll explore a restrict space of your large search space, improving the performance of your algorithm. On the other hand, you probably will deal with premature convergence or another problem of your metaheuristic, and you must find some way to scape of this problem.
I am always sceptical using time for efficiency. There is so many parameters outside that can change the time. For example, the CPU, the type of computer system (cluster, or PC), others services running in the background, disk activities. The list is not exhaustive.
Hybridisation has offered good solutions in NP-hard problems (TSP, Routing problems, timetables, scheduling problems). With the slow advance of generative hyper-heuristics, perhaps, it is way forward in this area of reserarch. Let the computer generate some hybrids and identify the best combination of operators.
Perhaps you might consider search reversion as well.
Silva Fennica. (2015) 49(2): article id 1232
Fuzzy logic control can be used to dynamically adapt parameters of optimization algorithm.Yo can refer to following article on improving the performance of Differential evolution using the above procedure:
Castillo, O., Ochoa, P., & Soria, J. (2016). Differential Evolution with Fuzzy Logic for Dynamic Adaptation of Parameters in Mathematical Function Optimization. In Imprecision and Uncertainty in Information Representation and Processing (pp. 361-374). Springer International Publishing.
http://link.springer.com/chapter/10.1007/978-3-319-26302-1_21
Please find our recent work on simulating the optimization algorithm's behavior using the deep learning models:
Preprint From feature selection to continuous optimization
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms