Trong trí tuệ nhân tạo, lập trình di truyền (genetic programming, GP) là một kỹ thuật tiến hóa các chương trình mà ban đầu chưa thích nghi (thường là chương trình ngẫu nhiên) cho đến khi thích nghi được với một nhiệm vụ cụ thể, bằng cách áp dụng các quá trình tương tự di truyền tự nhiên lên quần thể chương trình. Về cơ bản, nó là một kỹ thuật tìm kiếm heuristic thường được mô tả là "leo đồi", tức là tìm kiếm một chương trình tối ưu hoặc ít nhất là phù hợp trong không gian chứa tất cả chương trình.
Các quá trình thực hiện bao gồm: chọn lọc các chương trình tốt nhất để sinh sản (trao đổi chéo) và đột biến dựa trên một thang đo độ thích nghi được định nghĩa trước, thường là trình độ thực hiện đối với nhiệm vụ mong muốn. Quá trình trao đổi chéo bao gồm việc hoán đổi các bộ phận ngẫu nhiên của các cặp được chọn (cặp bố mẹ) để tạo ra các thế hệ con mới và khác biệt trở thành một phần của thế hệ chương trình mới. Đột biến là sự thay thế một bộ phận ngẫu nhiên của chương trình bằng một bộ phận ngẫu nhiên khác. Một số chương trình không được chọn để tái tạo được sao chép từ thế hệ hiện tại sang thế hệ mới. Sau đó, quá trình chọn lọc và các quá trình khác được áp dụng đệ quy cho thế hệ chương trình mới.
Thông thường, các cá thể của mỗi thế hệ mới trên trung bình thường tốt hơn các cá thể của thế hệ trước đó và chương trình tốt nhất thế hệ cũng thường tốt hơn các chương trình tốt nhất thế hệ của các thế hệ trước. Vòng lặp đệ quy được kết thúc khi xuất hiện cá thể chương trình nào đó đạt đến mức độ thành thạo hoặc độ thích nghi được định trước.
Mỗi lần chạy thuật toán có thể và thường xuyên xảy ra sự hội tụ sớm đến điểm cực đại cục bộ nào đó mà không phải là điểm tối ưu toàn cục hoặc thậm chí không phải là nghiệm tốt. Để có được một kết quả rất tốt thường đòi hỏi rất nhiều lần chạy (từ hàng chục tới hàng trăm lần). Ngoài ra, có thể phải tăng kích thước quần thể ban đầu và sự biến đổi của các cá thể để tránh nhiễm gen xấu.
Lịch sử
Đề xuất tiến hóa các chương trình đầu tiên trong lịch sử có lẽ là của Alan Turing vào năm 1950. Phải tới 25 năm sau, sự xuất bản cuốn sách "Sự thích nghi trong các hệ thống tự nhiên và nhân tạo" của John Holland mới đặt ra những nền móng lý thuyết và thực nghiệm của ngành khoa học này. Năm 1981, Richard Forsyth đã chứng minh sự tiến hóa thành công của các chương trình nhỏ, được biểu diễn dưới dạng cây, để thực hiện phân loại bằng chứng hiện trường vụ án cho Bộ Nội vụ Vương quốc Anh.
Mặc dù ý tưởng về các chương trình tự tiến hóa, ban đầu được viết bằng ngôn ngữ máy tính Lisp, đã nảy ra giữa các sinh viên của John Holland, phải đến khi họ tổ chức hội nghị Giải thuật di truyền (GA) đầu tiên ở Pittsburgh, Nichael Cramer mới công bố các chương trình tiến hóa trong hai ngôn ngữ được thiết kế đặc biệt, bao gồm phát biểu đầu tiên của lập trình di truyền "dựa trên cây" hiện đại (nghĩa là các ngôn ngữ thủ tục được tổ chức theo cấu trúc cây và được vận hành bởi các toán tử GA được định nghĩa phù hợp). Năm 1988, John Koza (cũng là một nghiên cứu sinh của John Holland) đã được cấp bằng sáng chế cho phát minh GA cho sự tiến hóa chương trình. Tiếp theo là công bố trong Hội nghị chung quốc tế về trí tuệ nhân tạo IJCAI-89.
Koza tiếp nối điều này với 205 ấn phẩm về "Lập trình di truyền" (GP), tên được đặt ra bởi David Goldberg, cũng là một nghiên cứu sinh của John Holland. Tuy nhiên, chính loạt 4 cuốn sách của Koza, bắt đầu từ năm 1992 với các video đi kèm, mới thực sự thành lập GP. Sau đó, đã có sự tăng lên đáng kể về số lượng xuất bản với thư mục Lập trình di truyền, vượt quá ngưỡng 10,000 mục. Năm 2010, Koza liệt kê 77 kết quả trong đó lập trình di truyền có khả năng cạnh tranh với con người.
Năm 1996, Koza bắt đầu hội nghị Lập trình di truyền hàng năm, sau đó là hội nghị EuroGP hàng năm vào năm 1998, và cuốn sách đầu tiên trong loạt bài GP do Koza biên tập. Năm 1998 cũng chứng kiến sách giáo khoa GP đầu tiên. GP tiếp tục phát triển mạnh mẽ, dẫn đến việc xuất bản tạp chí GP chuyên khoa đầu tiên và ba năm sau (2003) Hội thảo thường niên về lý thuyết và thực hành lập trình di truyền (GPTP) được thành lập bởi Rick Riolo. Các bài báo về Lập trình di truyền tiếp tục được xuất bản tại nhiều hội nghị và tạp chí liên quan. Ngày nay có mười chín cuốn sách GP trong đó có một số cuốn dành cho học sinh.
Công trình nền tảng trong GP
Những công trình đầu tiên tạo tiền đề cho các chủ đề nghiên cứu lập trình di truyền và ứng dụng hiện nay rất đa dạng, bao gồm tổng hợp và sửa chữa phần mềm, mô hình dự đoán, khai thác dữ liệu, mô hình tài chính, cảm biến mềm, thiết kế, và xử lý hình ảnh. Các ứng dụng trong một số lĩnh vực, chẳng hạn như thiết kế, thường sử dụng các biểu diễn trung gian, chẳng hạn như mã hóa tế bào của Fred Gruau. Sự tiếp nhận công nghiệp đã trở nên đáng kể trong một số lĩnh vực bao gồm tài chính, công nghiệp hóa chất, tin sinh học và công nghiệp thép.
Phương pháp
Biểu diễn chương trình
Theo truyền thống, các chương trình tiến hóa bằng GP được biểu diễn trong bộ nhớ dưới dạng cấu trúc cây. Cấu trúc cây có thể được định lượng dễ dàng một cách đệ quy. Mọi nút cây đều có một toán tử hàm và mọi nút đầu cuối đều có một toán hạng, làm cho việc tiến hóa và định lượng các biểu thức toán học trở nên dễ dàng. Vì vậy, theo truyền thống GP ủng hộ việc sử dụng các ngôn ngữ lập trình có cấu trúc cây một cách tự nhiên (ví dụ: Lisp, các ngôn ngữ lập trình hàm khác cũng phù hợp).
Các biểu diễn không phải cây đã được đề xuất và thực hiện thành công, chẳng hạn như lập trình di truyền tuyến tính phù hợp với các ngôn ngữ mệnh lệnh vốn truyền thống hơn [ví dụ, xem Banzhaf et al. (1998)]. Phần mềm GP thương mại Discipulus sử dụng mã máy nhị phân đệ quy tự động ("AIM") để đạt được hiệu suất tốt hơn. µGP sử dụng đa đồ thị có hướng để tạo ra các chương trình khai thác triệt để cú pháp của một hợp ngữ nhất định. Các biểu diễn chương trình khác mà các công trình nghiên cứu và phát triển quan trọng đã thực hiện bao gồm các chương trình cho máy ảo dựa trên ngăn xếp, và chuỗi các số nguyên được ánh xạ tới các ngôn ngữ lập trình tùy ý thông qua ngữ pháp.Lập trình di truyền Descartes là một dạng khác của GP sử dụng biểu diễn đồ thị thay vì biểu diễn dựa trên cây thông thường để mã hóa các chương trình máy tính.
Hầu hết các biểu diễn chứa phần mã vô hiệu về mặt cấu trúc (intron). Các gen không mã hóa như vậy có vẻ vô dụng vì chúng không ảnh hưởng đến hoạt động của bất kỳ cá thể nào. Tuy vậy, chúng thay đổi xác suất tạo ra các con khác nhau dưới các toán tử biến dị, và do đó làm thay đổi các thuộc tính biến dị của cá thể. Các thí nghiệm dường như cho thấy sự hội tụ nhanh hơn khi sử dụng các biểu diễn chương trình cho phép các gen không mã hóa so với các biểu diễn chương trình không có bất kỳ gen không mã hóa nào.
Chọn lọc
Chọn lọc là một quá trình theo đó những cá nhân nhất định được chọn từ thế hệ hiện tại sẽ đóng vai trò là cha mẹ cho thế hệ tiếp theo. Các cá nhân được chọn theo xác suất để những cá nhân có thành tích tốt hơn có cơ hội được chọn cao hơn. Phương pháp chọn lọc phổ biến nhất được sử dụng trong GP là chọn lọc giải đấu, mặc dù các phương pháp khác như chọn lọc thích nghi tỉ lệ, chọn lọc lexicase, và các phương pháp khác đã được chứng minh là hoạt động tốt hơn đối với nhiều vấn đề về GP.
Chọn lọc tinh hoa, hay gieo mầm cho thế hệ tiếp theo với cá thể tốt nhất (hoặc n cá thể tốt nhất) từ thế hệ hiện tại, là một kỹ thuật đôi khi được sử dụng để tránh thoái triển.
Trao đổi chéo
Trong Lập trình di truyền, hai cá thể phù hợp được chọn từ quần thể để làm bố mẹ cho một hoặc hai con. Trong lập trình di truyền cây, những bậc cha mẹ này được biểu diễn dưới dạng cây treo ngược, với các nút gốc ở trên cùng. Trong trao đổi chéo cây con, ở mỗi cá thể cha mẹ, một cây con (subtree) được chọn ngẫu nhiên. (Được đánh dấu bằng màu vàng trong hoạt hình.) Bên trong cá thể cha mẹ hiến gốc (trong hoạt hình bên trái), cây con đã chọn sẽ bị xóa và được thay thế bằng một bản sao của cây con được chọn ngẫu nhiên từ cá thể cha mẹ còn lại, để tạo ra một cá thể con mới (child tree).
Đôi khi trao đổi chéo hai con được sử dụng, trong trường hợp đó, cây con đã bị xóa (trong hoạt hình bên trái) không chỉ bị xóa mà được sao chép vào bản sao của cá thể cha mẹ thứ hai (ở đây bên phải) thay thế (trong bản sao) cây con đã được chọn ngẫu nhiên trước đó. Do đó, kiểu trao đổi chéo cây con này lấy hai cá thể thích nghi và tạo ra hai cá thể con.
Đột biến
Có nhiều dạng đột biến trong lập trình di truyền. Chúng đều xuất phát từ một cá thể cha mẹ thích nghi và đúng về mặt cú pháp và nhắm đến mục tiêu tạo ra một cá thể con ngẫu nhiên đúng về mặt cú pháp. Trong hoạt ảnh, một cây con được chọn ngẫu nhiên (được đánh dấu bằng màu vàng). Nó bị loại bỏ và thay thế bằng một cây con được tạo ngẫu nhiên.
Các phép đột biến khác chọn một lá (nút bên ngoài) của cây và thay thế nó bằng một lá được chọn ngẫu nhiên. Một phép đột biến khác nữa là chọn ngẫu nhiên một hàm (nút bên trong) và thay thế nó bằng một hàm khác có cùng arity (số đối số). Phép đột biến dịch lên chọn ngẫu nhiên một cây con và thay thế nó bằng một cây con bên trong chính nó. Do đó đột biến dịch lên bảo đảm con có kích thước nhỏ hơn. Phép thay thế lá và thay thế hàm cùng số đối số đảm bảo con có cùng kích thước với cha mẹ. Trong khi đó, đột biến cây con (trong hoạt hình) có thể, tùy thuộc vào tập hợp các hàm và đầu cuối, có xu hướng làm tăng hoặc giảm kích thước cây. Các đột biến dựa trên cây con khác cố gắng kiểm soát cẩn thận kích thước của cây con thay thế và do đó kích thước của cá thể con
Tương tự, có nhiều dạng đột biến lập trình di truyền tuyến tính, mỗi dạng đều cố gắng đảm bảo cá thể con bị đột biến vẫn đúng về mặt cú pháp.
Các ứng dụng
GP đã được sử dụng thành công như một công cụ lập trình tự động, một công cụ học máy và một công cụ giải quyết vấn đề tự động. GP đặc biệt hữu ích trong các lĩnh vực mà lời giải chính xác không được biết trước hoặc một lời giải gần đúng có thể chấp nhận được (có thể vì việc tìm ra lời giải chính xác là rất khó khăn). Một số ứng dụng của GP là khớp đường cong, mô hình hóa dữ liệu, hồi quy ký hiệu, chọn lọc đặc trưng, phân loại, v.v. John R. Koza đề cập đến 76 trường hợp mà Lập trình di truyền có thể tạo ra kết quả cạnh tranh với kết quả do con người tạo ra (được gọi là kết quả cạnh tranh với con người). Kể từ năm 2004, Hội nghị Tính toán di truyền và tiến hóa (GECCO) hàng năm tổ chức cuộc thi Giải thưởng cạnh tranh với con người (còn gọi là Humies), nơi các giải thưởng tiền mặt được trao cho các kết quả cạnh tranh được với con người bằng bất kỳ hình thức tính toán di truyền và tiến hóa nào. GP đã giành được nhiều giải thưởng ở cuộc thi này trong những năm qua.
Lập trình siêu di truyền
Lập trình siêu di truyền (Meta-genetic programing, Meta-GP) là kỹ thuật siêu học được đề xuất để phát triển một hệ thống lập trình di truyền bằng cách sử dụng chính lập trình di truyền. Nó đề xuất rằng nhiễm sắc thể, quá trình trao đổi chéo và đột biến đều là kết quả của sự tiến hóa, do đó, chúng nên được phép tự thay đổi như những phiên bản ngoài đời thực thay vì được xác định bởi một lập trình viên. Meta-GP được Jürgen Schmidhuber chính thức đề xuất vào năm 1987. Kĩ thuật này có thể tương đồng với công trình Eurisko trước đó của Doug Lenat. Nó là một thuật toán đệ quy tự dừng, cho phép tránh rơi vào đệ quy vô hạn. Trong phương pháp tiếp cận "tiến hóa tự xây dựng" đối với lập trình siêu di truyền, các phương pháp sinh sản và biến dị con cái được mã hóa trong chính các chương trình đang tiến hóa, và các chương trình được thực hiện để tạo ra các chương trình mới được thêm vào quần thể.
Những người chỉ trích ý tưởng này thường nói rằng cách tiếp cận này có phạm vi quá rộng. Tuy nhiên, có thể giới hạn tiêu chí thích nghi thành một tiêu chí chung để thu được một GP tốt hơn để tiến hóa cho các lớp con. Chẳng hạn như meta-GP tiến hóa để tạo ra các thuật toán đi bộ của con người, sau đó được sử dụng để tiến hóa hoạt động chạy, nhảy của con người, v.v. Tiêu chí thích nghi áp dụng cho meta GP này sẽ chỉ đơn giản là một giá trị hiệu suất.
Xem thêm
- Máy tính lấy cảm hứng từ sinh học
- Chiến lược tiến hóa ma trận hiệp phương sai thích nghi (CMA-ES)
- Xấp xỉ hàm mục tiêu
- Lập trình biểu hiện gen
- Cải thiện di truyền
- Đại diện di truyền
- Sự tiến hóa ngữ pháp
- Lập trình quy nạp
- Lập trình di truyền tuyến tính
- Lập trình đa biểu thức
- Lan truyền sơ đồ
Tham khảo
Liên kết ngoài
- Aymen S Saket & Mark C Sinclair
- Lập trình di truyền và Máy có thể tiến hóa, một tạp chí
- Evo2 cho lập trình di truyền
- Thư mục GP
- Hướng dẫn về tính toán tiến hóa của Hitch-Hiker
- Riccardo Poli, William B. Langdon, Nicholas F. McPhee, John R. Koza, " Hướng dẫn thực địa về lập trình di truyền " (2008)
- Lập trình di truyền, một nguồn tài nguyên do cộng đồng duy trì