《多目标进化.doc》由会员分享，可在线阅读，更多相关《多目标进化.doc（8页珍藏版）》请在三一文库上搜索。
1、Artif Life Robotics (2011) 16:373DOI 10.1007/S10015-011-0954-4-377? ISAROB 2011Takahiro Otani Takaya AritaImplementation of a probabilistic model-building co-evolutionary algorithmReceived and accepted: April 1,2011Abstract We propose an extended co-evolutionary algorithm (CA) with probabilistic mod
2、el buildi ng (CA-PMB) in order to improve the search performa nee of the CA. This article speci? cally describes an implementation of CA-PMB called a co-evoluti onary algorithm with populati on-based in creme ntal lear ning (CA-PBIL), and an alyzes the behavior of the algorithm through computati ona
3、l experime nts using an in tra nsitive n umbers game as a ben chmark problem. The experime ntal results show that desirable co- evoluti on may be inhibited by the over-specialization effect, and that the algorithm shows complex dyn amics caused by the game ' s intransitivity. However, further ex
4、periments show that the intransitivity encourages desirable co- evoluti on when a different learning rate is set for each populati on.algorithm. The CA has also bee n successfully applied to various problems, in clud ing the evoluti on of an arti?cialneural network for classi? cation problems, funct
5、ion approx- imati on, evolv ing strategies of game players, co-evolv ing predator - prey robots, and so on.In this study, we propose an exte nded CA called a co- evoluti onary algorithms with probabilistic model buildi ng (CA-PMB), in which a probabilistic model-buildi ng gen etic2algorithm (PMBGA)
6、is used as a search heuristic, and analyzes the behavior of the algorithm through computati onal experime nts.The sta ndard CA uses the search mecha nism of thegen etic algorithm to evolve can didate soluti ons. The CA-PMB adopts a PMBGA as a search heuristic in order to improve the search performa
7、nee of the sta ndard CA. A PMBGA (also called an estimati on of distributio n algo-game1 In troduct ionThe competitive co-evoluti onary algorithm is an exte nsion of the sta ndard evoluti onary algorithms in which in dividual solutions are not evaluated by a ? xed objective function (or ?tn ess fun
8、cti on), but are evaluated based on in teracti ons betwee n other soluti ons.The ? rst application of the algorithm is the design of a sort ing n etwork proposed by Hillis. He showed that the CA can desig n a feasible n etwork structure which has fewer comparators tha n a n etwork desig ned by a sta
9、 ndard gen eticT. Otani ( * )- T. AritaGraduate School of Information Science, Nagoya University,Furo-cho, Chikusa-ku, Nagoya 464-8601, Japan e-mail: t-otanialife.cs.is.nagoya-u.ac.jpThis work was presented in part at the 16th International Symposium on Arti? cial Life and Robotics, Oita, Japan, Jan
10、uary 27Key wordsCo-evoluti onary algorithm Probabilistic rithm) is a gen eric n ame give n to a class of evoluti onarymodel-build ing gen etic algorithm Intran sitive n umbersalgorithms in which gen etic operators, crossover and muta-tion, are replaced by building a probabilistic model which represe
11、 nts the distributi on of promis ing soluti ons, and gen- erati ng new soluti ons based on the model. The PMBGA can explicitly deal with the depe ndence of variables in a problem, and therefore it shows a better search performa nee in various optimizati on problems tha n sta ndard GAs. This article
12、shows an implementation of the CA-PMB called a co-evolutionary algorithm with population-based incre- men tal lear ning (CA-PBIL).This article an alyzes the behavior of CA-PBIL through computati onal experime nts using the in tra nsitive n umbers game as a ben chmark problem. The in tra nsitive n um
13、bers3 game is an abstract model devised by Wats on and Pollack to study in tra nsitivity, which refers to cyclic dominan ce, such as the rock - paper - scissors game, and has been seen as a substa ntial obstacle to progress in competitive co-evolu- tionary algorithms. Experime ntal results show that
14、 desirable co-evoluti on may be in hibited by the over-specializati on effect, and that the algorithm shows complex dyn amics caused by the game ' s intransitivity. However, further experime nts show that the intransitivity encourages desirable co-evoluti on whe n a differe nt lear ning rate is
15、set for each-29, populatio n.#F(s) =?结“)?”)if s &if s S2(1)2 Co-evoluti onary algorithmThe CA is an extension of the standard evolutionary algorithms. An importa nt differe nee betwee n (competitive) CA and sta ndard evoluti onary algorithms lies in how to de? ne an evaluati on fun eti on. In a
16、CA, not every soluti on is evaluated by a ? xed objective fun eti on as in sta ndard evoluti onary computati ons, but is evaluated based on in teracti ons betwee n other soluti ons. A model of the CA dealt with in1 2this paper uses two solution sets S and S . A solution s in a soluti on set is evalu
17、ated based on in teracti ons with all the soluti ons in the other soluti on set. An evaluati on fun cti on F (s) is de? ned asthe distribution of promising solutions, and evaluates each soluti on gen erated accord ing to Eq. 1. Then the model is updated based on good soluti ons.3.2 CA-PBIL: an imple
18、mentation of CA-PMBThis article shows an impleme ntati on of the CA-PMB called a co-evoluti onary algorithm with populati on-based in creme ntal lear ning (CA-PBIL). The pseudo-code of the algorithm is described in Fig. 2. The CA-PBIL uses a PBIL4algorithm as a search heuristic. The PBIL is a simple
19、 variation of the PMBGA. This algorithm deals with can didate solutions as bit-strings, and uses and updates a probability vector as a probabilistic model which represe nts the probability of assigning the value“1 ” to the corresponding bitfor a new can didate soluti on.375where E (s,t) deno tes a p
20、ayoff of soluti on s depe nding on an in teracti on with soluti on t, which is de? ned based on a targeted problem.3 Co-evolutionary algorithm with probabilistic model buildi ng3.1 Scheme of the proposed algorithmThe PMBGA (also called an estimati on of distributio n algorithm) is a gen eric n ame g
21、ive n to a class of evoluti onary algorithms in which genetic operators, crossover and muta- ti on, are replaced by buildi ng a probabilistic model which represe nts the distributi on of promis ing soluti ons and generat ing new soluti ons based on the model.In this study, we propose a co-evolutiona
22、ry algorithm with probabilistic model building (CA-PMB) in which a PMBGA is used as a search heuristic. A scheme of the algorithm is show n in Fig. 1. This algorithm gen erates each soluti on set using a probabilistic model which represe ntsFig. 1. Scheme of a co-evolutionary algorithm with probabil
23、istic model building (CA-PMB)4 Intransitive numbers gameThis article an alyzes the behavior of a CA-PBIL through computational experiments using the intransitive numbers game (ING) as a ben chmark problem. The ING is an abstract model for studyingintransitivity (as in the well-known rock - paper - s
24、cissors game), which has been seen as a substa ntial obstacle to progress in competitive co- evoluti onary algorithms, and is usually used to compare the performa nee of co-evoluti onary algorithms. 0.5, i 1 r. r., Li泌 0.5, i = 1 f., Lawhile rJ erminaticm condition not met do51 J /Vi solutions geTie
25、rated by p1'52 solutions oncratwl by p2best1 ipt *- - (1.0 Lt Z?丄)十 b&s if- LRi, i = 1 j, A i p?屯- (1-0 LRJ 十? E 11 ? Lhfbr i 1, r r r Li doif rand < MP thenpt p- (1.0 MSi) +1) MSifind ifend forfbr i =. doif ra.ntJ < A7 巴 tlien(1,0 MS切 + rand(0,1) MS2end ifend forend whileFig. 2. Pseud
26、ocode of a co-evolutionary algorithm with populationbased incremental learning (CA-PBIL)4.1 Problem de? nitio nThe soluti on of an ING is an n-dime nsional vector, and the range of values of each dime nsion is 0,k. The payoff function E (s,t) is de? ned asE(s t) =signn? ?孚？5 Computati onal experime
27、ntsIn this section, we analyze the behavior of a CA-PBIL using ING. The n umber of dime nsions and the maximum value of each dime nsion were set to n = 2 and k = 100, respectively. The optimal solution is (100,100). The length of a bit-string was set to L ! = L2 = 200.#where#?s - ti g =? 0if hi = mi
28、n hjotherwise5.1 Dynamics of the original INGsig n returns to 1 when an in put value is posi-1 whe n an in put value is n egative, andThe fun cti on tive, retur ns to retur ns 0 whe n an in put value is 0. Therefore, the winning soluti on is the one with the higher magn itude in the dime n- sio n of
29、 the least differe nee betwee n the two soluti ons.Furthermore, a modi? ed ING is also used for experimental an alysis of the algorithm .In this problem, the fun cti on sign in Eq. 2 is modi? ed as follows. The function returns to 1 when an in put value is positive, and otherwise returns to 0. These
30、 sett ings activate the algorithm more freque ntly.First, we carried out the following experiments using the original ING to study how the average value of the solution gen erated progresses. The algorithm' s parameters were set asfollows: the learning rates LR 勺=LR 2 = 0.01, the numbers of solu
31、ti on s gen erated at every iterati on N1 = N2 = 100, and the mutati on probabilities MP 勺=MP 2 = 0.0. This means that no mutati on procedure was executed. The n umber of iterati ons was set at 10 000, and the experiment was trialed 100 times.The experime ntal results show thata stag nati on patter
32、noccurred in almost all trials, while a pattern ofcon verge neeto a low value rarely occurred. Typical examples of each patter n which occurred are show n in Fig. 3. Figure 3a showss complexpattern which is called the over-specializatio n3effect. If two values in one dimension become suf?cientlyclos
33、er to each other than in the other dimension, the other#4.2 Bit-str ings soluti on represe ntati onA bit-stri ng b is con verted to a vector soluti on s as follows. The length of the bit-string is set to L1 = L2 = nk, and the i-th dime nsion value of a vector soluti on is calculated asks = ” b(i-1)*
34、+j where bi denotes the i-th bit value of the bit-string.dime nsion does not play a role in decisi on payoffs. Therefore, the former will evolve desirably, but the latter will stag nate.Figure 3b shows a rare case in which the con verge nee to a low value patter n occurred. This patter n is caused b
35、y the intransitivity of the game, and is called the relativism effect3in the literature. For example, consider a = (4,7) and b = (5,5). The dimension of least differenee is the ? rst, and b gets a positive payoff. Now a' = (3,6), which is a small variation from a. The dime nsion of least differe
36、 nee betwee na'#0080.1UQggul-p 苍 gincAs dimain&ion 1SI hs dimension 2 dimemBion 1Sp's dimension 2 产ia1000 2COT 3000 4OT0 5000 6000 7MX> 0000 9000 1QOOQkeration1000 2CXX) 3000 40OT 5000 6000 7000 8000 9000 10000iteration00BeK402C#Fig. 3. Typical examples of progress patterns in the ori
37、ginal intransitive numbers game. a Stagnation (99 times). b Convergence to a low value (once)377#UOISUME_P Lpnl血 JO Hnffl>U 口 一 SC-BE-P llCJEo!HCOJn-EA1000 2000 3000 4000 5000 6000 7000 8000 9000 100001OC8060iterationFig. 4. Typical examples of progress patterns in the modi? ed intransitive numbe
38、rs game. a Stagnation caused by over-specialization (38 times). b Converges to a low value in one dimension (49 times).cUCIS匚 bui-6lpe®o匚。厉匚ip富o中n BAC1D00 2000 3000 4000 5000 6000 7000 8000 9000 10000iteration俪aiion b6040Convergence to a high value in both dimensions (4 times). d Oscillation st
39、arting in one dimension (9 times)#and b is the second dimension, and a' gets a positive payoff. Therefore, a should be replaced by a'. Then, b ' = (4,4) gets a positive payoff depe nding on the in teracti on witha', andb should be replaced by b'. These soluti ons repeatedly evolv
40、e to low values in this manner.5.2 Dynamics on the modi? ed INGWe carried out the same experime nts using the modi? ed ING. The parameters of the algorithm were set as in the previous experime nts. In these experime nts, four types of patter n occurred. Typical examples of each pattern are show n in
41、 Fig. 4. The dyn amic patter ns show n in Fig. 4b were caused by the intransitivity of the game.5.3 Co-evolution under a different learning rateFin ally, we carried out experime nts to an alyze the behavior of the algorithm when a different learning rate was set foreach soluti on set. We exam ined t
42、he n umber of optimal solutions reached, and varied the learning rate ofS2's LR 2 from0.01 to 0.03. Other parameters were set as in the previous experime nts.Figure 5 shows the experime ntal results. Accord ing to these results, the search performa nee was in creased whe n a different learning r
43、ate was set for each population in the modi? ed ING. The reas on is believed to be that these settings would en courage con verge nee to high values, as show n in Fig. 4c.6 Con clusi ons-dWe have proposed an exte nded CA called a CA-PMB, showed the CA-PBIL as an in itial impleme ntati on, and examin
44、ed the algorithm ' s behavior through experiments using ING. The experimental results showed that desirable co-evoluti on may be in hibited by an over-specializati on effect. We also observed in terest ing co-evoluti onary behav-LR?Fig. 5. The number of optimal solutions reached_ceE匸dCJpeMu雷o>
45、;qEn u e£ior caused by the game ' s intransitivity, especially in the modi? ed ING. Further experiments showed that the intransitivity en courages desirable co-evoluti on whe n a differe nt learning rate is set for each populati on. This feature has the possibility of providi ng new ways to
46、 solve various problems in the co-evoluti onary doma in more effectively and ef? cie ntly.Future work will in clude an an alysis of the proposed algorithm by con duct ing further experime nts. In particular, the effectiveness of a different learning rate should be evaluated in more detail. Ano ther
47、directi on would be to compare its performance with other algorithms, and to evaluate them using other more practical problems. It might also be interesting to implement a CA combined with another PMBGA.Refere nces1. Hillis WD (1990) Co-evolving parasites improve simulated evolution as an optimizati
48、on procedure. Phys D: Nonlinear Phenomena 42:228 - 2342. Pelikan M, Goldberg DE, Lobo FG (2002) A survey of optimizationby building and using probabilistic models. Comput Optimization Appl 21:5- 203. Watson RA, Pollack JB (2001) Coevolutionary dynamics in aminimal substrate. Proceedings of the Genetic and Evolutionary Computa