lập trình tiến hóa

Question

Tôi chỉ xem một khá mát mẻ ted talk Danny Hillis đề ngày 1994.

Tại một thời điểm trong đoạn video, ông nói về "lập trình tiến hóa", tức là anh ta hỏi máy tính để tạo ra hàng trăm chương trình bằng cách tạo ra ngẫu nhiên chuỗi các lệnh, sau đó kiểm tra để xem mỗi chương trình sắp xếp số lượng như thế nào. Ông giữ 10% các chương trình phân loại số tốt nhất, sau đó tạo ra một vòng tiếp theo của chương trình dựa trên 10% đã làm tốt và lặp lại nhiều lần như ông muốn, để cuối cùng tạo ra các chương trình phân loại cuối cùng.

Có công cụ/ngôn ngữ lập trình nào ở đó thực hiện việc này không? Ví dụ. với một số ràng buộc nhất định, tạo ra mã C đáp ứng tốt nhất các ràng buộc đó.

Tôi đã truy cập một số bài viết wikipedia liên quan đến "Lập trình tiến hóa"; dường như có rất nhiều lý thuyết ở đó, nhưng có vẻ như không dễ dàng tìm thấy thứ gì đó bạn có thể chơi cùng.

Answer 1

Nguồn tải xuống miễn phí rất đơn giản và tổng quát là TinyGP được triển khai trong Java. Nhân tiện .. để biết thêm chi tiết về điều này, bạn nên tìm kiếm thông tin về "lập trình di truyền" thay vì "lập trình tiến hóa". nó là một chút bối rối bởi vì có rất nhiều trường con của tính toán tiến hóa với sự khác biệt nhỏ trong các tên như "thuật toán di truyền", "chiến lược tiến hóa", "lập trình tiến hóa", "lập trình di truyền" ... nhưng tôi nghĩ bạn là gì đang nói về thực sự là lập trình di truyền

Answer 2

Sách/hướng dẫn này sử dụng Ruby để lập trình tiến hóa.

http://www.cleveralgorithms.com/nature-inspired/index.html

Answer 3

Một ví dụ thực tế:

Csmith là một công cụ có thể tạo ra các chương trình C ngẫu nhiên mà tĩnh và động phù hợp với các tiêu chuẩn C99. Nó rất hữu ích cho các trình biên dịch thử nghiệm ứng suất, các trình phân tích tĩnh và các công cụ khác xử lý mã C. Csmith đã tìm thấy các lỗi trong mọi công cụ mà nó đã thử nghiệm, và chúng tôi đã sử dụng nó để tìm và báo cáo hơn 400 lỗi trình biên dịch chưa biết trước đây.

Answer 4

Ví dụ cổ điển là Tierra và Avida.

Khu vực có liên quan là tiến hóa phần cứng và rô bốt tiến hóa, xem this page chẳng hạn.

Ngoài ra còn có book tốt đẹp về tính toán tiến hóa trong Mathematica.

Answer 5

Tôi ghét trở thành người nói, nhưng chúng tôi đã làm một số thử nghiệm với lập trình tiến hóa và thấy rằng trên rất nhiều vấn đề, tìm kiếm toàn diện nhanh hơn.

Có các trường liên quan chặt chẽ như Thuật toán di truyền, mà tôi đã sử dụng để tạo rô bốt đi bộ, v.v .. Tôi đã sử dụng GALIB cho điều đó. Nó có lẽ là cổ đại bây giờ.

Trong khi ý tưởng là "tuyệt vời", cách tiếp cận tốt nhất có thể là sử dụng kết hợp các kỹ thuật tiến hóa cộng với học tập (tức là học tập tăng cường).

Điều này giống như cách con người học. Có sự tiến hóa lâu dài làm cho các thí nghiệm dần dần, cộng với việc học sửa chữa mọi thứ và điều chỉnh hệ thống với môi trường.

Tuy nhiên, quá trình tiến hóa chỉ mất quá nhiều thời gian để có hiệu quả.

Answer 6

Có lẽ chương trình linh hoạt nhất để tạo các chương trình tiến hóa sẽ là Assembler. Đây là ngôn ngữ duy nhất mà tôi biết có khả năng ghi đè lên các chương trình khác và thay đổi mã riêng của nó. Bạn có thể muốn xem qua các chương trình Core Wars cũ - một phiên bản khác hoặc cập nhật của một trong những chương trình này có thể phát triển và đánh bại sự cạnh tranh. Hơn nữa, bạn có khả năng sống sót của fittest, trong chừng mực vì có một số giới hạn các thư mục.

Answer 7

Trường tính toán tiến hóa tạo chương trình được gọi là Lập trình di truyền (GP). GP mô phỏng sự tiến hóa sinh học của một quần thể cá nhân, qua nhiều thế hệ. Thông thường, một cá nhân là một chương trình (hoặc đại diện của nó, thường là một cấu trúc dữ liệu cây) và cơ hội sống sót và tái tạo của nó được đo lường về mặt biểu diễn của nó trong việc giải quyết một nhiệm vụ.

Ngày nay bạn không thể tạo mã sản xuất thực tế cho các công việc hàng ngày, trung thực. Thay vào đó, GP và nhiều kỹ thuật Máy học khác được nghiên cứu trong nghiên cứu hiện đại và được sử dụng bởi các công ty rất lớn (tức là Google, Facebook, v.v.). Thực tế, phương pháp GP rất hữu ích khi bạn biết bạn muốn chương trình mục tiêu làm gì (ví dụ, bạn biết đầu ra cho đầu vào) nhưng bạn không biết làm thế nào (hoặc nó chỉ đơn giản là khó khăn cho bạn) để viết tự mình viết mã.

Để hiểu đúng chủ đề, bạn có thể muốn viết công cụ phát triển từ đầu và chơi với nó. Nó hoàn toàn tốt để viết mã bắt đầu từ một mô tả lý thuyết. Đó là cách tốt nhất để tìm hiểu cách những thứ này hoạt động, thay vì sử dụng một số "phần mềm dựng sẵn", imho. Ngoài ra, tôi khuyên bạn nên bắt đầu với thuật toán di truyền (GA), vì chúng thường đơn giản hơn. Thực tế, trong GA, bạn thường đánh giá kiểu gen của các cá nhân, tức là các bit tạo chúng, trong khi ở GP bạn có thể chuyển cây thành các chương trình, thực thi chúng, xem kết quả đầu ra và cuối cùng đo hiệu suất của chúng (không thẳng thắn, uh ?). Hãy xem điều này: http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3.

Phòng thí nghiệm nơi tôi đã làm luận văn Thạc sĩ của mình là chứng minh rằng GP có hiệu suất rất tốt trong việc tạo biểu thức chính quy từ các ví dụ về trích xuất văn bản. Họ xây dựng một GUI để chơi với động cơ của họ: http://regex.inginf.units.it/demo.html. Họ cũng chia sẻ mã động cơ trên github: https://github.com/MaLeLabTs/RegexGenerator. Cuối cùng, một người bạn của tôi đã mã hóa một số thử nghiệm trực quan hài hước bằng cách sử dụng GP và GA (Thuật toán di truyền) trong blog của mình. Hãy xem: http://www.nicassio.it/daniele/gp/enviroment/, http://www.nicassio.it/daniele/gp/santaclaus/.