基于贪心优化策略的网格排布算法

针对由存储带宽和数据访问速度导致的复杂数据集绘制性能低下等问题,提出了一种基于贪心优化策略的三角形排布算法,通过对绘制数据集进行重排以改善数据的空间局部性和时间局部性。该算法首先将顶点分为三类,根据改进的代价函数选择代价度量最小的顶点作为活动顶点;然后绘制(即输出)其所有未绘制的邻接三角形,并将相邻顶点压入缓存,算法迭代执行直到所有顶点的邻接三角形都绘制完成,得到重新排列后的三角形序列。实验结果表明,该算法不仅具备较高的顶点缓存命中率,还提高了渲染速度,减少了排序的时间,有效地解决了图形处理器的处理速度不断提升而数据访问速度严重滞后的问题。

求解0-1背包问题的贪心优化粒子群算法

为进一步加快粒子群算法求解0-1背包问题的收敛速度,通过对现有背包问题中非正常编码个体处理方法存在的不足进行分析,本文在传统粒子群算法中加入了贪心修复算子和贪心优化算子,提出了一种求解0-1背包问题的改进粒子群算法。仿真实验结果表明:在求解0-1背包问题时,与遗传算法、离散粒子群算法、蚁群算法等相比,该算法不仅显著提高了收敛速度,而且具有较强的寻优能力和鲁棒性。

基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题

针对确定性算法难于求解的各项的重量系数和价值系数在大范围内取值的折扣{0-1}背包问题(D{0-1}KP),提出了基于差分演化策略的混沌乌鸦算法(DECCSA)。首先,采用混沌映射生成初始乌鸦种群;然后,采用混合编码方式和贪心修复与优化策略(GROS)解决了D{0-1}KP的编码问题;最后,引入差分演化策略提高算法的收敛速度。对4类大规模D{0-1}KP实例的计算结果表明:DECCSA比遗传算法、细菌觅食算法和变异蝙蝠算法求得的最好值和平均值更优,能得到最优解或更好的近似解,非常适于求解D{0-1}KP。

求解0-1背包问题的混合粒子群改进算法研究

针对0-1背包问题求解,将离散二进制粒子群优化(Binary Particle Swarm Optimization, BPSO)算法、贪心优化策略和模拟退火算法有机结合,提出了一种改进算法:带贪心优化的混合粒子群和模拟退火(Hybrid optimization algorithm based on the BPSO, the Simulated Annealing (SA) Algorithm and the Combined Greedy Optimization Operator (CGOO), BPSOSA-CGOO)算法.基于新算法,完成了9组不同维度数据的仿真实验.实验结果表明, BPSOSA-CGOO算法能够以较小的种群规模及迭代次数实现0-1背包问题的有效求解,并在问题维度为20维的测试数据中找到优于已知最优解的解;独立重复实验验证了,无论对于低维度还是高维度背包问题, BPSOSA-CGOO算法均能以较高概率命中最优解,提高了高维度背包问题求解的稳定性和可靠性.