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

摘要：针对电力现货市场中日前(day-ahead,DA)市场和实时(real-time,RT)市场的价格差异导致的市场运行风险大、效率低等问题,可采用虚拟投标(virtual bidding,VB)对未知分布的日前和实时价差进行套利,以促进二者的价格趋同。从时空维度搭建虚拟投标的市场架构,将虚拟投标划分为机组型和负荷型2种类别,以虚拟投标者累积收益最大化为目标,建立含预算约束的多区域多时段虚拟投标模型,该模型可表述为经典的0-1背包问题。同时,采用条件风险价值工具量化风险偏好、规避、中立3种类型的虚拟投标者所面临的风险,建立考虑风险度量的电力市场虚拟投标策略模型。针对这一问题的求解,构建深度强化学习(deep reinforcement learning,DRL)网络框架,通过设计合理的状态、动作空间及奖励函数,并利用深度Q网络与环境交互,获得信息反馈并优化神经网络参数,实现对最优投标策略的有效求解。利用美国PJM电力市场2018年6—12月数据计算虚拟投标者的累积收益和夏普比率,并与贪心算法、动态规划等方法进行对比,验证了该文模型和算法的有效性、优越性。

摘要：软硬件划分是软硬件协同设计的关键环节,它决定系统中哪些组件由软件实现,哪些由硬件实现。软硬件划分问题已被证明是NP完全问题。将一类软硬件划分问题看作变异的0-1背包问题,在求解背包问题的算法基础上构造出软硬件划分问题的优质启发解。此外,采用禁忌搜索(Tabu Search)算法对求得的启发解进行改进,在软件开销和通信开销满足一定约束的条件下,使得硬件开销尽可能小。实验结果证明,所提算法对当前最新算法的改进最大可达到28%。

摘要：分析了目前网络广告投放领域存在的不足。使用能够体现网站间共同用户数量的用户迁徙网络作为平台,研究广告投放的网站选择策略。通过分析传统的网络广告投放问题的数学模型,发现其本质为0-1背包问题。通过实验比较,解决0-1背包问题常用的贪心算法和蚁群算法不能解决的广告受众重叠的问题;而使用用户迁徙网络的广告投放方法,在预算一定的情况下,达到广告的受众最多,广告投放的效果最优,是广告投放的最佳策略。

摘要：为解决差分进化算法后期收敛易陷入局部最优和早熟收敛的问题,提出一种群体智能优化算法,即协同智能的蝙蝠差分混合算法。利用蝙蝠个体脉冲回声定位的特点,与差分种群相互协作,在当前最优解gbest附近进行一次详细搜索,有效增加种群的多样性,跳出局部最优。通过蝙蝠种群和差分种群两个种群的相互协作,较好平衡全局搜索和局部开发之间的能力。为验证算法有效性,选用9个常用的基准测试函数和5个0-1背包问题,与标准粒子群算法、带高斯扰动的粒子群算法、蝙蝠算法、差分算法、烟花算法相对比,仿真实验表明,所提算法总体性能优于其它5种算法。

摘要：为了提高各类资源利用率,在分析基础设施服务层计算、存储、网络资源共性的基础上,提出以高效解决0-1背包问题为靶向的通用逐步优化策略;设计时间复杂度分别为多项式级别的基于贪婪算法、进化算法、线性规划算法的通用逐步优化策略;通过理论分析及实验验证,得出基于3类优化算法的通用逐步优化策略的优缺点及适用范围。结果表明:贪婪算法能够满足时间方面的要求,进化算法能够满足时间、单个资源利用率和整体资源利用率3个方面的要求,线性规划算法能够满足单个资源利用率和整体资源利用率2个方面的要求。

摘要：针对软件和硬件实现方式各自的优点及不足,提出了遗传算法的软硬件协同设计方法,并且将这种方法在FPGA上进行了具体的实现。首先对遗传算法流程中的各个模块进行了详细的分析,根据软硬件的不同特点以及设计实现的目标,对遗传算法的功能模块进行了软硬件划分,然后对硬件实现的部分进行了详细的介绍,包括模块之间的连接,模块的内部状态机,模块的端口,所有硬件模块的功能仿真。同时,为了保证软硬件之间的正常通讯,提出了一种新的软硬件交互通讯协议。最后将硬件实现部分做成通用IP核,方便其他设计者使用,并给出了软硬件协同的遗传算法在二进制问题和0-1背包问题两个实例中的具体应用数据。通过与纯软件实现方式的实验数据进行比较,提升了算法运行时间50%的效率,且算法的收敛性保持一致,进一步验证了该算法的适用性及高效性。

摘要：在本科课程中开展规范的科研训练是培养学生基本科研素质的途径之一。以算法课程中的0-1背包问题为例,在问题建模和算法设计的基础上,通过编程框架和测试数据,将学生工作重心集中到算法核心代码实现和实验结果分析上,通过矢量图绘制模板,训练学生绘制矢量图和分析实验结果的能力。通过在算法课程中开展科研训练,达到提升学生科研能力的目标,也为算法课程教学改革提供新思路。

摘要：为了进一步拓宽鸡群算法的研究领域,设计一种离散型鸡群算法(DCSO)。针对0-1背包问题的特点,在基本鸡群算法的基础上,对更新后的鸡群进行离散化处理,同时,在公鸡的位置更新过程中,引入自适应权重组合变异算子并动态调整变异权重,增强种群的多样性,更好地维持算法的"开采"与"搜索"两个阶段的平衡。最后,采用贪心修复算子对不可行解进行修正。通过4个经典0-1背包问题实例的仿真结果表明,相比离散粒子群算法、遗传算法和蚁群算法,DCSO算法在解的质量、收敛速度以及鲁棒性等方面效果显著提升,验证了该算法的可行性。

摘要：目的 解决人工蜂群算法在求解连续优化问题时易陷入局部最优,收敛速度慢,而且算法在最初设计时不适用于离散问题的求解等问题。方法 而0-1问题属于典型的二进制离散约束优化的NP-Hard问题,故提出了基于离散优化问题的人工蜂群算法(DABC)。首先,采用二进制编码方法,改进解的编码形式;其次,使用多维邻域搜索策略改进ABC算法的搜索策略,并在雇佣蜂阶段引入高斯变异,保持种群的多样性,加快算法的收敛速度。在侦察蜂阶段引入柯西变异算子,以增强算法的全局搜索能力,避免算法在迭代时陷入局部最优,进一步提高算法的效率和精准度。结果 通过实验仿真验证了算法的有效性和高效性,当种群规模增大时,算法的收敛速度加快,从而验证了不同的参数值对算法的影响。结论 改进后的算法在求解离散优化问题时确保种群的多样性,提高了算法的收敛速度、整体寻优能力和开发能力。