Tài liệu Thuật toán bầy đàn pso, giải thuật di truyền và ứng dụng giải các bài toán tối ưu đa mục tiêu

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN QUANG LẬP THUẬT TOÁN BẦY ĐÀN PSO, GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG GIẢI CÁC BÀI TOÁN TỐI ƢU ĐA MỤC TIÊU Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: TS. VŨ VINH QUANG Thái Nguyên - 2013 i LỜI CẢM ƠN Em xin chân thành cảm ơn Trường Đại Học Công Nghệ Thông Tin và truyền thông đã tạo điều kiện cho em thực hiện luận văn này. Em cũng xin chân thành cảm ơn tới toàn thể thầy cô giáo ở Viện công nghệ thông tin và trường Đại học công nghệ thông tin và truyền thông đã tận tình giảng dạy và hướng dẫn, trang bị cho em những kiến thức cần thiết trong quá trình thực hiện luận văn được thành công. Dựa trên sự chỉ bảo tận tình của TS. Vũ Vinh Quang dựa trên những kiến thức đã học và tìm hiểu được, em đã hoàn thành luận văn theo đúng thời gian quy định. Tuy nhiên trong quá trình thiết kế và thực hiện luận văn không tránh khỏi sai sót, do thời gian có hạn và khả năng còn hạn chế. Em mong quý thầy cô và các bạn thông cảm và có những ý kiến quý báu nhằm hoàn thiện hơn cho sản phẩm. Em xin chân thành cảm ơn! Thái nguyên, ngày 15 tháng 9 năm 2013 Học viên Nguyễn Quang Lập Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ ii LỜI CAM ĐOAN Em xin cam đoan luận văn tốt nghiệp: “Thuật toán bầy đàn PSO, giải thuật di truyền và ứng dụng giải các bài toán tối ưu đa mục tiêu” do em tự thực hiện dưới sự hướng dẫn của thầy giáo Vũ Vinh Quang. Các kết quả và số liệu hoàn toàn trung thực. Ngoài các tài liệu tham khảo đã dẫn ra ở cuối luận văn em đảm bảo rằng không sao chép các công trình hay luận văn tốt nghiệp của người khác. Nếu phát hiện có sự sai phạm với điều cam đoan trên, em xin hoàn toàn chịu trách nhiệm. Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ iii MỤC LỤC LỜI CẢM ƠN ................................................................................................................ i LỜI CAM ĐOAN .......................................................................................................... ii MỤC LỤC ................................................................................................................... iii DANH MỤC CÁC BẢNG ............................................................................................. v DANH MỤC CÁC HÌNH VẼ ....................................................................................... vi MỞ ĐẦU...................................................................................................................... 1 CHƢƠNG 1: MÔ HÌNH BÀI TOÁN TỐI ƢU ............................................................ 3 1.1 Mô hình bài toán tối ưu hóa .................................................................................. 3 1.1.1 Mô hình tổng quát .............................................................................................. 3 1.1.2 Phân loại bài toán tối ưu..................................................................................... 4 1.2 Bài toán quy hoạch tuyến tính............................................................................... 4 1.3 Bài toán tối ưu đa mục tiêu ................................................................................... 6 1.3.1 Phương pháp ràng buộc...................................................................................... 6 1.3.2 Phương pháp tổng trọng số ................................................................................ 8 1.3.3 Phương pháp nhượng bộ dần ............................................................................. 8 1.3.4 Phương pháp thoả hiệp ....................................................................................... 9 1.3.5 Phương pháp tìm nghiệm có khoảng cách nhỏ nhất đến nghiệm lý tưởng ........ 9 1.3.6 Phương pháp giải theo dãy mục tiêu đã được sắp ............................................. 9 1.3.7 Phương pháp từng bước của Benayoun ........................................................... 10 1.3.8 Phương pháp trọng số ...................................................................................... 11 CHƢƠNG 2: CƠ SỞ THUẬT TOÁN DI TRUYỀN .................................................. 13 2.1 Các khái niệm cơ bản .......................................................................................... 14 2.1.1 Cá thể, nhiễm sắc thể ....................................................................................... 14 2.1.2 Quần thể ........................................................................................................... 14 2.1.3 Chọn lọc (Selection) ......................................................................................... 14 2.1.4 Lai ghép (Cross-over) ..................................................................................... 15 2.1.5 Đột biến (Mutation)......................................................................................... 15 2.1.6 Mô hình GA ..................................................................................................... 15 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ iv 2.1.7 Các tham số của GA ......................................................................................... 16 2.2 Cơ chế thực hiện GA ........................................................................................... 17 2.2.1 Mã hóa .............................................................................................................. 17 2.2.2 Khởi tạo quần thể ban đầu ................................................................................. 18 2.2.3 Xác định hàm thích nghi .................................................................................. 19 2.2.4 Cơ chế lựa chọn ................................................................................................. 19 2.2.5 Các toán tử di truyền ........................................................................................ 20 2.3. Thuật toán di truyền kinh điển ........................................................................... 22 2.3.1. Mã hóa.............................................................................................................. 22 2.3.2. Toán tử chọn lọc ............................................................................................... 23 2.3.3. Toán tử lai ghép ................................................................................................ 24 2.3.4. Toán tử đột biến ................................................................................................ 25 2.3.5. Thuật toán di truyền mã hóa số thực (RCGA) ................................................... 27 2.4 Thuật toán tối ưu bầy đàn PSO ........................................................................... 33 2.4.1 Giới thiệu.......................................................................................................... 33 2.4.2 Khái niệm về bầy đàn thông minh................................................................... 34 2.4.3 Thuật toán PSO truyền thống .......................................................................... 35 2.5 Một số kết quả cải tiến đối với PSO ............................................................... 43 CHƢƠNG 3: ỨNG DỤNG THUẬT TOÁN GA VÀ PSO CHO CÁC BÀI TOÁN THỰC TẾ .................................................................................................................. 56 3.1 Đặt vấn đề ......................................................................................................... 56 3.2 Mô hình bài toán thức ăn gia súc ...................................................................... 58 3.2.1 Yêu cầu của bài toán........................................................................................ 58 3.2.2 Dữ liệu đầu vào của bài toán ........................................................................... 58 3.3 Bài toán thực tế ................................................................................................. 61 KẾT LUẬN ................................................................................................................ 68 TÀI LIỆU THAM KHẢO .......................................................................................... 69 PHỤ LỤC .................................................................................................................. 70 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ v DANH MỤC CÁC BẢNG Bảng 2.1: Phân tích kết quả một vài bài toán tối ưu thông dụng .............................. 53 Bảng 2.2: Kích thước quần thể và miền giá trị khởi tạo cho các bài toán tối ưu ...... 53 Bảng 3.1 Giá trị các tham số của bài toán ................................................................. 57 Bảng 3.2 Tiêu chuẩn dinh dưỡng .............................................................................. 61 Bảng 3.3 Tỉ lệ chất dinh dưỡng trong các loại nguyên liệu ...................................... 61 Bảng 3.4: Nghiệm của bài toán với một số bộ dữ liệu .............................................. 63 Bảng 3.5: Nghiệm của bài toán với một số bộ dữ liệu .............................................. 66 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ vi DANH MỤC CÁC HÌNH VẼ Hình 2.1: Sơ đồ mô tả GA ....................................................................................................15 Hình 2.2: Lai ghép CMX ......................................................................................................30 Hình 2.3: Phân bố của x cij ...................................................................................................31 Hình 2.4: Toán tử lai ghép SX ..............................................................................................32 Hình 2.5: Mô tả cách thức tìm kiếm thức ăn của bầy kiến ...................................................34 Hình 2.6: Mô tả cách thức tìm đường của đàn chim.............................................................35 Hình 2.7: Bầy đàn với 10 cá thể trong không gian tìm kiếm 2 chiều ...................................36 Hình 2.8: Quan hệ vị trí – vận tốc trong không gian 2 chiều................................................37 Hình 2.9: Một bầy đàn toàn cục và lân cận cục bộ ...............................................................38 Hình 2.10: Các topology lân cận đơn giản ...........................................................................38 Hình 2.11:Chuyển động của cá thể .......................................................................................42 Hình 2.12: Áp dụng kỹ thuật làm lệch cho hàm (2.13) tại điểm x* 4.60095589 , với λ=1 ....46 Hình 2.13 Áp dụng kỹ thuật làm lệch cho hàm (2.13) tại điểm x* 4.60095589 ,với λ=10 ...46 Hình 2.14:Áp dụng kỹ thuật làm lệch cho hàm (2.13) tại điểm x* 4.60095589 ,với λ=0.1. ..47 Hình 2.15: Áp dụng kỹ thuật làm lệch cho hàm (2.14) tại điểm x* ( ) , với λ=1 .....................47 2 Hình 2.16: Áp dụng kỹ thuật làm lệch cho hàm (2.14) tại điểm x* Hình 2.17: Áp dụng kỹ thuật làm lệch cho hàm (2.14) tại điểm x* 2 2 ,với λ=10 ..............48 , với λ=0.1 ...................48 Hình 2.18: Đồ thị của hàm Levy No.5 trong khối [-2,2]2 .....................................................50 Hình 2.19: Giai đoạn đầu G(x) của kỹ thuật kéo giãn cho hàm Levy No.5 trong khối [-2,2]2 ........50 Hình 2.20: Hàm Levy No.5 trong khối [-2,2]2 sau giai đoạn hai H(x) của kỹ thuật kéo giãn ........51 Hình 3.1: Kết quả bài toán khi sử dụng thuật toán GA – Test 2...........................................64 Hình 3.2 Kết quả giải bài toán khi sử dụng thuật toán PSO – Test 2 ...................................66 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 1 MỞ ĐẦU Trong thực tế, rất nhiều ngành khoa học phải giải quyết các bài toán tối ưu đa mục tiêu đặc biệt là trong ngành kinh tế. Chẳng hạn, người chế tạo sản phẩm thường phải đưa ra phương án sao cho vừa tiết kiệm vật liệu, chi phí sản xuất thấp và lại muốn giá trị sản phẩm là cao nhất. Nghiên cứu giải bài toán tối ưu đa mục tiêu là một vấn đề không đơn giản vì chưa chắc có lời giải thỏa mãn đồng thời các mục tiêu đặt ra (thường là các mục tiêu đối nghịch như ví dụ trên) mà không vi phạm các ràng buộc nào đó. Đã có nhiều phương pháp giải bài toán tối ưu đa mục tiêu được đề xuất, việc nghiên cứu phát triển các phương pháp này và ứng dụng chúng để giải quyết các bài toán thực tế là một vấn đề đang được quan tâm. Trong nhiều bài toán tối ưu thực tế, việc trọng tâm là tìm vị trí cực tiểu toàn cục của hàm mục tiêu giá trị thực f: E R, nghĩa là tìm điểm x* E sao cho f ( x* ) với tập đóng E f ( x), x E R d , trong đó d là số chiều. Đã có nhiều phương pháp tối ưu toàn cục (Global Optimization - GO) được phát triển để giải quyết vấn đề như trên như: Mô phỏng việc luyện thép (Simulated Annealing), Tabu search, Tính toán tiến hóa (Evolutionary computation). Về mặt lý thuyết tổng quát, các phương pháp GO có tính hội tụ mạnh, hay ít ra về nguyên tắc cũng dễ hiểu trong việc thực hiện và ứng dụng. Tính toán tiến hóa (Evolutionary computation) là kỹ thuật đặc biệt trong số các phương pháp GO. Phương pháp này làm việc trên một tập hợp những lời giải tiềm năng, được gọi là quần thể (population) và tìm lời giải tối ưu thông qua việc cộng tác và cạnh tranh giữa các lời giải tiềm năng. Thường được sử dụng nhất là các thuật toán di truyền (Genetic Algorithms – GA) và Artificial Life, dựa trên sự tiến hóa tự nhiên và cư xử xã hội. Các phương pháp này thường có thể tìm tốt nhất trong các bài toán tối ưu phức tạp với các phương pháp tối ưu truyền thống. Thuật toán tối ưu Particle Swarm Optimization (PSO) được R.C.Eberhat và J.Kennedy đề nghị năm 1995. Từ lúc ra đời đến nay PSO đã được nhiều nhà khoa Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 2 học tham gia nghiên cứu, cải tiến và ứng dụng nó để giải nhiều bài toán lý thuyết và thực tế. Đề tài “Thuật toán bầy đàn PSO, giải thuật di truyền và ứng dụng giải các bài toán tối ưu đa mục tiêu” nhằm tìm hiểu khả năng ứng dụng của thuật toán PSO, GA trong việc giải quyết các bài toán tối ưu đa mục tiêu trong thực tế. Với mục đích đó, đề tài tập trung trình bày về việc giải bài toán tối ưu bằng giải thuật PSO, GA và thực nghiệm về khả năng ứng dụng thực tế của hai thuật toán này. Nội dung đề tài gồm 3 chƣơng: Chương 1: Mô hình bài toán tối ưu đa mục tiêu. Chương 2: Cơ sở thuật toán di truyền. Chương 3: Ứng dụng thuật toán GA, và PSO cho các bài toán thực tế. Trong luận văn, các kết quả thực nghiệm được thực hiện bằng các chương trình viết trên nền Matlab version 7.0. Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 3 CHƢƠNG 1 MÔ HÌNH BÀI TOÁN TỐI ƢU Trong chương này, luận văn sẽ trình bày một số kiến thức cơ bản về mô hình tổng quát của bài toán tối ưu hóa, việc phân loại các bài toán tối ưu và một số phương pháp giải bài toán tối ưu đa mục tiêu, các kiến thức của chương này được tham khảo từ các tài liệu [1,2]. 1.1 Mô hình bài toán tối ƣu hóa 1.1.1 Mô hình tổng quát Tối ưu hóa là một trong những lĩnh vực quan trọng của toán học có ảnh hưởng đến hầu hết các lĩnh vực khoa học, công nghệ và kinh tế và xã hội. Việc tìm giải pháp tối ưu cho một bài toán thực tế nào đó chiếm một vai trò hết sức quan trọng như việc tiến hành lập kế hoạch sản xuất hay thiết kế hệ thống điều khiển các quá trình … Nếu sử dụng các kiến thức trên nền tảng của toán học để giải quyết các bài toán cực trị, người ta sẽ đạt được hiệu quả kinh tế cao. Điều này phù hợp với mục đích của các vấn đề đặt ra trong thực tế hiện nay. Bài toán tối ưu tổng quát được phát biểu như sau: Cực đại hóa (cực tiểu hóa) hàm: f (X ) max(min) Với các điều kiện: gi ( X ) bi , i J1 (1.1) g j ( X ) bj , j J2 (1.2) g k ( X ) bk , k J3 (1.3) x1 , x2 ,..., xn (1.4) 0. Trong đó f ( X ) được gọi là hàm mục tiêu, Các điều kiện (1.1) được gọi là ràng buộc đẳng thức. Các điều kiện (1.2), (1.3) được gọi là ràng buộc bất đẳng thức. Các điều kiện (1.4) được gọi là ràng buộc về dấu. X ( x1 , x2 ,..., xn ) là véc tơ thuộc không gian R n . Tập các véc tơ X thỏa mãn hệ ràng buộc lập nên một miền D được Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 4 gọi là miền phương án (hay miền chấp nhận được), mỗi điểm X D gọi là một phương án. Một phương án X * D làm cho hàm mục tiêu f ( X ) đạt max (min) được gọi là phương án tối ưu. 1.1.2 Phân loại bài toán tối ưu Dựa trên mô hình tổng quát, người ta thường phân loại lớp các bài toán tối ưu như sau: Qui hoạch tuyến tính: là những bài toán mà hàm mục tiêu f ( X ) và tất cả các hàm ràng buộc gi ( X ), g j ( X ), gk ( X ) là tuyến tính. Qui hoạch phi tuyến: là những bài toán một trong hàm mục tiêu f ( X ) hoặc các hàm ràng buộc gi X , g j X , g k X là phi tuyến. Qui hoạch lồi: Là các bài toán qui hoạch mà các hàm mục tiêu f ( X ) là lồi trên tập các ràng buộc D lồi. Qui hoạch lõm: Là các bài toán qui hoạch mà các hàm mục tiêu f ( X ) là lõm trên tập các ràng buộc D lõm. Qui hoạch rời rạc: Bài toán tối ưu được gọi là qui hoạch rời rạc nếu miền ràng buộc D là tập hợp rời rạc. Trong trường hợp riêng khi các biến chỉ nhận giá trị nguyên thì ta có qui hoạch nguyên. Qui hoạch đa mục tiêu: Nếu trên cùng một miền ràng buộc ta xét đồng thời các hàm mục tiêu khác nhau. Trong các lĩnh vực kinh tế kỹ thuật thì qui hoạch phi tuyến, qui hoạch tuyến tính là những bài toán thường gặp. 1.2 Bài toán quy hoạch tuyến tính Từ một số các mô hình trong thực tế, ta có mô hình tổng quát cho bài toán quy hoạch tuyến tính như sau: Xác định các biến x j ( j 1, 2,..., n) sao cho: n F ( x) cj x j Max( Min) j 1 n aij x j bi i I1 M j 1 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ (1.5) 5 n aij x j bi i I2 (1.6) M \ I1 j 1 xj Với M Vectơ X 0( j J 1, 2,..., m , N (1.7) N) 1, 2,..., n x1 , x2 ,..., xn thỏa mãn các điều kiện (1.5) - (1.7) được gọi là một phương án của bài toán. Tập các nghiệm thỏa mãn hệ ràng buộc được gọi là miền phương án ký hiệu là D . Phương án thỏa mãn điều kiện để hàm mục tiêu đạt Max(min) được gọi là phương án tối ưu. Dạng chính tắc: n F ( x) cj x j Min j 1 n aij x j bi i M j 1 xj 0( j N) Dạng chuẩn tắc: n F ( x) cj x j Min j 1 n aij x j bi i M j 1 xj 0( j N) Sử dụng các ký hiệu vectơ và ma trận, mô hình bài toán quy hoạch tuyến tính tổng quát được biểu diễn như sau: f X CT X AX X Max(min) b 0 Trong đó: X ( x1, x2 ,..., xn ), C (c1, c2 ,..., cn ) A a11 a21 ... am1 Số hóa bởi trung tâm học liệu a12 a22 ... a1n ... a2 n am 2 ... amn x1 ,X x2 ... xn b1 ,b b2 ... bm http://www.lrc.tnu.edu.vn/ 6 1.3 Bài toán tối ƣu đa mục tiêu Trong các bài toán kinh tế, kỹ thuật, khoa học công nghệ, ... nảy sinh từ thực tế, chúng ta phải xem xét tối ưu hóa đồng thời nhiều mục tiêu. Việc làm tốt hơn mục tiêu này thường dẫn tới việc làm xấu đi một số mục tiêu khác (nghĩa là không có lời giải nào tối ưu theo mọi mục tiêu). Như vậy, chúng ta cần phải tối ưu hóa (cực đại hóa hoặc cực tiểu hóa tùy theo tình huống cụ thể) không phải là chỉ một mục tiêu nào đó, mà là đồng thời tất cả các mục tiêu đã đặt ra thường là không tương thích với nhau. Xét mô hình tổng quát F (X ) = (f1(X ), f2(X ),..., fn (X )) ® Min (M ax), G (X ) > = (= , < = ) 0. (1.8) Trong đó + F (X ) được gọi là hàm mục tiêu + G (X ) được gọi là các biểu thức ràng buộc + X là phương án của bài toán Tập tất cả các phương án thỏa mãn hệ điều kiện ràng buộc được gọi là miền phương án, phương án thỏa mãn điều kiện để F (X ) ® Min (Max) được gọi là phương án tối ưu. Rõ ràng so đối với bài toán tối ưu 1 mục tiêu, việc tìm nghiệm của bài toán tối ưu nhiều mục tiêu khó khăn hơn rất nhiều và đại đa số, chúng ta không thể xác định được phương án tối ưu thật sự. Sau đây chúng ta sẽ nghiên cứu một số 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 Xét bài toán F (X ) = (f1(X ), f2 (X ),..., f p (X )) ® Min , G (X ) > = (= , < = ) 0. Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 7 Ta chuyển bài toán trên về bài toán fh (X ) ® M ax, fk (X ) ³ Lk , k = 1, 2,..., h - 1, h, h + 1,..., p. Trong đó mục tiêu thứ h được chọn tùy ý để lấy Max . Như vậy bài toán đa mục tiêu đã được chuyển về bài toán đơn mục tiêu và có thể áp dụng các thuật toán thông thường ví dụ như thuật toán đơn hình. Thuật toán trên được giải bằng phương pháp xây dựng bảng thỏa hiệp các hàm mục tiêu và từ đó xác định phương án tối ưu. Thuật toán: Bước 1: Xây dựng bảng thỏa hiệp + Giải lần lượt p các bài toán đơn mục tiêu tương ứng với các ràng buộc. Gọi ( ) nghiệm của mục tiêu thứ k là x k = x 1k ,..., x nk , k = 1, 2,..., p . Sau đó tính giá trị của p hàm mục tiêu đạt được tại các x k tương ứng. Kí hiệu là f1(x 1k ), f2 (x 2k ),..., f p (x pk ) . + 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 thỏa hiệp. …… f p (x k ) f1(x k ) f2 (x k ) x1 f1(x 1 ) f2 (x 1 ) f p (x 1 ) x2 f1(x 2 ) f2 (x 2 ) f p (x 2 ) …. …. …. …. xp f1(x p ) f2 (x p ) f p (x p ) + Xác định số lớn nhất và nhỏ nhất trọng cột thứ k, kí hiệu lần lượt là M k , m k ,(k = 1, 2,..., p). Bước 2: Quy ước một bài toán đa mục tiêu tương ứng với bài toán một mục tiêu Bước 3: Chọn giá trị L k với k ¹ h trong đoạn éêm k , M k ù ú ë û bằng cách chia đoạn éêm k , M k ù ú ra r phần bằng nhau. Khi đó L k có thể nhận 1 trong r giá trị sau ë û Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 8 Lk = n k + t (M - m k ), t = 0,1, 2,..., r - 1 . r- 1 k Bước 4: Ứng với mỗi giá trị của L k , ta giải bài toán đơn mục tiêu tương ứng 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 sẽ chọn nghiệm tối ưu nhất. 1.3.2 Phương pháp tổng trọng số F (X ) = (f1(X ), f2 (X ),..., f p (X )) ® Min , G (X ) > = (= , < = ) 0. Ta chuyển bài toán trên thành bài toán F (X ) = w1 f1(X ) + w2 f2(X ) + ... + w p f p (X ) ® Min , G (X ) > = (= , < = ) 0. p Trong đó wi ³ 0,(i = 1, 2,..., p), å wi = 1. i= 1 1.3.3 Phương pháp nhượng bộ dần Bước 1: Giải k bài toán 1 mục tiêu riêng rẽ, sau đó lập bảng thưởng phạt Bước 2: Căn cứ vào bảng thưởng phạt, với giá trị Y 10 , ta buộc Y 1 nhượng bộ một lượng D Y 1 và giải bài toán: M axY 2(X ) với X Î D;Y 1(X ) ³ Y 10 - D Y 1 Giả sử Y 2* là giá trị tối ưu của bài toán này, chuyển sang bước 3 Bước 3: Căn cứ vào Y 20 và Y 2* buộc Y 2 nhượng bộ lượng D Y 2 và giải bài toán: M axY 3 (X ) với X Î D ;Y 1(X ) ³ Y 10 - D Y 1;Y 2 (X ) ³ Y 2* - D Y 2 ; Giả sử Y 3* là giá trị tối ưu của bài toán này, chuyển sang bước tiếp ………….. Bước k: Căn cứ vào Y k0- 1 và Y k*- 1 buộc Yk-1 nhượng bộ lượng D Y k - 1 và giải bài toán: M axY k (X ) với X Î D ;Y 1(X ) ³ Y 10 - D Y 1;Y 2 (X ) ³ Y 2* - D Y 2 ;...;Y k - 1(X ) ³ Y k*- 1 - D Y k - 1; Nghiệm của bài toán cuối cùng này được lấy làm nghiệm của bài toán ban đầu. Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 9 1.3.4 Phương pháp thoả hiệp Bước 1: Giải k bài toán 1 mục tiêu riêng rẽ, giả sử nghiệm tối ưu là X i (i = 1, 2,...k ) . Đặt M i = Y i (X i ) và đưa vào biến phụ w : M i - Y i (X i ) £ W với mọi i = 1, 2,..., k . Mi Vế trái trong công thức trên gọi là độ lệch tương đối chung Bước 2: Giải bài toán Min (w) với X Î D từ đó tìm được nghiệm tối ưu X opt và wopt Trong trường hợp này, lợi ích tỷ lệ với độ lệch tương đối, phương án X 1 là tốt hơn X 2 nếu độ lệch tương đối chung của X 1 nhỏ hơn của X 2 . 1.3.5 Phương pháp tìm nghiệm có khoảng cách nhỏ nhất đến nghiệm lý tưởng Phương pháp này giả định có một nghiệm lý tưởng, X 1 là tốt hơn X 2 nếu khoảng cách từ X 1 đến nghiệm lý tưởng nhỏ hơn khoảng cách tương ứng của X 2 Định nghĩa: Giả sử X 1 , X 2 Î Rn, khoảng cách giữa X 1 và X 2 là số da xác định bởi da = å X 1i - X 2i a a là tham số a >1 Khi đó bài toán Max(Y (X )) với X Î D đưa về bài toán min {å Y i (X ) - Y i * a } Vấn đề xác định tham số a phụ thuộc vào từng bài toán. 1.3.6 Phương pháp giải theo dãy mục tiêu đã được sắp Trong phương pháp này, thứ tự của các hàm mục tiêu thể hiện sự quan trọng của các tiêu chuẩn, các mục tiêu xếp trước được ưu tiên hơn. Bước 0: Sắp xếp thứ tự các mục tiêu Y 1,Y 2,...,Y k Bước 1: Giải bài toán M ax(Y 1(X )) với X Î D , ký hiệu D 1 = {X 1 Y 1(X 1 ) = m axY1(X ), X Î D } Í D Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 10 Bước 2: Giải bài toán M ax(Y 2(X )) với X Î D 1 , ký hiệu { } D 2 = X 2 Y 2 (X 2 ) = m axY2 (X ), X Î D 1 Í D 1 ….. Bước k: Giải bài toán M ax(Y k (X )) với X Î D k - 1 , ký hiệu { } D k = X k Y k (X k ) = m axYk (X ), X Î D k - 1 Í D k - 1 Ta có dãy bao hàm thức: D Ê D 1 Ê ... Ê D k . Khi đó tập các nghiệm thuộc D k sẽ thỏa mãn tính chất tối ưu của bài toán đa mục tiêu. 1.3.7 Phương pháp từng bước của Benayoun Phương pháp này gần giống phương pháp tìm nghiệm xấp xỉ nghiệm lý tưởng. Thường có hai biến dạng sau: - Các độ lệch tương đối của hàm mục tiêu được gắn với một bộ trọng số. Trọng số này được xác định dựa trên khoảng biến động của từng mục tiêu. - Miền chấp nhận được của nó có thể thay đổi qua các bước giải Hàm lợi ích và các quan hệ xác định như phương pháp tìm nghiệm xấp xỉ nghiệm lý tưởng. Bài toán cơ bản mà phương pháp này xét là: Õ i M i - Y i (X ) £ da* X Î Di trong đó M i = M ax(Y i (X )) Thuật toán như sau: Bước 1: Tính thưởng phạt, xác định M i , m i ở cột thứ i M i = M ax(Y i (X )) , m i = Min (Y i (X )) Bước 2: Tìm các trọng số, xác định a i để tính i M i mi * M1 Õ i : 1 n (C1j ) 2 j 1 Với C ij là các hệ số của hàm mục tiêu thứ i. Đặt i=0 chuyển sang bước 3 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 11 Bước 3: Tính 1 1 i Bước 4: Giả sử nghiệm của bài toán thứ i là X (i ) và i £ k - 1 Xét các trường hợp: 1) Nếu chấp nhận X (i ) thì kết thúc. 2) Nếu không chấp nhận X (i ) và i £ k - 1 thì chuyển Bước 5 3) Nếu không chấp nhận X (i ) và i = k thì tìm phương án giải khác. Bước 5: Phân tích kết quả và tìm ra mục tiêu i * có thể nhượng bộ, cho nhượng bộ một lượng D i* chuyển Bước 6 Bước 6: Xác định miền chấp nhận mới D i + 1 Di X 1 i ¹ i* YI ( X ) YI X (i ) YI ( X ) YI * X (i ) Coi I* 0 I* * i 0 Với i ¹ i * thì tính i theo công thức trên. i = i + 1. Chuyển về Bước 3 Thuật toán kết thúc sau k lần lặp 1.3.8 Phương pháp trọng số Trong phương pháp này hàm lợi ích U tuyến tính theo các giá trị của phương án U (Y ( X )) p; Y ( X ) piYi ( X ) Bài toán quy hoạch đa mục tiêu ở dạng này là: max piYi ( X ) với pi (i = 1, 2,..., k ) là các trọng số; thường xét với pi không âm và Số hóa bởi trung tâm học liệu pi 1. http://www.lrc.tnu.edu.vn/ 12 Về mặt thực tiễn, có thể xem các trọng số pi là tỷ lệ quy đổi thứ nguyên của mục tiêu thứ i. Chẳng hạn quy đổi tất cả các mục tiêu về dạng tiền tệ thì pi biểu hiện cho số đơn vị tiền tệ của mục tiêu thứ i. Đây cũng là phương pháp quy đa mục tiêu về một mục tiêu phụ thuộc tham số. Kết luận: Nội dung chương 1 đã trình bày một số kiến thức cơ bản về mô hình của bài toán tối ưu tổng quát, mô hình của bài toán tối ưu đa mục tiêu cùng một số phương pháp giải. Các kiến thức này là cơ sở để trình bày các kết quả trong chương 2 và chương 3 của luận văn. Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 13 CHƢƠNG 2 CƠ SỞ THUẬT TOÁN DI TRUYỀN Trong chương 2, luận văn sẽ trình bày các kiến thức cơ bản về lĩnh vực tính toán mềm bao gồm thuật toán di truyền (GA) và thuật toán bầy đàn (PSO) giải các bài toán đa mục tiêu. Các kiến thức về các thuật toán này được tham khảo từ các tài liệu [3, 4, 5, 6, 7, 8, 9, 10]. Mở đầu Trong công nghệ thông tin, GA là một thành phần của Tính toán tiến hóa (Evolutionary computation – EC), một lĩnh vực được coi là có tốc độ phát triển nhanh của trí tuệ nhân tạo. Có thể chia EC thành 5 hướng nghiên cứu như sau : - GA (Genetic Algorithm - GA): Dựa vào quá trình di truyền trong tự nhiên để cải tiến lời giải qua các thế hệ bắt nguồn từ một tập các lời giải ban đầu. - Quy hoạch tiến hoá (Evolutionary Programming - EP): Dựa vào quy luật tiến hoá, tìm phương pháp kết hợp đủ khả năng giải quyết trọn vẹn một bài toán từ một lớp các phương pháp giải quyết được một số phần của bài toán. - Các chiến lƣợc tiến hoá (Evolutionary Strategies - ES): Dựa trên một số chiến lược ban đầu, tiến hoá để tạo ra những chiến lược mới phù hợp với môi trường thực tế một cách tốt nhất. - Lập trình di truyền (Genetic Programming - GP): Mở rộng GA trong lĩnh vực các chương trình của máy tính. Mục đích của nó là để sinh ra một cách tự động các chương trình máy tính giải quyết một cách tối ưu một vấn đề cụ thể. - Các hệ thống phân loại (Classifier Systems- CS): Các GA đặc biệt được dùng trong việc học máy và việc phát hiện các quy tắc trong các hệ dựa trên các quy tắc. GA cũng như các thuật toán tiến hoá đều được hình thành dựa trên một quan niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm "Quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu". Quá trình tiến hoá thể hiện tính tối ưu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước. Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/