NHững chú ong giải bài toán Người bán hàng như thế nào? travelling salesman problem – TSP

Năm 2012, bằng việc tìm hiểu về hành vi của loài ong, một nhóm các nhà nghiên cứu tại đại học Queen Mary, London đã tiến hành ghi chép và mô hình hóa quãng đường đi mà ong có thể bay từ bông hoa này sang bông hoa khác sau đó trở về tổ trong một khoảng thời gian ngắn nhất và ít tiêu tốn năng lượng nhất. Phát hiện lần này sẽ giúp các nhà nghiên cứu phát triển những giải pháp tính toán linh hoạt nhằm khắc phục nhiều vấn đề từ việc xây dựng hạ tầng mạng máy tính nhanh hơn cho đến việc chế tạo những vi xử lý mạnh hơn

Bài toán người bán hàng

Thử đặt ra một vấn đề đơn giản sau: bạn là một nhân viên bán hàng và khách hàng của bạn lại nằm rải rác trên một loạt các thành phố. Bạn biết chính xác khoảng cách giữa mỗi 2 thành phố và muốn tìm con đường ngắn nhất để có thể đến thăm mỗi thành phố một lần và sau đó trở về nhà, nơi bạn xuất phát.

Việc kết nối 15 thành phố lớn nhất nước Đức

với lộ trình ngắn nhất là một phép tính khá phức tạp.

Trong khoa học máy tính, ví dụ trên được gọi là “bài toán người bán hàng” (traveling salesman problem) – đây là một vấn đề rất cơ bản và ứng dụng của nó thì nhiều vô kể. Một ứng dụng rất điển hình là hoạt động hàng ngày của các công ty chuyển phát. Công việc của họ là phải phân phát và tiếp nhận hàng hóa sao cho ít tốn thời gian và chi phí nhiên liệu nhất trong khi vẫn đảm bảo không bỏ sót bất cứ điểm đến nào. Ngoài ra, vấn đề trên còn được các nhà sản xuất điện tử áp dụng để tạo ra những con chip siêu nhỏ tốt hơn hay được các nhà di truyền học sử dụng vào chuỗi DNA.

Vấn đề trên không phải “dễ xơi” và phương pháp trực tiếp nhằm tìm ra lời giải phổ biến là kiểm tra tất cả các tổ hợp. Tuy nhiên, trên thực tế phương pháp này không thật sự khả thi bởi nếu lấy mẫu chỉ gồm 20 thành phố thì sẽ có gần 60,8 triệu tỉ phép so sánh để tìm ra hành trình có lợi nhất.

Chim và ong

Mỗi khi các nhà nghiên cứu bị thách thức bởi một vấn đề nào đó thì việc tìm kiếm những giải pháp của tự nhiên có thể là một sự lựa chọn không tồi. Ngành khoa học máy tính cũng không phải là ngoại lệ: thế giới động vật đã mất hàng trăm triệu năm để đúc kết những giải pháp hiệu quả và đơn giản nhằm mở ra câu trả lời cho rất nhiều vấn đề mà chúng ta gặp hàng ngày. Chẳng hạn như loài chim đã liên tục học hỏi để có khả năng bay theo các lộ trình quen thuộc nhằm định hướng giữa các địa điểm quan trọng như tổ và khu vực kiếm ăn, hay những bầy kiến luôn là nguồn cảm hứng cho các kỹ thuật mới giúp nhanh chóng tìm ra giải pháp gần như tối ưu cho bài toán người bán hàng nói trên.

Giờ đây, qua việc đánh giá những phát hiện vừa công bố, một nhóm các nhà nghiên cứu tại đại học Queen Mary, London đã chứng minh rằng những chú ong vò vẽ có thể giải quyết vấn đề tương tự bài toán tìm đường đi ngắn nhất của người bán hàng bằng cách sử dụng một phép lặp đơn giản không cần dùng đến những con số thực, chỉ cần bộ não nhỏ bé của ong.

Không giống như người bán hàng, động vật dĩ nhiên không thể biết được khoảng cách giữa hàng loạt địa điểm một cách chính xác nhưng chúng sẽ thu thập thông tin dần dần. Do đó, động vật (kể cả con người) thực ra đã sử dụng chiến lược phỏng đoán để định vị giữa nhiều địa điểm nhằm tìm ra đoạn đường tối ưu, chẳng hạn như việc liên kết các địa điểm gần nhất chưa viếng thăm hoặc lên kế hoạch cho những địa điểm cần đến trước.

Để kiểm tra các giả thuyết, nhóm nghiên cứu đã thiết lập 5 bông hoa nhân tạo trong một khoảng sân nhỏ và theo dõi đường đi của từng cá thể ong nhằm quan sát xem chúng đã di chuyển từ bông hoa này sang bông tiếp theo như thế nào.

Dữ liệu được ghi nhận cho thấy, trung bình mỗi chú ong đã tìm ra đường đi ngắn nhất giữa 5 bông hoa và trở về tổ sau khi bay thử 20 trong số tổng số 120 lộ trình khả thi. Ngạc nhiên hơn, chúng dường như liên tục cải tiến đường đi của mình qua những thử nghiệm và sai sót – một tập quán phức tạp trước đây chỉ được phát hiện trên những động vật có não lớn.

Các nhà nghiên cứu đã cho thấy rằng hành vi của ong có thể được giải thích bằng một hệ thống đơn giản. Sau khi phát hiện ra tất cả những bông hoa trong một khu vực định sẵn, những chú ong thỉnh thoảng sẽ thử tìm một lộ trình mới và nếu lộ trình này là ngắn nhất tính đến thời điểm hiện tại, ong sẽ tăng xác suất thử nghiệm lộ trình này trong tương lai. Vì vậy, thông qua một vòng lặp gồm phản hồi tích cực, những đường bay tốt sẽ được gia cường trong trí nhớ qua thời gian trong khi số còn lại sẽ bị quên dần, qua đó cho phép ong nhanh chóng chọn ra lộ trình luôn ngắn và tối ưu.

Biểu đồ cho thấy cơ chế vạch lộ trình bay của ong từ tổ (N) đến các bông hoa (F1→F5). Chúng thỉnh thoảng thử nghiệm các lộ trình mới cho đến khi tìm được lộ trình tối ưu nhất.

Quy trình này rất tương đồng với thuật toán bầy kiến (ACO) vốn đang được sử dụng rộng rãi trong ngành khoa học máy tính. Tuy nhiên, khi so sánh với phương pháp bầy kiến, vẫn có những điểm khác biệt quan trọng trong cách thức thực hiện của loài ong. Một ví dụ, khi một trong 5 bông hoa được di chuyển khỏi vị trí ban đầu hoặc loại bỏ, những chú ong tham gia vào việc tìm kiếm lộ trình đến những bông hoa gần nhất luôn thành công. Vì vậy, khi được mô hình hóa phù hợp, việc phỏng theo hành vi của ong có thể mang lại một thuật toán tổng quát hơn, linh hoạt hơn và phù hợp hơn đối với những trường hợp trong đó số lượng tài nguyên, hình dạng không gian và giá trị của chúng thay đổi liên tục theo thời gian.

Kết luận

Như vậy bài toán này không phải được giải và có nghiệm duy nhất. Thực tế là như vậy. Nhưng bằng cachs học tập loài ong và mô tả đường đi của chúng chính là gợi ý để máy tính tối ưu hóa lộ trình trong thực tế.