Evolutionära algoritmer

[Kraniet]

Kunde ju vara kul att använda tillsammans med ett ordentligt simuleringsprogram. tydligen finns det en snubbe i USA som tillhandahåller tjänsten för kretskortslayout.
Kanske nåt för att göra nya transparenta förstärkare? Problemet ligger väl bara i simuleringen av det hela så man får en så exakt bild av verkligheten. Skulle man kunna simulera upplevt ljud kanske?

[Johan_Lindroos]

??

[EngelholmAudio_inaktiv]

Kunde ju vara kul att använda tillsammans med ett ordentligt simuleringsprogram. tydligen finns det en snubbe i USA som tillhandahåller tjänsten för kretskortslayout.
Kanske nåt för att göra nya transparenta förstärkare? Problemet ligger väl bara i simuleringen av det hela så man får en så exakt bild av verkligheten. Skulle man kunna simulera upplevt ljud kanske?

Backward engineering av NAD 208 och en rejäl funderare på vad som är så transparant med den lösningen vore väl vägen att vandra om det är transparant du söker.

Är det nån (förresten) som tittat in och har nån reflektion kring vad som är så ofärgande med just NAD208? Finns det nån märklighet (tekniskt sett) eller är all koppling enligt pappret?

[Morello]

Har rotat rätt mycket i 208:or. Finns inget konstigt i den, men det som finns är väldimensionerat. Jag kommer dock aldrig någonsin att göra ett klass G-slutsteg !

[Kraniet]

evolutionära algoritmer är en speciell form algoritmer där man anger ett mål och sen har flera "individer" som alla ska försöka ta sig till målet. de två bästa programmen får "kopulera" med varandra och avkomman har då lite bättre möjlighet att ta sig till målet.
det efterliknar alltså naturens evolution och producerar helt otroliga resultat ibland. En slags avel helt enkelt, en effektivt sådan då tusentals generationer kan avverkas per sekund.

[mike34]

:lol: Har rotat rätt mycket i 208:or. Finns inget konstigt i den, men det som finns är väldimensionerat. Jag kommer dock aldrig någonsin att göra ett klass G-slutsteg !

Nää usch Klass-G verkar helhispigt. Är 208 klass-G ?? Ingen koll alså.. ärligt.. KUL VA ??

[Naqref]

En slags avel helt enkelt, en effektivt sådan då tusentals generationer kan avverkas per sekund.

Det beror dock på hur lätt det är att räkna ut kostnadsfunktionen Finns sådana som tar rätt lång tid att räkna ut och troligen i det här fallet med förstärkare så lär det ta några sekunder att simulera varje kromosom/individ. Då kan du låta datorn stå på en stund

Men det är rätt intressant. Något som kan vara klurigt är att få fram är just en bra kostnadsfunktion som gör att evolutionen går åt rätt håll.... det är inte alltid den går åt det håll man vill nämligen

[Kraniet]

ja alltså målet sätter man ju upp helt själv och således dess egenskaper. det är allt man kontrollerar i dessa sammanhang. det och att särkerställa att programmen är syntaktiskt korrekta så man inte kraschar datorn.

man använder det kanske främst in AI forskning och en del forskare tror att det är det bästa sättet att skapa avancerad artificiell intelligens.
det är hur fräckt som helst med tanke på att det är datorn som gör allt. minst lika kreativ som naturen själv. ett problem är dock att de tenderar att exploatera alla möjligheter och således gärna fuskar om det finns kryphål att finna.
ett exempel från chalmers är en robot som var monterad på en påle(för centrering). tanken var att den skulle lära sig flyga med vingarna(alltså ta sig uppåt) men istället började den klättra genom att nypa fast sig på polen.

chalmers har ett program dom kallar "30 apor i en buss". liknelsen är alltså en buss med 30 apor. av dessa väljs sedan fyra helt slumpmässigt och dessa får tävla mot varandra två och två om att köra bussen. de som gör jobbet bäst vinner och får ha barn. det blir lustigt nog alltid två barn och dessa ersätter förlorarna. så har man 30 apor i bussen igen. sedan loopas detta om och om tills man får fram två apor som kör jättebra.

lösningarna som fås fram är väldigt kreativa och resultatet är närmast omöjligt att förutspå. ofta "tänks" det fram lösningar som människor aldrig skulle tänkt på.

[henrik]

Jag har varit nästan varit med om det där med aporna och bussen. Fast det brukar vara runt 50-60 (så många det får plats i en buss och lite fler) overallsklädda människor (inte riktigt apor) som åker till CS-bastun. Där ute är det tävlingar och en del slås ut så till den milda grad att man ibland kan undra om lever. Fast levern lever nog.

Men evultionära algoritmer är väl rätt vanligt bland i kretskortcad? Autorouter funktionen använder väl just sådana?


//henrik

[Style]

du menar genetiska algorithmer.

det är en heuristisk teknik för att hitta när-optimala lösningar på NP-hårda problem. Särskilt kombinatoriska och andra inom diskret matematik förekommande problem.

Fördelen med metoden är att den alltid går att avbryta mellan evolution och att den konvergerar mot optima.

Jag gjorde mitt X-jobb på en tillämpning av detta för läääänge sen.

Man ska dock inse att det är en beräkningsteknik och inget annat. Det Kraniet säger är ungefär som att säga: lösning av integraler med Newtin Rapson det vore kanske nåt för att optimera förstärkare.

[Max_Headroom]

det är en heuristisk teknik för att hitta när-optimala lösningar på NP-hårda problem. Särskilt kombinatoriska och andra inom diskret matematik förekommande problem.

Vad är NP-hårda problem?

Kan det vara sådan här teknik som används t.ex. i pro/E när det använder "design rules" och "solver" (alltså optimerar en viss egenskap efter vissa givna ramar)?

[Style]

NP-hårda problem är beräkningsproblem där man inte kan garantera en optimal lösning inom polynomial rymd eller tid. Dvs antingen minnesåtgång eller tidsåtgång växer snabbt mot oändligheten med nån viss inparameter som bestämmer problemets storlek. Man brukar prata om Ordo(n) som funktionen som beskriver problemets komplexitet. T ex har den effektivaste sorteringsalgorithmen Ordo n log n som komplexitetsfaktor och den funktionen är alltså icke NP. Medan många schemaläggningsproblem har Ordo n! som komplexitetsfaktor och den är NP-hård.

Man brukar säga NP-hård då man faktiskt inte kan bevisa att det inte finns en algorithm som klarar problemet på polynomial tid eller rymd. Om man kan visa det är problemet NP-komplett. Det finns inga NP-kompletta problem idag då aldrig någon har lyckats visa detta. Populärt att doktorera inom detta på teoretisk datalogi eller diskret matematik.

Solvers av olika slag använder ofta kombinationer av genetiska algorithmer, Lagrange-optimering och rena tumregelsheuristker

[Kraniet]

ja jag vet inte exakta appliceringen av det hela men man använder det för att lära robotar, gå, känna igen ansikten, röster etc etc. eller bara i enklaste fallen få en bill att köra i labyrint utan ta i väggarna.
finns väldigt intressanta videos där man har virtuella djur som utvecklar röresle. skrämmande levande ser dom ut.

en film kan hittas här
http://alife.ccp14.ac.uk/ftp-mirror/ali ... karl-sims/

dra ner filen som heter creatures-demo.mpg det är från ett program gjort av Karl Sims http://www.genarts.com/karl/ hans hemsida visar lite annat av vad de kan göra.
Evolutionära algoritmer eller genetiska algoritmer.. det är samma sak.

och jag måste nog säga att det skulle gå att skapa förstärkare med denna metod. det handlar om att stoppa in rätt mängd parametrar och annat. men visst det är en beräkningsmetod i sin grund. men det är ju alla datorprogram.

John Koza heter han som har den där kretskortslayout programmet. Är tydligen 1000 ihoppkopplade datorer som han kallar "invention machine". Med den har han avlat fram lösningar som tidigare varit patenterade. Rätt fascinerande.

edit: John Kozas hemsida
http://www.genetic-programming.com/johnkoza.html

[Style]

nu har jag chansen att briljera lite med kunskaper inom ett smalt område

För att förstå om genetiska algorithmer är en bra metod måste man veta problemets art och lösningsrymdens topologi.

genetiska algorithmer är bra om:
1, problemet är av diskret natur. T ex kombinatoriskt
2, topologin innehåller en relativt stor mängd näroptimala lösningar
3, och det finns ett stort inslag av ekvifinalitet för att nå dit

Nackdelen med genetiska algorithmer är att de i de flesta implementationer inte back-trackar utan man måste slumpa in lösningar från helt andra grenar då och då för att försäkra sig om att man inte fastnar i en del av rymden som ligger långt från optima.

Genetiska algorithmer är inte så krångliga att implementera. Det som är svårt är att hitta bra målfunktioner och ett sätt att ställa upp problemet som passar algorithmen.

När man pratar om att lära en robot att gå etc är problemställningen att få till lärande-loopen på ett vettigt sätt. Olika typer algorithmer för lazy vs eager learning är ett forskningsområde i sig självt och faktiskt bra mycket mer komplicerat.

[Kraniet]

precis: det är intressanta grejjor.. själv är jag lika flytande runt programmering som stenar i vatten. så själva detaljerna har jag ingen aning om. däremot är det väldigt intressant och jag tror det är ett viktigt verktyg i framtida AI-forskning. Tillsammans med neurala nätverk då.
Fördelen med genetiska(som du verkar vara mer trygg med) algoritmer är ju att man när som helst kan stoppa och gå in i programmet och läsa vad den gör. Neurala nätverk är smått omöjliga att veta vad dom egentligen gör. Tror inte man vill hamna i en sits där vi är beroende av idéer som tänkts fram av en dator där vi inte har en aning om hur det fungerar. Snacka om beroende..

Så du sysslar med nån slags programmering?
Själv har jag bara tagit några kurser i kognitionsvetenskap men jag måste säga att detta med robotar och AI är väldigt intressant. Kanske främst eftersom det är så tvärvetenskapligt att du kan komma in i det från vilket håll som helst nästan. Dessutom är det science fiction som är på väg att bli verklighet inom en överskådlig tid.
Stämmer förutsägningarna om att robotbranschen kommer mäta sig med elller passera bilbranschen så är det något verkligt häftigt som är på väg att hända.