chapter7.ps

收集了遗传算法、进化计算、神经网络、模糊系统、人工生命、复杂适应系统等相关领域近期的参考论文和研究报告

399.59 537.73 495.7 537.73 2 L
N
2 X
90 450 6.87 5.83 498.94 537.73 G
0 X
90 450 6.87 5.83 498.94 537.73 A
6 X
90 450 6.86 5.83 390.6 521.98 G
0 X
90 450 6.86 5.83 390.6 521.98 A
399.59 521.98 495.7 521.98 2 L
N
2 X
90 450 6.87 5.83 498.94 521.98 G
0 X
90 450 6.87 5.83 498.94 521.98 A
6 X
90 450 6.86 5.83 390.6 506.23 G
0 X
90 450 6.86 5.83 390.6 506.23 A
399.59 506.23 495.7 506.23 2 L
N
2 X
90 450 6.87 5.83 498.94 506.23 G
0 X
90 450 6.87 5.83 498.94 506.23 A
6 X
90 450 6.86 5.83 390.6 490.48 G
0 X
90 450 6.86 5.83 390.6 490.48 A
399.59 490.48 495.7 490.48 2 L
N
2 X
90 450 6.87 5.83 498.94 490.48 G
0 X
90 450 6.87 5.83 498.94 490.48 A
(\050c\051) 318.3 252.75 T
126.68 109.74 523.24 167.06 R
7 X
V
3 F
0 X
0.66 (Figure 34:) 126.68 159.06 P
2 F
0.66 (Thr) 183.97 159.06 P
0.66 (ee types of competitive \336tness functions. \050a\051 Full competition used) 200.85 159.06 P
3.84 (in Axelr) 126.68 147.06 P
3.84 (od \0501989\051; \050b\051 Bipartite competition used in Hillis \0501992\051; and \050c\051) 168.38 147.06 P
0.92 (T) 126.68 135.06 P
0.92 (ournament \336tness with each horizontal line designating a competition and each) 132.24 135.06 P
(upwar) 126.68 123.06 T
(d arr) 156.89 123.06 T
(ow designating the winner pr) 180.77 123.06 T
(ogr) 320.92 123.06 T
(essing in the tournament.) 337.14 123.06 T
0 F
(\050a\051) 228.72 459.99 T
389.7 283.11 402.04 283.11 2 L
N
368.41 319.23 378.49 319.23 2 L
N
497.81 308.23 500.81 313.43 503.81 308.23 500.81 308.23 4 Y
V
500.81 288.65 500.81 308.23 2 L
N
426.38 308.23 429.38 313.43 432.38 308.23 429.38 308.23 4 Y
V
429.38 287.82 429.38 308.23 2 L
N
382.83 306.85 385.83 312.05 388.83 306.85 385.83 306.85 4 Y
V
385.83 288.65 385.83 306.85 2 L
N
358.44 309.06 361.44 314.26 364.44 309.06 361.44 309.06 4 Y
V
361.44 287.82 361.44 309.06 2 L
N
310.53 309.06 313.53 314.26 316.53 309.06 313.53 309.06 4 Y
V
313.53 288.65 313.53 309.06 2 L
N
264.36 307.42 267.36 312.61 270.36 307.42 267.36 307.42 4 Y
V
267.36 287.82 267.36 307.42 2 L
N
192.06 307.42 195.06 312.61 198.06 307.42 195.06 307.42 4 Y
V
195.06 287.82 195.06 307.42 2 L
N
145.9 306.59 148.89 311.78 151.89 306.59 148.89 306.59 4 Y
V
148.89 287.82 148.89 306.59 2 L
N
497.81 342.12 500.81 347.32 503.81 342.12 500.81 342.12 4 Y
V
500.81 324.17 500.81 342.12 2 L
N
382.83 342.12 385.83 347.32 388.83 342.12 385.83 342.12 4 Y
V
385.83 324.17 385.83 342.12 2 L
N
263.49 340.47 266.49 345.66 269.49 340.47 266.49 340.47 4 Y
V
266.49 322.53 266.49 340.47 2 L
N
193.8 340.47 196.8 345.66 199.8 340.47 196.8 340.47 4 Y
V
196.8 322.53 196.8 340.47 2 L
N
193.8 373.53 196.8 378.72 199.8 373.53 196.8 373.53 4 Y
V
196.8 357.23 196.8 373.53 2 L
N
383.7 374.35 386.7 379.54 389.7 374.35 386.7 374.35 4 Y
V
386.7 356.41 386.7 374.35 2 L
N
384.57 410.71 387.57 415.91 390.57 410.71 387.57 410.71 4 Y
V
387.57 390.29 387.57 410.71 2 L
N
0 0 612 792 C
FMENDPAGE
%%EndPage: "131" 8
%%Page: "132" 8
612 792 0 FMBEGINPAGE
108 63 540 702 R
7 X
0 K
V
108 711 540 720 R
V
0 12 Q
0 X
(132) 522.01 712 T
108 90 540 702 R
7 X
V
0 X
0.19 (complex and requires a lar) 108 694 P
0.19 (ge population or a signi\336cant number of generations, this num-) 235.78 694 P
(ber of competitions per generation may be prohibitive.) 108 676 T
0.41 (Unfortunately) 126 646 P
0.41 (, Axelrod\325) 192.5 646 P
0.41 (s experimental goal was to encourage cooperation on the task) 241.55 646 P
-0.27 (rather than discourage cooperative stable states. Axelrod\325) 108 628 P
-0.27 (s experiments attempted to deter-) 381.18 628 P
0.22 (mine if a cooperative strategy for the Iterated Prisoner) 108 610 P
0.22 (\325) 370.01 610 P
0.22 (s Dilemma could evolve from ran-) 373.34 610 P
0.66 (dom initial conditions in the population. Because each member of the population always) 108 592 P
1.33 (competes against every other member of the population, there is ample opportunity for) 108 574 P
1.47 (reciprocation between dif) 108 556 P
1.47 (fering strategies. In fact, it was exactly this reciprocation that) 233.29 556 P
0.71 (Axelrod was interested in inducing. Thus, when the object is to avoid cooperative stable) 108 538 P
(states, a full competition may af) 108 520 T
(fect the search adversely) 261.68 520 T
(.) 379.12 520 T
1 F
(7.2.2.2  Hillis\325 Bipartite Competitive Model) 108 484 T
0 F
-0.07 (Hillis \0501992\051 demonstrates a competitive \336tness function with an interesting approach.) 126 458 P
0.21 (The problem explored in Hillis \0501992\051 is to evolve a sorting network for any arrangement) 108 440 P
0.87 (of 16 integers with as few element exchanges as possible. Notice that this task is not so) 108 422 P
-0.09 (dif) 108 404 P
-0.09 (ferent from a game; the sorting networks represent various strategies and the 16! poten-) 121.11 404 P
0.86 (tial arrangements of integers represent the various board con\336gurations. Clearly) 108 386 P
0.86 (, using a) 497.98 386 P
0.05 (\336tness function that tests all possible permutations on each sorting network is impractical.) 108 368 P
1.07 (Additionally) 108 350 P
1.07 (, a static subset of permutations would clearly encourage solutions that sort) 167.86 350 P
-0.05 (only the chosen subset. Hillis \0501992\051 reports that even using a randomly selected subset of) 108 332 P
0.8 (permutations that changes every generation does not provide a suf) 108 314 P
0.8 (\336cient environment to) 432.45 314 P
(evolve adequate sorting networks.) 108 296 T
0.37 (In order to maintain a consistently dif) 126 266 P
0.37 (\336cult set of permutations to evaluate the sorting) 308.55 266 P
0.53 (networks, Hillis \0501992\051 creates a second population. Each member of the second popula-) 108 248 P
0.15 (tion encodes a small set of permutations of integers to be sorted by one of the sorting net-) 108 230 P
0.38 (works of the \336rst population. In this experiment) 108 212 P
2 F
0.38 (both) 343.26 212 P
0 F
0.38 ( populations evolve from generation) 364.58 212 P
0.2 (to generation. Fitness for the population of sorting networks is de\336ned to be how well the) 108 194 P
0.14 (member sorts the various permutations within the associated member of the second popu-) 108 176 P
0.7 (lation. The \336tness of a member in the second population is a measure of how) 108 158 P
2 F
0.7 (poorly) 490.33 158 P
0 F
0.7 ( the) 521.64 158 P
-0.29 (sorting network sorts the set of permutations it contains. This bipartite competition is illus-) 108 140 P
0.75 (trated in Figure 34b. W) 108 122 P
0.75 (ith this \336tness function, Hillis\325 system evolved a sorting network) 222.77 122 P
FMENDPAGE
%%EndPage: "132" 9
%%Page: "133" 9
612 792 0 FMBEGINPAGE
108 63 540 702 R
7 X
0 K
V
108 711 540 720 R
V
0 12 Q
0 X
(133) 522.01 712 T
108 90 540 702 R
7 X
V
0 X
0.81 (with only 61 position exchanges, which is a single exchange worse than the best known) 108 694 P
(sorting network for 16 numbers.) 108 676 T
0.76 (Assuming the sizes of the populations are the same and when combined equal) 126 646 P
2 F
0.76 (n) 512.59 646 P
0 F
0.76 (, the) 518.59 646 P
-0.29 (bipartite competition in Hillis \0501992\051 uses a total of) 108 628 P
2 F
-0.29 (n) 354.94 628 P
0 F
-0.29 (/2 competitions each generation. This) 360.93 628 P
-0.12 (is far fewer than a full competition, as in Axelrod \0501987\051. However) 108 610 P
-0.12 (, while the \336tness func-) 428.24 610 P
1.93 (tion used in Hillis \0501992\051 is an example of a competitive \336tness function, there is no) 108 592 P
0.54 (method for determining which member of the population is the best sorter) 108 574 P
0.54 (. Because each) 468 574 P
1.12 (sorting network competes against a single member of the second population there is no) 108 556 P
0.08 (basis of comparison) 108 538 P
2 F
0.08 (between) 207.16 538 P
0 F
0.08 ( sorting networks. The score received by a sorting network is) 246.46 538 P
0.99 (relative to the dif) 108 520 P
0.99 (\336culty of permutations it attempted and each sorting network sees dis-) 193.02 520 P
0.56 (tinct sets of permutations. In addition, the bipartite nature of the competition model used) 108 502 P
(in Hillis \0501992\051 may be unnatural for some problems.) 108 484 T
0.52 (Pitting evolving members of a population against each other to determine \336tness cre-) 126 454 P
0.72 (ates an interesting tension in evolutionary algorithms. For instance, while the population) 108 436 P
1.49 (of sorting networks in Hillis \0501992\051 is adapting to the speci\336c permutations it is being) 108 418 P
0.47 (tested against, the population of permutations is searching for the set that forces the sort-) 108 400 P
0.73 (ing networks to perform as badly as possible. In order for the sorting networks to repro-) 108 382 P
0.34 (duce from generation to generation consistently) 108 364 P
0.34 (, they must generalize their sorting ability) 337.75 364 P
0.71 (rather than encode for a speci\336c subset of permutations. The need to compensate for the) 108 346 P
(continuing diversity in the permutations directs generalization in the sorting networks.) 108 328 T
1.15 (Hillis\325 bipartite model for competition does not remove the bias toward cooperative) 126 298 P
-0.07 (stable states. Consider a population as a single, very complex learner comprised of a num-) 108 280 P
0.2 (ber of homogeneous components, and, as in Samuel\325) 108 262 P
0.2 (s \0501959\051 competitive learner) 362.26 262 P
0.2 (, the two) 497.95 262 P
0.92 (populations as a single learner) 108 244 P
0.92 (. At this level, Hillis\325 system is just an implementation of) 256.26 244 P
0.03 (standard competition with a more complicated learner) 108 226 P
0.03 (. Therefore, similar to above, Hillis\325) 366.65 226 P
1.08 (learner seeks out cooperative stable) 108 208 P
2 F
1.08 ( populations) 282.83 208 P
0 F
1.08 (, i.e. populations that, on average, don\325) 343.55 208 P
1.08 (t) 536.67 208 P
1.47 (force each other to change signi\336cantly) 108 190 P
1.47 (. The entire population need not be involved to) 303.41 190 P
-0.13 (slow learning, only enough to make the current population relatively stable with respect to) 108 172 P
0.4 (itself. Thus, a population of learners alone is insuf) 108 154 P
0.4 (\336cient to inhibit cooperation. Note that) 351.46 154 P
(this type of cooperation was the object of Axelrod\325) 108 136 T
(s \0501987\051 experiments.) 351.83 136 T
FMENDPAGE
%%EndPage: "133" 10
%%Page: "134" 10
612 792 0 FMBEGINPAGE
108 63 540 702 R
7 X
0 K
V
108 711 540 720 R
V
0 12 Q
0 X
(134) 522.01 712 T
108 90 540 702 R
7 X
V
1 F
0 X
(7.3  T) 108 694 T
(ournament Fitness) 135.88 694 T
0 F
1.6 (This section describes) 126 670 P
2 F
1.6 (tournament \336tnes) 239.73 670 P
0 F
1.6 (s, a third model of competition in a \336tness) 324.95 670 P
-0.04 (function that addresses the problem of cooperative stable states. T) 108 652 P
-0.04 (ournament \336tness uses a) 423.2 652 P
0.16 (single elimination, binary tournament to determine a relative \336tness ranking for the popu-) 108 634 P
0.97 (lation. Initially) 108 616 P
0.97 (, the entire population is in the tournament. T) 179.49 616 P
0.97 (wo members are selected at) 403.58 616 P
-0.21 (random to compete against each other with only the winner of the competition progressing) 108 598 P
-0.09 (to the next level of the tournament. Once all the \336rst level competitions are completed, the) 108 580 P
0.28 (winners are randomly paired to determine the next level winners. The tournament contin-) 108 562 P
1.31 (ues until a single winner remains The \336tness of a member of the population is then its) 108 544 P
0.05 (height in the playof) 108 526 P
0.05 (f tree, the player at the top being the best player of the generation. The) 201.55 526 P
0.51 (competitive pairings for tournament \336tness are illustrated in Figure 34c. The hierarchical) 108 508 P
1.21 (nature of the ranking is strictly enforced, ties being broken by random selection. In the) 108 490 P
-0.21 (case that the number of competitors at a level is odd, a single population member is passed) 108 472 P
-0.18 (to the next level of the tournament without a competition, ef) 108 454 P
-0.18 (fectively receiving a \322bye\323 for) 394.84 454 P
(that round. The total number of competitions for a population of size) 108 436 T
2 F
(n) 440.78 436 T
0 F
( is:) 446.78 436 T
0 10 Q
(\050EQ 25\051) 507.53 391.03 T
0 12 Q
2.1 (which is one fewer comparison than) 108 341.79 P
2.1 (required to play each member of the population) 297.13 341.79 P
(against a single \322expert\323 strategy in a comparable independent \336tness function.) 108 323.79 T
0.78 (Quanti\336cation of performance on the task is unimportant when using tournament \336t-) 126 293.79 P
0.51 (ness; all that is required is a concept of \322better\323 to compare two strategies. This removes) 108 275.79 P
-0.09 (all need for determining exactly how much better one player is than another - the resulting) 108 257.79 P
1.13 (tournament hierarchy is suf) 108 239.79 P
1.13 (\336cient information for reproduction. Unless the competition,) 242.74 239.79 P
-0.21 (i.e., the measure of \322better\323, is noisy) 108 221.79 P
-0.21 (, an optimal player always wins the tournament. How-) 281.17 221.79 P
0.45 (ever) 108 203.79 P
0.45 (, if the environment is suitably complex and an optimal strategy is not in the popula-) 128.16 203.79 P
2.69 (tion, it is possible for an average or even a comparatively poor strategy to win the) 108 185.79 P
-0.28 (tournament for a particular generation. Thus this competitive \336tness function can contain a) 108 167.79 P
0.19 (level of noise associated with its ability to rank any given population. How accurately the) 108 149.79 P
2.99 (tournament ranks the population is dependent upon the set of competitors met. For) 108 131.79 P
0.91 (instance, if the best player in the population competes in the initial round of the tourna-) 108 113.79 P
253.58 373.79 361.95 414 C
2 12 Q
0 X
0 K
(n) 303.31 395.5 T
0 F
(2) 301.83 377.75 T
2 9 Q
(i) 308.29 382.89 T
(i) 265.24 376.74 T
0 F
(1) 278.67 376.74 T
4 F
(=) 270.74 376.74 T
2 F
(n) 278.45 406.85 T
4 F
(\050) 274.57 406.85 T
(\051) 283.34 406.85 T
0 F
(l) 260.58 406.85 T
(o) 263.08 406.85 T
(g) 267.57 406.85 T
4 18 Q
(\345) 267.79 387.83 T
2 12 Q
(n) 336.37 391.03 T
0 F
(1) 354.95 391.03 T
4 F
(-) 345.37 391.03 T
(=) 323.79 391.03 T
301.83 391.03 310.54 391.03 2 L
0.33 H
0 Z
N
295.83 376.14 295.83 403.71 2 L
N
295.83 403.71 298.83 403.71 2 L
N
315.79 376.14 315.79 403.71 2 L
N
315.79 403.71 312.79 403.71 2 L
N
255.58 404.86 255.58 413 2 L
N
255.58 413 258.58 413 2 L
N
291.83 404.86 291.83 413 2 L
N
291.83 413 288.83 413 2 L
N
0 0 612 792 C
FMENDPAGE
%%EndPage: "134" 11
%%Page: "135" 11
612 792 0 FMBEGINPAGE
108 63 540 702 R
7 X
0 K
V
108 711 540 720 R
V
0 12 Q
0 X
(135) 522.01 712 T
108 90 540 702 R
7 X
V
0 X
0.54 (ment with the second best member) 108 694 P
0.54 (, only the best player moves up the hierarchy with the) 277.11 694 P
(second best player being assigned the minimal \336tness.) 108 676 T
-0.11 (Fortunately) 126 646 P
-0.11 (, the inherent noise of tournament \336tness functions is not a serious problem) 180.52 646 P
0.64 (given that the \336tness ranking is being created to decide the proportions for reproduction.) 108 628 P
-0.03 (Consider that the worth of a single competition, in terms of reproduction, is inversely pro-) 108 610 P
-0.12 (portional to how high in the tournament the competition occurs. In other words, the higher) 108 592 P
0.93 (the level of the competition, the less it is worth in terms of reproductive advantage. For) 108 574 P
1.38 (example, consider a single competition in the initial round of the tournament. The \336rst) 108 556 P
0.77 (competition determines which half of the rankings the two competitors reside. The loser) 108 538 P
0.29 (receives a \336tness that places it in the lowest 50% of the population\325) 108 520 P
0.29 (s ranking. The winner) 433.89 520 P
-0.27 (earns a \336tness value at least in the upper 50% which gives it a reasonable chance for repro-) 108 502 P
0.61 (ducing. W) 108 484 P
0.61 (ith each successive round of competitions, exponentially decreasing subsets of) 158.1 484 P
2.58 (the population are divided into winners and losers until the last competition decides) 108 466 P
0.1 (between best and second best for the generation. At this level, the dif) 108 448 P
0.1 (ference in the proba-) 440.12 448 P
(bility of reproducing is negligeable with any reasonably sized population.) 108 430 T
0.28 (Once a tournament has been run, any standard selection method can be used to desig-) 126 400 P
0.86 (nate parents for the next generation. Because all the population members that lost at the) 108 382 P
-0.28 (same level of the tournament have the same \336tness values, tournament \336tness naturally de-) 108 364 P
0.8 (emphasizes their worth relative to each other) 108 346 P
0.8 (. This is more bene\336cial than over) 327.27 346 P
0.8 (-commit-) 495.36 346 P
1.85 (ting to an erroneous complete ordering of the population. Selecting between members) 108 328 P
0.4 (with the same \336tness must be at random which promotes better mixing of the representa-) 108 310 P
0.19 (tional components when using crossover and discourages premature conver) 108 292 P
0.19 (gence. In fact,) 471.69 292 P
0.08 (in many situations tournament \336tness naturally discourages conver) 108 274 P
0.08 (gence since as a partic-) 428.46 274 P
1.89 (ular strategy becomes too numerous it is forced to literally compete against copies of) 108 256 P
0.54 (itself. This is akin to a predator/prey system wher