专栏首页数据魔术师代码 | 自适应大邻域搜索系列之(5) - ALNS_Iteration_Status和ALNS_Parameters的代码解析

代码 | 自适应大邻域搜索系列之(5) - ALNS_Iteration_Status和ALNS_Parameters的代码解析

依旧写在前面

上一篇推文 代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析 说了,后面的代码难度直线下降,各位小伙伴可以放n的100次方心了。今天讲讲一些细枝末节,就是前面一直有提到的参数和一些状态的记录代码。

这个简单啦,小编也不作过多解释了。大家直接看代码都能看懂,不过小编还是会把逻辑结构给大家梳理出来的。好了,开始干活。

01 ALNS_Iteration_Status

这个类,咳咳,不是抽象类了哈。主要用来记录ALNS迭代过程中的一些中间变量和状态等。

主要是成员变量,成员函数都是简单的getter(获取成员变量的接口)或者setter(设置成员变量的接口)。

所以这里就把成员变量贴出来好了,各个变量记录的内容注释也写得很详细,小编就不做多赘述以免扰乱了大家看代码的心。

 1private:
 2
 3    //! Id of the iteration corresponding to this status.
 4    size_t iterationId;
 5
 6    //! Number of iteration since the last improvement of the BKS
 7    size_t nbIterationWithoutImprovement;
 8
 9    //! Number of iteration since the last improvement of the BKS
10    //! or the last reload of the best known solution.
11    size_t nbIterationWithoutImprovementSinceLastReload;
12
13    //! Number of iterations since the last improvement of the current
14    //! solution.
15    size_t nbIterationWithoutImprovementCurrent;
16
17    //! Number of iterations without transition.
18    size_t nbIterationWithoutTransition;
19
20    //! Indicate if a new best solution has been obtained.
21    State newBestSolution;
22
23    //! Indicate if the new solution has been accepted as the
24    //! current solution.
25    State acceptedAsCurrentSolution;
26
27    //! Indicate if the new solution is already known.
28    State alreadyKnownSolution;
29
30    //! Indicate if the new solution improve the current solution.
31    State improveCurrentSolution;
32
33    //! Indicate if a local search operator has been used.
34    State localSearchUsed;
35
36    //! Indicate if solution has been improved by local search.
37    State improveByLocalSearch;
38
39    //! Indicate if the solution has already been repaired.
40    State alreadyRepaired;
41
42    //! Indicate if the new solution has already been destroyed.
43    State alreadyDestroyed;
44
45};

02 ALNS_Parameters

该类是ALNS运行过程中的一些参数设置,和上面的ALNS_Iteration_Status差不多。

主要功能集中在成员变量上,成员函数都是简单的getter(获取成员变量的接口)或者setter(设置成员变量的接口)。

照例把成员变量贴出来吧~

  1public:
  2
  3    //! Enumeration representing the various kind of stopping criteria.
  4    //! MAX_IT: the maximum number of iterations.
  5    //! MAX_RT: the maximum run time.
  6    //! MAX_IT_NO_IMP: the maximum number of iterations without improvement.
  7    //! ALL: a mix of the MAX_IT, MAX_RT and MAX_IT_NO_IMP.
  8    enum StoppingCriteria {
  9        MAX_IT,
 10        MAX_RT,
 11        MAX_IT_NO_IMP,
 12        ALL
 13    };
 14
 15    //! An enumeration listing a set of packaged AcceptanceModule Implementation.
 16    enum AcceptanceCriterioKind {
 17        SA
 18    };
 19protected:
 20    //! Maximum number of iterations performed by the ALNS.
 21    size_t maxNbIterations;
 22
 23    //! Maximum running time of the ALNS.
 24    double maxRunningTime;
 25
 26    //! Maximum number of iterations without any improvement.
 27    size_t maxNbIterationsNoImp;
 28
 29    //! Which stopping criterion should be used.
 30    StoppingCriteria stopCrit;
 31
 32    //! Indicate if noise should be used.
 33    bool noise;
 34
 35    //! Indicate after how many iterations should the scores of
 36    //! the operators be recomputed.
 37    size_t timeSegmentsIt;
 38
 39    //! Indicate the number of iterations that should be performed
 40    //! before reinitialization of the scores of the operators.
 41    size_t nbItBeforeReinit;
 42
 43    //! score adjustment parameter in case the last remove-insert
 44    //! operation resulted in a new global best solution
 45    int sigma1;
 46
 47    //! score adjustment parameter in case that the last remove-insert
 48    //! operation resulted in a solution that has not been accepted before and
 49    //! the objective value is better than the objective value of current solution
 50    int sigma2;
 51
 52    //! score adjustment parameter in case that the last remove-insert
 53    //! operation resulted in a solution that has not been accepted before and such
 54    //! that the score objective value is worse than the one of current solution but
 55    //! the solution was accepted.
 56    int sigma3;
 57
 58    //! reaction factor 0 <= rho <= 1 for the update of the weights of the
 59    //! operators.
 60    double rho;
 61
 62    //! The minimum possible weight for an operator.
 63    double minimumWeight;
 64
 65    //! The maximum possible weight for an operator.
 66    double maximumWeight;
 67
 68    //! Indicates the probability of using noised operators.
 69    double probabilityOfNoise;
 70
 71    //! Kind of acceptance criterion used.
 72    AcceptanceCriterioKind acKind;
 73
 74    //! patht to the configuration file of the acceptance criterion.
 75    std::string acPath;
 76
 77    //! path to the file where the global stats have to be saved.
 78    std::string statsGlobPath;
 79
 80    //! path to the file where the operators stats have to be saved.
 81    std::string statsOpPath;
 82
 83    //! Indicate every each iteration logging is done. 不懂看后面。
 84    int logFrequency;
 85
 86    //! A set of forbidden operators. 不懂看后面。
 87    std::vector<std::string> forbidenOperators;
 88
 89    //! A set of forbidden local search operators. 不懂看后面。
 90    std::vector<std::string> forbidenLsOperators;
 91
 92    //! The minimum percentage of the solution destroyed by the destroy operators.
 93    int minDestroyPerc;
 94
 95    //! The maximum percentage of the solution destroyed by the destroy operators.
 96    int maxDestroyPerc;
 97
 98    //! Indicate after how many iterations without improvement
 99    //! does the best known solution is reloaded.
100    size_t reloadFrequency;
101
102    //! Indicate if local search should be used.
103    bool performLocalSearch;
104
105    //! When the optimization process start, the parameters
106    //! should not be modified. lock is set to true when the
107    //! optimization begin. If the setter of the value
108    //! of one parameter is called while lock is true, an
109    //! error is raised.
110    bool lock;
111
112};

不过有几个变量大家看了注释可能还不太明白是干嘛用的。在这里再解释一下。

logFrequency隔多少次迭代输出一下当前的信息。直接给大家上两个图让大家心领神会一下:

(logFrequency = 1)

(logFrequency = 100)

懂了吧。?

forbidenOperators是禁止的某些repair和destroy方法的集合,学过禁忌搜索的都知道这意味着什么,有些repair和destroy方法效果太差劲了,所以我们把它们给ban掉。

forbidenLsOperators和forbidenOperators差不多,不过它是禁止的某些LocalSearch方法的集合,效果太差嘛。。。

03 再论ALNS_Parameters

关于ALNS_Parameters它的大部分成员函数是简单的getter(获取成员变量的接口)或者setter(设置成员变量的接口)。

但其CPP文件中,还有一个函数是从xml文件读取相应参数的。代码就不具体介绍了,主要是xml文件操作的一些api的使用,有现成的lib库,感兴趣的同学了解一下。

至于为什么用xml文件呢?其实直接把参数写死在程序里面也是可以的不过读取xml文件获取相应的参数更符合标准,在实际生产中也更方便实用而已。

04 小结

至此,整一个ALNS模块已经讲得差不多了,不知道大家都看懂了没有。看不懂的话可以多看几遍,很多地方也只是小编个人的理解,不一定正确,如果你觉得你有更好的想法,也可以联系小编一起讨论。

后面再出多几篇估计就差不多了。把判断接受准则讲讲,把局部搜索讲讲就差不多可以了。最后谢谢大家一路过来的支持哈。

---The End---

文案 && 编辑:邓发珩

审稿:庄浩城

指导老师: 秦时明岳(华中科技大学管理学院)

本文分享自微信公众号 - 数据魔术师(data-magician)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • docker中安装mycat

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1149268
  • axis2:用ant脚本生成webservice client 端的java/c代码

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • gsoap入门:Schema类型映射塈将xsd:date类型转为struct tm

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • minigui:静态编译连接mgncs库时遇到的xml2的问题

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • gsoap入门:gsoap的plugin机制说明塈使用plugin实现调试soap函数时显示

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • gsoap入门:C/C++代码生成及编译

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • maven:升级到java 8 导致的插件报错 maven-plugin-plugin:3.2:descriptor

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • minigui: 基于miniStudio1.2.1创建模式对话框(DialogBox)

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • gsoap入门:解决axis2服务器返回错误

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648
  • java:自动搜索不同位置的properties文件并加载

    版权声明:本文为博主原创文章,转载请注明源地址。 https://blog.csdn.net...

    用户1148648

扫码关注云+社区

领取腾讯云代金券