HOME > 研究活動・産学官連携 > ネットジャーナル > ネットジャーナル6

ネットジャーナル6

10万~100万規模の組み合わせを計算する
世界最速レベルのハイパースケール最適化

――学習機能や人工生命というとSFに出てくるようなロボットをイメージしますが、自律系工学は私たちの身近なところで使われている技術なのですね。

古川 正志教授

古川 3つ目のプロジェクトである「ハイパースケール最適化問題」などは、まさにそうです。最適化とは、ある条件の中で最も適したものをコンピュータを使って見つけることです。たとえば、10カ所の都市を最短経路で回るルートを探すようなものです。10カ所を結ぶルートの組み合わせ総数は30万通りあり、そのすべてを比較して最も効率のよいルートを見つけます。15年ほど前から研究を始め、GAを使って最適化する「GAスケジューラ」に基づく産学応用開発を行ってきました。物流システムの効率化に非常に役立つことから、メーカーの配送センターや運送業界などで実用化されています。今までは人間が自分の経験則からスケジューリングしていたものを、コンピュータが最適化理論に基づいて計算できるようになったのです。しかし、GAを使った最適化では限界があることも分かってきました。工場の仕事の大規模スケジュールや暗号作成など、10万~100万規模の組み合わせ最適化には対応しきれないのです。そこで、GAと自己組織化学習を組み合わせ,それらををさらに進化させたアルゴリズム「局所クラスタリング組織化法(LCO/Local Clustering Organization)」を開発しました(解説2/図3)。これにより計算時間が大幅に短縮されます。3万都市を回る巡回セールスマンを想定した最適化の例題があるのですが、他の方法に比べて飛躍的に早く、しかも高い精度で最適化できることが検証されています。LCOは物流のみならず多様な分野に適用できる汎用的な解法なので、今後さらに研究を重ね、より実用的なシステムとして拡張させていきたいと考えています。

(2008/04/18)

ページの先頭へ