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

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

求解0-1背包问题的混合蝙蝠算法

针对基本蝙蝠算法易陷入局部最优、收敛速度慢等缺点,对其进行优化研究。基于0-1背包问题的具体特征,在基本蝙蝠算法原有概念和框架的基础上,引入遗传算法中的交叉机制以及反置算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化和充分利用,增强局部搜索能力,加快算法收敛速度,构建全新的混合蝙蝠算法。将混合蝙蝠算法应用于两组0-1背包算例,仿真实验结果优于自适应元胞粒子群算法、基本蝙蝠算法和贪心二进制蝙蝠算法。结果验证了该混合算法求解0-1背包问题的可行性和有效性。     

基于蜂群遗传算法的0-1背包问题

针对0-1背包问题,本文提出了基于蜂群遗传算法的优化求解方案。该算法包括两个种群,一个主要用于全局搜索,另一个主要用于局部搜索;每个个体采用二进制编码;采用最优个体交叉策略;对当前解的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止;不符合约束条件的解采用诱变因子指导变异处理;遗传算子包括单点交叉算子、简单变异算子、主动进化算子和抑制算子。本算法充分发挥了遗传算法的群体搜索和全局收敛的特性,快速地并行搜索,有效地克服了经典遗传算法容易陷入局部最优问题。数值实验表明,该算法在求解0-1背包问题中取得了较好的效果,同样可以应用于其它的组合优化问题。     

求解0-1背包问题的改进二进制捕鱼算法

经典群智能算法在求解0-1背包问题时普遍存在全局搜索能力不强、求解精度不高、收敛速度慢等缺点。针对这一情况,将二进制编码引入捕鱼算法中,提出二进制捕鱼算法。在此基础上,结合算法本身的特点,添加靠近搜索方法,改善渔夫之间的协作效果;借鉴贪心算法和轮盘赌的思想,设计贪心轮盘赌策略,并结合随机比例参数来改善算法初值;同时引入自适应半径系数来解决步长参数设置的问题,进而提出了一种改进二进制捕鱼算法。实验与对比部分对15个0-1背包问题进行求解测试,结果表明,对于常用算例而言,与其它群智能算法相比,改进二进制捕鱼算法能找到全部问题的最优解,且在总体性能上看较优;对于100维及以上的高维背包问题而言,改进算法在求解精度、稳定性、收敛速度、运行耗时等方面均具有明显优势。因此,将改进二进制捕鱼算法应用于求解0-1背包问题是有效的和可行的。     

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

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

遗传算法在0/1背包问题中的应用及研究

遗传算法作为一种优胜劣汰的自然规律,可应用于人工智能、机器学习等多个方面。本文将遗传算法应用于0/1背包问题,首先介绍简单遗传算法,通过实验数据分析遗传算法在搜索范围、收敛速度和精度等方面的不足,进而基于贪心算法、适应度函数及遗传算子,修正可行解和不可行解,逐步改进遗传算法,防止算法陷于局部最优,提高算法的全局搜索能力和收敛速度。最后通过实验数据,比较简单遗传算法和改进遗传算法的实验结果,证明改进遗传算法在0/1背包问题应用中的精确性和高效性。     

全局最优引导的差分演化二进制人工蜂群算法

针对基本二进制人工蜂群算法开采能力弱、收敛速度慢的缺点,提出一种全局最优引导的差分二进制人工蜂群算法。算法仿照粒子群优化,将全局最优参数引入二进制人工蜂群算法中以提高开采能力;同时受差分演化算法中“交叉”操作的启发,提出多维邻域搜索方式,加快收敛速度。采用0-1背包问题进行仿真,实验结果表明与传统算法相比,提出算法不仅寻优能力增强且收敛速度明显提高。对于10维背包问题,提出算法的收敛速度比基本二进制人工蜂群算法提高近10倍。     

遗传变异蝙蝠算法在0-1背包问题上的应用

0-1背包问题是经典组合优化NP难题。在蝙蝠算法的基础上结合遗传变异的思想,引入主动进化算子、无效蝙蝠和当前最优位置蝙蝠集聚的处理规则,提出了遗传变异蝙蝠算法,并将其用于求解0-1背包问题。仿真结果表明：该算法在收敛速度和精度上优于基本蝙蝠算法,并且能够有效地求解0-1背包问题。     

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

提出一种改进的混沌遗传算法来求解0-1背包问题。通过利用幂函数载波技术增强混沌搜索的遍历性,把混沌搜索得到的最优解直接作为新群体嵌入遗传算法来改善遗传算法的早熟问题,从而使算法有能力避免陷入局部极值而快速收敛于全局最优解。仿真实验结果表明了该算法求解0-1背包问题的有效性和适用性。     

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

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

An improved monkey algorithm for a 0-1 knapsack problem

The 0-1 knapsack problem is a classic combinational optimization problem. However, many exiting algorithms have low precision and easily fall into local optimal solutions to solve the 0-1 knapsack problem. In order to overcome these problems, this paper proposes a binary version of the monkey algorithm where the greedy algorithm is used to strengthen the local search ability, the somersault process is modified to avoid falling into local optimal solutions, and the cooperation process is adopted to speed up the convergence rate of the algorithm. To validate the efficiency of the proposed algorithm, experiments are carried out with various data instances of 0-1 knapsack problems and the results are compared with those of five metaheuristic algorithms.     

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

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

一种求解0-1背包问题的二进制修正和声搜索算法

针对0-1 背包问题, 提出一种二进制修正和声搜索算法. 该算法修正了即兴创作过程, 对参数PAR进行动态调整, 同时提出一种随机修复机制, 有效修复不可行的和声, 增强算法的局部搜索. 采用一种可行和声初始化方式, 保证初始和声都是可行的, 整个搜索过程完全采用0-1 二进制模式, 对14 个0-1 背包问题进行测试. 将所提出算法与其他算法进行比较, 结果验证了所提出算法的有效性.

     

基于拉马克进化的差分进化算法求解KPC问题

具有单连续变量的背包问题(knapsack problem with a single continuous variable,KPC)是标准0-1背包问题的自然推广,在KPC中背包容量不是固定的,因此其求解难度变大.针对现有差分进化(differential evolution,DE)算法在高维KPC实例上求解精度不...