《进化算法遗传算法》由会员分享，可在线阅读，更多相关《进化算法遗传算法（216页珍藏版）》请在金锄头文库上搜索。
1、Soft Computing Lab. XiDian UNIVERSITY1. Introduction to Genetic AlgorithmsInstitute of Intelligent Information Processing, XiDian University 优化问题优化问题o对于一个求函数最大值的优化问题，一般可描述为下述数学规划模型：Soft Computing Lab.2XiDian UNIVERSITY 例：无约束单目标，多峰例：无约束单目标，多峰Soft Computing Lab.3XiDian UNIVERSITY 约束单目标约束单目标Soft Comput
2、ing Lab.4XiDian UNIVERSITY 约束多目标约束多目标Soft Computing Lab.5XiDian UNIVERSITY TSP旅行商问题（TSP,traveling salesman problem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。（n1)!/2Soft Computing Lab.6XiDian UNIVERSITY TSP ADECBThe one below is length: 33ABCDEA57415B53410C7327D4429E151079Soft
3、 Computing Lab.7XiDian UNIVERSITY 传统最最优化面化面临新挑新挑战：实际问题：实际问题离散性问题主要指组合优化不确定性问题随机性数学模型半结构或非结构化的问题大规模问题：超高维动态优化问题有噪的现代优化方法： 追求满意近似解 实用性强解决实际问题Soft Computing Lab.8XiDian UNIVERSITY 优化问题的复杂性优化问题的复杂性Complexity: Hard problems and Easy problems When S is small (e.g. 10, 100, or only 1,000,000 or so items),
4、we can simply do socalled exhaustive search(穷举搜索)Exhaustive search: Generate every possible solution, work out its fitness, and hence discover which is best (or which set share the best fitness) 比如从n个数找到最大This is also called Enumeration(列举法）列举法）Soft Computing Lab.9XiDian UNIVERSITY 问题的复杂度问题的复杂度 This
5、 is all about characterising how hard it is to solve a given problem. Statements are made in terms of functions of n, which is meant to be some indication of the size of the problem. E.g.:（通过n的一个函数来描述问题的复杂度） Correctly sort a set of n numbers（排序）oCan be done in around n log n steps Find the closest p
6、air out of n vectors（从n个向量找出最接近两个)oCan be done in O(n2) stepsFind best multiple alignment of n sequences.oCan be done in O(2n) steps Soft Computing Lab.10XiDian UNIVERSITY Polynomial and Exponential ComplexityGiven some problem Q, with size n, imagine that A is the fastest algorithm known for solvin
7、g that problem exactly. The complexity of problem Q is the time it takes A to solve it, as a function of n. (问题Q的维数为n，A是一个已知快速算法，复杂度就是通过A求解Q所用时间)There are two key kinds of complexity:Polynomial: the dominant term in the expression is polynomial in n. E.g. n34, n.log.n, sin(n2.2), etc Exponential: th
8、e dominant term is exponential in n. E.g. 1.1n, nn+2 , 2n, Soft Computing Lab.11XiDian UNIVERSITY Polynomial and Exponential Complexity 1.1n1.211.331.461.611.772.596.7311713,780n1.12.143.354.595.877.1812.627.073.9159n234561020 50100Problems with exponential complexity take too long to solve at large
9、 nSoft Computing Lab.12XiDian UNIVERSITY Polynomial Complexity: these are called tractable, and easy problems. Fast algorithms are known which provide the best solution. Exponential Complexity: these are called intractable, and hard problems. The fastest known algorithm which exactly solves it is us
10、ually not significantly faster than exhaustive search.(为所谓的Hard难问题,已有的快速算法与穷举算法相比较并没有明显的提高)Soft Computing Lab.13XiDian UNIVERSITY polynomialexponential 指数复杂度一般要比多项式复杂 要复杂F(n)Increasing nSoft Computing Lab.14XiDian UNIVERSITY 随机算法：爬山法随机算法：爬山法0. Initialise: Generate a random solution c; evaluate its f
11、itness, f(c). Call c the current solution.1. Mutate a copy of the current solution call the mutant m Evaluate fitness of m, f(m).2. If f(m) is no worse than f(c), then replace c with m, otherwise do nothing (effectively discarding m).3. If a termination condition has been reached, stop. Otherwise, g
12、o to 1.Note. No population (well, population of 1). This is a very simple version of an EA, although it has been around for much longer.Soft Computing Lab.15XiDian UNIVERSITY 12435, 867910Soft Computing Lab.16XiDian UNIVERSITY 易陷入局部最优易陷入局部最优Soft Computing Lab.17XiDian UNIVERSITY 1. Introduction of G
13、enetic Algorithms1.Foundations of Genetic Algorithms1.1 Introduction of Genetic Algorithms1.2 General Structure of Genetic Algorithms1.3 Major Advantages2.Example with Simple Genetic Algorithms 2.1 Representation2.2 Initial Population2.3 Evaluation2.4 Genetic Operators3.Encoding Issue3.1 Coding Spac
14、e and Solution Space3.2 SelectionSoft Computing Lab.18XiDian UNIVERSITY 1. Introduction of Genetic Algorithms4.Genetic Operators4.1 Conventional Operators4.2 Arithmetical Operators4.3 Directionbased Operators4.4 Stochastic Operators5.Adaptation of Genetic Algorithms5.1 Structure Adaptation5.2 Parame
15、ters Adaptation6.Hybrid Genetic Algorithms6.1 Adaptive Hybrid GA Approach 6.2 Parameter Control Approach of GA6.3 Parameter Control Approach using Fuzzy Logic Controller6.4 Design of aHGA using Conventional Heuristics and FLCSoft Computing Lab.19XiDian UNIVERSITY 1. Introduction of Genetic Algorithm
16、s1.Foundations of Genetic Algorithms1.1 Introduction of Genetic Algorithms1.2 General Structure of Genetic Algorithms1.3 Major Advantages2.Example with Simple Genetic Algorithms 3.Encoding Issue4.Genetic Operators5.Adaptation of Genetic Algorithms6.Hybrid Genetic AlgorithmsSoft Computing Lab.20XiDia
17、n UNIVERSITY 进化论进化论oSimon把复杂性定义为：当给定各部分的性质和他们的相互作用规律，却很难推演总体性质的情形，系统的复杂性不仅与相互作用各部分的数目有关，而且与其结构和功能上的差别有关o复杂系统具有进化性，而进化又使得系统变得更复杂，生物系统是复杂系统，进化的总趋势是产生越来越复杂的生物体。Soft Computing Lab.21XiDian UNIVERSITY Lamarck 进化论进化论o一切物种都是其他物种演变和进化而来的，而生物的演变和进化是一个缓慢和连续的过程。o环境的变化能够引起生物的变异，环境的变化迫使生物发生适应性的进化。o有神经系统的动物发生变异的原
18、因，除了环境变化和杂交外，更重要是通过用进废退和获得性状遗传。o生物进化的方向从简单到复杂，从低到高。o最原始的生物起源于自然发生。生物并不起源于共同祖先。o拉马克曾以长颈鹿的进化为例，说明他的用进废退观点。长颈鹿的祖先预部并不长，由于干旱等原因。在低处已找不到食物，迫使它伸长脖颈去吃高处的树叶，久而久之，它的颈部就变长了。一代又一代，遗传下去，它的脖子越来越长，终于进化为现在我们所见的长颈鹿。Soft Computing Lab.22XiDian UNIVERSITY Darwin 进化论进化论o包括两部分：遗传(基因)变异；自然选择o生物不是静止的，而是进化的。物种不断变异，旧物种消灭，新
19、物种产生。o生物的进化是连续和逐渐，不会发生突变。o生物之间存在一定的亲缘关系，他们具有共同的祖先。o自然选择是变异的最重要的途径。生物过渡繁殖，但是它们的生存空间和食物有限，从而面临生存斗争，包括:种内、种间以及生物与环境的斗争。自然选择是达尔文进化论的核心。Soft Computing Lab.23XiDian UNIVERSITY 孟德尔学说孟德尔学说 1、分离定律： 基因作为独特的独立单位而代代相传。细胞中有成对的基本遗传单位，在杂交的生殖细胞中，一个来自雄性亲本，一个来自雌性亲本. 2、独立分配定律：在一对染色体上的基因对中的等位基因能够独立遗传。 孟德尔的这两条遗传基本定律就是新遗
20、传学的起点，孟德尔也因此被后人称为现代遗传学的奠基人。Soft Computing Lab.24XiDian UNIVERSITY Soft Computing Lab.25XiDian UNIVERSITY 比较比较o达尔文抛弃拉马克的获得性遗传法则，认为性状并不重要，只有可遗传的变异才具有明显的进化价值，变异在群体内遗传，产生进化效应。不过达尔文过分强调物种形成的渐进方式。o如果进化是渐变的话，为什么在化石的范围里面，找不到证据；如果进化是突变的话，但是根据医学及科学的研究，突变产生的不是进化，而是退化,如突变产生癌，进化论证据缺乏。Soft Computing Lab.26XiDian
21、UNIVERSITY 新达尔文主义新达尔文主义o将达尔文进化论和魏斯曼选择和孟德尔摩根基因相结合，成为现被广泛接受的新达尔文主义。o新达尔文注意认为，只用种群上和物种内的少量统计过程就可以充分地解释大多数生命历史，这些过程就是繁殖、变异、竞争、选择。繁殖是所有生命的共同特性；变异保证了任何生命系统能在正熵世界中连续繁殖自己；对于限制在有限区域中的不断膨胀的种群来说，竞争和选择是不可避免的结论。Soft Computing Lab.27XiDian UNIVERSITY 生物学中的遗传概念n在生物细胞中，控制并决定生物遗传特性的物质是脱氧核糖核酸，简称DNA。染色体是其载体。nDNA是由四种碱基
22、按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。例如，改变DNA长链中的特定一段（称为基因），即可改变人体的身高。n细胞在分裂时，DNA通过复制而转移到新产生的细胞中，新的细胞就继承了上一代细胞的基因。Soft Computing Lab.28XiDian UNIVERSITY 生物学中的遗传概念o有性生殖生物在繁殖下一代时，两个同元染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉形成两个新的染色体。o在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生新的染色体。o这些新的染色体将决定新的个体（后代）
23、的新的性状。Soft Computing Lab.29XiDian UNIVERSITY 生物学中的遗传概念p在一个群体中，并不是所有的个体都能得到相同的繁殖机会，对生存环境适应度高的个体将获得更多的繁殖机会；对生存环境适应度较低的个体，其繁殖机会相对较少，即所谓自然选择。而生存下来的个体组成的群体，其品质不断得以改良，称为进化。In particular, any new mutation that appears in a child (e.g. longer neck(脖), longer legs, thicker skin, longer gestation(孕) period, b
24、igger brain) and which helps it in its efforts to survive long enough to have children, will become more and more widespread in future generations. Soft Computing Lab.30XiDian UNIVERSITY Evolution as Problem Solving Heres a problem: Design a material for the soles of boots that can help you walk up
25、a smooth vertical brick wall We havent solved this, but nature has: Geckos（设计一种可以帮助人类爬上光滑的墙壁的鞋底材料） 生物的进化是经过无数次有利的进化积累而成的，不同的环境保留了不同的变异后代！Soft Computing Lab.31XiDian UNIVERSITY Evolution as a Problem Solving Method 所有的生物经常面临一个共同的问题 How can I survive in this environment？自然界解决问题的方法就是：进化Evolution The ba
26、sic method of it is trial and error(反复试验). 1. Come up with a new solution by randomly changing an old one. Does it work better than previous solutions? If yes, keep it and throw away the old ones. Otherwise, discard it. 2. Go to 1. Soft Computing Lab.32XiDian UNIVERSITY Lesson1: Keep a population/co
27、llection of different things on the go. Lesson2: Select parents with a relatively weak bias towards the fittest. Its not really plain survival of the fittest, what works is the fitter you are, the more chance you have to reproduce, and it works best if even the least fit still have some chance. （无偏见
28、的选择父代，或适者生存)Lesson3: It can sometimes help to use recombination of two or more parents I.e. generate new candidate solutions by combining bits and pieces from different previous solutions. 通过重组将父代优良基因遗传给后代This is genetic algorithm什么是进化？什么是进化？Soft Computing Lab.33XiDian UNIVERSITY More like selective
29、 breeding than natural evolution Time Soft Computing Lab.34XiDian UNIVERSITY Initial populationSoft Computing Lab.35XiDian UNIVERSITY SelectSoft Computing Lab.36XiDian UNIVERSITY CrossoverSoft Computing Lab.37XiDian UNIVERSITY Another CrossoverSoft Computing Lab.38XiDian UNIVERSITY A mutationSoft Co
30、mputing Lab.39XiDian UNIVERSITY Another MutationSoft Computing Lab.40XiDian UNIVERSITY Old population + childrenSoft Computing Lab.41XiDian UNIVERSITY New Population: Generation 2Soft Computing Lab.42XiDian UNIVERSITY Generation 3Soft Computing Lab.43XiDian UNIVERSITY Generation 4, etc Soft Computin
31、g Lab.44XiDian UNIVERSITY Soft Computing Lab.45XiDian UNIVERSITY 遗传算法的基本思想o首先实现从性状到基因得映射，即编码工作，然后从代表问题可能潜在解集得一个种群开始进行进化求解。o初代种群（编码集合）产生后，按照优胜劣汰的原则，根据个体适应度大小挑选（选择）个体，进行复制、交叉、变异，产生出代表新的解集的群体，再对其进行挑选以及一系列遗传操作，如此往复，逐代演化产生出越来越好的近似解。Soft Computing Lab.46XiDian UNIVERSITY 选择：通过适应度的计算，淘汰不合理的个体。类似于 自然界的物竞天择.
32、复制：编码的拷贝，类似于细胞分裂中染色体的复 制。交叉：编码的交叉重组，类似于染色体的交叉重 组。变异：编码按小概率扰动产生的变化，类似于基因 的突变。o这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中得最优个体经过解码（从基因到性状的映射），可以作为问题近似最优解。Soft Computing Lab.47XiDian UNIVERSITY 遗传算法历史遗传算法历史遗传算法的发展历史： o1965年，Holland首次提出人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。o1967年，Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博
33、弈中的应用。o1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。 Soft Computing Lab.48XiDian UNIVERSITY 遗传算法历史遗传算法历史o1975年是遗传算法研究的历史上十分重要的一年。这一年，Holland出版了他的著名专著自然系统和人工系统的适应性该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schemata theory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。o同年，DeJong完成了他的重要论文遗传自适应系统的行为分析。他
34、在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把Holland的模式理论与他的计算使用结合起来。 Soft Computing Lab.49XiDian UNIVERSITY 遗传算法历史遗传算法历史o在一系列研究工作的基础上，上世纪80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。Soft Computing Lab.50XiDian UNIVERSITY 产生初产生初始种群始种群计算计算适应度适应度是否满足是否满足优化准则优化准则最佳个体最佳个体选择选择交叉交叉变异变异编码编码（性状到基因）（性状到基因）解码解码（基因到性状）（基因到性状）Y Y
35、N N父父 代代子子代代开始开始结束结束Soft Computing Lab.51XiDian UNIVERSITY 1.3 Major Advantages n共轭梯度法、拟牛顿法、单纯形方法n特点：n渐进收敛n经典的优化搜索算法往往是基于梯度的，梯度方向提高个体性能；n单点搜索n局部最优p Conventional Method (pointtopoint approach)initial single pointimprovement(problemspecific)termination condition?startstopConventional MethodYesNoSoft C
36、omputing Lab.52XiDian UNIVERSITY 遗传算法遗传算法improvement(problemindependent)termination condition?startstopGenetic Algorithminitial point.initial pointinitial pointInitial populationYesNoo遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算子。Soft Comp
37、uting Lab.53XiDian UNIVERSITY o遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法就比较方便。Soft Computing Lab.54XiDian UNIVERSITY o遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种隐含并行性。Soft Computing Lab.55XiDian UNIVE
38、RSITY o遗传算法使用概率搜索技术 。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。Random Search + Directed SearchSearch spaceFitnessf(x)local optimumglobal optimumlocal optimumlocal optimum0xx1x2x4x5x3Soft Computing Lab.56XiDian UNIVERSITY Soft Computing Lab.57XiDi
39、an UNIVERSITY 1.1 Introduction of Genetic Algorithms分支：oThe best known algorithms in this class include:nGenetic Algorithms (GA), developed by Dr. Holland.Holland, J.: Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975; MIT Press, Cambridge, MA, 1992.Gold
40、berg, D.: Genetic Algorithms in Search, Optimization and Machine Learning, AddisonWesley, Reading, MA, 1989.nEvolution Strategies (ES), developed by Dr. Rechenberg and Dr. Schwefel.Rechenberg, I.: Evolution strategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution, Fromma
41、nnHolzboog, 1973.Schwefel, H.: Evolution and Optimum Seeking, John Wiley & Sons, 1995.nEvolutionary Programming (EP), developed by Dr. Fogel.Fogel, L. A. Owens & M. Walsh: Artificial Intelligence through Simulated Evolution, John Wiley & Sons, 1966. nGenetic Programming (GP), developed by Dr. Koza.K
42、oza, J. R.: Genetic Programming, MIT Press, 1992.Koza, J. R.: Genetic Programming II, MIT Press, 1994.Soft Computing Lab.58XiDian UNIVERSITY 1.2 General Structure of Genetic AlgorithmsoIn general, a GA has five basic components, as summarized by Michalewicz.(用遗传算法求解问题需要解决以下五个问题)1.A genetic represent
43、ation of potential solutions to the problem.(编码)2.A way to create a population (an initial set of potential solutions).(群体初始化)3.An evaluation function rating solutions in terms of their fitness.(个体评价)4.Genetic operators that alter the genetic composition of offspring (selection, crossover, mutation,
44、 etc.).(遗传算子) 5.Parameter values that genetic algorithm uses (population size, probabilities of applying genetic operators, etc.).(参数选择).Soft Computing Lab.59XiDian UNIVERSITY 1.2 General Structure of Genetic AlgorithmsoGenetic Representation and Initialization:nThe genetic algorithm maintains a pop
45、ulation P(t) of chromosomes or individuals vk(t), k=1, 2, , popSize for generation t. (保持一个规模不变群体)nEach chromosome represents a potential solution to the problem at hand. oEvaluation:nEach chromosome is evaluated to give some measure of its fitness eval(vk).oGenetic Operators:nSome chromosomes under
46、go stochastic transformations by means of genetic operators to form new chromosomes, i.e., offspring. nThere are two kinds of transformation: oCrossover, which creates new chromosomes by combining parts from two chromosomes. oMutation, which creates new chromosomes by making changes in a single chro
47、mosome.nNew chromosomes, called offspring C(t), are then evaluated. oSelection:nA new population is formed by selecting the more fit chromosomes from the parent population and the offspring population. oBest solution:nAfter several generations, the algorithm converges to the best chromosome, which h
48、opefully represents an optimal or suboptimal solution to the problem.Soft Computing Lab.60XiDian UNIVERSITY 1.2 General Structure of Genetic AlgorithmsInitialsolutionsstart1100101010101110111000110110011100110001encodingchromosome110010101010111011101100101110101110101000110110010011001001crossoverm
49、utation110010111010111010100011001001solutions candidatesdecodingfitness computationevaluationroulette wheelselectiontermination condition?YNbest solutionstop newpopulationp The general structure of genetic algorithms Gen, M. & R. Cheng: Genetic Algorithms and Engineering Design, John Wiley, New Yor
50、k, 1997.offspringoffspringt 0 P(t)CC(t)CM(t)P(t) + C(t)Soft Computing Lab.61XiDian UNIVERSITY 1.2 General Structure of Genetic AlgorithmsoProcedure of Simple GAprocedure: Simple GAinput: GA parametersoutput: best solutionbegint 0;/ t: generation numberinitialize P(t) by encoding routine;/ P(t): popu
51、lation of chromosomesfitness eval(P) by decoding routine;while (not termination condition) docrossover P(t) to yield C(t); / C(t): offspringmutation P(t) to yield C(t);fitness eval(C) by decoding routine; select P(t+1) from P(t) and C(t);t t+1; end output best solution;end Soft Computing Lab.62XiDia
52、n UNIVERSITY 1. Introduction of Genetic Algorithms1.Foundations of Genetic Algorithms2.Example with Simple Genetic Algorithms 2.1 Representation2.2 Initial Population2.3 Evaluation2.4 Genetic Operators3.Encoding Issue4.Genetic Operators5.Adaptation of Genetic Algorithms6.Hybrid Genetic AlgorithmsSof
53、t Computing Lab.63XiDian UNIVERSITY 2. Example with Simple Genetic Algorithms oWe explain in detail about how a genetic algorithm actually works with a simple examples. (举例说明如何用遗传算法求解具体的优化问题)oThe numerical example of unconstrained optimization problem is given as follows:max f (x1, x2) = 21.5 + x1si
54、n(4p x1) + x2sin(20p x2)s. t. -3.0 x1 12.1 4.1 x2 5.8Soft Computing Lab.64XiDian UNIVERSITY 2. Example with Simple Genetic Algorithmsmax f (x1, x2) = 21.5 + x1sin(4p x1) + x2sin(20p x2)s. t. -3.0 x1 12.1 4.1 x2 5.8Soft Computing Lab.65XiDian UNIVERSITY 2.1 RepresentationoBinary String Representation
55、n The domain of xj is aj, bj and the required precision is five places after the decimal point.(精度小数点后面五位)n The precision requirement implies that the range of domain of each variable should be divided into at least (bj aj )105 size ranges.nThe required bits (denoted with mj) for a variable is calcu
56、lated as follows:nThe mapping from a binary string to a real number for variable xj is completed as follows:Soft Computing Lab.66XiDian UNIVERSITY 2.1 RepresentationoBinary String Encoding(二进制编码)nThe precision requirement implies that the range of domain of each variable should be divided into at le
57、ast (bj aj )105 size ranges.x1 : (12.1-(-3.0) 10,000 = 151,000 217 151,000 218, m1 = 18 bitsx2 : (5.8-4.1) 10,000 = 17,000 214 17,000 215, m2 = 15 bitsprecision requirement: m = m1 + m2 = 18 +15 = 33 bitsnThe required bits (denoted with mj) for a variable is calculated as follows:Soft Computing Lab.
58、67XiDian UNIVERSITY 2.1 RepresentationoProcedure of Binary String Encoding(表现型基因型)step 1: The domain of xj is aj, bj and the required precision is five places after the decimal point.step 2: The precision requirement implies that the range of domain of each variable should be divided into at least (
59、bj aj )105 size ranges.step 3: The required bits (denoted with mj) for a variable is calculated as follows:step 4: A chromosome v is randomly generated, which has the number of genes m, where m is sum of mj (j=1,2). m=m1+m2 input: domain of xj aj, bj, (j=1,2)(输入可行解(x1,x2)，表现型)output: chromosome v(输出
60、二进制码，基因型）Soft Computing Lab.68XiDian UNIVERSITY 2.1 RepresentationoBinary String Decoding (基因型表现型)nThe mapping from a binary string to a real number for variable xj is completed as follows:Soft Computing Lab.69XiDian UNIVERSITY input: substringjoutput: a real number xj 2.1 RepresentationoProcedure o
61、f Binary String Decodingstep 1: Convert a substring (a binary string) to a decimal number.step 2: The mapping for variable xj is completed as follows:Soft Computing Lab.70XiDian UNIVERSITY 2.2 Initial PopulationoInitial population is randomly generated as follows:v1 = 0000010101001010011011110111111
62、10 = x1 x2 = 2.687969 5.361653v2 = 001110101110011000000010101001000 = x1 x2 = 0.474101 4.170144v3 = 111000111000001000010101001000110 = x1 x2 = 10.419457 4.661461v4 = 100110110100101101000000010111001 = x1 x2 = 6.159951 4.109598v5 = 000010111101100010001110001101000 = x1 x2 = 2.301286 4.477282v6 =
63、111110101011011000000010110011001 = x1 x2 = 11.788084 4.174346v7 = 110100010011111000100110011101101 = x1 x2 = 9.342067 5.121702v8 = 001011010100001100010110011001100 = x1 x2 = 0.330256 4.694977v9 = 111110001011101100011101000111101 = x1 x2 = 11.671267 4.873501v10 = 111101001110101010000010101101010
64、 = x1 x2 = 11.446273 4.171908Soft Computing Lab.71XiDian UNIVERSITY 2.3 EvaluationoThe process of evaluating the fitness of a chromosome consists of the following three steps:input: chromosome vk, k=1, 2, ., popSizeoutput: the fitness eval(vk)step 1: Convert the chromosomes genotype to its phenotype
65、, i.e., convert binary string into relative real values xk =(xk1, xk2), k = 1,2, , popSize.(基因型到表现型)step 2: Evaluate the objective function f (xk), k = 1,2, , popSize.step 3: Convert the value of objective function into fitness. For the maximization problem, the fitness is simply equal to the value
66、of objective function:eval(vk) = f (xk), k = 1,2, , popSize.f (x1, x2) = 21.5 + x1sin(4 x1) + x2sin(20 x2)eval(v1) = f (-2.687969, 5.361653) =19.805119Example: (x1=2.687969, x2= 5.361653)Soft Computing Lab.72XiDian UNIVERSITY oAn evaluation function plays the role of the environment, and it rates ch
67、romosomes in terms of their fitness.(适应度函数起到环境的作用)oThe fitness function values of above chromosomes are as follows:oIt is clear that chromosome v4 is the strongest one and that chromosome v3 is the weakest one.2.3 Evaluationeval(v1) = f (2.687969, 5.361653) =19.805119 eval(v2) = f (0.474101, 4.17014
68、4) = 17.370896eval(v3) = f (10.419457, 4.661461) = 9.590546eval(v4) = f (6.159951, 4.109598) = 29.406122eval(v5) = f (2.301286, 4.477282) = 15.686091eval(v6) = f (11.788084, 4.174346) = 11.900541eval(v7) = f (9.342067, 5.121702) = 17.958717eval(v8) = f (0.330256, 4.694977) = 19.763190eval(v9) = f (1
69、1.671267, 4.873501) = 26.401669eval(v10) = f (11.446273, 4.171908) = 10.252480Soft Computing Lab.73XiDian UNIVERSITY 2.4 Genetic OperatorsoSelection(无偏见，平等)nIn most practices, a roulette wheel approach is adopted as the selection procedure, which is one of the fitnessproportional selection and can s
70、elect a new population with respect to the probability distribution based on fitness values. (通过适应度来设计个体被选择的概率）nThe roulette wheel can be constructed with the following steps:step 1: Calculate the total fitness for the populationstep 2: Calculate selection probability pk for each chromosome vkstep 3
71、: Calculate cumulative probability qk for each chromosome vkstep 4: Generate a random number r from the range 0, 1.step 5: If r q1, then select the first chromosome v1; otherwise, select the kth chromosome vk (2 k popSize) such that qk1 r qk .input: population P(t1), C(t1)output: population P(t), C(
72、t)Soft Computing Lab.74XiDian UNIVERSITY 2.4 Genetic OperatorsoIllustration of Selection:step 1: Calculate the total fitness F for the population.step 2: Calculate selection probability pk for each chromosome vk.step 3: Calculate cumulative probability qk for each chromosome vk.step 4: Generate a ra
73、ndom number r from the range 0,1.135372.178)(101=kkevalFv0.197577 0.032685, 0.343242, 0.177618, 0.583392, 0.350871, 0.881893, 0.766503, 0.322062, 0.301431, input: population P(t1), C(t1)output: population P(t), C(t)Soft Computing Lab.75XiDian UNIVERSITY 1100.197577 0.032685, 0.343242, 0.177618, 0.58
74、3392, 0.350871, 0.881893, 0.766503, 0.322062, 0.301431, Soft Computing Lab.76XiDian UNIVERSITY 2.4 Genetic OperatorsoIllustration of Selection:step 5: q3 r1 = 0.301432 q4, it means that the chromosome v4 is selected for new population; q30 popij=1; poppopsizelen=aj+r*(bjaj); else popij=0; end end en
75、d end endSoft Computing Lab.105XiDian UNIVERSITY 适应度函数适应度函数(Fitness Function) o适应度函数(Fitness Function)的选取直接影响到遗传算法的收敛速度以及能否找到最优解，因为在进化搜索中基木不利用外部信息，仅以适应度函数为依据，利用种群每个个体的适应度来指导搜索.o在实际问题中，适应度函数与问题的目标函数是不完全一致的，如有的问题的目标是要求的最小值(费用问题)，而有的问题的目标是要求得最大值(利润函数)。Soft Computing Lab.106XiDian UNIVERSITY 遗传算子遗传算子o当很
76、难事先获得问题求解步骤时，搜索成为有效的求解方法。代表搜索方法：局部搜索和随机搜索。o经典算法的局部搜索能力较强，遗传算法是一种结合了局部搜索和随机两种能力的通用搜索方法，对深度搜索和广度搜索进行平衡，由选择机制来深度搜索积累的信息，由遗传算子来广度搜索解空间中新的区域！ Exploration: Discovering promising areas in the search space, i.e. gaining information on the problem(全局),crossover(算子)Exploitation: Optimising within a promising
77、area, i.e. using information(局部),mutation(算子)Soft Computing Lab.107XiDian UNIVERSITY 遗传算子遗传算子o从本质上讲，遗传算子执行的是随机搜索，不能保证产生改进的后代，关于解释遗传算法是如何搜索分布信息来产生优秀个体存在两个假设（1）积木假设（2）受控收敛偏差假设o积木假设是由Holland提出，并由Goldberg改进，根据假设杂交算子重组两个父代的特性来产生子代。由于个体的适应值通常依赖于简单性质的复杂模式，因此算子能否把对父代适应值有所贡献的这些模式传给后代就显得非常重要。异位显性的概念是指编码中的基因间的
78、相互作用，也就是说他是度量一个基因对适应值贡献依赖于其他基因程度的大小，显然高异位显性就无法形成积木块。o受控收敛偏差假设是由Schaffer提出。该假设认为应利用种群收敛的程度来指导搜索。搜索应根据种群的分布情况进行搜索。Soft Computing Lab.108XiDian UNIVERSITY 3.2 SelectionoThe principle behind genetic algorithms is essentially Darwinian natural selection.(选择的基础是达尔文的适者生存理论) oSelection provides the driving
79、force in a genetic algorithm and the selection pressure is a critical in it.(合适的选择压力很重要)nToo much, the search will terminate prematurely.nToo little, progress will be slower than necessary.nLow selection pressure is indicated at the start to the GA search in favor of a wide exploration of the search
80、 space. (初始阶段压力希望小)nHigh selection pressure is recommended at the end in order to exploit the most promising regions of the search space. (最终压力希望大)oThe selection directs GA search towards promising regions in the search space. (选择的作用使得群体最优解所在区域移动)oDuring last few years, many selection methods have b
81、een proposed, examined, and compared.o遗传算法本质上是一种随机搜索，选择算子则将遗传搜索的方向引向最优解所在区域！Soft Computing Lab.109XiDian UNIVERSITY 3.2 SelectionoSampling Space（选择空间)nIn Hollands original GA, parents are replaced by their offspring soon after they give birth(生成后即替换).oThis is called as generational replacement.(世代替换
82、) nBecause genetic operations are blind in nature, offspring may be worse than their parents. (遗传算子属于盲搜索或随机搜索，存在退化,所以上述算子不合适)oTo overcome this problem, several replacement strategies have been examined.（Holland认为当一个后代生成后可从父代个体中随机选取提个个体来替换）nHolland suggested that each offspring replaces a randomly ch
83、osen chromosome of the current population as it was born.(随机替换)nDe Jong proposed a crowding strategy(拥挤策略). oIn the crowding model, when an offspring was born, one parent was selected to die. The dying parent was chosen as that parent was most closely resembled the new offspring using a simple bitby
84、bit similarity count to measure resemblance.(拥挤原则，当一个新个体产生，死亡的个体应该是和他最接近的父代个体)Soft Computing Lab.110XiDian UNIVERSITY Selection( crowding strategy)子代个体子代个体父代个体父代个体新生成的子代个体新生成的子代个体个体之间的距离：个体之间的距离：码空间的距离码空间的距离 解空间的距离解空间的距离Soft Computing Lab.111XiDian UNIVERSITY 3.2 SelectionoSampling Space(选择空间)nIn Ho
85、llands works,(定义) selection refers to choosing parents for recombination and new population was formed by replacing parents with their offspring. They called it as reproductive plan.（再生计划)nSince Grefenstette and Bakers work, selection is used to form next generation usually with a probabilistic mech
86、anism.(随机机制) nMichalewicz gave a detail description on simple genetic algorithms where offspring replaced their parents soon after they were born at each generation and next generation was formed by roulette wheel selection (Michalewicz, 1994). (轮盘选择)Soft Computing Lab.112XiDian UNIVERSITY roulette
87、wheel selection染色体的 适应度和所占的比例用转轮方法进行选择Soft Computing Lab.113XiDian UNIVERSITY Roulette wheel selection染色体编号 1 2 3 4 5 6 7 8 9 10适应度 8 217 7 212117 3 7被选概率0.10.020.220.090.020.160.140.090.030.09适应度累计 8 10 27 34 36 48 59 66 6976随机数23497613 1 2757所选染色体号码 3 710 3 1 3 7被选的染色体个数Soft Computing Lab.114XiDia
88、n UNIVERSITY 3.2 SelectionoStochastic Sampling(随机采样)nThe selection phase determines the actual number of copies that each chromosome will receive based on its survival probability.(选择幅度决定了每个个体被复制的次数)nThe selection phase is consist of two parts: oDetermine the chromosomes expected value;(期望值)oConvert
89、 the expected values to the number of offspring.(实际值)nA chromosomes expected value is a real number indicating the average number of offspring that a chromosome should receive. The sampling procedure is used to convert the real expected value to the number of offspring.（经过选择将期望转化为实际值即后代个数）oRoulette
90、wheel selectionoStochastic universal sampling(一次随机采样)Soft Computing Lab.115XiDian UNIVERSITY Roulette wheel selection and Stochastic universal sampling（普遍采（普遍采样)Roulette wheel selectionuniversal sampling区别在于：后者采用均匀分布的且个数等于种群规模的旋转指针，这种方法的基本原则是保证每个染色体在下一代中复制的次数与期望值相差不大。Soft Computing Lab.116XiDian UNI
91、VERSITY 3.2 Selectiono Deterministic Sampling(确定性选择) 所谓确定性选择就是从父代和子代个体中选择最优的个体。nDeterministic procedures which select the best chromosomes from parents and offspring.o(+)selection(个父代， 个子代,从+选择最好的)o(, )selection(个父代， 个子代,从选择最好的)oTruncation selection(截断选择)oBlock selection(块选择)oElitist selection(贪婪选择，
92、在比例选择最优个体没有被选择，进行强制选择)oThe generational replacement(代替换)oSteadystate reproduction(稳态再生，n个最差的父代个体被子代替换)Soft Computing Lab.117XiDian UNIVERSITY 3.2 SelectionSoft Computing Lab.118XiDian UNIVERSITY 3.2 SelectionoMixed Sampling（混合选择同时具有随机性和确定性）nContains both random and deterministic features simultaneou
93、sly.oTournament selection(竞赛选择)oBinary tournament selection（规模为2的竞赛选择）oStochastic tournament selection（采用普通的方法计算选择概率，然后采用赌盘选择个体，适应度高的进入群体，否则被抛弃）oRemainder stochastic sampling(随机保留采样，期望选择次数的整数部分确定，小数部分随机！）Soft Computing Lab.119XiDian UNIVERSITY Tournament Selection Tournament selection: tournament si
94、ze = t Repeat t timeschoose a random individual from the pop and remember its fitness Return the best of these t individuals (BTR)This is very tunable, avoids the problems of superfit or superpoorsolutions, and is very simple to implement如何选择T,调节选择压力Soft Computing Lab.120XiDian UNIVERSITY 3.2 Select
95、ionoRegular Sampling Space(常规的选择空间)nContaining all offspring but just part of parents(保存所有的子代个体)Soft Computing Lab.121XiDian UNIVERSITY 3.2 SelectionoEnlarged sampling space(变大的采样空间)ncontaining all parents and offspring(所有的子代和父代均保留)Soft Computing Lab.122XiDian UNIVERSITY 比例选择存在问题比例选择存在问题o在算法的初期个别超级染
96、色体具有绝对的优势控制整个选择过程，竞争过于强烈；而在算法的晚期（大部分个体已经收敛）个体之间的适应度差别不大，竞争太弱，呈现随机搜索行为。比例变换和排序机制可以解决这些问题。Soft Computing Lab.123XiDian UNIVERSITY Selection Issues Very low pressure selection (e.g. random)No evolutionary progress at all.Very high pressure (e.g. always select best)You will end up here: A modest level o
97、f pressure.（合适的压力（合适的压力)You may well find yourself here or here:Soft Computing Lab.124XiDian UNIVERSITY Some Selection Methods Suppose there are P individuals with fitnesses f1, f2, , fPThe probability of selecting individual i is simply:This is equivalent to spinninga roulette wheel with sectorspro
98、portional to fitnessSoft Computing Lab.125XiDian UNIVERSITY 适适应应度度调调整整 Suppose we are trying to maximise something, and we have a population of 5 fitnesses: (对于最大化问题）o100, 0.4, 0.3, 0.2, 0.1 the best is 100 times more likely to be selected than all the rest put together! oBut a slight modification o
99、f the fitness calculation might give us: 200, 100.4, 100.3, 100.2, 100.1 a much more reasonable situation.Soft Computing Lab.126XiDian UNIVERSITY 3.2 SelectionoSelection ProbabilitynFitness scaling has a twofold intention:(适应度变换有两个目的)oTo maintain a reasonable differential between relative fitness ra
100、tings of chromosomes.(维持个体之间的合理差距，加速竞争)oTo prevent a toorapid takeover by some supper chromosomes in order to meet the requirement to limit competition early on, but to stimulate it later.(避免个体之间的差距过大，限制竞争)nSuppose that the raw(原始) fitness fk (e.g. objective function value) for the kth chromosomes,
101、the scaled fitness fk is:nFunction g() may take different form to yield different scaling methods.fk = g( fk )Soft Computing Lab.127XiDian UNIVERSITY 3.2 Selectionn Linear scalingn Power low scalingn Normalizing scalingn Boltzmann scalingp Scaling MechanismsSoft Computing Lab.128XiDian UNIVERSITY 排序
102、法与共享方法排序法与共享方法 依据个体的适应度对个体进行排序根据每个个体的等级给定每个个体一个复制规模。The selection probabilities areproportional to rank.Soft Computing Lab.129XiDian UNIVERSITY Rank with low bias Here, selective fitnesses are based（小的变大，大的变小)on rank0.5 Soft Computing Lab.130XiDian UNIVERSITY Rank with high bias Here, selective fitn
103、esses are based （大的更大，小的更小)on rank2 Soft Computing Lab.131XiDian UNIVERSITY 排序法与共享方法排序法与共享方法o排序法忽略了实际目标函数值，与之相对应是采用了染色体的排序来确定其生存的概率。o共享函数法。根据个体某个距离内与其他个体的临近程度来确定该个体的适应度应改变多少。在拥挤的峰周围的个体的复制概率受到抑制，利于其他个体产生后代。生存概率减少生存概率减少生存概率增大生存概率增大Soft Computing Lab.132XiDian UNIVERSITY The pop isspatially organised(e
104、ach individual has co-ordinates)LM is a combinedselection/replacement strategy.个体二个体二维维排列排列选择选择Soft Computing Lab.133XiDian UNIVERSITY 个体二个体二维维排列排列1. Choose random cell2. Random walk length w from that cell.Parameter: w, length of random walk.Soft Computing Lab.134XiDian UNIVERSITY 个体二个体二维维排列排列1. Ch
105、oose random cell2. Random walk length w from that cell.Parameter: w, length of random walk.3. Selected: the fittest encountered on the walkSoft Computing Lab.135XiDian UNIVERSITY Crossover and MutationoGenetic operators are used to alter the genetic composition of chromosomes during representation.(
106、通过改变染色体的基因序列，产生新的个体实现遗传算子) oThere are two common genetic operators:nCrossover oOperating on two chromosomes at a time and generating offspring by combining both chromosomes features.(遗传)nMutationoProducing spontaneous(自然) random changes in various chromosomes.Soft Computing Lab.136XiDian UNIVERSITY
107、4. Genetic OperatorsoGenetic Operators can be roughly classified into four classes:nConventional operators(经典的算子经典的算子)oSimple crossover (onecut point, twocut point, multicut point, uniform)oRandom crossover (flat crossover, blend crossover)oRandom mutation (boundary mutation, plain mutation)nArithme
108、tical operators(算术算子算术算子)oArithmetical crossover (convex, affine, linear, average, intermediate)oExtended intermediate crossoveroDynamic mutation (nonuniform mutation)nDirection-based operators(PSO)oDirectionbased crossoveroDirectional mutationnStochastic operators(随机算子随机算子)oUnimodal normal distribu
109、tion crossoveroGaussian mutationSoft Computing Lab.137XiDian UNIVERSITY 4.1 Conventional Operatorsp Onecut Point Crossover:crossing point at kth positionparentsoffspring二进制制或离散编码的交叉算子二进制制或离散编码的交叉算子oTSP交叉操作算子 p 1=2 4 3 |1 8 6 7| 5 9, p 2=2 1 3 |4 5 6 7| 8 9n然后移走p2中已在p1中的城市4、5、6和7后，得到n23189n该序列顺次放在o1中
110、：no1=（2 3 1 | 4 5 6 7 | 8 9）n类似地，可以得到另一个后代：no2=(2 3 4 |1 8 6 7| 5 9)Soft Computing Lab.138XiDian UNIVERSITY Random Mutationp Random Mutation (Boundary Mutation):mutating point at kth positionparentoffspring除了他以外其他除了他以外其他码保持不保持不变Soft Computing Lab.139XiDian UNIVERSITY Insert Mutation for permutations
111、oPick two allele values at random(选择两个等位基因）oMove the second to follow the first, shifting the rest along to accommodate（将第二个插入到第一个之后）oNote that this preserves most of the order and the adjacency information（优点保护大部分基因位信息的临近关系)Soft Computing Lab.140XiDian UNIVERSITY Swap mutation for permutations(交交换）
112、 ）Pick two alleles at random and swap their positionsPreserves most of adjacency information (4 links broken), disrupts order moreSoft Computing Lab.141XiDian UNIVERSITY 4.2 Arithmetical OperatorsnCrossoveroSuppose that these are two parents x1 and x2, the offspring can be obtained by 1x1+ 2x2 with
113、different multipliers 1 and 2 . Convex Crossover Affine Crossover Linear Crossover If 1+2=1, 1 0, 2 0 If 1+2=1 If 1+2 2, 1 0, 2 0x1=1x1+ 2x2x2=1x2+ 2x1x1x2linear hull = R2solution spacex1x2convex hullaffine hullFig 1.2 Illustration showing convex, affine, and linear hull仿射交叉仿射交叉Soft Computing Lab.14
114、2XiDian UNIVERSITY 4.2 Arithmetical Operators(实数变异实数变异)nNonuniform Mutation (Dynamic Mutation)oFor a given parent x, if the element xk of it is selected for mutation, the resulting offspring is x = x1 xk xn, where xk is randomly selected from two possible choice:t为代数owhere xkU and xkL are the upper
115、and lower bounds for xk .oThe function (t, y) returns a value in the range 0, y such that the value of (t, y) approaches to 0 as t increases (t is the generation number):where r is a random number from 0, 1, T is the maximal generation number, and b is a parameter determining the degree of nonunifor
116、mity.orxlxuxkb来决定一致性的大小，nonuniformityT固定，b越大值越小b固定，t越大值越小Soft Computing Lab.143XiDian UNIVERSITY 4.3 Direction-based Operators(有方向的遗传算子有方向的遗传算子)nThis operation use the values of objective function in determining the direction of genetic search:(通过目标函数值来决定搜索的方向)nDirectionbased crossoveroGenerate a si
117、ngle offspring x from two parents x1 and x2 according to the following rules: where 0 r 1.（x2不差于x1)nDirectional mutationoThe offspring after mutation would be:ininiixxxxfxxxxf-+=),(),(11LLLLdx = x + r d wherer = a random nonnegative real numberx = r (x2 - x1)+ x2Soft Computing Lab.144XiDian UNIVERSI
118、TY 多父辈交叉算子多父辈交叉算子o多父辈交叉有利于提高遗传算法的性能的随着在交叉操作中多父辈的引入，降低了超级个体将自身复制到子代中的可能性，这就意味着带来了更为多样的解空间搜索结果，从而减少了遗传算法早熟的危险.Soft Computing Lab.145XiDian UNIVERSITY 4.4 Stochastic Operators(随机算子随机算子)oUnimodal Normal Distribution Crossover (UNDX,单峰正态交叉) nThe UNDX generates two children from a region of normal distrib
119、ution defined by three parents. (通过三个父代个体来产生两个后代)nIn one dimension defined by two parents p1 and p2, the standard deviation of the normal distribution is proportional to the distance between parents p1 and p2. (方向取决于p1 and p2，标准差正比于p1 and p2之间的距离）nIn the other dimension orthogonal to the first one,
120、the standard deviation of the normal distribution is proportional to the distance of the third parent p3 from the line. （与第一个方向正交，标准方差取决于p3到第一个方向的距离nThe distance is also divided by in order to reduce the influence of the third parent.p3p1p2d2d1Axis Connecting two ParentsNormal Distribution1s2sSoft C
121、omputing Lab.146XiDian UNIVERSITY 4.4 Stochastic OperatorsoUnimodal Normal Distribution Crossover (UNDX)n Assume P1 & P2 : the parents vectors C1 & C2 : the child vectors n: the number of variables d1: the distance between parents p1 and p2 d2: the distance of parents p3 from the axis connecting par
122、ents p1 and p2 z1: a random number with normal distribution N(0, 2 ) zk : a random number with the normal distribution N(0, 2 ), k=1,2, n & : certain constants1kn The children are generated as follows:,.,2 , 1,|)(,., 3, 2, 0(), 0(2/ )(12121221122112121122111i jnjieePPPPenddnkNzNzPPmezezmCezezmCjikkn
123、kkknkkk=-=+=-=+=bsa sss)Soft Computing Lab.147XiDian UNIVERSITY 4.4 Stochastic OperatorsoGaussian Mutation (高斯变异，进化策略)An chromosome in evolution strategies consists of two components (x, ), where the first vector x represents a point in the search space, the second vector represents standard deviati
124、on. An offspring (x, ) is generated as follows: ), 0(), 0(xx+= NeNwhere N(0, D ) is a vector of independent random Gaussian numbers with a mean of zero and standard deviations .Soft Computing Lab.148XiDian UNIVERSITY 1. Introduction of Genetic Algorithms1.Foundations of Genetic Algorithms2.Example w
125、ith Simple Genetic Algorithms 3.Encoding Issue4.Genetic Operators5.Adaptation of Genetic Algorithms5.1 Structure Adaptation5.2 Parameters Adaptation6.Hybrid Genetic AlgorithmsSoft Computing Lab.149XiDian UNIVERSITY 5. Adaptation of Genetic AlgorithmoSince the genetic algorithms are inspired from the
126、 idea of evolution, it is natural to expect that the adaptation is used not only for finding solutions to a given problem, but also for tuning the genetic algorithms to the particular problem.(人们很希望不仅用于寻找某给定问题的解，而且还可让遗传算法根据特定问题进行变化)oThere are two kinds of adaptation of GA.(遗传算法对问题的适应性)nAdaptation to
127、 Problems(修改遗传算法的组成单元修改遗传算法的组成单元:编码，编码，交叉，变异和选择算子，构造合适的算法用于问题求解交叉，变异和选择算子，构造合适的算法用于问题求解nAdaptation to Evolutionary processes(进化过程的适应性进化过程的适应性)oSuggests a way to tune the parameters of the changing configurations of genetic algorithms while solving the problem. 通过调整决定算法结构的一些参数使得算法适用问题求解（交叉和编译概率)oDivi
128、ded into five classes:nAdaptive parameter settings(参数)nAdaptive genetic operators(遗传算子)nAdaptive selection(自适应选择)nAdaptive representation(解的自适应描述)nAdaptive fitness function(适应度函数的自适应性)Soft Computing Lab.150XiDian UNIVERSITY 5.1 Structure AdaptationoThis approach requires a modification of an origina
129、l problem into an appropriated form suitable for the genetic algorithms.(问题调整)oThis approach includes a mapping between potential solutions and binary representation, taking care of decodes or repair procedures, etc.(解空间到码空间的影射,或解的修补)oFor complex problems, such an approach usually fails to provide s
130、uccessful applications.（该方法具有一定的局限性） Fig. 1.3 Adapting a problem to the genetic algorithms. adaptationProblemAdapted problemGenetic AlgorithmsSoft Computing Lab.151XiDian UNIVERSITY 5.1 Structure AdaptationoVarious nonstandard implementations of the GAs have been created for particular problems.（针对特
131、定的问题可构造一些非标准的遗传算法）oThis approach leaves the problem unchanged and adapts the genetic algorithms by modifying a chromosome representation of a potential solution and applying appropriate genetic operators.(问题不变,算法变)oIt is not a good choice to use the whole original solution of a given problem as the
132、chromosome because many real problems are too complex to have a suitable implementation of genetic algorithms with the whole solution representation. (将整个解空间，很难找到一个合适的算法) Fig. 1.4 Adapting the genetic algorithms to a problem. adaptationProblemAdapted problemGenetic AlgorithmsSoft Computing Lab.152Xi
133、Dian UNIVERSITY 5.1 Structure AdaptationoThe approach is to adapt both GAs and the given problem. oGAs are used to evolve an appropriate permutation and/or combination of some items under consideration, and a heuristic method is subsequently used to construct a solution according to the permutation.
134、(启发式算法)oThe approach has been successfully applied in the area of industrial engineering and has recently become the main approach for the practical use of the GAs. Fig. 1.5 Adapting both the genetic algorithms and the problem. ProblemAdapted GAsGenetic AlgorithmsAdapted problemSoft Computing Lab.15
135、3XiDian UNIVERSITY 5.2 Parameters AdaptationoThe behaviors of GA are characterized by the balance between exploitation(广) and exploration(深) in the search space, which is strongly affected by the parameters of GA. (setandtest 试探法)nUsually, fixed parameters are used in most applications of GA and are
136、 determined with a setandtest approach.nSince GA is an intrinsically dynamic and adaptive process, the use of constant parameters is thus in contrast to the general evolutionary spirit.(遗传算法本质是动态，并行的,固定的参数和这种精神相违背)实现方法：（1）构造一种规则（2）获取当前搜索的状态信息（3）采用自适应机制。Soft Computing Lab.154XiDian UNIVERSITY 5.2 Par
137、ameters Adaptation（调解参数）（调解参数）oTherefore, it is a natural idea to try to modify the values of strategy parameters during the run of the genetic algorithm by using the following three ways.（在迭代过程中自适应修改参数)nDeterministic: using some deterministic rule（确定，线性）nAdaptive: taking feedback information from t
138、he current state of search（有适应能力的，即根据当前的状态修改参数）nSelfadaptive: employing some selfadaptive mechanism（自适应）Soft Computing Lab.155XiDian UNIVERSITY 5.2 Parameters AdaptationoThe adaptation takes place if the value of a strategy parameter by some is altered by some deterministic rule.oTimevarying approac
139、h is used, which is measured by the number of generations.(时变方法，根据代数对参数修改)oFor example, the mutation ratio is decreased gradually along with the elapse of generation by using the following equation.nwhere t is the current generation number and maxGen is the maximum generation. nHence, mutation ratio
140、 will decrease from 0.5 to 0.2 as the number of generations increase to maxGen. t pM = 0.5 0.3maxGenSoft Computing Lab.156XiDian UNIVERSITY 5.2 Parameters AdaptationoAdaptive Adaptation(有适应能力的适应性有适应能力的适应性)nThe adaptation takes place if there is some form of feedback from the evolutionary process, wh
141、ich is used to determine the direction and/or magnitude of the change to the strategy parameter.(根据反馈，决定参数改变的方向和幅度)nEarly approach include Rechenbergs 1/5 success rule in evolution strategies, which was used to vary the step size of mutation. 该规则认为，所有变异中成功的变异比例大于1/5，则步长增加，否则减小变异步长。nDaviss adaptive o
142、perator fitness utilizes feedback on the success of a larger number of reproduction operators to adjust the ratio being used. 利用成功复制的比较大的算子数目调整算法参数比率nJulstroms adaptive mechanism regulates the ratio between crossovers and mutations based on their performance.（根据交叉和变异的性能调整参数比率）nAn extensive study of
143、these kinds of learningrule mechanisms has been done by Tuson and Ross.Soft Computing Lab.157XiDian UNIVERSITY 5.2 Parameters AdaptationoSelf-adaptive AdaptationnThe adaptation enables strategy parameters to evolve along with the evolutionary process. The parameters are encoded onto the chromosomes
144、of the chromosomes and undergo mutation and recombination. （允许参数在进化过程中自动进化，对参数也进行编码，交叉和变异）o编码的参数并不直接影响个体的适应值，但优秀的参数将会产生优秀的个体，这些个体在进化过程中产生更多的后代，由此传播较好的参数。进行自适应调整的参数可以是那些控制遗传算法操作、控制复制和其他操作、或者进行替代搜索过程的概率。nSchwefel developed the method to selfadapt the mutation step size and the mutation rotation angles
145、 in evolution strategiesnHinterding used a multichromosome to implement the selfadaptation in the cutting stock problem with contiguity.owhere selfadaptation is used to adapt the probability of using one of the two available mutation operators, and the strength of the group mutation operator.Soft Co
146、mputing Lab.158XiDian UNIVERSITY 模式理论模式理论 指导遗传算法的基本理论，是指导遗传算法的基本理论，是J.H.Holland教授创立的教授创立的模式理论模式理论。该理论揭示。该理论揭示 了遗传算法的基本机理。了遗传算法的基本机理。 3.1 3.1 基本概念基本概念基本概念基本概念 3.1.1 3.1.1 问题的引出问题的引出问题的引出问题的引出 例：例： 求求 max f(x)=x2 x 0,31Soft Computing Lab.159XiDian UNIVERSITY 分析分析 当编码的最左边字符为当编码的最左边字符为“1”时，其个体适应度较大，如时，其
147、个体适应度较大，如2号个体和号个体和4号个体，号个体， 我们将其记为我们将其记为 “ 1* ”； 其中其中2号个体适应度最大，其编码的左边两位都是号个体适应度最大，其编码的左边两位都是1，我们记为，我们记为 “ 11* ”； 当编码的最左边字符为当编码的最左边字符为“0”时，其个体适应度较小，如时，其个体适应度较小，如1号和号和3号个体，号个体， 我们记为我们记为 “ 0* ”。 结论结论 从这个例子可以看比，我们在分析编码字符串时，常常只关心某一位或某几位字符，从这个例子可以看比，我们在分析编码字符串时，常常只关心某一位或某几位字符，而对其他字符不关心。换句话讲我们只关心字符的某些特定形式，
148、如而对其他字符不关心。换句话讲我们只关心字符的某些特定形式，如 1*，11*，0*。这种特定的形式就叫这种特定的形式就叫模式模式。 3.1.2 3.1.2 模式、模式阶及模式定义长度模式、模式阶及模式定义长度模式、模式阶及模式定义长度模式、模式阶及模式定义长度 模式集模式集模式集模式集(Schema)(Schema)指编码的字符串中具有类似特征的子集。指编码的字符串中具有类似特征的子集。 以五位二进制字符串为例，以五位二进制字符串为例， 模式模式 * *111*111* 可代表可代表4个个体：个个体： 01110，01111，11110，11111； 模式模式 * *00000000 则代表则
149、代表2个个体：个个体：10000，00000 。Soft Computing Lab.160XiDian UNIVERSITY 个体个体是由二值字符集是由二值字符集 V=0, 1 中的元素所组成的一个编码串中的元素所组成的一个编码串; 而而模式模式却是由三值字符集却是由三值字符集 V=0, 1,* 中的元素所组成的一个编码串，其中中的元素所组成的一个编码串，其中 “ * * ” 表示通配符，它既可被当作表示通配符，它既可被当作 “1” 也可被当作也可被当作 “0”。模式阶模式阶模式阶模式阶 (Schema Order)(Schema Order) 指模式中已有明确含意指模式中已有明确含意(二进
150、制字符时指二进制字符时指0或或1)的字符个数，的字符个数， 记做记做 o(s)，式中式中 s 代表模式。代表模式。 例如，模式例如，模式 ( 011*1* ) 含有含有4个明确含意的字符，其阶次是个明确含意的字符，其阶次是4， 记作记作 o( 011*1* ) =4; 模式模式 ( 0* ) 的阶次是的阶次是1，记作，记作 o( 0* ) =1。 阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然；阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然；阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然；阶次越低，模式的概括性越强，所代表的编码串个体数也越
151、多，反之亦然； 当模式阶次为零时，它没有明确含义的字符，其概括性最强。当模式阶次为零时，它没有明确含义的字符，其概括性最强。模式的定义长度模式的定义长度模式的定义长度模式的定义长度( Schema Defining Length)( Schema Defining Length) 指模式中第一个和最后一个具有明确含意的字符之间的距离，记作指模式中第一个和最后一个具有明确含意的字符之间的距离，记作 (s)。 例如，模式例如，模式( 011*l* ) 的的第一个字符为第一个字符为0，最后一个字符为最后一个字符为l，中间有中间有3个字个字 符，其定义长度为符，其定义长度为4，记作，记作 ( 011*
152、l* ) = 4 ； 模式模式 ( 0* ) 的长度是的长度是0，记作，记作 ( 0* ) = 0 ；Soft Computing Lab.161XiDian UNIVERSITY 一般地，有式子一般地，有式子 (s)b a 式中式中 b模式模式s 中最后一个明确字符的位置中最后一个明确字符的位置; a模式模式s 中最前一个明确字符的位置。中最前一个明确字符的位置。 模式的长度代表该模式在今后遗传操作模式的长度代表该模式在今后遗传操作模式的长度代表该模式在今后遗传操作模式的长度代表该模式在今后遗传操作( (交叉、变异交叉、变异交叉、变异交叉、变异) )中被破坏的可能性：中被破坏的可能性：中被破
153、坏的可能性：中被破坏的可能性： 模式长度越短，被破坏的可能性越小，长度为模式长度越短，被破坏的可能性越小，长度为模式长度越短，被破坏的可能性越小，长度为模式长度越短，被破坏的可能性越小，长度为0 0的模式最难被破坏。的模式最难被破坏。的模式最难被破坏。的模式最难被破坏。3.1.3 3.1.3 编码字符串的模式数目编码字符串的模式数目编码字符串的模式数目编码字符串的模式数目 (1) (1) 模式总数模式总数模式总数模式总数 二进制字符串二进制字符串 假设字符的长度为假设字符的长度为l，字符串中每一个字符可取字符串中每一个字符可取( 0, 1, * ) 三个符号中任意三个符号中任意 一个，可能组成
154、的模式数目最多为：一个，可能组成的模式数目最多为： 3 3 3 3 = (2+1)(2+1)ll 一般情况下一般情况下， 假设字符串长度为假设字符串长度为l，字符的取值为字符的取值为 k 种，字符串组成的模式数目种，字符串组成的模式数目 n1 最多最多 为：为： n1=(k+1)lSoft Computing Lab.162XiDian UNIVERSITY (2) (2) 编码字符串（一个个体编码串）所含模式总数编码字符串（一个个体编码串）所含模式总数编码字符串（一个个体编码串）所含模式总数编码字符串（一个个体编码串）所含模式总数 二进制字符串二进制字符串 对于长度为对于长度为l的某二进制字
155、符串，它含有的模式总数最多为：的某二进制字符串，它含有的模式总数最多为： 2 2 2 2 = 2 2ll 注意注意 这个数目是指字符串已确定为这个数目是指字符串已确定为0或或1，每个字符只能在已定值，每个字符只能在已定值 (0/1)中选取；中选取； 前面所述的前面所述的 n1 指字符串未确定，每个字符可在指字符串未确定，每个字符可在0, 1, * 三者中选取。三者中选取。 一般情况下一般情况下 长度为长度为l、取、取值有值有 k 种的某一字符串，它可能含有的模式数目最多为：种的某一字符串，它可能含有的模式数目最多为： n2 = kl (3) (3) 群体所含模式数群体所含模式数群体所含模式数群
156、体所含模式数 在长度为在长度为l，规模为规模为M的二进制编码字符串群体中，一般包含有的二进制编码字符串群体中，一般包含有2l M 2l个个 模式。模式。Soft Computing Lab.163XiDian UNIVERSITY 3.2 3.2 模式定理模式定理模式定理模式定理 由前面的叙述我们可以知道，在引入模式的概念之后，遗传算法的实质可看由前面的叙述我们可以知道，在引入模式的概念之后，遗传算法的实质可看 作是对模式的一种运算。对基本遗传算法作是对模式的一种运算。对基本遗传算法(GA)而言，也就是某一模式而言，也就是某一模式s 的各个的各个 样本经过选择运算、交义运算样本经过选择运算、交
157、义运算、变异运算之后，得到一些新的样本和新的模式。变异运算之后，得到一些新的样本和新的模式。3.2.1 3.2.1 复制时的模式数目复制时的模式数目复制时的模式数目复制时的模式数目 这里以比例选择算子为例研究。这里以比例选择算子为例研究。 公式推导公式推导公式推导公式推导 (1) 假设在第假设在第t次迭代时次迭代时, 群体群体P(t)中有中有M个个体个个体, 其中其中m个个体属于模式个个体属于模式s, 记作记作m(s,t)。 (2) 个体个体 ai 按其适应度按其适应度 fi 的大小进行复制。的大小进行复制。 从统计意义讲，个体从统计意义讲，个体ai被被复制的概率复制的概率pi是：是：(3)
158、因此复制后在下一代群体因此复制后在下一代群体 P(t+1)中，群体内属于模式中，群体内属于模式s（或称与模式或称与模式s匹配）匹配） 的个体数目的个体数目 m(s,t+1) 可用平均适应度按下式近似计算：可用平均适应度按下式近似计算：f(s)式中式中 第第t代属于模式代属于模式 s 的所有的所有 个体之平均适应度；个体之平均适应度； M群体中拥有的个体数目。群体中拥有的个体数目。f(s)Soft Computing Lab.164XiDian UNIVERSITY (4) 设第设第t代所有个体代所有个体(不论它属于何种模式不论它属于何种模式)的平均适应度是的平均适应度是 , 有等式有等式:f(
159、5) 综合上述两式，复制后模式综合上述两式，复制后模式s所拥有的个体数目可按下式近似计算：所拥有的个体数目可按下式近似计算：fff(s) 结论结论结论结论 上式说明复制后下一代群体中属于模式上式说明复制后下一代群体中属于模式上式说明复制后下一代群体中属于模式上式说明复制后下一代群体中属于模式s s 的个体数目，取决于该模式的平均的个体数目，取决于该模式的平均的个体数目，取决于该模式的平均的个体数目，取决于该模式的平均 适应度适应度适应度适应度 与群体的平均适应度与群体的平均适应度与群体的平均适应度与群体的平均适应度 之比之比之比之比; ; 只有当模式只有当模式只有当模式只有当模式s s 的平均
160、值的平均值的平均值的平均值 大于群钵的平均值大于群钵的平均值大于群钵的平均值大于群钵的平均值 时，时，时，时，s s模式的个体数目才模式的个体数目才模式的个体数目才模式的个体数目才 能增长。否则，能增长。否则，能增长。否则，能增长。否则，s s模式的数目要减小。模式的数目要减小。模式的数目要减小。模式的数目要减小。 模式模式s 的这种增减规律，正好符合复制操作的的这种增减规律，正好符合复制操作的“优胜劣汰优胜劣汰”原则，这也说明原则，这也说明模模 式的确能描述编码字符串的内部特征。式的确能描述编码字符串的内部特征。f(s)ff(s)fSoft Computing Lab.165XiDian U
161、NIVERSITY 进一步推导进一步推导进一步推导进一步推导 (1) 假设某一模式假设某一模式s 在复制过程中其平均适应度在复制过程中其平均适应度 比群体的平均适应度比群体的平均适应度 高高 出一个定值出一个定值 ，其中其中c 为常数，则上式改写为：为常数，则上式改写为：ff(s) c f 结论结论结论结论 从数学上讲，上式是一个指数方程，它说明模式从数学上讲，上式是一个指数方程，它说明模式从数学上讲，上式是一个指数方程，它说明模式从数学上讲，上式是一个指数方程，它说明模式s s 所拥有的个体数目所拥有的个体数目所拥有的个体数目所拥有的个体数目 在复制过程中以指数形式增加或减小。在复制过程中以
162、指数形式增加或减小。在复制过程中以指数形式增加或减小。在复制过程中以指数形式增加或减小。 f c ff += m( s, t ) (1+c ) (2) 从第一代开始，若模式从第一代开始，若模式s 以常数以常数c 繁殖到第繁殖到第 t+1代，其个体数目为：代，其个体数目为： m( s, t+1 ) = m( s, 1 ) (1+c )tSoft Computing Lab.166XiDian UNIVERSITY 3.2.2 3.2.2 交叉时的模式数目交叉时的模式数目交叉时的模式数目交叉时的模式数目 这里以单点交叉算子为例研究。这里以单点交叉算子为例研究。 举例举例举例举例 (1) 有两个模式
163、有两个模式 s1: “ * 1 * * * * 0 ” s2: “ * * * 1 0 * * ” 它们有一个共同的可匹配的个体（可与模式匹配的个体称为模式的表示）它们有一个共同的可匹配的个体（可与模式匹配的个体称为模式的表示） a: “ 0 1 1 1 0 0 0 ” (2) 选择个体选择个体a 进行交叉进行交叉 (3) 随机选择交叉点随机选择交叉点 s1: “ * 1 * * * * 0 ” 交叉点选在第交叉点选在第 2 6 之间都可能破坏模式之间都可能破坏模式s1; s2: “ * * * 1 0 * * ” 交叉点在交叉点在 第第 4 5之间才破坏之间才破坏s2。 公式推导公式推导公式
164、推导公式推导 (1) 交换发生在模式交换发生在模式s 的定义长度的定义长度 (s)范围内，即模式被破坏的概率是：范围内，即模式被破坏的概率是：例：例： s1 被破坏的概率为：被破坏的概率为：5/6 s2 被破坏的概率为：被破坏的概率为：1/6 lSoft Computing Lab.167XiDian UNIVERSITY (2) 模式不被破坏，存活下来的概率为：模式不被破坏，存活下来的概率为： (3) 若交叉概率为若交叉概率为pc，则模式存活下来的概率为：则模式存活下来的概率为： 结论结论结论结论 模式的定义长度对模式的存亡影响很大，模式的长度越大，越容易被破坏。模式的定义长度对模式的存亡影
165、响很大，模式的长度越大，越容易被破坏。模式的定义长度对模式的存亡影响很大，模式的长度越大，越容易被破坏。模式的定义长度对模式的存亡影响很大，模式的长度越大，越容易被破坏。 (4) 经复制、交叉操作后，模式经复制、交叉操作后，模式s在下一在下一 代群体中所拥有的个体数目为：代群体中所拥有的个体数目为： l-1 1l-1 1ff(s)l-1 1Soft Computing Lab.168XiDian UNIVERSITY 3.2.3 3.2.3 变异时的模式数目变异时的模式数目变异时的模式数目变异时的模式数目 这里以基本位变异算子为例研究。这里以基本位变异算子为例研究。 公式推导公式推导公式推导公
166、式推导 (1) 变异时个体的每一位发生变化的概率是变异概率变异时个体的每一位发生变化的概率是变异概率pm，也就是说，每一位存也就是说，每一位存 活的概率是活的概率是(1- pm)。根据模式的阶根据模式的阶o(s)，可知模式中有明确含意的字符有可知模式中有明确含意的字符有o(s) 个，于是模式个，于是模式s 存活的概率是：存活的概率是： (2) 通常通常 pm f (vn) then vc vn;output new best chromosome vn;end Soft Computing Lab.182XiDian UNIVERSITY 6.1.2 参数自适应改变参数自适应改变由于遗传算法从
167、本质上讲是动态和适应性的过程，因此采用固定参数的方法是与一般的进化精神相违背的，实现方法(1)通过采用一种规则（2）通过获取当前搜索的状态信息进行反馈（3）采用自适应机制，有三种原则性分类（1）确定性（2）有适应能力（3）自适应的（1）确定性 Pm=0.50.3t/G,依赖时间的策略由holland提出（2）有适应能力的自适应性。如果从进化过程中获取某种形式的反馈并用来确定参数改变的方向和大小，就称有适应能力的自适应性，如用于修改变异步长的1/5原则，该准则认为，所有变异中的成功变异比例为1/5，如果大于1/5，则步长增加，否则减少变异的步长。（3）自适应的适应性 参数也进行编码并且经历变异和
168、重组，编码的参数并不直接影响个体的适应度，但更优秀的参数将产生更优秀的个体，这些个体在选择过程生存下来并产生后代，由此来传播更好的参数值。Soft Computing Lab.183XiDian UNIVERSITY 6.1.2 Parameter Control Approach of GAnSrinvas and Patnaiks Approach (IEEESMC 1994)pHeuristic Updating Strategy 启发式启发式 This scheme is to control Pc and PM using various fitness at each genera
169、tion. where : maximum fitness value at each generation. : average fitness value at each generation. : the larger of the fitness values of the chromosomes to be crossed. : the fitness value of the ith chromosome to which the mutation with a rate PM is applied.Soft Computing Lab.184XiDian UNIVERSITY 6
170、.1.2 Parameter Control Approach using Fuzzy Logic ControlleroParameter Control Approach using Fuzzy Logic Controller (FLC) Song, Y. H., G. S. Wang, P. T. Wang & A. T. Johns: “Environmental/Economic Dispatch Using Fuzzy Logic Controlled Genetic Algorithms,” IEEE Proceedings on Generation, Transmissio
171、n and Distribution, Vol. 144, No. 4, pp. 377382, 1997.nBasic Concept(根据平均适应度之间的差值大小调整交叉和变异概率根据平均适应度之间的差值大小调整交叉和变异概率) Heuristic updating strategy for the crossover and mutation rates is to consider changes of average fitness in the GA population of two continuous generations. For example, in minimiza
172、tion problem, we can set the change of the average fitness at generation t, as follows: where parSize : population size satisfying the constraints offSize : offspring size satisfying the constraints Soft Computing Lab.185XiDian UNIVERSITY 6. Parameter Control Approach using Fuzzy Logic Controllerpro
173、cedure: regulation of pC and pM using the average fitness input: GA parameters, pC(t1), pM(t1),fave(t-1),fave(t), output: pC(t), pM(t) begin if then increase pC and pM for next generation;(规则) if then decrease pC and pM for next generation;(规则) ifthen rapidly increase pC and pM for next generation ;
174、(规则) output pC(t), pM(t);endSoft Computing Lab.186XiDian UNIVERSITY 参数模糊调整参数模糊调整(ZengZeng和和RabenasoloRabenasolo方法方法) )Soft Computing Lab.187XiDian UNIVERSITY 下图下图下图所示下图所示Soft Computing Lab.188XiDian UNIVERSITY 控制规则控制规则Soft Computing Lab.189XiDian UNIVERSITY WangWang，WangWang和和HuHu方法方法Soft Computing
175、Lab.190XiDian UNIVERSITY pImplementation Strategy for Crossover FLCstep 1: Input and output of crossover FLC The inputs of the crossover FLC are the and in continuous two generations, the output of which is a change in the ,step 2: Membership functions of , and The membership functions of the fuzzy
176、input and output linguistic variables are illustrated in Figures 1 and 2, respectively. The input and output results of discretization for the and are set at Table 1, and the and are normalized into the range 1.0, 1.0. The is also normalized into the range 0.1, 0.1 according to their corresponding m
177、aximum values. (discretization 离散化）Parameter Control Approach using Fuzzy Logic ControllerSoft Computing Lab.191XiDian UNIVERSITY p Implementation Strategy for Crossover FLC Fig.1.8 Membership functions for Fig. 1.9 Membership function of and where: NR Negative larger, NL Negative large, NM Negative
178、 medium, NS Negative small, ZE Zero, PS Positive small, PM Positive medium, PL Positive large, PR Positive larger. Soft Computing Lab.192XiDian UNIVERSITY pImplementation Strategy for Crossover FLC inputsoutputs4321 0 1 2 3 4Table 1.1 Input and output results of discrimination(离散化)Soft Computing Lab
179、.193XiDian UNIVERSITY pImplementation Strategy for Crossover FLC step 3: Fuzzy decision table Use the same fuzzy decision table as the conventional work Song, et al. (1997), and the table is as follow: Table 1.2 Fuzzy decision table for crossoverZESoft Computing Lab.194XiDian UNIVERSITY oImplementat
180、ion Strategy for Crossover FLC step 4: Defuzzification table for control actions 避免复杂的模糊推理，通过下表可实现模糊推理。 Table 1.3 Defuzzification table for control action of crossover(去模糊化)6. Parameter Control Approach using Fuzzy Logic Controller0Soft Computing Lab.195XiDian UNIVERSITY Soft Computing Lab.196XiDian
181、 UNIVERSITY pImplementation Strategy for Mutation FLC The inputs of the mutation FLC are the same as those of the crossover FLC, and the output of which is a change in the , m(t). nCoordinated Strategy between the FLC and GA 6.1.2 Parameter Control Approach using Fuzzy Logic ControllerFig. 1.10 Coor
182、dinated strategy between the FLC and GASoft Computing Lab.197XiDian UNIVERSITY 6. Parameter Control Approach using Fuzzy Logic ControlleroDetailed procedure for Implementing Crossover and Mutation FLCs input: GA parameters, pC(t1), pM(t1), , output: pC(t), pM(t) step 1: The input variables of the FL
183、Cs for regulating the GA operators are the changes of the average fitness in continuous two generations (t 1 and t) as follows: , step 2: After normalizing and , assign these values to the indexes i and j corresponding to the control actions in the defuzzification table (see Table 3). Soft Computing
184、 Lab.198XiDian UNIVERSITY 6.3 Parameter Control Approach using Fuzzy Logic Controllerstep 3: Calculate the changes of the crossover rate and the mutation rate as follows: , where the contents of are the corresponding values of and for defuzzification. The values of 0.02 and 0.002 are given values to
185、regulate the increasing and decreasing ranges of the rates of crossover and mutation operators. step 4: Update the change of the rates of the crossover and mutation operators by using the following equations: , The adjusted rates should not exceed the range from 0.5 to 1.0 for the and the range from
186、 0.0 to 0.1 for the (变动不能太大)Soft Computing Lab.199XiDian UNIVERSITY Soft Computing Lab.200XiDian UNIVERSITY Soft Computing Lab.201XiDian UNIVERSITY Soft Computing Lab.202XiDian UNIVERSITY Soft Computing Lab.203XiDian UNIVERSITY Soft Computing Lab.204XiDian UNIVERSITY Soft Computing Lab.205XiDian UNI
187、VERSITY Soft Computing Lab.206XiDian UNIVERSITY Soft Computing Lab.207XiDian UNIVERSITY Soft Computing Lab.208XiDian UNIVERSITY Soft Computing Lab.209XiDian UNIVERSITY Soft Computing Lab.210XiDian UNIVERSITY 6.4 Design of aHGA using Conventional Heuristics and FLCpDesign of Canonical GA (CGA)（标准遗传算法
188、）（标准遗传算法） For the canonical GA (CGA), we use a realnumber representation instead of a bitstring one, and the detailed implementation procedure for the CGA is as follows: procedure: Canonical GA (CGA) (Gen & Cheng, 2000)input: GA parametersoutput: best solutionbegint 0;initialize P(t) by random gener
189、ation based on system constraints; fitness eval(P);while (not termination condition) do crossover P(t) to yield C(t) by nonuniform arithmetic crossover; mutation P(t) to yield C(t) by uniform mutation; fitness eval(C); select P(t+1) from P(t) and C(t) by elitist strategy in enlarged sampling space;
190、t t+1;end output best solution;end Soft Computing Lab.211XiDian UNIVERSITY 6.4 Design of aHGA using Conventional Heuristics and FLCpDesign of Hybrid GA (HGA): CGA with Local Search For this HGA, the CGA procedure and the iterative hill climbing method (Yun & Moon, 2003) are used as a mixed type. pro
191、cedure: CGA with Local Search (HGA)input: GA parametersoutput: best solutionbegint 0;initialize P(t) by random generation based on system constraints; fitness eval(P);while (not termination condition) do crossover P(t) to yield C(t) by nonuniform arithmetic crossover; mutation P(t) to yield C(t) by
192、uniform mutation; local search C(t) by iterative hill climbing method (Yun & Moon, 2003); fitness eval(C); select P(t+1) from P(t) and C(t) by elitist strategy in enlarged sampling space; t t+1;end output best solution;end Soft Computing Lab.212XiDian UNIVERSITY 6.4 Design of aHGA using Conventional
193、 Heuristics and FLCpDesign of aHGAs: HGAs with Conventional Heuristics n aHGA1: CGA with local search and adaptive scheme 1 For the first aHGA (aHGA1), we use the CGA procedure, the iterative hill climbing method and the procedures of the heuristic by Mak et al. (2000) as a mixed type. procedure: CG
194、A with Local Search and Adaptive Scheme 1 (aHGA1)input: GA parametersoutput: best solutionbegint 0;initialize P(t) by random generation based on system constraints; fitness eval(P);while (not termination condition) do crossover P(t) to yield C(t) by nonuniform arithmetic crossover; mutation P(t) to
195、yield C(t) by uniform mutation; local search C(t) by iterative hill climbing method; fitness eval(C); select P(t+1) from P(t) and C(t) by elitist strategy in enlarged sampling space;adaptive regulation of GA parameters using heuristic updating strategy (Mak et al., 2000); t t+1;end output best solut
196、ion;end Soft Computing Lab.213XiDian UNIVERSITY 6.4 Design of aHGA using Conventional Heuristics and FLCpDesign of aHGAs: HGAs with Conventional Heuristics n aHGA2: CGA with local search and adaptive schema 2 For the first aHGA (aHGA1), we use the CGA procedure, the iterative hill climbing method an
197、d the procedures of the heuristic by Srinivas and Patnaik (1994) as a mixed type. procedure: CGA with local search and adaptive scheme 2 (aHGA2)input: GA parametersoutput: best solutionbegint 0;initialize P(t) by random generation based on system constraints; fitness eval(P);while (not termination c
198、ondition) do crossover P(t) to yield C(t) by nonuniform arithmetic crossover; mutation P(t) to yield C(t) by uniform mutation; local search C(t) by iterative hill climbing method; fitness eval(C); select P(t+1) from P(t) and C(t) by elitist strategy in enlarged sampling space; adaptive regulation of
199、 GA parameters using heuristic updating strategy (Srinivas and Patnaik, 1994); t t+1;end output best solution;end Soft Computing Lab.214XiDian UNIVERSITY 6.4 Design of aHGA using Conventional Heuristics and FLCpDesign of aHGAs: HGAs with FLC n flc-aHGA: CGA with local search and adaptive scheme of F
200、LC For the first aHGA (aHGA1), we use the CGA procedure, the iterative hill climbing method and the procedures of the FLC (Song et al., 1997) as a mixed type. procedure: CGA with Local Search and Adaptive Scheme of FLC (flcaHGA)input: GA parametersoutput: best solutionbegint 0;initialize P(t) by ran
201、dom generation based on system constraints; fitness eval(P);while (not termination condition) do crossover P(t) to yield C(t) by nonuniform arithmetic crossover; mutation P(t) to yield C(t) by uniform mutation; local search C(t) by iterative hill climbing method; fitness eval(C); select P(t+1) from
202、P(t) and C(t) by elitist strategy in enlarged sampling space; adaptive regulation of GA parameters using FLC (Song et al., 1997); t t+1;end output best solution;end Soft Computing Lab.215XiDian UNIVERSITY 6.4 Design of aHGA using Conventional Heuristics and FLCpFlowchart of the proposed algorithms s
203、toptermination conditionmutationcrossoverselectioninitial populationstartCGANoYesstoptermination conditionselectioninitial populationstartHGAiterative hillclimbingNoYesstoptermination conditionselectioninitial populationstartaHGA1iterative hillclimbingNoYesstoptermination conditionselectioninitial p
204、opulationstartaHGA2iterative hillclimbingNoYesstoptermination conditionselectioninitial populationstartflc-aHGAiterative hillclimbingNoYesevaluationmutationcrossoverevaluationmutationcrossoverevaluationmutationcrossoverevaluationmutationcrossoverevaluationadaptivescheme 1adaptivescheme 2adaptiveFLC启发式启发式启发式启发式Soft Computing Lab.216XiDian UNIVERSITY
