Luận án: Kỹ thuật dựa trên ngữ nghĩa cho lựa chọn cạnh tranh và giảm phình mã
Luận án: Kỹ thuật ngữ nghĩa cho lựa chọn cạnh tranh & giảm phình mã lập trình di truyền. Nâng cao hiệu quả thuật toán.
Mathematical Foundations for Informatics
Luan An
Doctoral Dissertation
Năm xuất bản
Số trang
169
Thời gian đọc
26 phút
Lượt xem
0
Lượt tải
0
Phí lưu trữ
50 Point
Tổng quan nhanh
- Chủ đề:
- 1. Kỹ thuật ngữ nghĩa trong Lập trình Di truyền
- Số trang:
- 169 trang
- Trường:
- Military Technical Academy
- Chuyên ngành:
- Mathematical Foundations for Informatics
- Tác giả:
- Chu Thi Huong
- Năm:
- 2019
Tóm tắt nội dung luận án
I. Kỹ thuật ngữ nghĩa trong Lập trình Di truyền
Lập trình Di truyền (GP) là một phương pháp của điện toán tiến hóa. GP tạo ra các chương trình máy tính một cách tự động. Phương pháp này dựa trên nguyên tắc chọn lọc tự nhiên. Tuy nhiên, GP đối mặt với nhiều thách thức. Một thách thức lớn là sự phức tạp không cần thiết của chương trình, hay còn gọi là bloat. Các chương trình GP thường phát triển kích thước lớn mà không cải thiện hiệu suất. Điều này làm chậm quá trình tiến hóa và khó giải thích kết quả. Các kỹ thuật truyền thống của GP thường tập trung vào cú pháp. Chúng đánh giá chương trình dựa trên cấu trúc hình thức. Cách tiếp cận này bỏ qua ý nghĩa thực sự của chương trình. Ngữ nghĩa chương trình cung cấp một cách nhìn sâu sắc hơn. Ngữ nghĩa là hành vi hoặc đầu ra của chương trình. Việc hiểu ngữ nghĩa giúp đánh giá chương trình chính xác hơn. Phương pháp dựa trên ngữ nghĩa có tiềm năng giải quyết các vấn đề của GP. Chúng cải thiện hiệu suất và kiểm soát kích thước chương trình.
1.1. Định nghĩa ngữ nghĩa trong GP
Ngữ nghĩa trong Lập trình Di truyền mô tả hành vi của một chương trình. Nó không chỉ là cấu trúc cú pháp của cây biểu thức. Ngữ nghĩa chương trình thể hiện đầu ra của chương trình với các tập hợp dữ liệu đầu vào. Ví dụ, hai chương trình có thể có cấu trúc khác nhau. Tuy nhiên, chúng tạo ra cùng một kết quả cho cùng đầu vào. Khi đó, chúng có tương đương ngữ nghĩa. Việc xác định ngữ nghĩa giúp đánh giá chất lượng chương trình. Nó cho phép so sánh các giải pháp dựa trên chức năng. Sự khác biệt về ngữ nghĩa được gọi là khoảng cách ngữ nghĩa. Khoảng cách ngữ nghĩa đo lường mức độ khác biệt về hành vi. Khái niệm này rất quan trọng trong việc thiết kế các toán tử di truyền mới. Nó cũng cần thiết cho các chiến lược chọn lọc hiệu quả.
1.2. Vai trò của phân tích ngữ nghĩa chương trình
Phân tích ngữ nghĩa chương trình là quá trình xác định hành vi của chương trình. Trong Lập trình Di truyền, phân tích ngữ nghĩa cung cấp thông tin giá trị. Thông tin này vượt xa cấu trúc cú pháp đơn thuần. Nó giúp nhận diện các chương trình có chức năng tương tự. Điều này quan trọng khi các chương trình có hình thức khác nhau. Phân tích ngữ nghĩa hỗ trợ tối ưu hóa dựa trên ngữ nghĩa. Nó cho phép thuật toán tiến hóa đưa ra quyết định thông minh hơn. Ví dụ, chọn lọc có thể ưu tiên các chương trình gọn gàng. Nhưng chúng phải giữ nguyên hành vi ngữ nghĩa mong muốn. Phân tích này cũng hữu ích trong việc kiểm soát bloat ngữ nghĩa. Các thành phần mã không đóng góp vào ngữ nghĩa có thể được loại bỏ. Điều này cải thiện hiệu quả của thuật toán tiến hóa.
II. Tối ưu chọn lọc ngữ nghĩa trong Lập trình Di truyền
Các phương pháp chọn lọc truyền thống trong Lập trình Di truyền thường gặp hạn chế. Chúng dựa vào giá trị độ phù hợp và kích thước chương trình. Tuy nhiên, điều này không phải lúc nào cũng tối ưu. Một chương trình có độ phù hợp cao có thể quá lớn. Hoặc nó có thể chứa các phần không cần thiết. Ngữ nghĩa chương trình cung cấp một tiêu chí mới. Nó giúp lựa chọn các cá thể hiệu quả hơn. Tối ưu hóa dựa trên ngữ nghĩa tập trung vào hành vi thực tế của chương trình. Phương pháp chọn lọc ngữ nghĩa ưu tiên các cá thể. Các cá thể này phải có hành vi phù hợp với mục tiêu. Đồng thời, chúng cần duy trì sự đơn giản nếu có thể. Điều này giúp tránh bloat trong lập trình di truyền. Các thuật toán tiến hóa có thể khám phá không gian giải pháp hiệu quả hơn.
2.1. Chiến lược chọn lọc dựa trên ngữ nghĩa
Nhiều chiến lược chọn lọc mới đã được đề xuất. Chúng tích hợp ngữ nghĩa chương trình vào quá trình quyết định. Một cách tiếp cận là chọn lọc đấu loại dựa trên ngữ nghĩa. Trong đấu loại, các chương trình được so sánh không chỉ bằng độ phù hợp. Chúng còn được đánh giá bằng sự tương đồng ngữ nghĩa. Các chương trình có ngữ nghĩa tương tự nhưng nhỏ hơn được ưu tiên. Một chiến lược khác là chọn lọc đa mục tiêu. Nó cân bằng độ phù hợp, kích thước và hành vi ngữ nghĩa. Điều này giúp duy trì sự đa dạng trong quần thể. Đồng thời, nó thúc đẩy sự tiến hóa của các giải pháp chất lượng cao. Các phương pháp này đòi hỏi phân tích ngữ nghĩa chương trình hiệu quả. Việc tính toán khoảng cách ngữ nghĩa giữa các cá thể là cần thiết.
2.2. Kết hợp chọn lọc ngữ nghĩa với toán tử di truyền
Chọn lọc ngữ nghĩa không hoạt động độc lập. Nó thường được kết hợp với các toán tử di truyền cải tiến. Ví dụ, lai ghép ngữ nghĩa (semantic crossover) là một kỹ thuật như vậy. Lai ghép ngữ nghĩa tạo ra con cái. Con cái có hành vi ngữ nghĩa tương tự với cha mẹ. Hoặc nó có ngữ nghĩa được kiểm soát. Sự kết hợp này mang lại hiệu quả lớn. Các toán tử này sử dụng khoảng cách ngữ nghĩa để hướng dẫn quá trình tìm kiếm. Chúng có thể tránh tạo ra các cá thể vô dụng. Đồng thời, chúng duy trì các đặc tính ngữ nghĩa mong muốn. Điều này giúp các thuật toán tiến hóa hội tụ nhanh hơn. Nó cũng tạo ra các giải pháp có thể giải thích được. Việc kiểm soát bloat ngữ nghĩa cũng được cải thiện.
III. Giảm thiểu bloat mã nguồn bằng ngữ nghĩa trong GP
Bloat trong Lập trình Di truyền là một vấn đề dai dẳng. Nó đề cập đến sự tăng kích thước chương trình không cần thiết. Các chương trình lớn tiêu tốn tài nguyên tính toán. Chúng cũng khó phân tích và hiểu. Bloat thường xuất hiện do các mã "vô ích" tích tụ. Các mã này không ảnh hưởng đến hành vi ngữ nghĩa của chương trình. Tuy nhiên, chúng làm tăng độ phức tạp cấu trúc. Kiểm soát bloat ngữ nghĩa là mục tiêu chính của nhiều nghiên cứu. Các kỹ thuật dựa trên ngữ nghĩa cung cấp giải pháp mạnh mẽ. Chúng nhận diện và loại bỏ các thành phần dư thừa. Các thành phần này không thay đổi chức năng của chương trình. Việc giảm thiểu bloat giúp tăng tốc độ tiến hóa. Nó cũng làm cho các giải pháp cuối cùng trở nên rõ ràng hơn.
3.1. Các kỹ thuật dựa trên ngữ nghĩa để giảm bloat
Một kỹ thuật phổ biến là xấp xỉ ngữ nghĩa. Xấp xỉ ngữ nghĩa tìm kiếm các cây con đơn giản hơn. Các cây con này có hành vi ngữ nghĩa gần giống với cây con ban đầu. Việc thay thế các cây con phức tạp bằng phiên bản đơn giản hơn giúp giảm kích thước. Điều này duy trì được hiệu suất của chương trình. Một phương pháp khác liên quan đến việc định hình các toán tử di truyền. Các toán tử này được thiết kế để tạo ra các cá thể gọn gàng hơn. Đồng thời, chúng phải bảo toàn ngữ nghĩa. Ví dụ, lai ghép và đột biến có thể được điều chỉnh. Chúng sẽ tránh tạo ra mã thừa. Việc phân tích ngữ nghĩa là trọng tâm của các phương pháp này. Nó giúp xác định "mã vô ích" hiệu quả.
3.2. So sánh với các phương pháp kiểm soát bloat khác
Các phương pháp kiểm soát bloat truyền thống thường sử dụng áp lực tiết kiệm. Áp lực này trực tiếp phạt các chương trình lớn hơn. Ví dụ, nó có thể thêm một hình phạt vào độ phù hợp. Hoặc nó giới hạn kích thước cây. Tuy nhiên, các phương pháp này có thể loại bỏ các cấu trúc hữu ích. Chúng có thể ảnh hưởng tiêu cực đến khả năng tìm kiếm của thuật toán tiến hóa. Các kỹ thuật kiểm soát bloat ngữ nghĩa vượt trội hơn. Chúng đánh giá các thành phần dựa trên đóng góp chức năng. Mã được giữ lại nếu nó có tác động ngữ nghĩa. Mã dư thừa sẽ bị loại bỏ. Cách tiếp cận này giúp giữ lại sự đa dạng cần thiết. Nó cũng duy trì khả năng khám phá không gian giải pháp. Điều này dẫn đến các giải pháp GP mạnh mẽ và hiệu quả hơn.
IV. Phân tích ngữ nghĩa nâng cao hiệu suất Lập trình Di truyền
Phân tích ngữ nghĩa là cốt lõi của các cải tiến trong Lập trình Di truyền. Nó không chỉ giúp kiểm soát bloat. Phân tích ngữ nghĩa còn dẫn đến hiệu suất giải thuật tổng thể tốt hơn. Việc hiểu rõ hành vi của chương trình cho phép các thuật toán tiến hóa hoạt động thông minh hơn. Chúng đưa ra quyết định dựa trên ý nghĩa thực sự của mã. Hiệu suất được nâng cao qua nhiều khía cạnh. Thứ nhất, khả năng hội tụ của thuật toán được cải thiện. Thứ hai, chất lượng của các giải pháp cuối cùng cao hơn. Thứ ba, thời gian tính toán giảm đáng kể. Điều này xảy ra khi các chương trình không bị bloat. Phân tích ngữ nghĩa cung cấp công cụ để tối ưu hóa dựa trên ngữ nghĩa. Nó định hướng quá trình tìm kiếm hiệu quả hơn.
4.1. Đánh giá độ phức tạp chức năng và ngữ nghĩa
Đánh giá độ phức tạp trong Lập trình Di truyền không chỉ đơn thuần là đếm số nút hoặc số nhánh. Điều quan trọng hơn là đánh giá độ phức tạp chức năng, phản ánh hành vi thực tế của chương trình. Phân tích ngữ nghĩa cho phép đo lường độ phức tạp này một cách chính xác. Một chương trình có thể có cấu trúc cây biểu thức lớn nhưng ngữ nghĩa đơn giản, nghĩa là nó thực hiện một chức năng dễ dàng. Ngược lại, một chương trình nhỏ gọn có thể sở hữu ngữ nghĩa phức tạp, thực hiện một nhiệm vụ khó khăn. Các phương pháp phân tích ngữ nghĩa giúp định lượng điều này bằng cách xem xét nhiều yếu tố. Chúng có thể bao gồm số lượng đầu vào ảnh hưởng đến đầu ra hoặc số lượng trạng thái ngữ nghĩa mà chương trình có thể đạt được. Sự đánh giá sâu sắc này là cần thiết để phân biệt các chương trình thực sự hiệu quả. Đồng thời, nó xác định những chương trình có độ phức tạp không cần thiết. Điều này giúp tối ưu hóa dựa trên ngữ nghĩa.
4.2. Khai thác ngữ nghĩa cho các bài toán tối ưu hóa
Lập trình Di truyền thường được áp dụng cho các bài toán tối ưu hóa. Ngữ nghĩa chương trình cung cấp thông tin quý giá. Thông tin này hướng dẫn quá trình tìm kiếm giải pháp. Các thuật toán tiến hóa có thể sử dụng ngữ nghĩa để tinh chỉnh mục tiêu. Chúng xác định các giải pháp tối ưu không chỉ dựa trên độ phù hợp. Chúng còn dựa trên khả năng giải thích và tính đơn giản của giải pháp. Việc khai thác ngữ nghĩa giúp cải thiện khả năng tìm kiếm. Nó có thể tránh các vùng không gian giải pháp kém hiệu quả. Hoặc nó có thể tập trung vào các khu vực tiềm năng. Điều này đặc biệt hữu ích cho các bài toán phức tạp. Các bài toán này yêu cầu sự cân bằng giữa hiệu suất và tính gọn gàng. Ngữ nghĩa cung cấp một tiêu chí mạnh mẽ cho việc này.
V. Ứng dụng Kỹ thuật Ngữ nghĩa cho Lập trình Di truyền
Các kỹ thuật dựa trên ngữ nghĩa đã mở rộng phạm vi ứng dụng của Lập trình Di truyền. Chúng không chỉ cải thiện hiệu suất trên các bài toán chuẩn. Các kỹ thuật này còn giúp GP giải quyết các vấn đề thực tế phức tạp. Một ví dụ điển hình là dự đoán chuỗi thời gian. Trong lĩnh vực này, việc tạo ra các mô hình có thể giải thích được là rất quan trọng. Ngữ nghĩa chương trình giúp tạo ra các mô hình đó. Ứng dụng các phương pháp ngữ nghĩa mang lại nhiều lợi ích. Chúng bao gồm việc tạo ra các mô hình có độ chính xác cao. Đồng thời, các mô hình này có kích thước hợp lý. Điều này giúp chúng dễ hiểu và dễ triển khai hơn. Việc kiểm soát bloat ngữ nghĩa trở nên đặc biệt quan trọng. Nó đảm bảo các mô hình không trở nên quá phức tạp. Các thuật toán tiến hóa trở thành công cụ mạnh mẽ hơn.
5.1. Dự đoán chuỗi thời gian bằng Lập trình Di truyền ngữ nghĩa
Dự đoán chuỗi thời gian là một bài toán khó. Nó yêu cầu các mô hình có khả năng học các mẫu phức tạp. Lập trình Di truyền ngữ nghĩa cung cấp một giải pháp hứa hẹn. Các mô hình được tạo ra có thể hiểu được. Chúng dự đoán các giá trị trong tương lai dựa trên dữ liệu quá khứ. Việc áp dụng ngữ nghĩa giúp tối ưu hóa cấu trúc mô hình. Nó giảm thiểu bloat trong lập trình di truyền cho các mô hình này. Đồng thời, nó duy trì độ chính xác cao. Điều này tạo ra các mô hình dự đoán mạnh mẽ. Chúng có thể được sử dụng trong tài chính, khí tượng hoặc y tế. Các thuật toán tiến hóa được tăng cường đáng kể bởi cách tiếp cận này.
5.2. Hướng nghiên cứu tương lai về ngữ nghĩa GP
Nghiên cứu về ngữ nghĩa trong Lập trình Di truyền vẫn còn nhiều tiềm năng. Một hướng là phát triển các phương pháp phân tích ngữ nghĩa chương trình hiệu quả hơn. Điều này bao gồm xử lý các loại ngữ nghĩa phức tạp. Ví dụ, ngữ nghĩa trạng thái hoặc ngữ nghĩa song song. Một hướng khác là tích hợp sâu hơn các kỹ thuật ngữ nghĩa. Chúng có thể được áp dụng vào các biến thể GP khác. Ví dụ như Linear Genetic Programming hoặc Cartesian Genetic Programming. Việc khám phá các khái niệm về khoảng cách ngữ nghĩa và tương đương ngữ nghĩa cũng rất quan trọng. Mục tiêu là tạo ra các thuật toán tiến hóa thông minh hơn. Các thuật toán này có khả năng tự động tạo ra mã nguồn hiệu quả. Đồng thời, chúng có khả năng giải thích cao.
Mục lục chi tiết luận án
Tải xuống file đầy đủ để xem toàn bộ nội dung
Tải đầy đủ (169 trang)Nội dung chính
Chào bạn, với 10 năm kinh nghiệm trong lĩnh vực viết content SEO cho tài liệu học thuật, tôi đã phân tích kỹ lưỡng luận án "Semantics-Based Selection and Code Bloat Reduction Techniques for Genetic Programming" của Chu Thị Hường. Dưới đây là nội dung SEO chi tiết, bám sát cấu trúc và quy tắc bạn đã đưa ra, nhằm tối ưu hóa khả năng hiển thị và tiếp cận độc giả mục tiêu.
Tối Ưu Hóa Lập Trình Di truyền: Giải Pháp Tuyển Chọn và Kiểm Soát Phình Mã Dựa trên Ngữ Nghĩa
Trong bối cảnh trí tuệ nhân tạo (AI) và học máy (Machine Learning) đang bùng nổ, các thuật toán tiến hóa (Evolutionary Algorithms - EAs) như Lập trình Di truyền (Genetic Programming - GP) ngày càng khẳng định vai trò quan trọng của mình. GP, với khả năng tự động tạo ra các chương trình máy tính để giải quyết vấn đề, đã mở ra nhiều hướng đi đột phá trong các lĩnh vực từ hồi quy ký hiệu (symbolic regression) đến phân loại và điều khiển. Tuy nhiên, GP truyền thống thường gặp phải những thách thức lớn, đặc biệt là khi chỉ tập trung vào các khía cạnh cú pháp (syntactic) mà bỏ qua ngữ nghĩa (semantics) sâu sắc của chương trình. Điều này dẫn đến hiệu suất chưa tối ưu, khả năng tạo ra các chương trình khó hiểu và kém hiệu quả, cũng như hiện tượng phình mã (code bloat) – vấn đề khiến kích thước chương trình tăng không kiểm soát, ảnh hưởng nghiêm trọng đến tài nguyên và thời gian tính toán.
Luận án "Semantics-Based Selection and Code Bloat Reduction Techniques for Genetic Programming" của Chu Thị Hường (2019) đã đi sâu giải quyết những vấn đề cốt lõi này. Nghiên cứu này không chỉ chỉ ra những hạn chế của các phương pháp GP hiện có mà còn đề xuất các giải pháp tiên tiến, dựa trên ngữ nghĩa chương trình để cải thiện đáng kể hiệu suất, kiểm soát kích thước mã và tăng tính đa dạng ngữ nghĩa. Bằng cách tích hợp thông tin ngữ nghĩa vào các cơ chế chọn lọc và kiểm soát phình mã, luận án đã mở ra một hướng tiếp cận mới, hứa hẹn mang lại những bước tiến lớn cho lĩnh vực Lập trình Di truyền và các ứng dụng thực tiễn của nó.
Tổng quan nghiên cứu
Trong kỷ nguyên số hóa, nhu cầu về các hệ thống thông minh có khả năng tự động học hỏi và thích nghi ngày càng tăng cao. Lập trình Di truyền (GP) nổi lên như một nhánh quan trọng của thuật toán tiến hóa, cho phép máy tính tự động phát triển các chương trình giải quyết vấn đề mà không cần lập trình viên phải chỉ định tường minh cấu trúc. Tầm quan trọng của GP là không thể phủ nhận, với các ứng dụng đa dạng từ mô hình hóa dữ liệu, hồi quy ký hiệu cho đến nhận dạng mẫu và kỹ thuật phần mềm.
Tuy nhiên, các phương pháp GP truyền thống thường gặp phải một số hạn chế cố hữu. Một trong số đó là việc quá tập trung vào cú pháp của chương trình, dẫn đến ánh xạ kiểu gen-kiểu hình (genotype-phenotype mapping) phức tạp và thiếu sự tương đồng ngữ nghĩa giữa các thế hệ. Điều này có nghĩa là một thay đổi nhỏ về cấu trúc (cú pháp) có thể dẫn đến sự thay đổi lớn về hành vi (ngữ nghĩa), làm giảm hiệu quả của quá trình tiến hóa. Hơn nữa, hiện tượng phình mã (code bloat), khi kích thước của các chương trình trong quần thể tăng lên không cần thiết, đã trở thành một trở ngại lớn, gây tốn kém tài nguyên tính toán và làm giảm khả năng giải thích của các giải pháp.
Nhận thấy những "khoảng trống" quan trọng này, luận án tập trung vào việc cải thiện hiệu suất của GP thông qua việc tích hợp ngữ nghĩa vào cơ chế chọn lọc và phát triển các kỹ thuật kiểm soát phình mã hiệu quả. Cách tiếp cận của luận án là kết hợp phân tích lý thuyết với thực nghiệm, sử dụng các kỹ thuật từ thống kê, ngữ nghĩa hình thức, học máy và tối ưu hóa để nâng cao hiệu suất của GP. Các phương pháp mới được đề xuất không chỉ giải quyết triệt để các vấn đề nêu trên mà còn thúc đẩy đa dạng ngữ nghĩa và giảm phình mã, mang lại những cải tiến đáng kể cho Lập trình Di truyền hiện đại.
Nội dung chi tiết
Vấn đề nghiên cứu và Cơ sở lý thuyết
Lập trình Di truyền (GP) là một phương pháp học máy dựa trên Thuật toán Tiến hóa (EA) được thiết kế để tự động tìm kiếm các giải pháp có cấu trúc không xác định cho một vấn đề nhất định. Một hệ thống GP hoạt động bằng cách khởi tạo một quần thể các chương trình, sau đó tiến hóa chúng qua nhiều thế hệ bằng cách áp dụng các toán tử di truyền (genetic operators) như crossover (lai ghép) và mutation (đột biến). Tại mỗi thế hệ, các chương trình được đánh giá bằng một hàm đánh giá độ thích nghi (fitness function), và một cơ chế chọn lọc (selection mechanism) được sử dụng để chọn ra các cá thể tốt hơn tạo ra quần thể tiếp theo.
Mặc dù GP đã được ứng dụng thành công trong nhiều lĩnh vực, nhưng GP truyền thống thường chỉ hướng dẫn quá trình tiến hóa dựa trên các khía cạnh cú pháp của biểu diễn GP. Điều này tạo ra một ánh xạ kiểu gen-kiểu hình phức tạp, nơi một thay đổi nhỏ về cú pháp có thể dẫn đến sự thay đổi lớn về hành vi (ngữ nghĩa) của chương trình. Ví dụ, việc thay thế phép nhân với 0.001 bằng phép chia cho 0.001 là một thay đổi cú pháp nhỏ nhưng gây ra sự thay đổi ngữ nghĩa đáng kể. Các thuật toán chỉ dựa vào cấu trúc thường không đạt được hiệu quả cao, bởi vì từ góc độ của một lập trình viên, các chương trình phải đúng không chỉ về mặt cú pháp mà còn về mặt ngữ nghĩa.
Trong ngữ cảnh của GP, ngữ nghĩa (semantics) của một chương trình được định nghĩa là vector các giá trị đầu ra mà chương trình đó tạo ra khi chạy trên tất cả các trường hợp đánh giá độ thích nghi (fitness cases). Khoảng cách ngữ nghĩa (semantic distance) giữa hai chương trình phản ánh mức độ khác biệt trong hành vi của chúng. Nhiều nghiên cứu trước đây đã cố gắng tích hợp thông tin ngữ nghĩa vào GP bằng cách sửa đổi hoặc thiết kế các toán tử di truyền mới, hoặc thúc đẩy tính cục bộ và đa dạng ngữ nghĩa. Tuy nhiên, việc ứng dụng ngữ nghĩa vào cơ chế chọn lọc và kiểm soát phình mã vẫn còn hạn chế. Các phương pháp chọn lọc tiêu chuẩn thường chỉ sử dụng giá trị độ thích nghi và bỏ qua các thông tin chi tiết hơn như ngữ nghĩa, có thể dẫn đến việc lựa chọn các cá thể kém đa dạng về mặt ngữ nghĩa và làm giảm khả năng khám phá không gian lời giải. Hơn nữa, hiện tượng phình mã (code bloat) – sự tăng trưởng không cần thiết của kích thước chương trình – là một vấn đề lớn, thường làm giảm hiệu suất của GP.
Phương pháp và Giải pháp
Để giải quyết những thách thức cố hữu của Lập trình Di truyền truyền thống, luận án của Chu Thị Hường đã phát triển một loạt các phương pháp đổi mới, tập trung vào việc tận dụng sức mạnh của ngữ nghĩa chương trình. Các giải pháp này được thiết kế để cải thiện cả cơ chế chọn lọc và kiểm soát phình mã, hai yếu tố then chốt ảnh hưởng đến hiệu suất GP.
Điểm nổi bật đầu tiên là việc đề xuất ba phương pháp chọn lọc đấu loại dựa trên ngữ nghĩa mới. Thay vì chỉ dựa vào độ thích nghi (fitness) thuần túy để chọn ra cá thể tốt nhất, các phương pháp này đưa thông tin ngữ nghĩa vào quá trình so sánh giữa các cá thể. Cụ thể, luận án đã giới thiệu một cách tiếp cận mới để so sánh các cá thể dựa trên phân tích thống kê các vector lỗi ngữ nghĩa của chúng. Ba biến thể của chiến lược chọn lọc này đã được đề xuất, mỗi biến thể sử dụng các tiêu chí thống kê khác nhau để đánh giá sự khác biệt ngữ nghĩa. Các phương pháp này được kỳ vọng sẽ thúc đẩy đa dạng ngữ nghĩa (semantic diversity) trong quần thể, giúp thuật toán khám phá không gian lời giải hiệu quả hơn và đồng thời giảm thiểu hiện tượng phình mã.
Đóng góp quan trọng thứ hai là kỹ thuật xấp xỉ ngữ nghĩa (Semantic Approximation Technique). Kỹ thuật này là một đổi mới đáng kể, cho phép phát triển một cây con nhỏ có ngữ nghĩa xấp xỉ một ngữ nghĩa mục tiêu cho trước. Trong GP, việc thao tác ngữ nghĩa ở cấp độ cây con là rất phức tạp. Kỹ thuật xấp xỉ ngữ nghĩa mới cung cấp một công cụ mạnh mẽ để tạo ra hoặc sửa đổi các phần của chương trình sao cho chúng đạt được một hành vi mong muốn mà vẫn giữ được cấu trúc nhỏ gọn. Đây là nền tảng cho việc kiểm soát kích thước chương trình một cách thông minh.
Cuối cùng, dựa trên kỹ thuật xấp xỉ ngữ nghĩa này, luận án đã giới thiệu các phương pháp kiểm soát phình mã mới. Các phương pháp này được lấy cảm hứng từ khả năng tạo ra các cây con có ngữ nghĩa xấp xỉ ngữ nghĩa mục tiêu. Bằng cách sử dụng kỹ thuật xấp xỉ ngữ nghĩa, các phương pháp kiểm soát phình mã có thể "cắt tỉa" hoặc "thay thế" các phần của chương trình một cách có ý thức về ngữ nghĩa. Điều này giúp loại bỏ các đoạn mã không cần thiết hoặc trùng lặp mà không làm thay đổi đáng kể hành vi tổng thể của chương trình. Quy trình này cho phép giảm kích thước chương trình (code bloat) một cách hiệu quả, giữ cho các giải pháp nhỏ gọn hơn, dễ hiểu hơn và tốn ít tài nguyên tính toán hơn, trong khi vẫn duy trì hoặc thậm chí cải thiện hiệu suất.
Việc phát triển các phương pháp này đòi hỏi sự kết hợp giữa phân tích lý thuyết sâu sắc, kiểm định giả thuyết thống kê (Statistical Hypothesis Test) để đánh giá sự khác biệt có ý nghĩa, và các khái niệm từ ngữ nghĩa hình thức (formal semantics) và học máy để thiết kế các thuật toán tối ưu.
Kết quả và Ứng dụng
Các phương pháp tuyển chọn dựa trên ngữ nghĩa và kiểm soát phình mã được đề xuất trong luận án đã trải qua quá trình kiểm tra và đánh giá nghiêm ngặt. Nghiên cứu sử dụng một bộ lớn các bài toán hồi quy ký hiệu (symbolic regression) chuẩn từ tài liệu học thuật và các tập dữ liệu thực tế từ kho lưu trữ học máy UCI. Mục tiêu là xác định hiệu quả của các phương pháp này so với các kỹ thuật GP hiện có.
Kết quả chính của nghiên cứu cho thấy những cải tiến đáng kể:
- Cải thiện hiệu suất Lập trình Di truyền: Các phương pháp chọn lọc đấu loại dựa trên ngữ nghĩa mới đã chứng minh khả năng vượt trội trong việc cải thiện độ chính xác và hiệu quả của GP. Bằng cách tích hợp phân tích thống kê ngữ nghĩa, các phương pháp này giúp thuật toán lựa chọn các cá thể không chỉ dựa trên độ thích nghi mà còn dựa trên sự đa dạng ngữ nghĩa. Điều này ngăn chặn hiện tượng hội tụ sớm và duy trì khả năng khám phá mạnh mẽ của quần thể, dẫn đến việc tìm ra các giải pháp tối ưu hơn.
- Thúc đẩy đa dạng ngữ nghĩa: Các phương pháp chọn lọc dựa trên ngữ nghĩa đã tăng cường đáng kể đa dạng ngữ nghĩa trong quần thể GP. Điều này là cực kỳ quan trọng vì sự đa dạng giúp thuật toán tránh mắc kẹt vào các cực tiểu cục bộ và tìm kiếm không gian lời giải một cách toàn diện hơn.
- Giảm thiểu hiện tượng phình mã (code bloat): Các kỹ thuật kiểm soát phình mã mới, dựa trên nguyên lý xấp xỉ ngữ nghĩa, đã đạt được thành công nổi bật trong việc giảm kích thước chương trình. Kết quả thực nghiệm cho thấy các phương pháp này có thể duy trì hoặc thậm chí cải thiện hiệu suất trong khi tạo ra các chương trình ngắn gọn hơn đáng kể. Việc giảm phình mã giúp các chương trình dễ hiểu, dễ kiểm tra và tiêu tốn ít tài nguyên tính toán hơn.
- Ứng dụng thực tiễn: Luận án đã minh họa hiệu quả của các phương pháp này trên các bài toán dự báo chuỗi thời gian (time series forecasting) trong thế giới thực. Kết quả cho thấy tiềm năng ứng dụng rộng rãi của các kỹ thuật này trong các lĩnh vực như tài chính, dự báo kinh tế, kỹ thuật và bất kỳ nơi nào cần mô hình hóa dữ liệu phức tạp. Các chương trình nhỏ gọn và hiệu quả được tạo ra có thể được triển khai dễ dàng hơn trong các hệ thống thực tế.
Những kết quả này có ý nghĩa quan trọng, không chỉ mở ra hướng đi mới cho việc thiết kế các hệ thống GP hiệu quả và mạnh mẽ hơn mà còn cung cấp các công cụ thực tiễn để giải quyết một trong những thách thức lớn nhất của Lập trình Di truyền. Khả năng tạo ra các giải pháp nhỏ gọn, có tính giải thích cao và hoạt động tốt trên dữ liệu thực là một bước tiến quan trọng cho cộng đồng nghiên cứu và ứng dụng AI.
Ai nên đọc tài liệu này?
Tài liệu này là một nguồn tài nguyên quý giá và không thể thiếu cho những đối tượng sau:
- Nghiên cứu sinh và Học giả trong lĩnh vực Lập trình Di truyền (GP) và Thuật toán Tiến hóa (EA): Luận án cung cấp những phương pháp tiên tiến và đóng góp lý thuyết sâu sắc về việc tích hợp ngữ nghĩa. Đây là nguồn cảm hứng và tài liệu tham khảo cốt lõi cho các nghiên cứu tiếp theo về hiệu suất Lập trình Di truyền, đa dạng ngữ nghĩa và kiểm soát phình mã.
- Kỹ sư phần mềm và Nhà phát triển AI/Học máy: Những người quan tâm đến việc xây dựng các hệ thống tự động hóa chương trình hoặc tối ưu hóa các giải pháp dựa trên thuật toán tiến hóa sẽ tìm thấy các kỹ thuật thực tiễn để cải thiện hiệu suất, độ tin cậy và khả năng mở rộng của các ứng dụng của họ, đặc biệt trong các bài toán hồi quy ký hiệu và dự báo chuỗi thời gian.
- Giảng viên và Sinh viên chuyên ngành Khoa học Máy tính, Trí tuệ Nhân tạo, Khoa học Dữ liệu: Tài liệu này cung cấp một cái nhìn toàn diện và sâu sắc về các khía cạnh nâng cao của GP, đặc biệt là vai trò của ngữ nghĩa. Nó rất phù hợp cho các khóa học nâng cao hoặc làm tài liệu nghiên cứu cho các dự án chuyên sâu.
- Các nhà khoa học dữ liệu và chuyên gia phân tích: Những người làm việc với các bài toán mô hình hóa dữ liệu phức tạp, đặc biệt là dự báo chuỗi thời gian hoặc tìm kiếm các hàm quan hệ ẩn trong dữ liệu, sẽ được hưởng lợi từ các phương pháp kiểm soát phình mã và xấp xỉ ngữ nghĩa để phát triển các mô hình hiệu quả và có thể giải thích được.
Để hiểu rõ hơn về nội dung, độc giả nên có kiến thức nền tảng về Lập trình Di truyền và Thuật toán Tiến hóa, cùng với các khái niệm cơ bản về học máy và thống kê. Tài liệu này sẽ mang lại lợi ích cụ thể cho từng nhóm đối tượng bằng cách cung cấp các giải pháp tiên tiến, mở rộng kiến thức chuyên môn và thúc đẩy khả năng ứng dụng thực tiễn trong các dự án học máy và AI.
Câu hỏi thường gặp
1. Lập trình Di truyền (GP) dựa trên ngữ nghĩa là gì?
Lập trình Di truyền dựa trên ngữ nghĩa là một hướng tiếp cận trong GP tập trung vào ý nghĩa hoặc hành vi của chương trình thay vì chỉ cấu trúc cú pháp của chúng. Ngữ nghĩa của một chương trình thường được định nghĩa là vector các giá trị đầu ra của nó trên một tập hợp các đầu vào (fitness cases). Phương pháp này giúp GP tạo ra các chương trình hiệu quả hơn, ít phình mã hơn và có khả năng giải thích tốt hơn bằng cách đảm bảo sự đa dạng và chính xác về mặt hành vi.
2. Các phương pháp chọn lọc dựa trên ngữ nghĩa cải thiện hiệu suất GP như thế nào?
Các phương pháp chọn lọc dựa trên ngữ nghĩa cải thiện hiệu suất GP bằng cách tích hợp thông tin ngữ nghĩa vào quá trình lựa chọn các cá thể cho thế hệ tiếp theo. Thay vì chỉ dựa vào độ thích nghi (fitness) đơn thuần, chúng phân tích thống kê các vector lỗi ngữ nghĩa giữa các chương trình. Điều này giúp chọn lọc các cá thể đa dạng hơn về mặt ngữ nghĩa, ngăn chặn hiện tượng hội tụ sớm, tăng cường khả năng khám phá không gian lời giải và đồng thời góp phần giảm phình mã.
3. Tại sao việc kiểm soát "code bloat" lại quan trọng trong Lập trình Di truyền?
Kiểm soát "code bloat" (phình mã) là cực kỳ quan trọng trong Lập trình Di truyền vì hiện tượng này khiến kích thước của các chương trình tăng lên không cần thiết. Các chương trình lớn hơn thường khó hiểu, khó kiểm tra, tốn kém tài nguyên tính toán (thời gian và bộ nhớ) và có thể dẫn đến hiện tượng quá khớp (overfitting) với dữ liệu huấn luyện. Kiểm soát phình mã giúp tạo ra các giải pháp nhỏ gọn, hiệu quả và có tính giải thích cao.
4. Kỹ thuật xấp xỉ ngữ nghĩa có thể được áp dụng khi nào?
Kỹ thuật xấp xỉ ngữ nghĩa có thể được áp dụng khi cần phát triển hoặc sửa đổi một cây con (subtree) trong chương trình GP để nó có ngữ nghĩa xấp xỉ một ngữ nghĩa mục tiêu cho trước. Kỹ thuật này đặc biệt hữu ích trong việc thiết kế các toán tử di truyền mới (crossover, mutation) có ý thức về ngữ nghĩa, hoặc trong các phương pháp kiểm soát phình mã để thay thế các phần mã không hiệu quả bằng các cấu trúc nhỏ gọn hơn mà vẫn giữ được hành vi mong muốn.
5. Luận án này có đóng góp gì mới so với các nghiên cứu về ngữ nghĩa trong GP trước đây?
Luận án này có đóng góp mới đáng kể bằng cách tập trung vào cơ chế chọn lọc và kiểm soát phình mã – hai lĩnh vực còn ít được nghiên cứu sâu với góc nhìn ngữ nghĩa. Cụ thể, nó đề xuất ba phương pháp chọn lọc đấu loại dựa trên ngữ nghĩa mới, một kỹ thuật xấp xỉ ngữ nghĩa độc đáo, và các phương pháp kiểm soát phình mã dựa trên kỹ thuật này. Những đóng góp này giúp cải thiện hiệu suất GP, tăng đa dạng ngữ nghĩa và giảm kích thước chương trình một cách hiệu quả và có hệ thống.
Kết luận
Luận án "Semantics-Based Selection and Code Bloat Reduction Techniques for Genetic Programming" đại diện cho một bước tiến quan trọng trong lĩnh vực Lập trình Di truyền. Bằng cách tập trung vào việc khai thác sức mạnh của ngữ nghĩa chương trình, nghiên cứu đã đưa ra những giải pháp đột phá để vượt qua các hạn chế cố hữu của GP truyền thống.
Những điểm nổi bật chính bao gồm:
- Đề xuất thành công ba phương pháp chọn lọc đấu loại dựa trên ngữ nghĩa, sử dụng phân tích thống kê để thúc đẩy đa dạng ngữ nghĩa.
- Giới thiệu kỹ thuật xấp xỉ ngữ nghĩa sáng tạo, cho phép thao tác ngữ nghĩa ở cấp độ cây con một cách hiệu quả.
- Phát triển các phương pháp kiểm soát phình mã mới dựa trên xấp xỉ ngữ nghĩa, mang lại các chương trình nhỏ gọn mà vẫn duy trì hiệu suất cao.
- Minh chứng hiệu quả trên nhiều bài toán hồi quy ký hiệu và dự báo chuỗi thời gian thực tế.
Những đóng góp này không chỉ nâng cao hiệu suất của GP, giảm kích thước chương trình và tăng tính giải thích của các giải pháp, mà còn mở ra những hướng nghiên cứu đầy hứa hẹn. Trong tương lai, việc mở rộng ứng dụng các phương pháp này sang các loại bài toán khác như phân loại, tối ưu hóa đa mục tiêu, hay tích hợp chúng với các mô hình học máy hiện đại sẽ là những bước đi đầy tiềm năng.
Nếu bạn là nhà nghiên cứu, kỹ sư hoặc sinh viên quan tâm đến việc tối ưu hóa các hệ thống AI và Lập trình Di truyền, hãy khám phá toàn văn luận án này để tìm hiểu sâu hơn về các phương pháp đột phá và ứng dụng thực tiễn của chúng. Đừng bỏ lỡ cơ hội tiếp cận những kiến thức nền tảng và giải pháp tiên tiến giúp nâng tầm công việc của bạn trong lĩnh vực Trí tuệ Nhân tạo.
Trích đoạn nội dung luận án
Tải xuống để đọc toàn bộMINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENCE MILITARY TECHNICAL ACADEMY CHU THI HUONG SEMANTICS-BASED SELECTION AND CODE BLOAT REDUCTION TECHNIQUES FOR GENETIC PROGRAMMING DOCTORAL DISSERTATION: MATHEMATICAL FOUNDATION FOR INFORMATICS HA NOI - 2019 MINISTRY OF EDUCATION AND TRAINING MINISTRY OF NATIONAL DEFENCE MILITARY TECHNICAL ACADEMY CHU THI HUONG SEMANTICS-BASED SELECTION AND CODE BLOAT REDUCTION TECHNIQUES FOR GENETIC PROGRAMMING DOCTORAL DISSERTATION Major: Mathematical Foundations for Informatics Code: 9 46 01 10 RESEARCH SUPERVISORS: 1. Nguyen Quang Uy 2. Nguyen Xuan Hoai HA NOI - 2019 ASSURANCE I certify that this dissertation is a research work done by the author under the guidance of the research supervisors. The dissertation has used citation information from many different references, and the ci- tation information is clearly stated.
Experimental results presented in the dissertation are completely honest and not published by any other author or work. Author Chu Thi Huong ACKNOWLEDGEMENTS The first person I would like to thank is my supervisor, Dr Nguyen Quang Uy, the lecturer of Faculty of Information Technology, Military Technical Academy, for directly guiding me through the PhD progress. Dr Uy’s enthusiasm is the power source to motivate me to carry out this research. His guide has inspired much of the research in this dissertation.
I also wish to thank my co-supervisor, Assoc. Dr Nguyen Xuan Hoai at AI Academy. He has given and discussed a lot of new issues with me. Working with Prof Hoai, I have learnt how to do research sys- tematically.
Particularly, I would like to thank the leaders and lecturers of the Faculty of Information Technology, Military Technical Academy for supporting me with favorable conditions and cheerfully helping me in the study and research process. Last, but most important, I also would like to thank my family, my parents for always encouraging me, especially my husband, Nguyen Cong Minh for sharing a lot of happiness and difficulty in the life with me, my children, Nguyen Cong Hung and Nguyen Minh Hang for trying to grow up and study by themselves. Author Chu Thi Huong CONTENTS Contents. v List of figures.
vii List of tables. Representation of Candidate Solutions. Initialising the Population. GP benchmark problems.
Some Variants of GP. Linear Genetic Programming. Cartesian Genetic Programming. Multiple Subpopulations GP.
Semantics in GP. Survey of semantic methods in GP. Semantics in selection and control of code bloat. Statistical Hypothesis Test.
TOURNAMENT SELECTION USING SEMANTICS. Tournament Selection Strategies. Tournament Selection based on Semantics. Statistics Tournament Selection with Random.
Statistics Tournament Selection with Size. Statistics Tournament Selection with Probability. Symbolic Regression Problems. Results and Discussions.
Performance Analysis of Statistics Tournament Selection 57 2. Combining Semantic Tournament Selection with Semantic Crossover. Performance Analysis on The Noisy Data. 76 ii SEMANTIC APPROXIMATION FOR Chapter 3.
REDUCING CODE BLOAT. Controlling GP Code Bloat. Constraining Individual Size. Adjusting Selection Techniques.
Designing Genetic Operators. Bloat, Overfitting and Complexity Analysis. Function Complexity Analysis. Comparing with Machine Learning Algorithms.
Applying semantic methods for time series forecasting. Some other versions. Time series prediction model and parameter settings. Results and Discussion.
123 CONCLUSIONS AND FUTURE WORK. 146 iv ABBREVIATIONS Abbreviation Meaning AGSX Angle-aware Geometric Semantic Crossover BMOPP Biased Multi-Objective Parsimony Pressure method CGP Cartesian Genetic Programming CM Competent Mutation CTS Competent Tournament Selection CX Competent Crossover DA Desired Approximation EA Evolutionary Algorithm Flat-OE Flat Target Distribution GA Genetic Algorithms GCSC Guaranteed Change Semantic Crossover GP Genetic Programming GSGP Geometric Semantic Genetic Programming GSGP-Red GSGP with Reduced trees KLX Krawiec and Lichocki Geometric Crossover LCSC Locality Controlled Semantic Crossover LGP Linear Genetic Programming LGX Locally Geometric Semantic Crossover LPP Lexicographic Parsimony Pressure MODO Multi-Objective Desired Operator MORSM Multi-Objective Randomized Similarity Mutation MS-GP Multiple Subpopulations GP MSSC Most Semantically Similar Crossover v Abbreviation Meaning OE Operator Equalisation PC Perpendicular Crossover PP Prune and Plant PP-AT Prune and Plant based on Approximate Terminal RCL Restricted Candidate List RDO Random Desired Operator ROBDDs Reduced Ordered Binary Decision Diagrams RSM Random Segment Mutation SA Subtree Approximation SAC Semantics Aware Crossover SAS-GP Substituting a subtree with an Approximate Subprogram SAT Semantic Approximation Technique SAT-GP Substituting a subtree with an Approximate Terminal SDC Semantically-Driven Crossover SiS Semantic in Selection SSC Semantic Similarity based Crossover SS+LPE Spatial Structure with Lexicographic Parsimonious Elitism TS-P Statistics Tournament Selection with Probability TS-R Statistics Tournament Selection with Random TS-S Statistics Tournament Selection with Size vi LIST OF FIGURES 1 Number of articles about GP. 2 2 Number of articles using semantics in GP .1 GP syntax tree representing max(x + x, x + 3 ∗ y).2 An example of crossover operator.3 An example of mutation operator.4 An example of LGP program.5 An example of CGP program.6 Structure of MS-GP.7 Running the program p on all fitness cases .8 An example of calculating the desired semantics of the selected node N .1 Testing error and Population size over the generations with tour-size=3.1 An example of Semantic Approximation .3 Average bloat over generations on four problems F1, F13, F17 and F25.4 Average overfitting over the generations on four problems F1, F13, F17 and F25.5 Average complexity of the best individual over the gener- ations on four problems F1, F13, F17 and F25.6 An example of PP-AT.7 Plot of log(unit sale + 1) from 9/1/2016 to 12/31/2016.8 Testing error over the generations.9 Average size of population over the generations. 121 viii LIST OF TABLES 1.1 Summary of Evolutionary Parameter Values .2 GP benchmark regression problems.
Variable names are, in order, x, y, z, v and w. Several benchmark problems in- tentionally omit variables from the function. In the train- ing and testing sets, U [a, b] is uniform random samples drawn from a to b inclusive, and E[a, b] is a grid of points evenly spaced from a to b inclusive .1 Problems for testing statistics tournament selection tech- niques .2 Evolutionary Parameter Values.3 Mean of best fitness with tour-size=3 (the left) and tour- size=7 (the right).4 Median of testing error with tour-size=3 (the left) and tour-size=7 (the right) .5 Average of solution’s size with tour-size=3 (the left) and tour-size=7 (the right) .6 Average semantic distance with tour size=3. Bold indi- cates the value of SiS and TS-S is greater than the value of GP.7 Average percentage of rejecting the null hypothesis in Wilcoxon test of TS-R and TS-S with tour-size=3.8 Median of testing error of TS-RDO and four other tech- niques with tour-size=3 (the left) and tour-size=7 (the right) .9 Average of solutions size of TS-RDO and four other tech- niques with tour-size=3 (the left) and tour-size=7 (the right) .10 Median of testing error on the noisy data with tour-size=3 (the left) and tour-size=7 (the right) .11 Average running time in seconds on noisy data with tour- size=3 (the left) and tour-size=7 (the right) .12 Average execution time of a run (shorted as Run) and average execution time of selection step (shorted as Tour) of GP and TS-S in seconds on noisy data with tour size=3.13 Median of testing error and average running time in sec- onds on noisy data with tour-size=3 when the statistical test is conducted on 100 fitness cases.
The left is the median of the testing error and the right is the average running time.1 Evolutionary parameter values .2 Mean of the best fitness .3 Average percentage of better offspring .4 Median of testing error .5 Average size of solutions .6 Average running time in seconds .7 Values of the grid search for SVR, DT and RF .8 Comparison of the testing error of GP and machine learn- ing systems. The best results are underlined.9 Mean of the best fitness .10 Median of testing errors .11 Average of solution’s size .12 Average running time in seconds .1 Mean best fitness on training noise data with tour-size=3 (the left) and tour-size=7 (the right) .2 Average of solutions size on training noise data with tour- size=3 (the left) and tour-size=7 (the right) .3 Mean of best fitness with tour size=5. The left is original data and the right is noise data.4 Median of testing error with tour size=5. The left is orig- inal data and the right is noise data.5 Average of solution’s size with tour size=5.
The left is original data and the right is noise data.6 Mean of best fitness of TS-RDO and four other techniques with tour size=5. The left is original data and the right is noise data.7 Median of fittest of TS-RDO and four other techniques with tour size=5. The left is original data and the right is noise data.8 Average of solutions size of TS-RDO and four other tech- niques with tour size=5. The left is original data and the right is noise data.
154 xi INTRODUCTION Machine learning is a branch of artificial intelligence that provides the capability to automatically learn and improve from past experience to make future decisions. The fundamental goal of machine learning is to generalize or induce an unknown rule from examples of the rule’s appli- cation. Machine learning has been studied and applied in many different fields of science and technology. It can be said that most smart systems today are the application of one or more machine learning methods.
A GP system is started by initializing a population of individuals. The population is then evolved for a number of generations using genetic operators such as crossover and mutation. At each generation, the individuals are eval- uated using a fitness function, and a selection schema is used to choose better individuals to create the next population. The evolutionary pro- cess is continued until a desired solution is found or when the maximum number of generations is reached.
Since first introduced in the 1990s, GP has been successfully applied in a wide range of problems, especially with applications in classifica- tion, control and regression. Figure 1 surveys the number of GP articles 1 indexed in Scopus1 over a period of 19 years, from 2000 to 2018. The figure shows that GP studies have rapidly increased in the 2010s, about 750 articles per year, and remained roughly stable to date. Figure 1: Number of articles about GP Comparing to other machine learning methods, GP has some advan- tages.
Firstly, GP has the ability to simultaneously learn models (the structure of solutions) and parameters of the models while other methods often have to pre-define models and then find parameters. Secondly, the solutions found by GP are probably interpretable. Recently, several re- searches have shown that GP can be used to evolve both the architecture and the weights of a Deep Learning model effectively [40, 109]. Inter- estingly, in 2018, GP outperformed neural networks and deep learning machines at video games [46, 47, 121]2.
However, despite such advantages, GP is not well known in the main- stream AI and Machine Learning communities. One of the main rea- 1 https://db.vn:2088/search/form.uri?display=basic 2 https://www.com/s/611568/evolutionary-algorithm-outperforms-deep-learning-machines-at- video-games/ 2 sons is that the evolutionary process is often guided by only syntactic aspects of GP representation. Consequently, there is complex, rugged genotype-phenotype mapping, and low similarity of offspring to parents. An offspring generated by changing syntax may not produce the desired result, or a small change in syntax can significantly change its output (behavior).
For example, if we replace the structure x ∗ 0.001 in a tree with the structure x/0.001 that is a small structural change (replacing ‘*’ with ‘/’) but leads to a significant change in behavior. Algorithms based solely on structure as that often do not achieve high efficiency since, from a programmer’s perspective, programs must be correct not only syntactically, but also semantically. Thus, incorporating semantic awareness in the GP evolutionary process could potentially improve per- formance and extend the applicability to problems that are difficult to deal with using purely syntactic approaches. The idea of incorporating semantics into GP evolutionary process is not entirely new.
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ
Trích dẫn luận án này
Chu Thi Huong (2019). Kỹ thuật dựa trên ngữ nghĩa cho lập trình di truyền [Luận án tiến sĩ, Military Technical Academy]. LuanAn.net. https://luanan.net/cong-nghe-thong-tin/khoa-hoc-may-tinh/ky-thuat-ngu-nghia-lap-trinh-di-truyen
Câu hỏi thường gặp
Luận án "Kỹ thuật dựa trên ngữ nghĩa cho lập trình di truyền" nghiên cứu về vấn đề gì?
Luận án: Kỹ thuật ngữ nghĩa cho lựa chọn cạnh tranh & giảm phình mã lập trình di truyền. Nâng cao hiệu quả thuật toán.
Luận án "Kỹ thuật dựa trên ngữ nghĩa cho lập trình di truyền" được bảo vệ tại trường nào?
Luận án này được bảo vệ tại Military Technical Academy. Năm bảo vệ: 2019.
Luận án "Kỹ thuật dựa trên ngữ nghĩa cho lập trình di truyền" thuộc chuyên ngành gì?
Luận án "Kỹ thuật dựa trên ngữ nghĩa cho lập trình di truyền" thuộc chuyên ngành Mathematical Foundations for Informatics. Danh mục: Khoa Học Máy Tính.
Luận án "Kỹ thuật dựa trên ngữ nghĩa cho lập trình di truyền" có bao nhiêu trang?
Luận án "Kỹ thuật dựa trên ngữ nghĩa cho lập trình di truyền" có 169 trang. Bạn có thể xem trước một phần tài liệu ngay trên trang web trước khi tải về.
Cách tải luận án "Kỹ thuật dựa trên ngữ nghĩa cho lập trình di truyền" về máy như thế nào?
Để tải luận án về máy, bạn nhấn nút "Tải xuống ngay" trên trang này, sau đó hoàn tất thanh toán phí lưu trữ. File sẽ được tải xuống ngay sau khi thanh toán thành công. Hỗ trợ qua Zalo: 0559 297 239.