J'ai une fonction,
p (x0, x1, ..., xn)
qui prend 100 entiers comme entrée et donne en tant qu'entretre. P est une fonction lente à évaluer (elle peut aller de 30 secondes à quelques minutes).
J'ai besoin de savoir quelles valeurs de points optimiseront la valeur donnée de p.
Quelles techniques puis-je utiliser pour accomplir cela? Je sais généralement que les gens utilisent généralement des algorithmes génétiques pour cela, mais je crains que cela ne prendrait que des âges pour la calculer, comme même avec une petite population et peu de générations (disons, population = 50, générations = 50), p est tellement Lent, il faudra plus de 40 heures pour le calculer.
Y a-t-il une méthode moins chère de le faire? Peut-être un processus itératif? Je n'ai pas besoin que cela soit vraiment optimal, mais je n'ai aucune idéie de la façon dont il se comporte (j'ai essayé linéaire / quadratique / exponentiel, mais il ne semble pas générer de bonnes valeurs. Je sais que p peut revenir valeurs au moins 5 à 10 fois mieux que ce que je reçois).
Cela devrait être quelque chose qui est plus facile à mettre en œuvre (c'est-à-dire que je dois la mettre en œuvre moi-même).
merci
EDIT: P est un processus stochastique.
10 Réponses :
réseaux de neurones : D ou Série Taylor ?
Cela n'a-t-il pas besoin de quantités insensées de données pour converger réellement?
Je sais que Taylor Series. Mais comment voudraient-ils m'aider ici?
Dépend entièrement du problème. Si cela ne vous dérange pas de l'entraîner itérativement que vous pouvez simplement commencer par un réseau sur-ajusté et formez-le itérativement. Vous pouvez également écrire le réseau ou la série à la main si vous comprenez le problème assez bien.
Il ne connaît pas p () analytiquement. Comment utiliserait-il la série Taylor? Cela n'a pas de sens pour moi.
Il connaît P par les moyens improactiques et il a accès à la fonction. Il veut faire le problème difficile.
Peut-être qu'une partie importante de votre algorithme est parallélizable? Si oui, avez-vous envisagé de paralléser votre code?
Je ne voudrais pas aller de la sorte. Je n'ai jamais fait paralliser de rien, et je n'ai pas autant de temps pour apprendre.
Vous dites que vous n'avez pas beaucoup de temps à dépenser de l'apprentissage, mais vous parlez de techniques d'optimisation. Si vous avez un tas de processeurs disponibles, vous pouvez être brut-forçant cette fonction avec chacune d'elles avec peut-être une des heures d'étude et de développement. C'est presque exactement comme un exemple de MPI commun, informatique PI en lançant des fléchettes.
Regardez les différentes techniques d'optimisation stochastique énumérées ici . Je recommande Recuit simulé .
Il existe de nombreux algorithmes d'optimisation globaux connus (recuit simulé, tunneling stochastique, etc.) pouvant trouver le maximum mondial, mais aucun n'est garanti de le trouver dans un délai raisonnable sans faire d'hypothèses sur la forme de la fonction.
Vous n'allez pas trouver un moyen rapide / facile d'optimiser une fonction 100 dimensionnelle et non triviale. Vous aurez besoin de beaucoup de pouvoir et de temps de traitement. En supposant que vous ne souhaitez pas écrire vous-même du code d'optimisation (basé sur votre question), vous aurez également besoin de bons logiciels mathématiques (par exemple, Mathematica).
Une autre réponse non entièrement sérieuse, mais la nourriture à la pensée:
Ce problème semble être si important que les droits que vous devriez avoir besoin de quelque chose comme un effort Seti @ home pour le résoudre. Des milliers d'ordinateurs font des travaux raisonnablement légers de ce genre de chose. Mais je ne sais pas comment vous atteindrez des milliers d'utilisateurs d'ordinateurs pour obtenir l'utilisation de leurs ordinateurs.
En fait, je fais. S'il vous plaît supporter avec moi un instant en négligeant la légalité de tout.
Il y a des botnets gérés par des gens qui se cachent derrière l'ancien rideau de fer. J'ai récemment vu une offre de louer un botnet pour 70 $ pendant 24 heures. Pensez simplement, des milliers de PC 0Wned prêt à faire votre enchère! Au lieu de les avoir des sites Internet DDOS, vous pouvez les faire valoriser votre problème. :)
Deux derniers bits de conseil à ce sujet, cependant:
bonne chance!
recuit simulé , étroitement lié à Markov Chain Monte Carlo (MCMC) . La variante que vous voulez probablement est Metropolis-Hastings . Quand vous avez le pendre, c'est assez agréable. Peut-être que certains moyens d'optimiser parce que vos entrées et vos résultats sont tous des entiers. Il est trop intensif et peut nécessiter un accord, mais il est assez robuste, et je ne suis pas sûr que d'autres méthodes puissent mieux faire mieux.
Voici un code mort-mort pour le faire: P>
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
Si vous avez accès à MATLAB, vous pouvez parallementer votre code assez rapidement et assez facilement. Même il peut faire de simples linéaires pour les boucles paralleller avec sa perforation
Si une solution Microsoft est une option, consultez Fondation Solver . J'ai entendu parler de Scott Hanselman's Podcast ( # 191 ).
comme algorithme de première ligne pour ce type de problème, je recommanderais un recuit simulé. SA est un excellent choix car vous pouvez clairement contrôler votre point de départ et votre temps d'exécution.
Si vous connaissez quelque chose à propos de la structure de votre espace 100 dimensionnel, avec SA, vous pouvez choisir un bon point de départ et qui peut avoir un impact important sur la qualité de votre résultat. Aussi avec SA, vous pouvez contrôler le «taux de refroidissement» qui impacte à la fois le temps d'exécution et la qualité de vos résultats - naturellement dans des directions opposées. Je fonctionne généralement avec un taux de refroidissement relativement rapide d'abord à rechercher de bons vecteurs de démarrage, puis ralentissez le taux de refroidissement lors de ses courses ultérieures pour améliorer les résultats. Sorte d'une technique de méta-sa pouvant être automatisée.
J'ai utilisé SA avec succès pour optimiser la fonction très haute dimension utilisée dans la modélisation des interactions de protons neutrons dans le passé.
En outre, je regarderais à réduire de manière dimensionnelle P () si possible. Pour votre problème particulier, les 100 variables sont-elles nécessaires? Si vous pouvez réparer 1/2 de ceux-ci, vous accélérez tout optimiseur et retrouvez de meilleurs résultats.
(et SA est facile à mettre en œuvre.)
Hypothèses:
Tout d'abord - les variables doivent être entier.
Deuxièmement, la fonction objectif P () est non linéaire.
Observation:
En général, la programmation entière non linéaire est très difficile à résoudre. En réalité, comme recommandé ci-dessus, arrondi une solution en relaxant la restriction entière peut aider.
Il existe des techniques d'optimisation générales non contraintes disponibles. Une approche issue de la conception expérimentale est la «méthodologie de la surface de réponse». Très utile lorsque le coût d'une expérience est significatif. L'approche consiste à exécuter un ensemble d'expériences en commençant par un point et en déviant chacune de vos entrées par un incrément de jeu. Vous calculez ensuite le gradient pour chaque entrée et faites une étape dans cette direction pour chacun, puis répétez. Fletcher - Méthodes pratiques d'optimisation et de boîtes Hunter & Hunter Statistiques pour les expérimentateurs est une place à regarder.
Vous voulez dire p (x0, x1, ..., x99) alors?
À quoi ressemblent les vecteurs d'entrée typiques? Certaines des intrants prennent-elles souvent les mêmes valeurs (peut-être une évaluation partielle possible)?
Je ne sais pas. Autant que je sache, c'est une boîte noire.
Si c'est une boîte noire, il n'est pas grand chose que vous pouvez faire de côté des algorithmes généraux habituels tels que GA ou recuit simulé. Que voulez-vous dire par stochastique? Si vous voulez dire, vous pouvez obtenir différentes sorties de la même entrée, je ne pense pas que ceux-ci fonctionnent. Vous devez savoir quelque chose à propos d'un problème à proposer une solution efficace.
Je sais que ce n'est pas ce que vous demandez, mais je cherche à accélérer P (). Tout algorithme d'optimisation va demander à P () d'évaluer les 1000 fois, sinon plus.