zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Khoa học tự nhiên

Khóa luận tốt nghiệp đại học: Bài toán tối ưu đa mục tiêu và ứng dụng xây dựng chương trình lập thời khóa biểu

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:71

Báo xấu

8
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Khóa luận tốt nghiệp đại học "Bài toán tối ưu đa mục tiêu và ứng dụng xây dựng chương trình lập thời khóa biểu" trình bày các nội dung chính sau: Ứng dụng của giải thuật di truyền vào bài toán lập thời khóa biểu; Xây dựng chương trình lập thời khóa biểu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Khóa luận tốt nghiệp đại học: Bài toán tối ưu đa mục tiêu và ứng dụng xây dựng chương trình lập thời khóa biểu

UBND TỈNH QUẢNG NAM TRƯỜNG ĐẠI HỌC QUẢNG NAM KHOA: CÔNG NGHỆ THÔNG TIN ---------- NGUYỄN THỊ THÚY KIỀU BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ ỨNG DỤNG XÂY DỰNG CHƯƠNG TRÌNH LẬP THỜI KHÓA BIỂU KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC Quảng Nam, tháng 04 năm 2017
UBND TỈNH QUẢNG NAM TRƯỜNG ĐẠI HỌC QUẢNG NAM KHOA: CÔNG NGHỆ THÔNG TIN LỜI CẢM ƠN --------- Trên thực tế không có thành công nào mà không gắn liền với sự hỗ trợ, giúp đỡ dù ít hay nhiều, dù trực tiếp hay gián tiếp từ người khác. Thật vậy! Trong suốt thời gian thực hiện đề tài khóa luận của mình, tôi luôn nhận được sự quan tâm hướng dẫn, chỉ bảo tận tình từ Thầy giáo, Thạc sĩ Huỳnh Tấn NGHIỆP hoàn thành tốt luận KHÓA LUẬN TỐT Khải để có thể văn này. Tôi xin trân trọng gửi đến Thầy một lời cảm ơn sâu sắc! Tôi cũng xin chân thành cảm ơn quý Thầy, Cô khoa Công nghệ thông tin, trường Đại học Quảng Nam đã tận tình truyền đạt kiến thức cho tôi trong suốt bốn năm học tại trường. Với vốn kiến thức được tiếp thu trong quá trình học tập không chỉ là nền Tên đề tài: tảng cho quá trình nghiên cứu đề tài này mà còn là hành trang quý báu để tôi bước vào BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ ỨNG đời một cách vững chắc và tự tin. DỤNG XÂY DỰNG CHƯƠNG TRÌNH Tôi cũng thầm biết ơn sự ủng hộ của gia đình, bạn bè và những người thân yêu LẬP THỜI KHÓA BIỂU luôn là chỗ dựa tinh thần vững chắc cho tôi. Cuối cùng, tôi xin kính chúc quý Thầy, Cô dồi dào sức khỏe và thành công trong sự nghiệp trồng người cao quý. Sinh viên thực hiện: Trong quá trình thựcNGUYỄN THỊ tránh khỏi sai sót, rất mong quý Thầy, Cô hiện đề tài, khó THÙY KIỀU bỏ qua. Đồng thời do trình độ lý luận cũng như kinh nghiệm thực tiễn còn hạn chế nên MSSV: 2113021017 bài báo cáo không thể tránh khỏi những thiếu sót, rất mong nhận được ý kiến đóng góp CHUYÊN NGÀNH từ quý Thầy, Cô để tôi có thể học hỏi thêm được nhiều kinh nghiệm và sẽ hoàn thành CÔNG NGHỆ THÔNG TIN tốt hơn bài báo cáo sắp tới. KHÓA: 2013 – 2017 Xin chân thành cảm ơn! Cán bộ hướng dẫn ThS. HUỲNH TẤN KHẢI Quảng Nam, ngày 13 tháng 04 năm 2017 Sinh viên thực hiện Nguyễn Thị Thúy Kiều Quảng Nam, ngày 14 tháng 04 năm 2017
MỤC LỤC Phần 1. MỞ ĐẦU ...........................................................................................................1 1.1. Lí do chọn đề tài ................................................................................................1 1.2. Mục tiêu của đề tài .............................................................................................2 1.3. Đối tượng và phạm vi nghiên cứu......................................................................2 1.4. Phương pháp nghiên cứu ...................................................................................2 1.5. Đóng góp của đề tài ...........................................................................................2 1.6. Cấu trúc của đề tài..............................................................................................3 Phần 2. NỘI DUNG NGHIÊN CỨU ............................................................................4 Chương 1. CƠ SỞ LÝ THUYẾT .................................................................................4 1.1. Giới thiệu bài toán tối ưu tổng quát và phân loại ..............................................4 1.1.1. Giới thiệu bài toán tối ưu tổng quát ............................................................4 1.1.2. Phân loại các bài toán tối ưu .......................................................................5 1.2. Ứng dụng của lý thuyết tối ưu ...........................................................................7 1.2.1. Phương pháp mô hình hóa ..........................................................................7 1.2.2. Một số ứng dụng của lý thuyết tối ưu .........................................................7 1.3. Các phương pháp giải bài toán tối ưu đa mục tiêu ......................................... 10 1.3.1. Phương pháp ràng buộc (Constraint method) .......................................... 10 1.3.2. Phương pháp tổng trọng số ...................................................................... 11 1.3.3. Phương pháp sử dụng giải thuật di truyền (Genetic Alogithm – GA) ..... 13 1.4. Kết chương ...................................................................................................... 22 Chương 2. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN ............................................ 23 VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU ............................................................ 23 2.1. Tìm hiểu chung về bài toán lập thời khóa biểu ............................................... 23 2.1.1. Mô tả bài toán lập thời khóa biểu............................................................. 23 2.1.2. Các đối tượng của thời khóa biểu ............................................................ 24 2.1.3. Quy trình lập thời khóa biểu .................................................................... 25 2.2. Ứng dụng giải thuật di truyền vào bài toán lập thời khóa biểu....................... 25 2.2.1. Giai đoạn 1: Xếp lịch học các lớp ............................................................ 26 2.2.2. Giai đoạn 2: Xếp lịch học cho toàn bộ cơ sở ........................................... 33 2.3. Kết chương ...................................................................................................... 36 Chương 3: XÂY DỰNG CHƯƠNG TRÌNH LẬP THỜI KHÓA BIỂU ............... 37 3.1. Phân tích chức năng của hệ thống................................................................... 37 3.1.1. Biểu đồ phân cấp chức năng (FDD) ......................................................... 37 3.1.2. Mô tả chi tiết chức năng ........................................................................... 37 3.1.3. Danh sách các tác nhân ............................................................................ 39
3.1.4. Biểu đồ ca sử dụng (USECASE - UC)..................................................... 40 3.2. Xây dựng chức năng của hệ thống .................................................................. 41 3.2.1. Thu thập thông tin tài nguyên .................................................................. 41 3.2.2. Xây dựng chức năng ................................................................................ 43 3.3. Một số giao diện hệ thống ............................................................................... 46 3.3.1. Giao diện chính của hệ thống ................................................................... 46 3.3.2. Giao diện giới thiệu hệ thống ................................................................... 47 3.3.3. Giao diện các ràng buộc Giáo viên .......................................................... 48 3.3.4. Giao diện các ràng buộc Lớp học ............................................................ 48 3.3.5. Giao diện các ràng buộc chung về Khóa học ........................................... 49 3.3.6. Giao diện in danh sách giáo viên ............................................................. 50 3.3.7. Giao diện trang in thời khóa biểu cho giáo viên ...................................... 50 3.3.8. Giao diện thiết lập các ràng buộc cho Giáo viên ..................................... 52 3.3.9. Giao diện thiết lập thông tin ..................................................................... 52 3.3.10. Giao diện thiết lập tiết dạy được/ không được phép xếp thời khóa biểu . 53 3.3.11. Giao diện xếp thời khóa biểu tự động ...................................................... 54 3.3.12. Giao diện trang in thời khóa biểu chính ................................................... 54 Phần 3. KẾT LUẬN VÀ KIẾN NGHỊ ...................................................................... 56 1. Kết luận .............................................................................................................. 56 2. Kiến nghị ............................................................................................................ 56 Phần 4. TÀI LIỆU THAM KHẢO............................................................................ 57
DANH MỤC HÌNH ẢNH Hình 1.1 - Các giả thiết của bài toán ............................................................................ 10 Hình 1.2 - Kết quả (giải bằng thuật toán PRIM) .......................................................... 10 Hình 1.3 - Sơ đồ khối của giải thuật di truyền ............................................................. 17 Hình 1.4 - Toán tử Chéo hóa áp dụng cho chuỗi số nguyên hoán vị. .......................... 18 Hình 1.5 - Toán tử chéo hóa áp dụng cho chuỗi nhị phân. .......................................... 18 Hình 1.6 - Toán tử Chéo hóa áp dụng cho chuỗi hoán vị............................................. 18 Hình 1.7 - Toán tử chéo hóa áp dụng cho chuỗi hoán vị ............................................. 19 Hình 1.8 - Toán tử chéo hóa áp dụng cho chuỗi hoán vị ............................................. 19 Hình 1.9 - Đột biến 2 gen gần nhau.............................................................................. 20 Hình 1.10 - Đột biến 2 gen cách xa nhau ..................................................................... 20 Hình 1.11 - Đột biến 3 gen cách xa nhau ..................................................................... 20 Hình 1.12 - Đột biến đảo ngược chuỗi con .................................................................. 21 Hình 1.13 - Đột biến bằng cách dịch chuyển ............................................................... 21 Hình 2.1 - Quy trình lập thời khóa biểu ....................................................................... 25 Hình 2.2 - Mô hình cá thể trong lịch lớp học ............................................................... 26 Hình 2.3 - Phân bổ các nhiễm sắc thể môn học ........................................................... 28 Hình 2.4 - Bảng phân bố các môn học trên lịch học .................................................... 29 Hình 2.5 - Lai ghép tạo ra 2 cá thể con từ 2 nhiễm sắc thể cha – mẹ........................... 31 Hình 2.6 - Xác suất xảy ra đối với phép đột biến ......................................................... 33 Hình 2.7 - Mô hình cá thể lịch cơ sở ............................................................................ 34 Hình 3.1 - Biểu đồ phân cấp chức năng hệ thống lập thời khóa biểu .......................... 37 Hình 3.2 - Ký hiệu của ca sử dụng ............................................................................... 41 Hình 3.3 - Biểu đồ ca sử dụng của hệ thống Lập thời khóa biểu ................................. 41 Hình 3.4 - Giao diện chính của hệ thống ...................................................................... 47 Hình 3.5 - Giao diện giới thiệu hệ thống ...................................................................... 48 Hình 3.6 - Giao diện ràng buộc chung cho Giáo viên .................................................. 48 Hình 3.7 - Giao diện các ràng buộc chung cho Lớp học .............................................. 49 Hình 3.8 - Giao diện các ràng buộc chung về Khóa học .............................................. 50
Hình 3.9 - Giao diện in danh sách giáo viên ................................................................ 50 Hình 3.10 - Giao diện trang in thời khóa biểu cho giáo viên ....................................... 51 Hình 3.11 - Giao diện thiết lập các ràng buộc cho Giáo viên ...................................... 52 Hình 3.12 - Giao diện thiết lập thông tin ...................................................................... 53 Hình 3.13 - Giao diện thiết lập tiết dạy được/ không được phép xếp thời khóa biểu .. 53 Hình 3.14 - Giao diện xếp TKB tự động ...................................................................... 54 Hình 3.15 - Giao diện trang in thời khóa biểu chính ................................................ 55
[Document title] Phần 1. MỞ ĐẦU 1.1. Lí do chọn đề tài Trong cuộc sống, ta thường bắt gặp các bài toán liên quan đến xếp lịch như xếp lịch công tác, xếp lịch giảng dạy, xếp lịch học cho học sinh - sinh viên, xếp lịch biểu cho các ca trực ở một bệnh viện, xếp lịch làm việc, xếp lịch vận hành máy móc,… Đối với loại bài toán này cần phải tìm ra một phương án xếp lịch thỏa mãn tất cả các ràng buộc cũng như khai thác hiệu quả các nguồn tài nguyên hiện có, giảm thời gian và chi phí thực hiện. Bài toán xếp thời khóa biểu trong các trường học là một trong những bài toán như vậy. Có rất nhiều các ràng buộc được đặt ra trong bài toán này như ràng buộc về đối tượng tham gia (giảng viên, lớp học, sinh viên), ràng buộc về tài nguyên phục vụ giảng dạy (phòng học lý thuyết, phòng thực hành,…), ràng buộc về thời gian (số tiết học, số lần học, số tiết mỗi lần học,…), ràng buộc về chuyên môn và rất nhiều các ràng buộc khác tùy thuộc vào từng trường. Vấn đề đặt ra là cần xây dựng một thời khóa biểu thỏa mãn tất cả các ràng buộc trên đồng thời khai thác hiệu quả các nguồn tài nguyên phục vụ giảng dạy. Thời khóa biểu của trường học là kế hoạch giảng dạy của giáo viên và học tập của học sinh - sinh viên. Một bảng thời khóa biểu hợp lý giúp giáo viên thuận tiện khi lên lớp và người học thoải mái khi đăng ký môn học học tập. Bài toán xếp thời khóa biểu là một bài toán không mới và đã có nhiều giải thuật được đưa ra để giải quyết như giải thuật nhánh cận, giải thuật leo đồi, giải thuật luyện thép, giải thuật tô màu đồ thị, giải thuật xấp xỉ,… Tuy nhiên các giải thuật này thường không có tính tổng quát và chỉ áp dụng hiệu quả đối với các trường học có quy mô nhỏ, ít ràng buộc về mặt dữ liệu. Vì vậy, việc đòi hỏi có một giải thuật chất lượng cao và sử dụng kỹ thuật trí tuệ nhân tạo đặc biệt rất cần thiết khi giải quyết các bài toán có không gian tìm kiếm lớn. Ở Việt Nam hiện nay, các trường đại học đang dần chuyển sang hình thức đào tạo tín chỉ. Mặc dầu hình thức đào tạo này có nhiều ưu điểm hơn so với đào tạo niên chế tuy nhiên việc xếp thời khóa biểu vẫn là một gánh nặng thực sự cho các trường, đặc biệt là các trường có quy mô đào tạo lớn. Vả lại trên thị trường cũng chưa có sản phẩm phần mềm nào giải quyết hiệu quả bài toán trên. Trong những năm gần đây, phương pháp tiếp cận di truyền đã thu hút rất nhiều sự chú ý trong các lĩnh vực nghiên cứu khác nhau trong đó có khoa học máy tính. Phương pháp này có nhiều đặc điểm nổi trội như không đòi hỏi tri thức, tránh tối ưu cục bộ, thực hiện tốt với các bài toán có không gian lời giải lớn và có thể áp dụng cho GVHD: Th.S Huỳnh Tấn Khải 1
[Document title] nhiều loại bài toán tối ưu khác nhau. Trên thế giới, giải thuật di truyền kết hợp với tin học được ứng dụng để giải quyết những bài toán tối ưu một cách rất hiệu quả. Vì vậy, việc nghiên cứu và ứng dụng giải thuật di truyền (Genetic Algorithm - GA) để giải quyết hiệu quả bài toán xếp thời khóa biểu nói trên là việc làm hết sức cần thiết. Xuất phát từ những thực tế trên đây, tôi đã chọn đề tài “Bài toán tối ưu đa mục tiêu và ứng dụng xây dựng chương trình lập thời khóa biểu” cho bài khóa luận tốt nghiệp của mình; với mong muốn giúp mọi người có một cái nhìn toàn diện hơn về giải thuật GA cũng như những ứng dụng đa dạng của nó, đồng thời giúp người dùng có thêm một lựa chọn nữa trong việc tìm kiếm phần mềm hỗ trợ xây dựng lịch học, thời khóa biểu. 1.2. Mục tiêu của đề tài Đề tài tập trung nghiên cứu và ứng dụng giải thuật di truyền vào bài toán xếp thời khóa biểu nhằm đưa ra phương án xếp thời khóa biểu thỏa mãn tất cả các ràng buộc đặt ra, đồng thời khai thác hiệu quả các nguồn lực đào tạo của nhà trường với thời gian ngắn nhất có thể. 1.3. Đối tượng và phạm vi nghiên cứu - Đối tượng nghiên cứu: Nghiên cứu các đặc điểm, đặc trưng của giải thuật di truyền, các thành phần cơ bản của giải thuật di truyền như khởi tạo quần thể ban đầu, đánh giá độ thích nghi của cá thể, các toán tử di truyền (chọn lọc, lai ghép, đột biến), điều kiện dừng. - Phạm vi nghiên cứu: Ứng dụng giải thuật di truyền vào bài toán xếp thời khóa biểu cho trường học các cấp với các ràng buộc và những yêu cầu cơ bản đặt trước. 1.4. Phương pháp nghiên cứu  Phương pháp nghiên cứu lý thuyết: - Nghiên cứu tài liệu, ngôn ngữ và công nghệ liên quan. - Tổng hợp các tài liệu lý thuyết về giải thuật di truyền. - Thu thập thông tin, nghiên cứu thực trạng. - Tham khảo sách, báo và các nguồn tài liệu từ Internet. - Tham khảo ý kiến từ giảng viên hướng dẫn đề tài.  Phương pháp nghiên cứu thực nghiệm: - Phân tích và thiết kế hệ thống xếp thời khóa biểu theo quy trình xây dựng ứng dụng phần mềm. - Xây dựng hệ thống xếp thời khóa biểu sử dụng giải thuật di truyền. - Thử nghiệm hệ thống và đánh giá kết quả đạt được dựa trên bộ dữ liệu thử nghiệm ở một trường học. 1.5. Đóng góp của đề tài GVHD: Th.S Huỳnh Tấn Khải 2
[Document title] - Cung cấp một nền tảng ứng dụng bài toán tối ưu hóa đa mục tiêu. Có thể nói đây là một ứng dụng thiết thực và có tính ứng dụng cao. Ứng dụng của nó sẽ làm phong phú thêm cho kho ứng dụng lập thời khóa biểu, giúp người dùng có thêm nhiều lựa chọn và những trải nghiệm tốt nhất. - Phần mềm này sẽ giúp cho người dùng lập thời khóa biểu một cách nhanh chóng và hiệu quả. - Với đề tài này tôi mong muốn cung cấp một tài liệu tham khảo cho các bạn sinh viên trong khoa cũng như ngoài khoa khi tiếp cận và tìm hiểu về lĩnh vực nghiên cứu ứng dụng của bài toán tối ưu hóa đa mục tiêu và nhất là lĩnh vực mà tôi đang nghiên cứu. 1.6. Cấu trúc của đề tài Cấu trúc của bài luận văn này bao gồm các phần: Lời cảm ơn, Mục lục, Phần mở đầu, Phần nội dung nghiên cứu, Phần kết luận và Phần tái liệu tham khảo. Trong đó phần Nội dung nghiên cứu sẽ gồm các nội dung chính như sau: Chương 1: Cơ sở lý thuyết. Chương này sẽ nghiên cứu trình bày các nội dung về cơ sở lý thuyết làm nền tảng cho các phần nghiên cứu tiếp theo của đề tài. Chương 2: Ứng dụng của giải thuật di truyền vào bài toán lập thời khóa biểu. Trong chương này chủ yếu tìm hiểu sâu sắc hơn về lý thuyết và thuật toán của giải thuật di truyền, sau đó phân tích ứng dụng của giải thuật đi truyền vào bài toán lập thời khóa biểu. Chương 3: Xây dựng chương trình lập thời khóa biểu. Chương cuối cùng trong phần Nội dung nghiên cứu này sẽ đi phân tích và xây dựng chức năng của hệ thống lập thời khóa biểu đồng thời giới thiệu một số giao diện chính của chương trình. GVHD: Th.S Huỳnh Tấn Khải 3
[Document title] Phần 2. NỘI DUNG NGHIÊN CỨU Chương 1. CƠ SỞ LÝ THUYẾT 1.1. Giới thiệu bài toán tối ưu tổng quát và phân loại 1.1.1. Giới thiệu bài toán tối ưu tổng quát a) Giới thiệu Lý thuyết tối ưu là một trong những lĩnh vực kinh điển của toán học có ảnh hưởng nhiều đến lĩnh vực kinh tế xã hội và khoa học công nghệ. Phương án tối ưu là phương án khả thi và tốt nhất, tức là phương án làm cho hàm mục tiêu đạt kết quả nhỏ nhất (min) hoặc lớn nhất (max) và phải thỏa mãn các điều kiện, yêu cầu của bài toán (gọi là thỏa mãn các điều kiện ràng buộc). Trong mô hình toán học, mục tiêu của bài toán được biểu diễn bởi hàm: f(x) → min (hoặc f(x) → max) (1.1) với x là một biến số rời rạc hoặc một biến kiểu vector x = (x1, x2,…, xn). Xét một cách tổng quát, chúng ta xem biến x là một biến vector, trường hợp x là biến số rời rạc tương ứng với vector chỉ có một thành phần. Biến x tổng quát có dạng x = (x1, x2,…, xn) thường có yêu cầu phải thỏa mãn một số điều kiện nào đó. Tập hợp các điều kiện của các biến thì được gọi là điều kiện ràng buộc và được biểu diễn bởi miền D (miền ràng buộc): x∈D (1.2) Yêu cầu tổng quát của bài toán tối ưu là tìm bộ giá trị của x để thỏa mãn điều kiện ràng buộc (1.2) và làm cực tiểu/ cực đại hàm mục tiêu (1.1). x* (một bộ các giá trị cụ thể của (x1, x2,…, xn)) thỏa mãn điều kiện (1.1) và (1.2) gọi là phương án tối ưu. Nếu x chỉ thỏa mãn điều kiện (1.2) thì ta gọi x là phương án chấp nhận được hay là phương án. b) Các ví dụ minh họa Ví dụ 1.1: Tìm x sao cho: f(x) = x3 – 3x +1 → max (1.3) với: x ∈ D = [-2,2; 1,8] (1.4) Bài giải: ∀ ∈ [-2,2; 1,8] là một phương án chấp nhận được ⟺ -2,2 ≤ x ≤ 1,8. Bài toán trên tương đương với bài toán tìm giá trị lớn nhất (GTLN) của hàm f(x) khi -2,2 ≤ x ≤ 1,8. Phương pháp tìm GTLN (đã học trong Giải tích 1) thực hiện như sau: GVHD: Th.S Huỳnh Tấn Khải 4
[Document title]  Tìm các cực trị của hàm f(x), tính các giá trị cực trị, tính các giá trị tại các đầu mút của miền D, sau đó so sánh để tìm ra giá trị lớn nhất (hay nhỏ nhất). Để tìm các điểm cực trị, ta tìm các giá trị của hàm f(x) ứng với các giá trị của x sao cho đạo hàm f '(x) = 0. Tính f(x) tại các điểm dừng. Tìm f (-2,2); f (1,8). Vậy f '(x) = 3x2 - 3 = 0 ⟺ x = ± 1 f (1) = -1 f (-1) = 3 f (-2,2) = -3,048 f (1,8) = 1,432 Do đó: fmax = 3 khi x* = -1 Ví dụ 1.2: Tìm phương án tối ưu của bài toán: Z = → max (1.5) Điều kiện ràng buộc được xác định từ điều kiện xác định (tập xác định) của hàm Z, tức là a2 – x2 – y2 ≥ 0, hay miền ràng buộc của bài toán là: x2 + y2 ≤ a2 (1.6) Tìm phương án tối ưu cho công thức (1.5) là bài toán tìm cực trị của hàm hai biến. Phương pháp giải: Dùng phương pháp tìm cực trị hàm hai biến. Z 0 0 Tìm điểm dừng: Z 0 0 → Có 1 điểm dừng M (0,0) Ta có: đạt giá trị lớn nhất khi ( đạt giá trị lớn nhất. Ta lại có: = ) => Z đạt giá trị lớn nhất khi đạt giá trị nhỏ nhất và đạt giá trị nhỏ nhất khi x = y =0 Như vậy hàm Z đạt cực đại tại điểm M (0,0). => Phương án tối ưu (x*, y*) = (0,0) và Zmax = Z (0,0) = a (Bài toán tối ưu có thể không có điều kiện ràng buộc, bất kỳ giá trị nào của x hoặc vector x cũng là một phương án chấp nhận được. Vậy chỉ cần tìm x bất kỳ sao cho f(x) → min (hoặc f(x) → max) là có thể đáp ứng được yêu cầu của bài toán. Có thể điều kiện ràng buộc được xác định trong hàm mục tiêu là miền xác định của hàm mục tiêu). 1.1.2. Phân loại các bài toán tối ưu GVHD: Th.S Huỳnh Tấn Khải 5
[Document title] Một trong những phương pháp thông dụng nhất để giải bài toán tối ưu đó là: Tính giá trị hàm mục tiêu f(x) trên tất cả các phương án, sau đó so sánh các giá trị tính được để tìm ra giá trị tối ưu và phương án tối ưu cho bài toán. Thực hiện theo phương pháp trên gặp rất nhiều khó khăn ngay cả khi kích thước của bài toán (số biến n và số ràng buộc m) là không lớn, bởi vì tập D thông thường gồm một số rất lớn các phần tử, trong nhiều trường hợp còn là không đếm được. Vì vậy, người ta đã nghiên cứu về mặt lý thuyết để có thể tách ra từ bài toán tổng quát thành các lớp bài toán đơn giản hơn, dễ thực hiện hơn. Các nghiên cứu lý thuyết đó thường là: - Nghiên cứu tính chất của các thành phần bài toán (hàm mục tiêu, các hàm ràng buộc, các biến số, các hệ số, …). - Các điều kiện tồn tại lời giải chấp nhận được. - Các điều kiện cần và đủ của cực trị. - Tính chất của các đối tượng nghiên cứu. Bài toán tối ưu hay còn gọi là bài toán quy hoạch. Dựa vào tính chất của các thành phần bài toán và đối tượng nghiên cứu người ta phân loại các lớp bài toán tối ưu như sau:  Bài toán tối ưu tuyến tính: Là bài toán mà hàm mục tiêu và tất cả các ràng buộc đều có dạng tuyến tính. Một cách khái quát: Hàm mục tiêu: f(x) → min (hoặc f(x) → max) là một hàm tuyến tính Và tất cả các ràng buộc: gi (x), với i = 1, cũng là một hàm tuyến tính.  Bài toán tối ưu phi tuyến: Bài toán mà trong đó hàm mục tiêu hoặc ít nhất một điều kiện ràng buộc là phi tuyến (có chứa ít nhất một yếu tố phi tuyến – bậc 2, logic, mũ, …).  Bài toán tối ưu rời rạc: Khi biến hoặc giá trị hàm mục tiêu là rời rạc. Chúng ta có thể chia bài toán tối ưu rời rạc thành hai dạng như sau:  Tối ưu nguyên (quy hoạch nguyên): Các biến hoặc các hàm mục tiêu nhận các giá trị nguyên.  Tối ưu đồ thị: Là một dạng đặc biệt của bài toán tối ưu rời rạc, có các đỉnh là các điểm rời rạc. Trong đồ thị, chúng ta kí hiệu tập đỉnh là: X = {A, B, C, D}, tập cạnh là E = {e1, e2, …, e8} hoặc biểu diễn tập cạnh thông qua tập đỉnh: E = {(A, D); (A, B); … }. Bài toán tối ưu đồ thị trở thành bài toán tìm đường đi ngắn nhất của đồ thị thỏa mãn điều kiện nào đó. GVHD: Th.S Huỳnh Tấn Khải 6
[Document title]  Bài toán quy hoạch động: Dạng bài toán này thường thì những kết quả của bước sau phụ thuộc vào kết quả của bước trước.  Bài toán tối ưu đa mục tiêu: Bài toán mà trong đó có nhiều hàm mục tiêu cần phải tối ưu trên cùng một miền ràng buộc. fi(x) → min (hoặc fi(x) → (max)) với i = 1, 2, …, n; x ∈ D Trong đó có nhiều hàm mục tiêu có thể đối lập nhau. Khi giải bài toán này, chúng ta phải kết hợp hài hòa các lợi ích (giá trị) đạt được của hàm mục tiêu. 1.2. Ứng dụng của lý thuyết tối ưu 1.2.1. Phương pháp mô hình hóa Trên thực tế, nhiều vấn đề ở các lĩnh vực kinh tế, khoa học - công nghệ và xã hội đều có thể giải quyết bằng phương pháp tối ưu toán học. Bởi lẻ người ta luôn mong muốn tìm ra các sản phẩm tốt nhất mà vẫn tiết kiệm được thời gian, công sức, chi phí, đường đi,... Điều quan trọng là từ thực tế, ta phải xây dựng được một mô hình toán học thích hợp. Từ đó, chúng ta sử dụng các phương pháp tối ưu cùng với các công cụ thích hợp để cho ra lời giải tối ưu nhất. Để làm được những điều này, chúng ta cần lưu ý các bước sau đây khi áp dụng phương pháp mô hình hóa: Bước 1: Khảo sát vấn đề thực tế, phát hiện vấn đề cần giải quyết bằng phương pháp tối ưu. Bước 2: Phát biếu các điều kiện ràng buộc và hàm mục tiêu dưới dạng định tính. Bước 3: Lựa chọn các biến đại diện cho các tham số và sau đó định lượng hóa các điều kiện ràng buộc và hàm mục tiêu. Từ đó xây dựng mô hình định lượng và mô hình toán học (mô hình tối ưu). Bước 4: Thu thập số liệu và lựa chọn phương pháp toán học thích hợp để giải mô hình. Bước 5: Xây dựng thuật toán và quy trình giải: Lựa chọn công cụ (giấy bút, máy tính) có thể lập trình cho bài toán ấy. Bước 6: Đánh giá kết quả thu được: Nếu phương pháp vừa xây dựng là phù hợp thực tế thì nó cho kết quả tối ưu và điều này cũng chứng tỏ mô hình mà chúng ta xây dựng là đúng và hợp lý. Nếu nó không phù hợp thực tế thì phải xem xét và điều chỉnh mô hình. 1.2.2. Một số ứng dụng của lý thuyết tối ưu Ứng dụng của lý thuyết tối ưu vô cùng phong phú và đa dạng. Tuy nhiên, tùy vào mỗi trường hợp cụ thể và tùy vào cách thức vận dụng sao cho hợp lý, hiệu quả thì ứng GVHD: Th.S Huỳnh Tấn Khải 7
[Document title] dụng của lý thuyết tối ưu mới mang lại kết quả như mong muốn. Ở đây, ta sẽ chỉ tiến hành xét một số ví dụ điển hình dẫn đến mô hình tối ưu. GVHD: Th.S Huỳnh Tấn Khải 8
[Document title] Ví dụ 1.3: Bài toán phân phối điện năng. Có ba hộ gia đình cần được cung cấp điện từ hai nguồn điện cách xa nhau. Giá thành truyền tải một đơn vị điện năng (hao tổn + chi phí bảo dưỡng đường dây, trạm) từ nguồn thứ i (i = 1, 2) đến hộ thứ j (j = 1, 2, 3) là Cij. Khả năng cung cấp của mỗi nguồn điện bị giới hạn bởi trữ lượng của chúng là A1, A2. Nhu cầu của các hộ tiêu thụ cần phải đáp ứng đủ là B1, B2, B3. Hãy lập kế hoạch phân phối điện năng khả thi sao cho tổng chi phí truyền tải là nhỏ nhất. Lời giải: Mô hình toán học được lập như sau: Giả thiết: Điều kiện cân bằng thu-phát: ∑ =∑ á Tức là: ∑ =∑ Đặt biến x là lượng điện chuyển từ trạm cung cấp thứ i đến hộ tiêu thụ thứ j. Ta có: x ≥ 0; i = 1, 2; j = 1, 2, 3 (điều kiện các biến không âm). Từ đó suy ra, tổng chi phí truyền tải: ∑ ∑ Vậy hàm mục tiêu sẽ là: f(x) = ∑ ∑ → min (1.7) Điều kiện ràng buộc: Tổng lượng điện từ trạm 1: 11 12 13 1 Tổng lượng điện từ trạm 2: 21 22 23 2 Tổng lượng điện của hộ 1: 11 21 1 Tổng lượng điện của hộ 2: 12 22 2 Tổng lượng điện của hộ 3: 13 23 3 Điều kiện không âm của biến : 11, 12 , . . . , 23 0 (1.8) Bài toán tối ưu tuyến tính chính là bài toán tìm các giá trị (1.7) để thỏa mãn các điều kiện (1.8). Ví dụ 1.4: Bài toán xây dựng hệ thống truyền tải điện. Một huyện (X0) có 5 xã X1, X2, X3, X4, X5. Huyện này cần xây dựng hệ thống truyền tải điện từ trung tâm huyện đến tất cả các xã. Giữa hai địa điểm có thể thay đổi được đường dây với chi phí được cho trong Hình 1.1. Hãy lập các phương án xây dựng hệ thống điện có thể nối liền các xã vào huyện với tổng chi phí là nhỏ nhất. GVHD: Th.S Huỳnh Tấn Khải 9
[Document title] Hình 1.1 - Các giả thiết của bài toán Đây là một bài toán tối ưu trên đồ thị được giải bằng thuật toán PRIM, KRUSKAL. Hình 1.2 - Kết quả (giải bằng thuật toán PRIM) Ta có : Sơ đồ đường dây cần xây dựng tối ưu như Hình 1.2, tổng chi phí đầu tư nhỏ nhất : fmin = 15. 1.3. Các phương pháp giải bài toán tối ưu đa mục tiêu 1.3.1. Phương pháp ràng buộc (Constraint method) a) Mô tả bài toán Cho bài toán đa mục tiêu với p mục tiêu, như sau: min {f1(x), f2(x),…, fp(x)} (1.11) Sao cho: x ∈ Rn Trong đó: x = (x1, x2,…, xn) ∈ Rn là không gian quyết định. Ta chuyển bài toán trên thành nhiều bài toán ràng buộc đơn mục tiêu như sau: GVHD: Th.S Huỳnh Tấn Khải 10
[Document title] fk (x1, x2, x3,…, xn) ≥ Lk (k = 1, …, p) (1.12) Công thức này là bài toán đơn mục tiêu. Do đó có thể giải được bằng các phương pháp giải bài toán đơn mục tiêu. Sau khi có các tối ưu cho từng hàm fk, chúng ta có thể tìm giá trị tối ưu nhất từ tập các giá trị tối ưu của các fk. b) Thuật toán Bước 1: Xây dựng bảng thỏa hiệp. - Giải lần lượt p bài toán đơn mục tiêu và các ràng buộc tương ứng. Gọi nghiệm ứng với mục tiêu thứ k là: xk = ( , , …, ) với k = 1,…, p. Sau đó tính giá trị của k p hàm mục tiêu này đạt được tại các x tương ứng, ta gọi là: f1( ), f2( ), …, fp( ). - Sắp xếp p giá trị ứng với p mục tiêu vừa tính được ở trên vào bảng. Ở đây, hàng ứng với các x1,…, xk và cột là nhãn của mục tiêu. Bảng 1.1. Bảng thoả hiệp cho một bài toán với p hàm mục tiêu f1 (xk) f2 (xk) … fp (xk) x1 f1 (x1) f2 (x1) … fp (x1) x2 f1 (x2) f2 (x2) … fp (x2) … … … … … xk f1 (xk) f2 (xk) … fp (xk) - Tìm số lớn nhất và nhỏ nhất trong cột thứ k, lần lượt kí hiệu là Mk, mk với k = 1, …, p. Bước 2: Quy ước một bài toán quy hoạch đa mục tiêu được cho ở (1.11) tương ứng với bài toán ràng buộc của nó như ở (1.12). Bước 3: Chọn giá trị của Lk trong đoạn [mk, Mk] bằng cách chia [mk,Mk] ra r phần bằng nhau. Lk có thể nhận một trong r giá trị sau: Lk = mk + (Mk - mk) , với: t = 0,1,…., r – 1 Bước 4: Ứng với mỗi giá trị của Lk ta giải bài toán (1.12) và mỗi bài toán cho một nghiệm chấp nhận được. Trong những nghiệm này ta chọn nghiệm tốt nhất. 1.3.2. Phương pháp tổng trọng số a) Các khái niệm tối ưu Tối ưu Pareto: Một điểm x* ∈ X được gọi là một nghiệm tối ưu Pareto nếu không tồn tại một nghiệm x ≠ x* ∈ X mà x trội hơn x*. Nghĩa là: f(x) < f(x*). Từ định nghĩa trên suy ra các tính chất sau: i) Nếu x* là nghiệm tối ưu Pareto thì ƒ(x∗) gọi là điểm hữu hiệu. GVHD: Th.S Huỳnh Tấn Khải 11
[Document title] ii) Nếu x1, x2 ∈ X và ƒ(x1) ≤ ƒ(x2) thì ta gọi x1 trội hơn x2 và ƒ(x1) trội hơn ƒ(x2). iii) Tập tất cả các nghiệm tối ưu Pareto x * ∈ X và tập các điểm hữu hiệu y= ƒ(x*) ∈ Y lần lượt ký hiệu là: Xpar và Yeff Nghiệm tối ưu Pareto chặt và yếu: Nghiệm x *∈ X được gọi là một nghiệm tối ưu yếu Pareto nếu không tồn tại một nghiệm x ∈ X sao cho: ƒ(x) ≪ ƒ(x*) Khi đó: Điểm y = ƒ(x*) ∈ Y gọi là điểm hữu hiệu yếu. Tập nghiệm tối ưu Pareto yếu và tập các điểm hữu hiệu yếu lần lượt ký hiệu là: và Nghiệm x * ∈ X được gọi là một nghiệm tối ưu chặt Pareto nếu không tồn tại một nghiệm x ∈ X và x ≠ x* sao cho: ƒ(x) ≤ ƒ(x*). Khi đó, tập nghiệm tối ưu Pareto chặt ký hiệu là: Xs–par b) Mô tả bài toán Bài toán tối ưu nhiều mục tiêu dạng tổng quát được phát biểu như sau: min {f1(x), f2(x),…, fp(x)} Sao cho: x ∈ Rn Trong đó: x = (x1, x2, …, xn) ∈ Rn : là không gian nghiệm. Ta chuyển bài toán trên thành bài toán tổng như sau: min f = w1 f1 (x) + w2f2 (x) + ⋯ + wpfp (x) Sao cho: x ∈ Rn Trong đó: wi ≥ 0, với: i = 1, 2,…, n. và: ∑ i 1 Ứng với mỗi bộ trọng số wi ta sẽ tìm được một nghiệm tối ưu Pareto. c) Ví dụ minh họa Ví dụ 1.5: Giải bài toán tối ưu hai hàm mục tiêu sau: , , , , với: , =3 − 2x1x2 + 4x2 + , = − x1 − x1x2 + 0.5 Sau khi thực hiện các bước tính toán ta xác định được giá trị của mỗi hàm mục tiêu như sau: GVHD: Th.S Huỳnh Tấn Khải 12
[Document title] Bảng 1.2. Bảng các hàm mục tiêu w = (w1, w2) (0,1) (0.2, 0.8) (0.4, 0.6) (0.6, 0.4) (0.8, 0.2) (1,0 , 6 -2.2 -4.45 2.53 -0.76 -6 , - 0,5 0.11 0.3 1.97 -0.88 3.5 1.3.3. Phương pháp sử dụng giải thuật di truyền (Genetic Alogrithm – GA) a) Giới thiệu giải thuật Giải thuật di truyền (Genetic Algorithm - GA) được đề xuất bởi ý tưởng của John Holland vào những năm 1970. Lấy cảm hứng từ quá trình chọn lọc một cách ngẫu nhiên các cá thể thông qua sự tác động của môi trường tự nhiên. Nếu cá thể nào có mức độ thích nghi cao với sự tác động này thì chúng sẽ tiếp tục sống sót, ngược lại chúng sẽ bị loại bỏ. Ý tưởng này đã được áp dụng để giải quyết các bài toán tối ưu một mục tiêu bằng cách làm xấp xỉ các nghiệm thành biên Pareto từ một số nghiệm khởi tạo ban đầu. Tuy nhiên từ thực tế số lượng hàm mục tiêu cần tối ưu tăng lên rất nhiều - ít nhất là hai mục tiêu và thường thì các mục tiêu này xung đột nhau như: Bài toán lựa chọn danh mục đầu tư tối ưu nhiều mục tiêu người ta cố gắng làm cực đại lợi nhuận thu được trong khi giảm thiểu rủi ro đến mức thấp nhất có thể hay bài toán trong sản xuất ta cố gắng làm cực tiểu số lượng nhân công nhưng giá trị sản lượng vẫn đạt cực đại. Như vậy, việc tìm một phương án hay nghiệm thỏa mãn tất cả các mục tiêu đặt ra như trên xem ra rất lý tưởng, nhưng trên thực tế có rất ít bài toán tồn tại phương án lý tưởng này. Do đó, ta chuyển sang tìm một phương án khả thi khác mà ta gọi là phương án thỏa hiệp. Phương án thỏa hiệp sẽ thỏa mãn các mục tiêu đặt ra ở một mức độ có thể chấp nhận được. Trên cơ sở này người ta cố gắng áp dụng thuật toán di truyền để giải quyết các loại bài toán này và thuật toán di truyền đa mục tiêu cũng xuất hiện trên cơ sở này. Cho đến nay có rất nhiều thuật toán di truyền để giải bài toán tối ưu đa mục tiêu dựa trên cơ sở thuật toán di truyền đã ra đời, chẳng hạn như thuật toán MOGA, thuật toán NSGA, thuật toán NSGA II,... Thông qua các thuật toán này ta có thể làm xấp xỉ được biên Pareto tốt nhất từ các nghiệm khởi tạo ban đầu. Giải thuật di truyền (hay giải thuật tiến hóa nói chung) là một trong những phát triển quan trọng của những nhà nghiên cứu về tính toán ứng dụng cuối thế kỷ trước trong việc giải xấp xỉ các bài toán tối ưu toàn cục. Việc khai thác nguyên lí tiến hóa như là một định hướng heuristics đã giúp cho giải thuật di truyền giải quyết hiệu quả các bài toán tối ưu (với các lời giải chấp nhận được) mà không cần sử dụng các điều kiện truyền thống (liên tục hay khả vi) như là điều kiện tiên quyết. GVHD: Th.S Huỳnh Tấn Khải 13
[Document title] Giải thuật di truyền là một giải thuật mô phỏng theo quá trình chọn lọc tự nhiên, là kỹ thuật chung giúp giải quyết các vấn đề bài toán bằng cách mô phỏng sự tiến hóa của con người hay của sinh vật nói chung (dựa trên thuyết tiến hóa muôn loài của Darwin) trong điều kiện qui định sẵn của môi trường. Lấy ý tưởng từ quá trình tiến hoá tự nhiên, xuất phát từ một lớp các lời giải tiềm năng ban đầu, GA tiến hành tìm kiếm trên không gian lời giải bằng cách xây dựng lớp lời giải mới tốt hơn (tối ưu hơn) lời giải cũ. Quá trình xây dựng lớp lời giải mới được tiến hành dựa trên việc chọn lọc, lai ghép, đột biến từ lớp lời giải ban đầu. Quần thể lời giải trải qua quá trình tiến hoá: Ở mỗi thế hệ lại tái sinh các lời giải tương đối tốt, trong khi các lời giải “xấu” thì chết đi. Một trong những đặc tính quan trọng của giải thuật di truyền là làm việc theo quần thể các giải pháp. Việc tìm kiếm bây giờ được thực hiện song song trên nhiều điểm (multipoints). Trong GA, một tập các biến của bài toán đưa ra được mã hóa sang một chuỗi (hay một cấu trúc mã hóa khác) tương tự như một nhiễm sắc thể trong tự nhiên. Mỗi chuỗi bao gồm một giải pháp có thể của bài toán. Giải thuật di truyền sử dụng các toán tử được sinh ra bởi sự chọc lọc tự nhiên một quần thể các chuỗi nhị phân (hoặc các cấu trúc khác), mã hóa khoảng tham số trên mỗi thế hệ, khảo sát các phạm vi khác nhau của không gian tham số và định hướng tìm kiếm đối với khoảng mà khoảng đó xác suất cao để tìm kiếm sự thực hiện tốt hơn. b) Thuật toán di truyền Các bước trong thuật toán di truyền được trình bày cụ thể như sau: Bước 1:  Đặt t = 0  Tạo ngẫu nhiên Np > 1 cá thể để hình thành quần thể thứ nhất gọi là Pt  Đánh giá độ thích nghi của nghiệm trong quần thể Pt Bước 2: Chéo hóa – Dùng toán tử Chéo hóa để tạo quần thể con Qt như sau:  Chọn 2 nghiệm x và y trong quần thể Pt dựa trên độ thích nghi.  Sử dụng toán tử chéo hóa tạo nghiệm con và bổ sung nghiệm con này vào tập Qt Bước 3: Đột biến – Dùng toán tử đột biến để tạo sự biến đổi ở mỗi nghiệm x ∈ Qt với mức biến đổi cho trước. Bước 4: Gán độ thích nghi cho mỗi cá thể trong quần thể. x ∈ Qt dựa trên giá trị hàm mục tiêu và khả năng không chấp nhận được của nghiệm này. GVHD: Th.S Huỳnh Tấn Khải 14

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.01: Bộ Luận Văn Thạc Sĩ Quản Trị Kinh Doanh MBA

165 tài liệu

2090 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright ©2025 TaiLieu.VN. All rights reserved.