función de aproximación

Question

Tengo una función,

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

que toma 100 enteros como entrada y da como salida un número entero. P es una función lenta de evaluar (puede oscilar entre 30 segundos y un par de minutos).

Necesito saber qué valores de los puntos maximizará el valor dado de P.

¿Qué técnicas puedo utilizar para lograr esto? Sé que, en general, las personas usan algoritmos genéticos para esto, pero me temo que tomará años calcularlo con ellos, ya que incluso con una población pequeña y pocas generaciones (digamos, población = 50, generaciones = 50), P es tan lento tomará más de 40 horas para calcularlo.

¿Hay algún método más barato de hacerlo? Tal vez un proceso iterativo? No necesito que sea realmente óptimo, pero no tengo ninguna idea de cómo se comporta (he intentado lineal/cuadrático/exponencial pero no parece dar buenos valores. Sé que P puede devolver valores al menos 5-10 veces mejor que lo que estoy obteniendo).

Debería ser algo más fácil de implementar (es decir, debo implementarlo yo mismo).

Gracias

edit: P es un proceso estocástico.

Answer 1

Como algoritmos de primera línea para este tipo de problema, recomendaría el recocido simulado. SA es una excelente opción porque puede controlar claramente su punto de partida y tiempo de ejecución.

Si conoce algo sobre la estructura de su espacio de 100 dimensiones, con SA puede elegir un buen punto de partida y puede tener un gran impacto en la calidad de su resultado. También con SA puede controlar la "tasa de enfriamiento" que afecta tanto el tiempo de ejecución como la calidad de sus resultados, naturalmente en direcciones opuestas. Por lo general, corro con una tasa de enfriamiento relativamente rápida primero para buscar buenos vectores de inicio, y luego disminuí la velocidad de enfriamiento en las ejecuciones posteriores para mejorar los resultados. Tipo de una técnica meta-SA que puede automatizarse.

He utilizado SA con éxito para maximizar la función dimensional muy alta utilizada en el modelado de las interacciones de protones de neutrones en el pasado.

Además, me gustaría reducir de forma dimensional P() si es posible. Para su problema particular, ¿se necesitan las 100 variables? Si puede arreglar la mitad de esos, acelerará cualquier optimizador y obtendrá mejores resultados.

(Y SA es fácil de implementar.)

Answer 2

Neural networks: D o Taylor series?

Answer 3

¿Quizás una parte importante de su algoritmo sea paralelizable? Si es así, ¿ha considerado la posibilidad de paralelizar su código?

Answer 4

Mire las diversas técnicas de optimización estocástica enumeradas here. Recomiendo simulated annealing.

Answer 5

Hay muchos algoritmos de optimización global bien conocidos (recocido simulado, túnel estocástico, etc.) que PUEDEN encontrar el máximo global, pero ninguno está garantizado para encontrarlo en un tiempo razonable sin hacer suposiciones sobre la forma de la función.

No va a encontrar una manera rápida/fácil de optimizar una función tridimensional no trivial. Necesitará mucho tiempo y potencia de procesamiento. Suponiendo que no quiera escribir el código de optimización usted mismo (basado en su pregunta), también necesitará algún buen software matemático (por ejemplo, Mathematica).

Answer 6

Otro no totalmente seria respuesta, pero para la reflexión:

Este problema parece ser tan grande que por los derechos de que necesite algo así como un esfuerzo de SETI @ home para resolverlo. Miles de computadoras hacen un trabajo razonablemente ligero de este tipo de cosas. Pero no estoy seguro de cómo llegaría a miles de usuarios de computadoras para obtener el uso de sus computadoras.

En realidad, lo hago. Por favor, tengan paciencia conmigo por un momento sin tener en cuenta la legalidad de todo.

Hay botnets dirigidas por algunas personas que se esconden detrás de la antigua cortina de hierro. Recientemente vi una oferta para alquilar una botnet por $ 70 por 24 horas. Solo piense en miles de computadoras preparadas para hacer su oferta. En lugar de tenerlos en los sitios de Internet de DDOS, podrías tenerlos revolviendo en tu problema.:)

dos últimos bits de asesoramiento sobre este, sin embargo:

• No pagar con su propia tarjeta de crédito :)
• No tome el asesoramiento jurídico de los extranjeros en SO :)

¡Buena suerte!

Answer 7

Simulated annealing, estrechamente relacionado con Markov Chain Monte Carlo (MCMC). La variante que probablemente desee es Metropolis-Hastings. Cuando te acostumbras, es bastante agradable. Posiblemente haya algunas formas de optimizarlo porque sus entradas y resultados son todos enteros. Es intensivo en cómputo y puede requerir un ajuste, pero es bastante robusto, y no estoy seguro de que otros métodos puedan ser mejores.

Aquí hay un código con muerte cerebral para hacerlo:

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 

maneras de modificar que son para ensanchar o estrechar la distribución propuesta, por lo que toma medidas más grandes o más pequeños, o puede tener inicialmente tome más grande pasos y luego pasos más pequeños. Lo que está buscando es un porcentaje de pasos que se mantienen que no son ni muy altos ni muy bajos. Probablemente desee tener una fase de "quemado" de una muestra inicial de 1k o más que usted tira, mientras busca el área del modo.

Y, por supuesto, perfil P. Tiene que ser lo más rápido posible. Here's my favorite way to do that.

Answer 8

Si tiene acceso a matlab, puede paralelizar su código bastante rápido y con bastante facilidad. Incluso puede hacer que los bucles lineales simples entren en paralelo con su ciclo parfor

Answer 9

Si existe una solución de Microsoft disponible, consulte Solver Foundation. Escuché sobre el podcast de Scott Hanselman (#191).

Answer 10

Supuestos:

En primer lugar - las variables deben estar entero.
Segundo: la función objetivo P() no es lineal.

Observación:

En programación entera en general, no lineal es muy difícil de resolver. En realidad, como se recomendó anteriormente, redondear una solución relajando la restricción entera puede ayudar.

Existen técnicas generales de optimización sin restricciones disponibles. Un enfoque que proviene del diseño experimental es la llamada 'metodología de superficie de respuesta'. Muy útil cuando el costo de un experimento es significativo. El enfoque es ejecutar un conjunto de experimentos comenzando con un punto y desviando cada una de sus entradas por un incremento establecido. Luego calcula el gradiente para cada entrada y da un paso en esa dirección para cada uno, luego repita. Fletcher - Métodos prácticos de optimización y Box Hunter & Hunter Statistics for Experimenters es el lugar para buscar.