Untitled

mail@pastecode.io avatar
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}")