Paper Info
Title
A Metaheuristic Relying On Random Walk On A Graph For Binary Optimization Problems
Abstract
Recently, evolutionary algorithms that can solve decomposable binary problems very efficiently have been developed. They are so-called model-based evolutionary algorithms, which build a model for generating solution candidates by a machine learning technique using a population. Their central procedure is linkage detection that reveals a problem structure, that is, how the entire problem consists of sub-problems. However, the model based evolutionary algorithms have been shown to be ineffective against problems that are hard to identify their structures. Therefore, metaheuristics including evolutionary algorithms that can solve both problems quickly, reliably, and accurately are required. In this paper, toward realizing such algorithms, we propose a new model-based metaheuristic. It initially forms a graph in which a pair of a position and a value on the string of a solution candidate is a vertex and directed edges are randomly made between vertexes, and then repeats the following three steps: (1) conducting random walk on the graph, (2) producing solution candidates, and (3) reconstructing the topology of the graph. The simulation results show that the proposed metaheuristic is inferior to conventional algorithms against decomposable problems, but superior to conventional ones against problems that are hard to identify their structures.
Year
DOI
Venue
2018
10.1109/SMC.2018.00134
2018 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS (SMC)
Field
DocType
ISSN
Population,Graph,Vertex (geometry),Evolutionary algorithm,Computer science,Random walk,Theoretical computer science,Binary optimization,Artificial intelligence,Machine learning,Metaheuristic,Binary number
Conference
1062-922X
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Takuya Sato100.34
Kei Ohnishi23917.71