gatbxa1.ps

王小平《遗传算法——理论、应用与软件实现》随书光盘

2.09 (fspring is approximately proportional to that individuals) 249.94 694.95 P
0.83 (performance. As there is no constraint on an individual\325) 135.65 680.95 P
0.83 (s performance in a given) 409.76 680.95 P
6.32 (generation, highly \336t individuals in early generations can dominate the) 135.65 666.95 P
5.59 (reproduction causing rapid conver) 135.65 652.95 P
5.59 (gence to possibly sub-optimal solutions.) 316.4 652.95 P
0.26 (Similarly) 135.65 638.95 P
0.26 (, if there is little deviation in the population, then scaling provides only a) 179.52 638.95 P
(small bias towards the most \336t individuals.) 135.65 624.95 T
0.33 (Baker [14] suggests that by limiting the reproductive range, so that no individuals) 135.65 598.95 P
-0.13 (generate an excessive number of of) 135.65 584.95 P
-0.13 (fspring, prevents premature conver) 304.27 584.95 P
-0.13 (gence. Here,) 471.52 584.95 P
0.97 (individuals are assigned a \336tness according to their rank in the population rather) 135.65 570.95 P
0.72 (than their raw performance. One variable,) 135.65 556.95 P
0 F
0.72 (MAX) 343.76 556.95 P
2 F
0.72 (, is used to determine the bias, or) 368.41 556.95 P
0 F
0.65 (selective pr) 135.65 542.95 P
0.65 (essur) 190.81 542.95 P
0.65 (e) 215.68 542.95 P
2 F
0.65 (, towards the most \336t individuals and the \336tness of the others is) 221.01 542.95 P
(determined by the following rules:) 135.65 528.95 T
(\245) 157.25 502.95 T
0 F
(MIN) 164.44 502.95 T
2 F
( = 2.0 -) 186.43 502.95 T
0 F
(MAX) 224.17 502.95 T
2 F
(\245) 157.25 482.95 T
0 F
(INC) 164.44 482.95 T
2 F
( = 2.0) 184.44 482.95 T
4 F
(\264) 215.19 482.95 T
2 F
( \050) 221.77 482.95 T
0 F
(MAX) 228.76 482.95 T
2 F
( -1.0\051 /) 253.41 482.95 T
0 F
(N) 288.72 482.95 T
0 10 Q
(ind) 296.72 479.95 T
2 12 Q
(\245) 157.25 462.95 T
0 F
(LOW) 164.44 462.95 T
2 F
( =) 189.76 462.95 T
0 F
(INC) 202.52 462.95 T
2 F
( / 2.0) 222.52 462.95 T
2.81 (where) 135.65 442.95 P
0 F
2.81 (MIN) 170.75 442.95 P
2 F
2.81 ( is the lower bound,) 192.74 442.95 P
0 F
2.81 (INC) 304.71 442.95 P
2 F
2.81 ( is the dif) 324.7 442.95 P
2.81 (ference between the \336tness of) 377.88 442.95 P
0.97 (adjacent individuals and) 135.65 428.95 P
0 F
0.97 (LOW) 258.13 428.95 P
2 F
0.97 ( is the expected number of trials \050number of times) 283.45 428.95 P
1.2 (selected\051 of the least \336t individual.) 135.65 414.95 P
0 F
1.2 (MAX) 311.73 414.95 P
2 F
1.2 ( is typically chosen in the interval [1.1,) 336.38 414.95 P
0.66 (2.0]. Hence, for a population size of) 135.65 400.95 P
0 F
0.66 (N) 316.12 400.95 P
0 10 Q
0.55 (ind) 324.11 397.95 P
2 12 Q
0.66 ( = 40 and) 336.89 400.95 P
0 F
0.66 (MAX) 387.59 400.95 P
2 F
0.66 ( = 1.1, we obtain) 412.24 400.95 P
0 F
0.66 (MIN) 499.24 400.95 P
2 F
0.66 ( =) 521.23 400.95 P
-0.18 (0.9,) 135.65 386.95 P
0 F
-0.18 (INC) 156.46 386.95 P
2 F
-0.18 ( = 0.05 and) 176.45 386.95 P
0 F
-0.18 (LOW) 232.81 386.95 P
2 F
-0.18 ( = 0.025. The \336tness of individuals in the population may) 258.13 386.95 P
(also be calculated directly as,) 135.65 372.95 T
(,) 439.73 335.53 T
(where) 135.65 299.28 T
0 F
(x) 167.95 299.28 T
0 10 Q
(i) 173.27 296.28 T
2 12 Q
( is the position in the ordered population of individual) 176.05 299.28 T
0 F
(i) 437.9 299.28 T
2 F
(.) 441.24 299.28 T
-0.04 (Objective functions must be created by the user) 135.65 273.28 P
-0.04 (, although a number of example m-) 363.03 273.28 P
0.7 (\336les are supplied with the T) 135.65 259.28 P
0.7 (oolbox that implement common test functions. These) 271.91 259.28 P
0.98 (objective functions all have the \336lename pre\336x) 135.65 245.28 P
3 F
2.36 (obj) 370.71 245.28 P
2 F
0.98 (. The T) 392.3 245.28 P
0.98 (oolbox supports both) 428.4 245.28 P
1.65 (linear and non-linear ranking methods,) 135.65 231.28 P
3 F
3.97 (ranking) 333.11 231.28 P
2 F
1.65 (, and includes a simple linear) 383.48 231.28 P
1.26 (scaling function,) 135.65 217.28 P
3 F
3.02 (scaling) 221.11 217.28 P
2 F
1.26 (, for completeness. It should be noted that the linear) 271.49 217.28 P
-0.14 (scaling function is not suitable for use with objective functions that return negative) 135.65 203.28 P
(\336tness values.) 135.65 189.28 T
1 16 Q
(Selection) 135.65 160.61 T
2 12 Q
0.46 (Selection is the process of determining the number of times, or) 135.65 133.28 P
0 F
0.46 (trials) 445.13 133.28 P
2 F
0.46 (, a particular) 470.46 133.28 P
1.43 (individual is chosen for reproduction and, thus, the number of of) 135.65 119.28 P
1.43 (fspring that an) 459.51 119.28 P
224.57 321.28 439.73 354.95 C
0 12 Q
0 X
0 K
(F) 225.57 335.53 T
(x) 240.7 335.53 T
0 9 Q
(i) 246.49 331.75 T
4 12 Q
(\050) 235.6 335.53 T
(\051) 249.59 335.53 T
2 F
(2) 274.17 335.53 T
0 F
(M) 292.75 335.53 T
(A) 303.45 335.53 T
(X) 311.48 335.53 T
4 F
(-) 283.17 335.53 T
2 F
(2) 331.39 335.53 T
0 F
(M) 345.2 335.53 T
(A) 355.89 335.53 T
(X) 363.93 335.53 T
2 F
(1) 383.84 335.53 T
4 F
(-) 374.26 335.53 T
(\050) 340.1 335.53 T
(\051) 390.45 335.53 T
0 F
(x) 404.51 345.75 T
0 9 Q
(i) 410.29 341.97 T
2 12 Q
(1) 425.37 345.75 T
4 F
(-) 415.79 345.75 T
0 F
(N) 398.14 327.91 T
0 9 Q
(i) 406.61 324.13 T
(n) 409.63 324.13 T
(d) 414.66 324.13 T
2 12 Q
(1) 431.73 327.91 T
4 F
(-) 422.15 327.91 T
(+) 321.81 335.53 T
(=) 261.59 335.53 T
398.14 338.12 437.48 338.12 2 L
0.33 H
0 Z
N
-8.35 24.95 603.65 816.95 C
FMENDPAGE
%%EndPage: "9" 10
%%Page: "10" 10
595.3 841.9 0 FMBEGINPAGE
0 10 Q
0 X
0 K
(Genetic Algorithm Toolbox User\325s Guide) 63.65 61.61 T
(1-10) 513.33 61.29 T
2 12 Q
-0.28 (individual will produce. The selection of individuals can be viewed as two separate) 135.65 736.95 P
(processes:) 135.65 722.95 T
(1\051) 135.65 696.95 T
0.93 (determination of the number of trials an individual can expect to receive,) 171.65 696.95 P
(and) 171.65 682.95 T
(2\051) 135.65 662.95 T
2.6 (conversion of the expected number of trials into a discrete number of) 171.65 662.95 P
(of) 171.65 648.95 T
(fspring.) 181.42 648.95 T
-0.07 (The \336rst part is concerned with the transformation of raw \336tness values into a real-) 135.65 628.95 P
0.47 (valued expectation of an individual\325) 135.65 614.95 P
0.47 (s probability to reproduce and is dealt with in) 310.06 614.95 P
0.51 (the previous subsection as \336tness assignment. The second part is the probabilistic) 135.65 600.95 P
-0.19 (selection of individuals for reproduction based on the \336tness of individuals relative) 135.65 586.95 P
3.05 (to one another and is sometimes known as) 135.65 572.95 P
0 F
3.05 (sampling) 365.89 572.95 P
2 F
3.05 (. The remainder of this) 409.87 572.95 P
2.11 (subsection will review some of the more popular selection methods in current) 135.65 558.95 P
(usage.) 135.65 544.95 T
-0.17 (Baker [15] presented three measures of performance for selection algorithms,) 135.65 518.95 P
0 F
-0.17 (bias) 508.66 518.95 P
2 F
-0.17 (,) 528.65 518.95 P
0 F
3.37 (spr) 135.65 504.95 P
3.37 (ead) 150.53 504.95 P
2 F
3.37 ( and) 167.85 504.95 P
0 F
3.37 (ef\336ciency) 197.9 504.95 P
2 F
3.37 (. Bias is de\336ned as the absolute dif) 242.41 504.95 P
3.37 (ference between an) 432.34 504.95 P
4.34 (individual\325) 135.65 490.95 P
4.34 (s actual and expected selection probability) 187.63 490.95 P
4.34 (. Optimal zero bias is) 412.04 490.95 P
1.03 (therefore achieved when an individual\325) 135.65 476.95 P
1.03 (s selection probability equals its expected) 326.95 476.95 P
(number of trials.) 135.65 462.95 T
-0.05 (Spread is the range in the possible number of trials that an individual may achieve.) 135.65 436.95 P
0.71 (If) 135.65 422.95 P
0 F
0.71 (f\050i\051) 147.34 422.95 P
2 F
0.71 ( is the actual number of trials that individual) 162 422.95 P
0 F
0.71 (i) 383.91 422.95 P
2 F
0.71 ( receives, then the \322minimum) 387.24 422.95 P
(spread\323 is the smallest spread that theoretically permits zero bias, i.e.) 135.65 408.95 T
0.3 (where) 135.65 321.65 P
0 F
0.3 (et\050i\051) 168.24 321.65 P
2 F
0.3 ( is the expected number of trials of individual) 188.23 321.65 P
0 F
0.3 (i) 412.42 321.65 P
2 F
0.3 (,) 415.76 321.65 P
0.3 ( is the \337oor of) 463.16 321.65 P
1.64 (et\050i\051 and) 135.65 307.65 P
1.64 ( is the ceil. Thus, while bias is an indication of accuracy) 223.32 307.65 P
1.64 (, the) 509.36 307.65 P
(spread of a selection method measures its consistency) 135.65 293.65 T
(.) 393.02 293.65 T
0.88 (The desire for ef) 135.65 267.65 P
0.88 (\336cient selection methods is motivated by the need to maintain a) 217.67 267.65 P
1.72 (GAs overall time complexity) 135.65 253.65 P
1.72 (. It has been shown in the literature that the other) 279.61 253.65 P
4.96 (phases of a GA \050excluding the actual objective function evaluations\051 are) 135.65 239.65 P
1 (O\050L) 135.65 225.65 P
2 10 Q
0.83 (ind) 155.63 222.65 P
2 12 Q
1 (.N) 168.4 225.65 P
2 10 Q
0.83 (ind) 180.06 222.65 P
2 12 Q
1 (\051 or better time complexity) 192.83 225.65 P
1 (, where L) 324.64 225.65 P
2 10 Q
0.83 (ind) 372.27 222.65 P
2 12 Q
1 ( is the length of an individual) 385.05 225.65 P
0.71 (and N) 135.65 211.65 P
2 10 Q
0.59 (ind) 165.33 208.65 P
2 12 Q
0.71 ( is the population size. The selection algorithm should thus achieve zero) 178.1 211.65 P
1.51 (bias whilst maintaining a minimum spread and not contributing to an increased) 135.65 197.65 P
(time complexity of the GA.) 135.65 183.65 T
1 14 Q
(Roulette Wheel Selection Methods) 135.65 156.31 T
2 12 Q
8.61 (Many selection techniques employ a \322roulette wheel\323 mechanism to) 135.65 129.65 P
-0.14 (probabilistically select individuals based on some measure of their performance. A) 135.65 115.65 P
2.72 (real-valued interval,) 135.65 101.65 P
0 F
2.72 (Sum) 240.67 101.65 P
2 F
2.72 (, is determined as either the sum of the individuals\325) 261.32 101.65 P
261.26 343.65 406.04 390.95 C
0 12 Q
0 X
0 K
(f) 262.26 364.71 T
(i) 273.4 364.71 T
4 F
(\050) 268.3 364.71 T
(\051) 277.34 364.71 T
0 F
(e) 312.75 365.19 T
(t) 318.78 365.19 T
(i) 329.92 365.19 T
4 F
(\050) 324.82 365.19 T
(\051) 333.86 365.19 T
0 F
(e) 357.85 365.19 T
(t) 363.89 365.19 T
(i) 375.03 365.19 T
4 F
(\050) 369.92 365.19 T
(\051) 378.97 365.19 T
(,) 345.86 365.19 T
(\376) 394.67 350.05 T
(\375) 394.67 362.17 T
(\374) 394.67 374.29 T
(\356) 299.88 350.05 T
(\355) 299.88 362.17 T
(\354) 299.88 374.29 T
(\316) 286.33 364.71 T
307.75 362.2 307.75 373.4 2 L
0.33 H
0 Z
N
307.75 362.2 310.75 362.2 2 L
N
343.86 362.2 343.86 373.4 2 L
N
343.86 362.2 340.86 362.2 2 L
N
352.85 362.2 352.85 373.4 2 L
N
352.85 373.4 355.85 373.4 2 L
N
388.96 362.2 388.96 373.4 2 L
N
388.96 373.4 385.96 373.4 2 L
N
-8.35 24.95 603.65 816.95 C
422.05 316.65 463.16 330.85 C
0 12 Q
0 X
0 K
(e) 429.05 321.65 T
(t) 435.08 321.65 T
(i) 446.23 321.65 T
4 F
(\050) 441.12 321.65 T
(\051) 450.17 321.65 T
424.05 318.65 424.05 329.85 2 L
0.33 H
0 Z
N
424.05 318.65 427.05 318.65 2 L
N
460.16 318.65 460.16 329.85 2 L
N
460.16 318.65 457.16 318.65 2 L
N
-8.35 24.95 603.65 816.95 C
182.22 302.65 223.32 316.85 C
0 12 Q
0 X
0 K
(e) 189.22 307.65 T
(t) 195.25 307.65 T
(i) 206.39 307.65 T
4 F
(\050) 201.29 307.65 T
(\051) 210.33 307.65 T
184.22 304.65 184.22 315.85 2 L
0.33 H
0 Z
N
184.22 315.85 187.22 315.85 2 L
N
220.32 304.65 220.32 315.85 2 L
N
220.32 315.85 217.32 315.85 2 L
N
-8.35 24.95 603.65 816.95 C
FMENDPAGE
%%EndPage: "10" 11
%%Page: "11" 11
595.3 841.9 0 FMBEGINPAGE
0 10 Q
0 X
0 K
(Genetic Algorithm Toolbox User\325s Guide) 63.65 61.61 T
(1-11) 513.33 61.29 T
2 12 Q
1.17 (expected selection probabilities or the sum of the raw \336tness values over all the) 135.65 736.95 P
0.26 (individuals in the current population. Individuals are then mapped one-to-one into) 135.65 722.95 P
1.69 (contiguous intervals in the range [0,) 135.65 708.95 P
0 F
1.69 (Sum) 321.33 708.95 P
2 F
1.69 (]. The size of each individual interval) 341.98 708.95 P
-0.14 (corresponds to the \336tness value of the associated individual. For example, in Fig. 2) 135.65 694.95 P
1.38 (the circumference of the roulette wheel is the sum of all six individual\325) 135.65 680.95 P
1.38 (s \336tness) 491.95 680.95 P
1.76 (values. Individual 5 is the most \336t individual and occupies the lar) 135.65 666.95 P
1.76 (gest interval,) 467.93 666.95 P
1.97 (whereas individuals 6 and 4 are the least \336t and have correspondingly smaller) 135.65 652.95 P
1.31 (intervals within the roulette wheel. T) 135.65 638.95 P
1.31 (o select an individual, a random number is) 318.59 638.95 P
1.88 (generated in the interval [0,) 135.65 624.95 P
0 F
1.88 (Sum) 280.29 624.95 P
2 F
1.88 (] and the individual whose segment spans the) 300.94 624.95 P
1.11 (random number is selected. This process is repeated until the desired number of) 135.65 610.95 P
(individuals have been selected.) 135.65 596.95 T
-0.04 (The basic roulette wheel selection method is stochastic sampling with replacement) 135.65 570.95 P
4.89 (\050SSR\051. Here, the segment size and selection probability remain the same) 135.65 556.95 P
3.36 (throughout the selection phase and individuals are selected according to the) 135.65 542.95 P
0.48 (procedure outlined above. SSR gives zero bias but a potentially unlimited spread.) 135.65 528.95 P
(Any individual with a segment size > 0 could entirely \336ll the next population.) 135.65 514.95 T
3.91 (Stochastic sampling with partial replacement \050SSPR\051 extends upon SSR by) 135.65 271.94 P
3.1 (resizing an individual\325) 135.65 257.94 P
3.1 (s segment if it is selected. Each time an individual is) 249.12 257.94 P
1.33 (selected, the size of its segment is reduced by 1.0. If the segment size becomes) 135.65 243.94 P
2.15 (negative, then it is set to 0.0. This provides an upper bound on the sprea