A Q-Learning Hyperheuristic Binarization Framework to Balance Exploration and Exploitation
Many Metaheuristics solve optimization problems in the continuous domain, so it is necessary to apply binarization schemes to solve binary problems, this selection that is not trivial since it impacts the heart of the search strategy: its ability to explo
- PDF / 639,954 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 99 Downloads / 182 Views
Many Metaheuristics solve optimization problems in the continuous domain, so it is necessary to apply binarization schemes to solve binary problems, this selection that is not trivial since it impacts the heart of the search strategy: its ability to explore. This paper proposes a Hyperheuristic Binarization Framework based on a Machine Learning technique of Reinforcement Learning to select the appropriate binarization strategy, which is applied in a Low Level Metaheuristic. The proposed implementation is composed of a High Level Metaheuristic, Ant Colony Optimization, using Q-Learning replacing the pheromone trace component. In the Low Level Metaheuristic, we use a Grey Wolf Optimizer to solve the binary problem with binarization scheme fixed by ants. This framework allowing a better balance between exploration and exploitation, and can be applied selecting others low level components. Keywords: Hyperheuristics · Binarization framework · Reinforcement learning · Metaheuristics · Combinatorial optimization
1
Introduction
The optimization problems are diverse in the industry, in general they can be considered as a maximization or minimization of an objective function, subject to constrains. In the field of combinatorial optimization, the solutions are coded in variables that take discrete values, this means that the solution to the problem can be an integer, a subset, a permutation or a graph [3], and those have no polynomial solution time, also know as NP-Hard [4]. Given the complexity of solving NP-Hard c Springer Nature Switzerland AG 2020 H. Florez and S. Misra (Eds.): ICAI 2020, CCIS 1277, pp. 14–28, 2020. https://doi.org/10.1007/978-3-030-61702-8_2
Hyperheuristic Binarization Framework
15
problems with exact methods, it is that approximate methods are used, sacrificing the guarantee of finding the optimal one, for good solutions [3]. This research proposes a framework, which supported through a Machine Learning (ML) technique, allows to properly decide a binarization scheme in the context of a problem that requires a binary solution. This paper proposes a Hyperheuristic Binarization Framework based on a Machine Learning technique of Reinforcement Learning, particularly Q-Learning, to select the appropriate binarization strategy, which is applied in a Low Level Metaheuristic, in this case Grey Wolf Optimizer, solving a Optimization Combinatorial Problem. This section exposes the general concepts around Metaheuristics, Hyperheuristics and the area of ML. Later, in Sect. 3 the Hyperheuristic Framework supported by Q-Learning is defined, and then in the Sect. 4 propose an implementation using Ant Colony Optimization and Grey Wolf Optimizer, solving the Set Covering Problem. Finally, in Sect. 6 conclusions are made with respect to the improvement potentials when using an automated decision framework, by virtue of improving the search for solutions.
2 2.1
Background Metaheuristics and Hyperheuristics
In the approximate methods, there are heuristic algorithms, procedures to find solutions that do not guarantee th
Data Loading...
