chapter5.ps

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

5 .9 FMFILL
6 .97 FMFILL
7 1 FMFILL
8 <0f1e3c78f0e1c387> FMFILL
9 <0f87c3e1f0783c1e> FMFILL
10 <cccccccccccccccc> FMFILL
11 <ffff0000ffff0000> FMFILL
12 <8142241818244281> FMFILL
13 <03060c183060c081> FMFILL
14 <8040201008040201> FMFILL
16 1 FMFILL
17 .9 FMFILL
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: "96" 1
%%BeginPaperSize: Letter
%%EndPaperSize
612 792 0 FMBEGINPAGE
108 72 540 81 R
7 X
0 K
V
0 12 Q
0 X
(96) 312.01 73 T
108 90 540 648 R
7 X
V
0 X
(CHAPTER V) 290.85 640 T
(EMERGENCE OF T) 144.26 604 T
(ASK-DIRECTED COMPONENT MANIPULA) 245.24 604 T
(TION) 475.1 604 T
1 F
(5.0  Emergence of T) 108 562 T
(ask-Dir) 209.15 562 T
(ected Component Manipulation) 247.58 562 T
0 F
1.15 (In the previous chapter) 126 536 P
1.15 (, the natural dynamics of an evolutionary weak method were) 239.21 536 P
0 (used to induce both the architecture and parametric values for a neural network. The dem-) 108 518 P
(onstrated dynamics were a natural component of the evolutionary algorithm used.) 108 500 T
1.53 (In this chapter) 126 470 P
1.53 (, representation speci\336c operators are added to an evolutionary weak) 197.19 470 P
0.9 (method, similar to GNARL from the last chapter) 108 452 P
0.9 (, that designate which components of a) 347.7 452 P
1.24 (\336nite state machine \050FSM\051 representation should and should not be manipulated by the) 108 434 P
0.28 (other operators in future generations. As with other operators in evolutionary weak meth-) 108 416 P
0.92 (ods, these operators are applied randomly) 108 398 P
0.92 (. Because the operators are representation spe-) 311.67 398 P
0.01 (ci\336c and they are applied randomly) 108 380 P
0.01 (, the knowledge that determines those components that) 276.79 380 P
0.93 (should be protected emer) 108 362 P
0.93 (ges from the interaction of the evolutionary weak method with) 231.49 362 P
(the task.) 108 344 T
1.11 (T) 126 314 P
1.11 (wo ef) 132.49 314 P
1.11 (fects result from the operators introduced in this chapter) 160.36 314 P
1.11 (. First, those compo-) 437.72 314 P
0.19 (nents that are crucial to solving a task, i.e., task-speci\336c structures, are identi\336ed and pro-) 108 296 P
1.6 (tected from future manipulation. The knowledge that determines which of components) 108 278 P
1.32 (should be protected emer) 108 260 P
1.32 (ges during problem solving. Second, as a result of identifying) 232.65 260 P
1.47 (those components that are task-speci\336c the time to acquire FSMs for the demonstrated) 108 242 P
0.43 (task decreases. This demonstrates not only that interaction with the task can direct which) 108 224 P
(features should be manipulated but that doing so is bene\336cial to the acquisition process.) 108 206 T
1 F
(5.1  Evolving Finite State Machines) 108 170 T
0 F
1.4 (The program used in this chapter is similar to the GNARL program of last chapter) 126 146 P
1.94 (except the representation being evolved is not neural networks but FSMs. Finite state) 108 128 P
-0.2 (machines were the original representation used in early evolutionary programming \050Fogel,) 108 110 P
FMENDPAGE
%%EndPage: "96" 2
%%Page: "97" 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
(97) 528.01 712 T
108 72 540 702 R
7 X
V
0 X
0.98 (Owens and W) 108 694 P
0.98 (alsh 1966\051. More recently T) 176.95 694 P
0.98 (omita \0501982\051 uses an evolutionary program to) 314.26 694 P
-0.09 (induce FSMs for languages and Fogel \0501992a; 1992c\051 describe evolving FSMs for various) 108 676 P
0.28 (experiments on the Prisoner) 108 658 P
0.28 (\325) 243.52 658 P
0.28 (s Dilemma \050Luce and Raif) 246.86 658 P
0.28 (fa 1957; Rapoport 1966\051; Axelrod) 374.99 658 P
(1984\051.) 108 640 T
0.56 (Accordingly) 126 610 P
0.56 (, the representation speci\336c operators in this program manipulate various) 185.18 610 P
-0 (representational aspects of an FSM. The components of an FSM are states and transitions.) 108 592 P
1.1 (Each transition is associated with an input symbol and an output symbol. This suggests) 108 574 P
-0.28 (separate operators to add states, delete states, add transitions, delete transitions and modify) 108 556 P
(transitions.) 108 538 T
0.32 (The method of evolving FSMs used in this chapter is slightly dif) 126 508 P
0.32 (ferent than the meth-) 438.79 508 P
1.02 (ods described in Fogel, Owens and W) 108 490 P
1.02 (alsh \0501966\051 and Fogel \0501992a\051. First, during early) 295.36 490 P
1.4 (experiments with this problem, the algorithm created individuals with lar) 108 472 P
1.4 (ger and lar) 470.82 472 P
1.4 (ger) 524.68 472 P
1.57 (numbers of states until reaching the allowed maximum. In addition, a disproportionate) 108 454 P
0.28 (percentage of the population acquired the same \336tness for a considerable amount of time.) 108 436 P
-0.14 (In these early experiments, there was an equal chance for adding a state, deleting a state or) 108 418 P
(modifying a transition.) 108 400 T
1.17 (The number of mutations made to a parent to create an of) 126 370 P
1.17 (fspring in this program is) 414.07 370 P
(given by the function:) 108 352 T
0 10 Q
(\050EQ 22\051) 507.53 320.8 T
0 12 Q
-0.22 (where) 108 283.8 P
2 F
-0.22 (size) 140.08 283.8 P
0 F
-0.22 ( is the number of transitions in the parent FSM and) 158.07 283.8 P
2 F
-0.22 (N) 403.18 283.8 P
0 F
-0.22 (\0500,) 411.18 283.8 P
2 F
-0.22 ( T) 424.17 283.8 P
0 F
-0.22 (\051 is a gaussian random) 433.62 283.8 P
0.28 (variable with mean 0 and variance proportional to the \336tness \322temperature\323 of the parent.) 108 265.8 P
0.25 (The method of selection was the competitive method described in Fogel \0501992a\051 and out-) 108 247.8 P
0.21 (lined in Chapter 2 with the exception that if the two population members being compared) 108 229.8 P
0.83 (had the same \336tness, a \322winner\323 was chosen randomly) 108 211.8 P
0.83 (. The number of competitions per) 375.31 211.8 P
-0.03 (individual was 5. The population was sorted by their competitive selection scores with the) 108 193.8 P
-0.08 (best half of the population retained and replicated to create the following generation. Each) 108 175.8 P
1.38 (population member created exactly one of) 108 157.8 P
1.38 (fspring for the next generation. A population) 316.86 157.8 P
(size of 300 machines was used for each run.) 108 139.8 T
-0.05 (After analyzing a few evolved FSMs with the above algorithm it became apparent that) 126 109.8 P
0.39 (a lar) 108 91.8 P
0.39 (ge percentage of the states in the resulting machines were in fact unused. Because of) 129.15 91.8 P
226.41 315.8 389.12 330 C
0 12 Q
0 X
0 K
(1) 227.41 320.8 T
(r) 245.99 320.8 T
(o) 249.99 320.8 T
(u) 255.98 320.8 T
(n) 261.98 320.8 T
(d) 267.98 320.8 T
(a) 278.97 320.8 T
(b) 284.29 320.8 T
(s) 290.29 320.8 T
2 F
(N) 303.76 320.8 T
0 F
(0) 319.57 320.8 T
2 F
(T) 331.56 320.8 T
3 F
(,) 325.56 320.8 T
(\050) 314.46 320.8 T
(\051) 338.84 320.8 T
2 F
(s) 357.42 320.8 T
(i) 362.79 320.8 T
(z) 366.83 320.8 T
(e) 372.2 320.8 T
3 F
(\264) 347.83 320.8 T
([) 298.66 320.8 T
(]) 378.13 320.8 T
(\050) 274.97 320.8 T
(\051) 384.12 320.8 T
(+) 236.41 320.8 T
0 0 612 792 C
FMENDPAGE
%%EndPage: "97" 3
%%Page: "98" 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
(98) 528.01 712 T
108 72 540 702 R
7 X
V
0 X
0.95 (the high probability of deleting a state, the additional states ensure a high percentage of) 108 694 P
-0.29 (self-replication for the FSMs. By including a lar) 108 676 P
-0.29 (ge number of super\337uous states, whenever) 336.94 676 P
0.01 (a state deletion is performed, there is a better chance that the of) 108 658 P
0.01 (fspring will retain the abil-) 411.36 658 P
-0.25 (ity of its parent. This accounts for the inordinate number of machines with the same \336tness) 108 640 P
-0.25 (and maximum number of states. It is interesting to note that the dynamics of the evolution-) 108 622 P
0.58 (ary weak method allowed this safeguard to emer) 108 604 P
0.58 (ge without being anticipated by the pro-) 344.65 604 P
(grammer) 108 586 T
(.) 150.64 586 T
1.01 (T) 126 556 P
1.01 (o discourage the introduction of unnecessary states, the probability of applying the) 132.49 556 P
-0.05 (operators for altering an FSM were modi\336ed so that there was an even chance of mutating) 108 538 P
-0.09 (either a state or a transition. If a state mutation is selected, the chance of deleting a state as) 108 520 P
(opposed to adding a state is given by:) 108 502 T
0 10 Q
(\050EQ 23\051) 507.53 463.73 T
0 12 Q
-0 (where) 108 420.65 P
2 F
-0 (numstates) 140.29 420.65 P
0 F
-0 ( is the number of states in the parent FSM and) 188.27 420.65 P
2 F
-0 (maxstates) 412.41 420.65 P
0 F
-0 ( is the maximum) 459.72 420.65 P
-0.06 (number of states allowed for the problem. Thus if the number of states in the parent is less) 108 402.65 P
1.42 (than half that allowed for the problem, there is a greater chance of adding a state than) 108 384.65 P
0.76 (deleting a state. When the number of states in the machine is more than half of the total) 108 366.65 P
0.5 (number allowed, there is a preference for deleting states. While this did not entirely curb) 108 348.65 P
1 (the tendency for the runs to approach the maximum number of states, it did allow for a) 108 330.65 P
-0.25 (consistently broader distribution of sizes in the population and improved the overall acqui-) 108 312.65 P
(sition times.) 108 294.65 T
1 F
(5.2  Fr) 108 258.65 T
(eezing and Unfr) 141.43 258.65 T
(eezing Repr) 223.16 258.65 T
(esentational Components) 283.89 258.65 T
0 F
1.75 (T) 126 234.65 P
1.75 (o identify task-speci\336c component manipulations in the evolving individuals, two) 132.49 234.65 P
-0.11 (operators are added to the basic program described above. The \336rst operator) 108 216.65 P
-0.11 (, called) 471.38 216.65 P
2 F
-0.11 (fr) 508.8 216.65 P
-0.11 (eeze,) 516.36 216.65 P
0 F
0.11 (selects a random portion of the FSM and signi\336es in the representation that it is to be pre-) 108 198.65 P
0.16 (served from future modi\336cation. The second operator) 108 180.65 P
0.16 (,) 365.29 180.65 P
2 F
0.16 (unfr) 371.45 180.65 P
0.16 (eeze) 390.99 180.65 P
0 F
0.16 (, is the opposite of freeze.-) 411.63 180.65 P
5.21 (Unfreeze releases a frozen representational component so it can once again be) 108 162.65 P
3.6 (manipulated by the reproduction operators. The opposite actions of the freeze and) 108 144.65 P
-0.17 (unfreeze operators is important to allow the set of features being preserved to be adaptable) 108 126.65 P
(to the changing dynamics of the task.) 108 108.65 T
242.71 452.65 372.82 480 C
2 12 Q
0 X
0 K
(P) 243.71 463.73 T
(d) 258.84 463.73 T
(e) 265.55 463.73 T
(l) 271.58 463.73 T
(e) 275.62 463.73 T
(t) 281.65 463.73 T
(e) 285.69 463.73 T
3 F
(\050) 253.74 463.73 T
(\051) 291.62 463.73 T
2 F
(n) 317.2 470.8 T
(u) 323.9 470.8 T
(m) 330.6 470.8 T
(s) 339.97 470.8 T
(t) 345.34 470.8 T
(a) 349.38 470.8 T
(t) 356.08 470.8 T
(e) 360.12 470.8 T
(s) 366.15 470.8 T
(m) 317.53 456.12 T
(a) 326.9 456.12 T
(x) 333.6 456.12 T
(s) 339.63 456.12 T
(t) 345 456.12 T
(a) 349.04 456.12 T
(t) 355.75 456.12 T
(e) 359.79 456.12 T
(s) 365.82 456.12 T
3 F
(=) 303.61 463.73 T
317.2 466.33 370.57 466.33 2 L
0.33 H
0 Z
N
0 0 612 792 C
FMENDPAGE
%%EndPage: "98" 4
%%Page: "99" 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
(99) 528.01 712 T
108 72 540 702 R
7 X
V
0 X
0.02 (Because there is no single, general method of identifying what portions of the individ-) 126 694 P
0.59 (ual should be preserved, the components modi\336ed by these operators are selected at ran-) 108 676 P
0.42 (dom. By the ar) 108 658 P
0.42 (guments of the Chapter 3, if a randomly selected freeze operation protects) 180.33 658 P
1 (crucial components of the representation from modi\336cation, thus posing a bene\336t to the) 108 640 P
1.86 (reproductive ability of the individual, then this \322feature\323 is passed on to its of) 108 622 P
1.86 (fspring.) 503.02 622 P
0.6 (Likewise, if a frozen component is detrimental to the member) 108 604 P
0.6 (\325) 410.33 604 P
0.6 (s proliferation, i.e., it pro-) 413.67 604 P
-0 (tects an erroneous component, then that modi\336cation is eventually removed from the pop-) 108 586 P
-0.13 (ulation. Referring back to Equation 8, the protected components are the feature of interest,) 108 568 P
3 F
-0.23 (m) 108 550 P
0 F
-0.23 (, and) 114.91 550 P
3 F
-0.23 (e\050m,) 140.76 550 P
2 F
-0.23 ( t) 159.93 550 P
0 F
-0.23 (\051 = 0 since the reproductive operators cannot modify the protected component.) 166.03 550 P
0.5 (Equation 8 then shows that) 108 532 P
250.67 541.61 243.44 541.61 2 L
V
0.65 H
0 Z
N
3 F
0.5 (s) 243.44 532 P
0 F
0.5 (\050) 250.67 532 P
3 F
0.5 (m) 254.67 532 P
0 F
0.5 (,) 261.58 532 P
2 F
0.5 (t) 268.08 532 P
0 F
0.5 (\051 > 1/) 271.41 532 P
2 F
0.5 (n) 298.5 532 P
0 F
0.5 (, where) 304.5 532 P
2 F
0.5 (n) 343.8 532 P
0 F
0.5 ( is the size of the population, is a suf) 349.8 532 P
0.5 (\336-) 529.34 532 P
-0 (cient average selection probability to propagate the protected component through the pop-) 108 514 P
(ulation.) 108 496 T
1 F
(5.3  Experiments) 108 460 T
0 F
0.85 (T) 126 436 P
0.85 (o illustrate the ef) 132.49 436 P
0.85 (fects of freezing and unfreezing, the ant problem, described in the) 215.76 436 P
0.21 (previous chapter) 108 418 P
0.21 (, was again used, but more like the form of Jef) 187.33 418 P
0.21 (ferson et al. \0501992\051 than in) 411.71 418 P
-0.11 (chapter 4. In this experiment, the goal is to evolve an FSM controller to guide the arti\336cial) 108 400 P
0.24 (ant along the path of food shown in Figure 17 within 200 time steps. As before, the ant is) 108 382 P
-0.06 (equipped with a single sensor that can detect the presence or absence of food in the square) 108 364 P
0.86 (directly in front of it. Actuation of the ant is signaled through four possible action com-) 108 346 P
0.08 (mands: move one square forward \050MOVE\051, spin left 90) 108 328 P
2 8 Q
0.05 (o) 374.73 332 P
0 12 Q
0.08 ( \050LEFT\051, spin right 90) 378.73 328 P
2 8 Q
0.05 (o) 485.3 332 P
0 12 Q
0.08 ( \050RIGHT\051,) 489.3 328 P
1.69 (or do nothing \050NOOP\051. On each time step, the ant executes an implicit sense/act loop) 108 310 P
0.66 (where an input of FOOD or NOFOOD is given to the ant and it executes a single action) 108 292 P
0.12 (command. Once the ant enters a position on the grid with food, the food is removed and a) 108 274 P
(point of \336tness is awarded.) 108 256 T
0.78 (As previously stated, Jef) 126 226 P
0.78 (ferson et al. \0501992\051 used a genetic algorithm to compare the) 246.05 226 P
1.84 (evolution of bit strings that were interpreted as either \336nite state machines \050FSMs\051 or) 108 208 P
1.57 (recurrent neural networks depending on the experiment. Jef) 108 190 P
1.57 (ferson et. al. \0501992\051 used a) 404.57 190 P
1.25 (population size of 65,536 and replaced 95% of the population each generation for both) 108 172 P
0.05 (representations in both experiments. Evolving an FSM controller for this problem took 52) 108 154 P
0.13 (generations while the neural network controller took 94 generations to emer) 108 136 P
0.13 (ge. Thus their) 473.46 136 P
0.19 (genetic algorithm searched a total of 3,303,014 FSMs and 5,917,900 recurrent neural net-) 108 118 P
(works to solve the ant problem.) 108 100 T
FMENDPAGE
%%EndPage: "99" 5
%%Page: "100" 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
(100) 522.01 712 T
108 72 540 702 R
7 X
V
0 X
-0.17 (In the following experiments, FSM controllers for the ant problem evolve using evolu-) 126 694 P
1 (tionary programming with and without the freezing operators. A single freeze operation) 108 676 P
0.31 (selects a single state and up to 5 transitions at random and designates them as being \322fro-) 108 658 P
-0.29 (zen\323 in the representation. Conversely) 108 640 P
-0.29 (, unfreeze releases a single randomly selected frozen) 289.59 640 P
0.11 (state and up to 5 frozen links. When creating an of) 108 622 P
0.11 (fspring there is a 10% chance of apply-) 351.04 622 P
1.76 (ing a freeze operation and then a 20% chance of applying an unfreeze operation. The) 108 604 P
0.36 (higher unfreeze rate is to ensure that if local minima are reached the number of protected) 108 586 P
(components will decrease and allow protected components to be mutable again. All freez-) 108 568 T
0.3 (ing and unfreezing operations are applied to the of) 108 550 P
0.3 (fspring prior to the other mutations. At) 351.98 550 P
-0.24 (most 75% of the states and 75% of the transitions for any one FSM are permitted to be fro-) 108 532 P
(zen at a time.) 108 514 T
0.93 (In order to provide slightly more discriminations between evolved FSMs, the \336tness) 126 484 P
(function for these experiments modi\336ed is:) 108 466 T
0 10 Q
(\050EQ 24\051) 507.53 427.73 T
0 12 Q
0.31 (where) 108 384.54 P
2 F
0.31 (food) 140.61 384.54 P
0 F
0.31 ( is the amount of food found by the ant within 200 time steps and) 161.93 384.54 P
2 F
0.31 (t) 482.76 384.54 P
0 F
0.31 ( is the time) 486.09 384.54 P
0.11 (step on which the last piece of food was found. This \336tness function encodes a preference) 108 366.54 P
(for FSMs that acquire the same amount of food in fewer time steps.) 108 348.54 T
0.48 (T) 126 318.54 P
0.48 (o determine the ef) 132.49 318.54 P
0.48 (fect of the freeze and unfreeze operators on the evolution of FSM) 220.64 318.54 P
0.2 (controllers for the ant problem, eight runs were executed, four with compression and four) 108 300.54 P
(without.) 108 282.54 T
1 F