Structured Approach for Local Clustering Organization [an abstract

Title
Author(s)
Structured Approach for Local Clustering Organization [an
abstract of dissertation and a summary of dissertation review]
今野, 陽子
Citation
Issue Date
2015-03-25
DOI
Doc URL
http://hdl.handle.net/2115/58695
Right
Type
theses (doctoral - abstract and summary of review)
Additional
Information
There are other files related to this item in HUSCAP. Check the
above URL.
File
Information
Yohko_Konno_review.pdf (審査の要旨)
Instructions for use
Hokkaido University Collection of Scholarly and Academic Papers : HUSCAP
学位論文審査の要旨
博士の専攻分野の名称 博士 (情報科学) 氏名 今野 陽子
審査担当者 主 査 教 授 鈴木 恵二
副 査 教 授 栗原 正仁
副 査 教 授 小野 哲雄
副 査 教 授 山本 雅人
副 査 准教授 川村 秀憲
学位論文題名
Structured Approach for Local Clustering Organization
（局所クラスタリング組織化法の構造化アプローチ）
ヒューリスティック (発見的解法) は組み合わせ最適化問題に対して実用的な時間で高精度な解
を探索することを目的として適用される. ヒューリスティックを総合したメタヒューリスティッ
クの解法設計の一般的な指針として, 探索の多様化 (Diversification) と集中化 (Intensification) の
設計技術が要求される. 探索の多様化は, 解の構造を崩して未探索領域に探索を進める操作であ
り, 探索の集中化は似た構造を持つ解を集中的に探索する操作である. 本学位論文はヒューリス
ティックのひとつ, 局所クラスタリング組織化法 (Local clustering organization: LCO) に着目した
ものである.LCO は, 自己組織化マップ (Self-Organization map: SOM) による巡回セールスマン問
題 (Traveling salesman problem: TSP) の解法原理をベースに大規模 TSP 向けの解法として開発さ
れ, 他のメタヒューリスティックとのハイブリッドによる組み合わせ最適化の研究が行われている.
しかし現状では LCO のオペレーションである局所クラスタリングを用いて探索の多様化と集中化
をどのように図るべきか, 探索能力向上に向けた体系的議論がなされていない.
以上の背景のもと, 本学位論文は LCO の設計方法の構築を目的に次のように構成されている.
第 1 章では,LCO の基本的なアルゴリズム, メタヒューリスティックの分類上の LCO の位置づ
け,LCO の利点と課題について説明している.
第 2 章では,LCO の局所クラスタリングオペレーションを定義し, 既存手法のオペレーションの
位置づけを分析して, 探索の多様化と集中化に対する設計方法としての拡張局所クラスタリングオ
ペレーション (拡張 LCO) と構造化局所クラスタリングオペレーション (構造化 LCO) について提
案を行っている. 具体的には SOM の学習原理に基づいて局所クラスタリングオペレーションの定
義を行い, オペレーションのパターンを形式化するとともに, 既存のオペレーションと λ-opt との対
応づけによりその不備を指摘し, 拡張として 3-opt タイプの挿入法 (Insert method: IM) を提案し, こ
の IM を付与した手法を拡張 LCO と位置付けている. またノード単位のオペレーションのみなら
ず, ノードの部分集合 (ノードセット) を含めたオペレーションによるパターンを提案し, 局所クラ
スタリングオペレーションの設計範囲を広げられることを示すとともに, ノードセットのオペレー
ションを取り入れた手法を構造化 LCO として提案している.
第 3 章では, 組み合わせ最適化問題である TSP を題材として,(a) 拡張 LCO の有効性を示すとと
もに,(b) 構造化 LCO として提案したノードセットを用いたオペレーションの基本的性能評価とし
て, 二重円環 TSP 群の最適接続問題を取り上げ, ノードセットに基づくオペレーションの有効性を
確認している.(c) また, 一般的な TSP を解くにあたり, 探索過程に現れる局所的に固定化できる部
分ツアーをノードセットとして抽出し, 他の部分をブリッジと位置づけ, 構造化オペレーションによ
り, ブリッジ部分に探索の集中化を図る構造化 LCO の適用方法の提案を行いその有効性を示して
いる.
第 4 章では, ジョブショップ・スケジューリング問題 (Job-shop scheduling problem: JSP) を取り
上げ,LCO の解表現であるジョブ番号の多重型の順序列の解釈において, リソース毎に各ジョブの
最適順序を探索していることを現象的性質の分析からも明らかにし, (a) ジョブの移動による拡張局
所クラスタリングの有効性, および (b) 解構造をリソース分割の表現型に拡張して同じリソースに
探索の近傍を固定する探索の集中化についての提案を行い, その検証結果を示している.
第 5 章では, 本学位論文の結論を述べるとともに, 今後の課題を示している.
これを要するに, 著者はヒューリスティック探索手法である LCO で用いられるオペレーション
の設計, 分析に関する方法論を示し, その具体化として探索の集中化と多様化に着目した構造化局所
クラスタリングオペレーションを提案しその有効性について有益な知見を得たものであり, 最適化
技術および複雑系工学の進歩に寄与するに大なるものがある. よって著者は, 北海道大学博士 (情報
科学) の学位を授与される資格があるものと認める.