12

別のプログラムが計算する入力データ [パラメーター] を生成するスクリプトを作成しています。結果のデータを最適化したいと思います。以前は、numpy powell 最適化を使用していました。擬似コードは次のようになります。

def value(param):
     run_program(param)
     #Parse output
     return value

scipy.optimize.fmin_powell(value,param)

これはうまくいきます。ただし、プログラムの反復ごとに実行に数日かかる場合があるため、非常に低速です。私がやりたいのは、これを粗粒度で並列化することです。そのため、一度に 1 つの反復を実行する代わりに、(パラメーターの数)*2 ずつ実行します。例えば：

Initial guess: param=[1,2,3,4,5]

#Modify guess by plus minus another matrix that is changeable at each iteration
jump=[1,1,1,1,1]
#Modify each variable plus/minus jump.
for num,a in enumerate(param):
    new_param1=param[:]
    new_param1[num]=new_param1[num]+jump[num]
    run_program(new_param1)
    new_param2=param[:]
    new_param2[num]=new_param2[num]-jump[num]
    run_program(new_param2)

#Wait until all programs are complete -> Parse Output
Output=[[value,param],...]
#Create new guess
#Repeat

変数の数は 3 ～ 12 の範囲である可能性があるため、このようなものを使用すると、1 年かかっていたコードが 1 週間に短縮される可能性があります。すべての変数は互いに依存しており、最初の推測から極小のみを探しています。ヘッセ行列を使用した実装を開始しました。ただし、それはかなり複雑です。これを行うもの、より簡単な方法、または開始するための提案はありますか?

したがって、主な質問は次のとおりです。最初の推測を取り、複数の推測を生成し、それらの複数の推測を使用して新しい推測を作成し、しきい値が見つかるまで繰り返すアルゴリズムはありますか? 分析導関数のみが利用可能です。これについての良い方法は何ですか、これを行うためにすでに構築されたものはありますか、他のオプションはありますか?

お時間をいただきありがとうございます。

小さな更新として、各次元の 3 点を通る単純な放物線を計算し、最小値を次の推測として使用することで、これを機能させています。これは適切に機能しているように見えますが、最適ではありません。私はまだ追加のオプションを探しています。

現在の最良の実装は、パウエルの方法の内側のループを並列化することです。

コメントありがとうございます。残念ながら、この特定の問題に対する簡潔な答えはないようです。これを実行する何かを実装する場合は、ここに貼り付けます。ただし、プロジェクトは特に重要ではないか、結果を急ぐ必要がないため、しばらくの間、ノードを取り上げることに満足するでしょう.

4

7 に答える 7

3

大学在学中に同じ問題が発生しました。変数のグループに基づいてエンジンの効率を計算するためのFortranアルゴリズムがありました。当時、modeFRONTIERを使用しており、正しく思い出せば、どのアルゴリズムも複数の推測を生成できませんでした。

通常のアプローチは、DOEを用意し、問題に最適なDOEを生成するためのいくつかのアルゴリズムを配置することです。その後、単一のDOEエントリを並列に実行し、アルゴリズムが最適化の開発を「監視」して、現在の最良の設計を示します。

補足：クラスターがなく、より多くの計算能力が必要な場合は、HTCondorが役立つ場合があります。

于 2012-12-14T01:00:34.543 に答える
1

目標関数の導関数は利用できますか？はいの場合、勾配降下法（古い、遅いが信頼できる）または共役勾配法を使用できます。そうでない場合は、有限差分を使用して導関数を近似し、これらの方法を使用できます。一般に、導関数に有限差分近似を使用する場合は、ニュートン法よりも共役勾配法を使用する方がはるかに優れていると思います。

より現代的な方法は、確率論的方法であり、派生物を必要としないSPSAです。SPSAは、ある程度正常に動作する問題に対して、共役勾配法の有限差分近似よりも、同じ収束率での目標関数の評価がはるかに少なくて済みます。

于 2012-12-10T09:24:01.360 に答える
1

勾配を推定する方法は 2 つあります。1 つは簡単に並列化でき、もう 1 つはそうではありません。

  • 単一点の周り、例えば (f( x + h 方向i ) - f(x)) / h; これは Ndim まで簡単に並列化できます
  • 「歩く」勾配: x 0 からe 0 の方向にx 1まで歩き、次に x 1からe 1の方向に x 2 ...; これはシーケンシャルです。

勾配を使用するミニマイザーは高度に開発されており、強力で、2 次的に収束します (十分に滑らかな関数で)。ユーザー指定の勾配関数は、もちろん、並列勾配推定器にすることができます。
いくつかの最小化ツールは、「ウォーキング」勾配を使用します。その中には、パウエルの方法があります。509.
だから私は混乱しています: どうやってその内側のループを並列化しますか?

おそらく片側ではなく中央の違いを使用して、並列勾配推定器を使用したscipy fmin_tncをお勧めします。
(Fwiw、 これ は 2 つの 10-d 関数; ymmv でいくつかの scipy 非導関数オプティマイザーを比較します。)

于 2012-12-11T13:55:38.753 に答える
0

私があなたが求めていることを間違えていなければ、あなたは一度に1つのパラメーターで関数を最小化しようとしています。

これは、単一の引数の関数のセットを作成することで取得できます。関数ごとに、1つを除くすべての引数をフリーズします。

次に、各変数を最適化し、部分解を更新するループに進みます。

この方法は、エネルギー地形がそれほど複雑ではない（パラメーター間の依存関係があまり強くない）多くのパラメーターの非常に多くの関数によってスピードアップすることができます。

与えられた機能

energy(*args) -> value

推測と関数を作成します。

guess = [1,1,1,1]
funcs = [ lambda x,i=i: energy( guess[:i]+[x]+guess[i+1:] ) for i in range(len(guess)) ]

最適化のためにしばらくの間それらを置くよりも

while convergence_condition:
    for func in funcs:
        optimize fot func
        update the guess
    check for convergence

これは、最小化タスクを簡素化するための非常にシンプルで効果的な方法です。このメソッドがどのように呼び出されたかは本当に思い出せませんが、最小化に関するウィキペディアのエントリをよく見るとうまくいくはずです。

于 2012-12-10T00:15:37.793 に答える
0

2 つの部分で並列処理を行うことができます。1) 1 回の反復計算の並列処理、または 2) N 初期推測の並列開始。

2) では、N 個の初期推測ディスカバリー スレッドを制御するためのジョブ コントローラーが必要です。

プログラムに追加の出力を追加してください: 現在の入力パラメータの適切な出力値がこの下限を下回らないことを示す「下限」。

最初の N 個の推測スレッドは互いに競合する可能性があります。いずれかのスレッドの下限が既存のスレッドの現在の値よりも高い場合、このスレッドはジョブ コントローラーによって削除される可能性があります。

于 2012-12-14T03:04:01.440 に答える
0

あなたがやりたいことは、Pythonに組み込まれているスレッド機能を使用することだと思います。作業関数のランタイムがパラメーターに関係なく多かれ少なかれ同じであれば、効率的です。

プールに 8 つのスレッドを作成し、関数の 8 つのインスタンスを実行し、8 つの結果を取得し、最適化アルゴリズムを実行して 8 つの結果でパラメーターを変更し、繰り返します.... 利益 ?

于 2012-12-08T02:11:23.010 に答える