[C++] Algoritmo Genetico per il quadrato magico
Salve ragazzi, vi espongo il mio problema:
Il professore ci ha chiesto di costruire un algoritmo su C++, l'input deve essere solo un numero N che sia l'ordine della matrice e il programma deve dare in output la matrice di ordine N che abbia come somma di numeri in ogni riga, in ogni colonna e in entrambe le diagonali lo stesso numero.
Esempio:
Dato il numero 3, la matrice di ordine 3 (chiamata anche "Quadrato Magico") sarà la seguente:
8 1 6
3 5 7
4 9 2
che, come potete osservare, la somma dei numeri presenti in ogni riga, in ogni colonna e in entrambe le diagonali è sempre lo stesso numero, in questo caso il numero 15 (chiamato anche "costante magica").
Sono riuscito a fare il programma, ma solo con N dispari, il prof così mi consigliò di usare l'Algoritmo Genetico per le N pari. Ho letto un po' qualcosa riguardo quest'algoritmo Genetico che purtroppo non conoscevo, ma per la costruzione del programma non so ancora come iniziare
Apprezzerei un vostro aiuto a riguardo o qualche considerazione o consiglio che in qualche modo mi possa aiutare, grazie in anticipo
Il professore ci ha chiesto di costruire un algoritmo su C++, l'input deve essere solo un numero N che sia l'ordine della matrice e il programma deve dare in output la matrice di ordine N che abbia come somma di numeri in ogni riga, in ogni colonna e in entrambe le diagonali lo stesso numero.
Esempio:
Dato il numero 3, la matrice di ordine 3 (chiamata anche "Quadrato Magico") sarà la seguente:
8 1 6
3 5 7
4 9 2
che, come potete osservare, la somma dei numeri presenti in ogni riga, in ogni colonna e in entrambe le diagonali è sempre lo stesso numero, in questo caso il numero 15 (chiamato anche "costante magica").
Sono riuscito a fare il programma, ma solo con N dispari, il prof così mi consigliò di usare l'Algoritmo Genetico per le N pari. Ho letto un po' qualcosa riguardo quest'algoritmo Genetico che purtroppo non conoscevo, ma per la costruzione del programma non so ancora come iniziare
Apprezzerei un vostro aiuto a riguardo o qualche considerazione o consiglio che in qualche modo mi possa aiutare, grazie in anticipo
Risposte
Ciao,
non ho molta voglia di cercare, perchè con ordine pari c'è da introdurre altre tecniche non più valide per i dispari? E' un problem più "difficile"?
per la tecnica vediamo dopo...
non ho molta voglia di cercare, perchè con ordine pari c'è da introdurre altre tecniche non più valide per i dispari? E' un problem più "difficile"?
per la tecnica vediamo dopo...
Ciao
sì con ordine pari è praticamente impossibile, o meglio, non è stato ancora trovato un metodo, a quanto ne so.
Credo che per questo il prof mi abbia consigliato di usare l'algoritmo generico che, a quanto ho capito, sarebbe una matrice casuale che opera delle permutazioni fino a quando non uscirà la matrice cercata.
Però non ne sono per nulla sicuro, per questo volevo sapere cosa ne pensate voi....
sì con ordine pari è praticamente impossibile, o meglio, non è stato ancora trovato un metodo, a quanto ne so.
Credo che per questo il prof mi abbia consigliato di usare l'algoritmo generico che, a quanto ho capito, sarebbe una matrice casuale che opera delle permutazioni fino a quando non uscirà la matrice cercata.
Però non ne sono per nulla sicuro, per questo volevo sapere cosa ne pensate voi....
Il problema sembra una variante del sudoku, una soluzione potrebbe essere ridurlo alla k-colorazione se non si trova una soluzione diretta utilizzando il quadrato magico.
"l'algoritmo genetico" è un modello di algoritmo che fa parte di una classe di tecniche per problemi intrattabili.
In particolare l'algoritmo genetico è molto utilizzato (tra quelli evolutivi è il simbolo), ma non quello che hai "descritto".
E' una tecnica perciò ha uno schema da seguire, ce ne sono tante varianti alcune complesse, altre più semplici se si rimane con le funzioni semplici e classiche (es. la permutazione che dici ha un nome "crossover operator").
Comunque hai provato a dare un'occhiata su google scholar
In caso di difficoltà proviamo ad aiutarti a scegliere le funzioni più o meno adatte
Se ti serve ancha capire come funzionano le tecniche evolutive vedi:
- http://www.algosort.com/ v. Genetic Algorithms
- http://profs.sci.univr.it/~posenato/hom ... lgavanzati
PS: il corso che segui è legato all'algoritmica od ottimizzazione o è semplice programmazione in c++? curiosità.
"sssebi":
Però non ne sono per nulla sicuro, per questo volevo sapere cosa ne pensate voi....
"l'algoritmo genetico" è un modello di algoritmo che fa parte di una classe di tecniche per problemi intrattabili.
In particolare l'algoritmo genetico è molto utilizzato (tra quelli evolutivi è il simbolo), ma non quello che hai "descritto".
E' una tecnica perciò ha uno schema da seguire, ce ne sono tante varianti alcune complesse, altre più semplici se si rimane con le funzioni semplici e classiche (es. la permutazione che dici ha un nome "crossover operator").
Comunque hai provato a dare un'occhiata su google scholar
In caso di difficoltà proviamo ad aiutarti a scegliere le funzioni più o meno adatte
Se ti serve ancha capire come funzionano le tecniche evolutive vedi:
- http://www.algosort.com/ v. Genetic Algorithms
- http://profs.sci.univr.it/~posenato/hom ... lgavanzati
PS: il corso che segui è legato all'algoritmica od ottimizzazione o è semplice programmazione in c++? curiosità.
E' semplice programmazione in C++, frequento la facoltà di Matematica, nulla di avanzato quindi per quanto riguarda la programmazione, per questo trovo problemi 
Sì, ho dato un'occhiata, ma mi sembrano cose piuttosto avanzate. Il prof mi ha solo consigliato di usare l'algoritmo genetico (perché è quello che avrebbe fatto lui), poi però ognuno può farlo come vuole in base alle conoscenze che ha, l'importante che alla fine ne esce fuori la matrice cercata. Se allora l'algoritmo genetico è così complesso avevo pensato a delle semplici permutazioni fino a quando non esce la matrice cercata.
Esempio, matrice ordine 3:
1 2 3
4 5 6
7 8 9
Non è un quadrato magico, quindi permuto:
1 2 3
4 5 6
7 9 8
Non è un quadrato magico, quindi permuto:
1 2 3
4 5 6
9 7 8
E così via, fino a quando uscirà la matrice che avrà lo stesso numero come somma degli elementi di ogni riga, di ogni colonna e di entrambe le diagonali (che so appunto che esiste per ogni matrice di ordine maggiore di 2).
Pensi che possa andare questo procedimento o meglio procedere in qualche altro modo?
Nel caso fosse più utile, mi piacerebbe sapere anche qualcosa in più riguardo il "ridurlo alla k-colorazione", è un metodo che non mi pare di conoscere
Sì, ho dato un'occhiata, ma mi sembrano cose piuttosto avanzate. Il prof mi ha solo consigliato di usare l'algoritmo genetico (perché è quello che avrebbe fatto lui), poi però ognuno può farlo come vuole in base alle conoscenze che ha, l'importante che alla fine ne esce fuori la matrice cercata. Se allora l'algoritmo genetico è così complesso avevo pensato a delle semplici permutazioni fino a quando non esce la matrice cercata.
Esempio, matrice ordine 3:
1 2 3
4 5 6
7 8 9
Non è un quadrato magico, quindi permuto:
1 2 3
4 5 6
7 9 8
Non è un quadrato magico, quindi permuto:
1 2 3
4 5 6
9 7 8
E così via, fino a quando uscirà la matrice che avrà lo stesso numero come somma degli elementi di ogni riga, di ogni colonna e di entrambe le diagonali (che so appunto che esiste per ogni matrice di ordine maggiore di 2).
Pensi che possa andare questo procedimento o meglio procedere in qualche altro modo?
Nel caso fosse più utile, mi piacerebbe sapere anche qualcosa in più riguardo il "ridurlo alla k-colorazione", è un metodo che non mi pare di conoscere
"sssebi":
E' semplice programmazione in C++, frequento la facoltà di Matematica, nulla di avanzato quindi per quanto riguarda la programmazione, per questo trovo problemi
Di solito questi argomenti (GA) saltan fuori in corsi dei più disparati, ed infatti anche questa volta non è da meno
Sì, ho dato un'occhiata, ma mi sembrano cose piuttosto avanzate. Il prof mi ha solo consigliato di usare l'algoritmo genetico (perché è quello che avrebbe fatto lui), poi però ognuno può farlo come vuole in base alle conoscenze che ha, l'importante che alla fine ne esce fuori la matrice cercata. Se allora l'algoritmo genetico è così complesso
di per sè non è complesso, son quattro definizioni in croce e poche righe di pseudo-codice. Poi se il problema ha anche una definizione non troppo complessa, come in questo caso, anche una definizione base dell'algortimo non è difficile
La cosa difficile è trovare e definire le migliori specifiche per trovare buone soluzioni (e qua entra in gioco l'esperienza). Ma di solito questa tecnica ne da la maggior parte dei casi.
In effetti le metodologie applicate nei Paper disponibili su google scholar non sono delle più immediate; domani o quando ho un po' di tempo vedo di abbozzarti qualcosa di più semplice (se non ti scrive qualcuno prima)...
avevo pensato a delle semplici permutazioni fino a quando non esce la matrice cercata
----
Pensi che possa andare questo procedimento o meglio procedere in qualche altro modo?.
questa "tecnica" è chiamata forza-bruta, teniamola come ultima speranza...
Nel caso fosse più utile, mi piacerebbe sapere anche qualcosa in più riguardo il "ridurlo alla k-colorazione", è un metodo che non mi pare di conoscere
era solo un'annotazione, visto che il sudoku si riduce a quel problema scommetto che è possibile farlo anche con questo. Diciamo che è la prassi in questo campo dei problemi NP (e famiglia) la tecnica della riduzione: utilizzare soluzioni di problemi ben noti, riducendoci ad quelli simili od equivalenti , che ci sembrano più malleabili per trovare una soluzione (di qualunque genere).
PS:
Su questa prassi, mi hai fatto ricordare una vecchia storiella sui matematici
I matematici non risolvono problemi, ma li trasformano in altri problemi dei quali conoscono già la soluzione.
Effettivamente la storiella è vera, ma fin quando la trasformazione ha un senso non c'è nulla di male, anzi... 
Purtroppo secondo le mie conoscenze a riguardo, quell'ultima speranza, essendo l'unica, era anche la prima... Però al prof voglio presentarci un progetto decente, quindi mi sa che ritorno all'argomento iniziale (GA), dato che mi hai detto che non è così difficile come pensavo questo mi incoraggia ancor di più a farlo in quel modo
A questo punto te ne sarei veramente grato (a te o qualsiasi altro utente) se mi dessi una mano, magari postando qualche abbozzo utile da cui partire... Grazie mille!
Purtroppo secondo le mie conoscenze a riguardo, quell'ultima speranza, essendo l'unica, era anche la prima... Però al prof voglio presentarci un progetto decente, quindi mi sa che ritorno all'argomento iniziale (GA), dato che mi hai detto che non è così difficile come pensavo questo mi incoraggia ancor di più a farlo in quel modo
A questo punto te ne sarei veramente grato (a te o qualsiasi altro utente) se mi dessi una mano, magari postando qualche abbozzo utile da cui partire... Grazie mille!
Allora vediamo...
aggiungo una piccola premessa in relazione con ciò che già scritto sopra.
L'algoritmo genetico è un particolare tipo di algoritmo evolutivo. Secondo me è meglio rimanere sul paradigma evolutivo generico ed utilizzare alcune specifiche del GA per rimanere in tema (non sempre è tutto applicabile, vedrai in seguito perchè dico ciò). Questo perchè non penso il tuo docente si aspetti l'Algoritmo Genetico con tutte le specifiche introdotte da Holland&Goldberg, dove può complicare la comprensione, anche se ti basta la mera applicazione (esistono dei teoremi che garantiscono la convergenza ad una soluzione ottima (locale o meno) ma solo se si segue una certa metodologia) dove anche in alcuni tipi di problemi alcune proprietà/modelli non solo validi. Il succo è che si può sbordare dallo schema fissato, nessuno lo vieta; basta adattarlo al problema in esame.
Detto questo, seguiamo questo schema sottostante di un algoritmo evolutivo generale (o più correttamente Evolutionary Algorithm) adattandolo al nostro problema.
Ora introduciamo qualche definizione ed un po' di formalismo; per non incorrere in fuorviature limitate dal linguaggio scritto.
Sia $S$ una matrice, $S^\text{x}$ e $H$ degli insiemi:
- $S^\text{x}$ è composto da $nxn$ interi distinti di range $[1,n^2]$
- $S$ è la matrice rappresentante del quadrato magico, $S^\text{x}$ è l'insieme dei numeri inclusi in $S$. Esiste una funzione (biettiva, mi pare) permutazione $\sigma:S^\text{x} -> S$ che mappa un elemento per ogni casella, la sua inversa è $v:S->S^x$ (nota che $v(i)$ è la stessa cosa che in informatica si scrive $v$. $S$ può essere considerato sia come matrice di coppie di valori, sia come un vettore lineare di $n^2$ interi. Generalizziamo il tutto considerando una matrice come termine generale.
- sia $h$ un intero positivo, chiamato costante magica del quadrato magico. Tale intero è calcolato secondo la seguente formula: \(h=\frac{n*(n^2 + 1)}2\). Cosicchè $h in H$.
- il quadrato magico è definito tale se l'insieme $H$ è composto solo da $1$ elemento: la costante magica. La cardinalità di $H$ è $1$ ssse il quadrato magico ha le sequenti proprietà. Dove $s_{ij} in S ^^ h in H$:
aggiungo una piccola premessa in relazione con ciò che già scritto sopra.
L'algoritmo genetico è un particolare tipo di algoritmo evolutivo. Secondo me è meglio rimanere sul paradigma evolutivo generico ed utilizzare alcune specifiche del GA per rimanere in tema (non sempre è tutto applicabile, vedrai in seguito perchè dico ciò). Questo perchè non penso il tuo docente si aspetti l'Algoritmo Genetico con tutte le specifiche introdotte da Holland&Goldberg, dove può complicare la comprensione, anche se ti basta la mera applicazione (esistono dei teoremi che garantiscono la convergenza ad una soluzione ottima (locale o meno) ma solo se si segue una certa metodologia) dove anche in alcuni tipi di problemi alcune proprietà/modelli non solo validi. Il succo è che si può sbordare dallo schema fissato, nessuno lo vieta; basta adattarlo al problema in esame.
Detto questo, seguiamo questo schema sottostante di un algoritmo evolutivo generale (o più correttamente Evolutionary Algorithm) adattandolo al nostro problema.
Evolutionary Algorithm: determine initial population sp While termination criterion is not satisfied: generate set spr of new candidate solutions by recombination generate set spm of new candidate solutions from spr and sp by mutation select new population sp from b candidate solutions in sp, spr , and spm
Ora introduciamo qualche definizione ed un po' di formalismo; per non incorrere in fuorviature limitate dal linguaggio scritto.
Sia $S$ una matrice, $S^\text{x}$ e $H$ degli insiemi:
- $S^\text{x}$ è composto da $nxn$ interi distinti di range $[1,n^2]$
- $S$ è la matrice rappresentante del quadrato magico, $S^\text{x}$ è l'insieme dei numeri inclusi in $S$. Esiste una funzione (biettiva, mi pare) permutazione $\sigma:S^\text{x} -> S$ che mappa un elemento per ogni casella, la sua inversa è $v:S->S^x$ (nota che $v(i)$ è la stessa cosa che in informatica si scrive $v$. $S$ può essere considerato sia come matrice di coppie di valori, sia come un vettore lineare di $n^2$ interi. Generalizziamo il tutto considerando una matrice come termine generale.
- sia $h$ un intero positivo, chiamato costante magica del quadrato magico. Tale intero è calcolato secondo la seguente formula: \(h=\frac{n*(n^2 + 1)}2\). Cosicchè $h in H$.
- il quadrato magico è definito tale se l'insieme $H$ è composto solo da $1$ elemento: la costante magica. La cardinalità di $H$ è $1$ ssse il quadrato magico ha le sequenti proprietà. Dove $s_{ij} in S ^^ h in H$:
- [*:2uwtq739]\(\forall i, \sum_{j=1}^n s_{i,j} = h\)[/*:m:2uwtq739]
[*:2uwtq739]\(\forall j, \sum_{i=1}^n s_{i,j} = h\)[/*:m:2uwtq739]
[*:2uwtq739]\(\sum_{i=1}^n s_{i,i} = h\)[/*:m:2uwtq739]
[*:2uwtq739]\(\sum_{j=1}^n s_{j,n-j+1} = h\)[/*:m:2uwtq739][/list:u:2uwtq739]
- definiamo ora il concetto di distanza. Sia $d$ un intero positivo, definiamo la distanza tra una soluzione parziale (un quadrato semi-magico) ed un'altra, coma la differenza in valore assoluto tra ogni riga, colonna e diagonale (ci torneremo poi su questo). Per il momento, limitiamoci a cercare un limite teorico sulla massima distanza tra due soluzioni/matrici, così per avere una valore di contronto. Ciò può avvenire ed essere calcolato quando la matrice è ordinata secondo righe, colonne oppure diagonali (principali), questo corrisponderà a calcolare la costante magica massima e minima di ogni riga/colonna/diag e farne la differenza. Facciamo un es con una matrice ordinata per righe:
$((1,2,3,4),(5,6,7,8),(9,10,11,12),(13,14,15,16))$
$h_\text{min} = 1+2+3+4 = 10$
$h_\text{max} = 13+14+15+16 = 58$
la distanza limite massima sarà: $58-10 = 48$
In generale per calcolare la distanza massima sarà: \[d_\text{max}=|(\sum_{i=0}^{n-1} n^2-i) - (\sum_{i=1}^n i)|\]
Per calcolare la distanza in generale ci pensiamo quando affrontiamo l'algoritmo. Piccola nota: quando $d=0$ perciò se $|H|=1$, sarà ovviamente la costante magica del quadrato magico.
L'idea chiave di un possibile algoritmo è giocare su questa distanza $d$. Ad ogni iterazione si raffina la soluzione cercando la miglior (fitness) distanza (riducendola) che si avvicina di più ad $h$, la costante magica.
Ora mi fermo, a definire le varie parti dell'algoritmo:
- [*:2uwtq739]inizializzazione[/*:m:2uwtq739]
[*:2uwtq739]ricombinazione[/*:m:2uwtq739]
[*:2uwtq739]mutazione[/*:m:2uwtq739]
[*:2uwtq739]selezione [/*:m:2uwtq739][/list:u:2uwtq739]
se sono applicabili e come, lo scrivo in seguito. Per il momento leggi ciò che ho scritto, se ti sembra essere ok e chiaro, in caso contrario ne discutiamo
PS: hai un limite per l'ordine di grandezza di $n$?
EDIT:
aggiunte qualche note.
Continuiamo...
Ora cerchiamo di abbozzare un approccio algoritmico al problema utilizzando un paradigma evolutivo, il modello sopra. Le problematiche implementative le discutiamo in seguito, è una fase successiva ora pensiamo ad alto livello.
prima di tutto definiamo un insieme $P$ popolazione e la sua cardinalità intera |P| oè il numero di generatori di creature sane e robuste.
Per il momento lo lasciamo non fissato, ma tieni conto che è piccolo o grande a piacere.
la definizone di distanza $d$ la raffiniamo.
Siano $i,j$ due righe, due colonne oppure le due diagonali (per il momento consideriamo che non sono combinabili due confronti righe,colonne od altro), allora la distanza tra esse sarà:
\[d_{i,j} = |\sum s_{i} - \sum s_{j}|\]
chiamiamo $d-$matrice un quadrato magica dove la sua distanza massima tra tutte le coppie è $d$.
Ora cerchiamo di abbozzare un approccio algoritmico al problema utilizzando un paradigma evolutivo, il modello sopra. Le problematiche implementative le discutiamo in seguito, è una fase successiva ora pensiamo ad alto livello.
prima di tutto definiamo un insieme $P$ popolazione e la sua cardinalità intera |P| oè il numero di generatori di creature sane e robuste.
Per il momento lo lasciamo non fissato, ma tieni conto che è piccolo o grande a piacere.
la definizone di distanza $d$ la raffiniamo.
Siano $i,j$ due righe, due colonne oppure le due diagonali (per il momento consideriamo che non sono combinabili due confronti righe,colonne od altro), allora la distanza tra esse sarà:
\[d_{i,j} = |\sum s_{i} - \sum s_{j}|\]
chiamiamo $d-$matrice un quadrato magica dove la sua distanza massima tra tutte le coppie è $d$.
- [*:20v0fchp] determine initial population P
l'inizializzazione è abbastanza importante.
Creiamo $|P|$ matrici con valori dell'insieme $S^x$ permutati però con una condizione, ogni distanza $d_(i,j)$, perciò una condizione sulle righe/colonne/diag, la fissiamo ad un limite da non oltrepassare $d°$ (ovviamente $< d_\text{max}$).
[/*:m:20v0fchp]
[*:20v0fchp] generate set F of new candidate solutions, by recombination
devo dire che non è facile trovare una funzione di ricombinazione applicabile in questo problema. Il fatto è che il crossover operator, cioè creare un figlio da due genitori, non è immediato.
Un'idea possibile è questa creiamo due figli (offspring) dato che le soluzioni sulle diagonali sono difficile da legare alle righe/colonne:
- prendiamo due elementi dalla popolazione $P$ e li chiamiamo $p_1$ e $p_2$ (sono due matrici).
- per il figlio $F_1$ lavoriamo prima sulle diagonali, essendo quelle maggiormente perturbative sulla soluzione (sono più livelli differenti) e calcoliamo quale delle due ha distanza minore (ripeto che si lavora sempre a coppie sulle distanze) facciamo che le diagonali minori siano in $p_1$.
- prendiamo le diagonali (o una diagonale vediamo..) di $p_1$ e le riportiamo su una nuova matrice $F_1$ (figlia) notando che ora in $F_1^x$ tali numeri sulle diagonali non sono più disponibili per la mappatura (la funzione $\sigma$ è già definita su tali valori).
- lavoriamo sul secondo genitore $p_2$ e cerchiamo $g$ righe/colonne che contengono i numeri dentro $F_1$ in corrispondenza delle diagonali (o perturbate, ma sempre sulla stessa riga/colonna).
per il figlio $F_2$ lavoriamo sulle righe e colonne
- cerchiamo le distanze minime tra le righe e colonne
- copiamo su una nuova matrice $F_2$ e segnamo come definiti i numeri in $F_2^x$
- poi stesso discorso delle diagonali ma cerchiamo $g$ colonne con gli stessi numeri nelle righe.
- i buchi rimasti nelle celle delle matrici mettiamo i numeri rimasti in $F_1^x$ e $F_2^x$.
questo lo facciamo per ogni coppia in $P$ oppure prendiamo due coppie e non le consideriamo più.
[/*:m:20v0fchp]
[*:20v0fchp] generate set M of new candidate solutions from P and F by mutation
Qui non vedo bene la sua applicazione, non essendoci una mutazione regolare (sarebbe sensata solo se si inserisco delle sottostrutture che filtrano i risultati), ed avendo i suoi elementi delle permutazioni. Di solito la mutazione è la modifica con un numero casuale di un elemento, ed ancora si genera una nuova popolazione dagli insiemi P ed F.
Una possibilità, la più semplice definizione di mutazione:
- su tutto l'insieme $P$ ed $F$ facciamo qualche swap di numeri in una posizione casuale della matrice. Direi che una variante per questo problema potrebbe essere quella di prendere come base dello swap la posizione centrale e fare questo con una posizione casuale del resto della matrice.
Se non si notatano miglioramenti dele soluzioni, togliamo nettamente la mutazione.
[/*:m:20v0fchp]
[*:20v0fchp] select new population E from d° factor candidate solutions in P, F , and M
questa parte è il fulcro dell'algoritmo, dove vengono alla luce le soluzioni migliori. Direi che l'approccio più semplice è quello di utilizzare elitist selection strategies cioè utilizzare come fitness una funzione fissata o sempre migliore per ogni iterazione dell'algoritmo.
Questa fitness o selettore dell'elite è la distanza $d$.
Quello che si può fare è avendo $F$ e $P$ insiemi di $d$-matrici, scartiamo tutte quelle che hanno distanza massima $>$ di $d°$. Alla fine si avrà un insieme $E$ solo componenti dell'elite con elementi di distanza $
[/*:m:20v0fchp]
[*:20v0fchp] While termination criterion is not satisfied:
il fattore di terminazione è quando $d°$ è $0$. Questo lo facciamo accadere perchè all'inizio abbiamo detto che fissiamo un $d°$ per generare le matrici della popolazione $P$. Ad ogni iterazione diminuiamo questo $d°$ finchè non sarà $0$ (nota che è lo stesso valore della fitness).[/*:m:20v0fchp][/list:u:20v0fchp]
Questo è più o meno tutto il discorso. Prima di pensare all'implementazione e strutture dati, cerca di capire cosa ho proposto e discutiamo dove non è chiaro. Forse questo algoritmo non è applicabile ed è poco efficiente ma per il momento è un abbozzo e si può migliorare.
EDIT:
corrette alcune cose.
Bene, il tutto è molto interessante, è una strada che credo non mi sarebbe mai venuta in mente. Per l'implementazione di questo progetto vedo ancora tutto nero davanti a me dato che trovo già di non facilissima comprensione anche solo la via teorica di questo percorso. Però è già qualcosa in più rispetto a prima e già solo il modo di ragionare per questa strada lo trovo molto più simile allo stile del prof, vedrò di fare un passo alla volta, tanto ho ancora qualche altro mese prima della consegna del progetto e ho questa affascinante base da cui partire.
Allora, vediamo quello che ho capito...
Sul primo dei due post tutto liscio, mi piace l'idea di giocare sulle distanze. Al massimo ti chiederei di togliermi qualche dubbio sul concetto di "mappatura" in informatica (anche perché il termine è ripreso in seguito).
Per l'ordine di grandezza di $ n $ non ha dato nessun limite, deve essere un programma valido per ogni $ n $ .
Sul secondo post invece non mi è chiarissimo cosa intendi per "popolazione", cioè quel valore di $ P $ , in che senso generatori di creature sane e robuste?
A questo punto mi confonde già l'inizializzazione. Vorrei meglio capire questo concetto in modo da poter comprendere meglio cosa intendi per elementi della popolazione, come ad esempio $ p_1 $ e $ p_2 $.
Intanto grazie infinite per tutto l'abbozzo, mi è già di grande aiuto
Allora, vediamo quello che ho capito...
Sul primo dei due post tutto liscio, mi piace l'idea di giocare sulle distanze. Al massimo ti chiederei di togliermi qualche dubbio sul concetto di "mappatura" in informatica (anche perché il termine è ripreso in seguito).
Per l'ordine di grandezza di $ n $ non ha dato nessun limite, deve essere un programma valido per ogni $ n $ .
Sul secondo post invece non mi è chiarissimo cosa intendi per "popolazione", cioè quel valore di $ P $ , in che senso generatori di creature sane e robuste?
A questo punto mi confonde già l'inizializzazione. Vorrei meglio capire questo concetto in modo da poter comprendere meglio cosa intendi per elementi della popolazione, come ad esempio $ p_1 $ e $ p_2 $.
Intanto grazie infinite per tutto l'abbozzo, mi è già di grande aiuto
"sssebi":
Sul primo dei due post tutto liscio, mi piace l'idea di giocare sulle distanze. Al massimo ti chiederei di togliermi qualche dubbio sul concetto di "mappatura" in informatica (anche perché il termine è ripreso in seguito).
In questo contesto considerala con lo stesso significato in algebra, un concetto astratto.
Oppure puoi intuirlo come una funzione che estrare da un'urna di $n^2$ numeri distinti, un numero alla volta senza reimbussolamento.
Nell'algoritmo la si può implementare in vari modi, tipo con un vettore di booleani, che estratto un numero casuale si controlla se è stato già estrapolato dall'insieme, vedendo se il suo valore è true/false.
Per l'ordine di grandezza di $ n $ non ha dato nessun limite, deve essere un programma valido per ogni $ n $ .
è una buona e cattiva notizia, bisognerà utilizzare studiare la struttura dati più adatta.
Sul secondo post invece non mi è chiarissimo cosa intendi per "popolazione", cioè quel valore di $ P $ , in che senso generatori di creature sane e robuste?
era una battuta
secondo me è meglio che leggi prima qualcosa sulla terminoligia utilizzata negli algoritmi genetici: http://it.wikipedia.org/wiki/Algoritmo_genetico
wiki it basta per un'infarinatura, poi ne riparliamo su cosa è una popolazione.
Ok, avevo capito bene la mappatura allora.
Ho letto meglio il funzionamento dell'Algoritmo Genetico, effettivamente non era poi così difficile capire cosa si intendesse per popolazione. Avevo comunque capito che fosse una battuta, non mi era ben chiaro il senso che ora credo di aver capito meglio.
Per quanto riguarda il passaggio ai figli in pratica, quando creiamo le due matrici figlie, queste sono più vicine alla soluzione rispetto ai genitori (per questo vengono create). Ma quindi nel nuovo insieme di matrici abbiamo solo i figli che sostituiscono i genitori? Cioè abbiamo costruito altre |P| matrici a partire dalle |P| matrici iniziali (due figli nati da due genitori) più vicine alla soluzione rispetto alle |P| iniziali?
Mi è venuto questo dubbio perché più avanti consideri l'insieme P ed F, mentre io pensavo che già solo il nuovo insieme F potesse bastare per andare avanti.
Ad ogni modo sono convinto che la tua spiegazione sia perfetta, purtroppo sono io (come tra l'altro tutti i miei colleghi) ad essere poco esperti su quest'argomento, quindi mi scuso in anticipo se sono lento nella comprensione.
Ho letto meglio il funzionamento dell'Algoritmo Genetico, effettivamente non era poi così difficile capire cosa si intendesse per popolazione. Avevo comunque capito che fosse una battuta, non mi era ben chiaro il senso che ora credo di aver capito meglio.
Per quanto riguarda il passaggio ai figli in pratica, quando creiamo le due matrici figlie, queste sono più vicine alla soluzione rispetto ai genitori (per questo vengono create). Ma quindi nel nuovo insieme di matrici abbiamo solo i figli che sostituiscono i genitori? Cioè abbiamo costruito altre |P| matrici a partire dalle |P| matrici iniziali (due figli nati da due genitori) più vicine alla soluzione rispetto alle |P| iniziali?
Mi è venuto questo dubbio perché più avanti consideri l'insieme P ed F, mentre io pensavo che già solo il nuovo insieme F potesse bastare per andare avanti.
Ad ogni modo sono convinto che la tua spiegazione sia perfetta, purtroppo sono io (come tra l'altro tutti i miei colleghi) ad essere poco esperti su quest'argomento, quindi mi scuso in anticipo se sono lento nella comprensione.
"sssebi":
Ok, avevo capito bene la mappatura allora.
ok.
Ho letto meglio il funzionamento dell'Algoritmo Genetico, effettivamente non era poi così difficile capire cosa si intendesse per popolazione. Avevo comunque capito che fosse una battuta, non mi era ben chiaro il senso che ora credo di aver capito meglio.
per sicurezza indendevo dire: se un gruppo di una specia metà di sesso maschile e metà femminile, sono stati selezionati in modo lasco ma sotto certe condizioni, c'è una buona probabilità che i loro figli abbiamo caratteristiche che li mantenga sani e riproducibili.
Il principio: se si inizia bane, si ha una buona speranza di finir meglio
Per quanto riguarda il passaggio ai figli in pratica, quando creiamo le due matrici figlie, queste sono più vicine alla soluzione rispetto ai genitori (per questo vengono create).
la ricombinazione.
attento possono essere vicine, non sappiamo dove sia, la cerchiamo di raggiungere con questi metodi.
Se i genitori hanno un fattore 1 sulla distanza (definizione diversa dall nostra) i figlio avranno distanza $1-\epsilon$.
Ma quindi nel nuovo insieme di matrici abbiamo solo i figli che sostituiscono i genitori? Cioè abbiamo costruito altre |P| matrici a partire dalle |P| matrici iniziali (due figli nati da due genitori) più vicine alla soluzione rispetto alle |P| iniziali?
no attento avremo sì un nuovo insieme $F$ di $|P|$ elementi (è puramente notazionale possiamo scegliere che abbiano 3 figli... ma è inutile il terzo è troppo simile ai fratelli. PS: comprendi la terminologia biologica? se no evito...), ma non si elimina $P$, lo filtriamo con la selezione insieme ad $F$ per creare la nuova popolazione $P$ iniziale del nuovo ciclio di vita.
Mi è venuto questo dubbio perché più avanti consideri l'insieme P ed F, mentre io pensavo che già solo il nuovo insieme F potesse bastare per andare avanti.
eh no, in questo caso ti ho ben scritto che non è facile trovare un'operazione di crossover, cioè di combinazione dei geni migliori.
Nota che nella ricombinazione scegliamo due righe/diagonali con distanze minori in due genitori nell'intervallo $[0,d°]$ e poi andiamo random sugli altri elementi, questo può portare a soluzioni peggiori
Ad ogni modo sono convinto che la tua spiegazione sia perfetta, purtroppo sono io (come tra l'altro tutti i miei colleghi) ad essere poco esperti su quest'argomento, quindi mi scuso in anticipo se sono lento nella comprensione.
nessun problema, tutti sugli argomenti nuovi hanno difficoltà
Tieni conto che la questione della distanza come fattore di fitness è una possibile soluzione del problema con un algoritmo. Ce ne possono essere mille altre (es. introducendo definizioni stocastiche), ma ho ritenuto che questa fosse semplice e intuibile
Ah ma certo, scusa non avevo considerato che le soluzioni potessero essere anche peggiori. Ovvio che sia così, però questo rende il tutto più complicato.
Non mi è tanto chiaro infatti il seguito, a quanto ho capito adesso abbiamo formato un insieme più grande composto da F e P, poi con degli swap mutiamo l'insieme in un nuovo insieme F e P per cercare di migliorare le soluzioni (se non migliorano eliminiamo la mutazione). Infine scartiamo tutte le matrici dell'insieme P ed F aventi distanza massima maggiore di $ d^0 $ e iteriamo tutto il procedimento finché $ d^0 $ non sarà $0$.
Sono troppo lontano da quello che intendevi tu?
Non mi è tanto chiaro infatti il seguito, a quanto ho capito adesso abbiamo formato un insieme più grande composto da F e P, poi con degli swap mutiamo l'insieme in un nuovo insieme F e P per cercare di migliorare le soluzioni (se non migliorano eliminiamo la mutazione). Infine scartiamo tutte le matrici dell'insieme P ed F aventi distanza massima maggiore di $ d^0 $ e iteriamo tutto il procedimento finché $ d^0 $ non sarà $0$.
Sono troppo lontano da quello che intendevi tu?
Sono troppo lontano da quello che intendevi tu?
direi di no
"sssebi":
Ah ma certo, scusa non avevo considerato che le soluzioni potessero essere anche peggiori. Ovvio che sia così, però questo rende il tutto più complicato.
complicato nella risoluzione algoritmica o nella comprensione?
se intendi da un punto di vista computazionale mi pare abb ovvio visto che il problema è "difficile", questo tipo di algoritmi ci danno una direzione sulle soluzione ma si può migliorare ma anche peggiorare ed è qui che entra in gioco la selezione dell'elite.
Non mi è tanto chiaro infatti il seguito, a quanto ho capito adesso abbiamo formato un insieme più grande composto da F e P,
ok e siamo alla fine del ricampionamento
poi con degli swap mutiamo l'insieme in un nuovo insieme F e P per cercare di migliorare le soluzioni (se non migliorano eliminiamo la mutazione).
perciò un nuovo insieme $M$ composto dall'insieme $F'\subeF$ e $P'\subeP$ possiamo scegliere $|P|/2$ da uno e dall'altro insieme a caso o tutto per poi mutarli (es. con degli swap).
L'eliminazione della mutazione la intendiamo proprio come toglierla e non inserirla nell'algoritmo. E' abbastanza intuibile che è un'operazione piuttosto costosa in termini computazionali ricopiare delle matrici (anche se dipende da che struttura dati utilizzeremo).
Infine scartiamo tutte le matrici dell'insieme P ed F
scartiamo da $P uu F uu M$ (la mutazione per il momento la teniamo)
aventi distanza massima maggiore di $ d^0 $ e iteriamo tutto il procedimento finché $ d^0 $ non sarà $0$.
tieni conto che la distanza massima (o peggiore) la dobbiamo calcolare per le nuove matrici in $F$ ed $M$. L'iterazione la intediamo come tutto l'algoritmo dalla mutazione alla selezione, ed il fattore di diminuzione (non trovo sinonimi...) di $d°$ lo possiamo scegliere noi. Nel senso che può essere lineare, logaritmico (o inversamente: esponenziale), diviso...
Ah bene
Più complicato nella risoluzione algoritmica dato che le soluzioni possono peggiorare. Infatti dovremmo cercare quelli con una fitness maggiore, invece nel caso in cui le soluzioni potevano solo migliorare bastava semplicemente iterare fino ad arrivare alla soluzione finale. O no?
E' infatti questa selezione dell'elite che non mi toglie ancora tutti i dubbi. Io ho capito che bisognava fare gli swap proprio per togliere le soluzioni peggiori. Ma a questo punto non potevamo farlo direttamente con la popolazione iniziale?
Non mi sono ben chiari i vantaggi di questo procedimento rispetto a quello di operare degli swap sulla stessa popolazione iniziale, eliminare quelli con distanza peggiore e continuare fino a quando la distanza risulterà nulla
Più complicato nella risoluzione algoritmica dato che le soluzioni possono peggiorare. Infatti dovremmo cercare quelli con una fitness maggiore, invece nel caso in cui le soluzioni potevano solo migliorare bastava semplicemente iterare fino ad arrivare alla soluzione finale. O no?
E' infatti questa selezione dell'elite che non mi toglie ancora tutti i dubbi. Io ho capito che bisognava fare gli swap proprio per togliere le soluzioni peggiori. Ma a questo punto non potevamo farlo direttamente con la popolazione iniziale?
Non mi sono ben chiari i vantaggi di questo procedimento rispetto a quello di operare degli swap sulla stessa popolazione iniziale, eliminare quelli con distanza peggiore e continuare fino a quando la distanza risulterà nulla
"sssebi":
Ah bene
Più complicato nella risoluzione algoritmica dato che le soluzioni possono peggiorare. Infatti dovremmo cercare quelli con una fitness maggiore, invece nel caso in cui le soluzioni potevano solo migliorare bastava semplicemente iterare fino ad arrivare alla soluzione finale. O no?
ad ogni iterazione le soluzioni sono migliori dell'iterazione precedente. Nel mezzo dell'algoritmo ci possono essere soluzioni peggiori ma le scartiamo nell'ultima parte, è strutturato in questo modo l'algoritmo per capire quale sia la strada corretta per trovare soluzioni migliori. Per la complessità computazionale c'è poco da fare si lavora con matrici, si può ridurre utilizzando strutture dati ed algoritmi più intelligenti che forza-bruta.
Il concetto che penso tu hai in mente è che possiamo sapere apriori quale sia l'algoritmo che produca la scelta sempre migliore per trovare la soluzione ottima, per certi problemi esiste tale algoritmo (scelta deterministica) altri no perchè come questo sono "difficili" (mai sentito problemi NP?) e quella si chiama scelta nondeterministica (inizio ad odiare sta parola...).
E' infatti questa selezione dell'elite che non mi toglie ancora tutti i dubbi.
l'elite è l'insieme con fitness migliore.
Io ho capito che bisognava fare gli swap proprio per togliere le soluzioni peggiori. Ma a questo punto non potevamo farlo direttamente con la popolazione iniziale?
lo swap serve per non rimanere stazionari su determinate soluzioni. Una mutazione può migliorare o peggiorare una specie.
Non mi sono ben chiari i vantaggi di questo procedimento rispetto a quello di operare degli swap sulla stessa popolazione iniziale, eliminare quelli con distanza peggiore e continuare fino a quando la distanza risulterà nulla
allora il problema del quadro magico è uno di quelli che si basano sulla permutazione degli elementi.
Il procedimento dell'utilizzo di fitness ecc.. è quello di ridurre alle sole permutazioni che possono essere soluzione del problema, cioè quelle ammissibili $
Pensaci un momento. Abbiamo la popolazione iniziale, facciamo degli swap e calcoliamo le distanze e filtriamo i risultati, questo può sì portare ad una soluzione ma quando?
Con le operazioni di crossover uniamo due buone soluzioni per crearne una possibilmente migliore, la mutazione da queste ne crea altre slegate che possono essere sia migliori che peggiori (un evento stocatistico sui geni), la selezione elimino la spazzatura tenendo solo l'elite. chiaro il concetto?
PS: su wiki en ho trovato un possibile riferimento per questo problema che penso ti sia di aiuto riguardo l'applicazione agli algoritmi genetici, applica più o meno il nostro ragionamento (differentemente da quelli disponibili su google scholar che come detto utilizzano altri approcci), a dire il vero mi stupisce che sia così simile, vuol dire che non siamo lontani dalla soluzione.
The construction of a magic square using genetic algorithms
A magic square can be constructed using genetic algorithms.[17] In this process an initial population of magic squares with random values are generated. The fitness scores of these individual magic squares are calculated based on the degree of deviation in the sums of the rows, columns, and diagonals. The population of magic squares reproduce by exchanging values, together with some random mutations. Those squares with a higher fitness score are more likely to reproduce. The next generation of the magic square population is again calculated for their fitness, and this process continues until a solution has been found or a time limit has been reached.
http://www.soc.napier.ac.uk/~benp/summe ... blem2.html
Ah bene, a questo punto credo di aver capito tutto, ora che ci ripenso effettivamente hai ragione. In questo modo arriveremo molto prima alla soluzione, probabilmente è il miglior metodo che esista per svolgere questo progetto, senza contare che è il tipo di algoritmo che farebbe piacere al mio docente (aveva detto che ognuno può farlo come vuole, ma era evidente la sua preferenza su sul GA). Complimenti h_b
Ora arriva il peggio, ma prima di cimentarmi nella parte più difficile ti ripeto i passaggi chiave per vedere se ho capito davvero bene, in caso mi correggi...
Creo P matrici casuali.
Confrontandoli a due a due creo due matrici, la prima che prende la miglior coppia di diagonali (cioè quella che ha distanza minore, il resto degli elementi sono casuali), la seconda prende la miglior coppia di righe o colonne.
Attraverso degli swap su tutto quest'insieme di matrici scelgo solo le matrici che hanno una soluzione migliore, il resto vengono eliminati.
Infine iterando sempre questo procedimento si arriverà a formare il quadrato magico.
Ho saltato qualcosa di fondamentale? Ho capito male qualcosa? ... O posso cominciare a pensare all'implementazione?
Ora arriva il peggio, ma prima di cimentarmi nella parte più difficile ti ripeto i passaggi chiave per vedere se ho capito davvero bene, in caso mi correggi...
Creo P matrici casuali.
Confrontandoli a due a due creo due matrici, la prima che prende la miglior coppia di diagonali (cioè quella che ha distanza minore, il resto degli elementi sono casuali), la seconda prende la miglior coppia di righe o colonne.
Attraverso degli swap su tutto quest'insieme di matrici scelgo solo le matrici che hanno una soluzione migliore, il resto vengono eliminati.
Infine iterando sempre questo procedimento si arriverà a formare il quadrato magico.
Ho saltato qualcosa di fondamentale? Ho capito male qualcosa? ... O posso cominciare a pensare all'implementazione?
"sssebi":
Ah bene, a questo punto credo di aver capito tutto, ora che ci ripenso effettivamente hai ragione. In questo modo arriveremo molto prima alla soluzione, probabilmente è il miglior metodo che esista per svolgere questo progetto, senza contare che è il tipo di algoritmo che farebbe piacere al mio docente (aveva detto che ognuno può farlo come vuole, ma era evidente la sua preferenza su sul GA). Complimenti h_b
attento che non è il miglior metodo, è una possibilità che computazionalmente mi sa che sarà costosa, se non si usano i giusti algoritmi.
Ora arriva il peggio, ma prima di cimentarmi nella parte più difficile ti ripeto i passaggi chiave per vedere se ho capito davvero bene, in caso mi correggi...
come punto di riferimento tieni presente la traccia che ho scritto, è facile dimenticarsi di qualcosa.
Creo P matrici casuali.
non proprio casuali, se ricordi il principio: "meglio si inizia...". Le creiamo con una distanza lasca fissata.
Confrontandoli a due a due creo due matrici
non solo due, due figli per ogni coppia, per creare una nuova generazione.
, la prima che prende la miglior coppia di diagonali (cioè quella che ha distanza minore, il resto degli elementi sono casuali),
ok, in controparte l'altra matrice non scelta si prende una o più righe che combaciano con le disposizioni dei numeri nelle diagonali, il resto casuale. Dico che si può far così, ma se è troppo costoso cambiamo.
la seconda prende la miglior coppia di righe o colonne.
ol.
Attraverso degli swap su tutto quest'insieme di matrici
no, creo un nuovo insieme copia di sottoinsiemi di popolazione e figli, e li faccio degli swap (teoricamente è questa la procedura, ma si può cambiare, come detto è costo in termini di memoria la copia, ne riparleremo).
scelgo solo le matrici che hanno una soluzione migliore, il resto vengono eliminati.
in tutti gli insiemi $P$, $F$ e $F'+P'$ filtro.
Infine iterando sempre questo procedimento si arriverà a formare il quadrato magico.
si spera che funzioni
Ho saltato qualcosa di fondamentale? Ho capito male qualcosa? ... O posso cominciare a pensare all'implementazione?
prima dell'implementazione cerchiamo di capire quali strutture dati posson esser migliori di altre, e abbozzare uno pseudo-codice di alcune parti (sempre alto livello). Il codice implementato sarà tra un po', non troppo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo