Untitled
unknown
plain_text
a year ago
13 kB
3
Indexable
Never
import random
import numpy as np
#import visualizer functions for paths and generations
from Visualizer import visualize_path, visualize_generation
#size of the checkerboard
boardsize = 16
#seed (leave empty if you want total randomness)
random.seed()
#start, endpoint and the manhatten distance on the grid
S = (random.randrange(boardsize), random.randrange(boardsize))
E = (random.randrange(boardsize), random.randrange(boardsize))
dist = min((E[0] - S[0])%boardsize, (S[0]-E[0])%boardsize) + min((E[1] - S[1])%boardsize, (S[1]-E[1])%boardsize)
#weights for the fitness function
fit_len = 1 #length
fit_dist = 2 #distance
fit_var = 1 #variation
#parameters for the mutator functions
step = 1 #stepsize
gen_size = 10 #size of generation
add = 1 #adding a character
sub = 1 #subtracting a character
change = 1 #changing a character
change_last = 1 #changing the last character
replace = 1 #replacing less fit paths with the fittest path (path[0])
#set to false if you don't want the visualizations (for debugging)
visualize = True
class Path:
def __init__(self, string_length, existing_string=None):
"""
Initializes a Path object with a random string of moves.
Parameters:
string_length (int): The length of the random string.
existing_string (list): An optional list for an existing string
Attributes:
length (int): The number of moves in the string.
string (list): A list of characters representing moves ('u', 'd', 'l', 'r', 'n').
distance (int): The calculated distance from the starting point to the endpoint.
variation (int): The variation number is the number of character changes in the string.
fitness (int): The fitness value of the path calculated from length, distance and variation.
"""
if existing_string:
self.string = existing_string
self.update(self.string)
else:
self.length = random.randrange(string_length)
self.string = self._random_string(string_length, self.length)
self.distance = self.calc_distance()
self.variation = self.calc_variation()
self.fitness = self.calc_fitness(self.length, self.distance, self.variation)
def _random_string(self, length, num_n):
"""
Generates a random string of moves.
Parameters:
length (int): The desired length of the random string.
num_n (int): The number of 'u', 'd', 'l', 'r', 'n' (move) characters in the string.
The rest of the length gets filled with 'n' (no move) characters.
Returns:
list: A list of characters representing moves ('u', 'd', 'l', 'r', 'n').
"""
characters = 'udlr'
random_string = [random.choice(characters) for _ in range(num_n)]
random_string += ['n'] * (length - num_n)
return random_string
def print(self):
"""
Prints the details of the Path object.
Output:
string: The string of moves.
length: The number of moves in the string.
distance: The calculated distance from the starting point to the endpoint.
fitness: The fitness value of the path calculated from length and distance.
"""
print("string: " + ''.join(self.string))
print("length: " + str(self.length))
print("distance: " + str(self.distance))
print("variation: " + str(self.variation))
print("fitness: " + str(self.fitness))
def calc_length(self):
"""
Calculates the length of the list in a path while ignoring all the 'n' characters.
Parameters:
string (list): A list of characters representing a path.
Returns:
int: The number of moves ('u', 'd', 'l', 'r') in the character list.
"""
return len([char for char in self.string if char != 'n'])
def calc_distance(self):
"""
Calculates the distance from the starting point to the endpoint using the string of moves.
Returns:
int: The calculated distance.
"""
x, y = S
for move in self.string:
if move == "u":
y = (y - 1) % boardsize
elif move == "d":
y = (y + 1) % boardsize
elif move == "l":
x = (x - 1) % boardsize
elif move == "r":
x = (x + 1) % boardsize
return min((E[0] - x) % boardsize, (x - E[0]) % boardsize) + min((E[1] - y) % boardsize, (y - E[1]) % boardsize)
def calc_variation(self):
"""
Calculates the variation in the list of characters for the path.
Returns:
int: The number of character changes in the string.
"""
# Convert the string to a set to get unique characters
variation_count = 0
prev_char = None
for char in self.string:
if char != 'n': # Exclude 'n' (no move) from variation count
if prev_char is not None and char != prev_char:
variation_count += 1
prev_char = char
return variation_count
def calc_fitness(self, length, distance, variation):
"""
Calculates the fitness value based on the path's length and distance.
Parameters:
length (int): The number of moves in the string.
dist (int): The calculated distance from the starting point to the endpoint.
Returns:
int: The fitness value.
"""
return length * fit_len + distance * fit_dist + variation * fit_var
def update(self, new_string):
"""
Recalculates all the fields (distance, fitness, and variation) for the path
whenever the character list (`string`) changes.
"""
self.string = new_string
self.length = self.calc_length()
self.distance = self.calc_distance()
self.variation = self.calc_variation()
self.fitness = self.calc_fitness(self.length, self.distance, self.variation)
class Generation:
def __init__(self, num_paths, existing_paths=None):
"""
Initializes a Generation object with a list of Path objects.
Parameters:
num_paths (int): The number of paths in the generation.
string_length (int): The desired length of the random strings for each path.
existing_paths (list): An optional list of existing Path objects.
Attributes:
paths (list): A list of Path objects representing paths in the generation.
size (int): The number of paths in the generation.
"""
if existing_paths:
self.paths = existing_paths
else:
self.paths = [Path(boardsize) for _ in range(num_paths)]
self.size = num_paths
self.paths.sort(key=lambda x: x.fitness) # Sorting paths based on fitness in ascending order
def print(self):
"""
Prints the details of each Path object in the Generation.
Output:
Details of each Path in the Generation, printed using Path's print method.
"""
for path in self.paths:
path.print()
print()
def mutate_replace(paths):
"""
Randomly replaces a path with the fittest path in the list with a given probability.
Parameters:
paths (list): A list of Path objects representing paths.
Returns:
list: The updated list of Path objects.
"""
curr = np.interp(paths[0].distance, (0, dist), (1, 0.7))
fittest_path = list(paths[0].string)
for path in paths:
if random.random() <= replace*curr:
path.update(fittest_path)
return paths
"""
def mutate_change_last(paths):
""
Randomly changes the last character in the list of letters for each path with a given probability.
Parameters:
paths (list): A list of Path objects representing paths.
Returns:
list: The updated list of Path objects.
""
curr = np.interp(paths[0].distance, (0, dist), (0, 1))
print("change last curr: ", curr)
letters = ['u', 'd', 'l', 'r']
for path in paths:
if random.random() <= change_last*curr:
if path.length > 0:
last_index = path.length - 1
old_char = path.string[last_index]
new_char = random.choice(letters)
while new_char == old_char:
new_char = random.choice(letters)
path.string[last_index] = new_char
path.update(list(path.string))
return paths
"""
def mutate_change(paths):
"""
Randomly changes a character in the list of letters for each path with a given probability.
Parameters:
paths (list): A list of Path objects representing paths.
Returns:
list: The updated list of Path objects.
"""
curr = max(np.interp(paths[0].distance, (0, dist), (0, 0.5)), np.interp(paths[0].variation, (0, boardsize), (0, 0.5)))
print("change curr: ", curr)
letters = ['u', 'd', 'l', 'r']
for path in paths:
for i in range(path.length):
if random.random() <= change*curr:
old_char = path.string[i]
new_char = random.choice(letters)
while new_char == old_char:
new_char = random.choice(letters)
s = list(path.string)
s[i] = new_char
new_path = Path(path.length, s)
if new_path.fitness < path.fitness:
path.update(list(s))
return paths
def mutate_add(paths):
"""
Randomly adds another character to the list of characters in each path with a given probability.
Parameters:
paths (list): A list of Path objects representing paths.
Returns:
list: The updated list of Path objects.
"""
curr = 1-paths[0].length/dist
letters = ['u', 'd', 'l', 'r']
for path in paths:
if path.length < boardsize:
if random.random() <= add*curr:
random_index = random.randint(0, 3)
path.string[path.length] = letters[random_index]
path.update(list(path.string))
return paths
def mutate_sub(paths):
"""
Randomly removes a character from the list of letters for each path with a given probability.
Parameters:
paths (list): A list of Path objects representing paths.
Returns:
list: The updated list of Path objects.
"""
curr = paths[0].length/dist-1
for path in paths:
if path.length - 1 >= 0:
if random.random() <= sub*curr:
random_index = random.randint(0, path.length-1)
path.string.pop(random_index)
path.string.append('n')
path.update(list(path.string))
return paths
def mutate(gen):
"""
Applies mutation operators to a list of Path objects.
Parameters:
gen: A generation containing all the generations paths.
Returns:
list: The updated list of Path objects after applying mutation operators.
"""
print(dist)
path = mutate_replace(gen.paths)
# path = mutate_change_last(path)
path = mutate_change(path)
path = mutate_add(path)
path = mutate_sub(path)
return list(path)
def evolve(gen, n, step):
"""
Evolves a generation into the next when 'm' is pressed and calls itself recusively until 'x' is pressed.
It also visualizes the fittest path of the generation and the generations in a certain stepsize frequency.
Parameters:
gen: A generation containing all the generations paths.
n (int): the number of the n'th generation.
step (int): the stepsize in which generations are printed and visualized.
Returns:
list: The updated list of Path objects after applying mutation operators.
"""
if (n == 1 or n % step == 0):
print("Generation", n, ": ")
gen.print()
if visualize:
visualize_path(S, E, boardsize, gen.paths[0].string, n)
visualize_generation(S, E, boardsize, gen, n)
key = input("Press m to mutate the fittest path for a new generation or 'x' to stop: ")
if key == 'm':
print("Mutating generation...")
next_gen_paths = mutate(gen)
next_gen = Generation(gen.size, next_gen_paths)
evolve(next_gen, n+1, step)
elif key == 'x':
print("Stopping evolution")
else:
print("Mutating generation...")
next_gen_paths = mutate(gen)
next_gen = Generation(gen.size, next_gen_paths)
evolve(next_gen, n+1, step)
if __name__ == "__main__":
#random.seed(0)
try:
gen1 = Generation(10)
evolve(gen1, 1, step)
except ValueError as e:
print(f"Error: {e}")