Bài giảng Tính toán tiến hóa - Bài 9: Multi-objective optimization

Tối ưu đa mục tiêu (Multi-objective Optimization) là một lĩnh vực nghiên cứu quan trọng trong khoa học máy tính và kỹ thuật, xuất phát từ nhu cầu giải quyết các bài toán thực tế mà ở đó cần tối ưu đồng thời nhiều mục tiêu thường xuyên mâu thuẫn lẫn nhau. Sự phức tạp của việc cân bằng các mục tiêu như lợi nhuận và rủi ro, hoặc hiệu quả và chi phí, đòi hỏi những phương pháp tiếp cận chuyên biệt vượt ra ngoài khuôn khổ tối ưu đơn mục tiêu truyền thống. Bài trình bày này nhằm giới thiệu tổng quan về khái niệm tối ưu đa mục tiêu, các hướng tiếp cận chính để giải quyết chúng, và đặc biệt đi sâu vào cấu trúc cũng như đánh giá thuật toán tiến hóa đa mục tiêu dựa trên phân hoạch (MOEA/D), một trong những phương pháp hiệu quả và được ứng dụng rộng rãi.

Giảng viên, nghiên cứu sinh, sinh viên sau đại học trong các lĩnh vực khoa học máy tính, kỹ thuật, toán ứng dụng và những người quan tâm đến tối ưu hóa đa mục tiêu và thuật toán tiến hóa.

Bài trình bày cung cấp một cái nhìn toàn diện về tối ưu đa mục tiêu (Multi-objective Optimization), một loại bài toán mà việc tìm kiếm một lời giải tối ưu duy nhất là không thể do sự xung đột nội tại giữa các hàm mục tiêu. Thay vào đó, mục tiêu là tìm ra một tập hợp các lời giải thỏa hiệp, hay còn gọi là Biên Pareto, nơi không có lời giải nào có thể được cải thiện ở một mục tiêu mà không làm giảm đi ở ít nhất một mục tiêu khác. Hai hướng tiếp cận chính được thảo luận là quy đổi bài toán đa mục tiêu về một bài toán đơn mục tiêu thông qua các phương pháp như tổng có trọng số (Weighted Sum Method) và Tchebycheff, cùng với hướng tiếp cận dựa trên khái niệm Pareto optimal để xác định tính trội và biên Pareto. Trọng tâm của tài liệu là thuật toán tiến hóa đa mục tiêu dựa trên phân hoạch (MOEA/D - Multi-objective Evolutionary Algorithm Based on Decomposition). Thuật toán này nổi bật với việc phân tách một bài toán tối ưu đa mục tiêu phức tạp thành nhiều bài toán con đơn mục tiêu, mỗi bài toán được định nghĩa bởi một vector trọng số khác nhau. Các bài toán con này được giải quyết thông qua việc tận dụng thông tin từ các bài toán "hàng xóm" gần kề, cho phép tìm kiếm và duy trì một biên Pareto đa dạng và phân bố tốt. Cấu trúc của MOEA/D được trình bày chi tiết qua ba bước chính: khởi tạo quần thể và các tham số như tập hàng xóm và điểm tham chiếu; quá trình tiến hóa theo thế hệ bao gồm tạo lời giải mới bằng lai ghép và đột biến, sửa chữa và cải thiện lời giải, cập nhật điểm tham chiếu và quần thể ngoài (External Population - EP); cuối cùng là các điều kiện dừng thuật toán. Về đánh giá, MOEA/D được ghi nhận với ưu điểm về tốc độ và khả năng tạo ra biên Pareto phân bố đều, đồng thời duy trì sự cân bằng giữa các mục tiêu, tránh hội tụ sớm. Tuy nhiên, hiệu quả của nó phụ thuộc nhiều vào việc lựa chọn tham số, đặc biệt là cách phân chia các vector trọng số, và có thể không hiệu quả bằng một số thuật toán tiến hóa đa mục tiêu khác như NSGA-II trong một số trường hợp cụ thể. Các khái niệm này giúp người đọc hiểu rõ hơn về cách tiếp cận các bài toán tối ưu đa mục tiêu phức tạp và giá trị ứng dụng của các thuật toán tiến hóa trong việc cung cấp các công cụ ra quyết định linh hoạt.