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, bao gồm: những lý thuyết và các nghiên cứu có liên quan 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 là hệ lập trình Gen định hướng bởi văn phạm nối cây – TAG3P. Hệ TAG3P sẽ được sử dụng là nền tảng cho các hướng nghiên cứu của luận án. 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.
Các đặc điểm của ngữ nghĩa trong hệ TAG3P cũng được phân tích trong chương này. 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.
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 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 [3]. 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ể; hai là 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; ba là 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. Năm 1975, giải thuật Gen do John Holland phát minh và được phát triển bởi ông cùng với các đồng nghiệp. Đến năm 1992, Koza đã dùng GA để xây dựng các chương trình giải quyết một số bài toán mà kích thước lời giải không được xác định trước và gọi phương pháp này là "Lập trình Gen". Mặc dù vậy, thuật toán của các EA đều rất giống nhau và được thể hiện như hình vẽ sau: 6 Hình vẽ 1.
Sơ đồ khối của thuật giải EA 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à là giải thuật tiến hóa khá phổ biến và được sử dụng rộng rãi. Đồng thời, nó được nghiên cứu và áp dụng cho nhiều bài toán thực tế. Hệ GA nguyên thủy có 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. Hình vẽ sau đây là ví dụ một chuỗi Gen của hệ giải thuật di truyền: Hình vẽ 1.
Biểu diễn cá thể trong GA 7 Từ khi Holland [4] 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.3 Các toán tử cơ bản trong GA chuẩn Điều quan trọng cần lưu ý ở đây là tất cả các biểu diễn trên đều sử dụng biểu diễn chuỗi Gen dạng tuyến tính. Tính tuyến tính này tạo thuận lợi cho việc thiết kế các toán tử di truyền khác nhau. Với ba toán tử ban đầu, ngày nay nhiều 8 toán tử di truyền mới và phỏng sinh học đã được đưa ra [4] [5] [6]. Hơn nữa, sẽ không khó khăn đối với GA khi sử dụng biểu diễn chuỗi Gen tuyến tính để thiết kế ra các toán tử mà tạo ra các thay đổi nhỏ khi áp dụng.
Nói cách khác, nếu có một cấu trúc đồ thị trong chuỗi Gen biểu diễn tuyến tính, nó dễ dàng thiết kế toán tử di truyền để duy trì cấu trúc này. Ví dụ như trong GA sử dụng biểu diễn nhị phân tuyến tính, nếu chúng ta sử dụng khoảng cách Hamming để định nghĩa cấu trúc lân cận trong không gian biểu diễn Gen của GA, toán tử đột biết sẽ làm thay đổi nhỏ về khoảng cách Hamming.3 LẬP TRÌNH GEN Lập trình Gen (GP) đượ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 [7], 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 [8] [2] [9] [10]. 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 [1]. 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 chươ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 học máy để tìm mô hình phù hợp nhất dựa trên dữ liệu đưa vào. Sự khác biệt giữa GA và GP cơ bản nằm ở mục đích của nó, trong khi GA chủ yếu sử dụng cho bài toán tối ưu thì GP lại được sử dụng cho việc học. GA được sử dụng để thực hiện việc tối ưu hóa một hàm dựa trên định nghĩa của hàm 9 đó, trong khi GP được sử dụng để học một hàm dựa trên tập dữ liệu học. Đây là điểm khác biệt nhất giữa GA và GP.
Ngoài ra, còn một điểm phân biệt khác giữa GA và GP là GP thường sử dụng biểu diễn chuỗi Gen linh hoạt với kích cỡ và cấu trúc thay đổi. Điều này càng cho thấy rõ là GA phù hợp với tối ưu hóa tham số khi mà cấu trúc đã được biết trước, trong khi GP phù hợp với bài toán học và tìm kiếm về cả nội dung cùng cấu trúc của lời giải và GP đã thành công trong việc giải quyết nhiều bài toán thực tế [7].1 Lập trình Gen chuẩn có cấu trúc cây Mặc dù đã có số lượng các nghiên cứu gần với GP, nhưng trong lĩnh vực GP lần đầu tiên được đưa ra bởi Koza trong [1], là tài liệu đầu tiên trên thế giới nói về khả năng của GP và đặt nền móng cho lĩnh vực nghiên cứu này. Trong tài liệu này, Koza đã đưa ra hệ thống GP dựa trên cơ chế chọn lọc tự nhiên của Darwin, trong tài liệu này sẽ được gọi là hệ GP chuẩn. Quá trình tiến hóa của GP bắt đầu với việc tạo ra ngẫu nhiên quần thể gồm các cá thể (chương trình).
Ở mỗi thế hệ, độ tốt của mỗi cá thể chương trình được đánh giá trên cơ sở mức độ tốt của chương trình trong việc giải quyết bài toán đặt ra. Do đó, các cá thể sẽ được lựa chọn thông qua các toán tử di truyền (lai ghép, đột biến,…) để tạo ra các cá thể con trong thế hệ tiếp theo. Quá trình này lặp đi lặp lại cho đến khi lời giải được tìm ra hoặc khi gặp một số điều kiện dừng nào đó [11]. GP phát sinh ra những chương trình máy tính để giải quyết bài toán bằng việc thực hiện các bước sau: - Tạo quần thể ban đầu bằng việc kết hợp ngẫu nhiên các phép tính và các ký hiệu kết của bài toán.
- Lặp lại các bước sau cho đến khi đạt điều kiện dừng: o Thực thi từng chương trình trong quần thể và gán cho nó một giá trị thích nghi dựa vào hàm tính giá trị thích nghi. o Tạo ra quần thể các chương trình mới bằng việc áp dụng các thao tác sau: Tái tạo: Sao chép chương trình được chọn vào quần thể mới. 10 Lai ghép: Tạo ra hai chương trình mới từ hai chương trình có sẵn bằng việc hoán vị một phần chương trình ban đầu tại một nút được chọn ngẫu nhiên trong từng chương trình. Đột biến: Tạo ra một chương trình mới từ một chương trình có sẵn bằng cách thay thế một phần chương trình được chọn ngẫu nhiên.
- Chương trình được đánh giá là tốt nhất sau khi thực hiện sẽ là kết quả của thuật toán. Đây chính là lời giải của bài toán. Hệ lập trình GEN chuẩn sẽ gồm 5 thành phần: 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ố. Cụ thể như sau: a.
Biểu diễn chương trình Chương trình trong GP được biểu diễn dưới dạng cây, trong đó mỗi nút được gán nhãn là một ký hiệu thuộc tập hàm (F) hay tập ký hiệu kết thúc (T) (trong trường hợp biểu thức tính toán, đó là các toán hạng) Hình vẽ 1. Biểu diễn chương trình GP b. Khởi tạo quần thể Để tạo một cấu trúc cây, GP lựa chọn ngẫu nhiên một phép tính hay một ký hiệu kết từ tập các phép tính và tập các ký hiệu kết thúc của bài toán. Tuy nhiên, việc lựa chọn cũng phải dựa vào tập các tham số điều khiển và phương pháp để phát sinh một cá thể.
Có các phương pháp khởi tạo quần thể sau: Full: Phương pháp này tạo nên những cây đầy đủ, là những cây có tất cả các ký hiệu kết ở mức lớn nhất của cây. 11 Grow: Lựa chọn ngẫu nhiên các phép tính và các ký hiệu kết cho nút gốc. Nếu nút gốc là một ký hiệu kết, một ký hiệu kết ngẫu nhiên sẽ được chọn. Nếu nút gốc là một phép tính, một phép tính ngẫu nhiên sẽ được chọn, và nút này sẽ có số lượng nhánh con bằng với số lượng đối số của phép tính.
