99 lines
3.1 KiB
Python
Executable File
99 lines
3.1 KiB
Python
Executable File
import numpy as np
|
|
from random import randrange, random
|
|
from math import floor
|
|
import copy
|
|
|
|
num_of_surviving = 6
|
|
num_of_couples = 8
|
|
mutation_probability = 0.07
|
|
max_population = 20
|
|
iterations = 50
|
|
|
|
# creates new random solution to add to population
|
|
def create_new_route(points):
|
|
route = np.random.permutation(points)
|
|
route = [x + 1 for x in route]
|
|
return route
|
|
|
|
# creates initian population
|
|
def create_population(points):
|
|
population = []
|
|
for i in range(max_population):
|
|
population.append(create_new_route(points))
|
|
return population
|
|
|
|
# gives score to a solution based on lenght
|
|
def score_route(graph_map, route):
|
|
score = graph_map[0][route[0]]
|
|
for i in range(len(route) - 2):
|
|
rack = len(route) + route[0]
|
|
score = score + graph_map[rack][route[i + 1]]
|
|
score = score + graph_map[route[i + 1]][route[i + 2]]
|
|
return score
|
|
|
|
# scores every solution in population
|
|
def score_all(graph_map, population):
|
|
scores = []
|
|
for i in range(len(population)):
|
|
tmp = [i, score_route(graph_map, population[i])]
|
|
scores.append(tmp)
|
|
return scores
|
|
|
|
# designed to create new population by mixing steps between most succesfull solutions
|
|
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
|
|
|
|
# adds randomness to newly created solutions
|
|
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
|
|
|
|
# main function that iterate population until the best solutions emerge
|
|
def genetic_trace_route(graph_map, packages):
|
|
population = create_population(packages)
|
|
for i in range(iterations):
|
|
new_population = []
|
|
scores = score_all(graph_map, population)
|
|
scores.sort(key=lambda x: x[1])
|
|
# breeding
|
|
for j in range(0, num_of_couples, 2):
|
|
a, b = crossover(population[scores[j][0]], population[scores[j+1][0]])
|
|
new_population.append(a)
|
|
new_population.append(b)
|
|
# mutations
|
|
for j in range(len(new_population)):
|
|
mutate(new_population[j])
|
|
# survival
|
|
for j in range(0, num_of_surviving):
|
|
new_population.append(population[scores[j][0]])
|
|
# random new
|
|
for j in range(max_population - (num_of_surviving + num_of_couples)):
|
|
new_population.append(create_new_route(packages))
|
|
population.clear()
|
|
population = copy.deepcopy(new_population)
|
|
scores = score_all(graph_map, population)
|
|
scores.sort(key=lambda x: x[1])
|
|
# print("Best route of all population in iteration " + str(i + 1))
|
|
# print(scores[0][1])
|
|
|
|
scores = score_all(graph_map, population)
|
|
scores.sort(key=lambda x: x[1])
|
|
return population[scores[0][0]]
|