考虑主观需求的0-1背包问题及其求解算法

背包问题的约束条件通常由客观因素构成,如背包的额定容量,但在实际生活中,确定物品选择方案时,需要结合决策者的主观需求进行调整.基于此,建立考虑决策者主观需求的0-1背包问题模型,并设计一种混合贪心遗传算法(hybrid greedy genetic algorithm,HGGA)对该模型进行求解.针对此模型,首先考虑主观需求,再考虑客观约束,设计一种贪心算子,对初始种群进行优化与修正;然后,设计一种局部搜索算子,改进扰动位点的选择方式,实现对局部最优解的扰动,达到跳出局部最优得到更优质解的目的;最后,在随机生成的9个算例上,分别与同类型的遗传算法进行对比实验.实验结果表明:混合贪心遗传算法在求解精度与算法鲁棒性上具有明显的优势.     

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

对于0-1背包问题设计一种价值密度,并在此基础上提出求解0-1背包问题的混合遗传算法.经大量数值实验比较该方法与传统方法及简单遗传算法,结果表明算法能有效求解0-1背包问题.     

基于遗传算法求解0—1背包问题的算法探讨

0-1背包问题是一类典型的组合优化问题,并且是NP完全问题,具有重要的研究意义.介绍了贪婪算法和基本遗传算法求解背包问题的设计思想,提出了基于贪婪算法的混合遗传算法求解0-1背包问题.实验结果表明改进的遗传算法有更好的近似解.     

基于贪婪策略整体分布优化算法的0-1背包问题求解

提出了一种思想简单且可用于0-1背包问题求解的基于贪婪策略整体分布优化算法.该算法首先随机产生一个初始种群,经贪婪策略将种群变成价值相对较高的可行解,保留本次最优解;然后以最优解为中心,用柯西分布产生新的种群,经贪婪策略将新种群变成相对价值较高的可行解,再保留本次最优解,重复以上过程,达到最大迭代次数,求出问题的全局最优解;最后,对不同规模的问题进行了实验.结果表明:该算法在求解0-1背包问题上是有效的,比遗传算法、贪婪算法具有更强的寻优能力.     

多维O-1背包问题的混合遗传算法

将贪婪法和遗传算法相结合，设计了一种价值密度，提出了一种求解多维0-1背包问题的混合遗传算法。经实例证明，该方法能较好地解决多维0-1背包问题并较简单遗传算法有较好的改善。     

有序组合树法求解0-1背包问题初探

以0-1背包问题为研究对象,建立数学模型,采用有序组合树法对中小规模的背包问题进行求解.与传统的贪婪算法相比,该算法更容易找到最优解.并通过实例说明该算法对解决中小规模的0-1背包问题是行之有效的.     

多维0/1背包与遗传算法的网格调度研究

首先分析了网格调度的代价和成本,设计出一个将多目标、多约束的网格任务转换成单目标、单任务的0/1背包的网格调度模型.提出使用多维0/1背包与改进的二重结构编码的遗传算法的方法来求解网格最优调度,并通过编程实现其算法,经实验验证该算法优于基本的遗传算法.     

求解0/1背包问题的自适应遗传退火算法

针对标准遗传算法易早熟收敛以及收敛速度慢的问题,提出一种自适应遗传退火算法用于解决高维约束优化问题.该算法采用轮盘赌和最优保存策略相结合的选择机制,并结合自适应交叉、变异概率,继而引入模拟退火算法,加快迭代后期算法的收敛速度.最后,比较了标准遗传算法和自适应遗传算法的实验结果,证明了自适应遗传退火算法在0/1背包应用中的高效性和精确性.     

一种求解多维背包问题的小世界算法

针对遗传算法求解复杂组合优化问题时出现早熟收敛和种群多样性丧失等问题,提出了一种解决多维背包问题的二进制编码小世界算法(BSWA).BSWA算法依据社会学中的小世界现象搜索机理,采用类似遗传变异操作的局部搜索,而非遗传算法中的交叉操作.针对多维背包问题的多约束性,BSWA算法还按照价值资源比大小对不可行解进行贪婪修正,以保证求解的正确性.与遗传算法相比,BSWA可以在一定程度上克服早熟收敛,在保持种群多样性和求解精度方面均体现出较大的优势,具有解决复杂组合优化问题的潜力.对55个标准的多约束0-1背包问题进行了50次随机实验,结果表明,BSWA算法对于其中72.73%的问题可以次次获得最优解,对于其他不能次次求解到最优解的问题,也可以获得非常接近全局最优解的满意解.     

差异演化算法求解多维0-1背包问题

多维0-1背包问题是典型的NP难题,设计了一种求解它的差异演化算法,阐述了算法求解多维0-1背包问题的具体操作过程。用提出的算法对55个测试算例进行了仿真实验,得到了全部算例的最优解。测试结果表明了文中算法是求解多维0-1背包问题的一种有效方法。     

0-1背包问题的非线性降维近似算法

求解0-1背包问题的精确算法不能在较短时间内求解大规模0-1背包问题,使其实用性受到限制.针对该问题,给出求解0-1背包问题的非线性降维算法,并进行了数值实验,验证了算法的有效性.该算法属于近似算法,相对其他一些近似算法,计算结果更为精确.     

改进的克隆选择算法求解0——1背包问题

提出了一种改进的克隆选择算法(Improved CSA),该算法采用贪婪策略与宽限边界值相结合的方法,利用未成熟优良子群体提供的信息修改个体基因位来改善种群质量;同时增加一个历史至当前代最佳个体记忆单元防止种群退化.通过对2个0-1背包问题的仿真实验表明:该算法比一般CSA算法和遗传算法能更快的找到最优解;其搜索效率更高,性能更加稳定.     

基于贪心算法的改进遗传算法解决背包问题

本文分析了简单遗传算法解决背包问题时候的一些缺陷,并通过适应度函数的计算以及选择方式的改进,给出了一种基于贪心算法的混合遗传算法以解决这些缺陷。实验表明,改进的遗传算法具有一定的优越性。     

基于改进的模拟退火算法求解0／1背包问题

提出了一种改进的具有变异和倒位算子的模拟退火算法,并将其用于求解0／1背包问题,其性能较标准模拟退火算法和贪心算法都有很大的改善．通过大量的数值实验,证明了文中改进的模拟退火算法求解背包问题的有效性和实用性．     

0_1背包问题及贪心算法应用

本文结合生活中顾客中奖后奖品的选择问题,给出背包问题的数学模型,介绍基于0_1背包问题的贪心算法,使用这种算法解决奖品选择问题,最后再用C＋＋编程实现.     

求解背包问题的一种改进粒子群优化算法

针对0—1背包问题,提出了一种改进的粒子群优化算法。在物品规模增大时,该算法能够有效寻找全局最优解,提高背包的空间利用率,降低背包的空置率。通过仿真实验表明,改进的粒子群优化算法在背包问题求解中具有更好的收敛性和稳定性。     

一种求解0-1背包问题的整数混沌粒子群优化算法

针对0-1背包问题(0-1KP)的特点,以经典的速度-位移模型为基础整数编码各粒子,以混沌序列指导全局搜索,以排列的改变描述粒子的飞行.更新粒子的位置,进而提出用于求解0-1KP的整数混沌粒子群优化(ICPSO)算法.该算法由于背包容量的限制,融入到编码和粒子飞行中,因而不会在进化中产生无效的粒子,从而提高了算法的求解效率.实验结果表明:ICPSO算法简明、有效,较典型遗传算法,及粒子群算法具有更好的收敛性能和求解速度.     

量子免疫算法及在0-1背包问题中的应用

将免疫算法的免疫算子思想引入到量子遗传算法中,提出了改进的算法:量子免疫算法。算法在保持量子遗传算法优点的同时,提高了算法的全局收敛性。并将此算法应用在0-1背包问题中,仿真结果表明,此改进算法具有良好的性能。     

一种改进的模拟退火算法求解0-1背包问题

从增强算法收敛性和减少参数依赖性的角度出发,提出应用改进的模拟退火算法求解0-1背包问题.对模拟退火算法有所改进,并有效地克服它的弱点,使其在优化性能,优化效率和可靠性方面有明显的优越性.阐明了用该算法求解0-1背包问题的具体实现过程,并通过实际数值计算和结果比较表明,该算法在求解0-1背包问题优于传统的模拟退火算法,并且得到更有效的近似解.     

基于遗传算法求解NPC问题的研究

首先建立了0-1KP问题和3-SAT问题的数学模型;然后分别基于遗传算法（GA）与贪心策略相结合给出了一种求解0-1KP的有效算法,基于GA与局部搜索相结合给出了一种求解3-SAT问题的可行算法;最后通过对0-1KP实例和3-SAT实例的仿真计算验证了算法的可行性与有效性。