1.Giới thiệu về giải thuật hỗn loạn (CE)
Tối ưu hóa là một ngành toán học xác định giải pháp tốt nhất được định nghĩa rõ ràng về mặt định lượng từ một tập hợp các giải pháp thay thế khả dụng [1], bao gồm nhiều loại hàm mục tiêu khác nhau và nhiều loại miền giá trị khác nhau. Trong khoa học máy tính, tính toán tiến hóa (Evolutionary computation), lấy cảm hứng từ quá trình tiến hóa sinh học từ các hiện tượng tự nhiên, có thể tạo ra các giải pháp được tối ưu hoá cao. Tính toán tiến hoá có thể liên quan đến các vấn đề tối ưu hóa liên tục và kết hợp, và thuật toán của nó có đặc điểm siêu heuristic hoặc ngẫu nhiên trong cơ chế tìm kiếm của chúng [2]. Lĩnh vực này được tiên phong phát hiện và nghiên cứu vào những năm 1960 bởi Rechenberg (1973) và Holland (1975) và cả hai đều chỉ xuất bản công trình của mình dưới dạng sách vào những năm 1970 [3]. Trong thuật toán này, hai quá trình chính hình thành nên cơ sở của hệ thống tiến hóa, bao gồm đột biến và lai tạo, tạo ra sự đa dạng cần thiết và do đó tạo điều kiện cho sự mới lạ cho các thế hệ sau, trong khi chọn lọc đóng vai trò là quá trình làm tăng chất lượng của quần thể.
Tuy nhiên, hầu hết các thuật toán EC không yêu cầu bài toán tối ưu phải có một số đặc điểm và cơ chế hoặc tính chất toán học cụ thể để đảm bảo sự hội tụ, chúng dễ mắc phải bẫy của môi trường.
Để giải quyết vấn đề đó, một trong những tính chất toán học có thể áp dụng ở đây là chuyển động hỗn loạn, do tính chất ergodic của hệ hỗn loạn, nó có thể giúp thuật toán truy cập bất kỳ điểm mong muốn nào trong không gian tìm kiếm, được gọi tên là Giải thuật hỗn loạn (CE).
CE là một thuật toán dựa trên quần thể sử dụng thuộc tính ergodic của hỗn loạn để thực hiện các chức năng thăm dò và khai thác nhằm đảm bảo tính hội tụ và tăng hiệu quả của thuật toán [4]. Trong CE, có một hoạt động đột biến với việc mô phỏng chuyển động hỗn loạn của từng cá nhân trong mỗi chiều. Tùy thuộc vào chiến lược lựa chọn khác nhau, cá thể bố mẹ có thể được thay thế [2]. Nguyên lý của CE là mô phỏng chuyển động ergodic hỗn loạn để thực hiện tìm kiếm [4]. Do chuyển động hỗn loạn có đặc tính linh hoạt nên thuật toán đề xuất có thể giúp thuật toán thoát khỏi cực tiểu cục bộ và đảm bảo một phần sự hội tụ toàn cục của nó.
Có ba khái niệm mới, khác với giải thuật di truyền tiêu chuẩn, quyết định hiệu quả của thuật toán CE, bao gồm vectơ hướng, vectơ hỗn loạn và tham số hỗn loạn. Đầu tiên, việc tạo ra một vectơ hỗn loạn là một hoạt động quan trọng trong CE. Điều này quyết định khả năng tìm kiếm thực tế của CE, vec-tơ này được tạo ra bằng cách giao nhau giữa vectơ mục tiêu và vectơ đột biến. Thứ hai, vectơ hướng (D_i) quyết định hướng tìm kiếm của mọi cá thể trong mỗi chiều, được kiểm soát bởi tỷ lệ hệ số hướng (DR), ví dụ, nếu DR = 0,7, nghĩa là 70% của Di là +1, phần còn lại là -1. Tham số hỗn loạn (CP_i) được đặt ban đầu thành một giá trị ngẫu nhiên và được cập nhật trong mỗi thế hệ bởi các phép chiếu hỗn loạn, ảnh hưởng đến các chức năng khám phá và khai thác của thuật toán [4].
Các bước chính của thuật toán CE được hiển thị bên dưới, được tham khảo từ [4].
Bước 1) Khởi tạo quần thể ban đầu.
Bước 2) Khởi tạo tham số D và CP.
Bước 3) Chọn một cá thể làm vectơ mục tiêu.
Bước 4) Tạo vectơ đột biến theo công thức
Mutant_i =Target_i *(1+D_i *CPi)
Bước 5) Lai giữa vectơ mục tiêu và vectơ đột biến để tạo vectơ hỗn loạn.
Chaotic_i = Crossover(Mutant_i,Target_i)
Bước 6) So sánh độ phù hợp của vectơ mục tiêu và vectơ hỗn loạn, vectơ nào tốt hơn sẽ được coi là thế hệ con của thế hệ tiếp theo.
Bước 7) Cập nhật tham số hỗn loạn CP từ hệ thống hỗn loạn và hệ số hướng.
CP_i = Hệ thống hỗn loạn(CP_i−1)
Bước 8) Đến bước 3) và tạo ra các cá thể con khác cho đến khi tất cả các cá thể được xử lý bằng các thao tác tương tự, sau đó tiếp tục với thế hệ tiếp theo
2.Chuyển động hỗn loạn là gì?
Chuyển động hỗn loạn mô tả một hệ thống không thể mô hình hóa bằng các phương pháp xác định ngẫu nhiên, và có các đặc điểm là phi tuyến tính và không thể đoán trước. Đây là một hệ thống động lực học phi tuyến tính cổ điển và có các tính chất ergodic, ngẫu nhiên và nhạy cảm với các điều kiện ban đầu của nó [4]. Các khái niệm “tiến hóa” và “hỗn loạn” có cùng các đặc điểm chung [4]. Cả hai đều đề cập đến các hiện tượng và lý thuyết cần được giải thích [4] và phải là một sự lặp lại trong các quy trình. Nhờ việc kết hợp các khái niệm này với nhau, giải thuật hỗn loạn ra đời, đem lại nhiều hướng đi mới khả quan trong tối ưu hoá.
Giải thuật hỗn loạn phụ thuộc rét lớn vào tính chất ergodic của các hệ thống hỗn loạn mà nó dùng. Bằng cách thay đổi hệ thống hỗn loạn trong khuôn khổ CE, chúng ta có thể thu được các loại thuật toán khác. Trong bài báo này, chúng tôi giới thiệu bốn hệ thống hỗn loạn, bao gồm phép chiếu Logistic (được dùng trong giải thuật hỗn loạn truyền thống), phép chiếu Tent, phép chiếu Gauss và phép chiếu He ́non.
2.1 Phép chiếu Logistic
Phép chiếu Logistic chứng minh rằng một phương trình động phi tuyến tính đơn giản có thể dẫn đến hỗn loạn. Đó là một phép ánh xạ đa thức (tương đương, quan hệ tái phát) của da thức bậc hai [4]. Trong phương trình dưới đây, với μ = 4, hệ thống tiến tới hỗn loạn
Hình 1: Chuyển động hỗn loạn của phép chiếu Logistic khi μ = 4
2.2 Phép chiếu Tent
Phép chiếu Tent cũng thường được gọi là phép chiếu tam giác, tuyến tính từng phần, giúp hệ thống Tent dễ phân tích hơn hệ thống logistic khi có quỹ đạo hỗn loạn. Phép chiếu Logistic và phép chiếu Tent liên hợp về mặt tôpô. Bản đồ Tent có hiện tượng hỗn loạn khi r = 2 [5] trong phương trình bên dưới
2.3 Phép chiếu Gauss
Trong toán học, phép chiếu Gauss (còn được gọi là phép chiếu Gaussian) là phép chiếu lặp phi tuyến tính của các số thực thành một khoảng thực được tạo bởi hàm Gauss. Biểu đồ phân nhánh của nó giống như một con chuột và có hành vi tương tự như phép chiếu logistic [5]. Phương trình dưới đây mô tả của phép chiếu Gauss, nó có thể dẫn đến hỗn loạn khi a = 6,2 và b = -0,5
2.4 Phép chiếu He’non
Phép chiếu He’non là một hệ thống phi tuyến tính hai chiều [4], một nguyên mẫu của động lực kéo giãn dẫn đến hỗn loạn xác định [5]. Nó có hai điểm (xn, yn) trên mặt phẳng và đi đến hỗn loạn khi a = 1,4 và b = 0,3. Phương trình của nó như sau:
3. Giải thuật hỗn loạn được đề xuất
Trong nghiên cứu này, chúng tôi giới thiệu năm thuật toán CE, có các tính chất ergodicity khác nhau tùy thuộc vào hệ thống hỗn loạn lần lượt gồm phép chiếu Logistic, phép chiếu Tent, phép chiếu Gaussian, phép chiếu Henon và sự kết hợp của bốn hệ thống hỗn loạn này. Quần thể ban đầu được tạo ngẫu nhiên trong không gian tham số có phân phối đều. Các giá trị của tham số hỗn loạn (CP_i) và vectơ hướng (D_i) theo tỷ lệ hệ số hướng (DR) cũng được tạo ngẫu nhiên cho mỗi chiều của vectơ hỗn loạn
4. Cài đặt thử nghiệm và kết quả
Để nghiên cứu hiệu quả của các thuật toán đề xuất, chúng tôi so sánh hiệu suất của thuật toán CE trước đó [4], sử dụng phép chiếu logistic, với các thuật toán khác, sử dụng 12 hàm Benchmark nổi tiếng từ CEC2005 [6]. Chúng bao gồm cả liên tục và rời rạc, lồi và không lồi, biến tách biệt và không tách biệt, đơn thức và đa thức. Bảng 1 trình bày chi tiết các thuộc tính, giới hạn tìm kiếm, loại và giá trị độ phù hợp tối ưu của chúng [6]. Thiết lập tham số được trình bày trong Bảng 2.
Bảng 1: Đặc trưng của các hàm Benchmark CEC2005[6]
Bảng 2: Các tham số được thiết lập[7]
Bằng cách sử dụng các hàm Benchmark làm hàm kiểm tra cho các thuật toán được đề xuất, chúng ta có thể có được các đường cong hội tụ của các hàm này ở 10-D và 30-D, được trình bày lần lượt trong Hình 2 và Hình 3.[7]
Hình 2 Đường cong hội tụ của các thuật toán đề xuất ở 10-D[7]
Hình 3: Đường cong hội tụ của các thuật toán đề xuất ở 30-D[7]
Từ Hình 2 và 3, chúng ta có thể kết luận rằng CE sử dụng phép chiếu Gaussian và hợp nhất nhiều hệ hỗn loạn cho kết quả tốt nhất và CE với bản đồ Tent cho kết quả tệ nhất đối với hầu hết các hàm ở 10-D và 30-D. Điều này chỉ ra rằng CE sử dụng hệ thống Tent thực sự ít hữu ích nhất đối với hầu hết các hàm thử nghiệm. Có sự khác biệt đáng kể giữa CE sử dụng phép chiếu logistic và các phép chiếu còn lại, giữa trường hợp tệ nhất và trường hợp tốt nhất đối với hầu hết các hàm.
CE đề xuất tốt hơn CE ban đầu trong hầu hết các trường hợp, đó là do việc khám phá và khai thác mà sự hợp nhất của các hệ hỗn loạn mang lại tốt hơn hệ thống logistic. Do đó, hệ hỗn loạn đóng vai trò quan trọng trong việc tạo ra hiệu suất tối ưu hóa.
Ngoài ra, nhìn các đường cong hội tụ của hàm Benchmark, có vẻ như tốc độ hội tụ của các thuật toán CE giảm xuống. Và một số thuật toán CE, đặc biệt là thuật toán sử dụng phép chiếu Tent, có xu hướng dễ dàng đạt đến tối ưu cục bộ và không thể thoát khỏi điều đó, lý do tại sao hiệu suất của CE sử dụng hệ thống Tent là tệ nhất.
Trong CE đề xuất, chúng tôi áp dụng các hệ thống hỗn loạn khác nhau vào khuôn khổ CE ở cấp độ cá nhân, do đó mỗi phần của quần thể sẽ trở nên hỗn loạn tùy thuộc vào hệ thống được phân biệt.Kết quả đánh giá cho thấy thuật toán CE sử dụng nhiều hệ hỗn loạn cho kết quả tốt hơn các thuật toán khác, đây sẽ là chủ đề đầy hứa hẹn để nghiên cứu sâu hơn.
Bài viết được tham khảo từ [7]
Các tài liệu tham khảo
[1] J. Kallrath, “Mathematical optimization and the role of modeling languages,” in Modeling Languages in Mathematical Optimization. Applied Optimization, Springer, 2004, vol. 88, pp. 3–24.[2] L. J. Fogel, Industrial research. Autonomous au- tomata, 1962.
[3] H. P. Schwefel., “Evolutions strategie und nu- merische optimierung,” Ph.D. dissertation, Technis- che Universit at Berlin, 1975.
[6] Y. Pei, “Chaotic evolution: fusion of chaotic ergod- icity and evolutionary iteration for optimization,” Natural Computing, vol. 13, no. 1, p. 79–96, 2014.
[5] L. Saha, M. Yuasa et al., “Measuring chaos: Topo- logical entropy and correlation dimension in dis- crete maps,” Annual reports by Research Insitute for Science and Technology, no. 24, 2012.
[6] P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y.-P. Chen, A. Auger, and S. Tiwari, “Problem defi- nitions and evaluation criteria for the cec 2005 spe- cial session on real-parameter optimization,” Kan- GAL report, 2005005:2005, 2005.
[7]T. T. Thoa and Y. Pei, “Chaotic evolution using multiple chaotic systems,” SICE2020, Chiangmai, Thailand, Sep. 2020.
