## 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.

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)

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.