Một nghiên cứu đột phá đã cải tiến bài toán ghép cặp nhị phân trong khoa học máy tính bằng cách mô phỏng quá trình kết nối giữa các neuron và sợi cơ trong hệ thần kinh. Phương pháp này không chỉ cải thiện hiệu suất ghép cặp trong các ứng dụng như dịch vụ chia sẻ xe, mà còn tăng cường quyền riêng tư nhờ khả năng thực hiện theo phương thức phân tán, không cần đến máy chủ trung tâm .
Giới thiệu
Bài toán ghép cặp nhị phân là một trong những thách thức quan trọng trong khoa học máy tính, được ứng dụng rộng rãi trong các lĩnh vực từ dịch vụ chia sẻ xe, cấy ghép nội tạng, đến các chương trình đào tạo y tế . Bài toán này yêu cầu tối ưu hóa việc ghép cặp giữa hai tập hợp khác nhau (ví dụ như tài xế và hành khách) nhằm giảm thiểu chi phí và tăng cường trải nghiệm người dùng.
Gần đây, nhà nghiên cứu Saket Navlakha tại Cold Spring Harbor Laboratory đã đưa ra một phương pháp mới, lấy cảm hứng từ hệ thần kinh của sinh vật sống. Thuật toán mới này không chỉ tối ưu hóa hiệu quả ghép cặp mà còn giải quyết được một trong những hạn chế lớn của các phương pháp hiện tại: sự phụ thuộc vào máy chủ trung tâm để xử lý dữ liệu .
Phương pháp
1. Bài toán ghép cặp nhị phân và hạn chế hiện tại
Trong các hệ thống hiện tại như dịch vụ chia sẻ xe, khi một hành khách yêu cầu xe, các máy chủ sẽ thu thập thông tin từ nhiều nguồn khác nhau để ghép cặp hành khách với tài xế. Tuy nhiên, việc này đòi hỏi toàn bộ thông tin phải được gửi về một máy chủ trung tâm để xử lý. Điều này không chỉ tốn thời gian mà còn làm giảm quyền riêng tư của người dùng .
2. Lấy cảm hứng từ hệ thần kinh
Trong hệ thần kinh của sinh vật sống, các neuron ban đầu kết nối với nhiều sợi cơ, nhưng qua quá trình cạnh tranh, mỗi neuron cuối cùng chỉ ghép cặp với một sợi cơ. Navlakha đã phát hiện ra quá trình này là một dạng bài toán ghép cặp nhị phân, và ông đã ứng dụng nguyên lý này vào khoa học máy tính .
Thay vì tập trung tất cả thông tin tại một máy chủ, các neuron trong hệ thần kinh tự tiến hành “đấu thầu” dựa trên sự truyền dẫn chất dẫn truyền thần kinh. Neuron nào gửi tín hiệu mạnh nhất sẽ giành quyền kết nối với sợi cơ, trong khi các neuron thất bại sẽ chuyển sang kết nối với sợi cơ khác. Quá trình đấu thầu này không cần đến một trung tâm điều phối mà vẫn đảm bảo hiệu quả tối ưu .
Sơ đồ này minh họa cách các neuron vận động của cơ thể kết nối với sợi cơ trước (bên trái) và sau (bên phải) quá trình cắt tỉa phát triển. Theo giải thích của Navlakha, “Mỗi khối tròn tương ứng với một đơn vị vận động. Các đơn vị vận động nhỏ hoạt động mạnh mẽ, được huy động đầu tiên trong quá trình co cơ (vì các neuron của chúng có ngưỡng kích hoạt thấp) và tạo ra lực nhỏ. Trong khi đó, các đơn vị vận động lớn ít hoạt động hơn, được huy động sau cùng (do các neuron của chúng có ngưỡng kích hoạt cao), và tạo ra lực mạnh hơn.”
Nghiên cứu từ Phòng thí nghiệm Navlakha, Cold Spring Harbor Laboratory
3. Thuật toán phân tán
Thuật toán mới dựa trên hai phương trình đơn giản:
- Cạnh tranh giữa các đối tượng ghép cặp: Tài xế và hành khách cạnh tranh để tìm được đối tượng ghép cặp tối ưu nhất, tương tự như các neuron đấu thầu với sợi cơ.
- Tái phân phối tài nguyên: Nếu một đối tượng (tài xế hoặc hành khách) không thành công, họ sẽ tái phân bổ nguồn lực và tìm đối tượng khác trong phạm vi của mình, thay vì gửi toàn bộ thông tin về một máy chủ .
4. Ví dụ thực tế về hệ thống phân tán
Hãy xem xét tình huống trong dịch vụ chia sẻ xe. Mỗi tài xế và hành khách không cần phải gửi vị trí của mình về một trung tâm điều phối. Thay vào đó, mỗi tài xế sẽ chỉ biết thông tin về các hành khách gần nhất (có thể nhận thông qua phạm vi giao tiếp khoảng 5 km), và gửi đề xuất dựa trên khoảng cách hoặc thời gian ước tính để đến điểm đón. Các hành khách sẽ nhận các đề xuất này và chọn tài xế có thời gian di chuyển ngắn nhất.
Nếu tài xế không được chọn, họ sẽ tiếp tục “đấu thầu” với hành khách khác gần họ, và ngược lại, hành khách cũng có thể điều chỉnh lựa chọn dựa trên các đề xuất mới. Như vậy, không cần phải có một máy chủ trung tâm so sánh toàn bộ dữ liệu của tất cả tài xế và hành khách. Quyết định ghép cặp được đưa ra thông qua các phép tính cục bộ, gần giống với cách hệ thần kinh hoạt động .
Một ví dụ dễ hiểu hơn:
- Bạn có thể tưởng tượng một phiên chợ nơi mỗi người bán hàng tìm kiếm khách mua gần họ. Người bán sẽ mời gọi những khách gần mình nhất, và khách cũng sẽ so sánh người bán gần nhất với giá tốt nhất. Nếu một người bán không được chọn, họ sẽ chuyển sang mời gọi khách khác. Không có ai đứng ra điều phối toàn bộ chợ, nhưng qua quá trình tự giao tiếp này, cuối cùng mỗi người bán và người mua cũng sẽ kết hợp với nhau dựa trên tiêu chí tối ưu tại phạm vi cục bộ.
Trong hệ thống này, mỗi quyết định ghép cặp được đưa ra bởi chính các đối tượng mà không cần tập trung mọi thông tin tại một trung tâm quyết định duy nhất.
Kết quả
Khi so sánh với các thuật toán ghép cặp tốt nhất hiện nay, thuật toán mới này cho thấy hiệu suất vượt trội. Nó tạo ra các cặp ghép tối ưu gần với mức tối ưu toàn cầu mà không cần đến một trung tâm điều phối, giúp giảm thời gian chờ đợi trong các ứng dụng thực tế như dịch vụ chia sẻ xe. Ngoài ra, phương pháp này cũng đảm bảo quyền riêng tư tốt hơn do không cần thu thập toàn bộ dữ liệu về một máy chủ .
Kết luận
Phương pháp phân tán lấy cảm hứng từ hệ thần kinh không chỉ cải thiện bài toán ghép cặp nhị phân mà còn mở ra nhiều ứng dụng trong thực tế, từ các hệ thống dịch vụ chia sẻ xe đến đấu giá trực tuyến. Điều quan trọng là, nó giúp bảo vệ quyền riêng tư và tránh phụ thuộc vào các máy chủ trung tâm. Navlakha hy vọng rằng nghiên cứu này sẽ truyền cảm hứng cho các nhà khoa học khác trong việc phát triển các công cụ dựa trên thuật toán phân tán cho những ứng dụng phức tạp hơn trong tương lai .
Tham khảo
Navlakha, S. et al., 2024, A neural algorithm for computing bipartite matchings, Proceedings of the National Academy of Sciences, DOI: 10.1073/pnas.2321032121.