Metaheuristics

Metaheuristics are high-level heuristics that aim to guide other heuristics toward better solutions. They are often used to solve large-scale, complex optimization problems where the search space is too vast to be searched exhaustively. Metaheuristics typically work by iteratively improving a candidate solution, trying to escape local optima and find a global optimum. Some examples of metaheuristics include simulated annealing, tabu search, and evolutionary algorithms.

Metaheuristics

●     A metaheuristic is a master strategy used to guide a simpler heuristic search for a solution

○     For example, a simple 2-opt heuristic can be greatly improved by adapting it using simulated annealing or tabu search.

○     Further metaheuristics used to escape local optima are

■     Variable neighbourhood search

■     Guided local search

■     Iterated local search 

Evolutionary algorithms (EA) are another type of metaheuristic. These algorithms are inspired by the process of natural evolution and use mechanisms such as reproduction, mutation, and selection to search for solutions to problems. EAs are commonly used to solve optimization problems and are particularly useful for problems with a large search space and no known algorithm for finding an optimal solution. Examples of evolutionary algorithms include genetic algorithms, differential evolution, and particle swarm optimization.

Construction metaheuristics

Construction metaheuristics are methods that iteratively build up a solution to a problem, usually starting from a partially constructed or empty solution and adding new elements until a complete solution is obtained. Some examples of construction metaheuristics include:

●     Greedy algorithms: These algorithms make the locally optimal choice at each step, hoping that these choices will lead to a globally optimal solution.

●     Genetic algorithms: These algorithms use principles of natural evolution, such as selection, crossover, and mutation, to generate new solutions and improve upon existing ones.

●     Ant colony optimization: This algorithm simulates the behavior of ants searching for food, using pheromone trails left by other ants to guide their search.

Construction metaheuristics are often used to solve problems in which the solution can be built up incrementally, such as scheduling or routing problems. They are typically less effective at solving optimization problems that require a significant amount of modification to an existing solution in order to improve it.

We can use metaheuristics to adapt greedy, construction algorithms as well as perturbation searches.

One example of a construction metaheuristic is the greedy randomized adaptive search procedure (GRASP). This algorithm starts by constructing a solution using a greedy approach, but then introduces randomness to escape local optima. At each step of the construction process, a set of candidates is created and a random candidate is chosen to be included in the solution. The algorithm then continues the construction process until a complete solution is formed. GRASP can be used to solve a variety of optimization problems, including the knapsack problem and the traveling salesman problem.

Let’s take an adaptation of the nearest neighbour algorithm for the TSP.

The nearest neighbour algorithm is:

●     Start at a given node

●     Find the node nearest to it and add to the tour

●     Then keep picking the nearest unused node and add until there are no more nodes left.

This can produce some pretty bad results - but we can improve it using a metaheuristic...

Here is an example of how we can use the metaheuristic of simulated annealing to improve the nearest neighbor algorithm for the TSP:

import random

 

def calc_distance(tour):

  # Calculate the total distance of a given tour

  distance = 0

  for i in range(len(tour) - 1):

    distance += distance_matrix[tour[i]][tour[i + 1]]

  return distance

 

def simulated_annealing(tour, temperature, cooling_rate):

  # Improve the given tour using simulated annealing

  while temperature > 0.1:

    # Pick two random nodes to swap

    i = random.randint(0, len(tour) - 1)

    j = random.randint(0, len(tour) - 1)

    if i == j:

      continue

 

    # Calculate the current and new distances

    current_distance = calc_distance(tour)

    new_distance = calc_distance(tour[:i] + tour[i:j + 1][::-1] + tour[j + 1:])

    delta = new_distance - current_distance

 

    # If the new tour is better, accept it

    if delta < 0:

      tour = tour[:i] + tour[i:j + 1][::-1] + tour[j + 1:]

    else:

      # If the new tour is worse, accept it with a probability

      # proportional to the current temperature

      if random.random() < 2.71828 ** (-delta / temperature):

        tour = tour[:i] + tour[i:j + 1][::-1] + tour[j + 1:]

   

    # Decrease the temperature

    temperature *= 1 - cooling_rate

  return tour

 

# Initialize variables

nodes = [0, 1, 2, 3, 4]

distance_matrix = [[0, 10, 15, 20, 25],

                   [10, 0, 35, 25, 30],

                   [15, 35, 0, 30, 15],

                   [20, 25, 30, 0, 40],

                   [25, 30, 15, 40, 0]]

tour = [0, 1, 2, 3, 4]

 

# Run the simulated annealing algorithm

tour = simulated_annealing(tour, 100, 0.1)

 

# Print the final tour and distance

print("Final tour:", tour)

print("Distance:", calc_distance(tour))

This code first defines a function calc_distance that calculates the total distance of a given tour. Then it defines the simulated_annealing function, which takes in a tour, a starting temperature, and a cooling rate. It repeatedly swaps two random nodes in the tour and calculates the new distance. If the new tour has a shorter distance, it is always accepted. If the new tour has a longer distance, it is accepted with a probability proportional to the current temperature. The temperature is decreased at each iteration by the cooling rate. Finally, the code initializes some variables and runs the simulated_annealing function to improve the initial tour.

GRASP

GRASP (Greedy Randomized Adaptive Search Procedure) is a metaheuristic for combinatorial optimization problems that combines the benefits of greediness and randomization. It works by iteratively constructing a solution by greedily selecting the locally best available option and then randomly perturbing the solution to escape local optima.

The algorithm works as follows:

1.       Initialize an empty solution

2.       While the solution is not complete:

3.       Select the best available option using a greedy heuristic

4.       Randomly perturb the solution by making a small number of changes

5.       Return the final solution

The key idea behind GRASP is to use the greediness of a local search algorithm to quickly find a good solution, while using the randomization to escape local optima and improve the overall quality of the solution.

The GRASP, or Greedy Random Adaptive Search Procedure metaheuristic takes a greedy algorithm, randomises its choices from a Reduced Candidate List (RCL) and repeats.

●     Repeat until no improvement found in k passes

○     Start at a random node

○     While there are unused nodes

■     Select the nearest c neighbours from the tour’s endpoints

■     Randomly pick one and add to the tour

○     (optional) do 2-opt search on resulting tour

We can perform a much more intensive search using this method, and keep getting different results each time.

Task

Try to produce a GRASP algorithm for the vertex cover problem by adapting one of the greedy algorithms.

To create a GRASP algorithm for the vertex cover problem, we can start by adapting the greedy algorithm that iteratively adds the vertex with the highest degree to the cover until all edges are covered.

Here is an example of how this could be implemented in Python:

def grasp_vertex_cover(G):

  # G is the input graph in the form of a list of edges

 

  # Initialize an empty vertex cover

  vertex_cover = set()

 

  # Repeat the following process a number of times (we can experiment with different values for the number of iterations)

  for i in range(10):

    # Create a list of the remaining vertices that are not yet in the cover

    remaining_vertices = set(G.keys()) - vertex_cover

   

    # Initialize an empty candidate set for the current iteration

    candidate_set = set()

 

    # While there are still remaining vertices

    while len(remaining_vertices) > 0:

      # Find the vertex with the highest degree

      highest_degree_vertex = max(remaining_vertices, key=lambda v: len(G[v]))

 

      # Add the highest degree vertex to the candidate set and remove it from the list of remaining vertices

      candidate_set.add(highest_degree_vertex)

      remaining_vertices.remove(highest_degree_vertex)

 

      # Remove all the edges incident to the highest degree vertex from the graph

      for neighbor in G[highest_degree_vertex]:

        del G[neighbor][highest_degree_vertex]

 

    # Choose the best solution from the candidate set using a randomization procedure (we can use a random selection or a greedy selection based on the vertex degrees)

    vertex_cover.update(random.sample(candidate_set, k=1))

 

  # Return the final vertex cover

  return vertex_cover

This GRASP algorithm for the vertex cover problem works by repeating the greedy algorithm a number of times, each time constructing a candidate set of vertices using the greedy selection strategy. The final vertex cover is then chosen from the union of all the candidate sets using a randomization procedure. This allows the algorithm to escape local optima and potentially find a better overall solution.

Ant Colony Optimisation (ACO)

Ant Colony Optimisation (ACO) is a heuristic optimization algorithm that simulates the behavior of ants searching for food. It is often used to find solutions to combinatorial optimization problems, such as the travelling salesman problem or the knapsack problem.

ACO works by maintaining a population of "virtual ants" that iteratively build solutions to the optimization problem by constructing a path through a graph. At each step, an ant chooses the next node in its path based on a combination of the pheromone levels on the edges and the distance between the nodes. As the ants traverse the graph, they leave behind a trail of pheromones that influence the choices of the other ants. Over time, the pheromone levels on the edges of the graph will converge towards the optimal solution, as the ants are more likely to follow paths with higher pheromone levels.

Here is a simple example of ACO implemented in Python for solving the travelling salesman problem:

import random

 

# Number of cities

n = 20

 

# Distance matrix

dist = [[0] * n for _ in range(n)]

 

# Randomly generate distance matrix

for i in range(n):

    for j in range(n):

        if i == j:

            dist[i][j] = 0

        elif dist[i][j] == 0:

            dist[i][j] = dist[j][i] = random.randint(1, 10)

 

# Number of ants

m = 10

 

# Number of iterations

t = 100

 

# pheromone matrix

pheromone = [[1 / (n * n)] * n for _ in range(n)]

 

# Heuristic information matrix

heuristic = [[1 / dist[i][j] for j in range(n)] for i in range(n)]

 

# Evaporation rate

q = 0.5

 

# Intensity of pheromone deposit

d = 0.1

 

# Find the shortest path using ACO

best_path = float("inf")

best_tour = []

for _ in range(t):

    tours = []

    for k in range(m):

        tour = [random.randint(0, n - 1)]

        while len(tour) < n:

            last = tour[-1]

            choices = [i for i in range(n) if i not in tour]

            probs = [pheromone[last][i] ** q * heuristic[last][i] ** (1 - q) for i in choices]

            norm = sum(probs)

            probs = [p / norm for p in probs]

            tour.append(choices[weighted_choice(probs)])

        tours.append(tour)

 

    for tour in tours:

        length = sum([dist[tour[i]][tour[i + 1]] for i in range(-1, n - 1)])

        if length < best_path:

            best_path = length

            best_tour = tour

        for i in range(-1, n - 1):

            pheromone[tour[i]][tour[i + 1]] += d / length

            pheromone[tour[i + 1]][tour[i]] += d / length

    for i in range(n):

        for j in range(n):

            pheromone[i][j] *= 1 - q

 

print(best_path)

print(best_tour)

This ACO algorithm works by simulating the behavior of ants searching for food. In this case, each ant is searching for the shortest path between a set of cities. At each step, the ant chooses the next city to visit based on the pheromone levels on the edges and the heuristic value of the cities. Pheromones are a chemical trail left by ants that other ants can follow, and in this case, the pheromone levels represent the desirability of an edge. The heuristic value represents the distance between two cities, with shorter distances being more desirable.

The algorithm runs for a specified number of iterations, with each iteration consisting of multiple ants building tours. At the end of each iteration, the pheromone levels on the edges are updated based on the length of the tours and the amount of pheromone deposited by the ants. The pheromone update rule used in this example is:

pheromone[i][j] = (1-rho)*pheromone[i][j] + delta_pheromone[i][j]

Where rho is the pheromone evaporation coefficient (set to 0.1 in this example) and delta_pheromone[i][j] is the amount of pheromone deposited on edge (i,j) by the ants. This amount is proportional to the length of the tour and the quality of the solution, with shorter and better tours depositing more pheromone.

The probability of an ant choosing a particular edge is also influenced by the pheromone levels on that edge. An edge with high pheromone levels will be more attractive to the ants, while an edge with low pheromone levels will be less attractive. The probability of an ant choosing edge (i,j) is given by:

probability[i][j] = (pheromone[i][j]**alpha) * ((1.0/distance[i][j])**beta)

Where alpha and beta are parameters that control the relative importance of the pheromone and distance factors. In this example, alpha is set to 1 and beta is set to 2.

The ACO algorithm iterates for a specified number of iterations, with each iteration consisting of the following steps:

1.       Initialise pheromone levels on all edges to a small positive value.

2.       For each ant:

1.       Initialise the ant at a random node.

2.       While the ant is not at the final node:

1.       Choose the next node based on the probabilities of the available edges.

2.       Update the ant's tour length.

3.       Deposit pheromone on the chosen edge.

1.       Update the best tour length and the corresponding tour if the ant's tour is better.

1.       Update the pheromone levels on all edges using the pheromone update rule.

2.       Repeat from step 2 until the number of iterations is reached.

At the end of the algorithm, the best tour found by the ants is returned as the solution.

ACO is a metaheuristic based on the foraging behaviour of Argentine ants.

●     It is observed that ant colonies are good at finding quick routes to food sources on a tree.

●     They achieve this by a process called stigmergy

○     Ants explore the tree randomly but leave pheromone trails when they return from a food source

○     The pheromone trail is stronger the nearer the food source is

○     Subsequent ants are still random, but bias their choices in favour of the branches with strong pheromone trails

○     The good trails get stronger and eventually all ants converge on the best route - until the food runs out.

○     This has actually been simulated for large scale network routing and outperforms many standard approaches

ACO for the TSP

We could do a simple adaptation for the TSP as follows:

●     Start with all pheromone levels equal (or zero)

●     While there is no improvement in k iterations:

○     Send out a number of ants (in parallel ideally)

○     For each ant

■     while there are unused nodes

●     Choose an edge randomly to join the tour, based on pheromone distribution

■     Do 2-opt or other iterative improvement search (optional)

■     Update pheromone levels so that highest levels are on edges in shortest tours

Evaporate (remove a percentage of pheromones from all edges)

Population vs Trajectory based techniques

Population based techniques refer to algorithms that maintain a population of candidate solutions and use some form of selection and variation to improve the solutions over time. Examples of population based techniques include evolutionary algorithms and genetic algorithms.

Trajectory based techniques, on the other hand, refer to algorithms that follow a single candidate solution as it evolves over time. These algorithms do not maintain a population of solutions and instead only focus on a single solution at a time. Examples of trajectory based techniques include simulated annealing and tabu search.

This is our first example of a population based technique, which works on many candidate solutions at a time and not just one.

Other examples of population based techniques include genetic algorithms, particle swarm optimization, and ant colony optimization. These techniques are often inspired by natural processes and involve the manipulation and evolution of a group of potential solutions.

On the other hand, trajectory based techniques involve the manipulation of a single solution, which is iteratively improved upon until it reaches an optimal or satisfactory state. Examples of trajectory based techniques include local search algorithms such as simulated annealing, tabu search, and iterated local search. These techniques work by making small changes to a current solution and evaluating whether it results in an improvement. If it does, the solution is accepted and the process continues, otherwise the solution is rejected and the process returns to the previous state.

These are particularly useful as they lend themselves well to parallel computation.

Genetic algorithms (GAs) are another example of population based techniques. They work by creating a population of candidate solutions (often called chromosomes), which are then evolved over time using the principles of natural selection and genetics.

In each iteration, the fitness of each chromosome is evaluated and the best performing ones are selected to create a new population of offspring through processes such as crossover (recombination of genes) and mutation. This process is repeated until a satisfactory solution is found or a pre-determined number of iterations have been reached.

GAs are often used to solve optimization problems, but they can also be applied to problems in machine learning and data mining. They are particularly useful for problems where the search space is large and the objective function is complex and non-linear.

Here is an example of a simple genetic algorithm implemented in Python for solving the knapsack problem:

Initialize population

population = [Individual() for i in range(POPULATION_SIZE)]

Evaluate population

for individual in population: individual.fitness = evaluate_fitness(individual.chromosome)

Loop until termination condition is met

while not termination_condition_met(): # Select parents parents = select_parents(population)

# Generate offspring

offspring = []

for i in range(0, len(parents), 2):

    offspring += crossover(parents[i], parents[i+1])

 

# Mutate offspring

for i in offspring:

    mutate(i)

 

# Evaluate offspring

for individual in offspring:

    individual.fitness = evaluate_fitness(individual.chromosome)

 

# Replace population with offspring

population = offspring

Return the best individual in the final population

best_individual = sorted(population, key=lambda x: x.fitness, reverse=True)[0] return best_individual

Genetic Algorithms and Evolutionary Computing

Genetic algorithms are a type of optimization algorithm that are inspired by the process of natural selection and evolution in biology. They are used to find solutions to optimization problems by simulating the process of evolution in a population of candidate solutions.

The basic idea behind genetic algorithms is to start with a population of candidate solutions, known as "chromosomes," and apply a set of rules to generate a new population of chromosomes for each iteration of the algorithm. These rules are inspired by the mechanisms of natural evolution, such as reproduction, mutation, and natural selection.

In each iteration, the genetic algorithm selects the best-performing chromosomes from the current population and reproduces them to create a new population of offspring. It also introduces random mutations to the offspring to add diversity to the population and prevent it from getting stuck in a local minimum. Finally, it applies a selection process to choose the fittest chromosomes to survive and carry on to the next generation.

The process is repeated until the algorithm reaches a satisfactory level of performance or a predefined number of iterations has been reached. At this point, the best-performing chromosome in the final population is returned as the solution to the optimization problem.

Genetic algorithms are widely used in various fields, including machine learning, data analysis, and engineering, to find solutions to a wide range of optimization problems. They are particularly useful for problems that have a large search space and are difficult to solve using traditional optimization techniques.

Genetic algorithms are similar to local search but with two main differences

●     GAs are population based so operate on many solutions at a time

●     They allow for crossover and recombination of candidate solutions as well as mutation

○     Our algorithms up until now have allowed only mutation, applying a small alteration to a single solution

○     Crossover and recombination allow the creation of new solutions by combining characteristics of existing ones (think parents and children here)

○     Genetic algorithms traditionally operated only on solutions represented by bitstrings, a similar process using a more complex solution (eg. containing integers) is called an evolutionary algorithm.

○     Many GAs only involve mutation as crossover is tricky and often breaks feasibility

GAs

Make changes to current population to create a new generation (crossover/mutation)

Evaluate new generation

Discard weak solutions

Initial population

 

 

 

 

 

 

 

 

 

Ridiculous metaphor

One way to think about genetic algorithms is to imagine that you are trying to climb a very tall mountain. You are not sure exactly where the peak is, but you have a pretty good idea of the general direction. You also know that the mountain is very steep, and there are a lot of cliffs and other obstacles that will make it difficult to reach the top.

To climb the mountain, you have a group of people (called the population). Each person has a unique set of traits that will help them navigate the mountain and reach the peak. These traits might include things like strength, agility, endurance, and so on.

As the group begins to climb, some people will naturally do better than others. The stronger and more agile people will be able to climb faster and more efficiently, while the weaker and less agile people will struggle.

Over time, the group will naturally evolve. The stronger and more agile people will reproduce and pass on their traits to their offspring, while the weaker and less agile people will either die off or be left behind.

As the group continues to evolve and climb the mountain, they will eventually reach the peak. At this point, the group will have the optimal set of traits for navigating the mountain and reaching the top.

This is essentially how genetic algorithms work. The mountain represents the problem you are trying to solve, and the population represents the different possible solutions. Through a process of evolution and natural selection, the population will eventually find the best solution to the problem.

●     Iterative improvement is like getting a kangaroo to climb a hill by always going upwards. It very quickly gets stuck on top of a small hump.

●     Simulated annealing gets the kangaroo drunk first, so it staggers around with a bit of an upwards bias but eventually sobers up and starts acting like iterative improvement again.

●     Tabu search allows the kangaroo to go down if there is no other alternative and gives it an electric shock if it tries to go back on itself.

●     Genetic algorithms have loads of kangaroos, let them walk whenever they want but periodically shoot any kangaroos going the wrong way.

●     Ant colony optimisation has many kangaroos which walk around randomly but start shrieking as they climb higher. Subsequent kangaroos follow the noise.