共查询到20条相似文献，搜索用时 31 毫秒
1.
《绵阳师范学院学报》2020,(2):93-99
根据萤火虫算法自身特点,本文提出一种基于模拟退火的改进萤火虫算法,并用于求解0-1背包问题.该算法在模拟退火过程中利用萤火虫算法搜索新解,采用贪心修复算子对不可行解进行修正.每一次退火操作完成时,对萤火虫种群实行变异操作,增强萤火虫的全局搜索能力.本算法在求解0-1背包问题时,能及时跳出局部最优,在算法初期增强全局搜索能力,在算法后期加快收敛速度.通过仿真实验表明,该算法可较好的求解0-1背包问题. 相似文献
2.
0-1背包问题的遗传算法求解及其改进 总被引：1，自引：0，他引：1
0-1背包问题是一个典型的组合优化问题,且为NP完全问题.目前常用的方法有贪心算法,动态规划,回溯法等.本文探讨了一种基于贪心算法的混合遗传算法求解0-1背包问题的方法,并在实验中获得了更佳近似解. 相似文献
3.
贪心算法是通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态某种意义的最好选择,即贪心选择。对于一个具体问题,我们该如何知道是否可以用贪心算法来解决,以及能否得到问题的一个最优解呢?可以从许多用贪心算法求解的问题当中,看到它们具有两个重要的性质:贪心选择性质和最优子结构性质。从这两个方面来说明货船装箱问题能用贪心算法来解决,并且能得到一个最优解。 相似文献
4.
0／1背包问题属于动态规划问题，部分背包问题属于贪心算法的范畴，通过比较两种算法的联系和区别，来寻求0／1背包问题的贪心算法的条件，用贪心算法来解决部分0／1背包问题的求解。 相似文献
5.
0-1背包问题在信息密码学和数论研究中有着极其重要的应用。首先对背包问题作了简要描述,然后对0-1背包问题的两种经典算法:动态规划算法、贪心算法给出了具体算法设计及实现过程,最后对两种算法在实现的时间、准确性等性能方面进行了分析和对比。 相似文献
6.
为了有效快速求解0-1背包问题,提出了改进的教与学优化算法.在基本教与学优化算法的基础上,根据0-1背包问题离散化的特点提出了二进制编码方案,利用贪心算子修复不可行解并优化可行解,加快了算法的收敛速度;为了更好地平衡全局探索和局部开发的关系,使用正余弦算子和自适应的惯性权重在迭代过程中调整探索和开发的相对比例,避免算法... 相似文献
7.
为了提高求解0-1背包问题的效率,提出了两种贪心局部搜索算法,分别称为固定候选算法和变化候选算法.算法都以有效的方式构造好的初始解,随后执行局部搜索对其进行解质量上的改进.实验结果表明了两种算法的有效性、可行性及与价值密度贪心算法相比的优越性,同时进一步看出两种算法中变化候选算法相对较优,能够取得更好的结果. 相似文献
8.
以0-1背包问题为研究对象,建立教学模型,采用有序组合树法对中小规模的背包问题进行求解。与传统的贪婪算法相比,该算法更容易找到最优解,并通过实例说明该算法对解决中小规模的0-1背包问题是行之有效的。 相似文献
9.
最大最小蚁群算法通过对信息素更新和限制的改进,有效提高收敛速度,但难以避免出现停滞并陷入局部最优的困境。基于贪心边的MMAS改进算法规定一种新的搜索停滞状态,设定不同等级贪心边,并在停滞状态下利用搜索过程中寻找到的贪心边进行优先搜索。该算法使搜索能够尽早地集中在有效边进行,丢弃“无用”搜索,提高发现更优路径的可能性。利用TSP标准实例进行测试,结果表明改进算法的最优解更加接近实际最优解,具有更高的全局寻优能力和更快的收敛速度。 相似文献
10.
在分析多维背包问题和多选择背包问题的基础上,提出一种广义的多维多选择背包问题,给出了该问题的数学模型并改进传统的贪婪算法对其进行了求解.该算法以价值密度为准则,并对每个约束条件先后执行贪婪优化,从而得到问题的近似最优解. 相似文献
11.
给出了基于混沌粒子群优化算法(CPSO)背包问题的一种新的求解方法.首先将背包问题对应到粒子群算法中的位置与速度问题的表示,然后为了抑制早熟停滞现象,将混沌理论引进优化,使得背包问题更接近最优解. 相似文献
12.
针对目前在求解经典0-1背包问题时已有算法的不足,运用改进的萤火虫算法对该问题进行求解。引入贪心策略修正萤火虫算法的不可行解,提出一种变异策略,增加萤火虫算法的种群多样性。通过对3个不同规模的算例进行测试,实验结果表明改进的萤火虫算法有效;通过和目前已有算法的求解结果进行比较,改进萤火虫算法具有较好的高效性和稳定性。 相似文献
13.
戴书文 《淮南职业技术学院学报》2005,5(1):72-74
在组合优化的实际问题求解中，背包问题，TSM问题等NP(Non—deterministic Polynomial)问题在多项式时间内无法得到最优解，要解决此类问题，就必须借助于启发式算法；简单介绍了计算复杂性概念，列举了几种常用的启发式算法，并给出算法的自然语言描述。 相似文献
14.
算法是解决问题方法的精确描述,算法设计的任务是对各类具体问题设计良好的算法及研究设计算法的规律和方法。通过介绍贪心算法与动态规划算法的基本原理以及具体实例,来比较两种算法的联系和区别。最后以背包问题为例子对比两种算法的使用特点和使用范围的不同。 相似文献
15.
多重二次背包问题,旨在将具有单独价值与协作价值的对象分配到一组容量有限的背包中,使总利润最大化,是一种具有广泛应用的NP难组合优化问题。针对该问题提出一种引入自适应模式替换和贪心算法思想的改进遗传算法（IGA）。首先对初始种群进行自适应模式替换,使每代种群中的最好基因个体保存下来形成模式,替换原种群中质量较差的个体,通过设计贪婪算子改进贪心思想对问题进行排序,然后进行扰动交叉操作和双重选择变异操作,最后采用最大化修复策略以保证解的可行性。标准算例仿真结果表明,相比传统算法,IGA具有较强的寻优能力。 相似文献
16.
贪心算法与动态规划的比较 总被引：3，自引：0，他引：3
介绍了计算机算法设计的两种常用算法思想:贪心算法与动态规划算法。通过介绍两种算法思想的基本原理,比较两种算法的联系和区别。通过背包问题对比了两种算法的使用特点和使用范围。 相似文献
17.
为利用和声搜索算法求解0-1背包问题,针对和声搜索的离散化技术和二进制编码的特点,借鉴遗传算子改进新和声的生成方式及微调方式,并基于贪心策略设计和声修正过程,提出了一种离散化的和声搜索算法.数值实验表明,与其它常用的智能算法相比,该算法在求解质量上具有较大优势,对大规模的背包问题效果也很明显. 相似文献
18.
19.
就多维背包问题的求解,提出一个基于遗传算法的启发式算法(MKPGA).该算法中加入了一个利用问题特性知识的启发式修复算予以帮助求解.测试实例使用270个不同特性的多维背包问题,实验结果表明,该算法对多维背包问题的求解十分有效,能获得不同特性问题的高质量解. 相似文献
20.
货郎担问题是组合优化中的著名问题,至今它还没有一个有效算法.主要针对多年来人们对它的研究而得到的一些较好的最优解或优秀的近似解,结合实例,说明这些算法的运行过程.并提出两个新的算法-贪心算法和修改最小生成树法. 相似文献