tailieunhanh - An Introduction to Genetic Algorithms phần 7

thí nghiệm kiểm soát so sánh hiệu suất của GA với các phương pháp tìm kiếm khác như leo núi đồi. Ở mức độ nào các kết quả bị hạn chế bởi thực tế rằng chỉ có một số điều kiện cho phép (tức là, điều kiện có liên từ của các phạm vi ngày độc lập | Chapter 4 Theoretical Foundations of Genetic Algorithms schemas with the best observed fitness. The SBBH was not what Holland 1975 proposed and it has never been proved or even empirically validated but it implicitly underlies the assumption that deceptive fitness functions will be difficult for a GA. Grefenstette gives two possible reasons related to his earlier concerns about the two-armed-bandit analogy why the SBBH can fail Collateral convergence Once the population begins to converge at some loci the samples of some schemas are no longer uniform. For example suppose instances of 111 are highly fit and the population has more or less converged on those bits . nearly every member of the population is an instance of that schema . Then almost all samples of say 000 will actually be samples of 111000 . This may prevent the GA from making any accurate estimate of u 000 . High fitness variance If a schema s static average fitness has high variance the GA may not be able to make an accurate estimate of this static average fitness. The fitness function given by equation is an example of this the variance of 1 is high so the GA converges on the highfitness subregions of it. As before this biases all subsequent samples of this schema preventing an accurate estimate of its static fitness. These points bear directly on the relevance of deception to the behavior of GAs since deceptive fitness functions are defined entirely in terms of the static average fitnesses of schemas. To illustrate the problems with this Grefenstette gives examples of deceptive problems that are easy for GAs to optimize and of nondeceptive problems that are arbitrarily hard for GAs to optimize. He concludes that deception is neither necessary nor sufficient to cause difficulties for GAs and that its relevance to the study of GAs remains to be demonstrated. There is nothing to indicate that the features listed above harm search performance of GAs they only demonstrate the danger of drawing .