代码 | 自适应大邻域搜索系列之(7) - 局部搜索LocalSearch的代码解析

 1class ILocalSearch
 2{
 3public:
 4    //! Perform a local search on the solution.
 5    //! \return true if the solution is improved.
 6    virtual bool performLocalSearch(ISolution& sol)=0;
 7
 8    //! \return the name of the local search operator.
 9    virtual std::string getName()=0;
10};

 1class ILocalSearchManager
 2{
 3public:
 4
 5    //! \param sol the solution to be improved.
 6    //! \param status the status of the alns iteration.
 7    //! \return true if the solution has been improved.
 8    virtual bool useLocalSearch(ISolution& sol, ALNS_Iteration_Status& status)=0;
 9
10    //! Indicate that the optimization process starts.
11    virtual void startSignal()=0;
12};

 1class SimpleLocalSearchManager: public ILocalSearchManager {
 2public:
 3
 4    SimpleLocalSearchManager(ALNS_Parameters& parameters){param = &parameters;};
 5
 6    virtual ~SimpleLocalSearchManager(){};
 7
 8    //! \param sol the solution to be improved.
 9    //! \param status the status of the alns iteration.
10    //! \return true if the solution has been improved.
11    virtual bool useLocalSearch(ISolution& sol, ALNS_Iteration_Status& status);
12
13    //! Add a local search operator to the manager.
14    void addLocalSearchOperator(ILocalSearch& ls);
15
16
17    virtual void startSignal(){};
18private:
19    //! A vector containing the local search operators managed by the current instance.
20    std::vector<ILocalSearch*> localSearchOperators;
21
22    //! Parameters of the ALNS.
23    ALNS_Parameters* param;
24};

 1bool SimpleLocalSearchManager::useLocalSearch(ISolution& sol, ALNS_Iteration_Status& status)
 2{
 3    if(status.getNewBestSolution()!=ALNS_Iteration_Status::TRUE
 4        || status.getAcceptedAsCurrentSolution()!=ALNS_Iteration_Status::UNKNOWN)
 5    {
 6        return false;
 7    }
 8    else
 9    {
10        status.setLocalSearchUsed(ALNS_Iteration_Status::TRUE);
11        bool improvement;
12        do
13        {
14            improvement = false;
15            for(size_t i = 0; i < localSearchOperators.size(); i++)
16            {
17                improvement = localSearchOperators[i]->performLocalSearch(sol)||improvement;
18            }
19        }while(improvement);
20        if(improvement)
21        {
22            status.setImproveByLocalSearch(ALNS_Iteration_Status::TRUE);
23            return true;
24        }
25        else
26        {
27            status.setImproveByLocalSearch(ALNS_Iteration_Status::FALSE);
28            return false;
29        }
30    }
31}
32
33void SimpleLocalSearchManager::addLocalSearchOperator(ILocalSearch& ls)
34{
35    //TODO find out why the set.find() == set.end() does not work.
36    bool ok = true;
37    for(size_t i=0; i< param->getForbidenLsOperators().size() && ok; i++)
38    {
39        if(param->getForbidenLsOperators()[i] == ls.getName())
40        {
41            std::cout << "NO " << ls.getName() << std::endl;
42            ok = false;
43        }
44    }
45    if(ok)
46    {
47        localSearchOperators.push_back(&ls);
48    }
49
50}