---

Læste lige et par lidt uklare artikler om en form for kunstige neurale net
kaldet GAs.
De brugte ikke back probagation (noget jeg stadig ikke helt har forstået at
implementere), men istedet en metoder der tilsyneladende gik på at lave en
større gruppe forskellige net som alle skulle løse samme opgave.
Efter en rætte test af de forskellige net (som blev initialiseret med
tilfældige vægte), så blev det bedste net taget ud og muteret med små
tilfældige værdier således at der nu igen var en lang række forskellige net,
som var små mutationer af det bedste fra den tidligere omgang.

Sådan forstod jeg det imidlertid. Er det GAs metodem korrekt forstået?
Hvor hurtig til at lære er denne metode sammenlignet med backprobagation?
Den virker jo unægteligt en del mere løs, og simpel... men det er på den
anden side mere lig hvordan tingene vil udvikle sig i virkeligheden, skulle
jeg mene.

Vil det give et fornuftigt resultat hvis man løbende lod de dygtige net pare
sig og lave et afkom som er gennemsnittet af de to oprindelige?
Jeg tænker her på at repræsentere et net som et væsen der tuller rundt i en
verden hvor det kan klare sig mere eller mindre godt, og beregne en
paringsvillighedsfaktor baseret på hvor effektiv væsnet er.
Derved kan man opnå at lave nye net som et gennemsnit af to dygtige net der
mødes, mens de mindre effektive net uddør med tiden.
Spørgsmålet er bareom gennemsnittet af to gode net giver et tredje godt net,
eller om man rykker systemet helt i stykker på den måde..?

---

---

> Du kan ikke bare tage gennemsnittet af to effektive net - hver for sig kan
> de godt vaere ganske effektive, men da de kan have vidt forskellige
> angrebsvinkler naar en opgave skal loeses, kan man ikke bare lave en
> crossover. Det er mere kompliceret end som saa...

Nej efter at jeg fandt nogen flere artikler blev det klart for mig at
metoden der bliver anvendt kaldes Generic AlgorithmS GAS. Der er så tale om
udvælgelsen af to gode net og brug af crossover og små mutationer.
Det ser dog ud til at virke.
Metoden der vises er ombytning af vægte fra et tilfældigt punkt, så med
binære tal kunne to net være

10100101011 og
00100110010 hvor crossover positionen sættes til random 6 hvilket giver to
nye

101001 10010 og
001001 01011

Her gør de så det at der laves 1000 net som prøver at løse problemet 1000
gange. Dernæst tager man 500 gange to tilfældige net, hvor sansynligheden
for at blive valgt er afhængig af deres effektivitet. De 500*2 net mikses
til 500*2 nye net og muteres evt en ganske lille smule.
Det skulle være det.
Noget jeg har misset?
Spørgsmålet er så bare hvordan GAs er sammenlignet med back probagation og
andre alm. metoder til nettræning.
At lave en række tilfældige forsøg og så arbejde videre med de mest
succesfulde forsøg, er jo naturlig udvælgese... bør virke, men måske ikke
lige så hurtigt som en aktiv justering af vægtene.

mig bekendt kan GAs også bruge på problemer af traveling salesman typen,
hvor man ikke har praktisk mulighed for at finde den optimale rute, så man
istedet laver små justeringer af bedre og bedre ruter.

---

> metoden der bliver anvendt kaldes Generic AlgorithmS GAS.

Ups.. ikke generic, men genetic

---

Desilva wrote:
>
> mig bekendt kan GAs også bruge på problemer af traveling salesman typen,
> hvor man ikke har praktisk mulighed for at finde den optimale rute, så man
> istedet laver små justeringer af bedre og bedre ruter.

Ja, men det er kun et af utallige anvendelsesområder. Hvis du er
interesseret i at læse mere om genetiske algoritmer og beslægtede emner,
kan jeg anbefale følgende bøger af Z. (jeg kan ikke stave hans fornavn)
Michalewicz: "Genetic Algorithms + Data Structures = Evolution Programs"
og "How To Solve It - Modern Heuristics".

--
mvh. Karsten Strandgaard Jørgensen - http://www.hammerich.cjb.net
"I call upon our Staffordshire delegate to explain this weird behaviour"

---

> Ja, men det er kun et af utallige anvendelsesområder. Hvis du er
> interesseret i at læse mere om genetiske algoritmer og beslægtede emner,
> kan jeg anbefale følgende bøger af Z. (jeg kan ikke stave hans fornavn)
> Michalewicz: "Genetic Algorithms + Data Structures = Evolution Programs"
> og "How To Solve It - Modern Heuristics".

Det må være Zbigniew. Hurra for cut and paste
Lyder spændende. Tror faktisk jeg vil bestille bogen med det samme.

---

In <a7ehj4$8ue$1@news.cybercity.dk> "Desilva" <a@a.a> writes:

>> Du kan ikke bare tage gennemsnittet af to effektive net - hver for sig kan
>> de godt vaere ganske effektive, men da de kan have vidt forskellige
>> angrebsvinkler naar en opgave skal loeses, kan man ikke bare lave en
>> crossover. Det er mere kompliceret end som saa...

>Nej efter at jeg fandt nogen flere artikler blev det klart for mig at
>metoden der bliver anvendt kaldes Generic AlgorithmS GAS. Der er så tale om
>udvælgelsen af to gode net og brug af crossover og små mutationer.
>Det ser dog ud til at virke.
>Metoden der vises er ombytning af vægte fra et tilfældigt punkt, så med
>binære tal kunne to net være

>10100101011 og
>00100110010 hvor crossover positionen sættes til random 6 hvilket giver to
>nye

>101001 10010 og
>001001 01011

Her vil man maaske bruge Gray Code istedet for normal decimal til binaer enkoding.

/Mvh
Martin

---

"Desilva" <a@a.a> wrote:

> Læste lige et par lidt uklare artikler om en form for kunstige neurale net
> kaldet GAs.
> De brugte ikke back probagation (noget jeg stadig ikke helt har forstået at
> implementere), men istedet en metoder der tilsyneladende gik på at lave en
> større gruppe forskellige net som alle skulle løse samme opgave.
> Efter en rætte test af de forskellige net (som blev initialiseret med
> tilfældige vægte), så blev det bedste net taget ud og muteret med små
> tilfældige værdier således at der nu igen var en lang række forskellige net,
> som var små mutationer af det bedste fra den tidligere omgang.

Vi har brugt den metode (i grove træk) til at lave et neuralt netværk som kan
spille "fire på stribe". Input er en given stilling (input-neuron per felt) og
output er et enkelt neuron som på en skala fra -1 til 1 angiver hvor gunstig
stillingen er (for den ene eller anden spiller). Vi initialiserede X netværk
(population size) tilfældigt, dvs. vægtene valgte vi tilfældigt. Vi lod
derefter alle netværkene spille imod hinanden N gange. Den der vandt fik 2
point, den der tabte fik -1 point og 0 point ved uafgjort. Vi lod dem spille
N/2 gang som `rød' og N/2 gange som `hvid'. Der blev spillet efter
`minimax'-algoritmen (med .ply 6). Med EA (som er en slags avanceret GA) valgte
vi de Z bedste netværk (som var summen af deres spilleresulatater) og muterede
vægtene med lidt normal fordelt `noise'. Derefter erstattede de Z dårligste
netværk i populationen. Vi lod den nye population spille imod hinanden ifølge
samme princip, etc.

Efter vildt mange iterationer (kan ikke huske hvor mange) stoppede vi
processen. Det bedste netværk i populationen anså vi for at være den bedste
strategi, dvs det bedste netværk som kan vinde hvis der spilles efter
minimax-algoritmen (den algoritme er jo ikke så kontroversiel). Et
computerprogram som spillede på baggrund at det resulterende netværk viste sig
at være en meget kompetent modstander!

mvh Carsten

---

> Vi har brugt den metode (i grove træk) til at lave et neuralt netværk som
kan
> spille "fire på stribe". Input er en given stilling (input-neuron per
felt) og
> output er et enkelt neuron som på en skala fra -1 til 1 angiver hvor
gunstig
> stillingen er (for den ene eller anden spiller). Vi initialiserede X
netværk
> (population size) tilfældigt, dvs. vægtene valgte vi tilfældigt. Vi lod
> derefter alle netværkene spille imod hinanden N gange. Den der vandt fik 2
> point, den der tabte fik -1 point og 0 point ved uafgjort. Vi lod dem
spille
> N/2 gang som `rød' og N/2 gange som `hvid'. Der blev spillet efter
> `minimax'-algoritmen (med .ply 6). Med EA (som er en slags avanceret GA)
valgte
> vi de Z bedste netværk (som var summen af deres spilleresulatater) og
muterede
> vægtene med lidt normal fordelt `noise'. Derefter erstattede de Z
dårligste
> netværk i populationen. Vi lod den nye population spille imod hinanden
ifølge
> samme princip, etc.


Jeg forstår det som at i kun brugte nettet til at vurdere om en stilling var
gunstig eller ugunstig for spilleren selv, og denne gunstighedsvurdering
blev så brugt til en alm.minimax søgning?
Det er egentlig en interesant metode, siden i ikke selv behøver kende til
spillet..bare i kender reglerne. Er det korrekt forstået?

> Efter vildt mange iterationer (kan ikke huske hvor mange) stoppede vi
> processen. Det bedste netværk i populationen anså vi for at være den
bedste
> strategi, dvs det bedste netværk som kan vinde hvis der spilles efter
> minimax-algoritmen (den algoritme er jo ikke så kontroversiel). Et
> computerprogram som spillede på baggrund at det resulterende netværk viste
sig
> at være en meget kompetent modstander!

Tror du det samme ville have kunnet lade sig gøre ved et rent netværk unden
almindelige søgemetoder til at støtte det?
ville man på overkommelig tid kunne træne et net op til på egen hånd at
spille effektivt?

---

"Desilva" <a@a.a> wrote:

> > Vi har brugt den metode (i grove træk) til at lave et neuralt netværk som
> > kan spille "fire på stribe". Input er en given stilling (input-neuron per

> Jeg forstår det som at i kun brugte nettet til at vurdere om en stilling var
> gunstig eller ugunstig for spilleren selv, og denne gunstighedsvurdering
> blev så brugt til en alm.minimax søgning?
> Det er egentlig en interesant metode, siden i ikke selv behøver kende til
> spillet..bare i kender reglerne. Er det korrekt forstået?

Ja - lige netop.

> > Efter vildt mange iterationer (kan ikke huske hvor mange) stoppede vi
> > processen. Det bedste netværk i populationen anså vi for at være den
> >bedste strategi

> Tror du det samme ville have kunnet lade sig gøre ved et rent netværk unden
> almindelige søgemetoder til at støtte det?

Du skal jo have en fitnessfunktion som på en eller anden måde angiver "hvor
godt" netværket er. Fitnessfunktionen er en funktion af parametrene der muteres
(og/eller rekombineres i GA), men "funktion" er i den forstand et meget vidt
begreb. Vores funktion var spilleresultat (som vi får ved at spille ifølge
minimax) - vinder eller taber netværket med de givne vægte?. Det er på baggrund
af den funtion at du udvælger de bedste i populationen. Dem der er "bedst"
overlever of laver vores "offspring" og/eller erstatter/tilføjer vores
(dårligste) netværk i populationen.

> ville man på overkommelig tid kunne træne et net op til på egen hånd at
> spille effektivt?

Du lader jo alle netværk spille imod hinanden. I principet bliver de bedre og
bedre (til en vis grænse - og bortset fra lokale minima (som iøvrigt forekommer
mindre ofte i EA/GA end i andre searchstrategier) etc.). De første netværk er
random. Du kan evt. give kvalificerede gæt; evt. kan du træne de første netværk
med gradient descent back.prop. eller lignende hvis du har data.

Vi lod vores computer iterere et døgn før vi stoppede. Det tager genrelt ret
lang tid før du har et brugbart resultat. Dertil skal også siges at der er
MANGE parametre ved EA/GA som du selv skal vælge før du starter. Poulation
size, selection size, mutation factor/frekvens, fitness funktion - hvad skal
der gives til et netværk der vinder/taber osv. A priori er det meget svært at
give et kvalificeret gæt mht til de ting. Vi måtte ofte prøve os frem til det
bedste resultat. Du ender tit med netværk som er tættere på "random" end
"strategisk".

mvh Carsten

---

> Vi lod vores computer iterere et døgn før vi stoppede. Det tager genrelt
ret
> lang tid før du har et brugbart resultat. Dertil skal også siges at der er
> MANGE parametre ved EA/GA som du selv skal vælge før du starter. Poulation
> size, selection size, mutation factor/frekvens, fitness funktion - hvad
skal
> der gives til et netværk der vinder/taber osv. A priori er det meget svært
at
> give et kvalificeret gæt mht til de ting. Vi måtte ofte prøve os frem til
det
> bedste resultat. Du ender tit med netværk som er tættere på "random" end
> "strategisk".

Jeg leger lidt med tanken om at lave en simpel kunstig verden med et antal
væsner der løber omkring og får plus point ved at samle "mad" op og som får
minus point ved at rende ind i stationære forhindringer.
Der er 6 input, 2 der er en vektor til maden, 2 er en vektor til
forhindringen og 2 er dens egen bevægelsesvektor.
Tanken er jo så at de til sidst skal opsøge nærmeste mad, undgå nærmeste
forhindring.

Men... er det praktisk muligt at løse denne opgave med en lille nn og ga til
udvikling af vægtene?
Spørgsmålet er jo også hvor stort nettet skal være. Det eneste jeg kan læse
mig frem til er at der ikke er nogen umidelbare regler for størelsen og
strukturen.
Jeg vil tro at et stort net lærer langsommere, men har større poteniale for
at kunne lære kompleks adfær, mens et lille net hurtigt lærer alt hvad det
kan.

Vektorene kan være binære så der er 4 retninger... vil det dramatisk øge
hvor hurtigt de kan lære at gebærde sig modsat kommatals vektorer... eller
vil det være lige modsat?