algorytm poszukujący optymalnego zestawu parametrów

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.

3

Monte carlo to nie do końca.

Szukasz algorytmów optymalizacyjnych generalnie.
jak wynik (funkcja celu) w zależności od parametrów ma skomplikowaną postać to algorytmy genetyczne sprawdzają się dobrze,
jak zależnośc celu od paremetrów jest liniowa to jest coś takiego jak optymalizacja liniowa, metoda simpleks (są algorytmy w javie),
jak zależnośc jest mniej więcej wielomianowa (kwadratowa zwłaszcza) to masz tzw. metody gradientowe (najszybszego spadku itp).

(kurteczka, dawno już się w numeryczne optymalizacje nie bawiłem)

0

sieci neuronowe
Dla 4-9 parametrów szybkość nie powinna mieć znaczenia - na upartego brute force z lekkim tuningiem też by przeszło...

1-100 to liczby całkowite czy float?

0

Całkowite.
Jedna symulacja trwa 200-300ms czyli dla 4 parametrów i zakresu 1-100 brute force zajmie prawie rok.
Obecnie optymalizuję po 1-2 parametrze.
Sieci neuronowe chyba mnie teraz przerastają - choć wgryzę się w to pewnie kiedyś.

Poczytam o metodach gradientowych bo wykres zależności pewnie będzie miał gdzieś maksimum.

krwq napisał(a):

sieci neuronowe
Dla 4-9 parametrów szybkość nie powinna mieć znaczenia - na upartego brute force z lekkim tuningiem też by przeszło...

1-100 to liczby całkowite czy float?<

jarekr000000 napisał(a):

jak zależnośc jest mniej więcej wielomianowa (kwadratowa zwłaszcza) to masz tzw. metody gradientowe (najszybszego spadku itp).

0

A czy jest tam jakiś porządek / monotoniczność w wynikach czy nie? Bo heurystyki zwykle opierają się na takich rzeczach jak jakiś gradient albo na tym, ze składanie dobrych rozwiazań daje dobre rozwiazanie itd. Pytanie czy u ciebie jest taka charakterystyka, czy to totalny random?

1

Do algorytmów genetycznych możesz zerknąć np. na: https://apacheignite.readme.io/docs/genetic-algorithms

Do optymalizacji wielokryterialnej szukałbym gotowców, szybkie google: http://www.optaplanner.org/

1

Jedna symulacja trwa 200-300ms czyli dla 4 parametrów i zakresu 1-100 brute force zajmie prawie rok.

A nie dałoby się tego jakoś zrobić równolegle?

np. puścić na 32 corach za 4zł/h lub 8 corów na miesiąc za 400zł https://www.ovh.pl/public-cloud/instances/cennik/ :D

0

Wyniki nie są losowe. Sąsiednie wartości danego parametrów dają zbliżone wyniki ale gdzieś jest maksimum (zakładam, że jedno).
Problemem jest ilość parametrów, które mogę optymalizować. Szukam metody dającej dość dobre przybliżenie optimum w akceptowalnym czasie.
Najprościej jest ustawić "step" dla pętli na 10 zamiast 1 a w drugim przejściu analizować zawężony obszar.
Będę oczywiście pracował nad samą symulacją - tu pewnie też wycisnę rząd wielkości.

@WeiXiao Kolejny trop ;-) wielowątkowość - pewnie większość moich rdzeni się leni :-D

@yarel Na pytanie o charakter zależności - po krótkim Googlowaniu myślę, że jest ciągła, ograniczona, rózniczkowalna

Shalom napisał(a):

A czy jest tam jakiś porządek / monotoniczność w wynikach czy nie? Bo heurystyki zwykle opierają się na takich rzeczach jak jakiś gradient albo na tym, ze składanie dobrych rozwiazań dale dobre rozwiazanie itd. Pytanie czy u ciebie jest taka charakterystyka, czy to totalny random?

1

ciągła, rózniczkowalna

Więc może metody gradientowe będą się nadawać? Taka wersja mega naiwna to po porstu wybranie losowego punktu, wyliczenie wartości w punktach dookoła a następnie wyznaczenie gradientu (czyli kierunki w którym "rośnie") i potem przesuwanie się zgodnie z gradientem.

0

Dzięki za podpowiedzi.
Starałem się poprawić symulację.
Wyrzuciłem niepotrzebne chwilowo obliczenia.
Symulacja obejmowała 7-16k rekordów na linii czasu dając 0,5-1,5% zdarzeń do analizy.
Warunki ulegały zmianie w czasie więc podzieliłem zakres symulacji na kawałki po 1-2k. Przy 5-15 zdarzeniach na cykl uznałem, że ryzyko przypadkowych, dużych fluktuacji jest akceptowalne.
Zamiast pętli użyłem strumieni.
Namęczyłem się trochę z parallel() bo działająca symulacja zaczęła sypać błędami.
Udało się w końcu zejść do 2,60-3 ms na symulację.

Teraz myślę nad zrobieniem mapy gdzie bym zaznaczał kombinacje parametrów dające zwykle słabe lub dobre wyniki - w formie kilku-wymiarowej tablicy. To będzie punkt wyjścia dla metody gradientowej.

Nie chcę też "przeoptymalizować" przez zbyt dokładne dopasowanie się do danych historycznych.

1

Hej,
zagadnienie jest tak ogólne, że wypowiem się ogólnie:

  1. jeżeli zagadnienie jest liniowe, to metoda sympleks (lub jakiś odpowiednik), rozwali Twój problem szybko...
  2. jeżeli zagadnienie jest nieliniowe, to problem jest dużo trudniejszy...
    a) można stosować metodę próbowania, trochę podobne do Monte Carlo...
    b) poczytaj też o MiniZinc, to takie fajne narzędzie do wyszukiwania rozwiązań optymalnych...
    c) tak jak piszą, spróbuj wykorzystać Sparka, może jakieś metody Machine Learning (ma wbudowane), a może nawet brute force, z lekka optymalizacją, wystarczy przy wykorzystaniu obliczania równoległego...

Jeżeli chcesz jakieś wskazówki bardziej konkretne, to opisz dokładnie problem... :)

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;

    }
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... :)

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.

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...

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.

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ę... :)

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.

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/default/files/losowosc_a_gielda_0.pdf

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