基于0-1背包问题的讨论

简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0-1背包问题,给出了具体的算法描述和求解过程.对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间,发现模拟退火算法是相对最优的算法.     

基于0/1背包问题的讨论

简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0/1背包问题,给出了具体的算法描述和求解过程。对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间。     

物化视图选择的一种两阶段优化算法

物化视图是数据仓库中提高查询效率的有效方法,物化视图选择问题是数据仓库设计时期最重要的决定之一。通过研究和实验,提出了一种结合迭代改进算法和模拟退火算法的两阶段优化算法,用于解决物化视图的选择。理论分析和实验结果表明,该算法有效地解决了传统模拟退火算法收敛过慢的缺点,并且其解的质量逼近经典贪婪算法。     

考虑学习效应的单人作业车间调度算法

单人负责多台机器的单一工序作业车间场景中,工人由于重复操作机器而产生学习效应.针对考虑依赖工件位置学习效应的单人单工序作业车间最小化最大完工时间的调度问题,建立一种混合整数规划模型.为解决该问题,设计一个考虑学习效应的贪婪算子,利用该算子构造两种贪婪算法,并提出一种基于贪婪的模拟退火算法.为衡量混合整数规划模型、贪婪算法和基于贪婪的模拟退火算法的性能,设计两种规模问题的数据实验.通过实验得出:现代混合整数规划模型求解器可以解决机器数量和工件总数量乘积小于75的小规模问题;基于贪婪的模拟退火算法求解此问题具有有效性,适用于各种规模的问题;间隔插入贪婪算法解决此问题速度较快,效果良好,可以应用于需要快速求解的场景.     

流不平衡条件下飞机恢复的优化模型与算法研究

为更有效地解决航空公司飞机恢复问题,在经典的资源指派优化模型中放宽飞机流平衡约束,加入合并航班的恢复策略;在贪婪随机自适应算法(GRASP)和模拟退火算法的基础上,提出一种新的启发式算法贪婪随机模拟退火算法,降低了陷入局部最优解的概率,同时通过限定路径对的种类和候选解的数量,提高了算法的时间效率.实例计算结果表明,本文提出的模型和算法能有效处理流不平衡条件下大规模飞机恢复问题,在有效的时间内求得最优解或近似最优解.     

多种群退火贪婪混合遗传算法

遗传算法是应用比较广泛的一种随机优化算法,遗传算法的收敛速度与问题解的质量是影响算法寻优性能的一对主要矛盾。为了提高遗传算法的性能,论文通过将局部搜索能力较强的贪婪算法引入遗传算法,并且同模拟退火和多种群并行遗传进化思想有机结合起来的方法,提出了一个改进型的算法——多种群退火贪婪混合遗传算法(MultigroupAnnealingGreedyHybridGeneticAlgorithm,简称MAGHGA)。仿真结果表明,该算法避免了在遗传算法中存在的早熟收敛问题,增强了算法的全局收敛性,同时也有效地提高了算法的收敛速度。     

高校自动排课系统算法比较分析

课程表的编排是高校教务管理中最为重要和复杂的一项工作。通过对几种自动排课算法的合理比较。统筹分析出各自的优劣,得出贪婪算法的综合适用性是最优的结论。在此基础之上．进一步分析贪婪算法是如何逐步解决排课的现实问题,并给出基于贪婪算法的自动排课系统算法的具体实现过程。     

基于遗传算法的混合优化策略研究

最优化问题是工程设计、科学研究、经济管理等众多领域经常遇到的一类问题。随着待解决问题范围的不断扩大以及优化算法研究的不断深入,混合优化策略已成为解决大规模、高复杂度优化问题的一种重要而有效的方法。介绍了遗传算法、贪婪法、模拟退火算法、禁忌搜索的基本原理,阐述了各种算法的优缺点;针对各单一算法存在的缺陷和不足,对三种以遗传算法为主体框架的混合优化算法进行了分析;最后,指出了混合优化算法存在的问题及今后的发展方向。     

基于遗传算法的混合优化策略研究

最优化问题是工程设计、科学研究、经济管理等众多领域经常遇到的一类问题。随着待解决问题范围的不断扩大以及优化算法研究的不断深入，混合优化策略已成为解决大规模、高复杂度优化问题的一种重要而有效的方法。介绍了遗传算法、贪婪法、模拟退火算法、禁忌搜索的基本原理，阐述了各种算法的优缺点；针对各单一算法存在的缺陷和不足．对三种以遗传算法为主体框架的混合优化算法进行了分析；最后，指出了混合优化算法存在的问题及今后的发展方向。     

一种改进的贪婪式覆盖算法

文中对覆盖算法进行了介绍和分析,提出了一种基于贪婪算法思想的改进的覆盖算法,称之为贪婪覆盖算法。通过对覆盖初始中心选择方式的改进,减少覆盖数量。通过实验,对比目前已有的几种实现方法,覆盖数量有了较大的下降,明显提高了分类识别的速度。     

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

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

K-median问题贪心近似算法的分析与实验

讨论K-median问题的贪心近似算法及其在实际计算中的表现。提出一个解K-median问题的贪心算法,证明该算法的近似度为O(ln(n/k)),通过实验证明该贪心算法在实际应用当中可以取得较好的效果,大约有90%的客户能被距离其最近、次近和第三近的设备服务。     

A hybrid algorithmic model for the minimum weight dominating set problem

Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches.     

求解0-1背包问题的改进混合遗传算法

针对一种混合遗传算法所采用的贪心变换法的不足,给出了一种改进的贪心修正法;并基于稳态复制的策略,对遗传算法的选择操作进行改进,给出了随机选择操作。在此基础上,提出了一种改进的混合遗传算法,并将新算法用于解决大规模的0-1背包问题,通过实例将新算法与 HGA 算法进行实验对比分析,并研究了变异概率对新算法性能的影响。实验结果表明新算法收敛速度快,寻优能力强。     

改进SA-SP算法的路面不平度信号压缩感知采集研究

为大幅度减少采集路面不平度信号的存储空间,提高采集速度,基于压缩感知理论针对标准路面的不平度信号进行压缩采样和重构。首先验证了B级路面不定度信号在频域下的近似稀疏性,并进行了信号的压缩采样。针对现阶段凸优化方法和常用的三种贪婪算法的不足,提出一种改进的模拟退火算法与子空间追踪算法相结合的稀疏度自适应匹配追踪算法,利用改进的模拟退火算法快速搜索匹配最优的稀疏度,并采用子空间追踪算法快速重构信号。仿真实验对比五种重构方法,结果表明,凸优化方法精度较高,耗时过长;OMP算法和SP算法耗时极短,但需要预先进行实验来估测信号的稀疏度,实用性低;SAMP算法能实现稀疏度的自适应匹配,但匹配的误差较大,且耗时较长;提的新方法具有良好的精度和较快的执行速度,R-squares和耗时的均值分别为0.9837和2.77 s,稀疏度估测效果较好,且采样点数的增加不影响算法重构信号的速度。     

基于RGI的浮空器任务规划问题研究

侦察任务规划是浮空器军事应用中的重要问题,对于最大化满足侦察任务需求、提高浮空器资源利用率具有重要作用。针对浮空器侦察系统的任务规划问题,考虑任务需求约束、载荷约束等条件下,构建了浮空器连续侦察监视的混合整数规划模型,并采用贪婪随机插入(RGI)算法对模型进行了求解。该算法结合了贪婪算法和模拟退火算法的设计思想,既保留了一定贪婪特征又提高了跳出局部最优解的能力。最后通过一个多浮空器多目标的仿真实例验证了算法的有效性。