Simulated Bee Colony Algorithm for the Traveling Salesman Problem using Python

A simulated bee colony (SBC) algorithm models the behavior of a hive of honeybees to solve combinatorial optimization problems. A combinatorial problem is one where the goal is to place discrete items into a correct order. Sudoku and the traveling salesman (TSP) problem are two examples.

BeeColonyDemo

In TSP, you start with a collection of cities and the problem is to find the path that visits every city just once, and has shortest distance possible. TSP is difficult. For example, if there are 20 cities, and all cities are connected to each other, then there are 20! = 2,432,902,008,176,640,000 distinct possible paths.

In SBC, each virtual bee represents a possible solution. Scout bees search randomly, hoping to get lucky. Regular foraging bees examine a neighbor solution and update if the neighbor is better. For example, if there are 5 cities then one bee might represent the path 1 -> 0 -> 4 -> 2 -> 3. A neighbor path would be a path with two cities swapped, for example, 1 -> 0 -> 2 -> 4 -> 3.

SBC is really a meta-heuristic, meaning it’s a loose set of guidelines rather than a rigid algorithm, so there are many, many possible implementations. I coded up a very rudimentary SBC solution for TSP in Python:

# beecolony.py
# python 3.4.3
# demo of simulated bee colony (SBC) optimization
# solves a dummy Traveling Salesman Problem

import random
import copy    # array-copying convenience
import sys     # max float

# ------------------------------------

def show_path(path):
  for i in range(len(path)-1):
    print(str(path[i]) + " -> ", end="")
  print(path[len(path)-1])

# ------------------------------------

def error(path):
  d = 0.0  # total distance between cities
  for i in range(len(path)-1):
    if path[i] < path[i+1]:
      d += (path[i+1] - path[i]) * 1.0
    else:
      d += (path[i] - path[i+1]) * 1.5
  minDist = len(path)-1
  return d - minDist

# ------------------------------------

class Bee:
  def __init__(self, nc, seed):
    #self.rnd = random.Random(seed)
    self.status = 0  # 0 = inactive, 1 = active, 2 = scout
    self.path = [0 for i in range(nc)]  # potential solution
    
    for i in range(nc):
      self.path[i] = i  # [0,1,2, ...]
    
    random.shuffle(self.path)
    self.error = error(self.path) # bee's current error

# ------------------------------------

def solve(nc, nb, max_epochs):
  # solve TSP for nc cities using nb bees
  # optimal soln is [0,1,2, . . n-1]
  # assumes dist between adj cities is 1.0 or 1.5 

  # create nb random bees
  hive = [Bee(nc, i) for i in range(nb)] 

  best_err = sys.float_info.max  # dummy init value
  for i in range(nb):  # check each random bee
    if hive[i].error < best_err:
      best_err = hive[i].error
      best_path = copy.copy(hive[i].path)
  
  # assign initial statuses
  numActive = int(nb * 0.50)
  numScout = int(nb * 0.25)
  numInactive = nb - (numActive + numScout)
  for i in range(nb):
    if i < numInactive:
      hive[i].status = 0
    elif i < numInactive + numScout:
      hive[i].status = 2
    else:
      hive[i].status = 1
  
  epoch = 0
  while epoch < max_epochs:
    if best_err == 0.0: break
    for i in range(nb):  # process each bee
      if hive[i].status == 1:    # active bee
        # find a neighbor path and associated error
        neighbor_path = copy.copy(hive[i].path)
        ri = random.randint(0, nc-1)  # random index
        ai = 0  # adjacent index. assume last->first
        if ri < nc-1: ai = ri + 1
        tmp = neighbor_path[ri]
        neighbor_path[ri] = neighbor_path[ai]
        neighbor_path[ai] = tmp
        neighbor_err = error(neighbor_path)

        # check if neighbor path is better
        p = random.random()  # [0.0 to 1.0)
        if (neighbor_err < hive[i].error or
         (neighbor_err >= hive[i].error and p < 0.05)):
          hive[i].path = neighbor_path
          hive[i].error = neighbor_err

          # new best?
          if hive[i].error < best_err:
            best_err = hive[i].error
            best_path = hive[i].path
            print("epoch = " + str(epoch) +
              " new best path found ", end="")
            print("with error = " + str(best_err))
        # active bee code

      elif hive[i].status == 2:  # scout bee
        # make random path and error
        random_path = [0 for j in range(nc)]
        for j in range(nc):
          random_path[j] = j
        random.shuffle(random_path)
        random_err = error(random_path)
        # is it better?
        if random_err < hive[i].error:
          hive[i].path = random_path  # ref assignmnt
          hive[i].error = random_err
          # new best?
          if hive[i].error < best_err:
            best_err = hive[i].error
            best_path = hive[i].path
            print("epoch = " + str(epoch) +
              " new best path found ", end="")
            print("with error = " + str(best_err))

      elif hive[i].status == 0:  # inactive
        pass  # null statement

    # for-each bee
    
    epoch += 1
  # while
  
  print("\nBest path found:")
  show_path(best_path)
  print("\nError of best path = " + str(best_err))

# ------------------------------------

print("\nBegin simulated bee colony optimization using
 Python demo\n")
print("Goal is to solve a dummy Traveling Salesman Problem")
print("\nDistance between cities A and B is (B-A) * 1.0 if B > A")
print(" or (A-B) * 1.5 if A > B. For example, d(3,5) = 2.0")
print(" and d(8,3) = 7.5. In a real scenario you'd have a
 lookup table")
print("\nFor n cities, the optimal path is 0 -> 1 -> . . -> (n-1)
print(" with a total path distance of n-1.\n") 

num_cities = 20
num_bees = 50
max_epochs =10000

print("Setting num_cities = " + str(num_cities))
print("Setting num_bees   = " + str(num_bees))
print("Setting max_epochs = " + str(max_epochs) + "\n")

random.seed(1)
solve(num_cities, num_bees, max_epochs)

print("\nEnd simulated bee colony demo\n")

In spite of its simplicity, SBC can be highly effective for solving some kinds of combinatorial optimization problems.

Advertisements
This entry was posted in Machine Learning. Bookmark the permalink.