Guide to Intelligent Systems; Second Edition; Michael Negnevitsky


Evolutionary Systems/Non Deterministic Searching



Download 281.84 Kb.
Page5/5
Date06.08.2017
Size281.84 Kb.
#27182
TypeGuide
1   2   3   4   5

6.0 Evolutionary Systems/Non Deterministic Searching

Chapter 7, page 219


Now we change our tact from use of a-priori knowledge to one of adaptation.
Evolutionary Computation consists of

  • Genetic Algorithm – Computer optimization based on Darwinian processes in biology.

  • Evolutionary strategies – Similar to Genetic Algorithm but uses statistically generated offsets to vary solution.

  • Genetic Programming – Use of Genetic algorithm to generate code.

Based on:



  • Darwin’s classical theory of evolution

  • Weismanns’s theory of natural selection

  • Mendals concept of genetics

Process


  • Reproduction

  • Mutation

  • Competition

  • Selection

Species undergo various pressures:



  • Environmental

  • Competition for resources among:

    • Themselves

    • Other species

  • Dangers from other species

Topics include:




  • Genetic algorithm

  • Genetic programming

  • Simulated annealing



6.1 Basic Genetic algorithm




Pseudo Code
#define popSize 100

#define chromoSize 20

#define numGens 100

#define MU 10


char population[popSize][chromoSize]

char newPop[popSize][chromoSize]


int scores[popSize]
void main()

{

int j, k



int mom, dad;
/* Set up random number generator. */

srand(time);


Generate Population(popSize)
for j = 1 to numGens

rankPop(popSize, chromoSize, "hello tv land!)


sortLo2Hi(popSize)
for k = 1 to popSize

kid = k


mom = getMom(popSize)

dad = getDad(popSize)

crossOver(mom, dad, kid, chromoSize)

mutate(MU, chromoSize, kid)

}

population = newPop



}

}


void Create Chromosome (int chromoIndex, int chromoSize)

{

range = high limit - lower limit


for j = 1 to chromoSize

chromo[chromoIndex][j] = rand()%range + lower limit

end for

}


void Generate Population (int popSize)
{

for j = 1, popSize

population [j] = Create a chromosome

end for


}

int Get fitness (int chromoIndex, int chromoSize, char fitString)

{

int j;


int sum;
sum = 0;

for j = 1 to chromoSize

sum = sum + abs(fitString[j] - population[chromoIndex][j])

end for
return sum;

}

void rankPop(int popSize, int chromoSize, char *string)



{

int j;
for j = 1 to popSize

scores[j] = Get fitness (j, chromoSize, string);

end for


}

void sortLo2Hi(int popSize)

{

int j,k
for j = 1 to popSize



for k = j + 1 to popSize

if (scores[j] < scores[k]) {

exchange(scores[j], scores[k])

exchange(population[j], population[k])

end if

end for k



end for j

}
int getMom(int popSize)

{

top = .3 * popSize


mom = rand() % top
return mom;

}
int getPop(int popSize)

{

getMom(popSize)



}

void crossOver(int mom, int dad, int kid, int chromoSize)

{

int cross, j;


cross = rand() % chromoSize
for j = 1 to cross

newPop[kid][j] =population[mom][j]

end j
for j = cross to chromoSize

newPop[kid][j] = population[dad][j]

end j

}
void mutate(int chance, int chromosize, int kid)



{

int muGene;


if (rand() % 100 < chance)

muGene = rand() % chromoSize

.......Alter newPop[kid][muGene] ......

end if


}

Example – Spell “hello tv land”

Generations: 100

Population: 100.

Mutation rate: 1


hello tv land

D≤N{╫WnX(╬q?I generation 0; best score 608.000000

'M[ª}ëïï‼→Çg generation 1; best score 460.000000

ÇÇsÇÇÇÇÇÇÇÇg generation 2; best score 431.000000

ÇÇsÇÇ►ïì‼▬Çj generation 3; best score 355.000000

fÇÇÇÇ►ïì‼▬Çj generation 4; best score 342.000000

fÇÇÇÇ►|Ç~|Çgk► generation 5; best score 320.000000

`ÇÇÇÇ►ïì‼|~gk► generation 6; best score 259.000000

fÇÇÇê►ïÇ‼|sgh► generation 7; best score 246.000000

fÇÇÇÇ►|ì‼|}gh► generation 8; best score 246.000000

fÇÇÇÇ►|Ç‼|~gk► generation 9; best score 237.000000

SÇÇÇÇ►ïÇ‼u~gh► generation 10; best score 223.000000

SpÇÇê►ïÇ▬|sgh☼ generation 11; best score 209.000000

SÇ⌂ÇÇ►|Ç‼|sgh► generation 12; best score 203.000000

SpÇyÇ►ïÇ‼usgh► generation 13; best score 189.000000

SpÇyÇ►|Ç‼ufgh► generation 14; best score 161.000000

RiÇÇÇ►|Ç‼ufgh► generation 15; best score 160.000000

SpÇyy►|Ç‼ufgh► generation 16; best score 154.000000

SpÇyÇ►|x‼ufgh► generation 17; best score 153.000000

SiÇwÇ►|z‼ufgh► generation 18; best score 146.000000

SiÇwÇ►|x‼ufgh► generation 19; best score 144.000000

RiÇyÇ►|x‼ufgh↔ generation 20; best score 132.000000

RhÇly►|Ç ufgh► generation 21; best score 119.000000

ShÇjy►|v‼ofgh↔ generation 22; best score 106.000000

ShÇjy►|v‼ofgh↔ generation 23; best score 106.000000

RhÇly►|z ufgh↔ generation 24; best score 100.000000

Oisy|∟yz ufgh↔ generation 25; best score 86.000000

Oisjy∟yz ufgh↔ generation 26; best score 72.000000

Oisjy∟yz ofgh↔ generation 27; best score 66.000000

Oisjy∟yv ufjh▲ generation 28; best score 64.000000

Oisjy∟yv ufjh▲ generation 29; best score 64.000000

Oiljy∟yv ufjh▲ generation 30; best score 57.000000

Khljy∟|v u`gh▲ generation 31; best score 54.000000

Khljy∟|v u`jh▲ generation 32; best score 51.000000

Ohljy∟yv u`kh generation 33; best score 49.000000

Khlky∟zv ufmh generation 34; best score 47.000000

Khljy∟yv s`kh generation 35; best score 43.000000

Kills∟yv u`kh▲ generation 36; best score 40.000000

Khljl∟yv u`lh generation 37; best score 37.000000

Kilks∟yv qclh generation 38; best score 35.000000

Kdlls∟yv s`mh generation 39; best score 31.000000

Kdlls∟yv h`mh generation 40; best score 28.000000

Kdlls▼yv g`mh generation 41; best score 26.000000

Kdllo▼yt q`mh generation 42; best score 24.000000

Kdllo▼yv q`mh generation 43; best score 22.000000

Hdllo▼yt h`mh generation 44; best score 20.000000

Hdllo▼yv g`me generation 45; best score 16.000000

Hdllo▼yv i`me generation 46; best score 14.000000

Hdllo▼yv j`me generation 47; best score 13.000000

Heljo!uv j`me generation 48; best score 10.000000

Hello!uv j`me generation 49; best score 8.000000

Hello!uv j`me generation 50; best score 8.000000

Hello▼sv l`me generation 51; best score 6.000000

Hello▼uv m`me generation 52; best score 7.000000

Hello▼uv m`me generation 53; best score 7.000000

Hello!tv m`me generation 54; best score 6.000000

Hello!uv m`md generation 55; best score 6.000000

Hello!tv m`md generation 56; best score 5.000000

Hello!tv mamd generation 57; best score 4.000000

Hello tv m`md generation 58; best score 4.000000

Hello!tv lamd generation 59; best score 3.000000

Hello tv lamd generation 60; best score 2.000000

Hello tv lamd generation 61; best score 2.000000

Hello tv lamd generation 62; best score 2.000000

Hello tv lamd generation 63; best score 2.000000

Hello tv lamd generation 64; best score 2.000000

Hello tv lamd generation 65; best score 2.000000

Hello tv land generation 66; best score 1.000000

Hello tv land generation 67; best score 1.000000

Hello tv lamd generation 68; best score 2.000000

Hello tv lamd generation 69; best score 2.000000

Hello tv lamd generation 70; best score 2.000000

Hello tv lamd generation 71; best score 2.000000

Hello tv lamd generation 72; best score 2.000000

Hello tv lamd generation 73; best score 2.000000

Hello tv lamd generation 74; best score 2.000000

Hello tv lamd generation 75; best score 2.000000

Hello tv land generation 76; best score 1.000000

Hello tv land generation 77; best score 1.000000

Hello tv land generation 78; best score 1.000000

Hello tv land generation 79; best score 1.000000

Hello tv land generation 80; best score 1.000000

Hello tv land generation 81; best score 1.000000

Hello tv land generation 82; best score 1.000000

Hello tv land generation 83; best score 1.000000

Hello tv land generation 84; best score 1.000000

Hello tv land generation 85; best score 1.000000

Hello tv land generation 86; best score 1.000000

Hello tv land generation 87; best score 1.000000

Hello tv land generation 88; best score 1.000000

Hello tv land! generation 89; best score 0.000000

Hello tv land! generation 90; best score 0.000000

Hello tv land! generation 91; best score 0.000000

Hello tv land! generation 92; best score 0.000000

Hello tv land! generation 93; best score 0.000000

Hello tv land! generation 94; best score 0.000000

Hello tv land! generation 95; best score 0.000000

Hello tv land! generation 96; best score 0.000000

Hello tv land! generation 97; best score 0.000000

Hello tv land! generation 98; best score 0.000000

Hello tv land! generation 99; best score 0.000000

Press any key to continue




6.2 Discussion of Parent Selection Functions


We talk about several methods of parent selection:


  • Elite

  • Roulette

  • Polygamy

  • Dog and Cat

  • Alien

6.3 Evolutionary Strategies (page 242)


Similar to GA.
Major differences:


  • Uses only mutation

  • Population consists of 1 individual, many parameters.



6.4 Simulated Annealing




6.5 Genetic Programming



6.6 Fitness Functions




7.0 Neural Networks

Book Sections: 6.1 to 6.3; pages 163 to175




  • Brief intro to neural networks

    • Nerve cells transmit information to and from various parts of the body.

    • As creatures get more complex and thing called cephalization occurs. This is when nerves tend to lead towards a central point.

    • The more advanced creatures are, the higher the degree of cephalization.

    • A little biology

      • Nerve cell



    • Artificial Neural Network





    • Structure of ANN





    • Supervised learning

      • PERCEPTRON

        • y = x1* w1 + x2* w2….. xn* wn

        • e(p) = y(d) – y(p); p = 1,2, 3, 4,….

        • w­i(p+1) = wi(p) + α* xi(p) * e(p)

      • PERCEPTRON training algorithm




  1. Create training set, each example needs to have a desired output matched to it.

  2. Initialization (set weights to random numbers (-1 to 1)

  3. For each training example

    1. Present to perceptron

    2. Calculate y

    3. Execute transfer function

    4. Adjust weights.




Download 281.84 Kb.

Share with your friends:
1   2   3   4   5



The database is protected by copyright ©ininet.org 2024
send message
    Main page
final exam
best solution
concepts learned