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

HOMEへ  

Blizzard 詳細へ戻る 

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


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


Q1:基本問題

「 20mmx3本 + 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 )となるので、この局所最適解にはまって割付不能となってしまいます。
アルゴリズム評価の基本問題ですが、これが解けない市販ソフトもありますので要注意です。

その2:

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

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時間以上実行しても、1万本のうちの1本目の材料への組合せ探索が終了しませんでした。 いわゆる「組合せ爆発 」にはまってしまいます。ソフトによっては無応答になってしまうものもありますので要注意です。
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比)。
また探索精度が向上し、全ての問題で最適解からの乖離が1%以下となりました。乖離の最大値は BPP'14 にて0.65%となっております。

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

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

HOMEへ

Blizzard 詳細へ戻る

Copyright © 2008-2010 supermab.com
All rights reserved.