Generalizált optimalizációs megoldás

A gyakorlati problémák felírhatók sok ismeretlenes egyenletként, melyek az ismeretlen faktorok közti összefüggéseket írják le. Nem tudjuk viszont sok esetben, hogy milyen értékek adják a legjobb megoldást.

Kutatásom célja egy olyan megoldás létrehozása volt, ahol ki tudom küszöbölni a globális helyetti lokális optimumon való megragadását az eljárásnak azért, hogy egy még jobb eredményt találjon.

Videó hossz <7 perc.

https://youtu.be/HEqci50boOw

(ropog néha a mikrofon, ezért elnézést)

( sinexton | 2022. 11. 29., k – 13:16 )

Pár ötlet alkalmazási területekre:

- 1 és több dimenziós függvény illesztés adat pontokra

- statisztikai eloszlás illesztése adat pontokra

- reinforcement learning-nél tanító adatok generálása szimulációs környezetben

- fizikai konstrukció optimalizálása vagy jobb találása (például mi a legjobb váz felépítés egy homokfutó gépjárműhöz sok szempontot figyelembe véve)

( rpsoft v | 2022. 11. 29., k – 13:21 )

tl; didn't watch

Mi a módszer, simulated annealing?

(Szerintem elegendően általános függvényosztály esetén be tudom bizonyítani, hogy nem létezik olyan algoritmus, ami véges lépésben garantáltan nem ragad meg lokális minimumon, hiszen még folytonos függvény is szinte tetszőlegesen csipkés lehet, de azért olyan lehet, ami ritkán; BFGS, gradient descent úgy, hogy lendülete is van, egész jó lehet, vagy a szimulált hőkezelés (monte carlo), csak az meg elég lassú a többi módszerhez képest, amikor van nemnulla gradiens, esetleg pl. a Numerical Recipes-nek van trükkös szimulált hőkezelés - amoeba kombinációja, de azért vadul csipkés függvényre meg az rosszabb, mint a sima MC).

Soha nem ragad lokális optimumban a megoldásom (a választott maximum intervallumon belül a lebegőpontos számítás korlátain belül), csak megnő a számítási idő természetesen. Akár közel végtelenre.

Tehát igazából nem is a lokális optimumban maradás a kérdés a működése szempontjából, hanem a számítási idő. A megoldásomat gyorsabbnak találom nehéz feladatoknál mint generalizált megoldás, más generalizáltakhoz képest.

A módszer MC szimuláció okosítása. A kulcs ötlet miatt gyorsabban konvergál a search space limitálása nélkül.

Soha ne mond, hogy soha :)

Ha definiálok egy olyan függvényt, mondjuk a [-1, 1]^10 kockában, ami mindenhol az x^2-tel egyenlő, kivéve egyetlenegy pontot (ami nem a 0), ahol -100 (de csak egzaktul abban az egy pontban, ill, ha szőrözni akarunk, akkor folytonosan, csak éppen a kis, folytonos csúcsot akörül az egyetlen egy pont körül úgy elhelyezve, hogy a szélessége a numerikus epszilonnál jóval kisebb legyen, tehát a gépi számábrázolásban tényleg csak egy pont marad), azt megtalálja?

Ettől függetlenül érdekes lehet. Leírtad valahol betűvel is az ötletet?

Troll, vagy nem, a kerdes jogos.

Az, hogy kitalalsz valamit, ami mukodni latszik, egy jo kezdet.

Ha atmegy egy rendes review-n az otlet, az meg jobb. A HUP kozonsege azert nem feltetlen egy nemzetkozileg elismert review forum, de neha erkezik par ertelmes hozzaszolas is (nem ezekert jarunk ide) :)

Majd, ha bizonyitod, vagy valaki bizonyitja, hogy az elmelet valoban jobb (legalabb bizonyos problemara, bizonyos korulmenyek kozott, es persze a "jo" sem egy onkenyesen megvalasztott meroszam), mint a tobbi, akkor PhD.

Nem elmondani, titkolozni, sejtetni nem jo. Sertettet jatszani meg kevesbe.  Olyan perpetuum mobile meg nullponti energiakicsatolas szaga van tole a dolognak.

Szerintem jól tudod hogy nem a kérdéssel van a baj :)

Mivel normális hangnemben írsz, válaszolok: Mérlegelem még, hogy van-e értelme a megnyitásnak üzletileg. Ez egy szakmai blog a részemről érdekességekkel. Sokszor megosztok publikusan részleteiben eljárásokat, melyek megoldásként szolgálnak nálam.

Hat, ha uzletet tudsz belole csinalni, akkor hajra! Az uzleti modelledrol is irhatnal, engem az is erdekelne :)

Viszont, amig az uzlethez akar jok is lehetnek biznyosos fokig a pozitiv jelzok pl., hogy "generalizalt", meg mindennel is jobb. Azonban egy kb. szakmai forumon (HUP, de hat legyen) konnyen felszalad par szemoldok az ilyenek miatt. Jopar ember itt tanult, es akar aktivan alkalmazza is a statisztikai ismereteit a napi munkajaban, legyen az kozgazdasag, penzugy vagy informacioelmelet. Par allitas azert tulzonak hathat, es nehezen hiheto, miutan (lehet, hogy 15-20 ev ulepedes utan) megertjuk, hogy mirol is ertekezett anno Shannon vagy Bhattacharyya.

Az irasaid egyebkent erdekesek, es emelik a szinvonalat. Semmikepp se hagyd abba!

https://en.wikipedia.org/wiki/Rosenbrock_function

Megtalálja az [1,1] optimum pontot. 10 másodperces futást adtam neki és csak 1 másodpercenként kérek kimenetet az aktuálisan talált legjobb optimumról. Intervallumot definiálva -10^3 és 10^3 között ez a kimenet:

 

mc_min_single proc{|x,y| a = 1; b = 100; (a-x)**2 + b*(y-x**2)**2 }, nil, -1e3, 1e3, time_min: 10, time_max: 10, time_print: 1

#1  error 10766814447657.701  time 2.77e-05s  param 573.6094690763118 899.5840619776343

#1254  error 6.575064281635551e-06  time 1s  param 0.9976532681664249 0.9952087035594538

#1538  error 2.4639774738723832e-15  time 2s  param 1.0000000495829044 1.0000000994006104

#1641  error 3.095657257542796e-22  time 3.07s  param 1.0000000000175542 1.0000000000352274

#1698  error 5.427856065986324e-28  time 4.36s  param 1.0000000000000215 1.0000000000000422

#1712  error 3.988677952023741e-29  time 5.36s  param 0.9999999999999938 0.9999999999999875

#1716  error 1.232595164407831e-30  time 7.89s  param 1.000000000000001 1.0000000000000022

#1717  error 4.930380657631324e-32  time 10s  param 1.0000000000000002 1.0000000000000004

 

Intervallum definiálása nélkül, teljesen automatikus módon (itt kellett neki 30 másodperc):

 

mc_min proc{|x,y| a = 1; b = 100; (a-x)**2 + b*(y-x**2)**2 }, time_min: 10, time_max: 10

error 4.930380657631324e-32  time 30s  param 1.0000000000000002 1.0000000000000004

 

Megnézem majd a többit is.

Powell negyedfokú-ra nem találok infót, de ahogy a videóban mutatom, sokkal komplexebb kimenetet kezelek. Generálok pár random egyenletet és megoldását:

 

Ez 8-ad fokú és van ismeretlen kitevőben is, stb:

x4 + 2 - 16 - x4 - exp( x5 ) + 15 - 9 * x1 ** x2 + x1 ** 8 - 10 + x2 * 16 + x3 = 10

x1 = 1.3001637756974223
x2 = 1.6642987003611736
x3 = 5.340875307294438
x4 = 9.105743895300119
x5 = 1.9747200303974215

=> "error 0  time 0.362s"

 

19-ed fokú:

x2 - 8 + asinh( x2 ) + 24 * 18 - x4 + 5 + exp( x5 ) ** cosh( x2 ) ** 19 - 2 * 5 - x3 + x2 * x5 ** 4 * 25 + 2 * x3 - cosh( x3 ) * x5 * x5 - x4 + x2 + sin( x1 ) = 16

x1 = 23.1180816912583
x2 = -7.174630236873243
x3 = 2.568593483660327
x4 = -9.809614574398552
x5 = -1.2201098012606149

=> "error 0  time 5.72s"

 

22 - 27 * x2 - 5 + 16 * 8 - 20 * 9 * x3 + x2 * x5 - tan( x6 ) - x6 - 19 - 9 - x1 - sinh( x2 ) ** 11 - sinh( x5 ) + 20 - x6 ** 30 + asinh( x1 ) ** exp( x4 ) - x2 ** tanh( x6 ) - x6 + x5 - x1 = 29

x1 = 0.2584124611175178
x2 = 0.21058379187327173
x3 = 0.567076578237669
x4 = -0.5251906679102831
x5 = -0.5263107026525904
x6 = -0.862545259195803

=> "error 0  time 2.26s"

 

cosh( x4 ) * 4 - 5 + cos( x5 ) + 13 + 21 + x1 - 10 * 18 * asinh( x6 ) * 21 + 21 - x4 + x5 ** 6 * x6 - 3 - x4 ** x3 ** x6 + x6 ** x4 - cos( x5 ) + 2 + x4 = 10

x1 = -0.0004141372612761436
x3 = 0.034457028654801714
x4 = 0.08270889079026573
x5 = 0.09207688128067658
x6 = 0.011538274913461136

=> "error 0  time 0.549s"

Csak annyi kifogasom van, hogy egy n-valtozos fuggvenynek altalaban n-1 dimenzios megoldasai vannak a f(x) = c egyenletre, igy ha talalsz is megoldast, az valoszinuleg egy vagy tobb osszefuggo feluleten van. Ha pedig beleveszel paratlan hatvanyu valtozokat, mint peldaul az x4 az elso peldaban, akkor altalaban lesz megoldas (de pl a (x + 1)**2 +1 -ben van  linearis tag, de nincs megoldasa 0-ra). 

A gravitacios peldadra ettol fuggetlenul kivancsi vagyok, ott nem kellene differencial-egyenletet megoldani?

Erdekes amugy, ahogy ezeket megoldod, a lokalis fugvenyillesztest szerintem mar mas is csinalta (asszem van conic bundle library neven hasonlo), van aki neuralis halokkal kozelit, aztan azt oldja minimalizalja (ha nem is epp gyokot keres), szoval van benne potencial.

Az nem baj, ha nincs megoldása az egyenletnek, mint x^2 = -2 esetén. A célom - ahogy írtam - a minél pontosabb numerikus megoldás keresése. Erre van szükségem.

A gravitációs példában magát a differenciál egyenletet szimulálom. Tehát az elhajított kő minden egyes iterációban a gravitációs vektorok eredője felé mozdul megfelelő mértékben. Ezzel végig szimulálom a folyamatot és megnézem, hogy mekkora volt a legkisebb hiba. Ami a kő legkisebb távolsága a célponttól. Ezt minimalizálom. Vagyis cél, hogy minél pontosabban érjen a célba.

Majd új paramétereket kérek (szög és sebesség) és újra kiszámolom. Így történik meg a közelítés. Nyilván a hibák mindig összeadódnak, ezért fontos a lépték felbontása. Végtelen finomságban nem gondolkodhatunk itt. káosz elméletileg elrobban mindig a hiba, ez van. De attól még a szimulációnak van értelme. Ha például olyan a feladat, ahol nem ismert az integrál vagy egyéb limitáció van.

Ebben nincs semmi új. Csupán az eljárásomat tesztelem. Mivel azt látom, hogy a rengeteg komplex, véletlen módon generált függvénnyel is elég jól elbán, így nyilván várható volt hogy itt is segít.

A függvény illesztésnél számomra nem tetszenek a neurális alapú és hasonló megoldások. Részben mert nagyon lassú, mert sok újratanítás kell. Vagy ha előzőleg volt szimulációban tanítva, akkor meg azért nem jó. Mert az új probléma erősen eltérhet. Szerintem itt egy NN nem tud kidomborodni. Máshol van az ereje.

Ráadásul - ahogy mondtam - nem tetszik, ha túl sok a kiindulási paraméter. Persze, a számukat nem lehet nullára csökkenteni, de ha csak 1 marad és az is jól automatizálható, akkor előrelépésnek veszem ahhoz képest, ha 10-et definiálni kell, mint például egy genetikai algo esetén.

Én egy olyan megoldást kerestem, mely extrém módon képes illeszkedni. Külsőleg egészen egyszerű, trükkös a működés. Ezért gondolom sokkal robusztusabbnak másnál.

Természetesen sok kutatás és tesztelés kell még. Ha publikus megosztás lesz, akkor megírom majd ide az infót. Még nagyon friss a dolog.

Köszi.

BTW függvény illesztést folyamatosan használok vele négyzetes hibával. A következőket illesztem tetszőleges 1D-s adatpontokra (ezekre van szükségem):

exp és log

Sigmoid-ok:

tanh, atanh, sinh, asinh

Parabola formához:

x^2, cosh

A megoldásom bármire tud illeszteni értelemszerűen. A kérdés a hiba mértéke ugye. Elég pontosnak találom.

Ami még fejlesztés alatt van részemről, az a futási idő maximumának teljesen automatikus meghatározása. Ez szintén kutatást és még több fejlesztést igényel, mert egy exponenciálisan növekvő időre kell limitet szabni, de közben nem akarjuk hogy túl rövid ideig fusson. Egy gyakorlati szempontból jó adaptivitást célzok.

Ez lehet egy sima exponenciális limit az eddigi időkre, melyek az új találatok között tellett el. Csak előtte érdemes egy log transzformációt végezni az adatokra, mert sok nagyságrendi különbségek vannak közte (pl 1e-8 és 1e2). Ez visszább húzza az exponenciális különbségeket.

De ez csak egy ötlet. Mélyebb vizsgálatot érdemel.

Egy változós az még nem olyan fájdalmas általában, hacsak nem oszcilláló. Vágj ki egy random darabot egy Bessel-függvényből valamilyen jó nagy x környékén, onnan vegyél random pontokat, és arra próbáld meg megilleszteni a sin(x + delta)-t.

A Powell fv egy implementációja (x az input):

double t1 = x(0) + 10 * x(1), t2 = x(2) - x(3), t3 = x(1) - 2 * x(2), t4 = x(0) - x(3); return t1*t1 + 5 * t2*t2 + t3*t3*t3*t3 + 10 * t4*t4*t4*t4;

Fletcher-Powell:

{
               double theta = (x(0) == 0) ? 0.25 : ((x(0) > 0) ? atan2(x(1), x(0)) / 2 / M_PI : atan2(x(1), x(0)) / 2 / M_PI + 0.5);
               double t0 = x(2) - 10 * theta;
               double t1 = sqrt(x(0)*x(0) + x(1)*x(1)) - 1.0;
               return 100 * t0*t0 + t1*t1 + x(2)*x(2);
}

Ezek olyanok, amik egy sima gradienst kinyírnak, és a különböző javított módszerek (BFGS, kvázi-Newton, ...) sikeresen elbánnak velük. A Numerical Recipes-ben van egy példa, ami a gradiens-alapú optimalizációnak nehéz szokott lenni, a szimulált hőkezelés tesztelésére. A FORTRAN verziót meg lehet nézni a honlapjukon ingyen. Nem másolom be, copyrightos, de megtalálható.

Vigyázz, melyik verziót keresed elő. Azért az eredeti fölött már eljárt az idő, és az első C változatnak rettenetes a kódja (kb. olyan, mintha géppel fordították volna FORTRAN-ból). A 2. kiadás FORTRAN verzióban már jobb módszerek vannak, és a jelenlegi legújabb C++-osban még újabbak is.

Ha esetleg ki akarod adni a kódját annak, amit csinálsz, akkor nézd meg H. M. Antia, Numerical methods for scientists and engineers c. könyvét, az indiai kiadást néha meg lehet szerezni egész olcsón (3. kiadás: Hindustan Book Agency, New Delhi, 2012). A NumRec jobb, de Antia nem kötekszik, hogy mit csinálsz a kóddal (ha beleírod, hogy honnan van). A NumRec kód licenszelése egy rémálom.

A kód fent van a szerző honlapján, https://www.tifr.res.in/~antia/nmse3.html

Papír könyvet találsz pl. az Abebooks-on, vagy amazon-on, de mostanra elég drága lett (úgy nézem, az indiai könyvkiadás is olyan, mint a magyar, nyomtatnak egy adagot, aztán hagyják kifogyni, és aztán vagy utánnyomják, vagy nem, ha már elég drága lett az utolsó pár példány meg a használt; angolok/amerikaiak azért nem szokták olyan sokáig out-of-print hagyni, ha volt valami sikere).

Koszi, ez jo!

Megneztem a ToC-ot, es valoban nagyobb a Numerical Recipes altal lefedett terulet. De van talan par dolog, amit ez a konyv jobban targyal.

Hobbinak, olvasgatni, agyat nem elsorvasztani mindketto nagyon hasznos. De lehet, hogy csak nekem perverziom a regi evekbol visszaolvasni dolgokat. Nagy kedvenc meg Simonyiek Villamossagtanja. Abbol pl. megerthetjuk, hogy miert is kell a Numerical Recipes :)

A konyvkiadas sajnos ilyen. Jott az info, hogy a fent emlitett villamossagtan konyv kaphato a V2 konyvesboltjaban sok-sok ev utan ujra (az egyik docens meg talalkozott valakivel, aki latta a konyvet). Aranyaron mertek, de az utolsok egyiket kaparintottam meg, pedig nagyon rohantam. A fizika konyv is igy lett meg. Cserebe, gyakorlatilag ipari hulladek minosegu jegyzetekbol tanultunk. Ugyanazt irtak le, csak erthetetlenul, es rakas hibaval, de meg az errataban is.

( sinexton | 2022. 11. 29., k – 15:51 )

Szerkesztve: 2022. 11. 29., k – 15:56

Közben még tesztelem a megoldást szimulált komplex gravitációs térben, ahol több objektum kreál gravitációs teret és egy követ kell eldobnom adott szögben adott sebességgel (mindkettő ismeretlen számomra), hogy egy másik pontra érkezzen pontosan, miközben ide oda rángatják haladás közben az útba eső közeli objektumok vonzásai. Tökéletesen hozza a megoldást. Nem kell integrálni és komplex elemzést végezni.

( DieHappy | 2022. 11. 30., sze – 09:57 )

Ha jol ertem, akkor egyenletmegoldast keresel optimializalassal?

Pl. van egy f(x) = 8 kenyszer, ahol keresed x-et, es ugy oldod meg, hogy 

argmin |f(x) - 8|   -t vagy egy hasonloan alulrol korlatos fuggvenyt minimalizalsz? Es ekkor a kerdes, hogy megtalalod-e az egyenlet megoldasat, amikor f(x) = 8, vagy csak egy kozelito megoldast.

Igen, természetesen a különbséget minimalizálom. Ebben nincs semmi új.

A kérdés az, hogy el tudok-e jutni elfogadható időn belül a megoldásig. Tesztelek evolúciós megoldásokat, és sokszor rosszabb eredményt adnak az enyémnél, vagy pedig nem találnak megoldást.

Fontos látni, hogy általános megoldásról beszélek. Tehát nem arról, hogy egy algo-t egy speciális egyenletre optimalizálunk. A célom az, hogy tetszőleges változó számú feltétel rendszerre kapjak megoldást, de úgy, hogy SEMMIT nem definiálok paraméterként. Vagyis kizárólag non-parametrikus megoldás kell.

Ahol más általam tesztelt algo megragad, ott tovább tud menni az enyém eddigi empirikus tesztjeim alapján. A héten fejeztem be a végleges kidolgozását, így még elég friss.