Frage

Ich habe eine Funktion,

P (x0, x1, ..., xn)

, die 100 ganze Zahlen als Eingabe und gibt als Ausgabe eine ganze Zahl. P ist eine langsame Funktion ausgewertet werden (es 30 Sekunden bis ein paar Minuten dauern kann).

Ich muss wissen, welche Werte von Punkten wird die erbrachte Wert von P maximieren.

Welche Techniken kann ich dies erreichen? Ich weiß, dass im Allgemeinen für diese Menschen genetische Algorithmen verwenden, aber ich fürchte, es ewig dauern wird es mit ihnen zu berechnen, als auch mit einer kleinen Bevölkerung und einigen Generationen (sagen wir mal, Bevölkerung = 50, Generationen = 50), P ist so langsam wird es mehr als 40 Stunden dauern, es zu berechnen.

Gibt es eine billigere Methode, es zu tun? Vielleicht ein iterativer Prozess? Ich brauche es nicht wirklich optimal zu sein, aber ich habe keine ideia davon, wie es sich verhält (Ich habe versucht, linear / quadratisch / exponentiell, aber es scheint keine guten Werte zu erhalten. Ich weiß, P zurückkehren Werte mindestens 5-10 mal besser als das, was ich bin immer).

Es sollte etwas sein, das einfacher zu implementieren (das heißt, muss ich es selbst implementieren).

Danke

edit: P ist ein stochastischer Prozess

.
War es hilfreich?

Lösung

Als erster Linie Algorithmen für diese Art von Problem, würde ich Simulated Annealing empfehlen. SA ist eine großartige erste Wahl, weil Sie klar Ihren Ausgangspunkt und Laufzeit steuern können.

Wenn Sie etwas über die Struktur Ihrer 100-dimensionalen Raum kennen, mit SA Sie einen guten Ausgangspunkt wählen kann und die einen großen Einfluss auf die Qualität der Ihr Ergebnis haben kann. Auch mit SA können Sie die ‚Abkühlungsrate‘ steuern, welche Auswirkungen sowohl Laufzeit und die Qualität der Ergebnisse - natürlich in entgegengesetzten Richtungen. Ich laufe in der Regel mit einer relativ schnellen Abkühlungsgeschwindigkeit zunächst für gute Ausgangsvektoren zu suchen, und dann verlangsamte die Kühlrate in nachfolgenden Läufen Ergebnisse zu verbessern. Art einer Meta-SA-Technik, die automatisiert werden kann.

ich verwendet habe, SA erfolgreich eine sehr hohe Dimensions Funktion bei der Modellierung Neutron Proton-Wechselwirkungen in der Vergangenheit zu maximieren.

Außerdem würde ich schauen, um dimensions P (), wenn möglich zu reduzieren. Für Ihr spezielles Problem werden alle 100 Variablen benötigt? Wenn Sie 1/2 die beheben können Sie jeden Optimierer beschleunigen und mit besseren Ergebnissen enden.

(Und SA ist einfach zu implementieren.)

Andere Tipps

Simulierte Glühen , eng verwandt mit Markov Chain Monte Carlo (MCMC) . Die Variante, die Sie wahrscheinlich wollen, ist Metropolis-Hastings . Wenn Sie den Dreh raus zu bekommen, dann ist es ganz nett. Möglicherweise gibt es einige Möglichkeiten, es zu optimieren, da Sie Ihre Eingaben und Ergebnis sind alle ganzen Zahlen. Es ist rechenintensiv und kann eine gewisse Abstimmung erfordern, aber es ist ziemlich robust, und ich bin nicht sicher, ob andere Methoden könnten besser tun.

Hier ist ein hirntoten Code, es zu tun: 

const int n = 100; // length of vector to optimize
int a[n]; // the vector to optimize
double P(a){..} // Get the probability of vector a.
                // This is the function to optimize.
// for a large number of a samples
for (i = 0; i < large_number; i++){
  // get P(a)
  double p = P(a);
  // for each element of vector a
  for (j = 0; j < n; j++){
    // get an amount by which to change it. This choice has to be symmetric.
    // this is called the Proposal Distribution
    int step = uniform_random_choice_from(-2, -1, 1, 2);
    // make the change to a[j], and get p1, the new value of p
    a[j] += step;
    double p1 = P(a);
    bool bKeepTheStep = true;
    // if p1 is better than p, keep the step
    // if p1 is worse than p, then keep the step p1/p of the time
    if (p1 < p){
      bKeepTheStep = (unif(0,1) < p1/p);
    }
    if (bKeepTheStep) p = p1;
    else a[j] -= step;
  }
  // now a is a sample, and p is its value
  // record a and p
}
// what you have now is a large random sampling of vectors from distribution P
// now you can choose the best one, the average, the variance,
// any statistic you like

Wege zwicken sie sind den Vorschlag Verteilung zu erweitern oder zu verengen, so dass es größer oder kleiner Schritte unternimmt, oder Sie können es zunächst größere Schritte unternehmen und dann kleinere Schritte. Was Sie suchen ist ein Prozentsatz von Schritten, die gehalten werden, die weder zu hoch noch zu niedrig ist. Sie wollen wahrscheinlich ein „Burn-in“ Phase eines anfänglichen 1k oder so Proben haben, die man wegwerfen, während es für den Bereich der Modus jagt.

Und mit allen Mitteln, Profil P. Es muss so schnell wie möglich sein. Hier ist mein Lieblings-Weg, das zu tun.

Vielleicht ein wesentlicher Teil des Algorithmus ist parallelizable? Wenn ja, haben Sie Ihren Code als Parallelisierung?

Schauen Sie sich die verschiedenen stochastischen Optimierungstechniken aufgelistet hier . Ich empfehle simulierte Glühen .

Es gibt viele bekannte globale Optimierungsalgorithmen (Simulated Annealing, stochastische Tunneln, etc ...), die das globale Maximum finden, aber keine sind garantiert es innerhalb einer angemessenen Zeit zu finden, ohne Annahmen über die Herstellung Form der Funktion.

Du wirst nicht eine schnelle / einfache Art und Weise zu finden, eine 100-dimensionale, nicht-triviale Funktion zu optimieren. Sie werden eine Menge Rechenleistung und Zeit benötigen. Angenommen, Sie wollen nicht, Optimierung Code selbst (basierend auf Ihre Frage) zu schreiben, müssen Sie auch einige gute Mathematik-Software (zB. Mathematica).

Eine weitere nicht ganz ernsthafte Antwort, sondern zum Nachdenken anregen:

Dieses Problem sieht so groß sein, dass durch Rechte, die Sie so etwas wie ein SETI @ Home Aufwand benötigen sollten, es zu lösen. Tausende von Computern machen erstaunlich leicht Arbeit dieser Art der Sache. Aber ich bin nicht sicher, wie man Tausende von Computer-Nutzer erreichen würde, die Nutzung ihrer Computer zu erhalten.

Eigentlich ich. Bitte beachten Sie bei mir für einen Moment in Vernachlässigung die Rechtmäßigkeit von allem.

Es gibt Botnets durch einige Leute laufen hinter dem ehemaligen Eisernen Vorhang versteckt. Vor kurzem sah ich ein Angebot ein Botnetz für $ 70 für 24 Stunden zu mieten. Man denke nur an, Tausende von 0wned PCs bereit, Ihre Wünsche zu erfüllen! Statt sie DDOS Internetseiten haben, könnten Sie haben sie auf Ihrem Problem am laufenden Band. :)

Zwei abschließende Bits der Beratung zu diesem Thema, aber:

  • Sie zahlen sie nicht mit Ihrer eigenen Kreditkarte:)
  • Nehmen Sie keine rechtliche Beratung von Fremden auf SO:)

Viel Glück!

Annahmen:

Zuerst - die Variablen müssen integer sein
. Zweitens -. Die Zielfunktion P () ist nicht linear

Beobachtung:

In der Regel nichtlineare ganzzahligen Programmierung ist sehr schwierig zu lösen. In Wirklichkeit, wie oben empfohlen, eine Lösung Rundung durch die ganze Zahl Einschränkung entspannen kann helfen.

Es gibt allgemeine unbeschränkte Optimierungstechniken zur Verfügung. Ein Ansatz, der aus experimentellem Design kommt, ist Aufruf ‚Response Surface Methode‘. Sehr hilfreich, wenn die Kosten eines Experiments signifikant ist. Der Ansatz ist es, eine Reihe von Experimenten ausgeführt werden, indem sie mit einem Punkt beginnen und jede Ihrer Eingaben durch einen Satz Schritt abweicht. Sie dann für jeden Eingang den Gradienten berechnen, und einen Schritt in diese Richtung für jede nehmen, dann wiederholen. Fletcher -. Praktische Methoden der Optimierung und Box Hunter & Hunter Statistiken Experimentatoren ist Platz zu suchen

Wenn Sie Zugriff auf Matlab haben, können Sie Ihren Code ziemlich schnell und ziemlich leicht parallelisieren. Auch kann es einfach linear macht für Schleifen mit seiner parfor Schleife parallell

Wenn eine Microsoft-Lösung ist eine Option Besuche Solver Foundation . Ich hörte auf Scott Hanselman Podcast ( # 191 ).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top