最小赋权支配集的迭代禁忌搜索算法

最小赋权支配集是一个NP困难的组合优化问题,有着广泛的应用背景。提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法。该算法采用随机贪心构造算法构造初始解,并利用快速的局部禁忌搜索算法寻找局部最优解,通过随机扰动和修复策略来搜索新的区域,以期跳出当前的局部最优解。用顶点数为800到1 000的大规模标准测试例子测试提出的算法。数值实验结果和与现存的启发式算法比较结果表明了算法是有效的。     

基于种子候选的贪心策略影响力最大化算法

爬山贪心算法的时间复杂度较高,不易扩展至大规模社会网络.为了解决此问题,文中从理论上分析节点集影响力评估可转化为局部概率解计算,能够提高算法运行效率.将局部概率解函数拓展到贪心算法中,提出基于种子候选的贪心影响力最大化算法和基于种子候选的偷懒贪心影响力最大化算法.在4个真实数据集上实验表明,文中算法与具有成本效益的惰性前向选择算法(CELF)性能一致,但在运行时间上快于CELF.     

无线传感器网络中干扰最小化问题的后悔贪心算法

无线传感器网络是当前信息领域的一个研究热点,由于无线传感器携带的能量有限,限制了无线传感器的使用寿命,通过减少由于邻近节点同时传输信号产生的干扰可以降低节点的能耗。拓扑控制技术可在保持网络连通的情况下,调整节点传输半径,以降低干扰。以接收者为中心的干扰模型中,求解无线传感器网络中基于拓扑控制技术的干扰最小化问题是NP难问题。现有的贪心算法求解思路是依据某个贪心准则依次确定每个节点的传输半径,求解速度快,但精度有待提高。探讨了增强目前最好贪心算法精度的策略,允许部分后悔操作,即每个贪心迭代步中当前网络的最大干扰增加时,通过两个后悔策略重新调整某些节点的传输半径,力图降低当前网络的最大干扰。模拟实验结果表明,针对随机产生的算例,所提出的后悔贪心算法在略有增加的时间内有效提高了现有贪心算法的精度。     

贪心算法求解k-median问题

文章讨论了用贪心算法解k-m edian问题以及其试验结果。首先提出了一个解k-m edian问题的简单贪心算法,然后对求解质量和求解的近似性能比进行了探讨。主要讨论了公制空间和非公制空间初始解的产生,用贪心算法解k-m edian问题以及全局最优解的计算。试验结果表明:贪心算法解公制空间的k-m edian问题效果要好于解非公制空间的k-m edian问题;用贪心算法解公制空间和非公制空间k-m edian问题都能得到较好的结果。     

最小MPR集选取问题的改进蚁群优化算法

多点中继(MPR)是移动自组网中用来降低网络开销所采用的一种机制,但由于最小MPR集的选取属于NP完全问题,传统的贪心算法往往难以取得较好的结果.本文将蚁群优化用于最小MPR集选取问题的求解,给出了一种基于候选解的改进蚁群算法CSACO.通过使用候选解集进行信息素的更新,提高了算法的收敛速度,同时避免了算法陷入早熟.模拟实验表明,CSACO可以有效降低MPR集的大小,同时在较短的时间内收敛到最优解,提高网络性能.     

离散Jaya算法的复杂网络社区发现

社区结构是复杂网络的重要特性之一, 基于模块度的复杂网络社区发现问题是一个NP难度的组合优化问题, 常用启发式算法求解. 最近出现的Jaya算法是求解连续优化问题的一种简单有效的元启发式方法. 本文在遵循Jaya算法按靠近最好解、远离最差解的方式更新种群个体的基础上, 针对复杂网络社区发现问题给出了Jaya算法离散化的策略, 提出一种复杂网络社区发现的离散Jaya算法. 实验表明, 在几个典型真实网络实例和一类人造网络实例上, 与几个经典算法和元启发式算法相比, 本文算法具有求解精度高、能自动确定社区数目等优点.     

马步遍历探索

马步遍历探索是一个有难度也有趣味的组合数学问题。分别应用回溯与贪心算法探索马步遍历n＊m棋盘。结果显示,回溯算法能够求出问题的所有解,但效率较低,而贪心算法的求解效率非常高,但只能求得问题的一个解,且对于有解棋盘往往得不到解。     

传感器网络中高效的最小连通支配集求解算法

在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。     

设备定位问题局部搜索算法的实验

讨论设备问题的局部搜索近似算法及其在实际计算中表现出的新性质。主要讨论局部搜索算法中初始解的产生方法,设备价值与服务价值大小对算法求解性能的影响。实验表明：约有99%以上的实例可直接利用局部搜索算法求得最优解;贪心算法产生初始解的局部搜索算法求解时间明显短于随机算法产生初始解的方法,但两者求解质量相当;设备价值和服务价值数值范围越大,局部搜索算法越容易求得最优解。     

测试集问题的集合覆盖贪心算法的深入近似

测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).     

Retrieving the maximal time-bounded positive influence set from social networks

The appearance of social networks provides great opportunities for people to communicate, share and disseminate information. Meanwhile, it is quite challenge for utilizing a social networks efficiently in order to increase the commercial profit or alleviate social problems. One feasible solution is to select a subset of individuals that can positively influence the maximum other ones in the given social network, and some algorithms have been proposed to solve the optimal individual subset selection problem. However, most of the existing works ignored the constraint on time. They assume that the time is either infinite or only suitable to solve the snapshot selection problems. Obviously, both of them are impractical in the real system. Due to such reason, we study the problem of selecting the optimal individual subset to diffuse the positive influence when time is bounded. We proved that such a problem is NP-hard, and a heuristic algorithm based on greedy strategy is proposed. The experimental results on both simulation and real-world social networks based on the trace data in Shanghai show that our proposed algorithm outperforms the existing algorithms significantly, especially when the network structure is sparse.     

移动传感器网络中路径扫描覆盖问题研究

扫描覆盖作为无线传感器网络中的重要应用之一,通过规划移动传感器对区域内兴趣点（POI）进行定期覆盖,因此相较于传统覆盖方法能以更低廉的成本监测POI。研究最少传感器数量-最小罚时路径扫描覆盖问题,即通过调度移动传感器扫描给定路径上的POI集合,使传感器使用数量及产生的POI总罚时成本之和最小。将该问题转换为整数规划,并基于该问题的特殊结构设计贪心算法和遗传算法,以求解大规模实例。在遗传算法基础上引入模拟退火操作,以设计一种遗传模拟退火算法,从而提高求解质量和算法局部寻优能力。实验结果表明,所提贪心算法、遗传算法及遗传模拟退火算法均有较好的收敛性,贪心算法求解质量相对较差,但求解速度快;遗传算法解的质量更好,但存在不稳定的问题,局部寻优能力较弱;遗传模拟退火算法的局部寻优能力和求解稳定性明显增强,解的质量优于其他两种算法。     

折扣{0-1}背包问题粒子群算法的贪婪修复策略探究

群智能启发式算法求解折扣{0-1}背包问题（D{0-1}KP）时,为提升求解效率和求解质量,需采用某种修复与优化策略将非正常编码个体转换为符合解约束条件的编码个体。在引入项集价值密度概念基础上,以粒子群算法（PSO）为例,提出一组基于项集的贪婪修复与优化方法（group greedy repair and optimization algorithm,GGROA）,并进一步构造PSO-GGRDKP算法（PSO based GGROA for solving D{0-1}KP）以探究GGROA方法的可行性和性能。PSO-NGROADKP（PSO based NGROA for solving D{0-1}KP）和PSO-GRDKP（PSO based GROA for solving D{0-1}KP）是基于项贪心修复与优化方法的粒子群算法。在D{0-1}KP标准数据集的实验结果表明：与PSO-NGROADKP和PSO-GRDKP相比,PSO-GGRDKP算法的解误差率略高,但算法时间性能分别提升了13.8%、12.9%。     

基于改进式贪婪算法的5G网络切片动态资源调度策略

为了解决移动通信网络中资源利用率和用户体验质量的瓶颈问题,5G 引入网络切片来应对用户的巨大资源需求。提出了一种基于改进式贪婪算法的网络切片动态资源调度策略,在切片调度和用户调度阶段,设计了一种两层模型,即切片?用户模型,并且结合改进式贪婪算法,使服务权重值最大的切片和优先级最高的用户组合,完成相应的服务。该方法是将全局资源最优问题简化为规模更小的子问题,通过每一次切片和用户的最佳组合,从而使整个系统的资源和用户的体验质量达到最优。Matlab的仿真结果表明,基于改进式贪婪算法的网络切片动态资源调度策略在系统剩余资源利用率、系统达到平均的QoE水平、系统吞吐量等方面都显优于现行的资源调度策略,能够更好地满足用户的需求。     

带权重的贪心萤火虫算法求解0-1背包问题

根据萤火虫算法的自身特点，将自适应权重、改进贪心算法、变异算子与基本萤火虫算法相结合，提出一种带权重的贪心萤火虫算法。通过加入自适应权重与变异算子，可以提高算法全局搜索能力，加入贪心算法在一定程度上可提高算法收敛速度，整体看，改进萤火虫算法提高了算法性能。通过仿真实验将改进后的算法与一些基本算法进行比较，实验结果表明，该算法在求解0-1背包问题时，无论在运算速度还是求解精度上都有明显改进。     

Design and Performance Evaluation of Sequence Partition Algorithms

Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of n distinct numbers into minimum number of monotone （increasing or decreasing） subsequences. This problem is NP-hard and the number of monotone subsequences can reach [√2n＋1/1-1/2]in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than [√2n＋1/1-1/2]monotone subsequences in O（n^1.5） time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity O（n^3）, a known greedy algorithm of time complexity O（n^1.5 log n）, and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.     

一种属性约简的探测性贪婪算法

贪婪算法一旦做出贪婪选择就不能反悔,因此设计简单、执行速度快,但其搜索空间过于狭小,从而降低了贪婪解的精度.针对该问题,提出一种属性约简的探索性贪婪算法,采用前景探测策略提高贪婪解的精度.实验结果表明,该算法在时间略有增加的情况下能提高解的精度.