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

松浦 隆文 准教授

教員紹介 紹介動画

「三人よれば文殊の知恵」と言われるように、人の「結びつき」が新たな可能性を生み出すことはよく知られています。また、近年社会的にも注目されている技術であるディープラーニングでは、コンピュータ上の仮想的な神経細胞の「結びつき」を調整することにより高度な情報処理機能を実現しています。本研究室では、様々な「結びつき」に着目し、高度な機能を実現するための「結びつき」の設計や調整の方法論を研究しています

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

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

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

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

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