Untitled
plain_text
2 months ago
11 kB
1
Indexable
Never
import random #import visualizer functions for paths and generations from Visualizer import visualize_path, visualize_generation #size of the checkerboard boardsize = 6 #seed (leave empty if you want total randomness) random.seed(0) #start and endpoint on the grid S = (random.randrange(boardsize), random.randrange(boardsize)) E = (random.randrange(boardsize), random.randrange(boardsize)) #weights for the fitness function fit_len = 1 #length fit_dist = 1 #distance fit_var = 1 #variation #parameters for the mutator functions step = 1 #stepsize add = 1 #adding a character sub = 1 #subtracting a character change = 1 #changing a character replace = 1 #replacing less fit paths with the fittest path (path[0]) class Path: def __init__(self, string_length): """ Initializes a Path object with a random string of moves. Parameters: string_length (int): The length of the random 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. """ 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, string_length, 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(string_length) 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. """ # Calculate the fittest path in the list fittest_path = list(paths[0].string) for path in paths: if random.random() <= replace: # Replace the path with the fittest path path.update(fittest_path) 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. """ letters = ['u', 'd', 'l', 'r'] for path in paths: for i in range(path.length): if random.random() <= change: old_char = path.string[i] new_char = random.choice(letters) while new_char == old_char: new_char = random.choice(letters) path.string[i] = new_char path.update(list(path.string)) 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. """ letters = ['u', 'd', 'l', 'r'] for path in paths: if path.length < boardsize: if random.random() <= add: 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. """ for path in paths: if path.length - 1 >= 0: if random.random() <= sub: 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. """ dist = min((E[0] - S[0])%boardsize, (S[0]-E[0])%boardsize) + min((E[1] - S[1])%boardsize, (S[1]-E[1])%boardsize) print(dist) path = mutate_replace(gen.paths) 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() #visualize_path(S, E, boardsize, gen.paths[0].string, n) #visualize_generation(gen, boardsize, S, E, n) key = input("Press m to mutate the fittest path for a new generation or 'x' to stop: ") if key == 'm': print("Mutating fittest path...") next_gen_paths = mutate(gen) next_gen = Generation(gen.size, boardsize, next_gen_paths) evolve(next_gen, n+1, step) elif key == 'x': print("Stopping evolution") else: print("Mutating fittest path...") next_gen_paths = mutate(gen) next_gen = Generation(gen.size, boardsize, next_gen_paths) evolve(next_gen, n+1, step) if __name__ == "__main__": #random.seed(0) try: gen1 = Generation(2, boardsize) evolve(gen1, 1, step) except ValueError as e: print(f"Error: {e}")