supermab.com 　　HOME　＞　Blizzard　＞　探索アルゴリズム評価用の例題

HOMEへ　　

Blizzard 詳細へ戻る　

探索アルゴリズム評価用の例題

---

Blizzard を公開／販売するにあたり、ネットから世界中のフリー／商用の材料取りソフトを入手・評価したところ、当然のことなのですが全てのソフトで最適解を得られない、 あるいはフリーズ等のトラブルに陥る問題が存在しました。また、非常に歩留まりが悪くお粗末な解を出力するソフトがほとんどでした。
一旦ソフトウェアを導入するとこれを完全に信頼してしまい、無駄に気付かない状況に陥ってしまう危険がありますので、
ソフトウェアの導入にあたっては、充分に性能を評価する必要があります！
もしすでに材料取りのソフトウェアをお使いなら、このページの問題を解いてみることを強く推奨いたします。
Hard28 で最適解を得られたなら、超一流のソフトと言えるでしょう。もし、解けるソフトが見つかったら・・・是非、教えてください。

---

Q1:基本問題

「 20mmｘ3本 + 30mmx3本 + 40mmx3本を、100mmx3本の材料から切り代2mmで切出すには？」
これを表にすると下のようになります。

【切代=2】

符号	長さ	本数
A	20	3
B	30	3
C	40	3
材料	100	3

解は、100mmの材料3本それぞれに、20,30,40mmのワークを各1本ずつ割り付ければ良いので( 簡単ですね )下記のようになります。

【切代=2】

材 料	ワーク
100〜3本	20(A)x1	30(B)x1	40(C)x1	残=4

一見簡単な問題ですが、欲張り法でこれを解いた場合、初めの材料に対して　20x3本 + 30x1本 を割り付けた時に、 残が最小 ( 100 - 22x3 - 32x1 = 2 )となるので、この局所最適解にはまって割付不能となってしまいます。
アルゴリズム評価の基本問題ですが、これが解けない市販ソフトもありますので要注意です。

その２：

Seek で全件探索してもほんの一瞬で終わるような問題ですが、ソフトウェアのテスト用に２つ載せておきます。
次の問題が割りつけられないソフトは、アルゴリズムが幼稚なソフトウェアと判ります。

2012’7/25 切代の設定を訂正いたしました。

職人さんには簡単な問題 【切代=0】 符号 長さ 本数 A 696 2 B 608 1 C 551 2 D 364 1 E 300 3 F 185 1 G 130 3 材料 1000 5 もし6本必要になると、 材料費が20％無駄になります。

職人さんでも厳しい問題 【切代=0】 符号 長さ 本数 A 2300 8 B 1870 3 C 1850 4 D 1350 3 E 1250 2 F 800 4 G 300 9 材料 5500 8 もし9本必要になると、 材料費が12.5％無駄になります。

欲張り法アニメーション

---

Q2:実用問題

「 表の A 〜 J の各ワークを、5500 の材料 517本に割付るには？」

【切代=2】

符号	長さ	本数
A	2300	500
B	1870	200
C	1850	300
D	1270	270
E	800	157
F	723	254
G	302	50
H	300	2
I	250	240
J	125	4
材料	5500	517

この問題も Q1 と同じく局所最適解にはまりやすい性質の問題です。
ソフトのアルゴリズムによっては10本以上もの材料を余計に要求する場合があります。
Blizzard が出力した解の一つが下記のものです。

切代 =2 で計算しました
5,500 〜 158本	2,300(A) x 1	1,850(C) x 1	1,270(D) x 1	残＝74
5,500 〜 1本	2,300(A) x 1	1,850(C)　x 1	723(F) x 1	250(I) x 2	残＝117
5,500 〜 157本	2,300(A) x 2	800(E) x 1	残＝94
5,500 〜 8本	2,300(A) x 2	723(F) x 1	残＝171
5,500 〜 2本	2,300(A) x 1	723(F) x 1	302(G) x 3	300(H) x 1	250(I) x 5	残＝1
5,500 〜 1本	2,300(A) x 1	723(F) x 3	250(I) x 4	残＝15
5,500 〜 4本	2,300(A) x 2	723(F) x 1	125(J) x 1	残＝44
5,500 〜 112本	1,870(B) x 1	1,850(C) x 1	1,270(D) x 1	250(I) x 2	残＝切代
5,500 〜 44本	1,870(B) x 2	723(F) x 2	302(G) x 1	残＝2
5,500 〜 29本	1,850(C) x 1	723(F) x 5	残＝23
5,500 〜 1本	723(F) x 3	残＝3,325
歩留=98.72%

---

Q3:規模の問題

下記の30種類ほどのワーク約10万本を、1万本の材料から取る組合せを求める問題です

【切代=2】

符号	長さ	本数
1	5656	2000
2	5582	2000
3	5545	1200
4	5439	1100
5	5177	1100
6	4746	2200
7	4143	2200
8	3898	1500
9	3889	2000
10	3568	2200
11	3169	1200
12	2594	3600
13	2160	1200
14	1911	3600
15	1877	9100
16	1779	700
17	1614	9900
18	1563	4500
19	1183	4500
20	1024	1500
21	932	1500
22	769	9100
23	595	700
24	563	3600
25	388	700
26	261	4500
27	244	9100
28	233	1100
29	167	9900
30	97	9900
材料	30266	1000
	27419	1000
	26354	1000
	18652	1000
	18267	1000
	13559	1000
	13056	1000
	11941	1000
	8790	1000
	1938	1000

長い材料に短いワークを割りつける場合、組合せが膨大になり計算時間が大きくなってしまいます。
全件探索の Seek でこの問題を探索すると8時間以上実行しても、１万本のうちの１本目の材料への組合せ探索が終了しませんでした。 いわゆる「組合せ爆発 」にはまってしまいます。ソフトによっては無応答になってしまうものもありますので要注意です。
Blizzard で探索すると 約30秒 で解を得ます。（ ※ CPU：Intel Core2-Quad 2.2GHz 搭載のパソコンにて実行時）

---

Q4:「Hard28」

切り出し問題は学術的には、Cutting Stock Problem（CSP）と呼ばれ、詰め込み問題と等価とされています。
詰め込み問題は、Bin Packing Problem（BPP）と呼ばれ、世界的に通用する「Hard28」という有名な28個の難問があります。
「Hard28」は　J. E. Schoenfieldという方が2002年に発表したもので大学の研究室レベルでも最適解を得ることが難しいものだそうです。

こういった難問は、問題を解析しアルゴリズムやパラメータをチューニングした専用のプログラムを作成して解くのが普通で、
汎用のソフトで挑むのは無謀なのですが、Blizzard の客観的な性能評価のために「Hard28」を解いてみました。
ver1.00およびver1.03の試験結果は、結果は下表のとおりです。
Shortage は不足長さ、Yield は歩留まり（％）、time は実行時間（秒）を示します。

　　　

Blizzard ver1.00 (at Core2 2.2GHz) Shortage Yield(%) time(sec) BPP' 14 417 99.24 7.2 BPP'832 340 99.4 7.4 BPP' 40 73 99.84 7.6 BPP'360 538 99 6.9 BPP'645 102 99.81 6.5 BPP'742 730 98.75 6.8 BPP'766 358 99.35 8.2 BPP' 60 411 99.25 8 BPP' 13 669 98.94 7.6 BPP'195 133 99.78 7.8 BPP'709 104 99.82 8.1 BPP'785 134 99.77 8.8 BPP' 47 844 98.64 7.7 BPP'181 494 99.22 8.9 BPP'359 577 99.03 8.9 BPP'485 376 99.39 8.7 BPP'640 733 98.87 8.8 BPP'716 654 98.92 8.2 BPP'119 399 99.44 10.9 BPP'144 167 99.76 10.7 BPP'561 108 99.84 10.9 BPP'781 143 99.79 9.7 BPP'900 958 98.69 10.4 BPP'175 1299 98.34 11.4 BPP'178 334 99.49 11.5 BPP'419 372 99.48 11.5 BPP'531 452 99.26 10.3 BPP'814 1121 98.39 10.0

Blizzard ver1.03 (at Core2 2.2GHz) Shortage Yield(%) time(sec) BPP' 14 390 99.28 3.5 BPP'832 340 99.4 3.8 BPP' 40 73 99.84 3.8 BPP'360 410 99.21 3.7 BPP'645 102 99.81 3.2 BPP'742 343 99.36 3.7 BPP'766 319 99.42 4.2 BPP' 60 411 99.25 4.3 BPP' 13 374 99.38 4 BPP'195 89 99.78 4.2 BPP'709 81 99.86 4.3 BPP'785 123 99.79 4.8 BPP' 47 423 99.24 4.4 BPP'181 372 99.39 4.8 BPP'359 391 99.28 5.2 BPP'485 371 99.4 4.7 BPP'640 408 99.31 4.8 BPP'716 337 99.34 4.7 BPP'119 399 99.44 5.7 BPP'144 105 99.85 5.6 BPP'561 77 99.88 5.6 BPP'781 143 99.79 5.1 BPP'900 491 99.31 5.4 BPP'175 592 99.19 6.0 BPP'178 334 99.49 6.1 BPP'419 290 99.59 6.1 BPP'531 352 99.38 5.9 BPP'814 517 99.13 5.7

結果（ver1.03）：処理速度が大幅に向上し、全問題について40％以上の高速化を実現しております（ver1.00比）。
また探索精度が向上し、全ての問題で最適解からの乖離が１％以下となりました。乖離の最大値は BPP'14 にて0.65％となっております。

実務で使用するソフトウェアが、ある問題で最適解を得られても、別の問題では極端に歩留まりが悪い解を出力するようでは困ります。
どんな問題でもコンスタントに高精度な解を得られなければ実用にはなりません。
そのためあらゆる種類の問題でテストする必要があるわけですが、良い（？）問題を入手すること自体が難しい事なのです。
じつは「Hard28」についての情報は、組合せ最適化を研究しておられるサイトユーザーさんから教えていただいたものです。
メールで頂いた難問に初めはびっくりしましたが、この方とは現在某SNSでお友達になっていただきました。
アルゴリズムの開発にあたって、難問は欠かすことのできない貴重な資料です。この場をお借りして改めてお礼申し上げます。

※：「Hard28」は ドレスデン大学のサイト からダウンロードできます。

HOMEへ

Blizzard 詳細へ戻る