遗传算法在组合优化问题中的应用

本文通过分析遗传算法的机理和特点,介绍了遗传算法在组合优化问题中的应用。在组合优化的求解问题中,相比于其他优化算法,遗传算法具有一定的优势,但仍存在着严重的局限性。为此,本文对传统的遗传算法进行了改进,并通过TSP(旅行商)问题验证了算法的有效性。     

旅行商问题(TSP)的一种改进遗传算法

传统的序号编码遗传算法(GA)使用PMX、CX和OX等特殊的交叉算子，这些算子实施起来很麻烦。针对TSP问题的求解，提出了一种新的改进遗传算法：单亲进化遗传算法(PEGA)，PEGA是利用父体所提供的有效边的信息，使用保留最小边的方法进行个体的进化。与传统的遗传算法相比，PEGA算法弥补了它们的不足之处，简化了遗传算法。给出了PEGA算法的数值算例，仿真实验表明了该算法对于对称的TSP和非对称的TSP问题，都具有收敛速度快的特点，证明了该算法的有效性。     

组合优化问题的启发式搜索

组合优化是一个离散最优化问题,在规划,调度,资源分配,决策等问题中有着非常广泛的应用。入们已经认识到,组合优化问题的计算复杂度高,属于NP难一类的问题,除了枚举一部分解空间之外,     

求解车辆路径问题的改进遗传算法

车辆路径问题是一个典型的组合优化类问题,遗传算法是求解此类问题的方法之一。针对遗传算法容易出现“早熟”现象的问题,借鉴免疫算法通过抗体浓度抑制以保持种群多样性的优势以及模拟退火算法的个体选择策略,提出了一种改进的遗传算法,并将其用于解决车辆路径问题。实验验证了算法的有效性以及求解的效率和解的质量。     

遗传算法在一类组合优化中的应用

文章研究了一类组合优化问题如：多路旅行商问题（MTSP）及分配问题。其实质为排序优化,提出了基于GA求解排序优化的求解策略,解释了实现该算法的一些关键问题,计算机模拟结果表明了该方法的有效性。     

改进的装炉组合问题建模与优化算法

针对罩式炉退火生产中的钢卷组合堆垛优化问题,建立了以最小化钢卷组炉总加热时间为目标的数学模型。模型综合考虑了钢卷自身属性以及生产工艺约束条件等因素对钢卷组炉加热处理时间的影响。在分析罩式炉退火加热工艺规范的基础上,提出了一种改进自适应遗传算法对模型求解。算法首先类比装炉组合问题与一维装箱问题的相似点分组编码染色体,借鉴装箱问题的优化思想改善初始解种群质量;然后在工艺规则的指导下对遗传基因进行启发式交叉和变异,变异率和交叉率随种群收敛程度自适应调整以保证种群多样性和全局收敛性;最后结合局部穷举搜索方法实现了对上述模型的优化计算。仿真对比实验以及现场实际应用效果均表明该算法相对其他算法的优越性。     

关于求解难组合优化问题的蚁群优化算法

1.引言组合优化问题在规划、调度、资源分配、决策等工程问题中有着非常广泛的应用。在问题规模较小时,可以使用分支定界法或动态规划方法等来求解。当问题规模增大时,解的数目虽然有限,但呈指数增长,要在合理时间内求得准确的最优解实际上已不可能。为此,人们设计了各种启发式算法。近年来,最重要和最有希望的一个研究领域是构造“师法自然“的启发式。它们类比社会系统、物理系统、生物系统等的运行机制,设计算法在问题的解空间中进行非确定性搜索。典型的有遗传算法(GA)、模拟退火(SA)、人工神经网络(ANN)。这些算法由于其自适应性,对难组合优化问题的求解取得了好的结果,被广泛应用于工程优化和控制中。本文将要介绍的蚁群优化算法,由于其较强的自适应性和对问题状态的学习能力,正逐步成为一种新的有潜力的优化算法。     

浮点数编码遗传算法及其在电站机组组合优化中的应用

对遗传算法进行浮点数编码并设计相应的遗传操作,得到浮点数编码的遗传算法ＦＧＡ。仿真实例表明：与ＡＧＡ相比,ＦＧＡ不易陷入局部极值,收敛速度快,且能得到较高的优化精度。ＦＧＡ应用到电站机组组合优化问题中,得到良好的结果。     

基于遗传算法的TSP优化问题

TSP问题是一个典型的组合优化问题,并且也是一个NP难题,其可能的路径总数与城市数目n成指数型增长,一般很难精确地求出其最优解。这里对BP问题提出了一种改进的遗传算法,通过对遗传算法的评估函数、交叉和变异方法以及参数选择等方面的分析和修改,构造了一种自适应函数以及交叉、变异方法。通过对CHN144的测试,实验结果证明此处提出的方法能更有效的求解TSP问题。     

WTA问题的遗传算法研究

提出一种解武器－目标分配问题（weapon target assignment,WTA)的遗传算法,此方法根据遗传算法理论,设计了一种新的武器－目标分级在系式,并缩小了搜索的可行解空间,经多个战例的仿真表明此算法不仅全局收敛性好,稳定性高,易于进行并行处理,而且每个解都具有实际的可分配性。     

An improved teaching-learning-based optimization algorithm and its application to a combinatorial optimization problem in foundry industry

Teaching-learning-based optimization (TLBO) algorithm is a novel nature-inspired algorithm that mimics the teaching and learning process. In this paper, an improved version of TLBO algorithm (I-TLBO) is investigated to enhance the performance of original TLBO by achieving a balance between exploitation and exploration ability. Inspired by the concept of historical population, two new phases, namely self-feedback learning phase as well as mutation and crossover phase, are introduced in I-TLBO algorithm. In self-feedback learning phase, a learner can improve his result based on the historical experience if his present state is better than the historical state. In mutation and crossover phase, the learners update their positions with probability based on the new population obtained by the crossover and mutation operations between present population and historical population. The design of self-feedback learning phase seeks the maintaining of good exploitation ability while the introduction of the mutation and crossover phase aims at the improvement of exploration ability in original TLBO. The effectiveness of proposed I-TLBO algorithm is tested on some benchmark functions and a combinatorial optimization problem of heat treating in foundry industry. The comparative results with some other improved TLBO algorithms and classic algorithms show that I-TLBO algorithm has significant advantages due to the balance between exploitation and exploration ability.     

一种新的免疫进化算法在函数优化中的应用

针对克隆选择算法在求解高维函数优化问题时易陷入局部最优以及收敛速度较慢的弱点,本文基于生物免疫系统内部学习优化机制以及进化算法,提出了一种新的免疫进化算法,它包括正交交叉、单形交叉、克隆、多极变异和选择。新算法将进化计算的思想融入到克隆选择中,提出了一种新的变异算子,在保证种群多样性的同时提高了算法的全全局寻优能力。理论分析证明了算法的收敛性,并将算法应用于不同的测试函数进行仿真实验。结果表明,该算法是有效的。     

An improved differential evolution algorithm with triangular mutation for global numerical optimization

This paper presents an Improved Differential Evolution (IDE) algorithm for solving global numerical optimization problems over continuous space. The proposed algorithm introduces a new triangular mutation rule based on the convex combination vector of the triplet defined by the three randomly chosen vectors and the difference vector between the best and the worst individuals among the three randomly selected vectors. The mutation rule is combined with the basic mutation strategy through a non-linear decreasing probability rule. Furthermore, a restart mechanism is also proposed to avoid premature convergence. IDE is tested on a well-known set of unconstrained problems and shows its superiority to state-of-the-art differential evolution variants.     

基于新型免疫算法的多峰函数优化

针对目前多峰函数优化问题较难找到全部局部最优解的情况,提出了改进的免疫优化求解方法。借鉴免疫系统的受体编辑操作、Baldwin效应,设计了相应的算子,增强了算法的学习能力,提高了算法的收敛速度。实验结果表明,本算法求解精度较高,提高了多峰函数寻优的精度。     

求解函数优化的新型差异演化算法*

针对差异演化算法存在早熟收敛和后期求解效率低的缺点,提出一种新型差异演化算法。该算法基于单种群,在演化过程中直接对当前种群进行变异、交叉和选择操作,无须差异演化算法中的中间过渡种群。此外,新型差异演化算法的变异与交叉概率是时变的,其中变异概率随着迭代次数的增加而减小;交叉概率随着迭代次数的增加而增加。对几个典型的测试函数进行仿真实验表明,该算法能够有效避免早熟收敛,改善了差异演化算法的优化性能。     

基于交叉变异的混合粒子群优化算法

粒子群优化算法是一种基于群体智能理论的全局优化算法,通过群体中粒子间的合作与竞争实现对问题空间的高效搜索。针对算法后期收敛速度较慢、易陷入局部最优的缺点,提出了一种混合粒子群算法。该算法通过改变种群初始化方法,引入交叉和变异机制等措施改善基本粒子群算法的性能。数值试验结果表明,改进型粒子群算法在提高全局寻优能力和加快收敛速度等方面均有良好的表现。     

An immune memory clonal algorithm for numerical and combinatorial optimization

Inspired by the clonal selection theory together with the immune network model, we present a new artificial immune algorithm named the immune memory clonal algorithm (IMCA). The clonal operator, inspired by the immune system, is discussed first. The IMCA includes two versions based on different immune memory mechanisms; they are the adaptive immune memory clonal algorithm (AIMCA) and the immune memory clonal strategy (IMCS). In the AIMCA, the mutation rate and memory unit size of each antibody is adjusted dynamically. The IMCS realizes the evolution of both the antibody population and the memory unit at the same time. By using the clonal selection operator, global searching is effectively combined with local searching. According to the antibody-antibody (Ab-Ab) affinity and the antibody-antigen (Ab-Ag) affinity, The IMCA can adaptively allocate the scale of the memory units and the antibody population. In the experiments, 18 multimodal functions ranging in dimensionality from two, to one thousand and combinatorial optimization problems such as the traveling salesman and knapsack problems (KPs) are used to validate the performance of the IMCA. The computational cost per iteration is presented. Experimental results show that the IMCA has a high convergence speed and a strong ability in enhancing the diversity of the population and avoiding premature convergence to some degree. Theoretical roof is provided that the IMCA is convergent with probability 1.     

一种改进的多目标粒子群优化算法及其应用

针对多目标粒子群优化算法在求解约束优化问题时存在难以兼顾收敛性能和求解质量这一问题,提出一种基于免疫网络的改进多目标粒子群优化算法.该算法通过免疫网络互通种群最优信息达到粒子群算法与人工免疫网络算法的协同搜索,同时给出了速度迁移策略、自适应方差变异策略和基于聚类的免疫网络策略.最后将所提出的方法应用于求解电弧炉供电优化模型,达到了减少电量消耗、缩短冶炼时间、延长炉衬使用寿命的目的,同时表明了该算法的有效性.     

一种新的约束优化遗传算法及其工程应用

提出一种新的用于求解约束优化问题的遗传算法,该算法利用佳点集方法初始化个体以维持种群的多样性.在进化过程中,通过可行解与不可行解算术交叉对问题的决策空间进行搜索;对可行种群与不可行种群分别采用高斯变异和柯西变异,从而协调算法的勘探和开采能力.几个标准测试问题的实验结果表明该算法的有效性;应用新算法求解两个工程优化设计问题,结果表明该算法的可行性.     

改进果蝇算法在净化除钴过程锌粉量优化设定中的应用

本文提出一种基于细菌迁徙的自适应果蝇算法(CAFOABM),用于求解净化除钴过程锌粉添加量优化设定问题.首先从净化除钴的反应机理出发,通过引入除钴率建立锌粉添加量与氧化还原电位值、出口钴离子浓度间带约束的非线性优化设定模型;为了避免果蝇算法在迭代寻优过程中出现停滞现象,CAFOABM引入多种群并行搜索策略和改进搜索算子对搜索状态的转移规则进行改进;并采用区分可行解与不可行解法进行约束处理,保留一定比例的不可行解个体,有效避免了有用解信息的丢失.实际生产数据验证结果表明,CAFOABM算法优化设定的锌粉添加量与人工操作的经验数据相比减少7.83%,出口钴离子浓度满足实际生产要求且趋于平稳.