Phần 22: Thuật toán di truyền – Lập trình AI bằng Python
Trong bài hôm nay, ta sẽ xem chi tiết về thuật toán di truyền trong AI
Table of Contents
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 những khái niệm về chọn lọc tự nhiên và di truyền. GAs là 1 tập con của 1 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 xây dựng do 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ừ đấy, nó được thử trên những vấn đề tối ưu khác nhau với mức độ thành công cao.
Trong GAs, ta có 1 nhóm các biện pháp khả thi cho vấn đề đã cho. Những dung dịch này rồi 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 nên những đứa trẻ mới và quá trình này được lặp lại trong khá nhiều thế hệ khác nhau. Mỗi cá thể (hay biện pháp ứng cử viên) được chỉ định 1 giá trị phù hợp (dựa vào 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 đó phù hợp đối 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 hay biện pháp tốt hơn qua nhiều thế hệ, cho tới khi đạt 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 biện pháp ngẫu nhiên, theo dõi các biện pháp tốt nhất cho tới nay), vì chúng cũng khai thác thông tin lịch sử.
2. Cách sử dụng GA đối với việc tối ưu hoá vấn đề :
Tối ưu là 1 hành động làm thiết kế, tình huống, nguồn lực và hệ thống trở nên hiệu quả tốt nhất có thể. Sơ đồ khối dưới đây cho ta thấy quá trình tối ưu:
a. Các giai đoạn của cơ chế GA cho quá trình tối ưu :
Sau đây chính là trình tự những bước của cơ chế GA khi được dùng để tối ưu những vấn đề.
- Tạo ngẫu nhiên quần thể ban đầu.
- Chọn biện pháp ban đầu với những giá trị phù hợp nhất.
- Tổng hợp lại các biện pháp chọn bằng cách sử dụng các toán tử đột biến và chéo.
- Đưa 1 con lai vào quần thể.
- Hiện tại, nếu như điều kiện dừng được đáp ứng, hãy trả lại biện pháp với giá trị thể lực tốt nhất của chúng. Hãy chuyển qua bước 2.
3. Các thư viện hỗ trợ cần thiết :
Để giải quyết được vấn đề bằng cách sử dụng Thuật toán di truyền trong Python, tôi sẽ sử dụng 1 gói mạnh mẽ cho GA có tên là DEAP. Nó là 1 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ự giúp đỡ của lệnh sau trên dấu nhắc lệnh:
pip set up deapconda:
conda set up -c conda-forge deap4. Thực hiện các biện pháp sử dụng thuật toán di truyền
Phần này giải thích cho các bạn cách triển khai các biện pháp sử dụng Thuật toán di truyền.
a. Tạo các mẫu bit
Ví dụ dưới đây cho các bạn thấy cách tạo 1 chuỗi bit chứa 15 chuỗi, dựa vào bài toán One Max.
import random
from deap import base, creator, instrumentsXác định tính năng đánh giá. Đây chính là bước trước tiên để tạo nên 1 thuật toán di truyền.
def eval_func(particular person):
target_sum = 15
return len(particular person) - abs(sum(particular person) - target_sum),Tạo toolbox với những thông số phù hợp
def create_toolbox(num_bits):
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", listing, health=creator.FitnessMax)toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("particular person", instruments.initRepeat, creator.Individual,
toolbox.attr_bool, num_bits)
toolbox.register("inhabitants", instruments.initRepeat, listing, toolbox.particular person)Đăng kí analysis operator
toolbox.register("consider", eval_func)Đăng kí crossover operator
toolbox.register("mate", instruments.cxTwoPoint)Đăng kí mutation operator :
toolbox.register("mutate", instruments.mutFlipBit, indpb = 0.05)Xác định đối tượng để breeding :
toolbox.register("choose", instruments.selTournament, tournsize = 3)
return toolbox
if __name__ == "__main__":
num_bits = 45
toolbox = create_toolbox(num_bits)
random.seed(7)
inhabitants = toolbox.inhabitants(n = 500)
probab_crossing, probab_mutating = 0.5, 0.2
num_generations = 10
print('nEvolution course of begins')Đánh giá tất cả inhabitants :
fitnesses = listing(map(toolbox.consider, inhabitants))
for ind, slot in zip(inhabitants, fitnesses):
ind.health.values = match
print('nEvaluated', len(inhabitants), 'people')Tạo và lặp lại qua nhiều thế hệ :
for g in vary(num_generations):
print("n- Generation", g)Chọn lựa các cá thể thế hệ tiếp theo
offspring = toolbox.choose(inhabitants, len(inhabitants))nhân bản các cá thể chọn
offspring = listing(map(toolbox.clone, offspring))Áp dụng trao đổi chéo 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.health.values
del child2.health.valuesáp dụng mauation
for mutant in offspring:
if random.random() < probab_mutating:
toolbox.mutate(mutant)
del mutant.health.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.consider, invalid_ind)
for ind, slot in zip(invalid_ind, fitnesses):
ind.health.values = match
print('Evaluated', len(invalid_ind), 'people')Tiếp theo thay thế inhabitants với cá nhân thế hệ tiếp theo
inhabitants[:] = offspringIn số liệu thống kê cho các thế hệ hiện giờ :
suits = [ind.fitness.values[0] for ind in inhabitants]
size = len(inhabitants)
imply = sum(suits) / size
sum2 = sum(x*x for x in suits)
std = abs(sum2 / size - imply**2)**0.5
print('Min =', min(suits), ', Max =', max(suits))
print('Average =', spherical(imply, 2), ', Standard deviation =',
spherical(std, 2))
print("n- Evolution ends")In ra kết quả cuối cùng :
best_ind = instruments.selBest(inhabitants, 1)[0]
print('nBest particular person:n', best_ind)
print('nNumber of ones:', sum(best_ind))
Following can be the output:
Evolution course of begins
Evaluated 500 people
- Generation 0
Evaluated 295 people
Min = 32.0 , Max = 45.0
Average = 40.29 , Standard deviation = 2.61
- Generation 1
Evaluated 292 people
Min = 34.0 , Max = 45.0
Average = 42.35 , Standard deviation = 1.91
- Generation 2
Evaluated 277 people
Min = 37.0 , Max = 45.0
Average = 43.39 , Standard deviation = 1.46
… … … …
- Generation 9
Evaluated 299 people
Min = 40.0 , Max = 45.0
Average = 44.12 , Standard deviation = 1.11
- Evolution ends
Best particular person:
[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: 155. Symbol Regression Problem
Đó là 1 trong các vấn đề được biết tới nhiều nhất trong lập trình di truyền. Toàn bộ các bài toán hồi quy tượng trưng đều sử dụng phân phối dữ liệu thoải mái và nỗ lực 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, những đo như RMSE (Root Mean Square Error) được dùng để đo lường sức khỏe của 1 cá nhân. Đây chính là 1 bài toán hồi quy cổ điển và tại đây ta đang dùng phương trình 5x^3-6x^2 + 8x = 1. Ta cần thực hiện theo toàn bộ các bước như dưới đây 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à những khối xây dựng cho các cá nhân để việc đánh giá có thể bắt đầu. Tại đây ta sẽ sử dụng tập hợp nguyên thủy cổ điển.
Đoạn mã dưới đây giải thích chi tiết điều đó:
import operator
import math
import random
import numpy as np
from deap import algorithms, base, creator, instruments, gp
def division_operator(numerator, denominator):
if denominator == 0:
return 1
return numerator / denominator
def eval_func(particular person, factors):
func = toolbox.compile(expr=particular person)
return math.fsum(mse) / len(factors),
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,health=creator.FitnessMin)
toolbox = base.Toolbox()
toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
toolbox.expr)
toolbox.register("inhabitants",instruments.initRepeat,listing, toolbox.particular person)
toolbox.register("compile", gp.compile, pset = pset)
toolbox.register("consider", eval_func, factors = [x/10. for x in range(-10,10)])
toolbox.register("choose", instruments.selTournament, tournsize = 3)
toolbox.register("mate", gp.cxOneLevel)
toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
toolbox.register("mutate", gp.mutUniform, expr = toolbox.expr_mut, pset = pset)
toolbox.embellish("mate", gp.staticLimit(key = operator.attrgetter("peak"), max_value = 17))
toolbox.embellish("mutate", gp.staticLimit(key = operator.attrgetter("peak"), max_value = 17))
return toolbox
if __name__ == "__main__":
random.seed(7)
toolbox = create_toolbox()
inhabitants = toolbox.inhabitants(n = 450)
hall_of_fame = instruments.HallOfFame(1)
stats_fit = instruments.Statistics(lambda x: x.health.values)
stats_size = instruments.Statistics(len)
mstats = instruments.MultiStatistics(health=stats_fit, dimension = stats_size)
mstats.register("avg", np.imply)
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
inhabitants, log = algorithms.eaSimple(inhabitants, toolbox,
probab_crossover, probab_mutate, number_gen,
stats = mstats, halloffame = hall_of_fame, verbose = True)Chú ý rằng toàn bộ các bước căn bản giống được dùng trong khi tạo các mẫu bit. Chương trình này sẽ cung cấp cho ta đầu ra là min, max, std (độ lệch chuẩn) sau 10 số thế hệ.
