代码 | 自适应大邻域搜索系列之(6) - 判断接受准则SimulatedAnnealing的代码解析

 1class IAcceptanceModule
 2{
 3public:
 4    //! Indicate if the new created solution have to be accepted or not
 5    //! \param bestSolutionManager a reference to the best solution manager.
 6    //! \param currentSolution current solution.
 7    //! \param newSolution new solution.
 8    //! \param status the status of the current alns iteration.
 9    //! \return true if the transition is accepted, false otherwise.
10    virtual bool transitionAccepted(IBestSolutionManager& bestSolutionManager, ISolution& currentSolution, ISolution& newSolution, ALNS_Iteration_Status& status) = 0;
11
12    //! Some Acceptance modules needs to initialize some variable
13    //! only when the solver actualy starts working. In this case
14    //! you should override this method.
15    virtual void startSignal(){};
16};

 1class SimulatedAnnealing: public IAcceptanceModule {
 2private:
 3    //! The cooling schedule to be use to compute the temperature each time it
 4    //! is needed.
 5    ICoolingSchedule* coolingSchedule;
 6public:
 7    //! Constructor.
 8    //! \param cs the cooling schedule to be used by the simulated annealing.
 9    SimulatedAnnealing(ICoolingSchedule& cs);
10
11    //! Destructor.
12    virtual ~SimulatedAnnealing();
13
14    //! Compute if the newly created solution have to be accepted or not
15    bool transitionAccepted(IBestSolutionManager& bestSolutionManager, ISolution& currentSolution, ISolution& newSolution, ALNS_Iteration_Status& status);
16
17    virtual void startSignal();
18
19};

 1bool SimulatedAnnealing::transitionAccepted(IBestSolutionManager& bestSolutionManager, ISolution& currentSolution, ISolution& newSolution, ALNS_Iteration_Status& status)
 2{
 3    double temperature = coolingSchedule->getCurrentTemperature();
 4    if(newSolution < currentSolution)
 5    {
 6        return true;
 7    }
 8    else
 9    {
10        double difference = newSolution.getPenalizedObjectiveValue() - currentSolution.getPenalizedObjectiveValue();
11        double randomVal = static_cast<double>(rand())/static_cast<double>(RAND_MAX);
12        return (exp(-1*difference/temperature)>randomVal);
13    }
14}
15
16void SimulatedAnnealing::startSignal()
17{
18    coolingSchedule->startSignal();
19}

 1class ICoolingSchedule
 2{
 3public:
 4    //! \return the current temperature.
 5    virtual double getCurrentTemperature()=0;
 6
 7    //! This method should be called when the optimization
 8    //! process start. The cooling schedules that actually need
 9    //! this should override this method.
10    virtual void startSignal(){};
11};

 1class LinearCoolingSchedule: public ICoolingSchedule {
 2private:
 3    //! The current temperature.
 4    double currentTemperature;
 5
 6    //! The amount to remove at each temperature recomputation.
 7    double amountRemove;
 8public:
 9    //! Constructor.
10    //! \param initSol the initial solution.
11    //! \param csParam the cooling schedule parameters.
12    //! \param nbIterations the number of iterations to be performed.
13    LinearCoolingSchedule(ISolution& initSol, CoolingSchedule_Parameters& csParam, size_t nbIterations);
14
15    //! Constructor.
16    //! \param startingTemperature the initial temperature.
17    //! \param nbIterations the number of iterations to be performed.
18    LinearCoolingSchedule(double startingTemperature, size_t nbIterations);
19
20    //! Destructor.
21    virtual ~LinearCoolingSchedule();
22
23    //! Compute and return the current temperature.
24    //! \return the current temperature.
25    double getCurrentTemperature();
26
27    void startSignal(){};
28};

 1LinearCoolingSchedule::LinearCoolingSchedule(ISolution& initSol, CoolingSchedule_Parameters& csParam, size_t nbIterations) {
 2    currentTemperature = (csParam.setupPercentage*initSol.getPenalizedObjectiveValue())/(-log(0.5));
 3    amountRemove = currentTemperature/static_cast<double>(nbIterations);
 4
 5}
 6
 7LinearCoolingSchedule::LinearCoolingSchedule(double startingTemperature, size_t nbIterations) {
 8    assert(nbIterations>0);
 9    assert(startingTemperature>=0);
10    currentTemperature = startingTemperature;
11    amountRemove = startingTemperature/static_cast<double>(nbIterations);
12
13}
14
15LinearCoolingSchedule::~LinearCoolingSchedule() {
16    // Nothing to be done.
17}
18
19double LinearCoolingSchedule::getCurrentTemperature()
20{
21    currentTemperature-= amountRemove;
22    if(currentTemperature < 0)
23    {
24        currentTemperature = 0;
25    }
26    assert(currentTemperature>=0);
27    return currentTemperature;
28}