人工智能课件 summary.ppt

* * * * * * * * 2.6 Q-Learning Algorithm * AI:Summary * r(state, action) immediate reward values Q(state, action) values V*(state) values 100 0 0 100 G 0 0 0 0 0 0 0 0 0 90 81 100 G 0 81 72 90 81 81 72 90 81 100 G 90 100 0 81 90 100 Using the discounted cumulative reward, the discount factor = 0.9 81=0+0.9*90 Learning the Q-value Note: Q and V* closely related Allows us to write Q recursively as Using Q-values * AI:Summary * A kind of Temporal Difference (TD) learning Solve: How to learn? Solve: How to choose the best action? Q-Learning Steps FOR each s, a DO Initialize table entry: Observe current state s WHILE (true) DO Select action a and execute it Receive immediate reward r Observe new state s’ Update table entry for as follows Move: record transition from s to s’ * AI:Summary * 2.7 Evolutionary Computation Evolutionary Computation is based on biological metaphor: Optimized Behavior – Optimal Solution Individual – Solution; Fitness – Objective; Environment – Problem Ingredients of EC Representation: Individual and Population Fitness evaluation: Objective Selection: Parent and Survivor Genetic Operators: Mutation and/or Recombination Initialization/Termination AI:Summary * * The Ingredients AI:Summary * * t t + 1 mutation recombination reproduction selection Image from Ida Sprinkhuizen-Kuyper: Introduction to Evolutionary Computation, 2000. The Evolution Mechanism Increasing diversity by genetic operators mutation Recombination Decreasing diversity by selection of parents of survivors AI:Summary * * The Evolutionary Cycle AI:Summary * * Recombination Mutation Population Offspring Parents Parent Selection Survivor Selection Image from Ben Paechter: Evolutionary Computing – A Practical Introduction Desirable Performance of EC AI:Summary * * Image from: Introduction to Stochastic Search and Optimization (ISSO) by J. C. Spall How to build a EA? Step1. Design a representation Step2.