Genetische algoritmen(GA) en genetische programmering(GP) zijn interessante onderzoeksgebieden.
Ik zou graag willen weten over specifieke problemen die je hebt opgelost met GA/GP en welke bibliotheken/frameworks je hebt gebruikt als je die niet zelf hebt gebruikt.
Vragen:
- Voor welke problemen heeft u GA/GP gebruikt om op te lossen?
- Welke bibliotheken/frameworks heb je gebruikt?
Ik ben op zoek naar ervaringen uit de eerste hand, dus reageer alsjeblieft niet tenzij je die hebt.
Antwoord 1, autoriteit 100%
Geenhuiswerk.
Mijn eerste baan als professionele programmeur (1995) was het schrijven van een op genetisch algoritme gebaseerd geautomatiseerd handelssysteem voor S&P500-futures. De applicatie is geschreven in Visual Basic 3 [!] en ik heb geen idee hoe ik toen iets deed, aangezien VB3 niet eens lessen had.
De applicatie begon met een populatie van willekeurig gegenereerde strings met een vaste lengte (het ‘gen’-gedeelte), die elk overeenkwamen met een specifieke vorm in de prijsgegevens van minuut tot minuut van de S&P500-futures, zoals evenals een specifieke order (kopen of verkopen) en stop-loss en stop-profit bedragen. Van elke string (of “gen”) werd zijn winstprestatie geëvalueerd door een reeks historische gegevens van 3 jaar; telkens wanneer de opgegeven “vorm” overeenkwam met de historische gegevens, nam ik de bijbehorende koop- of verkooporder aan en evalueerde ik het resultaat van de transactie. Ik voegde de waarschuwing toe dat elk gen begon met een vast bedrag en dus mogelijk failliet zou kunnen gaan en volledig uit de genenpool zou kunnen worden verwijderd.
Na elke evaluatie van een populatie werden de overlevenden willekeurig gekruist (door gewoon stukjes van twee ouders te mengen), waarbij de kans dat een gen als ouder werd geselecteerd evenredig was met de winst die het opleverde. Ik heb ook de mogelijkheid van puntmutaties toegevoegd om de zaken een beetje op te fleuren. Na een paar honderd generaties hiervan, eindigde ik met een populatie van genen die $ 5000 zou kunnen veranderen in een gemiddelde van ongeveer $ 10.000 zonder kans op overlijden/breuk (uiteraard op basis van de historische gegevens).
Helaas heb ik nooit de kans gekregen om dit systeem live te gebruiken, aangezien mijn baas bijna $ 100.000 verloor in minder dan 3 maanden door op de traditionele manier te handelen, en hij verloor zijn bereidheid om door te gaan met het project. Achteraf denk ik dat het systeem enorme winsten zou hebben gemaakt – niet omdat ik per se iets goed deed, maar omdat de populatie van genen die ik produceerde toevallig een voorkeur had voor kooporders (in tegenstelling tot verkooporders) met ongeveer een 5: 1 verhouding. En zoals we weten met onze 20/20 achteraf gezien, ging de markt na 1995 een beetje omhoog.
Antwoord 2, autoriteit 60%
Ik heb kleine beestjes gemaakt die in deze kleine wereld leefden. Ze hadden een neuraal netwerkbrein dat input van de wereld ontving en de output was een vector voor beweging onder andere acties. Hun hersenen waren de “genen”.
Het programma begon met een willekeurige populatie beestjes met willekeurige hersenen. De input- en outputneuronen waren statisch, maar wat er tussenin was, was dat niet.
De omgeving bevatte voedsel en gevaren. Voedsel verhoogde energie en als je genoeg energie hebt, kun je paren. De gevaren zouden de energie verminderen en als de energie 0 was, stierven ze.
Uiteindelijk zijn de wezens geëvolueerd om de wereld rond te reizen en voedsel te vinden en de gevaren te vermijden.
Ik besloot toen een klein experiment te doen. Ik gaf de hersenen van het wezen een uitgangsneuron genaamd “mond” en een invoerneuron genaamd “oor”. Begon opnieuw en was verrast om te ontdekken dat ze evolueerden om de ruimte te maximaliseren en dat elk respectief wezen in zijn respectieve deel zou blijven (voedsel werd willekeurig geplaatst). Ze leerden om met elkaar samen te werken en elkaar niet in de weg te lopen. Er waren altijd uitzonderingen.
Toen probeerde ik iets interessants. Ik dode wezens zouden voedsel worden. Probeer te raden wat er is gebeurd! Er zijn twee soorten wezens ontstaan, degenen die aanvielen zoals in zwermen, en degenen die veel vermeden werden.
Dus wat is de les hier? Communicatie betekent samenwerken. Zodra je een element introduceert waarbij het kwetsen van een ander betekent dat je iets wint, wordt de samenwerking vernietigd.
Ik vraag me af hoe dit reflecteert op het systeem van vrije markten en kapitalisme. Ik bedoel, als bedrijven hun concurrentie kunnen schaden en er mee wegkomen, dan is het duidelijk dat ze er alles aan zullen doen om de concurrentie te schaden.
Bewerken:
Ik schreef het in C++ zonder frameworks. Schreef mijn eigen neurale netwerk en GA-code. Eric, bedankt dat je zegt dat het aannemelijk is. Mensen geloven meestal niet in de kracht van GA (hoewel de beperkingen duidelijk zijn) totdat ze ermee speelden. GA is eenvoudig maar niet simplistisch.
Voor de twijfelaars: het is bewezen dat neurale netten elke functie kunnen simuleren als ze meer dan één laag hebben. GA is een vrij eenvoudige manier om door een oplossingsruimte te navigeren en een lokaal en mogelijk globaal minimum te vinden. Combineer GA met neurale netwerken en je hebt een redelijk goede manier om functies te vinden die bij benadering oplossingen vinden voor generieke problemen. Omdat we neurale netwerken gebruiken, optimaliseren we de functie voor sommige inputs, niet sommige inputs voor een functie, terwijl andere GA gebruiken
Hier is de democode voor het overlevingsvoorbeeld: http://www.mempko .com/darcs/neural/demos/eaters/
Bouwinstructies:
- Installeer dARCs, libboost, liballegro, gcc, cmake, make
darcs clone --lazy http://www.mempko.com/darcs/neural/cd neuralcmake .makecd demos/eaters./eaters
Antwoord 3, autoriteit 36%
In januari 2004 werd ik benaderd door Philips New Display Technologies, die de elektronica creëerde voor de allereerste commerciële e-inkt, de Sony Librie, die alleen in Japan was uitgebracht, jaren voordat Amazon Kindle en de anderen op de markt kwamen. markt in de VS en Europa.
De technici van Philips hadden een groot probleem. Een paar maanden voordat het product op de markt zou komen, kregen ze nog steeds ghosting op het scherm bij het wisselen van pagina. Het probleem waren de 200 drivers die het elektrostatische veld creëerden. Elk van deze drivers had een bepaalde spanning die moest worden ingesteld tussen nul en 1000 mV of iets dergelijks. Maar als je er één zou veranderen, zou alles veranderen.
Dus het was uit den boze om de spanning van elke driver afzonderlijk te optimaliseren. Het aantal mogelijke combinaties van waarden was in miljarden, en het duurde ongeveer 1 minuut voordat een speciale camera een enkele combinatie evalueerde. De ingenieurs hadden veel standaard optimalisatietechnieken geprobeerd, maar niets kwam in de buurt.
De hoofdingenieur nam contact met me op omdat ik eerder een bibliotheek voor genetische programmering had vrijgegeven aan de open-sourcegemeenschap. Hij vroeg of huisartsen zouden helpen en of ik mee kon doen. Dat deed ik, en ongeveer een maand werkten we samen, ik schreef en stemde de GA-bibliotheek af op synthetische gegevens, en hij integreerde het in hun systeem. Toen lieten ze het in een weekend live gaan met het echte werk.
De maandag daarop kreeg ik deze gloeiende e-mails van hem en hun hardware-ontwerper, over hoe niemand de verbazingwekkende resultaten kon geloven die de GA vond. Dit was het. Later dat jaar kwam het product op de markt.
Ik kreeg er geen cent voor betaald, maar ik kreeg ‘opscheppen’. Ze zeiden vanaf het begin dat ze al boven het budget zaten, dus ik wist wat de deal was voordat ik eraan begon te werken. En het is een geweldig verhaal voor toepassingen van GA’s. 🙂
Antwoord 4, autoriteit 35%
Ik heb een GA gebruikt om de zitplaatstoewijzingen op mijn huwelijksreceptie te optimaliseren. 80 gasten verdeeld over 10 tafels. De evaluatiefunctie was gebaseerd op het houden van mensen bij hun dates, het samenbrengen van mensen met iets gemeenschappelijks en het aan aparte tafels houden van mensen met extreem tegengestelde opvattingen.
Ik heb het meerdere keren uitgevoerd. Elke keer kreeg ik negen goede tafels en één met allemaal rare ballen. Uiteindelijk deed mijn vrouw de zitplaatsopdrachten.
Mijn reizende verkoper-optimizer gebruikte een nieuwe mapping van chromosoom naar route, waardoor het triviaal was om de chromosomen te fokken en te muteren zonder enig risico op het genereren van ongeldige tours.
Update: omdat een paar mensen hebben gevraagd hoe …
Begin met een reeks gasten (of steden) in een willekeurige maar consistente volgorde, bijvoorbeeld alfabetisch. Noem dit de referentieoplossing. Beschouw de index van een gast als zijn/haar stoelnummer.
In plaats van te proberen deze volgorde rechtstreeks in het chromosoom te coderen, coderen we instructies om de referentieoplossing om te zetten in een nieuwe oplossing. In het bijzonder behandelen we de chromosomen als lijsten met indexen in de array om te wisselen. Om een chromosoom te decoderen, beginnen we met de referentieoplossing en passen we alle swaps toe die door het chromosoom worden aangegeven. Het verwisselen van twee items in de array resulteert altijd in een geldige oplossing: elke gast (of stad) komt nog steeds precies één keer voor.
Dus chromosomen kunnen willekeurig worden gegenereerd, gemuteerd en gekruist met anderen en zullen altijd een geldige oplossing opleveren.
Antwoord 5, autoriteit 23%
Ik heb genetische algoritmen (evenals enkele verwante technieken) gebruikt om de beste instellingen te bepalen voor een risicobeheersysteem dat probeerde te voorkomen dat goudboeren gestolen creditcards gebruikten om voor MMO’s te betalen. Het systeem zou enkele duizenden transacties met “bekende” waarden (fraude of niet) opnemen en uitzoeken wat de beste combinatie van instellingen was om de frauduleuze transacties correct te identificeren zonder al te veel valse positieven.
We hadden gegevens over enkele tientallen (booleaanse) kenmerken van een transactie, die elk een waarde kregen en bij elkaar optelden. Als het totaal hoger was dan een drempel, was er sprake van fraude. De GA zou een groot aantal willekeurige reeksen waarden creëren, deze evalueren aan de hand van een corpus van bekende gegevens, degene selecteren die het beste scoorden (zowel op fraudedetectie als het beperken van het aantal valse positieven), en vervolgens de beste paar uit elkaar kruisen. elke generatie om een nieuwe generatie kandidaten voort te brengen. Na een bepaald aantal generaties werd de best scorende reeks waarden als winnaar beschouwd.
Het creëren van het corpus van bekende gegevens om tegen te testen was de achilleshiel van het systeem. Als je wachtte op terugvorderingen, liep je een aantal maanden achter toen je probeerde te reageren op de fraudeurs, dus iemand zou handmatig grote aantallen transacties moeten controleren om dat corpus aan gegevens op te bouwen zonder te lang te hoeven wachten.
Hiermee werd uiteindelijk de overgrote meerderheid van de fraude die binnenkwam geïdentificeerd, maar kon het niet helemaal onder de 1% komen voor de meest fraudegevoelige items (aangezien 90% van de inkomende transacties fraude zou kunnen zijn, was dat een goede prestatie goed).
Ik deed dit allemaal met perl. Eén run van de software op een redelijk oude Linux-box zou 1-2 uur duren (20 minuten om gegevens via een WAN-link te laden, de rest van de tijd besteed aan kraken). De grootte van een bepaalde generatie werd beperkt door het beschikbare RAM-geheugen. Ik zou het keer op keer uitvoeren met kleine wijzigingen in de parameters, op zoek naar een bijzonder goede resultatenset.
Al met al vermeed het enkele van de blunders die gepaard gingen met het handmatig aanpassen van de relatieve waarden van tientallen fraude-indicatoren, en kwam het consequent met betere oplossingen dan ik met de hand kon creëren. AFAIK, het is nog steeds in gebruik (ongeveer 3 jaar nadat ik het heb geschreven).
Antwoord 6, autoriteit 15%
Fooien bij voetbal. Ik heb een GA-systeem gebouwd om de week-tot-week-uitkomst van wedstrijden in de AFL (Aussie Rules Football) te voorspellen.
Een paar jaar geleden kreeg ik genoeg van de standaard voetbalpool, iedereen ging gewoon online en nam de keuze van een expert in de pers. Dus ik dacht dat het niet zo moeilijk kon zijn om een aantal grote journalisten te verslaan, toch? Mijn eerste gedachte was om de resultaten van Massey Ratingste nemen en aan het einde van het seizoen mijn strategie na het winnen te onthullen roem en glorie. Om redenen die ik echter nooit heb ontdekt, volgt Massey AFL niet. De cynicus in mij gelooft dat dit komt omdat de uitkomst van elk AFL-spel in feite willekeurig toeval is geworden, maar mijn klachten over recente regelwijzigingen horen thuis op een ander forum.
Het systeem hield in feite rekening met offensieve kracht, defensieve kracht, thuisvoordeel, verbetering van week tot week (of het ontbreken daarvan) en snelheid van veranderingen in elk van deze. Dit creëerde een reeks polynoomvergelijkingen voor elk team gedurende het seizoen. De winnaar en de score voor elke wedstrijd voor een bepaalde datum kunnen worden berekend. Het doel was om de set coëfficiënten te vinden die het beste overeenkwam met de uitkomst van alle eerdere games en die set te gebruiken om de game van de komende weken te voorspellen.
In de praktijk zou het systeem oplossingen vinden die meer dan 90% van de eerdere spelresultaten nauwkeurig voorspelden. Het zou dan met succes ongeveer 60-80% van de games voor de komende week kiezen (dat is de week die niet in de trainingsset zit).
Het resultaat: net boven het midden van het peloton. Geen grote geldprijs of een systeem dat ik zou kunnen gebruiken om Vegas te verslaan. Het was wel leuk.
Ik heb alles helemaal opnieuw opgebouwd, geen framework gebruikt.
Antwoord 7, autoriteit 15%
Naast enkele veelvoorkomende problemen, zoals de reizende verkoper en een variatie op Het Mona Lisa-programma van Roger Alsing, ik heb ook geschreven een evolutionaire Sudoku-oplosser(waarvoor een wat originelere gedachte van mijn kant nodig was, in plaats van alleen het idee van iemand anders opnieuw te implementeren). Er zijn betrouwbaardere algoritmen voor het oplossen van Sudoku’s, maar de evolutionaire benadering werkt redelijk goed.
De afgelopen dagen heb ik met een evolutionair programma gespeeld om “cold decks” voor poker te vinden na het zien van dit artikelop Reddit. Het is momenteel niet helemaal bevredigend, maar ik denk dat ik het kan verbeteren.
Ik heb mijn eigen raamwerkdat ik gebruik voor evolutionaire algoritmen.
Antwoord 8, autoriteit 12%
Ik heb een zelfgemaakte GA ontwikkeld voor een 3D-laseroppervlakprofielsysteem dat mijn bedrijf in 1992 voor de vrachtindustrie heeft ontwikkeld.
Het systeem vertrouwde op driedimensionale triangulatie en gebruikte een aangepaste laserlijnscanner, een 512×512-camera (met aangepaste opname hw). De afstand tussen de camera en de laser zou nooit precies zijn en het brandpunt van de camera’s was niet te vinden in de 256.256 positie die je had verwacht!
Het was een nachtmerrie om te proberen de kalibratieparameters uit te werken met behulp van standaardgeometrie en het oplossen van gesimuleerde gloeistijlvergelijkingen.
Het genetische algoritme werd in een avond ontwikkeld en ik heb een kalibratiekubus gemaakt om het op te testen. Ik kende de afmetingen van de kubus met hoge nauwkeurigheid en daarom was het idee dat mijn GA een reeks aangepaste triangulatieparameters voor elke scaneenheid kon ontwikkelen die productievariaties zouden overwinnen.
De truc werkte goed. Ik was op zijn zachtst gezegd verbijsterd! Binnen ongeveer 10 generaties zag mijn ‘virtuele’ kubus (gegenereerd op basis van de onbewerkte scan en opnieuw gemaakt op basis van de kalibratieparameters) er eigenlijk uit als een kubus! Na ongeveer 50 generaties had ik de kalibratie die ik nodig had.
9, Autoriteit 5%
Een paar weken geleden, suggereerde ik een oplossing op, dus met genetische algoritmen om een probleem van grafieklay-out op te lossen. Het is een voorbeeld van een beperkt optimalisatieprobleem.
Ook op het gebied van machinaal leren, implementeer ik een GA-gebaseerd classificatieregels Framework in C / C++ helemaal opnieuw.
Ik heb ook GA in een voorbeeldproject gebruikt voor training kunstmatige neurale netwerken (ann) in tegenstelling tot aan het gebruik van de beroemde backpropagation algoritme .
Bovendien, en als onderdeel van mijn afgestudeerde onderzoek, heb ik GA gebruikt in training Hidden Markov Models als een extra aanpak van de EM-gebaseerde Baum-Welch Algoritme (in C / C++ opnieuw).
10, Autoriteit 5%
Als onderdeel van mijn undergraduate COMPSCI-diploma kregen we het probleem toegewezen van het vinden van optimale JVM-vlaggen voor de virtuele Jikes-onderzoek. Dit werd geëvalueerd met behulp van de Dicappo Benchmark Suite die een tijd naar de console retourneert. Ik schreef een gedistribueerde gentic alogirthm die deze vlaggen heeft geschakeld om de runtime van de benchmarksuite te verbeteren, hoewel het dagen duurde om te rennen om te compenseren voor hardware jitter die de resultaten beïnvloedt. Het enige probleem was dat ik niet goed meer heb over de compilertheorie (die de bedoeling van de opdracht was).
Ik had de initiële bevolking kunnen bezaaiden met de exising standaardvlaggen, maar wat interessant was, was dat het algoritme een zeer vergelijkbare configuratie heeft gevonden aan het O3-optimalisatieniveau (maar was eigenlijk sneller in vele tests).
EDIT: Ook schreef ik mijn eigen genetische algoritm-framework in Python voor de opdracht en gebruikte de opdrachten van POP-opdrachten om de verschillende benchmarks uit te voeren, hoewel als het geen beoordeelde opdracht was die ik naar Pyevolve zou hebben gekeken.
11, Autoriteit 5%
eerst uit, “genetische programmering” door Jonathan Koza (op Amazon ) is vrijwel het boek over genetische en evolutionaire algoritme / programmeertechnieken, met veel voorbeelden. Ik stel uit dat ik het kan controleren.
Net als voor mijn eigen gebruik van een genetisch algoritme, gebruikte ik een (home geteeld) genetisch algoritme om een zwermalgoritme te evolueren voor een objectverzameling / vernietigingsscenario (praktisch doel had een mijnenveld kunnen opruimen). Hier is een link naar het papier . Het meest interessante onderdeel van wat ik deed was de multi-geënsceneerde fitnessfunctie, die een noodzaak was, omdat de eenvoudige fitnessfuncties niet genoeg informatie verstrekt voor het genetische algoritme om voldoende onderscheid te maken tussen leden van de bevolking.
12, Autoriteit 5%
Ik maak deel uit van een team dat onderzoek doet naar het gebruik van Evolutionary Computation (EC) om automatisch bugs in bestaande programma’s op te lossen. We hebben met succes een aantal echte bugs in echte softwareprojecten gerepareerd (zie de startpagina van dit project).
We hebben twee toepassingen van deze EC-reparatietechniek.
-
De eerste (code en reproductie-informatie beschikbaar via de projectpagina) ontwikkelt de abstracte syntaxisbomen die zijn ontleed uit bestaande C-programma’s en wordt geïmplementeerd in Ocaml met behulp van onze eigen aangepaste EC-engine.
-
De tweede (code en reproductie-informatie beschikbaar via de projectpagina), mijn persoonlijke bijdrage aan het project, ontwikkelt de x86-assemblage of Java-bytecode die is samengesteld uit programma’s die zijn geschreven in een aantal programmeertalen. Deze applicatie is geïmplementeerd in Clojure en gebruikt ook zijn eigen op maat gemaakte EC-engine.
Een mooi aspect van Evolutionary Computation is dat de eenvoud van de techniek het mogelijk maakt om je eigen aangepaste implementaties te schrijven zonder al te veel moeite. Zie de Field Guide to Genetic Programmingvoor een goede gratis beschikbare inleidende tekst over genetische programmering.
Antwoord 13, autoriteit 4%
Een collega en ik werken aan een oplossing om vracht op vrachtwagens te laden aan de hand van de verschillende criteria die ons bedrijf vereist. Ik heb aan een genetische algoritme-oplossing gewerkt terwijl hij een Branch And Bound gebruikt met agressief snoeien. We zijn nog bezig met het implementeren van deze oplossing, maar tot nu toe hebben we goede resultaten geboekt.
Antwoord 14, autoriteit 3%
Enkele jaren geleden heb ik ga’s gebruikt om de grammatica’s van asr (automatische spraakherkenning) te optimaliseren voor betere herkenningspercentages. Ik begon met vrij eenvoudige keuzelijsten (waarbij de ga combinaties van mogelijke termen voor elke slot testte) en werkte me op tot meer open en complexe grammatica’s. Fitness werd bepaald door de scheiding tussen termen/reeksen te meten onder een soort fonetische afstandsfunctie. Ik heb ook geëxperimenteerd met het maken van zwak equivalente variaties op een grammatica om er een te vinden die compileerde tot een compactere weergave (uiteindelijk koos ik voor een direct algoritme, en het vergrootte de “taal” die we in applicaties konden gebruiken drastisch) .
Meer recentelijk heb ik ze gebruikt als standaardhypothese om de kwaliteit van oplossingen die met verschillende algoritmen zijn gegenereerd, te testen. Dit ging grotendeels gepaard met categorisering en verschillende soorten aanpassingsproblemen (d.w.z. het creëren van een “regel” die een reeks keuzes verklaart die door reviewers zijn gemaakt over een dataset(s)).
Antwoord 15, autoriteit 3%
Ik heb een compleet GA-framework gemaakt met de naam “GALAB”, om veel problemen op te lossen:
- GSM ANT’s (BTS) lokaliseren om overlap te verminderen & lege locaties.
- Projectplanning met resourcebeperking.
- Evolutionaire beeldvorming. (Evopic)
- Probleem met reizende verkopers.
- N-Koningin & N-kleur problemen.
- Riddertocht & Knapzak problemen.
- Magisch vierkant & Sudoku-puzzels.
- stringcompressie, gebaseerd op Superstring-probleem.
- 2D-verpakkingsprobleem.
- Kleine kunstmatige leven-APP.
- Rubik-puzzel.
Antwoord 16, autoriteit 3%
Ik heb ooit een GA gebruikt om een hashfunctie voor geheugenadressen te optimaliseren. De adressen waren paginagroottes van 4K of 8K, dus ze vertoonden enige voorspelbaarheid in het bitpatroon van het adres (minst significante bits allemaal nul; middelste bits werden regelmatig verhoogd, enz.) De oorspronkelijke hashfunctie was “chunky” – het had de neiging om hits te clusteren op elke derde hash-emmer. Het verbeterde algoritme had een bijna perfecte verdeling.
Antwoord 17, autoriteit 3%
Ik heb een eenvoudige GA gebouwd om bruikbare patronen te extraheren uit het frequentiespectrum van muziek terwijl deze werd afgespeeld. De uitvoer werd gebruikt om grafische effecten aan te sturen in een winamp-plug-in.
- Invoer: een paar FFT-frames (stel je een 2D-array van floats voor)
- Output: enkele float-waarde (gewogen som van inputs), gedrempeld tot 0,0 of 1,0
- Genen: invoergewichten
- Fitness-functie: combinatie van duty-cycle, pulsbreedte en BPM binnen een redelijk bereik.
Ik had een paar GA’s afgestemd op verschillende delen van het spectrum en op verschillende BPM-limieten, zodat ze niet de neiging hadden om naar hetzelfde patroon te convergeren. De uitvoer van de top 4 van elke populatie werd naar de rendering-engine gestuurd.
Een interessant neveneffect was dat de gemiddelde fitheid van de bevolking een goede indicator was voor veranderingen in de muziek, hoewel het over het algemeen 4-5 seconden duurde om erachter te komen.
Antwoord 18, autoriteit 2%
Ik weet niet of huiswerk telt…
Tijdens mijn studie hebben we ons eigen programma ontwikkeld om het Travelling Salesman-probleem op te lossen.
Het idee was om een vergelijking te maken op verschillende criteria (moeilijkheid om het probleem in kaart te brengen, prestaties, enz.) en we gebruikten ook andere technieken zoals Gesimuleerd gloeien.
Het werkte redelijk goed, maar het kostte ons een tijdje om te begrijpen hoe we de ‘reproductie’-fase correct moesten uitvoeren: het modelleren van het probleem in iets dat geschikt is voor genetische programmering vond ik echt het moeilijkste deel…
Het was een interessante cursus omdat we ook met neurale netwerken en dergelijke bezig waren.
Ik zou graag willen weten of iemand dit soort programmering heeft gebruikt in ‘productie’-code.
Antwoord 19, autoriteit 2%
Ik heb een eenvoudig genetisch algoritme gebruikt om de signaal-ruisverhouding te optimaliseren van een golf die werd weergegeven als een binaire reeks. Door de bits over meerdere miljoenen generaties op een bepaalde manier om te draaien, kon ik een transformatie produceren die resulteerde in een hogere signaal-ruisverhouding van die golf. Het algoritme had ook “Simulated Annealing” kunnen zijn, maar werd in dit geval niet gebruikt. In de kern zijn genetische algoritmen eenvoudig, en dit was ongeveer net zo eenvoudig als een use-case die ik heb gezien, dus ik gebruikte geen raamwerk voor het maken en selecteren van generaties – alleen een willekeurig zaadje en de signaal-ruisverhouding functie bij de hand.
Antwoord 20, autoriteit 2%
Als onderdeel van mijn scriptie heb ik een generiek Java-raamwerk geschreven voor het multi-objective optimalisatie-algoritme mPOEMS (Multiobjective prototype optimization met geëvolueerde verbeteringsstappen), een GA die gebruikmaakt van evolutionaire concepten. Het is generiek op een manier dat alle probleem-onafhankelijke delen zijn gescheiden van de probleem-afhankelijke delen, en er is een interface voorzien om het raamwerk te gebruiken met alleen het toevoegen van de probleem-afhankelijke delen. Dus wie het algoritme wil gebruiken, hoeft niet bij nul te beginnen en het vergemakkelijkt het werk veel.
Je kunt de code hiervinden.
De oplossingen die u met dit algoritme kunt vinden, zijn in een wetenschappelijk werk vergeleken met de modernste algoritmen SPEA-2 en NSGA, en het is bewezen dat
het algoritme presteert vergelijkbaar of zelfs beter, afhankelijk van de metrics die je gebruikt om de prestaties te meten, en vooral afhankelijk van het optimalisatieprobleem waar je naar op zoek bent.
Je kunt het vinden hier.
Ook als onderdeel van mijn scriptie en bewijs van werk heb ik dit raamwerk toegepast op het projectselectieprobleem dat wordt aangetroffen in portfoliobeheer. Het gaat erom de projecten te selecteren die de meeste waarde toevoegen aan het bedrijf, de strategie van het bedrijf het meest ondersteunen of een ander willekeurig doel ondersteunen. bijv. selectie van een bepaald aantal projecten uit een specifieke categorie, of maximalisatie van projectsynergieën, …
Mijn scriptie die dit raamwerk toepast op het projectselectieprobleem:
http://www.ub.tuwien.ac.at/dipl/2008 /AC05038968.pdf
Daarna werkte ik op een afdeling voor portfoliobeheer in een van de Fortune 500, waar ze commerciële software gebruikten die ook een GA toepaste op het projectselectieprobleem / portfolio-optimalisatie.
Verdere bronnen:
De documentatie van het framework:
http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf
mPOEMS presentatie papier:
http://portal.acm.org/citation.cfm?id=1792634.1792653
Eigenlijk zou iedereen met een beetje enthousiasme de code van het generieke raamwerk gemakkelijk kunnen aanpassen aan een willekeurig multi-objectief optimalisatieprobleem.
Antwoord 21
Op het werk had ik het volgende probleem: gegeven M-taken en N DSP’s, wat was de beste manier om taken aan DSP’s toe te wijzen? “Best” werd gedefinieerd als “het minimaliseren van de belasting van de meest belaste DSP”. Er waren verschillende soorten taken, en verschillende taaktypes hadden verschillende gevolgen voor de prestaties, afhankelijk van waar ze waren toegewezen, dus ik codeerde de reeks taak-naar-DSP-toewijzingen als een “DNA-reeks” en gebruikte vervolgens een genetisch algoritme om te “fokken” de beste opdrachtreeks die ik kon.
Het werkte redelijk goed (veel beter dan mijn vorige methode, die was om elke mogelijke combinatie te evalueren… op niet-triviale probleemgroottes zou het jaren hebben gekost om te voltooien!), het enige probleem was dat er geen manier om te zien of de optimale oplossing was bereikt of niet. Je kon alleen beslissen of de huidige “beste poging” goed genoeg was, of het langer laten duren om te zien of het beter zou kunnen.
Antwoord 22
Er was een wedstrijd op codechef.com (geweldige site trouwens, maandelijkse programmeerwedstrijden) waarbij men een onoplosbare sudoku moest oplossen collumns/rows/etc mogelijk).
Wat ik zou doen, was om eerst een perfecte sudoku te genereren en dan de gegeven velden te negeren. Vanaf deze redelijk goede basis heb ik genetische programmering gebruikt om mijn oplossing te verbeteren.
Ik kon in dit geval geen deterministische benadering bedenken, omdat de sudoku 300×300 was en het zoeken te lang zou duren.
Antwoord 23
Tijdens een seminar in de school ontwikkelen we een applicatie om muziek te genereren op basis van de muzikale modus. Het programma is gebouwd in Java en de output was een midi-bestand met het nummer. We gebruiken verschillende benaderingen van GA om de muziek te genereren. Ik denk dat dit programma nuttig kan zijn om nieuwe composities te ontdekken.
Antwoord 24
in de middelbare school gebruikten we NERO (een combinatie van neuraal netwerk en genetisch algoritme) om in-game robots te leren intelligente beslissingen te nemen. Het was best gaaf.
Antwoord 25
Ik ontwikkelde een multithreaded swing-gebaseerde simulatie van robotnavigatie door een reeks gerandomiseerde rastergebieden van voedselbronnen en mijnen en ontwikkelde een op genetische algoritmen gebaseerde strategie om de optimalisatie van robotgedrag en overleving van de sterkste genen voor een robotchromosoom te onderzoeken. Dit werd gedaan met behulp van het in kaart brengen en in kaart brengen van elke iteratiecyclus.
Sindsdien heb ik nog meer spelgedrag ontwikkeld. Een voorbeeldtoepassing die ik onlangs voor mezelf heb gebouwd, was een genetisch algoritme voor het oplossen van het handelsreizigerprobleem bij het vinden van routes in het VK, rekening houdend met start- en doelstaten, evenals een / meerdere verbindingspunten, vertragingen, annuleringen, bouwwerkzaamheden, spitsuur, openbare stakingen, afweging tussen snelste vs goedkoopste routes. Geef vervolgens een uitgebalanceerde aanbeveling voor de route die op een bepaalde dag moet worden afgelegd.
Over het algemeen is mijn strategie om op POJO gebaseerde representatie van genen te gebruiken en vervolgens pas ik specifieke interface-implementaties toe voor selectie, mutatie, crossover-strategieën en het criteriapunt. Mijn fitnessfunctie wordt dan in feite vrij complex op basis van de strategie en criteria die ik als heuristische maatstaf moet toepassen.
Ik heb ook gekeken naar het toepassen van genetisch algoritme op geautomatiseerd testen binnen code met behulp van systematische mutatiecycli waarbij het algoritme de logica begrijpt en probeert een bugrapport vast te stellen met aanbevelingen voor codecorrecties. Kortom, een manier om mijn code te optimaliseren en aanbevelingen voor verbetering te doen, evenals een manier om de ontdekking van nieuwe programmatische code te automatiseren. Ik heb ook geprobeerd om onder andere genetische algoritmen toe te passen op muziekproductie.
Over het algemeen vind ik evolutionaire strategieën zoals de meeste metaheuristische/globale optimalisatiestrategieën, ze zijn in het begin traag om te leren, maar beginnen op te pikken naarmate de oplossingen steeds dichter bij de doelstaat komen en zolang je fitnessfunctie en heuristiek goed zijn uitgelijnd om die convergentie binnen uw zoekruimte te produceren.
Antwoord 26
Ik heb ooit geprobeerd een computerspeler te maken voor het spel Go, uitsluitend gebaseerd op genetische programmering. Elk programma zou worden behandeld als een evaluatiefunctie voor een reeks zetten. De geproduceerde programma’s waren echter niet erg goed, zelfs niet op een nogal klein 3×4 bord.
Ik heb Perl gebruikt en alles zelf gecodeerd. Ik zou de dingen vandaag anders doen.
Antwoord 27
Na het lezen van The Blind Watchmaker, was ik geïnteresseerd in het pascal-programma dat Dawkins zei dat hij had ontwikkeld om modellen te maken van organismen die in de loop van de tijd kunnen evolueren. Ik was geïnteresseerd genoeg om mijn eigen te schrijven met behulp van Swarm. Ik heb niet alle mooie afbeeldingen van beestjes gemaakt die hij maakte, maar mijn ‘chromosomen’ controleerden eigenschappen die het vermogen van organismen om te overleven beïnvloedden. Ze leefden in een eenvoudige wereld en konden het tegen elkaar en hun omgeving uitvechten.
Organismen leefden of stierven gedeeltelijk door toeval, maar ook op basis van hoe effectief ze zich aanpasten aan hun lokale omgeving, hoe goed ze voedingsstoffen consumeerden & hoe succesvol ze zich voortplantten. Het was leuk, maar ook meer bewijs voor mijn vrouw dat ik een nerd ben.
Antwoord 28
Het was een tijdje geleden, maar ik heb een GA uitgerold om te evolueren wat in feite beeldverwerkingskernels waren om kosmische stralingssporen van Hubble Space Telescope (HST)-beelden te verwijderen. De standaardbenadering is om meerdere opnamen te maken met de Hubble en alleen de dingen te bewaren die hetzelfde zijn in alle afbeeldingen. Omdat HST-tijd zo waardevol is, ben ik een astronomiefanaat en had ik onlangs het congres over evolutionaire berekeningen bijgewoond, dacht ik erover om een GA te gebruiken om enkele belichtingen op te schonen.
De individuen hadden de vorm van bomen die een gebied van 3×3 pixel als invoer namen, enkele berekeningen uitvoerden en een beslissing namen over of en hoe de middelste pixel moest worden gewijzigd. Fitness werd beoordeeld door de output te vergelijken met een afbeelding die op de traditionele manier is opgeschoond (d.w.z. door belichtingen te stapelen).
Het werkte eigenlijk wel, maar niet goed genoeg om af te zien van de oorspronkelijke aanpak. Als ik niet door mijn thesis beperkt was geweest in de tijd, had ik misschien de beschikbare genetische onderdelenbak voor het algoritme uitgebreid. Ik ben er vrij zeker van dat ik het aanzienlijk had kunnen verbeteren.
Gebruikte bibliotheken: als ik het me goed herinner, IRAF en cfitsio voor de verwerking van astronomische beeldgegevens en I/O.
Antwoord 29
Ik heb in mijn jeugd met GA geëxperimenteerd. Ik schreef een simulator in Python die als volgt werkte.
De genen codeerden voor het gewicht van een neuraal netwerk.
De ingangen van het neurale netwerk waren ‘antennes’ die aanrakingen detecteerden. Hogere waarden betekenden heel dichtbij en 0 betekende niet aanraken.
De uitgangen waren naar twee “wielen”. Als beide wielen vooruit gingen, ging de man vooruit. Als de wielen in tegengestelde richting stonden, draaide de man zich om. De kracht van de output bepaalde de snelheid van het draaien van het wiel.
Er is een eenvoudig doolhof gemaakt. Het was heel eenvoudig, zelfs dom. Er was de start onderaan het scherm en een doelpunt bovenaan, met vier muren ertussen. Elke muur had willekeurig een spatie, dus er was altijd een pad.
Ik begon in het begin met willekeurige jongens (ik beschouwde ze als bugs). Zodra een man het doel bereikte, of een tijdslimiet was bereikt, werd de fitheid berekend. Het was omgekeerd evenredig met de afstand tot het doel op dat moment.
Ik heb ze vervolgens gekoppeld en “gefokt” om de volgende generatie te creëren. De kans om te worden gekozen om te worden gefokt, was evenredig met de geschiktheid ervan. Soms betekende dit dat men herhaaldelijk met zichzelf werd gefokt als het een zeer hoge relatieve fitheid had.
Ik dacht dat ze een “linker muur knuffelen”-gedrag zouden ontwikkelen, maar ze leken altijd iets minder optimaal te volgen. In elk experiment convergeerden de insecten naar een spiraalpatroon. Ze zouden naar buiten draaien totdat ze een muur aan de rechterkant raakten. Ze zouden dat volgen, en als ze dan bij de opening kwamen, zouden ze naar beneden (weg van de opening) en rond gaan. Ze maakten een bocht van 270 graden naar links en gingen dan meestal het gat in. Dit zou ze door een groot deel van de muren heen krijgen, en vaak naar het doel.
Een functie die ik heb toegevoegd, was om een kleurvector in de genen te plaatsen om verwantschap tussen individuen te volgen. Na een paar generaties zouden ze allemaal dezelfde kleur hebben, wat me zegt dat ik een betere fokstrategie moet hebben.
Ik heb geprobeerd ze een betere strategie te laten ontwikkelen. Ik heb het neurale netwerk gecompliceerd door een herinnering toe te voegen en zo. Het hielp niet. Ik zag altijd dezelfde strategie.
Ik heb verschillende dingen geprobeerd, zoals aparte genenpools die pas na 100 generaties opnieuw worden gecombineerd. Maar niets zou hen tot een betere strategie dwingen. Misschien was het onmogelijk.
Een ander interessant ding is het in kaart brengen van de conditie in de loop van de tijd. Er waren duidelijke patronen, zoals de maximale fitheid die naar beneden ging voordat deze omhoog zou gaan. Ik heb nog nooit een evolutieboek over die mogelijkheid zien praten.