最適化アルゴリズム研究室

松浦 隆文 助教

Laboratory

研究室紹介

最適化アルゴリズムの開発とその工学的応用

私たちの身の回りには「最適化」が必要な問題が数多く存在します。例えば、小学校の遠足を思い出してください。お菓子代は500円までという条件(制約)のもとで、悩みに悩んで最も満足するお菓子を購入しリュックサックに詰めたと思います。これはナップサック問題とは呼ばれる代表的な最適化問題です。 最適化問題を解くために、脳・神経系をモデル化したニューラルネットワーク、生物の群れにおける行動や振る舞いモデル化した群知能、生物の進化をモデル化した進化的アルゴリズムといったメタヒューリスティックなアルゴリズムが提案されています。松浦研究室では、世界一のメタヒューリスティックなアルゴリズムの開発を目的とした研究を行なっています。

主な研究紹介

遺伝子解析に用いるアルゴリズムの研究

バイオインフォマティクスの分野において、DNA塩基配列やアミノ酸配列から生命にとって重要な情報が記述されている部分を見つけるためにモチーフ抽出が行われます。もともと様々な生物は、共通の祖先から進化し、DNAは進化過程において、置換・欠損・挿入などの変異を生じてきました。しかし、生命にとって重要な機能をもつ部分は生物種をこえて保存されてきたことがわかっています。この共通した部分配列をモチーフと呼びます。複数のアミノ酸配列に共通する部分配列を見つけることは、タンパク質の機能を推測する上で非常に役立ちます。松浦研究室では、複数の遺伝子配列からモチーフを見つける問題(共通モチーフ抽出問題(Motif Extraction Problem)、マルチプルアライメント問題(Multiple Sequence Alignment Problem))を解決するために、ニューラルネットワーク用いたChaotic Motif Sampler法を提案しています。

巡回を伴う組合せ最適化問題に対するアルゴリズムの研究

「朝、会社を出発して複数の営業先を訪問し、再び会社に戻って報告書を作成する」、「配送車に複数の宅配物を積んで集荷場を出発し、全ての配達先を訪問し荷物を届け、再び集荷場に戻ってくる」など、現実社会には多くの巡回活動が存在します。巡回活動では、巡回距離が長くなるとガソリン代が高くなってしまう、複数の配達場所を効率良く訪問しないと顧客の指定した時間帯に荷物を届けることができないといった問題が発生します。このような問題を解決するために「巡回セールスマン問題(Traveling Salesman Problem)」、「配送計画問題(Vehicle Routing Problem)」と呼ばれる組合せ最適化問題が提起されています。松浦研究室では、巡回を伴う組合せ最適化問題に対し、新たな局所探索法、新しいメタヒューリスティック解法の開発を行なっています。

バイクシェアリングシステムにおける効率的な巡回経路決定問題

現実問題を解決するために多くの組合せ最適化問題が提起されています。しかし、これまでに提起されている組合せ問題では取り扱うことができない、実問題も存在します。松浦研究室では、解決が望まれる問題を新たに発見し、その解決方法を構築する研究を行なっています。その一つとの取組みとして、バイクシェアリングシステム(コミュニティサイクル)における自転車回収車の効率的な巡回経路決定問題があります。Bike Sharing System(BSS)とは、街中に複数の駐輪場を設置し、借りた駐輪所とは異なる駐輪所に自転車を返却できるレンタルサイクルの仕組みです。BSS では、自転車が一方向ばかりに利用されると、各駐輪所の自転車台数に偏りが生じます。この問題を解決するために、自転車回収車が街中を巡回し、自転車が超過している駐輪場では自転車を回収し、自転車が不足している回収車には自転車を補充する巡回活動を行っています。 松浦研究室では、この自転車回収の効率的な巡回経路を求める問題を組合せ最適化問題として提起し、その解決方法の研究を行なっています。