genetica/Evolutionary algoritmo - Pittore

Question

Il mio compito:

creare un programma per copiare una foto (dato come input) utilizzando primitive solo (come triangolo o qualcosa del genere). Il programma dovrebbe utilizzare l'algoritmo evolutivo per creare un'immagine di output.

---

La mia domanda:

ho bisogno di inventare un algoritmo per creare popolazioni e controllare (quanto - in% - corrispondono le immagini in ingresso). Ho un'idea; lo puoi trovare qui sotto.

Quindi quello che voglio da te: consiglio (se trovate la mia idea non è così male) o l'ispirazione (forse hai un'idea migliore?)

---

mia idea:

Diciamo che userò solo triangoli per costruire l'immagine di output.

Il mio primo popolazione è P immagini (generati utilizzando T triangoli generati casualmente - chiamato Elementi).

ho controllare dalla mia funzione di fitness ogni foto in popolazione e selezionare E di loro come élite e resto della popolazione è sufficiente rimuovere:

To compare 2 pictures we check every pixel in picture A and compare his R,G,B with 
    the same pixel (the same coordinates) in picture B. 
    I use this: 
      SingleDif = sqrt[ (Ar - Br)^2 + (Ag - Bg)^2 + (Ab - Bb)^2] 
    then i sum all differences (from all pixels) - lets call it SumDif 
    and use: 
      PictureDif = (DifMax - SumDif)/DifMax 
    where 
      DifMax = pictureHeight * pictureWidth * 255*3 

Il meglio sono utilizzati per creare la popolazione prossimo in questo modo:

picture MakeChild(picture Mother, picture Father) 
    { 
      picture child; 
      for(int i = 0; i < T; ++i) 
      { 
         j //this is a random number from 0 to 1 - created now 
         if(j < 0.5) child.element(i) = Mother.element(i); 
         else child.element(i) = Father.element(i) 
         if(j < some small %) mutate(child.element(i)); 
      } 
      return child; 
    } 

Quindi è abbastanza semplice. Solo la mutazione ha bisogno di un commento: quindi c'è sempre una piccola probabilità che l'elemento X in child sia diverso da X nel suo genitore. Per fare ciò apportiamo modifiche casuali all'elemento in child (cambia il suo colore in base a un numero casuale, o aggiungi un numero casuale alla sua (x, y) coordinata - o al suo nodo).

Quindi questa è la mia idea ... Non l'ho testata, non l'ho codificata. Per favore controlla la mia idea - cosa ne pensi?

Answer 1

Vorrei rendere dinamico il numero di patch di ogni bambino e ottenere l'operazione di mutazione per inserire/eliminare patch con una probabilità (bassa). Naturalmente questo potrebbe comportare una grande ridondanza e un aumento del genoma del bambino. In queste situazioni, di solito è una buona idea utilizzare la lunghezza del genoma di un individuo come parametro della funzione di fitness in modo che gli individui vengano premiati (con un valore di fitness più alto) per l'utilizzo di un numero minore di patch. Quindi, ad esempio, se PictureDif delle persone A e B sono uguali ma A ha meno patch di B, allora A ha una maggiore idoneità.

Un altro problema è l'operatore riproduttivo che hai proposto (vale a dire, l'operazione di crossover). Affinché il processo evolutivo funzioni in modo efficiente, è necessario raggiungere un ragionevole equilibrio di esplorazione e sfruttamento. Un modo per farlo è avere una serie di operatori riproduttivi che mostrano una buona correlazione di fitness [1], il che significa che l'idoneità di un bambino deve essere vicino allo all'idoneità dei suoi genitori.

Nel caso della riproduzione monoparentale è necessario solo trovare i parametri di mutazione corretti. Tuttavia, quando si tratta di riproduzione multi-genitoriale (crossover) una delle tecniche più utilizzate è quella di produrre 2 bambini (anziché 1) dagli stessi 2 genitori. Per il primo figlio, ogni gene proviene dalla madre con la probabilità di 0,2 e dal padre con la probabilità di 0,8, e per il secondo figlio il contrario. Ovviamente dopo il crossover, puoi fare la mutazione.

Oh, e un'altra cosa, per gli operatori di mutazione, quando si dice

... fai cambiamenti casuali in elemento a bambino (cambiare il suo colore di numeri casuali, o aggiungere numeri casuali per la sua (x, y) di coordinate - o il suo nodo)

è una buona idea usare una gaussiana distribuzioneper cambiare il colore, coordinate ecc

[1] Calcolo evolutivo: un approccio unificato di Kenneth A. De Jong, pagina 69