Nghiên Cứu Và Ứng Dụng Giải Thuật Tiến Hóa Đa Mục Tiêu Dựa Trên Thông Tin Định Hướng

• Tác giả: Nguyen Long
• Người hướng dẫn: Dr Bui Thu Lam
• Trường học: Military Technical Academy
• Chuyên ngành: Fundamentals of Mathematics for Informatics
• Đề tài: Giải Thuật Tiến Hóa Đa Mục Tiêu Dựa Trên Thông Tin Định Hướng Và Ứng Dụng
• Loại tài liệu: thesis
• Năm xuất bản: 2014
• Địa điểm: Hanoi

Mục lục chi tiết

• Abstract
• Acknowledgements
• Originality Statement
• Contents
• 1. Introduction
• 1.1. Overview
• 1.4. Questions and Hypothesises
• 2. Background concepts and Issues
• 2.1. Multi-objective problems
• 2.3. Issue 02: Lack of an efficient niching method for the main population
• 2.4. Issue 03: The disadvantages of using the weighted sum scheme
• 2.5. Issue 04: Using a ’hard’ niching method
• 2.6. Issue 05: Investigating on how the DM can interact with DMEA
• 3. A guided methodology using directions of improvement
• 3.1. Using an adaptive ratio between convergence and spread directions
• 3.2. Using a Ray based density niching for the main population
• 3.3. Using a ray based density selection schemes
• 3.4. Direction based Multi-objective Evolutionary Algorithm-II
• 3.5. Results and Discussion
• 3.6. Analyzing effects of different selection schemes for the perturbation
• 4. A guided methodology using interaction with decision makers
• 4.2. A multi-point Interactive method for DMEA-II
• 4.3. Value Added Niching
• 4.5. Results and Discussion
• 5. An application of DMEA-II for a spam email detection system
• 5.2. Spam email detection
• 5.3. An interactive method
• 5.6. Results and Discussion
• 6. Conclusions and Future Work
• 6.1.
• Publications
• Appendix A Benchmark sets
• List of Figures
• List of Tables
• Abbreviations
• BẢNG THUẬT NGỮ SỬ DỤNG TRONG LUẬN ÁN

Tóm tắt

I. Giải thuật tiến hóa đa mục tiêu

Giải thuật tiến hóa đa mục tiêu (MOEA) là một phương pháp hiệu quả để giải quyết các bài toán tối ưu hóa đa mục tiêu (MOP). MOEA sử dụng một quần thể các giải pháp để xấp xỉ tập tối ưu Pareto trong một lần chạy. Các bài toán tối ưu hóa đa mục tiêu thường liên quan đến ít nhất hai mục tiêu xung đột và có một tập các giải pháp tối ưu Pareto. MOEA đã thu hút nhiều sự quan tâm nghiên cứu trong thập kỷ qua và vẫn là một trong những lĩnh vực nghiên cứu nóng trong lĩnh vực Trí tuệ Tính toán.

1.1. Khái niệm cơ bản về tối ưu hóa đa mục tiêu

Tối ưu hóa đa mục tiêu liên quan đến việc tối ưu hóa đồng thời nhiều mục tiêu, thường xung đột với nhau. Tập các giải pháp tối ưu Pareto là tập các giải pháp mà không thể cải thiện một mục tiêu mà không làm giảm ít nhất một mục tiêu khác. Giải thuật tiến hóa đa mục tiêu sử dụng quần thể các giải pháp để xấp xỉ tập tối ưu Pareto trong một lần chạy, thay vì phải thực hiện nhiều lần chạy riêng biệt như trong các phương pháp lập trình toán học truyền thống.

1.2. Hướng dẫn tìm kiếm trong MOEA

Các kỹ thuật hướng dẫn đã được thảo luận và sử dụng để hướng dẫn giải thuật tiến hóa đa mục tiêu trong quá trình tìm kiếm hướng tới tập tối ưu Pareto. Thông tin hướng dẫn thường được lấy từ quần thể, cá thể, kho lưu trữ hoặc người ra quyết định. Việc sử dụng thông tin hướng dẫn hiệu quả sẽ giúp MOEA đạt được tập các giải pháp với chất lượng hội tụ và đa dạng tốt.

II. Thông tin định hướng trong giải thuật tiến hóa

Thông tin định hướng đóng vai trò quan trọng trong việc hướng dẫn quá trình tiến hóa của MOEA. Luận án đề xuất một phương pháp mới dựa trên thông tin định hướng để cải thiện hiệu suất của MOEA. Phương pháp này sử dụng tỷ lệ thích nghi giữa hướng hội tụ và hướng tản mát, cùng với các kỹ thuật chọn lọc và tạo biến đổi mới.

2.1. Tỷ lệ thích nghi giữa hướng hội tụ và hướng tản mát

Luận án đề xuất sử dụng tỷ lệ thích nghi giữa hướng hội tụ và hướng tản mát để cân bằng giữa khai thác và khám phá trong quá trình tiến hóa. Điều này giúp MOEA duy trì sự cân bằng giữa hội tụ và đa dạng của các giải pháp.

2.2. Phương pháp chọn lọc dựa trên mật độ tia

Phương pháp chọn lọc dựa trên mật độ tia được sử dụng để chọn lọc các giải pháp bị chi phối và tạo ra các biến đổi mới. Phương pháp này giúp cải thiện chất lượng của tập các giải pháp tối ưu Pareto.

III. Ứng dụng của giải thuật tiến hóa đa mục tiêu

Luận án không chỉ tập trung vào việc cải thiện hiệu suất của giải thuật tiến hóa đa mục tiêu mà còn đề xuất các ứng dụng thực tế của phương pháp này. Một trong những ứng dụng nổi bật là hệ thống phát hiện thư rác dựa trên SpamAssassin sử dụng DMEA-II.

3.1. Hệ thống phát hiện thư rác dựa trên SpamAssassin

Hệ thống phát hiện thư rác dựa trên SpamAssassin sử dụng giải thuật tiến hóa đa mục tiêu DMEA-II để cải thiện hiệu suất phát hiện thư rác. Hệ thống này giúp người dùng có thêm các lựa chọn tốt hơn trong việc cấu hình SpamAssassin.

3.2. Phương pháp tương tác với người ra quyết định

Luận án cũng đề xuất một phương pháp tương tác với người ra quyết định trong quá trình tối ưu hóa. Phương pháp này sử dụng ba cách tiếp cận dựa trên tia: Thay thế tia, Phân phối lại tia và Tạo giá trị thêm vào. Các thí nghiệm cho thấy kết quả khả quan trên nhiều bài toán kiểm tra.