基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题

为了高效求解具有单连续变量的背包问题（KPC）,首先基于高斯误差函数提出了一个新颖S型转换函数,给出了利用该转换函数将一个实向量转换为0-1向量的新方法,由此提出了一个新的二进制粒子群优化（NBPSO）算法;然后,利用KPC的第二数学模型,并且把NBPSO与处理KPC不可行解的有效算法相结合,提出了求解KPC的一个新方法。为了检验NBPSO求解KPC的性能,利用NBPSO求解四类大规模KPC实例,并把所得计算结果与基于其他S、V型转换函数的二进制粒子群优化算法（BPSO）、具有混合编码的单种群二进制差分演化算法（S-HBDE）、具有混合编码的双种群二进制差分演化算法（B-HBDE）和二进制粒子群优化算法（BPSO）等的计算结果相比较。比较结果表明NBPSO不仅平均计算结果更优,而且稳定性更佳,说明NBPSO的性能比其他算法有显著提升。     

基于和声搜索算法求解组合优化问题

为了能够应用和声搜索算法（HSA）求解组合优化问题,基于HAS的三种操作的离散化实现提出了一种二进制和声搜索算法(BHSA),并将BHSA用于求解著名的k-可满足性(k-SAT)问题和0-1背包问题,通过与粒子群优化（BPSO）和遗传算法（GA）的实例计算对比验证了新算法的可行性与有效性。     

一种具有混合编码的二进制差分演化算法

差分演化(DE)是Storn和Price于1997年提出的一种基于个体差异重组思想的演化算法,非常适用于求解连续域上的最优化问题.首先引入"差异算子"等概念,给出DE的一种简洁算法描述,并分析了它所具有的特性.然后,为了使DE能够求解离散域上的最优化问题,基于数学变换思想引入"辅助搜索空间"和"个体混合编码"等概念,通过定义一个特殊的满射变换,在辅助搜索空间的作用下将连续域上的高效差分演化搜索变换为离散域上的同步演化搜索,由此提出了第1个二进制差分演化算法:具有混合编码的二进制差分演化算法(HBDE).接着,给出了HBDE的依概率收敛和完全收敛的定义,并利用离散Markov随机理论证明了HBDE是完全收敛的. HBDE不仅完全具有DE的各种特性和所有优点,而且非常适用于求解离散域上的最优化问题,对随机生成的大规模3-SAT问题实例和典型0/1背包问题实例的数值计算表明:该算法具有很好的全局收敛性和稳定性,其性能远远超过二进制粒子群优化算法和遗传算法.     

一种适于求解离散问题的二进制粒子群优化算法è

分析了二进制粒子群优化算法(BPSO)的缺陷.为克服此缺陷提出了"粒子位置的双重结构编码"的概念,以此为基础给出一种新的二进制粒子群优化算法--具有双重结构编码的二进制粒子群优化算法(简称DS_BPSO).DS_BPSO算法既保留了PSO的优点,又非常适用于求解离散优化问题.对随机3-SAT测试实例的数值计算表明:该算法的性能远远超过BPSO算法.     

混合二进制差异演化算法解0-1背包问题

为了有效求解0-1背包问题,提出一种混合二进制差异演化算法.该算法基于差异演化算法框架,采用二进制编码,通过增加映射操作、S型变换操作和逆映射操作等3种新的操作,将差异演化算法从实数优化领域推广至离散优化领域,成功解决了差异演化算法直接求解离散优化问题时的计算不封闭问题.此外,在每次迭代求解时,利用贪婪变换法对违反约束条件的不可行解进行变换,使其成为可行解.不同规模的背包问题的数值实验结果表明了该算法的有效性与适用性.     

二进制混合蛙跳算法求解0-1背包问题

为利用混合蛙跳算法（SFLA）求解具有二进制编码特点的组合优化问题,基于双重编码机制,提出了一种二进制混合蛙跳算法（记为BSFLA）。基于罚函数法和贪心变换策略,探讨了利用BSFLA求解背包问题（KP）的可行性与有效性。计算结果表明BSFLA与贪心策略相结合是求解KP问题的一种有效的新方法。     

利用二进制差分演化算法求解动态优化问题

利用进化算法求解动态优化问题是智能计算领域中的研究热点。基于HBDE求解动态位匹配问题（DBMP）和时变背包问题（TVKP）,在分析DBMP和TVKP的数学模型基础上分别提出利用HBDE求解它们的可行算法。与原对偶遗传算法的仿真计算结果比较表明：基于HBDE求解大规模DBMP和TVKPB问题不但是可行的,而且是高效的。     

一种具有双重进化空间的扩展粒子群优化算法

为了使粒子群优化(PSO)适于求解更多类问题,提出一种由动力空间和制导空间共同进化的改进粒子群优化算法-具有双重进化空间的扩展粒子群优化算法(简记EPSO).在EPSO中,在演化转换映射的作用下,首先将动力空间中对粒子辅助位置的进化转换为制导空间中对主导位置的进化,然后基于对主导位置的择优选择操作实现算法的进化过程.EPSO克服了PSO仅适于求解连续域最优化问题的缺陷,也非常适于求解离散组合优化问题.对于随机3-SAT问题、背包问题和TSP问题,通过与PSO、ACO和GA等算法的计算对比表明:EPSO是一种继承了PSO优点的高效、扩展演化算法.     

求解SAT问题的改进粒子群优化算法

利用限制哆公式的相关理论将可满足性问题（SAT）等价转换为定义在{0，1}^n上的多项式函数优化问题，并将二进制粒子群优化算法（BPSO）与局部爬山搜索策略相结合，给出了一种求解SAT问题的新算法：基于局部爬山搜索的改进二进制粒子群优化算法（简称IBPSO）．数值实验表明，对于随机产生的3-SAT问题测试实例，该算法的计算结果均优于著名的WalkSAT算法和SATI．3算法．     

求解背包问题的改进差异演化算法

提出一种求解0-1背包问题的改进差异演化算法。首先对差异演化算法的选择操作进行修改,得到的改进差异演化算法可以直接有效地处理约束优化问题。其次,利用一种新的区间编码映射机制,将差异演化算法扩展到求解离散领域优化问题。仿真实验结果表明,与其他进化算法相比,改进差异演化算法求解经典背包问题时,求解精度高,收敛速度快,是求解经典背包问题的一种高效算法。     

Ring Theory-Based Evolutionary Algorithm and its application to D{0-1} KP

In this paper, we propose a new view for designing an evolutionary algorithm by using algebraic theory to solve the combinatorial optimization problem. Using the addition, multiplication and inverse operation of the direct product of rings, we first propose two evolution operators: the global exploration operator (R-GEO) and the local development operator (R-LDO). Then, by utilizing the R-GEO and R-LDO to generate individuals and applying the greedy selection strategy to generate a new population, we propose a new algorithm – the Ring Theory-Based Evolutionary Algorithm (RTEA) – for the combinatorial optimization problem. Moreover, we give a new method for solving the discounted {0-1} knapsack problem (D{0–} KP) by using the RTEA. To verify the performance of the RTEA, we use it and existing algorithms to solve four kinds of large-scale instances of the D{0-1} KP. The computational results show that the RTEA performs better than the others, and it is more suitable for solving the D{0-1} KP problem. Moreover, it indicates that using algebraic theory to design evolutionary algorithms is feasible and effective.     

基于离散微粒群算法求解背包问题研究

微粒群算法(PSO)是一种新的演化算法,主要用于求解数值优化问题.基于离散微粒群算法(DPSO)分别与处理约束问题的罚函数法和贪心变换方法相结合,提出了求解背包问题的两个算法:基于罚函数策略的离散微粒群算法(PFDPSO)和基于贪心变换策略的离散微粒群算法(GDPSO).通过将这两个算法与文献[7]中的混合微粒群算法(Hybrid_PSO)进行数值计算比较发现:对于求解大规模的背包问题,GDPSO非常优秀,其求解能力优于Hybrid_PSO和PFDPSO,是求解背包问题的一种非常有效的方法.     

折扣{0-1}背包问题粒子群算法的贪婪修复策略探究

群智能启发式算法求解折扣{0-1}背包问题（D{0-1}KP）时,为提升求解效率和求解质量,需采用某种修复与优化策略将非正常编码个体转换为符合解约束条件的编码个体。在引入项集价值密度概念基础上,以粒子群算法（PSO）为例,提出一组基于项集的贪婪修复与优化方法（group greedy repair and optimization algorithm,GGROA）,并进一步构造PSO-GGRDKP算法（PSO based GGROA for solving D{0-1}KP）以探究GGROA方法的可行性和性能。PSO-NGROADKP（PSO based NGROA for solving D{0-1}KP）和PSO-GRDKP（PSO based GROA for solving D{0-1}KP）是基于项贪心修复与优化方法的粒子群算法。在D{0-1}KP标准数据集的实验结果表明：与PSO-NGROADKP和PSO-GRDKP相比,PSO-GGRDKP算法的解误差率略高,但算法时间性能分别提升了13.8%、12.9%。     

基于离散混合多宇宙算法求解折扣{0-1}背包问题

为了利用多宇宙算法（MVO）求解折扣{0-1}背包问题（D{0-1}KP）,基于模运算建立了离散型隧道模型和离散虫洞模型,引入具有反向搜索与突变特性的局部搜索策略,提出了第一个具有四进制编码的离散混合多宇宙算法DHMVO。在利用修复与优化算法消除不可行解的基础上,基于DHMVO提出了求解D{0-1}KP的一个新方法。为了检验DHMVO求解D{0-1}KP的性能,利用Kruskal-walli检验确定了其参数的最佳取值;将DHMVO求解四类大规模D{0-1}KP实例的计算结果与已有最好算法的计算结果进行比较,比较结果表明：DHMVO比其他算法的求解精度更高、稳定性更强,非常适合高效求解大规模D{0-1}KP实例。     

求解0-1背包问题的二进制狮群算法

针对传统二进制群智能算法求解0-1背包问题易陷入局部最优、收敛速度慢的缺点,提出一种新的解决离散空间问题的二进制狮群算法BLSO。二进制狮群算法对狮王、母狮和幼狮的位置重新定义,引入反置运算、移动算子和学习算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化处理和充分利用,增强局部搜索能力,进一步提高收敛速度。对9个典型的0-1背包算例进行仿真实验,实验结果表明,该算法不仅可以有效求解0-1背包问题,而且还能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性;同时,对高维背包问题的求解与参考算法相比,在寻优时间和精度上更具优势。     

求解广义背包问题的贪心DS_BPSO算法

首先针对演化算法求解背包问题定义了贪心变换的概念,并给出了该变换的一种有效实现算法;然后将此算法与文献[5]中提出的具有双重结构编码的二进制粒子群优化算法(DS_BPSO)相结合,提出了一种解决广义背包问题GKP(General Knapsack Problem)的快速算法:基于贪心变换的DS_BPSO算法(GDS_BPSO).利用该算法求解文献[3,6]中的著名背包实例,给出了该背包实例的目前最好结果.此外,对于随机生成的大规模背包实例,通过与文献[3]中的HGA算法对比计算表明:GDS_BPSO算法是求解广义背包问题的一种高效方法.     

混合猴群算法求解折扣{0-1}背包问题

针对折扣{0-1}背包问题(D{0-1}KP),当问题规模较大时,精确算法求解比较困难。基于此,将贪心核加速算子与猴群算法融合提出一种混合猴群算法(MMA)用于求解D{0-1}KP问题。同时在MMA算法的爬过程中引入诱导因子,避免爬过程陷入局部最优,再利用修复策略对不可行解进行修复。通过仿真实验,结果表明MMA算法求解大规模D{0-1}KP问题的计算性能有效,求解结果可行。     

求解0-1背包问题的混沌二进制乌鸦算法

针对离散空间的最优化问题,提出了二进制乌鸦算法,并在初始解中利用Chebyshev映射产生两种混沌序列优化乌鸦的初始解,保证个体的初始位置在整个搜索空间均匀分布;然后,为快速有效地求解0-1背包问题,引入贪心修复与优化策略处理非正常编码个体,得到基于混沌理论的二进制乌鸦算法（chaotic binary crow search algorithm,CBCSA）。仿真实验表明,CBCSA具有良好的全局寻优能力和收敛速度,能快速求得最优解,且混沌序列的第一映射方式比第二映射方式性能更佳。