Ottimizzazione di più parametri con molti minimi locali

Question

Sto cercando algoritmi per trovare un "migliore" insieme di valori di parametro. La funzione in questione ha molti minimi locali e cambia molto rapidamente. A peggiorare le cose, testare una serie di parametri è molto lento - nell'ordine di 1 minuto - e non riesco a calcolare direttamente la sfumatura.

Esistono algoritmi noti per questo tipo di ottimizzazione?

Ho avuto un discreto successo con il solo tentativo di valori casuali. Mi chiedo se posso migliorare le prestazioni facendo in modo che il selettore di parametri casuali abbia una minore possibilità di selezionare parametri vicini a quelli che hanno prodotto risultati negativi in ​​passato. Esiste un nome per questo approccio in modo che possa cercare un consiglio specifico?

Maggiori informazioni:

• I parametri sono continui
• Ci sono dell'ordine di 5-10 parametri. Certamente non più di 10.

Answer 1

ho provato Simulated Annealing e Particle Swarm Optimization. (Come promemoria, non ho potuto utilizzare la discesa del gradiente perché non è possibile calcolare il gradiente).

Ho anche provato un algoritmo che esegue le seguenti operazioni:

• selezionare un punto casuale e una direzione a caso
• valutare la funzione
• Continuate a muovervi lungo la direzione a caso per tutto il tempo della il risultato continua a migliorare, accelerando ogni iterazione di successo.
• Quando il risultato smette di migliorare, fare un passo indietro e tentare invece di spostarsi in una direzione ortogonale della stessa distanza.

Questa "direzione ortogonale" è stato generato creando un casuale matrice ortogonale (adattato this code) con il numero necessario di dimensioni.

Se lo spostamento nella direzione ortogonale ha migliorato il risultato, l'algoritmo ha continuato solo in quella direzione. Se nessuna delle direzioni migliorava il risultato, la distanza di salto veniva dimezzata e veniva tentata una nuova serie di direzioni ortogonali. Alla fine l'algoritmo ha concluso che doveva essere al minimo locale, ricordato e riavviato l'intero lotto in un nuovo punto casuale.

Questo approccio si è rivelato notevolmente migliore rispetto a Simulation Annealing e Particle Swarm: richiedeva meno valutazioni della (molto lenta) funzione per ottenere un risultato della stessa qualità.

Naturalmente le mie implementazioni di S.A. e P.S.O. potrebbe essere imperfetto - questi sono algoritmi difficili con un sacco di spazio per i parametri di tweaking. Ma ho solo pensato di menzionare ciò che ha funzionato meglio per me.

Answer 2

Non posso davvero aiutarti a trovare un algoritmo per il tuo problema specifico.

Tuttavia, per quanto riguarda la scelta casuale dei parametri, penso che quello che stai cercando sia genetic algorithms. Gli algoritmi genetici si basano generalmente sulla scelta di alcuni input casuali, selezionando quelli, che sono la soluzione migliore (finora) per il problema, e casualmente mutandoli/combinandoli per generare una generazione successiva per la quale sono selezionati i migliori.

Se la funzione è più o meno continua (cioè piccole mutazioni di ingressi buoni generalmente non generano input errati (essendo piccolo un po 'generico), questo funzionerebbe ragionevolmente bene per il tuo problema.

Answer 3

Quanti parametri ci sono - ad esempio, quante dimensioni nello spazio di ricerca? Sono continui o discreti, ad es. Numeri reali o interi o solo pochi valori possibili?

Gli approcci che ho visto usati per questo tipo di problemi hanno una struttura generale simile: prendi un gran numero di punti campione e li aggiusti tutti verso regioni che hanno in qualche modo risposte "buone". Dato che hai molti punti, le loro differenze relative fungono da gradiente improvvisato.

• Simulated Annealing: L'approccio classico. Prendi un po 'di punti, spostali in qualche modo in un punto vicino scelto a caso a seconda di quanto meglio è.
• Particle Swarm Optimization: Prendi uno "sciame" di particelle con velocità nello spazio di ricerca, muovendo a caso una particella in modo probabilistico; se è un miglioramento, fai sapere a tutto lo sciame.
• Genetic Algorithms: questo è un po 'diverso. Piuttosto che usare le informazioni dei vicini come sopra, ottieni sempre i migliori risultati e "incrocia" sperando di ottenere le migliori caratteristiche di ciascuno.

I collegamenti di Wikipedia hanno uno pseudocodice per i primi due; I metodi GA hanno così tanta varietà che è difficile elencare solo un algoritmo, ma puoi seguire i link da lì. Nota che esistono implementazioni per tutto quanto sopra che puoi usare o prendere come punto di partenza.

Si noti che tutti questi - e in realtà qualsiasi approccio a questo algoritmo di ricerca di grandi dimensioni - sono euristici, il che significa che hanno parametri che devono essere sintonizzati sul problema specifico. Quale può essere noioso.

A proposito, il fatto che la valutazione della funzione sia così costosa può essere fatta funzionare un po 'per voi; poiché tutti i metodi sopra citati comportano molte valutazioni indipendenti delle funzioni, tale parte dell'algoritmo può essere banalmente parallelizzata con OpenMP o qualcosa di simile per utilizzare tutti i core presenti sulla macchina.

Answer 4

La tua situazione sembra essere simile a quella del poster di Software to Tune/Calibrate Properties for Heuristic Algorithms e ti darei lo stesso consiglio I gave there: considera un approccio simile a Metropolis-Hastings con più camminatori e una ricottura simulata delle dimensioni del passo.

La difficoltà nell'utilizzo di un metodo Monte Carlo nel tuo caso è la valutazione costosa di ciascun candidato. Quanto costa il rispetto al tempo che hai a disposizione? Se hai bisogno di una buona risposta tra qualche minuto, non sarà abbastanza veloce. Se puoi lasciarlo correre per tutta la notte, funzionerà abbastanza bene.

Dato uno spazio di ricerca complicato, consiglierei una distribuzione iniziale casuale. La tua risposta finale potrebbe essere semplicemente il miglior risultato individuale registrato durante l'intera corsa o la posizione media del deambulatore con il miglior risultato.

Non essere scoraggiato dal fatto che stavo discutendo di massimizzare lì e che tu vuoi minimizzare: la figura del merito può essere negata o invertita.

Answer 5

Non esiste un modo generalizzato per rispondere alla domanda. Ci sono molti libri/articoli sull'argomento, ma dovrai scegliere il tuo percorso in base alle tue esigenze, che non sono chiaramente parlate qui.

Alcune cose da sapere, tuttavia - 1min/test è troppo per qualsiasi algoritmo da gestire. Credo che nel tuo caso, è necessario davvero fare uno dei seguenti modi:

• arrivare 100 computer per ridurre il tempo di prova parametro per un po 'di tempo ragionevole
• davvero cercare di capire i parametri a mano e la mente. Ci deve essere una certa ridondanza e almeno qualche controllo di integrità per poter testare il caso in < 1min
• per possibili set di risultati, provare a capire alcune "operazioni" che lo modificano leggermente invece di randomizzarlo. Ad esempio, in TSP un operatore di base è lambda, che scambia due nodi e quindi crea una nuova rotta. Il tuo può spostare qualche numero su/giù per un certo valore.
• quindi, trovarsi un buon algoritmo, il punto di partenza può essere da qualche parte here. Il libro è una risorsa inestimabile per chiunque inizi con la risoluzione di problemi.