Genetisch algoritme, zo geweldig kan het toch niet zijn?

[Icey]

Beste,

Op school zijn wij op dit moment veel bezig met Kunstmatige Intelligentie, een van de besproken zoektechnieken is het genetisch algoritme. Het is een zogenaamd evolutionair algoritmen waarbij je aan de hand van de evolutie theorie (de sterkste overwint) opzoek gaat naar een goede (niet de beste!) oplossing.

Ik kan vele goede voorbeelden opnoemen waarbij genetische algoritmen gebruikt kan worden, General Electric gebruikte het eind jaren 80 voor de ontwikkeling van een nieuwe turbinemotor voor de Boeing 777. Daarnaast word het ook veel gebruikt voor het samenstellen van roosters en het op elkaar aansluiten van processen.

Echter, het is geen optimaal algoritmen. Je krijgt dus ook niet gegarandeerd de beste oplossing terug. Ik kan mij dus ook niet voorstellen dat het zo'n geweldig algoritmen is... Ik ben dan dus ook opzoek naar voorbeelden waarbij het absoluut niet toepasbaar is of waarvan projecten mislukt zijn.

Kunnen we voorbeelden aanwijzen/opnoemen waarvoor het niet toepasbaar is? In welk geval is het absoluut noodzakelijk om de meest optimale oplossing terug te krijgen?

[eamelink]

Dat het geen optimale oplossing oplevert is over het algemeen niet zo heel erg; vaak is het probleemdomein zodanig groot dat er geen enkele methode bestaat om de optimale oplossing te vinden. Dan is een genetisch algoritme gewoon één van de mogelijkheden om een goede oplossing te vinden.

[edit]

Wat ik hier verder zei is niet perśe waar.

[ Voor 47% gewijzigd door eamelink op 24-06-2007 15:48 ]

[Verwijderd]

Bij genetische algoritmes zie ik vaak dezelfde gedachte gang als bij neurale netwerken, we snappen niet hoe het werkt maar je kan zonder nadenken elk probleem oplossen. Zo werkt ga (net als neurale netwerken niet). Veel voorkomende problemen/fouten zijn:

- er zitten veel lokale optima in de fitness functie, hoewel gegeven oneindig veel tijd een ga altijd (ook hier zitten mitsen en maren maar die laten we even buiten beschouwing) in het globale optimum komt is dit slechts een theoretisch resultaat, in de praktijk blijft ook GA vast zitten in lokale optima en zal hij een globaal optimum wat omringt is door een groot dal niet bereiken.

- de mutatie functie, vaak is helemaal niet duidlijk wat een goede mutatie operatie is, goed voorbeeld hiervan is het TSP, alhoewel dit probleem goed opgelost kan worden met GA is een goede mutatie operatie bedenken niet triviaal.

- Co-evolutie, als je bijvoorbeeld opzoek bent naar een goede schaakspeler en je evalueert je populatie door ze tegen elkaar te laten spelen, kun je erg onverwachte resulaten krijgen, meer hierover kun je vinden onder Evolutionary Gametheory.

- Er moet een graduele fitnes functie zijn, veel problemen hebben alleen goede en fout oplossingen en niet een beetje goed, dit sluit GA ip uit.

Mislukkingen vinden zal lastig zijn, mensen zullen hier niet snel over publiceren.

Het klassieke boek over GA is Holland (ik meen 1975 maar weet het niet zeker), hier worden alle heikele punten van GA in uit gelegd.

Verder is GA, en monte carlo methoden in het algemeen, een heel krachtig concept op met name NP-complete problemen aan te pakken.

@eamelink: als de probleem space discreet is en er is een fitness functie bestaat er altijd een methode om het globale optimum te vinden ,enumereren,

[ Voor 4% gewijzigd door Verwijderd op 24-06-2007 16:45 ]

[needless to say]

tjah, zoals hierboven reeds uitgedrukt ga je juist genetische algoritmen gebruiken in situaties waar gewone algoritmen gewoon niet in een aanvaardbare tijd een probleem kunnen oplossen. Denk aan NP-hard problemen zoals bvb TSP, project scheduling, etc...

Elk algoritme die een complexiteit heeft die hoger is dan polynomiaal is erg moeilijk om met de computer op te lossen. Bij zo een algoritmen maakt het zelf niet veel uit hoe krachtig je computer wel is om een grote probleemset op te lossen.

Vandaar dat je op zoek gaat naar suboptimale algoritmen die zeer snel convergeren naar een oplossing die niet te ver is van een optimale oplossing.

Zo heb ik eens een implementatie van TSP gedaan. Via een optimaal A*-algoritme (wat trouwens ook een heuristiek gebruikt) kon ik een probleem oplossen van een 20-tal steden voordat mijn pc het niet meer aan kon. Met genetische algoritmen kon ik in een aanvaardbare tijd veel grotere probleemsets beschouwen en meestal toch de ideale oplossing vinden, of tenminste een oplossing die in de buurt komt.

Veel hangt uiteraard af van je mutator/local search/crossover-functie en hoeveel keer je elke functie (+immigratie) gebruikt. Wanneer die goed gekozen zijn, dan merk je wel dat je vrij snel een betere oplossing vindt. Eens je dicht bij de oplossing zit duurt het wel iets langer voor je de beste oplossing vindt.

Genetische algoritmen klinken raar omdat je een oplossing gaat zoeken via probabiliteiten. Echter, je gaat toch gericht zoeken, aangezien je beter presterende oplossingen gaat selecteren om verder te gebruiken.


Mogelijke toepassingen:
routeplanner.
Wanneer je een route opvraagt van 1 plaats naar een ander kun je moeilijk verwachten dat je pc al de mogelijke routes gaat berekenen. Dit kan nooit in een eindige tijd op een huidige pc. Via genetische algoritmen ga je echter vrij snel een "aanvaardbare" oplossing verkrijgen. Hoe krachtiger je pc, hoe dichter dat deze oplossing zal aanleunen bij de optimale oplossing.

[ Voor 20% gewijzigd door needless to say op 24-06-2007 16:57 ]

[Verwijderd]

needless to say schreef op zondag 24 juni 2007 @ 16:52:


Zo heb ik eens een implementatie van TSP gedaan. Via een optimaal A*-algoritme (wat trouwens ook een heuristiek gebruikt) kon ik een probleem oplossen van een 20-tal steden voordat mijn pc het niet meer aan kon. Met genetische algoritmen kon ik in een aanvaardbare tijd veel grotere probleemsets beschouwen en meestal toch de ideale oplossing vinden, of tenminste een oplossing die in de buurt komt.

Mogelijke toepassingen:
routeplanner.
Wanneer je een route opvraagt van 1 plaats naar een ander kun je moeilijk verwachten dat je pc al de mogelijke routes gaat berekenen. Dit kan nooit in een eindige tijd op een huidige pc. Via genetische algoritmen ga je echter vrij snel een "aanvaardbare" oplossing verkrijgen. Hoe krachtiger je pc, hoe dichter dat deze oplossing zal aanleunen bij de optimale oplossing.

A-ster levert wel degelijk gegarandeerd de optimale oplossing, echter is het niet zonder meer toe te passen op een pad voor het TSP, of je moet een pad zoeken 1 of andere configuratie ruimte.

Voor een routeplanner kun je volgens mij toch aardig goed af met een a* implementatie/Dijkstra met misschien enkele beperkingen (in de trand van maar 1 keer de snelweg op en af oid.) ik kan mij niet voorstellen dat pc routeplanners met GA werken. Al zou het wel kunnen natuurlijk

[needless to say]

Verwijderd schreef op zondag 24 juni 2007 @ 17:54:
[...]


A-ster levert wel degelijk gegarandeerd de optimale oplossing, echter is het niet zonder meer toe te passen op een pad voor het TSP, of je moet een pad zoeken 1 of andere configuratie ruimte.

Ik heb nooit het tegenovergestelde beweerd. Een heuristiek geeft niet per definitie een suboptimale oplossing.

Wanneer je probleemset te groot is faalt A* omdat het te lang duurt eer je aan een oplossing geraakt (die optimaal is...).

Voor een routeplanner kun je volgens mij toch aardig goed af met een a* implementatie/Dijkstra met misschien enkele beperkingen (in de trand van maar 1 keer de snelweg op en af oid.) ik kan mij niet voorstellen dat pc routeplanners met GA werken. Al zou het wel kunnen natuurlijk

Het gaat me om "Al zou het wel kunnen natuurlijk". Uiteraard is het niet noodzakelijk zo, maar het zou mogelijk kunnen zijn.

Dat een routeplanner niet steeds de optimale oplossing vindt is makkelijk te toetsen. Gebruik gewoon 2 verschillende routeplanners (gps-toestellen) die dezelfde mappen gebruiken. Ze geven niet steeds dezelfde oplossing, juist omdat ze een suboptimale oplossing genereren en verschillende algoritmes gebruiken (intern ontwikkeld bij de devvers van het gps-toestel of de routeplanner)

[ Voor 9% gewijzigd door needless to say op 24-06-2007 19:15 ]

[titan_pi8]

needless to say schreef op zondag 24 juni 2007 @ 19:13:
[...]

Dat een routeplanner niet steeds de optimale oplossing vindt is makkelijk te toetsen. Gebruik gewoon 2 verschillende routeplanners (gps-toestellen) die dezelfde mappen gebruiken. Ze geven niet steeds dezelfde oplossing, juist omdat ze een suboptimale oplossing genereren en verschillende algoritmes gebruiken (intern ontwikkeld bij de devvers van het gps-toestel of de routeplanner)

Dat zou ook kunnen omdat ze verschillende gewichten toekennen aan de wegen. Zo geeft misschien het éne toestel een bepaalde weg een lager gewicht omdat die korter is, terwijl een ander toestel die weg een hoger gewicht geeft omdat je er niet snel mag rijden.

Het Dijkstra-algoritme heeft een worst-case complexiteit van n². Dat slechtste geval zal natuurlijk nooit bereikt worden bij een routeplanner, maar ik weet niet of het nog doenbaar is om Dijkstra (of variant) te gebruiken dan wel een sub-optimaal algoritme.