Jump to content

File:Ant Colony Algorihm applied to the Travelling Salesman Problem.gif

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Ant_Colony_Algorihm_applied_to_the_Travelling_Salesman_Problem.gif (640 × 480 pixels, file size: 207 KB, MIME type: image/gif, looped, 88 frames, 44 s)

Summary

Description
English: Visualization of the ant colony algorithm applied to the travelling salesman problem. Each iteration of the algorithm corresponds to the voyage of a single ant. The green lines represent the paths chosen by the ant, while the blue lines are the possible paths it may take at each given point. The opacity of each blue line is related to the likelihood of choosing the corresponding path (which is proportional to the path’s pheromone level and inversely proportional to its distance). When the ant finishes its voyage, the pheromone levels of each path are represented in red, with those with the highest pheromone levels in a darker tone.
Date
Source Own work
Author Rodrigo Castro Freibott

Licensing

I, the copyright holder of this work, hereby publish it under the following license:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

This program, written in Python (using the Matplotlib and NumPy libraries), will generate each frame of the animation, and join them together using ImageMagick.

Python code

import matplotlib.pyplot as plt
from math import *
import random
import numpy as np
import os
import matplotlib.patheffects as pe

# Define the number of nodes and their coordinates
num_nodes = 5  # Number of nodes
nodes_x = [1, 3, 2, 5, 4]  # Array of size 'num_nodes'
nodes_y = [4, 1.5, 3, 2, 3.5]

# Obtain the distance of each edge
edges_distances = np.matrix([[0.0 for i in range(num_nodes)] for j in range(num_nodes)])
for i in range(num_nodes):
    for j in range(i, num_nodes):
        edges_distances[i, j] = sqrt((nodes_x[j] - nodes_x[i])**2 + (nodes_y[j] - nodes_y[i])**2)
        edges_distances[j, i] = edges_distances[i, j]

# Define the parameters of the algorithm
alpha = 1
beta = 1

# Define the initial pheromone level of each edge
edges_pheromones = np.matrix([[1 for i in range(num_nodes)] for j in range(num_nodes)])

# Define the number of ants (number of iterations of the algorithm)
num_ants = 6

nodes = set(range(num_nodes))
optimal_length = np.matrix.sum(edges_distances)  # Initialized as a very high number
optimal_voyage = []

images = []
img_index = 0
filename = "TSP_AntColony_Animation_WithOptimum_BetterCode"


def capture(nframes=1):
    """
    Generates 'nframes' images of the current PyPlot figure
    """
    for i in range(nframes):
        global img_index  # Necessary to change its value
        image = filename + "_" + str(img_index) + ".png"
        img_index += 1
        plt.savefig(image)
        images.append(image)


def lighten_color(color, amount=0.5):
    """
    Function from StackOverflow (https://stackoverflow.com/questions/37765197/darken-or-lighten-a-color-in-matplotlib)
    Returns a lighter (amount<1) or darker (amount>1) version of the color
    Examples:
    >> lighten_color('green', 0.3)
    # Returns a color that is like the 'green' color, but lighter
    >> lighten_color('green', 1.3)
    # Returns a color that is like the 'green' color, but darker
    """
    import matplotlib.colors as mc
    import colorsys
    try:
        c = mc.cnames[color]
    except:
        c = color
    c = colorsys.rgb_to_hls(*mc.to_rgb(c))
    return colorsys.hls_to_rgb(c[0], 1 - amount * (1 - c[1]), c[2])


ax_main = plt.gca()
ax_optimum = plt.gcf().add_axes((0.05, 0.05, 0.25, 0.25))
ax_optimum.set_xticks([])
ax_optimum.set_yticks([])
ax_optimum.set_title("Current optimum",
                     path_effects=[pe.withStroke(linewidth=2, foreground='white')])

for ant in range(num_ants):

    # Clear main axes
    ax_main.clear()
    ax_main.scatter(nodes_x, nodes_y, c='black')
    ax_main.set_title("Iteration " + str(ant) + " of " + str(num_ants - 1))

    current_node = 0
    length = 0  # Sum of the distances of the voyage
    voyage = [0]  # Sequence of nodes

    while len(nodes.difference(set(voyage))) > 0:  # While there are unvisited nodes

        unvisited_nodes = []
        probabilities = []  # Likelihood of going to each unvisited node
        summation = 0

        # Calculate the probabilities to go to each node
        for node in nodes.difference(set(voyage)):
            unvisited_nodes.append(node)
            probability = (edges_pheromones[current_node, node]**alpha) *\
                          (1/edges_distances[current_node, node]**beta)
            probabilities.append(probability)
            summation += probability
        probabilities = np.array(probabilities)
        probabilities = probabilities / summation  # Normalized probabilities
        # Draw each possible path, indicating its probability with transparency
        lines = []
        for i in range(len(nodes.difference(set(voyage)))):
            lines.append(ax_main.plot([nodes_x[current_node], nodes_x[unvisited_nodes[i]]],
                                      [nodes_y[current_node], nodes_y[unvisited_nodes[i]]],
                                      c='blue', alpha=probabilities[i])[0])
        capture()

        # Choose a node among the unvisited nodes
        chosen_node = random.choices(unvisited_nodes, weights=probabilities, k=1)[0]
        # Mark the chosen path as green, and delete the others
        for i in range(len(nodes.difference(set(voyage)))):
            if unvisited_nodes[i] == chosen_node:
                lines[i].set_color('green')
                lines[i].set_alpha(1)
            else:
                lines[i].remove()
        capture()

        # Update edges, length and current node
        edges_pheromones[current_node, chosen_node] += 1  # Update the chosen path
        edges_pheromones[chosen_node, current_node] += 1  # We want it to be a symmetrical matrix
        length += edges_distances[current_node, chosen_node]  # Update the length of the voyage
        current_node = chosen_node
        voyage.append(current_node)

    # Include the path of return from the last node to 0
    edges_pheromones[current_node, 0] += 1
    edges_pheromones[0, current_node] += 1
    length += edges_distances[current_node, 0]
    voyage.append(0)

    # Update optimal length and voyage
    if length < optimal_length:
        optimal_length = length
        optimal_voyage = voyage
        ax_optimum.clear()
        ax_optimum.scatter(nodes_x, nodes_y, c='black')
        ax_optimum.set_xticks([])
        ax_optimum.set_yticks([])
        ax_optimum.set_title("Current optimum - " + str(round(optimal_length, 2)) + "m",
                             path_effects=[pe.withStroke(linewidth=2, foreground='white')])
        for i in range(len(optimal_voyage) - 1):
            ax_optimum.plot([nodes_x[optimal_voyage[i]], nodes_x[optimal_voyage[i + 1]]],
                            [nodes_y[optimal_voyage[i]], nodes_y[optimal_voyage[i + 1]]],
                            c=lighten_color('green'))

    # Draw the last path, resulting in a full view of the voyage
    ax_main.plot([nodes_x[current_node], nodes_x[0]],
                 [nodes_y[current_node], nodes_y[0]],
                 c='green')
    ax_main.set_title("Iteration " + str(ant) + " of " + str(num_ants - 1)
                      + " - " + str(round(length, 2)) + "m")
    capture(3)

    # Clear main axes
    ax_main.clear()
    ax_main.scatter(nodes_x, nodes_y, c='black')
    ax_main.set_title("Iteration " + str(ant) + " of " + str(num_ants - 1) + " - resulting pheromone levels")
    # Show pheromone level of each path
    for i in range(num_nodes):
        for j in range(i, num_nodes):
            ax_main.plot([nodes_x[i], nodes_x[j]],
                         [nodes_y[i], nodes_y[j]],
                         c=lighten_color('red', edges_pheromones[i, j] / num_ants))
    capture(3)

# Create a final image
plt.gcf().clf()
ax = plt.gca()
ax.scatter(nodes_x, nodes_y, c='black')
ax.set_title("PROGRAM FINISHED - RESULTING OPTIMUM - " + str(round(optimal_length, 2)) + "m")
for i in range(len(optimal_voyage) - 1):
    ax.plot([nodes_x[optimal_voyage[i]], nodes_x[optimal_voyage[i + 1]]],
            [nodes_y[optimal_voyage[i]], nodes_y[optimal_voyage[i + 1]]],
            c=lighten_color('green'))
capture(4)

# Create the animation using ImageMagick
fps = 2
os.system('convert -delay {} +dither +remap -layers Optimize {} "{}"'.
          format(100//fps, ' '.join(['"' + img + '"' for img in images]), filename + '.gif'))

# Delete the images
for img in images:
    if os.path.exists(img):
        os.remove(img)

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

15 April 2022

image/gif

a59d315f531c4d82bb4e8c776ce02a13978ecdae

211,913 byte

44 second

480 pixel

640 pixel

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current20:22, 15 April 2022Thumbnail for version as of 20:22, 15 April 2022640 × 480 (207 KB)Rodrigo Castro FreibottUploaded while editing "Ant colony optimization algorithms" on en.wikipedia.org

The following page uses this file: