frigidum 0.4.0

Simulated Annealing using tqdm

Simulated Annealing package for Python using tqdm

• Flat structure (no class definition needed to describe problem).
• Using tqdm for progress statistics.
• Return statistics of used neighbour functions.

Installation

pip install frigidum

Dependencies

• tqdm 3.4.0 or later.
• For some examples, numpy is required. numpy is not set as a requirement and therefore is not installed during installation.

Basic Example

import frigidum

import random

def random_start():
    return 10**4 + random.random()

def random_small_step(x):
    return x + 0.1 * (random.random() - .2)

def random_big_step(x):
    return x + 10 * (random.random() - .2)

def obj(x):
    return x**2

local_opt = frigidum.sa(random_start=random_start, 
                        neighbours=[random_small_step, random_big_step], 
                        objective_function=obj, 
                        T_start=10**5, 
                        T_stop=0.000001, 
                        repeats=10**4, 
                        copy_state=frigidum.annealing.naked)

Usage

Arguments

• random_start : function which returns a random start / state.
• objective_function : objective function to minimize.
• neighbours : list of neighbour functions, for one use [neighbour]. For each proposal, a neighbour is randomly selected (equal weights).
• T_start : Starting temperature.
• T_stop : Stopping temperature.
• O_stop : Stopping criterea, stop when Objective Functions reaches O_stop or lower (default set to None).
• alpha : Lower temperature by this factor, after repeats proposals.
• repeats : at each temperature lowering by factor alpha, do repeats proposals.
• copy : frigidum.annealing.copy, frigidum.annealing.deepcopy, frigidum.annealing.naked, or custom - the copy method.
• post_annealing : Function to call on state after annealing is finished. Usually attempt to prettify or improve solution.

Output & Return

• During annealing; prints the
  • Temperature T.
  • Movements proportion M, e.g. 0.1 means 10% of all proposal got accepted and changed the objective value in the last repeats.
  • Minimum Found Objective value O_min and last accepted Objective value O_current
• During annealing; progress statistics provided by tqdm, such as estimated remaining time.
• returns tuple (best_found_state, objective_function(best_found_state) ) when done.

Movements

A movement is a when a proposed state is accepted, and the objective function has changed. For each batch of repeats, the proportion of movements are displayed. The number of movements differ with the number of accepted proposals, as a accepted proposal might not necessary change the objective function value.

• In the early phase of annealing, movements should happen >90%.

• In the last phase of annealing, movements should happen <10%.

Movements are useful to determine the starting- and stopping temperature; T_start & T_stop, with the above guidelines.

Copy'ing of States

3 most important copy methods are included in the annealing module,

def copy(state):
	return state.copy()

def deepcopy(state):
	return state.deepcopy()

def naked(state):
	return state

In the example, naked with the argument copy_state=frigidum.annealing.naked is used,

• use copy_state=frigidum.annealing.copy for copy(),
• use copy_state=frigidum.annealing.deepcopy for deepcopy(),
• use copy_state=frigidum.annealing.naked if a = b would already create a copy, or if the neighbour function return copies.

Bag of Tricks for Simulated Annealing

The following bag-of-tricks for simulated annealing have sometimes proven to be useful in some cases.

• Movements-to-set-Temperature - Use the movements statistics to set the starting and stopping temperature.
• Neighbours-have-Impact - Focus on the neighbour function, not the cooling scheme or acceptance variations.
• Objective-has-Impact - The objective, or proxy for objective, also can have major impact on the annealing.
• Human-inspired-Neighbours - To get inspiration for random neighbours, try solve a similar problem yourself.
• Neighbour-Combinations - Try multiple neighbours together, combinations usually work well. The neighbours argument expects a list of neighbours. After a run, statistics are displayed. Don't discard a neighbour just by its statistics, it might be a catalyst for a different neighbours.
• Coarse-Neighbours - Try add neighbours, that might work well when warm (large simple steps).
• Smooth-Neighbours - Try add neighbours, that might work well when cold (small steps/smart steps).
• Local-Opt-Neighbours - Try add neighbours, that find a hyper local minima with local greedy algorithm.
• Delete-and-Fix-Neighbours - Try add neighbours, that deletes/removes a local solution and fix it again.
• Brazen-Overwrite-Neighbours - Try add neighbours, that overwrite a part of the solution rigorously.
• Stay-within-Contraints-When-Possible - When conditions apply, stay within the feasible zone when possible / easy. Going back from an infeasible solution to feasible can be difficult.
• Prevent-Optimize-Both-Objective-and-Condition - Only anneal on either condition or objective, not both at the same time. Often, a condition can be constructed as a penalty objective which have to become 0.
• It is difficult to predict the effect of a random neighbours, or their parameters, ideas usually don't survive the outcome of experiments.

Examples

The Rastrigin Function in 2 Dimensions

https://en.wikipedia.org/wiki/Rastrigin_function

import frigidum

from frigidum.examples import rastrigin

frigidum.sa(random_start=rastrigin.random_start,
           objective_function=rastrigin.rastrigin_function,
           neighbours=[rastrigin.random_small_step, rastrigin.random_big_step],
           copy_state=frigidum.annealing.naked,
           T_start=100,
           T_stop=0.00001,
           repeats=10**4)

The Traveling Salesman Problem (TSP) on pcb442

Requires numpy

https://en.wikipedia.org/wiki/Travelling_salesman_problem

The pcb442 is a TSP problem instance with 442 cities/vertices, from http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html. The known solution tsp.opt_sol has objective function value of about 50783.54.

Note we use post_annealing = tsp.local_search_2opt to possibly improve the solution with the 2-opt algorithm (https://en.wikipedia.org/wiki/2-opt), after annealing is done. This is a example of how the post_annealing argument can be used, as Simulated Annealing's output has sometimes 'raw' edges that can use fixing.

import frigidum

from frigidum.examples import tsp

local_opt = frigidum.sa(random_start=tsp.random_start,
           objective_function=tsp.objective_function,
           neighbours=[tsp.euclidian_bomb_and_fix, tsp.euclidian_nuke_and_fix, tsp.route_bomb_and_fix, tsp.route_nuke_and_fix, tsp.random_disconnect_vertices_and_fix],
           copy_state=frigidum.annealing.naked,
           T_start=10**5,
           alpha=.92,
           T_stop=0.001,
           repeats=10**2,
           post_annealing = tsp.local_search_2opt)

The Knapsack Problem

Requires numpy

https://en.wikipedia.org/wiki/Knapsack_problem

The Problem instance is the largest in number of items (10.000) taken from the Discrete Optimization course from Professor Pascal Van Hentenryck & Dr. Carleton Coffrin. The original data file is ks_10000_0. https://www.coursera.org/learn/discrete-optimization

An greedy approach would give a bag value of 1097042 (sorted by value/kg, added till full). The best known bag value is 1099893, found with Branch & Bound.

The objective function has been multiplied by -1 to engineer this maximisation problem into a minimisation problem.

The selection process of new items is randomly, and uses the relative value of items (value/kg) to prioritize items with higher value over lower.

The selection process of items to discard is also randomly, prioritizing items wih low relative value (value/kg).

import frigidum

from frigidum.examples import knapsack

local_opt = frigidum.sa(random_start=knapsack.random_knapsack,
           objective_function=knapsack.objective_function,
           neighbours=[knapsack.reconsider_few_items, knapsack.reconsider_many_items],
           copy_state=frigidum.annealing.naked,
           T_start=10**7,
           alpha=.9,
           T_stop=500,
           repeats=25)

The Graph Coloring Problem (GCP) on DSJC1000.9

Requires numpy

DSJC1000.9.col is a Graph Coloring Benchmark Instance from https://turing.cs.hbg.psu.edu/txn131/graphcoloring.html. It has 1000 nodes, 449449 edges. "Variations on Memetic Algorithms for Graph Coloring Problems" reports a solution exists of 222 colors, https://arxiv.org/abs/1401.2184.

The greedy 'Welsh and Powell' algorithm will find a solution of about 300 colors (depeding on second level sorting of vertices). This is implemented in the gcp.welsh_and_powell() function.

A objective/neighbourhood strategy is used, that is conservative on using colors. Instead of starting with K colors, and use annealing to get to K - 1 colors, we start with only using a few colors, and only add a color after a threshold vertices/color is obtained.

The rational behind is that it is difficult to put the 'devil back in the box', where the devil in this analogy is the color you want to get rid off.

Annealing color by color gives more room to move around, but this idea is not tested properly against a more general sum of squares of color classes, which start with K colors and try to reduce the number of colors.

This method requires that the number of maximum colors used is fixed at the start, and in the example below we aim for 250.

We use O_stop=0 to stop the annealing when an colering has been found, a stopping criterea on the Objective function.

import frigidum
from frigidum.examples import gcp

gcp.set_goal_colors(250)
print( "Trying to color DSJC1000.9 in {} colors".format(gcp.goal_number_of_colors) )

local_opt = frigidum.sa(random_start=gcp.random_start,
       objective_function=gcp.squared_classes,
       neighbours=[gcp.force_add_random_vertex,
       gcp.parallel_add_random_vertex,
       gcp.force_add_random_vertex_on_low_used_color,
       gcp.force_add_random_vertex_on_low_used_color,
       gcp.check_free_vertex_recoloring,
       gcp.check_free_vertex_recoloring,
       gcp.massive_try_single_vertex,
       gcp.kempe_chain_swap],
       copy_state=frigidum.annealing.naked,
       T_start=10,
       alpha=.999,
       T_stop=0.05,
       O_stop=0,
       repeats=10**2)