Chương này thảo luận chi tiết về các thuật toán di truyền của AI.
Thuật toán di truyền là gì?
Mục lục
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. GA là một tập hợ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 cùng 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, chúng tôi có một loạt các giải pháp khả thi cho vấn đề đã cho. Các 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 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ể phù hợp có cơ hội giao phối và sinh sản cao hơn thợ lắp máy các cá nhân. Điều này phù hợp với Học thuyết Darwin về Sự sống còn của Fittest.
Do đó, nó giữ đang 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 nó đạt đến tiêu chí dừng.
Các 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 chúng tôi 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ử.
Cách sử dụng GA cho các vấn đề về tối ưu hóa?
Tối ưu hóa là một hành động làm cho thiết kế, tình huống, tài nguyên và hệ thống, hiệu quả nhất có thể. Sơ đồ khối sau đây cho thấy quá trình tối ưu hó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 đề.
Bước 1 – Tạo ngẫu nhiên quần thể ban đầu.
Bước 2 – Chọn giải pháp ban đầu với các giá trị phù hợp nhất.
Bước 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à trao đổi chéo.
Bước 4 – Đưa một con lai vào quần thể.
Bước 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. Còn lại, hãy chuyển sang bước 2.
Cài đặt các gói 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, chúng tôi sẽ sử dụng một gói mạnh mẽ cho GA được gọi 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. Chú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 deap
Nếu bạn đang sử dụng anaconda môi trường, sau đó lệnh sau có thể được sử dụng để cài đặt deap –
conda install -c conda-forge deap
Thực hiện các giải pháp sử dụng các thuật toán di truyền
Phần này giải thích cho bạn việc triển khai các giải pháp sử dụng Thuật toán di truyền.
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 Một tối đa vấn đề.
Nhập các gói cần thiết như được hiển thị –
import random from deap import base, creator, tools
Xá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),
Bây giờ, hãy tạo hộp công cụ với các thông số phù hợp –
def create_toolbox(num_bits): creator.create("FitnessMax", base.Fitness, weights=(1.0,)) creator.create("Individual", list, fitness=creator.FitnessMax)
Khởi tạo hộp công cụ
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ý nhà điều hành đánh giá –
toolbox.register("evaluate", eval_func)
Bây giờ, hãy đăng ký nhà điều hành giao nhau –
toolbox.register("mate", tools.cxTwoPoint)
Đăng ký toán tử đột biến –
toolbox.register("mutate", tools.mutFlipBit, indpb = 0.05)
Xác định toán tử để nhân giống –
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ộ dân số –
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 theo –
offspring = toolbox.select(population, len(population))
Bây giờ, sao chép các cá thể đã chọn –
offspring = list(map(toolbox.clone, offspring))
Áp dụng phép lai và đột biến trên đời con –
for 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
Bây giờ, hãy áp dụng đột biến –
for 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')
Bây giờ, thay thế quần thể bằng cá thể thế hệ tiếp theo –
population[:] = offspring
In 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 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
Vấn đề hồi quy ký hiệu
Đây 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 ký hiệu đề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 ký hiệu. Thông thường, một thước đo như RMSE (Root Mean Square Error) được sử dụng để đo thể lực 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 tôi đang sử dụng phương trình 5x3-6x2+ 8x = 1. Chúng 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 để quá trình đá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 mã Python sau giải thích điều này một cách chi tiết:
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ệ.