46515

Na tych laboratoriach zapoznawaliśmy się z problemem komiwojażera. Rozwiązywaliśmy problem TSP przy użyciu algorytmu genetycznego. Piszemy program w którym na początku generujemy populację początkową o danym rozmiarze. Chromosomy mają długość genotypu, która odpowiada ilości miast. Genotyp reprezentuje losową kolejność odwiedzonych przez komiwojażera miast.

private List<Chromosom> lnicjalizacja(int rozmiarjjopulacji)

{

List<Chromosom> result = new List<Chromosom>(); int[] zajete = new int[ilejiiast]; int j;

for (int i = 0; i < rozmiar^populacji; i+-+)

{

result.Add(new Chromosom(ile_miast));

for (j = 0; j < ile_miast; j++) { zajete[j] = 0; }

result[i].Trasa[0] = rnd.Next(ile_miast);

zajete[result[i].Trasa[0]] = 1;

j = i;

while (j < ile_miast)

{

result[i].Trasafj] = rnd.Next(ile_miast); if (zajete[result[i].Trasa[j]] == 0) zajete[result[i] .Trasa[j]]=l; j⁺⁺;

}

}

Dokonujemy ewaluacji stworzonej populacji. Wyliczamy długość trasy jaką musi odbyć komiwojażer i zapisujemy to jako wartość fitness. Szukamy najlepszego chromosomu z danej populacji i zapamiętujemy go. Następnie dokonuje się reprodukcja na zasadzie turniejowej lub ruletki. Wybieramy parę rodziców. Potem dochodzi do krzyżowania z pewnym prawdopodobieństwem na zasadzie operatora losowego z uzupełnieniem.