Lập trình

TỔNG QUAN VỀ GIẢI THUẬT DI TRUYỀN

1.1.GIỚI THIỆU

Trong lịch sử phát triển của khoa học và công nghệ, sự ra đời của máy tính điện tử được xem như là cuộc cách mạng vĩ đại nhất. Nhờ đó, nó đã làm thay đổi sâu sắc đến nhiều lĩnh vực quan trọng trong một thời gian ngắn, thay vì hàng thập niên như những thập kỹ trước. Để có những thành tựu này chính là nhờ hình thức của các chương trình của máy tính đã tạo nên trí thông minh và sự sống nhân tạo ngày nay.

Đầu tiên, nó được áp dụng để tính toán quỹ đạo tên lửa và giải mã thông điệp trong lĩnh vực quân sự [20]. Sau đó, trong thập niên 1980s, nó được phát triển và áp dụng rộng rãi trong các lĩnh vực mạng neural, học máy (machine learning) và lĩnh vực đượ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. SƠ LƯỢC VỀ LỊCH SỬ TÍNH TOÁN TIẾN HÓA (EVOLUTIONARY COMPUTATION)

Trong các thập niên 1950s và 1960s, một số các nhà khoa học máy tính, trong quá nghiên cứu các hệ thống tiến hóa, đã đề xuấ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 di truyền tự nhiên và chọn lọc tự nhiên lấy từ thuyết tiến hóa của nhà sinh vật học Darwin.

Năm 1965, Rechenberg giới thiệu cuốn sách " Evolution Strategies "[15]-[16], trong đó ông đề xuất 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 [18]. Trong các lĩnh vực chiến lược tiến hóa 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.

Năm 1966, Fogel, Owens, và Walsh đã phát triển "lập trình tiến hóa (evolutionary programming)", một kỹ thuật trong đó các giải pháp ứng cử viên với nhiệm vụ được biểu diễn như là máy trạng thái hữu hạn (finite−state machine), đượ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. Cùng với các chiến lược tiến hóa, lập trình tiến hóa, và các 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ố nhà khoa học khác trong 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à máy học như Box (1957), Friedman (1959), Bledsoe (1961), Bremermann (1962), Reed, Toombs và Baricelli (1967).

Thuật toán di truyền (Genetic algorithms - GAs) đã được phát minh bởi John Holland trong những năm 1960; sau đó được tiếp tục phát triển bởi 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[9]. 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 Holland 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  đem vào vào hệ thống máy tính.

1975 cuốn sách Adaptation in Natural and Artificial Systems  của Holland [10] đã 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. GA của Holland 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 số 1 và số 0, hoặc "bits") 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  hoạt động di truyền như lai chéo, đột biến, và đảo ngược. Mỗi nhiễm sắc thể bao gồm "Genetics" (ví dụ, bits), mỗi gen là một thể hiện của một "allele" đặc biệt (ví dụ, 0 hoặc 1). Thuật toán sẽ 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à sinh sản nhiều hơn so với những người ít phù hợp. Trao đổi chéo (Crossover) các thành phần con của hai nhiễm sắc thể  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 (mutation randomly) 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 thứ tự (Inversion Reverses) 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.

Thuật toán dựa trên dân số của Holland với các với hoạt động lai ghép, đảo ngược, và đột biến là một sự đổi mới lớn và là nguồn cảm hứng cho việc giải quyết các vấn đề về tính toán.

Chẳng hạn, việc tìm kiếm tìm kiếm các chuỗi thứ tự các axit amin có thể với một protein cho trước hoặc tìm kiếm một bộ quy tắc hoặc các phương trình dự đoán những thăng trầm của thị trường tài chính. Hoặc trong điều khiển robot, làm thế nào robot có thể thực hiện một nhiệm vụ trong một điều kiện môi trường thay đổi v.v...

Thông thường, các vấn đề này đòi hỏi tìm kiếm một tập liên tục thay đổi các khả năng với số lượng lớn các khả năng để thích nghi cho điều kiện môi trường thay đổi. Các giải pháp. tìm kiếm như vậy thường yêu cầu sử dụng hiệu quả của xử lý song song, trong đó có nhiều khả năng khác nhau được khám phá cùng một lúc một cách hiệu quả để tạo ra thay đổi hàng triệu loài song song. Có thể nói, nhìn từ một mức độ cao các "nguyên tắc" của tiến hóa là khá đơn giản: các loài tiến hóa bằng phương tiện của biến ngẫu nhiên (thông qua đột biến, tái tổ hợp, và khai khác), tiếp theo là chọn lọc tự nhiên trong đó có xu hướng các thích nghi (fitness) để tồn tại và tái sản xuất; do đó truyền cho các thế hệ tương lai tạo ra  sự đa dạng bất thường và phức tạp như chúng ta thấy trong sinh quyển ngày nay.

1.3. PHƯƠNG PHÁP TÌM KIẾM VÀ TỐI ƯU HÓA

Hiện nay, người ta phân loại các thuật toán tối ưu thành 2 nhóm chính: Phương pháp truyền thống (Traditional  method) và phương pháp không truyền thống (Non traditional method).

• Phương pháp truyền thống : Đây là phương pháp tìm kiếm các giải pháp tối ưu các hàm liên tục và có dấu hiệu đặc trưng. Phương pháp này phân tích và sử dụng các kỹ thuật tính toán riêng biệt nhằm tìm kiếm các điểm tối ưu của các bài toán. Nó có 2 loại : Phương pháp trực tiếp và phương pháp dựa trên gradient.

+Phương pháp trực tiếp : Trong phương pháp này, không dựa bất kỳ thông tin dẫn xuất nào vào hàm mục tiêu chỉ có giá trị của nó được hướng dẫn quá trình tìm kiếm. Các phương pháp tìm kiếm trực tiếp thường chậm, đòi hỏi nhiều đánh giá chức năng cho hội tụ Các thuật toán, đại diên cho phương pháp này gồm : Bracketing methods, Region-elimination method, Point estimation method.

+Phương pháp gradient : Sử dụng dẫn dẫn xuất từ các hàm mục tiêu để hạn chế quá trình tìm kiếm.

 Tuy nhiên, hầu hết các phương pháp truyền thống đều có hạn chế như :

• Sự hội tụ đến một giải pháp tối ưu phụ thuộc vào các giải pháp ban đầu được lựa chọn.

• Hầu hết các thuật toán có xu hướng để có được bị “ sa lầy” vào một giải pháp tối ưu.

• Một thuật toán hiệu quả trong việc giải quyết một vấn đề tối ưu hóa này nhưng có thể không có hiệu quả trong việc giải quyết một vấn đề tối ưu hóa khác nhau.

• Các thuật toán là không hiệu quả trong việc xử lý các vấn đề có biến rời rạc.

• Các thuật toán không thể được sử dụng hiệu quả trên máy tính song song.

Như chúng ta biết, mỗi thuật toán tối ưu hóa truyền thống được thiết kế để giải quyết một loại hình cụ thể của bài toán. Chẳng hạn, phương pháp geometric  programming thiết kế để chỉ giải quyết các hàm mục tiêu dạng đa thức và ràng buộc, nhưng không áp dụng phù hợp để giải quyết các bài toán có các loại chức năng khác nhau.

Hơn nữa  các bài toán trong thực tiễn, yêu cầu có các biến số rời rạc nhằm đáp ứng các điều kiện phát sinh trong thực tế nên dẫn đến các khó khăn như :  các thuật toán tối ưu hóa dành thời gian rất lớn trong việc tính toán các giải pháp khả thi dẫn đến nỗ lực tìm kiếm không hiệu quả; giải pháp bổ sung sẽ rất lớn, với n biến rời rạc thì sẽ có 2ⁿ giải pháp bổ sung; kiểm tra cho từng biến không thể đảm bảo sự hình thành của sự kết hợp tối ưu đối với các biến khác.   

Gần đây, nhiều bài toán tối ưu hóa đòi hỏi việc sử dụng một phần mềm mô phỏng liên quan đến các phương pháp phần tử hữu hạn, như các bài toán : tính toán chất lỏng cơ học, giải các phương trình phi tuyến v.v… Rõ ràng, với khả năng vốn có của máy tính song song thuận tiện để để giải quyết các vấn đề kỹ thuật tối ưu hóa thiết kế phức tạp, nhưng hầu hết các phương pháp truyền thống sử dụng cách xử lý điểm-điểm nên lợi thế của máy song song có thể không được khai thác [5].

Các vấn đề trên, cho thấy rằng các phương pháp truyền thống không phải là “đại diện” tốt cho các thuật toán tối ưu đạt hiệu quả cao trong thiết kế kỹ thuật. Kỹ thuật GA có thể giảm bớt một số các khó khăn nêu trên và có thể tạo thành một công cụ tối ưu hóa hiệu quả.

- Phương pháp không truyền thống : Đây là phương pháp khá mới và đang trở nên phổ biến từng ngày. Hai thuật toán như vậy là :

+ Thuật toán di truyền (Genetictic Algorithm)

+ Luyện kim mô phỏng (Simulated Annealing)

Sự khác biệt giữa thuật toán di truyền và tối ưu hóa truyền thống thuật toán:

• GAs làm việc với một mã hóa các thông số thiết lập không phải các thông số không của bản thân nó.
  • GAs tìm kiếm từ một dân số của các điểm không phải là một điểm duy nhất.
• GAs sử dụng các luật chuyển đổi xác suất, không phải luật xác định.

1.4. THUẬT TOÁN DI TRUYỀN

1.4.1.Giới thiệu

Genetic algorithm (GA) là giải thuật lặp sử dụng quá trình ngẫu nhiên để thăm dò và tối ưu hóa nguồn gốc và cảm hứng của chúng được lấy từ thuyết tiến hóa sinh vật học của Darwin.

Như chúng ta đã biết, một sinh vật được cấu thành từ một hoặc nhiều tế bào, ví dụ như con người gồm khoảng 10¹⁴ tế bào. Mỗi tế bào có chứa cùng một tập của một hoặc nhiều chuỗi nhiễm sắc thể của DNA, đóng vai trò như là một "bản đồ thiết kế" cho các sinh vật. Một nhiễm sắc thể có thể được chia thành Genetics và đựơc mã hóa thành protein đặc trưng. Mỗi đặt điểm khác nhau được thiết lập (ví dụ, màu xanh, nâu, nâu nhạt) được gọi là alen. Mỗi Genetic nằm tại một vị trí đặc biệt trên nhiễm sắc thể. Rất nhiều sinh vật có nhiều nhiễm sắc thể trong mỗi tế bào. Các bộ sưu tập hoàn chỉnh các vật liệu di truyền (tất cả các nhiễm sắc thể lấy nhau) được gọi là hệ Genetic của sinh vật. Hai cá thể có bộ gen giống hệt nhau được cho là có kiểu gen giống nhau. Sinh vật có nhiễm sắc thể được dàn theo cặp được gọi là lưỡng bội; sinh vật có nhiễm sắc thể là lẻ được gọi là đơn bội.

Trong các thuật toán di truyền, nhiễm sắc thể thường đề cập đến một giải pháp ứng cử viên và thường được mã hóa như là một chuỗi bit. "Genetic" là một trong hai bit duy nhất hoặc các khối ngắn bit liền kề mã hóa một yếu tố đặc biệt của giải pháp ứng cử viên. Trong quá trình chọn lọc tự nhiên, những kiểu hình nào thích nghi với tự nhiên sẽ sống sót và ngược lại, những kiểu không thích nghi sẽ bị loại đào thải. Genetic di truyền của một sinh vật có được nhờ quá trình lai ghép (Crossover), đột biến (Mutation) và sinh sản (Reproduction) qua các thế hệ, chọn lọc tự nhiên  với quá trình đào thải các kiểu hình không thích nghi sẽ đào thải các kiểu Genetic không thích nghi. Với một tổ hợp Genetic lớn, một loài sẽ tiến hóa dần (tối ưu hóa dần) theo chọn lọc tự nhiên mặc dù số lượng cá thể trong loài không đủ lớn để một tập hợp có đầy đủ tổ hợp Genetic. Quá trình này lai, di truyền sẽ tạo nên một thế hệ mới với những đặc điểm đã được thích nghi, quá trình đột biến tạo ra những tổ hợp Genetic mới có thể có tính thích nghi cao hơn. 

Một giải thuật GAs điển hình bao gồm các thành phần sau :

• Một tập hợp của những chuỗi hay những giải pháp có thể mã hóa (được coi như là nhiễm sắc thể ).
• Một cơ chế mã hóa một giải pháp khả thi (Chủ yếu là chuỗi nhị phân).
• Hàm mục tiêu và những kỹ thuật ước lượng độ thích nghi, đánh là hàm đánh giá một giải pháp.
• Thủ tục chọn lọc và tái tạo.
• Những hoạt động Genetic (lai tạo và đột biến).
• Xác suất để thực hiện những hoạt động Genetic.

Population (dân số)

Để giải quyết vấn đề tối ưu hóa, GAs bắt đầu với cấu trúc nhiễm sắc thể đại diện cho một bộ tham số (). Bộ tham số được mã hóa như một chuỗi có chiều dài hữu hạn thông qua một bảng chữ cái với chiều dài hữu hạn. Thông thường những nhiễm sắc thể là những chuỗi của các bit 0 và 1. Ví dụ, cho () đại diện cho một bộ tham số (parameter set) và biểu diễn nhị phân của tương ứng là 10110, 00100, …, 11001, thì chuỗi 1011000100 …11001 là một nhiễm sắc thể biểu diễn cho bộ tham số (). Hiển nhiên, số nhiễm sắc thể (strings) khác nhau là 2^l, trong đó l là chiều dài của chuỗi. Mỗi nhiễm sắc thể được xem như là một giải pháp đã được mã hóa. Một tập hợp những nhiễm sắc thể như vậy trong một thế hệ được gọi là một dân số. Kích thước của dân số có thể thay đổi từ thế hệ này sang thế hệ khác hoặc có thể là cố định. Thông thường, các phần tử trong dân số đầu tiên được lựa chọn một cách ngẫu nhiên.

Cơ chế mã hóa (Coding)

Đây là cơ chế chuyển đổi giá trị thông số của một giải pháp khả thi sang chuỗi nhị phân đại diện giống như nhiễm sắc thể. Nếu giải pháp của một vấn đề phụ thuộc vào tham số p, và nếu ta muốn mã hóa mỗi tham số bằng một chuỗi nhị phân có độ dài q, thì chiều dài của mỗi nhiễm sắc thể sẽ là pxq.Việc giải mã chỉ là sự đảo ngược của chuỗi mã hóa.

Để thực hiện GAs trong các giải pháp tối ưu nêu trên, đầu tiên biến  phải được mã hóa trong một số cấu trúc chuỗi.  Biến được mã hoá bằng nhị phân đại diện có 0 và 1. Chiều dài của chuỗi mã hóa thường được xác định theo sự chính xác giải pháp mong muốn. Ví dụ, nếu 4 bits được sử dụng để mã hóa, mỗi biến thành 2 biến trong các vấn để tối ưu hóa chức năng, các dãy (0000, 0000) và (1111, 1111) sẽ đại diện cho các điểm ()^T ()^T. Bất kỳ chuỗi 8 bit khác có thể được tìm thấy để đại diện cho một điểm trong không gian tìm kiếm theo một quy tắc lập bản đồ cố định. Thông thường, các quy tắc ánh xạ tuyến tính sau đây được sử dụng:

                                                        ^{( giá trị mã hóa SA )}

Trong đẳng thức trên, biến  được mã hóa ở chuỗi con Si  với chiều dài li^.  Giá trị mã hóa của chuỗi nhị phân Si được tính : , ở đây và chuỗi S được mô tả (). Ví dụ, với chuỗi 4 bits (0111) có giá trị mã hóa bằng ((1) 2o + (1) 2' + (1) 22 + 23) hoặc 7. Như vậy chỉ với 4 bit để mã hóa mỗi biến, có 24 hoặc 16 chuỗi con riêng biệt có thể, vì mỗi vị trí bit có thể mất một giá trị là 0 hoặc 1. Độ chính xác có thể đạt được với một mã hóa bốn bit chỉ là khoảng 1/16 của không gian tìm kiếm. Nhưng độ dài chuỗi là một tăng, các tăng theo cấp số nhân có thể đạt được đến 1 / 32 của không gian tìm kiếm.

Hàm mục tiêu (Objective Fuction ) hay còn gọi là hàm thích nghi (Fitness Function)

Mỗi chuỗi thành viên trong một quần thể được đánh giá bằng các giá trị chức năng của hàm thích nghi. Vấn đề giảm thiểu thường được chuyển thành vấn đề giảm thiểu bằng một số chuyển đổi phù hợp. Hàm mục tiêu và độ thích nghi được lựa chọn phụ thuộc vào vấn đề và bài toán có liên quan. Nếu nó được lựa chọn theo những chuỗi thích nghi tốt (những giải pháp khả thi) cho những giá trị thích nghi cao.

Thủ tục chọn lọc và tài tạo (selection / reproduction Procedure)

Quá trình chọn lọc và tái tạo sao chép cho những chuỗi đặt biệt ( được gọi là những nhiễm sắc thể cha) cho ra một tập cá thể mới gọi là “ mating pool” (bồn lai) danh cho những hoạt động của Genetictic. Một bản sao được tái tạo cho thế hệ kế tiếp xác suất bằng tỷ lệ giá trị thích nghi của nó với tổng toàn bộ giá trị thích nghi trong dân số. Quá trình này bắt chước quá trình chọn lọc trong tự nhiên, những cá thể thích nghi hơn sẽ được ưu tiên tồn tại và phát triển. Kết quả của quá trình chọn lọc và tái tạo  se cho một mating pool có số lượng cá thể bằng với số lượng cá thể trong dân số, tỉ lệ của từng loại cá thể so với P(kích thước dân số) bằng với độ thích nghi của của loại đó so với tổng độ thích nghi trong dân số. (CÒN TIẾP)