遗传算法的一种新颖编码研究

提出了一种新的基于N进制分部编码算子的遗传算法．该编码算子首先将每个基因值用N进制的浮点数表示，然后将其分为整数部分和小数部分，分别重新编码组成染色体；相应的选择、交叉、变异算子采用符号编码的思想，充分利用N进制浮点数的特点进行设计．在遗传算法开始阶段，该编码算子进行整数部分和小数部分的遗传操作，使得遗传算法在早期具有很强的全局搜索能力，避免陷入局部极值；在后期进行小数部分的遗传操作，使得遗传在后期具有很强的局部搜索能力，能够很快地搜索到全局极值．通过理论分析，证明了N进制分部编码算子与传统的浮点数编码和二进制编码算子相比具有优越性，并通过典型函数的仿真进行了验证．     

基于禁忌搜索遗传混合算法的装配线平衡

针对装配线平衡问题（ALBP）,文中提出了一种禁忌搜索遗传混合算法。在混合算法中,遗传算法部分采用特殊的遗传变异操作算子（双点交叉和移位插入变异）,使算法只在可行作业序列子空间中进行搜索,有效减小了搜索范围,提高了算法运行效率;禁忌搜索部分是在每代遗传操作完成以后,随机选择一些个体进行禁忌搜索操作,来增强算法的搜索能力。最后以经典问题的求解验证了禁忌搜索遗传算法在收敛性能和计算效率上较使用单纯的遗传算法高。     

一种基于IP网络的QoS约束组播路由算法

针对时延约束最小代价组播路由问题,结合禁忌搜索算法和模拟退火算法的优点,提出了一种改进的混合遗传路由算法TSSAGMA。通过分析与仿真,证实了该算法在解决时延约束最小代价组播路由的问题上优于传统算法,能够在较小的代价下搜索到较好的解。     

Nonlinear inversion of potential-field data using a hybrid-encoding genetic algorithm

Using a genetic algorithm to solve an inverse problem of complex nonlinear geophysical equations is advantageous because it does not require computer gradients of models or “good” initial models. The multi-point search of a genetic algorithm makes it easier to find the globally optimal solution while avoiding falling into a local extremum. As is the case in other optimization approaches, the search efficiency for a genetic algorithm is vital in finding desired solutions successfully in a multi-dimensional model space. A binary-encoding genetic algorithm is hardly ever used to resolve an optimization problem such as a simple geophysical inversion with only three unknowns. The encoding mechanism, genetic operators, and population size of the genetic algorithm greatly affect search processes in the evolution. It is clear that improved operators and proper population size promote the convergence. Nevertheless, not all genetic operations perform perfectly while searching under either a uniform binary or a decimal encoding system. With the binary encoding mechanism, the crossover scheme may produce more new individuals than with the decimal encoding. On the other hand, the mutation scheme in a decimal encoding system will create new genes larger in scope than those in the binary encoding. This paper discusses approaches of exploiting the search potential of genetic operations in the two encoding systems and presents an approach with a hybrid-encoding mechanism, multi-point crossover, and dynamic population size for geophysical inversion. We present a method that is based on the routine in which the mutation operation is conducted in the decimal code and multi-point crossover operation in the binary code. The mix-encoding algorithm is called the hybrid-encoding genetic algorithm (HEGA). HEGA provides better genes with a higher probability by a mutation operator and improves genetic algorithms in resolving complicated geophysical inverse problems. Another significant result is that final solution is determined by the average model derived from multiple trials instead of one computation due to the randomness in a genetic algorithm procedure. These advantages were demonstrated by synthetic and real-world examples of inversion of potential-field data.     

一种求解旅行商问题的改进遗传算法

针对基本遗传算法存在容易"早熟",无法全局收敛的现象,设计了一种新交叉算子和变异算子,并在遗传算子构造中引入贪心控制策略.新算子的引入丰富了种群的多样性,提高了算法的全局搜索能力.实例仿真表明,改进遗传算法在迭代陷入局部最优时,能在较短的时间内跳出局部最优,继续寻找全局最优解.     

An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type-II

In this study, we consider the assembly line worker assignment and balancing problem of type-II (ALWABP-2). ALWABP-2 arises when task times differ depending on operator skills and concerns with the assignment of tasks and operators to stations in order to minimize the cycle time. We developed an iterative genetic algorithm (IGA) to solve this problem. In the IGA, three search approaches are adopted in order to obtain search diversity and efficiency: modified bisection search, genetic algorithm and iterated local search. When designing the IGA, all the parameters such as construction heuristics, genetic operators and local search operators are adapted specifically to the ALWABP-2. The performance of the proposed IGA is compared with heuristic and metaheuristic approaches on benchmark problem instances. Experimental results show that the proposed IGA is very effective and robust for a large set of benchmark problems.     

Genetic algorithms for flowshop scheduling problems

In this paper, we apply a genetic algorithm to flowshop scheduling problems and examine two hybridizations of the genetic algorithm with other search algorithms. First we examine various genetic operators to design a genetic algorithm for the flowshop scheduling problem with an objective of minimizing the makespan. By computer simulations, we show that the two-point crossover and the shift change mutation are effective for this problem. Next we compare the genetic algorithm with other search algorithms such as local search, taboo search and simulated annealing. Computer simulations show that the genetic algorithm is a bit inferior to the others. In order to improve the performance of the genetic algorithm, we examine the hybridization of the genetic algorithms. We show two hybrid genetic algorithms: genetic local search and genetic simulated annealing. Their high performance is demonstrated by computer simulations.     

用于游戏NPC路径规划的改进遗传算法

针对游戏非玩家控制(NPC)路径规划中传统遗传算法计算速度慢、正确率低等问题,设计了改进型遗传算法.提出了最佳种群规模估计方法,设计了基于精英主义思想的遗传算子.根据游戏地图的特点,引入了基于启发式深度优先搜索的变异操作.与传统遗传算法以及其他学者的改进算法进行了对比实验.实验结果表明:算法能够在保证正确率的前提下,提高计算速度,并且在多目标的环境下同样适用.     

PHGA-COFFEE:多序列比对问题的并行混合遗传算法求解

设计了一个求解多序列比对问题的并行混合遗传算法（与之相应的软件称为PHGA-COFFEE）.该算法采用COFFEE函数作为个体的适应度函数,构造了六种遗传算子,特别是设计了两种新颖的变异算子,其中一种变异算子基于COFFEE的一致性信息设计,以改善算法的整体搜索能力.另一种变异算子基于动态规划方法设计,以增强其局部搜索能力.通过对BAliBASE中144个测试例的测试,证明该算法是有效的.与已有的算法相比,该算法对处于朦胧区和具有N/C末端延伸的序列比对问题有更强的问题求解能力.同时通过对算法并行化,其运行时间显著缩短.     

基于开放读码框架的GEP遗传算子

基因表达式编程（GEP）采用的已有单点重组、两点重组、插串等遗传操作有很大概率发生在基因的非编码区,导致搜索过程中遗传操作前后的基因解码成相同的表达式树,这在一定程度上影响了GEP的搜索性能。为解决这一问题,提出了一类基于开放读码框架的遗传算子,这类算子从基因的编码区中选取作用点,以保证遗传操作将改变编码区中的基因片段,从而使遗传操作后的基因能解码成不同的表达式树。实验结果表明,与已有的同类遗传算子相比,提出的遗传算子缩短了GEP算法进化代数,提高了算法的成功率。     

求解k条最优路径问题的遗传算法

文章提出的任意两点间k条最优路径问题的遗传算法,采用节点的自然路径作为染色体编码,根据路径节点的连接实施染色体的交叉操作,将节点路径块作为染色体的变异基因块实施变异操作。算法结构简明,收敛速度快,可应用于求解大规模网络中的多条最优路径问题。     

基于跳跃基因算子的改进实数遗传算法

为了避免遗传算法在求解数值优化问题时出现搜索能力差、多样性缺失等弊端,提出一种基于实数编码的改进遗传算法(IRCGA).算法集成两个特别设计的算子:模拟二进制跳跃基因算子(SBJG)和多方向交叉算子(MX).SBJG算子以染色体为操作对象,本质上模拟了二进制跳跃基因操作中的插入运动,即利用一种随机的方式将选定的染色体块插入到染色体位点,实现种群内部染色体间的转位,为种群提供额外的遗传多样性;MX算子通过增加交叉方向的方式扩大算子的搜索区域,从而提升后代个体质量与算法的搜索能力.在11个实例的基础上进行对比实验,结果表明,采用改进算子能够明显提升算法在求解数值优化问题时的性能,同时,相比于其他先进有效的算法,IRCGA具有较强的搜索能力且能够维持一定的种群多样性,从而验证了改进算法的有效性和可行性.     

基于遗传粒子群算法的高维复杂函数优化方法

针对高维复杂函数优化的特点,提出了一种遗传算法与粒子群算法相结合的主-从结构算法。算法中,主级为全局搜索的遗传算法;从级为局部邻域搜索的粒子群算法。通过主-从协调机制和从级转换函数设计,使算法不依赖复杂的编码方式和进化算子进行全局精确搜索。通过仿真和比较实验,验证了算法对高维复杂函数优化的有效性。     

A hybrid multi-population genetic algorithm for the dynamic facility layout problem

Due to inherent complexity of the dynamic facility layout problem, it has always been a challenging issue to develop a solution algorithm for this problem. For more than one decade, many researchers have proposed different algorithms for this problem. After reviewing the shortcomings of these algorithms, we realize that the performance can be further improved by a more intelligent search. This paper develops an effective novel hybrid multi-population genetic algorithm. Using a proposed heuristic procedure, we separate solution space into different parts and each subpopulation represents a separate part. This assures the diversity of the algorithm. Moreover, to intensify the search more and more, a powerful local search mechanism based on simulated annealing is developed. Unlike the available genetic operators previously proposed for this problem, we design the operators so as to search only the feasible space; thus, we save computational time by avoiding infeasible space. To evaluate the algorithm, we comprehensively discuss the parameter tuning of the algorithms by Taguchi method. The perfectly tuned algorithm is then compared with 11 available algorithms in the literature using well-known set of benchmark instances. Different analyses conducted on the results, show that the proposed algorithm enjoys the superiority and outperformance over the other algorithms.     

求解折扣{0-1}背包问题的新遗传算法

折扣{0-1}背包问题（Discounted {0-1} Knapsack Problem,D{0-1}KP）是比0-1背包还要难以求解的NP-hard问题。提出了一种求解D{0-1}KP的新遗传算法GADKP。GADKP针对D{0-1}KP问题本身结构特征,借鉴启发式搜索思想设计了3种有效的交叉算子和1种变异算子。4种算子的操作都能够保证进化过程中解的可行性;3种交叉算子从3个不同的角度提高算法的搜索能力;变异算子采用逐层贪心机制提高个体的局部开发能力。通过4组共40个D{0-1}KP实例测试,和已有的求解D{0-1}KP的遗传算法相比,GADKP求解精度更高,是一种新颖有效的求解D{0-1}KP的方法。     

项目优化调度的病毒协同进化遗传算法

针对次序约束和资源约束的多模式项目调度问题提出了一种病毒协同进化遗传算法,并提出了解的编码、选择、交叉、变异和病毒感染操作等.算法用于求解项目活动的一个最优调度顺序和资源模式以使项目的成本最低,其操作特点是既可以通过遗传操作在父子代群体之间纵向传播进化基因进行全局搜索,又可以通过病毒感染操作在同一代群体内横向传播进化基因进行局部搜索.利用模板理论对算法的性能进行了分析.理论分析和实验结果表明,算法的搜索性能优于一般的遗传算法.算法对于不同优化目标的多模式项目调度问题可以同时求得一个满足次序约束的项目活动的最优调度顺序和满足资源约束的最优资源模式.     

On Appropriate Adaptation Levels for the Learning of Gene Linkage

A number of algorithms have been proposed aimed at tackling the problem of learning “Gene Linkage” within the context of genetic optimisation, that is to say, the problem of learning which groups of co-adapted genes should be inherited together during the recombination process. These may be seen within a wider context as a search for appropriate relations which delineate the search space and “guide” heuristic optimisation, or, alternatively, as a part of a comprehensive body of work into Adaptive Evolutionary Algorithms. In this paper, we consider the learning of Gene Linkage as an emergent property of adaptive recombination operators. This is in contrast to the behaviour observed with fixed recombination strategies in which there is no correspondence between the sets of genes which are inherited together between generations, other than that caused by distributional bias. A discrete mathematical model of Gene Linkage is introduced, and the common families of recombination operators, along with some well known linkage-learning algorithms, are modelled within this framework. This model naturally leads to the specification of a recombination operator that explicitly operates on sets of linked genes. Variants of that algorithm, are then used to examine one of the important concepts from the study of adaptivity in Evolutionary Algorithms, namely that of the level (population, individual, or component) at which learning takes place. This is an aspect of adaptation which has received considerable attention when applied to mutation operators, but which has been paid little attention in the context of adaptive recombination operators and linkage learning. It is shown that even with the problem restricted to learning adjacent linkage, the population based variants are not capable of correctly identifying building blocks. This is in contrast to component level adaptation which outperforms conventional operators whose bias is ideal for the problems considered.     

双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题

在实际生产过程中,生产调度和设备维护相互影响,因此两者应该统筹优化.为研究具有预防性维护的分布式柔性作业车间调度问题,以最小化最大完工时间为目标,提出一种双种群混合遗传算法.结合问题特性,设计三维编码以及对应的机器解码方案,采用不同的策略初始化种群以均衡一部分工厂负载,为双种群设计不同的交叉变异算子提高算法的多样性,并利用交换精英解的方法实现两个种群的协作优化,同时针对关键工厂和预防性维护操作设计相应的局部搜索.最后对比现有算法,在同构和异构工厂的算例上进行实验,使用正交试验法优化算法参数设置.实验结果验证了局部搜索以及种群协作的有效性和双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题的优越性.     

A multi-objective genetic algorithm for mixed-model assembly line rebalancing

When demand structure or production technology changes, a mixed-model assembly line (MAL) may have to be reconfigured to improve its efficiency in the new production environment. In this paper, we address the rebalancing problem for a MAL with seasonal demands. The rebalancing problem concerns how to reassign assembly tasks and operators to candidate stations under the constraint of a given cycle time. The objectives are to minimize the number of stations, workload variation at each station for different models, and rebalancing cost. A multi-objective genetic algorithm (moGA) is proposed to solve this problem. The genetic algorithm (GA) uses a partial representation technique, where only a part of the decision information about a candidate solution is expressed in the chromosome and the rest is computed optimally. A non-dominated ranking method is used to evaluate the fitness of each chromosome. A local search procedure is developed to enhance the search ability of moGA. The performance of moGA is tested on 23 reprehensive problems and the obtained results are compared with those by other authors.     

基于改进遗传算法的可重构计算任务划分

为实现可重构计算中的软硬件任务自动划分,引入了遗传算法来搜寻最优解。为解决标准遗传算法可能出现种群早熟和种群进化后期收敛速度慢的问题,使用了小生境技术来保护种群中基因的多样性。设计了能够随适应度自动改变的自适应遗传算子（杂交算子和变异算子）。对算法进行了50次随机实验,并对结果进行分析。实验表明,改进后的遗传算法搜寻到全局最优任务划分的概率和搜寻到最优任务划分时的进化代数都要优于标准遗传算法。