Genetische algoritmes versus deterministische algoritmes

[armageddon_2k1]

Naar aanleiding van http://gathering.tweakers.net/forum/list_messages/1525716 kwam ik daar de volgende opmerkingen tegen:

Iedereen die iets met evolutionary algorithms doet kan je vertellen dat je ze NIET moet gebruiken, tenzij er geen betere oplossingen beschikbaar zijn. Als je ze dan toch moet gebruiken, dan werkt een gespecialiseerd algoritme beter dan een generiek algoritme, maar ik zie hier daar niets over.

en

Ik vind genetische algoritmen stom en dus neig ik naar pedorus' suggestie om gewoon een deterministisch algoritme te ontwikkelen

Nu wil ik echter geen topic kapen, maar start ik een nieuwe omdat ik bovenstaande opmerkingen niet helemaal kan plaatsen.

Zelf ben ik niet professioneel bezig met programmeerwerk, maar vind ik het hobbymatig erg leuk en heb onderhand dusdanig veel gedaan, ook voor mijn data-analyses op mijn werk welke puur voor mijzelf zijn en nooit in productie gaan, dat ik van veel talen redelijk veel begrijp, mijn wiskundige kennis aardig op peil is, maar ook nog van heel veel heel veel nog niet weet

Voor mijn afstudeerwerk heb ik uitbundig gebruik gemaakt van genetische algoritmes en dat is puur omdat er, mijn inziens, bijna geen manier bestond om het deterministisch aan te pakken. Wij hadden namelijk data gemeten van 5 sensoren, 3 inputs naar een piloot en 2 outputs die de piloot genereert in 10 verschillende condities en probeerden daar een parametrisch model op te fitten. Aangezien een mens zich niet-lineair gedraagt gaan veel signaal-analyse trucjes niet op. Het model dat we hadden was gebaseerd op biologische kennis en we hadden 20 parameters waar we aan konden draaien. Door middel van een genetisch algoritme kwamen we op hele goede resultaten, zelfs een stuk gedetailleerder dan we hadden kunnen hopen . Bij die 10 verschillende condities zag je de parameters ook erg mooi verschuiven.

Zo heb ik ook ooit eens een presentatie gezien van een bedrijf dat werkt in de carbon fiber polymeer business en die bepaalden de orientatie, ligging en bochten van de carbon fibers in hele specialistische vormen aan de hand van GA en die dingen outperformden veel competitie terwijl ze fabricagekosten ook meenamen in de fitnessfunctie. Ze waren dus vaak beter, maar ook veel goedkoper omdat er minder materiaal gebruikt werd.

Het Travelling Salesman Probleem is er nog eentje waar ik me niet voor kan stellen dat een deterministisch algoritme beter is, maar dat komt misschien omdat mijn kennis niet toereikend is. Het is domweg niet mijn achtergrond en ik probeer de kersen te plukken van de kennis van mensen die dat wel als achtergrond hebben. Zo is ie met brute-force O(n!) en zijn er heuristische algoritmes die O(n^2 * 2^n) halen. GA heeft hier heel goed bewezen een mooie oplossing te genereren.

Ik snap wel wat het grote nadeel van genetische algoritmes is, namelijk je kan niet bewijzen of je antwoord het echte optimum is en je kan dus in een lokaal minimum terecht zijn gekomen.

Echter vind ik GA dusdanig 'elegant' en interessant dat ik benieuwd ben naar jullie mening waarom je het NIET zou moeten gebruiken, want volgens mij zijn er zat problemen waar je domweg niet iets kan gebruiken waarvan je zeker weet dat je het optimum bereikt zonder dat je 1E20 computerjaren tot je beschikking hebt

En hebben jullie voorbeelden over bekende problemen waar GA juist WEL werkt of juist NIET en wat het alternatief is? Er zijn namelijk legio voorbeelden waarom het WEL werkt waardoor ik verbaasd ben dat Iedereen die iets met evolutionary algorithms doet je kan vertellen dat je ze NIET moet gebruiken

[.oisyn]

Hoewel ik altijd sceptisch was tegenover GA moet ik wel zeggen dat ik die opmerking van pedorus gewoon geblaat vind (stond ook eerst in mijn reactie maar heb ik for sake of decency maar weer weggehaald ). GA heeft weldegelijk zijn toepassingen (als voorbeeld: stel ik wil de leestijd van resources meenemen in mijn berekening (wat ik eigenlijk al doe, maar dat terzijde), dan hoef ik alleen maar de cost function aan te passen en veelgebruikte resources verplaatsen zich automatisch naar de rand van de schijf, waar het lezen sneller gaat). En ze blinken vaak uit in hun flexibiliteit en hun eenvoud. Bovendien heeft het zich in de realiteit ook bewezen (niet dat wij mensen nou de meest optimale levensvorm zijn, maar gezien het feit dat we afstammen van eencelligen en verder terug heeft het toch best mooi uitgepakt ). Er tegenover staat wel dat ze vaak gewoon heel erg traag zijn.

[ Voor 20% gewijzigd door .oisyn op 14-11-2012 17:58 ]

[armageddon_2k1]

.oisyn schreef op woensdag 14 november 2012 @ 17:55:
Bovendien heeft het zich in de realiteit ook bewezen (niet dat wij mensen nou de meest optimale levensvorm zijn, maar gezien het feit dat we afstammen van eencelligen en verder terug heeft het toch best mooi uitgepakt ). Er tegenover staat wel dat ze vaak gewoon heel erg traag zijn.

Wij zitten als mensheid evolutionair gezien op het moment gewoon in een lokaal minimum

Wat betreft de traagheid denk ik dat een GA vele malen sneller is dan het vinden van het echte minimum maar dus ten koste van onzekerheid. Echter is het nog steeds vaak vele malen sneller. Op het moment dat GA veel trager is zou ik ook op zoek gaan naar een beter algoritme, mits de tijd (en dus de kosten), het toelaten

[Soultaker]

De reden dat ik genetische algoritmen en (tot op zekere hoogte vergelijkbare technieken, zoals neurale netwerken, simulated annealing, of monte carlo tree search) niet echt elegant vind is dat er geen domeinspecifieke kennis wordt gebruikt, waardoor je vaak geen idee hebt of de vele cpu cycles die je in het algoritme investeert werkelijk bijdragen aan het vinden van een optimale/goede oplossing.

Het is dus grotendeels brute force en vereist een hoop handmatige tuning (wat meestal nattevingerwerk is). Wat is daar elegant aan?

armageddon_2k1 schreef op woensdag 14 november 2012 @ 17:47:
Het Travelling Salesman Probleem is er nog eentje waar ik me niet voor kan stellen dat een deterministisch algoritme beter is, maar dat komt misschien omdat mijn kennis niet toereikend is. Het is domweg niet mijn achtergrond en ik probeer de kersen te plukken van de kennis van mensen die dat wel als achtergrond hebben. Zo is ie met brute-force O(n!) en zijn er heuristische algoritmes die O(n^2 * 2^n) halen. GA heeft hier heel goed bewezen een mooie oplossing te genereren.

Als ik op Wikipedia kijk lijkt de meeste TSP software niet op genetische algoritmen gebaseerd te zijn, maar op meer traditionele optimalisatietechnieken, die overigens ook niet volledig deterministisch zijn, maar dat is logisch aangezien het hier om een NP-compleet probleem gaat.

[armageddon_2k1]

Toevallig ben ik momenteel bezig met neurale netwerken en bayesiaanse netwerken voor mijn werk en ik ben er juist van overtuigt dat je, mits je een goed resultaat wilt hebben, welzeker domeinspecifieke kennis nodig hebt om de inputs voor het neurale netwerk goed te definieren. Je kan namelijk van tevoren al heel veel optimalisatie doen aan je data waardoor je neurale netwerk veel beter performed. Deze optimalisaties kan ik alleen maar doen als ik weet wat er achter die data schuilgaat.

Op het moment ben ik een proef aan het draaien om dit toe te passen bij MRI machines en die zijn zo ontiechelijk complex en de supergeleiding van de magneten kan zich dusdanig raar gedragen dat een normaal fysisch model maken bijna onhaalbaar is. Er lopen bij ons aardig wat PhD's in de supergeleiding rond en die kunnen niet zomaar een model maken van een supergeleidende MR magneet met al z'n interacties

Wat betreft de TSP zeg ik niet dat GA de beste oplossing is, maar juist dat het wel een mogelijke oplossing is die, snel, voor goede resultaten zorgt.

[JustAName]

Met dit onderwerp (GA's) ben ik ook bezig geweest voor mijn studie en ik denk dat het niet zozeer de kwestie is of genetische algoritmen beter of slechter zouden zijn dan deterministische algoritmen, maar meer dat beiden hun eigen toepassingsgebied hebben.

Als je een deterministisch algoritme kan gebruiken, dan is dat naar mijn mening de beste keuze. Dat betekend namelijk dat je al weet welke stappen je moet zetten om het probleem op te lossen, of om tot een gewenst eindresultaat te komen.

Maar als je daarentegen niet weet wat het beste eindresultaat is, of niet weet wat de stappen zijn die je moet nemen om tot een eindresultaat te komen, kan je in mijn ogen het beste een genetisch algoritme gebruiken. Ook kan het zijn dat je misschien denkt dat je weet welke stappen je moet nemen, maar dat een genetisch algoritme een andere kijk op de oplossing geeft, wat je van te voren niet gedacht had.

Dat betekend dan overigens niet dat je totaal geen domein kennis kan gebruiken in een genetisch algoritme, in tegendeel, wat je al weet kan je vastzetten om het zoekproces te sturen. Daarnaast is een GA in mijn ogen juist geen brute force algoritme, aangezien er wel degelijk gestuurd wordt naar een oplossing; door middel van een fitness functie. In die fitness functie zou je bijvoorbeeld óók domein kennis kunnen gebruiken om het zoekproces te sturen. Op die manier maak je van het GA een meer specifiek algoritme.

In mijn ogen zijn er dus legio mogelijkheden om GA's op een juiste manier in te zetten, maar inderdaad alleen als er geen beter algoritme mogelijk is. Ik ben het dan ook eens met de twee quotes in de TS, áls er een beter, of specifieker algoritme beschikbaar is zal die waarschijnlijk beter zijn (omgekeerd: waarom zouden we anders nog specifieke algoritmes hebben?). Maar ik denk juist dat een GA óók als specifiek algoritme ingezet kan worden, met de juiste tuning.

[pedorus]

armageddon_2k1 schreef op woensdag 14 november 2012 @ 17:47:
Er zijn namelijk legio voorbeelden waarom het WEL werkt waardoor ik verbaasd ben dat Iedereen die iets met evolutionary algorithms doet je kan vertellen dat je ze NIET moet gebruiken

lolol, anders haal je gewoon de hele tenzij uit de zin, en laat je de smilie die ervoor staat in dezelfde alinea weg. Dit is trouwens niet iets dat ik zelf heb verzonnen. Dit is een grap die komt van iemand die recentelijk is gepromoveerd op dit gebied. In zekere zin is het niet zozeer geblaat zoals ook in de post hierboven staat: pas als normalere methodes falen, moet je naar genetische algoritmes grijpen.

Natuurlijk hebben genetische algoritmes zo hun toepassingen, er zijn tal van toepassing waar ze de beste resultaten geven (als ik mijn eigen literatuuronderzoek van een aantal jaren geleden mag geloven dan). Over het algemeen gaat het dan wel om specialistische genetische algoritmes (hybrid genetic/memetic algorithms).

Het TSP-voorbeeld vindt ik bijvoorbeeld niet zo'n goed voorbeeld, zoals al is aangehaald is dit probleem overzichtelijk genoeg voor normale heuristieken/exacte oplossingen. Zie bijvoorbeeld http://www.tsp.gatech.edu/world/

Jouw voorbeeld met een piloot doet me dan weer denken aan een verhaaltje over berekeningen aan een helicopter door groepjes studenten. Tal van ingewikkelde methodes werden er gebruikt, maar een eenvoudig Kalman filtertje bleek toch het beste te scoren. Non-lineariteit hoeft ook geen probleem te zijn om systeemtheorie toe te passen.

Soultaker schreef op woensdag 14 november 2012 @ 18:44:
simulated annealing

Simulated annealing kan worden gezien als een specifiek evolutionary algorithm met populatie 1. Maar vaak wordt het ook apart gezien, gezien de oorsprong, en bijvoorbeeld als algemene genetic algorithms worden gecombineerd met simulated annealing. Ivm incremental updates zou dat in .oisyn's geval trouwens ook goed kunnen werken.

[.oisyn]

pedorus schreef op woensdag 14 november 2012 @ 23:05:
[...]

lolol, anders haal je gewoon de hele tenzij uit de zin, en laat je de smilie die ervoor staat in dezelfde alinea weg.

Ja, leuk bedacht, maar feitelijk zeg je dan: er is geen reden om X te gebruiken, tenzij er niets beters is dan X. Dat gaat natuurlijk altijd op he slimpie . De waarde van je opmerking is daarmee gereduceerd tot 0, maar dat is niet wat je ermee bedoelde te zeggen want anders zei je het niet.

[ Voor 14% gewijzigd door .oisyn op 14-11-2012 23:52 ]

[armageddon_2k1]

pedorus schreef op woensdag 14 november 2012 @ 23:05:
[...]

lolol, anders haal je gewoon de hele tenzij uit de zin, en laat je de smilie die ervoor staat in dezelfde alinea weg.

Je hebt gelijk Ik heb daar een beetje bruut geknipt.

Jouw voorbeeld met een piloot doet me dan weer denken aan een verhaaltje over berekeningen aan een helicopter door groepjes studenten. Tal van ingewikkelde methodes werden er gebruikt, maar een eenvoudig Kalman filtertje bleek toch het beste te scoren. Non-lineariteit hoeft ook geen probleem te zijn om systeemtheorie toe te passen.

Toevallig is het mijn afstudeerrichting geweest en heb veel met Kalman filters gewerkt. In dit specifieke geval ging een Kalman filter echter niet op vooral omdat een Kalman filter van lineaire systemen uitgaat in de basis en alle variabelen en ruis gaussiaans verdeeld moeten zijn. Lang verhaal Ik wil je het paper wel geven. Systeemtheorie toepassen op non-lineaire problemen is inderdaad geen probleem.

In het geval van die studenten (klinkt als mijn opleiding overigens) kan ik me voorstellen dat sommigen domweg niet bekend waren met Kalman filtering.

[ Voor 8% gewijzigd door armageddon_2k1 op 15-11-2012 10:03 ]

[alienfruit]

Kalman filters worden ook besproken bij de kunstopleiding die ik heb gevolgd. Kalman filtering is erg handig voor het verwerken van sensor input We gebruikten het vaak voor als we dingen wilde tracken middels cameras.

[djc]

Hmm, gaat dit nou over genetische algoritmen, evolutionary algorithms, of zijn die twee hetzelfde? Ik heb er andere ideeen bij; volgens mij gaat het bij GA's juist om het kruisen en muteren. Daar heb je niet echt mee te maken bij evolutionaire algoritmen (mijn kennis is vooral via Coursera's Machine Learning course), toch?

[.oisyn]

Een GA is een specifieke applicatie van een EA.

[pedorus]

.oisyn schreef op woensdag 14 november 2012 @ 23:51:
[...]

Ja, leuk bedacht, maar feitelijk zeg je dan: er is geen reden om X te gebruiken, tenzij er niets beters is dan X. Dat gaat natuurlijk altijd op he slimpie .

Ik denk dat je de grap goed uitlegt

De waarde van je opmerking is daarmee gereduceerd tot 0, maar dat is niet wat je ermee bedoelde te zeggen want anders zei je het niet.

Het eerste stukje van die post was natuurlijk vooral gericht op iets breder kijken. Met de oplossingsrichtingen die ik daar aandraag is meer ervaring, en die zijn eerder proven technology, ook op de langere termijn, dan iets met de GPU doen. Ik denk dat als je een automatische parameter-tuning pakket op je probleem had losgelaten bijvoorbeeld, dat je nu al verbeteringen had gehad. Zelfde met die andere richtingen. Nu heb je voor de GPU-oplossing gekozen, en heb je vooralsnog 'twee problemen'

Je ziet dat ik niet de enige ben met deze gedachten, even terugkomen om de GA--discussie in het andere draadje, en je hebt zo genoeg reacties juist daarover. Natuurlijk kan ik me voorstellen dat het hobbymatig interessant is om naar de GPU te gaan kijken. Ik ken ook iemand die het geweldig vond om XBox-en in te zetten voor high performance computing, als onderzoeker aan een universiteit. Ik geloof dat gezien de technologische vooruitgang het gebruik van XBox-en inmiddels al weer achterhaald is.

Een generalistisch EA-algoritme zou je elegant kunnen noemen omdat er geen probleem-specifieke kennis is toegevoegd. In EA-contests worden vaak alleen generalisten toegestaan. Echter, ook dit is vooral hobbymatig van zo ongeveer de gehele EA-community zou ik zeggen. In de praktijk blijkt namelijk dat een specialist het voor een specifiek probleem beter doet. Zo'n niet probleem-specifiek algoritme klinkt misschien elegant, maar het is gewoon zelden wat je wil in de praktijk.