9

シミュレーテッドアニーリングを使用して、NP完全リソーススケジューリング問題を解決しています。タスクの候補の順序ごとに、いくつかの異なるコスト（またはエネルギー値）を計算します。いくつかの例は次のとおりです（詳細はおそらく質問とは無関係ですが）：

  • global_finish_time：スケジュールがまたがる合計日数。
  • split_cost：他のタスクによる中断のために各タスクが遅延する日数（これは、タスクが開始された後の中断を阻止するためのものです）。
  • deadline_cost：各期限を過ぎた日数の2乗の合計。

従来の受け入れ確率関数は次のようになります（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)

これまでのところ、最初の2つのコストを1つにまとめて、結果をにフィードできるようにしていacceptance_probabilityます。しかし、私が本当に望んでいるのはdeadline_cost、常にを優先しglobal_finish_time、global_finish_timeを優先することsplit_costです。

したがって、Stack Overflowに対する私の質問は、複数のエネルギーを考慮に入れながら、常に最初のエネルギーが2番目のエネルギーよりも重要であると見なす受け入れ確率関数を設計するにはどうすればよいかということです。言い換えれば、私はいくつかのコストのタプルとして渡して、賢明な値を返しold_costたいと思います。new_cost

編集：提案されたソリューションを数日間実験した後、私にとって十分に機能する唯一の方法は、異なる単位を持つコストコンポーネントで他の多くの問題を引き起こすにもかかわらず、MikeDunlaveyの提案であると結論付けました。私は実際にリンゴとオレンジを比較することを余儀なくされています。

そこで、値を「正規化」することに少し力を入れました。まず、deadline_costは平方和であるため、指数関数的に増加し、他のコンポーネントは線形に増加します。これに対処するために、平方根を使用して同様の成長率を取得します。次に、コストの線形結合を計算する関数を開発しましたが、これまでに見られた最も高いコスト要素に従って係数を自動調整します。

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

これにより、新しい最大コストが検出されるため、コスト関数に「ジャギー」が作成されます。たとえば、Cが上がると、BCxとCyは両方とも、特定の（x、y、z）入力に対して高くなり、コスト間の差も大きくなります。コスト差が大きいということは、温度が突然1ステップ下がったかのように、受け入れ確率が低下することを意味します。実際には、これは問題ではありません。最大コストは最初は数回しか更新されず、後で変更されないためです。コストがより低い値に向かって収束することがわかっているので、これは理論的に正しい結果に収束することさえ証明できると思います。

まだ少し混乱しているのは、最大コストが1.0以下、たとえば0.5の場合にどうなるかということです。最大ベクトルが（0.5、0.5、0.5）の場合、これにより線形結合0.5 * 0.5 * x + 0.5 * y + zが得られます。つまり、優先順位が突然逆になります。これに対処する最善の方法は、最大ベクトルを使用してすべての値を指定された範囲にスケーリングすることです。これにより、係数は常に同じになります（たとえば、100x + 10y + z）。しかし、私はまだそれを試していません。

4

4 に答える 4

2

mbeckishは正しいです。

異なるエネルギーの線形結合を作成し、係数を調整できますか？

おそらくそれらをログインおよびログアウトしてログ変換しますか？

Metropolis-Hastingsを使用してMCMCを実行しました。その場合、私は特定の状態の（正規化されていない）対数尤度を定義しています（その事前確率が与えられている場合）、そして私が欲しいものについての私の考えを明確にする方法を見つけます。

于 2009-07-09T14:55:24.330 に答える
1

私は次のようなことを考えます：

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)

もちろん、確率を計算する3つの場所のそれぞれで、異なる関数を使用できます。

于 2009-07-09T14:52:31.577 に答える
1

多目的進化的アルゴリズム（MOEA）からヒントを得て、すべてacceptance_probabilityの目的が指定した関数と同時に通過した場合に遷移させます。これは、標準のシミュレーテッドアニーリングが同じエネルギーソリューションのプラトーを探索するのと同じように、パレートフロントを探索する効果があります。

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

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

于 2010-08-19T18:51:02.370 に答える
0

それはあなたが「優先する」という意味に依存します。たとえば、deadline_costが0.001減少したが、global_finish_timeコストが10000増加した場合はどうなりますか？減少したため、1.0を返しdeadline_costますか？それは他の何よりも優先されますか？これは、他の人が自分の情報に基づいた判断の呼びかけを提案できるようにプロジェクトに関する十分な背景情報を提供できない限り、あなただけが行うことができる判断の呼びかけのようです。

于 2009-07-09T14:41:21.193 に答える