[Algoritmi] Simulated Annealing

[asarom]

Ciao a tutti, sono nuova del forum e ho bisogno di del vostro aiuto. Volevo saper se riuscite a darmi una mano con un elaborato da svolgere in matlab con algoritmi genetici e simulated annealing.
Il problema riguarda una ditta che ha 15 rappresentanti e ad ognuno dei quali devo assegnare un area geografica (anche le aree geografiche sono 15); L'assegnazione di un rappresentante ad una specifica area geografica comporta un costo. Noto il costo C(rj,ai) che la ditta deve sostenere affinchè il rappresentante j possa occuparsi dell'area geografica ai, la ditta è interessata a minimizzare il costo totale delle associazioni rappresentante-area. Sapete darmi aiutarmi?
Grazie in anticipo

[apatriarca]

Ciao, benvenuta nel forum. Quale difficoltà incontri esattamente? Non sai come applicare gli algoritmi al tuo esempio? Non sai come implementare tali algoritmi in Matlab? Altro?

[asarom]

Non capisco bene questo algoritmo, il funzionamento e quindi non so come applicarlo a tale problema

[apatriarca]

Per prima cosa un piccolo chiarimento. Algoritmi genetici e Simulated Annealing sono due algoritmi diversi, che possono essere tuttavia combinati in diversi modi. Devi cercare di risolvere il problema usando un algoritmo (o entrambi) oppure usare un qualche algoritmo che combina le due strategie? Quali risorse ti sono state fornite per imparare tali algoritmi?

L'idea principale di questi algoritmi consiste nel selezionare delle possibili soluzioni al tuo problema e modificarle/combinarle in modo casuale al fine di arrivare ad una soluzione ottimale. E' quindi necessario definire i seguenti punti:

1. Rappresentazione delle soluzioni. In questo caso puoi usare per esempio una permutazione dei 15 rappresentanti, cioè un array di 15 elementi contenente i numeri da 1 a 15 in ordine casuale.
2. Funzione da ottimizzare. In questo caso è ovviamente il costo totale.
3. Le strategie di mutazione. Puoi per esempio pensare di scambiare due rappresentanti a caso.
4. Combinazione delle soluzioni (crossover). Questo è complicato perché stiamo parlando di permutazioni e non è quindi possibile scambiare semplicemente i valori. Ci dovrei pensare.

A questo punto l'algoritmo consiste principalmente nel selezionare alcune soluzioni, applicare le varie modifiche alle soluzioni e poi ripetere il procedimento. I dettagli dipendono tuttavia dall'esatto algoritmo che vuoi implementare.

[asarom]

si, infatti devo comparare le due euristiche, quindi svolgere il problema con i due algoritmi e tutto ciò fatto in matlab.
Non capisco cosa intendi per

"apatriarca":Quali risorse ti sono state fornite per imparare tali algoritmi?

Questo è lo schema di una slide del prof riguardante l'algoritmo genetico:
-Inizializzazione della popolazione.
-Valutazione della “fitness” della popolazione.
Ripeti
1.Seleziona la sub-popolazione per la riproduzione
2.Ricombina i '’geni'' dei genitori selezionati (Crossover)
3.Muta la popolazione generata in modo random
4.Valuata la “fitness” della nuova popolazione
5.Seleziona i sopravvissuti alla valutazione
Fino a quando la condizione di termine T = vera

mentre per il simulated annealing:
simulated annealing(is, c0, L0)
k=0;
i=is;
ripeti
for l=1 to Lk
j=TM(i);
if f(j)<=f(i) then i=j;
k=k+1;
ricalcola ck;
ricalcola Lk;
until(criterio di fermata)

[asarom]

io per esempio per il simulated annealing ho scritto questo (C è la mia matrice dei costi):

function [CostoAn]=Annealing(C)

k=1;
[P1]=Perturba(C);
c=sum(P1);
CostoAn(k)=c;
Temp=1./[20:49];        %Temperature per le k generazioni
M = 2*ones(1,20);       %Numero di ripetizioni
flag=1;

while(k<20)
    m=0;
    while(m<M(k))
        [P2]=ModPert(C, P1);
        c2=sum(P2);
        delta=c-c2;
        if delta>0
            c=c2;
        else
            if(rand<exp(-delta/Temp(k)))
                c=c2;
            end
        end
        m=m+1;
    end
    k=k+1;
    CostoAn(k)=c;
end
end


%la funzione perturba%

function [P1]=Perturba(C)
k=1;
rap=randperm(15);
ar=randperm(15);
for l=rap
    P1(1, k)=C(l, ar(k));
    k=k+1;
end


%la funzione modpert%

function [P2]=ModPert(C, P1)
l=randi(15);
a=find(P1==max(P1));
P1(1, a)=C(l, a);
P2=P1;
end

ma forse c'è qualcosa che non va bene, cosa ne pensate?

[apatriarca]

Ci sono alcune cose che non capisco del tuo codice (l'ho letto di fretta):
1. Perché accedi a P1 sempre nella forma P1(1, k) invece di scrivere direttamente P1(k)? Qual'è lo scopo del primo indice?
2. Non sono del tutto convinto sulla strategia di modifica adottata. Dovrebbe esserci un qualche tipo di scambio tra due elementi del vettore e invece vedo che assegni un nuovo valore ad un solo elemento del vettore.
3. Arrivi ad una somma di costi minimi, ma ho l'impressione che si sia perso quali sono i rappresentanti e a quali regioni sono associati.

[asarom]

Perché accedi a P1 sempre nella forma P1(1, k) invece di scrivere direttamente P1(k)? Qual'è lo scopo del primo indice?

Accedo con doppio indice perché altrimenti mi rilevava un errore (e non ne capisco il motivo). Lo scopo del primo indice è che ho sempre un vettore 1x15

Non sono del tutto convinto sulla strategia di modifica adottata. Dovrebbe esserci un qualche tipo di scambio tra due elementi del vettore e invece vedo che assegni un nuovo valore ad un solo elemento del vettore.

ma scambiando 2 elementi dello stesso vettore non si ha la stessa somma?

Arrivi ad una somma di costi minimi, ma ho l'impressione che si sia perso quali sono i rappresentanti e a quali regioni sono associati

Questo non so come sistemarlo. Perché non posso assegnare ad aree diverse lo stesso rappresentante. Le regioni ci sono sempre tutte poiché sono rappresentate dalle colonne quindi cambiando l'indice di colonna è una area diversa. Forse per quello accedo a P1 con doppio indice.

Mi sto perdendo

[apatriarca]

Personalmente lo farei nel seguente modo:
1. La soluzione proposta ad ogni iterazione è semplicemente una permutazione di valori a 1 a 15 che chiamo P.
2. Il costo è a questo punto uguale a sum(C(:,P)). Questa scritta significa che fa la somma di un vettore ottenuto da C prendendo per ogni riga, la colonna corrispondente al valore in P.
3. La funzione che modifica la soluzione scambia due valori a caso in P.

[asarom]

non capisco lo scambio di 2 valori in P visto che darebbe la stessa somma, no? forse mi sbaglio. Mi puoi far capire meglio?

[asarom]

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.

[asarom]

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:

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

[asarom]

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

io creo la mia popolazione così:

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

[asarom]

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

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).

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.

[asarom]

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

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