[Algoritmi] Simulated Annealing

[mari88]

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?

[mari88]

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.

[mari88]

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

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)

[mari88]

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

Codice:

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.

[mari88]

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.

[mari88]

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