Source code for optim

#!/usr/bin/python
# -*- coding: utf-8 -*-
"""
optimization algorithms
"""
__author__ = "Philippe Guglielmetti"
__copyright__ = "Copyright 2012, Philippe Guglielmetti"
__credits__ = ["http://www.psychicorigami.com/category/tsp/",]
__license__ = "LGPL"

import random
import math
import logging

import itertools2

[docs]def hillclimb(init_function,move_operator,objective_function,max_evaluations): ''' hillclimb until either max_evaluations is reached or we are at a local optima ''' best=init_function() best_score=objective_function(best) num_evaluations=1 logging.info('hillclimb started: score=%f',best_score) while num_evaluations < max_evaluations: # examine moves around our current position move_made=False for next in move_operator(best): if num_evaluations >= max_evaluations: break # see if this move is better than the current next_score=objective_function(next) num_evaluations+=1 if next_score > best_score: best=next best_score=next_score move_made=True break # depth first search if not move_made: break # we couldn't find a better move (must be at a local maximum) logging.info('hillclimb finished: num_evaluations=%d, best_score=%f',num_evaluations,best_score) return (num_evaluations,best_score,best)
[docs]def hillclimb_and_restart(init_function,move_operator,objective_function,max_evaluations): ''' repeatedly hillclimb until max_evaluations is reached ''' best=None best_score=0 num_evaluations=0 while num_evaluations < max_evaluations: remaining_evaluations=max_evaluations-num_evaluations logging.info('(re)starting hillclimb %d/%d remaining',remaining_evaluations,max_evaluations) evaluated,score,found=hillclimb(init_function,move_operator,objective_function,remaining_evaluations) num_evaluations+=evaluated if score > best_score or best is None: best_score=score best=found return (num_evaluations,best_score,best)
[docs]def P(prev_score,next_score,temperature): if next_score > prev_score: return 1.0 else: return math.exp( -abs(next_score-prev_score)/temperature )
[docs]class ObjectiveFunction: '''class to wrap an objective function and keep track of the best solution evaluated'''
[docs] def __init__(self,objective_function): self.objective_function=objective_function self.best=None self.best_score=None
[docs] def __call__(self,solution): score=self.objective_function(solution) if self.best is None or score > self.best_score: self.best_score=score self.best=solution logging.info('new best score: %f',self.best_score) return score
[docs]def kirkpatrick_cooling(start_temp,alpha): T=start_temp while True: yield T T=alpha*T
[docs]def anneal(init_function,move_operator,objective_function,max_evaluations,start_temp,alpha): # wrap the objective function (so we record the best) objective_function=ObjectiveFunction(objective_function) current=init_function() current_score=objective_function(current) num_evaluations=1 cooling_schedule=kirkpatrick_cooling(start_temp,alpha) logging.info('anneal started: score=%f',current_score) for temperature in cooling_schedule: done = False # examine moves around our current position for next in move_operator(current): if num_evaluations >= max_evaluations: done=True break next_score=objective_function(next) num_evaluations+=1 # probablistically accept this solution # always accepting better solutions p=P(current_score,next_score,temperature) if random.random() < p: current=next current_score=next_score break # see if completely finished if done: break best_score=objective_function.best_score best=objective_function.best logging.info('final temperature: %f',temperature) logging.info('anneal finished: num_evaluations=%d, best_score=%f',num_evaluations,best_score) return (num_evaluations,best_score,best)
[docs]def reversed_sections(tour): '''generator to return all possible variations where the section between two cities are swapped''' for i,j in itertools2.all_pairs(len(tour)): if i and j and i < j: copy=tour[:] copy[i:j+1]=reversed(tour[i:j+1]) yield copy
[docs]def swapped_cities(tour): '''generator to create all possible variations where two cities have been swapped''' for i,j in itertools2.all_pairs(len(tour)): if i < j: copy=tour[:] copy[i],copy[j]=tour[j],tour[i] yield copy
[docs]def tour_length(points,dist,tour=None): """generator of point-to-point distances along a tour""" if not tour:tour=range(len(points)) #will generate the closed tour length n=len(tour) for i in range(n): j=(i+1)%n yield dist(points[tour[i]],points[tour[j]])
[docs]def tsp(points,dist,max_iterations=100,start_temp=None,alpha=None,close=True,rand=True): """Travelling Salesman Problem @see http://en.wikipedia.org/wiki/Travelling_salesman_problem @param points : iterable containing all points @param dist : function returning the distance between 2 points : def dist(a,b): @param max_iterations :max number of optimization steps @param start_temp, alpha : params for the simulated annealing algorithm. if None, hill climbing is used @param close : computes closed TSP. if False, open TSP starting at points[0] @return iterations,score,best : number of iterations used, minimal length found, best path as list of indexes of points """ import optim, random n=len(points) def init_function(): tour=range(1,n) if rand: random.shuffle(tour) return [0]+tour def objective_function(tour): """total up the total length of the tour based on the dist ance function""" return -sum(tour_length(points,dist,tour if close else tour[:-1])) if start_temp is None or alpha is None: iterations,score,best=optim.hillclimb_and_restart(init_function,reversed_sections,objective_function,max_iterations) else: iterations,score,best=optim.anneal(init_function,reversed_sections,objective_function,max_iterations,start_temp,alpha) return iterations,score,best
if __name__ == "__main__": import logging #logging.basicConfig(level=logging.INFO) words=['geneva','london','new-york','paris','tokyo','rome','zurich','bern','berlin','mokba','washington','wien','biel'] n=2000 from math2 import levenshtein iterations,score,best=tsp(words,levenshtein,n) print('TSP hill climbing closed score=%d, best=%s'%(score,[words[i] for i in best])) iterations,score,best=tsp(words,levenshtein,n,2,.9) print('TSP annealing closed score=%d, best=%s'%(score,[words[i] for i in best])) iterations,score,best=tsp(words,levenshtein,n,close=False) print('TSP hill climbing open score=%d, best=%s'%(score,[words[i] for i in best])) iterations,score,best=tsp(words,levenshtein,n,2,.9,close=False) print('TSP annealing open score=%d, best=%s'%(score,[words[i] for i in best]))