Dr. Natalio Krasgonor from University of Nottingham, School of Computer Series and Information Technology has given a talk at Ashurst Lodge on “Modern Metaheuristics in a Nutshell“.
His group uses an assortment of techniques to solve complex problems that arise from a variety of industrial and scientific domains. They are actively engaged in the advancement of their current software platform, in the investigation of new and promising metaheuristic paradigms and its transfer to industry. Some of the methods used more routinely are: Tabu Search, Simulated Annealing, Evolutionary Algorithms and Swarm Optimization Algorithms. There is however, a vibrant research programme on other modern optimization methods such as Variable Neighborhood Search, GRASP, Multi-Start Local Search, Neural Networks, Linear, Integer Programming and Dynamic Programming, Hyperheuristics and Case-Base reasoning.
During his presentation he discussed:
- Computational Challenges in the Automated Design and Optimization of Complex systems
- Heuristics; what, how and when?
- Metaheuristics
- Evolutionary Algorithms
- Memetic Algorithms
- Applications and Cases Studies
Major advances in the national design of large and complex systems have been achieved and more recently the automated design and optimization of those systems by modern AI and Optimization tools has been introduced.
As the number of applications and their complexity increases one needs to rely even more on automated design and optimization based on AI. Automated design and optimization is not only good because it can solve large problems but also because the approach gives access to different regions of the space of possible designs.
The research challenge is to develop adequate sophisticated algorithms to automatically design the model regardless of the adverse results that may be obtained by standards algorithms.
That is where heuristics comes in. They are rules of thumb of how to solve problems but many problems cannot be attacked by simple heuristics.
Metaheuristics refers to a Master Strategy that guides and modifies other heuristics problems. It is a way of finding the global optimum in many cases instead of reaching only a local optimum. A way of finding it is to use simulated “annealing“techniques which introduce the possibility of moving the local solution.
Recent advances in memetic algorithms and Evolutionary Computations apply Darwin’s principle of natural selection in an artificial system. The problem is then solved using survival and reproduction concepts. A simulation of evolution consists of considering a population of diverse individuals. Variations are then introduced in the population by means of a mutation combination and local searches. Selection culls the population that gives bad solutions.
The challenge is to build algorithms that are robust across the set of problems and which are cheap, good and rapid, i.e. that can be applied in practise.
Adding domain specific knowledge to the genetic algorithms can be achieved by using memetic methods. They result from applying optimization algorithms to the population before using the evolutionary algorithm. Their approach is a hybrid method which essentially improves the solution. A “correlation of competence” principle applies, i.e. the better the algorithm is at solving any specific instance (class) of problems; the worst it is at solving a different instance (class).
Hence one cannot expect the presence of a “black box“metaheuristic that will solve all problem classes. The solution built “algorithms templates” for specific cases. The important condition is to which problem to apply which methods.
Memetic algorithms can be used for a wide range of problems in practise, from building proteins chains to using optimal engine calibrations in cars.
There are other metaheuristics algorithms such as a taboo search, genetic programming, -- swarm algorithms, etc, some of them are better than others for a given problem.
Natalio drew the following conclusions:
- Today problems complexity is going faster than CPU speeds.
- Many problems are intrinsically –intractable yet requiring solving!
- Metaheuristics are the “best” methods available for “good enough/fast enough/ cheap enough” solutions.
- Evolutionary design explores a space of alternative solutions.
The best approach is to use a series of solutions and let them to interact in a synergetic way reaching the best solution by applying all of them and letting the algorithms choose.
Dr. Natalio Krasnogor is a Lecturer within the Automated Scheduling, Optimization and Planning Research group at the University of Nottingham. He has established and co-chaired the series of international Workshop on Memetic Algorithms (WOMA). He is the holder of a US patent for an Internet related technology. Dr Krasnogor has published more than 40 papers on Metaheuristics. He has served as reviewer for various international conferences and prestigious journals. He was a guest editor of a special issue of Evolutionary Computation (MIT Press) dedicated to Memetic Algorithms and a follow up in the IEEE Transactions on Systems Man and Cybernetics. He is co-editor of a book on this topic. He is editor of the International Journal of Computational Intelligence, the Journal of Evolutionary Computation and committee member of the Society for the Study of Artificial Intelligence and the Simulation of Behavior. He is also a principal investigator and co-investigator in more than 7 EPSRC research grants plus other various EU grants.
Wessex Institute