面向测试用例优先排序的超启发式算法库构建研究
发布时间：2021-06-01 23:33
超启发式算法是一种启发式算法的启发式搜索方法,它通过启发式策略,可以动态选择、组合或生成一系列启发式算法来解决问题规模巨大的搜索难题。超启发式算法框架由顶层策略层与底层算法层构成,策略层提供了管理和操控不同算法的方法,而算法层则是由针对特定问题的多个算法构成。目前已有很多顶层策略层的研究,但是对于超启发式算法的底层算法层,通常是采用固定数目的同类算法来构建算法库,针对算法数量、多种类算法共存等问题尚缺乏深入的研究。作为超启发式算法重要的组成部分,底层算法库的构建方法对超启发式算法的性能有重要的影响。一方面来说,底层算法库中算法数量的增加可以使超启发式算法解决不同问题的能力增强,但与此同时,也会给顶层策略的调度带来压力,影响超启发式算法的性能;另一方面来说,同种类型算法在解决特定问题上具有相同的优缺点,例如全局优化算法虽然可以找到全局近似最优解,但是由于面向的是全部搜索空间,导致它的搜索效率较慢。是否可以通过融合不同类别的算法来构造算法库,克服单一类型算法的局限性,进而提升超启发式算法的性能,成为一个亟待解决的问题。基于以上两部分内容,本文对底层算法库的构建方法进行了充分的研究。本课题从...
【文章来源】：北京化工大学北京市 211工程院校 教育部直属院校
【文章页数】：62 页
【学位级别】：硕士
【图文】：
图１－１超启发式算法框架??Ｆｉｇ．?１－１?Ｔｈｅ?ｆｒａｍｅｗｏｒｋ?ｏｆ?ｔｈｅ?Ｈｙｐｅｒ－ｈｅｕｒｉｓｔｉｃ?ａｌｇｏｒｉｔｈｍ??
表示。其中算法库中每一个算法都具有一??个层次分布值，通过算法每次迭代过程中的表现来对层次分布值进行更新，对于顶层??策略层来说，每次调度算法时根据决策向量中每个算法的层次分布值的大小，来进行??算法的选龋??ｆｉ?－?■??＾?ｐｒｅｓｅｎｔ?ｉｎｄｉｖｉｄｕａｌｓ??Ｆｒｏｎｔ?Ｈ?〇?Ｌａｓｔ?ｉｎｄｉｖｉｄｕａｌｓ??Ｆｒｏｎｔ?Ｈ－ｌ?＇Ｏ??、、、、?ｎＨ??Ｆｒｏｎｔ?１?．?．?ＮＨ??°－＇－〇?＊??＼?Ｎｈ．，???＾＾??图２－１两个目标下的层次分布策略??Ｆｉｇ．２－１?Ｈｉｅｒａｒｃｈｙ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｓｔｒａｔｅｇｙ?ｆｏｒ?ｔｗｏ?ｏｂｊｅｃｔｉｖｅ?ｏｐｔｉｍｉｚａｔｉｏｎ?ｐｒｏｂｌｅｍ??对于层次分布值的具体描述可见图２－１。在图２－１中，层次分布策略使用了上文??中提到的非支配排序，来对状态解进行了非支配排序。如图所示，其中ｆｌ和ｆ２代表??了两个优化目标，图中每个点代表了一个测试用例序列在两个目标上的取值，根据不??同个体间的支配情况，可以分成若干层。由于超启发式算法是通过不断迭代的过程来??找寻最优解，那么如何评价每个算法在当前执行阶段的好坏，就成为了如何进行算法??评价的核心。??层次分布策略通过将当前种群中的个体，与上一代种群中的个体进行非支配排??序，对个体进行分层。对应到图上，假设ｆｌ和ｆ２的值都是越大越好，那么最外层Ｆｒｏｎｔ??Ｈ代表了当前的Ｐａｒｅｔｏ前沿，这一层可以支配剩下的所有层。在每一层中，黑色的点??代表了当前算法产生的个体，而白色代表了上一个算法产生的个体。关于层次分布值??具体的计算公式为：??１１?
过采用单种元启发式算法结合不同的交叉算子和多种元启发式算??法结合不同交叉算子来构建超启发式算法库，以此来形成复杂性不同的算法库。??ＨＨ－ＮＳＧＡ：?ＮＳＧＡ－Ｈ?＋?６种交叉算子??，算雜＇??／???＼?ＨＨ－ＳＰＥＡ?：?ＳＰＥＡ２?＋?６种交叉算子??Ｉ???ＨＳＡ２?Ｉ??Ｉ?）?ｈｈ－ｔａｅａ：?ＴＡＥＡ?＋?６?种交叉算子??＼?ＰｉＳ＂］?／??＼?Ｖ???／?ＨＨ－ＡＬＬ?：?ＮＳＧＡ－ＩＩ，?ＳＰＥＡ２＞?ＴＡＥＡ??＋?６种交叉算子??图３－１四种不同复杂性的超启发式算法库??Ｆｉｇ．３－１?Ｆｏｕｒ?ｄｉｆｆｅｒｅｎｔ?ｃｏｍｐｌｅｘ?Ｈｙｐｅｒ－ｈｅｕｒｉｓｔｉｃ?ａｌｇｏｒｉｔｈｍ?ｌｉｂｒａｒｙ??目前已经有非常多的算法来解决测试用例优先排序问题，常见的有ＮＳＧＡ－ＩＩ，??ＳＰＥＡ，ＳＰＥＡ２，?ＴＡＥＡ等算法，本文通过这些元启发式算法结合不同交叉算子来扩充??算法库中算法的数目。通过这种方式，本文提出了四种不同复杂性的算法库，用来证??明本文提出的观点，如图３－１所示。四种算法库分别为ＨＨ－ＮＳＧＡ，ＨＨ－ＳＰＥＡ，??ＨＨ－ＴＡＥＡ和ＨＨ－ＡＬＬ。其中ＨＨ－ＮＳＧＡ是由ＮＳＧＡ－ＩＩ算法结合六种不同交叉算子形??成的由六种算法构成的算法库；ＨＨ－ＳＰＥＡ是由ＳＰＥＡ２算法结合六种不同交叉算子形??成的算法库；ＨＨ－ＴＡＥＡ是由ＴＡＥＡ算法结合六种不同交叉算子形成的算法库；??ＨＨ－ＡＬＬ是由ＮＳＧＡ－ＩＩ，ＳＰＥＡ２和ＴＡＥＡ三种算法分别结合六种交叉算子形成的由十??八种算法构成的算法库。前三种不同复杂性的算法库虽然算法数目相同，但是由于算??法的实现原理并不相
本文编号：3210372
【文章来源】：北京化工大学北京市 211工程院校 教育部直属院校
【文章页数】：62 页
【学位级别】：硕士
【图文】：
图１－１超启发式算法框架??Ｆｉｇ．?１－１?Ｔｈｅ?ｆｒａｍｅｗｏｒｋ?ｏｆ?ｔｈｅ?Ｈｙｐｅｒ－ｈｅｕｒｉｓｔｉｃ?ａｌｇｏｒｉｔｈｍ??
表示。其中算法库中每一个算法都具有一??个层次分布值，通过算法每次迭代过程中的表现来对层次分布值进行更新，对于顶层??策略层来说，每次调度算法时根据决策向量中每个算法的层次分布值的大小，来进行??算法的选龋??ｆｉ?－?■??＾?ｐｒｅｓｅｎｔ?ｉｎｄｉｖｉｄｕａｌｓ??Ｆｒｏｎｔ?Ｈ?〇?Ｌａｓｔ?ｉｎｄｉｖｉｄｕａｌｓ??Ｆｒｏｎｔ?Ｈ－ｌ?＇Ｏ??、、、、?ｎＨ??Ｆｒｏｎｔ?１?．?．?ＮＨ??°－＇－〇?＊??＼?Ｎｈ．，???＾＾??图２－１两个目标下的层次分布策略??Ｆｉｇ．２－１?Ｈｉｅｒａｒｃｈｙ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｓｔｒａｔｅｇｙ?ｆｏｒ?ｔｗｏ?ｏｂｊｅｃｔｉｖｅ?ｏｐｔｉｍｉｚａｔｉｏｎ?ｐｒｏｂｌｅｍ??对于层次分布值的具体描述可见图２－１。在图２－１中，层次分布策略使用了上文??中提到的非支配排序，来对状态解进行了非支配排序。如图所示，其中ｆｌ和ｆ２代表??了两个优化目标，图中每个点代表了一个测试用例序列在两个目标上的取值，根据不??同个体间的支配情况，可以分成若干层。由于超启发式算法是通过不断迭代的过程来??找寻最优解，那么如何评价每个算法在当前执行阶段的好坏，就成为了如何进行算法??评价的核心。??层次分布策略通过将当前种群中的个体，与上一代种群中的个体进行非支配排??序，对个体进行分层。对应到图上，假设ｆｌ和ｆ２的值都是越大越好，那么最外层Ｆｒｏｎｔ??Ｈ代表了当前的Ｐａｒｅｔｏ前沿，这一层可以支配剩下的所有层。在每一层中，黑色的点??代表了当前算法产生的个体，而白色代表了上一个算法产生的个体。关于层次分布值??具体的计算公式为：??１１?
过采用单种元启发式算法结合不同的交叉算子和多种元启发式算??法结合不同交叉算子来构建超启发式算法库，以此来形成复杂性不同的算法库。??ＨＨ－ＮＳＧＡ：?ＮＳＧＡ－Ｈ?＋?６种交叉算子??，算雜＇??／???＼?ＨＨ－ＳＰＥＡ?：?ＳＰＥＡ２?＋?６种交叉算子??Ｉ???ＨＳＡ２?Ｉ??Ｉ?）?ｈｈ－ｔａｅａ：?ＴＡＥＡ?＋?６?种交叉算子??＼?ＰｉＳ＂］?／??＼?Ｖ???／?ＨＨ－ＡＬＬ?：?ＮＳＧＡ－ＩＩ，?ＳＰＥＡ２＞?ＴＡＥＡ??＋?６种交叉算子??图３－１四种不同复杂性的超启发式算法库??Ｆｉｇ．３－１?Ｆｏｕｒ?ｄｉｆｆｅｒｅｎｔ?ｃｏｍｐｌｅｘ?Ｈｙｐｅｒ－ｈｅｕｒｉｓｔｉｃ?ａｌｇｏｒｉｔｈｍ?ｌｉｂｒａｒｙ??目前已经有非常多的算法来解决测试用例优先排序问题，常见的有ＮＳＧＡ－ＩＩ，??ＳＰＥＡ，ＳＰＥＡ２，?ＴＡＥＡ等算法，本文通过这些元启发式算法结合不同交叉算子来扩充??算法库中算法的数目。通过这种方式，本文提出了四种不同复杂性的算法库，用来证??明本文提出的观点，如图３－１所示。四种算法库分别为ＨＨ－ＮＳＧＡ，ＨＨ－ＳＰＥＡ，??ＨＨ－ＴＡＥＡ和ＨＨ－ＡＬＬ。其中ＨＨ－ＮＳＧＡ是由ＮＳＧＡ－ＩＩ算法结合六种不同交叉算子形??成的由六种算法构成的算法库；ＨＨ－ＳＰＥＡ是由ＳＰＥＡ２算法结合六种不同交叉算子形??成的算法库；ＨＨ－ＴＡＥＡ是由ＴＡＥＡ算法结合六种不同交叉算子形成的算法库；??ＨＨ－ＡＬＬ是由ＮＳＧＡ－ＩＩ，ＳＰＥＡ２和ＴＡＥＡ三种算法分别结合六种交叉算子形成的由十??八种算法构成的算法库。前三种不同复杂性的算法库虽然算法数目相同，但是由于算??法的实现原理并不相
本文编号：3210372
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3210372.html
