アナログ λ-optアルゴリズムを使った2次割当て問題の解法

新妻　弘崇  石井　信  伊藤　実  

誌名
電子情報通信学会論文誌 D   Vol.J82-D2   No.12   pp.2375-2384
発行日: 1999/12/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1923
論文種別: 論文
専門分野: バイオサイバネティックス，ニューロコンピューティング
キーワード: 
非線形最適化,  2重制約ネットワーク,  2次割当て問題,  λ-opt,  

本文: PDF(350.9KB)
>>論文を購入

あらまし: 
本研究では， ニューラルネットワークに基づく新しい組合せ最適化問題の解法を提案する． 特に2次割当て問題に対して適用する． 本手法は， 順列の λ 個の要素を同時に入れ替える λ-optヒューリスティックスの アナログ版とみなすことができる． λ の値として中程度の値を使うことができるため， 中距離サーチを実現できる． この中距離サーチは，浅い局所最適解を乗り越えることができる． 比較的大きな (N=80 ～ 150) 2次割当て問題に対してこの手法の計算機実験を行った結果， 我々の新しい手法は今までのチャンピオンのアルゴリズムと 同程度に良い近似解を計算できることがわかった． また，二つのベンチマークについては， 現在のチャンピオンのアルゴリズムよりも良い解が計算できることがわかった．