利用遗传算法求解静态与动态背包问题的研究

为了有效处理遗传算法在求解静态与动态背包问题时产生非正常编码个体的问题,在分析已有处理方法不足的基础上,基于贪心策略提出了一种贪心修正算子与贪心优化算子相结合的新方法,并将该方法与遗传算法相融合给出了求解静态与动态背包问题的有效算法.仿真计算结果表明,在求解静态与动态背包问题时,利用所提出的新方法不仅可以解决非正常编码个体的问题,而且还能够显著提高个体所对应的可行解的质量,极大地改善了遗传算法的求解效果.     

交互式遗传算法的噪声及降噪策略

在交互式遗传算法中, 人对进化个体的评价含有噪声. 如何降低噪声对评价的不利影响, 至今没有有效的方法. 这严重制约了交互式遗传算法在复杂优化问题中的广泛应用. 本文首先针对交互式遗传算法中人评价个体适应值的不确定性和漂移性, 分析交互式遗传算法噪声的来源, 定义认知评价度和疲劳评价度, 给出交互式遗传算法的3阶段噪声模型; 然后, 给出基于个体海明距离的认知评价度和疲劳评价度刻画以及基于适应值可信度的降噪策略; 最后, 通过在服装设计中的应用实例验证噪声模型的正确性和降噪策略的有效性.     

快速寻优的遗传交叉策略

介绍了遗传算法中一种新的交叉策略, 它利用逼近方法决定遗传算法中子代个体的位置. 采用这种交叉策略可以使子代快速地向更高适应度的区域移动, 实验数据说明使用这种交叉策略的遗传算法可以极大地提高算法获得最优解的速度.     

最优子种群遗传算法求解柔性流水车间调度问题

为了验证最优子种群遗传算法在解决柔性流水车间调度问题时相比于传统遗传算法的优越性,分析了柔性流水车间调度问题的特点,并运用一种新的编码方法和新的遗传算法求解了该问题。考虑到最优个体保护策略法对复杂问题容易使种群收敛陷入局部最优解,为了提高精度、加快较优个体的产生并避免陷入局部最优解,首先提出了一种合理、全面的编码方法,并运用最优子种群遗传算法来求解柔性流水车间调度问题。最后运用实例验证了最优子种群遗传算法的有效性、优越性和编码方式的合理性。     

求解车辆路径安排问题的混合遗传算法

讨论了具有容量限制的车辆路径安排问题,设计了一个高效混合遗传算法。针对简单遗传算法易收敛于局部最优解的缺点,算法设计了交叉规则和选择策略。只有当两个个体的评价函数值满足一定条件时,才能进行交叉操作。采用优良个体保留策略执行选择操作,设计了保留函数。算法依据顶点间的位置关系,设计了优化策略,在每代进化中按概率选择一定数量的个体执行优化操作。数据实验表明,该算法是一个有效的求解车辆路径安排问题的混合遗传算法。     

简便的遗传算法在SSFCTP中的应用

对SSFCTP进行了研究,给出了一种简便的遗传算法,这种算法是在基本遗传算法的基础上省略掉杂交过程,仅仅通过对种群中每一个个体的基因进行随机重组而生成新种群.这样一来既可以减少计算量,提高计算效率,也可以保证种群中产生个体的多样性和可行性.并用实例验证和比较了它与基本遗传算法在解决此类问题中的有效性.同时也根据问题解的特殊结构,给出并证明了最优解的一些性质.     

基于PK模型的一种自适应遗传算法研究

遗传算法可以被理解为在逐代演化的过程中,适应性强的个体或种群具有更高的生存可能性的一种并行搜索算法。提出了基于PK竞争策略的遗传算法（Player Killing Genetical Algorithm,PKGA）,其核心思想在于通过PK赛式的竞争筛选,直至剩下一个全程最优的个体即为全局最优解。通过对全程最优解的即时检测,同时配合交叉率与变异率在个体粒度上自适应地动态调整,算法能很好地避开局部极值点并减少进化过程中的退化现象。这种PK竞争筛选策略保证了算法较高的搜索效率和较强的鲁棒性。仿真实验证明,算法在应对早熟问题和退化现象及收敛效率等方面明显优于传统的标准遗传算法。     

基于遗传算法的物流配送路径优化问题研究

遗传算法是一种基于自然进化原理的全局搜索随机算法.遗传算法在选址问题、配送问题、调度问题、运输问题、布局问题方面意义重大.在建立物流配送路径优化问题数学模型的基础上,构造了求解该问题的遗传算法.该遗传算法采用常用的二进制编码,在个体选择上结合使用最优个体保留策略和轮盘赌法.最后以这种方法进行了实验计算,通过计算结果表明,用遗传算法进行物流配送路径优化,可以方便有效地求得问题的最优解或近似最优解.     

基于进化稳定策略的遗传算法

为了解决传统遗传算法易陷入局部最优解的问题,在借鉴生物学中"进化稳定策略"的基础上,对传统的遗传算法进行了改进,提出了基于进化稳定策略的遗传算法.该算法的核心在于,稳定参数控制下的突变算子的构造,通过稳定参数的设定来稳定种群中最优个体的数目,并有目标地对最优个体进行突变操作,以达到快速扩大搜索空间、稳定群体中个体多样性的目的.仿真结果表明,该算法有效地避免了传统遗传算法中因选择压力过大造成早熟现象的发生,显著地提高了GA对全局最优解的搜索能力和收敛速度.这将使GA在众多实际的优化问题上具有更广泛的应用前景.     

一种立体匹配的新算法

提出了一种基于遗传算法进行立体匹配，并获得高密度视差图的方法。遗传算法比其它优化方法具有更强的搜索能力，因此非常适用于求解全局优化问题。利用这一特点，该文将每一幅视差图看作是一个个体，将视差值编码形成染色体，这样每个个体中都有许多染色体。然后，引入匹配约束条件，形成目标函数，利用遗传算法搜索全局最优解。另外，还采用了由粗到精的层次策略来减少匹配模糊性和搜索时间。最后，分别用合成图像和真实图像对这种方法进行了验证。     

一种防止浮点遗传算法早熟收敛的父代选择策略

通过对浮点遗传算法早熟收敛现象的分析，提出了一种新的父代选择策略，既使用当前代的子代个体作为下代的父代个体，可使交叉算子持续地探索和开发新空间。引入对个体的代数保护策略，即在它发生变异前保证有足够的演化，可以避免对新空间不成熟的开发。通过与其它父代选择策略的对比，并通过实验和GENOCOP系统比较，表明本方法能得到较好的结果。     

一种改进的非支配排序多目标遗传算法

多目标进化算法的研究目标主要是使算法快速收敛,并且广泛而均匀分布于问题的非劣最优域。在NSGA-II算法的基础上,提出了一种新的构造种群的策略——按照聚集距离选取部分非支配个体,并选取部分较好的支配个体形成下一代种群。该策略与原算法相结合后的算法(NSGA-II+IMP)与原NSGA-II进行比较,结果表明新算法较好地改善了分布性和收敛性。     

Multi-center variable-scale search algorithm for combinatorial optimization problems with the multimodal property

Combinatorial optimization problems (COPs) are discrete problems arising from aerospace, bioinformatics, manufacturing, and other fields. One of the classic COPs is the scheduling problem. Moreover, these problems are usually multimodal optimization problems with a quantity of global and local optima. As a result, many search algorithms can easily become trapped into local optima. In this article, we propose a multi-center variable-scale search algorithm for solving both single-objective and multi-objective COPs. The algorithm consists of two distinct points. First, the multi-center strategy chooses several individuals with better performance as the only parents of the next generation, which means that there are a number of separate searching areas around the searching center. Second, the next generation of the population is produced by a variable-scale strategy with an exponential equation based on the searching center. The equation is designed to control the neighborhood scale, and adaptively realize the large-scale and small-scale searches at different search stages to balance the maintenance of diversity and convergence speed. In addition, an approach of adjusting centers is proposed concerning the number and distribution of centers for solving multi-objective COPs. Finally, the proposed algorithm is applied to three COPs, including the well-known flexible job shop scheduling problem, the unrelated parallel machine scheduling problem, and the test task scheduling problem. Both the single-objective optimization algorithm and the multi-objective optimization algorithm demonstrate competitive performance compared with existing methods.     

一种新的基于进化策略的多目标优化算法

用进化策略求解多目标优化问题时，为了提高解在决策变量空间中的搜索能力和保证Pareto前沿的多样性，提出了一种新的基于进化策略的多目标优化算法。运用自适应变异步长的进化策略，使解在决策变量空间中进行全局和局部搜索；并引入非劣解按一定比例进入下一代的方法，使完全被占优的个体有机会参与到下一代的繁殖，保持了解在Pareto前沿的多样性。该算法在保证解在决策空间多样性的同时，也保持了Pareto前沿的多样性。仿真实验表明，该算法具有良好的搜索性能。     

双变异算子遗传算法的应用

针对简单遗传算法（SGA）所存在的缺点和不足,提出了一种新的改进遗传算法一双变异算子GA.该算想法通过将所有产生的子代个体与父代个体混合作为下一代种群,在种群选择前对适应度值较低的个体进行一次变异,然后通过选择、交叉,再一次变异产生新种群,再利用自适应算法改变交叉和变异率及最优保存策略保护历代最优个体,利用matlab软件编程计算,在TSP中得到了较好的优化结果。实例说明,双变异算子的遗传算法能够最大限度使种群多样性,这样最有可能得到最优解,也易突破局部收敛的局限而达到全局最优。     

具有组合变异策略的回溯搜索优化算法

针对回溯搜索优化算法收敛速度慢和易陷入局部最优的缺陷,提出了一种基于组合变异策略的改进回溯搜索优化算法。为了提高历史种群的多样性并扩大算法的搜索空间,在算法迭代过程中采用柯西种群生成策略,利用柯西分布尺度系数生成历史种群;引入基于混沌映射和伽玛分布的组合变异策略,在一定概率下对较差个体进行变异生成质量较好的个体;对新种群中越界个体采用越界处理策略,确保算法在预定的搜索空间内搜索。选取了11个标准测试函数,在低维和高维状态下进行数值仿真,并与3种表现良好的算法进行比较,结果表明该改进算法在收敛速度和收敛精度上有很大优势。     

Evolution of Appropriate Crossover and Mutation Operators in a Genetic Process

Traditional genetic algorithms use only one crossover and one mutation operator to generate the next generation. The chosen crossover and mutation operators are critical to the success of genetic algorithms. Different crossover or mutation operators, however, are suitable for different problems, even for different stages of the genetic process in a problem. Determining which crossover and mutation operators should be used is quite difficult and is usually done by trial-and-error. In this paper, a new genetic algorithm, the dynamic genetic algorithm (DGA), is proposed to solve the problem. The dynamic genetic algorithm simultaneously uses more than one crossover and mutation operators to generate the next generation. The crossover and mutation ratios change along with the evaluation results of the respective offspring in the next generation. By this way, we expect that the really good operators will have an increasing effect in the genetic process. Experiments are also made, with results showing the proposed algorithm performs better than the algorithms with a single crossover and a single mutation operator.     

Parallel skyline computation on multicore architectures

With the advent of multicore processors, it has become imperative to write parallel programs if one wishes to exploit the next generation of processors. This paper deals with skyline computation as a case study of parallelizing database operations on multicore architectures. First we parallelize three sequential skyline algorithms, BBS, SFS, and SSkyline, to see if the design principles of sequential skyline computation also extend to parallel skyline computation. Then we develop a new parallel skyline algorithm PSkyline based on the divide-and-conquer strategy. Experimental results show that all the algorithms successfully utilize multiple cores to achieve a reasonable speedup. In particular, PSkyline achieves a speedup approximately proportional to the number of cores when it needs a parallel computation the most.     

遗传算法的自适应代沟的替代策略研究

遗传算法的替代策略对遗传算法的性能具有重要意义,提出自适应代沟的替代策略,仿真表明,与现有的其他替代策略相比,该方法在不扣解的质量的情况下,使其于实数编码的遗传算法求解效率得到明显的改善。     

一种基于小生境策略的阴性选择算法

阴性选择算法是计算机人工免疫系统的传统核心算法之一,并以此为基础产生了许多改进算法,但这些算法大多存在计算时间过长以及空间资源消耗过大等问题。针对这些问题,提出了一种基于小生境策略的阴性选择算法,算法引入了小生镜策略,增强了检测器生成的多样性,降低了算法的复杂度并减少了检测器的生成时间,提高了阴性选择算法的生成效率。