代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析

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;};

};

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;
};

class ARepairOperator : public AOperator {

public:
	ARepairOperator(std::string s) : AOperator(s)
	{
	}

	virtual ~ARepairOperator(){};

	virtual void repairSolution(ISolution& sol)=0;
};

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;
};

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();
};

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();
}

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());
}

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);
	}
}