RecordHuntAlgorithm.hpp

Go to the documentation of this file.

#pragma once

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

namespace ISM {

using boost::filesystem::path;

template <class InstanceType>
class RecordHuntAlgorithm : public OptimizationAlgorithm<InstanceType>
{
        public:
                RecordHuntAlgorithm(NeighbourhoodFunctionPtr<InstanceType> neighbourhoodFunction,
                        CostFunctionPtr<InstanceType> costFunction,
                        AcceptanceFunctionPtr acceptanceFunction)
                        : OptimizationAlgorithm<InstanceType>(neighbourhoodFunction, costFunction)
                        , mAcceptanceFunction(acceptanceFunction)
                {}

                InstanceType optimize(InstanceType startInstance)
                {

                        mAcceptanceFunction->reset();

                        InstanceType selectedInstance = startInstance;
                        InstanceType bestInstance = startInstance;

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

                        while (keepOptimizing)
                        {
                                keepOptimizing = false;

                                this->mNeighbourhoodFunction->setReferenceInstance(selectedInstance);
                                double selectedInstanceCost = this->mCostFunction->calculateCost(selectedInstance);


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

                                                if (mAcceptanceFunction->isNewCostAcceptable(nextInstanceCost, selectedInstanceCost))
                                                {
                                                        keepOptimizing = true;
                                                        selectedInstance = nextInstance;
                                                        mAcceptanceFunction->update();

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

                                                        break;
                                                }

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

                        return bestInstance;
                }

        private:
                AcceptanceFunctionPtr mAcceptanceFunction;

};

template<class InstanceType>
using RecordHuntAlgorithmPtr = boost::shared_ptr<RecordHuntAlgorithm<InstanceType>>;

}