Løse IQ-oppgaver vha. genetisk programmering

[anders02]

Hei!

 

Jeg har tenkt på tanken med å løse IQ-oppgaver (kun tallrekker) ved hjelp av genetisk programmering. Inndataene vil være en rekke på 5 tall (Inndata1) i tillegg til 5 alternative løsninger (Inndata2), og utdataene vil være et enkelt tall (løsningen, Utdata).

 

Eksempel:

Inndata1: 1 2 4 8 16

Inndata2: 12 32 64 50 100

Utdata: 32

 

Relasjonen mellom tallene i Inndata1 er her at et tall er det dobbelte av tallet før. Relasjonen mellom tallene kan naturligvis være mye mer komplisert, og målet med programmet er å kunne finne ut Utdata selv om relasjonen mellom tallene i Inndata1 er nokså komplekse.

 

Treningseksemplene vil såvidt jeg kan skjønne bestå av Inndata1, Inndata2 og Utdata.

 

Vil dette la se løse vha. genetisk programmering? Kan noen gi meg noen hint på veien om hvordan jeg bør tenke, eventuelt noen gode pekere?

 

 

 

Anders

[Dead_Rabbit]

Det eneste jeg kan komme på er å sjekke relasjonene v.h.a. noen if`s eller noe. Hvilket språk er det du har tenkt å bruke?

[anders02]

Språk er egentlig ikke så viktig. Velger det språket som kan løse oppgaven på best mulig måte. Spørsmålet er heller om oppgaven faktisk lar seg løse vha. genetisk programmering.

 

Kom gjerne med forslag til språk som egner seg godt.

[aklla]

er vel ikke så vanskelig å lage noen regler som sier hva den skal velge...

jeg kan ikke så veldig mye nyttig programmering, så jeg kan nok ikke hjelpe deg der, mIRC er vel det eneste jeg kan lage en slik generator i

er bare å lage en haug med utregninger, og få den til å velge hva som stemmer best,

 

her er noen utregninger du kan bruke:

 

 

hva skal du bruke det til?

 

Inndata1: 1 2 4 8 16

Inndata2: 12 32 64 50 100

la oss kalle inndata1 for tall(i1-i5) og inndata2 for bokstaver(ia-ie)

if ( i1 * i2 = i3 & i2 * i3 = i4 & i3 * i4 = i5 ) {

if ( i4 * i5 = ia ) { echo riktig svar er ia }

if ( i4 * i5 = ia ) { echo riktig svar er ib }

if ( i4 * i5 = ia ) { echo riktig svar er ic }

if ( i4 * i5 = ia ) { echo riktig svar er id }

if ( i4 * i5 = ia ) { echo riktig svar er ie }

}

 

 

 

dette er nok ikke noe språk, men det viser formelen for gange, bare bytt ut med +, - og / så har du det dekket, gidder ikke lage noe mer avansert nå---

[anders02]

Jeg tror muligens du misforstår litt. Problemet skal som nevnt over løses vha. genetisk programmering, og løsningen du foreslår har nok dessverre ingenting med genetisk programmering å gjøre.

 

Veldig kort fortalt er ønsket at jeg i stedet for å skrive alle de if-setningene som du foreslår skal lage et program som lager et program som løser problemet.

 

Først lager programmet mange (la oss si 1000) små, tilfeldige programmer. Alle programmene blir testet på datasettet og de (la oss si 100) beste programmene går videre til neste generasjon og danner grunnlaget for 1000 nye programmer.

 

Var det forståelig eller skal jeg utdype mer/bedre?

 

Hva det skal brukes til? Ikkeno, egentlig. Bortsett i fra at programmet forhåpentligvis vil scoret veldig høyt i IQ-tester som kun består av tallrekker (kanskje alt også kan generaliseres til også å gjelde andre typer IQ-oppgaver).

 

En liten digresjon: Når IQ regnes ut spiller alder inn (spesielt når den som testes er veldig ung). Formelen for å regne ut IQ er noe sånt som

mental alder / faktisk alder * 100

Hva om alderen på programmet bare er noen få minutter når IQ-testen taes og scoren viser at den mentale alderen er noen år. Kan vi ikke da si at programmet har høy IQ?

[aklla]

oki, skjønner det nå, du vil altså lage ett programm som lager andre programmer, og "lærer" av dem og lager enda bedre...

 

er veldig mulig det, men du får en h******* jobb med å kode det, tror det er MYE jobb med det...

 

for at programmet skal funne ut hvem av de 100 som er best, så må det få en tilbakemelding av noe slag, du må nesten ha en generator som genererer tilfeldige tallrekker, som samtidig har svaret, og gir tilbakemelding til det første programmet, så det kan plukke ut de 100 små programmene som er best

 

dette er vel en jobb for nasa...

[A_N_K]

Kunstig intelligens er et svært interessant felt, men har minimal erfaring med det foreløpig og genetiske algoritmer har jeg ikke vært innom dessverre :\ Kunne denne typen oppgave løses vha. nevrale nettverk?

[søppel]

Det er begrenset hvor mye erfaring jeg har med dette selv.

 

Kan tenke seg at man har et sett med mulige funksjoner - og et sett med mulige data - og omtrent uendelige kombinasjoner av disse. Vi kan kalle én bestemt kombinasjon for DNA (en klasse f.eks.), et DNA består da av "pekere" til de mulige funksjoner (+, -, *, exp ..osv) og dataene (tilfeldige tall som f.eks. skal være parameter nr. 2 i sammenheng med parameter nr. 1 som er fra inndatarekken)...

 

Så lager man (tilfeldige) instanser av et DNA og vi får en algoritme (objekt). Denne kjøres på settet med inndata og vi får ett sett utdata.

 

Så må det være en rutine som sjekker om algoritmen er blandt de beste til nå.

 

Så må den ha et sett med de 10 (f.eks.) beste algoritmene som får lov til å "formere" seg ved å bytte egenskaper seg i mellom (funksjonsvalg og data til variablene sine).

 

I tillegg må det oppstå små (og noen ganger) større mutasjoner - dette vil si endringer av de egenskaper som er arvet fra "foreldre".

 

Et programmeringsspråk som kan genere eller interprete kode @ runtime er lettest her tror jeg.

 

Edit:

(dette ble skrevet fryktelig raskt)

Endret 3. januar 2005 av søppel

[anders02]

søppel: Tror du Scheme vil være et passende språk til implementering? Kan noe Scheme fra før, og håper det ikke vil ta altfor lang tid å sette seg inn i det. Hvis ikke vet jeg at det finnes noen tilgjengelige biblioteker (genetisk programmering) til blant annet Java jeg kan bruke hvis jeg velger det (eller C eller C++ for den saks skyld). Eller vil Python være et godt valg her? (Python har jeg bare såvidt vært borti, men det bør være rimelig enkelt å lære seg.)

 

Som fitness-krav til å bestemme hvilke programmer som skal få lov til å leve til neste generasjon vil jeg kanskje tro det holder å finne ut hvor mange programmer som velger riktig løsning på et gitt datasett (la oss si at jeg har 1000 tallrekker med tilgjengelige løsninger og de hvis et program er blant de f.eks. 10 % beste programmene når det gjelder å tippe riktig løsning på en tallrekke får lov til å være med til nesten generasjon).

 

Men hvordan bør jeg angripe problemet? Bør jeg begynne med å si hvordan jeg ønsker at det endelige programmet skal se ut (dvs. det programmet som gjør IQ-testen best)? Dette vil antageligvis ligne en del på det kodeeksemplet aklla gav, vil jeg tro.

 

aklla: Jeg er klar over at det er en nokså stor oppgave. Håpet er at jeg blir god på genetisk programmering når jeg er ferdig. Oppgaven skal forresten løses som hovedoppgave, så jeg har en del uker til disposisjon der jeg kun skal jobbe med dette.

 

Det store spørsmålet er: Kan jeg være helt sikker på at dette kan løses vha. genetisk programmering? Litt kjipt å begynne på problemet hvis jeg ikke vet om det kan løses...

[A_N_K]

Det kan virke som Prolog er et passende språk for GP.

[søppel]

http://en.wikipedia.org/wiki/Categorical_l...gical_languages

Kan hende Prolog ikke er så dumt -- dette er "way over my head" egentlig.

 

Kan man i det hele tatt være sikker på noe som helst hvis man "ikke gjør det selv", eller spesifiserer ting eksplisitt? (Til og med da skjer det ofte rare ting; fraktaler, C.A. og andre GameOfLife -lignende ting f.eks.)

 

Edit:

Til det andre du lurer på kan jeg vel sitere fra Paul Graham når han snakker om design og "Two-Phase Development":

If programming were an entirely mechanical process - a matter of simply translating specifications into code - it would be reasonable to do everything in a single step. But programming is neven like that. No matter how precise the specificatios, programming always invelves a certain amount of exploration - usually a lot more than anyone had anticipated.

 

It might seem that if the specifications were good, programming would simple be a matter of translatitng them into code. This is a widespread misconception. Programming necessarly invoves exploration, because specifications are necessarily vague. If they weren't vague, they wouldn't be specifications.

 

(de ville vært kode i stedet altså) .. Jeg har i hvertfall ingen "design patterns" liggende i bakhodet enn de alt for generelle jeg allerede forsøkte å nevne (innser nå at jeg misforsto litt av oppgaven forresten). Så det blir vel til at du må utforske litt her - da jeg ikke vet åssen man skal angripe et slikt problem. Som du nevnte kan det kanskje være en idé å titte på andre biblioteker (eller kanskje spesifikasjonene/dokumentasjonen/"forskningspapirene" dems!), men jeg tror ikke C++ og Java er de aller, aller beste språkene til det her.

Endret 3. januar 2005 av søppel

[anders02]

Meget mulig at Prolog er et godt alternativ. Det har i alle fall én åpenbar fordel, og det er at jeg behersker Prolog bedre enn jeg behersker Scheme.

 

Men når alt kommer til alt er vel valget av programmeringsspråk ikke så altfor viktig, og jeg tror nok, hvis jeg klarer å definere problemet godt nok, skal klare å implementere det i både Java, Prolog og Scheme.

 

Tror jeg må tenke litt hardt på dette. Spør igjen hvis det er noe mer, jeg. Takk for all hjelp så langt. (For all del: Kom gjerne med flere innspill, jeg trenger all hjelp jeg kan få.)

 

Edit: Dessverre har Paul Graham så altfor, altfor rett. Vanligvis liker jeg det sikre, og på en måte er det litt kjipt å velge en hovedoppgave som jeg ikke vet om kan løses eller ikke. På den annen side: Kan jeg vise at oppgaven ikke kan løses vha. GP, har jeg jo funnet ut noe da også...

Endret 3. januar 2005 av anders02

[søppel]

Kan jeg vise at oppgaven ikke kan løses vha. GP, har jeg jo funnet ut noe da også...

Sannt! :]

[Dead_Rabbit]

Hva med å gjør noe sånt som dette:

 

1)innput = 1. tall i rekken.

2)Opprette fire tråder hvor hver tar for seg +,-,* eller /.

3)Hvis vi finner noen match mellom det vi kommer frem til, og neste tall i rekken så lar vi den funksjonen "leve vidre" ved å "notere" hva gi gjorde. 4)Vi går løs på neste tall ved at vi begynner med å gjøre det vi kom frem til på pungt 3 og gjør pungt 2. Deretter går vi til pungt 3 og 4.

 

PS: Bare si ifra hvis det var litt dårlig forklart.

[delling81]

Dette kan fort bli litt over my head, har hatt litt lite om disse temaene. Scheme kjenner jeg ikke til

 

Det kan jo være mulig å teste en slags ape-shakespear approach. Ikke det om jeg tror det er lurt, det krever sikkert litt for mye generering for i heletatt finne noe som virker. (altså random generering av binær kode og velge det som virker ) Tror uansett det vil bli en utfordring å finne en måte som vil faktisk tvinge frem noe læring.

 

Dersom du tester prog først på et sett data, så et annet sett, så har man kanskje en god fordel med prolog. Problemet jeg ser for meg er at det ikke blir random når du lager programmet selv. Slik vil det være vanskelig å finne noe løsning som ikke kommer fra noe du selv har tenkt ut på forhånd.

 

Husker seff altforlite om hvordan vi laget alle disse programmene når vi holdt på med ai. Men om du klarer å bygge div neural networks og lignenede, så kan du jo alltids lære programmene dine ved å kjøre dem gjennom noe svar, og se hvordan de oppfører seg. Genetisk programenring er jo om å la de sukksessfulle overleve, men vet ikke om neural networks er litt utenfor hva du skal holde på med. Uansett vil du ha hendene dine fulle med å lage et program som genererer kode som løser disse problemene. (Mulig jeg ikke har nok highlevel forståelse for å forstå hvordan dette skal gjøres)

 

Men om jeg ikke husker helt feil, så må det finnes et program som kan dytte disse tallene inn i formler, komme ut med forskjellige tilnærminger (tilpassning av tallmatrialer), og som hoster ut en løsning. Det blir spm om regnekraft, og det er kanskje ikke en avveining mellom kompleksitet og tid (ocham's razor?) du ønsker som svar.

 

Ser ut som det blir endel koding for din del, allikevel, trodde hovedoppgave skulle heve seg over det

 

Min begrensede kjennskap til prolog tilsier at det sannsynligvis er et bra for oppgaven, problemet er om du må ha noen biblioteker som støtter lineær (ikke lineær approksimasjon) før det blir noe fart på sakene.

 

Føler dette ble mye ull, men samtidig ikke helt sikker på hva du spør om.

[aklla]

skal de 900 nye løsningene genereres tilfeldig tilfeldig eller har du tenk at det skal være en plan med dem?

 

hadde vært bra om du f.eks hadde laget 500 nye tilfeldig og blandet de 100 du hadde fra forrige generasjon, slik at du får 400 som er laget fra forrige generasjon, og 100 som kommer direkte fra forrige, så du bruker alle 3 måtene å generere på, tror det er den beste løsningen...

 

den kan jo evt også lære hvem av dem som er best å bruke, som øker antall koder den tar fra de forskjellige måtene...

 

edit: skal se om jeg kan lage en liten prototype

edit2: prototypen kommer ikke til å lære på samme måte, den blir veldig kuttet ned, og kodene programmert på forhånd, men den kommer til å plukke ut hvilke som funker og ikke funker selv...

Endret 4. januar 2005 av aklla

[anders02]

Takker for innspill!

 

zirener: Er det genetisk programmering? Hvis det er det hadde det vært greit om du forklarte bedre. Hvis ikke er det nok dessverre utenfor det jeg har tenkt å jobbe med.

 

delling81: Jeg må lese grundigere gjennom det du har skrevet, men skal komme med noen kommentarer nå. Kompleksiteten til programmet er uten betydning (så lenge jeg rekker å kjøre det ferdig før innlevering). Selv om problemet muligens kan løses på forskjellige måter er det en AI-måte som er interessant for meg. Dersom nevrale nettverk løser problemet bedre enn genetisk programmering er det forsåvidt ikke noe i veien for å bruke det i stedet. Men i det du skriver, tenker du da å bruke genetisk programmering i kombinasjon med nevrale nettverk, eller å kun bruke nevrale nettverk? Ape-shakespear approach har jeg aldri hørt om, skal ta en titt på det snart.

 

aklla: Akkurat hvordan de 1000 løsningene i en generasjon genereres blir et spørsmål om hva jeg tror gjør at de kommer først til målet. De 100 beste blir muligens kopiert direkte, mens de resterende 900 blir generert ved hjelp av krysning (crossover), mutasjon og mindre tilfeldigheter. Klarer du å lage en prototyp jeg får noe fornuftig ut av blir jeg happy.

 

Når det gjelder diskusjonen om programmeringsspråk føler jeg egentlig at denne er nokså underordnet... Men selvfølgelig: Jeg setter pris på konstruktive innspill også her.

[Dead_Rabbit]

Eh.. Tror jeg glemte litt det der med genetisk programmering..

Edit: Men på en måte, så er det vel kansje det..? Programmet prøver ut 4 regnearter, og den som lykkes med å finne det neste tallet i rekken, "går vidre", ved at man neste gang, først prøver den regnearten og så en ny en "oppå" den. Det blir som en formel:

 

input: 1 2 4 8

 

programmet gjør følgende:

 

1+1 = 2

dette matcher neste tall i rekken, så programmet bare går vidre

1*1 = 1

1*2 = 2

dette matcher også neste tall i rekken som er 2

1-1 = 0

tallet bare minker, dette gidder vi ikke

1/1 = 1

1/2 = 0.5

tallet bare minker, dette gidder vi ikke.

 

Vi står nå igjen med * og +. Begge gir like god match så vi prøver begge:

2+1=2

2+2=4

match!

2*1 = 2

2*2 = 4

match!

 

osv, osv.

Hvis vi får en litt mer kompileset formel nå, så vil nok etterhvert stå igjen med en regneart som vi kan bruke, og når det ikke går, så begynner vi på nytt med det tallet som vi når står ovenfor

 

Så det blir på en måte et utvalg, men jeg vet ikke om det var slik du ville...

Endret 4. januar 2005 av zirener

[anders02]

zirener: Hele cluet er å bruke genetisk programmering (evt. en annen AI-teknikk) til å løse problemet. Hvordan har du f.eks. tenkt å løse følgende rekke med din teknikk, uten å hardkode:

1 1 2 3 5 (et tall er summen av de to foregående)

 

Jeg er klar over at noen rekker antageligvis aldri vil kunne løses på denne måten, f.eks. følgende:

2 3 5 7 11 (primtall)

 

Kan det tenkes at et nevralt nettverk vil løse problemet bedre enn genetisk programmering?

[aklla]

 

2+1=2

2+2=4

 

bare en lite rettelse, den stemmer nok ikke, 2+1=3

 

 

tror at ett nevralt nettverk nettverk vil løse det bedre enn ett generisk program

 

edit: tror egentlig det beste er å kode tingene selv, generisk koding er vel mer på forsker-statiet, men man kan jo f.eks få til en "tenkende" kode, som kan sammenligne dine regler, ta noen unntak osv

 

edit2: primtall kan løses, vet at man først sjekker gjennom alle reglene du har satt opp, stemmer ingen kan du sjekke hva det kan deles på, er det ingenting, så kan det komme opp "primtall?"

Endret 4. januar 2005 av aklla