Bài 22: Thuật Toán Di Truyền - Lập Trình AI Bằng Python - VnCoder

• Học lập trình
• |
• Bài viết
• |
• Tin tức
• |
• Tuyển dụng
• |
• Liên hệ
• |

• Đăng ký
• |
• Đăng nhập

PHP

Laravel

Android

Java

HTML5

CSS3

NodeJS

VueJS

Swift

Python

Machine Learning

C/C++

Linux/Server

SQL

Javascript

Game

Phân tích thiết kế hệ thống

Servlet/JSP

AI

1. Trang chủ
2. AI
3. Lập trình AI bằng Python
4. Thuật toán di truyền

• Bài 1: Tổng quan AI
• Bài 2: Machine Learning
• Bài 3: Chuẩn bị dữ liệu
• Bài 4: Supervised Learning: Classification phần 1
• Bài 5: Supervised Learning: Classification phần 2
• Bài 6: Supervised Learning: Regression
• Bài 7: Logic Programming
• Bài 8: Unsupervised Learning: Clustering phần 1
• Bài 9: Unsupervised Learning: Clustering phần 2
• Bài 10: Natural Language Processing
• Bài 11: NLTK Package phần 1
• Bài 12: NLTK Package phần 2
• Bài 13: Analyzing Time Series Data phần 1
• Bài 14: Analyzing Time Series Data phần 2
• Bài 15: Nhận diện giọng nói phần 1
• Bài 16: Nhận diện giọng nói - phần 2
• Bài 17: Heuristic Search
• Bài 18: Gaming - Phần 1
• Bài 19: Gaming - Phần 2
• Bài 20: Neural Networks
• Bài 21: Reinforcement Learning
• Bài 22: Thuật toán di truyền
• Bài 23: Computer Vision
• Bài 24: Deep Learning

Bài 22: Thuật toán di truyền - Lập trình AI bằng Python

Đăng bởi: Admin | Lượt xem: 6101 | Chuyên mục: AI Trong bài hôm nay, chúng ta sẽ tìm hiểu chi tiết về thuật toán di truyền trong AI

1. Thuật toán di truyền là gì ?

Thuật toán di truyền (GA) là thuật toán tìm kiếm dựa trên các khái niệm về chọn lọc tự nhiên và di truyền. GAs là một tập con của một nhánh tính toán lớn hơn nhiều được gọi là Tính toán tiến hóa.GA được phát triển bởi John Holland và các sinh viên và đồng nghiệp của ông tại Đại học Michigan, nổi bật nhất là David E. Goldberg. Kể từ đó, nó đã được thử trên các vấn đề tối ưu hóa khác nhau với mức độ thành công cao.Trong GAs, ta có một nhóm các giải pháp khả thi cho vấn đề đã cho. Những dung dịch này sau đó trải qua quá trình tái tổ hợp và đột biến (giống như trong di truyền tự nhiên), tạo ra những đứa trẻ mới và quá trình này được lặp lại trong nhiều thế hệ khác nhau. Mỗi cá thể (hoặc giải pháp ứng cử viên) được chỉ định một giá trị phù hợp (dựa trên giá trị hàm mục tiêu của nó) và các cá thể lai tạo có cơ hội cao hơn để giao phối và sinh ra các cá thể phù hợp. Điều này phù hợp với Học thuyết của Darwin về sự sống còn của những người khỏe mạnh nhất.Do đó, nó tiếp tục phát triển các cá nhân hoặc giải pháp tốt hơn qua nhiều thế hệ, cho đến khi đạt được tiêu chí dừng.Thuật toán di truyền về bản chất là đủ ngẫu nhiên, nhưng chúng hoạt động tốt hơn nhiều so với tìm kiếm cục bộ ngẫu nhiên (nơi ta chỉ thử các giải pháp ngẫu nhiên, theo dõi các giải pháp tốt nhất cho đến nay), vì chúng cũng khai thác thông tin lịch sử.

2. Cách sử dụng GA cho việc tối ưu hoá vấn đề :

Tối ưu hóa là một hành động làm cho thiết kế, tình huống, nguồn lực và hệ thống trở nên hiệu quả nhất có thể. Sơ đồ khối sau đây cho thấy quá trình tối ưu hóa:

a. Các giai đoạn của cơ chế GA cho quá trình tối ưu hóa :

Sau đây là trình tự các bước của cơ chế GA khi được sử dụng để tối ưu hóa các vấn đề.

1. Tạo ngẫu nhiên quần thể ban đầu.
2. Chọn giải pháp ban đầu với các giá trị phù hợp nhất.
3. Tổng hợp lại các giải pháp đã chọn bằng cách sử dụng các toán tử đột biến và chéo.
4. Đưa một con lai vào quần thể.
5. Bây giờ, nếu điều kiện dừng được đáp ứng, hãy trả lại giải pháp với giá trị thể lực tốt nhất của chúng. Hãy chuyển sang bước 2.

3. Các thư viện hỗ trợ cần thiết :

Để giải quyết vấn đề bằng cách sử dụng Thuật toán di truyền trong Python, tôi sẽ sử dụng một gói mạnh mẽ cho GA có tên là DEAP. Nó là một thư viện của khung tính toán tiến hóa mới để tạo mẫu nhanh và thử nghiệm các ý tưởng. Tôi có thể cài đặt gói này với sự trợ giúp của lệnh sau trên dấu nhắc lệnh:pip install deapconda:conda install -c conda-forge deap

4. Thực hiện các giải pháp sử dụng thuật toán di truyền

Phần này giải thích cho bạn cách triển khai các giải pháp sử dụng Thuật toán di truyền.

a. Tạo các mẫu bit

Ví dụ sau đây cho bạn thấy cách tạo một chuỗi bit chứa 15 chuỗi, dựa trên bài toán One Max.import random from deap import base, creator, toolsXác định chức năng đánh giá. Đây là bước đầu tiên để tạo ra một thuật toán di truyền.def eval_func(individual): target_sum = 15 return len(individual) - abs(sum(individual) - target_sum),Tạo toolbox với các thông số phù hợpdef create_toolbox(num_bits): creator.create("FitnessMax", base.Fitness, weights=(1.0,)) creator.create("Individual", list, fitness=creator.FitnessMax)toolbox = base.Toolbox() toolbox.register("attr_bool", random.randint, 0, 1) toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, num_bits) toolbox.register("population", tools.initRepeat, list, toolbox.individual)Đăng kí evaluation operatortoolbox.register("evaluate", eval_func)Đăng kí crossover operatortoolbox.register("mate", tools.cxTwoPoint)Đăng kí mutation operator :toolbox.register("mutate", tools.mutFlipBit, indpb = 0.05)Xác định đối tượng để breeding :toolbox.register("select", tools.selTournament, tournsize = 3) return toolbox if __name__ == "__main__": num_bits = 45 toolbox = create_toolbox(num_bits) random.seed(7) population = toolbox.population(n = 500) probab_crossing, probab_mutating = 0.5, 0.2 num_generations = 10 print('\nEvolution process starts')Đánh giá toàn bộ population :fitnesses = list(map(toolbox.evaluate, population)) for ind, fit in zip(population, fitnesses): ind.fitness.values = fit print('\nEvaluated', len(population), 'individuals')Tạo và lặp lại qua nhiều thế hệ :for g in range(num_generations): print("\n- Generation", g)Lựa chọn các cá thể thế hệ tiếp theooffspring = toolbox.select(population, len(population))nhân bản các cá thể đã chọnoffspring = list(map(toolbox.clone, offspring))Áp dụng trao đổi chéo và đột biến trên đời confor child1, child2 in zip(offspring[::2], offspring[1::2]): if random.random() < probab_crossing: toolbox.mate(child1, child2)Xóa giá trị thể chất của trẻdel child1.fitness.values del child2.fitness.valuesáp dụng mauationfor mutant in offspring: if random.random() < probab_mutating: toolbox.mutate(mutant) del mutant.fitness.valuesĐánh giá những cá nhân có thể trạng không hợp lệinvalid_ind = [ind for ind in offspring if not ind.fitness.valid] fitnesses = map(toolbox.evaluate, invalid_ind) for ind, fit in zip(invalid_ind, fitnesses): ind.fitness.values = fit print('Evaluated', len(invalid_ind), 'individuals')Tiếp theo thay thế population với cá nhân thế hệ tiếp theopopulation[:] = offspringIn số liệu thống kê cho các thế hệ hiện tại :fits = [ind.fitness.values[0] for ind in population] length = len(population) mean = sum(fits) / length sum2 = sum(x*x for x in fits) std = abs(sum2 / length - mean**2)**0.5 print('Min =', min(fits), ', Max =', max(fits)) print('Average =', round(mean, 2), ', Standard deviation =', round(std, 2)) print("\n- Evolution ends")In ra kết quả cuối cùng :best_ind = tools.selBest(population, 1)[0] print('\nBest individual:\n', best_ind) print('\nNumber of ones:', sum(best_ind)) Following would be the output: Evolution process starts Evaluated 500 individuals - Generation 0 Evaluated 295 individuals Min = 32.0 , Max = 45.0 Average = 40.29 , Standard deviation = 2.61 - Generation 1 Evaluated 292 individuals Min = 34.0 , Max = 45.0 Average = 42.35 , Standard deviation = 1.91 - Generation 2 Evaluated 277 individuals Min = 37.0 , Max = 45.0 Average = 43.39 , Standard deviation = 1.46 … … … … - Generation 9 Evaluated 299 individuals Min = 40.0 , Max = 45.0 Average = 44.12 , Standard deviation = 1.11 - Evolution ends Best individual: [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1] Number of ones: 15

5. Symbol Regression Problem

Đó là một trong những vấn đề được biết đến nhiều nhất trong lập trình di truyền. Tất cả các bài toán hồi quy tượng trưng đều sử dụng phân phối dữ liệu tùy ý và cố gắng khớp dữ liệu chính xác nhất với công thức biểu tượng. Thông thường, một số đo như RMSE (Root Mean Square Error) được sử dụng để đo lường sức khỏe của một cá nhân. Đây là một bài toán hồi quy cổ điển và ở đây chúng ta đang sử dụng phương trình 5x^3-6x^2 + 8x = 1. Ta cần làm theo tất cả các bước như sau trong ví dụ trên, nhưng phần chính sẽ là tạo các tập hợp nguyên thủy vì chúng là các khối xây dựng cho các cá nhân để việc đánh giá có thể bắt đầu. Ở đây chúng ta sẽ sử dụng tập hợp nguyên thủy cổ điển.Đoạn code sau đây giải thích chi tiết điều này:import operator import math import random import numpy as np from deap import algorithms, base, creator, tools, gp def division_operator(numerator, denominator): if denominator == 0: return 1 return numerator / denominator def eval_func(individual, points): func = toolbox.compile(expr=individual) return math.fsum(mse) / len(points), def create_toolbox(): pset = gp.PrimitiveSet("MAIN", 1) pset.addPrimitive(operator.add, 2) pset.addPrimitive(operator.sub, 2) pset.addPrimitive(operator.mul, 2) pset.addPrimitive(division_operator, 2) pset.addPrimitive(operator.neg, 1) pset.addPrimitive(math.cos, 1) pset.addPrimitive(math.sin, 1) pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1)) pset.renameArguments(ARG0 = 'x') creator.create("FitnessMin", base.Fitness, weights = (-1.0,)) creator.create("Individual",gp.PrimitiveTree,fitness=creator.FitnessMin) toolbox = base.Toolbox() toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2) toolbox.expr) toolbox.register("population",tools.initRepeat,list, toolbox.individual) toolbox.register("compile", gp.compile, pset = pset) toolbox.register("evaluate", eval_func, points = [x/10. for x in range(-10,10)]) toolbox.register("select", tools.selTournament, tournsize = 3) toolbox.register("mate", gp.cxOnePoint) toolbox.register("expr_mut", gp.genFull, min_=0, max_=2) toolbox.register("mutate", gp.mutUniform, expr = toolbox.expr_mut, pset = pset) toolbox.decorate("mate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17)) toolbox.decorate("mutate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17)) return toolbox if __name__ == "__main__": random.seed(7) toolbox = create_toolbox() population = toolbox.population(n = 450) hall_of_fame = tools.HallOfFame(1) stats_fit = tools.Statistics(lambda x: x.fitness.values) stats_size = tools.Statistics(len) mstats = tools.MultiStatistics(fitness=stats_fit, size = stats_size) mstats.register("avg", np.mean) mstats.register("std", np.std) mstats.register("min", np.min) mstats.register("max", np.max) probab_crossover = 0.4 probab_mutate = 0.2 number_gen = 10 population, log = algorithms.eaSimple(population, toolbox, probab_crossover, probab_mutate, number_gen, stats = mstats, halloffame = hall_of_fame, verbose = True)Lưu ý rằng tất cả các bước cơ bản giống như được sử dụng trong khi tạo các mẫu bit. Chương trình này sẽ cung cấp cho chúng ta đầu ra là min, max, std (độ lệch chuẩn) sau 10 số thế hệ. Bài tiếp theo: Computer Vision >>

Theo dõi VnCoder trên Facebook, để cập nhật những bài viết, tin tức và khoá học mới nhất!

Chia sẻ bài viết

• Bài 1: Tổng quan AI
• Bài 2: Machine Learning
• Bài 3: Chuẩn bị dữ liệu
• Bài 4: Supervised Learning: Classification phần 1
• Bài 5: Supervised Learning: Classification phần 2
• Bài 6: Supervised Learning: Regression
• Bài 7: Logic Programming
• Bài 8: Unsupervised Learning: Clustering phần 1
• Bài 9: Unsupervised Learning: Clustering phần 2
• Bài 10: Natural Language Processing
• Bài 11: NLTK Package phần 1
• Bài 12: NLTK Package phần 2
• Bài 13: Analyzing Time Series Data phần 1
• Bài 14: Analyzing Time Series Data phần 2
• Bài 15: Nhận diện giọng nói phần 1
• Bài 16: Nhận diện giọng nói - phần 2
• Bài 17: Heuristic Search
• Bài 18: Gaming - Phần 1
• Bài 19: Gaming - Phần 2
• Bài 20: Neural Networks
• Bài 21: Reinforcement Learning
• Bài 22: Thuật toán di truyền
• Bài 23: Computer Vision
• Bài 24: Deep Learning