Evolutionary Algorithms

Thuật toán tiến hóa (EA) là một nhóm thuật toán tối ưu hóa mô phỏng chọn lọc tự nhiên. Chúng duy trì một quần thể các nghiệm ứng viên, chấm điểm từng nghiệm bằng hàm fitness, cho phép các ứng viên tốt nhất sinh ra thế hệ sau thông qua tái tổ hợp và đột biến ngẫu nhiên, rồi lặp lại qua nhiều thế hệ để quần thể dần hướng tới các nghiệm tốt hơn. EA chỉ cần đánh giá ứng viên, không cần tính gradient, nên phù hợp với những bài toán mà gradient descent không xử lý được: lựa chọn rời rạc, mục tiêu không khả vi hoặc nhiễu, và không gian tìm kiếm gồ ghề có nhiều cực trị cục bộ. Vì vậy, EA là công cụ tiêu chuẩn cho tinh chỉnh siêu tham số, tìm kiếm kiến trúc mạng nơ-ron, thiết kế kỹ thuật và lập lịch.

Cách thuật toán tiến hóa hoạt động#

Mọi EA đều được xây dựng từ những thành phần giống nhau:

1. Biểu diễn: Mỗi ứng viên được mã hóa thành một bộ gene, chẳng hạn chuỗi bit, vector số thực hoặc cây chương trình.
2. Khởi tạo: Thế hệ đầu tiên thường được tạo ngẫu nhiên, đôi khi được khởi tạo bằng các nghiệm tốt đã biết.
3. Đánh giá fitness: Hàm fitness chấm điểm từng ứng viên theo mục tiêu tối ưu hóa.
4. Chọn lọc: Ứng viên có fitness cao hơn có nhiều khả năng được chọn làm bố mẹ. Chẳng hạn, chọn lọc giải đấu chọn ứng viên tốt hơn trong một nhóm nhỏ gồm các ứng viên ngẫu nhiên, còn elitism sao chép nguyên vẹn ứng viên tốt nhất sang thế hệ tiếp theo.
5. Biến dị: Lai ghép kết hợp các phần từ hai cá thể bố mẹ, còn đột biến tạo những thay đổi nhỏ, ngẫu nhiên để quần thể tiếp tục khám phá.

Trong machine learning (ML), hàm fitness thường là một metric validation như độ chính xác hoặc độ chính xác trung bình trung bình (mAP), vì vậy đánh giá một ứng viên đồng nghĩa với huấn luyện và kiểm thử model, vốn là bước tốn kém nhất. Vòng lặp tiếp tục cho đến khi hết ngân sách hoặc fitness ngừng cải thiện:

Áp lực chọn lọc và cường độ đột biến quyết định sự cân bằng giữa khai thác và khám phá. Chọn lọc mạnh với đột biến nhỏ giúp hội tụ nhanh nhưng có thể mắc kẹt ở cực trị cục bộ, còn chọn lọc yếu với đột biến lớn khám phá rộng nhưng lãng phí các lượt đánh giá.

Các loại thuật toán tiến hóa chính#

• Thuật toán di truyền (GA): Mã hóa ứng viên thành chuỗi, thường là chuỗi bit, và phụ thuộc nhiều vào lai ghép. John Holland chính thức hóa phương pháp này trong cuốn sách Adaptation in Natural and Artificial Systems xuất bản năm 1975.
• Chiến lược tiến hóa (ES): Tối ưu hóa các vector số thực bằng đột biến Gaussian có kích thước bước tự điều chỉnh trong quá trình chạy. CMA-ES, phương pháp học toàn bộ ma trận hiệp phương sai của phân phối đột biến, là một trong những phương pháp đa dụng mạnh nhất cho các bài toán hộp đen liên tục.
• Lập trình di truyền: Tiến hóa các chương trình hoặc biểu thức toán học được biểu diễn dưới dạng cây, dùng cho hồi quy ký hiệu và thiết kế chương trình tự động.
• Tiến hóa mạng nơ-ron: Tiến hóa trọng số và đôi khi cả cấu trúc của mạng nơ-ron. Năm 2017, OpenAI cho thấy các chiến lược tiến hóa chạy trên hơn một nghìn worker song song có thể huấn luyện một hình người 3D biết đi trong 10 phút, một phương án thay thế có khả năng mở rộng cho học tăng cường.

Thuật toán di truyền trong mã#

Bài toán ba lô yêu cầu chọn các vật phẩm để đóng gói nhằm tối đa hóa tổng giá trị mà không vượt quá giới hạn khối lượng; đây là bài toán rời rạc không có gradient. Thuật toán di truyền NumPy này tiến hóa 50 bộ gene dạng chuỗi bit, mỗi bit ứng với một vật phẩm, bằng cách dùng chọn lọc giải đấu, lai ghép đồng đều, đột biến lật bit và elitism, sau đó đối chiếu kết quả với toàn bộ 1,048,576 phương án lựa chọn khả thi:

import itertools

import numpy as np

rng = np.random.default_rng(0)
# Knapsack problem: pick from 20 items to maximize total value within a weight limit of 200
values, weights, limit = rng.integers(10, 100, 20), rng.integers(5, 50, 20), 200


def fitness(pop):
    """Return each selection's total value, or 0 if it exceeds the weight limit."""
    return np.where(pop @ weights <= limit, pop @ values, 0)


population = rng.random((50, 20)) < 0.2  # 50 random genomes, one bit per item
for generation in range(100):
    scores = fitness(population)
    # Tournament selection: each parent is the better of two random genomes
    pairs = rng.integers(50, size=(50, 2))
    parents = population[np.where(scores[pairs[:, 0]] > scores[pairs[:, 1]], pairs[:, 0], pairs[:, 1])]
    # Uniform crossover with the next parent, then flip each bit with probability 0.05
    children = np.where(rng.random((50, 20)) < 0.5, parents, np.roll(parents, 1, axis=0))
    children ^= rng.random((50, 20)) < 0.05
    children[0] = population[scores.argmax()]  # elitism: keep the best genome
    population = children

all_selections = np.array(list(itertools.product([0, 1], repeat=20)))
print(f"GA best: {fitness(population).max()}, true optimum: {fitness(all_selections).max()}")

Chương trình in ra GA best: 811, true optimum: 811. Thuật toán tìm được cách đóng gói tối ưu sau 5,000 lượt đánh giá fitness, khoảng 0.5% trong số một triệu phương án mà phương pháp vét cạn phải kiểm tra.

Tiến hóa siêu tham số#

Các thiết lập huấn luyện như learning rate, trọng số loss và cường độ augmentation tương tác theo những cách không thể dự đoán bằng công thức; mỗi ứng viên lại tốn một lượt huấn luyện đầy đủ, nên đây là bài toán phù hợp với tìm kiếm tiến hóa. Phương thức tune() trong Ultralytics YOLO áp dụng cách tiếp cận này cho các model YOLO26: mỗi vòng lặp chọn một cá thể bố mẹ trong số chín cấu hình tốt nhất đến thời điểm đó, có trọng số theo fitness, đột biến khoảng một nửa trong số 26 siêu tham số thuộc không gian tìm kiếm mặc định bằng các bước Gaussian được điều chỉnh theo phạm vi tìm kiếm, huấn luyện model rồi ghi lại fitness, là mAP_50-95 đối với phát hiện đối tượng. Sau 30 kết quả, một số đột biến còn tuân theo hiệp phương sai của 20% cấu hình tốt nhất, một cách tiếp thu từ CMA-ES. Hướng dẫn tinh chỉnh siêu tham số liệt kê toàn bộ không gian tìm kiếm:

from ultralytics import YOLO

# Tải model YOLO26 nano đã pretrained
model = YOLO("yolo26n.pt")

# Tiến hóa siêu tham số: 30 vòng lặp, mỗi vòng huấn luyện một cấu hình đã đột biến trong 10 epoch
model.tune(data="coco8.yaml", epochs=10, iterations=30, plots=False)

Bộ tinh chỉnh ghi mọi cấu hình và fitness tương ứng vào tune_results.ndjson, đồng thời lưu cấu hình tốt nhất vào best_hyperparameters.yaml để sẵn sàng đưa vào một lượt huấn luyện đầy đủ.

Các ứng dụng khác#

• Tìm kiếm kiến trúc mạng nơ-ron: AmoebaNet của Google được tạo ra bằng tiến hóa có regularization, một EA dùng chọn lọc giải đấu và loại bỏ model cũ nhất thay vì model kém nhất; phương pháp này đạt độ chính xác top-1 83.9% trên ImageNet vào năm 2018.
• Thiết kế kỹ thuật: Nhiệm vụ Space Technology 5 của NASA đã đưa vào hoạt động năm 2006 một ăng-ten băng tần X được tiến hóa bằng máy tính; hình dạng dây uốn cong bất thường của ăng-ten đạt hiệu năng tương đương ăng-ten được thiết kế theo phương pháp thông thường.
• Khám phá thuật toán: AlphaEvolve, được Google DeepMind công bố vào tháng 5 năm 2025, kết hợp các model Gemini đề xuất thay đổi mã với bộ đánh giá tự động và cơ sở dữ liệu tiến hóa của các chương trình. Một heuristic lập lịch được tiến hóa cho các trung tâm dữ liệu của Google giúp thu hồi trung bình 0.7% tài nguyên tính toán trên toàn cầu của công ty.

Thuật toán tiến hóa và các phương pháp liên quan#

• Gradient descent: Đi theo gradient của loss khả vi và hiệu quả hơn nhiều khi huấn luyện trọng số mạng có hàng triệu tham số. EA phù hợp với các bài toán có ít tham số, chi phí đánh giá cao hoặc không có gradient.
• Trí tuệ bầy đàn: Các phương pháp như tối ưu hóa bầy đàn di chuyển một nhóm tác tử ổn định trong không gian tìm kiếm; mỗi tác tử điều chỉnh vị trí dựa trên kết quả tốt nhất của chính nó và các tác tử lân cận, không thay thế theo thế hệ, lai ghép hay đột biến.
• Tối ưu hóa Bayes: Xây dựng model xác suất cho hàm mục tiêu rồi chọn mỗi lượt thử tiếp theo tại vị trí mà model dự đoán sẽ cải thiện nhiều nhất; trên không gian tìm kiếm nhỏ, trơn, phương pháp này cần ít lượt đánh giá hơn EA nhưng mở rộng kém hơn khi có nhiều tham số và worker song song.