美文网首页
代码 | 自适应大邻域搜索系列之(3) - Destroy和Re

代码 | 自适应大邻域搜索系列之(3) - Destroy和Re

作者: 番茄鸡蛋炒饭被抢注啦 | 来源:发表于2019-03-23 17:29 被阅读0次

    前言

    上一篇文章中我们具体解剖了ALNS类的具体代码实现过程,不过也留下了很多大坑。接下来的文章基本都是“填坑”了,把各个模块一一展现解析给大家。不过碍于文章篇幅等原因呢,也不会每一行代码都进行讲解,那些简单的代码就跳过了,相信大家也能一眼就看懂。好了,废话不多说,开始干活吧。

    01 照旧总体概述

    前面我们提到,ALNS中的重中之重就是Destroy和Repair方法了,在整一个ALNS框架中呢,涉及这俩货的有Destroy和Repair方法的具体实现、Destroy和Repair方法管理(包括各个Destroy和Repair方法权重分配、成绩打分、按权重选择哪个Destroy和Repair方法等操作)。所以在这次的ALNS代码中呢,这俩货的代码实现呢也分为两个模块:

    • Destroy和Repair方法具体实现模块
    • Destroy和Repair方法管理模块

    下面我们将对其进行一一讲解,不知道大家小板凳准备好了没有。

    02 Destroy和Repair方法具体实现

    关于Destroy和Repair方法,由三个类组成,分别是AOperator、ADestroyOperator、ARepairOperator。它们之间的继承派生关系如下:


    下面对其一一讲解。

    2.1 AOperator

    这是一个基础父类,它抽象了Destroy和Repair方法共有的一些方法和特征(成绩、权重、名称等等),然后Destroy和Repair方法再各自继承于它,实现自己的功能模块。成员变量已经注释清楚了,关于protected的一个成员noise噪声模式会在后面讲到。其他的方法也很简单就不做多解释了。

    class AOperator
    {
    private:
        //! Total number of calls during the process.
        size_t totalNumberOfCalls;
    
        //! Number of calls since the last evaluation.
        size_t nbCallsSinceLastEval;
    
        //! score of the operator.
        double score;
    
        //! weight of the operator.
        double weight;
    
        //! designation of the operator.
        std::string operatorName;
    
    protected:
        //! Indicate if the operator is used in noise mode or not.
        bool noise;
    public:
    
        //! Constructor.
        AOperator(std::string name){
            operatorName = name;
            init();
        }
    
        //! Destructor.
        virtual ~AOperator(){};
    
        //! Initialize the values of the numbers of calls.
        void init()
        {
            totalNumberOfCalls = 0;
            nbCallsSinceLastEval = 0;
            score = 0;
            weight = 1;
        }
    
        //! reset the number of calls since last eval.
        void resetNumberOfCalls()
        {
            nbCallsSinceLastEval = 0;
        }
    
        //! Simple getter.
        //! \return the total number of calls to the operator since
        //! the beginning of the optimization process.
        size_t getTotalNumberOfCalls(){return totalNumberOfCalls;};
    
        //! Simple getter.
        //! \return the number of calls to this operator since the last
        //! evaluation.
        size_t getNumberOfCallsSinceLastEvaluation(){return nbCallsSinceLastEval;};
    
        void increaseNumberOfCalls()
        {
            totalNumberOfCalls++;
            nbCallsSinceLastEval++;
        }
    
        //! Simple getter.
        double getScore() const
        {
            return score;
        }
    
        //! Simple getter.
        double getWeight() const
        {
            return weight;
        }
    
        //! resetter.
        void resetScore()
        {
            this->score = 0;
        }
    
        //! Simple setter.
        void setScore(double s)
        {
            this->score = s;
        }
    
        //! Simple setter.
        void setWeight(double weight)
        {
            this->weight = weight;
        }
    
        //! Simple getter.
        std::string getName(){return operatorName;};
    
        //! Set noise to true.
        void setNoise(){noise=true;};
    
        //! Set noise to false.
        void unsetNoise(){noise=false;};
    
    };
    

    2.2 ADestroyOperator

    该类主要是继承于上面的AOperator类,然后再此基础上加上Destroy操作的具体实现。它是一个抽象类,需要在后续的应用中重写Destroy操作的方法。

    class ADestroyOperator : public AOperator {
    protected:
        //! The minimum destroy size used.
        size_t minimunDestroy;
        //! The maximum destroy size used.
        size_t maximumDestroy;
    
    public:
        //! Constructor.
        //! \param mini the minimum destroy size.
        //! \param maxi the maximum destroy size.
        //! \param s the name of the destroy operator.
        ADestroyOperator(size_t mini, size_t maxi, std::string s) : AOperator(s)
        {
            minimunDestroy = mini;
            maximumDestroy = maxi;
        }
    
        //! Destructor.
        virtual ~ADestroyOperator(){};
    
        //! This function is the one called to destroy a solution.
        //! \param sol the solution to be destroyed.
        virtual void destroySolution(ISolution& sol)=0;
    };
    

    2.3 ARepairOperator

    同理,也是由AOperator类派生出来并加上Repair自己的实现方法的类。也是一个抽象类,需要在后续的使用中重写Repair方法。

    class ARepairOperator : public AOperator {
    
    public:
        ARepairOperator(std::string s) : AOperator(s)
        {
        }
    
        virtual ~ARepairOperator(){};
    
        virtual void repairSolution(ISolution& sol)=0;
    };
    

    03 Destroy和Repair方法管理

    对Destroy和Repair方法进行管理的由两个类来实现:AOperatorManager、OperatorManager。其中AOperatorManager是抽象类,只提供接口,OperatorManager继承于AOperatorManager。并对其接口进行实现。

    3.1 AOperatorManager

    该类抽象了OperatorManager的一些特征,只提供接口。因此成员函数都是纯虚函数。相关方法的说明已经注释在代码里面了。关于保护成员:stats用于保存算法迭代过程中的一些状态量,这个类后续也会讲解的。

    class AOperatorManager
    {
    public:
        //! This method selects a destroy operator.
        //! \return a destroy operator.
        virtual ADestroyOperator& selectDestroyOperator()=0;
    
        //! This method selects a repair operator.
        //! \return a repair operator.
        virtual ARepairOperator& selectRepairOperator()=0;
    
        virtual void recomputeWeights()=0;
    
        //! Update the scores of the operators.
        virtual void updateScores(ADestroyOperator& des, ARepairOperator& rep, ALNS_Iteration_Status& status)=0;
    
        //! Indicate that the optimization process starts.
        virtual void startSignal()=0;
    
        //! Destroy the operators registered to this operator manager.
        virtual void end()=0;
    
        //! Simple setter.
        void setStatistics(Statistics* statistics){stats = statistics;};
    protected:
        //! A pointer to the instance of the statistics module.
        Statistics* stats;
    };
    

    3.2 OperatorManager

    该类在AOperatorManager基础上也添加了一些自己额外的成员变量和函数方法。具体还是看代码理解吧,挺简单的,没有需要多解释的,我在这多少无益。

    class OperatorManager: public AOperatorManager {
    private:
        //! The set of repair operators.
        std::vector<AOperator*> repairOperators;
    
        //! The set of destroy operators.
        std::vector<AOperator*> destroyOperators;
    
        //! The sum of the weights of the repair operators.
        double sumWeightsRepair;
    
        //! The sum of the weights of the destroy operators.
        double sumWeightsDestroy;
    
        //! The paramaters to be used by the ALNS.
        ALNS_Parameters* parameters;
    
        //! Indicate whether or not the next operators to be return
        //! should be noised or not.
        bool noise;
    
        //! A counter that indicates the number of times repair operators with noise have been successfull
        double performanceRepairOperatorsWithNoise;
        //! A counter that indicates the number of times repair operators without noise have been successfull
        double performanceRepairOperatorsWithoutNoise;
    
    
        //! Use a roulette wheel to select an operator in a vector of operators.
        //! \return the selected operator.
        AOperator& selectOperator(std::vector<AOperator*>& vecOp, double sumW);
    
        //! Recompute the weight of an operator.
        void recomputeWeight(AOperator& op, double& sumW);
    public:
        //! Constructor
        //! \param param the parameters to be used.
        OperatorManager(ALNS_Parameters& param);
    
        //! Destructor.
        virtual ~OperatorManager();
    
        //! This function recompute the weights of every operator managed by this
        //! manager.
        void recomputeWeights();
    
        //! This method selects a destroy operator.
        //! \return a destroy operator.
        ADestroyOperator& selectDestroyOperator();
    
        //! This method selects a repair operator.
        //! \return a repair operator.
        ARepairOperator& selectRepairOperator();
    
        //! This method adds a repair operator to the list
        //! of repair operator managed by this manager.
        //! \param repairOperator the repair operator to be added.
        void addRepairOperator(ARepairOperator& repairOperator);
    
        //! This method adds a destroy operator to the list
        //! of destroy operator managed by this manager.
        //! \param destroyOperator the destroy operator to be added.
        void addDestroyOperator(ADestroyOperator& destroyOperator);
    
        //! This method run some sanity checks to ensure that it is possible
        //! to "safely" use this manager within the ALNS.
        void sanityChecks();
    
        //! Update the scores of the operators.
        virtual void updateScores(ADestroyOperator& des, ARepairOperator& rep, ALNS_Iteration_Status& status);
    
        //! Indicate that the optimization process starts.
        virtual void startSignal();
    
        //! Destroy all the operators registered to this operator.
        void end();
    };
    

    上面是该类的.h文件,关于其中某些函数方法的实现,小编下面挑一些来重点给大家讲讲,那些以小编的脑瓜子都能理解的代码就省略了,大家应该都能懂……

    3.3 OperatorManager具体实现

    又到了一大波代码时间,来吧来吧,小板凳准备好,要开始啦~

    3.3.1 OperatorManager::recomputeWeight(...)

    重新计算单个操作的权重。其有两个参数AOperator& op, double& sumW,其中 op是要重新计算权重的repair或者destroy方法,sumW是其对应集合的权重总和。
    这里只讲一个新权重的计算方式就行:



    其中:
    Rho为设定的[0, 1]之间的参数,PrevWeight表示旧的权重,nbCalls表示在上一次自上一次更新完权重到现在该方法被调用的次数,timeSegmentsIt表示迭代多少次需要重新计算一下权重的迭代次数,currentScore表示旧的成绩。理解了这些就很easy了。

    void OperatorManager::recomputeWeight(AOperator& op, double& sumW)
    {
        double prevWeight = op.getWeight();
        sumW -= prevWeight;
        double currentScore = op.getScore();
        size_t nbCalls = op.getNumberOfCallsSinceLastEvaluation();
        double newWeight = (1-parameters->getRho())*prevWeight + parameters->getRho()*(static_cast<double>(nbCalls)/static_cast<double>(parameters->getTimeSegmentsIt()))*currentScore;
        // We ensure that the weight is within the bounds.
        if(newWeight > parameters->getMaximumWeight())
        {
            newWeight = parameters->getMaximumWeight();
        }
        if(newWeight < parameters->getMinimumWeight())
        {
            newWeight = parameters->getMinimumWeight();
        }
    
        sumW += newWeight;
        op.setWeight(newWeight);
        op.resetScore();
        op.resetNumberOfCalls();
    }
    

    值得注意的是还有一个OperatorManager::recomputeWeights()成员函数是用于重新计算repair或者destroy方法集合的,它的实现主要也还是调用OperatorManager::recomputeWeight(AOperator& op, double& sumW)方法来实现的。

    3.3.2 OperatorManager::selectOperator(...)

    相信了解过遗传算法轮盘赌实现过程的小伙伴对这里都不会陌生,当然,并不是说权重大的方法一定会被选中,只是被选中的可能性会大而已。具体过程是先生成一个在0到sumWeight之间的中间权重randomWeightPos ,然后从第一个方法开始用变量cumulSum进行权重累加,直到cumulSum>=randomWeightPos 为止,那么停止累加时最后这个方法就是幸运儿了。

    AOperator& OperatorManager::selectOperator(std::vector<AOperator*>& vecOp, double sumW)
    {
        double randomVal = static_cast<double>(rand())/static_cast<double>(RAND_MAX);
        double randomWeightPos = randomVal*sumW;
        double cumulSum = 0;
        for(size_t i = 0; i < vecOp.size(); i++)
        {
            cumulSum += vecOp[i]->getWeight();
            if(cumulSum >= randomWeightPos)
            {
                if(noise)
                {
                    vecOp[i]->setNoise();
                }
                else
                {
                    vecOp[i]->unsetNoise();
                }
                vecOp[i]->increaseNumberOfCalls();
                return *(vecOp[i]);
            }
        }
        assert(false);
        return *(vecOp.back());
    }
    

    3.3.3 OperatorManager::updateScores(...)

    该成员函数用来更新各个Destroy和Repair方法的成绩。参数是Destroy和Repair方法的集合,以及ALNS迭代过程中的各种状态信息。便于说明下面用rScore和dScore分别代表Repair和Destroy方法的成绩。具体实现如下:

    1. 如果找到新的最优解,rScore+=Sigma1,dScore+=Sigma1。其中Sigma1是设定参数。
    2. 如果当前解得到改进,rScore+=Sigma2,dScore+=Sigma2。其中Sigma2是设定参数。
    3. 如果当前解没有得到改进 and 当前解是之前没有出现过的 and 当前解被接受作为新的解了,rScore+=Sigma3,dScore+=Sigma3。其中Sigma3是设定参数。
    void OperatorManager::updateScores(ADestroyOperator& des, ARepairOperator& rep, ALNS_Iteration_Status& status)
    {
        if(status.getNewBestSolution() == ALNS_Iteration_Status::TRUE)
        {
            rep.setScore(rep.getScore()+parameters->getSigma1());
            des.setScore(des.getScore()+parameters->getSigma1());
            performanceRepairOperatorsWithNoise += 1;
            performanceRepairOperatorsWithoutNoise += 1;
        }
    
        if(status.getImproveCurrentSolution() == ALNS_Iteration_Status::TRUE)
        {
            rep.setScore(rep.getScore()+parameters->getSigma2());
            des.setScore(des.getScore()+parameters->getSigma2());
            performanceRepairOperatorsWithNoise += 1;
            performanceRepairOperatorsWithoutNoise += 1;
        }
    
        if(status.getImproveCurrentSolution() == ALNS_Iteration_Status::FALSE
                && status.getAcceptedAsCurrentSolution() == ALNS_Iteration_Status::TRUE
                && status.getAlreadyKnownSolution() == ALNS_Iteration_Status::FALSE)
        {
            rep.setScore(rep.getScore()+parameters->getSigma3());
            des.setScore(des.getScore()+parameters->getSigma3());
            performanceRepairOperatorsWithNoise += 1;
            performanceRepairOperatorsWithoutNoise += 1;
        }
        /* OLD VERSION */
        /*
        if(parameters->getNoise())
        {
            double randNoise = static_cast<double>(rand())/RAND_MAX;
            noise = (randNoise<parameters->getProbabilityOfNoise());
        }
        */
        /* NEW VERSION */
    
        if(parameters->getNoise())
        {
            double performanceRepairOperatorsGlobal = 0;
            performanceRepairOperatorsGlobal += performanceRepairOperatorsWithNoise;
            performanceRepairOperatorsGlobal += performanceRepairOperatorsWithoutNoise;
    
            double randomVal = static_cast<double>(rand())/RAND_MAX;
            double randomWeightPos = randomVal*performanceRepairOperatorsGlobal;
            noise = (randomWeightPos < performanceRepairOperatorsGlobal);
        }
    }
    

    至此,差不过难点都讲完了,不知道你萌都understand了吗?

    04 小结

    好了,以上就是今天的代码内容,别急着走开哦,后面还有好多好多的内容没讲呢。
    这是个天坑,希望大家和小编一起努力,共同填完它。哈哈,谢谢各位的至此。

    更多运筹优化算法相关内容可以关注公众化【程序猿声】进行获取哦。

    相关文章

      网友评论

          本文标题:代码 | 自适应大邻域搜索系列之(3) - Destroy和Re

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