Optimization by metaheuristic methods: Spy algorithm and B-VNS

メタヒューリスティック手法による最適化： SpyアルゴリズムとB-VNS

Optimization by metaheuristic methods: Spy algorithm and B-VNS

Degree Grantors Yamaguchi University

The role of optimization can be found in almost all aspects of human life. Optimization is common in but not limited to the fields of engineering, economics, design, and planning. Although the optimization problems to be solved change, the optimization goal never changes. That is to find effective solutions efficiently. In modern optimization studies, the metaheuristic algorithm has been one of the most interesting methods, considering the demands of a reasonable computational time.
Many metaheuristic algorithms have been introduced. However, based on the number of tentative solutions used in the search process, metaheuristic algorithms can be categorized into (1) population-based or (2) single-trajectory-based algorithms. The searching with singletrajectory-based metaheuristic algorithms manipulates and modifies a single solution point in every iteration. In contrast, the population-based metaheuristic algorithms combine a set of solution points to create new solutions in every iteration.
A metaheuristic algorithm usually consists of two components, i.e., exploration and exploitation. Exploration means searching for solutions in the global space. In contrast, exploitation means searching for a solution by focusing on a small area or an area near an already known solution. The single-trajectory-based metaheuristic algorithm is exploitation-oriented. On the other side, the population-based metaheuristic algorithm is exploration-oriented because of searching by many points distributed on all search spaces. Balance settings between exploration and exploitation are needed to produce good solutions. In fact, most population-based algorithms will encounter decreasing in exploration and become too exploitation-oriented as the iteration increase. Any metaheuristic algorithm applies parameters to control the behavior. However, the parameters usually do not provide a good intuition of the rate of exploration and exploitation. Hence, reaching a balance between them is hard to predict just by the algorithm parameters.
This dissertation proposes a conceptual design combining the spy algorithm and B-VNS. The spy algorithm is a population-based metaheuristic algorithm that mimics the strategy of a group of spies, the spy ring. The spy algorithm is a new concept with the main idea to ensure the benefit of exploration and exploitation, and cooperative and non-cooperative searches always exist. This goal is implemented by utilizing three kinds of dedicated search operators and regulating them in a fixed portion. The occurrences of exploration and exploitation are controlled by algorithm parameters. Thus, the spy algorithm parameters provide good before-running intuition to easier reach the balance between exploration and exploitation. The spy algorithm is first designed to be used in the continuous optimization model.
The spy algorithm was compared to the genetic algorithm, improved harmony search, and particle swarm optimization on a set of non-convex functions by aiming at accuracy, the ability to detect many global optimum points, and computation time. The Kruskal-Wallis tests, followed by Games—Howell post hoc comparison tests, were conducted using a. for the comparison. The statistical analysis results show that the spy algorithm outperformed the other algorithms by providing the best accuracy and detecting more global optimum points within less computation time. Furthermore, those results indicate that the spy algorithm is more robust and faster than other algorithms tested.
On the other hand, the B-VNS algorithm is a modification of the variable neighborhood search (VNS) algorithm. The benefit of VNS comes from its thorough search while avoiding the local optimum trap by moving to the neighboring point called shaking. The local search after shaking is another benefit of VNS that makes VNS a prominent algorithm. However, the thorough search has the drawback of long computation time. This dissertation introduces a modified neighborhood structure to reduce the computation times. The main idea is to apply the binomial distribution to create the neighboring point. As a result, the neighborhood distance has a random pattern. However, it follows a binomial distribution instead of a strictly monotonic increase like in VNS. The B-VNS is a modification of VNS and is classified as a single solution-based algorithm. The B-VNS is intended to solve combinatorial optimization problems, particularly the quadratic unconstrained binary optimization (QUBO) problems categorized as NP-hard problems.
The B-VNS and VNS algorithms were tested on standard QUBO problems from Glover and Beasley, on standard max-cut problems from Helmberg-Rendl, and those proposed by Burer, Monteiro, and Zhang. Finally, Mann-Whitney tests were conducted using a. to compare the performance of the two algorithms statistically. It was shown that the B-VNS and VNS algorithms are able to provide good solutions, but the B-VNS algorithm runs substantially faster. Furthermore, the B-VNS algorithm performed better in all of the max-cut problems regardless of problem size and in QUBO problems with sizes less than
The spy algorithms and B-VNS have different designs in the process and the domain of the solved problems. However, considering the benefit of the spy algorithm and B-VNS, their combination has the potential to provide good results. Conceptually, the spy algorithm can be seen as the first step of B-VNS. Conversely, B-VNS can be considered an additional refinement for the spy algorithm.

Creators Pambudi Dhidhi