最適化セミナーのご案内

15.3.3 制約充足アルゴリズム(wcsp/rcpsp)に有効なパラメータ

 タブー・サーチによる制約充足アルゴリズム(wcsp/rcpsp)は制約をできるだけ充足する解をいずれか一つ求めるという手法で,厳密な最適解を求めるものではありません.

  • 反復回数上限
    停止条件の一つである,反復回数上限を設定します.初期設定値-1は,無制限を意味します.
    モデルファイルに記述する方法
    options.maxitn = -1;
    パラメータファイルnuopt.prmに記述する方法
    crit:maxitn=-1
  • 計算時間上限
    停止条件の一つである,計算時間上限を設定します.初期設定値-1は,無制限を意味します.
    モデルファイルに記述する方法
    options.maxtim = -1;
    パラメータファイルnuopt.prmに記述する方法
    crit:maxtim=-1
  • 制約式の重み設定
    パラメータdefaultConstraintWeightを用いると,モデルファイルで出現する制約式全てに一律に重みを設定できます.次の例では,一律に重み12のソフト制約を指定しています.defaultConstraintWeightの値は,モデルファイル内でのみ設定できます.
    モデルファイル内
    options.defaultConstraintWeight = 12;
    defaultConstraintWeightに0を設定すると,ハード制約として扱われます.defaultConstraintWeightの初期設定値は0です.
    defaultConstraintWeightConstraint関数(hardConstraint関数,semiHardConstraint関数,softConstraint関数)が競合した場合,後者が優先されます.
  • 目的関数の重み設定
    目的関数の重みはパラメータdefaultObjectiveWeightで指定します.defaultObjectiveWeightの値は,モデルファイル内でのみ設定できます.次の例では,目的関数の重みに5を指定しています.
    モデルファイル内
    options.defaultObjectiveWeight = 5;
    パラメータdefaultObjectiveWeightの初期設定値は1です.
  • 目的関数の目標値設定(wcspのみ
    目標値targetの値は,パラメータdefaultObjectiveTargetで指定することができます.
    options.defaultObjectiveTarget = 5; // wcspのみ有効
    Objectiveの引数でのtarget値と,パラメータdefaultObjectiveTargetの値が競合した場合は,Objectiveの引数の値の方が優先されます.目標値targetの初期設定値は0です.このパラメータはrcpspには無効です.
  • 初期解生成時に使用する乱数発生の種
    初期解生成時に使用する乱数を発生するための値(種)を指定することができます.メタヒューリスティクス解法では初期解が最終的に得られる解の精度に影響することが知られており,初期解を変更することによって,より良い探索を行うことが期待できます.乱数を発生するための値はwcspRandomSeedで指定することができます.
    options.wcspRandomSeed = 3;
    初期解生成時に使用する乱数発生の種の初期設定値は1です.
  • 計算回数
    上記wcspRandomSeedで述べた通り,初期解を変更することによって最終的に得られる解が変化することがあります.初期解生成時に使用する乱数を変更し何回か解くことによって解の精度を向上することが期待されます.計算回数はwcspTryCountで指定することができます.
    options.wcspTryCount = 5;
    計算回数を複数回に設定した場合には,初期解生成時に用いる乱数を変更し,指定した回数求解を行い,その中で最もよい結果を自動的に残します.計算回数の初期設定は1です.
  • スレッド数の上限(wcspのみ
    WCSPはマルチコア環境において並列処理を行うことにより,異なる初期値からの解の探索を効率的に行うことができます.スレッド数の上限はwcspthreadsで指定することができます.
    options.wcspthreads = 8;
    計算回数はwcspTryCountオプションで設定することができますが,バージョン14までは1つのスレッド(1つのコア)しか使えなかったため,1回の計算に10秒かかるような問題の場合,wcspTryCount×10(秒)の計算時間がかかります.
    一方,本オプションに2を設定しますと,計算を2つのスレッドで同時に行いますので,wcspTryCount×10(秒)/2(並列)と,約半分の時間になります.(ただし,実行PCに指定スレッド数以上のCPU(コア)が搭載されている必要がございます)
    本オプションのデフォルト値は1ですので,並列化を有効にする場合は2以上の値を設定してください.なお,並列化を実行する場合「10.5分枝限定法・制約充足問題ソルバwcspの並列化」を参考に実行形式を作成する必要がございます.
  • 制約充足フェーズにおける計算時間上限
    制約充足フェーズ(ハードペナルティ及びセミハードペナルティが残っているフェーズ)における計算時間上限はwcspPhaseOneMaxtimeで指定することができます.
    options.wcspPhaseOneMaxtime = 60;
    -1を設定した場合,無制限と解釈されます.wcspPhaseOneMaxtimeの初期設定は-1です.
    wcspPhaseOneMaxtimeに値を設定した場合,ハード・セミハードペナルティが0になるか設定した時間が経過した時点で経過時間をリセットし,そのあとでmaxtimで設定した時間解の探索を行います.経過時間をリセットした後の探索は,ハード・セミハードペナルティのそれ以上の改善よりも,ソフトペナルティの改善を目指して行われます.
    ある一定の時間が経過した後にハード・セミハードペナルティが改善することはないとわかっている問題に対してwcspPhaseOneMaxtimeを使用することで,よりソフトペナルティの小さい解が得られる可能性があります.
  • 解更新間隔計算時間上限
    解が更新されてから指定した時間が経過すると計算を終了します.大規模問題では計算時間の設定は非常に難しいのですが,この機能を用いると簡単に有用な求解を行うことができます.解更新間隔計算時間上限はwcspPhaseTwoMaxIntervalで指定することができます.
    options.wcspPhaseTwoMaxInterval = 5;
    -1を設定した場合,無制限と解釈されます.解更新間隔計算時間上限の初期設定は-1です.
  • 指定した初期値からの探索(wcspのみ
    ユーザ指定による初期値からwcspの探索をスタートするか否かを指定ことができます.
    options.wcspInitialValueActivation = "on";
    本オプションのデフォルト値は"off"ですので,ユーザ指定による初期値から探索をスタートする場合は"on"を設定してください.なお,tryCountで計算回数を2以上に設定した場合,全ての回においてユーザ指定による初期値から探索を出発します.また,離散変数(DiscreteVariable)を含む場合は指定は無視され自動で"off"となります.

 

 

上に戻る