Genetic Programming: Evolution of Mona Lisa « Roger Alsing Weblog

Pubblicato: 10 dicembre 2008 in Vaccate ipertecnologiche

Genetic Programming: Evolution of Mona Lisa « Roger Alsing Weblog.

Per un fan degli algoritmi genetici questo deve essere una specie di paradiso. Solo non mi convince il punto 4.

(via kottke)

commenti
  1. ENTJ scrive:

    Concordo con i commentatori del post che hanno notato che il titolo è fuorviante: non si tratta di un algoritmo genetico, ma di uno stochastic hill climbing (popolazione di un solo individuo, nessuna ricombinazione del DNA, si limita a seguire passo-passo il gradiente della funzione di fitness). Di solito sono meno robusti dei GA, per esempio ho il sospetto che questo converga solo su figure semplici (pochi massimi locali) o grazie a sporadiche botte di culo (non dice quanti test ha fatto prima di arrivare alla sequenza mostrata).
    Però è un’applicazione molto interessante per la compressione di immagini (chissà se a parità di resa è competitiva rispetto a un jpeg).
    PS: il punto 4 non lo vedo un problema, in letteratura esistono diverse metriche per stimare il matching tra immagini (forse intendevi da un punto di vista computazionale?).

  2. Miki scrive:

    Sì, parlavo di complessità computazionale. L’idea in sé mi sembra buona anche per creare un algoritmo genetico vero e proprio, non vedo nessuna preclusione. Il problema potrebbe essere che il matching, soprattutto nei primissimi passaggi, potrebbe essere molto costoso (inutilmente costoso peraltro) e perfino non portare ad una convergenza, certo, è tutto bla bla, bisognerebbe fare qualche prova.
    Cito dalle Faq:

    Q) What is your fitness function?

    A) The fitness function is a pixel by pixel compare where the fitness for each pixel is summed and compared to the parent.

    Con tutti questi dubbi, mi sembra comunque uno spunto interessante.

  3. ENTJ scrive:

    Sono d’accordo, la funzione di fitness sembra estremamente onerosa (se si pensa che deve essere applicata su ogni individuo di ogni generazione). Questo potrebbe spiegare come mai il tizio usi una popolazione di un solo induividuo…
    C’è anche un’altra cosa che non ho capito: come vengono costruiti i poligoni, dato che a quanto pare sono poligoni irregolari di qualsiasi tipo. Mi pare una complicazione inutile per l’algoritmo. Da totale profano dei metodi di approssimazione di immagini raster con immagini vettoriali, mi chiederei invece se è possibile dare dei vincoli sul tipo di poligoni con cui si può ottenere una ricopertura ottimale con un basso numero di poligoni. Ma temo dipenda dall’immagine. Per esempio, se ritrae un ambiente strutturato (città, edifici, oggetti), una buona scelta potrebbe essere usare solo trapezi (facce piane viste in prospettiva). Per le forme naturali, le ellissi potrebbero andar meglio. Che tu sappia, esistono criteri generali?

  4. Miki scrive:

    No, ma ho un amico che lo sa di certo.
    Sono anche certo che esistono funzioni di fitness di gran lunga più efficienti.
    Il numero di poligoni utilizzati potrebbe essere il primo discriminante per la creazione di una popolazione sulla quale andare a fare selezione.

    Anche se temo che poi saltino fuori orrende regolarità nell’andamento, cose come “la popolazione 10-poligoni vince sempre” che dipendono da agghiaccianti teoremi topologici che ci vogliono secoli per dimostrare.

    Congettura di ENTJ-Mezzomondo detta anche dei dieci poligoni: con dieci poligoni arbitrari la cui area totale coincide con il doppio dell’area del riquadro approssimi male una foto della Gioconda ma meglio che con qualunque altro numero di poligoni la cui area totale coincide con il doppio dell’area del riquadro.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...