Hệ phương trình phi tuyến tính và giải thuật di truyền phương pháp nghiên cứu khoa học

MỤC LỤC DANH MỤC BẢNG Bảng 1. 1 Công nghệ tiên tiến 5 Bảng 5. 1 Các thông số của giải thuật di truyền 10 Bảng 5. 2 Giá trị khách quan 11 DANH MỤC HÌNH ẢNH Hình 5. 1 Kết quả thử nghiệm 11 MỞ ĐẦU Hệ phương trình phi tuyến được biểu diễn rất phức tạp và thuật toán để giải các hệ phương trình này là các phương pháp thông thường có độ phức tạp tính toán cao. Các phương pháp như chia đôi (Bisection), Regula Falsi, Newton - Raphson, Secant, Muller, ... được sử dụng để giải quyết những vấn đề như vậy. Bài báo này đã tìm được những hạn chế trong các phương pháp hiện có và giải thích cho việc sử dụng giải thuật di truyền để giải quyết vấn đề này. Một phương pháp dựa trên giải thuật di truyền đã được đề xuất, phương pháp này hiệu quả hơn và mang lại kết quả tốt hơn so với các phương pháp hiện có. Từ khóa: - Phương trình phi tuyến - Kỹ thuật tính toán mềm - Giải thuật di truyền Chương 1. TỔNG QUAN VỂ HỆ PHƯƠNG TRÌNH PHI TUYẾN VÀ GIẢI THUẬT DI TRUYỀN Hệ phương trình tuyến tính và phi tuyến được sử dụng nhiều trong ứng dụng kỹ thuật. Việc tìm một giải pháp mạnh mẽ và hiệu quả cho những hệ như vậy là một công việc tẻ nhạt và đôi khi quá phức tạp để được xử lý bằng các phương pháp thông thường như phương pháp của Newton, phương pháp băm, phương pháp Regula Falsi, ... Các phương pháp thông thường hiện có để giải quyết vấn đề trên có thể được phân loại như sau: Loại 1: Các phương pháp dựa trên tính toán, bao gồm các phương pháp thường gặp như: phương pháp Newton, phương pháp Secant, phương pháp chia đôi (Bisection), ... Loại 2: Các phương pháp mang tính kinh nghiệm (Heuristic), bao gồm các kỹ thuật tính toán tiến hóa như tối ưu hóa dòng hạt, Giải thuật di truyền, ... Độ phức tạp tính toán cao cả về thời gian và không gian cùng với những ràng buộc phức tạp trong các phương pháp thông thường làm cho việc giải các hệ phi tuyến gặp nhiều khó khăn. Điều này mở ra khả năng của Giải thuật di truyền cho thế giới toán học đầy mê hoặc. Lưu ý rằng, Giải thuật di truyền là quá trình tìm kiếm mang tính kinh nghiệm dựa trên lý thuyết tiến hóa của Darwin. Nó đã được tìm thấy qua những ứng dụng của Giải thuật di truyền đã tạo ra một kết quả mạnh mẽ và hiệu quả trong thời gian ngắn. Ngoài ra, nó có thể giải quyết những vấn đề rất lớn. Việc tìm ra giải pháp cho một phương trình hay của một bộ các phương trình cho trước cũng là một vấn đề cần tìm kiếm. Hơn nữa, một trong những yếu tố giúp Giải thuật di truyền được ứng dụng nhiều trong giải quyết vấn đề là có không gian tìm kiếm rộng lớn. Công việc này đề xuất một kỹ thuật tính toán mềm cho việc tìm kiếm các giải pháp hiệu quả để giải quyết hệ phương trình đã cho. Cách tiếp cận này sử dụng nguyên tắc tính toán tiến hóa và đã được áp dụng hiệu quả trong việc tìm ra các giải pháp gần đúng trong giải phương trình. Những phân tích từ thực nghiệm đã được thực hiện và đạt được kết quả trong khi giải quyết vấn đề. Trong khi công việc đang diễn ra, tỷ lệ chéo, đột biến được thực hiện trong các thí nghiệm, những hằng số được giữ nguyên và các biến thể của chúng cũng đang được phân tích. Quá trình đã được thực hiện thành công và kết quả rất đáng khích lệ. Ưu điểm của phương pháp này là không yêu cầu thêm ràng buộc nào liên quan đến sự khác biệt của phương trình. Do đó, phương pháp này cũng có thể được sử dụng cho các phương trình không liên tục. Cấu trúc của bài báo như sau: Chương 1: Giới thiệu tổng quan về hệ phương trình phi tuyến và Giải thuật di truyền. Chương 2: Đánh giá ngắn gọn các tài liệu tham khảo đã cung cấp những giải pháp đã được đề cập trước đó. Chương 3: Cung cấp kiến thức tổng quan về Giải thuật di truyền. Chương 4: Đề xuất công việc cần thực hiện. Chương 5: Thí nghiệm và kết quả. Chương 6: Trình bày kết luận, ứng dụng và khả năng trong tương lai. Chương 2. CÔNG NGHỆ TIÊN TIẾN Một đánh giá có hệ thống cung cấp một nguồn tài liệu tuyệt vời để hiểu, đánh giá và diễn giải tất cả các công việc liên quan đến lĩnh vực nghiên cứu. Nó cũng giúp cho việc áp dụng công nghệ tiên tiến trong giải quyết các vấn đề đạt hiệu quả. Ngoài ra, nó cũng giúp giải thích cho các giải pháp được đề xuất. Theo quan điểm này, một đánh giá tài liệu rộng rãi đã được thực hiện. Kết quả của đánh giá này đã được trình bày trong bảng 1. 1. Mặc dù, nhiều bài báo khác đã được nghiên cứu và phân tích, phương pháp này ít nhiều cũng giống với phương pháp được đề cập trong các bài báo được nhắc tới trong bảng sau. Các điểm quan trọng và các vấn đề liên quan đến các phương pháp này cũng đã được xem xét trong khi tiến hành thí nghiệm. Tuy nhiên, việc đánh giá những bài báo này chưa được đề cập trong bảng [1] [4] [5] [7] [9] [11] [12] [14] [20]. Bảng 1. 1 Công nghệ tiên tiến STT Năm Công việc đề xuất Kiểm tra 1 2001 Công trình sử dụng phương pháp giảm độ dốc để giải hệ phương trình phi tuyến [2] Công việc được đề xuất đã kiểm tra các vấn đề: - Mở rộng chức năng Rosenbrock - Chức năng tam giác Broyden 2 2005 Tác giả trình bày một phương pháp để sắp xếp các phương trình từ hệ phương trình phi tuyến, có thể được giải bằng phương pháp điểm cố định. Công việc liên quan đến việc kết hợp giữa học máy trên cơ sở di truyền và Giải thuật di truyền, giúp quản lý một quần thể của quá trình với giải pháp khả thi [19] Công trình đã xác minh được vấn đề mô phỏng chu trình kết hợp Tuabin với khí ga. 3 2006 Trong bài báo này, Giải thuật di truyền đa mã hóa đã được phát triển để ước tính các tham số khác nhau của hệ phi tuyến [3] Công việc được đề xuất đã kiểm tra các vấn đề: - Đơn hàng đầu tiên cộng với hệ thống thời gian chết - Vấn đề hệ phi tuyến và không ổn định 4 2006 Trong bài báo, lần đầu tiên việc giải hệ phương trình phi tuyến ở mỗi bước được chuyển thành một vấn đề lập trình có điều kiện ràng buộc và cùng với chiến lược tìm kiếm dòng, hệ được giải quyết bằng thuật toán SQP [15] Để kiểm tra cách giải này, một vài ví dụ về hệ phương trình phi tuyến bậc hai hai biến đã được xem xét. 5 2008 Đề xuất một yêu cầu mới là coi hệ phương trình phi tuyến là bài toán tối ưu hóa đa mục tiêu [6] Công việc này đã kiểm tra được các vấn đề: - Đo khoảng cách chuẩn trong Số học - Ứng dụng thần kinh - Ứng dụng động học - Ứng dụng đốt - Ứng dụng cân bằng hóa học 6 2011 Trong công việc được đề xuất, tác giả kết hợp hai công cụ tối ưu hóa dựa trên kinh nghiệm đó là Giải thuật di truyền và Tối ưu hóa dòng hạt để giải hệ phương trình phi tuyến phức tạp [1] Phương pháp đã được xác minh với một bộ gồm 17 vấn đề đã được kiểm tra 7 2013 Bài viết mô tả một ứng dụng riêng biệt của Giải thuật di truyền để giải quyết gần đúng các vấn đề tối ưu bằng cách giới thiệu các cặp cá thể phù hợp và đối xứng [18] Một số ví dụ liên quan đến hai biến đã được sử dụng để kiểm chứng giải pháp đưa ra 8 2013 Trong bài báo này, lần đầu tiên tác giả đã chuyển đổi hệ phương trình đơn tuyến thành bài toán tối ưu hóa không bị ràng buộc và tập hợp các hệ thống phức tạp thành bài toán tối ưu hóa bị ràng buộc. Sau đó, sử dụng Giải thuật di truyền để giải quyết hệ thống [16] Công việc được đề xuất đã kiểm tra được các vấn: - Ứng dụng chất lỏng trong cơ học - Ứng dụng số học - Ứng dụng đốt - Ứng dụng sinh lý thần kinh 9 2014 Bài báo ước tính nghiệm gốc của phương trình phi tuyến bằng Giải thuật di truyền thông qua kích thước quần thể, tỷ lệ chéo và mức độ đột biến [10] Công việc đề xuất đã kiểm tra được các vấn đề sau: - Vấn đề nhân viên bán hàng du lịch - Ứng dụng sinh lý thần kinh - Hệ thống bể Reactor 10 2015 Tác giả đã phát triển một cách tiếp cận mới, trong đó giải pháp tối ưu của hệ phương trình phi tuyến thu được bằng phương pháp dựa trên các biến thể của Giải thuật di truyền, sử dụng kỹ thuật tính toán tiến hóa [17] Công việc đã được xác minh trên một tập hợp gồm 20 phương trình phi tuyến một biến khác nhau Chương 3. GIẢI THUẬT DI TRUYỀN Giải thuật di truyền là một quá trình tìm kiếm dựa trên lý thuyết chọn lọc tự nhiên và tỷ lệ sống của cá thể [5] [13]. Chúng được phát triển bởi John Holland [8] vào năm 1960, tại trường đại học Michigan, Hoa Kỳ. Nhiều vấn đề tính toán yêu cầu phải có giải pháp tối ưu trong một không gian tìm kiếm lớn. Đối với những vấn đề như vậy, Giải thuật di truyền đã được chứng minh là một thuật toán mạnh mẽ và hiệu quả để trở thành một giải pháp tối ưu. Do đó, Giải thuật di truyền đã được áp dụng thành công trong nhiều lĩnh vực như trí tuệ nhân tạo, phân tích tài chính, xử lý hình ảnh, tối ưu hóa đa phương tiện, robot, quản lý danh mục đầu tư, Cơ chế của Giải thuật di truyền [8]: Trong Giải thuật di truyền, một nhóm các ứng cử viên cho một vấn đề tối ưu hóa cụ thể được tạo ngẫu nhiên. Mỗi cá thể trong giải thuật di truyền được đại diện như một nhiễm sắc thể, là một ứng cử viên của giải pháp. Việc lựa chọn nhiễm sắc thể được thực hiện theo cách cạnh tranh dựa trên tính chất của chúng. Tiếp theo là các toán tử tìm kiếm di truyền, chọn lọc, trao đổi chéo và đột biến được áp dụng trên các nhiễm sắc thể được chọn để tạo ra một thế hệ nhiễm sắc thể mới với chất lượng như mong đợi và giá trị độ bền của chúng tốt hơn thế hệ trước. Quá trình này được lặp lại cho đến khi các tiêu chí được đáp ứng, loại nhiễm sắc thể tốt nhất được tạo ra và quá trình này được xem là giải pháp tốt cho vấn đề liên quan. Chương 4. ĐỀ XUẤT CÔNG VIỆC Hệ phương trình phi tuyến: Một hệ phương trình phi tuyến có thể được định nghĩa như sau: f1(x) = 0 f2(x) = 0 . . . fn(x) = 0 trong đó mỗi hàm fi là hàm phi tuyến, đóng vai trò ánh xạ một vectơ x = (x1, x2, ..., xn) t của không gian n chiều Rn thành đường thẳng thực. Một số hàm có thể là tuyến tính và một số hàm khác là phi tuyến. Giải pháp cho hệ phi tuyến bao gồm giải pháp tăng dần theo cách sao cho mỗi hàm trên fi (x) bằng 0. Công việc dưới đây trình bày một giải pháp cho hệ thống phi tuyến như vậy bằng cách sử dụng kỹ thuật tính toán mềm gọi là Giải thuật di truyền. Giải thuật như sau: Bước 1: Chuyển đổi từng hàm fi (x) thành zi (x) dưới dạng: zi = abs fi (x) với mỗi i = 1, 2,..., n. Do đó, hệ trên trở thành một vấn đề tối ưu hóa đa mục tiêu: min z1, min z2, ..., min zn Bước 2: Một thế hệ dân số ban đầu được tạo ra hoạt động như một nhiễm sắc thể trong Giải thuật di truyền. Bước 3: Trên cơ sở giá trị phù hợp, một số nhiễm sắc thể được chọn từ quần thể ban đầu. Sử dụng tỷ lệ và đột biến chéo (được xác định trước), một thế hệ hậu thế được tạo ra cho đến khi nó không vượt quá số lượng thế hệ trước. Bước 4: Sự phù hợp giá trị cho mỗi cá thể từ thế hệ con được đánh giá dựa trên tính khách quan và tính khả thi của giải pháp. Bước 5: Kết thúc tiêu chí là tối thiểu hóa hàm z, là tổng của các hàm số riêng lẻ: z = z1 + z2 +···+ zn Nếu kết thúc tiêu chí đạt yêu cầu thì chuyển sang bước 6, ngược lại đến bước 3. Bước 6: Báo cáo giải pháp. Có thể lưu ý rằng dân số ban đầu được tạo ra theo yêu cầu nhất định và tính hợp lý của giải pháp trong thời gian cụ thể. Quần thể ban đầu không thể có quá nhiều hoặc quá ít nhiễm sắc thể. Một số lượng nhiễm sắc thể thích hợp đã được tìm thấy trong phân tích thực nghiệm và kể từ đây chúng được sử dụng trong thí nghiệm. Các giá trị của các tham số khác nhau và thiết lập thử nghiệm đã được báo cáo trong phần tiếp theo. Chương 5. THÍ NGHIỆM VÀ KẾT QUẢ Để xác nhận hiệu quả của giải thuật, một phân tích thực nghiệm mở rộng đã được thực hiện. Thử nghiệm được thực hiện bằng cách đặt các tham số khác nhau cho Giải thuật di truyền như được mô tả trong bảng 5.1. Để xác nhận và kiểm chứng phương pháp này, các phương trình sau đây đã được chọn sao cho một số nghiệm gốc của nó là không thể thiếu và phạm vi của các nghiệm gốc không thay đổi đáng kể. 4x3 – 7x2 + 0.578 = 0 (1) 8x3 – 6x2 – 3x – 54 = 0 (2) x4 – 5x3 + 5x2 + x -20 = 0 (3) x4 – 19x3 -21x2 + 400 = 0 (4) x3 - 977x2 + 975x + 976 = 0 (5) x2 + 105x + 500 = 0 (6) 3x2 + 3001x + 1000 = 0 (7) x2 - 9999x - 1000 = 0 (8) Bảng 5. 1 Các thông số của giải thuật di truyền Các thông số Thiết lập Quy mô dân số 200 Chức năng mở rộng Xếp hạng Chức năng lựa chọn Cuộc tuyển chọn Chức năng đột biến Gaussian Chức năng chéo Điểm đơn Các thế hệ 50 Tỷ lệ / Phân số Mặc định Hình 5. 1 Kết quả thử nghiệm Bảng 5. 2 Giá trị khách quan Số phương trình Phương trình Giá trị hàm mục tiêu 1 4x3 – 7x2 + 0.578 = 0 4.02E – 06 2 8x3 – 6x2 – 3x – 54 = 0 6.96E – 04 3 x4 – 5x3 + 5x2 + x -20 = 0 5.47E – 05 4 x4 – 19x3 -21x2 + 400 = 0 5.92E – 04 5 x3 - 977x2 + 975x + 976 = 0 3.20E – 03 6 x2 + 105x + 500 = 0 4.96E – 04 7 3x2 + 3001x + 1000 = 0 1.48E – 02 8 x2 - 9999x - 1000 = 0 1.20E – 02 Việc giải phương trình có ít nhất một giải pháp. Tuy nhiên, phương pháp tiếp cận không tìm thấy tất cả các giải pháp và nó dừng lại ngay khi tìm ra một giải pháp. Các thí nghiệm đã được thực hiện, 25 lần chạy cho mỗi hàm lựa chọn đã được thực hiện và kết quả đã được ghi nhận trong hình 5.1. Bảng 5.2 cho thấy giá trị hàm mục tiêu của mỗi phương trình và giá trị tốt nhất tương ứng. Các giá trị này có được bằng cách lấy tối thiểu các giá trị tốt nhất tương ứng, kết quả cho mỗi phương trình đã được hiển thị trong hình 5.1. Chương 6. KẾT LUẬN Bài viết này trình bày một cách tiếp cận mới để có được một giải pháp gần đúng cho hệ phương trình phi tuyến bằng kỹ thuật tính toán mềm được gọi là Giải thuật di truyền. Giải thuật di truyền tối ưu hóa sự phức tạp về thời gian để giải quyết những hệ phi tuyến như vậy. Giải pháp bao gồm một giả định ban đầu về các thông số khác nhau của Giải thuật di truyền, đó là quy mô dân số, chức năng chéo và chức năng đột biến, cùng với số lượng các thế hệ. Việc lựa chọn tham số giúp cải thiện tính hiệu quả của giải thuật. Chi phí tính toán có thể được giảm bằng cách xem vấn đề là vấn đề tối ưu hóa đa mục tiêu và do đó, việc áp dụng kỹ thuật tìm kiếm được dựa trên kinh nghiệm. Ngoài ra, người ta còn đề xuất sử dụng các biến thể của Giải thuật di truyền như giải thuật di truyền Diploid để giải quyết các vấn đề này [21] [22]. Trong quá trình làm việc, tỷ lệ chéo và tỷ lệ đột biến đã được thay đổi để kiểm tra sự ảnh hưởng của các tỷ lệ này đến chất lượng kết quả thu được của giải pháp. Ngoài ra, trong tương lai, giải pháp có thể được cải tiến để xử lý các hệ thống phi tuyến phức tạp và có kích thước lớn hơn. TÀI LIỆU THAM KHẢO [1] M. A. E.-S. W.F. Abd-El-Wahed, A.A. Mousa, “Integrating particle swarm optimiza-tion with genetic algorithms for solving nonlinear optimization problems.” Journal of Computational and Applied Mathematics 235, pp. 1446–1453, 2011. [2] M. Bianchini, S. Fanelli, and M. Gori, “Optimal algorithms for well-conditioned nonlinear systems of equations,” IEEE Transactions on Computers, vol. 50, no. 7. pp. 689–698, 2001. [3] W.-D. Chang, “An improved real-coded genetic algorithm for parameters estimation of nonlinear systems.” Mechanical Systems and Signal Processing 20, pp. 236–246, 2006. [4] S. Effati and A. R. Nazemi, “A new method for solving a system of the nonlinear equations,” Applied Mathematics and Computation, vol. 168, no. 2. pp. 877–894, 2005. [5] D. E. GOLDBERG, “Genetic Algorithms in Search, Optimization and Machine Learning.” Addion-Vesley, Reading, p. [1] “Goldberg_Genetic_Algorithms_in_Search.pdf.” ., 1989. [6] C. Grosan and A. Abraham, “A new approach for solving nonlinear equations systems,” IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans, vol. 38, no. 3. pp. 698–714, 2008. [7] A. N’Guessan, “Analytical existence of solutions to a system of nonlinear equations with application.” Journal of Computational and Applied Mathematics 234, pp. 297–304, 2010. [8] J. Holland, “An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence.” Adaptation in Natural and Artificial Systems. MIT Pres, Cambridge, 1975. [9] Z. J. Zhigang Ji, Zhenyu Li, “Research on Genetic Algorithm and Data Information based on Combined Framework for Nonlinear Functions Optimization.” a Engineering 23, pp. 155–160, 2011. [10] G. Joshi and M. B. Krishna, “Solving system of non-linear equations using Genetic Algorithm,” Proceedings of the 2014 International Conference on Advances in Computing, Communications and Informatics, ICACCI 2014. pp. 1302–1308, 2014. [11] A. E. S. Abdullah Konak, David W. Coit, “Multi-Objective Optimization Using Genetic Algorithms: A Tutoria.” Reliab. Eng. Syst. Saf. 91, pp. 992–1007, 2006. [12] N. E. Mastorakis, “Solving non-linear equations via genetic algorithms,” WSEAS Transactions on Information Science and Applications, vol. 2, no. 5. pp. 455–459, 2005. [13] J. McCall, “Genetic algorithms for modelling and optimisation,” Journal of Computational and Applied Mathematics, vol. 184, no. 1. pp. 205–222, 2005. [14] A. A. Mousa and I. M. El-Desoky, “GENLS: Co-evolutionary algorithm for nonlinear system of equations,” Applied Mathematics and Computation, vol. 197, no. 2. pp. 633–642, 2008. [15] P. Y. Nie, “An SQP approach with line search for a system of nonlinear equations,” Mathematical and Computer Modelling, vol. 43, no. 3–4. pp. 368–373, 2006. [16] M. S. C. Abolfazl Pourrajabian, Reza Ebrahimi, Masoud Mirzaei, “Applying genetic algorithms for solving nonlinear algebraic equations.” Applied Mathematics and Computation 219, pp. 11483–11494, 2013. [17] • M. A. Z. R. • Z. S. • N. M. • E. S. A.-A. and J. A. Khan, “Design of stochastic solvers based on genetic algorithms for solving nonlinear equations.” The Natural Computing Applications Forum. 26, pp. 1–23, 2015. [18] H. Ren, L. Wu, W. Bi, and I. K. Argyros, “Solving nonlinear equations system via an efficient genetic algorithm with symmetric and harmonious individuals,” Applied Mathematics and Computation, vol. 219, no. 23. pp. 10967–10973, 2013. [19] A. Rovira, M. Valdés, and J. Casanova, “A new methodology to solve non-linear equation systems using genetic algorithms. Application to combined cycle gas turbine simulation,” International Journal for Numerical Methods in Engineering, vol. 63, no. 10. pp. 1424–1435, 2005. [20] Z. W. Xin Zhang, “Study neighborhood field optimization algorithm on nonlinear sorptive barrier design problems.” The Natural Computing Applications Forum, 2015. [21] M. S. Harsh Bhasin, “On the Applicability of Diploid Genetic Algorithms.” AI Soc 31(2), pp. 265–274, 2015. [22] H. Bhasin, G. Behal, N. Aggarwal, R. K. Saini, and S. Choudhary, “On the applicability of diploid genetic algorithms in dynamic environments,” Proceedings - 2014 International Conference on Soft Computing and Machine Intelligence, ISCMI 2014. pp. 94–97, 2014.