HillClimbingAlogrithm.hpp

Go to the documentation of this file.

#pragma once

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

namespace ISM {

template <class InstanceType>
class HillClimbingAlogrithm : public OptimizationAlgorithm<InstanceType>
{
        public:
                HillClimbingAlogrithm(NeighbourhoodFunctionPtr<InstanceType> neighbourhoodFunction,
                        CostFunctionPtr<InstanceType> costFunction, bool randomWalkProbability = 0.0)
                        : OptimizationAlgorithm<InstanceType>(neighbourhoodFunction, costFunction)
                        , mRandomWalkProbability(randomWalkProbability)
                {}

                InstanceType optimize(InstanceType startInstance)
                {
                        InstanceType selectedInstance = startInstance;

                        double lowestCost = this->mCostFunction->calculateCost(selectedInstance);
                        bool keepOptimizing = true;

                        while (keepOptimizing)
                        {
                                keepOptimizing = false;

                                this->mNeighbourhoodFunction->setReferenceInstance(selectedInstance);

                                if (this->mNeighbourhoodFunction->hasNextNeighbour())
                                {
                                        //Check if random walk shuld be performed
                                        if (mDistribution(mGenerator) < mRandomWalkProbability)
                                        {
                                                        selectedInstance = this->mNeighbourhoodFunction->getNextNeighbour();
                                                        lowestCost = this->mCostFunction->calculateCost(selectedInstance);
                                                        keepOptimizing = true;
                                        }
                                        else
                                        {
                                                do
                                                {
                                                        InstanceType nextInstance = this->mNeighbourhoodFunction->getNextNeighbour();
                                                        double nextInstanceCost = this->mCostFunction->calculateCost(nextInstance);

                                                        if (nextInstanceCost < lowestCost)
                                                        {
                                                                selectedInstance = nextInstance;
                                                                lowestCost = nextInstanceCost;
                                                                keepOptimizing = true;
                                                        }
                                                } while (this->mNeighbourhoodFunction->hasNextNeighbour());
                                        }
                                }
                                else
                                {
                                        //The selected instance has no neighbours, we can't continue the optimization
                                        return selectedInstance;
                                }

                        }

                        return selectedInstance;
                }

          private:
                bool mRandomWalkProbability;
                std::default_random_engine mGenerator;
                std::uniform_real_distribution<double> mDistribution = std::uniform_real_distribution<double>(0.0, 1.0);
};

template<class InstanceType>
using HillClimbingAlogrithmPtr = boost::shared_ptr<HillClimbingAlogrithm<InstanceType>>;

}