Trí tuệ bầy đàn: Đánh giá thành công, học hỏi và tối ưu hóa mã (Phần 2)

Từ triết lý ra quyết định trong điều kiện không chắc chắn đến Hệ thống kiến Max-Min và tăng tốc thực thi bằng cách sử dụng Danh sách ứng cử viên hạn chế (Restricted Candidate Lists). Möbius Strip II (1963) của M.C. Escher. Ảnh: Escher in Het Paleis. Trong Phần 1 của loạt bài này, chúng tôi đã chuyển đổi kỳ quan sinh học của stigmergy thành một khuôn khổ toán học cho Bài toán đóng gói thùng (BPP). Chúng tôi đã chuyển đổi mô hình Tối ưu hóa đàn kiến (ACO) từ định tuyến sang nhóm, và chúng tôi đã xây dựng cấu trúc Python cốt lõi cho phép các con kiến ảo của chúng tôi xây dựng các giải pháp xác suất. Nhưng chúng tôi đã bỏ ngỏ hai câu hỏi lớn: Làm thế nào để chúng ta định nghĩa toán học một giải pháp “tốt”? Và làm thế nào để chúng ta ngăn chặn công cụ xác suất mất hàng giờ để chạy? Trong phần thứ hai và cuối cùng này, chúng tôi sẽ khám phá sự thiên vị triết học ẩn chứa trong các hàm mất mát, triển khai cơ chế học tập của đàn kiến và giới thiệu một tối ưu hóa tốc độ thông minh được mượn từ siêu thuật toán GRASP để làm cho mã Python của chúng tôi chạy cực nhanh. Thiên vị của số liệu: Một quyết định “tốt” là gì? Trước khi đàn kiến có thể học, nó cần một số liệu để đánh giá sự thành công. Trong học máy và tối ưu hóa, hàm mục tiêu (hoặc hàm mất mát) thường được coi là một sự thật lạnh lùng, khách quan. Trên thực tế, nó là một biểu hiện toán học của những thành kiến của chúng ta. Hãy nghĩ về việc ra quyết định của con người trong điều kiện không chắc chắn. Khi bạn đánh giá một lựa chọn nghề nghiệp hoặc một chiến lược đầu tư, số liệu bạn chọn để tối đa hóa (ví dụ: thời gian rảnh, tổng tài sản hoặc sự ổn định) sẽ thay đổi hoàn toàn con đường bạn đi. Thế giới không thay đổi, nhưng thuật toán của bạn để điều hướng nó thì có. Nếu không có la bàn phù hợp, chúng ta có nguy cơ hành quân như những con kiến bị mắc kẹt trong một vòng lặp vô hạn, nghịch lý – lặp đi lặp lại vô tận trong một không gian tìm kiếm NP-hard, thực hiện các bước cục bộ có vẻ hoàn toàn hợp lý, nhưng không bao giờ thoát khỏi chu kỳ để tìm ra tối ưu toàn cục. Trong Bài toán đóng gói thùng, một số liệu ngây thơ để đánh giá sự thành công sẽ chỉ đơn giản là đếm tổng số thùng được sử dụng (N). Càng ít thùng, càng tốt. Tuy nhiên, số liệu này là phẳng; nó không cung cấp cho các con kiến bất kỳ gradient nào để học hỏi nếu nhiều giải pháp sử dụng cùng một số thùng nhưng có sự phân bố nội bộ khác nhau. Để hướng dẫn đàn kiến một cách hiệu quả, chúng tôi sử dụng hàm thích nghi được đề xuất bởi Falkenauer và Dechembre [1]: Trong đó N là số thùng, F_i là tổng trọng lượng của các vật phẩm bên trong thùng i, và c là tổng dung lượng. Sự tài tình của hàm này nằm ở tham số k, mà các tác giả đã tối ưu hóa ở k=2. Bằng cách bình phương tỷ lệ sử dụng, hàm này hoạt động như một sự thiên vị nghiêm trọng: nó thưởng lớn cho các thùng được lấp đầy đến miệng và phạt theo cấp số nhân cho không gian bị lãng phí. Các con kiến không còn chỉ cố gắng sử dụng ít hộp hơn; chúng đang tích cực theo đuổi việc nén chặt hoàn hảo. def fitness(solution, capacity): total_sum = 0 for current_bin in solution: # Tính tổng trọng lượng trong thùng hiện tại và tính bình phương tỷ lệ sử dụng của nó utilization = (sum(current_bin) / capacity)**2 total_sum += utilization # Trả về mức sử dụng trung bình trên tất cả các thùng đã sử dụng eval_score = total_sum / len(solution) return eval_score Thiết lập giai đoạn: Khởi tạo ma trận pheromone Trước khi các con kiến có thể học từ hàm thích nghi, chúng cần một “tấm vải” trống. Trong việc điều chỉnh BPP của chúng tôi, ma trận pheromone τ(i, j) mã hóa mối quan hệ giữa các kích thước vật phẩm. Do đó, bước đầu tiên là trích xuất tất cả các trọng lượng vật phẩm duy nhất từ tập dữ liệu của chúng tôi và sắp xếp chúng theo thứ tự giảm dần để xây dựng các trục của ma trận của chúng tôi. Hơn nữa, ma trận không thể được khởi tạo bằng số không, vì điều này sẽ sẽ phá vỡ các tính toán xác suất trong thế hệ đầu tiên. Đối với thuật toán ACO tiêu chuẩn không có tìm kiếm cục bộ, giá trị pheromone khởi tạo tối ưu T(0) tỷ lệ nghịch với tốc độ bay hơi ρ, được định nghĩa là: Dưới đây là triển khai bằng Python cho giai đoạn tiền xử lý và khởi tạo này: ```python import numpy as np ``` def generate_unique_weights_list(item_weights): # Sắp xếp trọng số giảm dần và loại bỏ các giá trị trùng lặp để tạo các trục ma trận sorted_weights = sorted(item_weights, reverse=True) unique_weights = [] seen = set() for weight in sorted_weights: if weight not in seen: unique_weights.append(weight) seen.add(weight) return unique_weights def initialize_pheromone_matrix(unique_weights, rho): n = len(unique_weights) # Khởi tạo ma trận N x N với giá trị T(0) tối ưu initial_value = 1 / (1 - rho) return np.ones((n, n)) * initial_value Cách đàn kiến học: Hệ thống kiến tối đa-tối thiểu (MMAS) Nếu mỗi con kiến trong một đàn hàng trăm con đều để lại một vệt pheromone sau mỗi thế hệ, ma trận bộ nhớ chung sẽ nhanh chóng trở thành nhiễu. Để giải quyết vấn đề này, Levine (2004) [3] đã chứng minh rằng Hệ thống kiến tối đa-tối thiểu (MMAS) của Stützle và Hoos [2] mang lại kết quả xuất sắc cho bài toán đóng gói thùng (BPP). Trong biến thể này, chúng ta áp dụng chủ nghĩa tinh hoa cực đoan: chỉ con kiến tốt nhất tuyệt đối mới được phép cập nhật pheromone. Ma trận pheromone được cập nhật bằng công thức sau: Trong đó, ρ đại diện cho tốc độ bay hơi. Sự bay hơi là rất quan trọng; nếu không có nó, đàn kiến sẽ bị mắc kẹt trong cực tiểu cục bộ đầu tiên mà nó tìm thấy. Biến m chỉ ra số lần trọng số i và trọng số j xuất hiện cùng nhau trong giải pháp tốt nhất. Sự kết hợp trọng số cụ thể xuất hiện càng nhiều trong một mẫu đóng gói được đánh giá cao, vệt pheromone càng trở nên mạnh hơn. def count_pairs(solution, weight_i, weight_j): count = 0 for current_bin in solution: if weight_i in current_bin and weight_j in current_bin: if weight_i == weight_j: # Xử lý trường hợp đặc biệt khi cả hai vật phẩm có cùng trọng số count += current_bin.count(weight_i) * (current_bin.count(weight_i) - 1) // 2 else: # Đếm số lần xuất hiện của cả hai phần tử trong thùng count += current_bin.count(weight_i) * current_bin.count(weight_j) return count def update_pheromones(pheromone_matrix, rho, best_solution, unique_weights, capacity): for i in range(len(unique_weights)): for j in range(len(unique_weights)): # Tính toán cập nhật theo phương trình nhóm MMAS m = count_pairs(best_solution, unique_weights[i], unique_weights[j]) pherom