数理最適化セミナーのご案内

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制約式は，集合被覆型（例：$x_1 + x_2 \ge 2$），集合充填型（例：$x_1 + x_2 \le 1$），集合分割型（例：$x_1 + x_2 = 2$）に分類されます．

　<iteration begin>以降では初期解の情報が表示されます．上の例の場合，ユーザが指定した初期解は目的関数値が240であり，ハード制約違反量は54，ソフト制約違反量は430であると読み取れます．

　それぞれの項目の意味は次のとおりです．

表示 意味
# 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 初期解のハード制約違反量 / ソフト制約違反量

　

　

　途中経過

--------------------------------------------------------------------------------------
       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 ソフト制約違反量

　

　

　終了時

=========================================
#  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 最良解発見時の反復回数 / 総反復回数
2.6 分枝限定法における出力
2.8 資源制約付きスケジューリング問題ソルバ（rcpsp）における出力

 

 

上に戻る