Members Only :

Grid

Grid班では最適化問題を高速・高精度に解くことを目的として、新たなアルゴリズムや高速化手法の研究開発を行っています。

今までに知られている最適化手法の多くは数値最適化を対象としたものですが、Grid班ではより計算が困難なグラフ問題などを解くための最新のアルゴリズムを改良・応用する手法について研究しています。本研究室では、新たな近似解法の改良および考案、並列処理による高速化手法、現実世界での応用を考慮した問題への適用、そして深層学習を用いた新たな解法などが主なテーマとなっています。

最適化問題

最適化問題の中にはNP困難という分類があり、これらの問題では実用的な時間で最適解を計算することが困難となっています。そこで、Grid班では最適解になるべく近い解を高速に見つける近似解法(ヒューリスティクス)の研究開発を行っています。
  • Traveling Salesman Problem (TSP)

    TSPは巡回セールスマン問題とも呼ばれ、与えられたすべての頂点を1度だけ通るような経路のうち、総距離が最も短いものを求めるという問題です。荷物の配送計画問題などの応用例が考えられています。頂点数が増えるにつれて最適解を求めることが非常に困難になるという性質を持ち、組合せ最適化問題の代表例として知られています。


  • Integer Programming (IP)

    IPは整数計画法とも呼ばれ、与えられた条件式を満たすような整数の組を求める問題です。IPはLinear Programming (LP)と同様に目的関数と制約条件が線形不等式・等式によって定義されますが、LPでは解空間が連続であるのに対して、IPは離散空間として与えられます。これにより、LPでは多項式時間で解くことができるアルゴリズムが存在するのに対して、IPでは見つかっていません。

  • etc...

研究例

  • ハイブリッドアルゴリズム

    複数のアルゴリズム同士を組み合わせることで、互いの短所を長所で打ち消し合うという手法です。
    例えば「良い解を見つけることができるが、膨大な計算時間がかかる」アルゴリズムと「ある程度良い解を短時間で見つける」アルゴリズムがあったとき、後者の手法で「ある程度良い解」を高速に求め、この解を前者の手法に与えることで「良い解」を見つける、といった方法で計算時間と解の品質を両立することができます。


  • 超並列アルゴリズム

    複数のタスクを一つのコア(CPU)で計算するのではなく、複数のコアでタスクを分配して処理することで計算を高速化することができます。しかし、メニーコアなど大量のコアを持つ環境では、効率よくコアにタスクを分配することが難しくなります。そこで、待機状態のコアがなるべく発生しないような手法など、コア数を増やしても効率が落ちにくい並列アルゴリズムの開発を行っています。


  • 深層学習を用いた解法

    近年、囲碁などのゲームAIやデータマイニング、画像処理など、さまざまな分野において深層学習を用いた技術が研究されています。大量の学習データを用いてデータの特徴量を抽出し、人間のように複雑な判断能力を獲得できるということが深層学習の大きな特徴です。これらの深層学習の能力を組合せ最適化問題に適応することで、高精度で高速なアルゴリズムの構築を目指しています。

  • etc...

研究環境

  • Intel Core-i CPUシリーズ+デスクトップ付きLinux(Ubuntu、Fedora、CentOS、etc...)

    最新のプロセッサファミリ搭載PCをデスクトップ環境として利用します。グラフィカルな統合開発環境(IDE)をパワフルなPC上で動作させることで開発効率を向上させます。


  • マルチディスプレイ

    ライブラリリファレンスなどの資料を見ながら開発を進めたり、その他の雑務を効率よく進めるために一台のPCで複数のディスプレイを利用することが可能です。


  • 統合開発環境(IDE)+言語

    研究においてはプログラムやアプリケーションを作成するために様々なプログラミング言語を使用しており、その開発の際には統合開発環境(IDE)を利用します。例えば、C++ならQt Creator、JavaならEclipse、RならR Studio、PythonならPyCharmなどを利用しています。もちろん、使用するIDEや言語は自由で、IDEの使用も任意です。


  • コプロセッサ

    超並列アルゴリズムを支えるインフラストラクチャとして、Grid班ではXeon Phiを利用します。200を超えるスレッド、200-300GB/sクラスのメモリ帯域幅、1TFLOPSクラスの高い並列演算性能を利用することができます。

ートップに戻りますー


    Study


当研究室では、スタッフが3つのグループに別れて研究を行っています。

Grid

Network

Web