代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析

 1
 2class ISolution
 3{
 4public:
 5    virtual ~ISolution(){};
 6    //! A getter for the value of the objective function.
 7    //! \return the value of the objective function of this solution.
 8    virtual double getObjectiveValue()=0;
 9    //! \return a penalized version of the objective value if the solution
10    //! is infeasible.
11    virtual double getPenalizedObjectiveValue()=0;
12    //! A getter for the feasibility of the current solution.
13    //! \return true if the solution is feasible, false otherwise.
14    virtual bool isFeasible()=0;
15    //! A comparator.
16    //! \return true if this solution is "better" than the solution it is compared to.
17    virtual bool operator<(ISolution&)=0;
18    //! Compute the "distance" between solution.
19    //! This feature can be used as part of the ALNS to favor the
20    //! diversification process. If you do not plan to use this feature
21    //! just implement a method returning 0.
22    virtual int distance(ISolution&)=0;
23    //! This method create a copy of the solution.
24    virtual ISolution* getCopy()=0;
25    //! Compute a hash key of the solution.
26    virtual long long getHash()=0;
27};

 1class IBestSolutionManager
 2{
 3public:
 4    //! This method evaluate if a solution is a new best solution, and adds it to the
 5    //! best solution pool in this case.
 6    //! \param sol the solution to be tested.
 7    //! \return true if the solution is a new best solution, false otherwise.
 8    virtual bool isNewBestSolution(ISolution& sol)=0;
 9
10    //! Return a pointer to a best solution.
11    virtual std::list<ISolution*>::iterator begin()=0;
12
13    //! Return a pointer to a best solution.
14    virtual std::list<ISolution*>::iterator end()=0;
15
16    //! This function take care of reloading the best known
17    //! solution, as the current solution, if needed.
18    //! \param currSol a pointer to the current solution.
19    //! \param status the status of the current iteration.
20    //! \return a pointer to the current solution.
21    virtual ISolution* reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status)=0;
22};

 1class SimpleBestSolutionManager: public IBestSolutionManager {
 2public:
 3    SimpleBestSolutionManager(ALNS_Parameters& param);
 4
 5    virtual ~SimpleBestSolutionManager();
 6
 7    virtual bool isNewBestSolution(ISolution& sol);
 8
 9    //! Return a pointer to a best solution.
10    std::list<ISolution*>::iterator begin(){return bestSols.begin();};
11
12    //! Return a pointer to a best solution.
13    std::list<ISolution*>::iterator end(){return bestSols.end();};
14
15    //! This function take care of reloading the best known
16    //! solution, as the current solution, if needed.
17    //! \param currSol a pointer to the current solution.
18    //! \param status the status of the current iteration.
19    //! \return a pointer to the current solution.
20    virtual ISolution* reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status);
21
22    //! Simple getter.
23    std::list<ISolution*>& getBestSols(){return bestSols;};
24private:
25    std::list<ISolution*> bestSols;
26
27    ALNS_Parameters* parameters;
28
29};

 1bool SimpleBestSolutionManager::isNewBestSolution(ISolution& sol)
 2{
 3    for(list<ISolution*>::iterator it = bestSols.begin(); it != bestSols.end(); it++)
 4    {
 5        ISolution& currentSol = *(*it);
 6        if(currentSol<sol)
 7        {
 8            return false;
 9        }
10        else if(sol<currentSol)
11        {
12            delete *it;
13            it = bestSols.erase(it);
14            if(it == bestSols.end())
15            {
16                break;
17            }
18        }
19        else if(currentSol.getHash() == sol.getHash())
20        {
21            return false;
22        }
23    }
24    ISolution* copy = sol.getCopy();
25    bestSols.push_back(copy);
26    return true;
27}
28
29ISolution* SimpleBestSolutionManager::reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status)
30{
31    if(status.getNbIterationWithoutImprovementSinceLastReload() > 0 &&
32       ((status.getNbIterationWithoutImprovementSinceLastReload() % parameters->getReloadFrequency()) == 0))
33    {
34        status.setNbIterationWithoutImprovementSinceLastReload(0);
35        delete currSol;
36        return bestSols.back()->getCopy();
37    }
38    else
39    {
40        return currSol;
41    }
42}