進(jìn)化算法遺傳算法PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1進(jìn)化算法遺傳算法進(jìn)化算法遺傳算法Soft Computing Lab.2為連續(xù)優(yōu)化若取值離散為離散優(yōu)化，為約束優(yōu)化時(shí)為無約束優(yōu)化，否則當(dāng)時(shí)為多目標(biāo)優(yōu)化當(dāng)，時(shí)為單目標(biāo)優(yōu)化當(dāng)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個(gè)城市銷貨，所有城市走一遍再回到起點(diǎ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 指數(shù)復(fù)雜度一般要比多項(xiàng)式復(fù)雜 要復(fù)雜

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生物學(xué)中的遺傳概念第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（設(shè)計(jì)一種可以幫助人類爬上光滑的墻壁的鞋底材料） 生物的進(jìn)化是經(jīng)過無數(shù)次有利的進(jìn)化積累而成的，不同的環(huán)境保留了不同的變異后代！第30頁/共216頁Soft Computing Lab.32 所有的生物經(jīng)常面臨一個(gè)共同的問題 How can I survive in this environment？自然界解決問題的方法就是：進(jìn)化Evolution The basic method of it is trial and error(反復(fù)試驗(yàn)). 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. 通過重組將父代優(yōu)良基因遺傳給后代This is genetic algorithm什么是進(jìn)化？第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此往復(fù)，逐代演化產(chǎn)生出越來越好的近似解。第45頁/共216頁Soft Computing Lab.47第46頁/共216頁Soft Computing Lab.48第47頁/共216頁Soft Computing Lab.49的模式理論與他的計(jì)算使用結(jié)合起來。第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遺傳算法以決策變量的編碼作為運(yùn)算對象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身進(jìn)行優(yōu)化計(jì)算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運(yùn)算對象，從而可以很方便地引入和應(yīng)用遺傳操作算子。第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.(精度小數(shù)點(diǎn)后面五位)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)，表現(xiàn)型)output: chromosome v(輸出二進(jìn)制碼，基因型）第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.(基因型到表現(xiàn)型)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、個(gè)體是由二值字符集 V=0, 1 中的元素所組成的一個(gè)編碼串; 而模式卻是由三值字符集 V=0, 1,* 中的元素所組成的一個(gè)編碼串，其中 “ ” 表示通配符，它既可被當(dāng)作 “1” 也可被當(dāng)作 “0”。 指模式中已有明確含意(二進(jìn)制字符時(shí)指0或1)的字符個(gè)數(shù)， 記做 o(s)，式中 s 代表模式。 例如，模式 ( 011*1* ) 含有4個(gè)明確含意的字符，其階次是4， 記作 o( 011*1* ) =4; 模式 ( 0* ) 的階次是1，記作 o( 0* ) =1。 當(dāng)模式階次為零時(shí)，它沒有明確含義的字符，其概括性最強(qiáng)。 指模式中第一個(gè)和最后一個(gè)具有明確含意的字符之間的距離，記作 (s)。 例

46、如，模式( 011*l* ) 的第一個(gè)字符為0，最后一個(gè)字符為l，中間有3個(gè)字 符，其定義長度為4，記作 ( 011*l* ) = 4 ； 模式 ( 0* ) 的長度是0，記作 ( 0* ) = 0 ；第160頁/共216頁Soft Computing Lab.162 一般地，有式子 (s)b a 式中 b模式s 中最后一個(gè)明確字符的位置; a模式s 中最前一個(gè)明確字符的位置。 二進(jìn)制字符串 假設(shè)字符的長度為l，字符串中每一個(gè)字符可取( 0, 1, * ) 三個(gè)符號(hào)中任意 一個(gè)，可能組成的模式數(shù)目最多為： 3 3 3 3 = 一般情況下， 假設(shè)字符串長度為l，字符的取值為 k 種，字符串組成的

47、模式數(shù)目 n1 最多 為： n1=(k+1)l第161頁/共216頁Soft Computing Lab.163 二進(jìn)制字符串 對于長度為l的某二進(jìn)制字符串，它含有的模式總數(shù)最多為： 2 2 2 2 = 注意 這個(gè)數(shù)目是指字符串已確定為0或1，每個(gè)字符只能在已定值 (0/1)中選?。?前面所述的 n1 指字符串未確定，每個(gè)字符可在0, 1, * 三者中選取。 一般情況下 長度為l、取值有 k 種的某一字符串，它可能含有的模式數(shù)目最多為： n2 = kl 在長度為l，規(guī)模為M的二進(jìn)制編碼字符串群體中，一般包含有2l M 2l個(gè) 模式。第162頁/共216頁Soft Computing Lab.1

48、64 由前面的敘述我們可以知道，在引入模式的概念之后，遺傳算法的實(shí)質(zhì)可看 作是對模式的一種運(yùn)算。對基本遺傳算法(GA)而言，也就是某一模式s 的各個(gè) 樣本經(jīng)過選擇運(yùn)算、交義運(yùn)算、變異運(yùn)算之后，得到一些新的樣本和新的模式。 這里以比例選擇算子為例研究。 (1) 假設(shè)在第t次迭代時(shí), 群體P(t)中有M個(gè)個(gè)體, 其中m個(gè)個(gè)體屬于模式s, 記作m(s,t)。 (2) 個(gè)體 ai 按其適應(yīng)度 fi 的大小進(jìn)行復(fù)制。 從統(tǒng)計(jì)意義講，個(gè)體ai被復(fù)制的概率pi是： M1jii) j ( ffp(3) 因此復(fù)制后在下一代群體 P(t+1)中，群體內(nèi)屬于模式s（或稱與模式s匹配） 的個(gè)體數(shù)目 m(s,t+1)

49、可用平均適應(yīng)度按下式近似計(jì)算： + +M1j) j ( fM) t , s (m)1t , s (mf(s)式中 第t代屬于模式 s 的所有 個(gè)體之平均適應(yīng)度； M群體中擁有的個(gè)體數(shù)目。f(s)第163頁/共216頁Soft Computing Lab.165 (4) 設(shè)第t代所有個(gè)體(不論它屬于何種模式)的平均適應(yīng)度是 , 有等式:f(5) 綜合上述兩式，復(fù)制后模式s所擁有的個(gè)體數(shù)目可按下式近似計(jì)算：M) j(fM1j f + +)t , s(m)1t , s(mff(s) 模式s 的這種增減規(guī)律，正好符合復(fù)制操作的“優(yōu)勝劣汰”原則，這也說明模 式的確能描述編碼字符串的內(nèi)部特征。f(s)ff

50、(s)f第164頁/共216頁Soft Computing Lab.166 (1) 假設(shè)某一模式s 在復(fù)制過程中其平均適應(yīng)度 比群體的平均適應(yīng)度 高 出一個(gè)定值 ，其中c 為常數(shù)，則上式改寫為：ff(s) c f + +)t , s(m)1t , s(mf c ff += m( s, t ) (1+c ) (2) 從第一代開始，若模式s 以常數(shù)c 繁殖到第 t+1代，其個(gè)體數(shù)目為： m( s, t+1 ) = m( s, 1 ) (1+c )t第165頁/共216頁Soft Computing Lab.167 這里以單點(diǎn)交叉算子為例研究。 (1) 有兩個(gè)模式 s1: “ * 1 * * * *

51、 0 ” s2: “ * * * 1 0 * * ” 它們有一個(gè)共同的可匹配的個(gè)體（可與模式匹配的個(gè)體稱為模式的表示） a: “ 0 1 1 1 0 0 0 ” (2) 選擇個(gè)體a 進(jìn)行交叉 (3) 隨機(jī)選擇交叉點(diǎn) s1: “ * 1 * * * * 0 ” 交叉點(diǎn)選在第 2 6 之間都可能破壞模式s1; s2: “ * * * 1 0 * * ” 交叉點(diǎn)在 第 4 5之間才破壞s2。 (1) 交換發(fā)生在模式s 的定義長度 (s)范圍內(nèi)，即模式被破壞的概率是：例： s1 被破壞的概率為：5/6 s2 被破壞的概率為：1/6 1 ) s (pd l第166頁/共216頁Soft Computin

52、g Lab.168 (2) 模式不被破壞，存活下來的概率為： (3) 若交叉概率為pc，則模式存活下來的概率為： (4) 經(jīng)復(fù)制、交叉操作后，模式s在下一 代群體中所擁有的個(gè)體數(shù)目為：) s (1p1pds l-1) s (p1pcs l-1 + +),()1,(tsmtsmff(s) ) s (p1cl-1第167頁/共216頁Soft Computing Lab.169 這里以基本位變異算子為例研究。 (1) 變異時(shí)個(gè)體的每一位發(fā)生變化的概率是變異概率pm，也就是說，每一位存 活的概率是(1- pm)。根據(jù)模式的階o(s)，可知模式中有明確含意的字符有o(s) 個(gè)，于是模式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 啟發(fā)式啟發(fā)式 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(根據(jù)平均適應(yīng)度之間的差值大小調(diào)整交叉和變異概率根據(jù)平均適應(yīng)度之間的差值大小調(diào)整交叉和變異概率) 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;(規(guī)則) if then decrease pC and pM for next generation;(規(guī)則) ifthen

59、 rapidly increase pC and pM for next generation ;(規(guī)則) 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控制規(guī)則第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