ベイズ推定と指数移動平均を用いた組合せ最適化手法

カテゴリ: 研究会(論文単位)

論文No: ST22040

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

発行日: 2022/11/23

タイトル(英語): A Combinatorial Optimization Method using Bayesian Estimation and Exponential Moving Average

著者名: 角田 英一郎(大阪工業大学),重弘 裕二(大阪工業大学)

著者名(英語): Eiichiro Kakuda (Osaka Institute of Technology),Yuji Shigehiro(Osaka Institute of Technology)

キーワード: 組合せ最適化|近傍探索|ベイズ推定|指数移動平均|combinatorial optimization|neighborhood search|Bayesian estimation|exponential moving average

要約(日本語): 著者らはこれまでに、複数の近傍操作を使い分けながら効率良く解の探索を行う手法について考察を行っている。具体的には、近傍操作により得られる解の評価値の統計量を推定することで適切な近傍操作を選択するというものである。そのため、近傍解の統計量を「解改善確率」と「改善時の改善量の期待値」と名づけた2つの統計量で表し、それぞれをベイズ推定と指数移動平均により推定する。

要約(英語): This paper discusses a new method for the combinatorial　optimization problem. The method searches for better solutions in the solution space by means of multiple neighborhood operations. In the search process, the best neighborhood operation is selected on the basis of two statistics: ``the probability of solution improvement'' and ``the quantity of solution improvement''. These statistics are estimated by the Bayesian estimation algorithm and exponential moving average.We have applied the proposed　method to the traveling salesman problem. The experimental results are shown to demonstrate the effectiveness of the proposed method.

本誌: 2022年11月26日システム研究会

本誌掲載ページ: 15-20 p

原稿種別: 日本語

PDFファイルサイズ: 775 Kバイト