卒業論文紹介の巻

2001 年度卒業論文

一対比較グラフの頂点の順位づけ問題

A problem of ranking the vertices of a paired comparison digaph

いくつかの対象の順位を定めるとき，全体の中で対象の優劣の 程度を数値的に得ることは困難であるが，二つの対象間について 優劣の判定を行なうことは比較的容易である．ここで，各対象を頂点で表し， 一対比較の結果を頂点間の重み付き有向枝で表現すれば， 対象に順位を付ける問題は一対比較グラフの頂点の順位づけ問題として扱うことが出来る． 本研究ではこのような一対比較グラフの最適な頂点の順位づけについて考察する．

［ 亀本　 学 ］

最大利得部分木問題に対する遺伝的アプローチ

A Genetic Approach for Maximum Profitable Subtree Problem

限られた予算内でできるだけ多くの端末を繋ぐ通信ネットワークの構築や大小様々な 島に橋を掛ける場合など，あるコスト以内で最大の利得を得るための最適化問題が 最大利得部分木問題である． 本研究ではこの問題に対して遺伝的アルゴリズムを用い， 分枝限定法と比較して実行時間を，ヒューリスティックアルゴリズムと比較して 解の精度を，それぞれ検証する．

［ 栃木　隆道 ］

2000 年度卒業論文

遺伝的アルゴリズムを用いたチャネル割り当て問題の解法

A Genetic Approach for Channel Assignment Problem

携帯電話の基地局に対するチャネル割当問題を組合せ最適化問題と して定式化し，GA を用いた解法を提案する．さらにすでに提案さ れている，チャネル割当問題を線形計画問題に帰着した厳密解法と 比較し，その性能を評価する．

［ 有賀　洋介 ］

遺伝的アルゴリズムを用いた複数経路探索法

Exploration Method of Various Routes with Genetic Algorithm

最短経路問題とは，カーナビゲーションシステムなどで利用される， 目的地までの最短経路を発見する問題である．本研究で対象とする カーナビゲーションシステムでは，その性質上，最短経路を発見す るだけでなく二番目，三番目に短い経路を発見しなければならない． さらに，各経路は酷似していない必要がある．本研究ではこれらを ただ一度の実行で発見するアルゴリズムを提案する．

［ 井上　祐介 ］

遺伝的プログラミングを用いた時系列処理

Time Series Management with Genetic Programming

時系列予測問題は古くから研究され，実用価値も高い．そのため 応用範囲も色々と考えられ，株価，貯水量，商品の売上の予測な どに実用化されている．本研究では，時系列処理における GMDH （Group Method of Data Handling）の例外値を含むデータに対 して処理する方法を示し，遺伝的プログラミングを組み合わせた 解法について考察を行う．

［ 神谷　将司 ］

遺伝的アルゴリズムを用いた電子部品挿入順序問題

Insertion Ordering of Electronic Parts on Printed Circuit Boards Using Genetic Algorithm

電子部品挿入機における部品挿入順序を決定する問題において，2 つ の適応度関数を用いた GA による解法を提案する．過去に提案された ヒューリスティックな閉路探索法と GA を組み合わせた解法では， その探索時間に難点があった．本研究ではあらたなコーディング手法 を採用し，探索時間の短縮を図りつつより良い部品挿入順序を得る ためのアルゴリズムと，両手法の性能比較を報告する．

［ 登　伸一 ］

知識獲得を用いたデータベース圧縮における遺伝的アルゴリズムについて

On Genetic Algorithms for Database Compression Using KDD

データベース圧縮のため，ルールを適用する最適な順序を決定する 問題．ルールの組合せを GA の染色体で表現し解く手法を提案する． また，得られた最良解の圧縮率と処理時間を示す．

［ 山崎　聖太郎 ］

遺伝的アルゴリズムによる施設配置問題に対する解法

A Genetic Algorithm for the Metric Uncapacitated Facility Location Problem

容量無し施設配置問題に対する GA を用いた解法を提案する．施設 配置問題とは，ある地域内において，あるサービスを行なう施設を どのように配置したら全利用者にとって最も効率よく利用できるか という問題である．容量無し施設配置問題では，施設が供給する サービスに制限がない．本研究では，以前に報告されている貪欲法， 3 近似アルゴリズムと GA を用いた解法を比較・検討する．

［ 横谷　雅樹 ］