Một hướng tiếp cận của thuật toán Fictitious play đối với bài toán phân bổ nguồn lực

Mục tiêu của nghiên cứu này nhằm đưa ra mô hình toán học hiệu quả cho bài toán phân bố nguồn lực dưới dạng lý thuyết trò chơi thông qua việc tìm điểm cân bằng Nash. Từ mô hình đó, ta đưa ra phân bố xác suất của các chiến lược lựa chọn được đưa ra trong quá trình phân bổ nguồn lực.
Nội dung trích xuất từ tài liệu:
Một hướng tiếp cận của thuật toán Fictitious play đối với bài toán phân bổ nguồn lựcKỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018DOI: 10.15625/vap.2018.00040 MỘT HƯỚNG TIẾP CẬN CỦA THUẬT TOÁN FICTITIOUS PLAY ĐỐI VỚI BÀI TOÁN PHÂN BỔ NGUỒN LỰC Trịnh Bảo Ngọc, Huỳnh Quyết Thắng, Lê Công Thành, Lê Bá Trường Giang, Trần Quang Huy Viện Công nghệ thông tin và truyền thông, Đại học Bách khoa Hà Nội ngoctb@hanu.edu.vn, thanghq@soict.hust.edu.vn, thanhcls1316@gmail.com, giangpna98@gmail.com, 20164778@student.hust.edu.vnTÓM TẮT: Phân bổ nguồn nhân lực dự án là quá trình cân đối lại các nguồn lực trong thời gian thực hiện dự án, được thực hiệnthường xuyên và chính xác nhằm giải quyết các vấn đề xung đột của dự án, vấn đề xảy ra với nguồn lực dự án ảnh hưởng tới tất cảcác công việc của dự án. Chính vì sự quan trọng như vậy nên các vấn đề nội tại của Phân bổ nguồn lực đáng được đem ra cân nhắcvà tìm cách giải quyết. Mục tiêu của nghiên cứu này nhằm đưa ra mô hình toán học hiệu quả cho bài toán phân bố nguồn lực dướidạng lý thuyết trò chơi thông qua việc tìm điểm cân bằng Nash. Từ mô hình đó, ta đưa ra phân bố xác suất của các chiến lược lựachọn được đưa ra trong quá trình phân bổ nguồn lực. Từ các số liệu đó, các tổ chức, công ty có thể sử dụng , tham khảo để quátrình phân bổ nguồn lực diễn ra hiệu quả. Chúng tôi đề xuất một phương án mở rộng thuật toán Fictitious Play để phù hợp với môhình bài toán phân bổ nguồn lực cũng như nêu lên một số khó khăn của hướng đi này với bộ dữ liệu lớnTừ khóa: Thuật toán Fictitious Play, Cân bằng Nash, Phân bổ nguồn lực, Thuật toán CFR, Thuật toán CFR Plus, Lý thuyếttrò chơi. I. GIỚI THIỆU Phân bổ nguồn nhân lực là quá trình cân đối lại các nguồn lực trong suốt quá trình một tổ chức tồn tại và pháttriển. Nó là một trong các nội dung quan trọng và là điều kiện cần thiết để đảm bảo tính cân đối. Phân tích nguồn lực lànội dung quan trọng trong quản trị chiến lược. Phân bổ nguồn lực hợp lý là cơ sở để thực hiện các mục tiêu chiến lượcmột cách có hiệu quả. Đồng thời với đó, việc phân bổ nguồn lực cần được thực hiện một cách công bằng trước nhu cầucủa các bên. Phân phối nguồn lực một cách ngẫu hứng, thiếu căn cứ khoa học sẽ dẫn đến tình trạng lãng phí, kém hiệuquả trong việc sử dụng các nguồn lực và điều này sẽ dẫn đến việc thực hiện thất bại các mục tiêu đã đề ra. Chính vì tầmquan trọng như vậy, bài toán tối ưu hóa phân bổ nguồn lực thường xuyên được đặt ra và việc giải quyết nó một cách tốtnhất đóng một vai trò quyết định trong hoạt động của tổ chức. Lấy ví dụ, các nguồn lực trong một công ty có thể đượckể đến như: thông tin, tài chính, nhân sự, cơ sở vật chất, khách hàng, nhà cung cấp, công nghệ sử dụng, năng lực quảntrị, năng lực kinh doanh, thương hiệu, uy tín,… Trong bài báo này, chúng tôi phân tích và giải quyết vấn đề thông quaviệc đảm bảo lợi ích cân bằng giữa các bên trong quá trình phân bổ nguồn lực. Bài toán phân bổ nguồn lực có thể được giải quyết bằng cách sử dụng các mô hình trong lý thuyết trò chơi.Trong đó, các thành phần của tổ chức đóng vai trò như người chơi, còn nguồn lực mà họ được phân bổ thể hiện giá trịlợi ích mà họ thu được. Mỗi thành phần đều cố gắng giành được nhiều lợi ích nhất có thể và vì thế có thể xảy ra cạnhtranh lẫn nhau. Thuật toán Fictitious Play, được giới thiệu lần đầu bởi Brown (1951), là một mô hình học phổ biến trong lý thuyếttrò chơi [1, 2]. Trong thuật toán, hai người chơi thay phiên nhau thực hiện các hành động trong trò chơi, tại mỗi vòng lặp,mỗi người chơi sẽ chọn hành động đem lại lợi ích lớn nhất dựa trên tập các hành động trước đó của đối thủ. Trung bìnhcủa dãy các chiến lược, được lựa chọn, của mỗi người chơi sẽ hội tụ về điểm cân bằng Nash [2]. Tuy nhiên, thuật toánFictitious Play có một số hạn chế: thứ nhất thuật toán bổ sung các chiến lược mới không tận dụng đầy đủ thông tin saumỗi vòng lặp, theo đó vai trò của chiến lược mang lại nhiều lợi ích và ít lợi ích là không khác biệt; thứ hai thuật toán chỉhỗ trợ cho mô hình hai người chơi, với sự có mặt của người chơi thứ ba, thuật toán không thể sử dụng được. Hạn chế thứ nhất được khắc phục bằng các biến thể CFR và CFR+, được cải tiến từ thuật toán Fictitious Playgốc [6, 7]. Trong đó, một ma trận bổ sung để lưu trữ thông tin qua mỗi vòng lặp và đánh giá ảnh hưởng từ mỗi chiếnthuật mà người chơi chọn. Từ đó, tốc độ hội tụ của thuật toán được đẩy nhanh. Tuy nhiên cả hai biến thể này vẫnkhông thể giải quyết được hạn chế thứ hai. Để đối mặt với hạn chế đó, nhóm chúng tôi để xuất mô hình mới, dựa trênba thuật toán nêu trên, Fictitious Play, CFR, CFR+. Trong mô hình đề xuất, số người chơi tham gia được nâng lên ( ) Quá trình cập nhật d ...