"""
gpp_ts_intdiv.py: Construction and tabu search for graph partitioning.
The Graph Partioning Problem (GPP) is a combinatorial optimization
problem where: given a graph with an even number of nodes, find a
partition into half of the nodes that minimizes the number of edges
crossing it to the other partition.
This file contains a set of functions to illustrate:
- diversification/intensification
- div/intens tabu search
Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2007
"""
LOG = False # whether or not to print intermediate solutions
import random
from sys import maxint
Infinity = 1.e10000
from graphtools import *
from gpp_ts import *
def diversify(sol):
"""Diversify: keep a part of the solution with random size.
The solution is represented by a vector:
- sol[i]=0 - node i is in partition 0
- sol[i]=1 - node i is in partition 1
"""
ind1 = [i for i in nodes if sol[i] == 1]
ind0 = [i for i in nodes if sol[i] == 0]
random.shuffle(ind1)
random.shuffle(ind0)
n = len(sol)/2
start = int(random.random()*n)
for i in range(start,n):
bit = int(random.random() + .5)
sol[ind0[i]] = bit
sol[ind1[i]] = 1-bit
def ts_intens_divers(nodes, adj, sol, max_iter, tabulen, report):
"""Execute a tabu search run, with intensification/diversification."""
assert len(nodes)%2 == 0 # graph partitioning is only for graphs with an even number of nodes
cost, s, d = evaluate(nodes, adj, sol)
tabu = [0 for i in nodes]
bestcost = Infinity
lastcost = Infinity
D = 1
count = 0
for it in range(max_iter):
if LOG:
print "tabu search, iteration", it
print "initial sol: ", sol
cost += move(1, nodes, adj, sol, s, d, tabu, tabulen, it)
if LOG:
print "intermediate sol:", sol
cost += move(0, nodes, adj, sol, s, d, tabu, tabulen, it)
if LOG:
print "completed sol: ", sol
if cost < bestcost:
bestcost = cost
bestsol = list(sol)
if report:
report(bestcost, "it:%d"%it)
if LOG:
print "*** intensifying ***"
tabu = [0 for i in nodes]
count = 0
elif cost < lastcost:
count = 0
else:
count += 1
if count > D:
count = 0
if LOG:
print "*** diversifying ***"
tabu = [0 for i in nodes]
sol = list(bestsol)
diversify(sol)
cost, s, d = evaluate(nodes, adj, sol)
D += 1
if LOG:
print count, D, "iteration", it, "cost", cost, "/ best:", bestcost # , "\t", sol
lastcost = cost
return bestsol, bestcost
if __name__ == "__main__":
import sys
if len(sys.argv) == 1:
instance = "randomly created"
nodes,adj = rnd_adj_fast(100,.5)
rndseed = 1
max_iterations = 1000
tabulen = len(nodes)/2
elif len(sys.argv) == 5:
instance = sys.argv[1]
rndseed = int(sys.argv[2])
tabulen = int(sys.argv[3])
max_iterations = int(sys.argv[4])
nodes,adj = read_gpp_graph(instance)
else:
print "usage:", sys.argv[0], "instance seed tabulen iterations"
exit(-1)
# print "nodes:", nodes
# print "adjacencies", adj
random.seed(rndseed)
sol = construct(nodes)
# print "initial partition:", sol
# function for printing best found solution when it is found
from time import clock
init = clock()
def report_sol(obj,s=""):
print "cpu:%g\tobj:%g\t%s" % \
(clock(), obj, s)
print "*** graph partitioning problem ***"
print
print "instance", instance
# print "nodes:", nodes
# print "adjacencies", adj
sol = construct(nodes)
z,s,d = evaluate(nodes, adj, sol)
print "initial partition: z =", z
print sol
print
print "starting tabu search,", max_iterations, "iterations, tabu length =", tabulen
sol, cost = ts_intens_divers(nodes, adj, sol, max_iterations, tabulen, report_sol)
print "final solution: z=", cost
print sol