Tài liệu 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

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ----------------------------- 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. HUỲNH QUYẾT THẮNG Hà Nội, 2017 i LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi trong đó có sự giúp đỡ rất lớn của Thầy hướng dẫn PGS.TS Huỳnh Quyết Thắng và Thầy Ths. Trịnh Bảo Ngọc. Các nội dung nghiên cứu, số liệu và kết quả nêu trong luận văn là trung thực, rõ ràng. Trong luận văn, tôi có tham khảo đến một số tài liệu đã được liệt kê tại phần Tài liệu tham khảo ở cuối luận văn, các nội dung trích dẫn đã ghi rõ nguồn gốc. Hà Nội, ngày 26 tháng 4 năm 2017 Tác giả Hồ Thị Lợi i LỜI CẢM ƠN Trước tiên, tôi xin được bày tỏ lòng biết ơn sâu sắc tới Thầy, PGS.TS Huỳnh Quyết Thắng và Thầy Ths. Trịnh Bảo Ngọc đã dành thời gian quý báu, tận tình hướng dẫn, chỉ bảo và góp ý cho tôi trong suốt quá trình thực hiện luận văn tốt nghiệp. Tôi xin chân thành cảm ơn các Thầy giáo, Cô giáo trong Viện Công nghệ thông tin và Truyền thông đã tham gia giảng dạy tôi trong quá trình học tập tại Trường. Các thầy cô đã tận tình giảng dạy, truyền đạt kiến thức, tạo tiền đề cho tôi hoàn thành luận văn. Xin được cảm ơn sự giúp đỡ nhiệt tình của các Thầy giáo, Cô giáo trong Viện Đào tạo Sau đại học – Trường Đại học Bách Khoa Hà Nội. Cuối cùng, tôi xin chân thành cảm ơn các bạn bè, đồng nghiệp và nhất là gia đình tôi đã quan tâm và tạo mọi điều kiện tốt nhất, động viên, cổ vũ tôi trong suốt quá trình học tập và nghiên cứu để hoàn thành tốt luận văn tốt nghiệp này. Xin trân trọng cảm ơn! Hà Nội, ngày 26 tháng 4 năm 2017 Tác giả Hồ Thị Lợi ii MỤC LỤC DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT ................................................v DANH MỤC BẢNG BIỂU ...................................................................................... vi DANH MỤC HÌNH VẼ ........................................................................................... vii MỞ ĐẦU .....................................................................................................................1 CHƯƠNG 1. CƠ SỞ LÝ THUYẾT ........................................................................4 1.1. Giải thuật di truyền ................................................................................. 4 1.1.1. Khái niệm ..................................................................................................4 1.1.2. Toán tử và sơ đồ giải thuật di truyền .......................................................4 1.1.3. Hàm mục tiêu và điều kiện dừng của thuật toán ......................................7 1.2. Lý thuyết trò chơi và mô hình cân bằng Nash ........................................ 8 1.2.1. Lý thuyết trò chơi ......................................................................................8 1.2.2. Ứng dụng lý thuyết trò chơi trong kinh tế ..............................................15 1.2.3. Cân bằng Nash trong lý thuyết trò chơi .................................................17 1.3. Đấu thầu và các vấn đề liên quan ......................................................... 19 1.3.1. 1.3.2. 1.3.3. 1.3.4. 1.3.5. 1.4. Khái niệm ................................................................................................19 Các hình thức lựa chọn nhà thầu, nhà đầu tư ........................................20 Các phương thức lựa chọn nhà thầu, nhà đầu tư ...................................21 Các hình thức triển khai gói thầu ...........................................................22 Đấu thầu nhiều vòng ...............................................................................23 Tiểu kết chương 1 ................................................................................. 24 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 .................................................................25 2.1. 2.2. 2.3. Mô tả bài toán ....................................................................................... 25 Mô hình hóa bài toán ............................................................................ 27 Lựa chọn giải thuật ............................................................................... 28 2.3.1. Giải bài toán tối ưu với giải thuật di truyền ...........................................28 2.3.2. Kết hợp cân bằng Nash và giải thuật di truyền ......................................29 2.4. Tìm hiểu, đánh giá những nghiên cứu đã tiến hành trước đây ............. 30 2.4.1. Mô hình gen ............................................................................................30 2.4.2. Chọn lọc và sinh sản ...............................................................................31 2.4.3. Các hàm lợi ích, hàm mục tiêu và điều kiện dừng .................................31 2.4.4. Phân tích kết quả giải thuật đề xuất trong tài liệu [10] .........................33 iii 2.4.5. Nhận xét đánh giá ...................................................................................35 2.5. Đề xuất các cải tiến cần thực hiện ........................................................ 35 2.5.1. Cải tiến cấu trúc gen của thuật toán ......................................................35 2.5.2. Cải tiến hàm thích nghi của thuật toán ..................................................36 2.5.3. Cải thiện tính toán để tăng tốc độ chạy chương trình ............................36 2.6. Tiểu kết chương 2 ................................................................................. 36 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 ........................................37 3.1. 3.2. Sơ đồ thuật toán GA-Nash-Improved ................................................... 37 Xây dựng giải thuật cải tiến GA-NASH-IMPROVED ........................ 40 3.2.1. Xác định cấu trúc gen từ các ràng buộc của bài toán ............................40 3.2.2. Khởi tạo quần thể ban đầu của thuật toán .............................................42 3.2.3. Tính toán các hàm lợi ích và giá trị thích nghi ......................................43 3.2.4. Kiểm tra điều kiện dừng của thuật toán .................................................49 3.2.5. Chọn lọc và sinh sản ...............................................................................49 3.3. Xây dựng ứng dụng với giải thuật GA-NASH-IMPROVED ............... 52 3.3.1. Mô hình hóa chức năng ứng dụng ..........................................................52 3.3.2. Thiết kế CSDL .........................................................................................54 3.3.3. Thiết kế giao diện chương trình ứng dụng .............................................58 3.4. Thử nghiệm ứng dụng ........................................................................... 64 3.4.1. Thu thập dữ liệu ......................................................................................64 3.4.2. Phân tích, mô phỏng dữ liệu vào ............................................................64 3.4.3. Phân tích kết quả thử nghiệm .................................................................69 3.5. Đánh giá kết quả thử nghiệm ................................................................ 73 KẾT LUẬN ...............................................................................................................74 TÀI LIỆU THAM KHẢO .........................................................................................77 PHỤ LỤC ..................................................................................................................78 PL1. Thông tin tóm tắt, số liệu thực tế Dự án đầu tư ứng dụng CNTT trong hoạt động các cơ quan Đảng tỉnh Nghệ An giai đoạn 2015-2020 .........................................78 PL2. Chính sách giá của các nhà thầu (giả lập) cho Dự án đầu tư ứng dụng CNTT trong hoạt động các cơ quan Đảng tỉnh Nghệ An giai đoạn 2015-2020 ..............87 iv 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 v DANH MỤC BẢNG BIỂU Bảng 1.1: Biểu diễn trò chơi dạng chiến lược ..........................................................10 Bảng 1.2: Trò chơi có cân bằng Nash ......................................................................18 Bảng 2.1: Bảng so sánh kết quả các phương pháp kết hợp GA ................................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 ..........................................48 Bảng 3.2: Bảng mô tả BenMoiThau ..........................................................................54 Bảng 3.3: Bảng mô tả GoiThau ................................................................................55 Bảng 3.4: Bảng mô tả VatLieu ..................................................................................55 Bảng 3.5: Bảng mô tả VatlieuGoithau ......................................................................55 Bảng 3.6: Bảng mô tả GoiThauNhaThau .................................................................56 Bảng 3.7: Bảng mô tả LoaiHinh ...............................................................................56 Bảng 3.8: Bảng mô tả NhaThau ................................................................................56 Bảng 3.9: Bảng mô tả User .......................................................................................57 Bảng 3.10: Bảng giá vật liệu của các nhà thầu ........................................................57 Bảng 3.11: Bảng phụ mô tả VLDN ...........................................................................57 Bảng 3.12: Form mô tả thông tin gói thầu/vật liệu/hạng mục của bên mời thầu .....59 Bảng 3.13: Form mô tả thông tin gói thầu/vật liệu/hạng mục của các nhà thầu .....61 Bảng 3.14: Bảng tổng hợp kết quả thử nghiệm 1 .....................................................69 Bảng 3.15: Bảng tổng hợp kết quả thử nghiệm 2 .....................................................72 vi DANH MỤC HÌNH VẼ Hình 1.1: Sơ đồ cấu trúc giải thuật di truyền .............................................................6 Hình 1.2: Biểu diễn trò chơi dạng mở rộng ..............................................................10 Hình 1.3: Trò chơi thông tin hoàn hảo .....................................................................13 Hình 1.4: Trò chơi thông tin không hoàn hảo ..........................................................14 Hình 2.1: Mô tả chuỗi gen trong [10] ......................................................................30 Hình 3.1: Sơ đồ thuật tooán GA-Nash-Improved .....................................................37 Hình 3.2: Mô tả cấu trúc gen trong thuật toán cải tiến ............................................41 Hình 3.3: Sơ đồ chức năng chương trình Tư vấn đấu thầu ......................................52 Hình 3.4: Thiết kế CSDL chương trình ứng dụng .....................................................54 Hình 3.5: Giao diện trang chủ ..................................................................................58 Hình 3.6: Đăng ký bên mời thầu ...............................................................................58 Hình 3.7: Đăng nhập bên mời thầu ..........................................................................59 Hình 3.8: Đăng ký dự án mới ....................................................................................59 Hình 3.9: Quản lý thông tin dự án ............................................................................60 Hình 3.10: Tạo và quản lý danh sách nhà thầu ........................................................60 Hình 3.11: Đăng ký nhà thầu ....................................................................................61 Hình 3.12: Chạy chương trình tìm kiếm gợi ý ..........................................................62 Hình 3.13: Nhập các tham số dự án cần tìm gợi ý ...................................................62 Hình 3.14: Giao diện kết quả chạy chương trình .....................................................63 Hình 3.15: Kết quả thử nghiệm 2 ..............................................................................70 vii MỞ ĐẦU 1. 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. Nó tạo ra một hành lang pháp lý cho việc lựa chọn được các nhà thầu để thực hiện các dự án đầu tư, đồng thời góp phần nâng cao vai trò của chủ đầu tư và tăng cường trách nhiệm của nhà thầu. 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. Qua thực hiện đấu thầu, chủ đầu tư có điều kiện lựa chọn được phương án có hiệu quả trong việc mua sắm hàng hoá, lựa chọn được nhà thầu có đủ kinh nghiệm và năng lực, có phương án kỹ thuật, biện pháp thi công tốt để thực hiện dự án, đảm bảo chất lượng của công trình. 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”. Trong đấu thầu, dù là cạnh tranh nhưng nếu đạt được điều kiện lý tưởng là các bên đều được hưởng lợi, ai cũng được hài lòng thì sẽ hạn chế được rất nhiều tiêu cực. 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 1 độ 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). 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. Mục đích là để tìm ra điểm cân bằng Nash (cân bằng mục tiêu, lợi ích của các bên tham gia dự á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; Cuối cùng là đánh giá thuật toán thông qua kết quả thử nghiệm với các số liệu dự án thực tế. 3. Đố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. 4. 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. Cụ thể như sau: Thứ nhất là các nghiên cứu lý thuyết sẽ được thực hiện trên cơ sở tổng hợp, phân tích thông tin từ các nghiên cứu liên quan; 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; Cuối cùng là 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. 2 5. Ý 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. 6. 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. 3 CHƯƠNG 1. CƠ SỞ LÝ THUYẾT 1.1. 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. 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. 1.1.2. 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ử 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 = ∑𝑡𝑗=1 fi (1.1) Gọi Fn 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. b. 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 5 b c m e f 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ể. 1.1.2.2. 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 pháp tốt nhất Y 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). 1.1.3. Hàm mục tiêu và điều kiện dừng của thuật toán 1.1.3.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]. 1.1.3.2. Đ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]. 1.2. Lý thuyết trò chơi và mô hình cân bằng Nash 1.2.1. Lý thuyết trò chơi 1.2.1.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. Lý thuyết trò chơi được mô tả như một lý thuyết trong toán học, nghiên cứu tình huống trong đó người chơi sẽ hành động theo các cách khác nhau để tối ưu hóa lợi ích của mình. Một vấn đề quan trọng là lý thuyết trò chơi chính là phương pháp tiếp cận để đưa ra các quyết định nhằm giải quyết một vấn đề nào đó. Điều này sẽ xác định xác suất thành công khi cho trước một không gian chiến lược. 8 Một số ý tưởng lý thuyết trò chơi được khởi nguồn từ thế kỷ thứ 18, nhưng cho đến những năm 1920 thì lý thuyết trò chơi mới có sự phát triển lớn qua nhà toán học John Von Neumann (1903-1957) . Một sự kiện quyết định trong sự phát triển của học thuyết này là việc xuất bản cuốn sách “ Lý thuyết trò chơi và hành vi kinh tế” [7] của Von Neumann và Oskar Morgenstern năm 1944. Trong những năm 1950, mô hình lý thuyết trò chơi bắt đầu được sử dụng trong lý thuyết kinh tế, khoa học chính trị và tâm lý học đã bắt đầu nghiên cứu về cách cư xử của con người trong các trò chơi thử nghiệm. Những năm 1970, lần đầu tiên lý thuyết trò chơi được sử dụng như một công cụ trong sinh học tiến hóa. Sau đó, lý thuyết trò chơi dần thống trị lý thuyết kinh tế vi mô, khoa học xã hội và hành vi khác [6]. Lý thuyết trò chơi được áp dụng sử dụng vào nhiều ngành, lĩnh vực như Chính trị học, Đạo đức học, Kinh tế… và đặc biệt là Khoa học máy tính ứng dụng trong Trí tuệ nhân tạo và Điều khiển học. Lý thuyết trò chơi dần đóng vai trò quan trọng trong logic và khoa học máy tính. Một số lý thuyết logic có cơ sở trong ngữ nghĩa trò chơi, mô phỏng các tính toán tương tác với nhau. 1.2.1.2. Biểu diễn trò chơi Các trò chơi được nghiên cứu, xem xét trong lý thuyết trò chơi là các đối tượng toán học được xác định rõ. Một trò chơi trong lý thuyết trò chơi cần được xác định đầy đủ các yếu tố như: người tham gia trò chơi; những thông tin và hành động có sẵn cho mỗi người chơi tại mỗi thời điểm quyết định (hay còn gọi là tập các chiến lược) và cơ chế thưởng phạt tương ứng với mỗi tổ hợp các chiến lược. Tất cả các yếu tố này thường được sử dụng với một khái niệm giải pháp lựa chọn để có thể suy ra một tập hợp các chiến lược cân bằng cho mỗi người chơi. Những chiến lược cân bằng xác định một trạng thái cân bằng của các trò chơi hay là một trạng thái ổn định, trong đó một trong hai kết quả xảy ra hoặc một loạt các kết quả xảy ra với xác suất đã biết. Thường có 2 cách phổ biến để biểu diễn trò chơi như sau: a) Biểu diễn trò chơi dạng chiến lược Biểu diễn trò chơi dưới dạng chiến lược là hình thức biểu diễn ma trận thưởng phạt cho các tình huống của người chơi. Dạng biểu diễn này là một dạng biểu diễn thông thường của trò chơi trong đó những người chơi sẽ đồng thời đưa ra lựa chọn 9 cho chiến lược của họ. Mức kết quả thưởng phạt được trình bày trong một bảng với mỗi một ô tương ứng là mỗi cặp chiến lược. Dạng biểu diễn này thích hợp trong trường hợp các người chơi đồng thời thực hiện quyết định mà không biết về hành động của người kia [6]. Bảng 1.1: Biểu diễn trò chơi dạng chiến lược Tù nhân B Tù nhân A Im lặng Đổ tội Im lặng 2-2 0-3 Đổ tội 3-0 1-1 Bảng 1.1 là một minh họa biểu diễn trò chơi dưới dạng chuẩn tắc cho bài toán nổi tiếng “Song đề tù nhân” trong đó mỗi tù nhân sẽ có hai chiến lược hoặc là “Im lặng” hoặc là “Đổ tội” cho đối phương. Đây là hai tù nhân trong một vụ án được đặt trong một ô riêng và ở đây không có đủ bằng chứng để buộc tội ai trong số họ. Trong trò chơi này thưởng phạt là những giá trị tiêu cực bởi nó đại diện cho số năm tù. Nếu cả hai tù nhân cùng im lặng thì họ sẽ phải nhận hai năm tù, còn nếu cả hai cùng đổ tội cho đối phương thì họ chỉ phải ngồi một năm tù. Tuy nhiên, nếu một trong số họ thú nhận trong khi người kia không, họ sẽ nhận được kết quả khác nhau là một người sẽ được trả tự do trong khi người còn lại sẽ phải ngồi ba năm tù [6]. b) Biểu diễn trò chơi dạng mở rộng Hình 1.2: Biểu diễn trò chơi dạng mở rộng 10 Trong lý thuyết trò chơi, dạng biểu diễn mở rộng là một dạng trò chơi sử dụng một cây trò chơi, là dạng biểu đồ cho biết lựa chọn này được thực hiện tại thời điểm khác nhau tương ứng với một nút. Các trò chơi dạng mở rộng được sử dụng để hợp thức hóa các trò chơi với một trình tự thời gian của các lượt đi. Các đoạn thẳng đi ra từ đỉnh đó biểu diễn các hành động có thể cho người chơi đó. Mức thưởng phạt được ghi rõ tại đáy cây. Các dạng mở rộng có thể được xem như là một sự tổng quát nhiều người chơi của một cây quyết định. Trò chơi biểu diễn dưới dạng mở rộng còn có thể mô tả các trò chơi đi đồng thời và các trò chơi với những thông tin không hoàn hảo. Để biểu diễn nó, sử dụng hoặc là một đườn chấm chấm nối hai đỉnh khác nhau hoặc một đường tròn vẽ quanh hai đỉnh khác nhau để biểu diễn rằng chúng đều thuộc cùng một tập hợp thông tin. 1.2.1.3. Các loại trò chơi a) Trò chơi đồng thời và trò chơi tuần tự Trò chơi đồng thời là dạng trò chơi mà các người chơi sẽ đồng thời thực hiện nước đi mà không biết nước đi cùng thời điểm của các đối thủ kia. Họ đồng thời đưa ra quyết định cùng lúc và thường được mô tả qua hình thức chơi chiến lược. Trạng thái cân bằng của trò chơi đạt khi cả hai cùng đưa ra quyết định hợp lý và không có lý do để họ có thể thay đổi quyết định đó. Một ví dụ điển hình cho loại trò chơi này chính là bài toán “Song đề tù nhân”. Trò chơi tuần tự là trò chơi mà những người chơi lần lượt thực hiện các nước đi sau khi đã biết được nước đi của các người chơi phía trước. Trong trò chơi tuần tự thì người chơi sau có một số thông tin về hành động của người chơi trước đó nhưng thông tin này không phải là thông tin đầy đủ về mọi hành động của người chơi trước đó. Chẳng hạn, người chơi 1 có thể biết rằng người chơi 2 đã thực hiện những hành động cụ thể nào trước đó nhưng người chơi đó lại không biết được những hành động có sẵn khác của người chơi 2. Trò chơi tuần tự thường được biểu diễn dưới dạng cây trò chơi, có trục thời gian và còn được gọi là trò chơi mở rộng. Trong khi đó, trò chơi 11 đồng thời lại được biểu diễn như một ma trận thưởng phạt, không có trục thời gian diễn ra và là một dạng của kiểu trò chơi chiến lược. b) Trò chơi đối xứng và bất đối xứng Trò chơi đối xứng là trò chơi mà phần lợi ích cho việc chơi một chiến thuật nào đó chỉ phụ thuộc vào chiến thuật được sử dụng chứ không phụ thuộc vào người nào đang chơi. Cơ chế thưởng phạt ứng với một chiến lược cụ thể nào đó thì chỉ phụ thuộc vào chiến thuật sử dụng. Nếu như tính danh của những người chơi có thể thay đổi mà không làm thay đổi phần lợi ích đối với chiến thuật chơi thì một trò chơi là đối xứng. Các bài toán song đề tù nhân, săn hươu… đều là các trò chơi đối xứng. Trò chơi bất đối xứng là trò chơi mà chiến thuật sử dụng cho mỗi người chơi là khác nhau. Đa số những trò chơi bất đối xứng được nghiên cứu là những trò chơi mà tập các chiến thuật khác nhau được sử dụng bởi hai người chơi. Ví dụ dạng trò chơi bất đối xứng như trò chơi tối hậu thư và trò kẻ độc tài,… bởi mỗi người chơi có các chiến lược khác nhau. Tuy nhiên, trong một số trường hợp trò chơi vẫn có chiến lược giống nhau cho cả hai người chơi nhưng vẫn là trò chơi bất đối xứng. c) Trò chơi có tổng bằng không và trò chơi có tổng khác không Trò chơi có tổng bằng không là trò chơi mà tổng điểm của các người chơi bằng không, số lợi ích của người này thu được bằng thiệt hại từ người chơi khác. Trò chơi tổng bằng không là một trường hợp đặc biệt của trò chơi tổng không đổi, trong đó sự lựa chọn của người chơi không làm thay đổi các nguồn lực có sẵn. Trong trò chơi này, mọi tổ hợp các chiến lược chơi, tổng điểm của tất cả các người chơi trong ván chơi luôn bằng không. Các loại trò chơi cổ điển như cờ tướng, cờ vua là một ví dụ của dạng trò chơi tổng bằng không. Trò chơi có tổng khác không là loại trò chơi mà khi lợi ích của người chơi không nhất thiết thu được từ thiệt hại của người chơi khác hay lợi ích của người chơi này không nhất thiết phải tương ứng với thiệt hại của người chơi kia. Có thể biến đổi một trò chơi bất kỳ thành một trò chơi tổng bằng không bằng cách bổ sung môt người chơi bù nhìn sao cho thiệt hại của người chơi bù nhìn này bù lại tổng thu hoạch của 12