組合せ最適化問題に対する部品構造を用いた最適化手法

カテゴリ: 部門大会

論文No: OS5-3

グループ名: 【C】平成19年電気学会電子・情報・システム部門大会講演論文集

発行日: 2007/09/04

タイトル(英語): A Parts-Concept Based Optimization Method for Combinatorial Optimization Problems

著者名: 前田 恵美(首都大学東京),安田 恵一郎(首都大学東京)

著者名(英語): megumi maeda(Tokyo Metropolitan University),keiichiro yasuda(Tokyo Metropolitan University)

キーワード: 組合せ最適化問題|部品構造|近接最適性の原理近接最適性の原理|Combinatorial Optimization Problems|A Parts-Concept|Proximate Optimality Principle

要約(日本語): 本研究では工学における多くの組合せ問題を対象とした汎用的な最適化手法を構築することを目的とする。多くの組合せ最適化問題に成立するだろうといわれている近接最適性の原理（Proximate Optimality Principle ：以下POP）は『よい解どうしは何らかの類似構造を持っている』という曖昧とした原理である。ベンチマーク問題においてPOPが成立することを数値実験的に検証し、POPに立脚した解の偏りを利用したアルゴリズムを構築する。そこで、解どうしの類似構造を定量的に判断するために、解を部品構造として捉えることを提案する。その上で、探索の経過で得られるよい解がもつ部品の情報を探索方向にフィードバックすることで、効率的な探索を目指したアルゴリズムを構築する。

PDFファイルサイズ: 3,919 Kバイト