Next: Up: Previous:

ビンパッキング問題

Kröger, Schwenderling, Vornberger [22] は, ビンパッキング問題 (Bin Packing Problem) に特殊化した並列GAを考案し, 128プロセッサのハシゴ型 Transputer ネットワークで実行した. ビンパッキング問題は図5.8 のように長方形 tex2html_wrap_inline2233 をできるだけ隙間なくの B に詰める問題である. ビンの配置をグラフとして表し, これを個体として交配, 突然変異を定義した.


図5.8 二次元ビンパッキング問題



25〜65個の長方形を詰める10種類の問題について, 各種の並列GAモデルと逐次的な決定 的アルゴリズムの性能を比較した. 使用した並列GAモデルは

の3種類である. 決定的アルゴリズムは Bottom-Left 戦略と Level-Oriented 戦略の2種類を使用した.

3種類の並列GAの中では移出モデルが最も好成績を上げた. 拡散モデルは移入モデルよ りもやや良いが, 両方とも多様性をすぐに失なってしまう傾向にある. ただし, 拡散モ デルに関してはアルゴリズムに改善の余地がある.

プロセッサ数の増加に伴う性能向上度合の比較では, 移入モデルと拡散モデルではそれ ほど台数効果が現れなかった. 中には成績が落ちる場合もあった. 一方, 移出モデルは プロセッサ数の増加に従って, 良い解が安定的に得られるようになり, 少数のプロセッ サでは得られなかったようなより良い解が得られるという, 顕著な効果があった.

また, 決定的アルゴリズムはシンプルで並列GAより数十倍速いが, 移出モデルの方が確 実に良い解を発見している.



Mitsubishi Research Institute,Inc.
Mon Feb 24 19:32:36 JST 1997