To tylko jedna z 3 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Inteligencja Obliczeniowa
Sprawozdanie nr 7
Student: Katarzyna Nidecka
Kierunek: Informatyka i ekonometria
Rok: 3
Grupa laboratoryjna: 3
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 Inicjalizacja(int rozmiar_populacji)
{ List result = new List(); int[] zajete = new int[ile_miast]; int j; for (int i = 0; i
(…)
…] = rnd.Next(ile_miast); zajete[result[i].Trasa[0]] = 1; j = 1; while (j < ile_miast) { result[i].Trasa[j] = 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. Krzyżówki kończą się po otrzymaniu wyznaczonej populacji potomków. Dla każdego chromosomu dziecka sprawdzamy prawdopodobieństwo mutacji oraz inwersji. Jeżeli dochodzi do mutacji to dwa losowe genotypy…
… przystosowania i wyselekcjonowana zostaje ograniczona grupa stanowiąca nową populacje. Najmocniejszy chromosom z nowej populacji zostaje porównany z najmocniejszym chromosomem otrzymanym do tej pory (podczas badań). Jeśli nowy chromosom jest lepiej przystosowany zostaje zapisany w miejsce starego. Program przechodzi kolejnej iteracji i następuje ponowna reprodukcja. Program kończy działanie jeśli osiągnięta…
... zobacz całą notatkę
Komentarze użytkowników (0)