Ricerca casuale

La ricerca casuale (random search, o RS) è una famiglia di metodi di ottimizzazione numerica che non richiedono l'uso del gradiente del problema di ottimizzazione e può quindi essere utilizzata su funzioni che non siano continue o differenziabili. Tali metodi di ottimizzazione sono anche noti come metodi di ricerca diretta, senza derivate o metodi black-box.

Nel 1953, Anderson ha passato in rassegna i progressi dei metodi per problemi di ricerca di massimi / minimi che utilizzano una serie di tentativi distribuiti secondo un certo ordine o schema sullo spazio di ricerca dei parametri, ad esempio uno schema misto con spaziature/passi distribuiti esponenzialmente^[1]. Tale ricerca procede sequenzialmente su ciascun parametro e viene affinata iterativamente sulle migliori assegnazioni fatte nell'ultima sequenza. Lo schema può essere una ricerca a griglia (fattoriale) di tutti i parametri, una ricerca sequenziale su ciascun parametro o una combinazione di entrambe^[2]. Il metodo è stato sviluppato per controllare le condizioni sperimentali nelle reazioni chimiche da parte di diversi scienziati elencati nell'articolo di Anderson sopra menzionato.

Il nome "ricerca casuale" è attribuito a Rastrigin^[3] che ha presentato per primo la RS insieme ad una sua analisi preliminare. La RS funziona spostandosi iterativamente verso posizioni migliori nello spazio di ricerca, che vengono campionate su un'ipersfera definita attorno alla posizione corrente.

L'algoritmo descritto nell'articolo sopra citato è un tipo di ricerca casuale locale, in cui ogni iterazione dipende dalla soluzione candidata dell'iterazione precedente. Esistono metodi di ricerca casuale alternativi che campionano l'intero spazio di ricerca (ad esempio la ricerca casuale pura o la ricerca casuale globale uniforme) non descritti nell'articolo.

La ricerca casuale viene comunemente impiegata per l'ottimizzazione degli iperparametri dei diversi modelli di apprendimento automatico, quali le reti neurali artificiali.

Se le regioni più interessanti dello spazio di ricerca occupano il 5% del volume, le probabilità di trovare una buona configurazione nello spazio di ricerca sono del 5%. La probabilità di trovare almeno una buona configurazione è superiore al 95% testando 60 configurazioni (${\displaystyle 1-0.95^{60}=0.953>0.95}$, utilizzando la probabilità del complemento).

Algoritmo

Sia ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$  la funzione di costo che deve essere minimizzata e ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$  una posizione o soluzione candidata nello spazio di ricerca. L'algoritmo-base di RS può allora essere descritto come segue:

1. Inizializzare ${\displaystyle \mathbf {x} }$  con una posizione casuale nello spazio di ricerca.
2. Finché non viene soddisfatto un criterio di terminazione (ad esempio, sul numero di iterazioni eseguite o al raggiungimento di una soluzione adeguata) ripetere quanto segue:
   1. Campionare una nuova posizione ${\displaystyle \mathbf {x} '}$  sull'ipersfera di un dato raggio attorno alla posizione corrente ${\displaystyle \mathbf {x} }$  (vedere ad esempio la tecnica di Marsaglia per il campionamento di un'ipersfera).
   2. Se ${\displaystyle f(\mathbf {x} ')<f(\mathbf {x} )}$  spostarsi sulla nuova posizione impostando ${\displaystyle \mathbf {x} \gets \mathbf {x} '}$ 

Varianti

 

Schema di ricerca casuale che utilizza un problema di regressione non lineare come esempio. L'obiettivo è minimizzare il valore della funzione di penalità. In basso a destra sono mostrati alcuni metodi di esempio: 1. Ricerca casuale non strutturata, 2. Ricerca casuale strutturata, 3. Algoritmo di Gauss-Newton e 4. Algoritmo di Levenberg-Marquardt . 1 e 2 non hanno bisogno di conoscere il gradiente mentre 3 e 4 devono calcolare il gradiente e solitamente minimizzano contemporaneamente i parametri A e k (lo schema mostra solo la dimensione k).

In letteratura sono state introdotte diverse varianti di RS che prevedono il campionamento strutturato dello spazio di ricerca:

• procedura di Friedman-Savage
• ricerca casuale a passo fisso (FSSRS)
• ricerca casuale di dimensione del passo ottimale (OSSRS) di Schumer e Steiglitz
• ricerca casuale adattiva della dimensione del passo (ASSRS) di Schumer e Steiglitz
• ricerca casuale ottimizzata della dimensione del passo relativa (ORSSRS) di Schrack e Choit

Note

1. ^ R. L. Anderson, Recent Advances in Finding Best Operating Conditions, in Journal of the American Statistical Association, vol. 48, n. 264, 1º dicembre 1953, pp. 789–798, DOI:10.1080/01621459.1953.10501200. URL consultato il 7 agosto 2025.
2. ^ L'implementazione (in MATLAB) di una procedura sequenziale per la regressione non lineare generale per un modello matematico di esempio è disponibile presso GitHub
3. ^ Rastrigin, L.A., Automation and Remote Control 1963-11: Vol 24 Iss 11, collana Internet Archive, 24 (11), Springer Science & Business Media, 1963, pp. 1337–1342. URL consultato il 7 agosto 2025.