Transactions of JSCES, Paper No.20040001
離散最適化のための大域的交叉メカニズムを持つ 分散遺伝的アルゴリズム ∗
Global Crossover based Distributed Genetic Algorithm for Discrete Optimization Problems
三木 光範1，廣安 知之1，勝崎 俊樹2，水田 伯典2
Mitsunori MIKI, Tomoyuki HIROYASU , Toshiki KATSUZAKI and Takanori MIZUTA
1同 志 社 大 学工 学 部
(〒610-0321
京 都 府 京 田辺 市 多々羅 都 谷1-3)
2同 志 社 大 学大 学 院
(〒610-0321
京 都 府 京 田辺 市 多々羅 都 谷1-3)
This paper proposes a new method of genetic algorithms (GAs) for discrete optimization problems. For discrete optimization problems, the performance of Distributed GAs (DGAs) are not so good. We propose a new method of increasing the performance of DGAs for discrete optimization problems. The features of the proposed method, Global Crossover based DGA (GCDGA), are multiple crossover operations applied to the elite individuals and DGA without migration. We apply GCDGA to job-shop scheduling problems (JSPs). The experiments on JSPs showed that GCDGA has a better performance than the conventional GAs, and GCDGA provides an efficient distributed scheme in GAs for discrete optimization problems.
Key Words
: Genetic Algorithms, Distributed Genetic Algorithms, Discrete Optimization Prob- lems, Job-shop Schedule Problems, Global Crossover
1.
はじめに遺伝的アルゴリズム（
Genetic Algorithms: GAs
）は生 物の遺伝と進化を模倣したアルゴリズムであり，ヒュー リ ス ティック 法 と ラ ン ダ ム 探 索 法 を 有 効 に 組 み 合 わ せ た 手 法 で あ る(1)．GA
は そ の 実 装 が 容 易 で あ る こ と か ら ，確 率 的 探 索 ，学 習 ，最 適 化 な ど 幅 広 い 分 野 で 応 用 さ れ て い る(2)〜(4)．し か し な が ら ，
GA
に お け る 解 探 索 は 膨 大 な 反 復 計 算 を 必 要 と す る た め ，計 算 コ ス ト が 非 常 に 高 く な る と い う 問 題 が あ る ．こ の 問 題 に 対 す る 解 決 法 の 一 つ と し て，GA
の並 列処理 があげら れる．その手法 の1
つに集 団 を 分 割 す る 島 モ デ ル の 分 散GA
（Distributed Genetic Algorithms: DGAs
）が あ る ．分 散GA
で は ，集 団 を 複 数 の サ ブ 集 団（ 島 ）に 分 割 し ，各 島 ご と に 独 立 に 遺 伝 的 操 作 を 行 い ，一 定 期 間 ご と に 異 な る サ ブ 集 団 間 で 個 体 情 報 を交 換 する 移住 と 呼ば れ る操 作を 行 う(5)．分 散GA
は粗 粒度 の並 列モ デル に分 類さ れ ，PC
ク ラ スタ と∗ 原 稿 受 付2003年9月12日,改 訂 年 月 日2003年12月18日, 発 行 年 月 日2004年1月29日. c2004年 日 本 計 算 工 学 会.
Manuscript received, September 12, 2003; final revision, De- cember 18, 2003; published, January 29, 2004. Copyright c2004 by the Japan Society for Computational Engineering and Science.
の 親 和 性 が 高 い(6)．
連 続 最 適 化 問 題 に お い て ，分 散
GA
は 単 一 集 団GA
（
Single Population Genetic Algorithms: SPGAs
）と比較 して高品質の解が得られると報告されている(7)．一方，離 散 最 適 化 問 題 に お い て は ，単 一 集 団
GA
を 用 い た 研 究 は 多 い が(8)〜(10)，分 散GA
を 用 い た 研 究 は 少 な く，そ の 性 能 は 明 ら か と なって い な い ．そ こ で ，本 研 究 で は 離 散最 適 化問 題の 中か らジョブ ショップ ス ケジュー リ ン グ 問 題（
Job-shop Scheduling Problem: JSP
）を 取 り 上 げ，分 散GA
の 性 能 を 検 証 し た ．そ の 結 果 ，連 続 最 適 化 問 題 と は 異 な り，離 散 最 適 化 問 題 に 対 し て は 分 散GA
の 性 能は 良好 では ない ことが わかった ．そ こで ，本 研 究 で は ，離 散 最 適 化 問 題 に 対 し て 有 効 な ，分 散GA
に お け る 新 た な サ ブ 集 団 間 で の 情 報 交 換 ス キ ー ム の 提 案 を 行 い ，提 案 手 法 の 性 能 検 証 お よ び 考 察 を 行 う．2.
ジョブショップスケジューリング問 題に対する分散GA
の性能ジョブショップスケジューリ ング問題（
JSP
）は，各仕 事 を 処 理 す る 機 械 の 順 序（ 技 術 的 順 序 ），お よ び ，各 機 械 上 で の 各 仕 事（ 作 業 ）が 処 理 時 間 は 与 え ら れ て い る 状 況 下 で ，す べ て の 仕 事 を 処 理 し 終 え る ま で の 総 所 要 時 間（Makespan
）を 最 小 に す る よ う な 作 業 の 順 序 をTable 1 Performance of TSSB for JSP
(11)Problem n m Opt.(LB UB) Best ft10
(14)10 10 930 930 orb1
(16)10 10 1059 1064 ta21
(17)20 20 (1539 1647) 1659 ta31
(17)30 15 (1764 1766) 1771 ta41
(17)30 20 (1859 2023) 2045
決 定 す る 問 題 で あ る ．
JSP
は 代 表 的 な 離 散 最 適 化 問 題 と し て 知 ら れ ，GA
以 外 の 最 適 化 手 法 に よ る 研 究 も 行 わ れ て い る ．TSSB
（A tabu search method guided by shifting bottleneck
）(11)の よ う に タ ブ ー サ ー チ な ど を 用 い た 解 探 索 を 行 う こ と で ，Table 1
に 示 す よ う に 大 規 模 な 問 題 に 対 し て も 良 好 な 結 果 が 得 ら れ る こ と が 分 かってい る ．こ こ でn
は 仕 事 数 を ，m
は 機 械 数 を 示 す．ま た ，
Best
は 最 良 解 で あ り，Opt.
に お け るLB
，UB
は 下 界 値 と 上 界 値 で あ る ．し か し ，本 研 究 の 目 的 は 並 列 処 理 に 適 し た 分 散GA
の 性 能 向 上 で あ る た め ，分 散GA
を 改 良 す る こ と でJSP
に 対 し て よ り 良 好 な 解 探 索 性 能 を 得 る こ と を 考 え る ．JSP
に 対 す る 分 散GA
の 性 能 を 検 証 す る た め ，単 一 集 団GA
と 分 散GA
の 数 値 実 験 に お け る 性 能 比 較 を 行 う．実 験 で は ，交 叉 法 にInter-Machine JOX
(8) *1 を ， 突 然 変 異 に はJob-Based Shift Change
(8) *2を 用 い ，ア ク ティブ ス ケ ジュー ル を 得 る た めGT
法 (12) *3に よ る 強 制 操 作(13)を 適 用 し た ．世 代 交 代 モ デ ル に はCCM
(9)*4を 適 用 し ，生 成 子個 体 数 は
20
と し た ．GA
の パ ラ メ ー タ は ，集 団 サ イ ズ800
，交 叉 率1.0
，突 然 変 異 率0.1
と し た ．分 散GA
に お ける 移住 パ ラメ ータ に つい ては ， 分 散GA
の 性 能 に 大 き く 影 響 を 与 え る た め ，移 住 率 を0.1, 0.2, 0.5
の3
通り，移住間隔を2, 5, 10, 20
世代の4
通 りを 用い，最良の結 果を示した ものを実験 結果とした．実験は，最適解を得るか，評価計算回数が
100
万回に達 し た 時 点 で 打 ち 切った ．対 象 問 題 をFisher
・Thompson
よ り 提 案 さ れ た10
仕 事10
機 械 のJSP
で あ るft10
問 題（最適解の
Makespan : 930
）(14)として実験を行い，100
回 試 行 し た 結 果 のMakespan
の 平 均 値（avg
）と 最 適 解 取 得 率（success
）をTable 2
に 示 す．表 中 のDGA
nと あ る の は ，分 散GA
に お け る サ ブ 集 団 数 がnで あ る こ と を 示 し ，I
の 列 は 最 良 の 結 果 を 得 た 試 行 の 移 住 間 隔 を ，R
の 列 は 移 住 率 を 示 し て い る ．*1全 機 械 で の 仕 事 に 基 づ く 順 序 の 継 承 を 考 慮 し た 交 叉 法
*2ラ ン ダ ム に1つ の 仕 事 を 選 び ，全 て の 機 械 上 で そ の 仕 事 を 左 ま た は 右 にShift Changeす る 突 然 変 異 の 方 法
*3Inter-Machine JOXに よって 得 ら れ る 子 個 体 を 確 実 に 実 行 可 能 状 態 に す る た め に 行 う 修 正 操 作
*4JSPの よう に 交 叉 を用 い て も 容易 に 良 好 な個 体 を 生 成す る こ と が 困 難 で あ る 問 題 に 有 効 と さ れ る 世 代 交 代 モ デ ル
Table 2 Performance of SPGA and DGA for JSP(ft10)
Method avg success I R
SPGA 930.69 0.87 - -
DGA 4 930.57 0.89 2 0.2 DGA 10 930.67 0.88 5 0.5 DGA 20 930.87 0.86 10 0.5 DGA 40 931.14 0.79 2 0.5 DGA 80 931.88 0.66 2 0.5
サ ブ 集 団 数 が
4
の も の を 除 い て は ，移 住 率0.5
の 試 行 が 最 良 の 結 果 を 示 し た ．ま た 移 住 間 隔 に つ い て も ， サ ブ 集 団 数4, 40
お よ び80
の も の に お い て2
世 代 が 最 良 の 結 果 を 得 て い る こ と か ら ，短 い 方 が 性 能 が 高 く な る 傾 向 に あ る ．こ の こ と か ら ，移 住 に よ る 情 報 交 換 を 頻 繁 に 行 え ば 分 散GA
を 用 い て 比 較 的 良 好 な 性 能 が 得 ら れ る こ と が わ か る ．し か し な が ら ，分 散
GA
の 性 能 は 単 一 集 団GA
の 性 能 と 比 較 し て大 き な 差 は なく，サ ブ 集 団 数20
以 上 の場 合 に は 単 一 集 団GA
よ り も 性 能 が 低 く なって い る ．こ の こ と は ，移 住 を 行 う こ と に よって 集 団 全 体 の 多 様 性 を 維 持 し ，探 索 を 効 果 的 に 行 う こ と が で き て も ，適 切 な 情 報 交 換 を 行 い 性 能 を 向 上 さ せ る こ と が 十 分 で き て い な い こ と を 示 し て い る と い え る ．連 続 最 適 化 問 題 の 場 合 に は サ ブ 集 団 数 を 多 く す る こ と で 性 能が 向上 す ると 報 告さ れ てい る(7)．こ れは 各 サ ブ 集 団 に お い て 成 長 す る 部 分 解（ ビ ル ディン グ ブ ロッ ク ）が 移 住 に よって 組 み 合 わ せ ら れ ，効 果 的 に 最 適 解 を 得 る こ と が で き た た め で あ る ．し か し ，
JSP
で は 移 住 が 効 果 的 に 機 能 し な かった ．こ の 点 が 離 散 最 適 化 問 題 と 連 続 最 適 化 問 題 の 相 違 で あ る と 考 え ら れ る ．3.
新たなサブ集団間情報交換スキーム3.1 分 散GAの 問 題 点 前 節 の 実 験 結 果 よ り，
離 散 最 適 化 問 題 に お け る 分 散
GA
の 問 題 点 は ，移 住 を 行って も 適 切 な 情 報 交 換 が な さ れ に く い 点 に あ る と 考 え ら れ る ．離 散 最 適 化 問 題 は 連 続 最 適 化 問 題 と は 異 な り，対 象 問 題 に 特 化 し た 染 色 体 の コ ー ディン グ 法 や 交 叉 法 を 用 い る こ と が 多 い た め ，部 分 解 が 他 の 個 体 に 受 け 継 が れ に く い ．ま た ，対 象 問 題 に よって は ，大 き な 部 分 解 が 存 在 し な い こ と も 考 え ら れ る ．移 住 に よ る 情 報 交 換 は 交 叉 を 実 行 す る こ と で 実 現 す る ．す な わ ち ，移 住 先 の サ ブ 集 団 内 で 移 住 個 体 が 交 叉 に 組 み 込 ま れ る こ と で ，そ の サ ブ 集 団 内 の 個 体 と の 情 報 交 換 が な さ れ る ．し か し ，移 住 に よ り サ ブ 集 団 間 で の 個 体 の 移 動 が 行 わ れ た 際 に ，あ る サ ブ 集 団 か ら 良 好 な 個 体 が 移 住 し た と し て も ，移 住 先 の サ ブ 集 団 で そ れ
が 有 効 利 用 さ れ る（ こ こ で は 適 切 な 交 叉 が 行 わ れ る こ と を 指 す ）保 証 は な い ．ま た ，解 探 索 速 度 が 低 下 す る 探 索 中 盤 以 降 に お い て は ，大 域 的 探 索 よ り も 局 所 的 探 索 が 必 要 と な る こ と が 多 い た め ，性 質 が 大 き く 異 な る よ う な 移 住 個 体 は 有 効 利 用 さ れ る こ と が 少 な く な る ． そ の た め ，各 サ ブ 集 団 に お け る 有 力 な 情 報 を 持った 個 体 が 他 の サ ブ 集 団 に 移 住 し て も ，そ の 個 体 に 近 い 性 質 の 個 体 と の 交 叉 が 行 わ れ な け れ ば ，よ り 良 い 個 体 が 生 成 さ れ る 可 能 性 は 低 い ．
こ れ ら の こ と か ら ，離 散 最 適 化 問 題 に お い て は 移 住 に よ る 情 報 交 換 だ け で は ，分 散
GA
の 性 能 が 十 分 に 引 き 出 さ れ ず，各 サ ブ 集 団 間 の 情 報 交 換 に お い て は ，適 切 な 交 叉 対 象 個 体 の ペ ア を 作 成 す る こ と が 重 要 で あ る と 考 え ら れ る ．探 索 時 間 を 十 分 に 長 く す れ ば ，適 切 な 交 叉 の ペ ア が 生 成 さ れ に く い と い う 問 題 は 解 決 さ れ る 可 能 性 が あ る ．し か し ，限 ら れ た 時 間 内 で 良 好 な 解 を 得 る た め に は ，適 切 な 交 叉 の ペ ア を 自 動 的 に 生 成 す る よ う な 操 作 が 不 可 欠 で あ る ．3.2 大 域 的 交 叉 型 分 散 遺 伝 的 ア ル ゴ リ ズ ム の 提 案 本 節 で は 前 節 で 示 し た 分 散
GA
に お け る 問 題 点 を 解 消 し ，適 切 な 交 叉 の ペ ア を 生 成 す る 新 た な 手 法 ，大 域 的 交 叉 型 分 散GA
（Global Crossover based Distributed Genetic Algorithm: GCDGA
）の 提 案 を 行 う．GCDGA
は ，各 サ ブ 集 団 に お け る 有 力 な 情 報 を 持 つ エリート個 体による情報交換を中心とした探索を行う．具 体 的 に は ，各 サ ブ 集 団 か ら エ リ ー ト 個 体 を 含 む 数 個 の 個 体 を 抽 出 し ，そ れ ら の 個 体 に よ る 交 叉 を 連 続 し て 行う．この操 作を，大域 的交叉（
Global Crossover: GC
） と 呼 ぶ ．GC
を 適 用 す る こ と で サ ブ 集 団 間 の 情 報 交 換 が 行 わ れ る た め ，GCDGA
で は 移 住 を 行 わ な い ．Fig.1
にGCDGA
の 操 作 を 示 す．GCDGA
で は 移 住 に 代 わってGC
を 行 う．す な わ ち ，GC
適用までは分散GA
と同じく各サブ集団内で独立し てGA
を 行 い ，GC
間 隔 ご と にGC
を 実 行 す る ．GC
は(1)GC
個 体 群 の 決 定 ，(2)
交 叉 対 象 個 体 の 選 択 ，(3)
交 叉 対 象 個 体 に よ る 多 段 交 叉 ，(4)GC
終 了 判 定 の4
つ の フェー ズ か ら な る ．GC
操 作 の 詳 細 を 次 節 で 説 明 す る ．GC
は移住に置き換えられる操作であり，移住のように 適 用 間 隔（
GC
間 隔 ）ご と に 実 行 さ れ る ．GC
間 隔 に 達 し た 時 点 で ，(1)
〜(4)
の4
つ の フェー ズ を 実 行 す る ．各 操 作 の 詳 細 を 以 下 で 説 明 す る ．
1.
GC個 体 群 の 決 定
GC
に お い て 交 叉 を 適 用 す る 個 体 候 補 で あ るGC
個 体 群 を ，各 サ ブ 集 団 か ら 選 択 す る ．GC
個 体 群 は ，各 サ ブ 集 団 か ら 半 数 の 個 体 を ラ ン ダ ム に 選 択 し た 個 体 か ら な る ．た だ し ，そ の 中 に は 必 ず 各 サ ブ 集 団 の エ リ ー ト 個 体 が 含 ま れ る も の と す る ．こ の 個 体 群 選 択 に よ り，GC
を 実 行 す る こ と に よ る 影 響 範 囲 は ，最 大 で も 各 サ ブ 集 団 内 の 半 数 の 個 体 と な る ．2.
交 叉 対 象 個体 の 選 択
GC
個 体 群 か ら 交 叉 対 象 と な る 個 体 を 選 択 すGC
Initialization START
No
Yes Evaluation
Terminate Criterion
Selection
Crossover Mutation
END
Yes
GC Interval No
Select GC Individuals
Select Crossover Individuals
Multiple times of Crossover
GC Finalize Yes
No
Fig.1 Flow of GCDGA
る．これは，次の多段交叉を行うための親個体候 補 の 選 択 で あ る ．交 叉 対 象 個 体 に は ，各 サ ブ 集 団 の
GC
個体 群 か ら2
個 体 ず つ 選 択 す る ．こ の2
個 体 の 中 に は 高 い 確 率 で サ ブ 集 団 内 の エ リ ー ト 個 体 が 選 択 さ れ る よ う に し ，多 段 交 叉 に よ る 情 報 交 換 の 効 率 を 高 め る ．3.
交 叉 対 象 個体 に よ る 多 段 交 叉こ こ で ，選 択 さ れ た 個 体 に 対 し て 交 叉 を 行 い ， 各 サ ブ 集 団 間 で 個 体 の 情 報 交 換 を す る ．こ の 交
叉において親個体として選択される
2
個体は，必ず 異 な る サ ブ 集 団 か ら の 個 体 と す る ．親 個 体 の ペ ア は ，全 て の 交 叉 対 象 個 体 を 用 い て 非 復 元 抽 出 に よ り 作 成 す る ．
親 個 体 の ペ ア を 決 定 し た ら ，そ れ ぞ れ の ペ ア に対して交叉をn回行い子個体を
2
n個生成する．つ ま り，全 体 で
2n
×(
ペ ア 数)
の 子 個 体 を 生 成 す る．次に親 個体と 子個 体での 生存選 択を行 う．生 存選択で は，交叉によって生成さ れた子個 体のう ち 最 良 のも の と 親 個 体 を系 列 ご と に 比較 を 行 い ， 最 良 の 個 体 を1
個 体 ず つ 選 択 し ，次 の 交 叉 対 象 個 体 と す る ．こ こ で い う 系 列 と は ，交 叉 に 用 いる 親 個 体
2
個 体 そ れ ぞ れ に お い て ，片 方 の 親 個 体 の 特 徴 を よ り 濃 く 受 け 継 ぐ 子 個 体 に そ の 親 個 体 自 身 を 加 え た も の で あ る ．この 交叉 終了後 ，得 ら れた子 個体 はす ぐに
GC
個 体 群 に 戻 さ ず に ，子 個 体 同 士 で 再 度 非 復 元 抽 出によりペアを作り，同様の交叉を指定回数連続 し て 行 う．こ の 連 続 し た 交 叉 を 多 段 交 叉 と 呼 ぶ ．4.
GC終 了 判 定多段交叉終了後，あらかじめ設定された
GC
の終 了 条 件 を 満 た し て い な い 場 合 に は ，交 叉 対 象 個 体 を 再 度 選 択 し ，多 段 交 叉 を 繰 り 返 す．
GC
の 終 了 条 件 を満 た し た ら ，GC
個 体 群 を 分 割 し ，サ ブ集団 に戻す．その後，再び 各サ ブ集団 での探 索 に 戻 る ．3.3 GCDGAの特徴
GCDGA
の 特徴 を ま とめ る と 次 の よ う に な る ．• 特 定 個 体 へ の 連 続 し た 複 数 回 の 交 叉
GCDGA
はGC
個 体 群 か ら 交 叉 対 象 個 体 を 選 択し，それらの個体を用いて交叉を連続して行う た め ，交 叉 対 象 個 体 の 高 速 な 進 化 が 期 待 で き る ．• エ リ ー ト 個 体 重 視
GC
個 体 群 に は 必 ず 各 サ ブ 集 団 の エ リ ー ト 個 体 が 含 ま れ ，交 叉 対 象 個 体 群 に エ リ ー ト 個 体 が 含 ま れ や す い た め ，エ リ ー ト 個 体 に よ る 探 索 が 重点的 に行わ れる．これによ り，各サブ 集団か ら の 有 力 な 個 体 情 報 が 交 換 さ れ ，多 段 交 叉 で の 効 果 的 な 探 索 が 期 待 で き る ．• 移 住 を 行 わ な い
GCDGA
は移住を 行わないため ，GC
中の交叉 対 象 個 体 以 外 は 各 サ ブ 集 団 に お い て 独 自 に 進 化 す る こ と に な る ．そ の た め ，探 索 の 終 盤 ま で 多 様 性 を 維持 す る こ と が 可能 に な る と 期待 で き る ．• 実 行 環 境 へ の 柔 軟 な 応 用 性
GCDGA
は 交 叉 法 やGA
の モ デ ル に 依 存 す る こ とな く適 用可能 であ る．基本 的に ，分 散GA
に 適 用 で き る も の で あ れ ば 採 用 で き る た め ，既 存 の 環 境 に 対 す る 応 用 が 容 易 で あ る ．一 方 ，
GCDGA
を 適 用 す る た め に は 次 の 点 を 考 慮 す る 必 要 が あ る と 考 え ら れ る ．•
GCDGA
独 自 の パ ラ メ ー タ 設 定 が 必 要
GCDGA
には独自のパラメータが存在する．これ ら の 設 定 が
GCDGA
の 性 能 に 大 き く 影 響 を 与 え る た め ，性 能 を 引 き 出 す た め に は 予 備 実 験 が 必 要 と な る ．• 交 叉 法 に 対 す る 依 存 性
GCDGA
に は ど の よ う な 交 叉 法 も 適 用 可 能 で あ る ．し か し ，移 住 を 行 わ ず に 交 叉 対 象 個 体 に よ る 交 叉 を 連 続 し て 行 う こ と で 情 報 交 換 を 行っ て い る た め ，親 の 形 質 を 大 き く 破 壊 す る よ う な交 叉 法 を 適 用 す る と ，情 報 交 換 が 適 切 に 行 わ れ な い た め
GC
が 有 効 に 機 能 し な い ．• サ ブ 集 団 数 の 設 定
GCDGA
は 各 サ ブ 集 団 か ら 個 体 を 集 め ，連 続 し て 交 叉 を 行 う こ と で 移 住 よ り も 高 い 効 果 を 得 よ う と す る 手 法 で あ る た め ，サ ブ 集 団 数 を 多 く し て 多 様 な 個 体 を 集 め な け れ ば 高 い 性 能 を 得 に く い ．こ れ ら の こ と か ら ，
GCDGA
を 適 用 す る 際 に は 用 い る 交 叉 法 と サ ブ 集 団 数 の 設 定 を 十 分 に 考 慮 し な け れ ば な ら な い と い え る ．な お ，最 適 な サ ブ 集 団 数 に つ い て は5.2
節 で 検 討 す る ．4.
提案手法の性能前 節 で 提 案 し た
GCDGA
の 性 能 を 単 一 集 団GA
お よ び 分 散GA
と 比 較 す る こ と で 検 証 す る ．こ の 際 ，問 題 と し て は 代 表 的 なJSP
と し て ，2
章 で 用 い たft10
問 題 ，Lawrence
よ り 提 案さ れたla19
問 題(15)，お よび ，Applegate
・Cook
より提案されたorb1
問題(16)を用いた．4.1 ft10問 題 に 対 す る 性 能 前 節 で 提 案 し た
GCDGA
の 性 能 を 単 一 集 団GA
お よ び 分 散GA
と 比 較 す る こ と で 検 証 す る ．数 値 実 験 で 用 い たGCDGA
の 設 定 は 次 の よ う で あ る ．GC
は10
世 代 目 か ら5
世 代 ご と に 適 用 し ，エ リ ー ト 個 体 選 択 率 は0.5
，GC
中 の 交 叉 で は 子 個 体 を1
回 あ た り20
個 生 成 ，多 段 交 叉 中 の 交叉 回 数 は2
回 と した ．ま た ，GC
の 終 了 はGC
中の 評 価 計算 回 数 が8
万 に 達 し た 時 点 と し た ．な お ，
GC
の 開 始 世 代 と 適 用 世 代 間 隔 は 分 散GA
の 移 住 同 様 ，問 題 依 存 が 大 き い と 考 え ら れ る た め 予 備 実 験 に よ り 決 定 し た ．ま た ，多 段 交 叉 に お け る 親 個 体 の 選 択 に つ い て は ，各 サ ブ 集 団 の エ リ ー ト 個 体 と 他 の 個 体 と の 交 叉 を 目 指 す た め ，エ リ ー ト 個 体 選 択 率 は0.5
と し た ．GC
中 の 交 叉 で の1
回 あ た り の 子 個 体 生 成 数 は ，ど の 程 度 子 個 体 を 生 め ば 良 好 な 解 を 得 ら れ る か を 考 察 し た 結 果 ，20
個 体 に 決 定 し た ．選 択 で き る 多 段 交 叉 中 の 交 叉 回 数 お よ びGC
中 の 評 価 計 算 回 数 は ，ど の 程 度 の 評 価 計 算 を 行 え ばGC
に よ る 十 分 な 情 報 交 換 が 行 え る の か に つ い て 検 討 し た 結 果 ，適 切 と 思 わ れ る 値 を 用 い た ．す な わ ち ，GC
に 関 係 す る 個 体 数 は こ の 場 合400
で あ り，200
ペ ア作 成 さ れる こ と にな る ．各 ペア が20
個 体 ず つの 子 個 体 を 生 成し ，そ の 交 叉を2
世代 分 実 施 し ，こ の 全 体 の プ ロ セ ス を 親 個 体 の ペ ア を 変 化 さ せ て10
回 繰 り 返 す．こ れ がGC
中 の 評 価 計 算 回 数 が8
万 回 で あ る 根 拠 と な る ．こ こ で 用 い た 値 は 予 備 実 験 で 得 ら れ た 値 で あ る が ，多 く の 対 象 問 題 に 対 し て 普 遍 性 の 高 い 値 で あ る と 考 え て い る ．な お ，
GCDGA
に お い て も 実 験 の 打 ち 切 り 評 価 計 算 回 数 は100
万 回 と し て い る た め ，単 一 集 団GA
お よ び 分 散GA
と 同 じ 評 価 計 算 回 数 で 実 験 を 終 了 す る ．そ の 他 の パ ラ メ ー タ お よ び 環 境 は2
節 で 用 い た も の と 同 じ と し た ．対 象 問 題 をft10
問 題 と し た 実 験 結 果 をTable
Table 3 Performance of GCDGA and conventional GAs
GCDGA Conventional Method avg success avg success
SPGA - 930.69 0.87
DGA 4 930.83 0.86 930.57 0.89 DGA 10 930.85 0.86 930.67 0.88 DGA 20 930.53 0.90 930.87 0.86 DGA 40 930.43 0.93 931.14 0.79 DGA 80 930.27 0.95 931.88 0.66
0 50 100
930 935 940 945 950
Makespan
Number of evaluations (x104) GCDGA 4 GCDGA 80 DGA 4 DGA 80 ft10
...GC executing
Fig.2 History of Makespan on GCDGA and DGA
3
に 示 す．な お ，表 に お い て ，GCDGA
の 列 はGCDGA
の性 能を，Conventional
の列は2
節で示した 通常のGA
の 性 能 を 示 し て い る ．GCDGA
の 性能 は ，サ ブ集 団数 が20
以 上の とき 分 散GA
お よ び 単 一 集 団GA
の 性 能 を 上 回って い る ．ま た ， サ ブ 集 団 数 を 多 く す る こ と で 性 能 が 向 上 し て お り，サ ブ 集 団 数 を80
と し た 場 合 に 最 高 の 性 能 を 示 し て い る ． 一 方 ，サ ブ 集 団 数 が10
以 下 の 場 合 に は 通 常 の 分 散GA
よ り も 性 能 が 悪 い ．こ の 原 因 は3.3
節 で 述 べ た よ う に ， サブ集団数が少ないと交叉対象個体が少なくなるため，情 報 交 換 の 効 率 が 低 下 す る た め で あ る ．
こ の 結 果 か ら ，サ ブ 集 団 数 を 多 く し た 上 で
GCDGA
を 適 用 す れ ば ，個 体 を 各 サ ブ 集 団 に 分 散 す る こ と に よ る 効 果 が 有 効 に 活 用 さ れ ，解 の 成 長 が 効 果 的 に 行 わ れ る と 考 え ら れ る ．こ の こ と を 検 証 す る た め ，上 記 の 実 験 に お け る 解 成 長 の 履 歴 に つ い て 検 討 し た ．Fig.2
にMakespan
の100
試 行 平 均 の 履 歴 を 示 す．な お ，図 に お け るGCDGA
nと あ る の は ，GCDGA
に お け る サ ブ 集 団 数 がnで あ る こ と を 示 す．図 中 の 背 景 が 網 が け の 部 分 は
GC
実 行 中 の 箇 所 を 示 す．GCDGA
は 探 索 の 中 盤 に お い て す で に 分 散GA
よ り も 高 い 性 能 を 示 し て い る ．一 方 ，GCDGA
に お い て サ ブ 集 団 数4
と80
の 探 索 結 果 を 比 較 す る と ，3
度 目 のGC
を 適 用 す る ま で は ほ ぼ 同 じ 性 能 を 示 し て い る が ，0.8 0.85 0.9 0.95 1.0
Success rate
Number of sub-populations SPGA,DGA GCDGA
1 4 10 20 40 80
la19
200 0
0.1 0.2 0.3 0.4 0.5
Success rate
Number of sub-populations SPGA,DGA GCDGA
1 2 4 10 20 40 80 100
orb1
Fig.3 Success Ratio on GCDGA and DGA
そ れ 以 降 の
GC
に よ る 効 果 が 異 な り，サ ブ 集 団 数 を 多 く し た 方 がGC
に よ る 解 の 改 善 効 果 が 大 き い ．GCDGA
は 分 散GA
よ り も 高 い 性 能 を 示 す が ，サ ブ 集 団 数 が 少 な い 場 合 に は 探 索 の 後 半 に お け る 解 の 改 善 能 力 が 低 く なって し ま い ，最 終 的 に 分 散GA
よ り も 性 能 が 低 く なって い る ．一 方 で ，サ ブ 集 団 数 を 多 く す れ ばGC
適 用 に よ る 探 索 後 半 の 解 の 改 善 が 大 き い こ と か ら ，よ り 高 い 性 能 が 得 ら れ る こ と が わ か る ．こ れ ら の こ と か ら ，
GCDGA
は サ ブ 集 団 数 が 多 い 場合，探索前半においては移住を行わなくても
GC
によって 同 等 以 上 の 性 能 が 得 ら れ ，探 索 中 盤 以 降 に お い て は
GC
の実行によって適切な個体による交叉が行われるため ，分 散
GA
よ りも 高 い性 能が 得 られ るこ と がわ かる ． 4.2 他 の 問 題 に 対 す る 性 能GCDGA
の 性 能 を さ ら に 検 討 す る た め ，la19
問 題（10
仕 事10
機 械 問 題 ， 最 適 解 のMakespan: 842
）とorb1
問 題（10
仕 事10
機 械 問 題 ，最 適 解 のMakespan: 1059
）に 対 し ，同 じ パ ラ メ ー タ を 用 い て 実 験 を 行った ．そ れ ぞ れ の 問 題 に お け る 最 適 解 取 得 率（Success rate
）をFig.3
に 示 す．la19
問 題 に 対 す る 結 果 を 見 る と ，GCDGA
の 性 能 は 分 散GA
よ り もや や 低 い ．サ ブ 集 団 数 を80
と す る こと で サ ブ 集 団20
の 分 散GA
と 同 等 の 性 能 を 得 ら れ て い る が ，そ れ 以 上 の 性 能 は 得 ら れ な かった ．一 方 ，orb1
問 題 に 対 する 性 能 はGCDGA
に よ る 探 索の 性 能 が 非常 に 高 く なって い る ．サ ブ 集 団 数 を 増 や す ご と に 性 能 が 向 上 し て お り，200
の 時 に は 最 高 の 性 能 を 示 し て い る ．Table 4 Performance of GCDGA and conventional GAs
Prob. Opt. GCDGA SPGA
(8)ft10 930 930.0 931.9
la11 1222 1222.0 1222.0 la12 1039 1039.0 1039.0 la13 1150 1150.0 1150.0 la14 1292 1292.0 1292.0 la15 1207 1207.0 1207.0
la16 945 945.7 946.0
la17 784 784.0 784.0
la18 848 848.0 848.0
la19 842 842.1 845.9
la20 902 906.1 906.5
こ の こ と か ら ，
orb1
問 題 はGC
に よ る 情 報 交 換 の 効 果 を 得 や す い 問 題 で あ る と い え る ．こ れ ら か ら ，
GCDGA
の 性 能 は 対 象 問 題 に よって 異 な り，非 常に 効果 的 な探 索を 行う こ とが でき る問 題 と，分散
GA
の性能と 同等である問題が あることがわかる ． 4.3 従 来 手 法 と の 比 較 提 案 手 法 の 性 能 を 既 存 の 手 法 と 比 較 す る こ と で 検 証 す る ．こ こ で は ，本 論 文 で 採 用 し た 交 叉 法 ，Inter-Machine JOX
に よ る 性 能 を 示 し た 文 献(8)と の 性 能 比 較 を 行 う．比 較 の 条 件 を 同 じ と す る た め ，パ ラ メ ー タ は ，個 体 数600
，交 叉 率1.0
， 突 然 変 異 率0.1
，評 価 計 算 回 数300
万 回 と し た ．ft10
問 題, Lawrence
よ り 提 案 さ れ たJSP
で あ るla11
〜20
問 題 (15)に 対 す るGCDGA
を 用 い た 数 値 実 験 結 果 と 従 来 手 法（SPGA
）の 実 験 デ ー タ(8)をTable 4
に 示 す．結果 は100
試 行 のMakespan
の 平 均 値 を 示 し て い る ．従 来 手 法 に お い て ，
la11
〜15, 17, 18
問 題 に お い て は す べ て の 試 行 で 最 適 解 が 得 ら れ て い る ．GCDGA
で も これは同様であり，同等の性能を得ている．また，他の 問 題 に 対 し て は ，従 来 手 法 で は す べ て の 試 行 で 最 適 解 を 得 るに は 至って いな い が，GCDGA
に おい ては ，ft10
問 題 に お い て す べ て の 試 行 で 最 適 解 を 得 て お り，他 の 問題 でも，従来手法 と比較して 良好な性能 を得ている．ま た ，最 適 解 を 得 る こ と が 難 し い こ と で 知 ら れ る 大 規 模 な
JSP
で あ るThailand
よ り 提 案 さ れ たta21
問 題 (17)，Yamada
・Nakano
より提案されたyn1
〜2
問題(18)，Storer
らより提案されたswv20
問題(19)に対するInter- Machine JOX
を 用 い た 単 一 集 団GA
と の 比 較 を 上 述 の パ ラ メ ー タ の も と で 行 う．ta21
問題，yn1
〜2
問題，swv20
問題に対するGCDGA
と 従 来 手 法（SPGA
）を 用 い た 数 値 実 験 結 果 をTable 5
に 示 す．な お ，問 題 の 規 模 はjobs
，machines
と し て 示Table 5 Performance of GCDGA and conventional GAs for large-scale JSP
Prob. jobs machines GCDGA SPGA
ta21 20 20 1737.8 1737.6
yn1 20 20 917.2 920.95
yn2 20 20 947.0 948.65
swv20 50 10 2823 2823
す．結 果は
20
試 行 のMakespan
の 平均 値 を示 し て いる ．Table 5
よ り，大 規 模 なJSP
と し て 採 用 し た4
問 題 に 対 し ，ta21
問 題 の よ う にGCDGA
と 比 較 し て 従 来 の 手 法 の 方 が わ ず か に 良 好 な 結 果 を 示 す 場 合 も あ る が ，yn1
〜2
問 題 ，swv20
問 題 の 結 果 よ り，提 案 手 法 は 従 来 手 法 と 比 較 し て 良 好 ，も し く は ほ ぼ 同 等 の 性 能 を 持 つ と 考 え ら れ る ．一 方 ，従 来 の 手 法 で は 世 代 交 代 モ デ ル と し て
MGG
を 用 い て い る の に 対 し ，GCDGA
は 分 割 集 団 を 用 い た 手 法 で あ る た め 並 列 化 効 率 に 優 れ て い る ．そ の た め ，PC
ク ラ ス タ な ど 並 列 処 理 環 境 で の 利 用 価 値 は 高 い と 考 え ら れ る ．5.
考察GCDGA
に よ る 性 能 向 上 の メ カ ニ ズ ム を 考 察 す る た め ，JSP
に お け る 解 探 索 の 進 捗 を 表 す 新 た な 指 標 の 導 入 を 行 い ，GCDGA
に お け る 探 索 が 分 散GA
よ り も 効 果 的 に 行 わ れ て い る こ と を 示 す．5.1 最適クリティカルペア
JSP
で は ，最 適解 が 複 数 個 存 在 す る た め ，部 分 解 の 推 移 の よ う な 指 標 を 用 い て 探 索 の 進 捗 を 観 察 す る こ と が で き な い ．そ こ で ， 本 節 で はJSP
に おけ る 部 分 解の 数 を 示 す新 た な 指 標を 導 入 す る ．ft10
問 題 に 対 し て 数 値 実 験 を 行 い ，最 適 解 に つ い て 詳 細 に 検 討 し たと こ ろ ，70
種 類 以 上の 最 適 解 が あ るこ と が わ かった ．ま た ，こ の 得 ら れ た 最 適 解 を 解 析 し た と こ ろ ，ク リ ティカ ル パ ス に つ い て は ほ と ん ど 一 致 し ていることがわかった．また，orb1
問題に対しても，同 様 の 傾 向 が 見 ら れ た ．よって 探 索 中 の 個 体 に お け る ク リ ティカ ル パ ス が 最 適 解 の も の と 共 通 し て い る か ど う か を 調 べ る こ と で ，探 索 中 の 個 体 の 部 分 解 の 数 を 知 る こ と が 可 能 と な る ．ク リ ティカ ル パ ス は 単 独 で 存 在 し て い る わ け で は な く，クリティカルパスの 前後の作業との関連が強 い．そ こ で ，解 に 含 ま れ て い る ク リ ティカ ル パ ス の 位 置 を 調 べ る の で は な く，ク リ ティカ ル パ ス の 連 続 が 解 の 中 に 含 ま れ て い る か ど う か を 検 討 す る こ と と し た ．こ れ に よって ，ど の 程 度 の 部 分 解 が 探 索 中 の ス ケ ジュー ル に 含 ま れ て い る か を 把 握 す る こ と が で き る ．
ここでは，同一機械上でのクリティカルパス上作業が
0 20 40 60 80 100 0
5 10 15
Number of OCPs
Number of evaluations (X104) GCDGA80 SPGA DGA20 DGA80 16 f t 10
...GC executing
0 20 40 60 80 100
OCPs : SPGA OCPs : DGA80 OCPs : GCDGA200
Number of evaluations (X104) 0
5 10 15 20
Number of OCPs
23
...GC executing orb1
Fig. 4 History of OCPs on SPGA, DGA and GCDGA
2
つ連続しているもの，および異なる機械間のクリティカ ル パ ス 上 作 業 が 時 間 軸 上 で
2
つ 連 続 し て い る も の を 最適解の構成要素，クリティカルパスペア（Critical path Pair: CP
）と 呼 び ，最 適 解 中 のCP
をOCP
（Optimum CP
）と 呼 ぶ．OCP
が 探索 中の スケ ジュー ル にい くつ 含 ま れ て い る か を 調 べ る こ と で ，最 適 解 へ の 解 探 索 が ど のよ うに進んでい るかを知る 指標となる ．本論文では，あ る ス ケ ジュー ル 中 の
CP
がOCP
と 一 致 し て い る 数 をOCP
数 と 呼 ぶ ．最 適 解 を 得 た と き にOCP
数 は 最 大 と な る ．次 節 でOCP
数 の推 移 につ いて 示 し，GCDGA
に よ る 探 索 の 効 果 を 検 討 す る ．5.2 OCP数の推移
OCP
数の推移より，GCDGA
の 性 能 向 上 に つ い て 検 討 す る ．対 象 問 題 と し て ，ft10
問 題 とorb1
問 題を 扱った ．な お ，最 適解 に お けるOCP
数 はft10
問 題 が16
，orb1
問 題 が23
で あ る ．GCDGA
の 探 索 性 能 を 検 証 す る た め ，単 一 集 団GA
および分散GA
との比較を行った．Fig.4
に4
節で行った 実 験 に お け る 最 良 解 中 のOCP
数 の 推 移 を 示 す．Fig.4
上 はft10
問 題 ，下 はorb1
問 題 に 対 す る 実 験 結 果 で あ る ．な お ，図 中 の 背 景 が 網 が け の 部 分 はGC
実 行 中 で あ る こ と を 示 す．まず，
ft10
問題の結果について考察する．GCDGA
に お け るOCP
数 は，探 索 の中 盤まで は単 一集 団GA
や 分 散GA
と 大 き な 差 は な い ．し か し な が ら ，5
回 目 のGC
に よってOCP
数 が 大 き く 上 昇 し ，比 較 的OCP
数 の 多い サ ブ集 団数
20
の 分 散GA
と 比較 しても 大き な差が あ る ．以 降 のGC
に よって さ ら にOCP
数 が 上 昇 し ，こ れ は 探 索 の 終 盤 ま で 続 い て い る ．Fig.2
より，適合度においては探索の序盤からGCDGA
は 分 散GA
よ り も 性 能 が 高 い と い え た ．一 方 ，OCP
数 に よ る 部 分 解 の 構 築 と い う 点 か ら 見 る と ，GCDGA
は 探索の 中盤以降に分散GA
よりも大 きく増加している ．移住に変わって
GC
を行うことで，探索序盤では比較的良 好 な 個 体 の 成 長 を 早 め る 一 方 ，探 索 の 中 盤 以 降 は 各 島 に お け る 部 分 解 が
GC
によって 組 み 合 わ さ れ て い き ， 最 適 解 を 構 築 し て ゆ く．こ の こ と か ら ，GCDGA
に よ る 探 索 に よ り 高 い 性 能 が 得 ら れ て い る と 考 え ら れ る ．次 に
orb1
問 題 の 結 果に つ い て 検討 す る ．GCDGA
で は 探 索 序 盤 か らOCP
数 が 分 散GA
よ り も 多 い ．ま た ， 探索後 半におけるOCP
数は，GCDGA
におい ては増加 を 続 け て い る も の の ，単 一 集 団GA
や 分 散GA
に お い て は 停 滞 し てい る ．OCP
数 が停 滞 す る こ とは ，部 分解 の 成 長 が な く なって い る こ と か ら 局 所 解 へ の 収 束 を 意 味 し て い る と 考 え ら れ る ．よって ，orb1
問 題 で はGC
に よって 各 島 の 有 力 個 体 を 使って 交 叉 さ せ 探 索 す る こ と が 有 効 に 機 能 し て い る と い え る ．次 に ，
GCDGA
に よ る 探 索 が サ ブ 集 団 数 に よって ど の よ う に 影 響 す る か を 検 討 す る ．ft10
問 題 お よ びorb1
問 題 に お け る サ ブ 集 団 数 ご と のOCP
数 の 推 移 をFig.5
に示す．Fig.5
上はft10
問題に対してサブ集団数10
およ び80
と して 実験 を行った も の，下はorb1
問 題 を対象 と し て サ ブ 集 団 数 を20, 80
お よ び200
と し て 実 験 を 行っ た も の で あ る ．図 に お け るBest
は 探 索 中 の 最 良 解 のOCP
数 を ，Elites
は す べ て の サ ブ 集 団 に お け る エ リ ー ト 個 体 の 集 合 に 含 ま れ て い たOCP
数 を 示 す．2
つ の 問 題 に 対 す る 実 験 結 果 に お い て ，最 良 解 に お け るOCP
数 の 推 移 に つ い て は ほ ぼ 共 通 し て い る ．探 索 の 序 盤 で は サ ブ 集 団 数 に よ る 影 響 が ほ と ん ど な く，探 索 の 中 盤 以 降 か ら
GC
適 用 に よ る 効 果 に 差 が 生 じ る と い う 点 で あ る ．2
つ の 問 題 と も に ，サ ブ 集 団 数 を 多 く し た 方 が 多 いOCP
を 得 ら れ て い る ．ま た ，各 サ ブ 集 団 中 の 全 エ リ ー ト 個 体 を 集 め る と サ ブ 集 団 数 が 多 い 方 が よ り 多 いOCP
を 含 ん で い る 点 に つ い て も 共 通 し て い る ．こ の 原 因 の 一 つ は ，サ ブ 集 団 数 が 増 え る こ と で エ リ ー ト 個 体 数 が 増 え た た め で あ る が ，サ ブ 集 団 数 を 増 や し 集 団 全 体 の 多 様 性 を 高 め た こ と に よって 全 エ リ ー ト 個 体 集 合 に よ り 多 く のOCP
が 存 在 す る よ う に なった と も い え る ．GC
に よって ，各 サ ブ 集 団 中 の エ リ ー ト 個 体 を 中 心 に し て 探 索 が 進 め ら れ る た め ，各 エ リ ー ト 個 体 中 に 多 く の 部 分 解 が 存 在 し て い る こ と が 望 ま し い ．ft10
問 題 は 比 較 的 簡 単 な 問 題 で あ る た め ，探 索 を 進 め る こ と で 全 エ リ ー ト 個 体 集 合 のOCP
数 が 増 加 し て い る ．し か し ，orb1
問 題 で は 探 索 を 続 け る こ と で 全 エ リ ー ト 個 体 集 合 のOCP
数 が減 少し てい る．こ れは，大 きな 局所 解 が 存 在 し て い る た め に ，探 索 初 期 に は 存 在 し て い た 小 さ な 部 分 解 が 破 壊 さ れ ，集 団 中 に 存 在 し な く な る た め0 20 40 60 80 100 0
5 10 15
Number of OCPs
Number of evaluations (X104) Best, Elites : GCDGA80 Best, Elites : GCDGA10 16 ft10
...GC executing
0 20 40 60 80 100
0 5 10 15 20
Number of OCPs
Number of evaluations (X104) Best, Elites : GCDGA 20 Best, Elites : GCDGA 80 Best, Elites : GCDGA200 23 orb1
...GC executing
Fig.5 History of OCPs on GCDGA
だ と 考 え ら れ る ．
分 散
GA
に お い て は サ ブ 集 団 数 を 増 や し 多 様 性 を 向 上 さ せ る こ と で こ の 問 題 を 解 決 し ，探 索 の 後 半 ま で 集 団 全 体 のOCP
数 を 維 持 す る こ と が で き る ．さ ら にGCDGA
で は 移 住 を 行 わ な い た め ，GC
に よ る 集 団 全 体 か ら の 個 体 を 用 い た 交 叉 を 行 う こ と で ，部 分 解 を 組 み 合 わせ て 良好 な個 体を 生 成で きる ．こ の こと によ り，GCDGA
に よ る 探 索 に お い て サ ブ 集 団 数 を 増 や す こ と が 探 索 性 能 向 上 に つ な がって い る と 考 え ら れ る ．以 上 の 考 察 と 実 験 結 果 か ら ，
GCDGA
で は 分 散GA
に 用 い る サ ブ 集 団 数 よ り も 多 く し た 方 が 性 能 が 向 上 す る と い え る ．集 団 サ イ ズ に も よ る が ，サ ブ 集 団 内 の 個 体 数 を5
〜10
と し て ，サ ブ 集 団 数 を 増 や し た 方 が 性 能 が 向 上 す る と 考 え ら れ る ．6.
おわりに本 研 究 で は ，離 散 最 適 化 問 題 に 対 す る 分 散
GA
に お け る 新 た な 手 法 ，大 域 的 交 叉 型 分 散GA
（GCDGA
）の 提 案 とジョブ ショップ ス ケ ジュー リン グ問 題で の 性能 評 価 お よ び 考 察 を 行った ．数 値 実 験 の 結 果 ，GCDGA
の 性 能 に つ い て 次 の 点 が 明 ら か と なった ．• 従 来 の 分 散
GA
よ り も 高 い 性 能 を 示 す．• サ ブ 集 団 数 を 増 や す こ と で 性 能 が 向 上 す る ．
• 多 く の 部 分 解 を
GC
に 採 用 す る こ と で 探 索 性 能 が 向 上 す る ．今後の課題は，他の離散最適化問題に対する
GCDGA
の 性 能 を 検 証 す る こ と で あ る ．な お ，本 研 究 は 文 科 省 か ら の 補 助 を 受 け た 同 志 社 大 学 学 術 フ ロ ン ティア 研 究 プ ロ ジェク ト に お け る 研 究 の 一 環 と し て 行った ．こ こ に 記 し て 謝 意 を 表 す．参考文献
