3 F
(O) 171.65 154.95 T
3 10 Q
(1m) 178.84 151.95 T
3 12 Q
( = 1 0 0 0 0 0 0 0) 190.84 154.95 T
2 F
(.) 320.37 154.95 T
0.19 (Mutation is generally considered to be a background operator that ensures that the) 135.65 128.95 P
0.61 (probability of searching a particular subspace of the problem space is never zero.) 135.65 114.95 P
FMENDPAGE
%%EndPage: "4" 5
%%Page: "5" 5
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-5) 518.33 61.29 T
2 12 Q
1.57 (This has the ef) 135.65 736.95 P
1.57 (fect of tending to inhibit the possibility of conver) 210.43 736.95 P
1.57 (ging to a local) 458.64 736.95 P
(optimum, rather than the global optimum.) 135.65 722.95 T
1.87 (After recombination and mutation, the individual strings are then, if necessary) 135.65 696.95 P
1.87 (,) 528.65 696.95 P
4.09 (decoded, the objective function evaluated, a \336tness value assigned to each) 135.65 682.95 P
-0.01 (individual and individuals selected for mating according to their \336tness, and so the) 135.65 668.95 P
4.08 (process continues through subsequent generations. In this way) 135.65 654.95 P
4.08 (, the average) 462.55 654.95 P
3.36 (performance of individuals in a population is expected to increase, as good) 135.65 640.95 P
0.1 (individuals are preserved and bred with one another and the less \336t individuals die) 135.65 626.95 P
-0.26 (out. The GA is terminated when some criteria are satis\336ed, e.g. a certain number of) 135.65 612.95 P
0.66 (generations, a mean deviation in the population, or when a particular point in the) 135.65 598.95 P
(search space is encountered.) 135.65 584.95 T
1 16 Q
(GAs versus T) 135.65 556.29 T
(raditional Methods) 226.86 556.29 T
2 12 Q
1.06 (From the above discussion, it can be seen that the GA dif) 135.65 528.95 P
1.06 (fers substantially from) 421.6 528.95 P
3.43 (more traditional search and optimization methods. The four most signi\336cant) 135.65 514.95 P
(dif) 135.65 500.95 T
(ferences are:) 148.76 500.95 T
(\245) 157.25 474.95 T
(GAs search a population of points in parallel, not a single point.) 171.65 474.95 T
(\245) 157.25 454.95 T
1.32 (GAs do not require derivative information or other auxiliary knowledge;) 171.65 454.95 P
1.1 (only the objective function and corresponding \336tness levels in\337uence the) 171.65 440.95 P
(directions of search.) 171.65 426.95 T
(\245) 157.25 406.95 T
(GAs use probabilistic transition rules, not deterministic ones.) 171.65 406.95 T
(\245) 157.25 386.95 T
-0.26 (GAs work on an encoding of the parameter set rather than the parameter set) 171.65 386.95 P
(itself \050except in where real-valued individuals are used\051.) 171.65 372.95 T
1.06 (It is important to note that the GA provides a number of potential solutions to a) 135.65 346.95 P
0.5 (given problem and the choice of \336nal solution is left to the user) 135.65 332.95 P
0.5 (. In cases where a) 444.75 332.95 P
0.44 (particular problem does not have one individual solution, for example a family of) 135.65 318.95 P
4.61 (Pareto-optimal solutions, as is the case in multiobjective optimization and) 135.65 304.95 P
3.39 (scheduling problems, then the GA is potentially useful for identifying these) 135.65 290.95 P
(alternative solutions simultaneously) 135.65 276.95 T
(.) 307.44 276.95 T
FMENDPAGE
%%EndPage: "5" 6
%%Page: "6" 6
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-6) 518.33 61.29 T
63.65 716.95 531.65 726.95 C
63.65 725.95 531.65 725.95 2 L
1 H
2 Z
0 X
0 K
N
-8.35 24.95 603.65 816.95 C
1 18 Q
0 X
0 K
(Major Elements of the Genetic Algorithm) 63.65 732.95 T
2 12 Q
0.01 (The simple genetic algorithm \050SGA\051 is described by Goldber) 135.65 694.95 P
0.01 (g [1] and is used here) 428.67 694.95 P
0.09 (to illustrate the basic components of the GA. A pseudo-code outline of the SGA is) 135.65 680.95 P
1.58 (shown in Fig. 1. The population at time) 135.65 666.95 P
0 F
1.58 (t) 340.87 666.95 P
2 F
1.58 ( is represented by the time-dependent) 344.21 666.95 P
0.74 (variable) 135.65 652.95 P
0 F
0.74 (P) 178.02 652.95 P
2 F
0.74 (, with the initial population of random estimates being) 184.02 652.95 P
0 F
0.74 (P\0500\051) 453.87 652.95 P
2 F
0.74 (. Using this) 475.19 652.95 P
0.28 (outline of a GA, the remainder of this Section describes the major elements of the) 135.65 638.95 P
(GA.) 135.65 624.95 T
1 16 Q
(Population Repr) 135.65 336.01 T
(esentation and Initialisation) 248.64 336.01 T
2 12 Q
0.3 (GAs operate on a number of potential solutions, called a population, consisting of) 135.65 308.67 P
2.4 (some encoding of the parameter set simultaneously) 135.65 294.67 P
2.4 (. T) 395.08 294.67 P
2.4 (ypically) 409.97 294.67 P
2.4 (, a population is) 447.83 294.67 P
0.25 (composed of between 30 and 100 individuals, although, a variant called the micro) 135.65 280.67 P
1.11 (GA uses very small populations, ~10 individuals, with a restrictive reproduction) 135.65 266.67 P
(and replacement strategy in an attempt to reach real-time execution [2].) 135.65 252.67 T
0.4 (The most commonly used representation of chromosomes in the GA is that of the) 135.65 226.67 P
2.36 (single-level binary string. Here, each decision variable in the parameter set is) 135.65 212.67 P
0.23 (encoded as a binary string and these are concatenated to form a chromosome. The) 135.65 198.67 P
1.64 (use of Gray coding has been advocated as a method of overcoming the hidden) 135.65 184.67 P
4.2 (representational bias in conventional binary representation as the Hamming) 135.65 170.67 P
1.13 (distance between adjacent values is constant [3]. Empirical evidence of Caruana) 135.65 156.67 P
1.94 (and Schaf) 135.65 142.67 P
1.94 (fer [4] suggests that lar) 185 142.67 P
1.94 (ge Hamming distances in the representational) 303.11 142.67 P
5.36 (mapping between adjacent values, as is the case in the standard binary) 135.65 128.67 P
3.42 (representation, can result in the search process being deceived or unable to) 135.65 114.67 P
63.65 96.95 531.65 744.95 C
133.38 360.67 531.65 620.95 C
162.43 380.97 502.59 600.65 R
7 X
0 K
V
2 12 Q
0 X
(procedure GA) 198.43 592.65 T
(begin) 198.43 577.65 T
(t = 0;) 243.43 562.65 T
(initialize P\050t\051;) 243.43 547.65 T
(evaluate P\050t\051;) 243.43 532.65 T
(while not finished do) 243.43 517.65 T
(begin) 243.43 502.65 T
(t = t + 1;) 315.43 487.65 T
(select P\050t\051 from P\050t-1\051;) 315.43 472.65 T
(reproduce pairs in P\050t\051;) 315.43 457.65 T
(evaluate P\050t\051;) 315.43 442.65 T
(end) 243.43 427.65 T
(end.) 198.43 412.65 T
5 F
(Figure 1: A Simple Genetic Algorithm) 234.43 386.65 T
146.89 370.34 518.14 611.28 R
0.5 H
2 Z
N
63.65 96.95 531.65 744.95 C
-8.35 24.95 603.65 816.95 C
FMENDPAGE
%%EndPage: "6" 7
%%Page: "7" 7
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-7) 518.33 61.29 T
2 12 Q
0.64 (ef) 135.65 736.95 P
0.64 (\336ciently locate the global minimum. A further approach of Schmitendor) 144.75 736.95 P
0.64 (gf) 496.04 736.95 P
0 F
0.64 (et-al) 509.66 736.95 P
2 F
5.3 ([5], is the use of logarithmic scaling in the conversion of binary-coded) 135.65 722.95 P
3.46 (chromosomes to their real phenotypic values. Although the precision of the) 135.65 708.95 P
1.48 (parameter values is possibly less consistent over the desired range, in problems) 135.65 694.95 P
0.3 (where the spread of feasible parameters is unknown, a lar) 135.65 680.95 P
0.3 (ger search space may be) 413.9 680.95 P
0.51 (covered with the same number of bits than a linear mapping scheme allowing the) 135.65 666.95 P
-0.2 (computational burden of exploring unknown search spaces to be reduced to a more) 135.65 652.95 P
(manageable level.) 135.65 638.95 T
0.33 (Whilst binary-coded GAs are most commonly used, there is an increasing interest) 135.65 612.95 P
0.52 (in alternative encoding strategies, such as integer and real-valued representations.) 135.65 598.95 P
1.37 (For some problem domains, it is ar) 135.65 584.95 P
1.37 (gued that the binary representation is in fact) 311.22 584.95 P
1.28 (deceptive in that it obscures the nature of the search [6]. In the subset selection) 135.65 570.95 P
0.8 (problem [7], for example, the use of an integer representation and look-up tables) 135.65 556.95 P
5.49 (provides a convenient and natural way of expressing the mapping from) 135.65 542.95 P
(representation to problem domain.) 135.65 528.95 T
0.06 (The use of real-valued genes in GAs is claimed by W) 135.65 502.95 P
0.06 (right [8] to of) 392.27 502.95 P
0.06 (fer a number of) 457.2 502.95 P
1.02 (advantages in numerical function optimization over binary encodings. Ef) 135.65 488.95 P
1.02 (\336ciency) 493.68 488.95 P
0.45 (of the GA is increased as there is no need to convert chromosomes to phenotypes) 135.65 474.95 P
-0.02 (before each function evaluation; less memory is required as ef) 135.65 460.95 P
-0.02 (\336cient \337oating-point) 433.38 460.95 P
-0.03 (internal computer representations can be used directly; there is no loss in precision) 135.65 446.95 P
1.89 (by discretisation to binary or other values; and there is greater freedom to use) 135.65 432.95 P
0.23 (dif) 135.65 418.95 P
0.23 (ferent genetic operators. The use of real-valued encodings is described in detail) 148.76 418.95 P
0.08 (by Michalewicz [9] and in the literature on Evolution Strategies \050see, for example,) 135.65 404.95 P
([10]\051.) 135.65 390.95 T
1.85 (Having decided on the representation, the \336rst step in the SGA is to create an) 135.65 364.95 P
0.93 (initial population. This is usually achieved by generating the required number of) 135.65 350.95 P
0.95 (individuals using a random number generator that uniformly distributes numbers) 135.65 336.95 P
1.57 (in the desired range. For example, with a binary population of) 135.65 322.95 P
0 F
1.57 (N) 453 322.95 P
0 10 Q
1.3 (ind) 461 319.95 P
2 12 Q
1.57 ( individuals) 473.77 322.95 P
1.57 (whose chromosomes are) 135.65 308.95 P
0 F
1.57 (L) 261.27 308.95 P
0 10 Q
1.31 (ind) 267.94 305.95 P
2 12 Q
1.57 ( bits long,) 280.71 308.95 P
0 F
1.57 (N) 336.08 308.95 P
0 10 Q
1.31 (ind) 344.08 305.95 P
4 12 Q
1.57 (\264) 361.42 308.95 P
0 F
1.57 (L) 372.58 308.95 P
0 10 Q
1.31 (ind) 379.24 305.95 P
2 12 Q
1.57 ( random numbers uniformly) 392.02 308.95 P
(distributed from the set {0, 1} would be produced.) 135.65 294.95 T
3.16 (A variation is the) 135.65 268.95 P
0 F
3.16 (extended random initialisation) 234.23 268.95 P
2 F
3.16 ( procedure of Bramlette [6]) 387.8 268.95 P
1.02 (whereby a number of random initialisations are tried for each individual and the) 135.65 254.95 P
0.74 (one with the best performance is chosen for the initial population. Other users of) 135.65 240.95 P
-0.01 (GAs have seeded the initial population with some individuals that are known to be) 135.65 226.95 P
2.31 (in the vicinity of the global minimum \050see, for example, [1) 135.65 212.95 P
2.31 (1] and [12]\051. This) 440.12 212.95 P
3.22 (approach is, of course, only applicable if the nature of the problem is well) 135.65 198.95 P
-0.16 (understood beforehand or if the GA is used in conjunction with a knowledge based) 135.65 184.95 P
(system.) 135.65 170.95 T
5.61 (The GA T) 135.65 144.95 P
5.61 (oolbox supports binary) 195.31 144.95 P
5.61 (, integer and \337oating-point chromosome) 316.35 144.95 P
3.8 (representations. Binary and integer populations may be initialised using the) 135.65 130.95 P
1.9 (T) 135.65 116.95 P
1.9 (oolbox function to create binary populations,) 142.14 116.95 P
3 F
4.55 (crtbp) 372.38 116.95 P
2 F
1.9 (. An additional function,) 408.36 116.95 P
3 F
3.25 (crtbase) 135.65 102.95 P
2 F
1.35 (, is provided that builds a vector describing the integer representation) 186.02 102.95 P
FMENDPAGE
%%EndPage: "7" 8
%%Page: "8" 8
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-8) 518.33 61.29 T
2 12 Q
3.99 (used. Real-valued populations may be initialised with the function) 135.65 736.95 P
3 F
9.57 (crtrp) 492.67 736.95 P
2 F
3.99 (.) 528.65 736.95 P
2.54 (Conversion between binary strings and real values is provided by the routine) 135.65 722.95 P
3 F
(bs2rv) 135.65 708.95 T
2 F
( that supports the use of Gray codes and logarithmic scaling.) 171.63 708.95 T
1 16 Q
(The Objective and Fitness Functions) 135.65 680.29 T
2 12 Q
2.47 (The objective function is used to provide a measure of how individuals have) 135.65 652.95 P
-0.11 (performed in the problem domain. In the case of a minimization problem, the most) 135.65 638.95 P
1.87 (\336t individuals will have the lowest numerical value of the associated objective) 135.65 624.95 P
0.17 (function. This raw measure of \336tness is usually only used as an intermediate stage) 135.65 610.95 P
0.36 (in determining the relative performance of individuals in a GA. Another function,) 135.65 596.95 P
0.05 (the) 135.65 582.95 P
0 F
0.05 (\336tness function) 153.35 582.95 P
2 F
0.05 (, is normally used to transform the objective function value into) 225.7 582.95 P
(a measure of relative \336tness [13], thus:) 135.65 568.95 T
-0.29 (where) 135.65 514.76 P
0 F
-0.29 (f) 167.66 514.76 P
2 F
-0.29 ( is the objective function,) 170.99 514.76 P
0 F
-0.29 (g) 294.13 514.76 P
2 F
-0.29 ( transforms the value of the objective function to) 300.13 514.76 P
2.1 (a non-negative number and) 135.65 500.76 P
0 F
2.1 (F) 277.95 500.76 P
2 F
2.1 ( is the resulting relative \336tness. This mapping is) 285.28 500.76 P
1.97 (always necessary when the objective function is to be minimized as the lower) 135.65 486.76 P
3.03 (objective function values correspond to \336tter individuals. In many cases, the) 135.65 472.76 P
-0.29 (\336tness function value corresponds to the number of of) 135.65 458.76 P
-0.29 (fspring that an individual can) 392.24 458.76 P
0.33 (expect to produce in the next generation. A commonly used transformation is that) 135.65 444.76 P
1.03 (of proportional \336tness assignment \050see, for example, [1]\051. The individual \336tness,) 135.65 430.76 P
0 F
1.4 (F\050x) 135.65 416.76 P
0 10 Q
1.17 (i) 152.29 413.76 P
0 12 Q
1.4 (\051) 155.07 416.76 P
2 F
1.4 (, of each individual is computed as the individual\325) 159.07 416.76 P
1.4 (s raw performance,) 409.79 416.76 P
0 F
1.4 (f\050x) 509.22 416.76 P
0 10 Q
1.17 (i) 521.88 413.76 P
0 12 Q
1.4 (\051) 524.66 416.76 P
2 F
1.4 (,) 528.65 416.76 P
(relative to the whole population, i.e.,) 135.65 402.76 T
(,) 380.93 365.33 T
1.36 (where) 135.65 304.51 P
0 F
1.36 (N) 169.3 304.51 P
0 10 Q
1.13 (ind) 177.3 301.51 P
2 12 Q
1.36 ( is the population size and) 190.08 304.51 P
0 F
1.36 (x) 326.15 304.51 P
0 10 Q
1.13 (i) 331.47 301.51 P
2 12 Q
1.36 ( is the phenotypic value of individual) 334.25 304.51 P
0 F
1.36 (i) 525.32 304.51 P
2 F
1.36 (.) 528.65 304.51 P
1.87 (Whilst this \336tness assignment ensures that each individual has a probability of) 135.65 290.51 P
3.54 (reproducing according to its relative \336tness, it fails to account for negative) 135.65 276.51 P
(objective function values.) 135.65 262.51 T
0.15 (A linear transformation which of) 135.65 236.51 P
0.15 (fsets the objective function [1] is often used prior) 293.92 236.51 P
(to \336tness assignment, such that,) 135.65 222.51 T
0.2 (where) 135.65 168.32 P
0 F
0.2 (a) 168.15 168.32 P
2 F
0.2 ( is a positive scaling factor if the optimization is maximizing and negative) 174.14 168.32 P
-0.1 (if we are minimizing. The of) 135.65 154.32 P
-0.1 (fset) 272.83 154.32 P
0 F
-0.1 (b) 293.04 154.32 P
2 F
-0.1 ( is used to ensure that the resulting \336tness values) 299.04 154.32 P
(are non-negative.) 135.65 140.32 T
288.09 536.76 379.21 550.95 C
0 12 Q
0 X
0 K
(F) 289.09 541.75 T
(x) 304.22 541.75 T
4 F
(\050) 299.12 541.75 T
(\051) 310.16 541.75 T
0 F
(g) 334.73 541.75 T
(f) 348.54 541.75 T
(x) 359.68 541.75 T
4 F
(\050) 354.58 541.75 T
(\051) 365.61 541.75 T
(\050) 343.44 541.75 T
(\051) 372.21 541.75 T
(=) 322.15 541.75 T
-8.35 24.95 603.65 816.95 C
283.37 326.51 380.93 384.76 C
0 12 Q
0 X
0 K
(F) 284.37 365.33 T
(x) 299.5 365.33 T
0 9 Q
(i) 305.29 361.55 T
4 12 Q
(\050) 294.4 365.33 T
(\051) 308.4 365.33 T
0 F
(f) 343.44 375.55 T
(x) 354.58 375.55 T
0 9 Q
(i) 360.36 371.77 T
4 12 Q
(\050) 349.48 375.55 T
(\051) 363.47 375.55 T
0 F
(f) 352.9 343.76 T
(x) 364.04 343.76 T
0 9 Q
(i) 369.83 339.98 T
4 12 Q
(\050) 358.94 343.76 T
(\051) 372.93 343.76 T
0 9 Q
(i) 333.98 329.46 T
2 F
(1) 347.41 329.46 T
4 F
(=) 339.47 329.46 T
0 F
(N) 335.47 360.27 T
0 6 Q
(i) 341.82 357.82 T
(n) 343.94 357.82 T
(d) 347.4 357.82 T
4 18 Q
(\345) 336.52 340.55 T
4 12 Q
(=) 320.39 365.33 T
333.98 367.92 378.68 367.92 2 L
0.33 H
0 Z
N
-8.35 24.95 603.65 816.95 C
285.65 190.32 381.65 204.51 C
0 12 Q
0 X
0 K
(F) 286.65 195.31 T
(x) 301.79 195.31 T
4 F
(\050) 296.68 195.31 T
(\051) 307.72 195.31 T
0 F
(a) 332.3 195.31 T
(f) 339 195.31 T
(x) 350.14 195.31 T
4 F
(\050) 345.04 195.31 T