Sở Khoa học và Công nghệ Thành phố Hồ Chí Minh

View Original

Những bài toán nan giải có thể khiến thế giới đình trệ

See this content in the original post

Trong vài thập kỷ qua các nhà nghiên cứu đã phát triển một loạt giải pháp toán học khá hiệu quả để phân phối hay cấp phát tài nguyên của nhiều lĩnh vực với những kịch bản khác nhau có thể đáp ứng nhu cầu hàng ngày của con người. Nhưng khi thực hiện một phân phối tại một thời điểm thì sẽ ảnh hưởng đến các phân phối sau đó, đây là bài toán động và thời gian trôi qua được xem là một biến của phương trình. Điều này tạo nên một thách thức về mặt toán học, đòi hỏi giải pháp phải tính đến sự biến động và không chắc chắn của thế giới thực.

Những bài toán như vậy được gọi chung là bài toán phân phối tài nguyên động. Chúng nảy sinh bất cứ nơi nào có tài nguyên hạn chế cần được phân phối trong thời gian thực, chẳng hạn như khi bạn chờ taxi hoặc giao hàng. Danh sách các bài toán phân phối tài nguyên động và ứng dụng hàng ngày của chúng hầu như vô tận.

Không chỉ liên quan đến việc cung cấp đúng lúc những gì con người cần, bài toán phân phối tài nguyên động còn được dùng để giải quyết những vấn đề quan trọng và phức tạp như biến đổi khí hậu, giúp phân phối các tài nguyên khan hiếm và cạn kiệt trên hành tinh chúng ta theo những cách hiệu quả nhất.

Trước tiên, hãy xét một ví dụ đơn giản về bài toán phân phối tài nguyên động để biết vì sao nó nan giải.

Hãy tưởng tượng bạn đang nấu một bữa tối cho gia đình bốn người. Bạn chọn thịt bò với đủ thứ phụ liệu chế biến, đây là món yêu thích của cả nhà. Nhưng khi vừa nấu xong thì con gái báo hôm ấy ăn chay, chồng bạn nhắn tin về muộn, và con trai báo đã mời vài người bạn cùng ăn. Vậy là bạn phải cố gắng tìm cách đáp ứng nhu cầu của tất cả thành viên gia đình.

Đây là một ví dụ bình thường của bài toán phân phối tài nguyên động, nhưng nó cho thấy một số thách thức cốt lõi mà các nhà nghiên cứu gặp phải khi giải quyết bài toán này. Các thông số ảnh hưởng đến nhu cầu thay đổi bất ngờ cả trong ngắn hạn và dài hạn. Không có cách nào có thể dự đoán chính xác các vấn đề trên.

Về dài hạn, nhu cầu về bữa ăn trong nhà cũng thay đổi theo từng ngày. Bạn có thể cần phục vụ cho 2 hoặc 20 người ăn mỗi lần. Bạn không biết ai sẽ muốn ăn gì hoặc khi nào. Bạn có thể dự đoán dựa trên kinh nghiệm trước đây, nhưng đây không phải là một phương pháp chắc chắn vì bản chất của con người và nhiều thông số khác ảnh hưởng đến nhu cầu không thể đoán trước.

Bất cứ nơi nào có nguồn lực hạn chế nhưng mức độ nhu cầu thay đổi liên tục sẽ phải đối mặt với các vấn đề phân bổ tài nguyên động theo cách này hay cách khác.

Hành động của các cá nhân trong kịch bản này cũng ảnh hưởng đến trạng thái tương lai của hệ thống. Mỗi khi bạn phân phối một bữa ăn cho một người, nó sẽ làm thay đổi hệ thống - bớt đi một người đói và cả thức ăn trong bếp.

“Tất cả tình huống phân phối tài nguyên động đều cần phải đối phó với sự thay đổi các yếu tố đầu vào và môi trường rất biến động và khó dự đoán, vì trạng thái tương lai không phụ thuộc theo thống kê trạng thái hiện tại”, theo Eiko Yoneki, nhà nghiên cứu cao cấp đứng đầu nhóm nghiên cứu hệ thống trung tâm dữ liệu tại Phòng thí nghiệm máy tính của Đại học Cambridge. “Một thay đổi kích hoạt một thay đổi khác và nếu bạn muốn kiểm soát hệ thống bằng các quyết định chính xác thì phải xem xét trạng thái trong tương lai của hệ thống”.

Ngày nay, giao hàng đã trở thành điều mà nhiều người trong chúng ta coi là hiện nhiên, nhưng đảm bảo điều này có thể được thực hiện một cách hiệu quả hay không là vấn đề phức tạp.

Thêm nữa, khi có nhiều người hoặc tuỳ chọn thức ăn, mọi thứ càng phức tạp hơn. Giờ bạn có nhiều cách hơn để phân phối một loạt bữa ăn khác nhau cho những người khác nhau. Số lượng kết hợp quy mô này theo cấp số nhân khi bạn thêm nhiều người hoặc bữa ăn vào hệ thống.

Đây chính xác là những gì một bệnh viện lớn phải đối mặt, chẳng hạn như khi muốn cung cấp bữa ăn cho tất cả các bệnh nhân. Tương tự khi điều trị cho những bệnh nhân này. Các loại thuốc họ yêu cầu vốn có thời hạn sử dụng hạn chế, và thiết bị cần thiết cho chẩn đoán và điều trị sẽ thay đổi liên tục theo các bệnh nhân khác nhau. Các nguồn lực hạn chế như máy quét MRI, bác sĩ và y tá cũng cần được phân bổ. Để giải quyết vấn đề này và ngăn chặn chi phí vượt khỏi tầm kiểm soát, ban quản lý bệnh viện có thể triển khai các mô hình toán học để giúp điều phối tất cả những thứ này.

Vấn đề là hầu hết các phương pháp hiện có đều dựa vào dữ liệu lịch sử để đưa ra dự đoán. Phương pháp này khó mở rộng quy mô cho các hệ thống như vậy và không thể đối phó ngay cả với những thay đổi nhỏ nhất. Nếu một thay đổi xảy ra, họ phải quay lại giải bài toán từ đầu. Những vấn đề như vậy nhanh chóng trở nên khó tính toán, ngay cả với một số ít người và tài nguyên.

Các bài toán phân phối tài nguyên động cũng nảy sinh từ một loạt các kịch bản khác nhau và mỗi trường hợp có một vấn đề riêng. Ví dụ, các hệ thống máy tính hiện đại rất phức tạp và có nhiều thông số cấu hình cần được tinh chỉnh, bao gồm cấp phát tài nguyên bộ nhớ, bộ xử lý và bất kỳ đầu vào nào của hệ thống. Các hệ thống máy tính năng động và đối phó với môi trường luôn thay đổi, đòi hỏi phương pháp điều khiển động. Mạng điện thoại di động và điện toán đám mây cũng phải giải quyết những bài toán này.

Các công ty giao hàng cũng đang giải quyết các bái toán phân phối tài nguyên động để tăng tốc độ giao hàng. Ví dụ, UPS đã phát triển hệ thống Orion (On-Road Integrated Optimisation and Navigation) để tối ưu hóa các tuyến đường giao hàng bằng các thuật toán tiên tiến.

Chuỗi cung ứng là một bài toán khác. Các sản phẩm ngày nay rất phức tạp, để sản xuất một chiếc điện thoại thông minh, bạn cần phối hợp hàng trăm linh kiện từ khắp nơi trên thế giới, tất cả chúng được kết hợp theo một thứ tự nhất định. Sự gián đoạn chuỗi cung ứng là một vấn đề lớn trong việc đáp ứng nhu cầu của xã hội.

“Thực sự, bạn sẽ rất khó tìm thấy một ngành nào đó không phải đối mặt với những thách thức trong việc giải bài toán phân phối tài nguyên động dưới dạng này hay dạng khác”, theo Warren Powell, kỹ sư tại Đại học Princeton, người đã nghiên cứu bài toán này từ những năm 1980. Hiện có ít nhất 15 cộng đồng nghiên cứu bài toán đa dạng này theo những hướng khác nhau.

Một nhà bếp của bệnh viên bận rộn giải quyết các nhu cầu thay đổi liên tục, khiến cho việc dự đoán có bao nhiêu phần ăn cho bệnh nhân và các lưu ý trong đó trở nên khó khăn.

Sự đa dạng của các bài toán phân phối tài nguyên động có nghĩa cần phải chuẩn hóa các kỹ thuật và phương pháp tính toán khác nhau được sử dụng. Powell hiện cùng với một số người cố gắng tập hợp các cộng đồng khác nhau. “Cách tiếp cận của chúng tôi không thay thế bất kỳ công việc nào trước đây mà kết hợp tất cả lại với nhau và giúp xác định các cơ hội nhân sao những ưu điểm”.

Những tiến bộ trong lĩnh vực học máy đang mang lại hy vọng mới trong việc giải quyết các bài toán phân phối tài nguyên động. Một kỹ thuật trí tuệ nhân tạo được gọi là học sâu tăng cường cho phép một thuật toán học những gì cần làm bằng cách tương tác với môi trường. Thuật toán được thiết kế để học mà không cần sự can thiệp của con người bằng cơ chế thưởng khi thực hiện đúng và phạt khi thực hiện không chính xác. Bằng cách cố gắng tối đa hóa điểm thưởng và giảm thiểu điểm phạt, nó có thể nhanh chóng đạt đến trạng thái tối ưu.

Học sâu tăng cường gần đây đã giúp cho chương trình AlphaGo thuộc trung tâm nghiên cứu DeepMind của Google đánh bại nhà vô địch thế giới trong môn cờ vây. Hệ thống bắt đầu không biết gì về trò chơi cờ vây, sau đó chơi với chính nó để huấn luyện và tối ưu hóa hiệu suất. Mặc dù các trò chơi là bằng chứng quan trọng về các kỹ thuật học sâu tăng cường, nhưng học cách chơi trò chơi không phải là mục tiêu thật sự.

Yoneki và nhóm của cô đã nghiên cứu một giải pháp thay thế khả thi cho việc suy luận của con người để điều chỉnh hiệu suất trong các hệ thống máy tính bằng cách áp dụng việc học sâu tăng cường. Hệ thống máy tính mà họ đang phát triển có thể mở rộng quy mô để giải quyết các vấn đề ra quyết định mà trước đây không thể thực hiện được bằng máy tính, và cũng có thể đáp ứng với việc thay đổi các tham số trong thời gian thực.

Các hệ thống sử dụng phương pháp này đã được sử dụng để tối ưu hóa hiệu suất hệ thống trong các lĩnh vực như quản lý tài nguyên và làm mát trung tâm dữ liệu. Yoneki cho rằng các ứng dụng như vậy chỉ mới bắt đầu, còn nhiều cơ hội hoàn toàn mới đang mở ra.

Mạng di động cần phân bổ các tài nguyên như việc ưu tiên băng thông hay như tải xuống hoặc cuộc gọi.

Một nhóm các nhà nghiên cứu Anh tại công ty khởi nghiệp trí tuệ nhân tạo Prowler.io cũng đang sử dụng phương pháp học máy của riêng mình để giải quyết các bài toán phân phối tài nguyên động. Các thuật toán của họ đưa ra các khuyến khích để tạo ra một hành vi cụ thể trong hệ thống. Trong tình huống thực tế, điều này có thể tương đương với việc đưa ra các loại phí thông minh để khuyến khích người lái xe sử dụng các con đường cụ thể và giảm thiểu tắc nghẽn giao thông và ô nhiễm.

Nhưng vẫn còn nhiều việc phải làm trong lĩnh vực máy học, và các nghiên cứu đang tiến triển nhanh chóng . “Việc sử dụng phương pháp học sâu tăng cường sẽ giúp giải quyết các bài toán phân phối tài nguyên động, nhưng nó đòi hỏi nhiều dữ liệu để xây dựng mô hình, và nó vẫn đang ở giai đoạn thử nghiệm, đặc biệt các hệ thống máy tính phải xử lý nhiều tham số phức tạp hơn là các trò chơi đơn giản”, Yoneki nói.

Chúng ta vẫn còn khoảng cách trong việc giải quyết dạng bài toán độc đáo này vì ngày nay các kỹ thuật và tài nguyên tính toán nhanh chóng cạn kiệt khi giải quyết sự phức tạp và tính chất ngẫu nhiên của thế giới thực. Nhưng khi dân số thế giới tiếp tục phát triển và sự khao khát đối với các dịch vụ theo yêu cầu tăng lên, sự phức tạp của các bài toán phân phối tài nguyên động và tác động của chúng đối với cuộc sống hàng ngày của chúng ta cũng sẽ tăng lên.

Nếu bây giờ chúng ta không bắt đầu giải quyết các bài toán phân phối tài nguyên động thì tương lai chúng ta sẽ không chỉ vật lộn với bữa tối mà toàn bộ thế giới có thể bị đình trệ.

P.Uyên

See this content in the original post

Xem thêm

See this gallery in the original post