第 1 页
CS361 (Software Engineering Program) Artificial Intelligence II-Applied Machine Learning Lecture 3 Evolutionary Computation:DifferentialEvolution as anOptimization Method Amr S. Ghoneim (Assistant Professor, Computer Science Dept.) Helwan University Fall 2019 Lecture is based on its counterparts in the following courses (and the following resources): o Evolutionary Computing, University of Vaasa (Finland), Electrical & Energy Eng. o Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization 11: 341–359, 1997. o Data Clustering Method based on Mixed Similarity Measures, (ICORES 2017), 192-199 o Differential Evolution, University of Colorado (USA), Colorado Springs.
第 2 页
Machine Learning? {A r t i f i c i a l I n t e l l i g e n c e} M a c h i n e L e a r n i n g M a p 2
第 4 页
Evolutionary Computation (EC) o Evolutionary Computing (or Evolutionary Algorithms “EA”) is a field of science and engineering that tries to apply some phenomena that appears in the nature to the optimization. o Most notable is the adaptation of Charles Darwin’s evolution theory in order to solve difficult search and optimization tasks. o The method is universally applicable, since it has been successfully applied to almost all thinkable search & optimization problems in engineering, science & people’s everyday life.
第 7 页
Example: The 8 Queens Problem .. ➢ Place 8 queens on an 8x8 chessboard in such a way that they cannot check each other.
第 8 页
The 8 Queens Problem: Representation .. Phenotype: A board’s configuration .. Genotype: A permutation of Obvious mapping the numbers 1 : 8 1 3 5 2 6 4 7 8
第 9 页
The 8 Queens Problem: Fitness Function (Evaluation) .. o Penalty of one queen: the number of queens she can check. o Penalty of a configuration: the sum of the penalties of all queens. o Note: penalty is to be minimized o Fitness of a configuration: inverse penalty to be maximized
第 10 页
The 8 Queens Problem: Parents’ Selection for Recombination (Crossover).. Selecting Parents for Crossover/Recombination: o For e.g., by picking randomly 5 parents, and then select the best two to undergo crossover.
第 11 页
The 8 Queens Problem: Recombination (Crossover) .. Combining two chromosomes (in this case, permutations) into two new permutations: o Choose a random crossover point .. o Copy first parts into both children .. o Create the second part by inserting values from the other parent: ▪ In the order they appear there (at that parent) .. ▪ Beginning after the selected crossover point .. and .. ▪ Skipping values already in the child. 1 3 5 2 6 4 7 8 1 3 5 4 2 8 7 6 8 7 6 5 4 3 2 1 8 7 6 2 4 1 3 5
第 12 页
The 8 Queens Problem: Mutation .. o Small variation in one permutation: o For e.g., swapping values of two randomly chosen positions. 1 3 5 2 6 4 7 8 1 3 7 2 6 4 5 8
第 13 页
The 8 Queens Problem: Parents’ Selection for Replacement .. Survivors’ Selection (Replacement; “Creating a new generation”) .. For Example: when inserting a new child into the population, choose an existing member to replace by: o Sorting the whole population by decreasing fitness. o Enumerating this list from high to low. o Replacing the first with a fitness lower than the given child.
第 14 页
The 8 Queens Problem: Summary .. Note that this is only one possible set of choices of operators and parameters.
第 15 页
Typical Behaviour of an EA .. Phases in optimising on a 1-dimensional fitness landscape: An Early Phase: Quasi-random population distribution. A Middle Phase: Population arranged around/on hills. A Late phase: Population concentrated on high hills.
第 16 页
Typical Run: Progression of Fitness Best fitness in populationTime (Number of Generations) Typical run of an EA shows so-called “anytime behavior” ..
第 17 页
Are long runs beneficial? Progress in 2nd half Progress in 1st half Best fitness in population Time (Number of Generations) Answer: - it depends on how much you want the last bit of progress ..
第 18 页
Is it worth spending effort on smart initialisation? F F: fitness after smart initialisation T: time needed to reach level F after random initialisation Best fitness in population T Time (Number of Generations) Answer: - it depends. Possibly, if good solutions/methods exist ..
第 19 页
Evolutionary Algorithms DifferentialEvolution A generic Nature-inspired population- based global-search metaheuristic optimization algorithm. Based on vector differences and is therefore primarily suited for numerical optimization problems. 19
第 20 页
Requirements on a Practical Minimization Technique o Ability to handle non-differentiable, nonlinear, and multimodal cost functions. o Parallelizability to cope with computation intensive cost functions. o Ease of use, in particular, there should be few control variables or parameters. o Good convergence properties, i.e., consistent convergence to the global minimum (optimum) in consecutive independent trials.
评论 (0)
暂无评论。快来抢沙发吧！