2.7 重み付き局所探索法(wls)における出力
重み付き局所探索法(wls)を用いた場合には,[Progress]で始まるセクションに探索の情報が以下の順に表示されます.並列化機能の有効・無効の場合で出力が異なります.
開始時
<problem statistics> # Int Vars / Total = 620 / 625 # - 0-1 Vars = 400 # 0-1 Constrs / Total = 150 / 540 # - Set Multi-Cover = 50 # - Set Multi-Packing = 100 # - Set Multi-Partition = 0 # Soft Constrs / Total = 100 / 625 # Var Bounds # - Int Range Max = 12 # - Continuous Range Max = 0 # - Unbounded Vars = 105 # Assignment Labels (V1,V2,E) = (5, 10, 50) <iteration begin> # Initial Sol = given # Obj = 240.00 # (Hard/Soft) Penalty = 54.00 / 430.00
<problem statistics>
では,読み込まれた最適化問題についてWLSの性能に大きく影響する情報が表示されます.具体的には,変数や制約式の中に0-1変数や0-1制約式が多く含まれるほどWLSは高い性能を発揮します.ここで0-1制約式とはすべての係数が0か1である線形な制約式です.0-1制約式は,集合被覆型(例:),集合充填型(例:
),集合分割型(例:
)に分類されます.
<iteration begin>
以降では初期解の情報が表示されます.上の例の場合,ユーザが指定した初期解は目的関数値が240であり,ハード制約違反量は54,ソフト制約違反量は430であると読み取れます.並列化機能が有効のときには,初期解の設定方法が
"zero" と表示されます.
それぞれの項目の意味は次のとおりです.
表示 | 意味 |
---|---|
# Int Vars / Total | 整数変数の個数 / 変数の個数 |
# - 0-1 Vars | 0-1変数の個数 |
# 0-1 Constrs / Total | 0-1制約式の本数 / 制約式の本数 |
# - Set Multi-Cover | 集合被覆型制約式の本数 |
# - Set Multi-Packing | 集合充填型制約式の本数 |
# - Set Multi-Partition | 集合分割型制約式の本数 |
# Soft Constrs / Total | ソフト制約式の本数 / 制約式の本数 |
# - Int Range Max | 整数変数の「上限 - 下限」の最大値 |
# - Continuous Range Max | 連続変数の「上限 - 下限」の最大値 |
# - Unbounded Vars | 上限または下限が設定されていない変数の個数 |
# Assignment Labels (V1,V2,E) | 割当ラベルの二部グラフにおける頂点と辺の数 |
# Initial Sol | 初期解の設定方法 "given": ユーザ指定, "random": ランダム, "zero": ゼロ初期化 |
# Obj | 初期解の目的関数値 |
# (Hard/Soft) Penalty | 初期解のハード制約違反量 / ソフト制約違反量 |
# Workers | 求解する Worker の数(並列化機能が有効のときに表示) |
途中経過
初期解の情報に続き,探索の途中経過が表形式で逐次的に表示されます.現在の実行時間や,現在どういった解を探索しているのか,現在までに見つけた解の中で最も良い解は何なのか,といった情報が読み取れます.
途中経過(並列化機能が無効の場合)
-------------------------------------------------------------------------------------- Resources | Current Sol | Best Sol #Itrs Time(s) Mem(MiB) | Obj Hard Soft | Obj Hard Soft -------------------------------------------------------------------------------------- 1 0.67 250.23 | 688.23 11.00 123.00 | 688.23 11.00 123.00 5 0.75 403.34 | 347.43 3.00 23.00 | 400 0.00 43.00 ... --------------------------------------------------------------------------------------
上の表は,反復が一定回数行われたり最良解が更新されたりする度に行が追加されていきます.解が更新されないと表示の更新も鈍くなりますが,計算は行われています.局所探索法による探索の一般的な性質として,計算の後半には解の更新は鈍くなります.
それぞれの項目の意味は次のとおりです.
表示 | 意味 |
---|---|
#Itrs | 反復回数 |
Time(s) | 実行時間(秒) |
Mem(MiB) | メモリ使用量(メビバイト) |
Current Sol | 現在探索中の解 |
Best Sol | 最良解 |
Obj | 目的関数値 |
Hard | ハード制約違反量 |
Soft | ソフト制約違反量 |
途中経過(並列化機能が有効の場合)
---------------------------------------------------------------- Resources | Best Sol #Itrs Time(s) Mem(MiB) | Obj Hard Soft ---------------------------------------------------------------- 0 0.00 339 | 693091 109672 0 111552 4.00 339 | 3.20247e+07 0 0 sol: worker#2 272215 8.00 339 | 3.10217e+07 0 0 sol: worker#1 ... ----------------------------------------------------------------
上の表は,一定時間が経過する度に行が追加されていきます.
それぞれの項目の意味は次のとおりです.ここで worker#n は,n 個目の Worker を表します.例えば,スレッド数を 4 に設定した場合,worker#1 ~ #4 の 4 つの Worker が並行して探索を行います.
表示 | 意味 |
---|---|
#Itrs | Worker 間の最小の反復回数 |
Time(s) | 実行時間(秒) |
Mem(MiB) | 総メモリ使用量(メビバイト) |
Best Sol | 最良解 |
Obj | 目的関数値 |
Hard | ハード制約違反量 |
Soft | ソフト制約違反量 |
sol: worker#n | 最良解を発見した Worker の番号 |
終了時
========================================= # Obj = 230.00 # (Hard/Soft) Penalty = 0.00 / 4.00 # Elapsed Time (s) = 43.54 / 100.00 # Iterations = 81708 / 191770 ========================================= <iteration end>
アルゴリズムが終了すると実行時間や最良解などの情報が表示されます.上の例の場合,目的関数値230,ハード制約違反量0,ソフト制約違反量4である解が最良解として得られており,アルゴリズムの実行時間は100秒間であったことが読み取れます.
それぞれの項目の意味は次のとおりです.
表示 | 意味 |
---|---|
# Obj | 最良解の目的関数値 |
# (Hard/Soft) Penalty | 最良解のハード制約違反量 / ソフト制約違反量 |
# Elapsed Time (s) | 最良解発見時の実行時間 / 総実行時間 |
# Iterations | 最良解発見時の反復回数 / 総反復回数 |
上に戻る