Genetisch algoritme - fitness functie

[fjskmdl2]

Ik ben voor het eerst aan het experimenten met genetic algorithms.
Nu wil ik als test een programma maken in processing (java), waarin in een bronfoto (grayscale) probeer na te bouwen via evolutie. De doelfoto begint dus van pixels met random grijswaarden en probeert zoveel mogelijk te bronfoto te benaderen

Nu loop ik echter vast op 2 zaken:

1) Probleem 1:

hoe bepaal ik de fitness functie?

momenteel haal ik de brightness uit de bronpixel en evolution pixel (allebij de waardes kunnen tussen 0 en 100 liggen)

Nu moet ik de brightness kunnen omzetten naar een getal die de fitness voorstelt.
Hiervoor gebruik ik momenteel:

code:

float fitness(int target) {
    float percent = (100/(float)target)*bright;
    return percent;
}

Bright is hierbij de brightness van de evolutie pixel en target is de te vinden waarde (waarde van de bronpixel helderheid)

code:

Voorbeeldberekening:
bright = 37.5 en target = 75
percent = (100/75)*37,5 = 50%

Bovenstaande klopt.

Het probleem is echter wanneer de evolutiepixel een hogere brightness heeft dan de target pixel

code:

Voorbeeld:
bright = 95 en target = 75
percent = (100/75)*95 = 126%

De fitnessfunctie ligt dus niet meer tussen 0 en 100 wat voor problemen zorgt.

Ik heb ook al geprobeerd om verschil = target - bron, maar dit kan zowel positief als negatief zijn wat dan ook voor problemen zorgde.


2) Probleem 2:
Bij het maken van de volgende generatie doe je normaal het volgende:

Je kiest moeder en vader uit de matingpool (matingpool opgesteld via probability, dus hogere fitness komt meerdere keren voor in matingpool en heeft dus meer kans om als moeder / vader gekozen te worden van nieuwe child)
Via crossover + toepassen van mutatie bekom je het nieuwe child element.

Aangezien de DNA van mijn Color object slechts uit 1 gene bestaat (namelijk een integer met de grijswaarde gemapt tussen 0 en 100), weet ik niet hoe ik een combinatie kan vormen van delen van de moeder / vader om het child object te maken.

[Gerco]

fjskmdl2 schreef op donderdag 13 juli 2017 @ 21:42:
Aangezien de DNA van mijn Color object slechts uit 1 gene bestaat (namelijk een integer met de grijswaarde gemapt tussen 0 en 100), weet ik niet hoe ik een combinatie kan vormen van delen van de moeder / vader om het child object te maken.

Kun je niet gewoon het gemiddelde nemen van de twee ouders en een mutatiefactor toepassen (random waarde tussen -10 en 10 en die bij de waarde optellen bijvoorbeeld)?

[Dido]

fjskmdl2 schreef op donderdag 13 juli 2017 @ 21:42:
Ik heb ook al geprobeerd om verschil = target - bron, maar dit kan zowel positief als negatief zijn wat dan ook voor problemen zorgde.

Daar hebben knappe wiskundigen de |abs(olute waarde)| functie voor uitgevonden. Ook te implemeteren (als de taal van je keuze die functie niet kent) middels if (x < 0) x = -1 * x.

[.oisyn]

Dido schreef op donderdag 13 juli 2017 @ 22:27:
[...]

Daar hebben knappe wiskundigen de |abs(olute waarde)| functie voor uitgevonden. Ook te implemeteren (als de taal van je keuze die functie niet kent) middels if (x < 0) x = -1 * x.

Of zoals any sane person het zou opschrijven: if (x < 0) x = -x

[Dido]

.oisyn schreef op donderdag 13 juli 2017 @ 22:55:
Of zoals any sane person het zou opschrijven: if (x < 0) x = -x

Er zijn talen die dat niet pikken, maar ik ben met je eens dat het aantal sane people die in die talen programmeren waarschijnlijk miniem is

[fjskmdl2]

Gerco schreef op donderdag 13 juli 2017 @ 22:22:
[...]


Kun je niet gewoon het gemiddelde nemen van de twee ouders en een mutatiefactor toepassen (random waarde tussen -10 en 10 en die bij de waarde optellen bijvoorbeeld)?

Bedankt, op deze manier is het mij gelukt op de bronpixel te bekomen.

Nu zit ik nog steeds met een "schoonheidsfoutje" ivm het berekenen van de pixel fitness:

code:

float fitness(int target) {
    float percent = (100/(float)target)*bright;
    fitness = percent;
    
    println("target", target);
    println("bright", bright);
    println("fitness", fitness);
    println("----------------------");
    return fitness;
  }

Voorbeeld:

target pixel = 10 (= pixelwaarde naar waar moet geevolueerd worden.

eerste evolutie gekozen pixel waarde is bvb 70:

(100/10)*70 = 700, dus fitness = 700%
target pixel 10 = 100%
dus gegokte = 70 = 700%

eigenlijk klopt dit wel, maar dit betekent wanneer ik de statistieken bij het algoritme toon bij het uitvoeren,
dat de "max fitness" dan begint op 700% en geleidelijk aan daalt naar 100%.

Dit lijkt mij vreemd om dit zo voor te stellen.
Nu vroeg ik mij af of er toch geen manier is om geleidelijk aan van 0 naar 100% fitness te kunnen evolueren in de plaats (zelfs al is de gegokte pixel waarde veel groter dan de target pixel waarde)?

EDIT:

blijkbaar te vroeg gejuichd

als de target pixels een hoge brightness heeft, en de evolutie start met een lage brightness, dan geraakt hij nooit tot een resultaat.

Indien iemand hier ook in geintresseerd is en mij eventueel verder zou kunnen helpen / tips geven kan je de code vinden op bitbucket:

http://bit.ly/2ujZ8gm

(Ben hier reeds 2 dagen op aan het zoeken, dit gaat niet om huiswerk ofzo maar eerder uit interesse.
Eenmaal ik dit werkende krijg wil ik proberen om via een gelijkaardig programma een afbeelding na te maken )

[ Voor 16% gewijzigd door fjskmdl2 op 14-07-2017 00:55 ]

[Caelorum]

Probeer eens het idee van percentages los te laten en een hogere waarde is beter. Wat je wilt is dat de afwijking minder wordt en waarschijnlijk ook dat grotere afwijkingen zwaarder worden meegenomen dan kleine en dan kan je beter kijken maar iets als MSE en hier het minimum van opzoeken.

[Gerco]

fjskmdl2 schreef op vrijdag 14 juli 2017 @ 00:13:
eigenlijk klopt dit wel, maar dit betekent wanneer ik de statistieken bij het algoritme toon bij het uitvoeren,
dat de "max fitness" dan begint op 700% en geleidelijk aan daalt naar 100%.

Het lijkt erop dat je verkeerd om aan het denken bent. Hoe "fit" iets is betekent "hoeveel wijkt dit af van wat ik zoek". De waardes doen er verder niet zo toe. Je kan van de percentages afstappen en dan gewoon "hoger is beter" toepassen.

Als je percentages wilt blijven gebruiken moet je anders rekenen. Je wilt het verschil berekenen tussen de gekozen- en de target waarde en van dat verschil wil je de fitness bepalen. Hoe kleiner het verschil, des "fitter" de waarde is.

Dat omrekenen naar percentages is eigenlijk helemaal niet nodig en mogelijk zelfs wel verwarrend. Met pixels kan het omdat er een maximaal verschil is (het kan nooit groter zijn dan 255 bij 24 bit kleur dus een verschil van 255 is dan 0% fitness en een verschil van 0 is 100% fitness). Er zijn echter zat problemen waarbij je niet zo'n maximum hebt dus dan is een percentage heel moeilijk te bepalen.

[fjskmdl2]

code:

float fitness(int target) {
    //test 1:
    //float percent = (100/(float)target)*bright;
    //fitness = percent;
    
    //test 2:
    /*
    float diff;
    if (bright > target) {
      diff = bright - target;
    } else {
      diff = target - bright;
    }
    fitness = 100 - diff;
    */
    
    //test 3:
    fitness = Math.abs(target-bright);
    fitness = map(fitness, 0, 100, 100, 0);
    
    return fitness;
  }

Ik stel de matingPool array op via:

code:

for (int i = 0; i < population.length; i++) {
      float fitnessNormal = map(population[i].getFitness(), 0, maxFitness, 0, 100);
      int n = (int)fitnessNormal;
      for (int j = 0; j < n; j++) {
        matingPool.add(population[i]);
      }
    }

bright = 33 => fitness(25) = 92
maxfitness is ook 92 dus fitnessnormal = 100 terwijl dit niet juist kan zijn want dit zou pas zo mogen zijn als target = bright

als ik de matingpool print zie ik dat hij bij iedere generation steeds minder random waardes bevat, en op een bepaald moment enkel 1 unieke waarde (maar hierbij is target nog steeds niet gelijk aan bright)

De crossover functie ziet er momenteel zo uit (ik neem het gemiddelde van 2 waardes in de matingPool):
Aangezien de matingpool na een tijdje slechts 1 unique waarde bevat, is het nieuwe childobject ook gelijk aan die unique waarde aangezien ik bvb het gemiddelde van 2 * 30 neem = 60/2 = 30

code:

DNA crossover(DNA partner) {
    int[] child = new int[genes.length];
    
    for (int i = 0; i < genes.length; i++) {
      child[i] = (genes[i] + partner.genes[i])/2;
    }
    
    /*
    int crossover = int(random(genes.length));
    for (int i = 0; i < genes.length; i++) {
      
      if (i > crossover) child[i] = genes[i];
      else               child[i] = partner.genes[i];
    }
    */
    
    DNA newgenes = new DNA(child);
    return newgenes;
  }

[fjskmdl2]

het is uiteindelijk gelukt door in de crossover functie gewoon een random nieuw child te maken en indien dit een hogere fitness heeft, de parent te vervangen door het child (dus niet echt 2 parents combineren)

[Caelorum]

Is daarmee niet het genetische aspect kapot?

[NickThissen]

Dan kun je het niet echt een genetisch algoritme meer noemen denk ik nee.

Aan de andere kant is het sowieso niet echt een handige test case voor een GA, of mis ik nou iets? Dit is toch helemaal geen optimalisatie probleem? Er is maar 1 oplossing en die is exact bekend. Als je je fitness gaat bepalen aan de hand van een al bekende oplossing dan ben je volgens mij gewoon dingen aan het leren die je in een echte test case niet hebt (als je de oplossing al hebt hoef je ook geen GA meer te gebruiken).

[fjskmdl2]

Mijn oorspronkelijke doel was om iets gelijkaardigs te maken als dit:

http://alteredqualia.com/visualization/evolve/

Aangezien dit nog iets complexer is en met meer verschillende parameters rekening houdt, wou ik starten met een simpele versie.
Dus stap 1 was om uit een random pixel array met grijswaarden, via evolutie de juiste afbeelding te tonen. (is volgens mij gelijkaardig aan die link die ik gepost heb, maar dan een stuk vereenvoudigd.

Vandaar dus dat ik geen random pixel kleur naar een doelkleur wou doen "evolueren" om dit voor elkaar te krijgen.

[Caelorum]

Dat voorbeeld heeft geen perfecte oplossing, welke ook een optimalisatie is van de oorspronkelijke representatie. Wat ga een geschikte oplossingsrichtingen maakt. Jouw probleem heeft wel een perfecte oplossing (namelijk exact gelijk aan de input).