tailieunhanh - An Introduction to Genetic Algorithms phần 8

Hình thành các biểu thức này, chúng tôi liệt kê các chuỗi theo thứ tự từ 0 đến 2L 1. Nó không phải là khó để chứng minh rằng thực hiện tính toán này bằng cách sử dụng một thứ tự khác nhau của chuỗi sản lượng cùng một câu trả lời. Khả năng rằng số lượng chính xác của lần xuất hiện của mỗi y chuỗi (dân số Pj) được sản xuất (từ dân số Pi) | Chapter 4 Theoretical Foundations of Genetic Algorithms Nix and Vose we will enumerate this for each possible string. The number of ways of choosing Z0 j occurrences of string 0 for the Z0 j slots in population j is n Zoj Selecting string 0 Z0 j times leaves n Z 0 j positions to fill in the new population. The number of ways of placing the Zj j occurrences of string 1 in the n Z 0 j positions is n - Zoj k Z1J Continuing this process we can write down an expression for all possible ways of forming population Pj from a set of n selection-and-recombination steps To form this expression we enumerated the strings in order from 0 to 2l 1. It is not hard to show that performing this calculation using a different order of strings yields the same answer. The probability that the correct number of occurrences of each string y in population Pj is produced from population Pj is 2 -1 llPi y 2 . V O The probability that population Pj is produced from population Pị is the product of the previous two expressions forming a multinomial distribution -I n fowl The only thing remaining to do is derive an expression forPi y the probability that string y will be produced from a single selection-and-recombination step acting on population Pị. To do this we can use the matrices F and defined above. pị y is simply the expected proportion of string y in the population produced from Pị under the simple GA. The proportion ofy in Pị is 0 ỵ IỆ- I v where denotes the sum of the components of vector and  y denotes the yth component of vector . The probability that y will be selected at each selection step is 110 Chapter 4 Theoretical Foundations of Genetic Algorithms Fị F I and the expected proportion of string y in the next population is Since Pi y is equivalent to the expected proportion of string y in the next population we can finally write down a finished expression for Qự. f-l u n y-0 M fà Fà Z J Ĩ The matrix Qty gives an exact model of the simple GA acting on finite populations. Nix and .