Bài giảng Khai phá dữ liệu (Data mining): Genetic algorithm - Trịnh Tấn Đạt
Số trang: 70
Loại file: pdf
Dung lượng: 4.68 MB
Lượt xem: 15
Lượt tải: 0
Xem trước 7 trang đầu tiên của tài liệu này:
Thông tin tài liệu:
Bài giảng Khai phá dữ liệu (Data mining): Genetic algorithm, chương này trình bày những nội dung về: introduction to genetic algorithms (GA); classes of search techniques; nature to computer mapping; GA operators and parameters; example and homework;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Khai phá dữ liệu (Data mining): 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, ...
Nội dung trích xuất từ tài liệu:
Bài giảng Khai phá dữ liệu (Data mining): 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, ...
Tìm kiếm theo từ khóa liên quan:
Bài giảng Khai phá dữ liệu Khai phá dữ liệu Data mining Genetic algorithm Simple genetic algorithm Binary encoding Permutation encoding Roulette wheel selectionGợi ý tài liệu liên quan:
-
Bài tập lớn môn Khai phá dữ liệu: Phân lớp dữ liệu số bằng giải thuật K-NN
22 trang 351 1 0 -
Ứng dụng khai phá dữ liệu nâng cao dịch vụ thư viện số
16 trang 230 0 0 -
Thuật toán khai phá tập mục thường xuyên trong cơ sở dữ liệu lớn thông qua mẫu đại diện
11 trang 222 0 0 -
17 trang 186 0 0
-
Luận văn: Tổng quan khai phá dữ liệu và ứng dụng
55 trang 170 0 0 -
8 trang 131 0 0
-
4 trang 115 0 0
-
Bài giảng Khai phá dữ liệu: Chương 5 - TS. Võ Thị Ngọc Châu
116 trang 48 0 0 -
Bài giảng Khai phá dữ liệu (Data mining): Chương 8 - ĐH Bách khoa TP.HCM
8 trang 45 0 0 -
68 trang 44 0 0