SimulatedAnnealingAlgorithm.hpp

Go to the documentation of this file.

#pragma once

#include <boost/shared_ptr.hpp>
#include "OptimizationAlgorithm.hpp"
#include "NeighbourhoodFunction.hpp"
#include "CoolingSchedule.hpp"

namespace ISM {

using boost::filesystem::path;

template <class InstanceType>
class SimulatedAnnealingAlgorithm : public OptimizationAlgorithm<InstanceType> 
{
        public:
                SimulatedAnnealingAlgorithm(NeighbourhoodFunctionPtr<InstanceType> neighbourhoodFunction,
                        CostFunctionPtr<InstanceType> costFunction,
                        CoolingSchedulePtr coolingSchedule) 
                        : OptimizationAlgorithm<InstanceType>(neighbourhoodFunction, costFunction)
                        , mCoolingSchedule(coolingSchedule)
                {}

                InstanceType optimize(InstanceType startInstance)
                {
                        mCoolingSchedule->reset();

                        InstanceType selectedInstance = startInstance;
                        InstanceType bestInstance = startInstance;

                        unsigned visitedInstanceCounter = 0; 
                        double lowestCost = this->mCostFunction->calculateCost(bestInstance);

                        while (!mCoolingSchedule->hasReachedEnd())
                        {
                                double oldCost = this->mCostFunction->calculateCost(selectedInstance);
                                this->mNeighbourhoodFunction->setReferenceInstance(selectedInstance);

                                if (this->mNeighbourhoodFunction->hasNextNeighbour())
                                {
                                        bool foundAcceptable = false;
                                        do
                                        {
                                                InstanceType nextInstance = this->mNeighbourhoodFunction->getNextNeighbour();
                                                double nextInstanceCost = this->mCostFunction->calculateCost(nextInstance);

                                                if (mCoolingSchedule->isNewCostAcceptable(nextInstanceCost, oldCost))
                                                {
                                                        foundAcceptable = true;
                                                        selectedInstance = nextInstance;

                                                        if (nextInstanceCost < lowestCost)
                                                        {
                                                                bestInstance = nextInstance;
                                                                lowestCost = nextInstanceCost;
                                                        }
                                                }

                                                if (++visitedInstanceCounter % mCoolingSchedule->getRepetitionsBeforeUpdate() == 0)
                                                {
                                                        mCoolingSchedule->update();
                                                }

                                        } while (!foundAcceptable && this->mNeighbourhoodFunction->hasNextNeighbour());
                                }
                                else
                                {
                                        //The selected instance has no neighbours, we can't continue the optimization
                                        return selectedInstance;
                                }
                        }

                        return bestInstance;
                }

        private:
                CoolingSchedulePtr mCoolingSchedule;

}; 

template<class InstanceType>
using SimulatedAnnealingAlgorithmPtr = boost::shared_ptr<SimulatedAnnealingAlgorithm<InstanceType>>;

}