chapter3.ps

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

(e) 376.27 156.84 T
2 F
(H) 385.52 156.84 T
(t) 400.18 156.84 T
3 F
(,) 394.18 156.84 T
(\050) 381.53 156.84 T
(\051) 403.52 156.84 T
(-) 366.68 156.84 T
([) 352.58 156.84 T
(]) 408.12 156.84 T
(\263) 262.63 156.84 T
311.56 159.43 347.88 159.43 2 L
0.33 H
0 Z
N
0 0 612 792 C
FMENDPAGE
%%EndPage: "44" 5
%%Page: "45" 5
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
(45) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
-0.13 (where) 108 694 P
2 F
-0.13 (P) 140.17 694 P
2 10 Q
-0.11 (t) 147.49 691 P
0 12 Q
-0.13 (is the population at time) 152.66 694 P
2 F
-0.13 (t) 270.94 694 P
0 F
-0.13 ( and) 274.27 694 P
2 F
-0.13 (f\050i\051) 297.33 694 P
0 F
-0.13 ( is the \336tness of the) 311.98 694 P
2 F
-0.13 (i) 407.14 694 P
0 F
-0.13 (th population member) 410.47 694 P
-0.13 (. The) 515.48 694 P
1.64 (population then becomes a reservoir of useful schema which are recombined into new) 108 676 P
0.93 (combinations with assumably higher and higher \336tness. This constructive progression is) 108 658 P
(called the) 108 640 T
2 F
(building block hypothesis) 157.29 640 T
0 F
( \050Goldber) 279.89 640 T
(g 1989a\051.) 325.97 640 T
1.83 (While some have questioned various aspects of Holland\325) 126 610 P
1.83 (s theory \050Antonisse 1989;) 410.93 610 P
0.51 (V) 108 592 P
0.51 (ignaux and Michalewicz 1992; Fogel 1992\051 it is still the most generally held character-) 115.94 592 P
1 (ization of processing in genetic algorithms. Schema theory has even been extended to a) 108 574 P
2.65 (few more general, \336xed-length representational schemes \050Goldber) 108 556 P
2.65 (g and Lingle 1985;) 441.1 556 P
0.77 (Goldber) 108 538 P
0.77 (g 1989; Radclif) 147.09 538 P
0.77 (f 1991\051. However) 223.03 538 P
0.77 (, schema theory is not general across all evolu-) 309.02 538 P
0.2 (tionary weak methods since the concept of a schema, and its extentions is linked to \336xed-) 108 520 P
(length string representations.) 108 502 T
1 F
(3.1.2.2  Abstract Featur) 108 466 T
(es) 229.02 466 T
0 F
1.43 (Given that the only feedback to evolutionary weak methods is the \336tness values of) 126 440 P
-0.29 (each population member) 108 422 P
-0.29 (, components of a particular representation can never be explicitly) 225.52 422 P
1.26 (rated. Further) 108 404 P
1.26 (, there is nothing inside the evolutionary weak method shown in Figure 6) 174.06 404 P
0.7 (that can perform a component level credit assignment. Instead, probabilistic applications) 108 386 P
0.97 (of the representation speci\336c operators create new points in the problem space from the) 108 368 P
0.07 (current population members. Each new population member represents an experiment test-) 108 350 P
-0.23 (ing the features preserved by the applied operator against those that are modi\336ed. Success-) 108 332 P
1.69 (ful experiments, i.e. ones that construct comparatively \336t individuals, are added to the) 108 314 P
1.05 (population and used as the basis of future experimentation. Such an empirical approach) 108 296 P
0.31 (leads to the selection of features that are both bene\336cial for solving the problem and con-) 108 278 P
(ducive to manipulation by the operators being used.) 108 260 T
0.5 (Because evolutionary weak methods only have information about the performance of) 126 230 P
-0.07 (the complete individual and not its representational components, evolutionary weak meth-) 108 212 P
0.67 (ods propagate any abstract feature,) 108 194 P
3 F
0.67 (m) 281.22 194 P
0 F
0.67 (, of an individual that is preserved by the reproduc-) 288.12 194 P
0.33 (tion operators. An abstract feature is any aspect of a population member that is preserved) 108 176 P
0.6 (during reproduction. For instance, abstract features include any subset of possible values) 108 158 P
0.32 (for particular positions in the representations, similar to schemata. However) 108 140 P
0.32 (, abstract fea-) 474.43 140 P
0.95 (tures are not limited only by the explicit content of the representation. Abstract features) 108 122 P
FMENDPAGE
%%EndPage: "45" 6
%%Page: "46" 6
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
(46) 528.01 712 T
108 90 540 700.88 R
7 X
V
0 X
0.05 (may also be some property of the individual when interpreted in the task environment, for) 108 692.88 P
(instance, a particular strategy or substrategy for performing the task.) 108 674.88 T
2.25 (Abstract features dif) 126 644.88 P
2.25 (fer sharply from Holland\325) 228.2 644.88 P
2.25 (s schema theory \050Holland 1975\051 for) 357.87 644.88 P
1.43 (genetic algorithms. Schemata, and the associated theory) 108 626.88 P
1.43 (, assume that speci\336c or) 384.28 626.88 P
1.43 (ganiza-) 504.7 626.88 P
0.55 (tions of representational components are selected by the genetic algorithm and preserved) 108 608.88 P
0.22 (in the population \050Holland 1975\051. This is the intuition behind the building block hypothe-) 108 590.88 P
0.17 (sis. But there is nothing in the dynamics of a genetic algorithm, or any evolutionary weak) 108 572.88 P
0.38 (method, that permits it to distinguish between two individuals with distinct structures but) 108 554.88 P
-0.27 (identical \336tness ratings. Such confusions cause signi\336cant problems for genetic algorithms) 108 536.88 P
2.01 (\050Angeline, Saunders and Pollack 1994; Schaf) 108 518.88 P
2.01 (fer) 335.68 518.88 P
2.01 (, Whitley and Eshelman 1992; Belew) 348.51 518.88 P
2.01 (,) 537 518.88 P
0.41 (McInerney and Schraudolph 1992\051. Radclif) 108 500.88 P
0.41 (f \0501991\051 suggests that there should be \322minial) 318.27 500.88 P
(redundency\323 in genetic algorithm representations.) 108 482.88 T
-0.23 (Thus it cannot be the or) 126 452.88 P
-0.23 (ganizations of representational components that are selected by) 238.2 452.88 P
1.27 (evolutionary weak methods but the more abstract) 108 434.88 P
2 F
1.27 (phenotypic) 356.39 434.88 P
0 F
1.27 ( features, i.e., the qualities) 409.01 434.88 P
0.47 (the representation possesses when applied to the task. Interestingly enough, when a posi-) 108 416.88 P
0.39 (tional encoding is used, such as is often the case in genetic algorithm, there is no distinc-) 108 398.88 P
6.92 (tion between representational features and phenotypic features. But when the) 108 380.88 P
-0.03 (interpretation of the representation is not tied to a particular position of the representation,) 108 362.88 P
0.03 (such as in genetic programming or evolutionary programs, the mapping between structure) 108 344.88 P
0.26 (and behavior is more complex. Selection for representational components in evolutionary) 108 326.88 P
1.36 (algorithms using these more complex interpretation functions cannot occur because the) 108 308.88 P
0.16 (representational features, as well as or) 108 290.88 P
0.16 (ganizations of them such as schemas, are inaccessi-) 291.75 290.88 P
(ble to the credit assignment mechanism.) 108 272.88 T
1 F
(3.1.3  The Str) 108 236.88 T
(ength of Repr) 176.75 236.88 T
(oduction) 247.15 236.88 T
0 F
-0.19 (The key to understanding how evolutionary weak methods become stronger during the) 126 210.88 P
-0.06 (course of the search is not in the operation of the algorithm over the landscape, but in how) 108 192.88 P
2.1 (an evolutionary weak method manages the population of objects as a resource of the) 108 174.88 P
-0.29 (search. Consider that the next set of points investigated by an evolutionary weak method is) 108 156.88 P
0.55 (dependent on the composition of the current population. If the population contains struc-) 108 138.88 P
-0.02 (tures that are all dissimilar from the solution, then there is little or no chance that the solu-) 108 120.88 P
2.43 (tion is discovered on the next generation. If instead the population contains a single) 108 102.88 P
FMENDPAGE
%%EndPage: "46" 7
%%Page: "47" 7
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
(47) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
0.41 (member that is very similar to the goal solution, then there is potential for the solution to) 108 694 P
-0.23 (be constructed as an of) 108 676 P
-0.23 (fspring. As the number population members that are close to a solu-) 216.77 676 P
0.1 (tion increases, the probability of \336nding the solution in the next generation also increases.) 108 658 P
1.14 (This characterization is also consistent with standard weak methods that use a \322popula-) 108 640 P
(tion\323 such as beam search and best-\336rst search.) 108 622 T
1.61 (Given the population is a resource for the search, then evolutionary weak methods) 126 592 P
-0.06 (must allocate the resources of the population so that search ef) 108 574 P
-0.06 (fort is concentrated in pro\336t-) 402.33 574 P
0.2 (able regions of the space. Assuming that a particular object in the) 108 556 P
2 F
0.2 (t) 427.15 556 P
0 F
0.2 (th population,) 430.49 556 P
2 F
0.2 ( o) 497.32 556 P
2 10 Q
0.17 (i) 506.52 553 P
0 12 Q
0.2 (, has a) 509.3 556 P
-0.12 (probability of) 108 538 P
3 F
-0.12 (s) 176.38 538 P
0 F
-0.12 (\050) 183.62 538 P
2 F
-0.12 (o) 187.61 538 P
2 10 Q
-0.1 (i) 193.61 535 P
0 12 Q
-0.12 (,) 196.38 538 P
2 F
-0.12 (t\051) 199.38 538 P
0 F
-0.12 ( to be selected, the expected number of objects in the subsequent gen-) 206.71 538 P
(eration that are derived from it is:) 108 520 T
0 10 Q
(\050EQ 4\051) 512.53 485.33 T
0 12 Q
0.73 (where) 108 442.92 P
2 F
0.73 (n) 141.03 442.92 P
0 F
0.73 ( is the population size. Thus, when the chance that an object is selected is better) 147.02 442.92 P
0.62 (than 1/) 108 424.92 P
2 F
0.62 (n) 141.6 424.92 P
0 F
0.62 (, then the number of objects in the ensuing population that are derived from it is) 147.6 424.92 P
1.84 (likely to be greater than one, thus allocating more resources to objects that are in the) 108 406.92 P
1.44 (search neighborhood of) 108 388.92 P
2 F
1.44 (o) 228.56 388.92 P
2 10 Q
1.2 (i) 234.56 385.92 P
0 12 Q
1.44 (. Likewise, if the probability of selection is less than 1/) 237.34 388.92 P
2 F
1.44 (n) 514.91 388.92 P
0 F
1.44 ( the) 520.91 388.92 P
0.4 (expected number is less than one and less of the search resources is expended in the next) 108 370.92 P
(generation. The question is what determines the probability of selection for an object.) 108 352.92 T
-0.01 (This result can be re\336ned in the following way) 126 322.92 P
-0.01 (. Let an abstract feature of the represen-) 348.95 322.92 P
1.12 (tation be denoted as) 108 304.92 P
3 F
1.12 (m) 211.08 304.92 P
0 F
1.12 ( and let the objects in the) 217.98 304.92 P
2 F
1.12 (t) 348.74 304.92 P
0 F
1.12 (th population that have this feature be) 352.07 304.92 P
-0.08 (denoted by) 108 286.92 P
3 F
-0.08 (L\050m,) 163.8 286.92 P
2 F
-0.08 ( t) 185.93 286.92 P
0 F
-0.08 (\051. Then the number of objects in the subsequent population with this fea-) 192.18 286.92 P
(ture,) 108 268.92 T
2 F
(m\050) 132.65 268.92 T
3 F
(m) 145.3 268.92 T
2 F
(, t+1\051) 152.21 268.92 T
0 F
( is:) 179.62 268.92 T
0 10 Q
(\050EQ 5\051) 512.53 225.71 T
0 12 Q
0.83 (where) 108 167.53 P
3 F
0.83 (e) 141.13 167.53 P
0 F
0.83 (\050) 146.39 167.53 P
3 F
0.83 (m,) 150.39 167.53 P
2 F
0.83 (t) 160.29 167.53 P
3 F
0.83 (\051) 163.63 167.53 P
0 F
0.83 ( is the probability that the feature is disrupted by the reproduction operators) 167.62 167.53 P
2.18 (when constructing the of) 108 149.53 P
2.18 (fspring. Note that) 233.25 149.53 P
2.18 (. Equation 5 shows that) 419 149.53 P
0.25 (when the cumulative selection probability of all objects in the population with the feature) 108 131.53 P
0.27 (exceeds) 108 113.53 P
2 F
0.27 (m\050) 149.23 113.53 P
3 F
0.27 (m) 161.88 113.53 P
2 F
0.27 (,t\051/n) 168.79 113.53 P
0 F
0.27 ( and the chance of destroying the feature with the operators is small then) 188.44 113.53 P
-0.04 (the number of objects in the population with the feature is expected to increase. And if the) 108 95.53 P
256.64 474.92 363.88 498 C
2 14 Q
0 X
0 K
(E) 257.64 485.33 T
(o) 275.26 485.33 T
2 12 Q
(i) 282.79 479.97 T
3 14 Q
(\050) 269.35 485.33 T
(\051) 286.88 485.33 T
2 F
(n) 315.55 485.33 T
3 F
(s) 323.37 485.33 T
2 F
(o) 336.47 485.33 T
2 12 Q
(i) 344 479.97 T
2 14 Q
(t) 354.33 485.33 T
3 F
(,) 347.34 485.33 T
(\050) 331.81 485.33 T
(\051) 358.22 485.33 T
(=) 300.87 485.33 T
0 0 612 792 C
183.7 199.53 436.83 246.92 C
2 14 Q
0 X
0 K
(m) 184.7 225.71 T
3 F
(m) 201 225.71 T
2 F
(t) 213.98 225.71 T
0 F
(1) 229.77 225.71 T
3 F
(+) 219.23 225.71 T
0 F
(\050) 195.62 226.71 T
(,) 208.34 226.71 T
(\051) 237.41 226.71 T
2 F
(n) 263.75 225.71 T
0 F
(1) 279.81 225.71 T
3 F
(e) 300.77 225.71 T
(-) 290.31 225.71 T
(m) 312.29 225.71 T
2 F
(t) 327.35 225.71 T
3 F
(,) 320.35 225.71 T
(\050) 307.63 225.71 T
(\051) 331.24 225.71 T
([) 273.9 225.71 T
(]) 336.65 225.71 T
(s) 372.05 225.71 T
2 F
(i) 389.56 225.71 T
(t) 400.45 225.71 T
3 F
(,) 393.45 225.71 T
(\050) 383.65 225.71 T
(\051) 405.09 225.71 T
2 12 Q
(i) 342.59 209.21 T
3 F
(L) 356.72 209.21 T
(m) 368.95 209.21 T
2 F
(t) 381.85 209.21 T
3 F
(,) 375.85 209.21 T
(\050) 364.95 209.21 T
(\051) 385.19 209.21 T
(\316) 347.67 209.21 T
3 24 Q
(\345) 349.21 221.01 T
3 14 Q
(=) 249.07 225.71 T
0 0 612 792 C
327.07 145.53 419 160.53 C
2 12 Q
0 X
0 K
(m) 328.07 149.53 T
3 F
(m) 340.72 149.53 T
2 F
(t) 353.63 149.53 T
3 F
(,) 347.63 149.53 T
(\050) 336.73 149.53 T
(\051) 356.96 149.53 T
(L) 382.54 149.53 T
(m) 394.76 149.53 T
2 F
(t) 407.67 149.53 T
3 F
(,) 401.67 149.53 T
(\050) 390.77 149.53 T
(\051) 411.01 149.53 T
(=) 366.96 149.53 T
380.54 146.54 380.54 157.74 2 L
0.33 H
0 Z
N
416 146.54 416 157.74 2 L
N
0 0 612 792 C
FMENDPAGE
%%EndPage: "47" 8
%%Page: "48" 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
(48) 528.01 712 T
108 90 540 702 R
7 X
V
0 X
0 (cumulative selection probability is below) 108 694 P
2 F
0 (m\050) 308.89 694 P
3 F
0 (m) 321.54 694 P
2 F
0 (,t\051/n) 328.45 694 P
0 F
0 ( then the number of objects in the popu-) 348.11 694 P
(lation with the feature decreases.) 108 676 T
0.43 (The application of probabilistic reproductive operators modi\336es features of objects in) 126 646 P
1.83 (the population with dynamics as described in Equation 5. If modi\336cations produce an) 108 628 P
1.5 (improvement in terms of an increased selection of the object with a feature over other) 108 610 P
0.19 (objects in the population, then more objects with that feature are created in future genera-) 108 592 P
0.38 (tions. This suggests that the modi\336cation is bene\336cial in the current context of the search) 108 574 P
0.88 (and should be allotted more of the resource reserves. If a crucial feature of the object is) 108 556 P
0.95 (removed by the reproduction operators, then the modi\336ed object has less of a chance to) 108 538 P
-0.07 (propagate its features to other components of the population and the share of resources for) 108 520 P
(those features declines.) 108 502 T
-0.26 (The manipulation of the population as a resource for speci\336c features by the evolution-) 126 472 P
1.54 (ary weak method highlights a weak) 108 454 P
2 F
1.54 (empirical) 290.46 454 P
0 F
1.54 ( approach to credit assignment. Consider) 336.43 454 P
0.33 (that when no information is present about what features of an object are important, infor-) 108 436 P
1.66 (mation is gained by selecting some aspect of the object, modifying it and observing a) 108 418 P
1.09 (result in terms of the \336tness function. Such an experiment is not a suf) 108 400 P
1.09 (\336cient basis for a) 454.45 400 P
0.48 (complete induction of the global worth of the feature. It is important then to gather suf) 108 382 P
0.48 (\336-) 529.34 382 P
0.9 (cient statistics of the worth of speci\336c features in several contexts. Features found to be) 108 364 P
(bene\336cial in several contexts may be indicative of a necessary feature of the solution.) 108 346 T
0.87 (In essence, the number of objects in the population with a given feature can be con-) 126 316 P
1.64 (strued as an approximation of the importance of the abstract feature over the previous) 108 298 P
0.87 (empirical contexts. Thus, the population itself serves as a reservoir of features that have) 108 280 P
0.33 (previously been found to associate with better solutions. This leads to the conclusion that) 108 262 P
1.25 (the size of the population determines the accuracy of this method of credit assignment.) 108 244 P
0.69 (Stronger methods for empirically determining credit assignment could be constructed by) 108 226 P