ABCL/f による実現

並列GAのプログラムは約1100行の中規模プログラムであるが, 並列化に要したのはコン ストラクタ, 世代実行, 移住のわずか3箇所である. 実質的にはサブ集団を並列オブジェ クトに割り付け, サブ集団のメソッドをfuture呼び出しで実行しているだけであ る. Island型並列GAは,そもそも並列化が容易であるという面もあるが, ABCL/f が並列 アルゴリズム記述性が優れていることを示している. 以下, 並列GAの ABCL/f に よる実装方法の中で並列化に関わる部分をソースコードで示す.

• a クラス定義
• b コンストラクタ
• c 世代実行
• d 移住

クラス定義

Island型の並列GAには, 個体, サブ集団, 集団全体の3つの has-a 階層が存在し, それ ぞれを ABCL/f 上の並列オブジェクトとして実装した. ソースコード上では以下のよ うに, has-a 関係を下位オブジェクトのリストのメンバとして記述した.

    ;;; 集団
    (defclass population ()
      (fixnum number)                       ;サブ集団数
      ((list subpopulation) member))        ;サブ集団

    ;;; サブ集団
    (defclass subpopulation ()
      (fixnum number)               ;個体数
      ((list individual) member))   ;個体集合

    ;;; 個体クラス
    (defclass individual ()
      ((vector real) x)        ; 変数ベクトルｘ
      ((vector real) objf)     ; 目的関数ベクトルｆ(ｘ)
      (real          rank)     ; ランク
      (real       sharing))    ; シェアリング関数

下位クラスから見てゆくと, 個体クラス(individual)には変数ベクトル , 目的関数ベクトル , ランク, シェアリング関数の4つのメンバを持つ. サブ集団 クラス(subpopulation)は個体をリストとして保持している. さらに集団クラス (population)はサブ集団をリストとして保持する. 集団クラスはプログラム実行 中はただ一つのインスタンスを持つ.

コンストラクタ

初期サブ集団は, 集団クラスのコンストラクタ中で次のようなnow呼び出しで各 プロセッサに均等な数だけ生成し, 集団クラスのサブ集団リストにまとめる. さらに各 サブ集団に初期個体生成のメッセージを送る.

    (dotimes (i n_popu)
      (let ((popu (now (make-empty-subpopulation) :on (mod i *npe*))))
        (init-subpopulation! popu size)
        (setq newmember (cons popu newmember))))

1プロセッサのみの場合にはnow呼び出しが必要ないので以下のようになる.

    (dotimes (i n_popu)
      (let ((popu (make-empty-subpopulation))
        (init-subpopulation! popu size)
        (setq newmember (cons popu newmember))))

世代実行

サブ集団クラスには, 指定世代数を他のサブ集団と独立に実行する関数 run-generations があり, この関数を future 呼び出しで,

    (let ((boxes '()))
      (declare ((list (future unit)) boxes))
      (dolist (popu member)
        (push (future (run-generations popu パラメータ)) boxes))
      (dolist (r boxes) (touch r)))

のように, 並列に起動する. boxes は reply-box のリストであり,すべての future 呼び出しが終ったら, 順に touch することで同期をとっている.

1プロセッサのみの場合には, 単純に各サブ集団のメソッドを順に呼び出すだけである.

    (dolist (popu member)
      (run-generations popu パラメータ))

移住

移住は, 各サブ集団popuがランダムに選んだサブ集団from-popuに対して1 個体を要求する処理migration-fromを future 呼び出しで並列に実行する.

    (let ((boxes '()))
      (declare ((list (future unit)) boxes))
      (dolist (popu member)
        (let ((from-popu (nth (random-int number) member)))
          (push (future (migration-from popu from-popu)) boxes)))
      (dolist (r boxes) (touch r)))

1プロセッサのみの場合には, 世代実行と同様にして以下のようになる.

    (dolist (popu member)
      (let ((from-popu (nth (random-int number) member)))
        (migration-from popu from-popu)))