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 trong giải bài toán đấu thầu nhiều vòng

- HỒ THỊ LỢI 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 TRONG GIẢI BÀI TOÁN ĐẤU THẦU NHIỀU VÒNG CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS.
- Giải thuật di truyền.
- Toán tử và sơ đồ giải thuật di truyền.
- Lý thuyết trò chơi.
- Đấu thầu và các vấn đề liên quan.
- Đấu thầu nhiều vòng.
- 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.
- Mô tả bài toán.
- Mô hình hóa bài toán.
- Lựa chọn giải thuật.
- Giải bài toán tối ưu với giải thuật di truyền.
- Kết hợp cân bằng Nash và giải thuật di truyền.
- Phân tích kết quả giải thuật đề xuất trong tài liệu [10.
- Cải tiến hàm thích nghi của thuật toán.
- 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.
- Xây dựng giải thuật cải tiến GA-NASH-IMPROVED.
- Khởi tạo quần thể ban đầu của thuật toán.
- Tính toán các hàm lợi ích và giá trị thích nghi.
- Xây dựng ứng dụng với giải thuật GA-NASH-IMPROVED.
- Thử nghiệm ứng dụng.
- Phân tích kết quả thử nghiệm.
- Đánh giá kết quả thử nghiệm.
- 87 v DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT KÍ HIỆU Tiếng Anh Tiếng Việt GA Genetic algorithm Giải thuật di truyền NE Nash Equilibrium Cân bằng Nash NST Chromosome Nhiễm sắc thể Game Theory Lý thuyết trò chơi vi DANH MỤC BẢNG BIỂU Bảng 1.1: Biểu diễn trò chơi dạng chiến lược.
- 29 Bảng 2.2: Kết quả thử nghiệm giải thuật trong [10] phương án 1.
- 33 Bảng 2.3: Kết quả thử nghiệm giải thuật trong [10] phương án 2.
- 34 Bảng 2.4: Kết quả thử nghiệm giải thuật trong [10] phương án 3.
- 34 Bảng 3.1: Bảng hằng số chuyên gia cho hàm thích nghi.
- 72 vii DANH MỤC HÌNH VẼ Hình 1.1: Sơ đồ cấu trúc giải thuật di truyền.
- 41 Hình 3.3: Sơ đồ chức năng chương trình Tư vấn đấu thầu.
- 63 Hình 3.15: Kết quả thử nghiệm 2.
- Lý do chọn đề tài Quy chế Đấu thầu ra đời (năm 1996) và sau đó là Luật Đấu thầu (năm 2006) đã đánh dấu một bước tiến mới trong công tác quản lý của nước ta.
- Thực hiện đấu thầu sẽ tạo được sự công bằng và cạnh tranh giữa các nhà thầu, hạn chế tiêu cực trong việc lựa chọn đơn vị thực hiện và qua đó giảm được chi phí đầu tư, mang lại hiệu quả cho dự án.
- Trong đấu thầu nói riêng và trong mọi lĩnh vực đời sống nói chung thì mọi người đều mong muốn được “công bằng”.
- Trên thực tế, 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, ai ai cũng hài lòng, mối quan hệ hợp tác giữa các bên luôn luôn hữu hảo thì vẫn đang là một bài toán khó.
- Xuất phát từ thực tế này, tác giả đề xuất hướng nghiên cứu cho luận văn với tên đề tài “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 trong giải bài toán đấu thầu nhiều vòng”.
- Tác giả thực hiện đề tài này với mong muốn đóng góp thêm một mô hình, một hỗ trợ cho các nhà đầu tư và cả các nhà cung cấp trong việc trong việc tìm ra điểm cân bằng (hài hòa lợi ích giữa các bên) khi thực hiện dự án đấu thầu, đặc biệt là đấu thầu nhiều vòng.
- Trong quá trình nghiên cứu thực hiện đề tài của mình, tác giả đã bắt gặp một số ý tưởng giải quyết bài toán đấu thầu nhiều vòng tương tự hướng nghiên cứu của mình như tài liệu số [10] và tài liệu số [11].
- Trong đó, tài liệu số [11] mới chỉ dừng ở mức 2 độ tính toán các hàm chi phí của dự án đấu thầu nhiều vòng mà chưa mô hình hóa và chưa có chương trình thử nghiệm.
- 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ố (không cho phép người sử dụng được tùy biến cho phù hợp với từng loại dự án đấu thầu.
- Vì vậy, 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 (các đánh giá và đề xuất sẽ được mô tả chi tiết tại chương 2).
- Mục đích nghiên cứu Luận văn nghiên cứu các vấn đề lý thuyết liên quan tới đề tài (cân bằng Nash, giải thuật di truyền, đấu thầu.
- Tiếp theo là mô hình hóa bài toán đấu thầu nhiều vòng, xây dựng và thử nghiệm giải thuật cải tiến giải quyết bài toán này dựa trên cân bằng Nash và giải thuật di truyền.
- Từ đó đưa ra các gợi ý trong việc lựa chọn các nhà thầu cho từng gói thầu phù hợp, đảm bảo lợi ích hài hòa nhất giữa các bên, sao các bên tham gia đàm phán đấu thầu cùng hài lòng và hợp tác lâu dài.
- Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của luận văn là ứ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.
- Phạm vi nghiên cứu được đề cập tới là đấu thầu dự án nói chung và đấu thầu dự án công nghệ thông tin nói riêng.
- Phương pháp nghiên cứu Kết hợp nghiên cứu lý thuyết và xây dựng ứng dụng để thử nghiệm, đánh giá kết quả thực nghiệp.
- Thứ hai là mô hình hóa, ứng dụng giải thuật di truyền và cân bằng Nash vào việc giải quyết bài toán.
- Ý nghĩa khoa học và thực tiễn của đề tài Đề tài đề xuất một giải thuật cải tiến ứng dụng giải thuật di truyền (GA) và cân bằng Nash (trong lý thuyết trò chơi - Game Theory) vào việc mô hình hóa bài toán đấu thầu nhiều vòng (Multi-round Bidding Problem).
- Mô hình này nếu được nghiên cứu thành công và được áp dụng vào thực tiễn sẽ là một công cụ hỗ trợ hữu dụng cho việc ra quyết định trong đấu thầu dự án nói chung và đấu thầu dự án công nghệ thông tin (phần mềm) nói riêng.
- Nội dung chính của luận văn Luận văn được chia ra làm ba chương cụ thể như sau: Trong 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.1.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.
- 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).
- Toán tử và sơ đồ giải thuật di truyền 1.1.2.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ử 5 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 = ∑𝑡𝑗=1 fi (1.1) Gọi Fn là tổng độ thích nghi của toàn quần thể.
- 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].
- 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 6 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.
- 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: Hình 1.1: Sơ đồ cấu trúc giải thuật di truyền Bắt đầu Kết thúc Tính giá trị thích nghi Khởi tạo quần thể ban đầu Chọn giải pháp tốt nhất Sinh sản: chọn lọc, lai ghép, đột biến Y N 7 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.
- 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).
- 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ệ 8 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.
- Đ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 1.2.1.1.
- 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

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