chapter3.ps

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

18 .7 FMFILL
19 .5 FMFILL
20 .3 FMFILL
21 .1 FMFILL
22 0.03 FMFILL
23 0 FMFILL
24 <f0e1c3870f1e3c78> FMFILL
25 <f0783c1e0f87c3e1> FMFILL
26 <3333333333333333> FMFILL
27 <0000ffff0000ffff> FMFILL
28 <7ebddbe7e7dbbd7e> FMFILL
29 <fcf9f3e7cf9f3f7e> FMFILL
30 <7fbfdfeff7fbfdfe> FMFILL
%%EndSetup
%%Page: "41" 1
%%BeginPaperSize: Letter
%%EndPaperSize
612 792 0 FMBEGINPAGE
108 72 540 81 R
7 X
0 K
V
0 12 Q
0 X
(41) 312.01 73 T
108 90 540 648 R
7 X
V
0 X
(CHAPTER III) 289.19 640 T
(THE EVOLUTIONAR) 124.15 604 T
(Y WEAK METHOD AND EMERGENT INTELLIGENCE) 235.74 604 T
1 F
(3.0  The Evolutionary W) 108 562 T
(eak Method and Emergent Intelligence) 233.62 562 T
0 F
0.89 (The commonalities of evolutionary algorithms combined with their lack of task-spe-) 126 536 P
0.97 (ci\336c knowledge indicates their status as a weak method which this dissertation calls the) 108 518 P
2 F
0.17 (evolutionary weak method) 108 500 P
0 F
0.17 (. The major dif) 234.92 500 P
0.17 (ference between standard weak methods and the) 307.17 500 P
-0.09 (evolutionary weak is the adaptive behavior of evolutionary algorithms. Over time, an evo-) 108 482 P
1.33 (lutionary weak method garners information about the search environment and uses this) 108 464 P
1.6 (information to constrain future search. Thus evolutionary weak methods begin without) 108 446 P
1.66 (any informedness and become increasingly informed during the search. This is unique) 108 428 P
(among the collection of weak methods discussed in the previous chapters.) 108 410 T
0.54 (In this chapter) 126 380 P
0.54 (, I show that the evolutionary weak method\325) 195.21 380 P
0.54 (s technique of reproducing) 410.16 380 P
2.56 (with probabilistic variations de\336nes a weak, i.e. task-independent, approach to credit) 108 362 P
0.02 (assignment that has an empirical nature. This form of credit assignment allows the natural) 108 344 P
-0.24 (constraints of the task environment to emer) 108 326 P
-0.24 (ge as structures in the population without intro-) 314.18 326 P
0.99 (ducing explicit knowledge into the evolutionary weak method. Based on this method of) 108 308 P
1.6 (credit assignment,) 108 290 P
2 F
1.6 (emer) 201.48 290 P
1.6 (gent intelligence) 225.01 290 P
0 F
1.6 (, a new computational approach to intelligence) 306.22 290 P
0.23 (and problem solving, is de\336ned. The goal of emer) 108 272 P
0.23 (gent intelligence is to reduce or remove) 348.78 272 P
-0.22 (AI\325) 108 254 P
-0.22 (s reliance on explicit knowledge in a problem solver by favoring instead the) 123.99 254 P
2 F
-0.22 (emer) 488.5 254 P
-0.22 (gence) 512.03 254 P
0 F
(of problem speci\336c constraints through direct interaction with the task environment.) 108 236 T
1 F
(3.1  Empirical Cr) 108 200 T
(edit Assignment) 197.06 200 T
0 F
-0.18 (Evolutionary weak methods are distinct from standard weak methods because they use) 126 176 P
0.9 (past search points to increase their level of informedness during the search. The mecha-) 108 158 P
0.36 (nism that gathers this information during the search, which I call) 108 140 P
2 F
0.36 (empirical cr) 425.12 140 P
0.36 (edit assign-) 484 140 P
0.44 (ment) 108 122 P
0 F
0.44 (, works at a coarse grained, task-independent level. It relies on the empirical aspects) 131.32 122 P
-0.21 (of evolutionary weak methods and the \336nite resource of the population for its implementa-) 108 104 P
FMENDPAGE
%%EndPage: "41" 2
%%Page: "42" 2
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
(42) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
0.46 (tion. Because it is task-independent, empirical credit assignment is a weak form of credit) 108 694 P
1.66 (assignment. The features of empirical credit assignment that distinguish it from strong) 108 676 P
-0 (forms of credit assignment are its representation speci\336c operators, its ability to propagate) 108 658 P
(abstract features and the inherent strength of the empirical process at its core.) 108 640 T
1 F
(3.1.1  Repr) 108 604 T
(esentation Speci\336c Operators) 163.74 604 T
0 F
0.93 (As discussed in the last chapter) 126 578 P
0.93 (, standard weak methods are augmented by task-spe-) 280.38 578 P
0.78 (ci\336c knowledge in order to direct their problem solving ability) 108 560 P
0.78 (. T) 413.71 560 P
0.78 (ask-speci\336c knowledge) 426.97 560 P
0.87 (typically requires an understanding of the task environment to justify its presence in the) 108 542 P
0.36 (problem solving algorithm. In other words, task-speci\336c knowledge encodes some aspect) 108 524 P
0.48 (of the task environment that is generally invalid outside the task environment. This often) 108 506 P
0.8 (includes the de\336nition of task-speci\336c operators that transform a given solution into one) 108 488 P
(better able to solve the problem.) 108 470 T
0.15 (In an evolutionary weak method, the reproduction operators are de\336ned to manipulate) 126 440 P
3.36 (a speci\336c representation independent of its interpretation by a \336tness function. For) 108 422 P
3.06 (instance, genetic algorithms de\336ne crossover and point mutation speci\336cally for the) 108 404 P
0.44 (manipulation of bit strings. The operators in evolution strategies are similarly de\336ned for) 108 386 P
-0.28 (the real valued features that are typical in those weak methods. Evolutionary programming) 108 368 P
0.37 (also uses representation speci\336c operators to manipulate whatever representation is being) 108 350 P
0.39 (used. The distinctions between these methods lie in the amount of representation-speci\336c) 108 332 P
0.33 (knowledge they place into their respective reproduction operators. GAs are in a sense the) 108 314 P
-0.25 (weakest in representation-speci\336c knowledge since the \336xed-length bit string is often rein-) 108 296 P
1.23 (terpreted as a new structure before being evaluated.) 108 278 P
0 10 Q
1.02 (1) 363.71 282.8 P
0 12 Q
1.23 ( Manipulations of the bit string by) 368.71 278 P
0.12 (crossover and point mutation can violate the representational constraints of the interpreta-) 108 260 P
0.79 (tion. In genetic and evolutionary programming, more knowledge of the representation is) 108 242 P
-0.04 (provided to the operators to discourage unwarented manipulation. Genetic programming\325) 108 224 P
-0.04 (s) 535.33 224 P
-0.28 (crossover parses the program and manipulates the representation at the subtree level. Like-) 108 206 P
-0.15 (wise, evolutionary programs also mainpulate at a high representational level. For instance,) 108 188 P
3.52 (Angeline, Saunders and Pollack \0501994\051 provide separate reproduction heuristics for) 108 170 P
1.5 (manipulating the structural and parametric features of recurrent neural networks. Thus,) 108 152 P
0.05 (GAs are representationally weaker than GP and EP and, as with standard weak and strong) 108 134 P
108 104 540 124.09 C
108 111.99 239.98 111.99 2 L
0.25 H
2 Z
0 X
0 K
N
0 0 612 792 C
0 10 Q
0 X
0 K
(1.  See Chapter 4 of this dissertation for an example and discussion of this point.) 108 97.33 T
FMENDPAGE
%%EndPage: "42" 3
%%Page: "43" 3
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
(43) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
2.02 (methods, perform less ef) 108 694 P
2.02 (\336cient searches and require longer search times for the same) 232.42 694 P
-0.28 (tasks. Such a perspective suggests that Holland\325) 108 676 P
-0.28 (s \0501975\051 conclusion that binary representa-) 335.87 676 P
-0.09 (tions should be preferred in genetic algorithms since they allow maximal implicit parallel-) 108 658 P
2.09 (ism is erroneous and that genetic algorithms using multi-valued string representations) 108 640 P
(should perform quicker but at the expense of generality \050cf. Antonisse 1989\051.) 108 622 T
2.03 (Some GA researchers have investigated the augmentation of a genetic algorithm\325) 126 592 P
2.03 (s) 535.33 592 P
-0.04 (operators by task-speci\336c knowledge \050Grefensttete 1987; Michalewicz 1993\051. Given GA) 108 574 P
-0.04 (\325) 532 574 P
-0.04 (s) 535.33 574 P
1 (status as an evolutionary weak method, the associated increases in performance demon-) 108 556 P
0.74 (strated in these studies is not surprising. Designing operators with a priori knowledge of) 108 538 P
1.21 (the task is the basic philosophy of weak method and the subsequent increase in perfor-) 108 520 P
1.68 (mance should be expected. However) 108 502 P
1.68 (, while a short term bene\336t often results from the) 290.41 502 P
-0.07 (injection of knowledge into an evolutionary algorithm\325) 108 484 P
-0.07 (s operators, this practice eventually) 370.74 484 P
0.91 (leads to the same dif) 108 466 P
0.91 (\336culties experienced by standard AI strong methods. From the per-) 210.03 466 P
0.86 (spective of this dissertation, the addition of representation-speci\336c knowledge should be) 108 448 P
(similarly bene\336cial without overly narrowing the generality of the technique.) 108 430 T
1 F
(3.1.2  Abstract Featur) 108 394 T
(e Pr) 220.03 394 T
(opagation) 240.79 394 T
0 F
0.56 (Empirical credit assignment assigns credit at a coarse level to the abstract features of) 126 368 P
1.3 (population members. These points were \336rst made about genetic algorithms in Holland) 108 350 P
0.34 (\0501975\051. However) 108 332 P
0.34 (, the form of the theory in Holland \0501975\051 is too speci\336c to the bit string) 189.79 332 P
-0.18 (representations he assumed. In this subsection I generalize Holland\325) 108 314 P
-0.18 (s schema so it is appli-) 431.97 314 P
(cable to all evolutionary weak methods. First a review of schema is presented.) 108 296 T
1 F
(3.1.2.1  Schema Theory) 108 260 T
0 F
1.56 (Holland \0501975\051 hypothesizes that genetic algorithms preserve and recombine at the) 126 234 P
1 (representational level of schema. A) 108 216 P
2 F
1 (schema) 285.52 216 P
0 F
1 ( designates a set of bit string patterns across) 321.49 216 P
1.79 (the assumed \336xed-width binary string representation of the population. Designation of) 108 198 P
0.25 (schemata take the form \0501, 0, #\051) 108 180 P
2 8 Q
0.17 (n) 262.04 184 P
0 12 Q
0.25 ( where) 266.04 180 P
2 F
0.25 (n) 301.83 180 P
0 F
0.25 ( is the length of the binary string representation.) 307.83 180 P
0.24 (A \3221\323 or a \3220\323 at position) 108 162 P
2 F
0.24 (i) 235.28 162 P
0 F
0.24 ( in a schema signi\336es that each string in the set represented by) 238.61 162 P
0.55 (the schema contains that value at that position. A \322#\323 at position) 108 144 P
2 F
0.55 (i) 426.08 144 P
0 F
0.55 ( designates strings that) 429.41 144 P
0.41 (contain either a \3221\323 or a \3220\323 at position) 108 126 P
2 F
0.41 (i) 302.51 126 P
0 F
0.41 ( are in the set. Notice that the possible schemata) 305.84 126 P
1.23 (for a given length) 108 108 P
2 F
1.23 (n) 200.86 108 P
0 F
1.23 ( do not cover all possible subsets of binary strings of length) 206.86 108 P
2 F
1.23 (n) 510.12 108 P
0 F
1.23 (. For) 516.11 108 P
FMENDPAGE
%%EndPage: "43" 4
%%Page: "44" 4
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
(44) 528.01 712 T
108 90 540 700.88 R
7 X
V
0 X
0.32 (instance, there is no schema of length four that represents the set {0101, 1010}. The con-) 108 692.88 P
0.17 (cept of a schema encodes an assumption of sets of features. This is natural given the typi-) 108 674.88 P
(cal binary feature vector interpretation usually used in genetic algorithms.) 108 656.88 T
0.61 (Holland \0501975\051 ar) 126 626.88 P
0.61 (gues that a genetic algorithm assigns credit not to the strings in the) 212.93 626.88 P
1.69 (population but to schemata of the population, i.e. to sets of features. He observes that) 108 608.88 P
1.18 (assuming schema are assigned credit, feedback to a single population member provides) 108 590.88 P
(information about the various schemata it is a member in:) 108 572.88 T
-0.32 (Given) 162 542.88 P
2 F
-0.32 (l) 193.99 542.88 P
0 F
-0.32 ( [features], a single structure) 197.32 542.88 P
2 F
-0.32 (A) 335.58 542.88 P
0 F
-0.32 ( ... is an instance of 2) 342.9 542.88 P
2 10 Q
-0.27 (l) 442.55 547.67 P
0 12 Q
-0.32 ( distinct) 445.33 542.88 P
(schemata, as can be easily af) 162 524.88 T
(\336rmed by noting that) 299.66 524.88 T
2 F
(A) 403.61 524.88 T
0 F
( is an instance) 410.93 524.88 T
-0.22 (of any schema) 162 506.88 P
3 F
-0.22 (x) 233.62 506.88 P
0 F
-0.22 ( de\336ned by substituting [#\325) 239.54 506.88 P
-0.22 (s] for one or more of the) 367.28 506.88 P
2 F
(l) 162 488.88 T
0 F
( attribute values in [the structure\325) 165.33 488.88 T
(s] representation. \050p. 69\051) 324.22 488.88 T
0.36 (In ef) 108 458.88 P
0.36 (fect, Holland \0501975\051 ar) 130.45 458.88 P
0.36 (gues that while only a single population member is rated by a) 241.23 458.88 P
1.42 (\336tness function, information is garnered about all 2) 108 440.88 P
2 10 Q
1.18 (l) 363.75 445.67 P
0 12 Q
1.42 ( schemata of which that string is a) 366.53 440.88 P
1.68 (member) 108 422.88 P
1.68 (. Holland \0501975\051 calls this property) 146.64 422.88 P
2 F
1.68 (intrinsic parallelism) 328.28 422.88 P
0 F
1.68 ( and ar) 427.58 422.88 P
1.68 (gues that credit) 463.36 422.88 P
-0.12 (assignment \050which he called \322apportionment of credit\323\051 was performed on schema present) 108 404.88 P
(in the population.) 108 386.88 T
2.07 (Holland\325) 126 356.88 P
2.07 (s \0501975\051) 167.98 356.88 P
2 F
2.07 (schema theor) 214.76 356.88 P
2.07 (em) 280.67 356.88 P
0 F
2.07 ( provides the following lower bound for schema) 294.66 356.88 P
(growth in a standard genetic algorithm:) 108 338.88 T
0 10 Q
(\050EQ 2\051) 512.53 297.86 T
0 12 Q
0.62 (where) 108 251.86 P
2 F
0.62 (m\050H, t\051) 140.92 251.86 P
0 F
0.62 ( is the number of population members with schema) 176.18 251.86 P
2 F
0.62 (H) 430.65 251.86 P
0 F
0.62 ( at time) 439.31 251.86 P
2 F
0.62 (t) 480.16 251.86 P
0 F
0.62 (,) 483.49 251.86 P
2 F
0.62 (f\050H\051) 490.12 251.86 P
0 F
0.62 ( is the) 510.1 251.86 P
0.77 (average \336tness of the population members with schema) 108 233.86 P
2 F
0.77 ( H) 379.57 233.86 P
0 F
0.77 (,) 392.01 233.86 P
402.11 243.21 398.78 243.21 2 L
V
0.58 H
0 Z
N
2 F
0.77 (f) 398.78 233.86 P
0 F
0.77 ( is the average \336tness of the) 402.11 233.86 P
0.6 (population and) 108 215.86 P
3 F
0.6 (e) 183.82 215.86 P
2 F
0.6 (\050H,t\051) 189.08 215.86 P
0 F
0.6 ( is the probability that schema) 212.06 215.86 P
2 F
0.6 (H) 362.88 215.86 P
0 F
0.6 ( is disrupted by an operator) 371.54 215.86 P
0.6 (. Equa-) 504.77 215.86 P
(tion 2 can be rewritten in the following form:) 108 197.86 T
0 10 Q
(\050EQ 3\051) 512.53 156.84 T
213.71 283.86 406.82 316.88 C
2 12 Q
0 X
0 K
(m) 214.71 297.86 T
(H) 227.36 297.86 T
(t) 242.02 297.86 T
0 F
(1) 257.93 297.86 T
3 F
(+) 248.35 297.86 T
(,) 236.02 297.86 T
(\050) 223.37 297.86 T
(\051) 263.93 297.86 T
2 F
(m) 280.51 297.86 T
(H) 293.16 297.86 T
(t) 307.82 297.86 T
3 F
(,) 301.82 297.86 T
(\050) 289.17 297.86 T
(\051) 311.15 297.86 T
2 F
(f) 320.61 306.45 T
(H) 327.93 306.45 T
3 F
(\050) 323.94 306.45 T
(\051) 336.59 306.45 T
2 F
(f) 328.93 288.25 T
0 F
(1) 349.39 297.86 T
3 F
(e) 367.97 297.86 T
2 F
(H) 377.23 297.86 T
(t) 391.89 297.86 T
3 F
(,) 385.89 297.86 T
(\050) 373.24 297.86 T
(\051) 395.22 297.86 T
(-) 358.39 297.86 T
([) 344.29 297.86 T
(]) 399.83 297.86 T
(\263) 270.93 297.86 T
329.93 298.45 332.26 298.45 2 L
0.33 H
0 Z
N
320.61 300.45 340.34 300.45 2 L
N
0 0 612 792 C
202.06 119.94 418.46 175.86 C
2 12 Q
0 X
0 K
(m) 206.41 156.84 T
(H) 219.07 156.84 T
(t) 233.72 156.84 T
0 F
(1) 249.64 156.84 T
3 F
(+) 240.06 156.84 T
(,) 227.73 156.84 T
(\050) 215.07 156.84 T
(\051) 255.64 156.84 T
2 F
(m) 272.22 156.84 T
(H) 284.87 156.84 T
(t) 299.53 156.84 T
3 F
(,) 293.53 156.84 T
(\050) 280.88 156.84 T
(\051) 302.86 156.84 T
2 F
(f) 319.86 165.43 T
(H) 327.18 165.43 T
3 F
(\050) 323.19 165.43 T
(\051) 335.84 165.43 T
2 F
(f) 333.47 145.11 T
(i) 340.8 145.11 T
3 F
(\050) 336.81 145.11 T
(\051) 344.14 145.11 T
2 9 Q
(i) 311.56 132.81 T
(P) 324.97 132.81 T
2 6 Q
(t) 330.81 130.36 T
3 9 Q
(\316) 316.31 132.81 T
3 18 Q
(\345) 315.6 141.91 T
0 12 Q
(1) 357.69 156.84 T
3 F