多选择背包问题的快速求解算法

背包问题属于组合优化中的经典问题,它有许多重要的变形,其中以多选择背包问题最为复杂.为更快地求解多选择背包问题,文中首先对该问题进行了理论分析,然后基于动态规划提出了一种新的求解算法,并对一个复杂的案例进行了测试.结果表明,这种新算法比遗传算法快9.4倍,比传统的0-1整数规划求解法快78倍.通过对数学模型的改进可大大降低问题的规模.更重要的是,所用方法可避免求解任何线性规划问题.     

背包问题的动态规划改进算法

在动态规划算法的基础上提出了改进算法,对于0-1背包问题,改进了动态规划算法的状态表示以减少需要计算的状态个数来求解该问题;对于完全背包问题,简化了动态规划算法状态的决策依赖关系来求解该问题.实验结果表明:所提出的改进算法在时空效率上具有一定的有效性和优越性.     

求解0-1背包问题的两种方法的分析与比较

背包问题(KP)是计算机科学中典型的NP-hard问题,不存在多项式时间的精确算法。本文首先给出了求解0-1KP问题的一种改进的近似算法,讨论了算法复杂度与近似比;然后,给出了求解0-1KP的动态规划算法描述,并分析了算法的复杂度;最后,对两种方法进行了理论分析,并利用3个较大规模0-1KP实例的仿真计算结果与GDPSO进行比较。     

动态规划求解0—1背包问题的教学探索

针对动态规划在0—1背包问题中求解最优值时的教学难度，结合教学过程和特点，对计算最优值的算法进行了改进，在与最优值递归公式保持一致的情况下简化了迭代过程，消除算法技巧，增加了算法的规范性和连贯性，收到了理想的教学效果。     

基于改进混合蛙跳算法的动态环境路径规划

针对复杂场景中路径规划具有未知性和动态性,传统方法无法对路径规划问题进行求解的问题,设计一种改进混合蛙跳算法的机器人路径规划方法,以提高动态环境路径规划的求解精度.首先对动态环境路径规划的研究现状进行分析,并在此基础上建立数学模型;然后采用混合蛙跳算法对该模型进行求解,并针对基本混合蛙跳算法不足进行改进;最后对路径规划的有效性进行测试.测试结果表明,混合蛙跳算法可准确找到最优的路径规划方案,可应用于复杂场景路径规划中,且性能优于其他路径规划方法.     

基于进化规划算法的背包问题求解研究

背包问题是一个具有较强应用价值的NP完全问题.如何设计求解此类问题的算法,则具有很强的实用价值和理论意义.目前已有很多的求解方法,但背包问题并没有完全解决.本文在启发式算法的理论基础上,改进了进化规划算法求解背包问题,此方法简单通用、易于操作.数值实验表明该方法具有较高的准确率,能较快的收敛到全局最优点.     

轴辐式零担运输网络中集送货线路规划研究

根据零担运输企业集送货的运营流程,对集送货线路规划问题建立一个混合整数优化的数学模型并求解;然后提出了一个启发式求解算法.该启发式算法将该模型分解为多车场、带容量约束的集货规划和送货规划问题单独求解,并通过循环找到更优解.最后,通过对所研究企业在广东省的真实数据进行实验,得到改进的线路规划成本比当前模式节约达18.8%,为零担运输企业集送货线路的科学规划提供了参考．     

基于混沌粒子群算法的柔性线缆装配序列规划技术

针对复杂机电产品中柔性线缆装配序列自动规划难题,提出了一种基于改进粒子群算法的柔性线缆装配序列规划方法.首先确定了线缆装配的约束条件,在此基础上以线缆装配优先等级、线缆长度、直径、弯曲半径、分支数为综合优化目标,建立了线缆装配序列规划的数学模型;然后对标准粒子群算法进行离散化处理,使之适用于装配序列规划问题的求解;在此基础上分别对装配序列的初始化和算法的搜索策略进行改进;最后将所提算法应用到某型号卫星结构板的线缆装配序列规划过程中,验证了其可行性与计算效率.      

基于遗传算法的多约束背包问题求解方案

采用混合遗传算法求解多约束背包问题.首先构建多约束背包问题的数学模型,然后采用多维实数编码方式的遗传算法,结合附带染色体库技术、局部启发式算子和扰动算子对问题进行求解,并给出了一个实验实例.实验证明文中采用这种混合遗传优化算法解决多约束背包问题切实可行,有较高的搜索效率.     

"背包问题"算法设计及分析

随着网络技术的不断发展，网络安全中有关密码技术的应用作为有效可行的方法倍受网络开发人员的青睐，背包公钥密码在电子商务中的公钥设计中具有其它技术不可替代的作用。因此，“背包问题”求解也是算法设计及验证的一个热点，本文分别采用了优先策略、动态规划及递归三种不同方法对“背包问题”进行求解、算法设计及验证，文中较详细的描述其设计思想，并分析了各种算法实现的复杂度问题。     

带队列约束的RHFS列生成调度算法

为有效提升多重入车间的生产效率,考虑实际生产中队列约束,提出了基于列生成算法的可重入混合流水车间的调度方法.首先对两阶段生产调度问题进行描述,以最小化工件总完成时间为优化目标,建立数学规划模型.针对该调度模型提出列生成算法,设计带多重决策的动态规划方法来求解工件级子问题,为更快收敛,主问题求解中采用自适应加速策略.在使用分支定界将得到的解整数化的过程中,构造列池并设计局部变异.最后,对各种不同问题规模进行了数值实验,结果表明所提出的调度算法是有效可行的.     

一类有效的正定式几何规划的共轭梯度法

20世纪60年代以来,非线性规划一直是各学科普遍关注的研究领域,而几何规划是一类特殊的非线性规划问题,是优化理论与方法研究的一个重要分支,并且它已成为研究与解决自然科学与工程中许多复杂问题的一个强有力的工具。共轭梯度法是最优化理论中最常用的方法之一,它具有算法简便,存储需求小等优点。因此针对无约束下的正定式几何规划问题,通过对参数βk进行适当的修正,并采用推广的Wolfe步长搜索策略,再有效结合正定式几何规划问题的显著特点,给出了一类有效的求解无约束几何规划问题的共轭梯度算法。该算法的主要特点是允许初始点任意,且收敛速度较快,具有重要的理论意义和广泛的使用价值。最后在适当的条件下,证明了该算法具有下降性及全局收敛性。     

一类模糊运输问题及其混合智能算法

研究了一类更加贴近于现实生活的模糊环境下的运输问题，即需求量和供应量均为模糊变量的运输问题．并借鉴针对模糊环境中的优化问题提出的机会约束规划模型和相关机会规划模型的思想，建立了模糊运输问题的数学模型．此外，考虑到模型涉及大量具有复杂性和多样性的模糊变量，设计了一种混合智能算法，即基于模糊模拟的遗传算法来求解模型的近似最优解．最后，数值例子表明算法的有效性和可行性．     

划分测试中测试用例最优分配问题研究

研究了划分测试中每个子域错误率已知，测试资源受约束时，测试用例如何合理分配的优化问题．主要考虑了两类测试用例分配问题：测试资源受约束的测试用例分配及测试资源受约束且各个子域的可靠性要达到一定要求时测试用例的分配，证明了带约束的测试用例最优分配问题是一个NPC问题．给出了动态规划求解方法，从理论上证明了该方法是最优的，并通过随机模拟将该方法与其它常见的测试用例分配策略进行分析比较，用实验数据验证了该办法能合理利用有限测试资源，有效地提高缺陷检测能力．     

用带权极大模理想点法求解多目标双层规划问题

研究一种具有多个决策者卷入、 各决策者的目标不止 一个、 决策者之间存在二层递阶关系系统——双层多目标规划问题. 给出双层多目标决 策问题数学模型的一种解决方法, 把带权极大模理想点法和Kuhn-Tucker条件结合起来, 从 而把双层多目标规划问题转化为单层单目标约束规划问题, 进而求得原问题的弱有效解.     

复杂非线性公用工程系统的遗传算法最优设计

提出了公用工程系统参数优化的改进模型，结合算例给出了详细的建模方法，模型包含非凸线性费用目标函数和复杂非线性约束方程，在传统优化算法难以求解的情况下，采用改进的连续化遗传算法获得了理想的结果。     

神经优化计算模型求解油田开发中的优化问题

阐述了线性优化计算和非线性优化计算的神经网络模型,该模型可以在电路时间常数数量级(几百纳秒)内求解复杂的优化问题,且能克服一般数学理论求解优化问题的缺点。之后对油田开发中使用典型曲线自动拟合产量衰减曲线进行了分析,并讨论了油田开发规划模型的建立与求解,并论证这些优化问题可以由神经优化计算模型来实现。     

求解最大割问题的分枝定界算法

最大割问题是图论中的一个典型的NP困难问题。文中基于最大割问题的半定规划松弛模型，给出了最大割问题的一种二次规划松弛模型，并且理论证明了提出的二次规划松弛模型要优于半定规划松弛模型。在谈模型的基础上，利用分枝定界算法求解最大割问题。对小规模和中等规模的最大割问题分别作数值实验。实验表明分枝定界算法能够给出最大割问题一个好的近似解，是求解中小规模最大割问题的有效方法。     

一类非线性规划问题的求解及应用

根据负荷预报和交易规则制订满足电网安全运行的调度计划,在电网管理中具有重要的应用价值。针对该问题,以经济效益为目标,在机组出力及电网安全等因素的限制下,建立了一个非线性规划模型,该模型是由一系列线性表达式的绝对值构成。对模型进行求解时,通过引入一组参数,将其分解为若干个线性规划子问题,再比较这些子问题的解,得出原问题的最优解,并从理论上证明了本算法得到的解是精确最优解。结果表明,本算法在运算效率和计算精度上均优于现有的其他算法。