共查询到19条相似文献,搜索用时 109 毫秒
1.
针对一维下料优化问题,提出了基于蜂群遗传算法的优化求解方案.具体做法是,以实数表示的各零件长度的一个排列作为一个染色体,其中每个零件的长度作为基因;根据自然界蜂群生物学原理设置了两个种群,一个种群主要用于全局搜索,另一个种群主要用于局部搜索;采用最优个体交叉策略;遗传算子包括联赛选择算子,顺序交叉算子,2-交换变异算子和抑制算子.仿真实验结果表明,该算法逼近理论最优值,而且收敛速度快,较好地解决了一维下料问题. 相似文献
2.
遗传算法在0-1一维背包问题上的应用研究 总被引:1,自引:0,他引:1
遗传算法是改进式启发算法,模拟自然界生物进化过程的计算模型.本文将多种改进的遗传算法应用于背包问题,并通过算例来证明该算法解决背包问题的可行性与有效性,以及评价各算法得优缺点. 相似文献
3.
基于遗传算法的多目标0-1背包问题优化模型 总被引:1,自引:1,他引:1
多目标0-1背包问题是一个NP-complete的多目标优化问题,基于群体搜索机制的遗传算法非常适合多目标优化问题的求解。在著名的多目标优化遗传算法NSGA-II中,引入邻域搜索机制,并将其应用于多目标0-1背包问题的求解。数值实验表明,引入邻域搜索机制的NSGA-II算法在求解多目标0-1背包问题时表现出更好的性能。 相似文献
4.
遗传算法是一种基于自然选择和遗传机制的搜索算法。本文将其用于解决一个著名的NP完备问题——0- 1背包问题,并对经典遗传算法进行了改进。通过对贪婪算法进行了改进以产生初始种群,并在进行交叉和变异操作过程中引入了对无效个体的校正操作,从而较好地保持了种群的多样性和优良度。数值实验表明该算法具有较好的全局最优性。 相似文献
5.
折扣{0-1}背包问题(Discounted {0-1} Knapsack Problem,D{0-1}KP)是比0-1背包还要难以求解的NP-hard问题。提出了一种求解D{0-1}KP的新遗传算法GADKP。GADKP针对D{0-1}KP问题本身结构特征,借鉴启发式搜索思想设计了3种有效的交叉算子和1种变异算子。4种算子的操作都能够保证进化过程中解的可行性;3种交叉算子从3个不同的角度提高算法的搜索能力;变异算子采用逐层贪心机制提高个体的局部开发能力。通过4组共40个D{0-1}KP实例测试,和已有的求解D{0-1}KP的遗传算法相比,GADKP求解精度更高,是一种新颖有效的求解D{0-1}KP的方法。 相似文献
6.
求解0—1背包问题的共同进化遗传算法 总被引:3,自引:0,他引:3
0-1背包问题是一类组合优化问题,迄今已有40多年的研究历史,可广泛应用于碎片收集、作业调度、资金预算和货物装箱等领域。0-1背包问题是一类NP问题,所以传统方法如持续松弛法、分枝-界限法、动态规划法和一些近似算法等等,一般仅能获得问题的近似最优解。近年来,不少学者将稳健的遗传算法应用于0-1背包问题的求解,在问题求解质量方面收到了较好的效果。但是,由于传统的单种群遗传算法中一个染色体编码结构代表了问题的一个完整可行解,因此可能导致对解的较好部分的利用可能被其它较差的部分所掩盖,且问题求解效率随着问题规模的增大而下降。针对上述不足,本文基于合作式共同进化计算模型,将共同进化计算用于求解,提出一种求解0-1背包问题的共同进化遗传算法,以进一步提高问题的求解质量和算法效率。 相似文献
7.
8.
9.
求解0-1背包问题的混沌遗传算法 总被引:1,自引:0,他引:1
提出一种改进的混沌遗传算法来求解0-1背包问题。通过利用幂函数载波技术增强混沌搜索的遍历性,把混沌搜索得到的最优解直接作为新群体嵌入遗传算法来改善遗传算法的早熟问题,从而使算法有能力避免陷入局部极值而快速收敛于全局最优解。仿真实验结果表明了该算法求解0-1背包问题的有效性和适用性。 相似文献
10.
11.
提出对基本遗传算法(Genetic Algorithm,GA)的改进策略,并将其应用于多约束0-1背包问题(Multi-constrained 0-1Knapsack Problems,MKP)的求解。改进策略主要有:将线性规划松弛法求得的MKP的解作为初始解,另外为了避免种群多样化的丧失,将复杂的修复操作和局部优化操作应用于每一个最近产生的解。最后,对大规模测试数据的标准集进行实验,并将该算法与先前的方法进行比较,结果表明新的遗传算法在大多数时间能够更快速地收敛到较优解。 相似文献
12.
13.
根据萤火虫算法的自身特点,将自适应权重、改进贪心算法、变异算子与基本萤火虫算法相结合,提出一种带权重的贪心萤火虫算法。通过加入自适应权重与变异算子,可以提高算法全局搜索能力,加入贪心算法在一定程度上可提高算法收敛速度,整体看,改进萤火虫算法提高了算法性能。通过仿真实验将改进后的算法与一些基本算法进行比较,实验结果表明,该算法在求解0-1背包问题时,无论在运算速度还是求解精度上都有明显改进。 相似文献
14.
15.
求解多维0—1背包问题的混合遗传算法 总被引:8,自引:3,他引:8
文章研究一类典型的组合优化问题——多维0-1背包问题,提出了在简单遗传算法(SGA)中加入局部搜索机制的混合遗传算法(HGA)来求解该类问题,并在大量数值实验的基础上,将HGA与传统的求解方法及SGA进行了比较,实验的结果表明,该算法具有一定的优越性。 相似文献
16.
针对一种混合遗传算法所采用的贪心变换法的不足,给出了一种改进的贪心修正法;并基于稳态复制的策略,对遗传算法的选择操作进行改进,给出了随机选择操作。在此基础上,提出了一种改进的混合遗传算法,并将新算法用于解决大规模的0-1背包问题,通过实例将新算法与 HGA 算法进行实验对比分析,并研究了变异概率对新算法性能的影响。实验结果表明新算法收敛速度快,寻优能力强。 相似文献
17.
18.
19.
背包问题是经典的NP-hard组合优化问题之一,在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。文中用动态规划方法解决0-1背包问题,通过在Matlab6.5环境下对其算法进行测试和与其他方法对比分析,表明应用该方法可节省大量的计算时间,因而具有更高运行效率。 相似文献