Giới thiệu về giải thuật Di Truyền để giải quyết bài toán tối ưu phức tạp

1. Hạn chế của các phương pháp tối ưu truyền thống

Trong các bài toán tối ưu cổ điển, ta thường biết rõ hàm mục tiêu và có thể tính đạo hàm.

Ví dụ:

• Tìm cực tiểu của $f(x) = x^2$ , dùng Gradient Descent.

• Tìm đường đi ngắn nhất, dùng Dijkstra.

Nhưng nếu ta không biết hàm f(x) hoạt động thế nào - chỉ biết "đưa vào input, nhận về output"?

Các kỹ thuật cổ điển, chẳng hạn như Gradient Descent (GD), hoạt động hiệu quả khi có thể tính toán đạo hàm của hàm mục tiêu. Tuy nhiên, chúng bộc lộ những hạn chế cố hữu khi đối mặt với các bài toán phức tạp, nơi không gian giải pháp chứa nhiều "cạm bẫy" khiến việc đưa ra quyết định chưa đủ tổng quát.

Hãy tưởng tượng bạn đang đứng trên sườn núi trong sương mù và muốn tìm điểm thấp nhất. Toàn bộ dãy núi này chính là không gian độ thích nghi (fitness landscape). GD hoạt động bằng cách "lần theo con dốc" dốc nhất, đi từng bước xuống dưới. Đây là phương pháp dựa trên quỹ đạo (trajectory-based) - nó đi theo một con đường duy nhất.

Phương pháp này hiệu quả khi địa hình bằng phẳng. Nhưng nó dễ bị "mắc kẹt" ở "thung lũng" gần đó (cực trị cục bộ) thay vì tìm ra "thung lũng sâu nhất" (cực trị toàn cục). Tệ hơn nữa, điều gì xảy ra nếu chúng ta không có bản đồ?

Đây chính là các bài toán "hộp đen" (black-box), nơi chúng ta chỉ biết đầu vào và đầu ra mà không thể nhìn vào cơ chế hoạt động bên trong. Với những bài toán này, các phương pháp như GD không thể áp dụng được.

Đây là lúc Thuật toán Di truyền (Genetic Algorithm - GA) tỏa sáng. Thay vì chỉ đi theo một con đường, GA là một phương pháp dựa trên quần thể (population-based). Nó lấy cảm hứng từ quá trình tiến hóa của tự nhiên để tung ra một "đội quân" các nhà thám hiểm, cho phép họ khám phá toàn bộ bản đồ cùng một lúc và học hỏi lẫn nhau.

2 .Ý tưởng cốt lõi - từ tiến hóa tự nhiên đến thuật toán

Ý tưởng trung tâm của Thuật toán Di truyền là bắt chước quá trình "chọn lọc tự nhiên" để tìm ra lời giải tốt nhất cho một vấn đề. Thay vì dùng toán học phức tạp, nó dựa trên nguyên lý đơn giản: giải pháp tốt hơn sẽ tồn tại, sinh sản và tạo ra các thế hệ giải pháp tốt hơn nữa.

Hãy xem xét câu chuyện về loài hươu cao cổ:

• Quần thể ban đầu: Trong một quần thể hươu, có những cá thể với chiều cao cổ khác nhau - một số cổ ngắn, một số cổ dài hơn.

• Áp lực chọn lọc: Môi trường sống của chúng có nguồn thức ăn chính là lá cây ở trên cao. Đây chính là "áp lực chọn lọc" của tự nhiên.

• Độ thích nghi (Fitness): Những con hươu cổ dài có "độ thích nghi" cao hơn vì chúng dễ dàng vươn tới nguồn thức ăn. Điều này giúp chúng có khả năng sống sót và sinh sản cao hơn những con hươu cổ ngắn.

• Kế thừa và Tiến hóa: Qua nhiều thế hệ, đặc điểm "cổ dài" được truyền lại cho con cháu và dần trở nên phổ biến. Kết quả là, cả quần thể hươu cao cổ đã tiến hóa để thích nghi tốt hơn với môi trường.

Thuật toán Di truyền áp dụng chính xác logic này bằng cách dịch các khái niệm sinh học sang thuật ngữ thuật toán.

Vậy, làm thế nào để chúng ta áp dụng những khái niệm này vào việc giải một bài toán máy tính cụ thể? Hãy cùng xem qua một ví dụ đơn giản gọi là One-Max.

3. Quy trình hoạt động của thuật toán di truyền (qua ví dụ One-Max)

Hãy tưởng tượng chúng ta có một bài toán rất đơn giản: tìm ra một chuỗi nhị phân (gồm các số 0 và 1) có chứa nhiều số 1 nhất.

Ví dụ: với chuỗi dài 5 ký tự, lời giải tối ưu là [1, 1, 1, 1, 1].

Đây là một bài toán "toy problem" kinh điển, được dùng để minh họa cơ chế của GA một cách rõ ràng nhất vì độ "tốt" của một lời giải (số lượng bit 1) có thể được đo lường ngay lập tức.

GA sẽ giải bài toán này qua các bước sau:

Nguồn: AIO 2025 Module 5 Week 3.

Quá trình tiến hóa lặp lại từ thế hệ đầu tiên cho đến khi đạt đến số lượng thế hệ đã định trước.
Trong ví dụ này, chúng ta đặt các tham số như sau:

Bước 1: Khởi tạo Quần thể (Initialization)

Đầu tiên, chúng ta tạo ra một "quần thể" ban đầu gồm nhiều "cá thể". Mỗi cá thể là một chuỗi bit ngẫu nhiên, đại diện cho một lời giải thử.

Ví dụ:

• Cá thể 1: [0, 0, 0, 0, 0]

• Cá thể 2: [0, 0, 0, 1, 0]

• Cá thể 3: [0, 1, 1, 1, 1]

• Cá thể 4: [1, 1, 1, 0, 0]

• Cá thể 5: [1, 1, 0, 1, 1]

Bước 2: Đánh giá Độ thích nghi (Fitness Evaluation)

Tiếp theo, chúng ta cần một cách để "chấm điểm" xem cá thể nào tốt hơn. Đây là lúc "hàm thích nghi" (fitness function) phát huy tác dụng.

Hàm thích nghi chính là cách chúng ta tương tác với bài toán "hộp đen". Chúng ta không cần biết "bên trong" hộp đen hoạt động ra sao, chúng ta chỉ cần một cách để đưa một lời giải vào và nhận về một điểm số chất lượng.

• Với hươu cao cổ, fitness là chiều cao cổ.

• Với chuột hoang sống trên nền đất tối màu, fitness có thể là màu lông sẫm giúp chúng ngụy trang khỏi những con diều hâu săn mồi. Một con chuột màu sáng, dù khỏe mạnh, sẽ có độ thích nghi thấp trong môi trường này vì nó dễ bị phát hiện.

Đối với bài toán One-Max, hàm thích nghi rất đơn giản: độ thích nghi (fitness) chính là tổng số bit 1 trong chuỗi của cá thể đó.

Ví dụ:

Bước 3: Chọn lọc (Selection)

Dựa trên điểm fitness, chúng ta chọn ra những cá thể "ưu tú" nhất để làm "cha mẹ" cho thế hệ tiếp theo. Đây là bước cân bằng giữa khai thác (exploitation) và khám phá (exploration).

• Elitism (Cá thể ưu tú) - Khai thác: Một chiến lược thông minh là luôn giữ lại một vài cá thể tốt nhất (có fitness cao nhất) và cho chúng đi thẳng vào thế hệ sau mà không cần thay đổi gì. Đây là chiến lược khai thác, đảm bảo chúng ta không vô tình làm mất đi lời giải tốt nhất đã tìm được và chất lượng quần thể không bị suy giảm.
  Ví dụ: Trong ví dụ trên, Cá thể 3 và Cá thể 5 (cùng có fitness = 4) sẽ được giữ lại.

• Chọn lọc "giải đấu" (Tournament Selection) - Khám phá: Đối với các cá thể còn lại, chúng ta tổ chức các "giải đấu" nhỏ: chọn ngẫu nhiên hai cá thể và cho cá thể có fitness cao hơn "chiến thắng" để vào vòng lai ghép. Cơ chế này mang tính khám phá, vì nó cho những cá thể "tốt" nhưng chưa phải "tốt nhất" một cơ hội sinh sản, giúp duy trì sự đa dạng di truyền và tránh hội tụ quá sớm vào một cực trị cục bộ.

Bước 4: Lai ghép (Crossover)

Nguồn: AIO 2025 Module 5 Week 3.

Đây là lúc phép màu thực sự xảy ra. Chúng ta cho các "cha mẹ" đã được chọn kết hợp "gen" của chúng để tạo ra "con cái", với hy vọng con cái sẽ kế thừa những đặc điểm tốt từ cả hai, tương tự như quá trình trao đổi chéo nhiễm sắc thể trong sinh học.

Nguồn: AIO 2025 Module 5 Week 3.

Một phương pháp phổ biến là Uniform Crossover (Lai ghép đồng nhất). Thay vì chỉ cắt và đổi một đoạn, phương pháp này xem xét từng gen một. Tại mỗi vị trí, chúng ta tung một đồng xu (với một xác suất nhất định, gọi là pcross) để quyết định xem gen của cá thể con sẽ đến từ cha hay mẹ.

Ví dụ: ta sử dụng theo Uniform Crossover

Nguồn: AIO 2025 Module 5 Week 3.

Bước 5: Đột biến (Mutation)

Để tránh quần thể trở nên quá "một màu" và bị mắc kẹt ở một giải pháp chưa phải tốt nhất, chúng ta thêm vào một chút ngẫu nhiên gọi là "đột biến". Mục đích chính của nó là giúp duy trì sự đa dạng di truyền và cho phép thuật toán "nhảy" ra khỏi các cực trị cục bộ.

Nếu lai ghép là cách khám phá thông minh các khu vực xung quanh những đỉnh đã biết trên không gian độ thích nghi, thì đột biến chính là chiến lược cấp tiến, cần thiết để nhảy sang các "dãy núi" hoàn toàn khác, phòng trường hợp dãy núi hiện tại không phải là cao nhất.

Nguồn: AIO 2025 Module 5 Week 3.

Trong bài toán One-Max, đột biến đơn giản là lật một bit ngẫu nhiên (từ 0 thành 1 hoặc 1 thành 0) với một xác suất rất nhỏ (muta). Trong bước này, ta thực hiện tương tự như các bước trong Crossover.
Đầu tiên, chọn trước một ngưỡng, ví dụ mutation rate = 0.05. Kế tiếp, tiến hành lấy các giá
trị ngẫu nhiên trong khoảng từ [0,1] cho các vị trí, nếu vị trí nào có giá trị thấp hơn hoặc bằng
ngưỡng thì thực hiện đột biến tại vị trí đó.

Ví dụ: Thực hiện đột biến cho các thể con 1

Nguồn: AIO 2025 Module 5 Week 3.

Và cứ thế, quy trình này lặp đi lặp lại qua nhiều thế hệ, mỗi thế hệ lại tiến gần hơn đến lời giải tối ưu.

Khi nào thuật toán dừng lại?

Thuật toán sẽ kết thúc khi một trong các điều kiện sau được thỏa mãn:

• Đạt số thế hệ tối đa: Khi thuật toán đã chạy đủ số vòng lặp định trước.

• Đạt ngưỡng fitness: Khi tìm thấy một lời giải đủ tốt theo yêu cầu.

• Không có cải thiện: Khi fitness của cá thể tốt nhất không tăng trong nhiều thế hệ liên tiếp, cho thấy thuật toán có thể đã hội tụ.

Quá Trình Tiến Hóa Hoàn Chỉnh:

Toàn bộ quá trình tạo thành một chu kỳ cân bằng giữa chọn lọc và lai ghép, phối hợp nhằm khai thác những vật liệu di truyền tốt nhất đã được phát hiện, từ đó hướng quần thể đến các vùng tiềm năng trong không gian lời giải. Đồng thời, đột biến đóng vai trò cung cấp yếu tố khám phá quan trọng, đưa vào các đặc điểm mới một cách ngẫu nhiên để ngăn thuật toán hội tụ sớm vào các cực trị cục bộ. Qua từng thế hệ, sự giằng co giữa khai thác và khám phá này dẫn dắt quần thể tiến dần tới cực trị toàn cục.

Trong ví dụ One-Max của chúng ta, ví dụ sau khi chạy qua 5 thế hệ, thuật toán đã tìm ra lời giải :

Ví dụ:

Nguồn: AIO 2025 Module 5 Week 3.

• Chuỗi fitness của cá thể tốt nhất qua các thế hệ là [4, 4, 4, 4, 5].

• Cá thể tốt nhất được tìm thấy: [1, 1, 1, 1, 1]

• Độ thích nghi tốt nhất: 5

Lưu ý rằng độ thích nghi tốt nhất đã không thay đổi trong các thế hệ 1, 2 và 3. Điều này là hoàn toàn bình thường và phản ánh bản chất của quá trình tìm kiếm: sự cải thiện không phải lúc nào cũng xảy ra ở mỗi thế hệ, nhưng các cơ chế của GA vẫn đang hoạt động để khám phá không gian lời giải trước khi tìm ra bước đột phá ở thế hệ cuối cùng.

4 Kết luận

Thuật toán di truyền là một phương pháp tối ưu hóa mạnh mẽ, mô phỏng quá trình tiến hóa tự nhiên để giải quyết các bài toán phức tạp mà các phương pháp truyền thống gặp khó khăn.

Sức mạnh lớn nhất của GA nằm ở khả năng khám phá một không gian lời giải rộng lớn và tránh bị "mắc kẹt" ở các giải pháp tốt nhưng chưa phải tốt nhất (cực trị cục bộ).

Về bản chất, Thuật toán Di truyền là một phương pháp tìm kiếm heuristic ngẫu nhiên (stochastic heuristic). Nó không đảm bảo sẽ tìm ra lời giải tối ưu tuyệt đối, nhưng lại cực kỳ hiệu quả trong việc tìm ra các lời giải "đủ tốt" cho những bài toán cực kỳ phức tạp trong một khoảng thời gian hợp lý.

Nhờ tính linh hoạt này, GA được ứng dụng trong rất nhiều lĩnh vực thực tế, chẳng hạn như:

• Tối ưu các hàm phức tạp, phi tuyến tính.

• Tìm kiếm kiến trúc mạng nơ-ron (Neural Network) hiệu quả.

• Huấn luyện robot thực hiện các hành động phức tạp như đi lại, nơi không có "bộ dữ liệu" chuẩn để học và robot phải tự khám phá ra chuỗi chuyển động tối ưu thông qua thử và sai.

Bằng cách học hỏi từ cơ chế thông minh nhất của tự nhiên - sự tiến hóa - thuật toán di truyền mở ra một hướng đi đầy tiềm năng để giải quyết những vấn đề hóc búa.