A C++ implementation of the Simulated Annealing algorithm

In this article, the C++ code implementation of the "More Pizza" algorithm is provided and commented. The complete source file is available.

Introduction

The idea behind the Simulated Annealing algorithm used to solve the “More Pizza” problem is very simple: starting from a randomly chosen solution, this is further improved until a stop condition is met (e.g., the maximum score is achieved).

The description of the “More Pizza” algorithm have been provided in a previous post.

In this article, the C++ code implementation of that algorithm is provided and commented.

The main() function

Independently of the used approach, it is expected that these steps are followed:

  1. Reading of the input parameters (input file name, specific procedure parameters, etc. ).
  2. Reading of input data and storage of the information in a proper data structure.
  3. The solving procedure.
  4. Validation of the result (optional, as it is done by Google itself)
  5. Output of the solution to a file (if not already done in the solving procedure).

A set of global variables have been defined at the very top of the script:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <chrono>
#include <map>
#include <set>
#include <random>
#include <memory>
using namespace std;
// Default input and output filenames 
string iFileName{ "..\\a_example.in" };
string oFileName{ "..\\a_example.out" };
// Max number of slices (capacity)
int32_t M{ 0 };
// Number available of pizzas
int32_t N{ 0 };
using TSol = vector<int32_t>; // it is used for both pizzas and solution
TSol pizzas{}; // storing number of slices of each pizza
// Random numbers generator
std::random_device rd;
std::mt19937 g(rd());
std::uniform_int_distribution<int32_t> rnProbValue(0, 100);
std::uniform_real_distribution<double> rnProb(0, 1);
// Number of neighbors to check
int32_t numMaxItemsToCheck{ 5u };
double T0 = 10000.0; // Default initial temperature
double ae = 0.000001; // Default reduction factorCode language: PHP (php)

The structure of the main() function replicates the steps listed above.

int main(int argc, char* argv[])
{
    // Reading input parameters
    for (int i = 0; i < argc; i++)
    {
        cout << "argv[" << i << "] = " << argv[i] << endl;
    }
    if (argc > 1)
    {
        iFileName = argv[1];
        oFileName = iFileName;
        oFileName.append(".out");
        if (argc >= 3)
        {
            T0 = std::atof(argv[2]);
            if (argc >= 4)
            {
                numMaxItemsToCheck = std::atoi(argv[3]);
                if (argc >= 5)
                {
                    ae = std::atof(argv[4]);
                }
            }
        }
    }
    std::cout << "input file: " << iFileName << endl;
    std::cout << "output file: " << oFileName << endl;
    std::cout << "initial temperature: " << T0 << endl;
    std::cout << "alpha exp: " << ae << endl;
    std::cout << "num neighbours: " << numMaxItemsToCheck << endl;
    // Read data from input file
    readInput();
    auto start = chrono::steady_clock::now();
    orderPizzas();
    auto end = chrono::steady_clock::now();
    cout << "Elapsed time in milliseconds : "
        << chrono::duration_cast<chrono::milliseconds>(end - start).count()
        << " ms" << endl;
    return 0;
}Code language: C++ (cpp)

The validation of the solution and the saving of the solution to a file are part of the procedure itself. In fact, it is expected that each calculated solution is also valid. In addition, if the new solution improves the current result, then it should be saved to a file too.

Reading data from a file

The following code has been implemented to read the input file. The first two integers represent the maximum number of slices (i.e., the maximum score) and the number of pizzas respectively. The remaining N integers represent the number of each pizza.

// Read input data from a file
void readInput()
{
    ifstream iFile;
    iFile.open(iFileName);
    iFile >> M; // Maximum number of slices (i.e., max score)
    iFile >> N; // Number of pizzas
    std::cout << "Max. num. slices: " << M << endl;
    std::cout << "N. pizzas: " << N << endl;
    //init pizzas vector
    pizzas.reserve(N);
    for (int32_t i = 0; i < N; i++)
    {
        int32_t tmpPizza{};
        iFile >> tmpPizza;
        pizzas.emplace_back(tmpPizza);
    }
    iFile.close();
    pizzas.shrink_to_fit();
    std::cout << "DONE!" << endl;
}Code language: C++ (cpp)

The solution class

I preferred to represent the solution inside a class to:

  • store the actual solution.
  • store the score of the solution.
  • save the “state” of a solution (e.g., which pizzas can be added to the current solution).
  • implement utility functions to:
    • create an empty solution (i.e., having zero score).
    • create a random solution.
    • change the current solution in a random way (please, check mutate() function).
    • calculate the score of the solution (please, check score() function).
    • save the solution into a file with the required format (please, check the function saveSolutionToFile() ).
    • print the current solution to screen
// Container used to store the solution
// including its "state". The state of
// a solution is required to quickly change it
// and generate a new "neighbour"
struct TSolCnt
{
    // This constructor is used to create an empty solution
    TSolCnt() : sol{}, score{0}, availablePizzas(N,0)
    {
        // Initially, all pizzas are available
        for (int i = 0; i < N; i++)
        {
            availablePizzas[i]=i;
        }
    }
    // Constructor used to make an initial random solution
    TSolCnt( std::uniform_int_distribution<>& rnPizzaID ) :
        sol(), // empty solution
        score(0), // initial score
        availablePizzas(N,0)
    {
        // Initially, all pizzas are available
        for (int i = 0; i < N; i++)
        {
            availablePizzas[i] = i;
        }
        // Pizzas that cannot be used will be stored at the end of this vector
        std::sort(availablePizzas.begin(), availablePizzas.end(),[&](int a, int b)
        {
            return (M - (score + pizzas[a])) > (M - (score + pizzas[b]));
        });
        while ( score < M &&
            ( !availablePizzas.empty() && ( M - ( score + pizzas[availablePizzas.front()]))>0 ))
        {
            auto it_end = std::find_if(availablePizzas.cbegin(),
                availablePizzas.cend(),
                [&](int idx) {
                    return (M - (score + pizzas[idx])) < 0;
                });
            const auto numElToCheck = std::distance(availablePizzas.cbegin(), it_end);
            const int32_t avIdx = rnPizzaID(g) % numElToCheck;
            const auto searchIt = std::next(availablePizzas.cbegin(), avIdx);
            const int32_t searchIdx = *searchIt;
            if ( (pizzas[searchIdx] + score) <= M)
            {
                sol.emplace_back(searchIdx);
                score += pizzas[searchIdx];
                availablePizzas.erase(searchIt);
                cout << "searchIdx: " << searchIdx << ", score: " << score << "\t\r";
                // Sorting indexes by our criteria in descending order
                std::sort(availablePizzas.begin(), availablePizzas.end(), [&](int a, int b)
                {
                    return (M - (score + pizzas[a])) > (M - (score + pizzas[b]));
                });
                // Sorting indexes
                std::sort(sol.begin(), sol.end());
            }
        }
    }
    TSolCnt& operator= (const TSolCnt& rhs)
    {
        score = rhs.score;
        sol.assign(rhs.sol.begin(), rhs.sol.end());
        availablePizzas = rhs.availablePizzas;
        return *this;
    };
    void mutate(
        std::uniform_int_distribution<int32_t>& rnPizzaID,
        const int32_t maxNumRemovals)
    {
        const int32_t oldSize = static_cast<int32_t>(sol.size());
        int32_t numRemovals = 0;
        do
        {
            // find a pizza to remove
            const int32_t searchIdx = sol[rnPizzaID(g) % sol.size()];
            // update set of available pizzas
            availablePizzas.emplace_back(searchIdx);
            // update solution and its score
            score -= pizzas[searchIdx];
            auto it = std::find(sol.cbegin(), sol.cend(), searchIdx);
            sol.erase(it);
            // increase counter
            ++numRemovals;
        } while (!sol.empty()
            && (sol.size() == oldSize || numRemovals < maxNumRemovals));
        // Sorting indexes by our criteria in descending order
        std::sort(availablePizzas.begin(), availablePizzas.end(), [&](int a, int b)
        {
            return (M - (score + pizzas[a])) >(M - (score + pizzas[b]));
        });
        // adding slices to fill the order
        while (score < M &&
            (!availablePizzas.empty() && ( M - ( score + pizzas[availablePizzas.front() ] ) ) >=0 ) )
        {
            const int32_t avIdx = rnPizzaID(g) % availablePizzas.size();
            const auto searchIt = std::next(availablePizzas.cbegin(), avIdx);
            const int32_t searchIdx = *searchIt;
            if ((pizzas[searchIdx] + score) <= M)
            {
                sol.emplace_back(searchIdx);
                score += pizzas[searchIdx];
                availablePizzas.erase(searchIt);
                // Sorting indexes by our criteria in descending order
                std::sort(availablePizzas.begin(), availablePizzas.end(), [&](int a, int b)
                {
                    return (M - (score + pizzas[a])) > (M - (score + pizzas[b]));
                });
                // Sorting indexes
                std::sort(sol.begin(), sol.end());
            }
        }
    }
    // Helper function to print the solution
    void print()
    {
        std::cout << "Ordering " << sol.size() << " pizzas:" << std::endl;
        int32_t score = 0;
        for (auto item : sol)
        {
            std::cout << item << " ";
            score += pizzas[item];
        }
        cout << endl;
        cout << "Score: " << score << endl;
    }
    // Save solution to a file.
    // The name of the file is SCENARIO + "_" + SCORE + ".txt"
    void saveSolutionToFile()
    {
        // print to a file
        ofstream outFile;
        outFile.open(iFileName + "_" + to_string(score) + ".out");
        outFile << sol.size() << endl;
        int x = 0;
        for (auto& item : sol)
        {
            outFile << item;
            if (x < static_cast<int32_t>(sol.size() - 1))
            {
                outFile << " ";
            }
            ++x;
        }
        outFile << endl;
        outFile.close();
    }
    TSol sol; // vector of indexes of the pizzas
    int32_t score; // score of the current solution
    // Set storing the indexes of the available pizzas
    // This vector will be always sorted in a descending order
    // by the difference <M - (score + pizzas[index])>, where index
    // refers to each value stored inside this vector.
    TSol availablePizzas;
};Code language: C++ (cpp)

How to quickly calculate new solutions?

The Simulated Annealing is – by its nature – a slow algorithm. Despite that, it is easy to adapt the code proposed in this article to solve many NP-hard problems.

The implementation of this algorithm has been done having performance always in mind.

A bottleneck is – at each step – the choice of pizzas to replace and to add to the current solution.

For this reason, in the mutate() function, after a certain number of pizzas have been randomly removed, then only the pizzas that can effectively contribute to the solution are considered in the selection process.

For this reason, the vector of available pizzas is sorted so that the pizzas that can fit better inside the solution are placed at the front of the vector.

If no pizzas can be selected, then a score greater than the maximum value is achieved if the first at the front of the vector is chosen.

The orderPizzas() function

As described in this post, the used algorithm is a “Simulated Annealing” procedure. Please, find the implementation of that algorithm below:

/* This content is visible only to registered users. Please, login or register to view this content. */  

Every time a better solution is found, it is also saved to a file. In this way, it is possible to commit as soon as possible a new solution to the Google Hash Code Judge System.

The console output

The algorithm has been executed for all the unsolved test scenarios, as shown in the following images.

In the following table, the average execution time for each scenario is shown:

ScenarioAverage execution time
Small<1s
Medium<1s
Quite Big1-2 minutes
Also Big<1s
/* This content is visible only to registered users. Please, login or register to view this content. */  

The complete code

/* This content is visible only to registered users. Please, login or register to view this content. */  
Pietro L. Carotenuto
Pietro L. Carotenuto

C++ Software Engineer, Ph.D. in Information Engineering. I like reading and learning new things while working on new projects. Main author on PietroLC.com looking for contributions and guest authors.

Articles: 31

One comment

Leave your feedback here:

Your email address will not be published. Required fields are marked *