- Giải thuật di truyền cho bài toán đa mục tiêu. - Giải thuật di truyền. - Bài toán đa mục tiêu. - 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. - 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 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, NSGA . - 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 thiện 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. - 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.