基于混合搜索的含逻辑“与”“或”的RM优化算法
发布时间：2021-07-14 02:24
相对于标准约束优化问题,广义约束优化问题（或称析取优化问题）的等式或不等式约束条件中不仅包含逻辑"与"关系,还含有逻辑"或"关系.单调速率（RM）优化问题是广义约束优化问题的一个重要应用.目前RM优化问题已有的解法包括函数变换、混合整数规划、线性规划搜索等算法.随着任务数的增多,这些算法的求解时间较长.提出一种基于线性规划的深度广度混合搜索算法（LPHS）,将广义约束优化问题拆分成若干子问题,建立线性规划搜索树,合理选择搜索顺序,利用动态剪枝算法减小子问题的规模,最终求得最优解.实验结果表明,LPHS算法比其他方法有明显的效率提升.研究成果与计算机基础理论中的可满足性模理论的研究相结合,有助于提高可满足性模理论问题的求解效率,促进该理论在程序验证、符号执行等领域的进一步应用.
【文章来源】：软件学报. 2017,28(10)北大核心EICSCD
【文章页数】：14 页
【部分图文】：
RM优化问题约束条件树
这几组实验中均有未解出的问题,这表明,LPS方法的有效性并不能得到保证,进入局部搜索的陷阱后会有难以跳出的情况发生.为了进一步比较两种算法求解时间的波动性,我们统计了每组任务中求解时间的方差,由于计算结果的平均时间数值差异较大,我们先将每组数据均除以该组的平均运行时间(超时用例统一用1000s计算),统计的方差结果如图3所示.从图中可以看出,LPS在求解相同规模的任务时,求解时间的波动性比LPHS方法大很多.Fig.2ComparisionofexecutiontimebetweenFig.3VarianceofexcectuiontimewiththeLPSandLPHSmethodsametasknumber图2LPS与LPHS算法求解时间比较图3相同问题规模的求解时间方差LPHS算法比LPS方法效率更高的原因主要包括如下两点.(1)LPS算法在深度优先搜索中,没有确定同一层可选子问题求解的优先顺序,单纯使用了深度优先算法.而LPHS算法通过广度优先搜索,将同一层各子节点约束下的最优值进行排序,从最优值大的子节点开始计算.即对Node1和Node2两个节点,假设Node1节点的最优值opt1小于Node2节点的最优值opt2,LPHS算法会先求解Node2的子节点.因为Node2子节点求出的最优值opt有可能大于opt1时,此时可以将Node1节点剪掉,避免了对Node1子节点的计算,所以LPHS算法的混合搜索策略比LPS算法的深度优先策略更加高效.(2)RM优化问题在转化为搜索树后,对于任一节点Nodeparent=1111nknnnknnPROBhhh,在它的所有子节点中,可能存在一个节点Nodechild1111nknnnknknnPROBhhhh,使得当Nodeparent中约束条件满足时,Nodechild约束条件也满足,LPS方法没有考虑父子节点之间存在的上述关系,而LPHS方法通过第3.4节中的动态剪枝算法对父子节点关系进行了判断,若N
这几组实验中均有未解出的问题,这表明,LPS方法的有效性并不能得到保证,进入局部搜索的陷阱后会有难以跳出的情况发生.为了进一步比较两种算法求解时间的波动性,我们统计了每组任务中求解时间的方差,由于计算结果的平均时间数值差异较大,我们先将每组数据均除以该组的平均运行时间(超时用例统一用1000s计算),统计的方差结果如图3所示.从图中可以看出,LPS在求解相同规模的任务时,求解时间的波动性比LPHS方法大很多.Fig.2ComparisionofexecutiontimebetweenFig.3VarianceofexcectuiontimewiththeLPSandLPHSmethodsametasknumber图2LPS与LPHS算法求解时间比较图3相同问题规模的求解时间方差LPHS算法比LPS方法效率更高的原因主要包括如下两点.(1)LPS算法在深度优先搜索中,没有确定同一层可选子问题求解的优先顺序,单纯使用了深度优先算法.而LPHS算法通过广度优先搜索,将同一层各子节点约束下的最优值进行排序,从最优值大的子节点开始计算.即对Node1和Node2两个节点,假设Node1节点的最优值opt1小于Node2节点的最优值opt2,LPHS算法会先求解Node2的子节点.因为Node2子节点求出的最优值opt有可能大于opt1时,此时可以将Node1节点剪掉,避免了对Node1子节点的计算,所以LPHS算法的混合搜索策略比LPS算法的深度优先策略更加高效.(2)RM优化问题在转化为搜索树后,对于任一节点Nodeparent=1111nknnnknnPROBhhh,在它的所有子节点中,可能存在一个节点Nodechild1111nknnnknknnPROBhhhh,使得当Nodeparent中约束条件满足时,Nodechild约束条件也满足,LPS方法没有考虑父子节点之间存在的上述关系,而LPHS方法通过第3.4节中的动态剪枝算法对父子节点关系进行了判断,若N
【参考文献】：
期刊论文
[1]基于树状线性规划搜索的单调速率优化设计[J]. 陈力,王永吉,吴敬征,吕荫润. 软件学报. 2015(12)
[2]基于逻辑“或”约束优化的实时系统设计[J]. 刘军祥,王永吉,王源,邢建生,曾海涛. 软件学报. 2006(07)
[3]单调速率及其扩展算法的可调度性判定[J]. 王永吉,陈秋萍. 软件学报. 2004(06)
本文编号：3283216
【文章来源】：软件学报. 2017,28(10)北大核心EICSCD
【文章页数】：14 页
【部分图文】：
RM优化问题约束条件树
这几组实验中均有未解出的问题,这表明,LPS方法的有效性并不能得到保证,进入局部搜索的陷阱后会有难以跳出的情况发生.为了进一步比较两种算法求解时间的波动性,我们统计了每组任务中求解时间的方差,由于计算结果的平均时间数值差异较大,我们先将每组数据均除以该组的平均运行时间(超时用例统一用1000s计算),统计的方差结果如图3所示.从图中可以看出,LPS在求解相同规模的任务时,求解时间的波动性比LPHS方法大很多.Fig.2ComparisionofexecutiontimebetweenFig.3VarianceofexcectuiontimewiththeLPSandLPHSmethodsametasknumber图2LPS与LPHS算法求解时间比较图3相同问题规模的求解时间方差LPHS算法比LPS方法效率更高的原因主要包括如下两点.(1)LPS算法在深度优先搜索中,没有确定同一层可选子问题求解的优先顺序,单纯使用了深度优先算法.而LPHS算法通过广度优先搜索,将同一层各子节点约束下的最优值进行排序,从最优值大的子节点开始计算.即对Node1和Node2两个节点,假设Node1节点的最优值opt1小于Node2节点的最优值opt2,LPHS算法会先求解Node2的子节点.因为Node2子节点求出的最优值opt有可能大于opt1时,此时可以将Node1节点剪掉,避免了对Node1子节点的计算,所以LPHS算法的混合搜索策略比LPS算法的深度优先策略更加高效.(2)RM优化问题在转化为搜索树后,对于任一节点Nodeparent=1111nknnnknnPROBhhh,在它的所有子节点中,可能存在一个节点Nodechild1111nknnnknknnPROBhhhh,使得当Nodeparent中约束条件满足时,Nodechild约束条件也满足,LPS方法没有考虑父子节点之间存在的上述关系,而LPHS方法通过第3.4节中的动态剪枝算法对父子节点关系进行了判断,若N
这几组实验中均有未解出的问题,这表明,LPS方法的有效性并不能得到保证,进入局部搜索的陷阱后会有难以跳出的情况发生.为了进一步比较两种算法求解时间的波动性,我们统计了每组任务中求解时间的方差,由于计算结果的平均时间数值差异较大,我们先将每组数据均除以该组的平均运行时间(超时用例统一用1000s计算),统计的方差结果如图3所示.从图中可以看出,LPS在求解相同规模的任务时,求解时间的波动性比LPHS方法大很多.Fig.2ComparisionofexecutiontimebetweenFig.3VarianceofexcectuiontimewiththeLPSandLPHSmethodsametasknumber图2LPS与LPHS算法求解时间比较图3相同问题规模的求解时间方差LPHS算法比LPS方法效率更高的原因主要包括如下两点.(1)LPS算法在深度优先搜索中,没有确定同一层可选子问题求解的优先顺序,单纯使用了深度优先算法.而LPHS算法通过广度优先搜索,将同一层各子节点约束下的最优值进行排序,从最优值大的子节点开始计算.即对Node1和Node2两个节点,假设Node1节点的最优值opt1小于Node2节点的最优值opt2,LPHS算法会先求解Node2的子节点.因为Node2子节点求出的最优值opt有可能大于opt1时,此时可以将Node1节点剪掉,避免了对Node1子节点的计算,所以LPHS算法的混合搜索策略比LPS算法的深度优先策略更加高效.(2)RM优化问题在转化为搜索树后,对于任一节点Nodeparent=1111nknnnknnPROBhhh,在它的所有子节点中,可能存在一个节点Nodechild1111nknnnknknnPROBhhhh,使得当Nodeparent中约束条件满足时,Nodechild约束条件也满足,LPS方法没有考虑父子节点之间存在的上述关系,而LPHS方法通过第3.4节中的动态剪枝算法对父子节点关系进行了判断,若N
【参考文献】：
期刊论文
[1]基于树状线性规划搜索的单调速率优化设计[J]. 陈力,王永吉,吴敬征,吕荫润. 软件学报. 2015(12)
[2]基于逻辑“或”约束优化的实时系统设计[J]. 刘军祥,王永吉,王源,邢建生,曾海涛. 软件学报. 2006(07)
[3]单调速率及其扩展算法的可调度性判定[J]. 王永吉,陈秋萍. 软件学报. 2004(06)
本文编号：3283216
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3283216.html
