贪心二进制狮群优化算法求解多维背包问题

针对经典的多约束组合优化问题——多维背包问题(MKP),提出了一种贪心二进制狮群优化(GBLSO)算法。首先,采用二进制代码转换公式将狮群个体位置离散化,得到二进制的狮群算法;其次,引入反置移动算子对狮王位置进行更新,同时对母狮和幼狮位置重新定义;然后,充分利用贪心算法进行解的可行化处理,增强搜索能力并进一步提高收敛速度;最后,对10个MKP典型算例进行仿真实验,并把GBLSO算法与离散二进制粒子群(DPSO)算法和二进制蝙蝠算法(BBA)进行对比。实验结果表明,GBLSO算法是一种有效的求解MKP的新方法,在求解MKP时具有相对良好的收敛效率、较高的寻优精度和很好的鲁棒性。     

求解多维背包问题的蚁群-拉格朗日松弛混合优化算法

针对多维背包问题(MKP) NP-hard、约束强的特点, 提出一种高效的蚁群-拉格朗日松弛(LR) 混合优化算法. 该算法以蚁群优化(ACO) 为基本框架, 并基于LR 对偶信息定义了一种MKP效用指标. ACO使得整体算法具有全局搜索能力, 所设计的效用指标将MKP的优化目标与约束条件有机地融合在一起. 该指标一方面可以用来定 义MKP核问题, 降低问题规模; 另一方面, 可以用作ACO的启发因子, 引导算法在有希望的解区域中强化搜索. 在大量标准算例上的测试结果表明, 所提出算法的鲁棒性较好; 与其他已有算法相比, 在求解质量和求解效率方面均具有很强的竞争力.

     

改进的差分演化算法求解多维背包问题

多维背包（MKP）是组合优化中一个典型的NP难问题,广泛应用于工程和管理中。提出了一种改进的二进制差分演化算法（Modified Binary Differential Evolution algorithm,MBDE）求解MKP问题,算法关键步骤可分为两部分：二进制群体生成;得到候选可行解。提出了一种有效的衡量商品价值密度的方法用于对二进制个体修正和优化;设计了反向测试搜索和精英局部搜索策略来提高算法探索和开发能力,从而进一步提高了MBDE的求解精度和收敛速度。为验证MBDE算法的有效性,进行了三组实验,并和近期提出的解决MKP问题的其他启发式算法进行了比较,实验结果显示,MBDE算法求解精度更高。从算法运行时间看,求解速度快,非常适合求解大规模的MKP问题。     

有导向变异算子的无线Mesh网负载均衡算法研究*

为了提高无线Mesh网络(WMN)的传输性能,提出基于有导向变异算子的进化算法GM-EA(guidedmutation EA)来优化WMN网关负载均衡问题。在已有的WMN负载均衡算法基础上,GM-EA算法通过结合粒子群优化的方法,更好地利用种群中的全局信息,在较少迭代次数下可以达到网关数量和负载均衡两方面的优化。仿真实验表明,GM-EA算法以增加执行时间为代价下得到的网关数量与比其他算法得到的结果更优;在网关负载均衡方面,该算法也取得较好的结果。     

多维背包问题的一个蚁群优化算法

蚁群优化(ACO)是一种通用的启发式方法,已被用来求解很多离散优化问题.近年来,已提出几个ACO算法求解多维背包问题(MKP).这些算法虽然能获得较好的解但也耗用太多的CPU时间.为了降低用ACO求解MKP的复杂性,文章基于一种已提出但未实现过的MKP的信息素表示定义了新的选择概率的规则和相应的基于背包项的一种序的启发式信息,从而提出了一种计算复杂性较低、求解性能较好的改进型蚁群算法.实验结果表明,无论串行执行还是虚拟并行执行,在计算相同任务时,新算法耗用时间少且解的价值更高.不仅如此,在实验中,文中的新算法获得了ORLIB中测试算例5.250-22的两个"新"解.     

求解多维背包问题的二级协作果蝇优化算法

针对多维背包问题(MKP)约束性强和复杂度高的特点,提出一种新型二级协作果蝇优化算法(TCFOA).提出一级果蝇和二级果蝇的产生机制,将二级果蝇划分为开发用果蝇和探索用果蝇两类以协调开发与探索之间的平衡;设计果蝇交流策略以及基于全局性价比的解的修复补偿机制,并利用二级结构扩大搜索范围、改善一级果蝇的质量,以提高求解质量.基于MKP两个标准测试集的测试结果和算法性能对比,表明TCFOA在求解MKP方面具有较强的优势.     

改进二进制布谷鸟搜索算法求解多维背包问题

针对多约束组合优化问题--多维背包问题(MKP),提出了一种改进二进制布谷鸟搜索(MBCS)算法.首先,采用经典的二进制代码变换公式构建了二进制布谷鸟搜索(BCS)算法.其次,引入病毒生物进化机制和病毒感染操作,一方面赋予布谷鸟鸟巢位置自变异机制增加种群多样性;一方面将布谷鸟鸟巢位置所组成的主群体的纵向全局搜索和病毒群体的横向局部搜索进行动态结合,进一步提高了算法的收敛速度,降低了陷入局部极值的概率.再次,针对MKP特点设计了不可行解的混合修复策略.最后将MBCS算法同量子遗传算法(QGA)、二进制粒子群优化(BPSO)算法、BCS算法就来源于ELIB数据库和OR_LIB数据库的15个算例进行了仿真对比.实验结果表明,所提算法计算误差均小于1%,标准差小于170,相比这3种算法具有相对更好的寻优精度和求解稳定性,是一种求解多维背包等NP难问题有效的算法.     

改进二进制和声搜索算法求解多维背包问题

和声搜索（HS）是一种已广泛应用于连续优化问题的元启发式方法。针对典型的组合优化问题——多维背包问题（MKP）,提出一种改进二进制和声搜索（IBHS）算法。算法通过伯努利随机过程生成二进制群体,在候选和声生成算子中,引入动态自适应参数,通过算法参数的自适应调整来协调算法的全局搜索和局部搜索,并提出一种新的更有效的衡量商品多维加权价值密度的方法用于二进制个体修正和优化;引入精英局部搜索机制进行协同寻优,提高IBHS的收敛速度。通过求解10组不同规模的典型多维背包算例和与贪心二进制狮群优化（GBLSO）算法、改进的差分演化（MBDE）算法以及二进制修正和声（BMHS）算法的对比分析,实验结果表明,所提算法在求解MKP时有具有良好的收敛效率、较高的寻优精度和很好的鲁棒性。     

基于引导素更新和扩散机制的人工蜂群算法

人工蜂群算法是一种新型的搜索算法,其机理是通过模拟蜂群采蜜过程中体现出的智能行为来实现对问题的求解.在现有的蜂群算法中,蜂群间的信息交流仅使用单一的行为通信(跳舞),蜂群间的协作存在明显不足,影响了蜂群算法的求解性能.根据真实蜜蜂多模式传递信息的客观事实,通过引入基于引导素的化学通信方式,提出一种新的更忠实反映蜂群信息传递的蜂群算法,并应用于多维背包问题(MKP)的求解.新算法将行为通信和化学通信相融合,利用引导素的更新和扩散机制使蜂群能够更好地进行协作.MKP的仿真实验结果表明新算法优于传统的ABC算法.与其他一些元启发式搜索算法的比较同样显示了新算法的有效性.     

MKP的一种向量启发信息的设计和实现

多背包问题（MKP）是一个典型的NP-hard组合优化问题。启发信息的设计是众多启发搜索算法解决MKP的关键手段之一。提出了一种新的针对MKP的启发信息设计,利用了向量距离来度量背包容量和物体消耗之间的拟和程度。基于这种启发信息,通过蚁群优化算法ACS实现了对MKP标准测试库30个实例的计算,与ACS现有启发信息相比,该方法有16例找到最优解,并全面优于同类实现。同时与当前MKP最好解决方案GA比较了2例结果,该方法的平均性能都优于该解决方案。     

最小权度的网络构建问题

网络构建问题是组合最优化中的经典问题．而连通性是网络设计问题中的一个核心问题。考虑这样一个最优化问题：给定无向图G=（V,E;W）,W：E→Q^＋是权重函数,G’=（V,E’）为G的一个子图．要寻找E的一个子集E”E．使得由E’∪E”所得的诱导子图是一个连通图,其目标是使得所有方案中权度最大者的权度值达到最小。经过对问题分析．对问题的特殊情况E’=Ф,设计了两个时间复杂度分别为O（n^2）和O（mn）的启发式算法。而E”≠Ф的情况也可以类似讨论．     

基于混沌粒子群算法和Hopfield网络求解TSP问题

针对Hopfield网络求解TSP问题经常出现局部最优解,该文将混沌粒子群算法（PSO）与之结合,提出一种基于混沌粒子群的Hopfield神经网络方法。通过实验将其与文献[5,8]以及“PSO＋HNN”策略比较,验证了该文算法不仅能够以更大概率收敛到全局最优,而且耗时更少。     

Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem

The multidimensional knapsack problem (MKP) is a combinatorial optimization problem belonging to the class of NP-hard problems. This study proposes a novel self-adaptive check and repair operator (SACRO) combined with particle swarm optimization (PSO) to solve the MKP. The traditional check and repair operator (CRO) uses a unique pseudo-utility ratio, whereas SACRO dynamically and automatically changes the alternative pseudo-utility ratio as the PSO algorithm runs. Two existing PSO algorithms are used as the foundation to support the novel SACRO methods, the proposed SACRO-based algorithms were tested using 137 benchmark problems from the OR-Library to validate and demonstrate the efficiency of SACRO idea. The results were compared with those of other population-based algorithms. Simulation and evaluation results show that SACRO is more competitive and robust than the traditional CRO. The proposed SACRO-based algorithms rival other state-of-the-art PSO and other algorithms. Therefore, changing different types of pseudo-utility ratios produces solutions with better results in solving MKP. Moreover, SACRO can be combined with other population-based optimization algorithms to solve constrained optimization problems.     

递阶遗传粒子群算法在神经网络设计中的应用

将递阶遗传粒子群算法（HGAPSO）应用于神经网络设计,可以在对网络拓扑结构优化的同时对连接权重进行求解。该算法结合了遗传算法在解决离散问题和粒子群算法在解决连续问题上的优势,并利用BP算法沿误差最速下降的能力对连接权重进一步学习,达到全局最优和快速搜索的有机结合。通过对混沌时序信号的预测,表明递阶遗传粒子群算法在较大程度上提高了神经网络的学习性能和泛化能力。     

基于遗传退火算法的飞机定检原位工作流程优化

将遗传算法(GA)应用于飞机定检原位工作流程优化中。首先,建立原位工作流程优化模型;其次,提出"排序调整法"来保证个体对应解符合工序约束;最后采用精英选择算子。模拟退火算子和自适应机制对基本遗传算法(SGA)进行改进。仿真结果表明,改进遗传算法在最优解搜索能力上较SGA有明显提高,克服了其容易"早熟"的不足;优化后原位工作完成时间较优化前缩短19.78%,验证了GA在解决定检工作流程优化问题上的适用性。     

Kernel search: A general heuristic for the multi-dimensional knapsack problem

In this paper we apply the kernel search framework to the solution of the strongly NP-hard multi-dimensional knapsack problem (MKP). Kernel search is a heuristic framework based on the identification of a restricted set of promising items (kernel) and on the exact solution of ILP sub-problems. Initially, the continuous relaxation of the MKP, solved on the complete set of available items, is used to identify the initial kernel. Then, a sequence of ILP sub-problems are solved, where each sub-problem is restricted to the present kernel and to a subset of other items. Each ILP sub-problem may find better solutions with respect to the previous one and identify further items to insert into the kernel. The kernel search was initially proposed to solve a complex portfolio optimization problem. In this paper we show that the method has general key features that make it appropriate to solve other combinatorial problems using binary variables to model the decisions to select or not items. We adapt the kernel search to the solution of MKP and show that the method is very effective and efficient with respect to known problem-specific approaches. Moreover, the best known values of some MKP benchmark problems from the MIPLIB library have been improved.