In [1]:

    

%matplotlib inline


    

    




/home/christian/.virtualenvs/vpr-x64/local/lib/python2.7/site-packages/matplotlib/__init__.py:740: UserWarning: Found matplotlib configuration in ~/.matplotlib/. To conform with the XDG base directory standard, this configuration location has been deprecated on Linux, and the new location is now '/home/christian/.config'/matplotlib/. Please move your configuration there to ensure that matplotlib will continue to find it in the future.
  _get_xdg_config_dir())

In [2]:

    

from collections import OrderedDict

import numpy as np
import pandas as pd
from IPython.display import display
from IPython.html.widgets import IntSliderWidget, ContainerWidget
import matplotlib.pyplot as plt


    

In [3]:

    

def tour_cost(tour):
    left_city = tour[range(-1, cities_count - 1)]
    left_pairs = np.array([tour, left_city])
    left_pair_costs = np.array([distances[tuple(p)] for p in left_pairs.T])
    return left_pair_costs.sum()


def city_costs(tour):
    left_city = tour[range(-1, cities_count - 1)]
    right_city = tour[range(-cities_count + 1, 1)]
    left_pairs = np.array([tour, left_city])
    right_pairs = np.array([tour, right_city])
    left_pair_costs = np.array([distances[tuple(p)] for p in left_pairs.T])
    right_pair_costs = np.array([distances[tuple(p)]
                                 for p in right_pairs.T])
    return left_pair_costs + right_pair_costs


def city_delta_costs(tour, proposed_moves):
    pre_costs = city_costs(tour)
    left_city = tour[np.arange(-1, cities_count - 1) + proposed_moves]
    right_city = tour[np.arange(-cities_count + 1, 1) + proposed_moves]
    left_pairs = np.array([tour, left_city])
    right_pairs = np.array([tour, right_city])
    left_pair_costs = np.array([distances[tuple(p)] for p in left_pairs.T])
    right_pair_costs = np.array([distances[tuple(p)]
                                 for p in right_pairs.T])
    return (left_pair_costs + right_pair_costs) - pre_costs


    

In [4]:

    

class MovePattern(object):
    def __init__(self, magnitude, shift=0):
        self.magnitude = magnitude
        self.double_magnitude = 2 * magnitude
        self.shift = shift

    def __getitem__(self, i):
        if self.magnitude == 0:
            return 0
        index = (i + 2 * self.double_magnitude -
                 ((self.shift + self.magnitude + 1) % self.double_magnitude))
        if (index % self.double_magnitude) < self.magnitude:
            return self.magnitude
        else:
            return -self.magnitude
        
        
def random_pattern_params(max_magnitude, extent, non_zero=True):
    max_magnitude = min(extent - 1, max_magnitude)
    magnitude = np.random.randint(0, max_magnitude + 1)
    while non_zero and magnitude == 0:
        magnitude = np.random.randint(0, max_magnitude + 1)

    shift = 0

    if magnitude > 0:
        max_shift = 2 * magnitude - 1
        if extent <= 2 * magnitude:
            max_shift = magnitude - 1
        shift = np.random.randint(max_shift + 1)

    return magnitude, shift


    

In [5]:

    

def propose_moves(cities_count, max_distance=None):
    if max_distance is None:
        max_distance = cities_count - 1
    max_distance = min(max_distance, cities_count - 1)
    pattern_params = random_pattern_params(max_distance, cities_count - 1)
    move_pattern = MovePattern(*pattern_params)
    proposed_moves = [move_pattern[i] for i in xrange(cities_count)]
    proposed_moves = [m if i + m >= 0 and i + m < cities_count else 0
                      for i, m in enumerate(proposed_moves)]
    return proposed_moves


    

In [6]:

    

def iterate_search(tour, max_distance=None):
    proposed_moves = propose_moves(len(tour), max_distance=max_distance)
    delta_costs = city_delta_costs(tour, proposed_moves)

    associated_move_pair_ids = np.array([i if m > 0 else i + m if m < 0 else -1
                                         for i, m in enumerate(proposed_moves)])
    sorted_by_move_pair = np.argsort(associated_move_pair_ids)

    min_index = np.where(associated_move_pair_ids
                         [sorted_by_move_pair] >= 0)[0][0]

    move_pair_ids = (associated_move_pair_ids
                     [sorted_by_move_pair[min_index::2]])
    delta_costs[move_pair_ids] = (
        delta_costs[sorted_by_move_pair[min_index::2]] +
        delta_costs[sorted_by_move_pair[min_index + 1::2]])
    try:
        assessments = np.array([delta_costs[i] <= 0
                                if i >= 0 else False
                                for i in associated_move_pair_ids])
    except:
        print 'i:', i
        print associated_move_pair_ids
        print deltas_by_move_pair
        raise
    new_tour = tour[np.arange(cities_count) * ~assessments +
                    (np.arange(cities_count) + proposed_moves) * assessments]
    return new_tour


    

In [7]:

    

cities_count_slider = IntSliderWidget(min=10, max=1000, value=100,
                                      description='Cities count')
seed_slider = IntSliderWidget(min=1, max=1000, value=42, description='Seed')
display(cities_count_slider)
display(seed_slider)


    

In [8]:

    

seed = seed_slider.value
cities_count = cities_count_slider.value

np.random.seed(seed)

distinct_pairs = [(i, j)
                  for i in xrange(cities_count)
                  for j in xrange(i + 1, cities_count)]
distances_dict = OrderedDict(zip(distinct_pairs,
                                 np.random.randint(0, 100,
                                                   cities_count *
                                                   (cities_count - 1) / 2)))
distances = np.zeros((cities_count, cities_count), dtype=int)
# distances[map(list, distances_dict.keys())] = distances_dict.values()
distances[zip(*distances_dict.keys())] = distances_dict.values()
distances.T[zip(*distances_dict.keys())] = distances_dict.values()


    

In [9]:

    

tour = np.arange(cities_count)
np.random.shuffle(tour)


    

In [10]:

    

starting_cost = tour_cost(tour)
starting_cost


    

    
Out[10]:





4696

In [11]:

    

costs = [starting_cost]
for i in xrange(200):
    tour = iterate_search(tour)
    costs.append(tour_cost(tour))


    

In [12]:

    

plt.plot(costs)
display(costs[0])
display(costs[-1])


    

    






4696






    






1512






    




/home/christian/.virtualenvs/vpr-x64/local/lib/python2.7/site-packages/matplotlib/font_manager.py:1236: UserWarning: findfont: Font family ['monospace'] not found. Falling back to Bitstream Vera Sans
  (prop.get_family(), self.defaultFamily[fontext]))