http://repository.osakafu-u.ac.jp/dspace/ Title Author(s) Citation Issue

Title
材料取り合わせ問題のための対戦交叉法GAの改善
Author(s)
豊田, 丈輔
Citation
大阪府立大學經濟研究. 2008, 54(3), p.135-146
Issue Date
URL
2008-12-26
http://hdl.handle.net/10466/11022
Rights
http://repository.osakafu-u.ac.jp/dspace/
1
3
5
材料取り合わせ問題のための対戦交叉法 GA の改善
豊田丈輔
<概要>材料取り合わせ問題 (Cutting
グ問題 (Bin
S
t
o
c
kP
r
o
b
l
e
m
:CSP)
あるいはどンパッキン
P
a
c
k
i
n
gP
r
o
b
l
e
m
:BPP) は、いろいろな方向から研究が行われているが、
A
l
g
o
r
i
t
h
m
:GA) の適用については、アイテムの並びを
遺伝的アルゴリズム (Genetic
染色体とする通常の GA モデルを適用すると、交文によって遺伝子品質が劣化してしま
う傾向があるため成功例は多くない。複数の長さの材料を扱う Multiple
S
t
o
c
kL
e
n
g
t
h
CSP ではさらに例が少ない。我々は前回、アイテムの並びを染色体とするモデルではあ
るが、新しい交文法によって収束性のよいモデルを提案した。今回、さらにこのモデル
に焼きなまじ法の考え方を取り入れて、多様性と収束性のバランスをとる。
キーワード:遺伝的アルゴリズム、対戦交文、取り合わせ問題、焼きなまし法
Keyw
o
r
d
s
:G
e
n
e
t
i
cAlgorithm , TournamentCrossover , C
u
t
t
i
n
gS
t
o
c
kProblem ,
S
i
m
u
l
a
t
e
dA
n
n
e
a
l
i
n
g
1.はじめに
一次元の材料取り合わせ問題 (Cutting
問題 (Bin
StockP
r
o
b
l
e
m
:CSP)
あるいはビンパッキング
PackingP
r
o
b
l
e
m
:BPP) は単純なモデルではあるが、 NP 困難問題であり多項
式時間 (polynomial time) で最適解を求めるアルゴリズムは存在しない。しかし組み合わ
せ問題の中の最も基本的なもののひとつで、応用範囲も広く、いろいろな方向から研究が行わ
れている。過去の研究には、割付けパターン選択の整数計画を LP 緩和問題 (LP
R
e
l
a
x
a
ｭ
tion) として解く方法が古典的だが (Gilmore ， 1963) 、アイテムサイズが比較的大きな場合、
整数解を得ることがむずかしいという問題がある。ヒューリスティック法では First
(FF) 法、 Best Fit 法、 Minimum
BinS
l
a
c
k(MBS)
法 (Gupta
F
i
t
e
tal
.1999 , F
l
e
s
z
a
re
tal
.
2002) などがあるが、ビンサイズが複数ある場合は取り扱われていない。遺伝的アルゴリ
ズム
(Genetic
Algorithm:GA) の適用例としては、アイテム単位を基準にする“ Order
BasedGA" とビン単位に注目する“ Group- BasedGA" の 2 つの考え方がある。 Order
Based モデルは直感的にわかりやすいが、交文によって遺伝子品質が劣化してしまう傾向
があり、成功例は見当たらない
(Hinterding ，
e
ta l., 1
9
9
4
)
0 Group-Based モデルは、
Falkenauer がグルーピング GA として提案し成功している (Falkenauer ， 1994 , Falkenauer ,
1
3
6
材料取り合わせ問題のための対戦交文法 GA の改善
1996) 。
我々は前回、住宅のプレカットを対象に、複数の材料長を扱う CSP
(
M
u
l
t
i
p
l
eS
t
o
c
k
LengthCSP) に対して、製品の並びを遺伝子配列とする“ Order ~ Based" モデ、ルで遺伝子
単位に適応率を定義して交文制御を行う対戦交叉法 (Tournament
C
r
o
s
s
o
v
e
rO
p
e
r
a
t
i
o
n
Method:TCOM) を提案して、一般のプレカット工場では 90% 以下といわれている歩留を
95% 前後まで向上させた(豊田， 2008) 。しかし、このモテソレは交文において遺伝子単位の
比較決定を確定的に行うため、初期個体に多様性が不足している場合に局所解に陥る危険が
合った。そこで今回、交叉に確率的な要素を持ち込んで、 TCOM の回定的な交文方法に柔
軟性を取り入れることで、さらなる性能向上を図る。
本論文で使用する主な記号を表 1 にまとめた。なお、材料の長さ種別を「材長種」と表現し
た。以下、 2 で Multiple
S
t
o
c
kLengthCSP を定義し、 3 で従来のモデルとその問題を指摘
し改善を提案する。 4 でこれを評価し、最後に 5 でまとめる。
表1.使用する記号の一覧
生旦bol
E笠竺並tion
n
製品の数
m
材料の長さ種類(材長種)の数
製品(添え字)
(1三 i 壬 n)
t, t;
材長種(添え字)，製品 i を割付ける材料の材長種(添え字)
k , k(I)
材料(添え字)，材長種 t の材料(添え字)
l
i
製品 i の長さ
b , bt
材料の長さ，材長種 t の材料の長さ
I ,lk
製品の集合，材料 k に割付けられた製品の集合
B , Bt
使用した材料の集合，使用した材長種 t の材料の集合
(1 :::;t， t; 壬 m)
2. 材料取り合わせ問題 CCSP)
今、 m 種類の長さ bt(t
=1,… , m)
の材料が十分にあり、これから長さ IJi
=1,… , n)
の製品すべてを切り出すとき、材長種 t の材料の使用コストを C t とすると、 CSP は、
m
]= L
: .
2
:
t ニ 1
Ct•
kU) E B
t
s
u
b
j
e
c
tt
o
(1)
Min
2
: li 壬 bf vk(t)EBH(t=l ,…, m)
(2)
iEι川
m
U
(3)
U L
c
t
l= 1
I~] k'O 巴 B，
ιnι
山
ゆ
V k] , kzE B , k] 学 k z
大阪府立大学経済研究
54 ・ 3 (
2
2
5
)(
2
0
0
8
.
1
2
J
(4)
1
3
7
材料取り合わせ問題のための対戦交文法 GA の改善
と表せる。目的関数(1)は、使用コストが材積単価で表される材料費とすると、「使用材料
最小」と等価であり、 (5) 式のように書き換えられる。
m
]= L; :
2
: bt •
t= lk 川 EB，
(5)
Min
一方、歩留 u は (6) 式で与えられるが、右辺の分子の製品長合計は所与であるので、結局
(5) 式は「歩留最大」と等価となる。
(6)
y=L; li/:
2
:.
.
:
2
: bt
iE 1
t= 1kllJ E Bt
なお、実際の CSP では材料の両端を整える「鼻切」および製品を切り出す際の「鋸代」を
考慮する必要があるが、本質的な問題ではない。
3
. TCOM を使った GA とその問題
3
.
1 TCOM を使った GA モデル
我々は前回、敢えて Falkenauer が非効率性を指摘 (Falkenauer ， 1996)
した Order
Based モデノレであるアイテム単位の遺伝子構造モデルとし、遺伝子単位の適応率を定義して、
この適応率を遺伝子ごとに比較することでその遺伝子座の次世代に引き継ぐ遺伝子を決定す
る、対戦交文法 (Tournament
CrossoverOperationMethod:TCOM) を提案した(豊田，
2008) 。以下で TCOM について述べる。
3
.1
.1
遺伝子構造と取り合わせ計算ルール
割付ける製品の並びを染色体で表現し、製品を割付ける材長種を指定する遺伝子(以下
GeneB と略記)と、同じ材長種に割付けられた製品群の中での割付け順を指定するソート
キーとなる遺伝子(以下 GeneP と略記)の 2 重遺伝子構造の染色体を考える。表 2 に遺伝
子構造を示した。
この 2 つの遺伝子を使って、取り合わせ計算を以下のようなルールで行う。なお、「鼻切」
と「鋸代」は材料長や製品長の調整で組み込むことができるので、ここでは単純化のため無
視した。
表 2. 遺伝子構造
製品=遺伝子座
役割
GeneB
割付けられる材長種を指定
GeneP
割付けの順序(昇順ソートキー)
大阪府立大学経済研究
54 ・ 3(225)
(
2
0
0
8
.
1
2
)
1
3
8
材料取り合わせ問題のための対戦交叉法 GA の改善
<取り合わせ計算ルール>
製品を、 GeneB を第 1 キ一、 GeneP を第 2 キーとして昇順にソートし、ソー卜した順に
製品を取り出して、以下のステップをすべての製品が割付けられるまで繰り返す。
S
t
e
p1
. GeneB が変化したら、新しい材長種の新たな材料に割付ける
S
t
e
p2
.GeneB
が変化しないときは、現在割付け中の材料にその製品が割付け可能であれ
ば割付け、不可能であれば同じ材長種の新たな材料に割付ける。
3
.1
.2
収束性確保のための制御
しかし上記の取り合わせルールでは、割付け順が GeneP の相対的な大小関係で決まる結
果、 GeneP の微小な変化で、材料一製品グループが過敏に変化してしまうため、通常の一様
交文のような方法では安定的な最適解への進化が期待できない。そこでこれを回避するため
に、「高い材料歩留をもっ材料
製品グループが次世代に引き継がれる傾向」を持たせる。
具体的には次の 2 つの制御を行う。
制御 1 :材料歩留の高い材料製品グループに属する製品は優先的に割付け順を早くして、
先行する材料の取り合わせでグループが破壊されないようにする。
制御 2: 材料歩留の高い材料一製品グループに属する製品の遺伝子は、交叉操作で次世代
にできるだけ引き継がれるようにする。
この制御のために、まず材料の歩留を定義する。 t 番目の遺伝子座に対応した製品 t を割付
ける材長種を ti とし、製品 t の長さを li、材長種 t の材料の集合を Bt、その材料の長さを b t、
Bt に属する材料をどぺ= 1 ， 2，…)としてどのに割付けられた製品の集合を ιω とする。こ
のとき材料 k( t) の歩留 Yk( t) は次式で定義される。
Yk(t
)=
(7)
I
; l;/bt
jE ι 川
d
この歩留は (6) 式の全体歩留に対して材料単位の歩留であり、以降、 (6) 式を「個体歩留」
あるいは単に「歩留」、
(7) 式を「材料歩留」と呼ぶこととする。これを使って製品 t の遺伝
子座の各遺伝子を下記のように定義する。
GeneB:ti
1:
;t i
(8)
三三 m: 整数
GeneP:Si=(1-YkCti
)
)+ εk(ti) 0 豆町三三 1
但し、 b ti 孟 li
(9)
(
10
)
i= 1, 2,… , n
ここで (9) 式右辺第 2 項は同じ材料に割付けられた製品グループが確実に同じ値となるた
めの定数で、 E は材料歩留に対して十分に小さな値とする。(1 0) 式は製品長より短い材料が
大阪府立大学経済研究
54 ・ 3(225)
(
2
0
0
8
.
1
2
J
1
3
9
材料取り合わせ問題のための対戦交文法 GA の改善
割り当てられて致死遺伝子となることを防ぐための条件である。
<制御 l の実行: GeneP の設定>
(9) 式の GeneP の定義により、より高い材料歩留の材料一製品グループに属する製品の
GeneP は小さな値になり、取り合わせ計算での割付け順が早くなることで、制御 1 は実現
できる。
<制御 2 の実行:交文操作>
t 番目の遺伝子の製品が属する材料一製品グループの材料歩留を、その遺伝子に対する
「遺伝子適応率 (Gene
F
i
t
n
e
s
sR
a
t
i
o
:GFR)J として以下のように定義する。
t 番目の遺伝子の GFR: g
i= G( 仇 (h))=UK(h)
(
1
1
)
t=l , 2,…, n
これを使って、交文において 2 つの親個体の GFR を比較して、遺伝子単位にどちらの遺伝
子を引き継ぐかを決める。すなわち子の t 番目の遺伝子 t i ， Si は次のルールで引き継がれる。
I
fgiCl )ミ仏(2)then tt=tt(1) , sz=sjl)else tz=tj2) , sz=sJ2)
(
1
2
)
但し、右肩の(1)および (2) は、親 1 および親 2 の GFR および各遺伝子であることを表し
ている。
交叉は、ランダムに決定した遺伝子座の前後をそれぞれの親から引き継ぐ 1 点交文法や、
どちらの親の遺伝子を引き継ぐかをランダムに決定していく一様交文法が一般的であるが、
本モデルでは遺伝子毎に GFR を比較して高い適応率の遺伝子を次世代に引き継ぐことで、
遺伝子の総体である個体の適応率を高めていくことに特徴がある。対応する遺伝子を GFR の
優劣で対戦させるので、この交文方式を「対戦交文法 (Tournament
Method:TCOM)J
C
r
o
s
s
o
v
e
rO
p
e
r
a
t
i
o
n
と呼んだ。
3
.1
.3 その他の工夫
(
1
) RFF による初期個体の生成による収束の高速化
優秀な初期個体を生成し、収束の高速化と解の安定性を図る。 BPP で一般的な FFD
F
i
tDecreasing)
法を複数材長の CSP に対応した Revised
FFD(RFFD)
2008) に対して、特に製品の並び、に条件をつけない場合を Revised
(
F
i
r
s
t
法 (Toyoda，
FF(RFF)
e
tal ,
と呼ぶこと
にする。初期個体は、製品の並びを長さの降順にした RFFD によって 1 個体を生成し、残
りの必要な個体は製品をランダムに並び替えて RFF により生成する。なお、 RFF 生成比率
α をあらかじめ設定し、初期個体数× α を RFFD および RFF で、残りは乱数によって生成
することにする。各遺伝子は次のように設定される。
大阪府立大学経済研究
54 ・ 3(225)
(
2
0
0
8
.
1
2
J
1
4
0
材料取り合わせ問題のための対戦交文法 GA の改善
RFFD および RFF によって生成する個体
GeneB: 割付けられた材料の材長種
)
(
13
)
GeneP: 割付け結果をもとに (9) 式にて計算 j
乱数によって生成する個体
G
e
n
e
B:ti= [1,
G
e
n
e
P
:Si=
mJ の整数乱数但し、(1 0) 式を満たす。 l
￨
(0， β) の乱数
(
14
)
ここで β は (9) 式で計算される場合の GeneP の値から突出しないためのパラメータで、先
行実験によって材料歩留の分布をみて設定する。
(2) 新規個体の投入による多様性の確保
GA において、個体の多様性を確保することは、局所解を回避し最適解を得るための重要
なポイントである。本モデルでは、経過する世代のうち A の割合で世代を選択し、この世
代では突然変異の代わりに、突然変異対象の個体を新たな個体と入れ替える「新個体の投入」
を行うことで、多様性を豊かにする
(Yuu
e
ta
l
.2007) 。新規個体は、初期個体の生成ルー
jレ (13) 式と(1 4) 式に則って生成する。その他の世代では通常の突然変異を発生させる。
3
.
2
対戦交文法モデルの問題とその改善策
3
.
2
.
1
対戦交文法モテ酔ルの問題
TCOM は上記の 2 つの制御によって、製品の並びを染色体とする遺伝子構造にもかかわ
らず、材料に割付けられる製品のグルーフ。を尊重し、無駄な冗長性によって探査空間を広げ
ることなく、遺伝子毎に GFR を比較して高い適応率の遺伝子を次世代に引き継ぐことで、
遺伝子の総体である個体の適応率を高めていくことに特徴がある。
しかし、この方法は(1 2) 式のルールで引き継ぐ遺伝子が決まるため、例えば極めて高い
材料歩留をもっ材料に割付けられた製品の遺伝子は“常に"次世代に引き継がれることにな
る。ところが、一部の材料歩留が高くても材料歩留の総和としての個体歩留が高いとは限ら
ない。なかにはある材料の歩留を低くすることで、他の材料の歩留が改善され、全体の歩留
を高くする場合もありうるが、(1 2) 式のルールによる交文は固定的で、たとえば限りなく 1
に近い材料歩留の遺伝子の組は、必ず次世代に引き継がれ材料歩留が低くなる可能性はほと
んど無い。この場合、袋小路に入ってしまい、局所解に陥る危険がある。特に RFF で生成
される個体は、 FF 法の特徴である良い組み合わせの先取りにより、高い歩留の組み合わせ
のある一方で、最後に割付けられた材料の歩留が低くなり、全体歩留が高くならない場合が
ある。実際、後で述べるように前回の TCOM の提案(豊田， 2008) では、 BPP のベンチマー
大阪府立大学経済研究
54 ・ 3(225)
(
2
0
0
8
.
1
2
J
1
4
1
材料取り合わせ問題のための対戦交文法 GA の改善
クによる評価の中で、 RFF による初期個体生成率を α= 1 とした場合、 α= 0.5 とした場合
より悪くなることがわかっている。
3
.
2
.
2
改善した新しい TCOM の提案
この課題を解決するためには、(1 2) 式の交文ルールに確率的な要素を組み込むことを考
える必要がある。そこで焼きなまじ法 (Simulated Annealing) の考え方を取り入れること
にする。
焼きなまし法は、内部温度がゆっくり冷えるにつれて原子が初期の高エネルギー状態から
エネルギ一極小の状態に移る現象に倣って、内部温度を定義し、この温度が高いときは解を
大きく変化させることで探査範囲を広げ、温度の低下とともに徐々に探査範囲を収束させて
いく手法である。この考え方を次のように交文ルールに取り入れる。
親個体 ρ (p = 1, 2) の“温度 " T(p) を親の個体歩留の関数として以下のように定義する。
T(P)
=(
1-y(P))xr P=1, 2
(
15
)
ここで y(P) は親個体 ρ の個体歩留、 7 は調整パラメータで本論では r = 0.1 とした。子の t
番目の遺伝子が親 1 から引き継がれる確率を Pr (J)として、これを両親の GFR と温度差の関
数として以下のように定義する。親 1 と親 2 のそれぞれの t 番目の遺伝子の GFR を gz(I 〕， gz(2)
とし、
r
min[exp{(gi
(
J
)-
Pr(l) =
gi(勺 /(T(2)-T( J))}， 1
]
y (J) ミ y(2) のとき l
~
lmax[1-exp{(針。 -g?))/(T(2)-T( J))}， O
J y(
J
)< y(2) のとき j
(
16
)
とする。これは図 1 のような関数となる。言うまでもなく、親 2 から引き継がれる確率は
P
r
(
2
)= 1-Pr (J)である。(1 6) 式の確率関数を使って、(1 2) 式の交文ルールを次式のように
変更する。
I
fRnd<Pr(l)thenh=tz(l) , sz=sz(l)else L=tz(2) , sz=sz(2)(17 >
このルールは、個体歩留の低い個体は高い内部エネルギーを持つため、この個体のある遺
伝子が高い遺伝子適応率を持っていても、相対的に内部エネルギーの低い個体の遺伝子との
生存競争に敗れる場合があることを意味している。従って極めて高い材料歩留をもっ材料に
割付けられた製品の遺伝子であっても、その個体の歩留が相手の個体歩留より低い場合には、
子に引き継がれない可能性がでてくることになる。これにより、局所解に陥る危険を緩和す
ることができると期待される。
大阪府立大学経済研究
54 ・ 3(225)
(
2
0
0
8
.
1
2
J
1
4
2
材料取り合わせ問題のための対戦交文法 GA の改善
P
r
(1
)
~y(1) 詰(2)
-・-y( 1) <y(2)
g
(
1)
g
(
2
)
0
.
0
5
0
.
1
0
.
0
5
。
0
.
1
図1.親 l の遺伝子を引き継ぐ確率曲線(温度差= 0.01 の場合)
4. 改善結果の評価
4
.
1 BBP ベンチマーク問題による評価
前回提案した TCOM モデルでは、材料の長さ種類 m = 1 として BPP ベンチマーク問題
(http://www.wiwi.uni-jena.de/Entscheidung/binpp/index.htm) によって拡張エリート
選択 (Entended
E
l
i
t
i
s
mM
e
t
h
o
d
:EEM) GA
モデル (Toyoda ，
e
tα l. ， 2007) との比較や
TCOM モデルの RFF 初期個体生成率 α を l 、 0.5 および O とした場合の比較を行った。使
用したベンチマークデータは Data
S
e
t3
に分類されるもので、ビン容量が 100000 に対して
アイテムサイズは (20000 ， 35000) の範囲で一様分布し、ビンには 3 から 5 つのアイテムが
入るように設定される Very Hard とされる 10 例の問題で、現在知られている最少使用ビ
ン数が示されている。その結果、 EEM に対する優位性を確認すると同時に、 RFF による初
期個体生成の比率による違いは次のような結果となった。初期個体比率 α= 0.5 とした場合
は 10 問中 8 間でどンの最少解が得られ、 α=0 では収束速度は遅いものの得られた解は
α= 0.5 の場合と同等であった。しかし、 α= 1 として全ての初期個体を RFF と RFFD で
生成した場合は、 10 聞のうち最少解を得たのは 5 聞のみであり、 TCOM は初期固体の構成
によって局所解に陥る危険が高いことを確認した。
そこで、今回の交文に確率的要素を取り入れた新しい TCOM モデルを、同じベンチマー
ク問題に適用し、その効果を確認することにする。前回モデ、ルで、多様性維持のために行った
突然変異における新規個体投入を、今回は敢えて多様性より計算時間短縮を優先して行わな
いことにする。その他の条件は前回と同様に、個体数は 100、最大世代数は 1000 世代とし、
各種パラメータは(1 8) 式として、 10 回の試行で最も良い結果を採用する。ベンチマーク問
題は、前回と同じ Data
S
e
t3
の Very Hard とされる 10 例の問題を使い、実行環境も表 3
のとおり前回と同じである。
大阪府立大学経済研究
54 ・ 3(225)
(
2
0
0
8
.
1
2
J
1
4
3
材料取り合わせ問題のための対戦交文法 GA の改善
GeneP の初期設定定数 β= 0
.
3
適応率 :α = F(y)=y
l
O 但し U は (6) 式の個体歩留
選択確率二 50%
(
18
)
うちエリート選択 =5%
突然変異確率: 20% 変異遺伝子座数:製品数の 10% (切上げ)
新規個体投入世代比率 À=O
FL
e
n
CI
明日ロ且
0
犯 U
TAFU
ρLW
vi
q
a
免U
v
a
Ju
w
H
So丘ware
'
n
a
M
表 3. 実行環境
IBMT
h
i
n
kP
a
dG41
I
n
t
e
lP
e
n
t
i
u
m3GHz
Memory
5
1
2Mbyte
OS
WindowsXP
P
r
o
g
r
a
m
m
i
n
gL
a
n
g
u
a
g
e
MSE
x
c
e
l2002 , VBA
実行結果を表 4 に示した。 NewTCOM が今回の改善後の新モデルである。“ All RFF" は
α=100% 、“ 50%RFF" は α=50% 、“ All RN" は α=0% ですべての初期個体を乱数によっ
て生成したことを示している。“ Hits" は 10 の問題のうち最少解が得られた問題の数であり、
“ Av.Rel."は各問題の相対偏差平均、“ Max.Rel."は最大相対偏差、“ Av.Abs." は絶対偏差平
均、“ Max.Abs." は最大絶対偏差である。なお相対偏差は、 100x (実行値一最少解)/最少
解で、絶対偏差は(実行値一最少解)で計算される。“ Av.Time" は平均計算時間で単位は
秒である。表 4 からわかるように、今回の改善後のモデノレでは、 α= 100% の場合でも 8 聞
が最少解となり、また平均計算時間も優秀な初期個体の効果により最も早い 3 秒台となった。
表 4. ベンチマークデータによる比較
H
i
t
s
A
v
.
R
e
l
M
a
x
.
R
e
l
A
V
.
A
b
s
Max目Abs.
Av目 Time
NewTCOM
O
l
dTCOM
A
I
IR
F
F 50出 RFF A
I
IRN A
I
IR
F
F 50目 RFF A
I
IRN
8
5
8
8
8
8
.
3
6 0
.
3
6
1
.2
6 0
.
3
6 0
.
3
6
0
.
3
6 0
1
.
8
2 1 目 82
3
.
6
4 1
.
8
2 1
.
8
2
1 目 82
.
2
0 0
.
2
0
0
.
7
0 0
.
2
0
0
.
2 0
.
2
0 0
2
.
0
9 8
.
3
3
7
.
0
1 5
.
9
0 3
4
.
1
2
3
.
7
7 5
4
.
2 住宅プレカット材料データによる評価
前回のモデルに適用したものと同じ住宅プレカットデータで、改善モデルを評価する。住
宅フ。レカット CSP とは、いくつかの種類の長さを持つ木材母材から、住宅建築で要求される
長さの部材(製品)を切り出す問題である。ここでは標準的な 2 つの一戸建て住宅の横架材
に適用した(表 6、付表1)。これらの横架材は、断面形状 (Shape) や樹種 (Spec.) 、等級
大阪府立大学経済研究
54 ・ 3(225)
(
2
0
0
8
.
1
2
J
材料取り合わせ問題のための対戦交文法 GA の改善
144
表 5. プレカットデータによる評価(邸 1
一 222
4
OldTCOM
Y
i
e
l
dRate Num. Time
96.91 九
4
7
0
10
96.34 九
10
97.58 九
10
1
.19
97.58%
10
92.82%
10
0
.
1
3
92.82%
10
。
94 .4 0 弘
10
4
.
2
1
94 .4 0 弘
10
4
92.02%
10
0
.
0
2
92.02%
10
0
98.67%
4
4
.
1
4
98.67%
5
25.00%
10
0
.
0
0
25.00%
10
93.85%
10
0
.
0
1
93.85%
10
95.69%
10
0
.
1
5
95.69 九
10
89.93%
10
0
.
1
0
89.93%
10
96.22%
10
0
.
0
6
96.22%
10
96.01%
10
0
.
3
3
96.01 弘
10
98.81%
10
0
.
5
2
98.81%
10
96.
46%
9
0
.
5
8
96.
46%
9
98.31%
10
0
.
0
6
98.31%
10
83.64%
10
0
.
0
3
83.64%
10
10
1
.
2
1
92.76%
10
20.53
95.21%
95.21%
』
92.76%
nunununununununununU4
一
一問
一9
一d
T
圃
一屯
96.34%
凋斗
門一894500035405055586
96.91 弘
山m
一M
X
MG
ag238221322145415
-va-
336555535655553522
d一肌一
Ja111111111
一昨一31122112
N
2123456789012345678
一一
N一
問一札8一
34522311443815348
o
ふLEFC
'L.
NewTCOM
Y
i
e
I
dRate Num.
)
18
表 6. プレカットデータによる評価(邸 2)
a
MG
OldTCOM
4E・
4EZ4EE41E41
95.05%
10
96.26%
10
89.97%
10
95.90%
10
3
.
7
3
95.90%
10
92.02%
10
0
.
1
0
92.02%
10
94.36%
10
0
.
5
4
94.36%
10
29.13%
10
0
.
0
0
29.13%
10
98.36%
10
9
.
6
4
98.36 弘
92.84%
10
0
.
2
3
92.84%
10
95.56%
10
0
.
1
9
95.56%
10
93.34%
10
0
.
3
0
93.34%
10
94.94%
10
0
.
0
5
94.94%
10
95.82%
10
1
.3
1
95.82%
10
・
一
一1
一却
TE
一副
圃
4E・-4L
92.94%
10
92.94%
10
63.71%
10
0
.
0
1
63.71%
10
90.
48%
10
0
.
0
6
90.
48%
10
大阪府立大学経済研究
25.11
94.16 九
54 ・ 3(225) (
2
0
0
8
.
1
2
J
,
tEnuqunu--nuRununun
7
0.
42
94.16%
e-7
m一
i
e
l
dRate Num
Time Y
7
.
5
8
95.05% 10
0
.
8
5
96.26% 10
0
.
0
7
89.97% 10
TE
一
一 223
日一 25102562341731
・
XL2454053070052242
-VE-
3356553535553222
d一肌一
m-4一7837411696834626
3111321
N
一昨一
-4E
一-
一一
h一 1234567890123456
+L
O
EL-
NewTCOM
Y
i
e
l
dRate Num.
2
2
1
4
5
材料取り合わせ問題のための対戦交文法 GA の改善
(Grade) など同じ母材から切り出すことができる 16 および 18 のロットにグループに分か
れ、それぞれのロット毎に切り出す製品数 (Num.) や使用する母材群 (Kinds
o
fMateria
l
)
も異なる。なお邸全体の歩留は、ロット毎に断面形状が異なるため体積による材積歩留で比
較する。
パラメータは前回と同じように (18) 式で À
=0.2
とし、個体数は 100 とする。最大世代
数は前回の報告で実用を考えた場合の設定 jレールである(1 9) 式で設定する。また、試行回
数も前回と同じ 10 回である。その結果を邸 l については表 5 に、邸 2 については表 6 に示
す。
[製品数×材長種 X2
最大世代数= ~
l 製品数×材長種
製品数×材長種孟 1001
e
l
s
e
(
19
)
表 5 および表 6 で、“ Num. o
fPrd." および“ Num. o
fMtr・はそれぞれ各ロットの製品
数と材長種の数である。“ Max. Gen." は(1 9) 式の jレールに基づ、く最大世代数である。新旧
の TCOM 欄の“ Yield Rate" は 10 回の試行で得た最大歩留、“ Num." は 10 回の試行のうち
最大歩留を得た回数、“ Time" は計算時間を秒で表した。ここで、旧 TCOM のデータは前
回報告のものである。なお Time は、前回は有効数字 1 桁であったため若干小さ目に出てお
り、実質的には今回と前回は変わらなし、。以上の結果、プレカットデータによる評価では、
前回のモデルとほぼ同等の結果となった。これは、いずれの邸も歩留はほぼ最適値と想定さ
れ、また製品数が最大でも 40 以下であり、歩留と時間のいずれも顕著な差がでなかったと
推定できる。
5. まとめ
複数材長を扱う一次元の Multiple
S
t
o
c
kLengthCSP を対象に、前回報告した TCOM
を使った GA モデルについて、 TCOM による交文では引き継ぐ遺伝子を確定的に決定する
ため、局所解に陥る危険があることを指摘した。そしてこの打開策として、親個体の (1 一
歩留)を「温度」とみなして、遺伝子交換の決定過程に焼きなまし法の考え方を取り入れる
ことで、確率の要素を組み入れた新しい TCOM を提案した。これを前回と同じ BPP ベン
チマークデータとプレカットデータに適用し、新旧の TCOM を比較評価した。その結果、
ベンチマークデータでは RFF による初期個体性成立を 100% にしたとき、旧モデルでは 10
問中 5 聞の最少解であったのに対し、新 TCOM では 8 聞の最少解をより短時間に得ること
ができた。また、プレカットデータに対しては同等の性能であることを確認した。
大阪府立大学経済研究
54 ・ 3(225)
(
2
0
0
8
.
1
2
J
1
4
6
材料取り合わせ問題のための対戦交文法 GA の改善
参考文献
Fa1kenauer , E
.
:A NewR
e
p
r
e
s
e
n
t
a
t
i
o
nandO
p
e
r
a
t
i
o
n
sf
o
rG
e
n
e
t
i
cA1gorithmsA
p
p
1
i
e
dt
oGroupｭ
v
o
1
u
t
i
o
n
a
r
yComputation , 2, (
19
9
4
), p
p
.1
2
3
1
4
4
.
i
n
gProb1ems , E
.
:A HybridGroupingG
e
n
e
t
i
cA1gorithmf
o
rBinPacking , J
o
u
r
n
a
1o
fHeuristics , 2,
Fa1kenauer, E
(1 996) , p
p
.5-30
F1eszar , K., Hindi , K.S
.
:Newh
e
u
r
i
s
t
i
c
sf
o
ro
n
ed
i
m
e
n
s
i
o
n
a
1bin-packing , Computer& O
p
e
r
a
ｭ
t
i
o
n
sR
e
s
e
a
r
c
h2
9(
2
0
0
2
)p
p
.8
2
1
8
3
9
.
Gilmore , P
.C
.andGomory , R
.E
.
:A L
i
n
e
a
rProgrammingApproacht
ot
h
eC
u
t
t
i
n
gS
t
o
c
kP
r
o
b
p
e
r
a
t
i
o
n
sResearch , 1
1(1 963) , p
p
.8
6
3
8
8
8
.
1
e
m
;P
a
r
tII , O
Gupta , J
.andHo , J
.C
.
:A NewH
e
u
r
i
s
t
i
cA1gorithmf
o
rt
h
eOne-Dimensiona1Bin-PackingProb
1em , P
r
o
d
u
c
t
i
o
nP
1
a
n
n
i
n
g& Contro1 , 10-6 , (1 999) , p
p
.5
9
8
6
0
3
.
Hinterding , R
.andKhan , L
.
:G
e
n
e
t
i
cA1gorithmsf
o
rC
u
t
t
i
n
gS
t
o
c
kP
r
o
b
1
e
m
s
:w
i
t
handw
i
t
h
o
u
t
e
c
h
n
i
c
a
1R
e
p
o
r
t4
0CO恥1P 1
2(1994) , V
i
c
t
o
r
i
aU
n
i
v
.o
fTechno1ogy , A
u
s
t
r
a
1
i
a
Contiguity , T
.andTakeyasu , K
.
:E
xtendedE
1
i
t
i
s
mMethodf
o
rC
u
t
t
i
n
gS
t
o
c
kProb1emo
fTimber
Toyoda , J
Precutting , I
n
t
e
r
n
a
t
i
o
n
a
1J
o
u
r
n
a
1o
fI
n
f
o
r
m
a
t
i
o
nSystemf
o
rL
o
g
i
s
t
i
c
sandManagement , 3
p
.4
7
5
9
.
1, (2007), p
Toyoda , J
.andTakeyasu , K
.
:AR
e
v
i
s
e
dF
i
r
s
tF
i
tA1gorithmf
o
rTimberP
r
e
c
u
t
t
i
n
g
.I
n
t
e
r
n
a
t
i
o
n
a
1
p
.9
2
1
0
7
.
J
o
u
r
n
a
1o
fC
o
m
p
u
t
a
t
i
o
n
a
1S
c
i
e
n
c
e2-1 , (2008) , p
Yuu , Y. , Moon , C. , Kim , D
.andYeoum ,
S. ・ Comparison
o
fA
d
a
p
t
i
v
eG
e
n
e
t
i
cA1gorithmsw
i
t
h
P
o
p
u
1
a
t
i
o
nD
i
v
e
r
s
i
t
y
.The8
t
hAsia-P
a
c
i
f
i
cI
n
d
u
s
t
r
i
a
1E
n
g
i
n
e
e
r
i
n
gandManagementS
y
s
ｭ
2
0
0
7
)
.
temsConference , Kaohsiung , Taiwan(
豊田丈輔:材料取り合わせ問題のための対戦交文法を用いた遺伝的アルゴリズムの提案，大阪府立大
学経済研究，
54-2(2008 予定)
大阪府立大学経済研究
54 ・ 3(225)
(
2
0
0
8
.
1
2
J

Download Report