-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgenetic_operators.py
More file actions
97 lines (75 loc) · 3.1 KB
/
genetic_operators.py
File metadata and controls
97 lines (75 loc) · 3.1 KB
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
"""
Genetic Operators Module
-----------------------
Implements crossover and mutation operations for the genetic algorithm.
"""
import random
def breed(parent1, parent2):
"""
Performs ordered crossover between two parents to create a child individual.
This ensures that each city appears exactly once in the child route.
:param parent1: The first parent individual.
:param parent2: The second parent individual.
:return: The child individual created through crossover.
"""
child = []
childP1 = []
childP2 = []
geneA = int(random.random() * len(parent1))
geneB = int(random.random() * len(parent1))
startGene = min(geneA, geneB)
endGene = max(geneA, geneB)
# Copy a segment from parent1
for i in range(startGene, endGene):
childP1.append(parent1[i])
# Fill remaining positions with cities from parent2 (maintaining order)
childP2 = [item for item in parent2 if item not in childP1]
child = childP1 + childP2
return child
def breedPopulation(matingpool, eliteSize):
"""
Performs breeding (crossover) among individuals in the mating pool to create
a new generation.
:param matingpool: The pool of individuals selected for breeding.
:param eliteSize: The number of top individuals to preserve as elites.
:return: The new generation of individuals created through breeding.
"""
children = []
length = len(matingpool) - eliteSize
pool = random.sample(matingpool, len(matingpool))
# Preserve elite individuals
for i in range(0, eliteSize):
children.append(matingpool[i])
# Create offspring through crossover
for i in range(0, length):
child = breed(pool[i], pool[len(matingpool) - i - 1])
children.append(child)
return children
def mutate(individual, mutationRate):
"""
Applies swap mutation to an individual by swapping cities with a certain probability.
This introduces genetic diversity and helps avoid local optima.
:param individual: The individual (route) to be mutated.
:param mutationRate: The probability of mutation for each city in the individual.
:return: The mutated individual.
"""
for swapped in range(len(individual)):
if random.random() < mutationRate:
swapWith = int(random.random() * len(individual))
city1 = individual[swapped]
city2 = individual[swapWith]
individual[swapped] = city2
individual[swapWith] = city1
return individual
def mutatePopulation(population, mutationRate):
"""
Applies mutation to a population by mutating each individual in the population.
:param population: The population of individuals (routes) to be mutated.
:param mutationRate: The probability of mutation for each city in an individual.
:return: The mutated population.
"""
mutatedPopulation = []
for i in range(0, len(population)):
mutatedIndividual = mutate(population[i], mutationRate)
mutatedPopulation.append(mutatedIndividual)
return mutatedPopulation