进化算法遗传算法PPT学习教案

1、会计学1进化算法遗传算法进化算法遗传算法Soft Computing Lab.2为连续优化若取值离散为离散优化，为约束优化时为无约束优化，否则当时为多目标优化当，时为单目标优化当RDXX0km, 1n1n, 1, 0)(, 1, 0)()(,),(max1)(DXkjxhmixgstXffjinXFX第1页/共216页Soft Computing Lab.3第2页/共216页Soft Computing Lab.4第3页/共216页Soft Computing Lab.5第4页/共216页Soft Computing Lab.6旅行商问题（TSP,traveling salesman prob

2、lem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。（n-1)!/2第5页/共216页Soft Computing Lab.7 ADECBThe one below is length: 33ABCDEA57415B53410C7327D4429E151079第6页/共216页Soft Computing Lab.8第7页/共216页Soft Computing Lab.9第8页/共216页Soft Computing Lab.10第9页/共216页Soft Computing Lab.11nn, nn,

3、第10页/共216页Soft Computing Lab.12 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 n第11页/共216页Soft Computing Lab.13第12页/共216页Soft Computing Lab.14polynomialexponential 指数复杂度一般要比多项式复杂 要复杂

4、F(n)Increasing n第13页/共216页Soft Computing Lab.150. Initialise: Generate a random solution c; evaluate its fitness, 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, otherwis

5、e do nothing (effectively discarding m).3. If a termination condition has been reached, stop. Otherwise, go 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.第14页/共216页Soft Computing Lab.16 12435, 867910第15页/共216页Sof

6、t Computing Lab.17第16页/共216页Soft Computing Lab.18第17页/共216页Soft Computing Lab.19第18页/共216页Soft Computing Lab.20第19页/共216页Soft Computing Lab.21第20页/共216页Soft Computing Lab.22第21页/共216页Soft Computing Lab.23化论的核心。第22页/共216页Soft Computing Lab.24第23页/共216页Soft Computing Lab.25第24页/共216页Soft Computing Lab

7、.26第25页/共216页Soft Computing Lab.27第26页/共216页Soft Computing Lab.28生物学中的遗传概念第27页/共216页Soft Computing Lab.29第28页/共216页Soft Computing Lab.30第29页/共216页Soft Computing Lab.31 Heres a problem: Design a material for the soles of boots that can help you walk up a smooth vertical brick wall We havent solved th

8、is, but nature has: Geckos（设计一种可以帮助人类爬上光滑的墙壁的鞋底材料） 生物的进化是经过无数次有利的进化积累而成的，不同的环境保留了不同的变异后代！第30页/共216页Soft Computing Lab.32 所有的生物经常面临一个共同的问题 How can I survive in this environment？自然界解决问题的方法就是：进化Evolution The basic method of it is trial and error(反复试验). 1. Come up with a new solution by randomly changin

9、g 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. 第31页/共216页Soft Computing Lab.33 Lesson1: Keep a population/collection of different things on the go. Lesson2: Select parents with a relatively weak bias towards

10、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. （无偏见的选择父代，或适者生存)Lesson3: It can sometimes help to use recombination of two or more parents I.e. generate

11、 new candidate solutions by combining bits and pieces from different previous solutions. 通过重组将父代优良基因遗传给后代This is genetic algorithm什么是进化？第32页/共216页Soft Computing Lab.34More like selective breeding than natural evolution Time 第33页/共216页Soft Computing Lab.35Initial population第34页/共216页Soft Computing La

12、b.36Select第35页/共216页Soft Computing Lab.37Crossover第36页/共216页Soft Computing Lab.38Another Crossover第37页/共216页Soft Computing Lab.39A mutation第38页/共216页Soft Computing Lab.40Another Mutation第39页/共216页Soft Computing Lab.41Old population + children第40页/共216页Soft Computing Lab.42New Population: Generation

13、2第41页/共216页Soft Computing Lab.43Generation 3第42页/共216页Soft Computing Lab.44Generation 4, etc 第43页/共216页Soft Computing Lab.45第44页/共216页Soft Computing Lab.46此往复，逐代演化产生出越来越好的近似解。第45页/共216页Soft Computing Lab.47第46页/共216页Soft Computing Lab.48第47页/共216页Soft Computing Lab.49的模式理论与他的计算使用结合起来。第48页/共216页Soft

14、Computing Lab.50第49页/共216页Soft Computing Lab.51第50页/共216页Soft Computing Lab.52p Conventional Method (point-to-point approach)initial single pointimprovement(problem-specific)termination condition?startstopConventional MethodYesNo第51页/共216页Soft Computing Lab.53improvement(problem-independent)terminat

15、ion condition?startstopGenetic Algorithminitial point.initial pointinitial pointInitial populationYesNoo遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算子。第52页/共216页Soft Computing Lab.54第53页/共216页Soft Computing Lab.55第54页/共216页Soft Computing La

16、b.56Random Search + Directed SearchSearch spaceFitnessf(x)local optimumglobal optimumlocal optimumlocal optimum0 xx1x2x4x5x3第55页/共216页Soft Computing Lab.57第56页/共216页Soft Computing Lab.58第57页/共216页Soft Computing Lab.59第58页/共216页Soft Computing Lab.60第59页/共216页Soft Computing Lab.61Initialsolutionsstart

17、1100101010101110111000110110011100110001encodingchromosome110010101010111011101100101110101110101000110110010011001001crossovermutation110010111010111010100011001001solutions candidatesdecodingfitness computationevaluationroulette wheelselectiontermination condition?YNbest solutionstop newpopulation

18、p The general structure of genetic algorithms Gen, M. & R. Cheng: Genetic Algorithms and Engineering Design, John Wiley, New York, 1997.offspringoffspringt 0 P(t)CC(t)CM(t)P(t) + C(t)第60页/共216页Soft Computing Lab.62procedure: Simple GAinput: GA parametersoutput: best solutionbegint 0;/ t: generat

19、ion numberinitialize P(t) by encoding routine;/ P(t): population 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+

20、1; end output best solution;end 第61页/共216页Soft Computing Lab.63第62页/共216页Soft Computing Lab.64max f (x1, x2) 21.5 + x1sin(4p x1) + x2sin(20p x2)s. t. -3.0 x1 12.1 4.1 x2 5.8第63页/共216页Soft Computing Lab.65max f (x1, x2) 21.5 + x1sin(4p x1) + x2sin(20p x2)s. t. -3.0 x1 12.1 4.1 x2 5.8第64页/共216页Soft Co

21、mputing Lab.66n 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 v

22、ariable is calculated as follows:nThe mapping from a binary string to a real number for variable xj is completed as follows:1210)(251jjmjjmab12)(decimal+jmjjjjjabsubstringax第65页/共216页Soft Computing Lab.67nThe precision requirement implies that the range of domain of each variable should be divided i

23、nto at least (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:第66页/共21

24、6页Soft Computing Lab.68step 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 (bj - aj )105 size ranges.step 3: The required bits (denoted

25、 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 1210)(251jjmjjmabinput: domain of xj aj, bj, (j=1,2)(输入可行解(x1,x2)，表现型)output: chromosome v(输出二进制码，基因型）第67页/共216页Soft Computing Lab.69

26、nThe mapping from a binary string to a real number for variable xj is completed as follows:12)(decimal+jmjjjjjabsubstringax第68页/共216页Soft Computing Lab.7012)(decimal+jmjjjjjabsubstringaxinput: substringjoutput: a real number xj step 1: Convert a substring (a binary string) to a decimal number.step 2

27、: The mapping for variable xj is completed as follows:第69页/共216页Soft Computing Lab.71v1 = 000001010100101001101111011111110 = x1 x2 = -2.687969 5.361653v2 = 001110101110011000000010101001000 = x1 x2 = 0.474101 4.170144v3 = 111000111000001000010101001000110 = x1 x2 = 10.419457 4.661461v4 = 1001101101

28、00101101000000010111001 = x1 x2 = 6.159951 4.109598v5 = 000010111101100010001110001101000 = x1 x2 = -2.301286 4.477282v6 = 111110101011011000000010110011001 = x1 x2 = 11.788084 4.174346v7 = 110100010011111000100110011101101 = x1 x2 = 9.342067 5.121702v8 = 001011010100001100010110011001100 = x1 x2 =

29、-0.330256 4.694977v9 = 111110001011101100011101000111101 = x1 x2 = 11.671267 4.873501v10 = 111101001110101010000010101101010 = x1 x2 = 11.446273 4.171908第70页/共216页Soft Computing Lab.72input: chromosome vk, k=1, 2, ., popSizeoutput: the fitness eval(vk)step 1: Convert the chromosomes genotype to its

30、phenotype, 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 t

31、he value of objective function:eval(vk) = f (xk), k = 1,2, , popSize.), 2, 1(), 2, 1()()(nipopSizekxfvevalikf (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)第71页/共216页Soft Computing Lab.73eval(v1) = f (-2.687969, 5.361653

32、) =19.805119 eval(v2) = f (0.474101, 4.170144) = 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 (-

33、0.330256, 4.694977) = 19.763190eval(v9) = f (11.671267, 4.873501) = 26.401669eval(v10) = f (11.446273, 4.171908) = 10.252480第72页/共216页Soft Computing Lab.74step 1: Calculate the total fitness for the populationstep 2: Calculate selection probability pk for each chromosome vkstep 3: Calculate cumulati

34、ve 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 qk-1 r qk .input: population P(t-1), C(t-1)output: population P(t), C(t)第73页/共216页Soft

35、Computing Lab.75step 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 random number r from the range 0,1.135372.178)(101kkevalFv0.197577 0.032685

36、, 0.343242, 0.177618, 0.583392, 0.350871, 0.881893, 0.766503, 0.322062, 0.301431, input: population P(t-1), C(t-1)output: population P(t), C(t)第74页/共216页Soft Computing Lab.761100.197577 0.032685, 0.343242, 0.177618, 0.583392, 0.350871, 0.881893, 0.766503, 0.322062, 0.301431, 第75页/共216页Soft Computing

37、 Lab.77step 5: q3 r1 = 0.301432 q4, it means that the chromosome v4 is selected for new population; q30, 2 0 If 1+2=1 If 1+2 2, 1 0, 2 0 x1=1x1+ 2x2x2=1x2+ 2x1x1x2linear hull = R2solution spacex1x2convex hullaffine hullFig 1.2 Illustration showing convex, affine, and linear hull仿射交叉第141页/共216页Soft C

38、omputing Lab.143),(kUkkkxxtxx+),(LkkkkxxtxxorbTtryyt1),(xlxuxkb来决定一致性的大小，nonuniformityT固定，b越大值越小b固定，t越大值越小第142页/共216页Soft Computing Lab.144ininiixxxxfxxxxf+),(),(11dx = x + r d wherer = a random nonnegative real numberx = r (x2 - x1)+ x2第143页/共216页Soft Computing Lab.145.第144页/共216页Soft Computing Lab

39、.146np3p1p2d2d1Axis Connecting two ParentsNormal Distribution1s2s第145页/共216页Soft Computing Lab.147n 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 p

40、arents p1 and p2 z1: a random number with normal distribution N(0, s2 ) zk : a random number with the normal distribution N(0, s2 ), k=1,2, n & : certain constants1kn The children are generated as follows:,.,2 , 1,|)(,., 3, 2, 0(), 0(2/ )(12121221122112121122111i jnjieePPPPenddnkNzNzPPmezezmCeze

41、zmCjikknkkknkkk+s sss)第146页/共216页Soft Computing Lab.148An chromosome in evolution strategies consists of two components (x, s ), where the first vector x represents a point in the search space, the second vector s represents standard deviation. An offspring (x, s ) is generated as follows: ), 0(),0(

42、xx+ NeNwhere N(0, Ds ) is a vector of independent random Gaussian numbers with a mean of zero and standard deviations s.第147页/共216页Soft Computing Lab.149第148页/共216页Soft Computing Lab.150第149页/共216页Soft Computing Lab.151 Fig. 1.3 Adapting a problem to the genetic algorithms. adaptationProblemAdapted

43、problemGenetic Algorithms第150页/共216页Soft Computing Lab.152 Fig. 1.4 Adapting the genetic algorithms to a problem. adaptationProblemAdapted problemGenetic Algorithms第151页/共216页Soft Computing Lab.153 Fig. 1.5 Adapting both the genetic algorithms and the problem. ProblemAdapted GAsGenetic AlgorithmsAda

44、pted problem第152页/共216页Soft Computing Lab.154第153页/共216页Soft Computing Lab.155第154页/共216页Soft Computing Lab.156 t pM = 0.5 - 0.3maxGen第155页/共216页Soft Computing Lab.157第156页/共216页Soft Computing Lab.158第157页/共216页Soft Computing Lab.159第158页/共216页Soft Computing Lab.160第159页/共216页Soft Computing Lab.161

45、个体是由二值字符集 V=0, 1 中的元素所组成的一个编码串; 而模式却是由三值字符集 V=0, 1,* 中的元素所组成的一个编码串，其中 “ ” 表示通配符，它既可被当作 “1” 也可被当作 “0”。 指模式中已有明确含意(二进制字符时指0或1)的字符个数， 记做 o(s)，式中 s 代表模式。 例如，模式 ( 011*1* ) 含有4个明确含意的字符，其阶次是4， 记作 o( 011*1* ) =4; 模式 ( 0* ) 的阶次是1，记作 o( 0* ) =1。 当模式阶次为零时，它没有明确含义的字符，其概括性最强。 指模式中第一个和最后一个具有明确含意的字符之间的距离，记作 (s)。 例

46、如，模式( 011*l* ) 的第一个字符为0，最后一个字符为l，中间有3个字 符，其定义长度为4，记作 ( 011*l* ) = 4 ； 模式 ( 0* ) 的长度是0，记作 ( 0* ) = 0 ；第160页/共216页Soft Computing Lab.162 一般地，有式子 (s)b a 式中 b模式s 中最后一个明确字符的位置; a模式s 中最前一个明确字符的位置。 二进制字符串 假设字符的长度为l，字符串中每一个字符可取( 0, 1, * ) 三个符号中任意 一个，可能组成的模式数目最多为： 3 3 3 3 = 一般情况下， 假设字符串长度为l，字符的取值为 k 种，字符串组成的

47、模式数目 n1 最多 为： n1=(k+1)l第161页/共216页Soft Computing Lab.163 二进制字符串 对于长度为l的某二进制字符串，它含有的模式总数最多为： 2 2 2 2 = 注意 这个数目是指字符串已确定为0或1，每个字符只能在已定值 (0/1)中选取； 前面所述的 n1 指字符串未确定，每个字符可在0, 1, * 三者中选取。 一般情况下 长度为l、取值有 k 种的某一字符串，它可能含有的模式数目最多为： n2 = kl 在长度为l，规模为M的二进制编码字符串群体中，一般包含有2l M 2l个 模式。第162页/共216页Soft Computing Lab.1

48、64 由前面的叙述我们可以知道，在引入模式的概念之后，遗传算法的实质可看 作是对模式的一种运算。对基本遗传算法(GA)而言，也就是某一模式s 的各个 样本经过选择运算、交义运算、变异运算之后，得到一些新的样本和新的模式。 这里以比例选择算子为例研究。 (1) 假设在第t次迭代时, 群体P(t)中有M个个体, 其中m个个体属于模式s, 记作m(s,t)。 (2) 个体 ai 按其适应度 fi 的大小进行复制。 从统计意义讲，个体ai被复制的概率pi是： M1jii) j ( ffp(3) 因此复制后在下一代群体 P(t+1)中，群体内属于模式s（或称与模式s匹配） 的个体数目 m(s,t+1)

49、可用平均适应度按下式近似计算： + +M1j) j ( fM) t , s (m)1t , s (mf(s)式中 第t代属于模式 s 的所有 个体之平均适应度； M群体中拥有的个体数目。f(s)第163页/共216页Soft Computing Lab.165 (4) 设第t代所有个体(不论它属于何种模式)的平均适应度是 , 有等式:f(5) 综合上述两式，复制后模式s所拥有的个体数目可按下式近似计算：M) j(fM1j f + +)t , s(m)1t , s(mff(s) 模式s 的这种增减规律，正好符合复制操作的“优胜劣汰”原则，这也说明模 式的确能描述编码字符串的内部特征。f(s)ff

50、(s)f第164页/共216页Soft Computing Lab.166 (1) 假设某一模式s 在复制过程中其平均适应度 比群体的平均适应度 高 出一个定值 ，其中c 为常数，则上式改写为：ff(s) c f + +)t , s(m)1t , s(mf c ff += m( s, t ) (1+c ) (2) 从第一代开始，若模式s 以常数c 繁殖到第 t+1代，其个体数目为： m( s, t+1 ) = m( s, 1 ) (1+c )t第165页/共216页Soft Computing Lab.167 这里以单点交叉算子为例研究。 (1) 有两个模式 s1: “ * 1 * * * *

51、 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。 (1) 交换发生在模式s 的定义长度 (s)范围内，即模式被破坏的概率是：例： s1 被破坏的概率为：5/6 s2 被破坏的概率为：1/6 1 ) s (pd l第166页/共216页Soft Computin

52、g Lab.168 (2) 模式不被破坏，存活下来的概率为： (3) 若交叉概率为pc，则模式存活下来的概率为： (4) 经复制、交叉操作后，模式s在下一 代群体中所拥有的个体数目为：) s (1p1pds l-1) s (p1pcs l-1 + +),()1,(tsmtsmff(s) ) s (p1cl-1第167页/共216页Soft Computing Lab.169 这里以基本位变异算子为例研究。 (1) 变异时个体的每一位发生变化的概率是变异概率pm，也就是说，每一位存 活的概率是(1- pm)。根据模式的阶o(s)，可知模式中有明确含意的字符有o(s) 个，于是模式s 存活的概率是

53、： )s (oms)p1(p (2) 通常 pm f (vn) then vc vn;output new best chromosome vn;end 第181页/共216页Soft Computing Lab.183第182页/共216页Soft Computing Lab.184nSrinvas and Patnaiks Approach (IEEE-SMC 1994)pHeuristic Updating Strategy 启发式启发式 This scheme is to control Pc and PM using various fitness at each generatio

54、n. 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.avgcroavgcroavgcroCffkffffffkp,)(3maxmax1avg

55、mutavgmutavgmutMffkffffffkp,)(4maxmax2maxfavgfcrofmutf第183页/共216页Soft Computing Lab.185oParameter 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 Proceed

56、ings on Generation, Transmission and Distribution, Vol. 144, No. 4, pp. 377-382, 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 gener

57、ations. For example, in minimization 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 )(tfavg) )()()(tftftfoffSizeparSizeavg)()(11offSizetfparSizetfoffSize

58、kkparSizekk第184页/共216页Soft Computing Lab.186procedure: regulation of pC and pM using the average fitness input: GA parameters, pC(t-1), pM(t-1),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

59、 rapidly increase pC and pM for next generation ;(规则) output pC(t), pM(t);endtftfavgavg)() 1(andtftfavgavg)()1(andtftfavgavg)()1(and第185页/共216页Soft Computing Lab.187第186页/共216页Soft Computing Lab.188下图下图所示第187页/共216页Soft Computing Lab.189控制规则第188页/共216页Soft Computing Lab.190第189页/共216页Soft Computing

60、Lab.191pImplementation 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 input and output linguistic variable