Chương 1. TỔNG QUAN nó là một lời giải cực tiểu địa phương. Tuy nhiên khi giãn rộng hai đường kẻ này ra hai bên, lời giải màu xanh không còn tiếp tục là điểm thấp nhất nữa nên nó không phải là lời giải cực tiểu toàn cục. Với cách làm tương tư, điểm màu đỏ luôn là điểm thấp nhất trong toàn bộ không gian tìm kiếm nên nó là một lời giải cực tiểu toàn cục.
Mục tiêu lý tưởng của các bài toán MMO là thu thập chính xác một tập hợp bao gồm tất cả lời giải cực tiểu toàn cục của hàm mục tiêu ƒ(-) tương ứng. Tuy nhiên, việc xác định chính xác một lời giải nào đó trong không gian liên tục là bất khả thi đo hệ thống biểu diễn số của máy tính không cho phép. Vì vậy, thông thường, mục tiêu lúc này chỉ cần xác định một tập hợp xấp xỉ sao cho các lời giải tìm được nằm gần với lời giải cực tiểu toàn cục trong bán kính cho phép (bán kính này được chọn là 10-5 trong khóa luận này). Ví dụ, quay lại hình [1.1] không gian tìm kiếm được minh họa chứa 18 vi trí có màu tối nhất tương ứng với các lời giải cực tiểu toàn cục.
Nhiệm vụ của bài toán là xác định tất cả các lời giải thuộc 18 vị trí này. 112 Hướng tiếp cận Phụ thuộc vào lượng thông tin khai thác được, một bài toán Tối ưu hóa có thể được tiếp cận với hai cách thức chính là Hộp den (black-box) và Hộp trắng (white-box).3|mô tả hai cách thức tiếp cận này. Ở dạng hộp đen, ngoài những thông tin cần thiết để tạo một lời giải hợp lệ (như số chiều của không gian tìm kiếm và phạm vi giá trị), người giải quyết sẽ không được cho biết về cách thức tính toán giá trị hàm mục tiêu của bài toán. Cách duy nhất để xác định chất lượng của một lời giải là cho lời giải đó tương tác với bài toán, từ đó bài toán mới trả về một con số tương ứng với giá trị hàm mục tiêu.
Ngược lại, cách thức tiếp cận hộp trắng lại cung cấp đầy đủ cho người giải quyết tất cả thông tin ma dang hộp đen ẩn đi. Có thể thay ngay rằng để giải quyết bài toàn hộp đen sẽ cần nhiều lần thử sai rồi mới có thể cho ra một lời giải đủ tốt, trong khi với thông tin về cách thức tính toán của hàm mục tiêu từ hộp trắng, lời giải tối ưu có thể được phân tích và xác định ngay với một vài lần thử (ví dụ như sử dụng công cụ đạo hàm). Tuy nhiên, trong thực tế, việc xác định tường minh được hàm mục tiêu sẽ cần nhiều thời gian cũng như kinh nghiệm của các chuyên gia. Do đó, hộp đen là hướng tiếp cận khả thi cho hầu hết các bài toán tối ưu khi thông tin bị hạn chế.
TỔNG QUAN optimal Bài toán x Thuật toán tối ưu Thuật toán tối ưu HÌNH 1.3: Hai cách thức tiếp cận của một bài toán Tối ưu hóa bao gồm Hộp đen (bên trái) và Hộp trắng (bên phải). Một thách thức tôn tại khi giải quyết các bài toán MMO là số lượng lời giải cực tiểu địa phương của hàm mục tiêu có thể rất lớn so với lời giải toàn cục. Do đó, để thu được kết quả khả quan, một chiến lược tìm kiếm hiệu quả là vô cùng cần thiết. Dựa vào lượng thông tin thu được, sẽ ton tại những phương pháp khác nhau để giải quyết bài toán MMO.
Khi cách thức tính toán của hàm mục tiêu được tiết lộ, các phương pháp sử dụng đạo hàm (derivative-based methods) sẽ được ưu tiên hơn cả bởi độ chính xác tuyệt đối của chúng; trong khi với dạng hộp đen, các phương pháp ngẫu nhiên (stochastic optimization methods) luôn được sử dụng bởi khả năng dò tìm hiệu quả trong môi trường thiếu thông tin. Thuật toán tiến hóa (Evolutionary Algorithm) là một ứng cử viên sáng giá nhất khi tiếp cận theo hướng này.4|mô tả bức tranh tổng quát về các phương pháp giải quyết hiện tại trên bài toán MMO. Các phương pháp sử dung đạo hàm sé luôn tận dụng phương trình dao hàm của hàm mục tiêu để tìm ra các điểm cực trị. Có hai cách thức chính để khai thác dạng thông tin này là sử dụng thuật toán lặp và giải nghiệm phương trình ƒ'(x) = 0.
Thuật toán lặp bắt đầu với một lời giải cho trước. Trong mỗi vòng lặp, vectơ đạo ham (gradient) tại lời giải đang xét sẽ được tính thông qua phương trình đạo hàm và lời giải này sẽ di chuyển theo gradient của nó. Quá trình này dừng khi giá trị đạo hàm nhận được là xấp xỉ không. Ví dụ điển hình của kiểu thuật toán này là gradient descent.
Với cách thức giải nghiệm, người giải quyết mong muốn sẽ tìm tat cả các lời giải x sao cho đạo hàm ƒ”(x) tại đó không tồn tại hoặc bằng 0. Sau đó, giá tri hàm mục tiêu giữa các lời giải đó sẽ được so sánh với nhau để tìm ra các lời giải tốt nhất. TỔNG QUAN Hộp trắng | Phuong phap Phuong phap dua ngau nhién trén dao ham Thuật toán lặp HÌNH 1.4: Các phương pháp giải quyết khi bài toán MMO được tiếp cận ở dạng Hộp đen và Hộp trắng. Đường đi được tô màu đỏ sẽ được sử dụng trong khóa luận này.
Mặt khác, các phương pháp ngẫu nhiên phát sinh nhiều lời giải một cách ngẫu nhiên nhằm khám phá không gian tìm kiếm của bài toán. Thuật toán tiến hóa là tiêu biểu cho phương pháp này. Cơ chế hoạt động của thuật toán này khi áp dụng trong MMO sẽ được mô tả như sau. Ở đầu mỗi vòng lặp, một quân thể - tập hợp các lời giải, được khởi tạo ngẫu nhiên trong không gian tìm kiếm.
Sau đó, quần thể này được phân chia thành nhiều quan thể con va tạo điều kiện cho các quan thể con này có thể đi chuyên độc lập đến các vị trí khác nhau. Mỗi quần thể con sẽ trải qua một quá trình bao gồm các phép biến đổi (lai ghép, đột biến) và tiến hành chọn lọc. Trong giai đoạn chọn lọc, quần thể sẽ chỉ giữ lại một sO lượng cu thể những lời giải có giá trị hàm mục tiêu thấp nhất. Cơ chế chọn lọc này có vai trò điều hướng quan thể tiến tới các lời giải tốt hơn.
Quá trình này được lặp lại đến khi quần thể con hội tụ; khi đó, những lời giải còn tổn tại trong các quần thể con sẽ là các lời giải cần tìm.2 Phạm vi và mục tiêu nghiên cứu 12.1 Phạm vi Trong khóa luận này, chúng tôi tiếp cận bài toán Tối ưu hóa đa cực trị ở dạng hộp đen. Cụ thể thì với mỗi lời giải hợp lệ, thông tin duy nhất chúng tôi có được là giá trị hàm mục tiêu tương ứng đi kèm theo là chi phí để nhận được giá trị đó. Bên cạnh đó, chúng tôi tập trung phân tích về cơ chế tìm kiếm của các thuật toán tiến hóa và độ hiệu quả của chúng khi giải quyết bài toán Tối ưu hóa đa cực trị.2 Mục tiêu Dựa vào phạm vi nghiên cứu đã được trình bày, mục tiêu của chúng tôi đặt ra khi thực hiện khóa luận này là cung cấp một phương pháp phân tích hành vi tìm kiếm của các thuật toán tiến hóa cho bài toán MMO hộp đen. Từ đó, chúng tôi đưa ra chiến lược hiệu chỉnh cần thiết để cải thiện hiệu suất của các thuật toán từ những phân tích thu được.3 Nội dung thực hiện Để hoàn thành mục tiêu đặt ra, chúng tôi đã thực hiện những nội dung sau đây: © Tìm hiểu các công trình nghiên cứu về các phương pháp phân tích thuật toán tiến hóa đa cực trị khi giải quyết bài toán MMO hộp đen.
¢ Dé xuất phương pháp mới để phân tích hành vi tìm kiếm của thuật toán tiến hóa đa cực trị trên bài toán MMO hộp đen. © Tìm hiểu các thuật toán tiễn hóa đa cực trị hiệu quả trên bài toán MMO hộp đen nhằm phục vụ cho việc phân tích. ¢ Tìm hiểu bộ hàm số benchmark được sử dụng để đánh giá hiệu suất của một thuật toán tối ưu hóa đa cực trị. e Tiến hành thực nghiệm trên bộ hàm số benchmark tìm được và phân tích hành vi tìm kiếm của các thuật toán bằng cách sử dụng phương pháp đề xuất.4 Đóng góp của khóa luận Từ những kết quả đạt được trong quá trình thực nghiệm, thông qua khóa luận này, chúng tôi có những đóng góp sau đây: ¢ Đề xuất phương pháp mới giúp phân tích hành vi tìm kiếm của thuật toán tiến hóa đa cực trị trên bài toán MMO hộp đen.
© Phân tích tầm quan trong của các thành phan cấu thành một thuật toán tiến hóa đa cực trị thông qua phương pháp đề xuất. * Cung cấp chiến lược cải thiện hiệu suất của các thuật toán tiến hóa đa cực trị dựa trên các thông tin phân tích được. e Cung cấp mã nguồn thực nghiệm|| 1.5 Cấu trúc khóa luận Khóa luận của chúng tôi bao gồm 5 chương chính: ¢ Chương 1: Tổng quan * Chương 2: Các công trình liên quan và kiến thức nền tang se Chương 3: Phương pháp dé xuất s® Chương 4: Thực nghiệm * Chương 5: Kết luận và hướng phát triển https://github.com/tbaotr/BScThesis Chương 2 CÁC CÔNG TRÌNH LIÊN QUAN VÀ KIÊN THỨC NEN TANG Trong chương này, chúng tôi sẽ trình bày các công trình nghiên cứu liên quan đến phương pháp phân tích hành vi tìm kiếm của những thuật toán tiền hóa hiện nay và các kiến thức nền tảng được sử dụng xuyên suốt khóa luận này.1|trình bày một vài công trình nghiên cứu tiêu biểu liên quan đến việc phân tích thuật toán tiến hóa. Ngoài ra, đặc điểm và cơ chế hoạt động của các thuật toán tiến hóa đa cực trị được trình bày ở phân|2.1 Các công trình liên quan Trong việc phân tích hành vi tìm kiếm của các thuật toán tiến hóa, bên cạnh bảng số liệu, các nhà nghiên cứu mong muốn thu được hình ảnh về cách thức đi chuyển của các quan thể trong quá trình tối ưu hóa.
Tuy nhiên, điều này chỉ thực hiện được khi số chiều của không gian tìm kiếm không quá ba. Lý do là bởi không gian có chiều lớn hơn rat khó để có thể trực quan hóa trong thực tế. Một giải pháp được dé xuất để giải quyết van đề trên là giảm số chiều của không gian tìm kiếm (dimensionality reduction) - một phương pháp biến đổi dữ liệu từ không gian có số chiều lớn sang không gian có số chiều thấp hơn sao cho vẫn duy trì được một số tính chất quan trọng của dữ liệu gốc. Một số nghiên cứu nổi bật đã sử dụng Principal Component Analysis (PCA) để bảo toàn tính xa [5] hay t-Distributed Stochastic Neighbor Embedding (t-SNE) để bảo toàn tính gần của các lời giải (6, [12].