+ Rispondi al Thread
Pagina 1 di 2 12 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 14

Discussione: Algoritmi genetici e utilizzi concreti.

  1. #1
    Dev-01 non è in linea Scolaretto
    Post
    271

    Algoritmi genetici e utilizzi concreti.

    Buongiorno,

    per esercizio e curiosità mi sto dedicando allo studio e alla realizzazione di un algoritmo genetico.

    La libreria che sto realizzando esegue/eseguirà le seguenti funzioni:

    Generazione casuale di una popolazione di organismi (espressi in formato stringa formate da 1 e 0) di lunghezza arbitraria;
    Aggiunta, eliminazione e mutazione dinamica del materiale genetico;
    Selezione di individui corrispondenti ad un determinato criterio (liberamente ridefinibile);
    Operazioni di cross-over legate ad indici percentuali di materiale genetico genitoriale (ridefinibile) in sezioni non fisse (prestabilite) della sequenza.

    Quello che vorrei realizzare è una versione il più possibile dinamica e personalizzabile dell'algoritmo ma... dopo?!?

    Mi rendo perfettamente conto del fatto che l'argomento si abbastanza vasto e vario (e che il mio lavoro rappresenti esclusivamente la base minima di partenza) per cui non chiedo spiegazioni esaustive ma piuttosto qualche spunto per entrare nella logica e nella visuale delle possibili/probabili applicazioni reali di tali tecniche/conoscenze una volta terminatane la realizzazione.

    Grazie.

  2. #2
    L'avatar di AntonioG
    AntonioG non è in linea Moderatore Globale Ultimo blog: Commodore 64 e Codemotion
    Luogo
    Roma
    Post
    14,335
    Blogs
    5
    Sposto nella sezione

    Algoritmi e Strutture Dati
    Avvisi generali e importanti, a pena CHIUSURA thread e/o BAN
    Il crossposting è vietato.
    Le richieste di "pappa pronta" sono vietate.
    Utilizzate i tag CODE per il codice.
    Leggere il Regolamento per chiarimenti PRIMA di creare nuovi thread.
    Utilizzare sempre i PM per comunicare con i moderatori.
    Non mi contattate in PM per problemi di software, usate il forum

  3. #3
    Dev-01 non è in linea Scolaretto
    Post
    271
    Ok, grazie 1000.

  4. #4
    L'avatar di +m+
    +m+
    +m+ non è in linea Scribacchino
    Post
    920
    In generale, a parte che esistono 1000 tipi di genetici diversi, l'utilizzo è per trovare minimi locali per problemi difficili e non analitici.
    Cioè, praticamente, tutti

    Io ci ho risolto un problema della Settimana Enigmistica

  5. #5
    Dev-01 non è in linea Scolaretto
    Post
    271
    Ciao +m+,

    si ma la mia domanda non era quella...

    Tento di esplicitare meglio la mia domanda tentando di non dire baggianate:

    La questione degli algoritmi (almeno dove sono arrivato io e, credo, nella sua accezione teorica di base) viene legata alla costituzione e alla evoluzione di una stringa formata da una raccolta di caratteri (nel mio caso 1,0,*) tramite cross-over e mutazione, alla quale viene associato un valore a seconda che la stringa, ad ogni successiva generazione, rispetti o meno determinati paramentri e/o criteri posti come indice di bontà/validità dell'"individuo".

    Adesso, al di la delle tecniche e delle metodologie utilizzate, alla fine ti ritrovi con una stringa (che sempre nel mio caso) potrebbe essere così espressa:

    [01*]+

    Diciamo che la stringa debba contenere una determinata sequenza o almeno il numero specificato di geni con valore 1 e, inoltre, rispettare una certa lunghezza...

    come passo io ad interpretare questi dati dalla rappresentazione in essere alla realizzazione di una soluzione?
    (Non chiedo una spiegazione esaustiva ma anche un esempio molto blando, giusto per tentare di capire).

    Una volta trovati i minimi locali, come li trasformi in qualcosa di utilizzabile?

    Probabilmente la mia concezione è ancora troppo legata alla programmazione "normale" per riuscire ad estrapolarne il concetto alla base ed è per questo che sto chiedendo aiuto.

    Comunque, tanto per aiutarmi nella mia spiegazione, linko questo paper:

    Esempio di utilizzo.

    Intanto grazie 1000.

  6. #6
    L'avatar di +m+
    +m+
    +m+ non è in linea Scribacchino
    Post
    920
    codifichi in binario il valore delle variabili, ad esempio, nei geni con una funzione di fitness
    avrai quindi che il valore del gene/variabile lo calcoli banalmente come somma delle potenze di due per l'elemento della popolazione
    eventualmente normalizzato (riscalato) con attenzione alla stabilita numerica
    scusa ma lavori alla cieca?
    Ultima modifica di +m+; 12-04-2016 14:16 

  7. #7
    Dev-01 non è in linea Scolaretto
    Post
    271
    Non è che lavoro alla cieca... è che ho iniziato ad occuparmene da tre giorni.

    Credo che avere chiaro il concetto me ne semplifichi l'apprendimento.

    E' per questo che non ho chiesto cose troppo specifiche ma una esemplificazione estrema affidandomi a qualcuno con esperienza.

    Questo lo specifico per evitare interventi (giusti) sul fatto che il forum non sia una scuola.

    Nei miei test posso definire dei parametri di bontà come, ad esempio, la presenza di una determinata sequenza per effettuare il calcolo del fitness... ma con quale logica devo rapportare un problema iniziale alla richiesta di tali parametri?
    Come posso trasformare le eventuali soluzioni in codice?

    In una coltura generata randomicamente che evolve ed effettua cross-over sulla base del valore di fitness degli individui come faccio (in linea teorica) ad individuare una soluzione accettabile al problema posto prima che la quest'ultima sia superata dalla prossima generazione e che la coltura converga magari verso una soluzione di qualità inferiore?

    Mi sto un po' scoraggiando perché l'argomento è particolarmente impegnativo, il mio livello di conoscenza in merito basso e di conseguenza anche la mia capacità di effettuare domande ne risente.

    codifichi in binario il valore delle variabili nei geni
    Non ho capito cosa intendi...

    Non voglio richiedere sforzi particolari e gratuiti, credevo che nel suo concetto di base l'applicazione reale fosse più facilmente esplicabile.

    Mi viene quasi da scusarmi per aver aperto il thread...

  8. #8
    L'avatar di +m+
    +m+
    +m+ non è in linea Scribacchino
    Post
    920
    Quote Originariamente inviato da Dev-01 Visualizza il messaggio
    Non è che lavoro alla cieca... è che ho iniziato ad occuparmene da tre giorni.
    Vabbè dai alla ciechissima
    In una coltura generata randomicamente che evolve ed effettua cross-over sulla base del valore di fitness degli individui come faccio (in linea teorica) ad individuare una soluzione accettabile al problema posto prima che la quest'ultima sia superata dalla prossima generazione e che la coltura converga magari verso una soluzione di qualità inferiore?
    Mah vedo un pochino di idee confuse.
    1) non converge affatto

    Mi sto un po' scoraggiando perché l'argomento è particolarmente impegnativo, il mio livello di conoscenza in merito basso e di conseguenza anche la mia capacità di effettuare domande ne risente.
    Un pochino sì, ma non disperare, dopo 3 anni di uso quotidiano di AG (O GA se vuoi faaa l'ammerikano) tutto sarà più facile.

    Visto che vogliamo partire da cose semplici, niente codifica dinamica dei parametri (aka zoom)
    ecco un vecchio genetico accademico-dimostrativo in pascal (object)
    codice:
    unit Threads;
    
    interface
    
    uses
      Dialogs,Main,ComCtrls,Classes, Graphics, ExtCtrls,stdctrls,sysUtils,Math;
    
    type
    	MIO = integer;
    
    const
    	MAXPOP=100;
    	MAXLENGTH=300;
    
    type
    
    { TFranzThread }
    
    
      TFranzThread = class(TThread)
      private
    
      	FListBox:TListBox;			// listbox a scopo debug
    	FSeed:integer;				// seme random
       FPM:double; 				// mutazione
    	FPC:double; 				//probabilità crossover
       FChoice:integer; 	   		//funzione
    
       FMaxCicli:integer; 			//max num cicli
       FEpoca:integer; 			// cicli per output
       FObjectiveMin: integer; 	// indice individuo migliore
    	FSoluzioneMigliore:string;	// soluzione migliore in stringa
    
    	FProgressBarbestsol:TProgressBar;
       FProgressBarFomin:TProgressBar;
       Flblbestsol:TLabel;
       FlblFomin:TLabel;
    	FIterazione: integer;
       Fbestsol: double;
       FFomin: double;
       FFomax: double;
    
    
    	FOutputSuFile:boolean; 		// se true output su FFileOutput
       FNomeFileOutput:string; 	// nome file di output
       FHandleFileOutput:textfile;
        procedure doMostraMinimo;
    
    
      protected
        procedure Execute; override;
        procedure MostraMinimo(iterazione:integer;var bestsol:double;var fomin:double;var fomax:double;individuoMigliore:string);
      public
        constructor Create(outputSuFile:boolean;nomeFile:string;choice:integer;var lblbestsol:TLabel;var lblFomin:Tlabel;var lbListBox:TListBox;var pgrProgressbestsol:TProgressBar;var pgrProgressFomin:TProgressBar;seed:integer;mutazione:double;crossover:double;maxcicli:integer;epoca:integer);
      end;
    
    
    
      TMINGenetico = class(TFranzThread)
      private
    	numvar,bitvar,maxlen:longint;
    	deno:longint;
    
    	pop:			array [0..MAXPOP,0..MAXLENGTH] of MIO;
    	fitness:		array [0..MAXPOP] of double;
       incfitness:		array [0..MAXPOP] of double;
       bestsol:double;
    
    
    protected
      	procedure Execute; override;
      	function  getrandom(var x:longint;max:double):double;
    	function gauss(var x:longint):double;
    	function conver(k:integer;riga:integer):double;
    	function clcobj(line:integer):double;
    	procedure makeselection;
    	procedure compact(var vetcomp:array of MIO;canc:integer;cicle:integer);
    	procedure makexover;
    	procedure makemutation;
    	procedure Minimizza;
      end;
    
    
    implementation
    
    
    
    constructor TFranzThread.Create(outputSuFile:boolean;nomeFile:string;choice:integer;var lblbestsol:TLabel;var lblFomin:Tlabel;var lbListBox:TListBox;var pgrProgressbestsol:TProgressBar;var pgrProgressFomin:TProgressBar;seed:integer;mutazione:double;crossover:double;maxcicli:integer;epoca:integer);
    begin
    	FOutputSuFile:=outputsufile;
       FNomeFileOutput:=nomeFile;
    	FListBox:=lbListBox;
       FProgressBarbestsol:=pgrProgressbestsol;
    	FProgressBarFomin:=pgrProgressFomin;
    	Flblbestsol:=lblbestsol;
       FlblFomin:=lblFomin;
    	FSeed:=seed;
       FPM:=mutazione;
       FMaxCicli:=maxcicli;
       FEpoca:=epoca;
    	FPC:=crossover;
       FChoice:=choice;
       FObjectiveMin:=0;
      	FreeOnTerminate := True;
      inherited Create(False);
    end;
    
    procedure TFranzThread.DoMostraMinimo;
    begin
         FLblbestsol.caption:='IT '+inttostr(fiterazione)+'  '+format('%10.6f',[fbestsol]);
         FLblFomin.caption  :=FSoluzioneMigliore;
    
         if FBestSol<>0 then
         	FProgressbarFomin.position:=trunc((1.0/(FBestSol))*Ffomin);
         FProgressbarbestsol.position:=trunc(10000*FBestSol);
    
         if FOutputSuFile then
    		writeln(FHandleFileOutput,Format('Iterazione |%06d|  %s',[fiterazione,FsoluzioneMigliore]));
    end;
    
    
    procedure TFranzThread.MostraMinimo(iterazione:integer;var bestsol:double;var fomin:double;var fomax:double;individuoMigliore:string);
    begin
    	FSoluzioneMigliore:=individuoMigliore;
    	FIterazione:=iterazione;
       Fbestsol:=bestsol;
       FFomin:=Fomin;
       FFomax:=fomax;
      	Synchronize(DoMostraMinimo);
    end;
    
    
    procedure TFranzThread.Execute;
    begin
    end;
    
    
    
    
    procedure TMinGENETICO.Execute;
    begin
     	Minimizza;
    end;
    
    
    function  TMINGenetico.getrandom(var x:longint;max:double):double;
    var
    	y:longint;
       yfl:double;
    
    begin
    	y	:= x * 1220703125;
    
    	if (y<0) then
       begin
    		y	:=y+2147483647;
    		INC(y);
    	end;
    	x:=y;
    
    	yfl	 :=y;
    	yfl	:=yfl*0.4656613E-9;
    
       if max=1 then
           getrandom:=yfl
       else
       	getrandom:=y mod (trunc(max+1));
    end;
    
    // generiamo una v.a. distribuita normalmente (teorema limite centrale)
    // con media 3 , var. e sigma = 1
    
    // prendo media 3 e non 6 per limitare i rischi di
    // grandi valori negativi che potrebbero creare problemi nella
    // minimizzazione
    
    function TMINGenetico.gauss(var x:longint):double;
    var	somma:double;
    		i:integer;
    begin
    	somma:=0;
       for i:=1 to 12 do
       	somma:=somma+getrandom(x,1);
       result:=somma-3.0;
    end;
    
    
    // converte la K-esima variabile dell'individuo riga
    
    function TMINGenetico.conver(k:integer;riga:integer):double;
    var	j:integer;
    		cont:double;
    begin
    	cont:=0;
    	 for j:=0 to bitvar-1 do
        begin
      		//cont:=cont+power(2,bitvar-1-j)*pop[riga,k*bitvar+j];
      		cont:=cont+(1 shl (bitvar-1-j))*pop[riga,k*bitvar+j];
      	end;
      //cont:=(cont-power(2,bitvar-1))/deno;
      cont:=(cont-(1 shl (bitvar-1)))/deno;
     result:=cont;
    
    end;
    
    
    // nota: niente fronzoli, niente puntatori a funzioni, etc.
    
    function TMINGenetico.clcobj(line:integer):double;
    var	val,val1,x1,x2,x3:double;
    		i:integer;
    begin
    
    	VAL:=0;
       val1:=0;
    
     case (Fchoice) of
     1:	begin
    			for i:=0 to numvar-1 do
    			begin
           		val1:=conver(i,line);
    				val:=val+val1*val1;
    			end;
         	end;
    
      2:	begin
    			x1:=conver(0,line);
    			x2:=conver(1,line);
    			val:=100*(power((x1*x1)-x2,2)+power((1-x1),2));  // usato volutamente power() e non la moltiplicazione
               												 // per rallentare l'esecuzione
           end;
    
     3:	begin
    		for i:=0 to numvar-1 do
    			val:=val+trunc(conver(i,line));
           end;
     4:	begin
    
    			for i:=0 to numvar-1 do
    			begin
    		  		val1:=conver(i,line);
             		val:=val+i*val1*val1*val1*val1;
    			end;
    			val:=val+gauss(Fseed);
    
        	end;
     5:	begin
      			x1:=conver(0,line);
           	x2:=conver(1,line);
           	x3:=conver(2,line);
    
           	val:=abs(x1*18+x2*48+x3*42-600);
    			if x1<=0 then val:=val+600;
           	if x2<=0 then val:=val+600;
    			if x3<=0 then val:=val+600;
    
           	if (x1+x2+x3)<>20 then val:=val+600;
    		end;
       end;
    
     result:=val;
    end;
    
    
    // riproduzione
    
    procedure TMINGenetico.makeselection;
    var
    	i,k,linecopy:integer;
       pos:double;
    	popsel:array[0..MAXPOP,0..MAXLENGTH] of MIO;
    begin
    
    // metto in incfitness[] la fitness[] incrementale (somma da 0 a i delle fitness[i])
    
    	incfitness[0]:=fitness[0];
    	for k:=1 to MAXPOP-1 do
       begin
    		incfitness[k]:=incfitness[k-1]+fitness[k];
       end;
    
    
    	for k:=0 to MAXPOP-1 do
    	begin
    
    // genero numero casuale compreso tra 1 e il valore della fitness cumulata
     		pos:=(getrandom(Fseed,trunc(incfitness[MAXPOP-1])));
    
    // trova l'indice linecopy (all'interno della fitness cumulata) che e' >= di pos
    		linecopy:=0;
    		while(incfitness[linecopy]<pos) do
    			INC(linecopy);
    
    		for i:=0 to maxlen-1 do
    			popsel[k,i]:=pop[linecopy,i];
    	end;
    
    	for i:=0 to MAXPOP-1 do
    		for k:=0 to maxlen-1 do
    			pop[i,k]:=popsel[i,k];
    
    end;
    
    procedure TMINGenetico.compact(var vetcomp:array of MIO;canc:integer;cicle:integer);
    var	ind,ind1:integer;
    begin
    	ind:=0;
    
    	while(vetcomp[ind]<>canc) do
    		INC(ind);
    
    	for ind1:=ind to cicle-1 do
    		vetcomp[ind1]:=vetcomp[ind1+1];
    end;
    
    procedure TMINGenetico.makexover;
    var
    	num:array[0..MAXPOP] of MIO; // MIO
       couple:array[0..MAXPOP] of integer;
       temp:MIO; //MIO
       i,j,xcut,temp1:integer;
    
    begin
    
    	temp1:=MAXPOP;
    
    // inizializza vettore num[] a 0,1,2,...MAXPOP-1
    
    	for i:=0 to MAXPOP-1 do
    		num[i]:=i;
    
    // genera le coppie candidate per il crossover
    
    	for i:=0 to MAXPOP-1 do
    	begin
    		couple[i]:=num[trunc(getrandom(Fseed,temp1-1))];
    		compact(num,couple[i],temp1);
    		DEC(temp1);
    	end;
    
    	i:=0;
    	while (i<MAXPOP) do
    	//for(i=0;i<MAXPOP;i+=2)
    	begin
    		if(getrandom(Fseed,1)<=Fpc) then
    		begin
    			xcut:=trunc(getrandom(Fseed,maxlen-1));
    
    			for j:=xcut to maxlen-1 do
    			begin
    				temp				:= pop[couple[i],j];
    				pop[couple[i],j]	:= pop[couple[i+1],j];
    				pop[couple[i+1],j]	:= temp;
    			end;
    		end;
    		i:=i+2;
    	end;
    end;
    
    procedure TMINGenetico.makemutation;
    var i,j:integer;
    	test:double;
    begin
    
    	for i:=0 to MAXPOP-1 do
    		for j:=0 to maxlen-1 do
    		begin
           	test:=Fpm;
    			if (getrandom(Fseed,1)<=test) then
               begin
    	   			//pop[i,j] := not pop[i,j];
    				if pop[i,j]=1 then pop[i,j]:=0 else pop[i,j]:=1; // nota: i numeri in Pascal sono SIGNED.
                   												 // questo rallenta, ma rende sicuri
           	end;
    		end;
    end;
    
    procedure TMINGenetico.Minimizza;
    var	n,i,j,k:integer;
    	objective:array [0..MAXPOP] of double;
       fomin,fomax:double;
       numit:integer;
       individuoSoluzioneMigliore:integer;
       soluzioneMigliore:string;
       variabile:double;
    
    begin
    	if FOutputSuFile then
       begin
           try
    			AssignFile(FHandleFileOutput,FNomeFileOutput);
       		if FileExists(FNomeFIleOutput) then
               	append(FHandleFileOutput)
       		else
               	Rewrite(FHandleFileOutput);
           except
           	FOutputSuFile:=false;
           end;
    
       end;
    
    
    
    
       case Fchoice of
      	1:	begin
      			numvar:=3;
    			bitvar:=10;
           	deno:=100;
      		end;
     	2:	begin
       		numvar:=2;
    			bitvar:=12;
    			deno:=1000;
       	end;
     	3:	begin
     			numvar:=5;
    			bitvar:=10;
           	deno:=100;
     		end;
     	4:	begin
     			numvar:=30;
    			bitvar:=8;
           	deno:=100;
    		end;
      5:	begin
      			numvar:=3;
    			bitvar:=6;
    		  	deno:=1;
       	end;
      end;
    
       if FOutputSuFile then
    		writeln(FHandleFileOutput,Format('Funzione %d  Iterazioni  %06d  Mutazione %6.3f  Xver %6.3f seed  %d',[Fchoice,FMaxCicli,FPM,FPC,FSeed]));
    
       maxlen:=numvar*bitvar;
    
    	for i:=0 to MAXPOP-1 do
    		for j:=0 to maxlen-1 do
    			pop[i,j]:=trunc(getrandom(fseed,1)+0.5);
    
    
    	fomin:=0;
       fomax:=0;
    	bestsol:=10000000;
    
    	for numit:=0 to Fmaxcicli do
    	begin
        	if Terminated then
           begin
              if FOutputSuFile then closefile(FHandleFileOutput);
    			exit;
    		end;
    
           individuoSoluzioneMigliore:=-1;
          	for n:=0 to MAXPOP-1 do
    		begin
    // calcola funzioni obiettivo e le mette in objective[]
    			objective[n]:=clcobj(n);
    
    
    // setta fomin e fomax al min,max delle funzioni obiettivo della popolazione
    			if (objective[n]<fomin) OR (n=0) then
       			fomin:=objective[n];
    
    			if (objective[n]>fomax) OR (n=0) then
    				fomax:=objective[n];
    
               if objective[n]<bestsol then
               begin
               	bestsol:=objective[n];
                   individuosoluzionemigliore:=n;
               end;
    
    
           end;
    
    // test ad ogni generazione (anche se non Epoca). Usato per il debug
    
           if individuoSoluzioneMigliore>-1 then
           	begin
               	soluzioneMigliore:='';
            		for k:=0 to numvar-1 do
               		begin
    		  				variabile:=conver(k,individuoSoluzioneMigliore);
                   		soluzioneMigliore:=SOLUZIONemigliore+ format('%8.3f|',[variabile]);
    					end;
               		soluzioneMigliore:=format('%10.6f | %s',[bestsol,soluzioneMigliore]);
           	end;
    
    
    // ora di collezionare output?
    
           if (numit mod Fepoca)=0 then
           	MostraMinimo(numit,bestsol,fomin,fomax,soluzioneMigliore);
    
    // calcola fitness con metodo silly (niente window o sigma scaling)
    		for n:=0 to MAXPOP-1 do
    		begin
    	 		fitness[n]:=fomax-objective[n];
           end;
    
    // operatori genetici
    
    	   	makeselection;
    		makexover;
    	   	makemutation;
    
    // abbiamo una soluzione migliore? Si' aggiorna bestsol (nota:sarebbe bestmin...)
    
    	end;
    
       if FOutputSuFile then
       	closefile(FHandleFileOutput);
    end;
    
    
    end.

    Non ho capito cosa intendi...

    Non voglio richiedere sforzi particolari e gratuiti, credevo che nel suo concetto di base l'applicazione reale fosse più facilmente esplicabile.

    Mi viene quasi da scusarmi per aver aperto il thread...
    Bhè guarda che è come demoralizzarsi dopo 3 giorni di iscrizione a medicina

    La codifica banale la vedi sopra: ogni allele è un bit del genoma; ogni variabile continua la trasformi in discreta, col metodo più facile (potenze di 2).
    Questo è l'esempio più scemo: semplicemente sommi le potenze di due (i vari bit )per la popolazione, e sommi (in sostanza la convoluzione)

    codice:
    	cont:=0;
    	 for j:=0 to bitvar-1 do
        begin
      		//cont:=cont+power(2,bitvar-1-j)*pop[riga,k*bitvar+j];
      		cont:=cont+(1 shl (bitvar-1-j))*pop[riga,k*bitvar+j];
      	end;
      //cont:=(cont-power(2,bitvar-1))/deno;
      cont:=(cont-(1 shl (bitvar-1)))/deno;
     result:=cont;
    Questo approccio ha un caterva di problemi, è solo per didattica, ma l'idea è quella.

    Cosa ti turba?

  9. #9
    L'avatar di +m+
    +m+
    +m+ non è in linea Scribacchino
    Post
    920
    Riguardo agli utilizzi concreti, si tratta di ottimizzazione euristica.
    I problemi "reali" non vengono affrontati facilmente con i metodi derivativi (a discesa del gradiente, più o meno evoluti etc), perchè le funzioni non sono derivabili, e manco differenziabili spesso, e addirittura sono affetti da "rumore di fondo", anche casuale.

    Un metodo classico per trovare il minimo che so della funzione f=x^2*sin(y), come si insegna al liceo, è del tutto inutile nella "vita reale" dove la f vale magari f=x^2*sin(y)+random(0,1), con random... valore casuale.

    Come fai a trovare un buon minimo (non IL minimo) di una funzione difficile? A tentativi.

    Con metodi del tutto random (monte carlo, a casaccio), più o meno furbi (simulated annilhing, dove cerchi di "saltar fuori" dai minimi locali in modo simile a quello che accade in fisica) o coi genetici (o mille altri approcci)

    Nell'ultimo caso si immagina che le variabili, rappresentate dai geni, "magicamente" si modificheranno fino a giungere a un buon risultato di fitness (cosa che in generale non accade).

    Diciamo che è un andare a casaccio si spera... un po' più mirato.
    In realtà non funziona, va bene per problemi "davvero" difficili dove non si sa dove sbattere la testa e ci si accontenta di un risultato meglio... di niente.

  10. #10
    Dev-01 non è in linea Scolaretto
    Post
    271
    Ciao +m+,

    mi stai dedicando parecchio tempo, grazie.

    Da quello che mi pare di aver capito, il problema è noto (tipo il "problema del sacco") e si tratta di trovare (a "circa" tentativi) i parametri in ingresso di una funzione (che poi è quella di fitness) che consentano di riuscire a riempire il suddetto sacco il più possibile utilizzando le varie combinazioni di oggetti disponibili...

    Quindi si potrebbe dichiarare anche un range di accettabilità? Del tipo +-3(%)?

    Potrei ad esempio (e tanto per capirci) definire una soluzione pari a 1 miliardo ed impostare l'algoritmo per sapere fra i numeri primi quali posso addizionare senza ripetizioni in modo da avvicinarmi il più possibile alla cifra stabilita e possibilmente entro un determinato range?

    ----

    Vabbè dai alla ciechissima
    Direi proprio di si...

    1) non converge affatto
    Leggevo di convergenza prematura degli "individui" che, dopo x generazioni, cominciavano a somigliarsi... (che poi è la causa dell'utilizzo degli algoritmi di mutazione).

    ----

    Consentimi, ti prego, un'altra domanda: se noi selezioniamo la soluzione che maggiormente si appresta alla migliore, perchè si parla di minimi e di minimi locali? E locali in che senso?

    Leggevo inoltre che, per un migliore funzionamento dell'algoritmo, è meglio che individui con valore di fitness simile (in particolare quelli con valori più alti) siano situati vicini tra loro... è per via del crossover? Considerando il solo valore di fitness la interpreto come una affermazione non tanto sensata, o almeno non indispensabile...

    Ti devo alcune pizze...

    E grazie 1000 per l'apprezzatissimo codice.

+ Rispondi al Thread
Pagina 1 di 2 12 ultimoultimo

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi