生物信息学课件英文原版课件 (78)

Genetic Algorithms (GA),A class of probabilistic search algorithms.Inspired by natural genetics and biological evolution.Uses concept of “survival of fittest”.GA originally developed by John Holland (1975),GA general concepts,Iterative procedure(iterative improvement)Produces a series of “generations of populations” one per iterationEach member of a population represents a feasible solution,called a chromosome.,bag,chromosomes,Combine and die(mating),p1,1,2,3,K,m,evolution,Chromosome-a feasible solution,Selection crossover mutation,Pk,P3,The population during iteration of GA is denoted by the “bag”Pi=X1i,X2i,.,Xni.Xmi denotes the m th member of the population in i th iteration and n is the size of the population. Pi;is a bag ,not a set,hence can contain repeated solutions, i.e. all entries need not be unique.Initial population P1,may be created randomly or by a deterministic (constructive) heuristic.Cost(x) is the cost of solution x.This function is user supplied.,Assume cost(x)=0 V X.Let fitness of (x) =1/1+cost(x), thus V x, 0average-fitness(Pj) for ij.We go from Pi to Pi+1 via an evolution function that usually consists of three components called operators.,Operators,Selection: select some members of current population to move to the next generation.Try to select “highly fit “ solutions.Use an (imaginary) roulette wheel technique.Fitness of .37 = 37%,2,1,n,3,4,Area is Proportional to fitness value,Example,Chromosome fitness A .21 B .14 C .10 D .02 E .33 F .20 - 1.00,A21%,D 2%,10%,F20%,E33%,B14%,C,1) When wheel is turned and eventually stops,probability of stopping at A is 0.21 2) The function select-roulette(f) spins roulette wheel by a random degree(uniform between 0 and 2) and returns a chromosome the one pointed to by the arrow head,Crossover,Crossover operators combine features of highly fit members of a population to create new members.First select two unique parents(chromosome)Say Xa and Xb using select-roulette().Divide parents into two parts; Xa Xb Exchange to get ,This is a mating process of highly fit members.Example:Often bit strings are used to represent a chromosome.Xa;100011;1110 ya;100011;1010Xb;101010;1010 yb;101010;1110,Mutation,Mutation operators randomly alters structure of chromosome.Pm - user supplied probability .Select a chromosome with probability,Pm usually;.05Pm0.2.Mutation used to introduce new features into a population.,Inversion:,Third operator of GALike Mutation, it also operates on a single chromosome.To laterally invert the order of alleles between two randomly chosen points on chromosome.Example: Given String: 0 1 2: 3 4 5 6 7: 8 b i d:e f g c h: aWill Become: b i d:h c g f e: a,Representation,Often a chromosome is encoded as a bit stream. The actual representation might be a structure,such as a floorplan, placement or route(wire).By operating on bitstream one can generate a bit stream that doesnt correspond to a legal structure.Thus non bit string representations are often used including graphs and lists.,Solving the logic partitioning problem via a GA,Problem formulationK chipsEach has area AmaxEach has thermal capacity HmaxEach has Pm capacity PmaxDesign represented by a graph G=(V,E)Each mode v V represents a gate and has areaA(v),heat dissipation H(v).Each hyperedge e is a subset of modes of V.(e represents a signal.),Partition V into disjoint subsets V1,V2,.,Vk so that For i=1,2,3,.kPi =e E | (v,w) e such that v Vi and w Vi| = Pmax Ai = A(v) = Amax v Vi Hi = H(v) best_fitness) then best_solution x; best_fitness fitness; end if; end for; if (user-specified exit condition is satisfied) then exit else Pi+1evolve(Pi,n,Ps,Pm); ii+1 ; end if;forever;end;,function evolve(p,n,Ps,Pm); bs : bag of solutions selected bc : bag of solutions crossed over bm : the bag bs bc after mutationbegin bs select(p,n,Ps); bc crossover(p,n-|bs|); bm mutate(bs bc,n,Pm); return(bm); end;,function select(p,n,Ps) begin bs ; i 0; while(iPs *n) do x select_roulette(p); bs bs x; ii+1; end while;return(bs) end;,function crossover(p,c) begin bc ; i 0; while(i crossover(x1,x2); bc bc y1; ii+1; if (i p - where |v| = p is number of gates. For a given placement,its associated length L is given by L = L(e) where L(e) is an estimate of the length of eE interconnect (wire) needed to route net e. Find an assignment so that L is minimal.,Genetic Encoding and operators,Encoding Assume placement consists of a rectangular grid of slots as shown in the figure on the next slide.,Encoding Dummy Gates,C4,C3,C9,D6,C5,C12,D5,D7,C10,C14,C13,C7,C1,D3,C8,C18,C2,D4,C6,C11,C15,D2,C17,D1,C16,Col 0 Col 1 Col 2 Col 3 Col 4,Chip,Empty Slot,Occupied Slot,C1 (a gate) is in row 1 column 1, etc.Empty slots are filled with dummy gates that have unique names , zero area, zero heat (power), no connections .For previous placements the encoding is : C16 , D1 , C17 , D2 , C15 , D3 , C 1 etc. (Reading from bottom to top and left to right),G,C,B,A,F,E,D,I,H,End,Start,Encoding Using for Placement,Cross Over,Effect of Single Point Cross Over (Illegal Placements),A simple one- point crossover operator leads to illegal placements as shown above.,Parent 1,Child 1,Parent 2,Child 2,Child 1 has 2 As and 2 Bs , no C or D .Child 2 has 2 Ds and 2 Cs no A or BTo resolve this, we employ a cycle crossover operator .,Cycle Crossover,Let P1 and P2 denote the 2 parents & C1 and C2 denote the 2 children .Let P1 , P2 , C1 , C2 arrays be of size r.c,Child C1 is formed by first copying a number of genes (gate positions ) in P1 into C1 , and then filling the rest of the genes in C1 from P2 . First , C10 P10 Let location i in P1contain the gate that occupies position 0 in P2 Then C1iP1i. Continue this process . That if we just filled position i in C1 by copying position i in P1 , then we identify the gate in position i in P2 and determine the location j of that gate in P1 and copy that gate to position j in C1 .,This process halts when we get to a gate that has already been copied into C1. This completes a cycle . Subsequently , we fill each unfilled position X in C1 by copying from P2 the gate assignments at X , i.e C1XP2X. To form C2 carry out the same process while interchanging the role of P1 and P2,Example,P1 = I H B A G D E C F,P2 = A B C D E F G H I,I = 0 1 2 3 4 5 6 7 8,C1 = B C E G H,C2 = H B G E C,A,D,F,I,F,D,I,A,Cycle Crossover,C10 P10 ; so C10=IP20 = A . Location of A in P1 is 3 (i=3)C1i P1i ; So C13 = AP23 = D . The Location of D in P1 is 5 etc.The cycle ends when we come back to I .Then C11 P2 1= B C12 P22= C etc.Show that this procedure always leads to a legal placement,GA in placement (Module Assignment):,b 4 c 7 e g 1 1 3 6 7 a d i f h 3 2 4 8Design given in a form of a graph7 8 9d e f 4 5 6 c b i1 2 3 a g h (b) Partition Definition (c) One possible assignment,GA In-placement cont.,Thus the string (below) represents the solution in (c) 1 2 3 4 5 6 7 8 9 a g h c b i d e f with the fitness value of 1/85. Consider 2-modules g and f with the Manhattan distance of 3 (2 vertically and 1 horizontally)The connection between g and f has a weight of 7, thus for gf we have 7x3=21, doing as above for all assignments (in C) we get 85.Other possible solutions: b d e f i g c h a with fitness 1/110 i h a g b f c e d with fitness 1/95,Mutation (In Placement Example),Randomly select two gates (one gate and a dummy gate ) and interchange them . Interchange two arbitrary rows or columns (massive mutation ) Do a cyclic rotation of the entire placement i.e. P0 C1 , P1 C2, P2 C3, ., Pn C0.,Evaluation Function,Use P/ 2 measure .Lest = Pe , i.e. the sum of all the P/2 s for all nets .Cost = L/LmaxWhere L = 0 if Lest = L max Lest - Lmax otherwiseWhere Lmax is user specified constraint on the maximum wire length . ( a lower bound),Let L max = 1000 Lest1 = 1100 Lest2 = 1500 L1 = 100 L2 = 500Fitness1 = 1/ 1+100 1/100 = 0.01 Fitness2 = 1/1+500 1/500 = 0.002,MCM placement test cases,Genetic Algorithm,Simulated Annealing,Results of placement for GA and SA,Results,GA produced better results than SA .For one large problem it was even faster than SAFor large problems where convergence is slow GA is better because one can make use of the multiple solutio