Linee del livello della funzione obiettivo e dei punti dei test eseguiti dall'algoritmo in procinto di trovare il minimo. Credito:Università Lobachevsky
Per creare sistemi tecnici e processi tecnologici altamente efficaci, oltre all'uso di nuovi principi, nuovi materiali, nuovi effetti fisici e altre soluzioni che determinano la struttura complessiva dell'oggetto che si sta creando, i ricercatori devono scegliere la migliore combinazione dei parametri dell'oggetto (dimensioni geometriche, caratteristiche elettriche, eccetera.), poiché qualsiasi modifica dei parametri con una struttura complessiva dell'oggetto fissa può avere un impatto significativo sugli indicatori di efficacia.
Nella progettazione assistita da computer, il test delle opzioni può essere effettuato analizzando il suo modello matematico per diversi valori dei parametri. Man mano che i modelli diventano sempre più complessi, nasce la necessità di una scelta mirata di opzioni nella ricerca della soluzione ottimale (più efficace).
Un team di scienziati della Lobachevsky State University di Nizhny Novgorod (UNN) guidato dal professor Roman Strongin ha studiato le scelte mirate durante la ricerca della soluzione ottimale. Si tratta di un'analisi di un sottoinsieme delle possibili opzioni con l'obiettivo di escludere casi ovviamente poco promettenti e di concentrare la ricerca sul sottoinsieme contenente l'opzione migliore.
"Quando i modelli matematici dei processi che avvengono in un oggetto diventano più complicati, le caratteristiche di efficienza non possederanno la proprietà di monotonicità, ecco perché i metodi di ricerca locale sono insufficienti per valutare l'opzione migliore, "dice il professor Roman Strongin.
Le procedure di ricerca globale utilizzate in tali problemi (chiamate anche problemi di ottimizzazione multi-estremale) assicurano che la ricerca sia mirata tenendo conto della natura limitata del cambiamento nelle caratteristiche dell'oggetto quando i cambiamenti nei suoi parametri sono limitati. La formulazione matematica risultante può assumere la forma della condizione di Lipschitz, la condizione uniforme di Hölder, eccetera.
I problemi di ottimizzazione multi-estremale offrono un ambito ristretto di opportunità di ricerca analitica, e diventano computazionalmente costosi quando si cercano soluzioni numeriche, poiché i costi computazionali crescono esponenzialmente con l'aumentare della dimensione del problema.
Secondo Konstantin Barkalov, Professore Associato del Dipartimento di Software e Tecnologie dei Supercomputer della UNN, l'uso dei moderni sistemi di calcolo parallelo amplia la portata dei metodi di ottimizzazione globale. Però, allo stesso tempo, pone la sfida di parallelizzare efficacemente il processo di ricerca.
"Ecco perché gli sforzi principali in questo settore dovrebbero essere concentrati sullo sviluppo di metodi paralleli efficienti per risolvere numericamente problemi di ottimizzazione multi-estremali e sulla creazione di software appropriato per i moderni sistemi di calcolo sulla base di tali metodi, "dice Barkalov.
Generalmente, i metodi di ottimizzazione globale (sia sequenziale che parallela) sono destinati a risolvere un singolo problema di ottimizzazione. Per risolvere una serie di q problemi, i problemi della serie vengono risolti in sequenza, uno dopo l'altro. Perciò, la stima ottima nel problema i-esimo della serie rimane indefinita fino a quando tutti i problemi precedenti della serie (con gli indici 1, 2, . . . , io ? 1) sono stati completamente risolti. In caso di risorse computazionali limitate, le stime ottimali nei problemi i + 1, . . . , q non sarà ottenuto se le risorse di calcolo sono esaurite durante la risoluzione del problema i-esimo.
Le situazioni in cui è necessario risolvere una serie di q problemi non sono straordinarie. Per esempio, una serie di problemi scalari sorge quando si cerca un insieme di Pareto nella risoluzione di problemi di ottimizzazione multi-obiettivo. In questo caso, la soluzione di un singolo problema scalare corrisponde a uno dei punti ottimi paretiani di un problema multiobiettivo. Una serie di problemi di ottimizzazione sorge anche quando si utilizzano metodi di riduzione delle dimensioni per risolvere problemi di ottimizzazione multidimensionale. Finalmente, una serie di problemi di test può essere ottenuta anche con l'aiuto di un particolare generatore di problemi di test.
Gli scienziati ritengono che quando si risolvono una serie di problemi, è necessario avere stime iniziali delle soluzioni per tutti i problemi contemporaneamente, in modo che in ogni momento sia possibile valutare l'opportunità di proseguire la ricerca. In questo caso, è desiderabile avere le stime ottimali per tutti i problemi con la stessa accuratezza.
Esecuzione di molti processi indipendenti in un sistema di calcolo parallelo, ciascuno dei processi che risolvono un problema da una serie, presenta una serie di inconvenienti. Primo, si verificherà uno squilibrio del carico di lavoro tra i processori. Se la risoluzione del problema i-esimo richiede un numero considerevolmente inferiore di iterazioni del metodo rispetto alla risoluzione del problema j-esimo, il processore incaricato di gestire l'i-esimo problema rimarrebbe inattivo dopo aver completato l'attività. Secondo, le stime degli ottimi saranno ottenute con precisione diversa nei diversi problemi. I problemi più semplici saranno risolti con maggiore precisione, mentre la precisione sarà inferiore per problemi più complessi.
Lo scopo della ricerca svolta presso l'Università Lobachevsky era di sviluppare un nuovo metodo per risolvere una serie di problemi di ottimizzazione globale che garantisse:(i) un caricamento uniforme di tutti i core/processori impiegati; (ii) una convergenza uniforme alle soluzioni di tutti i problemi della serie.
Nella parte teorica del loro lavoro, Gli scienziati dell'UNN hanno anche dimostrato il teorema sulla convergenza uniforme del nuovo algoritmo. La parte sperimentale del lavoro consisteva nel risolvere una serie di diverse centinaia di problemi di prova di diverse dimensioni, ei risultati hanno dimostrato in modo convincente la presenza di convergenza uniforme.
Anche gli scienziati dell'UNN considerano problemi di ottimizzazione globale ad alta intensità di calcolo, per la cui risoluzione possono essere richiesti i sistemi di supercalcolo con prestazioni exaflop. Per superare tale complessità computazionale, i ricercatori propongono schemi computazionali paralleli generalizzati, che può coinvolgere numerosi algoritmi paralleli efficienti di ottimizzazione globale. Gli schemi proposti includono metodi di decomposizione multilivello di calcoli paralleli per garantire l'efficienza computazionale dei sistemi di supercalcolo con multiprocessori a memoria condivisa e distribuita che utilizzano migliaia di processori per soddisfare le sfide di ottimizzazione globale.