Những thuật toán nền tảng trong lĩnh vực Trí tuệ nhân tạo (Artificial Intelligence I)
1. BFS - Tìm kiếm theo chiều rộng
2. DFS - Tìm kiếm theo chiều sâu
3. IDDFS - Tìm kiếm theo độ sâu nhất định
5. Brute Force - Thuật toán vét cạn
6. Hill Climbing - Thuật toán leo đồi
7. Tabu Search - Thuật toán Tabu
8. Simulated Annealing - Phương pháp ủ luyện kim
9. Genetic Algorithm - Giải thuật di truyền
9. Particle Swarm - Thuật toán tối ưu bầy đàn
10. Minimax
[22:30] Xin chào, trong series này, mình sẽ tìm hiểu về Trí tuệ nhân tạo (AI) với các thuật toán cơ bản, thực ra là, mình có làm một báo cáo nghiên cứu khoa học với một nhánh nhỏ của trí tuệ nhân tạo là mạng noron tích chập CNN, nhưng vì nhiều công thức toán quá, với tại, máy mình là ubuntu, nên khi nào sang window mình sẽ post lại bài báo đó.
Trong series này, đừng kỳ vọng sẽ học được cái gì đó cao siêu như nhận diện hình ảnh (computer vision), nhận diện chuyển động với mô hình như R-CNN, Fast-CNN, hay xử lý ngôn ngữ tự nhiên NLP, đây chỉ là cái nền, một cái nền rất lớn của trí tuệ nhân tạo, có nhiều lập luận rằng đây là những kiến thức hàn lâm vô nghĩa, với những thuật toán đã 'lỗi thời', nhưng, quá trình phát triển của trí tuệ nhân tạo bắt đầu từ đây, và chúng ta cũng sẽ bắt đầu từ đây để có thể đi đến bất kỳ sự phát triển vượt bậc nào trong lĩnh vực này trong tương lnai.
Ngôn ngữ sử dụng trong chủ đề này sẽ là Java, nếu dùng python, mình có thể viết mạch lạc, dễ nhìn hơn, cũng nhanh hơn nữa, nhưng Java là một ngôn ngữ hướng đối tượng, dù không chắc mình sẽ dùng tới hướng đối tượng trong bài viết này, dù sao, đơn giản, vì mình thích Java, mình định dùng C++ để viết code cơ, nhưng thôi, Java là được rồi.
Mình cảm nhận chủ đề này nó không có gì mới quá đối với mình, các thuật toán tìm kiếm mình đều đã đọc qua, và mình từng làm một nghiên cứu khoa học về thuật toán minimax để cho ra đươc nước cờ tối ưu cho một trò chơi dân gian Việt Nam (bạn có thể xem ở github mình), nên mình muốn hoàn thành bài viết này nhanh nhất có thể.
23:11, không ngờ, sau 1 thời gian dài bỏ codeforces, giờ mình làm bài chậm vậy. nhưng dù sao cũng xong phần tìm kiếm mù.
Đầu tiên là cài đặt BFS, rất dễ dàng, mình có thể code nó từ năm lớp 12:
.Tiếp theo là cài đặt DFS theo 2 cách là dùng stack tối ưu hơn và đệ quy
DFS đơn giản hơn BFS về cách nhìn nhưng nó lại có trường hợp suy biến khi đi qua sâu vào 1 gốc mà gốc đó lại không có nghiệm, để tránh việc đó thì có thuật toán cải thiện là IDDFS, với độ sâu k, khi nó tới độ sâu k, thuật toán sẽ không đi xuống sâu hơn nữa, với bài toán bất kỳ, ban đầu ta sẽ thử cho k bằng số nhỏ, nếu không được thì tăng k cho đến khi ra tìm ra kết quả bài toán
Để làm được điều đó, ta có thể thêm một thuộc tính độ sâu vào mỗi nút trong quá trình duyệt, khi đi xuống xâu nữa thì ta tăng thuộc tính đó, như ở trên, dưới đây là 1 ứng dụng đơn giản của nó:
Thế là hết phần thuật toán tìm kiếm mù, tiếp theo là phần ứng dụng của nó, để duyệt từ đỉnh A tới đỉnh B trong 1 đồ thị thì BFS sẽ đi theo thứ tự từ điển nhỏ nhất, ở đây có hai ví dụ, ví dụ đầu tiên đã được đăng rất nhiều lần trên blog này, cách hiểu dễ nhất là DFS, trong một ma trận ta phải đi từ A đến B, vì nó dễ hình dùng, nên bạn hãy thử đọc code và hiểu, mình không giải thích đề bài:
Đừng hỏi làm sao code java lại dài nhé..
Ví dụ tiếp theo là một bài toán có tên là Triệu phú - Kẻ cướp, có 3 triệu phú và 3 kẻ cướp đứng bên 1 bờ sông, cần di chuyển sang bờ sông bên kia biết thuyền chỉ chờ được tối đa 2 người và 2 bên bờ số kẻ cướp không được lớn hơn số triệu phú, thuyền lúc nào cũng phải có người chở, chứ không tự động ..
Mình định kiếm cái ảnh chèn vào, nhưng dễ hiểu mà, thôi khỏi tìm kiếm, bao giờ mình thành thạo môn vẽ mình sẽ vẽ vào, nếu bạn chịu khó nhắc. Thôi, quay lại vấn đề bài toán, ở đây ta đặt một kiểu dữ liệu gồm 3 thành phần là (a,b,c) trong đó a là số triệu phú bên bờ đi, b là số kẻ cướp bên bờ đi, c là giá trị xác định bờ, 1 là bờ đi, 0 là bờ đến. Vậy cần tìm một phép chuyển đồi từ (3,3,1) thành (0,0,0), ở đây, mình implement nó bằng cả 2 thuật toán là BFS và DFS, nhưng về phần trình bày kết quả, mình chỉ chơi cái khó hơn là DFS thôi, còn lại, coi như là dành cho bạn, xem hai thuật toán có tìm ra các cách đi khác nhau không, dưới đây là code cả DFS, BFS và kết quả:
DFS
Kết quả nha, hay bạn thử giải bằng tay xem, bài toán này cũng hay được đưa vào đề kiểm tra IQ.
Nói chút sao ra được kết quả trên thì mình dùng một thuật toán có tên gọi là truy vết nhé, bạn có thể tìm hiểu thêm.
Tiếp tục, chúng ta sẽ đổi gió bằng việc nói đến 1 thuật toán khá hay ho, cũng có hàm đánh giá như mạng noron, đó là thuật toán A*, tên gọi của thuật toán này cũng khá kỳ cục, nó chả nói lên điều gì, ban đầu, họ đặt nó là A1, rồi cải tiền nó lên A2, thấy nó tốt nhát nên đổi tên thành A*.
Ý tưởng của thuật toán này là một thuật toán tương tự như Dijstra nhưng tổng quát hơn, nó có 1 hàm đánh giá, như sau:
+ Gọi x,y,z là quãng đường đi từ x đến z qua y.
+ Thì g(x) là đoạn xz.
+ h(x) là đoạn yz. Nhưng vì đoạn h(x) chưa biết (nếu biết thì ta đã tìm được đường tối ưu), nên ta gọi nó là hàm heuristic, hàm này thì có quá nhiều công thức định nghĩa, ví dụ bạn có thể tính khoảng cách theo tiên đề Euclid, hay cross entropy, nó được gọi là hàm đánh giá.
Quá trình tìm ra đường đi ngắn nhất thì thuật toán sẽ tối thiểu hóa hàm f(x) sau mỗi vòng lặp.
Thuật toán là thế này: ta khởi tạo một hàng đợi ưu tiên, hàng đợi này dùng để tìm ra node có giá trị hàm heuristic ở trên bé nhất đấy, mỗi lần lấy ra phần tử bé nhất, ta duyệt trên tất cả các hàng xóm (nút mà nó liền kề) của nó, nếu các hàng xóm của nó chưa có trong hàng đợi, đơn giản là ta cập nhật lại hàm f(x) của mỗi nút, rồi ném nó vào hàng đợi, còn nếu nó ở trong hàng đợi rồi ,mà hàm f(x) ta cập nhật nhỏ hơn hàm f(x) trong hàng đợi (tại sao à, hãy tưởng tượng, 1 nút thì chỉ có 1 điểm là điểm đến cuối, nhưng lại có thể đi đến từ nhiều điểm khác nhau). Thuật toán dừng khi node mà ta duyệt trùng với điểm đến mà ta mong muốn.
Chúng ta nên lưu lại quá trình, bằng cách thêm parent vào mỗi node, để in ra đường đi sau này..
Dưới đây là thuật toán:
Có 1 trang mô phỏng các thuật toán này khá hay, bạn có thể theo link tại đây
[2:50] Tiếp theo đến 1 thuật toán trong mảng brute-force, tên là hillclimping (leo đồi), thuật toán này không tìm thấy các vùng cực tiểu (hoặc cực đại) cục bộ, chỉ tìm được cực tiểu địa phương.
Ý tưởng của thuật toán rất đơn giản, xuất phát từ một vị trí bất kỳ, nếu muốn tìm giá trị nhỏ nhất thì đi ngược phía với chiều tăng, và ngược lại, thuật toán dừng khi nó thấy giá trị đổi chiều, giả sử bạn tìm min cho một hàm như dưới đây:
Mình định không code thuật toán đơn giản như thế này, nhưng thôi cứ cho vào cho nó đủ:
Trước khi bắt đầu với các thuật toán tiếp theo, thì mình muốn nói về một khái niệm tìm kiếm mới, trong các tìm kiếm trước, nó luôn tìm được kết quả bài toán tối ưu nhất, nhưng trong thực tế, bạn sẽ khó có thể tìm được nghiệm tối ưu nhất, thay vì vậy, bạn tìm một nghiệm vừa phải, chấp nhận được, cách là như thế được gọi là tối ưu heuristic và meta-heuristic.
Điểm khác nhau giữa 2 dạng tối ưu trên là heuristic thì nó tối ưu dựa vào một số đặc điểm đặc trưng cụ thể của bài toán ví dụ áp dụng trong việc tính nước đi tối ưu khi chơi cờ, còn meta-heuristic được sử dụng khi ta không thể khái quát hóa đặc trưng cụ thể, nó được ứng dụng trong các thuật toán về giải mã GEN di truyền.
Tabu Search
Chào mừng đến với thuật toán khó chịu đầu tiên mang tên là Tabu Search, thuộc nhánh meta-heuristic, khi không khái quát hóa được nội dung cụ thể của thuật toán, Fred Glover công bố nó năm 1986, nguyên tắc cơ bản của nó là tìm điểm local nhưng khi tìm thấy local nó sẽ chấp nhận 1 số điểm làm giảm độ chính xác bài toán để đi tới điểm global. Việc quay lại danh sách trước đố được ngăn chặn bởi Tabu List (Short-term memory), nó ghi lại lịch sử tìm kiếm trước đó. Đa số trường hợp người ta dùng nó để tối ưu 1 hàm toán học, nó cũng có thể để giải quyết bài toán đường đi ngắn nhất, như Traveling salesman problem.
Từ "tabu" (hoặc taboo) xuất phát từ thổ dân trên đảo Tonga Island, ngôn ngữ Polynesia, nghĩa của nó là không được chạm vào 1 cái gì đó vì nó rất thiêng liêng.
Phương pháp tabu bắt đầu tìm kiếm giải pháp ban đầu, sau đó đi tìm kiếm các giải pháp lân cận, xem cái nào tốt nhất, hãy nghĩ nó gần giống thuật toán tham lam (greedy), mô tả thuật toán:
+ Bước 1: Khởi tạo không gian giải pháp và khởi tạo giải pháp ban đầu.
+ Bước 2: Tạo ra các giải pháp lân cận từ giải pháp ban đầu.
+ Bước 3: Một hàm cost funciton để đo lường các giải pháp lân cận.
+ Bước 4: Một danh sách liên kết vòng (cycle queue) để ngăn chặn việc đi lại các giải pháp đã tìm kiếm trước đó, khám phá các không gian giải pháp chưa từng đặt chân đến.
+ Bước 5: Một nguyện vọng (aspiration criterion- hãy nhớ từ này, đây là đặc trưng của tabu search", nếu thỏa mãn thì chấp nhận giải pháp đó.
Mình sẽ ví dụ với 2 trường hợp, đầu tiên là tìm điểm tối ưu hàm toán sau:
Đầu tiên, xây dựng không gian trạng thái, xét x,y trong khoảng từ -10,10, bước nhảy 0.1, như vậy có 200*200 điểm.
Xây dựng hàm để trong mỗi vòng lặp tìm kiếm ra điểm tối ưu nhất, như hình ví dụ dưới đây, điểm đang đứng màu xanh, điểm đang xét là màu vàng (điểm lân cận điểm hiện tại):
Đọc thuật toán sau đây để hiểu:
Cuối cùng, đây là implement Tabu search:
Tiếp theo đến bài toán Traveling Sale Man, từ 1 điểm đến tất cả các điểm còn lại rồi quay về điểm ban đầu sao cho trọng lượng đường đi ngắn nhất:
Hình như hồi cấp 3 mình gọi bài toán này đường đi tìm thấy là một chu trình Halminton, bạn có thể tìm hiểu thêm.
Giả sử có 5 thành phố, đây là bản ma trận kề mối liên hệ giữa các thành phố và trọng lượng giữa chúng.
Một chu trình halminton hợp lệ:
Phần thuật toán không khác ở trên, chỉ khác phần khởi tạo, tưởng tượng mỗi một nghiệm (một đỉnh như hình vẽ minh họa tabusearch ở trên) không phải là một giá trị nữa, mà giờ là một tập đường đi như chu trình halminton ở trên, như thế chỉ cần hoán vị các phần tử là ra trường hợp mới, ví dụ, 1 giải pháp là 2→5→1→4→3→2, tabu list ở đây là một mảng trạng thái thành phó thứ i giá trị x[i], ví dụ, ban đầu, chưa xét thành phố nào thì nó là [0,0,0,0,0], hàm cost function tính gía trị các cạnh, nếu nghiệm mới không tồn tại trong tabu list cũ, thì thêm vào, ngược lại thì tiếp tục cho đến khi hết số vòng lặp.
Mình xin dừng phần tìm hiểu về TabuSearch ở đây, phần implement nó mình không thực hiện được do nó sẽ tốn rất nhiều thời gian với trình độ của mình bây giờ.
Simulated Annealing
Phương pháp ủ luyện kim có thể hiểu đơn giản cho những người không chuyên như mình là giảm dần từ nhiệt độ cao xuống nhiệt độ thấp từ từ để kim loại nóng chảy đạt được tổ chức nhất định, bền hơn.
Tương tự như TabuSearch ở trên, Simulated Annealing cũng cố gắng tìm ra điểm tối ưu toàn cục, bỏ qua điểm tối ưu cục bộ bằng cách chấp nhận một số bước "không tối ưu", bằng cách nào, bằng cách tương tự quá trình ủ luyện kim, vì sao?
Thuật toán tìm kiếm như leo đồi (hilling climping) không đảm bảo cho ta tìm được nghiệm tối ưu toàn cục, để cho nghiệm tìm được gần với tối ưu toàn cục, ta có thể áp dụng thuật toán leo đồi với các điểm lựa chọn ngẫu nhiên. Bây giờ, bây giờ, thay cho việc luôn luôn "leo lên đổi" xuất phát từ các điểm khác nhau, a thực hiên một số bước "đi xuống" nhằm thoát khỏi các điểm cực đại địa phương. Đó chính là tư tưởng của thuật toán tìm kiếm mô phỏng luyện kim.
Trong tìm kiếm mô phỏng luyện kim, ta chọn ngẫu nhiên một trạng thái v trong lân cận u (tức chọn 1 trong 1 tập trạng thái hàng xóm của u), ta sẽ tính hàm năng lượng theo một công thức nào đó, gọi là hàm mục tiêu, nếu như bài toán tối ưu hàm f(x) thì đơn giản hàm năng lượng chính là f(x), nếu f(v)>f(v) thì ta tới v, còn nếu không, ta chỉ đi tới v với 1 xác xuất nào đó. Xác xuất này phụ thuộc vào tham số nhiệt độ T. Nhiệt độ T càng cao thì bước đi tới trạng thái xấu càng có khả năng thực hiện. Trong quá trình tìm kiếm, tham số nhiệt độ T giảm dần tới 0 như trong luyện kim. Khi T gần 0, thuật toán hoạt động gần giống như leo đồi, hầu n hư ó không thực hiện bước "đi xuống". Hãy xem các ví dụ sau:
Trên đây là một ví dụ về một hàm phân phối xác xuất, giả sử tìm max của hàm dưới đây:
Ta xét trong khoảng [-2,2] với các tham số sau đây:
Dưới đây là thuật taosn Simulated Annealing
Phần chạy tìm kiếm các bạn có thể thử, sau đây mình sẽ nói một ứng dụng của nó trong 1 bài toán ở trên mình chưa hoàn thành với TabuSearch, Traverling Sale Man.
Ở bài toán này ta sẽ xây dựng trường hợp tổng quát cho nó chứ không chỉ dừng lại ở việc biết trọng số từng cạnh. Thụât toán Simulated Annealing không có gì thay đổi, khác nhau ở ý tưởng khởi tạo, ta coi 1 chuỗi thành phố theo thứ tự (giống như đã giải thích ở phần TabuSearch) là một kết quả của bài toán, mỗi lần chạy Simulated Annealing, đang ở nghiệm nào đó, ta sẽ nhảy đến 1 nghiệm ngẫu nhiên nào đó nếu nó "đủ tốt" theo hàm phân phối xác xuất ta đã đặt ra, còn nếu nó tốt hẳn, thì tất nhiên sẽ nhảy đến (trường hợp khoảng cách của nghiệm mới nhỏ hơn khoảng cách của nghiệm cũ, lưu ý là ta đang tối ưu quãng đường ngắn nhất cho "sale man".
Như vậy, để tổng quát, ta sẽ coi mỗi thành phố có 1 tọa độ nào đó (thực tế là vậy), rồi ta tính khoảng cách dựa trên tọa độ đó, dùng Euclid Distance, vì đây là mặt phẳng 2 chiều. Phần implement sẽ như ở dưới đây:
Trên đây là khởi tạo thành phố.
Repositry chính là một tập thành phố cần xét.
SingleTour chính là một tập nghiệm khả thi:
Một số tham số cho bài toán:
Thuật toán Simulated Annealing với ý tưởng cho bài Travelling Sale Man tương tự như cho tìm cực trị hàm số:
Như vậy, đã quá dễ hiểu về thuật toán này, độ chính xác của thuật toán càng tăng cao khi nhiệt độ tăng (tất nhiên), tuy nó không luôn luôn tìm được nghiệm tối ưu nhất như bactracking, nhưng ta đã đánh đổi thời gian (sự nhanh của nó) để lấy một nghiệm phù hợp, và có thể, nó rất gần với nghiệm tốt nhất, nếu không tìm được nghiệm tối ưu, hãy nghiên cứu lại 1 số tham số cho phù hợp với bài toán, cũng như lượng dữ liệu khổng lồ của bài toán, thuật toán sẽ hoạt động tốt nhất với những gì có thể.
Genetic Algorithms (Giải thuật di truyền)
Bắt đầu luôn nào! Giải thuật di truyền (Genetic Algorithm) là thuật toán bắt chước sự chọn lọc tự nhiên và di truyền, bạn có thể tìm hiểu về chọn lọc tự nhiên và di truyền ở wikipedia. Mỗi cá thể (chroniosome) có cấu trúc gen đặc rưng cho phẩm chất của cá thể đó, trong quá trình sinh sản (crossover), các cá thể con thừa hưởng các phẩm chất của cả cha và mẹ, cấu trúc gen của nó mang một phần cấu trúc gen của cha và mẹ. Ngoài ra, trong quá trình tiến hóa, có thể xảy ra hiện tượng đột biến (mutation), cấu trúc gen của cá thể con có thể chứa gen mà cả cha và mẹ đều không có.
Như vậy, quá trình tiến hóa (hay trong tin học chúng ta gọi là tìm kiếm) được diễn ra bao gồm: chọn lọc -> lai ghép -> tiến hóa, tất cả dựa trên một hàm tên là fitness function (hàm mục tiêu - hàm thích nghi).
Trong khoa học máy tính cổ điển, một cá thể có thể là 1 dãy nhị phân, dưới đây ví dụ về crossover:
Một ví dụ nữa về mutation:
Nói chung, crossover giúp đi đến điểm cực trị local, còn mutation giúp đi đến điểm cực trị global.
Không đi quá sâu vào phần trình bày, tiếp theo, hãy cùng thử áp dụng giải thuật di truyền vào 1 bài toán cụ thể: giả sử ta cần có 1 dãy kết quả cần tìm là {0,1,2,3,4,5,6,8,9}, dễ thấy, nó gồm 10 phần tử, ta cần tìm xem thuật toán mất bao nhiêu bước để tìm ra được dãy số đó, với hàm fitness function là sự tương đồng giữa dãy số mới và dãy số cần tìm. Mình sẽ giải thích các thuật ngữ chuyên ngành ở trong phần code.
Đoạn code dưới đây là phần khai báo tham số, SOLUTIOON_SEQUENCE là mục tiêu cần đến của bài toán, CROSSOVER_RATE là xác xuất lai ghép, MUTATION_RATE là xác xuất đột biến, TOURNAMENT_SIZE là số phần tử được chộn để xem xét trong 1 tập phần tử (population).
Cứ bình tĩnh, nếu bạn chưa hiểu gì.
Đây là 1 lớp mà cứ hiểu đơn giản là 1 cá thể, hay individual, (chromosome trong thuật toán này), nó có nhiệm vụ khởi tạo ban đầu 1 individual ở đây là 1 chuỗi giá trị dài 10 ký tự, như lấy giá trị hàm mục tiêu (fitness function), thay đổi một phần trong chuỗi, lấy gia từng giá trị trong chuỗi.
Lớp population giống như 1 tập hợp các cá thể, ta sẽ chọn 1 số cá thể giựa trên lớp này.
Còn dưới đây là trọng tâm của bài toán, thuật toán di truyền (genetic algorithm):
Mình sẽ giải thích kĩ hơn về từng hàm trong lớp này, đầu tiên là evolvePopulation, đúng như tên gọi, nó là hàm tiến hóa, hàm quan trọng nhất của bài toán, bao gồm 2 toán tử con là crossover và muations, nó trả về một tập cá thể mới.
Như vậy, ta cần xây dựng hàm crossover và mutate với xác xuất đã được định nghĩa ở trên, ví dụ, vì crossover là sản phẩm của hai parent, nên nó (child) được tạo nên từ việc lấy xác xuất xem nên lấy từ ai, còn mutate, ta sẽ dùng cái child vừa rồi, lấy xác xuất đột biến ngẫu nhiên, giúp nó linh hoạt hơn.
Hàm randomSelection, lấy ngẫu nhiên TOURNAMENT_SIZE phần tử và chọn ra phần tử tốt nhất để trả về, như vậy, hàm này có nhiệm vụ ta sẽ chọn ra hai cá thể ưu tú nhất ngẫu nhiên, tiến hành lai ghép như ở trên.
Cuối cùng, sẽ là phần triển khai thuật toán, ta sẽ tìm kiếm, liên tục tiến hóa cho đến khi tìm thấy đáp án đề bài, tức là khi đó hàm mục tiêu sẽ bằng với MAX_FITNESS=10, còn không, ta liên tục tiến hóa quần thể population.
Thuật toán sẽ hội tụ sau khoảng vài trăm vòng lặp, nhanh hơn rất nhiều nếu bạn dùng tổ hợp để chạy brute-force thì nó có thể lên đến 1 tỷ vòng lặp.
Để cho mọi việc bớt bỡ ngỡ, mình sẽ trình bày 1 vài ứng dụng của nó tiếp theo, như là tìm cực trị 1 hàm số, hay bài toán knapsack quen thuộc đã được giải bằng phương pháp Quy hoạch động vô cùng tốn kém về bộ nhớ trên blog này.
Đầu tiên là tìm cực trị của hàm số này, min, max tùy bạn:
Thực ra mọi chuyện khá là tuông tự, cái ta cần thay đổi là hàm mục tiêu và khởi tạo (như bao thuật toán Trí tuệ nhân tạo khác).
Trong lớp individual, ta định nghĩa lại hàm mục tiêu, nên nhớ, máy tính hoạt động không liên tục trên hệ nhị phân, nên ta cần chuyển hệ cơ số 10 (base) về hệ nhị phân để tìm kiếm đáp án.
Chúng ta không thể biết thuật toán sẽ hội tụ khi nào, nên cần 1 điểm để dừng lại, ở đây đơn giản là khi chạy bao nhiêu vòng lặp đã được định nghĩa sẵn SIMULATION_LENGTH.
Pingo, hãy chạy thử thuật toán xem, fullcode ở trong repository github của mình nhé.
Phần tiếp theo, sẽ là bài toán KnapSack, đây là một bài toán kinh điển, mình sẽ không viết nội dung bài toán ở đây, bạn có thể tìm trên blog, mình đã giải rất nhiều bằng phương pháp quy hoạch động, nó luôn tìm được nghiệm tối ưu.
Ta có thể coi tổng quát hóa bài toán KnapSach dưới dạng thuật toán meta-heuristic.
Gọi $x_i$ là toán tử có cho món đồ thứ i vào túi hay không (0-1), $v_i$ là giá trị của món đồ thứ i, $w_i$ là trọng lượng món đồ thứ i, M là tổng trọng lượng túi tối đa có thể mang được, hàm mục tiêu (fitness function) của bài toán sẽ như sau:
Đã có hàm mục tiêu, tiếp theo chỉ cần khởi tạo bài toán theo giải thuật di truyền.
Mỗi 1 individual hay chromosome là 1 trạng thái của phương trình trên, ví dụ: chọn [1,0,0,0,1] tức chỉ chọn túi thứ 1 và thứ 5, như vậy, ta đã giải quyết xong không gian đầy đủa của bài toán.
Hàm fitness được viết lại như trên, tại sao khi không thỏa mãn lại trả về âm vô cùng ? Đơn giản, ta phạt một giá trị không thỏa mãn (penaty), các cấu trúc còn lại của thuật toán không thay đổi nhiều, xin phép không trình bày lại, dưới đây là hàm main để test thử thuật toán:
Thuật toán hoạt động tốt với độ phức tạp tuyến tính phụ thuộc vào tham số, không còn độ phức tạp hàm mũ như các phương pháp brute-force hay dynamid programming.
Particle Swarm (Thuật toán tối ưu bầy đàn)
Thuật toán tối ưu bầy đàn là thuật toán cuối cùng mình nghiên cứu trong nhánh meta-heuristic, và đối với mình, nó là thuật toán khó nhất, có lẽ tại mình đang khá là buồn ngủ, đợi chút, mình sẽ đeo tai nghe cho nó đỡ nản.
Có thể hiểu thuật toán là kết luận của việc một đàn kiến kém thông minh kết hợp lại lại cho ra một tập thể thông minh trong tìm kiếm thứ ăn, hay bạn có thể tìm hiểu về Game of life, nói tóm lại, Particle Swarm Optimization tạo ra một tập hợp gồm n phần tử, mỗi phần tử di chuyển và tiến hóa theo mỗi bước để rồi cuối cùng hội tụ tại điểm tối ưu. Ban đầu, các phần tử đuọc gán với vị trí và vận tốc di chuyển ngẫu nhiên. Sau đó tại mỗi bước, mỗi phần tử cập nhật vị trí tốt nhất của nó, $p_{i,d}$ và vị trí tốt nhát của cả đàn, $g_d. $
Hãy hiểu là có 1 tập phần tử từ i=1...S, với mỗi phần tử sẽ có rấ nhiều chiều (ví dụ nếu là tối ưu một hàm số thì sẽ có 2 chiều) d=1...n, công thức của vận tốc và cập nhật lại $x_i$ sẽ là:
Bạn sẽ là bình thường nếu choáng với công thức và đống tham số trên, nhưng phân tích ra, nó cũng không có gì phức tạp, chia làm 3 phần, phần đầu tiên w gọi là inerita weight, một tham số quán tính, nó càng lớn thì phương trình càng phụ thuộc vào nghiệm toàn cục, nó càng bé phương trình càng phụ thuộc vào nghiệm cục bộ, cái thứ 2 là cục bộ, cái thứ 3 là toàn cục, tham số c1,c2 ban đầu được khởi tạo như nhau.
Có thể hiểu w là hệ số giảm vận tốc, c1 là hằng số đặc rưng cho yếu tố cá thể, c2 là hằng số đặng trưng cho yếu tố bầy đàn, $r_p$ và $r_g$ là hai biến ngaãu nhiên phân phối đều trong khoảng [0,1], hai phương trình trên sẽ di chuyển ngẫu nhiên nhưng có khuynh hướng tiến về vị trí tốt nhất của cả đàn và vị trí tốt nhất mà nó đã đi qua. Tương quan giữa yếu tố bầy đàn và yếu tố cá thể được thể hiện thông qua hệ số c1 và c2.
Sau đây sẽ là ví dụ tìm cưc trị hàm: $f(x) = e^{x^2+y^2}$
Khởi tạo tham số như trên. Mỗi một cá thể sẽ được định nghía như sau:
Hàm setBestPosition(position) sẽ hoạt động nếu cá thể là một bestPosition (cứ từ từ, ở dưới sẽ hiểu).
Hàm checkBestPosition cập nhật lại globalBestSolution nếu có thể.
Trên đây là lớp tối ưu bầy đàn chính, NUM_PARTICALS là số cá thể, khởi tạo ban đầu, cập nhật lại globalBestSolution bằng tham chiếu theo hàm checkBestPosition ở trên, sau đó vào vòng while, chạy 1000 vòng lặp, sau này, ta sẽ gọi mỗi lần chạy là 1 epochs.
Trong 1 epochs ta sẽ duyệt tất cả các cá thể, đầu tiên, tính giá trị $v_i$ như theo công thức ở trên cho tẩt cả các chiểu của cá thể.
Vòng lặp tiếp theo cập nhật lại vị trí di chuyển cho cá thể theo các chiều có thể, chú ý, vì phạm vi di chuyển có biên nên ta càn kiểm tra điều kiện cá thể có di chuyển về biên hay không.
Tiếp theo kiểm tra nếu vị trí mới tốt hơn vị trí cũ thì cập nhật lại vị trí tốt nhất cho cá thê đó (setBestPosition).
Nếu vị trí tốt nhất cho cá thể đó lại tốt hơn cả vị trí global tốt nhất, tất nhiên là cập nhật lại global rồi.
Tổng kết lại, thuật toán gồm bước, khởi tạo 1 tập hợp các cá thể ngẫu nhiên, khởi tạo globalBestSolution của các cá thể đó (chính là vị trí cá thể tốt nhất), sau đó tính vận tốc để cập nhật lại vị trí từng cá thể theo các chiều có thể, nếu vị trí mới tốt hơn thì cập nhật lại biến lưu giá trị tốt nhất, nếu biến lưu giá trị tốt nhất của cá thể đấy hiện tại còn tốt hơn biến globalBestSolution thì cập nhật lại globalBestSolution, sau >100 vòng lặp, sẽ tìm được một kết quả chấp nhận được của bài toán.
Mình xin kết thúc nhánh thuật toán về meta-heuristic ở đây.
Game tree and Minimax
Thuật toán minimax là thuật toán tối thiểu hóa rủi do cho tình huống rủi do tôí đa, trong lý thuyết trò chơi, thuật toán giả sử 2 người chơi đều chơi hết mình, max- tối đa hóa khả năng chiến thắng của bản thân, min - tối thiểu hóa khả năng chiến thắng của đối thủ.
Quá trình tìm ra nước đi tối ưu của thuật toán là: đầu tiên, tạo cây trò chơi, sau đó duyệt ngược (bằng đệ quy) từ nốt cuối lên nốt gốc để tìm ra nước đi tối ưu. Với node là trạng thái trò chơi, các cạnh của mõi tầng đại diện cho lượt chơi của người hay máy tính, ví dụ hình trên có 3 tầng cạnh, tầng 1 lượt đi của máy tính (tối đa), tầng 2, lượt đi của đối thủ (tối thiểu),.v..v
Như vậy, có thể thấy, ở hàng 2 (lượt đi của đối thủ) đã có dự đoán bằng hàm đánh giá và minimax, căn cứ vào đấy, chỉ cần lấy trạng thái xấu nhất có thể cho đối thủ, tức cột 2 hàng 2, đó là nước đi tối ưu cho máy tính.
Minimax có 1 điểm yếu là không gian trò chơi tùy thuộc vào độ sâu, ví dụ DeepBlue có độ sâu 12, (5 nước đầu tiên của cờ vua đã là 318 tỉ cách). Vì thế cần áp dụng thêm bẻ nhánh alpha-beta.
Tư tưởng của cắt bỏ nhánh alpha-beta là một trạng thái tồi rồi thì không cần tìm thêm một trạng thái tồi hơn nữa, để hiểu rõ điều này hoạt động như thế nào, ta cần biết về quá trình xây dựng cây dồ thị dựa vào DFS của trò chơi.
Quấ trình đi của thuật toán sẽ theo thứ tự trên, ban đầu khởi tạo beta là dương vô cùng để khi ở hàng max (hàng cần tối đa), nó có nhiệm vụ tìm min của beta, khởi tạo alpha là dương vô cùng, để khi ở hàng min, nó có nhiệm vụ tối đa hàm max, nói tóm lại, alpha cập nhật khi có nút lớn hơn nó, beta cập nhật khi có nút nhỏ hơn nó.
Thuật toán cập nhật alpha-beta theo đường đi của cây tìm kiếm DFS, khi alpha > beta, nó sẽ tiến hành cắt bỏ nhánh không duyệt tiếp nhánh đấy nữa.
Để giải thích điều này, cần hiểu ở 2 trường hợp, đang ở hàng min hay hàng max, nhưng trước tiên, cần lý giải về cập nhật alpha beta như sau: ban đầu ở 1 (alpha âm vô cùng, - âm vô cùng), sang tầng 2 và 3,4 vẫn vậy, đến 5, bắt đầu có giá trị (vì đạt độ sâu và đó là tính chất của đệ quy), ta có 2 giá trị của nhánh 4 và 5 lần lượt là 5 và 6, vì trên đó (hàng 4) là nhánh max, nên ta có thể cập nhật beta (5 nhỏ hơn dương vô cùng) là 5, sau đó đi tiếp lên trên, ta cập nhật lại alpha là 5 (vì đang ở hàng min) và beta cho về dương vô cùng, đi tiếp sang trái theo tính chất duyệt, alpha và beta vẫn như cũ, ta thấy nhánh ở dưới có node trái là 4, ta cập nhật lại beta đang là dương vô cùng thành 4, vì alpha lớn hơn gamma, ta bỏ không cần duyệt tiếp nhánh bên phải (sẽ giải thích ở dưới), quá trình tiếp tục như vậy.
Trường hợp đầu tiên, ta đang ở hàng max (hàng số 4 theo hình vẽ), khi beta nhỏ lơn gamma, ta đang ở hàng max, tức là hàng trên đó là hàng min, giá trị của beta là do tầng dưới nó đẩy lên, dù hàng bên cạnh beta có lớn hơn hay nhỏ hơn beta, thì hàng trên nó (hàng 3) vẫn chọn alpha là trạng thái tiếp theo (vì beta nhỏ hơn alpha mà hàng max cần tối đa mà). Hãy suy nghĩ thật kỹ điều này.
Trường hợp số 2, hãy để ý nhánh số 9, sau 1 hồi cập nhật thì alpha=8 và beta=5, đang ở tầng 3- hàng max, như vậy hàng trên nó là hàng min, dù thế nào, hàng trên nó sẽ luôn lấy beta để so sánh, chứ không lấy alpha, mà alpha được tạo thành từ các nhánh dưới, như vậy, không cần đi sâu vào nhánh này, vì nó không bao giờ ảnh hưởng đến kết quả dù node đó có thấp hay cao.
Nhận xét
Đăng nhận xét