Báo cáo buổi học: Genetic Algorithms (Optimization and Linear Regression)

Giảng viên: Dr. Vinh Dinh Nguyen

Người viết: Thoi Gia Nghi

Ngày viết: 22/10/2025

I. Giới thiệu tổng quan

Buổi học tập trung vào Genetic Algorithms (GA) — một nhánh thuộc Evolutionary Algorithms (EA), tức các thuật toán tiến hóa mô phỏng quá trình chọn lọc tự nhiên trong sinh học để giải quyết bài toán tối ưu hóa.

GA không chỉ được dùng trong các bài toán kỹ thuật cổ điển mà còn được ứng dụng rộng rãi trong học máy, thiết kế hệ thống, dự đoán, và hồi quy (linear regression).

Mục tiêu chính của buổi học là:
- Hiểu cơ chế hoạt động của các thuật toán tiến hóa.
- Nắm rõ cấu trúc và thành phần chính của Genetic Algorithm.
- Áp dụng GA vào các bài toán tối ưu cụ thể như Sphere Function, One-Max Problem, và Linear Regression (House Price Prediction).
- Nhận diện các hướng ứng dụng thực tiễn của GA trong khoa học và công nghiệp.

(Nguồn: AIO Slide)

II. Evolutionary Algorithms – Nền tảng sinh học và nguyên lý hoạt động

1. Cảm hứng từ tiến hóa sinh học

Thuật toán tiến hóa bắt nguồn từ các cơ chế tự nhiên trong quá trình tiến hóa loài:
- Chọn lọc tự nhiên (Natural Selection): những cá thể thích nghi tốt hơn có khả năng sống sót và sinh sản.
- Di truyền học (Genetic Inheritance): đặc tính tốt được truyền lại cho thế hệ sau.
- Đột biến (Mutation): tạo ra sự đa dạng di truyền, giúp loài có cơ hội thích nghi với môi trường mới.

Từ góc độ tính toán, Evolutionary Algorithms (EAs) là một lớp các phương pháp mô phỏng quá trình này để tìm lời giải gần tối ưu cho bài toán phức tạp, nơi không thể áp dụng giải pháp giải tích.

(Nguồn: AIO Slide)

2. Cấu trúc cơ bản của một thuật toán tiến hóa

Quy trình tổng quát gồm:
1. Khởi tạo quần thể – tạo ra tập hợp ngẫu nhiên các nghiệm (cá thể).
2. Đánh giá độ thích nghi (Fitness Evaluation) – xác định chất lượng từng nghiệm.
3. Chọn lọc (Selection) – chọn các cá thể tốt để tái sản xuất.
4. Lai ghép (Crossover) – kết hợp các gen của hai cá thể để sinh ra thế hệ mới.
5. Đột biến (Mutation) – thay đổi ngẫu nhiên một phần gen để tăng đa dạng.
6. Kiểm tra hội tụ (Convergence) – lặp lại cho đến khi đạt tiêu chí dừng.

3. Ưu điểm và hạn chế

Ưu điểm:
- Không yêu cầu tính đạo hàm hay tính khả vi của hàm mục tiêu.
- Dễ mở rộng cho nhiều loại biến (nhị phân, thực, nguyên...).
- Có khả năng thoát khỏi cực tiểu cục bộ.

Hạn chế:
- Tốc độ hội tụ chậm hơn so với các phương pháp tất định (deterministic).
- Cần tinh chỉnh nhiều tham số (kích thước quần thể, tỉ lệ lai, tỉ lệ đột biến...).

III. Giới thiệu về Genetic Algorithms (GA)

1. Bản chất của GA

Genetic Algorithm (GA) là một thuật toán tìm kiếm heuristic dựa trên mô hình tiến hóa của quần thể, được sử dụng để giải bài toán tối ưu hóa có hoặc không có ràng buộc.

GA biểu diễn các lời giải bằng chromosome (nhiễm sắc thể), mỗi nhiễm sắc thể là một chuỗi gen mã hóa các biến quyết định của bài toán.

Mục tiêu của GA là tối đa hóa hoặc tối thiểu hóa hàm mục tiêu (objective function) thông qua quá trình tiến hóa nhiều thế hệ.

Biểu diễn hình thức:

$$ \text{Tìm } v^* \in \Omega \text{ sao cho } g(v^*) = \max_{v \in \Omega} g(v) $$

Trong đó:

• $\Omega$: không gian tìm kiếm (search space),
• $v$: vector các biến quyết định,
• $g(v)$: hàm đánh giá (fitness function).

(Nguồn: AIO Slide)

2. Các thành phần chính của GA

a. Encoding (Mã hóa)
Các biến của bài toán được mã hóa thành chuỗi gen — thường ở dạng nhị phân hoặc số thực.

b. Population (Quần thể)
Tập hợp các cá thể (chromosome). Kích thước quần thể ảnh hưởng trực tiếp đến độ đa dạng và tốc độ hội tụ.

c. Fitness Function (Hàm thích nghi)
Đánh giá “độ tốt” của mỗi cá thể. Đây là yếu tố quyết định hướng tiến hóa.

d. Genetic Operators (Toán tử di truyền)
Gồm ba nhóm chính:
- Selection (Chọn lọc): xác định cá thể nào được nhân bản.
- Crossover (Lai ghép): kết hợp gen giữa hai cá thể để sinh thế hệ mới.
- Mutation (Đột biến): thay đổi ngẫu nhiên gen nhằm tránh hội tụ sớm.

(Nguồn: Stochastic optimization of a uranium oxide reaction mechanism using plasma flow reactor measurements)

3. Các chiến lược chọn lọc trong GA

a. Roulette Wheel Selection
Xác suất chọn một cá thể tỉ lệ thuận với giá trị fitness của nó — giống như “vòng quay may mắn”.

b. Tournament Selection
Chọn ngẫu nhiên một nhóm nhỏ cá thể và lấy cá thể có fitness cao nhất trong nhóm làm bố mẹ.
Hai phương pháp này cân bằng giữa khai thác (exploitation) và thăm dò (exploration) trong không gian nghiệm.

(Nguồn: AIO Slide)

4. Crossover (Lai ghép)

Lai ghép mô phỏng di truyền sinh học, bằng cách trộn thông tin giữa hai bố mẹ:
- One-point crossover: cắt chuỗi tại một điểm.
- N-point crossover: cắt tại nhiều điểm.
- Uniform crossover: chọn ngẫu nhiên từng gen từ bố hoặc mẹ.
Crossover là toán tử chính để khám phá nghiệm mới, vì nó tạo ra tổ hợp đặc tính chưa từng có trong thế hệ cũ.

5. Mutation (Đột biến)

Đột biến thay đổi ngẫu nhiên giá trị gen.
Mục đích là tăng tính đa dạng, giúp tránh việc quần thể bị mắc kẹt tại cực trị cục bộ.
Ví dụ:
- Trong mã nhị phân: 0 → 1 hoặc 1 → 0.
- Trong mã số thực: thay đổi giá trị bằng một nhiễu nhỏ ngẫu nhiên.
Tỉ lệ đột biến thường nhỏ (1–5%) để đảm bảo tính ổn định của tiến hóa.

6. Chu trình hoạt động của GA

Toàn bộ quá trình tiến hóa được lặp qua các bước:

1. Khởi tạo quần thể ngẫu nhiên.
2. Đánh giá fitness cho từng cá thể.
3. Áp dụng chọn lọc, lai ghép, và đột biến.
4. Sinh ra quần thể mới.
5. Dừng lại khi hội tụ hoặc đạt giới hạn thế hệ.

(Nguồn: AIO Slide)

IV. Ví dụ 1 – One-Max Problem

One-Max Problem là một ví dụ kinh điển, được dùng để minh họa cách Genetic Algorithm hoạt động trên dữ liệu nhị phân.

1. Mô tả bài toán

Bài toán đặt ra như sau: Cho một chuỗi bit có độ dài $N$, hãy tìm chuỗi có tổng số bit bằng 1 lớn nhất.

Biểu thức hàm mục tiêu:
$$ f(x) = \sum_{i=1}^{N} x_i, \quad \text{với } x_i \in {0, 1} $$

Mục tiêu là tối đa hóa giá trị $f(x)$.
Nghiệm tối ưu toàn cục là chuỗi toàn 1:
$$ x^* = (1, 1, 1, ..., 1) $$

Dù lời giải hiển nhiên, One-Max là một bài kiểm thử lý tưởng cho GA vì nó giúp quan sát cách quần thể tiến hóa qua từng thế hệ — từ những chuỗi ngẫu nhiên đến nghiệm tốt nhất.

2. Quy trình thực thi GA cho One-Max

GA vận hành qua các bước sau:

a. Khởi tạo quần thể

Tạo ngẫu nhiên $m$ cá thể, mỗi cá thể là chuỗi nhị phân độ dài $N$.
Ví dụ: với $N = 6$ và $m = 10$, ta có:

b. Đánh giá (Evaluation)

Hàm fitness ở đây là số lượng bit “1” trong chuỗi.

c. Chọn lọc (Selection)

Sử dụng Roulette Wheel hoặc Tournament Selection để chọn cá thể có fitness cao hơn, giúp gen tốt có nhiều cơ hội truyền lại.

d. Lai ghép (Crossover)

Thực hiện 1-point crossover, ví dụ:

| Bố | 101011 |
| Mẹ | 000111 |
Cắt tại vị trí thứ 3 → Sinh ra con:
101111 và 000011.

e. Đột biến (Mutation)

Thay đổi ngẫu nhiên một vài bit trong chuỗi (ví dụ: đổi 0 → 1 ở vị trí thứ 2).

f. Kiểm tra hội tụ

Khi tất cả cá thể đều có fitness = N (toàn bit 1), hoặc số thế hệ đạt giới hạn, thuật toán dừng.

3. Quan sát và thảo luận

• Giai đoạn đầu: Fitness trung bình thấp, quần thể đa dạng.
• Giữa quá trình: Fitness trung bình tăng nhanh, cá thể tốt chiếm ưu thế.
• Cuối quá trình: Hội tụ về nghiệm tối ưu (toàn 1).

Nhận xét:
Bài toán One-Max cho thấy rõ cơ chế “sống sót của kẻ thích nghi nhất” và cách các toán tử di truyền tương tác để cải thiện nghiệm. Tuy nhiên, bài toán này đơn giản và không có cực trị cục bộ, nên chưa thể hiện hết ưu thế của GA so với các thuật toán khác.

V. Ví dụ 2 – Sphere Function (Continuous Optimization)

Sphere Function là bài toán chuẩn trong tối ưu hóa liên tục, dùng để đánh giá khả năng tìm cực tiểu của các thuật toán metaheuristic.

1. Mô tả bài toán

Hàm mục tiêu được định nghĩa:
$$ f(x) = \sum_{i=1}^{n} x_i^2 $$

Trong đó:

• $ x_i \in \mathbb{R} $,
• không gian tìm kiếm: $ x_i \in [-20, 20] $,
• nghiệm tối ưu toàn cục: $ x^* = (0, 0, ..., 0) $,
• giá trị tối ưu: $ f(x^*) = 0 $.

(Nguồn: AIO Slide)

2. Thiết lập GA cho bài toán Sphere

Khác với One-Max (nhị phân), Sphere dùng biểu diễn số thực (floating-point encoding). Mỗi chromosome gồm $n$ gen, tương ứng các biến $x_i $.

a. Khởi tạo quần thể

Các giá trị khởi tạo được lấy ngẫu nhiên trong khoảng $[-20, 20]$.

Ví dụ với $n = 2$ và $m = 10$:

b. Hàm thích nghi (Fitness Function)

Vì đây là bài toán cực tiểu hóa, nên fitness có thể được tính bằng:
$$ \text{fitness}(x) = \frac{1}{1 + f(x)} $$
để biến nó thành bài toán tối đa hóa.

c. Toán tử chọn lọc

Giữ nguyên nguyên tắc “cá thể có fitness cao hơn được chọn nhiều hơn”.
Các cá thể gần gốc (có $f(x)$ nhỏ hơn) được ưu tiên.

d. Toán tử lai ghép và đột biến

• Crossover: có thể là trung bình giữa hai vector cha mẹ.
  $$ x_{\text{child}} = \alpha x_{\text{parent1}} + (1 - \alpha) x_{\text{parent2}} $$
  với $ \alpha \in [0, 1] $.
• Mutation: thêm nhiễu ngẫu nhiên Gaussian nhỏ vào một hoặc nhiều gen.

e. Kiểm tra hội tụ

Thuật toán dừng khi fitness trung bình của quần thể thay đổi rất nhỏ qua nhiều thế hệ hoặc đạt giới hạn thế hệ.

(Nguồn: AIO Slide)

3. Kết quả và nhận xét

Khi chạy đủ số thế hệ, quần thể dần hội tụ về vùng gần gốc tọa độ (0,0).
Điều này chứng minh rằng GA có khả năng xấp xỉ cực trị toàn cục, ngay cả trong không gian liên tục vô hạn.

Ưu điểm nổi bật của GA trong Sphere Function:

• Không cần đạo hàm (gradient-free).
• Dễ mở rộng cho nhiều biến.
• Có thể thoát khỏi cực trị cục bộ nhờ cơ chế đột biến.

Hạn chế:

• Tốc độ hội tụ phụ thuộc mạnh vào tỉ lệ lai và đột biến.
• Với số biến lớn, yêu cầu tính toán tăng đáng kể.

4. So sánh giữa One-Max và Sphere Function

Cả hai ví dụ minh họa cho thấy GA là một khung tối ưu tổng quát, có thể thích nghi với nhiều loại biến và cấu trúc bài toán khác nhau.

VI. Genetic Algorithm và Hồi quy tuyến tính

Hồi quy tuyến tính (Linear Regression) là một phương pháp thống kê dùng để mô hình hóa mối quan hệ giữa một biến phụ thuộc $ y $ và một (hoặc nhiều) biến độc lập $ x $.

1. Mô tả bài toán

Mô hình tuyến tính tổng quát:
$$ y = a \cdot x + b $$ trong đó:
* $ a $: hệ số góc (slope),
* $ b $: hệ số chặn (intercept),
* $ y $: giá trị dự đoán (predicted output).

Thông thường, $ a $ và $ b $ được tìm bằng phương pháp bình phương tối thiểu (Least Squares):
$$ \min_{a,b} \sum_{i=1}^n (y_i - (a x_i + b))^2 $$Tuy nhiên, khi không thể hoặc không muốn giả định các điều kiện tuyến tính, hoặc khi hàm lỗi phức tạp, Genetic Algorithm có thể được sử dụng như một công cụ tối ưu hóa thay thế để tìm ra $ a $ và $ b $ sao cho sai số dự đoán nhỏ nhất.

(Nguồn: AIO Slide)

2. Mục tiêu của GA trong hồi quy tuyến tính

Mục tiêu là tìm cặp tham số $ (a, b) $ sao cho sai số bình phương trung bình (Mean Squared Error – MSE) nhỏ nhất:

$$ \text{MSE}(a, b) = \frac{1}{n} \sum_{i=1}^{n} (y_i - (a x_i + b))^2 $$

Trong ngữ cảnh Genetic Algorithm, đây là hàm mục tiêu cần tối thiểu hóa.
Vì GA vốn là công cụ tối đa hóa fitness, ta định nghĩa lại:
$$ \text{Fitness}(a, b) = \frac{1}{1 + \text{MSE}(a, b)} $$ Cặp $(a, b)$ cho giá trị fitness cao nhất sẽ là mô hình hồi quy tốt nhất.

3. Biểu diễn và khởi tạo

• Biểu diễn (Encoding): mỗi cá thể (chromosome) là một cặp $(a, b)$ biểu diễn bằng số thực.
  Ví dụ: $ \text{Cá thể}_1 = (a = 0.8, b = 2.3) $

• Khởi tạo quần thể:
  Sinh ngẫu nhiên nhiều cặp $(a, b)$ trong khoảng giá trị hợp lý (ví dụ $a, b \in [-10, 10]$).

• Quy mô quần thể: tùy chọn, thường khoảng 20–50 cá thể cho bài toán nhỏ.

4. Quy trình GA cho hồi quy tuyến tính

Quy trình hoạt động của Genetic Algorithm trong bài toán dự đoán giá nhà bao gồm:

a. Evaluation (Đánh giá)

Tính fitness cho từng cá thể dựa trên MSE giữa giá trị thực và giá trị dự đoán:
$$ \text{Fitness}(a, b) = \frac{1}{1 + \text{MSE}(a, b)} $$ Các cá thể cho giá trị fitness cao (MSE nhỏ) được xem là “có gen tốt”.

b. Selection (Chọn lọc)

Chọn các cặp tham số có fitness cao hơn để tham gia sinh sản thế hệ tiếp theo. Có thể dùng Tournament Selection để duy trì tính cạnh tranh và đa dạng.

c. Crossover (Lai ghép)

Kết hợp gen giữa hai cá thể cha mẹ:
$$ a_{\text{new}} = \alpha a_1 + (1 - \alpha)a_2, \quad b_{\text{new}} = \alpha b_1 + (1 - \alpha)b_2 $$ với $ \alpha \in [0,1] $ là hệ số trộn ngẫu nhiên.

d. Mutation (Đột biến)

Thêm nhiễu nhỏ ngẫu nhiên (ví dụ Gaussian noise) vào (a) hoặc (b) để khám phá nghiệm mới:
$$ a' = a + \epsilon, \quad b' = b + \epsilon', \quad \epsilon, \epsilon' \sim \mathcal{N}(0, \sigma) $$ Tỉ lệ đột biến thấp ~$1–5\%$ để đảm bảo sự ổn định.

e. Stopping Criteria (Điều kiện dừng)

• Khi fitness trung bình thay đổi không đáng kể trong nhiều thế hệ.
• Hoặc khi đạt số thế hệ giới hạn (ví dụ 100).

5. Ví dụ minh họa – Dự đoán giá nhà (House Price Prediction)

Giả sử tập dữ liệu có dạng:

GA sẽ tìm tham số $a$ và $b$ sao cho:
$$ y = a \cdot \text{area} + b $$ phù hợp nhất với các dữ liệu trên.

a. Quần thể khởi tạo

Khởi tạo 10 cá thể với giá trị ngẫu nhiên của $a, b$.

b. Tiến hóa qua các thế hệ

• Sau 1–10 thế hệ: các cá thể còn phân tán, sai số lớn.
• Sau 20–50 thế hệ: fitness tăng dần, quần thể hội tụ quanh nghiệm tốt nhất.
• Sau 100 thế hệ: mô hình đạt gần cực tiểu toàn cục của MSE.

Ví dụ nghiệm tối ưu:
$$ a^* = 4.2, \quad b^* = 90.5 $$Dự đoán tương ứng:
$$ \hat{y} = 4.2 \cdot x + 90.5 $$sai số trung bình nhỏ hơn đáng kể so với phương pháp khởi tạo ngẫu nhiên ban đầu.

6. Thảo luận và nhận xét

Ưu điểm khi sử dụng GA cho hồi quy:

• Không phụ thuộc vào giả định tuyến tính nghiêm ngặt.
• Có thể tối ưu hàm lỗi phi tuyến hoặc phi khả vi.
• Thích hợp cho bài toán có nhiều cực trị cục bộ hoặc nhiều biến.

Hạn chế:

• Tốn nhiều thời gian tính toán hơn so với phương pháp giải tích (Least Squares).
• Cần tinh chỉnh tham số để đảm bảo hội tụ ổn định (population size, mutation rate...).

Kết luận phần này:
GA có thể xem như một công cụ tối ưu hóa mô hình học máy nói chung, không chỉ giới hạn ở bài toán hồi quy tuyến tính.
Nó cho phép tìm tham số tốt nhất cho bất kỳ mô hình nào, ngay cả khi hàm mục tiêu phức tạp hoặc không có công thức đạo hàm.

VII. Ứng dụng thực tế của Genetic Algorithms (GA)

Phần cuối của bài giảng trình bày một loạt ứng dụng thực tiễn của Genetic Algorithm (GA), nhấn mạnh rằng mọi bài toán tối ưu hóa trong thế giới thực, bất kể thuộc lĩnh vực nào, đều có thể được mô hình hóa dưới dạng mà GA có thể giải quyết.

Nói cách khác, GA không chỉ là một thuật toán, mà là một khuôn khổ tổng quát (general optimization framework) có thể thích nghi với nhiều loại bài toán, cả rời rạc lẫn liên tục, có ràng buộc hoặc không ràng buộc.

(Nguồn: AIO Slide)

1. GA trong bài toán tối ưu kỹ thuật (Engineering Optimization)

a. Thiết kế cấu trúc (Structure Design)

GA được dùng trong:

• Thiết kế cầu, khung nhà, giàn thép nhằm giảm khối lượng và tăng độ bền.
• Tối ưu hóa hình dạng cánh máy bay hoặc ăng-ten vệ tinh (như ví dụ NASA 2004), nơi GA tìm ra cấu trúc có hiệu năng tốt nhất trong không gian thiết kế phức tạp.

(Nguồn: AIO Slide)

b. Tối ưu hệ thống điện tử và mạch

GA có thể tự động:

• Chọn cấu trúc mạch analog (topology synthesis),
• Điều chỉnh thông số linh kiện (component sizing),
• Giảm thiểu nhiễu hoặc năng lượng tiêu thụ.

2. GA trong khoa học máy tính và trí tuệ nhân tạo

a. Tối ưu mạng nơ-ron (Neural Network Optimization)

GA được sử dụng để:

• Chọn cấu trúc mạng (topology),
• Điều chỉnh trọng số khởi tạo hoặc siêu tham số (hyperparameters).

So với Gradient Descent, GA không cần đạo hàm, giúp tránh kẹt tại cực tiểu cục bộ trong mạng sâu.

b. AI học hành vi: Game và Robotics

• Evolutionary Robotics: robot tự học cách đi, nhảy, hay né vật cản thông qua tiến hóa gen.
• AI trong trò chơi: ví dụ trong NERO (University of Texas), người chơi huấn luyện đội quân ảo bằng GA thay vì code tay.
• Evolutionary Checkers: sử dụng GA kết hợp mạng nơ-ron để đạt trình độ gần chuyên gia mà không cần tri thức sẵn có.

(Nguồn: AIO Slide)

3. GA trong nghệ thuật và sáng tạo (Evolutionary Art)

• Máy tính sinh ra hàng loạt tác phẩm (màu sắc, hình dạng, họa tiết), người dùng chọn lựa mẫu ưa thích.
• GA học theo “gu thẩm mỹ” của người dùng, tạo ra phong cách nghệ thuật riêng biệt.

Ví dụ:

• Galapagos của Karl Sims là hệ thống tạo hình động qua tiến hóa.
• MusiGenesis hoặc GenJam: hệ thống sáng tác nhạc tự động bằng GA, có thể “ngẫu hứng jazz” cùng nhạc công thật.

(Nguồn: AIO Slide)

4. GA trong sinh học và y học

• Phân tích gene và protein folding: xác định cấu trúc protein ổn định nhất.
• Khám phá thuốc (Drug Discovery): tìm hợp chất có tính liên kết tối ưu với mục tiêu sinh học.
• Chẩn đoán ung thư hoặc bệnh di truyền: chọn đặc trưng (feature selection) tối ưu từ dữ liệu y học.

Nhờ khả năng tìm nghiệm toàn cục, GA đặc biệt hữu ích trong các bài toán không tuyến tính, không khả vi, đa đỉnh (multi-modal), vốn phổ biến trong sinh học phân tử.

5. GA trong kinh tế và xã hội

• Tối ưu danh mục đầu tư (Portfolio Optimization): chọn tổ hợp cổ phiếu tối ưu rủi ro – lợi nhuận.
• Dự báo chuỗi thời gian (Time-Series Forecasting): dự đoán giá cổ phiếu, thời tiết, hoặc nhu cầu tiêu thụ.
• Mô phỏng hành vi ra quyết định: ví dụ Prisoner’s Dilemma được mô hình hóa bằng GA để phân tích chiến lược tiến hóa trong trò chơi.

(Nguồn: AIO Slide)

VIII. Thảo luận – So sánh và đánh giá GA với các phương pháp khác

GA vượt trội trong các bài toán:

• Có nhiều cực trị cục bộ.
• Không có dạng giải tích rõ ràng.
• Không thể hoặc không muốn tính đạo hàm.

Tuy nhiên, nhược điểm chính là chi phí tính toán cao và tốc độ hội tụ chậm, do đó thường được kết hợp với các phương pháp khác như:

• Hybrid GA + Gradient Descent,
• GA + Simulated Annealing,
• hoặc GA + Reinforcement Learning.

IX. Tổng kết và bài học rút ra

1. Kiến thức trọng tâm của buổi học

• Hiểu được nguyên lý sinh học đứng sau Evolutionary Algorithms.
• Nắm vững cấu trúc và quy trình của Genetic Algorithm, bao gồm: khởi tạo, chọn lọc, lai ghép, đột biến, và kiểm tra hội tụ.
• Ứng dụng GA trong ba dạng bài toán tiêu biểu:

1. One-Max Problem: minh họa nguyên lý tiến hóa cơ bản.
2. Sphere Function: bài toán tối ưu liên tục.
3. Linear Regression: mô hình học máy ứng dụng GA để tìm tham số tối ưu.
   * Thấy được sự đa dạng của ứng dụng GA trong thực tiễn, từ kỹ thuật, y học, kinh tế đến nghệ thuật.

2. Ý nghĩa phương pháp luận

Buổi học cho thấy một thông điệp cốt lõi trong trí tuệ nhân tạo hiện đại:

“Không nhất thiết phải biết công thức chính xác để tìm nghiệm tối ưu — chỉ cần biết cách tiến hóa dần tới nó.”

GA thể hiện tinh thần đó: khám phá không gian nghiệm bằng tiến hóa tự nhiên, thay vì cố định quy tắc học cứng nhắc.

3. Hướng phát triển nâng cao

Các biến thể hiện đại của GA được mở rộng sang nhiều hướng:

• Hybrid Evolutionary Algorithms: kết hợp với gradient-based optimization.
• Quantum Genetic Algorithms: tận dụng tính song song của máy tính lượng tử.
• Co-evolutionary Algorithms: nhiều quần thể tiến hóa đồng thời trong các môi trường tương tác.

Những hướng này tiếp tục khẳng định vị thế của GA như một nền tảng metaheuristic mạnh mẽ cho trí tuệ nhân tạo tối ưu hóa thế hệ mới.

X. Kết luận cuối cùng

Buổi học “Genetic Algorithms (Optimization and Linear Regression)” không chỉ dừng lại ở việc hiểu cơ chế của một thuật toán, mà còn là bài học về tư duy tối ưu hóa tổng quát:
từ sinh học tự nhiên đến trí tuệ nhân tạo, mọi hệ thống đều có thể học hỏi, thích nghi, và tiến hóa.

Genetic Algorithm là minh chứng cho khả năng đó, đây là một cầu nối giữa khoa học tự nhiên và khoa học máy tính, giữa ngẫu nhiên và thông minh, giữa hệ thống tự nhiên và hệ thống nhân tạo.

Tài liệu tham khảo

• Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.
• Mitchell, M. An Introduction to Genetic Algorithms. MIT Press, 1998.
• Dinh Nguyen Vinh, Lecture slides: Genetic Algorithms (Optimization and Linear Regression), AIO 2025.

Phụ lục: Code minh họa các ví dụ GA

1. One-Max Problem (Mã nhị phân)

Bài toán:
Tìm chuỗi bit có tổng số 1 lớn nhất: $\max f(x) = \sum_{i=1}^{N} x_i, \quad x_i \in {0,1} $

import random

# ----- Cấu hình -----
N_BITS = 20          # độ dài chromosome
POP_SIZE = 30        # số lượng cá thể
N_GENERATIONS = 50   # số thế hệ
CROSS_RATE = 0.8
MUT_RATE = 0.01

# ----- Hàm khởi tạo -----
def create_individual():
    return [random.randint(0, 1) for _ in range(N_BITS)]

def fitness(individual):
    return sum(individual)  # số lượng bit 1

# ----- Toán tử chọn lọc (Roulette Wheel) -----
def selection(pop):
    total_fit = sum(fitness(ind) for ind in pop)
    pick = random.uniform(0, total_fit)
    current = 0
    for ind in pop:
        current += fitness(ind)
        if current >= pick:
            return ind

# ----- Lai ghép -----
def crossover(p1, p2):
    if random.random() < CROSS_RATE:
        point = random.randint(1, N_BITS - 1)
        child = p1[:point] + p2[point:]
        return child
    return p1.copy()

# ----- Đột biến -----
def mutate(ind):
    for i in range(N_BITS):
        if random.random() < MUT_RATE:
            ind[i] = 1 - ind[i]
    return ind

# ----- Vòng lặp tiến hóa -----
population = [create_individual() for _ in range(POP_SIZE)]

for gen in range(N_GENERATIONS):
    population = [mutate(crossover(selection(population),
                                   selection(population)))
                  for _ in range(POP_SIZE)]
    best = max(population, key=fitness)
    print(f"Thế hệ {gen+1}: Best fitness = {fitness(best)}")

print("\nKết quả tối ưu:", best)

Giải thích:

• Mỗi cá thể là chuỗi bit 0/1.
• Fitness = số bit 1.
• Sau mỗi thế hệ, các cá thể được lai ghép và đột biến.
• Quần thể dần tiến hóa về chuỗi toàn 1.

2. Sphere Function (Tối ưu hóa liên tục)

Bài toán: $ \min f(x) = \sum_{i=1}^{n} x_i^2, \quad x_i \in [-20, 20] $

import numpy as np

# ----- Cấu hình -----
DIM = 2                # số biến (n)
POP_SIZE = 30
N_GEN = 100
CROSS_RATE = 0.8
MUT_RATE = 0.05
BOUND = [-20, 20]

# ----- Hàm fitness -----
def sphere(x):
    return np.sum(x**2)

def fitness(x):
    return 1 / (1 + sphere(x))  # càng nhỏ càng tốt

# ----- Khởi tạo -----
population = np.random.uniform(BOUND[0], BOUND[1], size=(POP_SIZE, DIM))

# ----- Hàm chọn lọc -----
def select(pop, fits):
    idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, p=fits/fits.sum())
    return pop[idx]

# ----- Lai ghép -----
def crossover(p1, p2):
    if np.random.rand() < CROSS_RATE:
        alpha = np.random.rand()
        return alpha * p1 + (1 - alpha) * p2
    return p1.copy()

# ----- Đột biến -----
def mutate(ind):
    for j in range(DIM):
        if np.random.rand() < MUT_RATE:
            ind[j] += np.random.uniform(-1, 1)
            ind[j] = np.clip(ind[j], *BOUND)
    return ind

# ----- Tiến hóa -----
for g in range(N_GEN):
    fits = np.array([fitness(ind) for ind in population])
    population = select(population, fits)
    new_pop = []
    for i in range(POP_SIZE):
        p1, p2 = population[np.random.randint(0, POP_SIZE, 2)]
        child = mutate(crossover(p1, p2))
        new_pop.append(child)
    population = np.array(new_pop)

    best = population[np.argmax([fitness(ind) for ind in population])]
    print(f"Thế hệ {g+1}: best f(x) = {sphere(best):.5f}, tại x = {best}")

print("\nNghiệm tối ưu gần đúng:", best)

Giải thích:

• Mỗi cá thể là vector số thực (x = (x_1, x_2)).
• GA dần hội tụ về nghiệm gần gốc ((0,0)).
• Hàm fitness được định nghĩa nghịch đảo với hàm chi phí để phù hợp cơ chế tối đa hóa.

3. Linear Regression bằng Genetic Algorithm

Bài toán: Tìm hệ số $a, b$ trong mô hình: $y = a \cdot x + b$ sao cho Mean Squared Error (MSE) giữa giá trị thật và giá trị dự đoán nhỏ nhất.

import numpy as np

# ----- Dữ liệu mẫu -----
X = np.array([30, 50, 70, 90])
Y = np.array([210, 310, 390, 480])

# ----- Cấu hình -----
POP_SIZE = 40
N_GEN = 100
CROSS_RATE = 0.8
MUT_RATE = 0.05
BOUND = [-10, 10]  # cho cả a và b

# ----- Hàm fitness -----
def mse(a, b):
    y_pred = a * X + b
    return np.mean((Y - y_pred)**2)

def fitness(a, b):
    return 1 / (1 + mse(a, b))

# ----- Khởi tạo quần thể -----
population = np.random.uniform(BOUND[0], BOUND[1], size=(POP_SIZE, 2))  # cột 0: a, cột 1: b

# ----- Toán tử -----
def crossover(p1, p2):
    if np.random.rand() < CROSS_RATE:
        alpha = np.random.rand()
        return alpha * p1 + (1 - alpha) * p2
    return p1.copy()

def mutate(ind):
    for j in range(2):
        if np.random.rand() < MUT_RATE:
            ind[j] += np.random.uniform(-1, 1)
            ind[j] = np.clip(ind[j], *BOUND)
    return ind

# ----- Vòng lặp tiến hóa -----
for g in range(N_GEN):
    fits = np.array([fitness(a, b) for a, b in population])
    probs = fits / fits.sum()
    parents = population[np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, p=probs)]
    new_pop = []
    for i in range(POP_SIZE):
        p1, p2 = parents[np.random.randint(0, POP_SIZE, 2)]
        child = mutate(crossover(p1, p2))
        new_pop.append(child)
    population = np.array(new_pop)

    best_idx = np.argmax([fitness(a, b) for a, b in population])
    best = population[best_idx]
    print(f"Thế hệ {g+1}: a={best[0]:.3f}, b={best[1]:.3f}, MSE={mse(*best):.3f}")

a_best, b_best = best
print(f"\nMô hình tối ưu: y = {a_best:.3f} * x + {b_best:.3f}")

Giải thích:

• Mỗi cá thể là cặp ((a, b)).
• Fitness dựa trên MSE của dự đoán so với dữ liệu thật.
• GA tự động tìm ra đường hồi quy tốt nhất mà không dùng giải tích.
• Kết quả thường hội tụ quanh nghiệm tương đương với phương pháp bình phương tối thiểu.