GIẢI THUẬT DI TRUYỀN – BÍ MẬT CỦA NHỮNG CỖ MÁY BIẾT HỌC

1. Giới thiệu

Trong khi các phương pháp cổ điển như Gradient Descent có thể bị mắc kẹt ở cực trị cục bộ với những bài toán phức tạp, Thuật toán Di truyền (GA) mang đến một hướng tiếp cận lấy cảm hứng từ tự nhiên. Thay vì đi theo một quỹ đạo duy nhất, GA làm việc với một "quần thể" các giải pháp. Qua các quá trình mô phỏng chọn lọc, lai ghép và đột biến qua nhiều thế hệ, GA có khả năng khám phá không gian nghiệm một cách toàn diện, giúp vượt qua các "thung lũng cục bộ" để tìm kiếm lời giải tối ưu toàn cục

2. Tổng quan về Thuật toán Di truyền (GA)

2.1. Định nghĩa Bài toán Tối ưu hóa

Tối ưu hóa là việc tìm ra giải pháp tốt nhất có thể từ tất cả các lựa chọn có sẵn.

Ví dụ:
- Tìm giá trị nhỏ nhất của một hàm số như $y = x^2$ bằng cách sử dụng đạo hàm.
- Tìm ra các trọng số tốt nhất cho một hàm tuyến tính để giảm thiểu tổn thất (loss) bằng gradient descent.
- Tìm đường đi ngắn nhất trên bản đồ bằng các thuật toán như Dijkstra.
- Huấn luyện robot đi bộ hoặc tìm ra kiến trúc mạng nơ-ron tốt nhất khi không có dữ liệu hoặc hàm số rõ ràng để tuân theo.

2.2. Tối ưu hóa Hộp đen (Black-Box)

Đôi khi, chúng ta đối mặt với những bài toán mà ta không biết hàm số $f(x)$ cơ bản. Chúng ta chỉ có thể quan sát đầu vào ($x$) và đầu ra ($f(x)$).

=> Đây được gọi là tối ưu hóa hộp đen (black-box optimization).

Đối với những tình huống phức tạp này, chúng ta có thể sử dụng Thuật toán Tiến hóa (Evolutionary Algorithms - EA), vốn được lấy cảm hứng từ tự nhiên.

2.3. Nguồn cảm hứng từ sự Tiến hóa Tự nhiên

Thuật toán Tiến hóa dựa trên ý tưởng rằng sự tiến hóa tự nhiên chính là một quá trình tối ưu hóa. Qua nhiều thế hệ, các sinh vật thích nghi dần và trở nên phù hợp hơn với môi trường sống.

Những nguyên lý này có thể được áp dụng để thiết kế các thuật toán tối ưu hóa nhờ vào bốn đặc điểm nổi bật sau:

• Hiệu quả (Effectiveness): Tạo ra các sinh vật (hoặc lời giải) có độ phức tạp và chất lượng cao hơn qua từng thế hệ.
• Hiệu suất (Efficiency): Có khả năng thử nghiệm nhiều phương án cùng lúc (tức là "xử lý song song").
• Bền bỉ (Robustness): Quá trình vẫn tiếp tục ngay cả khi một số cá thể thất bại.
• Đơn giản (Simplicity): Ý tưởng chung đơn giản, dễ hiểu và linh hoạt để tùy chỉnh.

2.4. Giới thiệu về Thuật toán Di truyền (GA)

Thuật toán Di truyền (Genetic Algorithm - GA) là một loại thuật toán Tiến hóa cụ thể, mô phỏng quá trình chọn lọc tự nhiên. Ý tưởng chính là các cá thể khỏe mạnh nhất (phù hợp nhất) sẽ có khả năng sống sót, sinh sản và truyền lại các đặc điểm của mình cho thế hệ tiếp theo.

Các thuật ngữ chính:
- Individual (Cá thể): Một giải pháp tiềm năng duy nhất cho bài toán.
- Chromosome (Nhiễm sắc thể): Cách một cá thể được biểu diễn, thường là một chuỗi các bit (0 và 1).
- Gene (Gen): Một bit duy nhất (0 hoặc 1) trong nhiễm sắc thể.
- Population (Quần thể): Một tập hợp các cá thể (các giải pháp tiềm năng).

3. Giải mã GA: Khi Random Search "Tiến hóa"

3.1. Yếu tố cốt lõi của thuật toán Di Truyền ?

Ở phần hai, chúng ta đã có cái nhìn tổng quan về thuật toán Di truyền (Genetic Algorithm – GA) — từ nguồn gốc hình thành, nguyên lý hoạt động, cho đến cách mà thuật toán này tương tác và thích nghi với các bài toán tối ưu hóa trong thế giới hiện đại.

Mỗi giai đoạn trong quá trình "tiến hóa" của thuật toán đều được trình bày rõ ràng, giúp người đọc nắm bắt cách GA vận hành một cách hệ thống.

• Tuy nhiên, để hiểu sâu hơn về bản chất của thuật toán này, ta có thể đặt ra một số câu hỏi ngược lại, nhằm khám phá nguồn gốc hình thành và tư tưởng nền tảng phía sau:

1. Đâu là yếu tố cốt lõi hình thành nên giải thuật?
2. Vì sao Genetic Algorithm lại có thể mô phỏng được quá trình tiến hóa trong tự nhiên?
3. Quá trình tiến hóa trong tự nhiên được hình thành theo cơ chế nào?

Để giải đáp những câu hỏi này, chúng ta cần quay trở lại với nền tảng sinh học, cụ thể là quá trình tiến hóa trong tự nhiên — đây chính là nguồn cảm hứng đã dẫn đến sự ra đời của thuật toán Di truyền (GA).

3.2. Tiến Hóa là gì - Người phổ biến khái niệm này là ai ?

3.2.1. Tiến Hóa Là Gì?

Tiến hóa là quá trình thay đổi dần dần các đặc điểm di truyền của một quần thể sinh vật qua nhiều thế hệ.

Theo định nghĩa phổ biến trong sách giáo khoa Sinh học:

Tiến hóa là quá trình mà qua đó các sinh vật sống thay đổi về mặt di truyền theo thời gian, dẫn đến sự hình thành các đặc điểm mới, sự thích nghi với môi trường, và đôi khi là sự xuất hiện của loài mới.

3.2.2. Ai Là Người Đưa Ra Khái Niệm Tiến Hóa?

Khái niệm tiến hóa được phát triển và phổ biến rộng rãi bởi Charles Darwin – nhà tự nhiên học người Anh.
Trong tác phẩm nổi tiếng "On the Origin of Species" (1859), Darwin đã trình bày lý thuyết chọn lọc tự nhiên như cơ chế chính của tiến hóa.

Theo Darwin, các sinh vật có đặc điểm phù hợp hơn với môi trường sẽ có khả năng sống sót và sinh sản cao hơn, từ đó truyền lại gen có lợi cho thế hệ sau.

3.2.3. QUÁ TRÌNH TIẾN HÓA TRONG TỰ NHIÊN ĐƯỢC HÌNH THÀNH THEO CÁC CƠ CHẾ NÀO ?

1. Chọn lọc tự nhiên là gì? – Randomness trong môi trường và sinh tồn

Tại sao loài này sống sót, còn loài khác biến mất?
Vì chọn lọc tự nhiên chỉ giữ lại những cá thể có đặc điểm di truyền phù hợp nhất với môi trường. Chúng sống lâu hơn, sinh sản nhiều hơn, và truyền gen có lợi cho thế hệ sau.

Nhưng "tự nhiên" không hề hoàn hảo.

Môi trường có thể thay đổi bất ngờ.

Một thiên tai, dịch bệnh hay tai nạn cũng có thể xóa sổ cả những cá thể mang gen tốt.

Ví dụ: Trong vùng khí hậu lạnh, những cá thể có lớp lông dày dễ sống sót hơn, và đặc điểm "lông dày" dần trở nên phổ biến.

👉 Randomness ở đây: Ai sống sót không chỉ nhờ gen, mà còn vì yếu tố ngẫu nhiên của môi trường.

2. Đột biến gen là gì? – Randomness là bản chất

Nếu chọn lọc tự nhiên là "bộ lọc", thì đột biến gen chính là "nguồn nguyên liệu" của tiến hóa.
Đột biến là những thay đổi ngẫu nhiên trong DNA – có thể do lỗi sao chép, hoặc do tác động của môi trường như bức xạ, hóa chất,...

Một số đột biến gây hại, số khác vô nghĩa, nhưng đôi khi – một đột biến nhỏ lại mang đến lợi thế sinh tồn.

Ví dụ: Một đột biến khiến cánh của côn trùng dài hơn giúp nó bay xa hơn, thoát khỏi kẻ thù dễ hơn.

👉 Randomness ở đây: Không ai biết khi nào, ở đâu, hay loại đột biến nào sẽ xảy ra – tất cả đều ngẫu nhiên.

3. Di truyền là gì? – Randomness trong tổ hợp gen

Tưởng rằng con cái sẽ giống cha mẹ? Đúng, nhưng không hoàn toàn.
Di truyền là quá trình truyền thông tin di truyền qua gen, song sự kết hợp gen khi sinh sản lại hoàn toàn ngẫu nhiên.

Khi tế bào sinh dục hình thành, nhiễm sắc thể phân ly và tái tổ hợp ngẫu nhiên.

Mỗi cá thể sinh ra là một tổ hợp gen độc nhất, không ai giống ai.

Ví dụ: Hai anh em sinh đôi khác trứng – cùng cha mẹ, nhưng có thể khác nhau về màu mắt, chiều cao, thậm chí khả năng miễn dịch.

👉 Randomness ở đây: Con cái không phải bản sao của cha mẹ, mà là kết quả của sự trộn ngẫu nhiên giữa hai bộ gen.

4. Di nhập gen là gì? – Randomness trong di cư và giao phối

Sinh vật không đứng yên. Chúng di chuyển, di cư, giao phối, và trong quá trình ấy, gen cũng "di chuyển" theo.
Đó chính là di nhập gen – sự trao đổi gen giữa các quần thể cùng loài.

Khi một cá thể từ quần thể này đến quần thể khác và sinh sản:

Không ai biết cá thể nào sẽ di cư,

Hay nó sẽ giao phối với ai.

Ví dụ: Một con chim từ vùng núi bay xuống đồng bằng và sinh sản – gen của nó giờ đã hòa vào quần thể đồng bằng.

👉 Randomness ở đây: Việc di chuyển và kết hợp gen diễn ra không theo quy luật cố định, nhưng chính sự ngẫu nhiên ấy lại làm tăng đa dạng di truyền.

KẾT LUẬN:

Từ khái niệm "tiến hóa" trong sinh học, chúng ta có thể xác định rằng quá trình này vận hành thông qua bốn cơ chế chính:
- Chọn lọc tự nhiên
- Đột biến gen
- Di truyền
- Di nhập gen

Khi phân tích sâu vào từng cơ chế, ta nhận thấy rằng yếu tố ngẫu nhiên chính là cốt lõi hình thành nên quá trình tiến hóa. Chính sự ngẫu nhiên này đã truyền cảm hứng cho sự ra đời của Genetic Algorithm (GA) – một thuật toán mô phỏng tiến hóa tự nhiên trong môi trường tính toán.

Từ đó, chúng ta có thể trả lời hai câu hỏi quan trọng:

1. Yếu tố nào là nền tảng hình thành nên giải thuật GA?

=> Chính là randomness – tính ngẫu nhiên trong chọn lọc, lai ghép và đột biến.

2. Vì sao Genetic Algorithm có thể mô phỏng được quá trình tiến hóa trong tự nhiên?

=> Vì GA tái hiện lại các cơ chế tiến hóa sinh học, trong đó randomness đóng vai trò trung tâm.

3.3. Diễn Giải Randomness Trong Luồng Hoạt Động Của Genetic Algorithm

Chúng ta đã tìm hiểu cách Genetic Algorithm (GA) mô phỏng quá trình tiến hóa tự nhiên thông qua các cơ chế như chọn lọc, lai ghép, đột biến, và di truyền.
Tuy nhiên, một yếu tố xuyên suốt và đóng vai trò cốt lõi trong toàn bộ quá trình này chính là randomness – tính ngẫu nhiên.

VẬY RANDOMNESS XUẤT HIỆN Ở ĐÂU TRONG LUỒNG HOẠT ĐỘNG CỦA GA?

Giải thuật di truyền (GA) vận hành theo một chu trình gồm sáu bước chính:

1. Khởi tạo (Initialization)
2. Đánh giá (Fitness Evaluation)
3. Lựa chọn (Selection)
4. Lai ghép (Crossover)
5. Đột biến (Mutation)
6. Dừng (Termination)

Để mô phỏng quá trình tiến hóa trong tự nhiên một cách hiệu quả, GA không chỉ tái hiện các cơ chế sinh học, mà còn tích hợp yếu tố ngẫu nhiên (randomness) vào các bước:
- Khởi tạo – quần thể ban đầu được sinh ra ngẫu nhiên, đảm bảo tính đa dạng.
- Lựa chọn – cá thể được chọn theo xác suất, phản ánh yếu tố "may mắn" trong tự nhiên.
- Lai ghép – việc kết hợp các gen có yếu tố ngẫu nhiên để tạo ra cá thể mới.
- Đột biến – sự thay đổi ngẫu nhiên trong gen giúp khám phá các hướng tiến hóa mới.

Chính tính ngẫu nhiên có kiểm soát này giúp GA:
- Duy trì đa dạng di truyền trong quần thể.
- Khám phá không gian lời giải một cách toàn diện hơn.
- Tránh hội tụ sớm vào các cực trị cục bộ.

Randomness không phải là sự bất định vô nghĩa — mà là công cụ tiến hóa có chủ đích trong môi trường tính toán.

1. Khởi tạo quần thể
- Các cá thể ban đầu được sinh ra ngẫu nhiên trong không gian tìm kiếm.
- Mục tiêu: đảm bảo sự đa dạng ban đầu, tránh bias và tăng khả năng khám phá.

2. Chọn lọc (Selection)
- Dù dựa trên giá trị fitness, quá trình chọn lọc thường có yếu tố ngẫu nhiên (ví dụ: roulette wheel, tournament).
- Mục tiêu: duy trì đa dạng di truyền, tránh hiện tượng "gen trội" chiếm ưu thế quá sớm.
* Cách chọn lọc diễn ra như sau:
- Ngẫu nhiên chọn 2 cá thể từ quần thể hiện tại.
- So sánh giá trị fitness của 2 cá thể này.
- Giữ lại cá thể có fitness cao hơn.

3. Lai ghép (Crossover)
- Vị trí lai ghép hoặc hệ số tổ hợp giữa hai cá thể thường được chọn ngẫu nhiên.
- Mục tiêu: tạo ra tổ hợp gen mới, tăng khả năng sinh ra lời giải tốt hơn.

Crossover trong giải thuật di truyền mô phỏng quá trình trao đổi chéo giữa các nhiễm sắc thể trong sinh học. Như minh họa trong hình, một phần gen từ cá thể cha được kết hợp với một phần gen từ cá thể mẹ, tạo ra một cá thể con mang đặc điểm di truyền từ cả hai nguồn.

Quá trình này giúp duy trì sự đa dạng di truyền trong quần thể, đồng thời tạo ra các tổ hợp gen mới có tiềm năng thích nghi tốt hơn với bài toán tối ưu.

4. Đột biến (Mutation)
- Một phần nhỏ của cá thể bị thay đổi ngẫu nhiên.
- Mục tiêu: khám phá vùng mới trong không gian lời giải, thoát khỏi cực trị cục bộ.

Giải thuật sẽ tạo ra một giá trị ngẫu nhiên (random value) và so sánh với ngưỡng đột biến (mutation rate). Nếu giá trị ngẫu nhiên này nhỏ hơn hoặc bằng ngưỡng đã định, thì quá trình đột biến sẽ được thực hiện tại vị trí gen tương ứng trong cá thể.

Cách tiếp cận này giúp đảm bảo rằng đột biến xảy ra một cách có kiểm soát nhưng vẫn duy trì yếu tố ngẫu nhiên cần thiết để tạo ra sự đa dạng trong quần thể.

4. Mở rộng GA: Hàm Sphere và Bài toán Hồi quy Tuyến tính

4.1. Khái niệm hàm fitness - Đánh giá độ tốt của các thể

Hàm fitness (Fitness Function) là một hàm đánh giá mức độ thích nghi của mỗi cá thể trong quần thể với mục tiêu tối ưu của bài toán, xác định xem cá thể nào tốt hơn để giữ lại và cá thể nào bị loại bỏ trong quá trình tiến hóa
$$ Fitness(x) = f(x) $$
Trong đó:
- $f(X)$: Hàm mục tiêu do người dùng tự định nghĩa tùy theo bài toán với mục tiêu có thể là tối đa hoặc tối thiểu hóa tùy thuộc bài toán
- $x = [x_1, x_2, ... x_n]$: Bộ gene của cá thể

Tùy thuộc bài toán cụ thể, người dùng có thể thiết kế ra các hàm đánh giá fitness khác nhau để có thể đánh giá cho phù hợp

• Ví dụ: Với trường hợp quần thể hươu cao cổ, ban đầu có các chiều cao khác nhau, sau nhiều thế hệ thì chỉ có các cá thể có cổ dài hơn sống sót, các cá thể cổ ngắn chết dần, qua nhiều thế hệ hình thành hươu có cổ dài hơn để thích nghi với môi trường sống

=> Trong bài toán này, hàm fitness có thể là chiều cao của cổ. Cổ càng dài sẽ dễ vươn tới những tán lá cao, giúp chúng tiếp cận nguồn thức ăn dồi dào hơn và giảm sự cạnh tranh của các loài khác

4.2. Trường hợp con của hàm fitness: Hàm Sphere

• Hàm Sphere là một trường hợp con của hàm fitness, hàm này thường đơn giản và được lấy để đánh giá khả năng hội tụ và hiệu suất tìm kiếm cực trị toàn cục của thuật toán
• Hàm này có mục tiêu đơn giản: Tìm giá trị tối ưu sao cho tổng $f(x) = 0$

$$ f(x) = \sum_{i=1}^{n} x_i^2 $$

• Trong đó:

  • $x_i$ : Gene thứ $i$ trong cá thể, hay ta có thể hiểu là một tham số cần tối ưu
  • $n$: Số lượng gene trong cá thể, hay số chiều của không gian tìm kiếm

• Ví dụ cơ bản về cách thức hoạt động của hàm Sphere

  • Giả sử ta có hàm Sphere với $n=2$, ta sẽ có công thức:

  $$ f(x) = x_1^2 + x_2^2 $$

  • Với ví dụ này, ta sẽ làm việc với bộ data input đầu vào đơn giản được trình bày ở dưới đây:

• Bước 0: Khởi tạo các tham số đầu vào
  • n_generations=2: Số lượng lặp lại
  • size_of_population=4: Số lượng cá thể trong quần thể
  • size_selection_pool=5: Số lượng cá thể tốt trong

selection_pool
- elitism=0: Vì ở đây có khá ít cá thể nên sẽ không chọn lọc ra các cá thể ưu tú trước
- CrossOverRate=0.5: Tỷ lệ lai ghép giữa 2 cặp gene của 2 cặp bố mẹ, ở đây ta sẽ dùng Uniform Crossover (Phép lai đồng nhất) xét từng gene theo tỷ lệ
- MutationRate=0.05: Tỷ lệ đột biến của các gene trong 1 cá thể
- Bước 1: Đánh giá độ thích nghi
- Ta sẽ tiến hành đánh giá độ thích nghi của từng cá thể bằng cách thế vào hàm Sphere như đã trình bày ở trên, ta sẽ có 1 bảng đánh giá như sau:

Với bài toán này, ta cần tối ưu sao cho hàm $f(x)$ đạt giá trị nhỏ nhất, tức là $f(x)$ tiến đến 0

• Bước 2: Chọn lọc
  • Ta có quy trình chọn lọc ra các cá thể tốt nhất với size_selection_pool=5 như sau:
    • Chọn ngẫu nhiên 2 cá thể từ quần thể hiện tại
    • So sánh giá trị fitness của 2 cá thể này
    • Giữ lại cá thể có fitness cao hơn

• Bước 3: Lai ghép
  • Ta thực hiện lai ghép bằng phương pháp Uniform crossover, với CrossOverRate=0.5 , ta có quy trình như sau:
    • Với từng vị trí trong chuỗi gene, sinh ra 1 số ngẫu nhiên trong khoảng $[0,1]$
    • Nếu số nhỏ hơn hoặc bằng so với CrossOverRate=0.5 thì thực hiện hoán đổi gene giữa 2 cá thể tại vị trí đó

Sau quá trình lai ghép, ta thu được quần thể sau:

• Bước 4: Đột biến
  • Với các cá thể vừa thu được từ lai ghép, ta thực hiện quá trình đột biến, ở đây ta chọn MutationRate=0.05 , ta cũng sẽ xét theo phương pháp Uniform crossover như ở trên:
    • Với từng vị trí trong chuỗi gene, sinh ra 1 số ngẫu nhiên trong khoảng $[0,1]$
    • Nếu số nhỏ hơn hoặc bằng so với MutationRate=0.05 thì thực hiện đột biến gene tại vị trí đó bằng cách cộng thêm với 1 khoảng giá trị nhiễu nhỏ ngẫu nhiên, giúp thuật toán thoát khỏi cực trị cục bộ, tránh hội tụ quá sớm

Và cuối cùng ta thu được quần thể sau đột biến

• Bước 5: Lặp lại cho đến khi đạt điều kiện dừng

  • Đây là bước cuối cùng nhằm quyết định xem có tiếp tục tối ưu hay kết thúc giải thuật di truyền, một số tiêu chí phổ biến để dừng như sau:
    • Đã đạt số thế hệ tối đa
    • Đạt ngưỡng fitness mong muốn
    • Nếu sau nhiều thế hệ liên tiếp mà chất lượng của cá thể tốt nhất không tăng, thì việc dừng thuật toán vì có khả năng đã hội tụ

4.3. Hàm fitness trong bài toán hồi quy tuyến tính

• Khi xét giải thuật Genetic Algorithm (GA) trong bài toán hồi quy tuyến tính, trước hết ta sẽ có công thức tổng quát của hồi quy tuyến tính đa biến như sau:

$$ \hat{y} = b + w_1 x_1 + w_2 x_2 + ... + w_n x_n $$

• Trong đó:

  • $b$: Hệ số chệch (bias) giúp mô hình không bắt buộc đi qua gốc tọa độ
  • $w = [w_1, w_2,..., w_n]$: Trọng số của mô hình
  • $\hat{y}$: Kết quả dự đoán của mô hình

• Với bài toán này, ta có thể coi hàm loss function MSE là hàm fitness với mục tiêu là tối thiểu hóa giá trị lỗi

$$ MSE = \frac{1}{N} \sum_{i=1}^{N} (y_i - \hat{y}_i)^2 $$

• Vì GA là một thuật toán tối ưu hóa, nên ta sẽ có các hướng khác nhau khi lấy hàm MSE làm hàm fitness

  • Cách 1: Đảo ngược và chuẩn hóa loss trong khoảng $[0,1]$, loss càng thấp (tiến về 0) thì sẽ cho đầu ra fitness càng cao

  $$ Fitness = \frac{1}{1+MSE} $$

  • Cách 2: Đảo ngược lại hàm MSE, biến bài toán tối thiểu hóa MSE thành tối đa hóa -MSE

  $$ Fitness = -MSE $$

  • Cách 3: Đơn giản là lấy luôn hàm MSE để đánh giá

  $$ Fitness = MSE $$

• Tuy nhiên, các quá trình hoạt động của thuật toán về sau sẽ thay đổi để tùy thuộc với cách thiết kế ra hàm fitness, ví dụ nếu dùng Cách 3, trong quá trình chọn lọc sẽ chọn ra cá thể có độ đo fitness thấp hơn thay vì cao hơn

• Ví dụ: Cho bộ dataset đơn giản như sau:

Ta coi hàm fitness là MSE, vậy ở đây quy về bài toán tối ưu sao cho hàm loss đạt giá trị nhỏ nhất

• Bước 0: Ta cần xác định các tham số đầu vào trước, ở đây ta sẽ có các bộ tham số:
  • n_generations=2: Số lượng lặp lại
  • size_of_population=10: Số lượng cá thể trong quần thể
  • size_selection_pool=5: Số lượng cá thể tốt trong selection_pool
  • elitism=0.2: Tỷ lệ % các cá thể tốt nhất được giữ lại trực tiếp cho thế hệ tiếp theo, bỏ qua quá trình chọn lọc, lai ghép và đột biến
  • CrossOverRate=0.95: Tỷ lệ lai ghép giữa 2 cặp gene của 2 cặp bố mẹ, ở đây ta sẽ dùng Uniform Crossover (Phép lai đồng nhất) xét từng gene theo tỷ lệ
  • MutationRate=0.05: Tỷ lệ đột biến của các gene trong 1 cá thể
• Bước 1: Khởi tạo bộ trọng số random ngẫu nhiên
  • Vì ở đây có 2 giá trị đầu vào (feature) nên ta sẽ có 3 trọng số là $b, w_1, w_2$ được khởi tạo random 10 lần tương ứng với size_of_population=10

• Bước 2: Đánh giá độ thích nghi Fitness
  • Công thức tính toán cho giá trị dự đoán như sau:
    $$ \hat{y} = b + w_1x_1 + w_2x_2 $$
  • Công thức tính toán cho Fitness score (ở đây là MSE) như sau:
    $$ MSE = \frac{1}{N} \sum_{i=1}^{N} (y_i - \hat{y}_i)^2 $$

• Bước 2.1: Sắp xếp theo độ fitness từ tốt nhất

• Bước 2.2: Chọn ra các cá thể ưu tú, giữ lại và không tham gia vào quá trình chọn lọc, lai ghép, đột biến, với chỉ số elitism=0.2 và size_of_population=10, ta chọn ra 2 cá thể ưu tú nhất.

• Bước 3: Chọn lọc ra các cá thể tốt nhất trong quần thể còn lại để đưa vào Selection Pool qua quy trình:

  • Chọn ngẫu nhiên 2 cá thể từ quần thể hiện tại
  • So sánh giá trị fitness của 2 cá thể này
  • Giữ lại cá thể có fitness cao hơn

  Ta có bảng các quần thể còn lại như sau:

• Tiến hành chọn ngẫu nhiên cặp các thể khác nhau từ quần thể còn lại, so sánh fitness và giữ lại cá thể có fitness cao hơn để đưa vào Selection Pool.

• Và ta sẽ có được Selection Pool chứa các cá thể sau:

• Bước 4: Tiến hành lai ghép các cá thể trong Selection Pool
  • Các cá thể trong Selection Pool sẽ được bắt cặp ngẫu nhiên để tạo ra thế hệ con mới sao cho tổng số cặp cá thể con được tạo ra + số cá thể ưu tú chọn ở trên = size_of_population=10
  • Sau đây là ảnh mô phỏng, ta lấy ngẫu nhiên cặp cá thể bố mẹ 7 và 4, ứng với từng gene, ta sẽ tiến hành random trong khoảng $[0,1]$, nếu giá trị bé hơn CrossOverRate=0.95, sẽ tiến hành đổi gene giữa 2 cá thể, và cuối cùng sinh ra 2 cá thể con mới
  • Tương tự, ta thu được bảng kết quả như sau:

• Bước 5: Tiến hành đột biến các cá thể với mô phỏng như sau:
  • Xét từng gene trong cá thể sau khi lai ghép, nếu tỷ lệ random trong khoảng $[0,1]$ bé hơn mức ngưỡng MutationRate=0.05 sẽ tiến hành cộng thêm 1 giá trị
  • Tương tự với các cá thể còn lại, ta thu được bảng sau khi thực hiện đột biến:

Trong bảng này có 5 gene bị đột biến gồm các vị trí C1-w1, C3-w1, C5-b, C7-b, C7-w2

• Bước 6: Tạo ra quần thể mới và lặp lại
  • Ta ghép 2 cá thể ưu tú với 8 cá thể sau đột biến, tạo ra quần thể mới

• Các bước này được lặp lại cho đến khi đạt 1 trong các mục tiêu:
  • Đạt hệ số tối đa: Khi lặp số vòng lặp nhất định
  • Đạt ngưỡng fitness mong muốn: Nếu cá thể tốt nhất trong quần thể có giá trị fitness đủ cao, tức lời giải đã tốt thì có thể dừng
  • Không có cải thiện: Nếu sau nhiều thế hệ liên tiếp mà chất lượng của cá thể tốt nhất không tăng, dừng thuật toán vì có thể đã hội tụ

5. Triển khai code (Vinh)

5.1. Bài toán OneMax với GA

• Thuật Toán Di Truyền Đơn Giản (Genetic Algorithm - GA)

• Mục tiêu: Tối đa hóa số lượng bit 1 trong chuỗi nhị phân (Bài toán OneMax)

Bước 1: Import các thư viện và khởi tạo tham số đầu vào

"""
Thuật Toán Di Truyền Đơn Giản (Genetic Algorithm - GA)
Mục tiêu: Tối đa hóa số lượng bit 1 trong chuỗi nhị phân (Bài toán OneMax)
"""

import random
import matplotlib.pyplot as plt

n = 100               # Độ dài của mỗi cá thể (chuỗi nhị phân). Mục tiêu là đạt fitness = n.
m = 200               # Kích thước quần thể (số lượng cá thể trong mỗi thế hệ).
generations = 300      # Số thế hệ tối đa mà thuật toán sẽ chạy.
elitism = 5           # Số lượng cá thể "tinh hoa" (tốt nhất) được giữ lại trực tiếp
                      # cho thế hệ sau mà không bị lai ghép hay đột biến.
crossover_rate = 0.9  # Tỷ lệ lai ghép (90% cơ hội các cặp cha mẹ sẽ lai ghép).
mutation_rate = 0.05  # Tỷ lệ đột biến (5% cơ hội mỗi gen sẽ bị lật)

Bước 2: Xây dựng các hàm tạo giá trị ngẫu nhiên, tính toán độ thích nghi của một cá thể, tạo cá thể ngẫu nhiên.

#Tạo giá trị ngẫu nhiên 0 hoặc 1
def generate_random_value():
    return random.randint(0, 1)

#Tính toán độ thích nghi (fitness) của một cá thể.
def compute_fitness(individual):
    return sum(individual)

#Tạo một cá thể (giải pháp) ngẫu nhiên với độ dài n.
def create_individual(n):
    return [generate_random_value() for _ in range(n)]

Bước 3: Xây dựng các hàm lai ghép, đột biến, chọn lọc

"""
Hàm Lai ghép (Crossover) - Sử dụng phương pháp Uniform Crossover.
Tạo ra 2 con từ 2 cha mẹ (ind1, ind2).
"""
def crossover(ind1, ind2, rate=0.9):

    # Tạo bản sao của cha mẹ để không làm thay đổi cá thể gốc
    ind1_new = ind1.copy()
    ind2_new = ind2.copy()

    # Chỉ thực hiện lai ghép nếu một số ngẫu nhiên nhỏ hơn tỷ lệ lai ghép
    if random.random() < rate:
        # Lặp qua từng vị trí gen
        for i in range(len(ind1)):
            # Tung đồng xu (50% cơ hội)
            if random.random() < 0.5:
                # Nếu True, hoán đổi gen tại vị trí i giữa 2 cá thể con
                ind1_new[i] = ind2[i]
                ind2_new[i] = ind1[i]

    # Trả về hai cá thể con mới
    return ind1_new, ind2_new

"""
Hàm Đột biến (Mutation) - Lật bit ngẫu nhiên.
Duyệt qua từng gen của cá thể và lật nó (0->1, 1->0) với một xác suất nhỏ.
"""
def mutate(individual, rate=0.05):
    return [1 - val if random.random() < rate
            else val for val in individual]

"""
Hàm Chọn lọc (Selection) - Sử dụng phương pháp Tournament Selection.
Chọn ra cá thể tốt nhất từ một nhóm nhỏ ngẫu nhiên.
"""
def selection(population):

    tournament_size = 3  # Chọn 3 cá thể ngẫu nhiên để "thi đấu"

    # Lấy ngẫu nhiên 'tournament_size' cá thể từ quần thể
    tournament = random.sample(population, tournament_size)

    # Tìm cá thể tốt nhất trong nhóm "thi đấu"
    best_individual = tournament[0]
    best_fitness = compute_fitness(best_individual)

    for ind in tournament[1:]:
        fitness = compute_fitness(ind)
        if fitness > best_fitness:
            best_individual = ind
            best_fitness = fitness

    return best_individual.copy()

Bước 4: Chương trình chính thực hiện huấn luyện GA qua nhiều thế hệ và thực hiện đánh giá

# Chương trình chính
print("Thuật toán di truyền - Bài toán OneMax")
print(f"Độ dài cá thể (n): {n}")
print(f"Kích thước quần thể (m): {m}")
print(f"Số thế hệ (generations): {generations}")
print(f"Số lượng tinh hoa (elitism): {elitism}")
print(f"Tỷ lệ lai ghép (crossover): {crossover_rate}")
print(f"Tỷ lệ đột biến (mutation): {mutation_rate}")

# 1. Khởi tạo quần thể ban đầu (Thế hệ 0)
# Tạo ra 'm' cá thể ngẫu nhiên, mỗi cá thể dài 'n'
population = [create_individual(n) for _ in range(m)]

# Các list để lưu lại lịch sử tiến hóa (dùng để vẽ biểu đồ)
fitness_history = []          # Fitness tốt nhất mỗi 10 thế hệ
best_fitness_history = []     # Fitness tốt nhất của mọi thế hệ
average_fitness_history = []  # Fitness trung bình của mọi thế hệ

# 2. Vòng lặp tiến hóa qua các thế hệ
for gen in range(generations):

    # 2.1. Đánh giá (Evaluation)
    # Sắp xếp quần thể: cá thể tốt nhất (fitness cao nhất) lên đầu
    population = sorted(population,
                        key=compute_fitness,
                        reverse=True)         

    # 2.2. Thu thập thống kê
    fitness_values = [compute_fitness(ind) for ind in population]
    best_fitness = fitness_values[0]       # Fitness tốt nhất
    avg_fitness = sum(fitness_values) / len(fitness_values) # Fitness trung bình
    worst_fitness = fitness_values[-1]     # Fitness tệ nhất

    # Lưu lại lịch sử
    best_fitness_history.append(best_fitness)
    average_fitness_history.append(avg_fitness)

    # 2.3. In kết quả và kiểm tra điều kiện dừng
    # In thông báo mỗi 10 thế hệ
    if gen % 10 == 0:
        print(f"Generation {gen:3d} - Best: {best_fitness:3d} - "
              f"Average: {avg_fitness:.1f} - Worst: {worst_fitness:3d}")
        fitness_history.append(best_fitness) # Chỉ lưu mỗi 10 thế hệ cho biểu đồ 1

    # Điều kiện dừng: Nếu đã tìm thấy giải pháp tối ưu (toàn bit 1)
    if best_fitness == n:
        print(f"\\n Thế hệ {gen}!")
        print(f"Cá thể tối ưu: Chuỗi {n} bit 1")
        fitness_history.append(best_fitness) # Lưu điểm cuối cùng
        break  # Thoát khỏi vòng lặp tiến hóa

    # 2.4. Tạo quần thể mới (New Generation)
    new_population = []

    # 2.4.1. Elitism (Giữ lại tinh hoa)
    # Giữ lại số lượng elitism cá thể tốt nhất từ thế hệ cũ
    new_population.extend(population[:elitism])

    # 2.4.2. Sinh sản (Reproduction)
    # Lấp đầy phần còn lại của quần thể mới (m - elitism)
    while len(new_population) < m:
        # a. Chọn lọc (Selection)
        # Chọn 2 cha mẹ từ quần thể cũ
        parent1 = selection(population)
        parent2 = selection(population)

        # b. Lai ghép (Crossover)
        # Tạo ra 2 con từ 2 cha mẹ
        child1, child2 = crossover(parent1, parent2, crossover_rate)

        # c. Đột biến (Mutation)
        # Áp dụng đột biến cho cả 2 con
        child1 = mutate(child1, mutation_rate)
        child2 = mutate(child2, mutation_rate)

        # d. Thêm con vào quần thể mới
        new_population.append(child1)
        if len(new_population) < m: #
            new_population.append(child2)

    # 2.5. Thay thế (Replacement)
    # Quần thể mới thay thế hoàn toàn quần thể cũ
    population = new_population[:m]

# 3. Kết thúc và In kết quả cuối cùng
# Sắp xếp quần thể cuối cùng để tìm cá thể tốt nhất
best_individual = sorted(population,
                         key=compute_fitness,
                         reverse=True)[0]
final_fitness = compute_fitness(best_individual)

print("Kết quả cuối cùng:")
print(f"Fitness tốt nhất: {final_fitness}/{n}")
print(f"Tỷ lệ tối ưu: {final_fitness/n*100:.1f}%")
# In 20 gen đầu tiên của cá thể tốt nhất
print(f"Cá thể tốt nhất (20 gen đầu): {best_individual[:20]}...")

Output:

Fitness ban đầu (Gen 0): 61
Fitness cuối cùng: 97
Cải thiện: +36 (59.0%)
Đạt 95% tối ưu (fitness >= 95) tại thế hệ: 67
Độ đa dạng quần thể cuối (Range): 24
(Max: 97, Min: 73)

Nhận xét: 

Thuật toán di truyền đã hoạt động tốt và hiệu quả cho bài toán OneMax:

• Hiệu quả (Effectiveness): Đạt được giải pháp gần như hoàn hảo (97/100).

• Hội tụ (Convergence): Cho thấy sự cải thiện rõ rệt qua các thế hệ.

• Bền vững (Robustness): Duy trì được độ đa dạng di truyền tốt, giúp tránh bị mắc kẹt sớm và đảm bảo quá trình tìm kiếm vẫn tiếp diễn (Độ đa dạng quần thể cuối là 24).

5.2. Bài toán Linear Regression với GA

Bước 1: Import thư viện và khởi tạo các tham số đầu vào

import random
import numpy as np
from numpy import genfromtxt
import matplotlib.pyplot as plt

n = 2                  # Độ dài cá thể (chromosome), [theta_0, theta_1]
m = 100                # Kích thước quần thể
generations = 100      # Số thế hệ
elitism = 2            # Số lượng "tinh hoa"
crossover_rate = 0.9   # Tỷ lệ lai ghép
mutation_rate = 0.05   # Tỷ lệ đột biến
search_bound = 100     # Giới hạn tìm kiếm cho các giá trị theta

Bước 2: Tải dữ liệu từ data.csv, vẽ các điểm dữ liệu từ data.csv

# Tải dữ liệu từ data.csv, bỏ qua dòng tiêu đề
data = genfromtxt('data.csv', delimiter=',', skip_header=1)
X = data[:,:1]
y = data[:,1]

# Thêm cột bias (toàn số 1) vào X để tính toán theta_0
X = np.c_[np.ones((X.shape[0], 1)), X]

print("--- Ma trận X (đã thêm cột bias) ---")
print(X[:5]) # In 5 dòng đầu
print("\\n--- Vector y (target) ---")
print(y[:5])

# Trực quan hóa Dữ liệu ban đầu
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(6, 4))
ax.set_ylim((0, 9))
ax.set_xlim((0, 7))

plt.scatter(X[:, 1], y)
plt.xlabel('Area')
plt.ylabel('House Price')
plt.title('Dữ liệu Huấn luyện')
plt.show()

Bước 3: Xây dựng các hàm tạo giá trị ngẫu nhiên, tính toán độ thích nghi của một cá thể, tạo cá thể ngẫu nhiên

# Tạo một giá trị thực ngẫu nhiên trong khoảng [-bound, +bound].
def generate_random_float(bound=search_bound):
    return (random.random() * 2 - 1) * bound

# Tính hàm mất mát (MSE) cho một cá thể (bộ [theta_0, theta_1]).
def compute_loss(individual):
    theta = np.array(individual)
    y_hat = X.dot(theta)
    loss  = np.multiply((y_hat-y), (y_hat-y)).mean()
    return loss

"""
Tính độ thích nghi (fitness). GA sẽ TỐI ĐA HÓA fitness.
Chúng ta muốn TỐI THIỂU HÓA loss, nên fitness = 1 / (loss + epsilon).
"""
def compute_fitness(individual):
    loss = compute_loss(individual)
    fitness = 1 / (loss + 0.0001) # 0.0001 để tránh chia cho 0
    return fitness

def create_individual(n):
    return [generate_random_float() for _ in range(n)]

Bước 4: Xây dựng các hàm lai ghép, đột biến, chọn lọc

"""
    Hàm Lai ghép (Crossover)
    Sử dụng phương pháp Uniform Crossover.
"""
def crossover(ind1, ind2, rate=crossover_rate):

    ind1_new = ind1.copy()
    ind2_new = ind2.copy()

    if random.random() < rate:
        for i in range(len(ind1)):
            if random.random() < 0.5:
                ind1_new[i] = ind2[i]
                ind2_new[i] = ind1[i]

    return ind1_new, ind2_new

"""
    Hàm Đột biến (Mutation)
"""
def mutate(individual, rate=mutation_rate):

    individual_m = individual.copy()
    for i in range(n): # n là độ dài cá thể (số gen)
        if random.random() < rate:
            individual_m[i] = generate_random_float()
    return individual_m

"""
Hàm Chọn lọc (Selection) - Sử dụng phương pháp Tournament Selection.
Chọn ra cá thể tốt nhất từ một nhóm nhỏ ngẫu nhiên.
"""
def selection(population):

    tournament_size = 3  # Chọn 3 cá thể ngẫu nhiên để "thi đấu"

    # Lấy ngẫu nhiên 'tournament_size' cá thể từ quần thể
    tournament = random.sample(population, tournament_size)

    # Tìm cá thể tốt nhất trong nhóm "thi đấu"
    best_individual = tournament[0]
    best_fitness = compute_fitness(best_individual)

    for ind in tournament[1:]:
        fitness = compute_fitness(ind)
        if fitness > best_fitness:
            best_individual = ind
            best_fitness = fitness

    return best_individual.copy()

Bước 5: Chương trình chính thực hiện huấn luyện GA qua nhiều thế hệ và thực hiện đánh giá

# Chương trình chính

print("--- Bắt đầu quá trình Tiến hóa GA cho Hồi quy Tuyến tính ---")
print(f"Kích thước quần thể (m): {m}")
print(f"Số thế hệ (generations): {generations}")
print(f"Số lượng tinh hoa (elitism): {elitism}")
print(f"Tỷ lệ lai ghép (crossover): {crossover_rate}")
print(f"Tỷ lệ đột biến (mutation): {mutation_rate}")

# 1. Khởi tạo quần thể ban đầu
population = [create_individual(n) for _ in range(m)]

# Các list để lưu lại lịch sử tiến hóa
best_fitness_history = []
average_fitness_history = []
best_loss_history = [] # Thêm list để lưu loss tốt nhất

# 2. Vòng lặp tiến hóa qua các thế hệ
for gen in range(generations):

    # 2.1. Đánh giá (Evaluation)
    # Sắp xếp quần thể: cá thể tốt nhất (fitness cao nhất) lên đầu
    population = sorted(population,
                        key=compute_fitness,
                        reverse=True)

    # 2.2. Thu thập thống kê
    fitness_values = [compute_fitness(ind) for ind in population]
    best_fitness = fitness_values[0]
    avg_fitness = sum(fitness_values) / len(fitness_values)

    # Tính loss tốt nhất từ fitness tốt nhất
    best_loss = (1 / best_fitness) - 0.0001 if best_fitness != 0 else float('inf')

    # Lưu lại lịch sử
    best_fitness_history.append(best_fitness)
    average_fitness_history.append(avg_fitness)
    best_loss_history.append(best_loss)

    # 2.3. In kết quả
    if gen % 10 == 0:
        print(f"Generation {gen:3d} - Best Fitness: {best_fitness:8.4f} - "
              f"Average Fitness: {avg_fitness:8.4f} - Best Loss (MSE): {best_loss:8.6f}")

    # 2.4. Tạo quần thể mới
    new_population = []

    # 2.4.1. Elitism (Giữ lại tinh hoa)
    new_population.extend(population[:elitism])

    # 2.4.2. Sinh sản (Lấp đầy phần còn lại)
    while len(new_population) < m:
        parent1 = selection(population)
        parent2 = selection(population)

        child1, child2 = crossover(parent1, parent2)

        child1 = mutate(child1)
        child2 = mutate(child2)

        new_population.append(child1)
        if len(new_population) < m:
            new_population.append(child2)

    # 2.5. Thay thế
    population = new_population[:m]

# 3. Kết thúc và In kết quả cuối cùng
print("Quá trình tiến hóa hoàn tất!")

best_individual = sorted(population,
                         key=compute_fitness,
                         reverse=True)[0]
final_fitness = compute_fitness(best_individual)
final_loss = compute_loss(best_individual)

print(f"Loss (MSE) tốt nhất: {final_loss:.8f}")
print(f"Fitness tốt nhất: {final_fitness:.4f}")
print(f"Cá thể tốt nhất (theta_0, theta_1): {best_individual}")

• Output:

Kích thước quần thể (m): 100
Số thế hệ (generations): 100
Số lượng tinh hoa (elitism): 2
Tỷ lệ lai ghép (crossover): 0.9
Tỷ lệ đột biến (mutation): 0.05

• Generation 0 - Best Fitness: 0.0024 - Average Fitness: 0.0002 - Best Loss (MSE): 409.709949
• Generation 10 - Best Fitness: 0.0408 - Average Fitness: 0.0363 - Best Loss (MSE): 24.510438
• Generation 20 - Best Fitness: 0.0408 - Average Fitness: 0.0361 - Best Loss (MSE): 24.510438
• Generation 30 - Best Fitness: 0.0449 - Average Fitness: 0.0367 - Best Loss (MSE): 22.293423
• Generation 40 - Best Fitness: 0.0449 - Average Fitness: 0.0405 - Best Loss (MSE): 22.293423
• Generation 50 - Best Fitness: 0.0449 - Average Fitness: 0.0400 - Best Loss (MSE): 22.293423
• Generation 60 - Best Fitness: 0.0451 - Average Fitness: 0.0405 - Best Loss (MSE): 22.182128
• Generation 70 - Best Fitness: 0.0525 - Average Fitness: 0.0402 - Best Loss (MSE): 19.031115
• Generation 80 - Best Fitness: 0.0525 - Average Fitness: 0.0475 - Best Loss (MSE): 19.031115
• Generation 90 - Best Fitness: 0.0525 - Average Fitness: 0.0489 - Best Loss (MSE): 19.031115

-> Quá trình tiến hóa hoàn tất!
Loss (MSE) tốt nhất: 19.03111518
Fitness tốt nhất: 0.0525
Cá thể tốt nhất (theta_0, theta_1): [-9.545461166129154, 4.318013691517031]

Thuật toán đã cải thiện đáng kể giải pháp, giảm Best Loss (MSE) từ 409.7 xuống chỉ còn 19.03 trong vòng 100 thế hệ.

Quá trình hội tụ không diễn ra một cách trơn tru mà theo dạng "bậc thang":

• Hội tụ nhanh (Gen 0-10): Tìm thấy một giải pháp "khá tốt" ban đầu.

• Mắc kẹt (Gen 10-20): Bị kẹt tại giải pháp đó.

• Nhảy vọt (Gen 30, 70): Một đột biến (mutation) hoặc lai ghép (crossover) may mắn tạo ra một cá thể tốt hơn, giúp thuật toán thoát khỏi điểm tối ưu cục bộ.

• Hội tụ cuối (Gen 70-90): Thuật toán tìm thấy một giải pháp tốt (MSE 19.03) và ổn định ở đó cho đến hết.

6. Tóm tắt

💡 Insight 1: Tiến hóa Tự nhiên là Quá trình Tối ưu hóa (Optimization)

Sự tiến hóa của loài người và sinh vật có thể được xem là một quá trình tối ưu hóa kéo dài. GA mô phỏng triết lý này: sau mỗi thế hệ, các cá thể (lời giải) mới được sinh ra có độ thích nghi (Fitness) tốt hơn với môi trường (bài toán).

• Cốt lõi: GA vận hành trên nguyên tắc "Survival of the fittest" (chọn lọc tự nhiên).

💡 Insight 2: GA là Chiến lược Khám phá Song song cho Bài toán Hộp Đen

GA (Genetic Algorithm) đặc biệt hiệu quả với các bài toán tối ưu hóa mà hàm mục tiêu $f$ là “hộp đen” – tức ta có thể đánh giá kết quả, nhưng không biết công thức hay đạo hàm của nó.

• Minh triết: GA không tìm một lời giải đơn lẻ mà duy trì và tiến hóa cả một quần thể các cá thể cùng lúc. Cách tiếp cận này tạo ra nhiều hướng khám phá song song, giúp tránh rơi vào cực trị cục bộ và tăng khả năng thích nghi trong không gian tìm kiếm phức tạp.

💡 Insight 3: Sự Cân bằng giữa Kế thừa (Inheritance) và Đột biến (Variation)

Quá trình tiến hóa của GA được xây dựng dựa trên sự cân bằng giữa việc giữ lại các gen tốt và tạo ra sự đột phá.

• Kế thừa (Crossover): Các cá thể tốt được chọn (Selection) để sinh sản, trao đổi vật chất di truyền (Crossover) để tạo ra con cái có sự pha trộn gen tốt hơn.

• Đột biến (Mutation): Đưa vào những thay đổi ngẫu nhiên nhỏ 1010, giúp khám phá các vùng mới trong không gian tìm kiếm và tránh mắc kẹt tại cực trị cục bộ.

💡 Insight 4: Thành phần Cơ bản: Mã hóa Gen, Đo lường Fitness

Để áp dụng GA, cần phải chuyển bài toán thực tế thành ngôn ngữ sinh học máy tính.

• Chromosome (Nhiễm sắc thể): Là cách mã hóa (encoding) một giải pháp tiềm năng.
  Ví dụ: One-Max Problem dùng chuỗi bit Binary, còn Sphere Function dùng vector số thực.

• Fitness Function: Là hàm đo lường độ tốt của cá thể, xác định mức độ phù hợp để tiếp tục sinh tồn và sinh sản.

7. Thảo luận

7.1. Vì sao GA cần yếu tố Ngẫu nhiên (Randomness)?

👉 Randomness là chìa khóa cho Khám phá (Exploration). Nó giúp GA liên tục tạo ra các biến thể (variation), ngăn chặn sự đồng nhất gen (Homogeneity) của quần thể, nhờ đó có thể tìm kiếm được giải pháp tốt hơn và tránh bị mắc kẹt tại các bẫy cục bộ.

7.2. Fitness và Loss có gì khác nhau ?

👉 Fitness thường là hàm nghịch đảo của Loss (ví dụ: $Fitness \approx \frac{1}{Loss + \epsilon}$). Chúng ta cần hàm Fitness vì triết lý cốt lõi của GA là mô phỏng chọn lọc tự nhiên, nơi các cá thể "khỏe mạnh" (có Fitness cao) phải có xác suất sống sót/sinh sản cao hơn.

7.3. GA có phải là thuật toán Tốt nhất?

👉 Không phải là tốt nhất. Đối với các hàm đơn giản, liên tục, có đạo hàm rõ ràng, các phương pháp tính toán trực tiếp (như dùng đạo hàm/Gradient Descent) sẽ nhanh hơn và chính xác hơn rất nhiều. GA nên được dành cho những bài toán mà phương pháp truyền thống gặp khó khăn.

8. Kết luận

Genetic Algorithm là minh chứng cho thấy những nguyên lý sinh học cơ bản—như chọn lọc, lai ghép và đột biến—lại có thể là những công cụ tính toán mạnh mẽ nhất. Đây không chỉ là một thuật toán tối ưu hóa, mà là một hướng tiếp cận triết học, nơi máy móc học cách tìm ra giải pháp tối ưu bằng cách mô phỏng hàng triệu năm tiến hóa của tự nhiên. GA vượt qua rào cản của những bài toán phức tạp không thể giải bằng công thức, mang lại một phương pháp linh hoạt và mạnh mẽ cho Kỹ thuật Trí tuệ Nhân tạo hiện đại.

9. Tài liệu tham khảo

Slide buổi học thứ 3:
https://lms.aivietnam.edu.vn/api/files/6831882b519c0e157fb514eb/Documents%2F2025-9%2FM05W03%20-%20Genetic%20Algorithms%20(Warm-up)%2F%5BSlide_v2%5D-GA.pdf

Slide buổi học thứ 4:
https://lms.aivietnam.edu.vn/api/files/68318833519c0e157fb514ec/Documents%2F2025-9%2FM05W03%20-%20Randomness%20and%20Genetic%20Algorithms%2F%5BSlide_v4%5D-StepsIntoGAs.pdf

Slide buổi học thứ 6:
https://lms.aivietnam.edu.vn/api/files/68318843519c0e157fb514ee/Documents%2F2025-9%2FM05W03%20-%20Genetic%20Algorithms%20(Optimization%20and%20Linear%20regression)%2FAIO2025_Genetic_Linear_Regression_v2.pdf