0: (Coding)
(). , , ().
,
,
- , - .
, - , .. .
= {0,1}, . = R { }, real-valued .
1: (Initial population construction)
- , , , (a random sample of search space). , () .
2: (Fitness evaluation)
. , (fitness) . (fitness function) ( , ).
, , (3 4).
3: (Selection)
(an intermediate population) ( (mating pool), ) (reproduction, selection operator).
( reproduction, copy) . ( ) , .
, , F. ( / F) (a relative fitness).
(random trials), , . , , -, ( ) (Monte Carlo random procedure, wheel of fortune (Roulette wheel)).
.2.22 -.
. (= ) , (selected) ( ) :
, (2.10)
N
|
|
. (2.11)
. 2.22. -
1. (2.10) .
2. . , , :
uniform selection: ;
tournament selection: , ;
Selection with elitism: . .
, .
4: () (Crossover and Mutation) . , . : .
. :
1. ,
2. () ,
3. , .. (offspring).
. . . (a point of crossover) (, , ). , ( ) . , -: . = 3 . :
.
:
.
, .
. , , :
a) Uniform crossover:
, , a crossover mask. 1 -, . 0 , .
b) Linear interpolation 2-point crossover:
, ( ) , .
, , , . , . , . , , .
. .
|
|
5: (Checking of the End_Test)
t = t+ 1; IF NOT (End_Test) THEN go to Step2; else stop.
(End_Test) . (, 200), (, 3 ) .. , . .
: .
: [0-31] . , :
, .
, ( , ). , , [0-31] . . , : {00000} {11111}.
. . , 1,2,3,...,32 (25 = 32). , , , 2.2.
2.2
. 2.2 : . :
.
,
.
. (mating pool) : 01101, 11000 10011 .
, 2.3. .
2.3
Mating pool crossover
, (). . 2.4 ( , ).
2.4
. , ( ) , , , .
, ( ) . , . , . , .
, :
́ ́ , , , . . , -, .
. 2.23 (a,b,c,d) - .
(a) (Coding and Evaluation)
(b) (Selection)
(c) (Crossover)
(d) (Mutation)
. 2.23. -
:
|
|
,
(Coding system);
(Fitness function);
(Initial population);
(Population size);
(Selection operation);
(Crossover operation),
(Probability of crossover);
(Mutation operation),
(Probability of mutation);
(Termination condition).
, , . , :
,
- ;
- .
, . . .
. - .
(), . , . , . , , , .
, . , .
.2.24 - .
(Selection) , . , , , . . . , , .
- .2.25.
, , . .
. 2.24.
. 2.25. - .
, .
( ) :
1. ;
2. , [0, 1] , , , 5;
|
|
3. , [0, l];
4. , ;
5. ;
6. 1-5 .
. 2.26.
, . (two-point crossover). , .
. 2.26. -
, . . , , , . .
, . , .. , .
:
1. ;
2. [0 1]. , . 5;
3. (mutation point) - [0 l];
4. , ;
5. ;
6. 1-5 .
. 2.27.
. 2.27. -
, . .
(Fundamental Theorem of GA).
, , .
(). , A = {0,1}. () (-). - 1 .
: (a schema) S , A = {0,1,*}, * : . , :
S = * 1 * 0 * * 0 0. (2.12)
: (a representative of a schema)
, (0 1) -, .
, A, B, C S, (2.12).
A = 1 1 0 0 1 0 0 0
B = 0 1 1 0 0 0 0 0
C = 1 1 1 0 1 1 0 0.
: (an order of a schema)
, o (S), (0 1) -
, S, (2.12), o (S) = 4.
: (a defining length of a schema)
, (S), (0 1) - () (0 1) - (). (S) : .
, S, (2.12), :
(S) = = 8 2 = 6.
, . .
, 1101 4, , , 24 =16 :
1100, 110*, 11*0, 11**, 1*00, 1*0*, 1**0, 1***, *100, *10*, *1*0, *1**, **00, **0*, ***0, 0***, ****.
:
,
- .
, , , , . (implicit parallelism of GA).
|
|
. S t, . , , ..
=?
, . .
(Schema Theorem):
, , , ..
:
- S t;
- S;
- ;
- ; - ();
- S; - S;
- .
: . , , .
1. , , . , . , , - . , , - . , . , - .
2. .
3. () - , , . .
4. - , , . "", .
. (. 2.28,), . (. 2.28,) ( ), , . , , , , . .
. 2.28.
.
1. , (derivative based methods). - (derivative free optimization) . , , .
2. . . , () . . (0 1). .
3. - .
4. - .
5. (in poorly understood and irregular spaces).