实值优化问题的非对称负相关搜索算法
发布时间：2021-10-19 06:50
现实世界中的许多应用与实值优化问题紧密相关.为了求解复杂的实值优化问题,一些研究工作提出不同的元启发式假设并设计相应的搜索策略.在搜索解空间过程中,如何平衡探索解空间新区域（多样化）与实现优质解利用（集约化）之间的关系,是提高元启发式搜索算法性能的关键因素之一.特别地,负相关搜索（negatively correlated search, NCS）通过在搜索进程中引入负相关的搜索趋势,促进了解的多样性,有效改进了并行爬山算法的搜索性能.负相关搜索将每一个搜索进程的搜索行为建模为概率分布,在此基础上,根据搜索进程的搜索范围的相对大小,将搜索行为进一步划分为全局搜索行为和局部搜索行为.然后提出一种新的元启发式搜索算法,即非对称负相关搜索（negatively correlated search with asymmetry, NSA）,它假设具有全局搜索行为的搜索进程应尽可能远离具有局部搜索行为的搜索进程.得益于搜索进程之间非对称的负相关的搜索趋势,提出的算法相比负相关搜索拥有更优的搜索效率.实验结果表明:相比成熟的搜索方法,非对称负相关搜索在20个多模态实值优化问题上取得了最佳的整体性能...
【文章来源】：计算机研究与发展. 2019,56(08)北大核心EICSCD
【文章页数】：12 页
【部分图文】：
图２二维解空间（标注等高线）的搜索示例Ｆｉｇ．２Ｉｌｌｕｓｔｒａｔｉｏｎｏｆｓｅａｒｃｈｂｅｈａｖｉｏｒｓｉｎａｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｓｅａｒｃｈｓｐａｃｅ
过种群大小，所以对大种群更友好的元启发式搜索并行化潜力更大，通常是更被青睐的算法．特别地，基于种群的搜索算法通常因为个体间频繁的信息交流与现实中昂贵的通信代价，导致并行化效率较低，无法谋求以种群规模交换迭代轮数的目的［２９］，因此消除个体之间不必要的通信可以很好地释放算法的并行潜力．这里设计实验研究了非对称负相关搜索在并行化方面的性能，并与负相关搜索进行比较．具体地，采用细粒度的“主－从模型”作为并行框架［３０］，如图５所示，主机负责控制搜索流程，每个计算单元享有一个独立的搜索进程，搜索进程之间的通信由主机转接．实验硬件环境为英特尔至强多核服务器集群，软件环境为Ｍａｔｌａｂ分布式计算系统．设定搜索算法的种群大小从１０增大到１００，相应地计算单元由１０个扩充到１００个，并且保持搜索算法在生成３０００００个候选解时终止，也就是说迭代轮数从３００００轮减少到３０００轮，记录下平均函数误差与算法运行时间的变化．Ｆｉｇ．５Ｆｉｎｅ－ｇａｉｎｅｄＭａｓｔｅｒ－Ｓｌａｖｅｓｐａｒａｌｌｅｌｆｒａｍｅｗｏｒｋ图５细粒度的“主－从模型”并行框架在３０维基准测试函数Ｆ７上的结果如图６和图７所示．通过观察图６可以得到，对于最小化基准测试函数，我们保持搜索算法生成候选解的个数，在牺牲迭代轮数的同时扩大种群的规模，搜索算法的性能受到不同程度上的影响．其中，非对称负相关搜索对于种群规模较大的情况适应较好，负相关搜索在种群规模极大的情况搜索
Ｍａｔｌａｂ分布式计算系统．设定搜索算法的种群大小从１０增大到１００，相应地计算单元由１０个扩充到１００个，并且保持搜索算法在生成３０００００个候选解时终止，也就是说迭代轮数从３００００轮减少到３０００轮，记录下平均函数误差与算法运行时间的变化．Ｆｉｇ．５Ｆｉｎｅ－ｇａｉｎｅｄＭａｓｔｅｒ－Ｓｌａｖｅｓｐａｒａｌｌｅｌｆｒａｍｅｗｏｒｋ图５细粒度的“主－从模型”并行框架在３０维基准测试函数Ｆ７上的结果如图６和图７所示．通过观察图６可以得到，对于最小化基准测试函数，我们保持搜索算法生成候选解的个数，在牺牲迭代轮数的同时扩大种群的规模，搜索算法的性能受到不同程度上的影响．其中，非对称负相关搜索对于种群规模较大的情况适应较好，负相关搜索在种群规模极大的情况搜索性能急剧下降，两者的相对差值呈多项函数趋势．这是由于负相关搜索在种群规模极大的情况容易出现因负相关产生的拥挤现象，也就是说个体集中在局部极值点附近且流通性较差．非对称负相关的元启发式假设只关注全局搜索行为，促进了个体的流通，有效缓解了拥挤现象，对基于大种群的大规模并行环境更友好．通过观察图７可以得到，在生成候选解的个数不变的情况下，非对称负相关搜索可以通过细粒度的并行化方法有效节约运行时间，并且种群规模越大，运行时间越短，这得益于随着种群规模扩大时算法迭代轮数减少．同时，并行化负相关搜索的运行时间随着种群规模的扩大反而急剧提升，这是由于种群规模扩大导致整体相关性的计算代价呈幂律提
本文编号：3444364
【文章来源】：计算机研究与发展. 2019,56(08)北大核心EICSCD
【文章页数】：12 页
【部分图文】：
图２二维解空间（标注等高线）的搜索示例Ｆｉｇ．２Ｉｌｌｕｓｔｒａｔｉｏｎｏｆｓｅａｒｃｈｂｅｈａｖｉｏｒｓｉｎａｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｓｅａｒｃｈｓｐａｃｅ
过种群大小，所以对大种群更友好的元启发式搜索并行化潜力更大，通常是更被青睐的算法．特别地，基于种群的搜索算法通常因为个体间频繁的信息交流与现实中昂贵的通信代价，导致并行化效率较低，无法谋求以种群规模交换迭代轮数的目的［２９］，因此消除个体之间不必要的通信可以很好地释放算法的并行潜力．这里设计实验研究了非对称负相关搜索在并行化方面的性能，并与负相关搜索进行比较．具体地，采用细粒度的“主－从模型”作为并行框架［３０］，如图５所示，主机负责控制搜索流程，每个计算单元享有一个独立的搜索进程，搜索进程之间的通信由主机转接．实验硬件环境为英特尔至强多核服务器集群，软件环境为Ｍａｔｌａｂ分布式计算系统．设定搜索算法的种群大小从１０增大到１００，相应地计算单元由１０个扩充到１００个，并且保持搜索算法在生成３０００００个候选解时终止，也就是说迭代轮数从３００００轮减少到３０００轮，记录下平均函数误差与算法运行时间的变化．Ｆｉｇ．５Ｆｉｎｅ－ｇａｉｎｅｄＭａｓｔｅｒ－Ｓｌａｖｅｓｐａｒａｌｌｅｌｆｒａｍｅｗｏｒｋ图５细粒度的“主－从模型”并行框架在３０维基准测试函数Ｆ７上的结果如图６和图７所示．通过观察图６可以得到，对于最小化基准测试函数，我们保持搜索算法生成候选解的个数，在牺牲迭代轮数的同时扩大种群的规模，搜索算法的性能受到不同程度上的影响．其中，非对称负相关搜索对于种群规模较大的情况适应较好，负相关搜索在种群规模极大的情况搜索
Ｍａｔｌａｂ分布式计算系统．设定搜索算法的种群大小从１０增大到１００，相应地计算单元由１０个扩充到１００个，并且保持搜索算法在生成３０００００个候选解时终止，也就是说迭代轮数从３００００轮减少到３０００轮，记录下平均函数误差与算法运行时间的变化．Ｆｉｇ．５Ｆｉｎｅ－ｇａｉｎｅｄＭａｓｔｅｒ－Ｓｌａｖｅｓｐａｒａｌｌｅｌｆｒａｍｅｗｏｒｋ图５细粒度的“主－从模型”并行框架在３０维基准测试函数Ｆ７上的结果如图６和图７所示．通过观察图６可以得到，对于最小化基准测试函数，我们保持搜索算法生成候选解的个数，在牺牲迭代轮数的同时扩大种群的规模，搜索算法的性能受到不同程度上的影响．其中，非对称负相关搜索对于种群规模较大的情况适应较好，负相关搜索在种群规模极大的情况搜索性能急剧下降，两者的相对差值呈多项函数趋势．这是由于负相关搜索在种群规模极大的情况容易出现因负相关产生的拥挤现象，也就是说个体集中在局部极值点附近且流通性较差．非对称负相关的元启发式假设只关注全局搜索行为，促进了个体的流通，有效缓解了拥挤现象，对基于大种群的大规模并行环境更友好．通过观察图７可以得到，在生成候选解的个数不变的情况下，非对称负相关搜索可以通过细粒度的并行化方法有效节约运行时间，并且种群规模越大，运行时间越短，这得益于随着种群规模扩大时算法迭代轮数减少．同时，并行化负相关搜索的运行时间随着种群规模的扩大反而急剧提升，这是由于种群规模扩大导致整体相关性的计算代价呈幂律提
本文编号：3444364
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3444364.html
