1、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 conceptsIterative procedure(iterative improvement)Produces a series of “generations of

2、 populations one per iterationEach member of a population represents a feasible solution,called a chromosome. bagchromosomesCombine and die(mating)p1123KmevolutionChromosome-a feasible solutionSelection crossover mutationPk P3The population during iteration of GA is denoted by the “bagPi=X1i,X2i,.,X

3、ni.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

4、) 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, 0=fitness(x)average-fitness(Pj) for ij.We go from Pi to Pi+1 via an evolution function that usually consists of three components called operators.OperatorsSelection: select some

5、 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% 21n34Area is Proportional to fitness valueExampleChromosome fitness A .21 B .14 C .10 D .02 E .33 F .20 - 1.00A21% D 2% 10%F20%E33%B14%

6、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 headCrossoverCrossover operators combine features of highly

7、 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;1000

8、11;1110 ya;100011;1010Xb;101010;1010 yb;101010;1110 MutationMutation 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

9、 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 RepresentationOften a chromosome is encoded as a bit stream. The a

10、ctual 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 pro

11、blem via a GAProblem 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

12、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); i

13、i+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

14、 select_roulette(p); bs bs x; ii+1; end while;return(bs) end; function crossover(p,c) begin bc ; i 0; while(ic) repeat x1 select_roulette(p); x2 select_roulette(p); untill (x1 x2) crossover(x1,x2); bc bc y1; ii+1; if (i p - where |v| = p is number of gates. For a given placement,its associated lengt

15、h 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 operatorsEncoding Assume placement consists of a rectangular grid of slots as shown in the figure on the next slide.Encoding

16、Dummy GatesRow 4Row 3Row 2 Row 1Row 0C4C3C9D6C5C12D5 D7C10C14C13C7C1D3C8C18C2D4C6C11C15D2C17D1C16 Col 0 Col 1 Col 2 Col 3 Col 4 ChipEmpty SlotOccupied SlotC1 (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 connectio

17、ns .For previous placements the encoding is : C16 , D1 , C17 , D2 , C15 , D3 , C 1 etc. (Reading from bottom to top and left to right) GCBAFEDIHEndStartABCDEFGHIEncoding Using for Placement Cross Over ABEABABCDED CEABDCCDEEffect of Single Point Cross Over (Illegal Placements) A simple one- point cro

18、ssover operator leads to illegal placements as shown above.Parent 1 Child 1 Parent 2 Child 2Child 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 CrossoverLet P1 and P2 denote the 2 parents & C1 and C2 denote the 2 chil

19、dren .Let P1 , P2 , C1 , C2 arrays be of size r.cChild 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 th

20、is 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. Thi

21、s 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

22、E G H C2 = H B G E C ADFIFDIACycle CrossoverC10 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

23、 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 assignmentGA 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

24、 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

25、with fitness 1/110 i h a g b f c e d with fitness 1/95Mutation (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, .,

26、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 L

27、2 = 500Fitness1 = 1/ 1+100 1/100 = 0.01 Fitness2 = 1/1+500 1/500 = 0.002 Design No of Chips No of SlotsNo of Nets Mcc2377 x 74767Viper104 x 3658Find 104 x 4 479TLC94 x 3 203Move Machine 73 x 3 366FIFO73 x 3 187MCM placement test cases DesignWire Length106 micronsHeat Cost CaloriesExec. Time Sec.Wire

28、 Length106 micronsHeat Cost CaloriesExec. Time SecMcc236009243374100132313874Viper21.6030325.566.67235Find1172534612012997Move6.52.71307.60 25FIFO1.86101502.19087TLC1.665.41042.2338.832 Genetic Algorithm Simulated AnnealingResults of placement for GA and SAResults 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