Bài giảng Máy học nâng cao: Genetic algorithm - Trịnh Tấn Đạt

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:70

Thêm vào BST

Báo xấu

53
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Máy học nâng cao: Genetic algorithm" cung cấp cho người học các kiến thức: Introduction - Genetic algorithm (GA), genetic algorithm operators and parameters, example. Cuối bài giảng có phần bài tập để người học ôn tập và củng cố kiến thức.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Máy học nâng cao: Genetic algorithm - Trịnh Tấn Đạt

Trịnh Tấn Đạt Khoa CNTT – Đại Học Sài Gòn Email: trinhtandat@sgu.edu.vn Website: https://sites.google.com/site/ttdat88/
Contents  Introduction: Genetic Algorithm (GA)  GA Operators and Parameters  Example  Homework
Introduction History Of Genetic Algorithms  “Evolutionary Computing” was introduced in the 1960s by I. Rechenberg.  John Holland wrote the first book on Genetic Algorithms ‘Adaptation in Natural and Artificial Systems’ in 1975.  In 1992 John Koza used genetic algorithm to evolve programs to perform certain tasks. He called his method “Genetic Programming”.
What Are Genetic Algorithms (GAs)?  GAs are search and optimization techniques based on Darwin’s Principle of Natural Selection and Genetic Inheritance.  A class of probabilistic optimization algorithms.  Widely-used in business, science and engineering.
Basic Idea Of Principle Of Natural Selection “Select The Best, Discard The Rest” An Example of Natural Selection:  Rabbits are fast and smart  Some of them are faster and smarter than other rabbits. Thus, they are less likely to be eaten by foxes.  They have a better chance of survival and start breeding.  The resulting baby rabbits (on average) will be faster and smarter  Now, evolved species are more faster and smarter Genetic Algorithms Implement Optimization Strategies By Simulating Evolution Of Species Through Natural Selection
Classes of Search Techniques Search Techniques Calculus Base Guided random search Enumerative Techniques techniques Techniques Fibonacci Sort DFS Dynamic BFS Programming Tabu Search Hill Climbing Simulated Evolutionary Anealing Algorithms Genetic Genetic Programming Algorithms
Nature to Computer Mapping  GAs use a vocabulary borrowed from nature genetics Nature Computer (GAs) Population Set of solutions Individuals in environment Solutions to a problem Individual’s degree of adaptation to its Solutions quality (fitness function) surrounding environment Chromosome Encoding for a Solution Gene Part of the encoding of a solution Selection, crossover and mutation in Stochastic operators nature’s evolutionary process
Working Mechanism Of GAs
Simple Genetic Algorithm Simple_Genetic_Algorithm() { Initialize the Population; Calculate Fitness Function; While(Fitness Value != Optimal Value) { Selection;//Natural Selection, Survival Of Fittest Crossover;//Reproduction, Propagate favorable characteristics Mutation;//Mutation Calculate Fitness Function; } }
Designing GAs ⚫ How to represent chromosomes? ⚫ How to create an initial population? ⚫ How to define fitness function? ⚫ How to define genetic operators? ⚫ How to generate next generation? ⚫ How to define stopping criteria?
GA Operators and Parameters
Search Space and Population  The search space S is the finite set of possible solutions.  Each solution x  S is called an individual  Population of size N is a subset of search space S.  Start with a population of randomly generated individuals, or use  A previously saved population  A set of solutions provided by a human expert  A set of solutions provided by another heuristic algorithm
Representation (Encoding) The process of representing the solution in the form of a string (chromosome) that conveys the necessary information.  Just as in a chromosome, each gene controls a particular characteristic of the individual  Similarly, each bit in the string represents a characteristic of the solution.
Binary Encoding
Binary Encoding  Binary Encoding – Most common method of encoding. Chromosomes are strings of 1s and 0s  In classic genetic algorithms, binary strings of fixed length m are used.  In order to be able to encode each solution of the search space S in a one-to-one way, the inequality 2m  | S |  For example, we have S={1,2,…,15}. Choose m = 4 to represent 15 chromosomes 8 = 23  15  2 4 = 16
Value Encoding  Every chromosome is a string of some values.  Values can be anything connected to problem, form numbers, real numbers or chars to some complicated objects.
Permutation Encoding  Permutation encoding can be used in ordering problems, such as travelling salesman problem or task ordering problem.  In permutation encoding, every chromosome is a string of numbers, which represents number in a sequence.
Tree Encoding  Tree encoding is used mainly for evolving programs or expressions, for genetic programming.  In tree encoding every chromosome is a tree of some objects, such as functions or commands in programming language.
Fitness function A fitness function quantifies the optimality of a solution (chromosome) so that particular solution may be ranked against all the other solutions.  A fitness value is assigned to each solution depending on how close it actually is to solving the problem.  A fitness function is a nonnegative function f f:S→R
Genetic Operators  Reproduction (Selection) Copy existing chromosomes, chosen at random, to the new population.  Recombination (Crossover) Create new chromosomes by recombining randomly chosen substrings from existing chromosomes.  Mutation Create a new chromosome from an existing one by performing small random changes.