[Algoritmi] Simulated Annealing

[mari88]

a no, scusa...in poche parole P sono le colonne. Ovviamente cambia il costo. Ma quindi avrei solo una funzione?
Ma come creo il primo vettore con cui devo fare lo scambio?prendo direttamente la prima riga? non capisco bene l'inizio

[apatriarca]

Non ho capito a cosa ti riferisci nell'ultimo post. In ogni caso inizializzi lo stato del sistema con randperm e poi ad ogni iterazione ottieni un nuovo stato scegliendo due interi (distinti) con randi e li scambi tra di loro. Dopodiché devi decidere se passare a questa nuova permutazione o rimanere a quella precedente in base alle regole del SA.

[mari88]

ok, grazie; ma con sum(C(:,P)) ho una matrice e non un vettore e invece mi sa che ho bisogno solo di un vettore, no?sbaglio?

[apatriarca]

Sì, scusa. Quella espressione è in effetti sbagliata. Devi usare sub2ind per ottenere gli indici corretti. Qualcosa come la seguente:

Codice:

sum( C( sub2ind(size(C), 1:size(C,1), P) ) )


[mari88]

ok, grazie mille. Sto cercando di apportare questi cambiamenti.
Mentre per l'algoritmo genetico? cosa mi puoi dire?

io creo la mia popolazione così:

Codice:

for j=1:50
    k=1;
    %r=randperm(15)
    for l=randperm(15)
        Popolazione(j, k)=C(l, k);
        k=k+1;
    end
end

ma già forse lì ci sarà qualcosa che non va

[mari88]

Ma come mai non mi risponde più nessuno?ho bisogno di voi!!!

[apatriarca]

Sono semplicemente stato occupato. Non mi è chiaro il significato dell'ultimo codice che hai postato. Che cosa rappresenta esattamente? L'inizializzazione per l'algoritmo genetico?

La problematica più grossa dell'algoritmo genetico è la scelta della strategia per il crossover. In altre situazioni è infatti possibile semplicemente scegliere alcuni valori di uno e dell'altro a caso. In questo caso non è però possibile perché seguendo questa strategia si possono generare soluzioni non valide. Siccome lo stato è una permutazione è necessario fare ricorso ad un metodo che mantenga questa proprietà della soluzione. In questa pagina di Wikipedia trovi questi metodi elencati nella sezione "For ordered chromosomes" (per saperne di più è necessario poi cercarli con google in quanto non ci sono granché dettagli). Ti fornisco un paio di esempi.

Il seguente codice implementa quello che è chiamato partially matched crossover. In questo caso vengono scelti due indici. I valori compresi tra questi due indici saranno uguali al primo cromosoma. Per farlo partiamo dal secondo cromosoma e operiamo degli scambi per ottenere i valori desiderati al centro. Qui trovi una descrizione più lunga

Codice:

function [C] = crossover(A, B)
    C = B; % Partiamo da B
    i = randi(15);
    j = randi(15);
    % scelgo i due valori a caso
    if i > j
        tmp = i
        i = j;
        j = i;
    end
    for k=i:j
        % Scambio i valori in modo che C(k) sia uguale a A(k) in [i, j]
        if C(k) ~= A(k)
            s = find(C == A(k));
            C(s) = C(k);
            C(k) = A(k);
        end
    end
end


In seguito ti posto un esempio del cycle crossover (che trovi descritto per esempio in questa pagina).

Codice:

function [C] = crossover(A, B)
    C = A; % Inizializzo il vettore C in modo che sia uguale ad A
    i = randi(15); % scelgo un elemento da cui partire
    initial = A(i); % memorizzo il valore che mi serve in seguito come condizione di fine
    C(i) = B(i);
    while initial ~= C(i)
        i = find(A == C(i)); % trova la posizione originale del valore sostituito
        C(i) = B(i); % sostuitisci il valore corrispondente trovato in B(i) in quella posizione
    end
end


Non ho testato questi codici (non ho Matlab dove sono in questo momento) e sono principalmente dei punti di partenza. La scelta dell'algoritmo usato può avere effetto sull'efficacia del metodo. Sinceramente non sono molto esperto, avevo visto questi metodi parecchio tempo fa e mai più guardati/usati.

[mari88]

grazie di tutto. Si quel codice era come creavo la mia inizializzazione.

Ancora grazie di tutto, mi sentivo davvero persa....ora va meglio