- Hội nghị toàn quốc lần thứ 3 về Điều khiển và Tự động hoá - VCCA-2015 Tính toán tối ưu sử dụng thuật toán lai tạo thành bởi thuật toán tiến hóa vi sai và tối ưu suy giảm độ dốc Optimization using a hybrid algorithm based on differential evolution and gradient descent method * Nguyễn Ngọc Sơn, **Hồ Phạm Huy Ánh, **Trương Đình Châu. - Phần mở đầu Trong bài báo này, tác giả đề xuất thuật toán lai HDE Tối ưu hóa được xem như một lĩnh vực kinh điển của được tạo thành bằng cách lai ghép thuật toán tiến hóa toán học và có rất nhiều ứng dụng trong các lĩnh vực vi sai cơ bản DE và thuật toán suy giảm độ dốc GD. - khác nhau như thiết kế chế tạo máy, điều khiển tự Đầu tiên, chúng tôi sử dụng khả năng tìm kiếm toàn động, quy hoạch tài nguyên…Có rất nhiều thuật toán cục của thuật toán DE để tìm giải pháp tối ưu trong đã và đang được sử dụng để tìm kiếm lời giải tối ưu không gian tìm kiếm và sau đó sử dụng khả năng tìm cho bài toán tối ưu hóa. - Trong số đó, các thuật toán kiếm cục bộ chính xác của thuật toán GD để tăng tốc tiến hóa được xem như lựa chọn đầy hứa hẹn. - độ hội tụ. - Chất lượng của thuật toán HDE được kiểm Thuật toán tiến hóa vi sai DE được xem như là một chứng trên một số hàm benchmark và được so sánh trong những thuật toán tối ưu hóa ngẫu nhiên mạnh với các thuật toán khác như thuật toán tối ưu hóa bầy mẽ nhất được sử dụng hiện nay. - Thuật toán tiến hóa đàn PSO, thuật toán tiến hóa vi sai cơ bản DE. - Thuật toán tiến hóa vi sai Từ khóa: Thuật toán di truyền, tối ưu tiến hóa vi sai, có khả năng xử lý rất hiệu quả các bài toán tìm cực trị thuật toán suy giảm độ dốc, bài toán tối ưu hóa. - Thuật toán tiến hóa vi sai với các ưu điểm như có Abstract: In this paper, we propose a hybrid khả năng tìm kiếm chính xác lời giải tối ưu toàn cục algorithm HDE is created by combining a traditional mà không phân biệt giá trị tham số ban đầu, tốc độ hội differential evolution algorithm and a gradient descent tự nhanh, ít thông số liên quan đã làm cho thuật toán method. - Initially, we use global searching ability of DE trở nên một trong những công cụ mạng mẽ nhất the DE algorithm to find the global optimal solution trong lĩnh vực tối ưu hóa. - Vesterstrom và các cộng sự in the search space and then precise local seaching of [2] đã đánh giá chất lượng của các thuật toán DE, the GD method in that region to converge to optimal PSO và các thuật toán tối ưu khác kiểm chứng trên 34 solution. - Karaboga và các cộng sự on some benchmark functions and is compared with [3] đã ứng dụng thuật toán DE để thiết kế bộ lọc FIR the other algorithms such as particle swarm và thực hiện so sánh chất lượng của thuật toán DE với optimization and traditional differential evolution. - thuật toán di truyền GA. - toán DE khi so sánh với các thuật toán GA, PSO. - Tuy Keywords: Genetic algorithm, differential evolution, nhiên, nhược điểm chung của các thuật toán tiến hóa gradient descent method, optimization problem. - Hiện Ký hiệu tượng này làm cho không thể tìm trong không gian Ký hiệu Ý nghĩa tìm kiếm mới lời giải tối ưu toàn cục. - Để thoát khỏi hiện tượng này, các giải thuật tìm kiếm cục bộ F hệ số đột biến được áp dụng để tìm giải pháp khả thi hơn trong NP Kích thước quần thể không gian cục bộ. - Các bài báo [4-7] đã lai ghép thành công các thuật toán suy giảm độ dốc GD với Chữ viết tắt các thuật toán tiến hóa GA, PSO để cải thiện chất EAs evolution algorithms lượng hội tụ của thuật toán. - DE differential evolution Trong bài báo này, tác giả đề xuất thực hiện lai ghép GD gradient descent thuật toán suy giảm độ dốc GD với thuật toán tiến hóa GA genetic algorithm vi sai DE để cải thiện chất lượng hội tụ của thuật toán HDE hybrid differential evolution DE cơ bản. - Thuật toán sau lai ghép HDE mang cả ưu PSO particle swarm optimization điểm của thuật toán DE với khả năng tìm kiếm toàn VCCA-2015 Hội nghị toàn quốc lần thứ 3 về Điều khiển và Tự động hoá - VCCA-2015 cục và thuật toán GD với khả năng tìm kiếm chính trình tìm kiếm lời giải tối ưu được trải rộng trong xác cục bộ. - Kết quả thực nghiệm kiểm chứng trên một không gian tìm kiếm. - Các chỉ số r1i , r2i và r3i là số số hàm benchmark được sử dụng để chứng tỏ chất nguyên loại trừ lẫn nhau được chọn lựa ngẫu nhiên từ lượng và hiệu quả của thuật toán đề xuất HDE khi so khoảng [1, NP] và khác với véc-tơ cơ sở thứ i. - Các chỉ sánh với các thuật toán tối ưu khác. - số này được tạo ra ngẫu nhiên một lần cho mỗi véc-tơ đột biến. - Hiệu của hai véc-tơ bất kỳ trong ba véc-tơ 2. - Nội dung chính được thu nhỏ lại bởi số vô hướng F và sau đó được 2.1 Thuật toán tiến hóa vi sai cơ bản Thuật toán tiến hóa vi sai DE được R.Storn và K.V. - cộng với véc-tơ thứ ba để được véc-tơ đột biến Vi ,G . - Cho Quá trình này có thể biểu diễn như sau: đến nay, thuật toán tiến hóa vi sai đã trở nên phổ biến. - Lưu đồ thực hiện thuật toán tiến hóa vi sai cơ bản Vi ,G = X r i ,G + F( X r i ,G - X r i ,G được mô tả như H.1. - Khởi tạo X1 X ri X ri Véc-tơ Đột biến 2 3 đột biến Vi ,G Lai ghép Chọn lọc no Hội tụ X ri 2 F ( X ri X ri ) yes 2 3 X ri Kết thúc 3 X ri X0 H.1 Lưu đồ thực hiện thuật toán DE 1 H.2 Quá trình đột biến trong không gian 2-D Khởi tạo: Giả sử chúng ta muốn tìm kiếm lời giải tối ưu cho một hàm thực với D tham số. - Đầu tiên, chúng Lai ghép: Sau khi tạo ra véc-tơ đột biến, lai ghép ta phải chọn kích thước quần thể NP. - Thuật toán DE được thực hiện để tăng cường sự đa dạng của quần bắt đầu bằng cách tạo ra một cách ngẫu nhiên NP vector D chiều. - Véc-tơ đột biến Vi ,G được lai ghép với véc-tơ mục và được biểu diễn như sau. - tiêu X i ,G hình thành véc-tơ thử nghiệm X i ,G [ x1,i ,G , x2,i ,G. - Thuật toán DE thường sử Trong đó: G là số thế hệ, G 0,1. - lai ghép. - Vì vậy, các thành phần thứ j của véc-tơ thứ i được khởi tạo như sau: Chọn lọc: Véc-tơ mục tiêu X i ,G được so sánh với x j ,i x j ,min rand j ,i [0,1] x j ,max x j ,min (2) véc-tơ thử nghiệm U i ,G . - U i ,G if f (U i ,G ) f ( X i ,G ) lai ghép và chọn lọc. - Trong thuật toán DE, X i ,G otherwise một véc-tơ mẹ ở thế hệ hiện tại được gọi là véc-tơ Trong đó, f (X ) là hàm chi phí cực tiểu. - mục tiêu, một véc-tơ đột biến thu được từ quá trình đột biến. - Để tạo ra véc-tơ đột biến cho mỗi véc-tơ Hội tụ: Quá trình trên được thực hiện trong một vòng mục tiêu thứ i từ thế hệ hiện tại, ba véc-tơ khác nhau lặp. - Sự lựa chọn ngẫu nhiên ba véc-tơ - Khi giá trị hàm chi phí không thay đổi đáng kể. - 1 2 3 VCCA-2015 2.2 Thuật toán lai HDE Bước 6: Lai ghép mỗi một véc-tơ mục tiêu trong Thuật toán lai HDE được tạo thành bằng cách lai ghép quần thể hiện tại với một véc-tơ đột biến để tạo ra thuật toán tiến hóa vi sai cơ bản DE và thuật toán suy một véc-tơ thử nghiệm, mô tả ở (4). - Có nhiều cách khác nhau để áp Bước 7: Tìm kiếm cục bộ dựa trên giải thuật suy dụng lai thuật toán GD với thuật toán DE. - Ở đây, giảm độ dốc, mô tả ở (6). - thuật toán GD được áp dụng ở giai đoạn “lai ghép” để Bước 8: Chọn lựa giữa véc-tơ mục tiêu và véc-tơ tạo ra véc-tơ thử nghiệm mới trước khi bước vào giai thử nghiệm sao cho thỏa điều kiện, mô tả ở (5). - Thuật toán HDE sau lai ghép giúp cải Bước 9: Lặp lại chu kỳ huấn luyện từ bước 4 đến thiện chất lượng hội tụ của thuật toán tiến hóa vi sai bước 8 cho đến khi tiêu chí hội tụ được đáp ứng. - Chi tiết lưu đồ thực hiện thuật toán HDE được mô tả như theo H.3. - Các hàm benchmark được sử dụng trong bài báo Hàm Giới hạn Công thức toán học Bắt đầu n Sphere 100,100 n f1 ( x) xi2 Khởi tạo i 1 n n 1 xi Đột biến Griewank 600,600 n f 2 ( x) 1 xi2 cos 4000 i 1 i 1 i Lai ghép 1 n f 3 ( x) 20 exp 0.2 xi2 Tìm kiếm cục bộ n i 1 n Ackley 30,30 (Thuật toán GD) n 1 exp cos(2 xi ) Chọn lọc n i 1 n no n f 4 ( x) 10n ( xi2 10 cos(2 xi. - Hội tụ Rastrigin 5.12,5.12 i 1 yes Kết thúc 2.4 Kết quả thực nghiệm Trong bài báo này, tất cả các kết quả kiểm chứng H.3 Lưu đồ thực hiện thuật toán HDE được chúng tôi thực hiện trên phần mềm Matlab Các bước khởi tạo, đột biến, lai ghép, chọn lọc và hội 2013b được cài đặt trong máy tính có cấu hình Intel tụ được thực hiện tương tự như ở thuật toán tiến hóa Core i3, 2.00GB RAM và tốc độ xử lý 2.53GHz. - vi sai cơ bản. - Bước tìm kiếm cục bộ dựa trên thuật Chất lượng của thuật toán HDE được so sánh với các toán suy giảm độ dốc được mô tả như sau. - thuật toán PSO và DE bằng cách so sánh quá trình hội U i*,G U i ,G ( f (U i ,G. - (6) tụ và giá trị tối ưu nhất được tìm thấy cho các hàm Trong đó, η là bước nhảy của thuật toán suy giảm độ benchmark được mô tả ở bảng 1. - Bảng 2 mô tả các. - tham số điều khiển của các thuật toán DE, PSO và dốc. - Vì các thuật toán PSO, DE và HDE là các thuật toán tối ưu ngẫu nhiên. - Do đó, cần lặp lại quy trình 2.3 Tối ưu hóa hàm toán học dùng thuật toán HDE nhiều lần để thống kê các giá trị tìm kiếm ở các trị tối Bài toán tối ưu hóa hàm nói chung là xác định giá trị ưu nhất và trị trung bình. - Các tham số điều khiển của PSO, DE, HDE tối ưu các hàm benchmark được mô tả ở bảng 1 dùng Phương pháp Tham số Giá trị thuật toán HDE. - Kích thước quần thể, NP 18 Với các công thức toán học và không gian tìm kiếm Hệ số đột biến, F 0.5026 DE Xác suất lai ghép, CR 0.6714 được mô tả ở bảng 1, quy trình tìm kiếm tối ưu dùng Số lượng các biến, n 2 thuật toán HDE được mô tả chi tiết như sau: HDE Tốc độ học hay bước nhảy, η 0.01 Bước 1: Chọn các thông số như kích thước quần Kích thước quần thể, s 149 thể NP, hệ số đột biến F, xác suất lai ghép C, số Trọng số quán tính, w -0.3236 PSO thế hệ cực đại Gmax, số lượng các biến n. - Hệ số gia tốc, c1 -0.1136 Bước 2: Tạo ra một quần thể từ NP véc-tơ n chiều Hệ số gia tốc, c2 3.9789 được chọn lựa ngẫu nhiên, mô tả ở (1). - Kết quả thống kê về giá trị tối ưu nhất và trị trung Bước 4: Với mỗi cá thể thứ i trong quần thể lựa bình sau 10 lần lặp quá trình tìm kiểm giá trị tối ưu chọn ngẫu nhiên các biến r1 , r2 , r3 [1,2. - của các hàm Sphere, Griewank, Ackley và Rastrigin dùng các thuật toán PSO, DE và HDE được mô tả ở và r1 r2 r3 i. - Ngoài ra, H.4, H.5, H.6 và H.7 mô tả kết quả Bước 5: Áp dụng toán tử đột biến cho mỗi một cá so sánh sự hội tụ của các thuật toán PSO, DE và HDE thể trong quần thể để được một véc-tơ đột biến, trong quá trình tìm kiếm giá trị tối ưu của các hàm mô tả ở (3). - Thống kê kết quả tìm kiếm dùng PSO, DE và HDE 2 10 Hàm PSO DE HDE f1 Trung bình 2.1387e-4 6.8596e-6 6.7537e-6 Tốt nhất 9.7768e-7 6.3167e-7 2.3047e-7 0 10 f2 Trung bình e-4 2.2925e-5 Fitness value Tốt nhất e-6 1.0576e-6 f 3 Trung bình e-4 1.3484e-4 -2 10 Tốt nhất e-5 1.7646e-5 f4 Trung bình e-5 Tốt nhất 1.5937e-5 3.2059e-5 1.5203e-5 -4 10 Magenta dotted line: PSO 4 10 Blue dashed line: DE Magenta dotted line: PSO -6 Red solid line: HDE 2 Blue dashed line: DE Red solid line: HDE Iteration number 0 10 H.7 So sánh hội tụ của các thuật toán PSO, DE và HDE với Fitness value hàm Rastrigin -2 10 Dựa trên các kết quả mô tả ở bảng 3, H.4, H.5, H.6 và -4 H.7, chúng ta thấy rằng chất lượng và hiệu quả vượt 10 trội của thuật toán lai HDE so với các thuật toán PSO -6 và DE. - Chẳng hạn, khi kiểm chứng thuật toán HDE 10 với hàm Sphere thì sau khoảng 950 thế hệ thì đã tìm -8 kiếm được điểm tối ưu có giá trị trung bình là e-6. - Tương tự, kiểm chứng với thuật toán DE Iteration number thì sau khoảng 2000 thế hệ ta được trị trung bình H.4 So sánh hội tụ của các thuật toán PSO, DE và HDE với 6.8596e-6 và kiểm chứng với thuật toán PSO ta được hàm Sphere trị trung bình là 2.1387e-4. - Kết luận Blue dashed line: DE Red solid line: HDE Trong bài báo này, tác giả đã xây dựng quy trình tìm 0 10 kiếm tối ưu dùng thuật toán lai HDE được tạo thành bằng cách lai ghép thuật toán tiến hóa vi sai và thuật Fitness value toán suy giảm độ dốc. - Chất lượng và hiệu quả của -2 10 thuật toán HDE được kiểm chứng thực nghiệm trên các hàm toán học như Sphere, Griewank, Ackley, Rastrigin. - Kết quả thực nghiệm chứng tỏ hiệu quả -4 10 vượt trội của thuật toán HDE so với thuật toán DE và thuật toán PSO. - Tương lai, tác giả sẽ sử dụng thuật toán HDE để tối ưu các trọng số mạng nơ rôn ứng -6 10 dụng trong nhận dạng điều khiển các hệ phi tuyến. - Iteration number H.5 So sánh hội tụ của các thuật toán PSO, DE và HDE với Acknowledgements hàm Griewank This paper was supported by the NAFOSTED and the 2 DCSELAB, VNU-HCM, Viet Nam. - H.6 So sánh hội tụ của các thuật toán PSO, DE và HDE với [3] Karaboga, Nurhan, and Bahadir Cetinkaya, hàm Ackley Performance comparison of genetic and VCCA-2015 differential evolution algorithms for digital FIR filter design, Advances in information systems