ビンパッキング問題

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

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

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

• 移入(immigration)モデル(=island GA)
• 移出(emigration) モデル(=island GA で移住個体を元のサブ集団に残さない)
• 拡散(diffusion)モデル(=cellular GA)

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

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

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

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