Code samples for Simulated Annealing

README.md

Download the following files and keep them inside the same directory.

• launch.sh
• plot.py
• anneal.c
• [arXiv-1305-5837v1.tar.gz] http://arxiv.org/src/1305.5837v1

To launch the annealing algorithm, use the following command: bahs launch.sh

anneal.c

/**
 * Simulated annealing algorithm for the D-Wave problem
 * Copyright (C) 2014 Anirudha Bose
 * Code released under the The MIT License (MIT)
 */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

/* Simulated annealed algorithm parameters */
#define INITIAL_TEMPERATURE	0.0012
#define COOLING_STEPS		100000
#define COOLING_FACTOR		0.999997
#define HIDDEN_ENERGY		512  /* Hidden potential energy to increase success probability */
#define POTENTIAL_ENERGY	1024 /* Add some potential energy to the Hamiltonian to keep it positive */

/* D-Wave parameters */
#define QUBITS_NUM		108  /* Number of qubits used in D-Wave Benchmarks */
#define COUPLINGS		255  /* Number of couplings in each instance */

int Z[QUBITS_NUM];
int nodes[COUPLINGS][3];
int actualHamiltonian;
int optimalHamiltonian;

void dataBinaryCouplings(void)
{
    int i,j,k;
    scanf("%d\n", &actualHamiltonian);
    for (k=0; k<COUPLINGS; k++)
    {
        scanf("%d %d %d\n",&i,&j,&nodes[k][2]);
        nodes[k][0] = i-1;
        nodes[k][1] = j-1;
    }
}

int getHamiltonian(void)
{
    int k, H=POTENTIAL_ENERGY;
    for(k=0; k<COUPLINGS; k++)
        H -= nodes[k][2] * Z[nodes[k][0]] * Z[nodes[k][1]];
    return H;
}

void initQubits(void)
{
    int i;
    /*For details about the pseudo-random number generator used, see http://stackoverflow.com/a/7343909 */
    srand(time(NULL));
    struct timeval t1;
    gettimeofday(&t1, NULL);
    srand(t1.tv_usec * t1.tv_sec);
    for (i=0; i<QUBITS_NUM; i++)
        Z[i] = rand()%2 ? 1 : -1;
}

int anneal(void)
{
    int i;
    double threshold;
    double T;
    int currentHamiltonian;
    int dH;
    int randomQubit = 0;

    T = INITIAL_TEMPERATURE;
    currentHamiltonian   = HIDDEN_ENERGY + POTENTIAL_ENERGY;
    optimalHamiltonian   = currentHamiltonian;

    for (i=0; i<COOLING_STEPS; i++)
    {
        randomQubit = rand()%QUBITS_NUM;
        Z[randomQubit] = -1 * Z[randomQubit];
        dH = getHamiltonian() - currentHamiltonian;
        if(dH < 0)
        {
            currentHamiltonian = currentHamiltonian + dH;
            T *= COOLING_FACTOR;
        }
        else
        {
            threshold = expf(-(float)dH/(currentHamiltonian * T));
            if (threshold > rand()/(float)RAND_MAX)
            {
                currentHamiltonian = currentHamiltonian + dH;
                if (dH == 0)
                    T *= (1-(1-COOLING_FACTOR)/7.0);
            }
            else
                Z[randomQubit] = -1 * Z[randomQubit]; /* Go back to initial state of Z */
        }

        if (currentHamiltonian < optimalHamiltonian)
            optimalHamiltonian = currentHamiltonian;
    }
    return optimalHamiltonian;
}

int main(void)
{
    dataBinaryCouplings();
    initQubits();
    int predictedHamiltonian = anneal();
    (actualHamiltonian == predictedHamiltonian - POTENTIAL_ENERGY) ? printf("SUCCESS\n") : printf("FAILURE\n");
    return 0;
}

launch.sh

#!/bin/bash

echo "Create directory: arXiv-1305-5837v1"
mkdir -pv arXiv-1305-5837v1

echo "Create directory: probability_graphs"
mkdir -pv probability_graphs

echo "Extracting archive: arXiv-1305-5837v1.tar.gz"
tar xf arXiv-1305-5837v1.tar.gz -C arXiv-1305-5837v1

echo "Compile: anneal.c"
gcc -O4 -Wno-unused-result -o anneal anneal.c -lm

for file in arXiv-1305-5837v1/anc/instances/*.txt ; do
    energy=$(cat $file | head -1)
    sed -i "s|$energy|${energy/* }|g" $file
    count=1
    success=0
    echo "Run annealing with file: $file"
    while [ $count != 100 ]; do
	if [ $(./anneal < $file) == "SUCCESS" ]; then
		((success++))
	fi
	((count++))
    done
    echo "Success probability: $success"
    echo ""
    echo $success >> arXiv-1305-5837v1/anc/predicted_success.csv
done

echo "Plotting graphs..."
python plot.py

echo "Cleanup"
echo "Remove directory: arXiv-1305-5837v1"
rm -Rf arXiv-1305-5837v1

rm -f *~

echo "Remove file: anneal"
rm -f anneal

echo "Done"

plot.py

#!/usr/bin/env python

import numpy as np
import matplotlib.pyplot as plt
import csv

def autolabel(rects):
    for rect in rects:
        height = rect.get_height()
        ax.text(rect.get_x()+rect.get_width(), 1.05*height, height,
                ha='center', va='bottom')

success_dwave = open('arXiv-1305-5837v1/anc/success.txt', 'r')
success_dwave_csv = open('arXiv-1305-5837v1/anc/actual_success.csv', 'w')
for each in success_dwave:
    success_dwave_csv.write(each.split()[1] + '\n')
success_dwave_csv.close()

n_groups = 5
i = 0
while i<= 995:
    sa = np.genfromtxt('arXiv-1305-5837v1/anc/predicted_success.csv')[i:i+5]/100.0
    qa = np.genfromtxt('arXiv-1305-5837v1/anc/actual_success.csv')[i:i+5]

    fig, ax = plt.subplots()

    index = np.arange(n_groups)
    bar_width = 0.1
    opacity = 0.4

    rects1 = plt.bar(index, sa, bar_width, alpha=opacity, color='b', label='Simulated Annealing')
    rects2 = plt.bar(index + bar_width, qa, bar_width, alpha=opacity, color='r', label='Quantum Annealing')

    plt.xlabel('Benchmark')
    plt.ylabel('Success Probability')
    plt.title('Performance Benchmarking')

    benchmark = open('arXiv-1305-5837v1/anc/success.txt', 'r')
    benchmark_list = []
    for each in benchmark:
        benchmark_list.append('-'.join(each.split()[0].replace('.mat', '').split('-')[-3:]))
    benchmark.close()

    lab = benchmark_list[i:i+5]
    plt.xticks(index + bar_width, lab)
    plt.legend()
    plt.tight_layout()

    plt.savefig('probability_graphs/' + str(i+1) + '-' + str(i+5) + '.png')
    plt.close()
    i=i+5