MỞ ĐẦU 1. Lý do chọn đề tài Trên thực tế, tồn tại rất nhiều bài toán yêu cầu tối ưu hóa đồng thời nhiều mục tiêu (thường là cạnh tranh lẫn nhau) ví dụ như: định tuyến các phương tiện giao thông để xác định các tuyến đường tối ưu nhằm cung cấp dịch vụ cho một tập hợp các khách hàng có thể liên quan đến một số mục tiêu khác nhau: tổng quãng đường đi (hoặc thời gian thực hiện), lượng xe sử dụng, độ hài lòng của khách hàng (giao hàng trong khoảng thời gian đã thỏa thuận trước), … hay việc đi chợ mua thức ăn cần đảm bảo sao cho đủ lượng calo cần thiết, chất lượng bữa ăn đảm bảo, số tiền chi tiêu không vượt quá giới hạn, … Giải thuật di truyền (GA) là một trong những mô hình tính toán phổ biến và thành công nhất trong lĩnh vực tính toán thông minh. Cùng với các kỹ thuật tính toán thông minh khác như tính toán mờ (fuzzy computing), mạng Nơ-ron (neural networks), hệ đa tác tử (multi- agent systems), trí tuệ bầy đàn (swarm intelligence), giải thuật di truyền ngày càng phát triển, được áp dụng rộng rãi trong các lĩnh vực của cuộc sống. Đối với bài toán đa mục tiêu, đã có nhiều phương pháp nghiên cứu đề xuất ra các thuật toán để giải quyết bài toán như: MOGA, NSGA2, SPEA2, SEAMO2, … trong đó giải thuật SEAMO2 là hiệu quả hơn cả [4].
Với giải thuật SEAMO2, việc thay thế cá thể vào quần thể (thực hiện chiến lược chọn lọc tự nhiên) thì độ hội tụ về tập nghiệm tối ưu (với lần chạy ngắn) là chưa cao và khi quần thể nghiệm đã đạt ngưỡng tối ưu (với lần chạy dài) thì sẽ mất nhiều thời gian để loại cá thể không phù hợp. Chính vì vậy, tác giả mạnh dạn nghiên cứu phương pháp cải tiến chiến lược chọn lọc tự nhiên trong giải thuật SEAMO2 để giải các bài toán tối ưu đa mục tiêu trong luận văn: “Giải thuật di truyền cho bài toán đa mục tiêu”. Mục đích nghiên cứu Mục tiêu của luận văn là nghiên cứu các toán tử trong giải thuật di truyền (hay giải thuật tiến hóa nói chung) đặc biệt là toán tử chọn lọc tự nhiên để chọn lọc và thay thế các lời giải nhằm tối ưu tập lời giải thu được 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 đa mục tiêu. Mục đích cụ thể của luận văn là sử dụng các toán tử di truyền khác nhau đối với thuật toán SEAMO2, ứng dụng cho bài toán cái túi đa mục tiêu, thay đổi chiến lược chọn lọc tự nhiên của thuật toán nhằm cải tiến thuật toán.
Phương LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 pháp này sẽ được so sánh với kết quả của các thuật toán tối ưu đa mục tiêu khác như: SPEA2, NSGA2, …[3,13,16,17]. Do đó mục tiêu của luận văn là: Nghiên cứu giải thuật di truyền cho bài toán đa mục tiêu. Nhiệm vụ nghiên cứu Nghiên cứu các mô hình của giải thuật di truyền có áp dụng các nguyên lý tiến hóa và trên cơ sở đó tiếp cận các ý tưởng t thuật toán di truyền để giải bài toán cái túi đa mục tiêu như: NSGA2, SPEA2, SEAMO2, cách thức tìm nghiệm của các thuật toán này để cải tiến thuật toán di truyền có áp dụng nguyên lý tiến hóa SEAMO2. Đối tượng và phạm vi nghiên cứu Tìm hiểu về bài toán tối ưu đa mục tiêu, bài toán cái túi 0-1 đa mục tiêu.
Tìm hiểu về giải thuật tiến hóa, các mô hình giải thuật tiến hóa có thể áp dụng cho bài toán cái túi 0 - 1 đa mục tiêu. Xây dựng ứng dụng giải bài toán cái túi 0 - 1 đa mục tiêu với giải thuật SEAMO2 và đề xuất phương pháp cải tiến giải thuật. So sánh kết quả thực nghiệm của phương pháp đề xuất với các kết quả của các thuật toán khác. Phương pháp nghiên cứu Dựa trên tài liệu thu thập t nhiều nguồn (tài liệu, bài báo do giảng viên hướng dẫn cung cấp, sách, báo, tạp chí, internet…) tổng hợp, phân tích và trình bày lại theo sự hiểu biết của bản thân Mở rộng các cách tiếp cận trước đây trên cơ sở phân tích đặc thù giải thuật, bài toán cần giải quyết để đưa ra những ý kiến, đề xuất cải tiến hợp lý.
Ứng dụng những kết quả dựa trên nghiên cứu để xây dựng chương trình thực nghiệm, t đó so sánh với kết quả của các thuật toán tối ưu đa mục tiêu khác. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 CHƢƠNG 1 TỔNG QUAN VỀ TỐI ƢU ĐA MỤC TIÊU 1. Giới thiệu bài toán tối ƣu đa mục tiêu Tối ưu đa mục tiêu (multiobjective optimization) hay cũng còn gọi là tối ưu đa tiêu chuẩn (multicriteria optimization), tối ưu đa nhiệm (multiperformance optimization) hay tối ưu vectơ (vector optimization) có thể được định nghĩa như là một bài toán tìm kiếm vectơ của các biến quyết định mà nó thỏa mãn các ràng buộc và tối ưu hóa một hàm vectơ mà các thành phần của nó biểu diễn các hàm mục tiêu thông thường đối nghịch lẫn nhau. Vì vậy thuật ngữ tối ưu có nghĩa là tìm kiếm một lời giải mà nó cho các giá trị của các hàm mục tiêu có thể chấp nhận được đối với người thiết kế.
Chúng ta gọi các đại lượng số mà các giá trị của nó được chọn cho bài toán tối ưu hóa là các biến quyết định, ký hiệu là ( ). Vectơ của biến lấy quyết định được biểu diễn như sau[1, 2]: ⃗ ( ) Trong mỗi bài toán tối ưu đa mục tiêu luôn luôn có các hạn chế được đặt ra bởi các đặc trưng đặc biệt của môi trường hay các tài nguyên có sẵn. Các hạn chế này phải được thỏa mãn trong việc xem xét lời giải nào đó có thể chấp nhận được. Tổng quát, chúng ta gọi các hạn chế này là các ràng buộc, chúng mô tả sự phụ thuộc giữa các biến lấy quyết định và các hằng số (hay các tham số) trong bài toán.
Các ràng buộc thường được biểu diễn dưới dạng bất đẳng thức toán học như sau [1, 2]: Để biết một lời giải nào đó tốt như thế nào chúng ta cần phải có một số tiêu chuẩn để đánh giá nó. Các tiêu chuẩn này được biểu diễn như là các hàm toán học theo các biến quyết định, chúng được gọi là các hàm mục tiêu. Trong các hàm mục tiêu đó, một số hàm này đối nghịch với một số hàm khác, và một số mục tiêu thì được cực tiểu hóa trong khi các mục tiêu khác thì được cực đại hóa. Các hàm mục tiêu này có thể so sánh được với nhau, nghĩa là chúng được đo lường trong các đơn vị giống nhau, hay không so sánh được với nhau, nghĩa là chúng được đo lường trong các đơn vị khác nhau [1,2].
Mô hình bài toán tối ưu đa mục tiêu có ràng buộc Chúng ta xét một mô hình tối ưu đa mục tiêu có ràng buộc gồm có hàm mục tiêu ( )( ) và r hàm (có thể phi tuyến) ràng buộc ( )( ) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 với ⃗ ( ) là biến quyết định n chiều được định nghĩa theo mô hình sau , ( )- ( ) sao cho ( ) ( ) Chúng ta có một vectơ sao cho ( ) ( ) ( ) với tất cả lời giải khả thi. Nếu trường hợp này xảy ra, được gọi là lời giải mong ước (desirable solution) hay lời giải lý tưởng (ideal solution), điều này có nghĩa là tất cả các ( ) đều có cực đại trong Yf tại một điểm chung. Nhưng chúng ta thường không có được lời giải lý tưởng này, nên chúng ta phải thiết lập một tiêu chuẩn để xác định cái gì sẽ được xem là lời giải tối ưu. Trong luận văn này, chúng ta chỉ xem xét tiêu chuẩn tối ưu theo khái niệm tối ưu Pareto.
Khái niệm tối ưu Pareto Khái niệm tối ưu Pareto được giới thiệu bởi Vilfredo Pareto vào năm 1896, và nó tạo thành cơ sở cho việc nghiên cứu trong lĩnh vực này. Ta có định nghĩa như sau : Gọi ( ). ( ) ( ) ( )/ ( ) là hàm vectơ chiều. Gọi là tập lời giải khả thi của mô hình trên, nghĩa là tập các vectơ thỏa mãn các điều kiện ràng buộc [1,2].
Khái niệm trội Pareto Gọi là hai lời giải khả thi. Ta nói trội hơn nếu và chỉ nếu ( ) tốt hơn ( ), nghĩa là : ( ) ( )( ) và ( ) ( )( ) và * +: ( ) ( ) hay * +: ( ) ( ) 1. Tập các lời giải tối ưu Pareto Khái niệm: Gọi * sao cho ( ) tốt hơn ( )+ là tập các lời giải khả thi bị trội của. Khi đó là tập các lời giải khả thi không bị trội của hay còn gọi là tập các lời giải tối ưu Pareto của.
Tuy nhiên, điểm tối ưu Pareto hầu như luôn luôn không duy nhất, mà có đến một tập các điểm tối ưu Pareto thường được gọi là tập các lời giải không bị trội (non- dominated). Thông thường một lớp bài toán tối ưu đa mục tiêu trong thiết kế kỹ thuật có một tập tối ưu Pareto, và các bài toán đó lại có một số lượng lớn các lời giải có khả năng để chọn lựa, và điều này gây khó khăn ở 2 điểm: một là việc phát sinh ra tập lời giải, hai là việc xử lý các kết quả. Toàn bộ các lời giải tối ưu Pareto được gọi là tập tối ưu Pareto, các vectơ mục LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 tiêu tương ứng thành lập một biên (front) Pareto hay mặt (surface) Pareto. Trong hầu hết các trường hợp, sẽ có nhiều lời giải tối ưu khác nhau theo nghĩa Pareto khi đó ta sẽ phải tìm kiếm các giá trị của các hàm mục tiêu để quyết định giá trị nào của chúng là thích hợp nhất gọi là quá trình lấy quyết định.
Nếu ta biết trước được tầm quan trọng tương đối của mỗi hàm mục tiêu thì quá trình lấy quyết định sẽ đơn giản. Tuy nhiên, trong nhiều trường hợp ta không biết tầm quan trọng tương đối của mỗi hàm mục tiêu vì nó không đầy đủ hay không thể biểu diễn một cách hình thức hóa đầy đủ, nên các phương pháp này thường không được áp dụng trong thực tế. Một cách tổng quát, ta không dễ dàng tìm được một biểu diễn giải tích cho các đường hay các mặt chứa các điểm tối ưu Pareto và các thủ tục chuẩn để tính toán các điểm trong cho các điểm tương ứng của nó trong. Tuy nhiên, khi ta có một số lượng tương đối đầy đủ các điểm này thì ta có thể tiến hành lấy quyết định cuối cùng.