遗传算法解决多背包问题

文章运用遗传算法求解多背包问题，给出了具体的求解步骤：运用两种不同的方法采处理约束条件，并将遗传算法和贪心算法进行比较通过举例给出了设置参数的具体方法，并通过对搜索效率的分析，证明了遗传算法在解决多背包问题时是行之有效的算法只需搜索解空间中的很小一部分，就可搜索到很好的结果。     

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

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

文化基因算法在第四方物流路径规划中的应用

第四方物流路径问题是复杂的组合优化问题。基本遗传算法在第四方物流路径问题上存在随着问题规模扩大,算法的成功率和准确率不断下降等缺点。针对基本的遗传算法已经不能满足规模较大的第四方物流问题等缺点,结合实验分析,提出了一种以遗传算法为全局搜索策略的文化基因算法,并针对第四方物流的问题特点设计了相应的局部搜索策略。实验结果表明,与基本遗传算法相比,该混合算法不仅在求解质量上有了较大的改进,并且在大规模第四方物流问题上也能获得质量较好的解,算法的成功率和准确率明显高于基本的遗传算法。因此,基于遗传算法的文化基因算法是解决大规模第四方物流路径问题的一种有效方法。     

求解带容量约束车辆路径问题的改进遗传算法

为解决传统遗传算法求解带容量约束的车辆路径问题时收敛速度慢和局部搜索能力差的问题,对传统遗传算法提出一种改进策略。使用基于贪婪策略的启发式交叉算子加强算法接近最优解的能力,加快算法收敛速度,在变异操作中,引入最近邻搜索算子,缩小基因变异范围,使用单点局部插入算子提高算法的局部优化能力。采用精英选择和轮盘赌法结合的选择策略,保持种群多样性以加强算法的全局搜索能力。实例计算测试表明,与传统遗传算法相比,所提算法求解平均偏差降低了70.25%,求解时间减少了87.41%;与ALNS和AGGWOA算法相比,有更高的求解质量和更好的稳定性。     

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

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

一种求解三维集装箱装箱问题的混合遗传算法

在遗传算法的基础上结合传统启发式装箱算法,设计了一个混合遗传算法,该算法既继承了遗传算法的全局搜索好的优点,也克服了遗传算法局部搜索能力差的缺点,能够较好地解决集装箱这类多目标多约束的空间三维分布的问题。     

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

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

一种求解0-1背包问题的启发式遗传算法

分析求解背包问题的多种方法,研究背包问题的贪婪策略及最优值的特点,将贪婪策略融入到遗传算法的种群初始化、交叉算子、变异算子中,将分治策略引入到选择算子中,提出一种启发式遗传算法。实验结果表明:算法无论在求解速度上还是在求解质量上都有明显改进。     

一种求解背包问题的混合遗传微粒群算法

背包问题是计算科学理论中一个著名的NP-hard问题,也是典型的组合优化问题,在物流系统的库存分配和货物装载等方面都有非常重要的应用.采用借鉴遗传算法的编码、交叉和变异的遗传微粒群算法对背包问题进行求解.为了增强遗传微粒群算法的搜索性能,将基于自学习规则的启发式算法与遗传微粒群算法相结合得到混合遗传算法用于求解背包问题.对多个标准测试实例的仿真计算表明,该算法能有效求解KP问题.     

一种改进的禁忌搜索算法求解背包问题

提出一种改进的禁忌搜索算法来求解背包问题.该算法基于禁忌搜索技术,并采用I&D策略,同时设计了两种针对局部最优解的变异算子.改进后的算法能有效地弥补标准禁忌算法对初始解依赖的缺陷,同时也避免了搜索停滞的现象.通过对具体实例和随机问题的测试,表明改进后的禁忌搜索算法有更好的性能.     

Real-coded memetic algorithms with crossover hill-climbing

This paper presents a real-coded memetic algorithm that applies a crossover hill-climbing to solutions produced by the genetic operators. On the one hand, the memetic algorithm provides global search (reliability) by means of the promotion of high levels of population diversity. On the other, the crossover hill-climbing exploits the self-adaptive capacity of real-parameter crossover operators with the aim of producing an effective local tuning on the solutions (accuracy). An important aspect of the memetic algorithm proposed is that it adaptively assigns different local search probabilities to individuals. It was observed that the algorithm adjusts the global/local search balance according to the particularities of each problem instance. Experimental results show that, for a wide range of problems, the method we propose here consistently outperforms other real-coded memetic algorithms which appeared in the literature.     

文化基因算法(Memetic Algorithm)研究进展

文化基因算法(memetic algorithm)是Pablo Moscato提出的建立在模拟文化进化基础上的优化算法,它实质上是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体.文化基因算法的概念被提出后,已被越来越多的研究人员接受和采纳.本文主要介绍了文化基因算法的起源、实现过程,以及在各类优化问题中的应用情况.     

Memetic algorithm using multi-surrogates for computationally expensive optimization problems

In this paper, we present a multi-surrogates assisted memetic algorithm for solving optimization problems with computationally expensive fitness functions. The essential backbone of our framework is an evolutionary algorithm coupled with a local search solver that employs multi-surrogate in the spirit of Lamarckian learning. Inspired by the notion of ‘blessing and curse of uncertainty’ in approximation models, we combine regression and exact interpolating surrogate models in the evolutionary search. Empirical results are presented for a series of commonly used benchmark problems to demonstrate that the proposed framework converges to good solution quality more efficiently than the standard genetic algorithm, memetic algorithm and surrogate-assisted memetic algorithms.     

A particle swarm optimization based memetic algorithm for dynamic optimization problems

Recently, there has been an increasing concern from the evolutionary computation community on dynamic optimization problems since many real-world optimization problems are dynamic. This paper investigates a particle swarm optimization (PSO) based memetic algorithm that hybridizes PSO with a local search technique for dynamic optimization problems. Within the framework of the proposed algorithm, a local version of PSO with a ring-shape topology structure is used as the global search operator and a fuzzy cognition local search method is proposed as the local search technique. In addition, a self-organized random immigrants scheme is extended into our proposed algorithm in order to further enhance its exploration capacity for new peaks in the search space. Experimental study over the moving peaks benchmark problem shows that the proposed PSO-based memetic algorithm is robust and adaptable in dynamic environments.     

Balancing exploration and exploitation in memetic algorithms: A learning automata approach

One of the problems with traditional genetic algorithms (GAs) is premature convergence, which makes them incapable of finding good solutions to the problem. The memetic algorithm (MA) is an extension of the GA. It uses a local search method to either accelerate the discovery of good solutions, for which evolution alone would take too long to discover, or reach solutions that would otherwise be unreachable by evolution or a local search method alone. In this paper, we introduce a new algorithm based on learning automata (LAs) and an MA, and we refer to it as LA‐MA. This algorithm is composed of 2 parts: a genetic section and a memetic section. Evolution is performed in the genetic section, and local search is performed in the memetic section. The basic idea of LA‐MA is to use LAs during the process of searching for solutions in order to create a balance between exploration performed by evolution and exploitation performed by local search. For this purpose, we present a criterion for the estimation of success of the local search at each generation. This criterion is used to calculate the probability of applying the local search to each chromosome. We show that in practice, the proposed probabilistic measure can be estimated reliably. On the basis of the relationship between the genetic section and the memetic section, 3 versions of LA‐MA are introduced. LLA‐MA behaves according to the Lamarckian learning model, BLA‐MA behaves according to the Baldwinian learning model, and HLA‐MA behaves according to both the Baldwinian and Lamarckian learning models. To evaluate the efficiency of these algorithms, they have been used to solve the graph isomorphism problem. The results of computer experimentations have shown that all the proposed algorithms outperform the existing algorithms in terms of quality of solution and rate of convergence.     

带时间窗车辆路径问题的文化基因算法

针对物流配送中带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）,建立了数学模型,并设计了求解VRPTW的文化基因算法。种群搜索采用遗传算法的进化模式,局部搜索采用禁忌搜索机制,并结合可行邻域结构避免对不可行解的搜索,以提高搜索效率。与单纯的遗传算法和禁忌搜索算法进行对比实验,表明该算法是求解VRPTW的一种有效方法。     

Memetic algorithms based on local search chains for large scale continuous optimisation problems: MA-SSW-Chains

Nowadays, large scale optimisation problems arise as a very interesting field of research, because they appear in many real-world problems (bio-computing, data mining, etc.). Thus, scalability becomes an essential requirement for modern optimisation algorithms. In a previous work, we presented memetic algorithms based on local search chains. Local search chain concerns the idea that, at one stage, the local search operator may continue the operation of a previous invocation, starting from the final configuration reached by this one. Using this technique, it was presented a memetic algorithm, MA-CMA-Chains, using the CMA-ES algorithm as its local search component. This proposal obtained very good results for continuous optimisation problems, in particular with medium-size (with up to dimension 50). Unfortunately, CMA-ES scalability is restricted by several costly operations, thus MA-CMA-Chains could not be successfully applied to large scale problems. In this article we study the scalability of memetic algorithms based on local search chains, creating memetic algorithms with different local search methods and comparing them, considering both the error values and the processing cost. We also propose a variation of Solis Wets method, that we call Subgrouping Solis Wets algorithm. This local search method explores, at each step of the algorithm, only a random subset of the variables. This subset changes after a certain number of evaluations. Finally, we propose a new memetic algorithm based on local search chains for high dimensionality, MA-SSW-Chains, using the Subgrouping Solis Wets’ algorithm as its local search method. This algorithm is compared with MA-CMA-Chains and different reference algorithms, and it is shown that the proposal is fairly scalable and it is statistically very competitive for high-dimensional problems.     

城市轨道车辆阻力公式经验参数文化基因优化算法的研究

为了解决城市轨道车辆阻力公式经验参数不易精确求解的问题,提出了一种改进的文化基因优化算法。首先,基于城市轨道车辆运行阻力经验公式和实际的运行数据,建立了城市轨道车辆运行阻力经验参数最优化问题的数学模型。为提升算法性能以提高求解精度,结合了遗传算法全局搜索能力强与粒子群算法收敛速度快的特点,进行优势互补,构造了的一种混合算法以便于全局搜索。其次,结合方程组求解法求解速度快和爬山法局部搜索能力强的特点,构造了一种混合算法以便于局部搜索。最后,在Matlab2010a GUI平台下采用几种不同的经验参数辨识算法和优化算法进行仿真试验。仿真结果表明,在相同条件下改进的文化基因优化算法能够寻到更精确的阻力公式经验参数。     

Evolutionary decision-makings for the dynamic weapon-target assignment problem

The dynamic weapon-target assignment (DWTA) problem is an important issue in the field of military command and control. An asset-based DWTA optimization model was proposed with four kinds of constraints considered, including capability constraints, strategy constraints, resource constraints and engagement feasibility constraints. A general “virtual” representation of decisions was presented to facilitate the generation of feasible decisions. The representation is in essence the permutation of all assignment pairs. A construction procedure converts the permutations into real feasible decisions. In order to solve this problem, three evolutionary decision-making algorithms, including a genetic algorithm and two memetic algorithms, were developed. Experimental results show that the memetic algorithm based on greedy local search can generate obviously better DWTA decisions, especially for large-scale problems, than the genetic algorithm and the memetic algorithm based on steepest local search.     

基于模因算法的多模盲均衡算法

由于常模盲均衡算法(Constant modulus blind equalization,CMA)收敛速度和均方误差都不甚理想,且对多模信号均衡时会发生相位旋转,本文提出了基于模因算法的多模盲均衡算法(Multi-modulus blind equalization algorithm based on memetic algorithm,MA-MMA)。该算法将多模盲均衡算法(Multi-modulus blind equalization algorithm,MMA)代价函数的倒数作为模因算法(Memetic algorithm,MA)的适应度函数,利用MA全局优化机制和局部深度搜索能力,在每次全局搜索后对全部新产生的个体进行局部深度搜索,将全局和局部搜索得到的最优个体解向量作为MMA的初始最优权向量。仿真结果表明,与传统的CMA,MMA以及基于遗传算法的多模盲均衡算法相比,MA-MMA 的收敛速度最快,稳态误差最小,输出信号星座图最清晰。