美文网首页
代码 | 自适应大邻域搜索系列之(6) - 判断接受准则Simu

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

作者: 番茄鸡蛋炒饭被抢注啦 | 来源:发表于2019-04-30 18:16 被阅读0次

    前言

    前面三篇文章对大家来说应该很简单吧?不过轻松了这么久,今天再来看点刺激的。关于判断接受准则的代码。其实,判断接受准则有很多种,效果也因代码而异。今天介绍的是模拟退火的判断接受准则。那么,相关的原理之前的推文有讲过,不懂的同学回去翻翻这个文章 复习一下哈,小编也回去看看,咳咳~。好了,废话不多说,开始干活。

    01 总体概述

    其实这个ALNS的代码库提供了很多的判断接受准则,有最简单的直接根据目标值来判断,也有各种复杂的模拟退火降温冷却等过程来判断。不过,今天挑一个最具代表性的来讲吧,就是模拟退火的判断接受准则。其代码实现是由两个类IAcceptanceModule、SimulatedAnnealing来实现的。它们的关系依旧如下:


    其中IAcceptanceModule依旧是抽象类,只提供接口。下面对这两货进行解析。

    02 IAcceptanceModule

    这个抽象类也很简单,只提供了一个接口transitionAccepted,以用来判断是否要接受新的解,为纯虚函数,需要在后续的代码中重写的。

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

    03 SimulatedAnnealing

    SimulatedAnnealing继承于上面的接口类IAcceptanceModule,它利用模拟退火的判断接受准则实现了transitionAccepted的功能。值得注意的是,该类成员变量里面是一个CoolingSchedule,用来获取当前温度。该表有另一个抽象类ICoolingSchedule定义,下面会详细说道。

    class SimulatedAnnealing: public IAcceptanceModule {
    private:
        //! The cooling schedule to be use to compute the temperature each time it
        //! is needed.
        ICoolingSchedule* coolingSchedule;
    public:
        //! Constructor.
        //! \param cs the cooling schedule to be used by the simulated annealing.
        SimulatedAnnealing(ICoolingSchedule& cs);
    
        //! Destructor.
        virtual ~SimulatedAnnealing();
    
        //! Compute if the newly created solution have to be accepted or not
        bool transitionAccepted(IBestSolutionManager& bestSolutionManager, ISolution& currentSolution, ISolution& newSolution, ALNS_Iteration_Status& status);
    
        virtual void startSignal();
    
    };
    

    其成员函数的实现也非常的简单,不过多说两句。先利用CoolingSchedule获取当前冷却过程的温度。如果新解目标值<当前解的,那么直接接受就行了。如果>,那么按照一定的概率接受。具体公式解释嘛,小编截个图过来吧,因为在以前的文章已经讲过了:


    不过这里的能量差计算用的是解的目标惩罚值算的,不是目标值。

    bool SimulatedAnnealing::transitionAccepted(IBestSolutionManager& bestSolutionManager, ISolution& currentSolution, ISolution& newSolution, ALNS_Iteration_Status& status)
    {
        double temperature = coolingSchedule->getCurrentTemperature();
        if(newSolution < currentSolution)
        {
            return true;
        }
        else
        {
            double difference = newSolution.getPenalizedObjectiveValue() - currentSolution.getPenalizedObjectiveValue();
            double randomVal = static_cast<double>(rand())/static_cast<double>(RAND_MAX);
            return (exp(-1*difference/temperature)>randomVal);
        }
    }
    
    void SimulatedAnnealing::startSignal()
    {
        coolingSchedule->startSignal();
    }
    

    04 ICoolingSchedule

    4.1 ICoolingSchedule

    这货是一个抽象类,CoolingSchedule有很多种类型,根据不同需要由这个类可以派生出下面类型的CoolingSchedule:


    ICoolingSchedule只提供了两个接口,其中getCurrentTemperature是纯虚函数,用以获取当前的退火温度,需要重写。

    class ICoolingSchedule
    {
    public:
        //! \return the current temperature.
        virtual double getCurrentTemperature()=0;
    
        //! This method should be called when the optimization
        //! process start. The cooling schedules that actually need
        //! this should override this method.
        virtual void startSignal(){};
    };
    

    4.2 LinearCoolingSchedule

    由于CoolingSchedule有很多类型,小编挑一个LinearCoolingSchedule给大家讲解吧。LinearCoolingSchedule主要的根据是迭代的次数来工作的。成员函数getCurrentTemperature是核心,用以获取当前的温度,便于上面的判断接受准则计算概率。

    class LinearCoolingSchedule: public ICoolingSchedule {
    private:
        //! The current temperature.
        double currentTemperature;
    
        //! The amount to remove at each temperature recomputation.
        double amountRemove;
    public:
        //! Constructor.
        //! \param initSol the initial solution.
        //! \param csParam the cooling schedule parameters.
        //! \param nbIterations the number of iterations to be performed.
        LinearCoolingSchedule(ISolution& initSol, CoolingSchedule_Parameters& csParam, size_t nbIterations);
    
        //! Constructor.
        //! \param startingTemperature the initial temperature.
        //! \param nbIterations the number of iterations to be performed.
        LinearCoolingSchedule(double startingTemperature, size_t nbIterations);
    
        //! Destructor.
        virtual ~LinearCoolingSchedule();
    
        //! Compute and return the current temperature.
        //! \return the current temperature.
        double getCurrentTemperature();
    
        void startSignal(){};
    };
    

    然后现在来看看其具体方法是怎么实现的吧。其实也很简单,没有那么复杂。每次获取currentTemperature的时候呢,先让currentTemperature降降温,再返回。降温的幅度是利用currentTemperature 减去 amountRemove实现的。那么amountRemove又是怎么得出来的呢?LinearCoolingSchedule提供了两个构造函数,对应不同的计算方法:

    1. currentTemperature = (csParam.setupPercentage*initSol.getPenalizedObjectiveValue())/(-log(0.5));
      amountRemove = currentTemperature/static_cast<double>(nbIterations);
      其中,setupPercentage为参数,nbIterations为总的迭代次数。
    2. amountRemove = startingTemperature/static_cast<double>(nbIterations);
      其中,startingTemperature为传入参数。
    LinearCoolingSchedule::LinearCoolingSchedule(ISolution& initSol, CoolingSchedule_Parameters& csParam, size_t nbIterations) {
        currentTemperature = (csParam.setupPercentage*initSol.getPenalizedObjectiveValue())/(-log(0.5));
        amountRemove = currentTemperature/static_cast<double>(nbIterations);
    
    }
    
    LinearCoolingSchedule::LinearCoolingSchedule(double startingTemperature, size_t nbIterations) {
        assert(nbIterations>0);
        assert(startingTemperature>=0);
        currentTemperature = startingTemperature;
        amountRemove = startingTemperature/static_cast<double>(nbIterations);
    
    }
    
    LinearCoolingSchedule::~LinearCoolingSchedule() {
        // Nothing to be done.
    }
    
    double LinearCoolingSchedule::getCurrentTemperature()
    {
        currentTemperature-= amountRemove;
        if(currentTemperature < 0)
        {
            currentTemperature = 0;
        }
        assert(currentTemperature>=0);
        return currentTemperature;
    }
    

    05 小结

    今天讲的总体也不是很难,相信之前模拟退火学得好的小伙伴一眼就能看懂了,如果其他小伙伴还不是很理解的话,回去看看之前的文章,看看模拟退火的判断接受准则再多加理解,相信对大家不是什么问题。

    至此,代码已经讲得差不多了,估摸着还能再做几篇文章,依然感谢大家一路过来的支持。谢谢!咱们下期再见。

    代码及相关内容可关注公众号。更多精彩尽在微信公众号【程序猿声】

    相关文章

      网友评论

          本文标题:代码 | 自适应大邻域搜索系列之(6) - 判断接受准则Simu

          本文链接:https://www.haomeiwen.com/subject/uycwdqtx.html