Tài liệu Nghiên cứu ngữ nghĩa trong hệ lập trình gen định hướng bởi văn phạm nối cây và ứng dụng trong xấp xỉ hàm q [tt]

GIỚI THIỆU CHUNG 1. MỤC ĐÍCH Lập trình Gen (Genetic Programming – GP) được đề xuất bởi Koza [1], từ khi ra đời đã được xem như một phương pháp học máy có tiềm năng. Chính vì vậy GP đã được áp dụng rộng rãi để giải quyết thành công nhiều bài toán, trong đó phần nhiều là các bài toán liên quan đến học máy. GP có thể dùng để giải quyết những bài toán học khi độ phức tạp cấu trúc của lời giải là không biết trước, GP đòi hỏi ít tri thức nền của bài toán, và cho lời giải dưới dạng tường minh (cách tiếp cận hộp trắng) cho người dùng. Hệ lập trình Gen định hướng bởi văn phạm nối cây TAG3P (Tree-Adjunct Grammar Guided Genetic) được đề xuất trong [2] là hệ thống sử dụng văn phạm nối cây để định hướng quá trình tiến hóa. TAG3P sử dụng văn phạm nối cây cùng với văn phạm phi ngữ cảnh để đặt ra những ràng buộc về cú pháp cũng như những sai lệch khi tìm kiếm của chương trình tiến hóa. Hệ thống TAG3P có tất cả những thuộc tính của các hệ thống GP thông thường dựa trên các biểu diễn dạng hình cây khác. Ngữ nghĩa là một khái niệm khá rộng được nghiên cứu trong xử lý ngôn ngữ tự nhiên, khoa học máy tính. Trong khoa học máy tính, ngữ nghĩa được định nghĩa một cách không chính thức là ý nghĩa của một chương trình hoặc một hàm có cú pháp đúng. Hai chương trình có cùng cú pháp thì sẽ có cùng ngữ nghĩa, nhưng ngược lại thì không chắc là như vậy. Một ví dụ đơn giản như sau đây, nếu xét về cú pháp thì hai chương trình khác nhau về cú pháp. Nhưng xét về ngữ nghĩa thì hai chương trình là có cùng ngữ nghĩa. Trong thời gian gần đây, vấn đề nghiên cứu ngữ nghĩa và áp dụng ngữ nghĩa trong các hệ lập trình Gen là hướng nghiên cứu rất được quan tâm để cải tiến, định hướng cho quá trình tiến hóa của các cá thể. Mặc dù vậy, khái niệm ngữ nghĩa chưa được nghiên cứu và đề xuất trong hệ lập trình Gen định hướng bởi văn phạm nối cây. Do đó, đây là hướng nghiên cứu cần tiếp tục được thực hiện đối với TAG3P như: nghiên cứu về ngữ nghĩa cây con, thiết kế toán tử di truyền dựa trên ngữ nghĩa. Trong lĩnh vực viễn thông, các nhà nghiên cứu giả thuyết rằng hệ thống nhiễu có dạng biến Gaussian ngẫu nhiên. Tuy nhiên, hàm Q chỉ duy nhất được định nghĩa dưới dạng tích phân suy rộng, điều này sẽ gây nhiều khó khăn cho những phân tích sau này đối với với các hệ thống viễn thông. Do đó, rất cần thiết phải tìm ra các biểu diễn tường minh (dạng giải tích) của hàm Q. Đến thời điểm này, chưa có giải pháp chính xác tuyệt đối cho dạng tường minh của hàm Q, và do đó, các hàm xấp xỉ là lựa chọn duy nhất. Mặc dù có nhiều hàm xấp xỉ dạng tường minh của hàm Q đã được đề xuất bởi các chuyên gia, nhưng do tính chất quan trọng và phổ biến của hàm Q trong lĩnh vực viễn thông, việc tìm kiếm các hàm xấp xỉ tốt hơn, có dạng giải tích và có nhiều đặc điểm quan trọng (chẳng hạn như sự đơn giản, tính khả tích,…) vẫn tiếp tục được 1 thực hiện. Thực tế cho thấy, các nhà khoa học vẫn không ngừng tìm kiếm các dạng xấp xỉ mới, đơn giản hơn, tốt hơn của hàm Q, cụ thể là trong những năm gần đây, các công trình khoa học tiếp tục đăng tải các dạng xấp xỉ mới tìm thấy. Với đặc điểm của hệ lập trình Gen nói chung và hệ TAG3P sẽ phù hợp với bài toán tìm xấp xỉ, do đó, trong luận án sẽ ứng dụng các kết quả nghiên cứu mới để tìm kiếm các dạng xấp xỉ mới, đơn giản hơn, tốt hơn của hàm Q. Đây là là kết quả ứng dụng thực tế và rất có ý nghĩa, đặc biệt trong lĩnh vực viễn thông. 2. MỤC TIÊU NGHIÊN CỨU Đề tài nghiên cứu được triển khai trên cơ sở hệ TAG3P với mục tiêu: - Nghiên cứu, đề xuất khái niệm ngữ nghĩa cây con trong hệ TAG3P làm cơ sở để định hướng quá trình tiến hóa của các cá thể. - Nghiên cứu, đề xuất và thử nghiệm các toán tử di truyền mới dựa trên “Ngữ nghĩa”. - Thử nghiệm hệ TAG3P với toán tử mới để giải quyết các bài toán thực tế có tính ứng dụng cao là bài toán học xấp xỉ hàm Q và hàm ngược Q. 3. CÁC ĐÓNG GÓP CHÍNH Các đóng góp chính của luận án bao gồm: 1. Đề xuất khái niệm “Ngữ nghĩa” của các cây con trong hệ TAG3P. Trong hệ TAG3P trước đây khái niệm ngữ nghĩa chưa được nghiên cứu, đề xuất, chính vì vậy, việc nghiên cứu và đề xuất khái niệm ngữ nghĩa là sự mở rộng của hệ TAG3P. 2. Dựa trên định nghĩa về ngữ nghĩa trong TAG3P, luận án thiết kế và đề xuất toán tử lai ghép, toán tử đột biến dựa trên ngữ nghĩa. Việc thiết kế với các toán tử mới sẽ giúp quá trình tiến hóa được định hướng tốt hơn dựa trên ngữ nghĩa. Kết quả thực nghiệm cho thấy, toán tử di truyền được thiết kế dựa trên ngữ nghĩa thu được kết quả cải tiến so với toán tử thông thường trên TAG3P. 3. Ứng dụng các kết quả nghiên cứu mới của luận án vào bài toán thực tế là học xấp xỉ hàm Q và học xấp xỉ hàm ngược Q, trong đó: - Nghiên cứu đề xuất hàm thích nghi phù hợp với đặc điểm của bài toán học xấp xỉ hàm Q, hàm ngược Q. - Tìm ra được xấp xỉ hàm Q ở dạng tường minh với cấu trúc rất đơn giản và đặc biệt là có độ chính xác rất cao. Điều này rất có ý nghĩa bởi bài toán tìm các dạng xấp xỉ của hàm Q có một vai trò quan trọng trong lĩnh vực viễn thông, nó cũng được các nhà khoa học không ngừng nghiên cứu nhằm tìm ra các xấp xỉ mới tốt hơn, đơn giản hơn. Kết quả này rất quan trọng vì kể từ khi xấp xỉ OPBCS được đưa ra năm 1979 đến nay chưa có một xấp xỉ nào tốt hơn được tìm ra. Hơn thế nữa, xấp xỉ tìm được này lại có dạng hàm mũ nên rất đơn giản trong quá trình tính toán, phù hợp với đặc điểm sử dụng trong phân tích hệ thống viễn thông. - Tìm ra được xấp xỉ hàm ngược Q ở dạng tường minh, hiện chưa có những công bố về dạng tường minh của hàm ngược này. 2 Các kết quả của luận án đã được công bố bao gồm: 02 bài đăng tại các tạp chí có uy tín (trong đó có 01 tạp chí nước ngoài thuộc danh mục ISI), 03 bài báo được đăng tại kỷ yếu hội thảo quốc tế (trong đó có 02 hội nghị quốc tế thuộc danh mục ISI Proceeding). Ngoài ra, một số công trình nghiên cứu thuộc lĩnh vực viễn thông đã trích dẫn và sử dụng các kết quả nghiên cứu này. 4. TỔNG QUAN VỀ CẤU TRÚC CỦA LUẬN ÁN Luận án sẽ được trình bày như sau: Giới thiệu chung: phần này sẽ trình bày mục đích của việc nghiên cứu, các mục tiêu của luận án đặt ra, phương pháp nghiên cứu, các kết quả đóng góp chính của luận án và cấu trúc các chương trong luận án. Chương 1: các nội dung lý thuyết và các nghiên cứu trước đây có liên quan sẽ được trình bày. Chương 2: Chương này sẽ trình bày khái quát về các định nghĩa ngữ nghĩa và các toán tử di truyền dựa trên ngữ nghĩa trong một số nghiên cứu gần đây. Trên cơ sở đó, khái niệm về ngữ nghĩa của cây con trong hệ TAG3P được đề xuất. Chương 3: Dựa trên ngữ nghĩa, các toán tử di truyền mới đã được thiết kế và một số thí nghiệm đã được tiến hành để đánh giá kết quả và so sánh hiệu quả của toán tử di truyền dựa trên ngữ nghĩa so với toán tử di truyền thông thường trên TAG3P và với hệ GP khác. Chương 4: Ứng dụng những kết quả nghiên cứu mới để giải quyết bài toán ứng dụng thực tế là: bài toán học xấp xỉ hàm Q và hàm ngược của Q. Tiếp theo là danh mục các kết quả đã công bố, hướng nghiên cứu tiếp theo, danh mục tài liệu tham khảo. CHƯƠNG 1. TỔNG QUAN Chương này sẽ trình bày tổng quan những nghiên cứu trước đây trong lĩnh vực lập trình gen, lập trình gen định hướng bởi văn phạm và đặc biệt sẽ trình bày chi tiết về hệ lập trình gen định hướng bởi văn phạm nối cây. Trên cơ sở đó, luận án đưa ra một số hướng nghiên cứu mở rộng cũng như khả năng áp dụng vào các bài toán thực tế. 1.1 GIẢI THUẬT TIẾN HÓA Giải thuật tiến hóa (Evolutionary Algorithms – EA) là tập các giải thuật tìm kiếm mô phỏng quá trình tiến hóa. Sự mô phỏng này được thực hiện theo ba mặt. Một là EA sử dụng quần thể gồm tập hợp các cả thể; các cá thể đó cạnh tranh với nhau, dựa trên thuyết chọn lọc tự nhiên của Darwin để tái tạo; và quá trình tiến hóa được thực hiện ngẫu nhiên. EA dựa trên quan niệm "Quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu". Quá trình tiến hoá thể hiện tính tối ưu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước. 3 1.2 GIẢI THUẬT DI TRUYỀN Giải thuật di truyền (GA) nguyên thủy được đề xuất bởi Holland và hiện là giải thuật tiến hóa phổ biến nhất. Nó được nghiên cứu và áp dụng cho nhiều bài toán thực tế. GA nguyên thủy sử dụng chuỗi nhị phân tuyến tính và có độ dài cố định để biểu diễn chuỗi Gen. Từ khi Holland phát minh ra hệ GA đầu tiên, đến nay đã có một số biến thể GA được đề xuất và sử dụng các biểu diễn khác nhau như: sử dụng mã thực, mã gray, chuỗi gen với độ dài thay đổi và tương tự như vậy [1]. 1.3 LẬP TRÌNH GEN Lập trình Gen được định nghĩa như là phương pháp học máy để tạo ra các chương trình thông qua quá trình tiến hóa [4], là một công nghệ tính toán tiến hóa tự động giải quyết bài toán, không đòi hỏi phải biết dạng thức hay cấu trúc của lời giải [5] [6] [7] [8]. GP được kế thừa từ GA và đôi khi được xem như là một nhánh nghiên cứu của GA. GP có thể khái quát là phương thức có hệ thống và độc lập với bài toán để tự động giải quyết bài toán từ những định nghĩa cấp cao. GP dựa trên ý tưởng chính là các chương trình máy tính có khả năng tự tiến hóa để thực hiện một công việc nào đó, được đưa ra bởi Koza vào năm 1992 [9]. Kỹ thuật này cung cấp một nền tảng cho việc tạo ra những chương trình máy tính một cách tự động. Lập trình gen đạt được mục đích này bằng việc phát sinh ra một quần thể các chuơng trình máy tính, sử dụng thuyết tiến hóa của Darwin để chọn ra chương trình tốt nhất để thực hiện công việc. GP khác những thuật toán tiến hóa khác ở phạm vi ứng dụng: những thuật toán tiến hóa khác thường được áp dụng cho các bài toán tìm lời giải tối ưu, trong khi GP được xếp vào nhóm các thuật toán máy học: tìm mô hình phù hợp nhất dựa trên dữ liệu đưa vào. 1.4 LẬP TRÌNH GEN ĐỊNH HƯỚNG BỞI VĂN PHẠM Một hướng khác để giải quyết yêu cầu đóng trong GP là sử dụng văn phạm hình thức để ràng buộc cú pháp đối với chương trình. Ngôn ngữ hình thức được sử dụng rộng rãi trong việc định nghĩa ngôn ngữ của một số lĩnh vực, như trong ngôn ngữ lập trình và ngôn ngữ tự nhiên [36]. Đã có một số nghiên cứu về việc sử dụng ràng buộc dựa trên văn phạm trên GP được gọi là lập trình Gen định hướng bởi văn phạm (GGGP). Sử dụng văn phạm giúp mã hóa miền tri thức về cấu trúc cú pháp của chương trình. Do miền tri thức ràng buộc cấu trúc lời giải, sử dụng văn phạm sẽ giúp kiểm soát được cấu trúc. Trong [9] một số cơ chế học đơn giản sử dụng để mã hóa cấu trúc cú pháp của lời giải. Hơn thế nữa sử dụng văn phạm hình thức sẽ cung cấp cách thức linh hoạt hơn. Ngoài ra, sử dụng văn phạm sẽ dễ điều hướng về cấu trúc cú pháp của chương trình bằng cách thay đổi văn phạm. Do văn phạm nằm ngoài hệ GP chứ không phải là một thành phần của GP, việc điều hướng có thể thay đổi bằng cách thay đổi văn phạm mà không phải triển khai lại hệ thống. Ngoài ra, việc cài đặt 4 điều hướng trong chương trình dẫn đến việc giảm không gian tìm kiếm do đó tăng cơ hội tìm kiếm được lời giải. Cuối cùng, việc sử dụng văn phạm để thiết kế các toán tử tương đồng. 1.4.1 GGGP với biểu diễn dạng cây Những nghiên cứu đầu tiên gần như được đưa ra cùng một lúc bởi ba nhà nghiên cứu. Whigham [43] đề xuất sử dụng hệ CFG với văn phạm phi ngữ cảnh sử dụng để tạo ra quần thể là cây dẫn xuất trong CFG. Schultz trong [44] sử dụng hệ GGGP để học các qui tắc trong hệ chuyên gia. Hệ này tương tự như Whigham, chỉ khác nhau ở thuật toán khởi tạo quần thể [45] [46] [47] [48] [49] [50] đề xuất sử dụng hệ LOGENPRO sử dụng văn phạm mệnh đề nhất định (DCG), một kiểu văn phạm logic trong LISP để tạo ra chương trình. DCG có tính biểu diễn cao hơn CFG, có khả năng tạo ra các ngôn ngữ cảm ngữ cảnh hơn. 1.4.2 GGGP với biểu diễn tuyến tính Cũng như với GP chuẩn, GGGP cũng có những biểu diễn chương trình dưới dạng tuyến tính. Giải pháp chính được sử dụng là ánh xạ giữa kiểu Gen và kiểu hình, trong đó kiểu Gen là chuỗi tuyến tính còn kiểu hình là cây dẫn xuất của văn phạm (G). Trong một số nghiên cứu trước đó [52] [53] [54] [55], kiểu Gen là chuỗi cố định được sử dụng để mã hóa chỉ số của luật dẫn xuất trong văn phạm G. Việc chuyển đổi từ kiểu Gen sang kiểu hình được thực hiện từ trái sang phải và kiểu hình (cây dẫn xuất trong văn phạm G) được hình thành tương ứng. Ở mỗi bước, nếu vẫn còn nhánh chưa kết thúc của kiểu hình được đánh dấu bởi ký tự không kết, một Gen (gồm một số bit) sẽ được đọc và biên dịch như là số nguyên, tương ứng với quy luật trong tập luật P của văn phạm G có nhánh bên trái là A, sẽ được sử dụng để mở rộng cho nhánh của kiểu hình. Nếu kiểu hình đã hoàn thành mà vẫn còn kiểu những Gen chưa sử dụng trong kiểu Gen, nó sẽ bị bỏ qua vì đó là những Gen dư thừa. Trong trường hợp đã sử dụng hết các Gen là kiểu hình vẫn chưa được hình thành đầy đủ thì một số cây dẫn xuất con sẽ được tạo ra ngẫu nhiên để hoàn thành kiểu hình. 1.4.3 Một số vấn đề gặp phải với GGGP Cũng như với GP, hệ thống GGGP cũng gặp phải những vấn đề. Trong hệ thống GGGP dựa trên biểu diễn dạng cây sẽ rất khó khăn để thiết kế các toán tử có thay đổi nhỏ và đóng. Ngoài những ràng buộc bởi cây văn phạm GP, cây dẫn xuất trong GGGP còn bị ràng buộc bởi luật viết lại của văn phạm. Do đó, một thay đổi của chương trình, là cây dẫn xuất của văn phạm, có thể tạo ra một chương trình không hợp lệ. Những thay đổi tạo ra bởi các toán tử có thể dẫn đến việc không kiểm soát được. Còn đối với hệ GGGP biểu diễn tuyến tính, một phần vấn đề được giải quyết liên quan đến việc thiết kế các toán tử thay đổi nhỏ, đóng và các toán tử phỏng sinh học. Tuy nhiên, sự không tuân theo luật nhân quả trong quá trình ánh xạ giữa kiểu gen và kiểu hình, có nghĩa là ảnh hưởng của những thay đổi nhỏ và đóng sẽ không xuất hiện trong không gian của kiểu hình. 5 1.5 VĂN PHẠM NỐI CÂY VÀ LẬP TRÌNH TIẾN HÓA ĐỊNH HƯỚNG BỞI VĂN PHẠM NỐI CÂY (TAG3P) 1.5.1 Văn phạm nối cây (Tree-Adjoining Grammars – TAGs) Văn phạm nối cây [60] đã và đang trở thành loại văn phạm quan trọng trong xử lý ngôn ngữ tự nhiên (Natural Language Processing – NLP). Mục đích của TAG là chỉ ra một cách trực tiếp cách tạo cấu trúc của các ngôn ngữ tự nhiên so với các hệ viết lại trên xâu thuộc các lớp văn phạm Chomsky. Cụ thể là, TAG chỉ ra được quá trình hình thành các câu phức trong ngôn ngữ tự nhiên từ một tập câu đơn giản thông qua việc thêm vào chúng các cấu trúc câu phụ. Trong văn phạm phi ngữ cảnh (Context Free Grammar – CFG) (lớp Chomsky – loại 2), mối quan hệ giữa câu đầu và câu cuối chỉ có thể được phân biệt bằng cách phân tích chi tiết các cây dẫn xuất của chúng. Song, trong biểu diễn TAG, cây dẫn xuất tiếp sau được mở rộng trực tiếp từ cây dẫn xuất trước đó. Nói cách khác, việc tạo ra sự khác nhau giữa các cây dẫn xuất trong biểu diễn TAG đơn giản và dễ dàng hơn nhiều so với biểu diễn CFG. Cấu trúc văn phạm của TAG được hình thành bởi hai tập hợp cây con, cây khởi tạo hay còn gọi là cây α, tương ứng với các thành phần cơ bản của ngôn ngữ và cây bổ trợ hay còn gọi là cây β tương ứng với các nhân tố có thể chèn thêm của ngôn ngữ. Các cây con này còn được gọi là các cây cơ bản. Cũng giống như đối với các văn phạm Chomsky, các nút của cây được gán bằng các ký hiệu kết thúc (terminal symbols) và không kết thúc (non-terminal symbols), trong đó các nút bên trong phải được gán bằng các ký hiệu không kết thúc, các nút lá có thể được gán bằng cả hai loại ký hiệu kết thúc hoặc không kết thúc. Văn phạm TAG là một bộ năm thành phần (Σ, N, I, A, S), trong đó: - Σ: tập hữu hạn các kí hiệu kết thúc. - N: tập hữu hạn các kí hiệu không kết thúc. - S: tập phân biệt các kí hiệu không kết thúc. - I: tập các cây khởi tạo. Trong cây khởi tạo, các nút bên trong phải được gán bằng các ký hiệu không kết thúc, các nút lá có thể được gán bằng cả hai loại ký hiệu kết thúc hoặc không kết thúc. Nút lá có kí hiệu không kết thúc có đánh dấu ↓ thể hiện khả năng thực hiện phép thế tại các nút đó. - A: tập các cây bổ trợ. Trong cây bổ trợ, các nút trong được gán bằng các ký hiệu không kết thúc. Mỗi cây đều có chứa một nút lá trùng tên với nút gốc (mang kí hiệu không kết thúc). Ở nút lá này được đánh dấu bằng kí hiệu * và được gọi là nút chân của cây phụ trợ. Mỗi cây phụ trợ chỉ có một nút chân. Khi xây dựng văn phạm TAG cho một ngôn ngữ tự nhiên, người ta áp dụng một số nguyên lý ngôn ngữ học sau. Thứ nhất, văn phạm LTAG được từ vựng hóa: mỗi cây cơ bản đều có ít nhất một nút lá gắn với một đơn vị từ vựng gọi là từ neo. Thứ hai, mỗi cây khởi tạo của LTAG biểu diễn các thành phần chiếu của một từ neo, hay nói cách khác là các thành phần đối bổ nghĩa cho từ neo. Thứ ba, các cây cơ bản là cực tiểu: cây khởi tạo phải có từ neo là từ trung tâm của một thành phần chính trong câu và chứa tất cả các thành phần đối bắt buộc của từ neo. Tất cả các thành phần phụ của từ neo có thể thêm vào một cách đệ quy bằng cách sử dụng phép kết nối với các cây phụ trợ. 6 Như vậy, khi xây dựng câu, các phép thế tương ứng với việc gắn các đối vào vị từ, phép kết nối tương ứng với việc thêm các thành phần phụ. Vì thế, cây dẫn xuất biểu diễn quan hệ phụ thuộc ngữ nghĩa giữa các từ trong câu. Đây là lý do hầu hết các tiếp cận tới ngữ nghĩa trong văn phạm LTAG sử dụng cây dẫn xuất như là giao diện giữa cú pháp và ngữ nghĩa. LTAG thuộc lớp các văn phạm cảm ngữ cảnh yếu, tức là có khả năng sinh mạnh hơn các văn phạm phi ngữ cảnh, trong khi độ phức tạp thời gian của bộ phân tích cú pháp LTAG vẫn là đa thức. Văn phạm hình thức LTAG rất phù hợp với các ứng dụng ngôn ngữ học. Người ta đã chỉ ra rằng các tính chất của văn phạm LTAG cho phép mô tả các hiện tượng cú pháp một cách tự nhiên. Các cây trung gian sinh ra khi áp dụng các phép thế và kết nối được gọi là các cây phân tích. Cây phân tích đầy đủ là cây phân tích trong đó mọi nút lá đều được gán nhãn kết. Như vậy, việc phân tích cú pháp của một câu là việc xuất phát từ một cây cơ bản có gốc là tiên đề, tìm một cây phân tích đầy đủ có các nút lá tương ứng với dãy các từ trong câu. Đối với văn phạm phi ngữ cảnh, nhìn vào cây phân tích ta biết được ngay các quy tắc viết lại đã thực hiện. Đối với văn phạm TAG, từ cây phân tích ta không thể biết cụ thể các phép viết lại đã được thực hiện để tạo nên cây đó, chính vì vậy, trong hệ hình thức TAG, người ta cần dùng một cấu trúc đặc biệt gọi là cây dẫn xuất để ghi lại các thao tác tạo nên cây phân tích từ các cây cơ bản. Mỗi nút trên cây dẫn xuất là tên của một cây cơ bản, mỗi cung biểu diễn một phép kết nối (nét liền) hoặc một phép thay thế (nét đứt). Ngoài ra, mỗi nút tại đó có áp dụng thao tác viết lại được đánh dấu bằng một địa chỉ Gorn. 1.5.2 Hệ lập trình Gen bởi văn phạm nối cây TAG có giá trị ứng dụng cao đối với xử lý ngôn ngữ tự nhiên, đặc biệt, một điểm mạnh trong cây dẫn xuất của TAG là khi xóa bất kỳ một cây con nào ra khỏi cây dẫn xuất, phần còn lại vẫn là một cây dẫn xuất TAG và là cây hợp lệ. Nói cách khác, cây dẫn xuất trong TAG là cây có thứ phân không cố định. Hệ quả của điều này là khả năng tạo ra các toán tử mới giống như trong các hệ tính toán phỏng tiến hóa sinh học dùng biểu diễn tuyến tính cho nhiễm sắc thể mà vẫn duy trì tính chất ưu việt của biểu diễn dạng hình cây. Hệ lập trình GEN định hướng bởi văn phạm nối cây (TAG3P) [2] [9] [61] [62] là hệ thống sử dụng văn phạm nối cây để định hướng tiến hóa. TAG3P sử dụng văn phạm nối cây cùng với văn phạm phi ngữ cảnh để đặt ra những ràng buộc về cú pháp cũng như những sai lệch khi tìm kiếm của chương trình tiến hóa. Hệ thống TAG3P có tất cả những thuộc tính của các hệ thống GP thông thường dựa trên các biểu diễn dạng hình cây khác. Cấu trúc văn phạm được xác định bằng tập hợp các cây α và cây β. Cấu trúc quần thể là các cây dẫn xuất từ văn phạm này. Việc lượng giá độ tốt của mỗi cá thể được thực hiện bằng cách tạo ra các cây dẫn xuất được tương ứng từ cây dẫn xuất TAG, sau đó đánh giá biểu thức trên cây dẫn được (tương tự như trong GP). Không gian tìm kiếm khi đó được xác định bằng văn phạm, tập hợp tất cả các cây biểu thức 7 GP đều do văn phạm cho trước tạo ra với giới hạn về độ phức tạp của cây này. Tuy nhiên, đặc tính thứ nguyên không xác định của cây giúp kiểm soát một cách dễ dàng theo kích thước của cây, do đó, kích thước của cây được sử dụng để kiểm soát độ phức tạp của cây trong TAG3P thay vì theo chiều cao của cây như trong các hệ GP khác. Cũng giống như trong hệ lập trình GEN chuẩn, TAG3P gồm 5 thành phần là biểu diễn chương trình, khởi tạo quần thể, hàm thích nghi, toán tử di truyền và các tham số. CHƯƠNG 2. NGỮ NGHĨA TRÊN HỆ TAG3P Ngữ nghĩa là một khái niệm khá rộng được nghiên cứu trong nhiều lĩnh vực như ngôn ngữ tự nhiên, tâm lý học và khoa học máy tính. Trong chương này, luận án sẽ trình bày tóm tắt những kết quả nghiên cứu trước đây về ngữ nghĩa áp dụng trong hệ lập trình gen. Đồng thời, trên cơ sở hệ lập trình gen định hướng bởi văn phạm nối cây, luận án sẽ đề xuất ngữ nghĩa của cây con, ngữ nghĩa này sẽ làm cơ sở cho quá trình định hướng tiến hóa mở rộng. 2.1 NGỮ NGHĨA TRONG LẬP TRÌNH TIẾN HÓA Ngữ nghĩa là một khái niệm khá rộng được nghiên cứu trong xử lý ngôn ngữ tự nhiên, khoa học máy tính. Có nhiều định nghĩa khác nhau về ngữ nghĩa tùy theo từng lĩnh vực, nói chung ngữ nghĩa có quan hệ chặt chẽ so với cú pháp. Cú pháp liên quan đến hình dạng, cấu trúc bên ngoài của biểu thức, ngữ nghĩa liên quan sâu hơn phía bên trong. Trong khoa học máy tính, ngữ nghĩa được định nghĩa một cách không chính thức là ý nghĩa của một chương trình hoặc một hàm có cú pháp đúng. Hai chương trình có cùng cú pháp thì sẽ có cùng ngữ nghĩa, nhưng ngược lại thì không chắc là như vậy. Nếu xét về cú pháp thì hai chương trình khác nhau về cú pháp. Nhưng xét về ngữ nghĩa thì hai chương trình là có cùng ngữ nghĩa. Trong GP, ngữ nghĩa nói chung sẽ được sử dụng để cung cấp thêm định hướng cho GP trong quá trình tìm kiếm. Nói chung thông tin thêm vào hoặc là được đưa thêm, hoặc là được lấy ra từ các biểu diễn của GP. Do đó, có nhiều khả năng xảy ra phụ thuộc vào miền bài toán (logic hay giá trị thực), biểu diễn GP (văn phạm hay cây biểu diễn hay đồ thị,..) và đặc tính thuật giải tìm kiếm (đánh giá độ tốt, toán tử di truyền,..). Theo hiểu biết của tác giả, những vấn đề này có ba hướng liên quan đến biểu diễn và trích xuất thông tin ngữ nghĩa và thể chia thành ba nhóm: Sử dụng văn phạm ( [64] [65] [66] [67] [46] [47]), Sử dụng phương pháp hình thức ( [68] [69] [70] [71] [72] [73]), Sử dụng ngữ nghĩa dựa trên biểu diễn cây của GP ( [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84]). Sau đây là tổng quát một số kết quả nghiên cứu có liên quan, đặc biệt, phần sử dụng ngữ nghĩa dựa trên cây biểu diễn GP sẽ được trình bày chi tiết hơn vì có liên quan nhiều đến hệ thống ngữ nghĩa được đề xuất trên TAG3P. 8 2.1.1 Sử dụng văn phạm để biểu diễn ngữ nghĩa Việc sử dụng văn phạm phi ngữ cảnh sẽ khó để tích hợp được ngữ nghĩa vào trong GP. Nhiều nghiên cứu đã được thực hiện theo hướng sử dụng văn phạm thuộc tính, văn phạm logic,… 2.1.2 Sử dụng phương pháp hình thức Phương pháp hình thức là một lớp các kỹ thuật dựa trên toán học cho việc đặc tả, phát triển và đánh giá hệ thống phần mềm và phần cứng [87] 2.1.3 Sử dụng ngữ nghĩa dựa trên biểu diễn của GP Khác với cách tiếp cận dựa trên văn phạm và trên phương pháp hình thức, ngữ nghĩa có thể trực tiếp tính toán, trích xuất từ biểu diễn dạng cây của GP. Ngữ nghĩa có thể trích xuất từ biểu diễn cây sẽ phụ thuộc vào bài toán cần giải quyết. Trong các bài toán logic, ngữ nghĩa có thể tính chính xác theo nhiều cách. Beadle và Johnson [74] tính toán thông tin ngữ nghĩa dựa vào Cây quyết định nhị phân thứ tự [88]. Cây quyết định nhị phân thứ tự là một đồ thị quyết định nhị phân mà thứ tự các nhãn giữa các nút được đảm bảo. Điều đó có nghĩa là nhãn của một nút luôn lớn hơn nhãn của nút con. McPhee và đồng nghiệp đã trích xuất thông tin ngữ nghĩa từ cây biểu thức logic bằng cách đánh số tất cả các khả năng đầu vào của mỗi cá thể [79]. Theo phương pháp này, họ quan tâm đến ngữ nghĩa của hai thành phần trong cây là cây con và ngữ cảnh, trong đó ngữ cảnh là phần còn lại của cây sau khi loại bỏ cây con. Một phương pháp khác sử dụng cách đánh giá độ tốt của cá thể là trong [89]. Theo đó, bằng cách xác định ngữ nghĩa của ngữ cảnh có thể biết được cây con sẽ ra sao nếu việc lai ghép được thực hiện ở vị trí cây con bị loại bỏ. Thông tin này sẽ được sử dụng để tính độ tốt và được gọi là hàm độ tốt tiềm năng [89]. Tuy nhiên, đối với các bài toán hồi qui tuyến tính với các hàm giá trị thực, việc tính toán chính xác ngữ nghĩa là không khả thi, do đó, có một phương pháp là tính toán xấp xỉ, được đề cập trong [90]. Theo đó, ngữ nghĩa của hai cá thể được gọi là tương đương khi thực hiện so sánh chúng trên một tập mẫu ngẫu nhiên các giá trị đầu vào. Hai cá thể được gọi là tương đương nếu lỗi trung bình của chúng trong tập mẫu ngẫu nhiên là nhỏ hơn một giá trị nhỏ tùy ý nào đó. Định nghĩa này sẽ được sử dụng để đơn giản cây trong quá trình tiến hóa. Krawiec và Lichocki đề xuất phương pháp tính ngữ nghĩa của cá thể dựa trên các dữ liệu học [78], khi đó, ngữ nghĩa sẽ được định nghĩa là véc tơ trong đó mỗi thành phần là đầu ra tương ứng với giá trị đầu vào của dữ liệu học. Ngữ nghĩa này định hướng quá trình lai ghép và được gọi là toán tử lai ghép xấp xỉ không gian. 2.2 ĐỊNH NGHĨA NGỮ NGHĨA TRONG TAG3P 2.1.1 Định nghĩa ngữ nghĩa của cây con trong TAG3P Như đã trình bày trong chương 1, TAG3P sử dụng sự biến đổi giữa kiểu Gen (genotype) và kiểu hình (phenotype). Kiểu Gen ở đây là các cây dẫn xuất còn kiểu hình là cây dẫn được. Cây dẫn xuất để ghi lại các thao tác tạo nên cây dẫn được từ các cây cơ bản. Mỗi nút trên cây dẫn xuất là tên của một cây cơ bản, mỗi cung biểu 9 diễn một phép kết nối (nét liền) hoặc một phép thay thế (nét đứt). Ngoài ra, mỗi nút tại đó có áp dụng thao tác viết lại được đánh dấu bằng một địa chỉ Gorn. Với đặc điểm như vậy, trong hệ TAG3P có vấn đề như sau: - Các thao tác thực hiện toán tử di truyền như lai ghép, đột biến,…. được thực hiện và thao tác trên cây dẫn xuất. - Việc tính toán độ tốt của một cá thể lại được tính toán trên cây dẫn được (là cây biểu diễn trong hệ GP thông thường). Chính vì vậy, ngữ nghĩa của một cây con trong TAG3P rất khó có thể áp dụng cách tính toán tương tự trước đây (dựa trên cây biểu thức). Kiểu Gen là biểu diễn dưới dạng cây dẫn xuất, nó cho biết cấu trúc hình thành của cá thể từ các cây cơ bản và các thao tác được thực hiện. Mã con trong mỗi cá thể của TAG3P là cây con. Mọi mã con đều được biểu diễn, được sử dụng để mã hóa kiểu hình. Tuy nhiên, như đã trình bày ở trên, TAG3P sử dụng sự chuyển đổi giữa kiểu Gen (genotype) và kiểu hình (phenotype), và trong ví dụ trên, kiểu hình chính là dạng cây biểu diễn. Khi đó, việc tính toán độ tốt của cá thể sẽ được thực hiện trên cây biểu diễn này. Tuy nhiên, vấn đề đối với hệ TAG3P là, cây con trong cây biểu diễn lại không tương ứng với cây con trong kiểu Gen (cây dẫn xuất). Các thao tác thực hiện toán tử di truyền như lai ghép, đột biến,…. được thực hiện và thao tác trên cây dẫn xuất. Chính vì vậy, việc áp dụng việc tính toán ngữ nghĩa của cây con dựa trên dạng biểu diễn cây biểu thức là không thực hiện được trong TAG3P, mặc dù kiểu hình của cá thể là dạng cây biểu thức. Không giống như GP và GGGP, trong TAG3P, nó có thể đánh giá được sự ảnh hưởng của một cây con đối với độ tốt của cá thể. Nhờ khả năng không cố định về số lượng tham số, nó có thể tạm thời bỏ một cây con ra khỏi cá thể mà vẫn đảm bảo cá thể đó hợp lệ (có thể đánh giá được độ tốt). Do đó có thể đánh giá được mức độ ảnh hưởng của một cây con đối với cá thể bằng cách so sánh độ tốt cá thể đó trong trường hợp có và không có cây con đó. Định nghĩa 2.1: Ngữ nghĩa của một cây con trong TAG3P được xác định là độ đóng góp của cây con đó đối với toàn bộ cây (cá thể). Giá trị ngữ nghĩa cây con được xác định là hiệu của độ tốt cá thể khi có cây con và độ tốt của cá thể khi không có cây con đó. Để tính ngữ nghĩa của cây con (t), theo định nghĩa trên có thể thực hiện như sau: Bước 1: Tính độ tốt của cá thể. Để thực hiện việc này, đầu tiên ta sẽ chuyển đổi thành cây dẫn được trong Glex. Sau đó, quá trình tính toán độ tốt của cá thể được thực hiện trên cây dẫn được. Giả sử giá trị tính được là n. Bước 2: Thực hiện việc ngắt (tạm thời) cây con (t) ra khỏi cá thể. Do đặc tính thứ phân không cố định nên cá thể thu được sau khi loại bỏ cây con (t) vẫn là một cá thể hợp lệ. Khi đó ta lại thực hiện tính toán độ tốt của cá thể sau khi loại bỏ cây con (t). Giả sử giá trị tính được là m. Bước 3: Ngữ nghĩa của cây con (t) sẽ là n – m. 10 Và sẽ xảy ra ba tình huống (ở đây ta coi độ tốt của một cá thể càng nhỏ thì càng tốt) sau: 1. Trường hợp 1: Nếu n – m = 0. Với trường hợp này, độ tốt của cá thể trong trường hợp có và không có cây con là không thay đổi. Điều đó có nghĩa cây con (t) không có đóng góp gì đối với độ tốt của cá thể. 2. Trường hợp 2: nếu n – m < 0 Với trường hợp này, độ tốt của cá thể trong trường hợp không có cây con lớn hơn trong trường hợp có cây con. Với việc ta coi độ tốt của một cá thể càng nhỏ thì càng tốt thì điều đó đồng nghĩa với việc khi không có cây con thì độ tốt của cá thể đó tăng lên, tức là cá thể đó xấu đi. Nghĩa là nếu có cây con đó tồn tại thì cá thể tốt hơn. 3. Trường hợp 3: nếu n – m > 0 Với trường hợp này, độ tốt của cá thể trong trường hợp không có cây con nhỏ hơn trong trường hợp có cây con. Với việc ta coi độ tốt của một cá thể càng nhỏ thì càng tốt thì điều đó đồng nghĩa với việc khi không có cây con thì độ tốt của cá thể đó giảm đi, tức là cá thể đó tốt lên. Nghĩa là nếu có cây con đó tồn tại thì cá thể xấu hơn. 2.1.2 Đặc điểm ngữ nghĩa cây con trong TAG3P Theo định nghĩa ngữ nghĩa trong hệ TAG3P, ngữ nghĩa của cây con là mức độ đóng góp của cây con đó trong tổng thể độ tốt của cá thể. Và như phân tích ở trên ngữ nghĩa của cây con có thể là một trong 3 trường hợp: - Ngữ nghĩa có giá trị âm: tương ứng với trường hợp cây con đó có ảnh hưởng tốt với cá thể. - Ngữ nghĩa có giá trị dương: tương ứng với trường hợp cây con đó có ảnh hưởng xấu với cá thể. - Ngữ nghĩa có giá trị bằng không: tương ứng với trường hợp cây con đó không có ảnh hưởng gì đối với cá thể. Như vậy, ngữ nghĩa được đưa ra ở đây có tính chất cảm ngữ cảnh, nó phản ánh được mối quan hệ của nó (ảnh hưởng xấu, tốt hay không có ảnh hưởng gì) trong ngữ cảnh của một cá thể. Đó là đặc điểm khác biệt của ngữ nghĩa được định nghĩa trong TAG3P so với các ngữ nghĩa trước đây, đặc biệt trong hệ GP sử dụng biểu diễn dạng cây và để giải quyết bài toán thực. CHƯƠNG 3. TOÁN TỬ DI TRUYỀN DỰA TRÊN NGỮ NGHĨA Trong chương này, luận án sẽ trình bày một số toán tử di truyền được thiết kế dựa trên khái niệm ngữ nghĩa của cây con đề xuất ở chương 2. Trên cơ sở đó, một số thí nghiệm đã được tiến hành để đánh giá hiệu quả của toán tử. 3.1 TỔNG QUAN VỀ TOÁN TỬ DI TRUYỀN DỰA TRÊN NGỮ NGHĨA Toán tử lai ghép là toán tử chính trong GP [91]. Trong toán tử lai ghép chuẩn (Standard Crossover - SC), hai cây cha, mẹ được lựa chọn, và hai cây con được lựa chọn từ các cây cha, mẹ đó. Một thủ tục được thực hiện để kiểm tra xem hai cây con đó có hợp lệ để lai ghép không (tính đóng, độ sâu của cây,…). Nếu hợp lệ thì hai 11 cây con sẽ được hoán đổi cho nhau và hai cây mới tạo ra sẽ được đưa vào thế hệ tiếp theo. O’Reilly và Oppacher [93] đưa ra toán tử lai ghép có độ cao tương tự, theo đó, độ cao của hai cây cha, mẹ được lưu lại và một độ cao được lựa chọn ngẫu nhiên, khi đó vị trí lai ghép được lựa chọn tại cây cha, mẹ sẽ bị giới hạn bởi độ cao đó. Poli và Langdon [92] đưa ra toán tử lai ghép tại một điểm và lai ghép đồng nhất, theo đó, hai cây cha mẹ được lựa chọn để thực hiện lai ghép sẽ được căn chỉnh dựa trên hình dạng của nó. Ngữ cảnh cũng được sử dụng như thông tin để lựa chọn vị trí thực hiện lai ghép [94] [95]. Nhóm toán tử lai ghép này khá gần với các toán tử lai ghép dựa trên ngữ nghĩa. Altenberg [94] đưa ra toán tử lai ghép mới, theo đó hai cây cha mẹ được lựa chọn và N toán tử lai ghép ngẫu nhiên được thực hiện để tạo ra 2N cá thể con, sau đó chúng được tính toán độ tốt và hai cá thể con tốt nhất sẽ được đưa vào thế hệ tiếp theo, toán tử này được đặt tên là Soft Brood Selection (SBS). Majeed và Ryan [95] đề xuất toán tử lai ghép Context Aware Crossover (CAC). Krawiec và Lichocki đề xuất phương pháp tính ngữ nghĩa của cá thể dựa trên các dữ liệu học [78], khi đó, ngữ nghĩa sẽ được định nghĩa là véc tơ trong đó mỗi thành phần là đầu ra tương ứng với giá trị đầu vào của dữ liệu học. Ngữ nghĩa này định hướng quá trình lai ghép và được gọi là toán tử lai ghép xấp xỉ không gian (Approximating Geometric Crossover – AGC). Tiếp theo đó, toán tử lai ghép khác được đưa ra bởi Krawiec trong [96], được gọi là lai ghép ngữ nghĩa không gian cục bộ (Locally Geometric Semantic Crossover - LGX). Gần đây, Moraglio và cộng sự đề xuất một hướng nghiên cứu mới để thiết kế toán tử lai ghép dựa trên ngữ nghĩa [97]. Bắt nguồn từ biểu diễn không gian, một toán tử lai ghép dựa trên ngữ nghĩa được đưa ra với tên gọi là lai ghép không gian ngữ nghĩa (Geometric Semantic Crossover - GSC) để tìm kiếm trực tiếp trong không gian ngữ nghĩa của các hàm, chương trình. Đối với các bài toán trên miền giá trị thực, Uy và cộng sự [81] đã đề xuất toán tử lai ghép được gọi là Semantics Aware Crossover (SAC) với mục đích để đẩy mạnh việc đa dạng hóa ngữ nghĩa. Tiếp theo đó, SAC được mở rộng thành Semantic Similarity Based Crossover (SSC) trong [80]. Cuối cùng, phiên bản cải tiến mới nhất là Most Semantically Similar Crossover (MSSC) [98] , bằng cách chọn ngẫu nhiên N cặp cây con và chọn cặp có khoảng cách ngữ nghĩa là nhỏ nhất để tiến hành lai ghép. Bên cạnh toán tử lai ghép cũng có một số toán tử đột biến dựa trên ngữ nghĩa. Chẳng hạn như trong [99], Uy có đề xuất toán tử đột biến Semantic Aware Mutation (SAM) và Semantic Similarity-based Mutation (SSM). 3.2 TOÁN TỬ LAI GHÉP DỰA TRÊN NGỮ NGHĨA TRONG HỆ TAG3P 3.2.1 Toán tử lai ghép dựa trên ngữ nghĩa trong TAG3P Toán tử lai ghép thông thường trước khi tiến hành sẽ thực hiện việc lựa chọn cặp hai cây con ngẫu nhiên từ hai cá thể cha mẹ, trên cơ sở hai cây con này sẽ tiến hành hoán đổi vị trí để tạo thành hai cá thể mới. 12 Với việc tính toán được ngữ nghĩa của mỗi cây con, giá trị ngữ nghĩa sẽ cung cấp thêm thông tin về cây con đó, điều này sẽ giúp ích trong việc lựa chọn các cặp cây con phù hợp để tiến hành lai ghép. Với hệ TAG3P và định nghĩa ngữ nghĩa được đề xuất, giả sử trường hợp sẽ tiến hành chọn ngẫu nhiên N cặp cây con để trên cơ sở đó lựa chọn một cặp tiến hành lai ghép. Trong số các cặp cây con được lựa chọn ra sẽ một số trường hợp xảy ra như sau: 1. Cặp cây con đều có giá trị ngữ nghĩa là âm. Trường hợp này cả hai cây con đó có ảnh hưởng tốt với cá thể cha, mẹ tương ứng. Xét về mặt lý thuyết, nếu một cây con có ảnh hưởng tốt với cá thể thì ta nên giữ lại cây con đó trong cá thể. Nếu tiến hành lựa chọn lai ghép ở vị trí cây con này, đồng nghĩa với việc sẽ loại bỏ cây con đó ra khỏi cá thể. Khi tiến hành chọn ngẫu nhiên N cặp cây con để tiến hành lai ghép, trong số các cặp mà 2 cây con đều có giá trị ngữ nghĩa là âm, một số lựa chọn như sau có thể được thực hiện: - Chọn cặp bất kỳ mà 2 cây con đều có giá trị ngữ nghĩa là âm để thực hiện lai ghép. Trường hợp lựa chọn này được ký hiệu là TAG3P_GG_RD. - Chọn cặp mà 2 cây con đều có giá trị ngữ nghĩa là âm nhưng có tổng giá trị ngữ nghĩa là nhỏ nhất. Do ngữ nghĩa của các cây con có giá trị âm nên tổng giá trị ngữ nghĩa là nhỏ nhất có nghĩa là ở trường hợp này chúng ta chọn cặp cây con có tổng ảnh hưởng nhiều nhất để tiến hành lai ghép. Trường hợp lựa chọn này được ký hiệu là TAG3P_GG_MAX. - Chọn cặp mà 2 cây con đều có giá trị ngữ nghĩa là âm nhưng có tổng giá trị ngữ nghĩa là lớn nhất. Do ngữ nghĩa của các cây con có giá trị âm nên tổng giá trị ngữ nghĩa là lớn nhất có nghĩa là ở trường hợp này chúng ta chọn cặp cây con có tổng ảnh hưởng ít nhất để tiến hành lai ghép. Trường hợp lựa chọn này được ký hiệu là TAG3P_GG_MIN. 2. Cặp cây con đều có giá trị ngữ nghĩa là dương. Trường hợp này cả hai cây con đó có ảnh hưởng xấu với cá thể cha, mẹ tương ứng. Xét về mặt lý thuyết, nếu một cây con có ảnh hưởng xấu với cá thể thì nếu tiến hành lựa chọn lai ghép ở vị trí cây con này, đồng nghĩa với việc sẽ loại bỏ cây con đó ra khỏi cá thể và thay bằng cây con khác. Việc loại bỏ cây con có ảnh hưởng xấu này ra khỏi cá thể trước tiên sẽ giúp cải thiện độ tốt của cá thể. Tuy nhiên, kết quả cuối cùng sẽ phụ thuộc vào cây con mới được thay thế và có thể cây con mới này có ảnh hưởng xấu hoặc ảnh hưởng tốt (tạo ra cá thể mới xấu hoặc tốt hơn cá thể ban đầu). Điều này đảm báo tính ngẫu nhiên của quá trình tiến hóa tự nhiên. Khi tiến hành chọn ngẫu nhiên N cặp cây con để tiến hành lai ghép, trong số các cặp mà 2 cây con đều có giá trị ngữ nghĩa là dương, một số lựa chọn như sau có thể được thực hiện: - Chọn cặp bất kỳ mà 2 cây con đều có giá trị ngữ nghĩa là dương để thực hiện lai ghép. Trường hợp lựa chọn này được ký hiệu là TAG3P_BB_RD. - Chọn cặp mà 2 cây con đều có giá trị ngữ nghĩa là dương nhưng có tổng giá trị ngữ nghĩa là nhỏ nhất. Trong trường hợp này chúng ta chọn cặp cây con 13 có tổng ảnh hưởng ít nhất để tiến hành lai ghép. Trường hợp lựa chọn này được ký hiệu là TAG3P_GG_MIN. - Chọn cặp mà 2 cây con đều có giá trị ngữ nghĩa là dương nhưng có tổng giá trị ngữ nghĩa là lớn nhất. Trong nghĩa là ở trường hợp này chúng ta chọn cặp cây con có tổng ảnh hưởng lớn nhất để tiến hành lai ghép. Trường hợp lựa chọn này được ký hiệu là TAG3P_GG_MAX. 3. Trong hai cây con, một cây con có giá trị ngữ nghĩa là âm, một cây con có giá trị ngữ nghĩa là dương. Trường hợp này sẽ tiến hành lai ghép ở vị trí một cây con có ảnh hưởng tốt với một cây con có ảnh hưởng xấu. Lựa chọn này được ký hiệu là TAG3P_BG_RD. Dựa trên các trường hợp phân tích ở trên, các thuật toán thực hiện toán tử lai ghép dựa trên ngữ nghĩa trong hệ TAG3P được đề xuất như sau: Thuật toán lai ghép dựa trên ngữ nghĩa định lượng: Bước 1: Chọn ngẫu nhiên N cặp cây con được lấy ngẫu nhiên từ hai cây cha, mẹ. Bước 2: Tính toán ngữ nghĩa của từng cây con trong mỗi cặp. Lưu trữ các giá trị ngữ nghĩa này để tiến hành lựa chọn cặp cây con phù hợp để tiến hành lai ghép. Bước 3: Trong N cặp cây con lựa chọn ngẫu nhiên, dựa trên giá trị ngữ nghĩa, thực hiện lai ghép theo một trong bảy trường hợp như đã đề xuất ở trên (mỗi trường hợp lựa chọn sẽ tương ứng với một thuật toán độc lập để đánh giá kết quả): 1. TAG3P_GG_RD. 2. TAG3P_GG_MAX. 3. TAG3P_GG_MIN. 4. TAG3P_BB_RD. 5. TAG3P_BB_MAX. 6. TAG3P_BB_MIN. 7. TAG3P_BG_RD. Bước 4: Trong trường hợp lai ghép được thực hiện thành công thì cá thể mới nhận được sẽ được đưa vào thế hệ tiếp theo. Với thuật toán ở trên, luận án sẽ tiến hành thí nghiệm chi tiết ở phần tiếp theo để qua đó xác định trong 7 lựa chọn cặp cây con dựa trên ngữ nghĩa, lựa chọn nào cho kết quả tốt nhất để từ đó đề xuất phương án lựa chọn lai ghép áp dụng. 3.2.2 Thử nghiệm Để thực hiện đánh giá kết quả của toán tử lai ghép dựa trên ngữ nghĩa, luận án tiến hành thử nghiệm như sau: a. Tập hợp bài toán Để đánh giá hiệu quả của toán tử lai ghép dựa trên ngữ nghĩa so với toán tử lai ghép thông thường và các hệ GP khác, mười bài toán hồi quy ký hiệu với giá trị thực được sử dụng để làm thử nghiệm. Hàm số Tập dữ liệu học F1 = x3 + x2 + x 20 giá trị ngẫu nhiên trong đoạn [-1;1] F2 = x4 + x3 + x2 + x 20 giá trị ngẫu nhiên trong đoạn [-1;1] 14 F3 = x5 + x4 + x3 + x2 + x 20 giá trị ngẫu nhiên trong đoạn [-1;1] F4 = x6 + x5 + x4 + x3 + x2 + x 20 giá trị ngẫu nhiên trong đoạn [-1;1] F5 = sin(x2)cos(x) - 1 20 giá trị ngẫu nhiên trong đoạn [-1;1] F6 = sin(x) + sin(x + x2) 20 giá trị ngẫu nhiên trong đoạn [-1;1] F7 = log (x + 1) + log(x2+ 1) 20 giá trị ngẫu nhiên trong đoạn [0;2] F8=√ 20 giá trị ngẫu nhiên trong đoạn [0;4] 100 cặp giá trị ngẫu nhiên trong F9 = sin(x) + sin(y2) đoạn [-1;1]x[-1;1] 100 cặp giá trị ngẫu nhiên trong F10 = 2sin(x)cos(y) đoạn [-1;1]x[-1;1] Những bài toán này được chia thành ba nhóm: học hàm đa thức; hàm lượng giác, logarit và căn; và hàm hai biến. Hầu hết các hàm này được lấy từ các nghiên cứu của Hoài và cộng sự [61] và Keijzer [73]. Đây là các bài toán được sử dụng rộng rãi trong việc đánh giá hiệu quả các hệ thống GP. b. Cấu hình tham số Thử nghiệm được thiết lập thông số cấu hình để tiến hành học các hàm số ở trên. c. Kết quả Để so sánh kết quả của các toán tử lai ghép dựa trên ngữ nghĩa so với toán tử lai ghép thông thường trên hệ TAG3P, các thử nghiệm học hàm dựa trên cấu hình trong mục a,b ở trên được tiến hành. Với mỗi thử nghiệm ở trên sẽ thực hiện lưu trữ các kết quả sau để so sánh: 1. Tỷ lệ số lần chạy thành công/100 lần chạy thử nghiệm. (điều kiện thành công được mô tả trong bảng 3.2) 2. Trung bình độ tốt của 100 lần chạy thử nghiệm 3. Trung bình của sự thay đổi độ tốt sau khi thực hiện lai ghép. Kết quả thí nghiệm cho thấy: Với các kết quả thu được, có thể rút ra kết luận là tiến hành lai ghép ở hai vị trí cây con có ngữ nghĩa dương (cây con có ảnh hưởng xấu) sẽ thu được kết quả tốt, trong đó, đặc biệt khi vị trí lai ghép là hai cây con có ảnh hưởng xấu mà tổng giá trị ngữ nghĩa của hai cây con đó là lớn nhất thì thu được kết quả tốt hơn cả. 3.2.3 Toán tử lai cặp cây con có tổng giá trị ngữ nghĩa dương lớn nhất Trên cơ sở kết quả thử nghiệm trên, luận án đề xuất thuật toán lai ghép ngữ nghĩa trong TAG3P như sau sẽ được áp dụng: 15 Thuật toán 3.2“Thuật toán lai ghép cặp cây con có tổng ngữ nghĩa dương lớn nhất” Bước 1: Chọn ngẫu nhiên N cặp cây con được lấy ngẫu nhiên từ hai cây cha, mẹ. Bước 2: Tính toán ngữ nghĩa của từng cây con trong mỗi cặp. Lưu trữ các giá trị ngữ nghĩa này để tiến hành lựa chọn cặp cây con phù hợp để tiến hành lai ghép. Bước 3: Chọn cặp cây con đều có giá trị ngữ nghĩa là dương, và có tổng giá trị ngữ nghĩa lớn nhất để tiến hành lai ghép. Bước 4:Trong trường hợp lai ghép được thực hiện thành công thì cá thể mới nhận được sẽ được đưa vào thế hệ tiếp theo. Kết quả thử nghiệm Thuật toán lai ghép cặp cây con có tổng ngữ nghĩa dương lớn nhất như trên cho kết quả tốt, điều này có thể lý giải là bởi ngữ nghĩa của cây con trong TAG3P là có tính quan hệ với toàn bộ cá thể, được đặt vào trong ngữ cảnh của cá thể đó, hay còn gọi là tính cảm ngữ cảnh. Khi tiến hành lai ghép ở những vị trí này nó sẽ loại bỏ cây con có ảnh hưởng xấu ra khỏi cây cha mẹ và thay thế bằng cây con của cá thể bên kia và khả năng sẽ được thay thế vào là cây con có ảnh hưởng tốt, dẫn đến cá thể sẽ tốt hơn, tất nhiên quá trình tiến hóa vẫn đảm bảo tính ngẫu nhiên. Trong các thí nghiệm tiếp theo, luận án sẽ sử dụng Thuật toán lai ghép cặp cây con có tổng ngữ nghĩa dương lớn nhất để tiến hành việc so sánh kết quả với các toán tử khác và các hệ GP khác và ứng dụng trong các bài toán thực tế. 3.2.4 SO SÁNH KẾT QUẢ VỚI CÁC TOÁN TỬ TƯƠNG TỰ Trong phần trên, toán tử lai ghép dựa trên ngữ nghĩa chủ yếu được so sánh về hiệu quả so với toán tử lai ghép thông thường trên hệ TAG3P. Để đánh giá thực sự hiệu quả của toán tử lai ghép dựa trên ngữ nghĩa so với một số hệ GP khác, các toán tử lai ghép tương tự khác, Ngoài việc so sánh với toán tử lai ghép chuẩn, trong các toán tử lai ghép dựa trên ngữ nghĩa, luận án lựa chọn hai toán tử lai ghép là SSC và MSSC để tiến hành so sánh. Hai toán tử lai ghép này được Uy và cộng sự đề xuất trong [80], [98]. Lý do lựa chọn hai toán tử lai ghép này để so sánh là bởi đây là những toán tử lai ghép dựa trên ngữ nghĩa được đánh giá là tốt so với các toán tử tương tự, đồng thời, xét về phương pháp luận thì hai toán tử này tương đồng so với toán tử lai ghép dựa trên ngữ nghĩa đề xuất trong hệ TAG3P. Luận án đã tiến hành thí nghiệm như sau: 1. Tập hợp các bài toán để tiến hành thí nghiệm tương tự như mục 3.1 ở trên. 2. Tiến hành thí nghiệm và so sánh kết quả giữa TAG3P với toán tử lai ghép dựa trên ngữ nghĩa với toán tử lai ghép chuẩn, toán tử lai ghép SSC, MSSC. 3. Toán tử lai ghép dựa trên ngữ nghĩa trong TAG3P cũng được thử nghiệm điều chỉnh tham số N (số cặp cá thể được chọn để tính ngữ nghĩa) khác nhau để đánh giá độ nhạy của tham số này. Với mỗi thí nghiệm ở trên sẽ thực hiện lưu trữ các kết quả sau để so sánh: Tỷ lệ số lần chạy thành công/100 lần chạy; Trung bình độ tốt của 100 lần chạy; Trung bình của sự thay đổi độ tốt sau khi thực hiện lai ghép. Kết quả thử nghiệm thu được: Với các kết quả thu được, khi so sánh với các toán tử 16 tương tự, có thể rút ra kết luận là toán tử lai ghép dựa trên ngữ nghĩa trong TAG3P thu được nhìn chung cho kết quả tốt. Ngoài ra, việc thay đổi tham số N (số cặp các cá thể lấy ngẫu nhiên để tính ngữ nghĩa) cũng có những ảnh hưởng nhất định đến kết quả. Điều này có thể được giải thích là do ngữ nghĩa trong TAG3P có thể có giá trị âm hoặc dương (tức là cây con có thể có ảnh hưởng tốt hoặc xấu), nên khi lấy ngẫu nhiên N cặp cây con để tính ngữ nghĩa, nếu N lớn thì xác xuất thu được các cặp cây con cùng có ảnh hướng xấu sẽ nhiều hơn. Tuy nhiên, điều chỉnh tham số cũng có tác dụng khác nhau với các bài toán học khác nhau và khi điều chỉnh tham số N là 30, 40 thì sự thay đổi không đáng kể, có thể đây là ngưỡng của độ nhạy tham số này. Điều này cần được nghiên cứu và có thêm thí nghiệm để đánh giá độ nhạy của tham số này. 3.3 TOÁN TỬ ĐỘT BIẾN DỰA TRÊN NGỮ NGHĨA TRONG HỆ TAG3P 3.3.1Toán tử đột biến dựa trên ngữ nghĩa trong TAG3P Với việc tính toán được ngữ nghĩa của cây con, giá trị ngữ nghĩa sẽ cung cấp thêm thông tin về cây con đó, điều này sẽ giúp ích trong việc lựa chọn vị trí cây con phù hợp để tiến hành đột biến. Với hệ TAG3P và định nghĩa ngữ nghĩa được đề xuất, giả sử trường hợp sẽ tiến hành chọn ngẫu nhiên N vị trí cây cây con để trên cơ sở đó chọn một cây con để tiến hành đột biến. Khi đó, một số trường hợp có thể xảy ra như sau: 1. Cây con có giá trị ngữ nghĩa là âm. Khi tiến hành chọn ngẫu nhiên N vị trí cây con để tiến hành đột biến, trong số các cây con có giá trị ngữ nghĩa là âm, một số lựa chọn như sau có thể được thực hiện: - Chọn ngẫu nhiên cây con có giá trị ngữ nghĩa là âm bất kỳ để thực hiện đột biến. Trường hợp lựa chọn này được ký hiệu là TAG3P_G_RD. - Chọn cây con có giá trị ngữ nghĩa là âm nhỏ nhất. Mục đích là lựa chọn cây con có ảnh hưởng tốt nhiều nhất để đột biến. Trường hợp lựa chọn này được ký hiệu là TAG3P_G_MAX. - Chọn cây con có giá trị ngữ nghĩa là âm lớn nhất. Mục đích là lựa chọn cây con có ảnh hưởng tốt ít nhất để đột biến. Trường hợp lựa chọn này được ký hiệu là TAG3P_G_MIN. 2. Cây con có giá trị ngữ nghĩa là dương. Khi tiến hành chọn ngẫu nhiên N cây con để tiến hành đột biến, trong số các cây con có giá trị ngữ nghĩa là dương, một số lựa chọn như sau có thể được thực hiện: - Chọn ngẫu nhiên cây con có giá trị ngữ nghĩa dương bất kỳ để thực hiện đột biến. Trường hợp lựa chọn này được ký hiệu là TAG3P_B_RD. - Chọn cây con có giá trị ngữ nghĩa dương nhỏ nhất. Mục đích là lựa chọn cây con có ảnh hưởng xấu ít nhất để đột biến. Trường hợp lựa chọn này được ký hiệu là TAG3P_B_MIN. - Chọn cây con có giá trị ngữ nghĩa dương lớn nhất. Mục đích là lựa chọn cây con có ảnh hưởng xấu nhiều nhất để đột biến. Trường hợp lựa chọn này được ký hiệu là TAG3P_B_MAX. Dựa trên các trường hợp phân tích ở trên, thuật toán thực hiện toán tử đột biến dựa trên ngữ nghĩa trong hệ TAG3P được đề xuất như sau: 17 Thuật toán đột biến dựa trên ngữ nghĩa định lượng: Bước 1: Chọn ngẫu nhiên N cây con trong cá thể. Bước 2: Tính toán ngữ nghĩa của từng cây con đó. Lưu trữ các giá trị ngữ nghĩa này để tiến hành lựa chọn vị trí cây con phù hợp để tiến hành đột biến. Bước 3: Trong N cây con lựa chọn ngẫu nhiên ở trên, dựa trên giá trị ngữ nghĩa, thực hiện đột biến tại vị trí theo một trong 6 trường hợp như đã đề xuất ở trên: 1. TAG3P_G_RD. 2. TAG3P_G_MAX. 3. TAG3P_G_MIN. 4. TAG3P_B_RD. 5. TAG3P_B_MAX. 6. TAG3P_B_MIN. Bước 4:Trong trường hợp đột biến được thực hiện thành công thì cá thể mới nhận được sẽ được đưa vào thế hệ tiếp theo. Với thuật toán ở trên, luận án sẽ tiến hành thí nghiệm chi tiết ở phần tiếp theo để qua đó xác định trong 6 lựa chọn cây con dựa trên ngữ nghĩa, lựa chọn nào cho kết quả tốt nhất để từ đó đề xuất phương án lựa chọn vị trí đột biến áp dụng trong thuật toán này. 3.3.2 Thử nghiệm Với các kết quả thu được, có thể rút ra kết quả là khi tiến hành đột biến ở vị trí cây con có ngữ nghĩa dương (cây con có ảnh hưởng xấu) sẽ thu được kết quả cải tiến. Mặc dù những kết quả trên cho thấy có sự cải tiến khi áp dụng ngữ nghĩa trong toán tử đột biến. Tuy nhiên, trong lập trình Gen, toán tử đột biến thường chỉ được sử dụng với xác xuất nhỏ (khoảng 0.1), do đó, ảnh hưởng của toán tử này là không nhiều. Các nghiên cứu và thử nghiệm sau đây sẽ chủ yếu sử dụng toán tử lai ghép dựa trên ngữ nghĩa. CHƯƠNG 4. ỨNG DỤNG THỰC TẾ Với các nghiên cứu đã được trình bày và thí nghiệm trong các chương trước đây, trong chương này, luận án tiến hành áp dụng để giải quyết các bài toán thực tế, cụ thể là ứng dụng trong bài toán học hàm Q và hàm ngược Q. 4.1 BÀI TOÁN HỌC XẤP XỈ HÀM Q VÀ HÀM NGƯỢC Q 4.1.1 Hàm Q Trong lĩnh vực viễn thông, các nhà nghiên cứu giả thuyết rằng hệ thống nhiễu có dạng biến Gaussian ngẫu nhiên. Việc tính toán xác suất lỗi trong hệ thống thông tin số thường gắn liền với việc tính toán dựa trên hàm lỗi Q(x), được định nghĩa như sau: (5.1) 18 Dạng hàm Q này có hai vấn đề. Trước tiên, xét về góc độ tính toán, nó đòi hỏi sự chặn trên của giới hạn vô cực khi sử dụng tích phân số hoặc kỹ thuật tính toán. Vấn đề thứ hai gặp phải là tham số của hàm là giá trị dưới của hàm tích phân, do đó, nó sẽ gặp khó khăn về mặt giải tích khi tham số này phụ thuộc vào một biến số ngẫu nhiên đòi hỏi trung bình thống kê trên phân bố xác suất. Trong những trường hợp như vậy, chúng ta cần có dạng hàm Q(x) với tham số đầu vào không những không phải là giới hạn trên hay dưới của hàm tích phân, mà còn xuất hiện trong hàm tích phân như là tham số đầu vào của các hàm cơ bản. Dạng thức mong muốn vẫn là dạng mà giới hạn của tham số độc lập là hữu hạn, đồng thời, hàm tích phân vẫn duy trì cấu trúc tự nhiên của nó. Các biểu diễn tường minh của hàm Q rất cần cho các bài toán liên quan đến hiệu năng của hệ thống viễn thông, đặc biệt là lỗi trung bình, bit và xác xuất khối lỗi và hàm mũ số nguyên với biến ngẫu nhiên thu được trong môi trường Fading [98] [99]. Tuy nhiên, hàm Q chỉ duy nhất được định nghĩa dưới dạng tích phân suy rộng, điều này sẽ gây nhiều khó khăn cho những phân tích sau này đối với với các hệ thống viễn thông [100] [101] [102] [103] [104]. Do đó, rất cần thiết phải tìm ra các biểu diễn tường minh (dạng giải tích) của hàm Q. Mục đích cơ bản của việc xấp xỉ hàm Q là nhằm đưa ra dạng đơn giản và tường minh của hàm Q, tiện lợi trong việc phân tích toán học của hiệu năng hệ thống viễn thông . Tuy nhiên, đến thời điểm này, chưa có giải pháp chính xác tuyệt đối cho dạng tường minh của hàm Q, và do đó, các hàm xấp xỉ là lựa chọn duy nhất. Mặc dù có nhiều hàm xấp xỉ dạng tường minh của hàm Q đã được đề xuất bởi các chuyên gia (một số hàm xấp xỉ phổ biến sẽ được trình bày trong phần tiếp theo), nhưng do tính chất quan trọng và phổ biến của hàm Q trong lĩnh vực viễn thông, việc tìm kiếm các hàm xấp xỉ tốt hơn, có dạng giải tích và có nhiều đặc điểm quan trọng (chẳng hạn như sự đơn giản, tính khả tích,…) vẫn tiếp tục được thực hiện. 4.1.2 Một số dạng xấp xỉ do chuyên gia đề xuất Đến thời điểm này, có một số dạng xấp xỉ được đề xuất bởi các chuyên gia (các nhà toán học) trong lĩnh vực viễn thông về các xấp xỉ hàm Q dạng tường minh. Trong [102] đưa ra một tập các xấp xỉ của hàm lỗi bù, liên quan đến hàm Q . Xấp xỉ hàm Q trong [ [102], eqn. (9)] được định nghĩa như sau: (4.2) Trong [103] sử dụng xấp xỉ PBCS với hàm xấp xỉ trong [ [102], eqn. (13)] (4.3) Với a = 0.339, b = 5.510, sẽ được ký hiệu là xấp xỉ OPBCS. Trong [104], một dạng xấp xỉ đơn giản và hữu ích khác được đưa ra. Tuy nhiên, những xấp xỉ này có sai số lớn với tham số đầu vào nhỏ, chính vì vậy nó ít phù hợp với kênh fading trên trung bình. Hàm xấp xỉ của Q trong [104] là: 19 (4.4) trong bài báo này được ký hiệu là xấp xỉ CDS. Trong [105], các tác giả đã đề xuất dạng thức đơn giản khác của xấp xỉ hàm Q với sai số nhỏ trên toàn bộ dải giá trị đầu vào. Để thuận tiện, hàm xấp xỉ Q được đưa ra trong [105] như sau: (4.5) Trong đó, giá trị tối ưu của biến số A và B là A = 1.98 và B =1.135, và mối quan hệ là: (4.6) được áp dụng trong [ [105], eqn. (6)], trong đó erfc(.) là hàm lỗi bù. Độ chính xác có thể được điều chỉnh bằng cách thay đổi các giá trị khác nhau của A và B. Xấp xỉ này được ký hiệu là xấp xỉ GKAL. Tuy nhiên, những hạn chế của xấp xỉ dạng tự do này là nó có thể rất chính xác nhưng khó áp dụng trong thực tế bởi sự phức tạp của dạng hàm xấp xỉ. Do đó, những dạng xấp xỉ, mặc dù có độ chính xác thấp hơn nhưng có dạng đơn giản thì vẫn hữu ích trong thực tế. Benitez và Casadevall trong [106] đã đề xuất dạng xấp xỉ (được gọi là xấp xỉ dạng hàm mũ) với dạng tương tự với hàm Gaussian, gọi là eP(x), trong đó P(x) là đa thức bậc 2, P(x) = ax2 +bx+c. Với dạng xấp xỉ này, trong khoảng [0;7], họ đã tìm được các giá trị tối ưu của tham số a, b và c tương ứng là -0.4698, 0.5026, và -0.8444. Dạng xấp xỉ này ít chính xác hơn so với OPBCS, nhưng khả năng dễ tính toán làm nó trở nên hữu ích trong bài toán phân tích hệ thống viễn thông. 4.1.3 Hàm ngược Q Bên cạnh hàm Q, hàm ngược Q cũng có ý nghĩa rất quan trọng, nó giúp cho việc tìm kiếm các giá trị của tỷ số tín hiệu trên nhiễu trong khoảng ngưỡng xác xuất lỗi nhất định hoặc trong hệ thống sóng thông minh (là một hệ thống vô tuyến sử dụng công nghệ cho phép hệ thống có được thông tin của môi trường hoạt động và địa lý của hệ thống, các chính sách được thiết lập và trạng thái bên trong của hệ thống; để điều chỉnh các thông số hoạt động và các giao thức của hệ thống một cách linh hoạt và chủ động theo thông tin có được của hệ thống để đạt được các mục tiêu được định nghĩa trước). Tham số đầu vào của hàm ngược Q sẽ là xác suất lỗi, nằm trong khoảng giá trị -6 10 đến 10-1. Do vậy, bài toán đặt ra là tìm dạng giải tích của hàm ngược Q dựa trên tập dữ liệu huấn luyện có được từ hàm Q (đảo vị trí giá trị đầu vào, đầu ra). Hiện nay, chưa có công bố nào về dạng giải tích của hàm ngược Q. Việc tính toán giá trị của hàm ngược chủ yếu được thực hiện qua việc sử dụng các hàm mà không biết được cụ thể dạng giải tích của hàm đó. 20