Lập lịch thanh toán dự án sử dụng mô hình cân bằng Nash và thuật toán di truyền

- 1 CHƯƠNG 1: TỔNG QUAN VỀ MÔ HÌNH CÂN BẰNG NASH TRONG LÝ THUYẾT TRÒ CHƠI VÀ THUẬT TOÁN DI TRUYỀN.
- Tổng quan về lập lịch thanh toán dự án.
- Lý thuyết trò chơi và cân bằng Nash.
- Giới thiệu lý thuyết trò chơi.
- Các loại trò chơi.
- Mô hình cân bằng Nash.
- Thuật toán di truyền.
- Các toán tử di truyền.
- Các bước của thuật toán di truyền.
- Kết hợp thuật toán di truyền và cân bằng Nash.
- 10 CHƯƠNG 2: XÂY DỰNG THUẬT TOÁN DI TRUYỀN VÀ CÂN BẰNG NASH TRONG LẬP LỊCH THANH TOÁN DỰ ÁN.
- Mô hình hóa trò chơi và cân bằng Nash trong lập lịch thanh toán.
- Mạng dự án.
- Cách thức mô hình hóa việc thanh toán dự án.
- Thuật toán di truyền và giải pháp cân bằng Nash.
- Mô hình chung của thiết kế thuật toán di truyền cho bài toán lập lịch thanh toán dự án.
- Thiết kế thuật toán di truyền cho chiến lược thứ nhất.
- Thiết kế thuật toán di truyền cho chiến lược thứ hai.
- Các tham số của thuật toán di truyền.
- Hà Nội, ngày 19 tháng 04 năm 2016 Người thực hiện Nguyễn Thị Thu Bích LỜI CAM ĐOAN Luận văn Thạc sĩ “Lập lịch thanh toán dự án sử dụng mô hình cân bằng Nash và thuật toán di truyền”, chuyên ngành Kỹ thuật Máy tính là công trình của cá nhân tôi.
- GA Genetic algorithm Thuật toán di truyền 4.
- NST Nhiễm sắc thể DANH MỤC HÌNH VẼ Hình 1.1: Sơ đồ cấu trúc thuật toán di truyền.
- 14 Hình 3.1: Sơ đồ mạng dự án 1.
- 30 Hình 3.2: Sơ đồ mạng dự án 2.
- 35 Hình 3.3: Kết quả chạy chương trình của dự án 1.
- 43 Hình 3.4: Kết quả chạy chương trình của dự án 2.
- 46 DANH MỤC CÁC BẢNG Bảng 3.1: Mạng dự án 1.
- 32 Bảng 3.2: Bảng thông số các hoạt động của mạng dự án 1.
- 34 Bảng 3.3: Mạng dự án 2.
- 38 Bảng 3.4: Bảng thông số các hoạt động của mạng dự án 2.
- 41 Bảng 3.5: Lịch thanh toán ban đầu của dự án 1.
- 42 Bảng 3.6: Lịch thanh toán tối ưu theo phần mềm của dự án 1.
- 42 Bảng 3.7: Lịch thanh toán ban đầu của dự án 2.
- 44 Bảng 3.8: Lịch thanh toán tối ưu theo phần mềm của dự án 2.
- Trong đó, lập lịch thanh toán dự án là một vấn đề quan trọng và quyết định chất lượng của dự án.
- Tuy nhiên công việc lập lịch thanh toán thường gặp khó khăn do sự bất đồng giữa chủ đầu tư và nhà thầu.
- Do đó, quá trình ra quyết định trong lập kế hoạch thanh toán dự án đều phải đáp ứng yêu cầu của cả hai bên là chủ đầu tư và nhà thầu.
- Thông thường, chủ đầu tư luôn mong muốn việc thanh toán tất cả khoản tiền cho dự án được thực hiện muộn nhất tức là khi dự án được hoàn thành, trong khi đó mong muốn từ phía nhà thầu lại ngược lại, họ muốn các khoản thanh toán nên thực hiện ngay từ đầu khi bắt đầu dự án.
- Bởi vậy, để giải quyết vấn đề này cần phải có một phương án phù hợp nhất cho yêu cầu của cả hai bên, đảm bảo lợi ích cho cả nhà đầu tư và nhà thầu trong suốt quá trình thực hiện dự án.
- Xuất phát từ lý do đó mà mục đích của đồ án này là nghiên cứu ứng dụng của thuật toán di truyền và mô hình cân bằng Nash vào trong công tác lập lịch thanh toán dự án nhằm đưa ra những giải pháp tối ưu trong công tác lập lịch và cân bằng lợi ích cho chủ đầu tư dự án và nhà thầu mà họ mong muốn.
- Mục tiêu của đề tài Đề tài tập trung nghiên cứu sử dụng mô hình cân bằng Nash và thuật toán di truyền trong lập lịch thanh toán dự án.
- Nghiên cứu về lý thuyết trò chơi và mô hình cân bằng Nash.
- Nghiên cứu về thuật toán di truyền và sự kết hợp thuật toán di truyền và cân bằng Nash.
- Ứng dụng thuật toán di truyền và mô hình cân bằng Nash vào lập lịch thanh toán dự án phần mềm và đánh giá các kết quả nhận được.
- Cơ sở lý luận của lý thuyết trò chơi và mô hình cân bằng Nash.
- Tổng quan về thuật toán di truyền.
- Lập lịch thanh toán dự án sử dụng mô hình cân bằng Nash và thuật toán di truyền.
- Nghiên cứu tổng quan về lý thuyết trò chơi và cân bằng Nash.
- Tìm hiểu về thuật toán di truyền.
- Sự kết hợp thuật toán di truyền và cân bằng Nash b.
- Phương pháp nghiên cứu thực nghiệm: Ứng dụng mô hình cân bằng Nash và thuật toán di truyền vào lập lịch thanh toán dự án phần mềm.
- Kết quả Nghiên cứu ứng dụng từ việc kết hợp thuật toán di truyền cùng mô hình cân bằng Nash trong lý thuyết trò chơi vào việc tối ưu hóa lịch thanh toán dự án, đảm bảo cân bằng những yêu cầu của chủ đầu tư và nhà thầu.
- Xây dựng một mô hình thực nghiệm trong quản lý lập lịch thanh toán dự án, đưa ra những giải pháp tối ưu trong lịch trình thanh toán của dự án.
- Ý nghĩa khoa học và thực tiễn Với sự kết hợp mô hình cân bằng Nash và thuật toán di truyền sẽ tối ưu hóa trong công việc lập lịch thanh toán dự án mà vẫn đảm bảo được lợi ích của chủ đầu tư và nhà thầu.
- Bố cục luận văn Bố cục luận văn được chia làm 4 chương như sau: Chương 1: Tổng quan về mô hình cân bằng Nash trong lý thuyết trò chơi và thuật toán di truyền.
- Chương 2: Xây dựng thuật toán di truyền và cân bằng Nash trong lập lịch thanh toán dự án.
- 3 CHƯƠNG 1: TỔNG QUAN VỀ MÔ HÌNH CÂN BẰNG NASH TRONG LÝ THUYẾT TRÒ CHƠI VÀ THUẬT TOÁN DI TRUYỀN 1.1.
- Tổng quan về lập lịch thanh toán dự án Lập lịch thanh toán dự án là một kế hoạch thanh toán chi tiết của một dự án mà chủ đầu tư cần thực hiện.
- Mục đích của việc lập lịch thanh toán là tạo ra một quy trình thanh toán tương ứng với mỗi công việc trong dự án đã hoàn thành.
- Số lần thanh toán sẽ phụ thuộc vào quy mô của dự án, số lượng công việc cần thực hiện và những ưu đãi của chủ đầu tư đối với nhà thầu.
- Mỗi giai đoạn thanh toán là phần trăm số tiền dự kiến đầu tư cần trả tương ứng với một hoặc một số các công việc cần hoàn thành hay chính là các mốc của dự án.
- Việc thanh toán phải được tương đương với giá trị công việc hoàn thành.
- Việc lập lịch thanh toán thường gặp khó khăn xuất phát từ sự bất đồng giữa chủ đầu tư và nhà thầu.
- Các chủ đầu tư muốn thực hiện việc thanh toán vào cuối dự án tức là khi bàn giao tất cả các công việc đã hoàn thành, nhưng nhà thầu lại muốn các khoản tiền đầu tư cần thanh toán ngay lúc đầu.
- Vậy một lịch thanh toán phù hợp là phải cân bằng cả hai nhu cầu trên và giữ cho công việc được thực hiện đúng tiến độ.
- Việc lập lịch thanh toán cần một lịch trình các công việc cụ thể hay là một tiến trình triển khai dự án và để tránh các xung đột trong việc lập lịch thanh toán thì tiến độ thanh toán phải phản ánh sát giá trị thực tế của công việc hoàn thành.
- Đã có nhiều thuật toán được sử dụng để giải quyết bài toán lập lịch thanh toán như: thuật toán tham lam, các thuật toán heuristic, thuật toán tìm kiếm cục bộ, thuật toán Simulated Annealing, thuật toán Tabu Search, thuật toán di truyền…Tuy nhiên hầu hết các thuật toán đều có không gian tìm kiếm khá lớn.
- Thuật toán di truyền có lợi ích là làm giảm không gian tìm kiếm, hội tụ về lời giải toàn cục và tối ưu đa mục tiêu trong bài toán lập lịch thanh toán.
- Một số bài báo nước ngoài đã nghiên cứu và cho thấy kết quả khả quan khi sử dụng cân bằng Nash và thuật toán di truyền như: 4 - "A Preference-Based Bi-Objective Approach to the Payment Scheduling Negotiation Problem with the Extended r-Dominance and NSGAII” của tác giả Wei-neng Chen và Jun Zhang.
- Lý thuyết trò chơi và cân bằng Nash 1.2.1.
- Các loại trò chơi a.
- Mô hình cân bằng Nash Một trò chơi bao gồm ba yếu tố như: một tập hợp các người chơi.
- Các kết quả thưởng phạt này tương ứng với mỗi hành động chiến lược của người chơi đã lựa chọn.
- Một mô hình cân bằng Nash cơ bản là một tập các hành động với các kết quả thưởng phạt nhằm đảm bảo không có bất cứ người chơi nào có thể có kết quả thưởng phạt cao hơn bằng việc làm sai lệch các lựa chọn có sẵn [6].
- Định nghĩa cơ bản của cân bằng Nash là: Nếu tồn tại một tập hợp các chiến lược cho một trò chơi với đặc tính là không có một đối thủ nào có thể hưởng lợi bằng cách thay đổi chiến lược hiện tại của mình khi các đối thủ khác không thay đổi, tập hợp các chiến lược đó cùng kết quả tương ứng nhận được tạo nên cân bằng Nash.
- Cân bằng Nash trong game cộng tác với 2 người chơi với 2 chiến lược khác nhau và người này biết hành động của người kia, ở trạng thái cả 2 đều tối ưu được lợi ích của mình với trạng thái tương ứng của đối thủ thì khi đó ta được trạng thái cân bằng Nash.
- Thuật toán di truyền 1.3.1.
- Khái niệm Thuật toán di truyền (Genetic algorithm – GA) là một phương pháp tìm kiếm tối ưu mô phỏng quá trình tiến hóa của tự nhiên, thuộc lớp thuật toán tiến hóa và sử dụng các kỹ thuật như kế thừa, đột biến, lai ghép, chọn lọc.
- Trong thuật toán di truyền, từ một quần thể gồm các cá thể tương ứng với một tập các “lời giải cho bài toán” và để đạt tới một lời giải tối ưu là một quá trình tiến 6 hóa nhằm tạo ra các thế hệ tốt hơn.
- Thuật toán di truyền sử dụng một số thuật ngữ của ngành di truyền học như: Nhiễm sắc thể, Quần thể, Gen… Nhiễm sắc thể (NST) được tạo thành từ các Gen (được biểu diễn của một chuỗi tuyến tính).
- Các toán tử di truyền a.
- Toán tử đột biến: 7 Toán tử đột biến là cá thể con mang một số đặc tính không có trong mã di truyền của cha mẹ hay một đoạn mã di truyền đã bị thay đổi tức là khác với cá thể cha mẹ.
- Toán tử di truyền được thực hiện bằng cách chọn ngẫu nhiên một đoạn mã di truyền trong quần thể rồi tạo ra một số k ngẫu nhiên trong khoảng từ 1 đến m với điều kiện 1 ≤ k ≤ m rồi thay đổi mã thứ k và đưa vào quần thể để tham gia quá trình tiến hóa ở thế hệ tiếp theo [10].
- Các bước của thuật toán di truyền Thuật toán di truyền lại là một phương thức giải quyết vấn đề bài toán bằng cách sử dụng mô hình di truyền tiến hóa, tìm kiếm các giải pháp gần đúng nhằm tối ưu hóa và tìm kiếm các vấn đề [9].
- Bởi vậy, quy trình cơ bản của thuật toán di truyền bắt đầu bằng bước khởi tạo một quần thể ban đầu là các chuỗi nhiễm sắc thể gồm các gen tương ứng với lời giải của bài toán.
- Thuật toán sẽ kết thúc khi thỏa mãn các điều kiện dừng cho trước.
- Các bước của thuật toán được thể hiện bằng sơ đồ sau [9]: 8 Nhận các tham số của bài toánKhởi tạo quần thể ban đầuTính giá trị thích nghiSinh sảnLai ghépĐột biếnĐiều kiện dừngKết thúcBắt đầuLựa chọn giải pháp tốt nhất Hình 1.1: Sơ đồ cấu trúc thuật toán di truyền 1.4.
- Kết hợp thuật toán di truyền và cân bằng Nash Một vấn đề đặt ra về trạng thái cân bằng Nash chính là việc tìm ra nó không đơn giản.
- Nhưng bằng việc kết hợp cân bằng Nash với thuật toán di truyền, bài toán đã trở nên dễ dàng hơn.
- Ta có thể thấy rằng trong lý thuyết trò chơi, mỗi người chơi có một tập các chiến lược, khi các bên đều đạt được lợi ích nhất định thì trò chơi sẽ ở trạng thái cân bằng Nash.
- Nếu xem tập các chiến lược của người chơi như một tập quần thể lời giải tương ứng, chiến lược tối ưu được tìm dựa trên những người chơi khác xem như cách tạo thế hệ mới trong thuật toán di truyền, dựa trên ý tưởng này ta có sự kết hợp giữa thuật toán di truyền và cân bằng Nash trong lý thuyết trò chơi.
- P2 ~ Quần thể 2 Gửi Yk-1 Gửi Xk-1 Tối ưu Xk+1 Cố định Y từ người chơi 2 Tối ưu Yk+1 Cố định Y từ người chơi 2 Tối ưu Xk-1 Cố định Y từ người chơi 2 Tối ưu Yk-1 Cố định X từ người chơi 1 Tối ưu Xk Cố định Y từ người chơi 2 Tối ưu Yk Cố định X từ người chơi 1 Gửi Xk Gửi Yk Thế hệ k-1 Thế hệ k Thế hệ k+1 Phương pháp kết hợp thuật toán di truyền và cân bằng Nash đã được mô tả theo sơ đồ trên có thể được hiểu chi tiết trong bài toán 2 người chơi như sau: Hai người chơi P1, P2 có tập các chiến lược tương ứng là X,Y, cũng là 2 quần thể lời giải của 2 người chơi [8].
- Theo lý thuyết cân bằng Nash, người chơi 1 tối ưu s bằng việc giữ nguyên chiến lược Y của người chơi 2 và chỉ tối ưu chiến lược X của mình.
- Ngược lại, khi người chơi 2 tối ưu s thì chỉ tối ưu trên tập chiến lược Y của mình và giữ nguyên X [8].
- Ở thế hệ thứ k, người chơi P1 tìm ra tập chiến lược tối ưu Xk bằng việc đánh Hình 1.2: Mô hình chiến thuật Nash GA 10 giá s = XkYk-1.
- Trạng thái cân bằng quần thể tương ứng với việc cả 2 người chơi đều không thể tối ưu hơn được phương án của mình.
- Tiểu kết chương 1 Chương này đã tập trung nghiên cứu những kiến thức cơ bản về lập lịch thanh toán dự án, mô hình cân bằng Nash trong lý thuyết trò chơi và thuật toán di truyền.
- Từ kết quả nghiên cứu này cho ta thấy rằng bản chất của bài toán lập lịch thanh toán chính là một mô hình trò chơi gồm hai đối thủ có thông tin hoàn hảo và là trò chơi có tổng khác không.
- Sự kết hợp cả thuật toán di truyền và cân bằng Nash sẽ đưa ra một lời giải tối ưu cho bài toán được quyết định thông qua hàm thích nghi.
- Đây cũng là cơ sở để tác giả đi vào xây dựng mô hình ứng dụng thuật toán di truyền và mô hình cân bằng Nash vào lập lịch thanh toán dự án trong chương 2.

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt