Random search

[JKZ]

Stel je voor, je moet een speld zoeken in een zesdimensionale hooiberg.

Je kunt van twee punten in de hooiberg bepalen welke van de twee het dichtst bij de speld zit.

Wat meer wiskundig: ik heb een functie (waar ik weinig van weet) van een aantal variabelen, weet wel dat hij unimodaal is (slechts één extreem). Voor elk stel waarden van de variabelen kan ik de functie berekenen. Ik zoek het maximum.

De snelheid van de computer maakt dingen mogelijk die voordien ondenkbaar waren. Bijvoorbeeld “random search”.

Begin zomaar ergens in de hooiberg. Trek zes kleine random getallen en verander daarmee de coördinaten. Is het nieuwe punt beter? Nee, vergeet dat nieuwe punt, trek nogmaals zes getallen en probeer het nog eens. Ja, probeer vanuit het nieuwe punt op dezelfde manier weer een nog beter punt te vinden. En zo kruipen we naar de speld toe.

Niet moeilijk te programmeren.

Bouw een tellertje in en tel steeds het aantal mislukte pogingen om een beter punt te vinden. Ben je op een punt gekomen waarop je na een paar honderd pogingen nog steeds niets beters hebt gevonden, neem dan maar aan dat je op het maximum of althans voor de praktijk dicht genoeg in de buurt zit.

Je moet misschen nog wat experimenteren met de grootte van je random stappen, maar erg kritisch is het niet.

Heb er succes mee gehad bij een probleem waarop alle “gewone” zoekmethodes het lieten afweten.

[Drieske]

En wat is je discussiepunt/vraag?

Overigens heb ik serieuze twijfels bij de eindigheid van je programma. Of weet je de waarde van het extremum?

[eezacque]

Heb je het ook vergeleken met situaties waarin de bekende methoden wel uitkomst bieden?

Heb je geexperimenteerd met grillige functies, waarin de kans dat je raakschiet erg klein is? Denk bijvoorbeeld aan een spiraalvormige geul die rondom een kegel naar beneden cirkelt.

Heb je geexperimenteerd met een functie die vrijwel constant is? Denk aan een kegel met een tophoek van bijna 180 graden.

Ik mis een zinvol terminatiecriterium, en een zoekrichting en stapgrootte. Je zou 'ns kunnen zoeken op probabilistische algoritmen, er is volgens mij wel aan gewerkt, maar de benadering die je hier schetst is net even te makkelijk...

[JKZ]

Ik schreef dit omdat ik dacht daar misschien iemand een plezier mee te doen en natuurlijk ook om te horen over eventuele ervaringen van anderen met random search.

In mijn geval ging het om het schatten van positie en snelheidscomponenten van een geluidsbron die geluid met een constante maar onbekende frequentie uitzendt (target motion analysis TMA). Beschikbaar zijn een stel onnauwkeurige waarnemingen van de richting waaruit het geluid komt en van de frequentie (met daarin variaties door dopplerverschuiving) op achtereenvolgende tijdstippen. Je probeert een veronderstelde situatie te vinden zodanig dat wat je dan had waargenomen zo goed mogelijk lijkt op wat je werkelijk hebt waargenomen.

Anderen en ik hadden veel geprobeerd met Kalman filter maar dat lukte maar steeds niet, proces te niet-lineair, had problemen met de stabiliteit. Mijn random search liep goed, zelfs als je bijna absurde veronderstelde situaties als startpunt koos. Amerikaanse collega´s hadden het werkend met Gauss-Newton, maar zijn overgestapt op random search.

Op internet is het een en ander over random search voor optimisatie te vinden, beetje vervelend dat de term random search ook in andere betekenissen wordt gebruikt.

Terminatiecriterium kan inderdaad een probleem zijn, was het in mijn geval niet. Met stapgrootte moet je wat experimenteren, maar heeft weinig invloed op het resultaat, wel op rekentijd, tegenwoordig niet meer zo´n probleem

[Drieske]

Maar ik zie helemaal niet in hoe het in jouw situatie ooit kan eindigen. Hoe weet je ooit of je het maximum hebt bereikt? Je hebt oneindig veel punten om te proberen.

[JKZ]

Drieske, Experiment met dezelfde dataset maar met steeds andere beginpunten leverde (tot onse verrassing) met zeer grote nauwkeurigheid steeds hetzelfde resultaat.

Ik denk dat de random search, daarom kom ik ermee aandragen, soms uitkomst kan bieden bij hardnekkige optimalisatieproblemen vooral op het gebied van toegepassingen, waar het soms anders toegaat dan in de zuivere wiskunde. In de praktijk zal dat " zijn we er al" vaak niet zo´n probleem zijn.

In het geval van die TMA bijvoorbeeld, ben je al tevreden en kun je al stoppen zodra je zodra je criterium een bepaalde waarde passeert, dus als je een veronderstelde situatie hebt gevonden die waarnemingen zou opleveren die voldoende lijken op wat je hebt waargenomen. Dan is het misschien nog niet optimaal maar al mooi genoeg.

[Drieske]

Maar dan weet je al op voorhand wat je maximum is?

[eezacque]

Als ik het goed begrijp heb je een methode gevonden die voor een enkele hooiberg met bijbehorende speld werkt?

[Drieske]

In mijn ogen werkt er niets aan die methode zonder a priori kennis van wat je zoekt.

[Xenion]

Ik denk dat JKZ misschien een beetje slordig is in zijn verwoording. Zoals het hier beschreven wordt ziet het er aannemelijker uit.

[eezacque]

Ik denk dat JKZ misschien een beetje slordig is in zijn verwoording. Zoals het hier beschreven wordt ziet het er aannemelijker uit.

Ik lees daar "optimum to be approached very slowly and moreover that the methods were actually unable to locate a solution of adequate fitness, unless the process was started sufficiently close to the optimum to begin with." Het lijkt me een zeer beperkt bruikbare methode...

[Drieske]

Het geeft inderdaad al een vollediger beeld. Maar ik heb inderdaad ook serieuze twijfels bij de bruikbaarheid in diverse situaties.

[Xenion]

Het enige voordeel is dat je geen gradient moet berekenen en dat het zelfs niet nodig is om een analytische uitdrukking van de kostfunctie te hebben.

Zulke methoden zijn '0de orde', terwijl Newton, en Gauss Newton (en varianten) respectievelijk 1e en 2e orde methoden zijn. Orde in de betekenis van afgeleide. In het algemeen convergeer je sneller als je meer inzicht in de functie hebt, i.e. 1e en hogere afgeleiden.

[Drieske]

Okee, maar je hebt, in veel situaties lijkt me, ook geen enkele garantie dat je ook maar in de buurt van je maximum zit wanneer je proces stopt, toch? Je zult immers steeds moeten toevoegen dat er na x stappen moet gestopt worden.

En ik zie ook helaas nog steeds niet hoe je zou kunnen zeggen wanneer je dicht bij je maximum zit, tenzij je de waarde van het maximum kent.

[Xenion]

Als je niet in het wilde weg gaat random samplen, maar steeds in de buurt van je 'huidige maximum' blijft, dan zal je wel convergeren naar een lokaal maximum. Maar er is zeker geen garantie om het globale maximum te vinden als er lokale bestaan.

Het is zeker niet de beste methode, maar ze kan zeker gebruikt worden als het bijvoorbeeld teveel werk is om de afgeleiden uit te rekenen of als je numerieke benaderingen van de afgeleiden niet blijken te werken.