Thuật toán di truyền là gì?
Thuật toán di truyền (GA) là các 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, đáng chú ý nhất là David E. Goldberg. Kể từ đó, nó đã được thử nghiệm trên các bài toán tối ưu hóa khác nhau với mức độ thành công cao.
Trong GA, chúng tôi có một nhóm các giải pháp khả thi cho vấn đề đã cho. Những giải pháp 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 cho nhiều thế hệ khác nhau. Mỗi cá thể (hoặc giải pháp ứng cử viên) được gán 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 hơn có cơ hội cao hơn để giao phối và sinh ra các cá thể phù hợp hơn . Điều này phù hợp với Thuyết sinh tồn của Darwin về loài thích nghi nhất .
Do đó, nó tiếp tục phát triển các cá thể hoặc giải pháp tốt hơn qua nhiều thế hệ, cho đến khi đạt đến điểm 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ử.
Làm cách nào để sử dụng GA cho các vấn đề 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 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
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 dân số ban đầu một cách ngẫu nhiên.
- 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 – Kết hợp lại các giải pháp đã chọn bằng cách sử dụng toán tử đột biến và chéo.
- Bước 4 – Đưa một thế hệ con 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ả về giải pháp có giá trị phù hợp nhất của chúng. Khác đi đến 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ó tên là DEAP . Nó là một thư viện 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 ta 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 môi trường anaconda , thì có thể sử dụng lệnh sau để cài đặt deap −
conda install -c conda-forge deap
Thực hiện các giải pháp bằ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 bằ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 bit, dựa trên bài toán Một Max . Nhập các gói cần thiết như được hiển thị
import random
from deap import base, creator, tools
Định nghĩa hàm đánh giá. Đó 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 tham 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ý toán tử đánh giá
toolbox.register("evaluate", eval_func)Bây giờ, hãy đăng ký toán tử chéo
toolbox.register("mate", tools.cxTwoPoint)
Đăng ký một 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 các thế hệ
for g in range(num_generations):
print("\n- Generation", g)
Lựa chọn các cá nhân thế hệ tiếp theo
offspring = toolbox.select(population, len(population))
Bây giờ, sao chép các cá nhân đã chọn –
offspring = list(map(toolbox.clone, offspring))
Áp dụng lai ghép và đột biến trên thế hệ 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ể lực của con
del child1.fitness.values
del child2.fitness.values
Bây giờ, áp dụng đột biến
for mutant in offspring:
if random.random() < probab_mutating:
toolbox.mutate(mutant)
del mutant.fitness.values
Đánh giá các cá nhân có thể lực 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[:] = offsprinIn 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 đầu ra 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: 15Vấ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 vấn đề về hồi quy ký hiệu đều sử dụng phân phối dữ liệu tùy ý và cố gắng điều chỉnh dữ liệu chính xác nhất bằng một công thức ký hiệu. Thông thường, một phép đo như RMSE (Lỗi bình phương trung bình gốc) được sử dụng để đo mức độ phù hợp 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 . Chúng ta cần làm theo tất cả các bước như 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à nền tả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 đây 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 khi tạo các mẫu bit. Chương trình này sẽ cho chúng ta kết quả là min, max, std (độ lệch chuẩn) sau 10 số thế hệ.