AI Cho Mọi Người

AI Cho Mọi Người

Random search

 

 

 

Phương pháp phổ biến và khoa học nhất để tìm giá trị min/max cho một hàm số là dựa vào đạo hàm trong quá trình tìm kiếm. Chúng ta sẽ làm việc với các phướng pháp dựa vào đạo hàm ở phần sau của khóa học khi học tới các thuật toán dựa vào training. Tìm giá trị tối ưu dựa vào đạo hàm đòi hỏi hàm số phải liên tục và tính được đạo hàm tại mọi điểm. Tuy nhiên, rất nhiều mô hình cho các bài toán trong thực tế không thỏa mãn yêu cầu này. Trong những trường hợp này, chúng ta không thể dùng các phương pháp tối ưu dựa vào đạo hàm được.

Ví dụ xét bài toán sau, cho một tập hợp các phần tử, mỗi phần tử có trọng lượng và giá trị. Bài toán yêu cầu chọn ra một nhóm các phần tử sao cho tổng trọng lượng ở mức cho phép và tổng giá trị của các phần tử đó là cao nhất có thể.

Dạng bài toán như thế này rất phổ biến trong thực tế và các phương pháp dựa vào đạo hàm dường như không khả thi để giải quyết chúng. Bây giờ, để minh họa ý tưởng cho việc giải quyết một bài toán dùng giải thuật di truyền (GA) một cách dễ hiểu, chúng ta sẽ dùng bài toán one-max để minh họa các hoạt động bên trong của GA.

Bài toán one-max phát biểu như sau: Cho vector v có chiều dài n và mỗi phần từ nhận giá trị 0 hoặc 1, score s (hay fitness) của một vector bằng tổng giá trị các phần tử của vector đó \(s = \sum_i v_i\). Nói cách khác, score của một vector chính là tổng số lượng phần tử có giá trị là một. Hãy viết chương trình tìm giá trị max mà score có thể đạt được.

Chúng ta có thể nhận ra một cách dễ dàng được là score lớn nhất có thể đạt được là khi vector v chứa n phần tử có giá trị 1. Vậy viết chương trình tìm chi nữa vậy?

Các bạn có thể xem bài toán này giống như một bộ test để kiểm tra khả năng của một thuật toán optimization. Chúng ta biết kết quả tối ưu và so sánh với kết quả của một thuật toán đang xét. Trong thực tế và trong nghiên cứu, khi chúng ta đề xuất ra một thuật toán mới, chúng ta phải chạy kết quả và so sánh với các thuật toán khác dùng rất nhiều bộ test (hay hàm test) khác nhau.

Bây giờ chúng ta sẽ đi vào thiết kế thuật toán giải cho bài toán one-max. Bài toán được phát biểu lại cho phù hợp với ngữ cảnh như sau: Cho hàm secret() với đầu vào là một vector v. Vector v có chiều dài n = 10 và nhận giá trị binary. Chúng ta không biết nội dung của hàm secret() mà chỉ biết output của hàm này là giá trị score cho vector đầu vào.

Tìm kiếm dùng random search (RS)

Cách đơn giản nhất để tìm kiếm vector v  là sinh ra m vector v khác nhau, trong đó m là số hữu hạn do thực tế tài nguyên máy tính là hữu hạn. Ở ví dụ này, giả sử cho m = 8.

Source code sinh ra m vector có giá trị ngẫu nhiên và có độ dài n.

Kết quả sinh ra ngẫu nhiên m vector như sau

Random search cho ra kết quả ngẫu nhiên và chúng ta sẽ có những kết quả khác nhau cho mỗi lần chạy. Trong trường hợp này, giá trị score tốt nhất đạt được là 6.

Để hiểu hơn về random search, chúng ta cùng quan sát hình sau

Chúng ta hãy tưởng tượng đây là không gian tìm kiếm. Trong không gian này, chỉ có duy nhất một ví trị cho kết quả tối ưu. Việc sinh ra ngẫu nhiên 8 vector để tìm vị trí tối ưu có thể mình họa như sau

Rõ ràng, không gian tìm kiếm quá lớn so với việc dùng 8 điểm (vector) để tìm vị trí tối ưu. Nếu tài nguyên bộ nhớ và khả năng/tốc độ tính toán là vô tận thì mọi việc đơn giản hơn rất nhiều. Chúng ta chỉ việc tăng m lên là có thể cải thiện độ chính xác. Tuy nhiên, điều giả sử này hiện nay là vô lý, không thực tế.

Một cách làm bắt chước theo ý tưởng trên mà không vi phạm ràng buộc về giới hạn của tài nguyên. Đó là lặp lại việc sinh ra m vector ngẫu nhiên. Nói một cách chi tiết hơn, các nhóm m vector sẽ được lần lượt sinh ra; và trong quá trình này, vector tốt nhất (tính tới thời điểm hiện tại) được lưu và truyền cho lần lặp tiếp theo.

Hình sau mô tả các vector được sinh ra cho 10 lần lặp. Giá trị score tốt nhất được lưu lại qua các lần lặp. (Nếu hình dưới không chạy bạn nhấn Ctrl+F5 để reload nhé)

Hình sau miêu tả quá trình tìm kiếm của các vector qua các lần lặp.

Chúng ta thấy độ chính xác có cải thiện một ít, nhưng RS hoạt động không ổn định. Có một số điểm cần thảo luận khi quan sát hành vi của phương pháp RS

1) Những vector sinh ra giữa các lần lặp độc lập nhau. Nói cách khác, không có sự kế thừa thông tin từ của lần lặp (t-1) cho lần lặp thứ t. Các vector sinh ra ở lần lặp hiện tại đều được sinh ra mới hoàn toàn và không dùng lại giá trị nào của các vector ở lần lặp trước.

2) Các vector chưa tương tác với nhau. Một vector có thể chứa thông tin mà vector khác không có hay đang cần.

Bài tập: Các bạn tự suy nghĩ các cách để nâng cao phương pháp RS và giải quyết được (1) và (2). Bạn nào nghĩ ra được phương pháp gì thì comment trên post tuần 4 để mọi người cùng thảo luận nhé. Idea gì cũng được; không quan trọng đúng hay sai đâu.