2次
元取合せ問題 に対す る遺伝 アルゴ リズムの適用
平 山
克 己
・ 。河合
*社
会開発工学専攻 。社会開発 システムエ学科
(1994年8月29日受理)A Genetic Algorithni for Solving 2‐
Dimensional Packing Problem
by
Kastumi HIRAYAMAl),Haiime KAWAIう
1)Course in Engineering of Social Development
2)Department of Social Systems Engineering
(Received August 29,1994)This paper discribes a neⅥ/approach to solve the two dimensiOnal packing prOblem
which is knowh as NP‐ complete(Non‐ deterministic P01ynomial)problem Of two dimensional geometOry We prOpose an approach applying Genetic Algorithms in
order to guide a search procett effectively and Obtain a near‐ optimal aHocation. Genetic Algorithms are search algorithms based on the mechanics of survival and randoHlized information exchange,Packing method is controlled by evaluation func‐ tions which describe the selecting a bOx and space allocation.Genetic operators are apphed to bit strings and combined the、veighted coefficients of evcaluation items.
1。 まえが き 複数の図形を2次元領域 に適当な制約 の もとに配置 し たいとい う要求 は、様 々な場面で発生す る。
VLSIの
レイア ウ ト、建築 や都市計画の レイアウ ト、布地・ ガラ ス・鉄 などの効率的裁断な どはすべて このよ うな配置間 題の一種である。l' これまで、オペ レー ションズ・ リサーチ(OR)の
分野 では、組合せ問題 に対 して様 々な最適化手法 が提案 され て きた。 しか し、要素数が非常 に多い実問題 を求解す る 際 には、従来の最適化手法では多大な計算時 間がかか り 実時間内で答えを求 めることは実際 には不可能であ った。 しか し、今 日の計算機の目覚 ま しい発達 によ り、要素数 が非常 に多い組合せ問題 に対 して、最適解で はな くとも ある程度良質な解を求めることが望 まれ るよ うにな って きた。 このよ うな状況 の中で、近似解法 によって非常 に難 し い問題 の近似解 を求 めるアプローチが生 まれた。最近 の 代表的な近似解法 と しては、ニュー ラル・ コ ンピューテ ィング、 シ ミュ レーテ ィ ド・ アニー リング、遺伝 アルゴ リズムな どが挙 げ られ る。 本研究では配置問題 に対 して「 生物 の進化 の法則」を 模倣 した優れたアルゴ リズムである遺伝 アル ゴ リズムを 適用 し、組合せ問題 への新 しいアプローチを試みる。 ま た、数値実験 を行 うことによ り、その有効性 を検証す る。 取合せ問題 に遺伝 アルゴ リズムを適用 した例 としては、 3次元箱詰問題 に関す る研究=】と して川上 らによって報 告 されている。本研究 はこの研究の2次元の場合であ り、 基本的には同様の考 えにより、遺伝7″]´リス・ムを適用 して ヽヽる。 但 し、本研究で は この3次元箱諸問題 では考慮 されて いなか った板の向 きを9o度
回転 した場合について も考 慮 し、よ リー般的なアプローチをめ ざしてい る。90度
回転を許 した場合、組合せ数は元の問題 の組 合せ数 に2 の(板枚数)乗倍 した大 きさにな り、複雑 にな る。そこで 本研究では、板の縦横を遺伝子 によ り決定す ることによ り、板枚数が増加 した場合で も、探索範囲をある程度限 定 しなが ら探索す る方法を提案 し、4章の数値実験ではCASE3で
その有効性を示す。2.遺
伝 アルゴ リズムの概要 遺伝アルゴ リズムは、1960年代にアメ リカのホー ラン ドによって基本的な考え方が提唱 されたアル ゴ リズムで ある。 この章では遺 伝7″コ'リス'ムの概要 について説明す る。 図1
板取 り問題 の コーデ ィングの例 遺伝 アルゴ リズムは図1に示す よ うな遺伝子 と呼ばれ る数字 もしくは文字列か らな り、その複数 の数字列を最 適化問題であればある解候補 に変換す る。 この変換 は一 般的にコーデ ィングと呼ばれ る。 初期個体群(t=0) 遺伝子変換
適応度 個体1 010101000 f(遺 伝子
1)56
個体2 110101000 f(遺伝子2)34
個体n olo101000 f(遺伝子n)14
t=t+1
表現 型 y 板取 り 適応度80 遺伝子x 0110101010裾
襟
￨￨￨￨￨1帯
￨￨￨￨ I個 体i'lHll:1111 :
t口と
F!∼P,,PP_i蝉
___」 t世代 個体群 110111000 110111000 図2
遺 伝 アル ゴ リズムの概 要また、遺伝子 を何 らかの解 に変換 した ものを表現型 と 呼び、 これ らの遺伝子 と表現型が1対 1対 応 もしくは、 1対 多対応す るよ うにコーデ ィングした ものを個体 と呼 ぶ。各個体 はそれぞれの表現型か ら適応度 と呼ばれる評 価関数値を計算す ることがで きる。 遺伝 アルゴ リズムは図2のよ うに、まず、複数の個体 か らなる初期個体群 と呼 ばれ る初期解 を生成す る。 この 初期解 は ランダムに生成 して も、他の手法 によ り生成 し て も良 い。 これ らの初期個体か ら交叉、突然変異等の遺 伝子演算 と呼ばれ る演算 をす ることにより、次の世代の 個体を生成す る。 ここで、図2では交叉 は一点交叉、突 然変異 は一点逆位の例を示 している。 この他 に も様々な 交叉、突然変異の方法が提案 されてお り、問題 に適 した 遺伝子演算を用いることがで きる。 t世 代 に生成 された個体 と元の個体 は淘汰 され、適応 度の高い個体だけが
t+1世
代 に生 き残 る。 この処理を 規定の世代数だけ繰返す ことによ り、良 い解だけが次世 代 に継承 され る。3.二
次元板取 り問題への遺伝7″]・リス・ムの適用 問題 の記述 を以下 に行 う。 人物 となる大板の寸法:DB=(V,と) 板群の個数in
板群の各小板の寸法 :D8J=(■ ,,1,)(j=1、 2、…n) ここで、入物 とな る大板を一つの隅が原点 に当るよ うに X,Y座標内に設定す る。 また、 面積率(=適
応度) :R=IΣ
(wJ・lJ)/(Y,と)' 選択 された板の枚数:m
とす る。 ここで、W、 Lは大板 の幅、長 さ wJ、 lJは小 板の幅、長 さを表す。 本研究の目的は この面積率を最大 にす る様な小板の選 択順 と小板の配置位置を決定す ることである。 (1)小板選択方法 板の選択 にはグ リーデ ィアルゴ リズム3)を採用する。 これは、最適化問題 を解 くとき、計算の各段階で最 も利 益の大 きい部分解を選 びなが ら計算を進 め、それ らの部 分解を合わせた ものを最終的に解 にす る技法のことであ る。 この手法 はあ る金額 を何種類かの紙幣 と硬貨で用意 す るときのよ うに、おそ らく種 々の状況下で我々が無意 鳥 取 大 学 工 学 部 研 究 報 告 第25巻
211 識の うちに用いている素朴 なアルゴ リズムである。 した が って、人間の考 え方 によ く似てお り、板取合せ問題 に おいては大 きな板か ら先 に積めてい く方法である。 この 考 え方を用 いて次 の評価関数Qを最大 とす るよ うな小板 を選択す る。Bt=(BJ i naxQょ
)QJ =eド
f:(v,,1,)■e3・f3(Wl,1,) (1)
(3=1,2,・・m) ここで、B,は板群の中のJ番目の板、fI、f4は 1)大板形状 との非相似度:fi(w,,lJ)=(vj/V)B+(1,ん)を 2)板の大 ききの度合 :fB(vj.1,)=(▼ j・11)/(V・L)'elヽ e2は重 み付 けパ ラメータであ り、e:がe2よりも大 き い場合、FIの非相似度項が小板選択 に強 く影響 し、大板 と非相似形の小板が選択 されやす くなる。逆 に、elがeB 小 さい場 合、fBの項 が小板選択 に強 く影響 し、面積の大 きい小板 が選択 されやす くなる。 (2)配置位置選択方法 小板が 1つ 配目 され る度 に新 しい配置位置候補の集 合 を次 の手続 によ り更新す る。 例 えば、配置位置(X,V)にk番目の小板、中vi、長 さ1と が配置 されたとす る。 この時、k-1番目の配置位置候補の
集合に2点 (X+wi,V)、 (X、Y+l.)を追加 し、(X,Y)を削除す
る。 したが って、k番目の配置位置候補の集合の要素数 はk個とな り、1番目の板の配置位置候縮 は1(0,0),であ る。
配置位置候補の中か ら配置位置を選択す る関数 は
(xt,v4)=((xk,yx)l min PH)
Ph t e3・X■B■e4・ yゝ= (k=1,2.・・m) (2)
とす る。そ して、配置位置候補 の集合の全要素 について Pを求 め、最 もPを最小 にす るような配置位置(x.,yk)を 選択す る。 選択 された配置位置(x.,yL)に、(1)式の板選択関数 に より選択 された小板が配置可能 かどうかを調べ、配置可 能であれば配置 し、その配置位置候補を配置位置候補集 合の要素か ら削除す る。 また、板群の中か ら選択小板 を 削除す る。選択 された配置位置 に選択 された小板が配置 不可能であれば、小板選択の操作を再帰的に繰 り返 し、 配置可能 な小板を(1)式の板選択関数 によ り探索す る。板 群 におけるすべての小板が配置不可能であれば、他 の配 置候補点 を(2)式の配置位置選択関数 によ り再帰的 に探索 す る。
また、es、 e4は重 み付けパ ラメータであ り、e3がe4よ
位置選択関数の値が小 さい ものを選おゞ傾向が強 く表れる。 逆 に、e3がe4より小 さい場合、Y学山方向よ りの配置位置候
補の中か ら配置位置選択関数の値が小 さい ものを選ボ傾 向が強 く表れる。 このよ うに重 み付 けパ ラメータの値が変化す ることに よって、選択 され る小板 の配置順 と配置位置が変化 し、 最終的に取合せ結果 も変化す る。 そこで、本研究で は、 これ らe:∼ e4の 4つのパ ラメー タを送伝 アルゴ リズムを用 いてチュー エングす ることに より面積率 を最大 とす るような小板 の配置順 と配置位置 を求 める。 この時 、el∼e llよそれぞれ、4ビッ トの二進 数(0■)で表す。それ らをつなげた形で1本の ス トリング を表現 し、次のSよ うな
16ビ
ッ トの二進数で表 され る。S,= el e2 e3 e4
個体1 0101101010100100
個体2 1010001001001100
個体n oolo l100 1000 0101 ここで、pは個体番号(p=1,2・… れ) また、本研究では、小板を90度
回転 さす ことによっ て、小板 の幅 、長 さをいれかえ ることを許 した場合を考 える。90度
回転を許 さない場合を5章のCASElで
数値実験 を行 うことによ り、e:∼ etのパ ラメータチュー ニングを遺伝アルゴ リズムによって行 った場合の評価を イ子う。 次 に、90回
転を許 した場合についてCASE2、
3 で考 える。CASE2で
は小板の縦横 の選択 は小板選択 関数Qだけで行 い、CASE3で
は、先 に述 べたe:∼ e 4の他 にi番目に配置 され る小板 の縦横を0-1の二進数で 表 し、次のように遺 伝子Sにつけ加 え、小板 の縦横を遺 伝子 によって選択す る方法を提案 した。個体
n
七
!!!!!!!!!!O!!!!_」七
!!!二二
!■ !_…」
突然変異 は独立 して行 うよ うに した。4.数
値実験 本研究 では、グ リーデ ィアルゴ リズムのバ ラメー ター チューニ ングに遺伝 アルゴ リズムを適用 した次の3ケー スについて、一様乱数により生成 したデータ 1と 人間が 実際 に大板か ら生成 したデータ2の2種類を用 いて シ ミ ュ レー ションによ り実験 を行 った。CASEl
入カデータの90度
回転を許 さず、ク'り∼テ・ 17″ ]'リス・ム+ 遺伝アルゴ リズムを用 いた板取 りCASE2
入カデータの90度
回転 を許 し、縦横両方のデータを 用意 して板選択評価関数Bを求 めるク´リーテ'17″」・ リス・ム +遺伝 アルゴ リズムを用 いた板取 りCASE3
入 カデータの90度
回転を許 し、夕・リーテ'17″」´リス・ム十 遺伝子 によ り縦機の板の配置を決定す る遺伝 アル ゴ リ ズムを用いた板取 り 実験 デー タ くデータ1>
くデータ2>
〈遺伝7'ゴ リス´ムのA・ラメサ〉 個体数i20
世十ヽ数i 50
くデー タ2>
幅 長 枚 7 7 10 14 16 18 20 4 S 8 1 2 3 4 5 6 7 8 9 10 3 A・ラメツ決定す る部分 縦横を決定す る部分ど
F`と
ξ
:今
:ξ
営
吾
￨:と
書
ri:融
)1姜kぁ異
買
はPMX法
、突然変位 は逆位、淘汰はエ リー ト保存戦略 を用 いた。但 し、CASE3の
小板 の縦横を選択す る遺 伝子 とパ ラメーター チューニ ングを行 う遺伝子の交叉や 幅 長 枚 幅 長 枚 1 2 3 2 5 6 3 6 1 4 3 6 1 2 3 4 3 1 3 1 2 1 3 3 1 3 2 2 1 3 3鳥 取 大 学 工 学 部 研 究 報 告 第
25巻
5。 実験結果 以下に各cASEの
取 合せ結果(各世代 における最 も適 応度の高か った個体の取合せ結果)を示す。 (1)データ1を用 いて シ ミュレー ションを行 った場合CASEl
O世代目で面積率100%と な った。板取 合せ結果を図3に 示す。 510152025S03540 図8 CASE2の
1世代 目の取合せ結果 (2)データ2を用 いて シ ミュ レー ションを行 った場 合CASI,I
O世代目で面積率948%、 50世代目で面積率990%となっ た。板取 合せ結果を図9,10に示す。 また、入カテ生夕の縦 横を入替えて計算 した結果を図11に示す。 この場合0世代 目か ら解 の改善 は見 られなか った。 5 10 15 20 23 30 35 40 5 10 C 目ASE2
0世代 目で面積率925%.10世代 日で面積率955%.50世代 で面積率985Xと な った。板取 合せ結 果 を図4∼6に示す。 Ａ Ｃ ｍ Ａ ０ 図 図9 CASE
5 10 15 1の0世代 日の取合せ結果 20 25 30 35SE2の
0世代 目の取 合せ結果 1520253035CASE2の
lo世代 目の取合せ結果 10 15 20 25 30 38 5 10CASE3
0世代 目で面積率995%,1世代 目で面積率100%と な った。 0,1世 代 目の板取 合 せ結 果 を図7,81こ示 す。 図1l cASElの
縦 脱を入れ瞥えた取合 世紺果CASED
O世代 日で面積率41,0%,6世 代 目で面積率730%,21世代 目で面積率90o%とな ったが、21世代 目か ら解 の改善 は見 られなか った。板取合せ結果を図12∼ 14に示す。 図 10 6SEl
16 のhO世代 目 の 取 合 世結 果202g3035
図 5 5 図3 CASElの
取合せ結果 5 10 15 20 25 30 35 40 図6 CASE2の
50世代目の取合せ結果 5 1o 15 20 25 5 1o 15 20 25 30 3S 図12 CASE2の
0世代 目の取合せ結果 図7 CASE3の
0世代 目のの取合せ結果各ケースの世十ヽ推移による面積率の変化
CASE3
0世代で面 積率970%か ら15世代 で100%と改 善 された。 0,9,15世 代 の取 合せ結 果 を図15∼ 17に示 す 。 5101520網 303540 図17 CASE3の
15世代目の取合せ結果 データ2での、各CASEの
世代の難移 による適応度 の変化の様子 を図18に示す。 図18 デー タ2のIII代おける面積率 のlll移6.考
察 実験結果か ら、CASE3の
90度回転を遺伝7,1・ リスタム の遺伝子 によ り決定す るア″」・リスイムの有効性が検証で きた。CASElの
ク・リーテ・17″ユコリス′ムと遺伝 アルゴ リズムだけ では、板 の90度
回転を許 していないが、データ1では 問題な く面積率をloo%にす ることがで きた。 これは入物 である大板面積 に対 して、投入す る板 の総面積が十分 あ る場合には有効であるが、デー タ2のよ うに大板の而職 に対 して投入す る板の総面積が同 じであるバズルのよう なような問題 の場合、90度
回転を許 されないアルゴ リ ズムでは、図11のよ うに良 い結果が得 られたミい とい うこ とが判 る。CASE2で
はデータ1の場 合、 まず ますの結果が得 られたと思 う。今回の実験 では世代数を50まで としたが、 もう少 し世代数を増やせば面積率100%にな る可能性 は大 きい。 しか し、cASElよ
りも悪 い結果がでた原因 と しては、90度
回転を計 したため、れTの探索範141が広が り仮選 '(lXl数 だけでは効率的な探索が行えなか ったこと を図4∼6が示 していると考え られ る。 また、データ2では、図12∼14が示す よ うに、毎回板 を選択す る時、縦横同 じ向 きの板 を選択す る傾向がある。 これは各板 に対 して縦向 き、横向 き両方の板選択関数の 評l 値を持 ってお り、その評lh市1の 大 きい板か ら '選 択す るため遺 伝アルゴ リズムによる重み付けバ ラメータのllj に対 して縦横を選択す る自由度 を逆 に失 っていると考え らオιる。CASE3で
は予想以上 の結 果が得 られた。 この理由 として、板選択関数 よ りも、縦 横を決定す る遺伝 アルゴ リズムによる探索能力の強靭 さが上 げ られる。 また、9o度
回転 を許 した場合、CASE2の
アルゴ リ ズムが縦横の選択 の自由度を失 っているのに対 して、遺 図13 CASE2の
6世代 目の取合せ結果 図14 CASE2の
21世代 目の取 合 せ*き果 図15 CASE3の
0世代 目の取合せ結果 図16 CASE3の
9世代 目の取合せ結果鳥 取 大 学 工 学 部 研 究 報 告 第
