gokan
24-10-2003, 09:38
Salve a tutti, so che l’argomento qui sotto trattato non è molto comune, quindi è ben accetto qualsiasi suggerimento. Sono alle prese con algoritmi genetici e devo dire sebbene abbia una “discreta” conoscenza di programmazione sto avendo qualche difficoltà con questi nuovi argomenti. Assumerò che abbiate qualche conoscenza di quello che sto scrivendo.Introduco prima un po’ di codice:
%Dobbiamo trovare lo zero di questa funzione
function y=funzione(x)
y=0.3*(x-305)^3-30.7*(x+51)^2-x+105;
%%% 0.3*(x^2-330.354*x+41687.5)*(x-686.98)
%Questa funzione prende in ingresso i due cromosomi genitori, il punto di taglio dei cromosomi e %restituisce i cromosomi figli.
function [c3,c4]=crossover(c1,c2,t)
c3=bitor(bitshift(bitshift(c1,-t),t),bitshift(bitshift(c2,53-t),t-53));
c4=bitor(bitshift(bitshift(c2,-t),t),bitshift(bitshift(c1,53-t),t-53));
%Questa funzione compie la mutazione del cromosoma “c” nella posizione iesima.
%Esempio c=0110 vogliamo mutare il gene sottolineato, quindi diventa c=0100
function x=mutation(c,i)
x=bitxor(c,bitset(0,i));
%Serve ad ottenere valori tra 0 e 2^28-1
function t=decodifica(c)
t=c/134217.7275-1000;
%Restituisce la “bontà” di un cromosoma
function t=fitness(c)
t=abs(funzione(decodifica(c)));
In pratica, dovrei trovare lo zero della funzione y=….. (ossia 686.98). Tutto questo facendo uso delle varie tecniche di crossover e mutazione. Ho commentato la funzione primo nei passaggi che ho compreso, ci sono alcuni punti invece che sono poco chiari.
function primo(nc, ni, pc, pm)
Cr=round(rand(nc, 1)*(2^28-1)); %%% genera nc cromosomi di 28 bit
mc=fix(nc/2); Fn=[]; Fm=[]; Fs=[]; %Inizializziamo alcune variabili
%Il ciclo for serve a calcolare la fitness degli nc cromosomi, ed inserire ogni singola fitness in un %vettore Fn
for i=1:nc,
Fn=[Fn; fitness(Cr(i))];
end;
Fm=[Fm, mean(Fn)]; %media
Fs=[Fs, std(Fn)]; %deviazione standard
for n=1:ni,
%generiamo una permutazione casuale di nc numeri e riarrangiamo i cromosomi con le rispetive fitness
r=randperm(nc); Cr=Cr(r); Fn=Fn(r);
for i=1:mc,
if rand<pc
% esclude tagli banali, (a e b sono i figli che verranno fuori dal crossover)
[a, b]=crossover(Cr(i), Cr(mc+i), round(rand*26+1));
% t1 dovrebbe contenere le fitness ordinate, t2 contiene gli indici corrispondenti alle varie fitness %ordinate, ([Fn([i, mc+i]) è la fitness dei genitori, fitness(a) e fitness(b) è quella dei figli.
[t1, t2]=sortrows([Fn([i, mc+i]); fitness(a); fitness(b)]);
%La fitness dei genitori la sostituiamo con la fitness dei primi 2 cromosomi (che
%dovrebbe essere quella più bassa)
Fn([i, mc+i])=t1([1, 2]);
%Queste istruzioni sotto non le ho capite
t=[Cr([i, mc+i]); a; b]; Cr([i, mc+i])=t(t2([1, 2]));
end;
end;
%Si fa la mutazione
for i=1:nc,
if rand<pm
Cr(i)=mutation(Cr(i), round(rand*27)+1);
Fn(i)=fitness(Cr(i));
end;
end;
Fm=[Fm, mean(Fn)]; %Aggiorniamo la fitness media
Fs=[Fs, std(Fn)]; %--------------------- dev. standard
end;
%Cr' ci consente di visualizzare tutti i cromosomi in un vettore riga (prima erano in
%colonna), stampiamo la Fm, la Fs. decodifica(Cr)'==>??
Cr, Fm, Fs, decodifica(Cr)
-------------------------------------------------------------------------------------------------
dove
nc= # cromosomi; ni= # interazioni; pc= probabilità di crossover;
pm= prob. di mutazione; Fm= fitness media; Fs= fitness della dev. standard
Fn= vettore colonna contenente la fitness dei cromosomi;
Cr=--------------------------------- nc cromosomi di 28 bit
Fornendo in input dei valori simili:
>>primo(100,60,0.5,0.01)
ottengo l’output allegato.
Mi rendo conto che l’argomento trattato non è tra i più semplici (a parte il fatto che bisogna conoscere un po’ di Matlab) quindi ogni suggerimento è ben accetto. Mi piacerebbe sapere pure se conoscete qualche buon libro di testo in italiano che tratti argomentazioni simili. A noi il professore ha suggerito:
Zbigniew Michalewicz, Genetic Algorithms + Data Structure = Evolution Programs, Springer, 1996
Un conto è leggere qualche paginetta per capire il senso generale di un testo inglese, un’altra cosa è studiare su un testo inglese.
Grazie comunque.
%Dobbiamo trovare lo zero di questa funzione
function y=funzione(x)
y=0.3*(x-305)^3-30.7*(x+51)^2-x+105;
%%% 0.3*(x^2-330.354*x+41687.5)*(x-686.98)
%Questa funzione prende in ingresso i due cromosomi genitori, il punto di taglio dei cromosomi e %restituisce i cromosomi figli.
function [c3,c4]=crossover(c1,c2,t)
c3=bitor(bitshift(bitshift(c1,-t),t),bitshift(bitshift(c2,53-t),t-53));
c4=bitor(bitshift(bitshift(c2,-t),t),bitshift(bitshift(c1,53-t),t-53));
%Questa funzione compie la mutazione del cromosoma “c” nella posizione iesima.
%Esempio c=0110 vogliamo mutare il gene sottolineato, quindi diventa c=0100
function x=mutation(c,i)
x=bitxor(c,bitset(0,i));
%Serve ad ottenere valori tra 0 e 2^28-1
function t=decodifica(c)
t=c/134217.7275-1000;
%Restituisce la “bontà” di un cromosoma
function t=fitness(c)
t=abs(funzione(decodifica(c)));
In pratica, dovrei trovare lo zero della funzione y=….. (ossia 686.98). Tutto questo facendo uso delle varie tecniche di crossover e mutazione. Ho commentato la funzione primo nei passaggi che ho compreso, ci sono alcuni punti invece che sono poco chiari.
function primo(nc, ni, pc, pm)
Cr=round(rand(nc, 1)*(2^28-1)); %%% genera nc cromosomi di 28 bit
mc=fix(nc/2); Fn=[]; Fm=[]; Fs=[]; %Inizializziamo alcune variabili
%Il ciclo for serve a calcolare la fitness degli nc cromosomi, ed inserire ogni singola fitness in un %vettore Fn
for i=1:nc,
Fn=[Fn; fitness(Cr(i))];
end;
Fm=[Fm, mean(Fn)]; %media
Fs=[Fs, std(Fn)]; %deviazione standard
for n=1:ni,
%generiamo una permutazione casuale di nc numeri e riarrangiamo i cromosomi con le rispetive fitness
r=randperm(nc); Cr=Cr(r); Fn=Fn(r);
for i=1:mc,
if rand<pc
% esclude tagli banali, (a e b sono i figli che verranno fuori dal crossover)
[a, b]=crossover(Cr(i), Cr(mc+i), round(rand*26+1));
% t1 dovrebbe contenere le fitness ordinate, t2 contiene gli indici corrispondenti alle varie fitness %ordinate, ([Fn([i, mc+i]) è la fitness dei genitori, fitness(a) e fitness(b) è quella dei figli.
[t1, t2]=sortrows([Fn([i, mc+i]); fitness(a); fitness(b)]);
%La fitness dei genitori la sostituiamo con la fitness dei primi 2 cromosomi (che
%dovrebbe essere quella più bassa)
Fn([i, mc+i])=t1([1, 2]);
%Queste istruzioni sotto non le ho capite
t=[Cr([i, mc+i]); a; b]; Cr([i, mc+i])=t(t2([1, 2]));
end;
end;
%Si fa la mutazione
for i=1:nc,
if rand<pm
Cr(i)=mutation(Cr(i), round(rand*27)+1);
Fn(i)=fitness(Cr(i));
end;
end;
Fm=[Fm, mean(Fn)]; %Aggiorniamo la fitness media
Fs=[Fs, std(Fn)]; %--------------------- dev. standard
end;
%Cr' ci consente di visualizzare tutti i cromosomi in un vettore riga (prima erano in
%colonna), stampiamo la Fm, la Fs. decodifica(Cr)'==>??
Cr, Fm, Fs, decodifica(Cr)
-------------------------------------------------------------------------------------------------
dove
nc= # cromosomi; ni= # interazioni; pc= probabilità di crossover;
pm= prob. di mutazione; Fm= fitness media; Fs= fitness della dev. standard
Fn= vettore colonna contenente la fitness dei cromosomi;
Cr=--------------------------------- nc cromosomi di 28 bit
Fornendo in input dei valori simili:
>>primo(100,60,0.5,0.01)
ottengo l’output allegato.
Mi rendo conto che l’argomento trattato non è tra i più semplici (a parte il fatto che bisogna conoscere un po’ di Matlab) quindi ogni suggerimento è ben accetto. Mi piacerebbe sapere pure se conoscete qualche buon libro di testo in italiano che tratti argomentazioni simili. A noi il professore ha suggerito:
Zbigniew Michalewicz, Genetic Algorithms + Data Structure = Evolution Programs, Springer, 1996
Un conto è leggere qualche paginetta per capire il senso generale di un testo inglese, un’altra cosa è studiare su un testo inglese.
Grazie comunque.