遺伝的アルゴリズムを用いた格子状グラフにおける方向付けの最適化

スポンサーリンク

概要

論文の詳細を見る
格子状に節点が配置された有向グラフにおける方向付けの最適化問題とは、有向グラフにおいて、すべての節点間が最小距離で結ばれるような枝の方向付けを行う問題である。この問題は、グラフが大きくなるにつれて解空間が指数的に大きくなる典型的なNP困難な問題と考えられる。評価の基準は違うものの、この問題に対する理論的研究は、既にRobertsらによって最適化の手法が提案されている。しかし、この問題において、実際に各々の格子グラフにおける最適化を目指した論文は少ない。そこで我々は数ある最適化の手法の中から、遺伝的アルゴリズムを選び適用を試みた。本研究では、この問題をGAに適用する際に必要となる、格子グラフにおける諸性質の基礎的調査を行った。そして、この調査によって得られた結果を考察し、この問題に対するGAの適用方法を提案する。
社団法人電子情報通信学会の論文
1993-06-24

著者

関連論文

もっと見る

スポンサーリンク