複数の異なるコストでシミュレーテッドアニーリングの受入確率関数を設計するにはどうすればよいですか？

Question

私はsimulated annealingを使用して、NP完全なリソーススケジューリング問題を解決しています。各タスクの候補発注については、いくつかの異なるコスト（またはエネルギー値）を計算します。いくつかの例があります（具体的な内容はおそらく問題とは関係ありませんが）。

• global_finish_time：スケジュールが跨る合計日数です。
• split_cost：他のタスクの中断により各タスクが遅延される日数。これは、タスクが開始されると中断されるのを防ぐためのものです。
• deadline_cost：逃した各期限が過ぎた二乗日数の合計。

伝統的な受理確率関数は（Pythonで）次のようになります。私はに結果を養うことができるように

def acceptance_probability(old_cost, new_cost, temperature): 
    if new_cost < old_cost: 
     return 1.0 
    else: 
     return math.exp((old_cost - new_cost)/temperature) 

これまでのところ私は、単にそれらを追加することによって、一つに私の最初の二つのコストを組み合わせていますacceptance_probability。しかし、私が本当に望むのは、global_finish_timeよりも常にdeadline_costが優先され、global_finish_timeがsplit_costよりも優先されるということです。

私の質問は、スタックオーバーフローです：複数のエネルギーを考慮に入れるが、常に最初のエネルギーを2番目のエネルギーよりも重要と考えるなど、受け入れ確率関数を設計するにはどうすればいいですか？言い換えれば、私はold_costとnew_costをいくつかのコストのタプルとして渡したいと思い、妥当な値を返します。

編集：これは異なる単位を持つコストコンポーネントと他の多くの困難を作成していても、私は私のために十分に働く唯一の方法は、マイクDunlaveyの提案であると結論している提案された解決法を試してから数日後 。私は実際にはリンゴとオレンジを比較することを余儀なくされています。

だから、私は値を「正規化する」ために多少の努力をしました。まず、deadline_costは平方和であるため、指数関数的に増加し、他の成分は直線的に増加します。これに対処するために、私は平方根を使って同様の成長率を得る。次に、コストの線形結合を計算する機能を開発しましたが、それまでに見られた最高コスト要素に応じて係数が自動調整されます。

たとえば、最高コストのタプルが（A、B、C）で、入力コストベクトルが（x、y、z）の場合、線形結合はBCx + Cy + zです。そうすれば、高いz値が得られても、x値1より重要なことは決してありません。

これは、新しい最大コストが発見されたときにコスト関数に「ジャギー」を作成します。例えば、Cが上がると、与えられた（x、y、z）入力に対してBCxとCyの両方が高くなるため、コストの差も生じます。より高いコスト差は、あたかも温度が急激に低下したかのように、受入れ確率が低下することを意味する。実際には、これは問題ではありません。なぜなら、最大コストは最初に数回更新され、後では変更されないからです。コストがより低い値に収束することがわかっているので、理論的に正しい結果に収束することが理論的に証明されていると私は信じています。

私がやや混乱していることの1つは、最大コストが1.0以下、たとえば0.5となったときに起こることです。 （0.5,0.5,0.5）の最大ベクトルでは、これは線形結合0.5 * 0.5 * x + 0.5 * y + zを与える。優先順位が突然逆転します。私はそれに対処する最良の方法は、係数が常に同じ（つまり、100x + 10y + z）になるように、すべての値を与えられた範囲にスケールするために最大ベクトルを使用することです。しかし、私はまだそれを試みていない。

Answer 1

mbeckishです。

さまざまなエネルギーを線形結合して係数を調整できますか？

可能性としてログインとアウトを変換しますか？

私はMetropolis-Hastingsを使用してMCMCを行っています。その場合、私は特定の州の（正規化されていない）対数尤度を定義しています（その前任者を前提とします）、私は自分の思考を明確にする方法を見つけます。

Answer 2

「優先順位」が意味することによって異なります。 たとえば、deadline_costが0.001でダウンしたのに、global_finish_timeのコストが10000まで上がるとどうなりますか？ deadline_costが減少し、それが他の何よりも優先されるため、1.0を返しますか？ これは、他の人が自分の情報に基づいた判断を呼び出すことができるように、プロジェクトに関する十分な背景情報を提供できない限り、あなただけが行うことができる判断のようです。もちろん、確率は異なる機能を使用することができます計算する3ヶ所の各

If (new deadline_cost > old deadline_cost) 
    return (calculate probability) 

else if (new global finish time > old global finish time) 
    return (calculate probability) 

else if (new split cost > old split cost) 
    return (calculate probability) 

else 
    return (1.0) 

：

Answer 3

は、私はの線に沿って何かを検討します。

Answer 4

あなたが与えたacceptance_probabilityの機能で同時にすべてのが合格すると、多目的進化アルゴリズム（MOEA）からのヒントが得られます。これは、標準のシミュレーテッドアニーリングが同じエネルギーソリューションのプラトーを探索するのと同じように、パレートフロントを探索する効果があります。

しかし、これは、最初のものが優先されるという考えをあきらめます。

おそらく、より高い初期温度を与えるなど、パラメータを調整する必要があります。