2.8 KiB
Podprojekt: algorytm genetyczny
Jakub Damiński
Opis problemu
Metodą uczenia, którą postanowiłem zaimplementować w projekcie był algorytm genetyczny. Zastosowalem go, by znaleźć najszybszą ścieżkę, którą może podążyć wózek widłowy pomiędzy paczkami, by przejechać w sumie jak najkrótszy dystans.
Metoda
Pierwszym krokiem jest zbudowanie grafu z wagami w którym wierzchołkami są paczki, regały na które te paczki mają trafić oraz punkt startowy wózka, a wagi krawędzi to odległości między nimi. Ponieważ środowisko opiera się na 2-wymiarowej powierzchni, gdzie nie ma odizolowanych pól jest to graf pełny. Graf zapisany jest w 2-wymiarowej tablicy.
Ponieważ wózek musi odwiedzić wszystkie paczki każde rozwiązanie tego problemu będzie permutacja zbioru tych paczek, przedstawiający, które paczki po kolei powinien wózek odwiedzić. Wartościowość takiego rozwiązania jest weryfikowana poprzez zsumowanie odległości jakie wózek musi przebyć do paczki oraz od paczki do jej wyznaczonego regału.
Wykorzystując algorytm genetyczny sprawimy, że spośród losowych permotacji zaczną wyłaniać się tej najbardziej efektywne, czyli te o najkrótszej ścieżce.
Zasada działania
Pierwszym krokiem jest zapełnienie populacji losowymi permutacjiami. Następnie wykonuje się liczba iteracji w których najlepsze osobniki krzyżują się ze sobą tworzyć nowe permutacje wymianiając między sobą losową ilość elementów
def crossover(a, b):
new_a = copy.deepcopy(a)
new_b = copy.deepcopy(b)
for i in range(floor(len(a) / 2)):
rel = randrange(len(a))
tmp_a = new_a[rel]
tmp_b = new_b[rel]
if tmp_a == tmp_b:
continue
new_a[new_a.index(tmp_b)] = tmp_a
new_b[new_b.index(tmp_a)] = tmp_b
new_a[rel] = tmp_b
new_b[rel] = tmp_a
return new_a, new_b
Nowo stworzone osobniki mają następnie szansę na mutacje, która polega na zamienieniu dwóch losowych elementów ze sobą
def mutate(route):
new_route = copy.deepcopy(route)
for i in range(len(route) - 1):
if random() < mutation_probability:
tmp = new_route[i]
new_route[i] = new_route[i + 1]
new_route[i + 1] = tmp
return new_route
Następnym krokiem jest dodanie do populacji najlepszych osobników z poprzedniej populacji
for j in range(0, num_of_surviving):
new_population.append(population[scores[j][0]])
Po wykonaniu tych kroków do nowej populacji dodawane są zupelnie nowe soobniki by osiągną maksymalną ilość populacji
for j in range(max_population - (num_of_surviving + num_of_couples)):
new_population.append(create_new_route(packages))
Na koniec iteracji wszystkie permutacje są oceniane na podstawie tego ile wózkowi zajęło by przejechanie całej trasy