algoritmi genetici: implementazione cycle crossover

turillo

Utente Attivo
23 Apr 2012
47
0
0
cari amici chiedo il vostro consulto per un lavoro che sto preparando per dare una materia all'università.

come da titolo del topic si tratta della computazione naturale, cioè tecniche di programmazione che utilizzano
come base teorica i principi delle dinamiche che regolano i comportamenti in natura. tra queste tecniche di
computazione naturale ci sono gli algoritmi genetici che si ispirano alle teorie di darwin sulla selezione naturale.
se volete potete dare una occhiata su internet e troverete diverso materiale, io non sto qua a spiegarvi perchè
non rientra nel topic.

praticamente devo implementare una funzione che simuli il crossover, un operatore genetico che può essere inteso
come una sorta di riproduzione tra due o più individui che genera dei figli, con determinate caratteristiche.

in questo caso gli individui li rappresentiamo come array di lunghezza uguale e il crossover non fa altro che
scambiare i valori tra i due array simulando un pò la riproduzione genetica mischiando il DNA tra i genitori per
ottenere due nuovi figli.

vi siete annoiati a leggere? spero di no..:crying:

riprendiamo il discorso, io dovrei implementare in php una funzione che simuli il cycle crossover,
qui potete trovare una pagina dove spiega schematicamente come funziona(slide 43 e 44).

alla fine il problema è come rendere operativo il meccanismo del cycle crossover.

spero mi possiate dare qualche suggerimento, io ho provato a implementarne una ma mi non funziona ed inoltre
spreca molta memoria e mi restituisce fatal error allowed memory size of ... exhausted

grazie!!
 

borgo italia

Super Moderatore
Membro dello Staff
SUPER MOD
MOD
4 Feb 2008
16.046
150
63
PR
www.borgo-italia.it
ciao
scusa, ma per noi poveri mortali :), non è molto semplice capire.
ho guardato gli slide è ti dico cosa ho capito e cosa no:
1. individuo "a" con n. 9 posti (sempre 9?)
1.1. da "a" prelevi quattro posti (sempre 4?) e li metti nei posti corrispondenti a "x"
2. accoppi "a" ad un altro individuo "b", e qui non ho capito come vengono prelevati/combinati e disposti in "x"
3. prendi i posti di "b" che non si sono combinati con "a" (punto 2) e li metti nei corrispondenti posti di "x"
il ragionamento è "circa" giusto? comunque cerca di spiegare meglio cosa succede in 2
 

turillo

Utente Attivo
23 Apr 2012
47
0
0
ciao
scusa, ma per noi poveri mortali :), non è molto semplice capire.
ho guardato gli slide è ti dico cosa ho capito e cosa no:
1. individuo "a" con n. 9 posti (sempre 9?)
1.1. da "a" prelevi quattro posti (sempre 4?) e li metti nei posti corrispondenti a "x"
2. accoppi "a" ad un altro individuo "b", e qui non ho capito come vengono prelevati/combinati e disposti in "x"
3. prendi i posti di "b" che non si sono combinati con "a" (punto 2) e li metti nei corrispondenti posti di "x"
il ragionamento è "circa" giusto? comunque cerca di spiegare meglio cosa succede in 2

beh anche io sono un povero mortale, più povero di voi :)

allora cerco di spiegare a parole, spero un pò meglio delle slide, il meccanismo del cycle crossover.

il meccanismo si basa su dei cicli, come si evince dal nome, e consiste poi nell'invertire gli elementi dei due array in base al ciclo.
partiamo dal primo indice
1 2 3 4 5 6 7 8 9 indici

a=1 2 3 4 5 6 7 8 9
b=9 3 7 8 2 6 5 1 4

praticamente devi creare un ciclo immaginario come se tracciassi una linea che parte dal valore 1 e va a 9, poi dal 9 devi cercare in a la cella che contiene il 9, poi colleghi il 9 alla cella dello stesso indirizzo in b, che contiene 4, poi ti cerchi il 4 di nuovo in a e cosi via fino a quando non si ritorna all'indice di partenza che nel nostro caso era il primo. alla fine tutti questi indici formano un primo ciclo e non vengono più considerati e cosi si riparte per gli indici rimanenti. purtroppo lo so che viene male a spiegare ma se ti rivedi bene lo schema della slide 44 sono sicuro che prima o poi lo si capisce.

sulle domande che mi hai posto:
1) entrambi gli array sono sempre uguali in lunghezza, qualsiasi essa sia
1.1) il prelievo non c'è all'inizio ma solo dopo aver individuato i cicli, praticamente copi nel nuovo individuo(x) i valori da a o b a seconda dei cicli individuati, scambiandone i valori
2) come ti ho detto qui sopra, x viene creato considerando i valori presi da a e b in base ai cicli

nella slide 44 trovi nello step 1 i cicli che sono 3
1 ciclo: indici 1 4 8 9
2 ciclo: indici 2 3 5 6 7
3 ciclo: 6

questo vale per a e b

come avviene la creazione di x e y(sono 2 che vengono creati)
a partire dal primo ciclo x e y conterrano gli stessi valori nelle posizioni 1 4 8 9 rispettivamente di a e b (x=a e y=b)
quando passiamo al 2 ciclo si invertono e sarà invece x=b e y=a con i che sarà 2 3 5 6 7
al terzo ciclo rimangono inviariati e non si invertono.

quindi in definitiva quando si passa al ciclo successivo si inverte l'ordine fino a "riempire" i nuovi array creati.

spero che sia stato più chiaro
 

borgo italia

Super Moderatore
Membro dello Staff
SUPER MOD
MOD
4 Feb 2008
16.046
150
63
PR
www.borgo-italia.it
ciao
ci provo, problema: quanta fretta hai? se tanta spero che intervenga qualcun'altro, domattina vado via per alcuni gg. quindi penso che inizierò a ponderare al ritorno.
comunque penso che la parte più difficle sia comprendere bene il meccanisco, poi lo script viene di conseguenza
 

turillo

Utente Attivo
23 Apr 2012
47
0
0
diciamo che devo consegnare il progetto entro ferragosto, almeno spero prima del 15.

non ti obbligo a cimentarti in qualcosa che non ti va se hai altri impegni, ci mancherebbe :)

spero che i contributi siano da più lati, cosi anche da valutare al meglio le possibili soluzioni
 

turillo

Utente Attivo
23 Apr 2012
47
0
0
qui propongo uno script che svolge il cycle crossover ma ho un problema:

mi da come errore

Fatal error: Allowed memory size of 268435456 bytes exhausted (tried to allocate 24 bytes) in C:\Programmi\EasyPHP-12.0\www\progettoAES\crossover2.php on line 31

PHP:
<?php

function cycle_crossover($parent1,$parent2,$distanze) {

	$lenght=count($parent1->crom); // dimensione cromosoma
	
	$ciclo=1;
	
	$indici=array();
	$m=0;
	
	$cicli=array();
	$n=1;
	
	$array=array();
	for($i=0;$i<$lenght;$i++){
	
		$array[$i]=$i;
	
	}
	
	for($i=0;$i<$lenght;$i++){
	
		if(in_array($i,$array)) {
		
			$start=$i;
			$ind=$start;
			
			do{
				
				$ind=array_search($parent2->crom[$ind],$parent1->crom); // questo è il rigo dell'errore
				unset($array[$ind]);
				$indici[$m]=$ind;
				//echo $indici[$m]." ciclo ".$ciclo."<br>";
				$m++;
				
			}while($ind!=$start);			
			$ciclo++;
			$cicli[$n]=$indici;
			$str=implode('-',$cicli[$n]);
			//echo $str."<br>";
			$n++;
			$indici=array();
			$m=0;
			//echo "---------------<br>";
		}
		
	}
	
	$s=1;
	
	while($s<=count($cicli)) {		
		
		if($s%2==0) {
		
			for($z=0;$z<count($cicli[$s]);$z++) {
		
				$temp=$parent1->crom[$cicli[$s][$z]];
				$parent1->crom[$cicli[$s][$z]]=$parent2->crom[$cicli[$s][$z]];
				$parent2->crom[$cicli[$s][$z]]=$temp;
		
			}
			$s++;
		}
		else {
		
			$s++;
		
		}
		
		
		
	}
	$parent1->fit=$parent1->calc_fit($parent1->crom,$distanze);
	$parent2->fit=$parent2->calc_fit($parent2->crom,$distanze);
	
}


?>

ho provato questo script su array di dimensioni piccole e funziona egregiamente, quindi a livello di errori non ce ne sono,
la sintassi ovviamente funziona. nel progetto ho a che fare con array che hanno dimensioni da 200 a 400 elementi ma non penso sia questo, resta allora una questione di consumo di memoria eccessiva durante l'esecuzione dello script ma non so cosa fare, è diversi giorni che ci sbatto la testa :crying:
 

turillo

Utente Attivo
23 Apr 2012
47
0
0
ho provato a creare un file di prova con lo stesso script precedente ma dando come parametri due array di dimensioni 50 e purtroppo l'errore non scompare(fatal error: allowed memory size etc...)

PHP:
<?php

function cycle_crossover($parent1,$parent2) {

	$lenght=count($parent1); // dimensione cromosoma
	
	$ciclo=1;
	
	$indici=array();
	$m=0;
	
	$cicli=array();
	$n=1;
	
	$array=array();
	for($i=0;$i<$lenght;$i++){
	
		$array[$i]=$i;
	
	}
	
	for($i=0;$i<$lenght;$i++){
	
		if(in_array($i,$array)) {
		
			$start=$i;
			$ind=$start;
			
			do{
				
				$ind=array_search($parent2[$ind],$parent1);
				unset($array[$ind]);
				$indici[$m]=$ind; // qui la riga dove mi segnala l'errore
				//echo $indici[$m]." ciclo ".$ciclo."<br>";
				$m++;
				
			}while($ind!=$start);			
			$ciclo++;
			$cicli[$n]=$indici;
			$str=implode('-',$cicli[$n]);
			//echo $str."<br>";
			$n++;
			$indici=array();
			$m=0;
			//echo "---------------<br>";
		}
		
	}
	
	$s=1;
	
	while($s<=count($cicli)) {		
		
		if($s%2==0) {
		
			for($z=0;$z<count($cicli[$s]);$z++) {
		
				$temp=$parent1[$cicli[$s][$z]];
				$parent1[$cicli[$s][$z]]=$parent2[$cicli[$s][$z]];
				$parent2[$cicli[$s][$z]]=$temp;
		
			}
			$s++;
		}
		else {
		
			$s++;
		
		}
		
		
		
	}
	$stringa=implode(',',$parent1);
	echo "a -> ".$stringa."<br>";
	$stringa=implode(',',$parent2);
	echo "b -> ".$stringa."<br>";
	
}

for($i=0;$i<50;$i++) {
$a[$i]=rand(1,50);
$b[$i]=rand(1,50);
}

cycle_crossover($a,$b);

?>

ho impostato nel php.ini di easyphp come memory size 256M, a questo punto non so proprio che pesci pigliare. voi che ne pensate?
 

borgo italia

Super Moderatore
Membro dello Staff
SUPER MOD
MOD
4 Feb 2008
16.046
150
63
PR
www.borgo-italia.it
ciao
ho fatto delle piccole prove, secondo me non dipende dalla lunghezza del parent, ma dal fatto che il ciclo ti va in loop infinito sino a che non si blocca "fatal error: allowed memory size etc"
dovresti verificare passo passo come si modificano le varie variabili
 

turillo

Utente Attivo
23 Apr 2012
47
0
0
ciao
ho fatto delle piccole prove, secondo me non dipende dalla lunghezza del parent, ma dal fatto che il ciclo ti va in loop infinito sino a che non si blocca "fatal error: allowed memory size etc"
dovresti verificare passo passo come si modificano le varie variabili

perdonami ma la cosa è strana.
se ad esempio nel codice invece di generare i due array a e b in maniera random gli creo già prestabiliti lo script funziona a meraviglia.
quindi presumo che il codice sia corretto altrimenti mi andrebbe in loop anche in quel caso o no?
 

turillo

Utente Attivo
23 Apr 2012
47
0
0
borgo pio forse ho capito l'errore, mi hai fatto venire in mente un particolare che non avevo considerato..
faccio alcune prove e ti faccio sapere, grazie per il tuo contributo!!
 

borgo italia

Super Moderatore
Membro dello Staff
SUPER MOD
MOD
4 Feb 2008
16.046
150
63
PR
www.borgo-italia.it
ciao
da quello che ho capito (poco) i due parent devono avere gli stessi tipi di cromosomi (eventualmete disposti in modo diverso) e all'interno di un parent non puoi avere due volte lo stesso cromo (sbaglio?)
con
PHP:
<?php
for($i=0;$i<50;$i++) {
	$a[$i]=rand(1,50);
	$b[$i]=rand(1,50);
}
?>
generi si due parent ma puo essere (vado per assurdo, cioè molto improbabile, ma possibile) che il primo ti si riempia di tutti 1 e il secondo di tutti 2)
se devi generare due parent, con gli stessi cromosomi, ma disposti in modo diverso potresti fare

PHP:
<?php
for($i=1;$i<=50;$i++) {
	//non serve mettere l'indice si autogenera
	$a[]=$i; //$a[0]=1, $a[1]=2,...$a[49]=50
}
$b=$a;
//e li rimescoli casualmente
shuffle($a);
shuffle($b);
var_dump($a);echo "<br>";
var_dump($b);echo "<br>";
?>
 

turillo

Utente Attivo
23 Apr 2012
47
0
0
ho trovato la falla che provocava il loop: siccome gli array che passo come argomenti hanno il primo e l'ultimo elemento uguale si generava un loop e quindi io in realtà doveva operare col for fino alla penultima posizione dell'array. difatti applicando la modifica nella condizione del for tutto va liscio. ci ho pensato solo dopo a questo dettaglio che avevo banalmente tralasciato ma che era decisivo ai fini del funzionamento dello script. grazie tante per i tuoi contributi
 

turillo

Utente Attivo
23 Apr 2012
47
0
0
ma perchè accadono certe cose strane? ahahahah

ho un nuovo problema che mi pare alquanto strano: praticamente il codice di questo algoritmo genetico è racchiuso in un ciclo while che rappresenta il numero di generazioni( in ogni ciclo si ripetono le operazioni sulla popolazione) ma praticamente quando invoco lo script non mi completa tutti i cicli. ad esempio io ho una cosa del tipo

PHP:
<?php

while($cicli<500) {

// codice

}

?>

solo che alla fine nella pagina web mi arriva a 420 e non a 499 come dovrebbe essere..cosa può causare questa anomalia?

da premettere che se invece metto come valore un numero più piccolo, ad esempio 50, il tutto funziona a meraviglia

consigli? suggerimenti?
 

borgo italia

Super Moderatore
Membro dello Staff
SUPER MOD
MOD
4 Feb 2008
16.046
150
63
PR
www.borgo-italia.it
ciao
è quello che supponevo, il tempo di vita di default di uno script è di 30 sec (se non termina comunque si arresta)
quindi metti in testa allo script
PHP:
<?php
set_time_limit(240);//tempo espresso in secondi, prova eventualmente aumenta
//.......
?>
oppure devi modificare ini.php (difficile che tu possa farlo in remoto)
 

turillo

Utente Attivo
23 Apr 2012
47
0
0
ciao
è quello che supponevo, il tempo di vita di default di uno script è di 30 sec (se non termina comunque si arresta)
quindi metti in testa allo script
PHP:
<?php
set_time_limit(240);//tempo espresso in secondi, prova eventualmente aumenta
//.......
?>
oppure devi modificare ini.php (difficile che tu possa farlo in remoto)

lavoro su locale(easyphp) e ho impostato nel php.ini max_execution_time = 600

ora magari provo ad aumentarlo, forse è questo il problema..
 

borgo italia

Super Moderatore
Membro dello Staff
SUPER MOD
MOD
4 Feb 2008
16.046
150
63
PR
www.borgo-italia.it
ciao
se con max_execution_time = 600 si ferma a 420 invece di 499 prova ad aumentare il tempo a
600*499/420 = circa 720 sec (sempre che la relazione numero cicli/tempo sia lineare, se esponenziale a cira 2000)
 

Discussioni simili