Ứng dụng

1.1.         MỞ ĐẦU

Khoa học xuất phát từ mong muốn rất con người để hiểu và kiểm soát thế giới. Trong suốt lịch sử, con người chúng ta đã dần dần xây dựng một dinh thự lớn của kiến ​​thức đó cho phép chúng ta dự đoán, với mức độ khác nhau, thời tiết, sự chuyển động của các hành tinh, nhật thực và nguyệt, các khóa học của bệnh, những thăng trầm tăng trưởng kinh tế, các giai đoạn phát triển ngôn ngữ ở trẻ em, và một bức tranh toàn cảnh rộng lớn của các hiện tượng tự nhiên, xã hội và văn hóa khác. Gần đây chúng tôi đã thậm chí đến để hiểu một số giới hạn cơ bản đến khả năng của mình để dự đoán. Trong thời gian rất dài, chúng tôi đã phát triển phương tiện ngày càng phức tạp để kiểm soát nhiều khía cạnh của cuộc sống và tương tác của chúng tôi với thiên nhiên, và chúng tôi đã học được, thường một cách khó khăn, mức độ mà các khía cạnh khác là không kiểm soát được.

Sự ra đời của máy tính điện tử đã cho là được sự phát triển tính cách mạng nhất trong lịch sử khoa học và công nghệ. Cuộc cách mạng đang diễn ra này là sâu sắc tăng khả năng tiên đoán và kiểm soát chất trong những cách mà hầu như đã được hình thành ngay cả nửa thế kỷ trước. Đối với nhiều người, những thành tựu huy hoàng của cuộc cách mạng này sẽ là việc tạo ra theo các hình thức của các chương trình của máy tính của loài mới của sinh vật thông minh, và thậm chí cả các hình thức mới của cuộc sống.

Các mục tiêu của việc tạo ra trí thông minh nhân tạo và sự sống nhân tạo có thể được truy trở lại khởi đầu của thời đại máy tính. Các nhà khoa học-Alan máy tính sớm nhất Turing, John von Neumann, Norbert Wiener, và những người khác-đã được thúc đẩy một phần lớn bởi hình ảnh của imbuing chương trình máy tính với trí thông minh, có khả năng giống như cuộc sống để tự sao chép, và có khả năng thích nghi để học và kiểm soát môi trường của họ. Những người tiên phong đầu của khoa học máy tính đã được nhiều quan tâm trong sinh học và tâm lý học như trong điện tử, và họ nhìn vào các hệ thống tự nhiên như hướng dẫn những ẩn dụ cho cách để đạt được tầm nhìn của họ. Nó không nên ngạc nhiên, sau đó, từ các máy tính ngày sớm nhất được áp dụng không chỉ để tính toán quỹ đạo tên lửa và giải mã mã quân sự mà còn để mô hình hóa não, bắt chước học tập của con người, và mô phỏng sự tiến hóa sinh học. Những hoạt động sinh học tính toán động lực đã sáp và nhạt dần trong những năm qua, nhưng từ đầu những năm 1980 họ đã trải qua tất cả một sự hồi sinh trong cộng đồng nghiên cứu tính toán. Việc đầu tiên đã trở thành lĩnh vực của mạng lưới thần kinh, thứ hai vào máy tính học tập, và thứ ba vào những gì bây giờ được gọi là "tính toán tiến hóa", trong đó các thuật toán di truyền là những ví dụ nổi bật nhất.

1.2.           LỊCH SỬ TÍNH TOÁN TIÊN HÓA

Trong các thập niên 1950 và thập niên 1960 một số nhà khoa học máy tính nghiên cứu độc lập các hệ thống tiến hóa với ý tưởng rằng sự tiến hóa có thể được sử dụng như một công cụ tối ưu hóa cho các vấn đề kỹ thuật. Ý tưởng trong tất cả các hệ thống này là để phát triển một số các giải pháp ứng cử viên cho một vấn đề nào đó, bằng cách sử dụng toán tử lấy cảm hứng từ sự biến đổi gen tự nhiên và chọn lọc tự nhiên.

Trong những năm 1960, Rechenberg (1965, 1973) giới thiệu "chiến lược tiến hóa" (Evolutionsstrategie trong bản gốc tiếng Đức), một phương pháp mà ông sử dụng để tối ưu hóa các thông số giá trị thực cho các thiết bị như airfoils. Ý tưởng này đã được phát triển thêm bởi Schwefel (1975, 1977). Các lĩnh vực chiến lược tiến hóa vẫn là một lĩnh vực mới trong nghiên cứu, chủ yếu là phát triển một cách độc lập từ các lĩnh vực của các thuật toán di truyền (mặc dù gần đây hai cộng đồng đã bắt đầu tương tác). (Đối với một bình luận ngắn về chiến lược tiến hóa, xem lại, Hoffmeister, và Schwefel 1991.) Fogel, Owens, và Walsh (1966) đã phát triển "lập trình tiến hóa", một kỹ thuật mà trong đó các giải pháp ứng cử viên với nhiệm vụ đưa ra được biểu diễn như là máy hữu hạn nhà nước , được phát triển bởi đột biến ngẫu nhiên sơ đồ trạng thái của họ và lựa chọn thích hợp nhất. Một công thức có phần rộng hơn về lập trình tiến hóa cũng vẫn là một lĩnh vực nghiên cứu hoạt động (xem, ví dụ, Fogel và Atmar 1993). Cùng với nhau, các chiến lược tiến hóa, lập trình tiến hóa, và thuật toán di truyền tạo thành xương sống của lĩnh vực tính toán tiến hóa.

Một số người khác làm việc trong các thập niên 1950 và thập niên 1960 đã phát triển các thuật toán tiến hóa lấy cảm hứng để tối ưu hóa và học máy. Box (1957), Friedman (1959), Bledsoe (1961), Bremermann (1962), và Reed, Toombs, và Baricelli (1967) tất cả làm việc trong lĩnh vực này, mặc dù công việc của họ đã được đưa ra ít hoặc không có các loại chú ý hoặc followup rằng các chiến lược tiến hóa, lập trình tiến hóa, và thuật toán di truyền đã thấy. Ngoài ra, một số nhà sinh vật học tiến hóa sử dụng máy tính để mô phỏng sự tiến hóa cho mục đích của thí nghiệm kiểm soát (xem, ví dụ, Baricelli năm 1957, 1962; Fraser 1957 a, b; Martin và Cockerham 1960). Tính toán tiến hóa chắc chắn là trong không khí trong những ngày hình thành của các máy tính điện tử.

Các thuật toán di truyền (GAS) đã được phát minh bởi John Holland trong những năm 1960 và được phát triển bởi Hà Lan, sinh viên và đồng nghiệp của ông tại Đại học Michigan trong thập niên 1960 và thập niên 1970. Ngược lại với các chiến lược phát triển và lập trình tiến hóa, mục tiêu ban đầu của Hà Lan đã không để thiết kế các thuật toán để giải quyết các vấn đề cụ thể, mà là để chính thức nghiên cứu các hiện tượng của sự thích nghi khi nó xảy ra trong tự nhiên và phát triển những cách thức mà các cơ chế thích ứng tự nhiên có thể được nhập khẩu vào hệ thống máy tính. 1.975 cuốn sách thích ứng của Hà Lan trong các hệ thống tự nhiên và nhân tạo đã trình bày các thuật toán di truyền như là một sự trừu tượng của sự tiến hóa sinh học và đã đưa ra một khuôn khổ lý thuyết cho thích ứng theo GA. Hà Lan của GA là một phương pháp để di chuyển từ một dân số "nhiễm sắc thể" (ví dụ, chuỗi của những người thân và số không, hoặc "bit") cho một dân số mới bằng cách sử dụng một loại "chọn lọc tự nhiên" cùng với các nhà khai thác di truyền cảm hứng của chéo , đột biến, và đảo ngược. Mỗi nhiễm sắc thể bao gồm "gen" (ví dụ, bit), mỗi gen là một thể hiện của một "allele" đặc biệt (ví dụ, 0 hoặc 1). Nhà điều hành lựa chọn chọn những nhiễm sắc thể trong dân số sẽ được cho phép để tái sản xuất, và trung bình các nhiễm sắc thể fitter sinh sản nhiều hơn so với những người ít phù hợp. Trao đổi chéo subparts của hai nhiễm sắc thể, khoảng bắt chước tái tổ hợp sinh học giữa hai đơn nhiễm sắc thể ("đơn bội") sinh vật; đột biến thay đổi ngẫu nhiên các giá trị alen của một số địa điểm trong các nhiễm sắc thể; và đảo ngược đảo ngược thứ tự của một phần tiếp giáp của các nhiễm sắc thể, do đó sắp xếp lại thứ tự các gen được dàn trận. (Ở đây, như trong hầu hết các văn GA, "chéo" và "tái hợp" sẽ có nghĩa tương tự.

Giới thiệu một thuật toán dựa trên dân số với chéo, đảo ngược, và đột biến của Hà Lan là một sự đổi mới lớn. (Chiến lược tiến hóa Rechenberg của bắt đầu với một "dân số" của hai cá nhân, một phụ huynh và một con cái, con cái là một phiên bản đột biến của cha mẹ; quần thể nhiều-cá nhân và crossover không được kết hợp cho đến sau này Fogel, Owens, và lập trình tiến hóa Walsh. tương tự như vậy chỉ sử dụng đột biến để cung cấp biến thể.) Hơn nữa, Hà Lan đã là người đầu tiên cố gắng đưa những tiến hóa tính toán trên một nền tảng lý thuyết vững chắc (xem Hà Lan 1975). Cho đến gần đây nền tảng lý thuyết này, dựa trên khái niệm "lược đồ", là cơ sở của công tác lý luận gần như tất cả các

tiếp theo về giải thuật di truyền.

 Trong vài năm qua đã có sự tương tác rộng rãi giữa các nhà khoa học phương pháp tính toán tiến hóa khác nhau, và ranh giới giữa khí, chiến lược tiến hóa, lập trình tiến hóa, và cách tiếp cận tiến hóa khác đã bị phá vỡ các mức độ nào đó. Hôm nay, các nhà nghiên cứu thường sử dụng thuật ngữ "thuật toán di truyền" để mô tả một cái gì đó rất xa từ khái niệm ban đầu của Hà Lan. Trong cuốn sách này, tôi áp dụng linh hoạt này. Hầu hết các dự án mà tôi sẽ mô tả ở đây được giới thiệu bởi originators của họ như là GAS; một số thì không, nhưng họ đều có đủ của một "giống gia đình" mà tôi bao gồm chúng trong phiếu đánh giá của các thuật toán di truyền.