Heuristic Algorithms: A Neighbor Generation Mechanism for Single Solution Based Algorithms
Tarih ve Saat
13 Mayıs 2019 - 16:00
The world of optimization is vast and improving. In ancient China, government officials needed to solve the puzzle of how to store rice for upcoming winter and in the modern world, people need to solve the puzzle of how to store data. However, most of the real-life problems are too complex to solve by using exact solution methods.
Heuristic methods to solve optimization problems as an alternative way to deal with computationally hard problems were introduced in mid-1990s and gained world-wide popularity. Since then, they have evolved and got more sophisticated. Even though these methods cannot guarantee optimality, they are effective in finding approximate solutions within relatively short computer time.
No-free launch theorem suggests that there is not a “best-suited” metaheuristic algorithm that can solve all optimization problems. An algorithm may show satisfactory results on a set of problems or even on some problem instances. However, it can produce poor results for other problems, or different instances of the same problem.
There are many state-of the heuristic algorithms. The ones that are designed for specific problems are called problem specific heuristics and the ones that have a wider solution range are called metaheuristics. Metaheuristics can be classified considering their different characteristics. One of the main classifications includes single solution-based or population-based heuristics. As the names suggest, single solution-based metaheuristics manipulate a single solution, while population-based metaheuristics transform a set of solutions throughout the search. In single solution-based algorithms; encoding scheme, how to generate an initial solution, neighbor generation mechanism, stopping condition are the most common concepts.
This presentation will contain the basic knowledge on the on single solution based heuristic algorithms. It will also describe a novel neighbor generation mechanism called cantor-set based neighbor generation mechanism (CB Method).
Biography: Melike ÖZTÜRK has graduated from Sakarya University, Department of Industrial Engineering in 2011 and received her MSc. from the same department in 2013. She worked as a manufacturing engineer and a manufacturing manager between 2013-2015. She started her Ph.D. at Marmara University in 2015. She began working as a research assistant at Doğuş University in 2016. She studies heuristic algorithms and optimization.