algorytm poszukujący optymalnego zestawu parametrów

Odpowiedz Nowy wątek
2018-07-03 23:02
0

Mam symulację, której wynik zależy od kilku parametrów np. 4-9.
Parametry przyjmują wartość w zakresie np. 1-100.
Poszukując optymalnego zestawu parametrów mogę oczywiście użyć zagnieżdżonych pętli i wywołać symulację dla każdej kombinacji parametrów.
Szukam metody bardziej wydajnej. Podpowiecie jakąś nazwę metody/algorytmu?
Czytałem o metodzie Monte Carlo i algorytmach genetycznych/ewolucyjnych.
Pierwsze rozumiem jako wielokrotne losowanie zestawu parametrów.
Drugie jako cykle losowania kilku zestawów parametrów (pokolenie), poszukiwaniu najlepszych zestawów, "skrzyżowaniu" najlepszych osobników z uwzględnieniem "mutacji".
Czego mógłbym jeszcze użyć? Są jakieś biblioteki do tego?
Koduję w Javie. Nie mam wykształcenia informatycznego.

edytowany 1x, ostatnio: ronaldexim, 2018-07-03 23:38

Pozostało 580 znaków

2018-07-16 20:45
0

Opiszę obecny etap moich usiłowań.

Analiza dotyczy 10 000 rekordów. Rekordy to kolejne wartości double ułożone na osi czasu. Na ich podstawie wyliczam funkcje zależące od kilku parametrów (do 10). Na podstawie funkcji filtruję rekordy - dalej przechodzi np: 1% rekordów. Analiza tego 1% daje mi informację czy wybrałem dobrze czy źle - wynik symulacji jest ujemny czy dodatni. Nie można założyć, że warunki symulacji będą stałe dla wszystkich rekordów.

Ponieważ warunki mogą się zmieniać podzieliłem dane na fragmenty po 1000 rekordów.
Optymalizuję po 3 parametry - liczby naturalne z zakresu 1-100. Zestawy tworzą tablicę [100][100][100]. Możliwych kombinacji: 1 000 000. Pozostałe parametry ustawiam "standardowo".

W pierwszym etapie próbkuję tablicę w zagnieżdżonych pętlach z krokiem 10 dla każdego wymiaru (takie niby MonteCarlo tylko bez losowości) - mam sprawdzonych 1000 symulacji.
Wybieram 10 z najlepszym wynikiem.

Te punkty traktowałem metodą gradientową - sprawdzałem rekurencyjnie sąsiadów szukając lepszych wyników. Niestety wyniki symulacji o zbliżonych parametrach często są równe - w tablicy parametrów tworzą się obszary o jednakowych wynikach. To powoduje, że rekurencja wchodziła w głąb góra na 2-3 poziomy.

Zastosowałem coś co chyba podpada pod grafy. Wybieram obszar o jednakowych wynikach symulacji. Szukam następnie największej wartości sąsiadującej z tym obszarem i rekurencyjnie powtarzam procedurę. Teraz rekurencja rozpełzała się po całej tablicy i obliczenia trwały za długo. Ograniczyłem więc odległość od punktu początkowego do połowy oczka siatki z pierwszego etapu - czyli 5.

Wyniki symulacji trzymam w tablicy [][][] aby nie liczyć kilka razy tego samego.
Otoczenie sprawdzam używając wektorów np: -1,0,0. Używam albo 6 podstawowych kierunków (góra, dół, prawo, lewo, przód, tył) albo wszystkich 26 (z kierunkami skośnymi). Druga wersja jest 50% wolniejsza a daje podobne wyniki.
Obliczenia robię w strumieniach równoległych co daje 3-4 krotne przyśpieszenie.

Całość wymaga wykonania 2500 - 15000 symulacji i trwa 25-150s. Brute force zajęłoby prawie 3h. Ciekawe ile dojdzie po dodaniu czwartego parametru.

Szybkość i jakość optymalizacji jest już dobra. Teraz będę myślał nad etapami "nauki" i "testu".

@hurgadion MiniZinc, Spark z MLlib i wszystkie biblioteki Java do ML czy gradient descent mnie przerastają. Nie mogłem zmusić bibliotek do współpracy - podobnie jak było np. z filtrami dolno i górno przepustowymi (lowpass, highpass). Szybciej mi poszło samemu to napisać. Chyba tylko "org.apache.commons.math3.stat.regression" uruchomiłem.
Na wszystko pewnie przyjdzie czas - dopiero od kwietnia zacząłem z Javą.

private int diam = 100;
private ResultSimple[][][] result = new ResultSimple[diam + 1][diam + 1][diam + 1];
private List<Parameters> paramList = new ArrayList<>();
private List<ResultSimple> resultList = new ArrayList<>();
.
.
.
 
resultList = paramList.parallelStream()
                .map(ResultSimple::new)
                .sorted(revByPips)
                .limit(10)
                .collect(Collectors.toList());
 
resultList = resultList.parallelStream().map(g -> checkBorders(g, g)).collect(Collectors.toList());
 
// resultList = resultList.parallelStream().map(g -> checkNeighbors(g, 100)).collect(Collectors.toList());
public ResultSimple checkBorders( ResultSimple start, ResultSimple origin) {
       Vector[] vectors = {
                new Vector(1,0,0), new Vector(-1,0,0),
                new Vector(0,1,0), new Vector(0,-1,0),
                new Vector(0,0,1), new Vector(0,0,-1)};
 
        List <ResultSimple> equal = new ArrayList<>();
        List <ResultSimple> checked = new ArrayList<>();
        List <ResultSimple> better = new ArrayList<>();
        equal.add(start);
 
        while ( equal.size() > 0 ) {
            ResultSimple toCheck = equal.get(0);
            double begin = Math.round(toCheck.sum);
            for (Vector one : vectors) {
                ResultSimple temp = giveResult(toCheck, one);
                double tempVar = Math.round( temp.sum );
                if ( tempVar == begin && !equal.contains(temp) && !checked.contains(temp) ) {
                    if (tooFar(temp, origin)) continue;
                    equal.add(temp);
                } else if ( tempVar > begin && !better.contains(temp) ) {
                    better.add(temp);
                }
            }
            checked.add(toCheck);
            equal.remove(0);
        }
 
        if (better.size() == 0) {
            System.out.format("%n %.0f %.0f %n", start.sum, origin.sum ); // największe zagłębienie
            return start;
        }
 
        ResultSimple temp = better.get(0);
        double max = Math.round(temp.sum);
        for (ResultSimple one : better) {
            if (Math.round(one.sum) > max) {
                max = Math.round(one.sum);
                temp = one;
            }
        }
        if (max > Math.round(start.sum)) {
            temp = checkBorders(temp, origin); // rekurencja
        }
        return temp;
    }
 
private ResultSimple giveResult(ResultSimple s, Vector d) {
        int tabX = Math.max( 1, s.x+d.x ); tabX = Math.min( tabX, diam );    // sprawdza indeksy tablicy
        int tabY = Math.max( 1, s.y+d.y ); tabY = Math.min( tabY, diam );
        int tabZ = Math.max( 1, s.z+d.z ); tabZ = Math.min( tabZ, diam );
 
        if ( result[ tabX ][ tabY ][ tabZ ] == null ){                       // unikamy powtórnego liczenia wyniku
            result[ tabX ][ tabY ][ tabZ ] = new ResultSimple( newParam( s.param, tabX, tabY, tabZ) );
        }
        return result[ tabX ][ tabY ][ tabZ ];
    }
 
private boolean tooFar(ResultSimple point, ResultSimple origin) {
        int far = 5;
        return  (Math.abs(point.x - origin.x) > far) ||
                (Math.abs(point.y - origin.y) > far) ||
                (Math.abs(point.z - origin.z) > far);
    }
 
public ResultSimple checkNeighbors( ResultSimple start, int maxDeep ) {
        Vector[] vectors = {
                new Vector(-1,-1,-1), new Vector(-1,-1,0), new Vector(-1,-1,1),
                new Vector(-1,0,-1), new Vector(-1,0,0), new Vector(-1,0,1),
                new Vector(-1,1,-1), new Vector(-1,1,0), new Vector(-1,1,1),
 
                new Vector(0,-1,-1), new Vector(0,-1,0), new Vector(0,-1,1),
                new Vector(0,0,-1),                               new Vector(0,0,1),
                new Vector(0,1,-1), new Vector(0,1,0), new Vector(0,1,1),
 
                new Vector(1,-1,-1), new Vector(1,-1,0), new Vector(1,-1,1),
                new Vector(1,0,-1), new Vector(1,0,0), new Vector(1,0,1),
                new Vector(1,1,-1), new Vector(1,1,0), new Vector(1,1,1),
        };
 
        double begin = Math.round(start.sum);
        double max = begin;
        ResultSimple best = start;
        for (Vector one : vectors) {
            ResultSimple temp = giveResult(start, one);
            double tempVar = Math.round( temp.sum );
            if ( tempVar > max ) {
                max = tempVar;
                best = temp;
            }
        }
 
        if ( maxDeep > 0 && max > begin ) {                  // kończy gdy nie znaleziono większej wartości
            best = checkNeibours(best, maxDeep-1);           // rekurencja
        } else
            System.out.format(" %.0f %d ", max, 101-maxDeep ); // największe zagłębienie
 
        if (maxDeep == 100) System.out.format(" %.0f %n", begin);
        return best;
 
    }
edytowany 1x, ostatnio: ronaldexim, 2018-07-16 20:47

Pozostało 580 znaków

2018-07-16 20:59
0

OK,
ciut lepiej... Nie mam czasu za bardzo na rozgryzanie Twojego kodu, ale na metodę gradientową mi to nie wygląda, bardziej na wyszukiwanie lokalnych ekstremów w przestrzeni trójwymiarowej, dla tych okrojonych danych... 10k danych to nie jest w sumie bardzo dużo, ale ilość parametrów i ich rozpiętość nie jest mała... Próbowałeś jakoś znaleźć podobieństwa w wynikach w zależności od parametrów ?? Wspominałeś coś o gradiencie, może skorzystaj z jakiejś metody AI, np z sieci neuronowych, są programy i to niezłe (np. SNNS)... Opisz bardziej swój problem, dalej za mało danych... a jeżeli to tajemnica, i masz ochotę, to wyślij mi te rekordy, razem z bardzo dokładnym opisem Twojego zagadnienia... Zobaczę co się da zrobić, może nawet jutro... :)

PS. albo mniej więcej napisz jakie to jest zagadnienie... jakie mniej więcej parametry, jakie są między nimi zależności... jaka jest funkcja kosztu lub sposób w jaki porównujesz dane dla określonego zestawu parametrów, bez tego nie zrozumiem Twojego problemu... :)

edytowany 1x, ostatnio: hurgadion, 2018-07-16 21:11

Pozostało 580 znaków

2018-08-06 11:05
cs
1

Spróbuj poczytać o algorytmie Levenberga-Marquardta i zastosować jakąś bibliotekę, która implementuje ten algorytm np. tutaj. Samodzielnie tworzenie całego aparatu obliczeniowego to nie jest najlepsza droga, spróbuj zainwestować ten czas na poznanie gotowych klocków i z nich zbudować coś co da rezultat.

Pozostało 580 znaków

2018-08-09 13:37
1

Tak mi się jeszcze przypomniało... Looknij może na TensorFlow może tam znajdziesz coś dla Ciebie konkretnego... Natomiast temat optymalizacji jest wyjątkowo szeroki, a czasem bardzo skomplikowany...

Pozostało 580 znaków

2018-08-09 18:01
cs
1

Hurgadion, SSN to właściwie uniwersalny aproksymator, który sam sobie dobiera parametry i "odpowiednie" funkcje, a zadanie kolegi to dobór parametrów do gotowej funkcji. Po drugie SSN nadają się do oceny jakościowej typu dobrze - źle, pasuje - nie pasuje itd. W ocenie ilościowej radzą sobie dużo gorzej. O metodzie L-M piszę, bo kiedyś stosowałem, więc ewentualnie mógłbym pomóc.

Pozostało 580 znaków

2018-08-09 18:37
0

całkiem możliwe, nie wykluczam... natomiast temu Panu chyba jeszcze chodzi o ewentualną predykcję... z tego co się orientuję, to on szuka rozwiązań dla ekonomicznych procesów, więc deterministyczne metody mogą nie pomóc... może bardziej stochastyczne... a SNNS z tego co się orientuję można oprogramować... w ogólnej sytuacji najważniejsze jest rozpoznanie problemu... i dobór do niego najbardziej optymalnej metody... obawiam się jednak, że dla procesów ekonomicznych ciężko znaleźć dobrą metodę... :)

sorki, pomysliłem SNNS z SNN... ale może załapałeś... ;) czasem czytam teksty po sobie... :) - hurgadion 2018-08-09 20:36

Pozostało 580 znaków

2018-08-09 20:59
0

Całość tematu traktuję edukacyjnie, więc dziękuję za wszystkie sugestie. Ostatnio coś zwolniłem - pewnie te upały ;-) Doszlifowuję fragment kodu wstawiony wcześniej - 4 parametry, łatwiejsze ustalanie zakresu i dokładności optymalizacji. Teraz myślę, czy nie da się zaprząc do roboty GPU.

Pozostało 580 znaków

2018-08-09 21:48
0

Generalnie temat jest bardzo trudny, i poza moim zasięgiem, z wielu względów... Natomiast niewątpliwie przy próbie jakichkolwiek predykcji wskaźników ekonomicznych należy również brać pod uwagę zewnętrzne czynniki makroekonomiczne wpływające na zmiany danego wskaźnika, można szukać trendów, ważna jest też analiza wahań okresowych (proponuję poczytać)... ważna jest także nieprzewidywalna Polityka (niestety)... oraz czynniki spekulacyjne... Także zamiast wyliczania konkretnych wartości lepiej (moim zdaniem) zająć się metodami ciut bardziej zaawansowanymi... a jak masz (macie) ochotę, to proponuję taką lekturkę: https://www.opokatfi.pl/sites[...]files/losowosc_a_gielda_0.pdf

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0