<jupyter_start><jupyter_text>Simple Genetic Algorithm<jupyter_code>import numpy as np
from scipy.spatial.distance import euclidean
import matplotlib.pyplot as plt
import random as rnd<jupyter_output><empty_output><jupyter_text>Data (Travelling Salesman Problem)<jupyter_code># Define the location of each city
X = [5, 10, 23, 34, 45, 60, 50, 45, 30, 20]
Y = [10, 30, 55, 50, 58, 53, 40, 25, 20, 10]
city_map = dict(enumerate(zip(X,Y))) # A dict mapping of city index to location
city_map
cities = list(city_map.keys()) # all indices of cities
cities
# Plot the cities
plt.scatter(X + [X[0]], Y + [Y[0]])
for i, (x, y) in enumerate(zip(X,Y)):
    plt.annotate(i, (x, y), (x+0.5, y+0.5))
plt.plot(X + [X[0]], Y + [Y[0]])
# This is also the ideal solution that we expect the model to learn<jupyter_output><empty_output><jupyter_text>Initialization of population<jupyter_code>def initialize_pop(pop_size=10):
    population = []
    for i in range(pop_size):
        individual = cities.copy()
        rnd.shuffle(individual) # shuffle the cities
        population.append(individual)
    return population
sample_pop = initialize_pop(pop_size=5)
sample_pop<jupyter_output><empty_output><jupyter_text>Fitness Function<jupyter_code>def fitness(solution):
    '''Returns the total travel distance for a given solution'''
    total_distance = 0
    
    # Calculate the acyclic distance from first city to last city
    for i in range(len(solution)-1):
        p1 = city_map[solution[i]]
        p2 = city_map[solution[i+1]]
        total_distance += euclidean(p1, p2)
    
    # Complete the loop by adding the distance between last city and first city
    p1 = city_map[solution[-1]]
    p2 = city_map[solution[0]]
    total_distance += euclidean(p1, p2)
       
    return total_distance
# fitness of an individual from sample population
fitness(sample_pop[0])<jupyter_output><empty_output><jupyter_text>Selection<jupyter_code>def selection(population):
    '''Selects an individual randomly based on its fitness value as weights'''
    # Calculate the fitness values of every individual in the population
    fitness_values = list(map(fitness, population))
    # Calculate the relative inverse fitness as our goal is to minimize the total distance
    inverse_fitness = [max(fitness_values) - x for x in fitness_values]
    # Assign weights to each individual based on the inverse fitness
    weights = [x / sum(inverse_fitness) for x in inverse_fitness]
    # Select a individual as a parent with weighted randomness
    selected_individual = rnd.choices(population, weights)[0]
    
    return selected_individual
selection(sample_pop)<jupyter_output><empty_output><jupyter_text>Crossover<jupyter_code>def crossover(parent1, parent2, prnt=False):
    '''Returns the child after crossover between the parents'''
    # Select cut points
    c1 = rnd.randint(0, len(parent1)-2)
    c2 = rnd.randint(c1+1, len(parent2)-1)
    
    # Create an Empty Child DNA
    child = ["X"] * len(parent1)
    
    # Set the values between the cut points from parent1 in the child DNA
    child[c1:c2+1] = parent1[c1:c2+1]
    if prnt: print('Child DNA from Parent 1', child)
    
    # Fill the remaining values from parent2
    for i in range(len(child)):
        for j in range(len(parent2)):
            # If the parent value is not already in the child then
            if parent2[j] not in child:
                # Replace with parent value only at places marked X
                child[i] = parent2[j] if child[i] == "X" else child[i]
                # break out of the inner loop and move over to the next position in the DNA
                break
    
    if prnt: print('Child DNA after adding Parent 2', child)
    
    return child
parent1 = [5, 1, 4, 2, 7, 6, 3, 8, 0, 9]
parent2 = [5, 2, 9, 0, 7, 8, 1, 4, 6, 3]
child = crossover(parent1, parent2, prnt=True)<jupyter_output>Child DNA from Parent 1 [5, 1, 4, 2, 7, 6, 3, 8, 0, 9]
Child DNA after adding Parent 2 [5, 1, 4, 2, 7, 6, 3, 8, 0, 9]<jupyter_text>Mutation<jupyter_code>def mutation(individual):
    '''Mutates the DNA of a child/individual by swapping the values at two positions'''
    # Selecting the index values to swap
    pos_1 = rnd.randint(0, len(individual)-1)
    pos_2 = rnd.randint(0, len(individual)-1)
    # Init the mutant
    mutant = individual.copy()
    # Swap
    mutant[pos_1] = individual[pos_2]
    mutant[pos_2] = individual[pos_1]
    
    return mutant
mutated_child = mutation(child)
print('Before Mutation', child)
print('After Mutation', mutated_child)<jupyter_output>Before Mutation [5, 1, 4, 2, 7, 6, 3, 8, 0, 9]
After Mutation [5, 1, 4, 2, 3, 6, 7, 8, 0, 9]<jupyter_text>Putting Everything Together<jupyter_code>def optimize_GA(pop_size, max_generations, crossover_prob, mutate_prob):
    '''Returns the final solution by optimizing using genetic algorithm'''

    # Initialize the Population
    population = initialize_pop(pop_size)
    global_best = {}

    # Start Evolution
    for g in range(max_generations):

        # Calculate Fitness of the population
        population_fitness = list(map(fitness, population))

        # Get the individual with the best fitness value (min distance value)
        best_fitness = min(population_fitness)
        best_fit_index = population_fitness.index(best_fitness)
        best_fit_individual = population[best_fit_index]

        # Check with global best
        if g == 0:
            global_best['fitness'] = best_fitness
            global_best['dna'] = best_fit_individual
        else:
            if best_fitness <= global_best['fitness']:
                global_best['fitness'] = best_fitness
                global_best['dna'] = best_fit_individual
#             print('Best Solution at Generation', g)

        new_population = []
        for i in range(pop_size):
            # Select the parents
            parent1 = selection(population)
            parent2 = selection(population)

            # Crossover between the parents with a certain probability
            if rnd.random() <= crossover_prob:
                child = crossover(parent1, parent2)
            else: # or directly clone one of the parents
                child = rnd.choice([parent1, parent2])

            # Mutation
            if rnd.random() <= mutate_prob:
                child = mutation(child)

            # Add child to new population
            new_population.append(child)

        population = new_population
    return global_best
# Hyperparameters
pop_size = 10
max_generations = 200
crossover_prob = 1
mutate_prob = 0.7
%%time
# Start Optimization with Genetic Algorithm
solution = optimize_GA(pop_size, max_generations, crossover_prob, mutate_prob)
solution<jupyter_output>CPU times: user 6.6 s, sys: 20 ms, total: 6.62 s
Wall time: 6.62 s<jupyter_text>Visualizing the results<jupyter_code># Get the x,y coordinates of the cities for plotting
solution_points = np.array([city_map[x] for x in solution['dna']] + [city_map[solution['dna'][0]]])
solution_points
# Plot the Solution
X_sol = solution_points[:, 0]
Y_sol = solution_points[:, 1]

plt.scatter(X_sol, Y_sol)
plt.plot(X_sol, Y_sol)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09882583170254403, 'fraction_numerical': 0.027257478333799275, 'mean_word_length': 3.4112207151664613, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '514655', 'license': 'MIT', 'n_tokens_mistral': 2469, 'n_tokens_neox': 2234, 'n_words': 710, 'path': 'optimization/Genetic_Algorithm_TSP.ipynb', 'repo_name': 'futureseadev/hgwxx7', 'size': '7154'}