第3回   メタヒューリスティックスと並列／分散処理

本特定領域研究ではその重要な課題の一つとして
計算困難問題を合理的な時間で解決することを掲げており,
その具体的な戦略としてメタヒューリスティックと並列／分散処理が
別個に検討されて来た.
しかしながら, この二つの戦略はもちろん排他的なものではなく,
むしろ協調によってさらに強力な戦略を得ることができる可能性
すら否定できない.
そこで, 両戦略の研究者に並列／分散型メタヒューリスティック
の可能性を議論する場を提供することを目的として,
平成12年6月23日(金)13:00--17:20,
九州大学システム情報科学府講義棟第2講義室において
第3回テーマ別研究会「メタヒューリスティックと並列／分散処理」
が開催されたのでその報告を行なう.

参加人数は30名程度で,
部屋が小さかったこともあるが,
立見が出る程の盛況であった.
本特定領域研究関係者以外からも多数の参加があり,
このテーマへの関心の深さを感じさせた.

講演プログラムとその概要を議事録（朝廣雄一作成）から
抜粋して紹介する.


13:00-13:40:
FPGAを用いた探索アルゴリズムの高速化
(和田幸一○, 伊藤暁一, 中野浩嗣（名工大）)

FPGA を用いたSATアルゴリズムの紹介．
汎用プログラムに対して数倍から数100倍，
専用プログラムに対しても数倍程度の高速化に成功して
いるという実験結果が報告された．
これに対し，並列化の粒度や、効率良くとける問題サイズ，
また，ハードウェアで実現可能な，
データ構造表現やアルゴリズムの動作についての質問がなされた．

13:40-14:20:
一般化割り当て問題に対する排除連鎖法の分散化

(朝廣雄一○, 伊東孝紘, 石橋正裕, 山下雅史（九大）)

局所探索法に基づく排除連鎖法の PVM を用いた分散化についての報告.
数台のWSを用いた分散化の実験結果が示された．
並列化の方針，実験結果に対する質問がなされた．

14:20-15:00:
HTTP＋PVM を用いた SAT 局所探索のグローバルコンピューティング

(菊岡雅仁, 宮崎修一, 岡部寿男○, 岩間一雄（京大）)

SATの局所探索法のPVMを用いた並列化について.
広域分散環境下での実行を想定した 
HTTP と CGIを利用したシステムが提案された．
提案システムの仕様や，対象とする問題サイズ，
ならびにアルゴリズムデータベー スとの関係について質問がなされた．

15:20-16:00:
広域並列計算システム Ninf と最適化ソフトウェア

(藤沢克樹（京大）)

グローバルコンピューティングシステム NINF の紹介と，
NINF上で動くSDPA 問題を解く並列プログラムについての解説があり，
実験結果が報告された．
対象とするネットワークの構造，実験結果，ならびに SDP 
の反復利用手法についての質問がなされた．

16:00-16:40:
分散化メタヒューリスティクスの勘どころ

(茨木俊秀（京大）)

メタヒューリスティックスの種々のテクニックが紹介され，
メタヒューリスティックスと分散化の方針について解説があった．
局所探索法における，局所解からの脱出のための再出発点の選択法，
分散化した際の各プロセス間の通信の頻度ならびに重要度についての質問があった．

16:40-17:20:
雑談会 -- 失敗は成功の母（だったらいいな） 
--- こうして私は並列／分散化に失敗した

ソフトウェア開発における乱数の利用法についての質問が，
京都大の岡部 よりなされ，  
   
・UNIX の乱数生成器ではダメ
    
・Mersenne Twister乱数を使っている
    
・気にしていない
    
・物理現象のばらつきから乱数を生成する手法もあり，
PC-UNIX ならカーネルに組み込むことが可能

・擬ランダム生成器ではだめで，真にランダムなものが必要な計算もある

・モンテカルロ法や積分などに使う乱数がよい．

という意見が聞かれた．
また乱数に関しては，
 
・組み合わせ問題を解く際に必要なランダム性というのは，完全にランダ
ムなものが必要なのではなく，ランダムの種を一様にばらまけるように
なればよいのでは? 

・乱数だと思っていても，解こうとしている問題に対しては，ある意味
全くランダムでないかもしれないので，問題の構造をとらえて，何がラ
ンダムであるかの意味を考えないといけない．

・ランダムではなく，解空間を分割することにより，例えば格子点の位置
のものを選び局所探索の開始点として用いるのは，どうか?

・プロセッサ 8台で，x1, x2, x3 に 000 から 111を割り当てて，残り
の変数の部分に対して局所探索を行うという方針は全然だめ．

・逆に，局所探索法で，乱数が有効に働いている意味が分からない。

・数値の一様性が必要であり，そういう意味での良いランダム生成器が必
要だが、局所探索くらいでは不必要かもしれない．

という意見も聞かれた．

<最終更新作成日時 2000年9月27日 >