基于适应度景观的元启发式算法算子调优策略研究

发布时间：2021-04-19 01:57

　　元启发式算法在求解现实生活中遇到的复杂组合优化问题时,显示出了它的优越性,常见的算法有禁忌搜索、模拟退火、遗传算法、迭代局部搜索等。这些算法基于局部搜索采用不同的策略使算法逃出局部最优,其中局部搜索使用的邻域算子定义了算法搜索空间中各个解之间的邻接关系,不适当的邻域算子会使得搜索变得无效,因此邻域算子的调优直接影响到元启发式算法的性能。为了更好地将算子调优策略与问题的结构特征相结合,弥补现有算子调优策略的不足,本文试图基于适应度景观对元启发式算法的邻域算子进行调优。适应度景观源于理论生物学,是遗传学家在利用数学模型理解生物个体的进化机制时提出的,该模型基于优化问题解的基因型、邻域算子和适应度函数,可以形象地刻画问题的结构。本文通过度量适应度景观的特征,凭借适应度景观分析对邻域算子进行调优。主要的研究内容如下:（1）鉴于物流配送在物流系统中的重要作用,本文以车辆路径问题为例,基于反转和互换两种邻域算子分别建立了车辆路径问题的适应度景观模型。（2）结合车辆路径问题解的特点,建立了距离空间并定义了相关的熵,从平均距离、平均步长、自相关函数、崎岖度以及局部最优解的适应度等角度,更加全面地度量适... 

【文章来源】：大连海事大学辽宁省 211工程院校

【文章页数】：81 页

【学位级别】：硕士

【部分图文】：

图３．１车辆路径问题算例结点分布??Ｆｉｇ．?３．１?Ｎｏｄｅｓ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｏｆ?Ｖｅｈｉｃ?

?基于适应度景观的元启发式算法算子调优策略研宄???随机选择Ｉ??亲代?１?２?３?４?５?６?｜?７?｜?８?［７￣??子代?１２７４５６３８９??图３．４互换算子??Ｆｉｇ．?３．４?Ｓｗａｐ?Ｏｐｅｒａｔｏｒ??反转算子在个体的基因型上任意选择两个切入点截取一段基因，然后将该段所含元??素的顺序反转，在车辆路径问题中即反转两个插入点之间的路线上客户结点的访问次序，??重新插入形成子代个体，如图３．５所示。与互换算子类似，反转算子的邻域大小同样为??Ｎ（Ｎ?－?１）／２。??随机截取ｊ??亲代?１２３４５６７８９??子代?１２６５４３７８９??图３．５反转算子??Ｆｉｇ．?３．５?Ｉｎｖｅｒｓｅ?Ｏｐｅｒａｔｏｒ??３．?５本章小结??本章首先对ＶＲＰ问题进行了简要介绍，阐述了包括组成要素，约束条件和目标函??数在内的三个明显特征，接着对车辆路径问题变体做了大概的分类，以及其的常用解决??算法在第一节末尾进行了罗列。第二小节利用数学语言对带有容量约束的车辆路径问题??进行了建模，确定了车辆路径问题解的目标函数。接着，第三小节对文章所使用算例的??数据来源做了说明并给出了各个节点的位置图示。为了完整地建立适应度景观模型，本??章最后对本文使用的编码方式和邻域算子进行了说明。??－２６?－??

图４．１距离的分布??Ｆｉｇ．?４．１?Ｄｉｓｔｒｉｂｕｔｉｏｎ?ｏｆ?Ｄｉｓｔａｎｃｅ??另外，Ｐｓ中熵的值明显要高于Ｐｉ

【参考文献】：
期刊论文
[1]混沌扰动模拟退火蚁群算法低碳物流路径优化[J]. 张立毅,王迎,费腾,周修飞.  计算机工程与应用. 2017(01)
[2]需求可拆分车辆路径问题的三阶段禁忌算法[J]. 熊浩,鄢慧丽.  系统工程理论与实践. 2015(05)
[3]带软时间窗整车物流配送路径优化研究[J]. 侯玉梅,贾震环,田歆,尉芳芳.  系统工程学报. 2015(02)
[4]车辆路径问题的快速多邻域迭代局部搜索算法[J]. 刘万峰,李霞.  深圳大学学报(理工版). 2015(02)
[5]基于自适应学习群体搜索技术的集成进化算法[J]. 薛羽,庄毅,许斌,张友益.  系统工程理论与实践. 2014(02)

博士论文
[1]智能优化算法表型空间的动态行为学分析与应用[D]. 王莽.中国科学技术大学 2017

硕士论文
[1]基于增强学习的启发式和元启发式搜索的参数调优策略[D]. 刘赛赛.电子科技大学 2016



本文编号：3146597