NEAT (NeuroEvolution of Augmenting Topologies)- Nhiệm vụ hạ cánh tàu vũ trụ

Để hiểu bài viết này, các bạn cần phải có một số kiến thức nền tảng:

• Thuật giải di truyền Genetic Programming

• Mạng Artificial Neural Network - đặc biệt là thuật toán Lan truyền tới (Feed Forward)

Ý tưởng của NEAT là gì?

Việc thiết kế cấu trúc (topology) tối ưu cho một mạng neuron – bao gồm số lượng lớp ẩn, số neuron trong mỗi lớp và cách chúng kết nối với nhau – thường là một quá trình thử sai tốn kém và đòi hỏi nhiều kinh nghiệm. Đặc biệt đối với các bài toán điều khiển phức tạp, cấu trúc mạng phù hợp có thể không hề rõ ràng. Thay vì yêu cầu con người thiết kế cấu trúc mạng trước, NEAT sử dụng một phương pháp lấy cảm hứng từ quá trình tiến hóa sinh học để tự động tìm ra cả cấu trúc mạng lẫn các trọng số kết nối phù hợp nhất cho bài toán.

NEAT kết hợp hai ý tưởng chính dựa trên Genetic Programming:

1. NeuroEvolution (Tiến hóa Thần kinh): Đầu tiên ta sinh ra một quần thể gồm nhiều các thể. Mỗi cá thể lại mang một bộ gene (genome), thực chất là một mạng neuron. Áp dụng các nguyên lý của thuật giải di truyền (như chọn lọc tự nhiên, đột biến, lai ghép) để cải thiện một quần thể các mạng nơ-ron qua nhiều thế hệ.

2. Augmenting Topologies (Tăng cường Cấu trúc): Bắt đầu với các mạng neuron có cấu trúc rất đơn giản (thường chỉ có kết nối trực tiếp từ đầu vào đến đầu ra) và dần dần thêm sự phức tạp (nơ-ron ẩn và kết nối mới) vào mạng thông qua các đột biến cấu trúc trong quá trình tiến hóa. Các cá thể mạnh khỏe hơn sẽ được

Ý tưởng đơn giản là như vậy. Chúng ta tìm hiểu tiếp xem làm cách nào để đưa bài toán về dạng Genetic Programming

Các thành phần bài toán

Các thành phần cốt lõi của NEAT bao gồm:

• Genome (Bộ gen): Mỗi mạng nơ-ron trong quần thể được mã hóa dưới dạng một bộ gen. Bộ gen này chứa danh sách các "gen" đại diện cho các neuron (nodes) và các kết nối (connections) cùng với trọng số của chúng (gần như là một mô tả về cấu trúc đồ thị graph). Điểm đặc biệt là mỗi gen kết nối mới được gán một "số đổi mới" (innovation number) duy nhất, đánh dấu lịch sử nguồn gốc của nó, con số này dùng để căn chỉnh và so sánh cấu trúc của hai bộ gen khác nhau rồi từ đó để phân loài (Speciation) sau này.

• Population (Quần thể): Một tập hợp các bộ gen (đại diện cho các mạng nơ-ron khác nhau) cùng cạnh tranh và tiến hóa.

• Fitness Function (Hàm thích nghi): Đây là "thước đo thành công". Hàm này đánh giá xem mỗi mạng nơ-ron (genome) trong quần thể thực hiện nhiệm vụ tốt đến mức nào. Điểm fitness càng cao, khả năng cá thể đó được chọn để sinh sản càng lớn. Việc thiết kế hàm fitness phù hợp là cực kỳ quan trọng.

• Mutation (Đột biến): Thay đổi ngẫu nhiên bộ gen. NEAT có hai loại đột biến chính:

  • Đột biến trọng số (Phenotype mutation): Thay đổi nhẹ giá trị trọng số của các kết nối hiện có.

  • Đột biến cấu trúc (Genotype mutation): Đây là điểm mấu chốt! NEAT có thể thêm một nơ-ron mới (bằng cách chia một kết nối hiện có) hoặc thêm một kết nối mới giữa hai nơ-ron chưa được kết nối. Chính nhờ đột biến này mà mạng có thể tăng dần độ phức tạp.

• Crossover (Lai ghép): Kết hợp bộ gen của hai cá thể cha mẹ để tạo ra con cái. Nhờ các số đổi mới, NEAT có thể lai ghép hiệu quả ngay cả khi hai mạng cha mẹ có cấu trúc khác nhau bằng cách căn chỉnh các gen có cùng nguồn gốc lịch sử.

• Speciation (Phân loài): Chia quần thể thành các "loài" dựa trên sự tương đồng về cấu trúc gen. Điều này rất quan trọng vì nó bảo vệ các đột biến cấu trúc mới lạ. Một cấu trúc mạng mới có thể ban đầu hoạt động chưa tốt, nhưng nếu được bảo vệ trong loài của nó, nó có thời gian để tối ưu hóa trọng số trước khi phải cạnh tranh trực tiếp với các cấu trúc phức tạp và đã tối ưu hóa khác. Việc chia sẻ fitness thường diễn ra trong phạm vi loài.

• Selection (Chọn lọc): Các cá thể có fitness cao hơn (thường là trong cùng một loài) có nhiều khả năng được chọn làm cha mẹ cho thế hệ tiếp theo. Các cá thể yếu kém sẽ dần bị loại bỏ.

Qua nhiều thế hệ, quần thể mạng neuron sẽ tiến hóa, các cấu trúc mạng ngày càng phức tạp và phù hợp hơn với bài toán sẽ xuất hiện và chiếm ưu thế.

Ví dụ thực tiễn - Hạ cánh tàu vũ trụ

Bài toán: Mục tiêu là điều khiển một tàu vũ trụ hạ cánh nhẹ nhàng và chính xác vào một vùng đáp được chỉ định trên bề mặt hành tinh. Tàu chịu tác động của trọng lực, gió ngang ngẫu nhiên và có 3 loại động cơ tạo ra lực đẩy: lên, trái, phải. Hạ cánh thành công yêu cầu đáp đúng vùng, với vận tốc tiếp đất (ngang và dọc) đủ nhỏ.

Áp dụng NEAT:

• Inputs (Đầu vào cho mạng nơ-ron): Tàu cần "biết" những gì để ra quyết định? Chúng ta cung cấp cho mạng các thông tin trạng thái quan trọng, đã được chuẩn hóa:

  • Tọa độ hiện tại \(x,y\)

  • Vận tốc hiện tại \(v_x, v_y\)

  • Khoảng cách \(d_1, d_2\) từ vị trí \(x\) đến hai biên của vùng đáp

• Outputs (Đầu ra của mạng nơ-ron): Tàu có thể "làm" gì? Mạng có 3 nơ-ron đầu ra, tương ứng với 3 hành động:

  • Bật động cơ chính (Thrust Up)

  • Bật động cơ đẩy trái (Thrust Left)

  • Bật động cơ đẩy phải (Thrust Right)

  • Tại mỗi bước, hành động có giá trị đầu ra cao nhất sẽ được thực hiện (nếu vượt một ngưỡng nhất định).

• Fitness Function (Đánh giá "phi công" AI): Đây là linh hồn của việc huấn luyện. Chúng ta định nghĩa điểm số dựa trên kết quả của mỗi lần hạ cánh thử. Điểm số này sẽ được tính toán sau mỗi lượt huấn luyện kết thúc, và được tính như sau:

  • Hạ cánh thành công:

    • Thưởng lớn

    • Thưởng thêm nếu hạ cánh nhanh

    • Thưởng thêm nếu dùng ít nhiên liệu

  • Hạ cánh thất bại:

    • Bay chạm màn hình thì sẽ phạt rất nặng

    • Tàu hạ cánh không đúng nơi quy định hoặc với vận tốc không an toàn:

      • Phạt tăng khi khoảng cách hạ cánh xa với nơi quy định, càng xa phạt càng nặng

      • Phạt tăng thêm khi vận tốc vượt ngưỡng an toàn, càng lớn phạt càng nặng

• Quá trình Tiến hóa:

  • Khởi tạo quần thể các mạng nơ-ron đơn giản.

  • Trong mỗi thế hệ:

    • Mỗi mạng nơ-ron (genome) điều khiển một chiếc lander trong môi trường mô phỏng. Nghĩa là, tại mỗi render frame trong graphic loop, các thông số hiện tại bao gồm \(x,y,v_x,v_y,d_1, d_2\) sẽ được feed vào mạng neuron của cá thể đó để ra quyết định sẽ làm hành động nào.

    • Chạy mô phỏng cho đến khi lander hạ cánh, rơi, hoặc hết giờ.

    • Tính điểm fitness cho mỗi lander dựa trên kết quả và các tiêu chí thưởng/phạt.

    • Phân loài các genome dựa trên sự tương đồng cấu trúc.

    • Chọn lọc các cá thể tốt nhất trong mỗi loài.

    • Tạo thế hệ mới bằng cách lai ghép và đột biến (cả trọng số và cấu trúc).

  • Lặp lại qua nhiều thế hệ để tìm cá thể tốt nhất

Demo