;
!"#$%&'()*+,-./0123456789:;<=>?@ABDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root Entry
FMicrosoft Word-Dokument
MSWordDocWord.Document.89qOh+'0
X`
&Bhabha Atomic Research Centre (BARC):KrisNormal.dotnaresh8@@@ÒR@%D
[bbDefault$a$1$A$*$/B*OJQJCJsH sH PJ^JaJ_HtHnH`` Heading 1@&
&F
&F<$OJQJCJ 5KH^JaJ \\\ Heading 3@&
&F
&F<$OJQJCJ5^JaJ\BA@BAbsatz-Standardschriftart22 WW8Num2z0OJQJPJ^J.. WW8Num2z1OJQJ^J** WW8Num2z2OJQJ*!* WW8Num2z3OJQJ*1* WW8Num3z0OJQJ.A. WW8Num3z1OJQJ^J*Q* WW8Num3z3OJQJ*a* WW8Num4z0OJQJ.q. WW8Num4z1OJQJ^J** WW8Num4z3OJQJ22 WW8Num5z0OJQJPJ^J22 WW8Num6z0OJQJPJ^J.. WW8Num6z1OJQJ^J** WW8Num6z2OJQJ** WW8Num6z3OJQJ(( WW8Num7z065,,
WW8Num14z0OJQJ00
WW8Num14z1OJQJ^J,,
WW8Num14z3OJQJ4!4
WW8Num16z0OJQJPJ^J010
WW8Num16z1OJQJ^J,A,
WW8Num16z2OJQJ,Q,
WW8Num16z3OJQJ*a*
WW8Num17z0654q4
WW8Num18z0OJQJPJ^J00
WW8Num18z1OJQJ^J,,
WW8Num18z2OJQJ,,
WW8Num18z3OJQJ,,
WW8Num19z0OJQJ00
WW8Num19z1OJQJ^J,,
WW8Num19z2OJQJ88
WW8Num21z0OJQJ5PJ^J44
WW8Num23z0OJQJPJ^J00
WW8Num23z1OJQJ^J,,
WW8Num23z2OJQJ,!,
WW8Num23z3OJQJ212WW8NumSt3z0OJQJ^J<A<Default Paragraph Font&XBQ&Emphasis6]4WBa4Strong Emphasis5\6UBq6
Internet LinkB*ph>*FBFHTML TypewriterOJQJCJPJ^JaJFFHeading
9x$OJQJCJPJ^JaJ.B. Text body
:x / List;^J @@Caption
<xx$CJ6^J aJ]&&Index=$^J RRNormal (Web)>d$a$B*ph,,,CJaJ88
Plain Text?OJQJCJaJHTML Preformatted7@
2(
Px4 #\'*.25@9OJQJCJPJ^JaJ44Table ContentsA$>">
Table HeadingB$a$$5\020Frame contentsC'.8)ILd345V2z f!!6)))*/"0J0r0006AVHXb:clcccc$dHdNd6789:;<=>?@ABCDEFGHIJKLMNOPQRSTY\\-X8@>(
N||C"
<
C'.zpT^`P^@`@^`0^```^`^`^`^``^0`0^p`p.^`.^`.WW8Num8WW8Num10WW8Num20@'.'.P
GTimes New Roman5Symbol3&ArialI&Arial Unicode MS?4Courier New;Wingdings7&VerdanaGMicrosoft YaHei5Mangal5MangalBhRf'&{"-{"-'00%Bhabha Atomic Research Centre (BARC):KrisnareshDyKyKhhttp://www.rennard.org/alife/english/gavintrgb.htmlr09Dd{|f
BA?b8團Vgn團VgPNG
IHDR@9PLTE3f3333f333ff3fffff3f̙3f3f3333f3333333333f333333f3f33f3ff3f3f33333f33̙33333f3333333f333ff3fffff3f3f33ff3f3f3fffff3fffffffffff3ffff̙fff3fffffff3fffff3f3333f333ff3fffff3f̙̙̙3̙f̙̙̙3f3f̙3333f3̙33ff3fff̙ff3f̙̙3f̙3f̙3f3333f333ff3fffff3f̙3f3fkd1bKGDHcmPPJCmp0712HsIDAT8OSA 78(:MHav%Q0Q6 ?CM8Q6d$@W@0 XUaKFz,
qgfSk@v`O+|qvxAH'^Xe
^tIENDB`Ddf
BA?b*פrv`nפrv`PNG
IHDR@9PLTE3f3333f333ff3fffff3f̙3f3f3333f3333333333f333333f3f33f3ff3f3f33333f33̙33333f3333333f333ff3fffff3f3f33ff3f3f3fffff3fffffffffff3ffff̙fff3fffffff3fffff3f3333f333ff3fffff3f̙̙̙3̙f̙̙̙3f3f̙3333f3̙33ff3fff̙ff3f̙̙3f̙3f̙3f3333f333ff3fffff3f̙3f3fkd1bKGDHcmPPJCmp0712HsIDAT8OK DW,3b~J-uRތG4.fA7&@
hA!8WhUfxz5\/@ /8AN7u`6̈*IENDB`Ddf
BA?bETB$'bd!nTB$'bdPNG
IHDR@9PLTE3f3333f333ff3fffff3f̙3f3f3333f3333333333f333333f3f33f3ff3f3f33333f33̙33333f3333333f333ff3fffff3f3f33ff3f3f3fffff3fffffffffff3ffff̙fff3fffffff3fffff3f3333f333ff3fffff3f̙̙̙3̙f̙̙̙3f3f̙3333f3̙33ff3fff̙ff3f̙̙3f̙3f̙3f3333f333ff3fffff3f̙3f3fkd1bKGDHcmPPJCmp0712HsIDAT8OI E{U+ &Br5ӞqaCW
z̀鑽y rqBYK`{ШW 6dfqwٚGnPN8uPǼZ*(u ty_ÏH}CIENDB`Ddf
BA?b<vTcnvTcPNG
IHDR@9PLTE3f3333f333ff3fffff3f̙3f3f3333f3333333333f333333f3f33f3ff3f3f33333f33̙33333f3333333f333ff3fffff3f3f33ff3f3f3fffff3fffffffffff3ffff̙fff3fffffff3fffff3f3333f333ff3fffff3f̙̙̙3̙f̙̙̙3f3f̙3333f3̙33ff3fff̙ff3f̙̙3f̙3f̙3f3333f333ff3fffff3f̙3f3fkd1bKGDHcmPPJCmp0712HsIDAT8OK E{|LP2nh+6j"J@ȯuFguqo!?]JB8P xC?ؽB(
QϞq6Rĵ~`6ԢZR
IENDB`Ddf
BA?b9pH(V5bn
pH(V5bPNG
IHDR@9PLTE3f3333f333ff3fffff3f̙3f3f3333f3333333333f333333f3f33f3ff3f3f33333f33̙33333f3333333f333ff3fffff3f3f33ff3f3f3fffff3fffffffffff3ffff̙fff3fffffff3fffff3f3333f333ff3fffff3f̙̙̙3̙f̙̙̙3f3f̙3333f3̙33ff3fff̙ff3f̙̙3f̙3f̙3f3333f333ff3fffff3f̙3f3fkd1bKGDHcmPPJCmp0712HsIDAT8OK Dލ+V>*81.Su7v'7.b/Y
QkπGg`
`;_>/qaU_M>ej؉HCT|/̈NIENDB`Ddf
BA?b(pi%anpi%aPNG
IHDR0gpPLTE3f3333f333ff3fffff3f̙3f3f3333f3333333333f333333f3f33f3ff3f3f33333f33̙33333f3333333f333ff3fffff3f3f33ff3f3f3fffff3fffffffffff3ffff̙fff3fffffff3fffff3f3333f333ff3fffff3f̙̙̙3̙f̙̙̙3f3f̙3333f3̙33ff3fff̙ff3f̙̙3f̙3f̙3f3333f333ff3fffff3f̙3f3fkd1bKGDHcmPPJCmp0712HsIDAT8ORI!>_o|q,h2$ElB@g &nAK"`*O,+PJ:T0Vȩim'ޟՖ¤yҲƼðfӘ}(__ObI`IENDB`Ddf
BA?b6FQ!n6FQ!PNG
IHDR(-SPLTE3f3333f333ff3fffff3f̙3f3f3333f3333333333f333333f3f33f3ff3f3f33333f33̙33333f3333333f333ff3fffff3f3f33ff3f3f3fffff3fffffffffff3ffff̙fff3fffffff3fffff3f3333f333ff3fffff3f̙̙̙3̙f̙̙̙3f3f̙3333f3̙33ff3fff̙ff3f̙̙3f̙3f̙3f3333f333ff3fffff3f̙3f3fkd1bKGDHcmPPJCmp0712Hs*81.Su7v'7.b/Y
QkπGg`
`;_>/qaU_M>ej؉HCT|/̈NIENDB`M 0NdCaolan80 @\-36VV4
hb "V8rkT<
[Start] Generate random population of n chromosomes (suitable solutions for the problem)
[Fitness] Evaluate the fitness f(x) of each chromosome x in the population
[New population] Create a new population by repeating following steps until the new population is complete
[Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
[Crossover] With a crossover probability cross over the parents to form new offspring (children). If no crossover was performed, offspring is the exact copy of parents.
[Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
[Accepting] Place new offspring in the new population
[Replace] Use new generated population for a further run of the algorithm
[Test] If the end condition is satisfied, stop, and return the best solution in current population
[Loop] Go to step 2
The crossover and mutation are the most important parts of the genetic algorithm. Mainly these two operators influence the performance. Before we can explain more about crossover and mutation, some information about chromosomes will be given.
ENCODING:
A chromosome should in some way contain information about solution that it represents. The most used way of encoding is a binary string. A chromosome then could look like this:
Chromosome 11101100100110110Chromosome 21101111000011110A binary string represents each chromosome. Each bit in the string can represent some characteristics of the solution. Another possibility is that the whole string can represent a number - this has been used in the basic GA applet.
Of course, there are many other ways of encoding. The encoding depends mainly on the solved problem. For example, one can encode directly integer or real numbers, sometimes it is useful to encode some permutations and so on.
CROSSOVER:
After we have decided what encoding we will use, we can proceed to crossover operation. Crossover operates on selected genes from parent chromosomes and creates new offspring. The simplest way how to do that is to choose randomly some crossover point and copy everything before this point from the first parent and then copy everything after the crossover point from the other parent.
Crossover can be illustrated as follows: (| is the crossover point):
Chromosome 111011 | 00100110110Chromosome 211011 | 11000011110Offspring 111011 | 11000011110Offspring 211011 | 00100110110
There are other ways how to make crossover, for example we can choose more crossover points. Crossover can be quite complicated and depends mainly on the encoding of chromosomes. Specific crossover made for a specific problem can improve performance of the genetic algorithm.
MUTATION:
After a crossover is performed, mutation takes place. Mutation is intended to prevent falling of all solutions in the population into a local optimum of the solved problem. Mutation operation randomly changes the offspring resulted from crossover. In case of binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can be then illustrated as follows:
Original offspring 11101111000011110Original offspring 21101100100110110Mutated offspring 11100111000011110Mutated offspring 21101101100110110The technique of mutation (as well as crossover) depends mainly on the encoding of chromosomes. For example when we are encoding permutations, mutation could be performed as an exchange of two genes.
FUNCTIONING:
As an example, we're going to enter a world of simplified genetic. The "chromosomes" encode a group of linked features. "Genes" encode the activation or deactivation of a feature.
Let us examine the global genetic pool of four basilosaurus belonging to this world. We will consider the "chromosomes" which encode the length of anterior members. The length of the "paw" and the length of the "fingers" are encoded by four genes : the first two encode the "paw" and the other two encode the fingers.
In our representation of the genome, the circle on blue background depict the activation of a feature, the cross on green background depict its deactivation. The ideal genome (short paws and long fingers) is :
.
The genetic pool of our population is the following one :
Subject Genome A B C D We can notice that A and B are the closest to their ancestors ; they've got quite long paws and short fingers. On the contrary, D is close to the optimum, he just needs a small lengthening of his fingers.
This is such a peculiar world that the ability to move is the main criteria of survival and reproduction. No female would easily accept to marry basilosaurus whose paws would look like A's. But they all dream to meet D one day.
The fitness is easy to compute : we just have to give one point to each gene corresponding to the ideal. The perfect genome will then get four points. The probability of reproduction of a given subject will directly depend on this value. In our case, we'll get the following results :
Subject Fitness Reproduction probability A 1 1/7=0.143 B 1 1/7=0.143 C 2 2/7=0.286 D 3 3/7=0.428 Total 7 7/7=1
We'll consider a cycle of reproduction with for descendants, i.e. four mating concerning height subjects. D will be selected four times and will then get four descendants. C will be selected twice and will get two descendants. Finally A and B will only be selected once.
The reproduction pattern is the following :
During reproduction crossovers occur at a random place (center of the genome for A', B' and C', just after the first gene for D'). The link existing between the degree of adaptation and the probability of reproduction leads to a trend to the rise of the average fitness of the population. In our case, it jumps from 7 to 10.
During the following cycle of reproduction, C' and D' will have a common descendant :
D' : + C' : =
The new subject has inherited the intended genome:his paws have become flippers.
We can then see that the principle of genetic algorithms is simple :
Encoding of the problem in a binary string.
Random generation of a population. This one includes a genetic pool representing a group of possible solutions.
Reckoning of a fitness value for each subject. It will directly depend on the distance to the optimum.
Selection of the subjects that will mate according to their share in the population global fitness.
Genomes crossover and mutations.
And then start again from point 3.
The functioning of a genetic algorithm can also be described in reference to genotype (GTYPE) and phenotype (PTYPE) notions HYPERLINK "http://www.rennard.org/alife/english/gavintrgb.html" \l "r09"10.
Select pairs of GTYPE according to their PTYPE fitness.
Apply the genetic operators (crossover, mutation...) to create new GTYPE.
Develop GTYPE to get the PTYPE of a new generation and start again from 1.
Crossover is the basis of genetic algorithms, there is nevertheless other operators like mutation. In fact, the desired solution may happen not to be present inside a given genetic pool, even a large one. Mutations allow the emergence of new genetic configurations which, by widening the pool improve the chances to find the optimal solution. Other operators like inversion are also possible, but we won't deal with them here.
The possible applications of genetic algorithms are immense. Any problem that has a large search domain could be suitable tackled by GAs. A popular growing field is genetic programming (GP).
APPLICATIONS:
Genetic Programming
In programming languages such as LISP and Scheme, the mathematical notation is not written in standard notation, but in prefix notation. Some examples of this:
+ 2 1: 2 + 1
* + 2 1 2: 2 * (2+1)
* + - 2 1 4 9:9 * ((2 - 1) + 4)
Notice the difference between the left-hand side to the right? Apart from the order being different, no parenthesis! The prefix method makes life a lot easier for programmers and compilers alike, because order precedence is not an issue. You can build expression trees out of these strings that then can be easily evaluated, for example, here are the trees for the above three expressions.
+ * *
/ \ / \ / \
1 2 + 2 + 9
/ \ / \
1 2 - 4
/ \
2 1
You can see how expression evaluation is thus a lot easier. What this has to do with GAs? If for example you have numerical data and 'answers', but no expression to conjoin the data with the answers. A genetic algorithm can be used to 'evolve' an expression tree to create a very close fit to the data. By 'splicing' and 'grafting' the trees and evaluating the resulting expression with the data and testing it to the answers, the fitness function can return how close the expression is. The limitations of genetic programming lie in the huge search space the GAs have to search for - an infinite number of equations. Therefore, normally before running a GA to search for an equation, the user tells the program which operators and numerical ranges to search under. Uses of genetic programming can lie in stock market prediction, advanced mathematics and military applications .
Evolving Neural Networks:
GAs have successfully been used to evolve various aspects of GAs - either the connection weights, the architecture, or the learning function. You can see how GAs are perfect for evolving the weights of a neural network - there are immense number of possibilities that standard learning techniques such as back-propagation would take thousands upon thousands of iterations to converge to. GAs could evolve working weights within a hundred or so iterations.
Many would think that a learning function could be evolved via genetic programming.Unfortunately, genetic programm ing combined with neural networks could be incredibly slow, thus impractical.As with many problems, you have to constrain what you are attempting to create. For example, in 1990,Chalmers attempted to evolve a function as good as the delta rule. He did this by creat ing a general equation based upon the delta rule with 8 unknowns, which the genetic algorithm then evolved.
Other Areas
Genetic Algorithms can be applied to virtually any problem that has a large search space. Al Biles uses genetic algorithms to filter out 'good' and 'bad' riffs for jazz improvisation, the military uses GAs to evolve equations to differentiate between different radar returns, stock companies use GA-powered programs to predict the stock market.
CONCLUSION:
Genetic algorithms are original systems based on the supposed functioning of the Living. The method is very different from classical optimization algorithms.
Use of the encoding of the parameters, not the parameters themselves.
Work on a population of points, not a unique one.
Use the only values of the function to optimize, not their derived function or other auxiliary knowledge.
Use probabilistic transition function not determinist ones.
It's important to understand that the functioning of such an algorithm does not guarantee success. We are in a stochastic system and a genetic pool may be too far from the solution, or for example, a too fast convergence may halt the process of evolution. These algorithms are nevertheless extremely efficient, and are used in fields as diverse as stock exchange, production scheduling or programming of assembly robots in the automotive industry.
Sub Rec ed genes Genome Fit-nessRepro tion probability A' A:D
: 2 2/10=0.2 B' B:D
: 2 2/10=0.2 C' D:C
: 3 3/10=0.3 D' C:D:3 3/10=0.3 Total 10 10/10=1
NP$ & N p &
>
DZb
x
fr.:RTXZ@BV2p 8R^bz~ P!R!`!b!!!!!!!!###%'6)8) B* ph B*
ph@ B*ph B*phCJ>*5aJ\CJaJ6]5\T8):)>))))))))**+h-/002:3<3>3@35x6666666>77&;<<<<<<<<^>AB$C4CPCxCDDD>ETHVH`HHHHH:I\IIICJ>*aJ6]0J7H*CJaJ0J7jUUUj0#CJaJUjCJaJUjCJaJ jU Uj Uj Uj
UjCJaJUjCJaJ>IIJJJJVJNN8QlQT:VPVXX[[[\>c@cHcJcLcNcxczccccccccccccccccc$d&d(dLdB*phPJ^JOJQJ Uj] UjX UjS UjO Uj,J UjlE Ujp@ Uj; Uj6 Uj1 Uj, Uj$(CJ>*5aJ\CJ5aJ\CJ^JaJOJQJCJ6aJ]CJ>*5aJ5\CJaJ.N &
Db
f.X@BV>$a$>$a$>^]`$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$
&F$a$^]`<V2q`$If$a$G$^]`$If$a$G$^]`R$$If0ex p44444f4T$If$a$G$^]`$If$a$G$^]`>^]`24p~veT$If$a$G$^]`$If$a$G$^]`>^]`>^]`
>$a$^]`
>$a$^]`>^]`>^]`R$$If0ex p44444f4T 7R$$If0 p44444f4T$If$a$G$^]`$If$a$G$^]`R$$If0 p44444f4T8:Rzyh$If$a$G$^]`$If$a$G$^]`R$$If0 p44444f4T$If$a$G$^]`$If$a$G$^]`z|~ ~skZ$If$a$G$^]`>^]`
>$a$^]`
>$a$^]`
>$a$^]`>^]`>^]`>^]`R$$If0 p44444f4T !!D!f!y$If$a$G$^]`$If$a$G$^]`R$$If0 p44444f4T$If$a$G$^]`f!h!!!!7R$$If0 p44444f4T$If$a$G$^]`$If$a$G$^]`R$$If0 p44444f4T!!!"###%'6)zog_W>^]`>^]`>^]`
>$a$^]`>^]`>^]`R$$If0 p44444f4T$If$a$G$^]`$If$a$G$^]` 6)>)))))))ziX$If$a$G$^]`$If$a$G$^]`R$$If0 p44444f4T$If$a$G$^]`$If$a$G$^]`>^]`>^]`)))))7R$$If0 p44444f4T$If$a$G$^]`$If$a$G$^]`R$$If0 p44444f4T))))**yh$If$a$G$^]`$If$a$G$^]`R$$If0 p44444f4T$If$a$G$^]`$If$a$G$^]`**+h-////{p
$If$a$G$
$If$a$G$
$IfG$^]`>^]`>^]`>^]`R$$If0 p44444f4T//00"0zo
$If$a$G$
$If$a$G$$If$a$G$^]`h$$IfF p44444f4T"0$0*000J0zo
$If$a$G$
$If$a$G$$If$a$G$^]`h$$IfF p44444f4TJ0L0R0X0r0zo
$If$a$G$
$If$a$G$$If$a$G$^]`h$$IfF p44444f4Tr0t0z000zo
$If$a$G$
$If$a$G$$If$a$G$^]`h$$IfF p44444f4T00000zo
$If$a$G$
$If$a$G$$If$a$G$^]`h$$IfF p44444f4T0002:3<3@35x66~|tld\>^]`>^]`>^]`>^]`>>^]`>^]`>^]`h$$IfF p44444f4T 6>77"899::&;<0==^>Aw>^]`
&F$a$
&F$a$
&F$a$
>^]`
&F$a$
&F$a$
&F$a$
>^]`>^]`
A4CPCxCDDD>E@ELHNHPHTHVH@$If$a$G$^]`
$a$^]`
$a$^]`
$a$^]`
$a$^]`
$a$^]`@$a$@$a$@$a$
$a$^]`
&F
&F$a$^]`
$a$^]`
VHHH:IIIJVJXJZJ8QlQTX{>^]`
$a$^]`
$a$^]`
$a$^]`
$a$^]`<$$If
p
4K4K4K4K4f4T@$If$a$^]`
XX[[[\]]^8_bbb|q
$If$a$G$
$If$a$G$$a$^]`
&F$a$
&F$a$
&F$a$
>^]`
>$a$^]`>^]`>^]`
&F$a$^]`bbc0c2c:cK@
$If$a$G$$$IfrF.H
R
2p244444f4
$If$a$G$
$If$a$G$
$If$a$G$:cDcLcPcVcjclc7$$IfrF.H
R
2p244444f4
$If$a$G$
$If$a$G$
$If$a$G$ $If$a$
$If$a$G$lctc~ccccc
$If$a$G$
$If$a$G$
$If$a$G$ $If$a$
$If$a$G$
$If$a$G$ccccccj_TK@
$If$a$G$ $If$a$
$If$a$G$
$If$a$G$$$IfrF.H
RX
2p244444f4ccccccTI=>$IfG$
$If$a$G$$$IfrF.H
R
2p244444f4
$If$a$G$
$If$a$G$ccddd$dI>
$If$a$G$$$IfrF.H
RK
2p244444f4
$If$a$G$
$If$a$G$
$If$a$G$$d&d(d0dBdDdHd@>$$IfrF.H
R
2p244444f4
$If$a$G$
$If$a$G$
$If$a$G$
$If$a$G$HdJdLdNd$a$^]`>. A!"#$P002P1h0p3P(20՜.+,D՜.+,\Root Entry FCompObjjOle
1TablepData
bSummaryInformation(0WordDocumentC@ObjectPoolDocumentSummaryInformation8t