chapter6.ps

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

0.33 (T) 126 494 P
0.33 (o of) 132.49 494 P
0.33 (fset the loss of diversity in the population due to the application of the compres-) 151.59 494 P
0.68 (sion operator) 108 476 P
0.68 (, GLiB provides an additional mutation operator) 171.15 476 P
0.68 (. When applied, the) 406.07 476 P
2 F
0.68 (expand) 505.36 476 P
0 F
-0.21 (operator searches the parent for all modules at the top level and selects one at random. The) 108 458 P
0.91 (chosen module name is then replaced by its de\336nition stored in the genetic library) 108 440 P
0.91 (. This) 511.77 440 P
0.73 (reintroducing the previously removed genetic material. The expansion process is exactly) 108 422 P
0.57 (the reverse of compression. A copy of the module\325) 108 404 P
0.57 (s de\336nition from the genetic library is) 355.37 404 P
1.47 (expanded by replacing all occurrences of parameters with the bindings speci\336ed in the) 108 386 P
-0.1 (genotype\325) 108 368 P
-0.1 (s call to the module. GLiB then splices the expanded subtree back into the geno-) 155.3 368 P
0.62 (type. One could literally reverse the directions of the arrows in Figure 24, Figure 25 and) 108 350 P
1.09 (Figure 26 as illustrations.Because mutations are executed locally in an individual, other) 108 332 P
(population members which also refer to the module being expanded are not af) 108 314 T
(fected.) 482.17 314 T
1 F
(6.2.3  Non-monotonic Formation of Hierar) 108 278 T
(chical Decompositions) 325.31 278 T
0 F
1.57 (A hierarchical decomposition forms in GLiB when a subtree containing an already) 126 252 P
1.01 (compressed module is itself compressed. W) 108 234 P
1.01 (ith continual manipulation of the individual,) 323.08 234 P
0.49 (the hierarchy deepens and widens. Because expansion only works on the highest level of) 108 216 P
1.16 (modules in an individual, modules further down the hierarchy are protected from being) 108 198 P
0.77 (expanded and further manipulated. Thus the problem is decomposed from the bottom of) 108 180 P
-0.26 (the hierarchy towards the top as a natural consequence of the dynamics of the compression) 108 162 P
(and expansion operators.) 108 144 T
2.42 (The combination of the compression and expansion mutations allow for the non-) 126 114 P
0.33 (monotonic development of the task decomposition. The random identi\336cation of subtrees) 108 96 P
FMENDPAGE
%%EndPage: "110" 8
%%Page: "111" 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
(1) 522.9 712 T
(1) 528.45 712 T
(1) 534 712 T
108 90 540 702 R
7 X
V
0 X
0.15 (to compress provides no guarantee that a compressed module is bene\336cial to the develop-) 108 694 P
0.2 (ing genotypes in its initial form. It could be that the acquired module contains only a por-) 108 676 P
0.35 (tion of a useful subtree, a useful subtree along with some extraneous additions, or simply) 108 658 P
0.15 (nothing of import. The original subtree\325) 108 640 P
0.15 (s replacement by an expansion operation provides) 299.29 640 P
-0.06 (the chance to capture a better version of the module in a later compression. For instance, a) 108 622 P
0.67 (compressed module can be created and the genetic program can evolve further using the) 108 604 P
0.61 (compressed module. Once further re\336nement is made to the program, the module can be) 108 586 P
1.41 (expanded and modi\336ed. Such non-monotonic manipulations of hierarchical decomposi-) 108 568 P
(tions may be indispensable when solving complex problems.) 108 550 T
1 F
(6.2.4  Evaluation of Modules) 108 514 T
0 F
0.96 (Randomly compressing subtrees from the genotypes does not guarantee useful addi-) 126 488 P
0.28 (tions to the representation language that bene\336t the evolutionary process. It is not enough) 108 470 P
0.51 (to de\336ne modules without an appropriate mechanism to judge and discard them if neces-) 108 452 P
0.86 (sary) 108 434 P
0.86 (. One appropriate criterion for an evolved module is to examine the number of calls) 127.2 434 P
-0.05 (made to it in the subsequent generations \050Bedau and Packard 1992\051. If the population uses) 108 416 P
0.47 (a module frequently then it must provide some consistent bene\336cial behavior in previous) 108 398 P
(generations.) 108 380 T
0.26 (The only way that a compressed module can be propagated in GLiB is through repro-) 126 350 P
1.38 (duction and crossover) 108 332 P
1.38 (. A module is not added explicitly to the global primitives of the) 215.34 332 P
1.58 (genetic program since this would increase the number of global primitives greatly and) 108 314 P
0.3 (af) 108 296 P
0.3 (fect performance. Thus any mutation operator that generates a random subtree from the) 117.1 296 P
2.66 (available primitives does not insert a dynamically de\336ned module. Compression and) 108 278 P
2.38 (expansion are local manipulations in that they af) 108 260 P
2.38 (fect only the genetic program being) 357.25 260 P
(mutated.) 108 242 T
0.15 (As an added bene\336t, the constrained propagation of compressed modules provides the) 126 212 P
0.87 (foundation for their evaluation as a by-product of the dynamics of the evolutionary pro-) 108 194 P
0.66 (cess. Once a subtree is compressed, no further manipulation of the module\325) 108 176 P
0.66 (s contents by) 476.04 176 P
-0.08 (crossover or other mutations is permitted until an expansion restores it. If the compression) 108 158 P
-0.03 (protects a subtree that is a bene\336cial decomposition, meaning that it solves some subprob-) 108 140 P
0.04 (lem of the task suf) 108 122 P
0.04 (\336ciently) 196.56 122 P
0.04 (, then the presence of the module contributes to the overall suc-) 235.1 122 P
1.41 (cess of the program on the task. If the program\325) 108 104 P
1.41 (s \336tness is high compared to the other) 348.55 104 P
FMENDPAGE
%%EndPage: "111" 9
%%Page: "112" 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
(1) 522.45 712 T
(12) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
0.12 (population members, it produces children that also contain the module. As long as a com-) 108 694 P
1.57 (pressed module provides an evolutionary advantage to the members that contain refer-) 108 676 P
1.92 (ences to it, or at least does not inhibit their reproductive success, the module spreads) 108 658 P
1.75 (through the population. If, however) 108 640 P
1.75 (, a module protects a subtree that is detrimental to) 285.07 640 P
0.41 (solving the problem, it eventually becomes a liability to each of) 108 622 P
0.41 (fspring that uses it, limit-) 417.4 622 P
-0.15 (ing the \336tness of the individual. Eventually) 108 604 P
-0.15 (, all individuals relying on the malformed mod-) 313.2 604 P
(ule disappear from the population through attrition.) 108 586 T
0.67 (Modules that survive over several generations and become entrenched in the popula-) 126 556 P
0.61 (tion are termed) 108 538 P
2 F
0.61 (evolutionarily viable) 185.45 538 P
0 F
0.61 ( \050Angeline and Pollack 1992\051. In this case, a bene\336-) 285.67 538 P
1.71 (cial module is \322induced\323 when more and more of the population relies on its content.) 108 520 P
0.97 (Often bene\336cial modules spread through the population very quickly so that their usage) 108 502 P
0.04 (grows dramatically) 108 484 P
0.04 (. Such quick proliferations are indicative of phase changes that Pollack) 199.52 484 P
(\0501991\051 suggests are a form of induction in complex systems including human cognition.) 108 466 T
0.02 (A module is evaluated dynamically by how useful it is to the population members that) 126 436 P
0.79 (use it or contain a reference to it. The global worth of a particular compression emer) 108 418 P
0.79 (ges) 524.01 418 P
0.06 (from the local interactions of a population with the \336tness function and each other) 108 400 P
0.06 (. Such a) 501.57 400 P
0.26 (usage centered method for evaluation of modules is a result of the opportunistic nature of) 108 382 P
(emer) 108 364 T
(gent intelligent techniques.) 131.76 364 T
1 F
(6.2.5  The Emergence of High-Level Repr) 108 328 T
(esentations) 320.31 328 T
0 F
-0.17 (GLiB\325) 126 302 P
-0.17 (s compression operator introduces a new dynamic into the evolutionary process:) 156.65 302 P
0.39 (the evolution of the representational language. Each compressed module extends the rep-) 108 284 P
1.44 (resentational language of the genotypes, like a library of functions extends a particular) 108 266 P
1.06 (programming language. Since the new modules are constructed from the primitives and) 108 248 P
0.95 (modules already in the representation language, they are necessarily at a higher level of) 108 230 P
(abstraction. If they are evolutionarily viable and) 108 212 T
1.7 (One of the most important aspects of GLiB and its emer) 126 182 P
1.7 (gent modules is that each) 411.94 182 P
1.33 (module is an abstraction away from the primitive language of the genetic program and) 108 164 P
-0.13 (towards a task-speci\336c language that is more conducive to solving the problem. Much like) 108 146 P
1.36 (the progression of computer languages from machine code to high-level languages, the) 108 128 P
0.41 (dynamics in GLiB allow increasingly general abstractions to form and be tested for solv-) 108 110 P
FMENDPAGE
%%EndPage: "112" 10
%%Page: "113" 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
(1) 522.45 712 T
(13) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
-0.28 (ing the problem. Because the dynamics of GLiB propagates only those abstractions that do) 108 694 P
0.38 (not inhibit the evolution of better solutions to the problem, the resulting high-level repre-) 108 676 P
0.78 (sentations in GLiB are necessarily task-speci\336c. However) 108 658 P
0.78 (, like the solutions themselves,) 389.64 658 P
(these abstractions are highly opportunistic and consequently dif) 108 640 T
(\336cult to describe.) 413.24 640 T
1 F
(6.2.6  T) 108 604 T
(ask-Speci\336c Featur) 144.88 604 T
(e Acquisition) 242.94 604 T
0 F
2.24 (The automatic acquisition of task-speci\336c features is a problem \336rst described by) 126 578 P
0.46 (Samuel \0501966; 1959\051. In his classic checker program, Samuel demonstrated how to use a) 108 560 P
1.39 (variety of knowledge sources, including books, humans and other programs, to teach a) 108 542 P
1.57 (program how to play checkers at a moderate level. In order to represent an evaluation) 108 524 P
-0.19 (function for the program, Samuel chose several sets of features to describe the positions of) 108 506 P
1.41 (the pieces on the board. The evaluation function combined these binary features into a) 108 488 P
0.23 (sum with coef) 108 470 P
0.23 (\336cients to designate their relative importance. Samuel \0501959; 1966\051 learned) 176.2 470 P
2.12 (the coef) 108 452 P
2.12 (\336cients of the equation from examples of expert checker play using a simple) 148.2 452 P
2.43 (update rule. Samuel lamented the dif) 108 434 P
2.43 (\336culty of determining suf) 296.47 434 P
2.43 (\336cient features to ade-) 425.8 434 P
1.42 (quately represent the checker board and described his desire to acquire them automati-) 108 416 P
(cally) 108 398 T
(.) 130.54 398 T
0.78 (The dif) 126 368 P
0.78 (\336culty of determining a best set of features for checkers, or many other com-) 161.53 368 P
-0.24 (plex tasks, is that there may be no objective set of features that are suf) 108 350 P
-0.24 (\336cient for evaluating) 440.55 350 P
-0.03 (every move of every game. Samuel \0501966\051 understood this and began using multiple eval-) 108 332 P
-0.29 (uation functions: one for moves early in the game, one for the middle game and one for the) 108 314 P
(end game. However) 108 296 T
(, in each evaluation function, the same features are used.) 203.77 296 T
0.51 (The salient features for representing a solution for a complex task are not necessarily) 126 266 P
0.89 (static and objectively de\336nable. Appropriate features are dependent not only on the task) 108 248 P
1.18 (but on the current state of solving the task and even the current instance of solving the) 108 230 P
0.42 (task. For instance, in a game, the salient features of the board change from the beginning) 108 212 P
0.68 (of a game to the end. In backgammon, once all of one player) 108 194 P
0.68 (\325) 407.71 194 P
0.68 (s pieces are in the \322home\323) 411.04 194 P
0.27 (area, most features of the board that were crucial at the beginning of play are obsolete. In) 108 176 P
1.19 (addition, an expert backgammon player may use a dif) 108 158 P
1.19 (ferent set of features for dif) 374.76 158 P
1.19 (ferent) 512.03 158 P
1.89 (players based on perceived ability and past experience. Thus the features required for) 108 140 P
(solving a complex task often require a similar dynamic.) 108 122 T
FMENDPAGE
%%EndPage: "113" 11
%%Page: "114" 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
(1) 522.45 712 T
(14) 528.01 712 T
108 90 540 702 R
7 X
V
1 F
0 X
(6.3  Generality of Emergent Modules) 108 694 T
0 F
0.32 (GLiB\325) 126 670 P
0.32 (s form of emer) 156.65 670 P
0.32 (gent module de\336nition is general across all evolutionary compu-) 228.33 670 P
0.71 (tations since it relies only on empirical credit assignment that is a natural dynamic in all) 108 652 P
-0.18 (evolutionary weak methods. For instance, the previous chapter demonstrated that a variant) 108 634 P
1.96 (of compression and expansion, called) 108 616 P
2 F
1.96 (fr) 300.98 616 P
1.96 (eeze) 308.54 616 P
0 F
1.96 ( and) 329.18 616 P
2 F
1.96 (unfr) 356.41 616 P
1.96 (eeze) 375.96 616 P
0 F
1.96 (, speed-up the acquisition of) 396.6 616 P
0.02 (\336nite state machines \050FSMs\051 in a evolutionary program. Similar methods could be used in) 108 598 P
(genetic algorithms and evolution strategies.) 108 580 T
1 F
(6.4  Comparison to Koza\325) 108 544 T
(s ADFs) 238.48 544 T
0 F
2.83 (Koza \0501992\051 also describes a method for constructing modular genetic programs) 126 520 P
0.36 (which he calls) 108 502 P
2 F
0.36 (automatically de\336ned functions) 180.68 502 P
0 F
0.36 ( \050ADFs\051. In his method, the decomposition) 331.98 502 P
1.28 (of the program is designed prior to evolving the genetic programs, each ADF having a) 108 484 P
0.87 (unique primitive language that is speci\336ed by the programmer) 108 466 P
0.87 (. Each individual contains) 412.79 466 P
1.35 (its own local de\336nition of the designed functions. Unlike GLiB\325) 108 448 P
1.35 (s modules, when using) 426.67 448 P
0.82 (ADFs the individual\325) 108 430 P
0.82 (s functions are initialized to be random and are evolved along with) 210.92 430 P
0.18 (the individual by an occasional crossover operation with another individual\325) 108 412 P
0.18 (s local de\336ni-) 474.35 412 P
-0.14 (tion. Eventually) 108 394 P
-0.14 (, an individual and its ADFs settle into a complete solution to the problem.) 183.71 394 P
0.27 (While the de\336nition of each individual ADF is emer) 126 364 P
0.27 (gent, the hierarchy of modularity) 378.47 364 P
0.27 (,) 537 364 P
2.08 (including the number of parameters to each module, is necessarily static. This makes) 108 346 P
0.42 (ADFs a special case of applying GP at several levels in parallel. If explicit knowledge of) 108 328 P
-0.29 (the solution\325) 108 310 P
-0.29 (s decomposition is available, then it is better to allow only the de\336nition of the) 167.35 310 P
0.31 (functions to emer) 108 292 P
0.31 (ge as in ADFs. Systems with more emer) 192.35 292 P
0.31 (gent components are more gen-) 387.54 292 P
0.87 (eral. Therefore, because GLiB allows both the hierarchy and the de\336nitions of the func-) 108 274 P
2.81 (tions to emer) 108 256 P
2.81 (ge from the dynamics of the systems, GLiB\325) 176.02 256 P
2.81 (s method of creating task) 408.2 256 P
0.59 (decompositions is more general than ADF) 108 238 P
0.59 (. As is always true, if one system is more gen-) 312.88 238 P
0.54 (eral than another then the less general algorithm often has certain other advantages. Kin-) 108 220 P
(near \0501994b\051 describes such an advantage for ADFs.) 108 202 T
3.23 (The emer) 126 172 P
3.23 (gence of high-level representational abstractions is the chief dif) 174.64 172 P
3.23 (ference) 504.71 172 P
0.55 (between GLiB and Koza\325) 108 154 P
0.55 (s ADFs. Where GLiB is dynamic in its pursuit of all aspects of) 231.89 154 P
0.23 (the hierarchical structure for a particular task, the pre-speci\336cation of hierarchical or) 108 136 P
0.23 (gani-) 515.35 136 P
0.09 (zation of ADFs forces them to create the same modularity each time, although the seman-) 108 118 P
2.65 (tics of the individual functions may be dif) 108 100 P
2.65 (ferent. While the de\336nitions of ADFs are) 327.23 100 P
FMENDPAGE
%%EndPage: "114" 12
%%Page: "115" 12
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
(1) 522.45 712 T
(15) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
-0.28 (emer) 108 536.5 P
-0.28 (gent, their or) 131.76 536.5 P
-0.28 (ganization is not. This leads to the conclusion that while ADFs can allow) 192.6 536.5 P
0.85 (modular or) 108 518.5 P
0.85 (ganizations to emer) 161.6 518.5 P
0.85 (ge, they cannot allow higher) 257.02 518.5 P
0.85 (-level abstractions to emer) 396.43 518.5 P
0.85 (ge.) 525.68 518.5 P
-0.25 (Both the hierarchical or) 108 500.5 P
-0.25 (ganization and the semantics of each level of the hierarchy must be) 220.62 500.5 P
(manipulated to avoid limiting the or) 108 482.5 T
(ganization of the developing individuals.) 280.69 482.5 T
1 F
(6.5  The Emergence of Envir) 108 446.5 T
(onment Speci\336c Modules) 254.36 446.5 T
0 F
0.94 (In this section, we present experiments illustrating some of the properties of GLiB\325) 126 422.5 P
0.94 (s) 535.33 422.5 P
-0.21 (evolved programs and their associated modules. In the \336rst set of experiments, designed to) 108 404.5 P
0.5 (provide initial insights into the nature of an evolved high-level representation, GLiB cre-) 108 386.5 P
-0.17 (ated programs to solve the familiar T) 108 368.5 P
-0.17 (ower of Hanoi problem. These results permit analysis) 284.03 368.5 P
1.06 (of the properties of evolved modularity) 108 350.5 P
1.06 (. The second experiment takes a more ambitious) 300.73 350.5 P
0.6 (track. A general primitive language is used to evolve programs to play and beat an auto-) 108 332.5 P
0.34 (mated T) 108 314.5 P
0.34 (ic-T) 147.56 314.5 P
0.34 (ac-T) 166.7 314.5 P
0.34 (oe opponent. The experiments show GLiB preserves important schemata) 187.84 314.5 P
0.06 (in the created modules while highlighting some additional unexpected features of evolved) 108 296.5 P
(modular programs.) 108 278.5 T
1 F
(6.5.1  T) 108 242.5 T
(ower of Hanoi Experiments) 144.88 242.5 T
0 F
0.37 (Initial experiments with GLiB evolved solutions for the classic T) 126 216.5 P
0.37 (ower of Hanoi prob-) 440.64 216.5 P
1.25 (lem. This puzzle consists of three pegs, labeled by position, and several uniquely sized) 108 198.5 P
0.13 (disks. The initial state has all disks on the \336rst peg such that no disk is on top of a smaller) 108 180.5 P
0.87 (disk. The goal is to reconstruct the tower of the initial con\336guration on the third peg by) 108 162.5 P
(moving the disks, one at a time, such that a lar) 108 144.5 T
(ger disk never rests on a smaller disk.) 330.31 144.5 T
0.1 (The primitive language for the genotypes included the six possible moves from peg to) 126 114.5 P
0.21 (peg shown in Figure 27. Each primitive moves the top disk from one peg and places it on) 108 96.5 P
128.81 544.5 519.19 702 C
142.31 563.06 502.31 590.06 R
7 X
0 K
V
3 12 Q
0 X
2.81 (Figure 27:) 142.31 582.06 P
2 F
2.81 (Primitive language for T) 203.91 582.06 P
2.81 (ower of Hanoi experiments. Each) 330.18 582.06 P
(command moves a single disk between the speci\336ed pegs.) 142.31 570.06 T
0.5 H
2 Z
0 90 7.46 20.6 285.6 671.76 A
283.2 683.72 278.13 671.76 276.09 684.59 279.64 684.15 4 Y
V
90 143 7.46 20.6 285.6 671.76 A
293.06 640.86 296.79 671.76 R
N
311.7 640.86 315.43 671.76 R
N
274.41 640.86 278.14 671.76 R
N
270.68 630.56 319.16 640.86 R
N
0 90 7.46 20.6 491.16 671.76 A
488.75 683.72 483.69 671.76 481.64 684.59 485.2 684.15 4 Y
V
90 143 7.46 20.6 491.16 671.76 A
478.57 640.86 482.3 671.76 R
N
497.22 640.86 500.95 671.76 R
N
459.92 640.86 463.65 671.76 R
N
456.19 630.56 504.68 640.86 R
N
90 180 7.46 20.6 160.61 671.76 A
170.11 684.59 168.07