-
Notifications
You must be signed in to change notification settings - Fork 0
/
Genetic.py
101 lines (82 loc) · 4.04 KB
/
Genetic.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import random
from Chromosome import TourManager, Tour
from Population import Population
class Genetic:
def __init__(self, tourmanager, num_generations):
self.tourmanager = tourmanager
self.num_generations = num_generations
self.mutationRate = 0.01
self.tournamentSize = 5
self.elitism = True
def evolveCostPopulation(self, pop: Population):
best_population = self.NaturalCostSelection(pop)
for i in range(0, self.num_generations):
best_population = self.NaturalCostSelection(best_population)
return best_population
def NaturalCostSelection(self, pop: Population):
newPopulation = Population(self.tourmanager, pop.populationSize(), False)
elitismOffset = 0
if self.elitism:
newPopulation.saveTour(0, pop.getFittestCost())
elitismOffset = 1
for i in range(elitismOffset, newPopulation.populationSize()):
parent1 = self.tournamentCostSelection(pop)
parent2 = self.tournamentCostSelection(pop)
offspring = self.crossover(parent1, parent2)
newPopulation.saveTour(i, offspring)
for i in range(elitismOffset, newPopulation.populationSize()):
self.mutate(newPopulation.getTour(i))
return newPopulation
def evolveCoorDistancePopulation(self, pop: Population):
best_population = self.NaturalCoorDistanceSelection(pop)
for i in range(0, self.num_generations):
best_population = self.NaturalCoorDistanceSelection(best_population)
return best_population
def NaturalCoorDistanceSelection(self, pop: Population):
newPopulation = Population(self.tourmanager, pop.populationSize(), False)
elitismOffset = 0
if self.elitism:
newPopulation.saveTour(0, pop.getFittestCoorDistance())
elitismOffset = 1
for i in range(elitismOffset, newPopulation.populationSize()):
parent1 = self.tournamentCoorDistanceSelection(pop)
parent2 = self.tournamentCoorDistanceSelection(pop)
offspring = self.crossover(parent1, parent2)
newPopulation.saveTour(i, offspring)
for i in range(elitismOffset, newPopulation.populationSize()):
self.mutate(newPopulation.getTour(i))
return newPopulation
def crossover(self, parent1, parent2):
offspring = Tour(self.tourmanager)
startPos, endPos = sorted(random.sample(range(parent1.tour_size()), 2))
for i in range(startPos, endPos):
offspring.set_city(i, parent1.get_city(i))
for i in range(0, parent2.tour_size()):
if not offspring.contains_city(parent2.get_city(i)):
for j in range(0, offspring.tour_size()):
if offspring.get_city(j) == None:
offspring.set_city(j, parent2.get_city(i))
break
return offspring
def mutate(self, tour):
for tourPos1 in range(0, tour.tour_size()):
if random.random() < self.mutationRate:
tourPos2 = int(tour.tour_size() * random.random())
city1 = tour.get_city(tourPos1)
city2 = tour.get_city(tourPos2)
tour.set_city(tourPos2, city1)
tour.set_city(tourPos1, city2)
def tournamentCostSelection(self, pop : Population):
tournament = Population(self.tourmanager, self.tournamentSize, False)
for i in range (0, self.tournamentSize):
randomId = int(random.random() * pop.populationSize())
tournament.saveTour(i, pop.getTour(randomId))
fittest = tournament.getFittestCost()
return fittest
def tournamentCoorDistanceSelection(self, pop: Population):
tournament = Population(self.tourmanager, self.tournamentSize, False)
for i in range(0, self.tournamentSize):
randomId = int(random.random() * pop.populationSize())
tournament.saveTour(i, pop.getTour(randomId))
fittest = tournament.getFittestCoorDistance()
return fittest