解空間の確率モデルに基づいた大規模問題に対する組合せ最適化手法

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2017/08/01

タイトル(英語): A Combinatorial Optimization Method for Large Scale Problems Based on a Probabilistic Model of Solution Space

著者名: 重弘　裕二（大阪工業大学工学部），増田　達也（大阪工業大学工学部）

著者名(英語): Yuji Shigehiro (Faculty of Engineering, Osaka Institute of Technology), Tatsuya Masuda (Faculty of Engineering, Osaka Institute of Technology)

キーワード: 組合せ最適化，近傍探索法，確率モデル，近傍操作　　combinatorial optimization，neighborhood search，probabilistic model，neighborhood operation

要約(英語): In this paper we consider, from the point of view of probability theory, an effective search method for large scale combinatorial optimization problems. The fundamental ideas on which our method is based are the following: 1) Many different neighborhood operations, which consist of the iterations of unit neighborhood operations, are applied to solutions. 2) The probability distribution of the objective function values of the neighborhood solutions is estimated, from the data obtained in the search process. 3) The neighborhood operation, which maximizes the expected value of the amount of the improvement of the current solution, is selected to be applied. From these ideas and the fundamentals of probability theory, a new method for searching for solutions is derived. We have applied the local search method, the genetic algorithm, and the proposed method to traveling salseman problems and maximum satisfiability problems. The effectiveness of the proposed method is shown by the computational experiments.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.137 No.8 （2017） 特集：システム技術によるエネルギーの効率活用

本誌掲載ページ: 1090-1101 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/137/8/137_1090/_article/-char/ja/