代码 | 自适应大邻域搜索系列之(2) - ALNS算法主逻辑结构解析

 1 //! The current solution.
 2 ISolution* currentSolution;
 3
 4 //! The acceptance criteria to be used.
 5 IAcceptanceModule* acceptanceCriterion;
 6
 7 //! The parameters to be used.
 8 ALNS_Parameters* param;
 9
10 //! Manager of the operators.
11 AOperatorManager* opManager;
12
13 //! Manager of the best solutions.
14 IBestSolutionManager* bestSolManager;
15
16 //! Manager of the local search operators.
17 ILocalSearchManager* lsManager;
18
19 //! The number of iterations since last weight recomputation.
20 size_t nbIterationsWC;
21
22 //! The current number of iterations.
23 size_t nbIterations;
24
25 //! The current number of iterations without improvement.
26 size_t nbIterationsWithoutImprovement;
27
28 //! The number of iterations without improvement of the current solution.
29 size_t nbIterationsWithoutImprovementCurrent;
30
31 //! The number of iterations without acceptation of a transition.
32 size_t nbIterationsWithoutTransition;
33
34 //! The number of iterations since the last call to a local search
35 //! operator.
36 size_t nbIterationsWithoutLocalSearch;
37
38 //! The time the optimization process started.
39 clock_t startingTime;
40
41 //! A lower bound on the optimum solution cost.
42 double lowerBound;
43
44 //! A set containing the hash keys of the encountred solutions.
45 std::set<long long> knownKeys;
46
47 //! An object to compute some statistics about the solving process.
48 Statistics stats;
49
50 //! An object representing the status of the last iteration.
51 ALNS_Iteration_Status status;
52
53 //! A list of object that we need to update at the end of each iteration. 不懂往下看
54 std::vector<IUpdatable*> updatableStructures;
55
56 std::string name;

 1 //! Constructor.
 2 //! \param name the name of the instance.
 3 //! \param initialSolution the starting solution that is going to be optimized.
 4 //! \param acceptanceCrit the module that determine whether or not a new solution
 5 //! is accepted as the current solution.
 6 //! \param parameters the set of parameters to be use by the ALNS.
 7 //! \param opMan an operator manager.
 8 ALNS(std::string instanceName,
 9     ISolution& initialSolution,
10     IAcceptanceModule& acceptanceCrit,
11      ALNS_Parameters& parameters,
12      AOperatorManager& opMan,
13      IBestSolutionManager& solMan,
14      ILocalSearchManager& lsMan);
15
16 //! Destructor.
17 virtual ~ALNS();
18
19 //! This method launch the solving process.
20 //! \return true if a feasible solution is found,
21 //! false otherwise.
22 bool solve();
23
24 //! This method seeks if a solution is already known,
25 //! if not it is added to the set of known solutions.
26 //! \param sol the solution to be checked.
27 //! \return true if the solution was unknown, false otherwise.
28 bool checkAgainstKnownSolution(ISolution& sol);
29
30 //! This method perform one iteration of the ALNS solving
31 //! process.
32 void performOneIteration();
33
34 //! This method check whether or not the stopping criteria is met.
35 bool isStoppingCriterionMet();
36
37 //! Determine whether or not the new solution is better than the
38 //! best known solution.
39 bool isNewBest(ISolution* newSol);
40
41 //! \return the number of known solutions.
42 size_t getNumberKnownSolutions(){return knownKeys.size();};
43
44 //! Determine whether or not the new solution should be accepted
45 //! as the current solution.
46 bool transitionCurrentSolution(ISolution* newSol);
47
48 //! Return a pointer to the best known solution.
49 IBestSolutionManager* getBestSolutionManager(){return bestSolManager;};
50
51 //! Add an object to the list of object to be updated at the end of each
52 //! iteration of the ALNS.
53 //! \param up the updatable object to be added.  不懂往下看
54 void addUpdatable(IUpdatable& up){updatableStructures.push_back(&up);};
55
56 //! Destroy the manager that have been provided at the construction of
57 //! the instance.
58 void end();

 1 //构造
 2 ALNS::ALNS(string instanceName,
 3          ISolution& initialSolution,
 4          IAcceptanceModule& acceptanceCrit,
 5          ALNS_Parameters& parameters,
 6          AOperatorManager& opMan,
 7          IBestSolutionManager& bestSolMan,
 8          ILocalSearchManager& lsMan)
 9 {
10     name = instanceName;
11     currentSolution = initialSolution.getCopy();
12     acceptanceCriterion = &acceptanceCrit;
13     param = &parameters;
14     lowerBound = -DBL_MAX;
15     nbIterationsWC = 0;
16     nbIterations = 0;
17     nbIterationsWithoutImprovement = 0;
18     opManager = &opMan;
19     bestSolManager = &bestSolMan;
20     lsManager = &lsMan;
21
22     opManager->setStatistics(&stats);
23
24     // We add the initial solution in the best solution manager.
25     bestSolManager->isNewBestSolution(initialSolution);
26
27     nbIterationsWithoutImprovementCurrent = 0;
28 
29     nbIterationsWithoutTransition = 0;
30
31     nbIterationsWithoutLocalSearch = 0;
32 }
33 //析构
34 ALNS::~ALNS()
35 {
36     delete currentSolution;
37 }

  1 void ALNS::performOneIteration()
  2 {
  3     //重新初始化一些状态量。
  4     status.partialReinit();
  5     //选择Repair和Destroy方法
  6     ARepairOperator& repair = opManager->selectRepairOperator();
  7     ADestroyOperator& destroy = opManager->selectDestroyOperator();
  8 
  9     ISolution* newSolution = currentSolution->getCopy();
 10     //输出迭代次数等信息。 param->getLogFrequency()获取的是logFrequency变量的值，logFrequency变量表示的意思是每隔多少次输出一下相关信息。
 11     if(nbIterations % param->getLogFrequency() == 0)
 12     {
 13         cout << "[ALNS] it. " << nbIterations << " best sol: " << (*(bestSolManager->begin()))->getObjectiveValue() << " nb known solutions: " << knownKeys.size() << endl;
 14     }
 15     //destroy操作
 16     destroy.destroySolution(*newSolution);
 17     //更新状态
 18     status.setAlreadyDestroyed(ALNS_Iteration_Status::TRUE);
 19     status.setAlreadyRepaired(ALNS_Iteration_Status::FALSE);//未进行repair操作
 20     //表示newSolution还是status的信息对解进行更新。这里只提供接口，后面应用的时候要具体重写。
 21     for(vector<IUpdatable*>::iterator it = updatableStructures.begin(); it != updatableStructures.end(); it++)
 22     {
 23         (*it)->update(*newSolution,status);
 24     }
 25     //进行repair操作
 26     repair.repairSolution(*newSolution);
 27     status.setAlreadyRepaired(ALNS_Iteration_Status::TRUE);
 28     //更新迭代次数
 29     nbIterations++;
 30     status.setIterationId(nbIterations);
 31     nbIterationsWC++;
 32
 33     double newCost = newSolution->getObjectiveValue();
 34     //判断新生产的解是不是新的最优解
 35     isNewBest(newSolution);
 36     //判断新生成的解之前有没有出现过
 37     checkAgainstKnownSolution(*newSolution);
 38     //判断新生成的解和当前解谁更优
 39     bool betterThanCurrent = (*newSolution)<(*currentSolution);
 40     //如果新生成的解更优
 41     if(betterThanCurrent)
 42     {
 43         nbIterationsWithoutImprovementCurrent = 0;//清0
 44         status.setImproveCurrentSolution(ALNS_Iteration_Status::TRUE);
 45     }
 46     //否则
 47     else
 48     {
 49         nbIterationsWithoutImprovementCurrent++;
 50         status.setImproveCurrentSolution(ALNS_Iteration_Status::FALSE);//解没有得到提高
 51     }
 52     //更新状态
 53     status.setNbIterationWithoutImprovementCurrent(nbIterationsWithoutImprovementCurrent);
 54     //param->getPerformLocalSearch()指出要不要用LocalSearch，然后再用LocalSearch对新生成的解进行搜索。lsManager->useLocalSearch(*newSolution,status)将返回true如果经过LocalSearch之后的解有改进的话。
 55     if(param->getPerformLocalSearch() && lsManager->useLocalSearch(*newSolution,status))
 56     {
 57     //判断LocalSearch之后的新解是不是最优解。
 58         bestSolManager->isNewBestSolution(*newSolution);
 59     }
 60     //判断是否接受当前的解。
 61     bool transitionAccepted = transitionCurrentSolution(newSolution);
 62     //如果接受
 63     if(transitionAccepted)
 64     {
 65         status.setAcceptedAsCurrentSolution(ALNS_Iteration_Status::TRUE);
 66         nbIterationsWithoutTransition = 0;
 67     }
 68     //否则
 69     else
 70     {
 71         status.setAcceptedAsCurrentSolution(ALNS_Iteration_Status::FALSE);
 72         nbIterationsWithoutTransition++;
 73     }
 74     //更新信息
 75     status.setNbIterationWithoutTransition(nbIterationsWithoutTransition);
 76     //再一次进行LocalSearch操作，以取得更好的效果。
 77     if(param->getPerformLocalSearch() && lsManager->useLocalSearch(*newSolution,status))
 78     {
 79         bestSolManager->isNewBestSolution(*newSolution);
 80         if(status.getAcceptedAsCurrentSolution() == ALNS_Iteration_Status::TRUE)
 81         {
 82             transitionCurrentSolution(newSolution);
 83         }
 84     }
 85     //对destroy,repair方法进行成绩更新。
 86     opManager->updateScores(destroy,repair,status);
 87 
 88     //记录本次迭代过程的一些信息。
 89     stats.addEntry(static_cast<double>(clock()-startingTime)/CLOCKS_PER_SEC,nbIterations,destroy.getName(),repair.getName(),newCost,currentSolution->getObjectiveValue(),(*(bestSolManager->begin()))->getObjectiveValue(),knownKeys.size());
 90
 91     //更新destroy,repair方法的权重。是在进行了一定迭代次数以后才更新的，具体次数由param->getTimeSegmentsIt()获得。
 92     if(nbIterationsWC % param->getTimeSegmentsIt() == 0)
 93     {
 94         opManager->recomputeWeights();
 95         nbIterationsWC = 0;
 96     }
 97     //接口，在求解的过程中某些内容需要更新。
 98     for(vector<IUpdatable*>::iterator it = updatableStructures.begin(); it != updatableStructures.end(); it++)
 99     {
100         (*it)->update(*newSolution,status);
101     }
102     //如果有需要，将当前解转变成最优解再进行下一次迭代操作。
103     currentSolution = bestSolManager->reloadBestSolution(currentSolution,status);
104
105     delete newSolution;
106 }

 1 bool ALNS::checkAgainstKnownSolution(ISolution& sol)
 2 {
 3     bool notKnownSolution = false;
 4     long long keySol = sol.getHash();
 5     //哈希值匹配
 6     if(knownKeys.find(keySol) == knownKeys.end())
 7     {
 8         notKnownSolution = true;
 9         knownKeys.insert(keySol);
10     }
11     //之前已经出现过的解。
12     if(!notKnownSolution)
13     {
14         status.setAlreadyKnownSolution(ALNS_Iteration_Status::TRUE);
15     }
16     //全新的解，之前没有出现过。
17     else
18     {
19         status.setAlreadyKnownSolution(ALNS_Iteration_Status::FALSE);
20     }
21     return notKnownSolution;
22 }

 1 bool ALNS::isNewBest(ISolution* newSol)
 2 {
 3     //如果是新的最优解
 4     if(bestSolManager->isNewBestSolution(*newSol))
 5     {
 6         status.setNewBestSolution(ALNS_Iteration_Status::TRUE);
 7         nbIterationsWithoutImprovement = 0;
 8         status.setNbIterationWithoutImprovement(nbIterationsWithoutImprovement);
 9         status.setNbIterationWithoutImprovementSinceLastReload(0);
10         return true;
11     }
12     //如果不是。
13     else
14     {
15         status.setNewBestSolution(ALNS_Iteration_Status::FALSE);
16         nbIterationsWithoutImprovement++;
17         status.setNbIterationWithoutImprovement(nbIterationsWithoutImprovement);
18         status.setNbIterationWithoutImprovementSinceLastReload(status.getNbIterationWithoutImprovementSinceLastReload()+1);
19         return false;
20     }
21 }

 1 bool ALNS::transitionCurrentSolution(ISolution* newSol)
 2 {
 3     //如果接受。
 4     if(acceptanceCriterion->transitionAccepted(*bestSolManager,*currentSolution,*newSol,status))
 5     {
 6         delete currentSolution;
 7         currentSolution = newSol->getCopy();
 8         return true;
 9     }
10     //不接受，原来解不变，什么也不做。
11     else
12     {
13         return false;
14     }
15 }

 1 bool ALNS::isStoppingCriterionMet()
 2 {
 3     //是否找到最优可行解。
 4     if((*(bestSolManager->begin()))->isFeasible() && (*(bestSolManager->begin()))->getObjectiveValue() == lowerBound)
 5     {
 6         return true;
 7     }
 8     else
 9     {
10         switch(param->getStopCrit())
11         {
12             //是否达到最大迭代次数。
13             case ALNS_Parameters::MAX_IT: {
14                 return nbIterations >= param->getMaxNbIterations();
15             }
16             //是否达到最大限制运行时间。
17             case ALNS_Parameters::MAX_RT: {
18                 clock_t currentTime = clock();
19                 double elapsed = (static_cast<double>(currentTime - startingTime)) / CLOCKS_PER_SEC;
20                 return elapsed >= param->getMaxRunningTime();
21             }
22             //the maximum number of iterations without improvement. 
23             case ALNS_Parameters::MAX_IT_NO_IMP: {
24                 return nbIterationsWithoutImprovement >= param->getMaxNbIterationsNoImp();
25             }
26            //a mix of the MAX_IT, MAX_RT and MAX_IT_NO_IMP.
27             case ALNS_Parameters::ALL: {
28                 if(nbIterations >= param->getMaxNbIterations())
29                 {
30                     return true;
31                 }
32                 if(nbIterationsWithoutImprovement >= param->getMaxNbIterationsNoImp())
33                 {
34                     return true;
35                 }
36                 clock_t currentTime = clock();
37                 double elapsed = (static_cast<double>(currentTime - startingTime)) / CLOCKS_PER_SEC;
38                 if(elapsed >= param->getMaxRunningTime())
39                 {
40                     return true;
41                 }
42                 return false;
43             }
44
45             default: {
46                 assert(false);
47                 return false;
48             }
49         }
50     }
51
52 }

 1 bool ALNS::solve()
 2 {
 3     startingTime = clock();
 4     param->setLock();
 5     acceptanceCriterion->startSignal();
 6     opManager->startSignal();
 7     stats.setStart();
 8     //如果没有遇到终止条件，那么将一次次迭代下去。
 9     while(!isStoppingCriterionMet())
10     {
11         performOneIteration();
12     }
13     //获取运行结果，返回解是否可行。
14     string pathGlob = param->getStatsGlobPath();
15     pathGlob += name;
16     pathGlob += ".txt";
17     string pathOp = param->getStatsOpPath();
18     pathOp += name;
19     pathOp += ".txt";
20     stats.generateStatsFile(pathGlob,pathOp);
21     return (*(bestSolManager->begin()))->isFeasible();
22 }