Xây dựng giải thuật ải tiến ứng dụng cân bằng nash và giải thuật di truyền trong giải bài toán đấu thầu nhiều vòng

Chuyên khảo kỹ thuật phân tích Xây dựng giải thuật ải tiến ứng dụng cân bằng nash và giải thuật di truyền trong giải bài toán đấu, đánh giá các khía cạnh quan trọng, đề xuất hướng

• Tác giả: Hồ Thị Lợi
• Người hướng dẫn: PGS. Huỳnh Quyết Thắng
• Trường học: Trường Đại Học Bách Khoa Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Giải Thuật Cải Tiến Ứng Dụng Cân Bằng Nash Trong Đấu Thầu Nhiều Vòng
• Loại tài liệu: Luận Văn Thạc Sĩ Kỹ Thuật
• Năm xuất bản: 2017
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. MỞ ĐẦU
• 1.2. Giải thuật di truyền
• 1.2.1. Khái niệm
• 1.2.2. Toán tử và sơ đồ giải thuật di truyền
• 1.2.3. Hàm mục tiêu và điều kiện dừng của thuật toán
• 1.3. Lý thuyết trò chơi và mô hình cân bằng Nash
• 1.3.1. Lý thuyết trò chơi
• 2. CHƯƠNG 2: PHÂN TÍCH BÀI TOÁN ĐẤU THẦU NHIỀU VÒNG VÀ Ý TƯỞNG CỦA GIẢI THUẬT CẢI TIẾN
• 2.1. Mô tả bài toán
• 2.2. Mô hình hóa bài toán
• 2.3. Lựa chọn giải thuật
• 2.4. Giải bài toán tối ưu với giải thuật di truyền
• 2.5. Kết hợp cân bằng Nash và giải thuật di truyền
• 2.6. Tìm hiểu, đánh giá những nghiên cứu đã tiến hành trước đây
• 2.7. Mô hình gen
• 2.8. Chọn lọc và sinh sản
• 2.9. Các hàm lợi ích, hàm mục tiêu và điều kiện dừng
• 2.10. Phân tích kết quả giải thuật đề xuất trong tài liệu [10]
• 2.11. Nhận xét đánh giá
• 2.12. Đề xuất các cải tiến cần thực hiện
• 2.12.1. Cải tiến cấu trúc gen của thuật toán
• 2.12.2. Cải tiến hàm thích nghi của thuật toán
• 2.12.3. Cải thiện tính toán để tăng tốc độ chạy chương trình
• 2.13. Tiểu kết chương 2
• 3. CHƯƠNG 3: XÂY DỰNG GIẢI THUẬT CẢI TIẾN GA-NASH IMPROVED TRONG GIẢI BÀI TOÁN ĐẤU THẦU NHIỀU VÒNG
• 3.1. Sơ đồ thuật toán GA-Nash-Improved
• 3.2. Xây dựng giải thuật cải tiến GA-NASH-IMPROVED
• 3.3. Xác định cấu trúc gen từ các ràng buộc của bài toán
• 3.4. Khởi tạo quần thể ban đầu của thuật toán
• 3.5. Tính toán các hàm lợi ích và giá trị thích nghi
• 3.6. Kiểm tra điều kiện dừng của thuật toán
• 3.7. Chọn lọc và sinh sản
• 3.8. Xây dựng ứng dụng với giải thuật GA-NASH-IMPROVED
• 3.8.1. Mô hình hóa chức năng ứng dụng
• 3.8.2. Thiết kế CSDL
• 3.8.3. Thiết kế giao diện chương trình ứng dụng
• 3.8.4. Thử nghiệm ứng dụng
• 3.8.5. Thu thập dữ liệu
• 3.8.6. Phân tích, mô phỏng dữ liệu vào
• 3.8.7. Phân tích kết quả thử nghiệm
• 3.8.8. Đánh giá kết quả thử nghiệm
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Giải Thuật Cải Tiến Ứng Dụng Cân Bằng Nash

Bài toán đấu thầu nhiều vòng đặt ra yêu cầu cấp thiết về một phương pháp tiếp cận tối ưu, đảm bảo tính công bằng và hiệu quả. Các phương pháp truyền thống thường gặp khó khăn trong việc cân bằng lợi ích giữa các bên liên quan, dẫn đến những bất cập và hạn chế trong quá trình thực hiện dự án. Luận văn này tập trung vào việc xây dựng và cải tiến giải thuật ứng dụng cân bằng Nash và giải thuật di truyền (GA) để giải quyết bài toán này. Mục tiêu là tìm ra một giải pháp, một công cụ hỗ trợ hữu ích cho các nhà đầu tư và nhà cung cấp trong việc xác định điểm cân bằng, hài hòa lợi ích, đặc biệt trong đấu thầu nhiều vòng. Như tác giả Hồ Thị Lợi đã đề xuất, việc nghiên cứu này hướng đến một mô hình hỗ trợ, đóng góp vào việc tìm ra điểm cân bằng lợi ích giữa các bên khi thực hiện dự án đấu thầu.

1.1. Giới Thiệu Lý Thuyết Trò Chơi và Cân Bằng Nash

Lý thuyết trò chơi là một công cụ mạnh mẽ để phân tích các tình huống cạnh tranh, nơi kết quả phụ thuộc vào quyết định của tất cả người chơi. Trong đó, mỗi người chơi sẽ cố gắng dự đoán sự lựa chọn của những người chơi khác để có thể đưa ra lựa chọn tốt nhất cho mình. Cân bằng Nash là một trạng thái trong đó không người chơi nào có động lực để thay đổi chiến lược của mình nếu những người chơi khác giữ nguyên chiến lược của họ. Áp dụng lý thuyết trò chơi và cân bằng Nash vào đấu thầu nhiều vòng giúp xác định chiến lược tối ưu cho mỗi nhà thầu, đảm bảo sự công bằng và minh bạch trong quá trình đấu thầu.

1.2. Ứng Dụng Giải Thuật Di Truyền Trong Tối Ưu Hóa

Giải thuật di truyền (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 tự nhiên. Nó sử dụng các kỹ thuật như kế thừa, đột biến, lai ghép và chọn lọc để tìm ra lời giải tốt nhất cho một bài toán. Trong đấu thầu nhiều vòng, giải thuật di truyền có thể được sử dụng để tìm ra các chiến lược đấu thầu tối ưu cho mỗi nhà thầu, dựa trên các yếu tố như chi phí, năng lực và kỳ vọng lợi nhuận. Giải thuật di truyền cho phép tìm kiếm trong một không gian giải pháp rộng lớn, từ đó tìm ra những giải pháp không thể tìm thấy bằng các phương pháp truyền thống.

II. Thách Thức Tối Ưu Chiến Lược Đấu Thầu Trong Nhiều Vòng

Việc tối ưu chiến lược đấu thầu trong đấu thầu nhiều vòng là một bài toán phức tạp, đòi hỏi sự cân nhắc kỹ lưỡng các yếu tố như thông tin không đầy đủ, sự cạnh tranh giữa các nhà thầu và mục tiêu tối đa hóa lợi nhuận. Các nhà thầu phải đưa ra quyết định dựa trên dự đoán về hành vi của đối thủ, đồng thời phải thích ứng với thông tin mới nhận được trong mỗi vòng đấu. Điều này đòi hỏi một phương pháp tiếp cận linh hoạt và hiệu quả, có khả năng xử lý các yếu tố không chắc chắn và đưa ra quyết định tối ưu trong thời gian ngắn. Theo tác giả, việc làm thế nào để tối ưu được hiệu quả của việc đấu thầu dự án mà vẫn đảm bảo lợi ích cho các bên được hài hòa vẫn đang là một bài toán khó.

2.1. Các Yếu Tố Ảnh Hưởng Đến Hiệu Quả Đấu Thầu

Nhiều yếu tố có thể ảnh hưởng đến hiệu quả đấu thầu, bao gồm số lượng nhà thầu tham gia, mức độ cạnh tranh, thông tin về chi phí và năng lực của các nhà thầu, và các quy định của cuộc đấu thầu. Việc thiếu thông tin đầy đủ và chính xác có thể dẫn đến quyết định không tối ưu, gây thiệt hại cho cả nhà thầu và chủ đầu tư. Để nâng cao hiệu quả đấu thầu, cần có một hệ thống thu thập và phân tích thông tin hiệu quả, cũng như một phương pháp đánh giá rủi ro chính xác.

2.2. Hạn Chế Của Các Phương Pháp Đấu Thầu Truyền Thống

Các phương pháp đấu thầu truyền thống thường dựa trên các quy tắc đơn giản và giả định rằng các nhà thầu hành động một cách hợp lý và có đầy đủ thông tin. Tuy nhiên, trong thực tế, các nhà thầu có thể có các mục tiêu khác nhau, thông tin không đầy đủ và có thể hành động một cách phi lý. Điều này có thể dẫn đến kết quả không tối ưu, hoặc thậm chí thất bại trong việc lựa chọn nhà thầu phù hợp. Do đó, cần có một phương pháp tiếp cận mới, có khả năng xử lý các yếu tố phức tạp và không chắc chắn trong đấu thầu.

III. Giải Pháp Cải Tiến Thuật Toán GA Nash Cho Đấu Thầu

Luận văn này đề xuất một giải thuật cải tiến dựa trên sự kết hợp giữa giải thuật di truyền (GA) và cân bằng Nash. Giải thuật này được thiết kế để tìm ra các chiến lược đấu thầu tối ưu cho mỗi nhà thầu trong đấu thầu nhiều vòng, đồng thời đảm bảo sự công bằng và minh bạch trong quá trình đấu thầu. Giải thuật cải tiến này tập trung vào việc cải thiện cấu trúc gen, hàm thích nghi và tốc độ tính toán, nhằm nâng cao hiệu quả và tính ứng dụng của giải thuật. Theo tác giả Hồ Thị Lợi, sau khi tìm hiểu và đánh giá các nghiên cứu đã có trước đây, tác giả đã đưa ra một số đề xuất cải tiến nhằm nâng cao hiệu quả của giải thuật đã chọn.

3.1. Cải Tiến Thuật Toán Tối Ưu Cấu Trúc Gen

Cấu trúc gen đóng vai trò quan trọng trong việc biểu diễn các chiến lược đấu thầu của nhà thầu. Cải tiến thuật toán bằng cách tối ưu cấu trúc gen giúp biểu diễn các chiến lược một cách hiệu quả hơn, từ đó giúp giải thuật di truyền tìm ra các giải pháp tốt hơn. Việc cải tiến thuật toán bao gồm việc xác định các gen quan trọng, thiết kế các toán tử lai ghép và đột biến phù hợp và sử dụng các phương pháp mã hóa hiệu quả.

3.2. Cải Tiến Thuật Toán Nâng Cao Hàm Thích Nghi

Hàm thích nghi đánh giá chất lượng của các chiến lược đấu thầu và hướng dẫn quá trình tìm kiếm của giải thuật di truyền. Cải tiến thuật toán bằng cách nâng cao hàm thích nghi giúp đánh giá các chiến lược một cách chính xác hơn, từ đó giúp giải thuật di truyền tìm ra các giải pháp tối ưu hơn. Việc nâng cao hàm thích nghi bao gồm việc xem xét các yếu tố như chi phí, năng lực, kỳ vọng lợi nhuận và rủi ro.

IV. Ứng Dụng Thực Tiễn Thử Nghiệm Giải Thuật Cải Tiến GA Nash

Để đánh giá hiệu quả của giải thuật cải tiến GA-Nash, luận văn tiến hành thử nghiệm trên một số bộ dữ liệu thực tế, mô phỏng các cuộc đấu thầu dự án công nghệ thông tin. Kết quả thử nghiệm cho thấy giải thuật cải tiến có khả năng tìm ra các chiến lược đấu thầu tối ưu, mang lại lợi ích cho cả nhà thầu và chủ đầu tư. Việc thử nghiệm cũng giúp xác định các tham số tối ưu cho giải thuật, cũng như các hạn chế và hướng cải thiện trong tương lai. Theo tác giả, tài liệu số [10] đã vận dụng các hàm chi phí trong [11] để xây dựng chương trình thử nghiệm nhưng việc mô hình hóa bài toán còn khá phức tạp, chương trình thử nghiệm bị cố định các tham số.

4.1. Mô Hình Hóa Bài Toán Đấu Thầu Nhiều Vòng

Để ứng dụng giải thuật cải tiến GA-Nash, cần xây dựng một mô hình toán học cho bài toán đấu thầu nhiều vòng, bao gồm các yếu tố như số lượng nhà thầu, số lượng vòng đấu, thông tin về chi phí và năng lực của các nhà thầu, và các quy định của cuộc đấu thầu. Mô hình hóa bài toán giúp đơn giản hóa các yếu tố phức tạp và tạo điều kiện cho việc áp dụng các kỹ thuật tối ưu.

4.2. Phân Tích Kết Quả Thử Nghiệm và Đánh Giá

Sau khi thử nghiệm giải thuật cải tiến, cần phân tích kết quả và đánh giá hiệu quả của giải thuật. Việc phân tích kết quả giúp xác định các chiến lược đấu thầu tối ưu, cũng như các yếu tố ảnh hưởng đến hiệu quả của cuộc đấu thầu. Đánh giá hiệu quả của giải thuật giúp xác định các hạn chế và hướng cải thiện trong tương lai.

4.3 Xây dựng ứng dụng với giải thuật GA NASH IMPROVED

Xây dựng ứng dụng với giải thuật GA-NASH-IMPROVED là một bước quan trọng trong quá trình triển khai và ứng dụng giải thuật vào thực tế. Ứng dụng giúp đơn giản hóa quá trình sử dụng giải thuật, cung cấp giao diện thân thiện cho người dùng và tích hợp các chức năng cần thiết. Qua đó, tạo ra một công cụ hỗ trợ đắc lực cho các nhà thầu và chủ đầu tư trong quá trình đấu thầu

V. Kết Luận Hướng Phát Triển Giải Thuật Cải Tiến

Luận văn này đã trình bày một giải thuật cải tiến ứng dụng cân bằng Nash và giải thuật di truyền (GA) để giải quyết bài toán đấu thầu nhiều vòng. Kết quả thử nghiệm cho thấy giải thuật có tiềm năng lớn trong việc nâng cao hiệu quả đấu thầu và mang lại lợi ích cho cả nhà thầu và chủ đầu tư. Trong tương lai, có thể tiếp tục nghiên cứu và phát triển giải thuật theo các hướng như tích hợp thêm các yếu tố rủi ro, áp dụng cho các loại đấu thầu khác nhau và xây dựng các công cụ hỗ trợ ra quyết định cho nhà thầu. Giải thuật 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 [4].

5.1. Tổng Kết Về Cải Tiến Thuật Toán và Kết Quả

Luận văn đã tập trung vào việc cải tiến thuật toán GA-Nash bằng cách tối ưu cấu trúc gen và nâng cao hàm thích nghi. Kết quả thử nghiệm cho thấy các cải tiến này đã giúp nâng cao hiệu quả của giải thuật, cho phép tìm ra các chiến lược đấu thầu tối ưu hơn so với các phương pháp truyền thống. Việc tổng kết về cải tiến thuật toán giúp rút ra các bài học kinh nghiệm và định hướng cho các nghiên cứu tiếp theo.

5.2. Hướng Phát Triển Tiềm Năng Của Giải Thuật Trong Tương Lai

Trong tương lai, giải thuật có thể được phát triển theo nhiều hướng khác nhau, chẳng hạn như tích hợp thêm các yếu tố rủi ro, áp dụng cho các loại đấu thầu khác nhau (ví dụ: đấu thầu trực tuyến, đấu thầu ngược), và xây dựng các công cụ hỗ trợ ra quyết định cho nhà thầu. Hơn nữa, việc nghiên cứu các phương pháp kết hợp giải thuật di truyền với các kỹ thuật tối ưu khác cũng có thể mang lại những kết quả tích cực. Việc xây dựng chương trình và thử nghiệm thuật toán để trợ giúp ra quyết định cho người quản trị dự án.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển kinh tế và quản lý dự án hiện đại, đấu thầu nhiều vòng trở thành một phương thức phổ biến nhằm tối ưu hóa chi phí và nâng cao hiệu quả đầu tư. Theo ước tính, các dự án công nghệ thông tin tại Việt Nam trong giai đoạn 2015-2020 đã áp dụng hình thức đấu thầu nhiều vòng với tổng kinh phí lên đến hàng chục tỷ đồng, đòi hỏi các giải pháp tối ưu trong lựa chọn nhà thầu. Vấn đề nghiên cứu trọng tâm của luận văn là xây dựng giải thuật cải tiến ứng dụng cân bằng Nash và giải thuật di truyền nhằm giải quyết bài toán đấu thầu nhiều vòng, đảm bảo hài hòa lợi ích giữa các bên tham gia, đồng thời tối ưu hóa chi phí và thời gian thực hiện dự án.

Mục tiêu cụ thể của nghiên cứu là mô hình hóa bài toán đấu thầu nhiều vòng dựa trên lý thuyết trò chơi và giải thuật di truyền, xây dựng giải thuật GA-Nash-Improved, thử nghiệm và đánh giá hiệu quả giải thuật trên các bộ dữ liệu thực tế và mô phỏng. Phạm vi nghiên cứu tập trung vào các dự án đấu thầu trong lĩnh vực công nghệ thông tin, đặc biệt là các dự án có nhiều giai đoạn đấu thầu với sự tham gia của nhiều nhà thầu.

Ý nghĩa của nghiên cứu được thể hiện qua việc cung cấp một công cụ hỗ trợ ra quyết định khoa học, giúp chủ đầu tư lựa chọn nhà thầu phù hợp, cân bằng lợi ích giữa các bên, giảm thiểu rủi ro và nâng cao hiệu quả đầu tư. Các chỉ số đánh giá hiệu quả như tỷ lệ lợi nhuận bên mời thầu dưới 10%, tỷ lệ lợi nhuận nhà thầu phù hợp với thực tế, và thời gian chạy thuật toán được cải thiện rõ rệt so với các phương pháp truyền thống.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai nền tảng lý thuyết chính: giải thuật di truyền (Genetic Algorithm - GA) và lý thuyết trò chơi với trọng tâm là cân bằng Nash (Nash Equilibrium).

• Giải thuật di truyền (GA): Là phương pháp tối ưu hóa dựa trên mô phỏng quá trình tiến hóa tự nhiên, sử dụng các toán tử chọn lọc, lai ghép và đột biến để tìm kiếm lời giải tối ưu trong không gian lớn. GA được áp dụng để giải quyết bài toán tối ưu đa mục tiêu với nhiều ràng buộc phức tạp, đặc biệt phù hợp với bài toán đấu thầu nhiều vòng có nhiều biến số và điều kiện.

• Lý thuyết trò chơi và cân bằng Nash: Lý thuyết trò chơi phân tích các tình huống cạnh tranh, trong đó kết quả phụ thuộc vào quyết định của tất cả người chơi. Cân bằng Nash là trạng thái mà không người chơi nào có thể cải thiện lợi ích của mình bằng cách đơn phương thay đổi chiến lược khi các người chơi khác giữ nguyên chiến lược. Trong bài toán đấu thầu, cân bằng Nash giúp xác định điểm hài hòa lợi ích giữa chủ đầu tư và các nhà thầu.

Các khái niệm chính bao gồm: nhiễm sắc thể (chromosome) trong GA, quần thể (population), hàm thích nghi (fitness function), các toán tử di truyền (chọn lọc, lai ghép, đột biến), trò chơi đồng thời và tuần tự, trò chơi có thông tin hoàn hảo và không hoàn hảo, trò chơi hợp tác và không hợp tác.

Phương pháp nghiên cứu

Nghiên cứu kết hợp phương pháp lý thuyết và thực nghiệm:

• Nguồn dữ liệu: Bao gồm dữ liệu mô phỏng và dữ liệu thực tế từ các dự án đầu tư ứng dụng công nghệ thông tin tại tỉnh Nghệ An giai đoạn 2015-2020, với tổng kinh phí dự kiến khoảng 36,9 tỷ đồng, thời gian thực hiện 48 tháng.

• Phương pháp phân tích: Mô hình hóa bài toán đấu thầu nhiều vòng dưới dạng bài toán tối ưu đa mục tiêu với các ràng buộc về thời gian, kinh phí, số lượng gói thầu và lợi ích các bên. Sử dụng giải thuật di truyền kết hợp cân bằng Nash (GA-Nash) để tìm lời giải tối ưu. Cải tiến cấu trúc gen và hàm thích nghi nhằm tăng tính linh hoạt và hiệu quả thuật toán.

• Timeline nghiên cứu: Quá trình nghiên cứu kéo dài trong năm 2017, bao gồm tổng hợp lý thuyết, xây dựng mô hình, phát triển giải thuật cải tiến, cài đặt chương trình ứng dụng, thử nghiệm trên bộ dữ liệu mô phỏng và thực tế, phân tích kết quả và đề xuất giải pháp.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả của giải thuật GA-Nash-Improved: Thuật toán cải tiến cho phép tìm ra điểm cân bằng Nash trong bài toán đấu thầu nhiều vòng với độ chính xác cao. Kết quả thử nghiệm trên bộ dữ liệu mô phỏng cho thấy tỷ lệ lợi nhuận bên mời thầu duy trì dưới 10%, tỷ lệ lợi nhuận nhà thầu phù hợp với thực tế (khoảng 3-5 lần so với bên mời thầu), đồng thời thời gian chạy thuật toán được rút ngắn đáng kể so với các phương pháp trước đây (từ 4-6 giờ xuống còn khoảng 20 phút đến vài giờ tùy cấu hình).

2. Cấu trúc gen cải tiến giúp giảm độ phức tạp: Việc mô hình hóa nhiễm sắc thể dựa trên thông tin gói thầu thay vì từng sản phẩm giúp giảm đáng kể độ dài chuỗi gen, từ đó giảm thời gian tính toán và tăng khả năng hội tụ của thuật toán.

3. Hàm thích nghi linh hoạt với các hằng số chuyên gia: Bổ sung các hệ số tin cậy của nhà thầu và các hằng số chuyên gia trong hàm fitness giúp thuật toán điều chỉnh phù hợp với từng loại dự án, nâng cao tính thực tiễn và độ chính xác của kết quả.

4. Đảm bảo các ràng buộc thực tế: Thuật toán tuân thủ nghiêm ngặt các ràng buộc về thời gian đấu thầu, số lượng gói thầu, lựa chọn nhà thầu phù hợp, đảm bảo tính khả thi và hiệu quả của kế hoạch đấu thầu.

Thảo luận kết quả

Kết quả nghiên cứu cho thấy sự kết hợp giữa giải thuật di truyền và cân bằng Nash là hướng đi hiệu quả trong giải quyết bài toán đấu thầu nhiều vòng, giúp cân bằng lợi ích giữa các bên tham gia. So với các nghiên cứu trước đây, giải thuật cải tiến đã khắc phục được nhược điểm về cấu trúc gen phức tạp và thời gian chạy dài, đồng thời bổ sung các yếu tố thực tiễn như hệ số tin cậy nhà thầu.

Dữ liệu thử nghiệm có thể được trình bày qua các bảng tổng hợp lợi nhuận, tỷ lệ chọn nhà thầu, và biểu đồ so sánh thời gian chạy thuật toán giữa các phương pháp. Ví dụ, bảng so sánh tỷ lệ lợi nhuận bên mời thầu và nhà thầu giữa các phương án thử nghiệm cho thấy sự ổn định và hợp lý của giải thuật cải tiến.

So sánh với các nghiên cứu khác, GA-Nash-Improved thể hiện ưu thế vượt trội về khả năng hội tụ toàn cục và tính linh hoạt trong điều chỉnh tham số, phù hợp với các dự án có quy mô và độ phức tạp cao. Ý nghĩa thực tiễn của nghiên cứu là cung cấp công cụ hỗ trợ ra quyết định khoa học, giảm thiểu rủi ro và tăng cường sự hài hòa trong quan hệ hợp tác giữa chủ đầu tư và nhà thầu.

Đề xuất và khuyến nghị

1. Áp dụng giải thuật GA-Nash-Improved trong các dự án đấu thầu nhiều vòng: Chủ đầu tư nên triển khai giải thuật này để tối ưu hóa kế hoạch đấu thầu, đảm bảo lợi ích hài hòa giữa các bên, giảm thiểu chi phí và rủi ro. Thời gian áp dụng có thể bắt đầu từ giai đoạn lập kế hoạch dự án.

2. Tăng cường thu thập và quản lý dữ liệu nhà thầu: Cần xây dựng hệ thống quản lý thông tin chi tiết về năng lực, lịch sử và hệ số tin cậy của nhà thầu để bổ sung vào hàm thích nghi, nâng cao độ chính xác của thuật toán. Chủ thể thực hiện là các cơ quan quản lý dự án và bộ phận đấu thầu.

3. Đào tạo và nâng cao năng lực cho cán bộ quản lý dự án: Tổ chức các khóa đào tạo về lý thuyết trò chơi, giải thuật di truyền và ứng dụng phần mềm hỗ trợ ra quyết định nhằm nâng cao hiệu quả sử dụng công cụ. Thời gian đào tạo nên được thực hiện định kỳ hàng năm.

4. Phát triển phần mềm ứng dụng tích hợp giải thuật: Xây dựng và hoàn thiện phần mềm ứng dụng giải thuật GA-Nash-Improved với giao diện thân thiện, khả năng tùy biến cao, hỗ trợ nhập liệu và phân tích kết quả nhanh chóng. Chủ thể thực hiện là các đơn vị công nghệ thông tin phối hợp với các chuyên gia đấu thầu.

5. Nghiên cứu mở rộng và cập nhật thuật toán: Tiếp tục nghiên cứu cải tiến thuật toán để xử lý các bài toán đấu thầu phức tạp hơn, tích hợp các yếu tố rủi ro, biến động thị trường và các chính sách pháp luật mới. Thời gian nghiên cứu nên được lên kế hoạch dài hạn, khoảng 3-5 năm.

Đối tượng nên tham khảo luận văn

1. Chủ đầu tư và quản lý dự án: Luận văn cung cấp công cụ và phương pháp khoa học giúp chủ đầu tư tối ưu hóa kế hoạch đấu thầu, lựa chọn nhà thầu phù hợp, cân bằng lợi ích và giảm thiểu rủi ro tài chính.

2. Các nhà thầu và nhà cung cấp: Thông qua việc hiểu rõ mô hình cân bằng Nash và giải thuật di truyền, nhà thầu có thể xây dựng chiến lược đấu thầu hiệu quả, nâng cao khả năng trúng thầu và duy trì mối quan hệ hợp tác lâu dài.

3. Chuyên gia và nhà nghiên cứu trong lĩnh vực công nghệ thông tin và quản lý dự án: Luận văn cung cấp cơ sở lý thuyết và phương pháp nghiên cứu ứng dụng giải thuật di truyền và lý thuyết trò chơi, mở ra hướng nghiên cứu mới trong tối ưu hóa quyết định phức tạp.

4. Cơ quan quản lý nhà nước và tổ chức đấu thầu: Tài liệu giúp các cơ quan này hiểu rõ hơn về các phương pháp khoa học trong tổ chức đấu thầu, từ đó xây dựng chính sách, quy trình đấu thầu minh bạch, hiệu quả và công bằng.

Câu hỏi thường gặp

1. Giải thuật GA-Nash-Improved có ưu điểm gì so với giải thuật di truyền truyền thống?
   Giải thuật GA-Nash-Improved kết hợp cân bằng Nash giúp tìm kiếm lời giải tối ưu trong môi trường cạnh tranh đa bên, tăng khả năng hội tụ toàn cục và giảm thiểu rủi ro hội tụ cục bộ, đồng thời cải tiến cấu trúc gen giúp giảm độ phức tạp và thời gian tính toán.

2. Làm thế nào để đảm bảo hài hòa lợi ích giữa chủ đầu tư và nhà thầu trong đấu thầu nhiều vòng?
   Bằng cách mô hình hóa bài toán dưới dạng trò chơi với cân bằng Nash, thuật toán tìm ra điểm cân bằng lợi ích, sao cho không bên nào có thể đơn phương cải thiện lợi ích mà làm tổn hại bên kia, tạo ra trạng thái win-win.

3. Phạm vi áp dụng của giải thuật này là gì?
   Giải thuật phù hợp với các dự án có nhiều giai đoạn đấu thầu, đặc biệt trong lĩnh vực công nghệ thông tin và các dự án có tính phức tạp cao về số lượng gói thầu và nhà thầu tham gia.

4. Thời gian chạy thuật toán có phù hợp với thực tế không?
   Nhờ cải tiến cấu trúc gen và hàm thích nghi, thời gian chạy thuật toán được rút ngắn đáng kể, từ vài giờ xuống còn khoảng 20 phút đến vài giờ tùy quy mô dự án, phù hợp với yêu cầu thực tiễn.

5. Có thể tùy chỉnh các tham số trong giải thuật không?
   Có, giải thuật cho phép điều chỉnh các hằng số chuyên gia, hệ số tin cậy nhà thầu và các tham số khác để phù hợp với từng loại dự án và điều kiện thực tế, giúp nâng cao tính linh hoạt và hiệu quả.

Kết luận

• Đã xây dựng thành công giải thuật cải tiến GA-Nash-Improved ứng dụng cân bằng Nash và giải thuật di truyền trong giải bài toán đấu thầu nhiều vòng.
• Giải thuật đáp ứng tốt các ràng buộc thực tế, cân bằng lợi ích giữa chủ đầu tư và nhà thầu, đồng thời tối ưu hóa chi phí và thời gian thực hiện dự án.
• Kết quả thử nghiệm trên dữ liệu mô phỏng và thực tế cho thấy hiệu quả vượt trội so với các phương pháp truyền thống về độ chính xác và thời gian chạy.
• Đề xuất áp dụng giải thuật trong thực tiễn, phát triển phần mềm hỗ trợ và tiếp tục nghiên cứu cải tiến để mở rộng phạm vi ứng dụng.
• Khuyến khích các chủ đầu tư, nhà thầu và cơ quan quản lý nghiên cứu, áp dụng để nâng cao hiệu quả đấu thầu và quản lý dự án.

Chủ đầu tư và các bên liên quan nên phối hợp triển khai thử nghiệm giải thuật trong các dự án thực tế, đồng thời tổ chức đào tạo và phát triển phần mềm ứng dụng để tối ưu hóa quy trình đấu thầu nhiều vòng.

Trích đoạn nội dung tài liệu

chương 1, tác giả trình bày các nghiên cứu lý thuyết về cân bằng Nash (NE), giải thuật di truyền (GA) và các vấn đề liên quan tới đấu thầu. Chương 2, mô tả bài toán đấu thầu nhiều vòng cùng một số đánh giá về phương pháp giải quyết bài toán đấu thầu nhiều vòng đã được nghiên cứu và thử nghiệm gần đây, và đề xuất giải pháp cải tiến. Chương 3, tác giả sẽ trình bày về phương pháp mô hình hóa bài toán, từ đó xây dựng giải thuật cải tiến GA-NASH IMPROVED và xây dựng chương trình ứng dụng, thử nghiệm và đánh giá kết quả thử nghiệm chương trình ứng dụng. Giải thuật di truyền 1.

Khái niệm Giải thuật 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 [4]. Trong giải thuật 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 hóa nhằm tạo ra các thế hệ tốt hơn. Mỗi cá thể lời giải được xem như một nhiễm sắc thể chứa các gen (thành phần của lời giải) có thể bị thay đổi. Quá trình tiến hóa được bắt đầu từ một quần thể ngẫu nhiên các cá thể và quá trình tiến hóa được tiến hành qua các thế hệ vòng lặp.

Trong mỗi thế hệ, độ thích nghi của mỗi cá thể được đánh giá lại và độ thích nghi thường được lấy từ giá trị hàm mục tiêu ban đầu. Quá trình lựa chọn cá thể để tiến hành lai ghép, đột biến là quá trình lựa chọn ngẫu nhiên dựa trên mức độ thích nghi của cá thể, từ đó hình thành nên thế hệ mới. Quá trình tiến hóa sẽ dừng lại khi đạt số thế hệ xác định hoặc thỏa mãn điều kiện dừng cho trước [4]. Giải thuật 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).

Mỗi gen mang một số đặc trưng và có vị trí nhất định trong NST. Mỗi NST sẽ biểu diễn một lời giải của bài toán. Toán tử và sơ đồ giải thuật di truyền 1. Các toán tử di truyền a.

Toán tử chọn lọc: Toán tử chọn lọc (hay tái sinh) thường là toán tử đầu tiên áp dụng trong một quần thể. Toán tử chọn lọc là hình thức chọn lọc cá thể tốt nhất và có dạng như một tổ hợp lai ghép. Ý tưởng ban đầu là chọn một cá thể có độ thích nghi trên trung bình rồi đưa vào tổ hợp lai ghép. Toán tử chọn lọc thường được sử dụng chính là để chọn lọc các cá thể có độ thích nghi phù hợp tương ứng với điều kiện đặt ra của bài toán.

Đầu tiên sẽ xác định độ thích nghi của từng cá thể trong quần thể ở thế hệ thứ t rồi lập bảng cộng dồn các giá trị thích nghi (theo thứ tự đã gán cho mỗi cá thể). Giả sử 4 rằng quần thể P có n cá thể. Gọi độ thích nghi của cá thể i tương ứng là fi, tổng cộng dồn thứ i là fti được xác định như sau: fti =  fi (1.1) Gọi F n là tổng độ thích nghi của toàn quần thể. Chọn một số ngẫu nhiên f trong khoảng 0 tới Fn.

Chọn cá thể thứ k đầu tiên thỏa mãn f ≥ ftk đưa vào quần thể mới. Toán tử lai ghép: Toán tử lai ghép là quá trình tạo mới được tiến hành tại bước tiếp theo sau khi chọn lọc cá thể thích hợp trong một quần thể bằng cách đưa vào tổ hợp lai ghép. Trong toán tử lai ghép có hai cá thể được chọn một cách ngẫu nhiên từ tổ hợp lai ghép. Toán tử lai ghép chính là quá trình tạo NST mới trên cơ sở các NST cha mẹ bằng cách ghép một đoạn trên NST cha mẹ với nhau được một cá thể mới để đưa vào quần thể [9].

Thế hệ cha mẹ: Thế hệ con: a b c d e f a b c j k l g h i j k l g h i d e f c. Toán tử đột biến: 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 sao cho 1 ≤ k ≤ m) sau đó 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. a b c d e f a b c m e f 5 Như ví dụ trên ta có thể thấy đã có ba đoạn mã di truyền bị thay đổi so với bản mã di truyền gốc và tạo ra một mã di truyền mới tương ứng với một cá thế mới trong quần thể.

Điều quan trọng đối với quần thể chính là nhu cầu đột biến để duy trì sự đa dạng trong quần thể. Các bước của giải thuật di truyền Một thuật toán là một tập các bước để giải quyết một vấn đề của bài toán. Một 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. Đó là một kỹ thuật 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ủa giải thuật di truyền bao gồm các bước được thể hiện bằng sơ đồ sau: Bắt đầu Khởi tạo quần thể ban đầu Tính giá trị thích nghi Chọn giải Y pháp tốt nhất Kết thúc N Sinh sản: chọn lọc, lai ghép, đột biến Hình 1.1: Sơ đồ cấu trúc giải thuật di truyền 6 Bước 1- Khởi tạo quần thể ban đầu: Khởi tạo quần thể ban đầu bằng việc qua chọn ngẫu nhiên n Nhiễm sắc thể (các lời giải phù hợp cho bài toán). Bước 2- Tính giá trị thích nghi: Đánh giá độ thích nghi f(x) cho mỗi nhiễm sắc thể (NST) x trong quần thể. Có thể tiến hành sắp xếp luôn các NST theo thứ tự độ thích nghi giảm dần. Bước 3- Chọn giải pháp tốt nhất: Kiểm tra điều kiện dừng của giải thuật, nếu đạt yêu cầu (Y) thì đưa ra giải pháp tốt nhất (lời giải phù hợp nhất được chọn); Nếu chưa đạt điều kiện dừng (N) thì tiến hành các bước sinh sản để tạo ra quần thể mới tốt hơn.

Bước 4- Sinh sản: Tạo một quần thể mới thông qua việc lặp lại các quá trình chọn lọc, lai ghép, đột biến,… cho đến khi quần thể mới được tạo ra. + Chọn lọc: Chọn hai cá thể bố mẹ từ quần thể ban đầu với độ thích nghi tương ứng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn). + Lai ghép: Với một xác suất lai ghép được chọn, lai ghép hai cá thể bố mẹ để tạo ra một cá thể mới. + Đột biến: Với một xác suất đột biến được chọn làm thay đổi một hay vài đoạn gen bất kỳ trên NST nhằm biến đổi cá thể mới.

Vòng lặp: Sau khi kết thúc quá trình sinh sản, một thế hệ mới được tạo ra, chúng ta lại tiến hành tính toán giá trị thích nghi của mỗi cá thể (Bước 2), rồi kiểm tra điều kiện dừng để chọn được lời giải tốt nhất (Bước 3), nếu chưa thỏa mãn điều kiện dừng thì sẽ tiến hành quá trình sinh sản để tạo ra thế hệ mới (Bước 4). Như vậy, các Bước 2-3-4 được lặp lại cho tới khi đạt được điều kiện dừng của thuật toán (tức là tìm được được giải pháp phù hợp nhất với hàm thích nghi). Hàm mục tiêu và điều kiện dừng của thuật toán 1. Hàm mục tiêu Sau khi hoàn thành quá trình lai ghép chéo tạo ra các thế hệ mới nhằm duy trì và tạo sự đa dạng trong quần thể thì cần phải tính lại độ thích nghi cho từng cá thể mới hình thành.

Số lượng các cá thể trong quần thể tăng lên qua lai ghép và độ thích nghi giữa các cá thể không có sự chênh lệch đáng kể. Do đó, các cá thể có độ thích nghi cao chưa hẳn chiếm ưu thế trong thế hệ tiếp theo. Vì vậy, cần ấn định tỷ lệ đối với hàm thích nghi nhằm nâng cao khả năng cho các nhiễm sắc thể đạt độ thích nghi cao hay chính là đánh giá chất lượng lời giải cho bài toán. Có ba cơ chế định tỷ lệ 7 trong hàm thích nghi là: định tỷ lệ tuyến tính, phép cắt Sigma, định tỷ lệ cho luật dạng lũy thừa.

Sau đó áp dụng phương pháp lựa chọn Roulette để chọn lọc các cá thể có độ thích nghi phù hợp. Lúc này những cá thể có độ thích nghi phù hợp với điều kiện bài toán sẽ được lưu lại còn các cá thể có độ thích nghi thấp sẽ bị loại bỏ [9]. Điều kiện dừng của thuật toán Thuật toán di truyền có hai điều kiện dừng cơ bản. Các điều kiện này sử dụng các đặc trưng tìm kiếm để quyết định ngừng quá trình tìm kiếm.

Điều kiện dừng thứ nhất là dựa trên cấu trúc NST do sự hội tụ của quần thể bằng cách kiểm soát số gen được hội tụ tức các gen này có giá trị trùng với số lượng quần thể định trước đó nhưng nếu nó vượt quá số phần trăm của tổng số gen đó thì việc tìm kiếm sẽ kết thúc [9]. Điều kiện dừng thứ hai là dựa vào ý nghĩa đặc biệt của một NST bằng cách đo độ tiến bộ của giải thuật trong một số thế hệ trước nếu nhỏ hơn một hằng số xác định thì thuật toán sẽ kết thúc [9]. Lý thuyết trò chơi và mô hình cân bằng Nash 1. Lý thuyết trò chơi 1.

Khái niệm Lý thuyết trò chơi là một nhánh của toán học ứng dụng được sử dụng để phân tích các tình huống cạnh tranh mà kết quả không phụ thuộc vào sự lựa chọn của một bên hay còn là cơ hội lựa chọn của các người chơi khác. Bởi vậy, kết quả sẽ phụ thuộc vào quyết định của tất cả người chơi, trong đó mỗi người chơi sẽ cố gắng dự đoán sự lựa chọn của những người chơi còn lại để có thể đưa ra lựa chọn tốt nhất cho mình. Lý thuyết trò chơi là một ngành chuyên nghiên cứu về việc đưa ra quyết định chiến lược.