最適化の観点から見たGAの確率的操作に関する基礎検討

カテゴリ: 部門大会

論文No: GS15-6

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

発行日: 2002/09/02

タイトル(英語): A Basic Study of Operations in Genetic Algorithms from the View Point of Optimization

著者名: 永岡 右明(東京都立大学),金澤 貴彦(東京都立大学),安田 恵一郎(東京都立大学)

著者名(英語): Takaaki Nagaoka(Metropolitan University),Takahiko Kanazawa(Metropolitan University),Keiichiro Yasuda(Metropolitan University)

キーワード: 最適化|メタヒューリスティクス確定論的最適化手法|確定論的最適化手法|Optimization|Meta Heuristics|Genetic Algorithm|Deterministic Optimization Method

要約(日本語): 組み合わせ最適化問題における効果的な探索手法の一つとして，生物の進化のメカニズムにヒントを得た遺伝的アルゴリズム(Genetic Algorithm:GA)がある。

生物の進化を模擬するという観点からは確率的なオペレータは必要不可欠であることから，これにヒントを得たGAの探索も確率的オペレータにより構成されている。

しかしながら最適化手法として捉えた場合，Tabu Searchに代表される確定論的な手法の有効性が示されているように，GAの確率論的オペレータの必要性については検討の余地がある。

本研究では以上の観点に基づき，確率論的なオペレータにより構成される確定論的なGAを提案する。

提案手法と従来のGAをナップサック問題に適用し，探索性能を比較検討することによ り，GAのもつ確率的なオペレータの意義について検証した。

PDFファイルサイズ: 1,760 Kバイト