差分进化帝王蝶优化算法求解折扣{0-1}背包问题 被引量：21

1

作者 冯艳红 杨娟 +1 位作者 贺毅朝 王改革 《电子学报》 EI CAS CSCD 北大核心 2018年第6期1343-1350,共8页

帝王蝶优化算法(Monarch Butterfly Optimization,MBO)是一种新颖的群体智能算法,自从提出就在实际优化问题上表现出很好的性能.但是,帝王蝶优化算法的迁移算子采用随机选择两个个体来生成新个体,并没有记忆整个种群的最优解,容易造成... 帝王蝶优化算法(Monarch Butterfly Optimization,MBO)是一种新颖的群体智能算法,自从提出就在实际优化问题上表现出很好的性能.但是,帝王蝶优化算法的迁移算子采用随机选择两个个体来生成新个体,并没有记忆整个种群的最优解,容易造成全局最优帝王蝶搜索经验的丢失.根据MBO寻优过程的内在机制以及差分进化算法的变异算子能够利用个体间的差异信息,将MBO分别与目前性能最优、应用范围最广的7种差分进化(Differential Evolution,DE)变异策略相结合,实验验证了7种不同算法的性能.基于性能最优的DE/best/2/bin变异模式,提出了一种差分进化帝王蝶优化算法(Monarch Butterfly Optimization Algorithm with Differential Evolution,DEMBO),使得算法能够记忆种群最优解并实现种群内部信息的充分共享,达到既加快收敛速度又提高解的精度的目的.在30个典型折扣{0-1}背包问题(D{0-1}KP)实例上进行了一系列实验,实验结果表明:(1)DEMBO能够在时间复杂度不变的条件下,显著提高算法的求解精度和收敛速度;(2)DEMBO在求解所有D{0-1}KP实例时,均能够获得一个近似比非常接近1的近似解. 展开更多

关键词 折扣{0-1}背包问题 差分进化 帝王蝶优化算法 贪心修复策略 近似比

下载PDF 职称材料

机器带准备时间的三台平行机排序问题的线性时间算法 被引量：12

2

作者 范静 杨启帆 《浙江大学学报（理学版）》 CAS CSCD 北大核心 2005年第3期258-263,共6页

对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数) ,并证明了当ε=15 时,对偶阈值算法DA315 的近似比为65 ,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间... 对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数) ,并证明了当ε=15 时,对偶阈值算法DA315 的近似比为65 ,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法. 展开更多

关键词 排序 近似比 机器 住备时间 线性时间

下载PDF 职称材料

求图的最小顶点覆盖集的一个近似算法 被引量：8

3

作者 闫兴篡 殷建平 +1 位作者 蔡志平 刘湘辉 《哈尔滨工业大学学报》 EI CAS CSCD 北大核心 2008年第7期1131-1135,共5页

已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略... 已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充. 展开更多

关键词 最小顶点覆盖集 近似算法 近似比 运行时间 NP难问题

下载PDF 职称材料

基于贪婪策略的0/1背包问题算法研究 被引量：7

4

作者 游维 《计算机与现代化》 2007年第4期10-12,16,共4页

对求解0/1背包问题的贪婪策略进行了详细的讨论。在分析价值密度贪婪算法缺陷的基础上,提出了重做贪婪选择的改进算法,并从理论和实验两个方面证明了其求解质量的提高。本文还详细分析了k阶优化算法,并证明了其近似比为k/(k+1),最后编... 对求解0/1背包问题的贪婪策略进行了详细的讨论。在分析价值密度贪婪算法缺陷的基础上,提出了重做贪婪选择的改进算法,并从理论和实验两个方面证明了其求解质量的提高。本文还详细分析了k阶优化算法,并证明了其近似比为k/(k+1),最后编程模拟了该算法的实现过程,并对结果进行了分析。 展开更多

关键词 0/1背包问题 贪婪策略 k阶优化算法 近似比

下载PDF 职称材料

基于效用替代率的物资储备量模型与算法 被引量：7

5

作者 徐寅峰 张敏娇 +1 位作者 余海燕 鱼敏 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2011年第2期270-275,共6页

研究在物资储备有容量限制且需求未知的情形下,考虑多种物资之间具有替代性时应如何决定各物资的储备量,使得所有储备物资在满足需求时带来的效用尽可能大的物资储备问题.对物资之间的替代性进行分析并给出了效用替代率的定义,在此基础... 研究在物资储备有容量限制且需求未知的情形下,考虑多种物资之间具有替代性时应如何决定各物资的储备量,使得所有储备物资在满足需求时带来的效用尽可能大的物资储备问题.对物资之间的替代性进行分析并给出了效用替代率的定义,在此基础上建立一般的物资储备量模型,分析了该模型与背包问题模型以及指派问题模型之间的区别和联系.针对该问题的一种特殊情形设计了效用替代率贪婪算法并进行了算法的性能分析.最后通过一个数值算例说明引入替代率可以改善物资储备的效用. 展开更多

关键词 效用替代率 物资储备 贪婪算法 近似比

原文传递

一种求解能量受限的最大圆盘覆盖问题的进化算法

6

作者 李伟东 蓝欢 刘晓非 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2024年第2期36-41,共6页

面对大规模多数据监测任务,有限的能量将成为无线传感器的瓶颈,本文将该问题抽象为能量受限的最大圆盘覆盖问题.即试图寻找一种能量分配方案,使得在总能量受限的情况下,传感器网络覆盖的用户收益之和最大.基于贪婪策略,设计了一个多项... 面对大规模多数据监测任务,有限的能量将成为无线传感器的瓶颈,本文将该问题抽象为能量受限的最大圆盘覆盖问题.即试图寻找一种能量分配方案,使得在总能量受限的情况下,传感器网络覆盖的用户收益之和最大.基于贪婪策略,设计了一个多项式时间(1/2)(1-1/e)-近似算法;进一步通过构造一个合理的代理函数,设计了一个分组进化算法,并证明在期望多项式时间内,该算法具有相同近似比.实验结果表明,分组进化算法输出解的目标函数值与最优值几乎相同. 展开更多

关键词 圆盘覆盖问题 能量受限 贪婪算法 进化算法 近似比

原文传递

d-正则二部图的最大1-相关集问题

7

作者 曹苑真 陈光亭 +1 位作者 陈永 张安 《杭州电子科技大学学报（自然科学版）》 2023年第4期36-39,45,共5页

区块链中的有些区块包含的交易数据不可信,提高有效交易量处理效率的关键在于可信区块的识别。从图论的角度看,区块链是有向无环图(Directed Acyclic Graph,DAG),最大可信区块的识别问题可转化为无向图G=(V,E)的最大k-相关集问题。针对... 区块链中的有些区块包含的交易数据不可信,提高有效交易量处理效率的关键在于可信区块的识别。从图论的角度看,区块链是有向无环图(Directed Acyclic Graph,DAG),最大可信区块的识别问题可转化为无向图G=(V,E)的最大k-相关集问题。针对k=1的情况,调用最大独立集算法,给出了求解d-正则二部图(d≥3)最大1-相关集问题的多项式时间近似算法,从理论上证明了算法的近似比为2d/2d-1,并给出d=3的3-正则二部图上的紧例。 展开更多

关键词 区块链 可信区块 k-相关集 近似算法 近似比

下载PDF 职称材料

无线传感器网络虚拟骨干近似算法综述 被引量：3

8

作者 张昭 《计算机研究与发展》 EI CSCD 北大核心 2016年第1期15-25,共11页

在无线传感器网络中应用虚拟骨干,可以有效地节约能量、减少干扰、延长网络寿命,在几何路由算法和网络拓扑控制等方面具有广泛的应用.虚拟骨干可以模型化为图中的连通控制集.主要从近似算法角度介绍连通控制集及其各种变形在国内外的研... 在无线传感器网络中应用虚拟骨干,可以有效地节约能量、减少干扰、延长网络寿命,在几何路由算法和网络拓扑控制等方面具有广泛的应用.虚拟骨干可以模型化为图中的连通控制集.主要从近似算法角度介绍连通控制集及其各种变形在国内外的研究现状及最新进展,侧重于研究方法和理论结果,为相关研究人员提供参考. 展开更多

关键词 无线传感器网络 虚拟骨干 连通控制集 近似算法 近似比

下载PDF 职称材料

独立多处理机任务静态调度问题的近似算法 被引量：3

9

作者 黄金贵 李荣珩 《软件学报》 EI CSCD 北大核心 2010年第12期3211-3219,共9页

研究独立多处理机任务静态调度问题Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题Pm|fix|Cmax和其中... 研究独立多处理机任务静态调度问题Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题Pm|fix|Cmax和其中所有任务都是单位处理机时间的特殊情形Pm|fix,p=1|Cmax的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题Pm|fix,p=1|Cmax的2m+1近似算法和问题Pm|fix|Cmax的2 m近似算法,优于目前已有文献的最好结果. 展开更多

关键词 多处理机任务调度 近似算法 近似比 NP难问题

下载PDF 职称材料

内部节点受限的最小生成树问题算法研究 被引量：3

10

作者 蒋小娟 张安 +1 位作者 陈永 陈光亭 《计算机工程与应用》 CSCD 北大核心 2017年第10期35-37,共3页

研究内部节点受限的最小生成树问题:给定一个赋权无向完全图G=(V,E),假定w:E→R^+为边集E的权重函数且满足三角不等式,给定点集V的一个子集R(RV),目标是寻找图G的一个满足R中的点皆为内部顶点的权重最小的生成树。由于该问题是NP-困难... 研究内部节点受限的最小生成树问题:给定一个赋权无向完全图G=(V,E),假定w:E→R^+为边集E的权重函数且满足三角不等式,给定点集V的一个子集R(RV),目标是寻找图G的一个满足R中的点皆为内部顶点的权重最小的生成树。由于该问题是NP-困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。 展开更多

关键词 无向赋权图 生成树 近似算法 近似比

下载PDF 职称材料

个体开销受限的交通流优化分配方法 被引量：3

11

作者 马东超 武涛 +2 位作者 王晓亮 徐恪 马礼 《中国公路学报》 EI CAS CSCD 北大核心 2016年第7期134-142,共9页

为了提供一种多原则指导下的交通流建模及求解方法,针对非两类极端条件下(用户最优、系统最优)的交通流分配问题展开研究,着重解决追求系统总体最优而忽视个体出行者承受多余开销导致的服从意愿较差的问题。引入距离和时间2种因素重新... 为了提供一种多原则指导下的交通流建模及求解方法,针对非两类极端条件下(用户最优、系统最优)的交通流分配问题展开研究,着重解决追求系统总体最优而忽视个体出行者承受多余开销导致的服从意愿较差的问题。引入距离和时间2种因素重新定义了车辆综合开销,从增强诱导信息影响效果的角度,将个人因服从诱导信息所新增的开销引入动态分配模型的约束条件中,以一种启发式的免回溯求解算法降低计算复杂度,并分析了近似比。研究结果表明:模型在以系统最优为主要目标的前提下可帮助出行者以较低的绕行开销避开拥堵,提高用户对诱导信息的遵从程度;在5类指标方面的表现显著优于DUO及最短路径模型;近似算法以接近线性的计算复杂度达到了DSO系统最优模型90%以上的效果。 展开更多

关键词 交通工程 交通流分配 交通仿真 交通流诱导信息 路径选择 近似比

原文传递

最大和搜索结果多样性问题及其贪婪算法分析 被引量：2

12

作者 代文强 李晓荣 冯毅 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2016年第3期706-711,共6页

研究互联网搜索结果的最优多样性问题.给定用户搜索关键词较少,以及关键词本身的多义性,同时由于搜索系统一次呈现结果存在数量上的限制,系统常不能准确定位用户的真实搜索需求.为了最大化覆盖用户的搜索需求,搜索系统显示的结果不仅需... 研究互联网搜索结果的最优多样性问题.给定用户搜索关键词较少,以及关键词本身的多义性,同时由于搜索系统一次呈现结果存在数量上的限制,系统常不能准确定位用户的真实搜索需求.为了最大化覆盖用户的搜索需求,搜索系统显示的结果不仅需要最大化同关键词的相关性,而且需要最大化结果之间的差异性.考虑了最大和搜索结果多样性问题,给出了贪婪算法,并针对实际中的差异性度量常常不满足三角不等式的情况下,分析证明了该贪婪算法具有的近似性能比.结果表明贪婪算法具有很好的理论近似性能. 展开更多

关键词 多样性 关键词搜索 贪婪 算法 近似比

原文传递

有限自动机重置问题的算法研究进展 被引量：2

13

作者 朱凯 毋国庆 +1 位作者 梁早清 袁梦霆 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2021年第2期20-27,共8页

论述了最近10多年有限自动机重置问题在算法方面的研究进展。首先形式定义一些基本概念和四个有关重置的问题,给出这些问题的计算复杂性结果;然后回顾了2008年前的算法发展历程和若干结论;接着将2008年后的算法分为判定自动机是否可重... 论述了最近10多年有限自动机重置问题在算法方面的研究进展。首先形式定义一些基本概念和四个有关重置的问题,给出这些问题的计算复杂性结果;然后回顾了2008年前的算法发展历程和若干结论;接着将2008年后的算法分为判定自动机是否可重置的基本算法、短重置字求解算法和最短重置字求解算法三类,分别对各个算法背后的思想、复杂度、生产的重置字的质量和存在的问题等进行分析;最后总结了这些算法的评估标准和优化策略,给出了理论上须要进一步探讨的问题。 展开更多

关键词 有限自动机 重置字 广度优先搜索 双向搜索 近似比 计算复杂性

原文传递

3台平行机上带有2个服务等级的离线负载均衡 被引量：1

14

作者 贾珊珊 嵇雯蕙 陈智斌 《软件导刊》 2022年第2期97-100,共4页

排序问题是一类重要的组合最优化问题,在生产计划、计算机控制等领域有着广泛应用,一直是理论界研究热点。对带服务等级的3台平行机排序问题进行研究,每台机器和每个工件都有等级标号,每个工件只能被某台服务等级不高于该工件等级的机... 排序问题是一类重要的组合最优化问题,在生产计划、计算机控制等领域有着广泛应用,一直是理论界研究热点。对带服务等级的3台平行机排序问题进行研究,每台机器和每个工件都有等级标号,每个工件只能被某台服务等级不高于该工件等级的机器加工,目标是最小化最大机器的完工时间。运用新的算法思想解决离线状态等级约束下的3台机器负载均衡问题。对等级约束为1、2、2的3台平行机给出一个43-近似算法;对于等级约束为1、1、2的3台平行机给出一个2-近似算法。 展开更多

关键词 等级约束 排序问题 近似比 目标函数

下载PDF 职称材料

带模具约束的两台同型机排序问题的改进算法

15

作者 甄谭 张安 +1 位作者 陈光亭 陈永 《杭州电子科技大学学报（自然科学版）》 2022年第2期86-89,共4页

研究带模具约束的两台同型机排序问题,针对极小化工件最大完工时间的目标函数,与已有的3/2近似算法相比,增加对最大工件集的处理,得到改进算法的近似比为4/3,并给出了紧例。

关键词 排序问题 模具约束 近似算法 近似比

下载PDF 职称材料

一类带平行机的两阶段柔性流水调度近似算法 被引量：1

16

作者 张明会 韩鑫 《应用数学学报》 CSCD 北大核心 2018年第3期420-432,共13页

本文研究一类柔性流水调度与平行机调度相结合的两阶段流水调度模型，模型中第1阶段有1台机器，第2阶段有m台同构并行机，每个任务在第2阶段需要size／台机器同时并行执行．目标是所有任务都完成的完工时间最小化．该模型已被证明出是... 本文研究一类柔性流水调度与平行机调度相结合的两阶段流水调度模型，模型中第1阶段有1台机器，第2阶段有m台同构并行机，每个任务在第2阶段需要size／台机器同时并行执行．目标是所有任务都完成的完工时间最小化．该模型已被证明出是强NP难的，并给出了在某种特定情况下近似比为3的近似算法．本文首先详细分析了前人近似算法基本过程，给出该算法近似比分析的局限性；接着给出了一个近似比为3的算法，摒弃了前人给出的近似比为3时的约束条件；最后研究了当第2阶段机器数为2和3时的两种特定情况，采用列表调度思想，给出了近似比为25和2．67的近似算法． 展开更多

关键词 柔性流水调度 平行机调度 近似算法 近似比

原文传递

带冲突约束两台平行专用机排序的一个改进算法

17

作者 张亮 张安 +1 位作者 陈永 陈光亭 《杭州电子科技大学学报（自然科学版）》 2022年第3期90-94,共5页

研究带冲突约束的两台平行专用机排序问题的一种特殊情形,针对极小化工件最大完工时间的目标函数,与已有的5/3-近似算法相比,考虑了一类专属工件的加工,并对时间窗口作出改进,得到新算法的近似比为5+1/2,并给出了紧例。

关键词 平行专用机排序 冲突约束 近似算法 近似比

下载PDF 职称材料

软容量约束带随机需求的设施选址问题的近似算法 被引量：1

18

作者 王星 徐大川 《运筹与管理》 CSSCI CSCD 北大核心 2018年第4期35-38,共4页

文考虑了软容量约束带随机需求的设施选址问题,根据此问题构造出一个无容量约束带随机需求的设施选址问题,通过求解无容量约束情形给出软容量情形的一个可行解,分析出近似比为6。

关键词 软容量约束带随机需求 近似算法 近似比

下载PDF 职称材料

带冲突约束的两台专用机器调度问题 被引量：1

19

作者 龚悦 张安 +2 位作者 陈光亭 李好好 陈永 《杭州电子科技大学学报（自然科学版）》 2021年第5期88-91,共4页

给定2台并行专用机器,每个作业都有专有的机器进行加工,资源的有限性导致属于不同机器的作业之间相互冲突,即相互冲突的作业不能同时加工。对于极小化作业最大完工时间的目标函数,即使其中1台机器上作业的加工顺序已确定,该问题仍然是NP... 给定2台并行专用机器,每个作业都有专有的机器进行加工,资源的有限性导致属于不同机器的作业之间相互冲突,即相互冲突的作业不能同时加工。对于极小化作业最大完工时间的目标函数,即使其中1台机器上作业的加工顺序已确定,该问题仍然是NP-难的。在其中1台机器上作业加工顺序已经确定的情况下,为了使机器完工时间尽可能小,该文引用贪婪算法,设计了求解此问题的多项式时间近似算法,并从理论上证明了算法的近似比为5/3,且给出相关紧例。 展开更多

关键词 专用机器 冲突图 近似算法 近似比

下载PDF 职称材料

两阶段选址优化问题研究 被引量：1

20

作者 代文强 《运筹与管理》 CSCD 2007年第6期47-50,共4页

本文主要考虑如下实际问题:假设选址决策者需要建设p个设施,但是由于资金等等的影响,实际建设时会被要求先建设q个设施,其次再建设p-q个设施(设p>q),同时要求,在建设p-q个设施的时候,已经建设好的q个设施不被删除。本文建立了一个两... 本文主要考虑如下实际问题:假设选址决策者需要建设p个设施,但是由于资金等等的影响,实际建设时会被要求先建设q个设施,其次再建设p-q个设施(设p>q),同时要求,在建设p-q个设施的时候,已经建设好的q个设施不被删除。本文建立了一个两阶段优化问题,问题的输出是两个待修建的设施的集合Fq,Fp,|Fp|=p,|Fq|=q,且Fq是Fp的子集,问题的目标是最小化这两个设施集合的费用同对应的最优费用的比值的最大值。本文给出一个近似比为9的近似算法,并对一些特殊的情况进行了讨论。所得结论对实际的选址决策具有理论意义,同时也完善已有相关研究结果。 展开更多

关键词 运筹学 选址 中心 算法 近似比

下载PDF 职称材料