Implementation of Genetic Algorithm and Local Search Optimization

When tackling optimization problems like the Traveling Salesman Problem (TSP), various algorithms can be employed to find optimal or near-optimal solutions. Two popular methods are Genetic Algorithms (GA) and Local Search Optimization (LSO). Below, we demonstrate how both techniques can be applied to the TSP using Python.

Importing Required Libraries

First, we need to import the necessary libraries:

import numpy as np
import random
from scipy.spatial import distance_matrix
import matplotlib.pyplot as plt

Generating Random Cities

We’ll start by generating random cities for our TSP:

# Generate random cities
def create_cities(num_cities):
    return np.random.rand(num_cities, 2)

Calculating the Total Distance of a Route

To evaluate the quality of a route, we calculate its total distance:

# Calculate the total distance of a route
def total_distance(route, dist_matrix):
    return sum(dist_matrix[route[i], route[i + 1]] for i in range(len(route) - 1)) + dist_matrix[route[-1], route[0]]

Genetic Algorithm

Creating Initial Population

The initial population is created randomly:

# Create initial population
def create_population(pop_size, num_cities):
    return [random.sample(range(num_cities), num_cities) for _ in range(pop_size)]

Evaluating the Population’s Fitness

Fitness is evaluated based on the total distance of each route:

# Evaluate fitness of the population
def evaluate_population(population, dist_matrix):
    return [total_distance(individual, dist_matrix) for individual in population]

Selection of Parents Using Tournament Selection

We select parents for crossover using tournament selection:

# Selection: Select parents using tournament selection
def select_parents(population, fitness, tournament_size=3):
    selected = []
    for _ in range(len(population)):
        tournament = random.sample(list(zip(population, fitness)), tournament_size)
        selected.append(min(tournament, key=lambda x: x[1])[0])
    return selected

Crossover and Mutation Operations

We perform ordered crossover and swap mutation:

# Crossover: Ordered crossover
def crossover(parent1, parent2):
    size = len(parent1)
    start, end = sorted(random.sample(range(size), 2))
    child = [None] * size
    child[start:end] = parent1[start:end]
    ptr = end
    for gene in parent2:
        if gene not in child:
            if ptr >= size:
                ptr = 0
            child[ptr] = gene
            ptr += 1
    return child

# Mutation: Swap mutation
def mutate(individual, mutation_rate=0.01):
    if random.random() < mutation_rate:
        i, j = random.sample(range(len(individual)), 2)
        individual[i], individual[j] = individual[j], individual[i]
    return individual

Genetic Algorithm for TSP

The main loop of the genetic algorithm:

# Genetic Algorithm for TSP
def genetic_algorithm_tsp(cities, pop_size=100, num_generations=500, mutation_rate=0.01):
    dist_matrix = distance_matrix(cities, cities)
    population = create_population(pop_size, len(cities))
    
    for generation in range(num_generations):
        fitness = evaluate_population(population, dist_matrix)
        parents = select_parents(population, fitness)
        next_population = []
        
        for i in range(0, pop_size, 2):
            parent1, parent2 = random.sample(parents, 2)
            child1 = mutate(crossover(parent1, parent2), mutation_rate)
            child2 = mutate(crossover(parent2, parent1), mutation_rate)
            next_population.extend([child1, child2])
        
        population = next_population
    
    best_route = min(population, key=lambda ind: total_distance(ind, dist_matrix))
    return best_route, total_distance(best_route, dist_matrix)

Local Search Optimization

The local search optimization algorithm:

# Local Search Optimization for TSP
def local_search_tsp(cities, max_iterations=1000):
    dist_matrix = distance_matrix(cities, cities)
    
    def get_neighbors(route):
        neighbors = []
        for i in range(len(route)):
            for j in range(i + 1, len(route)):
                neighbor = route[:]
                neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
                neighbors.append(neighbor)
        return neighbors
    
    def evaluate(route):
        return total_distance(route, dist_matrix)
    
    current_route = random.sample(range(len(cities)), len(cities))
    current_distance = evaluate(current_route)
    
    for iteration in range(max_iterations):
        neighbors = get_neighbors(current_route)
        next_route = min(neighbors, key=evaluate)
        next_distance = evaluate(next_route)
        
        if next_distance < current_distance:
            current_route = next_route
            current_distance = next_distance
        else:
            break
    
    return current_route, current_distance

Plotting the Routes

Finally, we plot the routes to visualize the results:

# Function to plot the cities and the route
def plot_route(cities, route, title):
    plt.figure(figsize=(10, 6))
    plt.scatter(cities[:, 0], cities[:, 1], c='red')
    
    for i in range(len(route)):
        plt.plot([cities[route[i], 0], cities[route[(i + 1) % len(route)], 0]], 
                 [cities[route[i], 1], cities[route[(i + 1) % len(route)], 1]], 'b-')
    
    plt.title(title)
    plt.xlabel('X Coordinate')
    plt.ylabel('Y Coordinate')
    plt.show()

Code Implementation of Genetic Algorithm and Local Search Optimization

Output:

Best route (GA): [11, 16, 10, 1, 19, 5, 0, 14, 8, 13, 3, 18, 17, 12, 4, 9, 2, 7, 15, 6]
Best distance (GA): 3.8821983753581844
Best route (LSO): [14, 5, 10, 6, 15, 7, 9, 2, 11, 1, 19, 13, 18, 3, 17, 12, 4, 16, 8, 0]
Best distance (LSO): 4.482746334228395

The code demonstrates how Genetic Algorithms and Local Search Optimization can be applied to solve the TSP. While Genetic Algorithms use a population-based approach with crossover and mutation, Local Search Optimization relies on exploring the neighborhood of the current solution. Both methods have their strengths and can be chosen based on the specific requirements of the problem at hand.

Artificial Intelligence (AI) has revolutionized how we solve problems and optimize systems. Two popular methods in the optimization field are Local Search Optimization (LSO) algorithms and Genetic Algorithms (GAs). While both are used to tackle complex issues, their approaches, uses, and performance characteristics differ significantly.

The article provides an overview of genetic algorithms and local search optimization in AI, and highlight the differences between both of them.