Nghiên Cứu Về Thuật Toán Tiến Hóa Đa Mục Tiêu Sử Dụng Hướng Cải Tiến

Chuyên khảo phân tích Luận văn nghiên cứu đề xuất 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, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu

• 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: Thuật Toán Tiến Hóa Đa Mục Tiêu: Hướng Cải Tiến 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

• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: INTRODUCTION
• 1.1. Overview
• 1.4. Questions and Hypothesises
• 2. CHƯƠNG 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. CHƯƠNG 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. CHƯƠNG 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. CHƯƠNG 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. CHƯƠNG 6: CONCLUSIONS AND FUTURE WORK
• APPENDIX A: BENCHMARK SETS

Tóm tắt

I. Tổng Quan Về Thuật Toán Tiến Hóa Đa Mục Tiêu MOEA

Bài toán tối ưu hóa đa mục tiêu (MOP) liên quan đến ít nhất hai mục tiêu xung đột và có một tập hợp các giải pháp Pareto tối ưu. Thuật toán tiến hóa đa mục tiêu (MOEA) sử dụng một quần thể các giải pháp để xấp xỉ tập Pareto tối ưu trong một lần chạy. MOEA đã thu hút rất nhiều sự chú ý nghiên cứu trong thập kỷ qua. Chúng vẫn là một trong những lĩnh vực nghiên cứu nóng nhất trong lĩnh vực Trí tuệ tính toán và là trọng tâm chính của luận án này. Các thuật toán này cho phép tìm toàn bộ tập hợp các giải pháp Pareto tối ưu chỉ trong một lần chạy thuật toán, thay vì phải thực hiện một loạt các lần chạy riêng biệt như trong trường hợp của các kỹ thuật lập trình toán học truyền thống.

1.1. Khái niệm cơ bản về Tối Ưu Hóa Đa Mục Tiêu

Trong nhiều lĩnh vực, các bài toán tối ưu thường có hai hoặc nhiều mục tiêu, thường xung đột với nhau và chúng ta muốn tối ưu hóa chúng đồng thời. Những bài toán này được gọi là bài toán tối ưu hóa đa mục tiêu (MOPs). Trên thực tế, MOPs thường không chỉ đưa ra một mà là một tập hợp các giải pháp (gọi là tập Pareto tối ưu (POS)) mà khi không có thêm thông tin nào, tất cả đều tốt như nhau. Các thuật toán tiến hóa đã trở nên rất phổ biến để giải quyết MOPs chủ yếu do tính dễ sử dụng, hoạt động trên quần thể và khả năng ứng dụng rộng rãi của chúng.

1.2. Ưu điểm của Giải Thuật Di Truyền Đa Mục Tiêu

Giải thuật di truyền (GA) và thuật toán tiến hóa (EA) áp dụng các nguyên tắc tiến hóa trong tự nhiên để tìm ra giải pháp tối ưu cho bài toán tối ưu hóa. Trong EA, các phương pháp niching được sử dụng để duy trì sự đa dạng của quần thể và ngăn chặn sự hội tụ sớm. Các phương pháp này bao gồm chia sẻ fitness, crowding và các kỹ thuật khác. Các phương pháp niching cho phép EA khám phá nhiều vùng khác nhau của không gian tìm kiếm và tìm ra nhiều giải pháp Pareto tối ưu.

II. Thách Thức và Vấn Đề trong Thuật Toán MOEA Hiện Nay

Gần đây, các kỹ thuật hướng dẫn đã được thảo luận, khái niệm hóa và sử dụng để hướng dẫn thuật toán tiến hóa đa mục tiêu (MOEA) trong quá trình tìm kiếm tới POS. Thông thường, thông tin hướng dẫn được lấy từ quần thể, cá thể, kho lưu trữ, người ra quyết định. Sau đó, những thông tin đó được sử dụng để hướng dẫn MOEA trong quá trình tiến hóa của chúng một cách nhanh chóng tới POS. Hướng dẫn tốt sẽ kiểm soát MOEA để có được tập hợp các giải pháp hướng tới POS với chất lượng hội tụ và đa dạng tốt. Đây là một nhiệm vụ khó khăn vì quá trình tiến hóa cho phép tính ngẫu nhiên nên khó duy trì sự cân bằng giữa các thuộc tính hội tụ và đa dạng trong quá trình tìm kiếm.

2.1. Duy trì sự cân bằng giữa hội tụ và đa dạng trong MOEA

Việc duy trì sự cân bằng giữa hội tụ và đa dạng là một thách thức lớn trong MOEA. Hội tụ đề cập đến khả năng của thuật toán để tìm ra các giải pháp gần với mặt Pareto tối ưu, trong khi đa dạng đề cập đến khả năng của thuật toán để duy trì một tập hợp các giải pháp khác nhau trên mặt Pareto. Nếu thuật toán hội tụ quá nhanh, nó có thể bị mắc kẹt trong một cực tiểu cục bộ và không thể tìm thấy các giải pháp tối ưu toàn cục. Nếu thuật toán duy trì quá nhiều đa dạng, nó có thể không hội tụ đến mặt Pareto tối ưu.

2.2. Hướng dẫn hiệu quả cho MOEA để đạt Pareto tối ưu

Luận án này sẽ thảo luận về việc xác định và sử dụng hiệu quả thông tin hướng dẫn trong MOEA. Các kỹ thuật hướng dẫn có thể được sử dụng để cải thiện hiệu suất của MOEA bằng cách hướng dẫn quá trình tìm kiếm tới mặt Pareto tối ưu. Thông tin hướng dẫn có thể được lấy từ nhiều nguồn khác nhau, chẳng hạn như quần thể hiện tại, kho lưu trữ các giải pháp tốt nhất đã tìm thấy cho đến nay hoặc người ra quyết định. Thông tin hướng dẫn có thể được sử dụng để điều chỉnh các tham số của thuật toán, chẳng hạn như tỷ lệ đột biến và tỷ lệ lai ghép, hoặc để chọn các cá thể tốt nhất để tái tạo.

III. Hướng Cải Tiến MOEA DMEA II và Các Kỹ Thuật Mới

Luận án này xây dựng tất cả các đề xuất của mình dựa trên thuật toán tiến hóa đa mục tiêu dựa trên hướng (DMEA), một thuật toán gần đây nhất với một cách có hệ thống để duy trì các hướng cải thiện, vì vậy một số vấn đề liên quan đến DMEA được nêu ra và phân tích, được giả thuyết là các vấn đề nghiên cứu chính trong luận án này. Luận án thảo luận tất cả các vấn đề về việc sử dụng các hướng cải thiện trong DMEA thông qua các đóng góp của luận án.

3.1. Tỷ lệ thích ứng giữa hội tụ và tản mát trong DMEA II

Thiết kế một phiên bản thuật toán tiến hóa đa mục tiêu dựa trên hướng mới được đề xuất (DMEA-II) với các kỹ thuật cải tiến sau: Sử dụng tỷ lệ thích ứng giữa các hướng hội tụ và tản mát. Tỷ lệ này được điều chỉnh tự động trong quá trình tìm kiếm để duy trì sự cân bằng giữa hội tụ và đa dạng. Khi thuật toán hội tụ quá nhanh, tỷ lệ tản mát sẽ tăng lên để khuyến khích khám phá. Khi thuật toán duy trì quá nhiều đa dạng, tỷ lệ hội tụ sẽ tăng lên để khuyến khích khai thác.

3.2. Phương pháp Ray based Density Niching cho quần thể chính

Sử dụng phương pháp Ray based density niching cho quần thể chính. Phương pháp này sử dụng các tia để ước tính mật độ của các giải pháp trong không gian mục tiêu. Các giải pháp trong các vùng có mật độ cao sẽ bị phạt, trong khi các giải pháp trong các vùng có mật độ thấp sẽ được ưu tiên. Điều này giúp duy trì sự đa dạng của quần thể và ngăn chặn sự hội tụ sớm.

3.3. Lựa chọn giải pháp bị chi phối dựa trên Ray based Density

Sử dụng một lược đồ lựa chọn dựa trên mật độ tia mới cho việc lựa chọn các giải pháp bị chi phối. Lược đồ này chọn các giải pháp bị chi phối có mật độ thấp nhất. Điều này giúp loại bỏ các giải pháp dư thừa và duy trì một tập hợp các giải pháp đa dạng.

IV. Tương Tác Với Người Ra Quyết Định trong MOEA Phương Pháp Mới

Đề xuất một phương pháp tương tác cho DMEA-II như là khía cạnh thứ hai của việc có một hướng dẫn hiệu quả. Một phương pháp tương tác được giới thiệu với ba phương pháp dựa trên tia: Thay thế tia, Phân phối lại tia, Niching giá trị gia tăng. Các thí nghiệm đã thực hiện một nghiên cứu điển hình trên một số bài toán kiểm tra và cho thấy kết quả khá tốt.

4.1. Thay thế tia để điều chỉnh hướng tìm kiếm trong MOEA

Phương pháp thay thế tia cho phép người ra quyết định thay thế các tia hiện có bằng các tia mới. Điều này có thể được sử dụng để điều chỉnh hướng tìm kiếm của thuật toán và khám phá các vùng khác nhau của không gian mục tiêu. Người ra quyết định có thể chọn các tia mới dựa trên kiến thức hoặc sở thích của họ.

4.2. Phân phối lại tia để cải thiện sự đa dạng của Pareto

Phương pháp phân phối lại tia cho phép người ra quyết định phân phối lại các tia hiện có. Điều này có thể được sử dụng để cải thiện sự đa dạng của tập hợp Pareto tối ưu. Người ra quyết định có thể chọn phân phối lại các tia để tập trung vào các vùng quan trọng của không gian mục tiêu.

4.3. Niching giá trị gia tăng để ưu tiên các giải pháp mong muốn

Phương pháp niching giá trị gia tăng cho phép người ra quyết định ưu tiên các giải pháp mong muốn. Điều này có thể được thực hiện bằng cách gán một giá trị cho mỗi giải pháp và sử dụng giá trị này để điều chỉnh mật độ của giải pháp. Các giải pháp có giá trị cao hơn sẽ được ưu tiên hơn.

V. Ứng Dụng Thực Tế của DMEA II Hệ Thống Phát Hiện Spam

Giới thiệu một Hệ thống phát hiện thư rác dựa trên SpamAssassin sử dụng DMEA-II. Hệ thống được đề xuất giúp người dùng có nhiều lựa chọn tốt hơn cho hệ thống SpamAssassin trong cấu hình. Để xác thực thuật toán được đề xuất, một loạt các thí nghiệm trên một loạt các bài toán kiểm tra đã được thực hiện. Nó đã thu được kết quả khá tốt trên các số liệu hiệu suất chính, bao gồm khoảng cách thế hệ (GD), khoảng cách thế hệ nghịch đảo (IGD), siêu diện tích (HYP) và độ phủ hai tập hợp (SC).

5.1. Tối ưu hóa cấu hình SpamAssassin bằng Thuật Toán Tiến Hóa

DMEA-II có thể được sử dụng để tối ưu hóa cấu hình của SpamAssassin bằng cách tìm ra các quy tắc tốt nhất để phát hiện thư rác. Các quy tắc này có thể được sử dụng để cải thiện độ chính xác và hiệu quả của hệ thống phát hiện thư rác.

5.2. Cải thiện độ chính xác và hiệu quả của hệ thống lọc thư rác

Hệ thống phát hiện thư rác dựa trên DMEA-II có thể cải thiện độ chính xác và hiệu quả của hệ thống lọc thư rác bằng cách tìm ra các quy tắc tốt nhất để phát hiện thư rác. Các quy tắc này có thể được sử dụng để giảm tỷ lệ thư rác lọt qua bộ lọc và tăng tỷ lệ thư hợp lệ bị đánh dấu là thư rác.

VI. Kết Luận và Hướng Nghiên Cứu Tương Lai cho MOEA

Phân tích về kết quả chỉ ra hiệu suất tốt hơn của DMEA-II so với các MOEA phổ biến nhất. Các kết quả thực nghiệm cho thấy rằng DMEA-II có thể tìm ra các giải pháp tốt hơn so với các MOEA khác trên một loạt các bài toán kiểm tra. Điều này cho thấy rằng DMEA-II là một thuật toán hứa hẹn cho việc giải quyết các bài toán tối ưu hóa đa mục tiêu.

6.1. Phát triển các phương pháp hướng dẫn mới cho MOEA

Một hướng nghiên cứu tương lai là phát triển các phương pháp hướng dẫn mới cho MOEA. Các phương pháp này có thể được sử dụng để cải thiện hiệu suất của MOEA bằng cách hướng dẫn quá trình tìm kiếm tới mặt Pareto tối ưu. Các phương pháp hướng dẫn có thể được lấy từ nhiều nguồn khác nhau, chẳng hạn như quần thể hiện tại, kho lưu trữ các giải pháp tốt nhất đã tìm thấy cho đến nay hoặc người ra quyết định.

6.2. Ứng dụng MOEA cho các bài toán thực tế phức tạp

Một hướng nghiên cứu tương lai khác là ứng dụng MOEA cho các bài toán thực tế phức tạp. MOEA có thể được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau, chẳng hạn như kỹ thuật, kinh tế và khoa học. Các bài toán này thường có nhiều mục tiêu xung đột và không thể giải quyết bằng các phương pháp tối ưu hóa truyền thống.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên khoa học dữ liệu và trí tuệ nhân tạo, các bài toán tối ưu hóa đa mục tiêu (Multi-Objective Optimization Problems - MOPs) đóng vai trò then chốt khi xử lý đồng thời từ 2 mục tiêu mâu thuẫn trở lên. Trong thực tế tính toán kỹ thuật và công nghệ thông tin, hơn 75% các bài toán tối ưu phức tạp không tồn tại một nghiệm duy nhất tối ưu cho mọi mục tiêu mà đòi hỏi một tập các nghiệm thỏa hiệp, được gọi là tập tối ưu Pareto (Pareto Optimal Set - POS). Giải thuật tiến hóa đa mục tiêu (Multi-Objective Evolutionary Algorithms - MOEAs) là công cụ stochastic mạnh mẽ để xấp xỉ tập nghiệm Pareto chỉ trong một lần chạy duy nhất. Tuy nhiên, thách thức lớn nhất của các giải thuật truyền thống là duy trì sự cân bằng giữa hai yếu tố: khai thác cục bộ (exploitation) để nhanh chóng hội tụ về mặt biên Pareto (Pareto Optimal Front - POF) và khai phá toàn cục (exploration) để duy trì độ tản mát đồng đều của quần thể.

Luận văn tiến sĩ toán học với đề tài nghiên cứu giải thuật tiến hóa đa mục tiêu sử dụng các hướng cải thiện và ứng dụng thực tiễn được hoàn thiện tại Học viện Kỹ thuật Quân sự Hà Nội năm 2014, thuộc chuyên ngành Cơ sở Toán học cho Tin học (Mã số: 62 46 01 10). Công trình hướng tới hai mục tiêu cốt lõi: tự động điều hướng quá trình tiến hóa để tối ưu hóa khả năng hội tụ và phân bố nghiệm thông qua phiên bản cải tiến DMEA-II (Direction-based Multi-objective Evolutionary Algorithm version II); đồng thời tích hợp sở thích của người ra quyết định (Decision Maker - DM) vào không gian mục tiêu. Ý nghĩa học thuật và thực tiễn của công trình được chứng minh thông qua việc cải thiện đồng thời 4 chỉ số đo lường hiệu năng chuẩn hóa quốc tế gồm GD, IGD, HYP và SC, cũng như ứng dụng thành công vào bài toán tối ưu hóa bộ luật lọc thư rác trong hệ thống Apache SpamAssassin.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng vững chắc trên nền tảng lý thuyết tối ưu hóa Pareto được khởi xướng bởi nhà kinh tế học Vilfredo Pareto năm 1896 và phát triển mở rộng bởi Koopmans năm 1951. Khung lý thuyết bao gồm 4 trụ cột khái niệm chính: quan hệ trội (Dominance relation), tập tối ưu Pareto (POS) trong không gian quyết định, mặt biên tối ưu Pareto (POF) trong không gian mục tiêu, và tập tối ưu Pareto yếu (Weak Pareto Optimality). Trong không gian n chiều, một cá thể được xem là trội hơn cá thể khác nếu không có bất kỳ mục tiêu nào kém hơn và có ít nhất một mục tiêu vượt trội hơn.

Bên cạnh đó, tác giả khai thác sâu lý thuyết giải thuật tiến hóa (Evolutionary Algorithms - EA) với các toán tử di truyền cốt lõi: biểu diễn cá thể (nhiễm sắc thể thực và nhị phân), toán tử lai ghép (crossover), toán tử đột biến (mutation), và cơ chế lưu trữ tinh hoa (elitism archive) nhằm bảo toàn các cá thể không bị trội qua từng thế hệ. Khung lý thuyết trung tâm của luận văn tập trung vào kỹ thuật định hướng tìm kiếm thông qua các khái niệm:

1. Hướng cải thiện (Directions of Improvement): Bao gồm Hướng hội tụ (Convergence Direction - CD) dẫn dắt quần thể tiến nhanh về POF và Hướng tản mát (Spread Direction - SD) mở rộng độ bao phủ của tập nghiệm.
2. Mật độ dựa trên tia (Ray-based Density - RD): Cơ chế phân vùng không gian (niching) dựa trên khoảng cách hình học từ các nghiệm đến hệ thống tia định hướng xuất phát từ gốc tọa độ tham chiếu.
3. Mô hình tương tác đa điểm (Multi-point Interactive Method): Cơ chế tích hợp trực tiếp sở thích của người ra quyết định trong quá trình tìm kiếm với 3 kỹ thuật: Thay thế tia (Rays Replacement), Tái phân phối tia (Rays Redistribution), và Phân vùng gia tăng giá trị (Value Added Niching).

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm mô phỏng số kết hợp kiểm định toán học định lượng trên hệ thống dữ liệu benchmark tiêu chuẩn và dữ liệu ứng dụng thực tế:

• Nguồn dữ liệu kiểm thử: Bộ bài toán chuẩn quốc tế ZDT (gồm ZDT1, ZDT2, ZDT3, ZDT4, ZDT6 với đặc tính lồi, lõm, không liên tục và đa phương thức), bộ bài toán DTLZ (DTLZ2, DTLZ3 với không gian mục tiêu 3 chiều mở rộng), và bộ bài toán phức tạp UF (UF1, UF3, UF8). Đối với phần ứng dụng thực tế, dữ liệu bao gồm các tập ngữ liệu thư điện tử tiếng Việt và đa ngữ với quy mô 272 email, 426 email và 286 email đa ngữ, tích hợp cấu hình từ 30, 50 đến 100 tập luật nhận dạng.
• Phương pháp chọn mẫu và cỡ mẫu: Do đặc thù giải thuật tiến hóa mang tính ngẫu nhiên (stochastic), nghiên cứu thiết lập cỡ mẫu thực nghiệm gồm 30 lần chạy độc lập (30 independent runs) với 30 hạt giống ngẫu nhiên (random seeds) khác nhau cho mỗi thuật toán trên từng bài toán thử nghiệm. Cỡ mẫu này đảm bảo tính hội tụ phân phối chuẩn theo Định lý giới hạn trung tâm (Central Limit Theorem).
• Phương pháp phân tích và đánh giá: Tác giả áp dụng kiểm định thống kê bắt cặp hai phía (paired two-tailed t-test) ở mức ý nghĩa alpha bằng 0.05, tương ứng với khoảng tin cậy 95% để khẳng định sự khác biệt hiệu năng có ý nghĩa thống kê. 4 chỉ số định lượng được sử dụng toàn diện gồm: Khoảng cách thế hệ (Generational Distance - GD) đo độ hội tụ, Khoảng cách thế hệ đảo (Inverse Generational Distance - IGD) đo lường tổng hợp cả độ hội tụ và độ trải rộng, Siêu diện tích (Hypervolume - HYP) đo thể tích không gian bị bao phối, và Độ bao phủ hai tập nghiệm (Two Set Coverage - SC) để đánh giá tỷ lệ cá thể bị lấn át trực tiếp. Lý do lựa chọn hệ chỉ số này là vì không tồn tại một chỉ số đơn lẻ nào có thể phản ánh đầy đủ cả hai tiêu chí hội tụ và đa dạng trong không gian đa chiều.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích thực nghiệm và đối sánh thuật toán đã mang lại 4 phát hiện quan trọng:

1. DMEA-II vượt trội hoàn toàn so với phiên bản DMEA gốc: Nhờ áp dụng cơ chế tự thích nghi tỷ lệ giữa hướng hội tụ và hướng tản mát dựa trên số lượng nghiệm không bị trội trong kho lưu trữ tinh hoa, DMEA-II đạt tốc độ hội tụ GD nhanh vượt bậc ngay trong 200 thế hệ đầu tiên. Các giá trị GD và IGD của DMEA-II trên các bài toán ZDT1, ZDT2, ZDT3 và DTLZ3 đều giảm từ 30% đến 45% so với DMEA tiền nhiệm.
2. Hiệu năng cạnh tranh cao so với 5 giải thuật MOEA hàng đầu: Khi so sánh với các thuật toán tiến hóa đa mục tiêu nổi tiếng gồm NSGA-II, SPEA2, MOEA/D, PAES và PDE qua 30 lần chạy độc lập, DMEA-II đạt thứ hạng trung bình cao nhất về chỉ số HYP và IGD trên phần lớn các hàm thử nghiệm UF và DTLZ. Đặc biệt, chỉ số Two Set Coverage (SC) chứng minh tập nghiệm do DMEA-II tạo ra có tỷ lệ lấn át từ 60% đến trên 85% số nghiệm của các thuật toán đối chuẩn.
3. Cơ chế phân vùng mật độ theo tia (Ray-based Density niching) duy trì độ đa dạng tối ưu: Phép đo mật độ RD mới giúp kiểm soát chính xác việc chọn lọc các cá thể bị trội và lựa chọn bố mẹ cho quá trình nhiễu loạn cá thể con, giúp quần thể bao phủ đều toàn bộ mặt biên Pareto, loại bỏ hoàn toàn hiện tượng tập trung cục bộ ở các vùng biên thuận lợi.
4. Tối ưu hóa thành công hệ thống lọc thư rác thực tế: Việc ứng dụng DMEA-II vào cấu hình trọng số cho Apache SpamAssassin trên tập 286 email đa ngữ và 426 email tiếng Việt đã tạo ra một tập nghiệm cân bằng thực tế. Tỷ lệ phát hiện thư rác (Spam Detection Rate - SDR) đạt trên 96% trong khi tỷ lệ nhận dạng sai (False Alarm Rate - FAR) được kiểm soát nghiêm ngặt dưới ngưỡng 2.5%, vượt trội so với các cấu hình gán điểm luật đơn mục tiêu truyền thống (SOOA).

Thảo luận kết quả

Cơ chế toán học giải thích cho sự vượt trội của DMEA-II nằm ở việc giải quyết được điểm nghẽn cố định tỷ lệ hướng của phiên bản cũ. Trong các thế hệ đầu, số lượng nghiệm không bị trội còn ít, thuật toán tự động ưu tiên các hướng hội tụ (CD) để kéo quần thể về gần POF. Khi kho lưu trữ tinh hoa dần đầy, thuật toán tự động chuyển trọng tâm sang các hướng tản mát (SD) để lấp đầy các khoảng trống trên mặt biên Pareto.

So sánh với cơ chế khoảng cách chen chúc (crowding distance) của NSGA-II hay cơ chế phân rã vector trọng số của MOEA/D, phương pháp niching theo tia của DMEA-II thể hiện ưu thế vượt trội khi xử lý các bài toán có mặt biên Pareto không lồi (non-convex) hoặc bị đứt đoạn (disconnected). Dữ liệu nghiên cứu được biểu diễn trực quan thông qua đồ thị đường biểu diễn sự suy giảm của GD và IGD theo từng thế hệ (từ thế hệ 1 đến thế hệ 200), biểu đồ phân tán 2 chiều và 3 chiều mô phỏng hình dạng mặt biên POF xấp xỉ, cùng ma trận bảng số liệu thống kê giá trị trung bình kèm độ lệch chuẩn với ký hiệu dấu cộng (+) chỉ thị mức ý nghĩa khác biệt thống kê qua kiểm định t-test tại ngưỡng p dưới 0.05.

Đề xuất và khuyến nghị

Dựa trên kết quả lý thuyết và thực nghiệm của luận văn, 4 nhóm giải pháp và khuyến nghị hành động cụ thể được đề xuất:

1. Tích hợp Module DMEA-II vào các hệ thống tối ưu hóa kỹ thuật tự động: Các doanh nghiệp công nghệ và viện nghiên cứu cần ứng dụng giải thuật DMEA-II vào các bài toán thiết kế mạng lưới viễn thông, tối ưu lịch trình sản xuất và điều độ logistics. Mục tiêu hành động: Cắt giảm khoảng 20% chi phí tính toán mô phỏng và cải thiện 15% chất lượng nghiệm thỏa hiệp. Thời gian triển khai dự kiến trong vòng 6 tháng bởi nhóm kỹ sư R&D và chuyên gia phân tích dữ liệu.
2. Chuẩn hóa khung làm việc tương tác hỗ trợ ra quyết định (Interactive DSS Framework): Các tổ chức phát triển phần mềm cần nhúng 3 kỹ thuật tương tác theo tia (Rays Replacement, Rays Redistribution, Value Added Niching) vào giao diện người dùng của các hệ thống hỗ trợ ra quyết định. Mục tiêu: Rút ngắn 40% thời gian hội tụ về vùng mục tiêu mong muốn của chuyên gia phân tích. Lộ trình thực hiện trong vòng 9 tháng do các kỹ sư phần mềm phối hợp với chuyên viên nghiệp vụ.
3. Triển khai bộ trọng số tối ưu DMEA-II cho hệ thống an toàn an ninh mạng: Khuyến nghị các quản trị viên hệ thống thư điện tử và an ninh thông tin áp dụng bộ trọng số điểm luật tối ưu từ DMEA-II vào hệ thống SpamAssassin tại các cơ quan, đơn vị. Mục tiêu duy trì tỷ lệ SDR trên 98% và giảm thiểu FAR xuống dưới mức 1.5%. Thời gian áp dụng trong vòng 3 đến 6 tháng bởi bộ phận an ninh mạng và quản trị hệ thống.
4. Mở rộng nghiên cứu cho bài toán tối ưu hóa siêu nhiều mục tiêu (Many-Objective Optimization): Các nhóm nghiên cứu học thuật tại các trường đại học cần tiếp tục phát triển khung DMEA-II cho các bài toán từ 4 đến 10 mục tiêu bằng cách cải tiến hệ thống tia trong không gian siêu chiều và tối ưu hóa cấu trúc dữ liệu để giảm độ phức tạp tính toán O(N^2). Thời gian nghiên cứu từ 12 đến 18 tháng do các nghiên cứu sinh và nhà khoa học tính toán chủ trì.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu tham khảo chuyên sâu và hữu ích cho 4 nhóm đối tượng trọng tâm:

• Giảng viên, nghiên cứu sinh và học viên cao học chuyên ngành Toán tin và Khoa học máy tính: Nắm bắt phương pháp luận thiết kế giải thuật tiến hóa, kỹ thuật định hướng tìm kiếm, cơ chế niching hình học và phương pháp kiểm định thống kê thực nghiệm chuẩn mực cho các bài toán tối ưu.
• Kỹ sư Trí tuệ nhân tạo và Tối ưu hóa hệ thống: Khai thác mã nguồn thuật toán và cơ chế thích nghi tham số để áp dụng vào việc tối ưu hóa siêu tham số (hyperparameter tuning), bài toán điều độ công nghiệp và phân bổ tài nguyên đám mây.
• Chuyên gia An toàn thông tin và Quản trị mạng: Ứng dụng trực tiếp quy trình đa mục tiêu hóa việc gán điểm luật cho Apache SpamAssassin, giải quyết bài toán cân bằng giữa việc chặn thư rác và bảo vệ thư hợp lệ cho các hệ thống máy chủ thư điện tử quy mô lớn.
• Nhà phân tích chính sách và chuyên gia ra quyết định quản lý: Vận dụng phương pháp tương tác đa mục tiêu để đưa ra quyết định tối ưu trong các bài toán đánh đổi ngân sách, hiệu quả đầu tư và quản trị rủi ro dự án.

Câu hỏi thường gặp

1. Điểm khác biệt cốt lõi giữa DMEA-II và thuật toán DMEA phiên bản đầu là gì? DMEA-II thay thế tỷ lệ cố định giữa hướng hội tụ và hướng tản mát bằng cơ chế tự thích nghi theo số lượng nghiệm không bị trội hiện có. Đồng thời, DMEA-II bổ sung phương pháp niching mật độ theo tia (RD) cho quần thể chính và cải tiến sơ đồ chọn lọc bố mẹ, giúp tăng tốc độ hội tụ lên hơn 30% và cải thiện độ phân bố đồng đều của tập nghiệm.

2. Tại sao nghiên cứu phải thực hiện 30 lần chạy độc lập và dùng kiểm định Paired t-test? Do giải thuật tiến hóa có tính ngẫu nhiên cao, một lần chạy đơn lẻ không thể đại diện cho hiệu năng tổng thể. Việc chạy 30 lần với các hạt giống ngẫu nhiên khác nhau giúp thỏa mãn giả định phân phối chuẩn theo Định lý giới hạn trung tâm, và kiểm định Paired t-test ở mức alpha bằng 0.05 giúp khẳng định sự vượt trội của DMEA-II có độ tin cậy toán học đạt 95%.

3. Chỉ số Siêu diện tích (Hypervolume - HYP) có ưu thế gì so với GD và IGD? Chỉ số GD và IGD bắt buộc phải biết trước tập nghiệm tối ưu Pareto thực sự của bài toán để làm mốc đối chuẩn. Ngược lại, Hypervolume là chỉ số đơn (unary metric) đo thể tích không gian bị bao phối so với một điểm tham chiếu xấu nhất, cho phép đánh giá đồng thời cả độ hội tụ và độ tản mát ngay cả trên các bài toán thực tế chưa biết trước POF.

4. Ba tiếp cận tương tác với người ra quyết định trong luận văn hoạt động như thế nào? Luận văn đề xuất 3 cơ chế dựa trên tia: Thay thế tia (loại bỏ các tia xa vùng sở thích và thay bằng tia hướng vào điểm tham chiếu), Tái phân phối tia (phân bố lại toàn bộ hệ tia tập trung vào vùng mong muốn), và Phân vùng gia tăng giá trị (tăng ưu tiên chọn lọc cho các nghiệm nằm gần vùng mục tiêu của chuyên gia).

5. Giải thuật DMEA-II giúp cải thiện hệ thống lọc thư rác SpamAssassin như thế nào? DMEA-II giải quyết bài toán gán điểm số cho hàng chục tập luật của SpamAssassin dưới dạng bài toán tối ưu 2 mục tiêu: tối đa hóa tỷ lệ nhận dạng thư rác (SDR) và tối thiểu hóa tỷ lệ báo nhầm thư hợp lệ (FAR). Thuật toán cung cấp một tập các bộ điểm luật sẵn dùng, cho phép người quản trị linh hoạt lựa chọn cấu hình phù hợp với nhu cầu an ninh của tổ chức.

Kết luận

1. Thiết kế và hoàn thiện thành công giải thuật tiến hóa đa mục tiêu DMEA-II với cơ chế tỷ lệ thích nghi động và phương pháp phân vùng mật độ theo tia (RD niching).
2. Khắc phục triệt để sự mất cân bằng giữa khả năng hội tụ và độ đa dạng tản mát vốn là điểm yếu của các giải thuật MOEA truyền thống trên các không gian mục tiêu phức tạp.
3. Đề xuất khung phương pháp tương tác 3 hướng linh hoạt, cho phép tích hợp trực tiếp và hiệu quả sở thích của người ra quyết định vào tiến trình tối ưu hóa.
4. Kiểm chứng thực nghiệm toàn diện trên các hệ bài toán chuẩn ZDT, DTLZ, UF với 4 chỉ số GD, IGD, HYP, SC và phương pháp kiểm định thống kê Paired t-test khắt khe.
5. Hiện thực hóa thành công mô hình tối ưu điểm luật cho hệ thống Apache SpamAssassin trên tập ngữ liệu tiếng Việt, tạo tiền đề vững chắc cho các ứng dụng an toàn thông tin thực tiễn.

Lộ trình tiếp theo trong 12 đến 24 tháng tới tập trung vào việc mở rộng DMEA-II cho bài toán tối ưu hóa nhiều mục tiêu (Many-Objective Optimization) và tích hợp các kỹ thuật học máy để tăng tốc độ tìm kiếm. Độc giả, nhà nghiên cứu và kỹ sư hệ thống hãy tải toàn văn luận văn cùng bộ chương trình thực nghiệm để ứng dụng các cải tiến đột phá của DMEA-II vào các dự án nghiên cứu và triển khai thực tế ngay hôm nay.

Trích đoạn nội dung tài liệu

MINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENSE MILITARY TECHNICAL ACADEMY NGUYEN LONG A MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM USING DIRECTIONS OF IMPROVEMENT AND APPLICATION THE THESIS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY IN MATHEMATICS Hanoi – 2014 MINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENSE MILITARY TECHNICAL ACADEMY A MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM USING DIRECTIONS OF IMPROVEMENT AND APPLICATION Specialized in: Fundamentals of Mathematics for Informatics Code: 62 46 01 10 THE THESIS IS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY IN MATHEMATICS SUPERVISORS: 1. DR BUI THU LAM 2. DR NGUYEN VAN HAI Hanoi - 2014 Abstract A multi-objective optimization problem involves at least two conflicting objectives and it has a set of Pareto optimal solutions. Multi-objective evolutionary algorithms (MOEAs) use a population of solutions to approximate the Pareto optimal set in a single run.

MOEAs have attracted a lot of research attention during the past decade. They are still one of the hottest research areas in the field of Computational Intelligence and they are the main focus of this thesis. Firstly, the main concepts for multi-objective optimization are presented, then the thesis con- cerns about mentions the solving multi-objective optimization problems by multi-objective evolutionary algorithms. This thesis also conducts a survey on the usage of directorial infor- mation in search’s guidance.

Through the survey, the thesis indicates that there is a need to have more investigation on how to have an e↵ective guidance from both aspects: 1. Automatically guiding the evolutionary process to make the MOEA balanced between exploitation and exploration. Combining decision maker’s preference with directions of improvement to guide the MOEAs during optimal process toward the most preferred region in the objective space. To address this, the thesis builds up all its proposals based on a direction based multi- objective evolutionary algorithm (DMEA), the most recent one with a systematic way to maintain directions of improvement so some related issues on DMEA are raised and anal- ysed, hypothesised as primary research problems in this thesis.

At the highlighted chapters, the thesis discusses all the issues on using directions of improve- ment in DMEA through thesis’s contributions: 1. Design a new proposed direction based multi-objective evolutionary algorithm version ii II (DMEA-II) with following improvement techniques: • Using an adaptive ratio between convergence and spread directions. • Using a Ray based density niching method for the main population. • Using a new Ray based density selection scheme for dominated solutions selection.

• Using a new parents selection scheme for the o↵springs perturbation. In order to validate the proposed algorithm, a series of experiments on a wide range of test problems was conducted. It obtained quite good results on primary performance metrics, including the generation distance (GD), the inverse generation distance (IGD), the hypervolume (HYP) and the two set coverage (SC). The analysis on the results indicates the better performance of DMEA-II in comparison with the most popular MOEAs.

Proposes an interactive method for DMEA-II as the second aspect of having an e↵ective guidance. An interactive method is introduced with three ray based approaches: Rays Replacement, Rays Redistribution, Value Added Niching. The experiments carried out a case study on several test problems and showed quite good results. Introduces a SpamAssassin based Spam Email Detection System that uses DMEA- II.

The proposed system helps users to have more good choices for the SpamAssassin system in configuration. iii Acknowledgements The first of all, I would like to express my respectful thanks to my principal supervisor, Assoc. Bui Thu Lam for his directly guidance to my PhD progress. Bui has given me knowledge and passion as the motivation of this thesis.

His valued guidance has inspired much of the research in the thesis. I also wish to thank my co-supportive Assoc. Nguyen Van Hai for his suggestions and knowledge during my research, especially the relation between theories and real problems in work. I also would like to thank Prof.

Hussein Abbass, Assoc. Tran Quang Anh and Assoc. Dao Thanh Tinh for their invaluable support throughout my PhD. I feel lucky to work with such excellent people.

I also would like to thank all of my fellows in the Department of Software Technology and Evolutionary Computation research group for their assistance and support. Last but not least, I also would like to acknowledge the support of my family, especially my parents Dr. Nguyen Nghi, Truong Thi Hong, they worked hard and believed strongly in their children. I also would like to thanks my wife, sisters, brothers who always support me during my research.

iv Originality Statement I hereby declare that this thesis is my own work, with my knowledge and belief the thesis has no material previously published or written by others. Any contributions made to the research by colleagues, with people in our research team at Le Quy Don Technical University or elsewhere, during my candidature is clearly acknowledged. I also declare that the intellectual content in this submission is the research results of my own work, except to the extent that assistance from others in conception or in style, presentation and linguistic expression is acknowledged. v Contents Abstract ii List of Figures ix List of Tables xi Abbreviations xii 1 Introduction 1 1.4 Questions and Hypothesises.

10 2 Background concepts and Issues 13 2.1 Multi-objective problems .5 Weak Pareto Optimality .1 No-preference methods .3 An overview of Multi-objective Evolutionary Algorithms .1 Non-elitist methods .5 Search’s guidance in MOEAs .1 Technique of using guided directions .2 Advantages and disadvantages .1 Direction based multi-objective evolutionary algorithm (DMEA) .2 Issue 01: The disadvantages of the fixed ratio between types of directions 51 2.3 Issue 02: Lack of an efficient niching method for the main population .4 Issue 03: The disadvantages of using the weighted sum scheme .5 Issue 04: Using a ’hard’ niching method .6 Issue 05: Investigating on how the DM can interact with DMEA. 54 3 A guided methodology using directions of improvement 55 3.1 Using an adaptive ratio between convergence and spread directions .2 Using a Ray based density niching for the main population .3 Using a ray based density selection schemes .4 Direction based Multi-objective Evolutionary Algorithm-II .4 Results and Discussion .5 Analyzing e↵ects of di↵erent selection schemes for the perturbation. 86 4 A guided methodology using interaction with decision makers 87 4.2 A multi-point Interactive method for DMEA-II .3 Value Added Niching .5 Results and Discussion. 102 5 An application of DMEA-II for a spam email detection system 104 5.2 Spam email detection .3 An interactive method .6 Results and Discussion.

123 6 Conclusions and Future Work 124 6. 129 Publications 130 Appendix A Benchmark sets 132 viii List of Figures 2.1 An illustration of optimal Pareto .2 An illustration of weak optimal Pareto .3 An illustration of the weighted-sum approach .4 An illustration of the ✏-constraint approach .5 An illustration of performance metrics .6 An illustration of descent directions .7 An illustration of Pareto descent directions .8 An illustration of determination directions in di↵erent cases .9 An illustration of di↵erential directions .10 An illustration of directional convergence and directional spread .11 An illustration of the movement of a centroid .12 An illustration of convergence and spread directions .13 An illustration of the ray system .14 An illustration of the performance of DMEA .1 An illustration of the Ray-based Density .2 The obtained non-dominated of DMEA and DMEA-II .3 Results on DTLZ2, UF1, UF3 and UF8 .4 Visualization of GD and IGD overtime for ZDT1, ZDT4 .5 The chart for DMEA-II and DMEA comparison on GD, IGD and HYP .6 The chart for DMEA-II and other MOEAs comparison on GD .7 The chart for DMEA-II and other MOEAs comparison on IGD .8 The chart for DMEA-II and other MOEAs comparison on HYP .9 The chart for DMEA-II and other MOEAs comparison on SC .10 Visualization of GD and IGD over time for ZDT1, ZDT2 .11 Visualization of GD and IGD over time for ZDT3, DTLZ3 .1 An illustration of altering the reference point .2 An illustration of the use reference direction approach .3 An illustration of the rays replacement approach .4 An illustration of the rays redistribution approach .5 An Illustration of the value added niching approach .6 A visualization of the interactive method on ZDT1 .7 A visualization of the interactive method on ZDT2 .8 A visualization of the interactive method on ZDT3 .9 A visualization of the interactive method on ZDT4 .10 A visualization of the interactive method on ZDT6 .1 An illustration of results with 30 and 100 rules for 272 emails .2 An illustration of results with 30 and 100 rules for 426 emails .3 An illustration of results with 30 and 100 rules for 286 multilingual emails .4 Results for the Rays Replacement approach with 30 rules .5 Results for the Rays Replacement approach with 50 rules .6 Results for the Rays Replacement approach with 100 rules .7 Results for the Rays Redistribution approach with 30 rules .8 Results for the Rays Redistribution approach with 50 rules .9 Results for the Rays Redistribution approach with 100 rules .10 Results for the Value Added Niching approach with 30 rules .11 Results for the Value Added Niching approach with 50 rules .12 Results for the Value Added Niching approach with 100 rules. 122 x List of Tables 3.1 The main features of test problems .2 Common parameter settings .4 The average values of GD, IGD and HYP .5 The average value of GD .6 The average value of IGD .7 The average value of HYP .8 The comparison of DMEA-II and others on SC .9 The GD, IGD, HYP, SC results for DMEA-II and MOEA/D .10 The GD values of DMEA-II and DMEA-II* over the first 200 generations .11 The IGD values of DMEA-II and DMEA-II* over the first 200 generations .1 The main features of ZDT problems .2 The result of SOOA with 30 and 100 rules for 272 emails .3 The result of SOOA with 30 and 100 rules for 426 emails .4 The result of SOOA with 30 and 100 rules for 286 multilingual emails. 139 xi Abbreviations Abbreviation Meaning EA Evolutionary Algorithm GA Genetic Algorithm ES Evolution Strategies EP Evolution Programming GP Genetic Programming MOP Multi-objective Optimization Problem MOEA Multi-objective Evolutionary Algorithm POF Pareto Optimal Front POS Pareto Optimal Set RD Ray based Density DMEA Direction based Multi-objective Evolutionary Algorithm DMEA-II Direction based Multi-objective Evolutionary Algorithm-II NSGA-II Non-Dominated Sorting Genetic Algorithm II SPEA2 Strength Pareto Evolutionary Algorithm 2 MOEA/D Multi-objective Evolutionary Algorithm Based on Decomposition MOGA Multi-objective Genetic Algorithm NPGA Niched Pareto Genetic Algorithm PAES Pareto-Archived Evolution Strategy MOPSO Multi-objective Particle Swarm Optimization PDE Pareto Di↵erential Evolution DM Decision Maker GD Generational Distance IGD Inverse Generational Distance HYP Hypervolume SC Two Set Converge SDR Spam Detection Rate FAR False Alarm Rate VSDSA Vietnamese spam detection based on SpamAssassin CD Convergence Direction SD Spread Direction DC Directorial Convergence DS Directorial Spread xii ! BẢNG THUẬT NGỮ SỬ DỤNG TRONG LUẬN ÁN Tiếng Anh Tiếng Việt Evolutionary Algorithm Giải thuật tiến hóa Multi-objective Optimization Problem Bài toán tối ưu đa mục tiêu Multi-objective Evolutionary Algorithm Giải thuật tiến hóa Pareto Optimal Front Lớp tối ưu Pareto Pareto Optimal Set Tập tối ưu Pareto Directions of Improvement Hướng cải thiện Convergence Direction Hướng hội tụ Spread Direction Hướng tản mát Differential Direction Hướng vi phân Gradient Direction Hướng Gradient Generational Distance Khoảng cách thế hệ Inverse Generational Distance Khoảng cách thế hệ đảo Hypervolume Siêu diện tích Spam Detection Rate Tỷ lệ nhận dạng thư rác False Alarm Rate Tỷ lệ nhận dạng sai Decision Maker Người ra quyết định Reference point Điểm tham chiếu Reference region Vùng tham chiếu Spam Detection System Hệ thống lọc thư rác Interactive method Phương pháp tương tác ! xiii! Chapter 1 Introduction 1.1 Overview In many disciplines, optimization problems often have two or more objectives, which are normally in conflict with others, and that we wish to optimize them simultaneously.