19/06/2025 05:58:59 AM

Lập trình

GIẢI THUẬT DI TRUYỀN - Phần 1

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ố.

1.4.2. Nguyên tắc hoạt động

Không giống như phương pháp truyền thống, GAs không sử dụng tìm kiếm ngẫu nhiên đơn giản như hoặc tùy thuộc một hành động xác suất đơn giản như tung đồng xu. GAs sử dụng lựa chọn ngẫu nhiên như là một công cụ để hướng dẫn một tìm kiếm liên quan đến vùng của không gian tìm kiếm với khả năng cải thiện.

Để minh họa cho nguyên tắc hoạt động của GAs, ta xem xét vấn đề tối ưu sau đây:

Tối ưu:

Hoạt động của GAs được hoàn thành nhờ các công việc sau:

Khởi tạo (Initialization)

Hoạt động này đề cập đến việc vấn đề tối ưu hóa một tập các chuỗi nhị phân đại diện bởi biến xi được tạo ra một cách ngẫu nhiên để tạo ra dân số ban đầu.

Hoạt động di truyền (Genetic Operators)

Được áp dụng trên những nhiễm sắc thể trong “mating pool” và những nhiễm sắc thể mới (con cái - offspring) được tạo ra.

Với một dân số ban đầu của các cá thể của các giá trị thích nghi khác nhau, hoạt động của GAs bắt đầu để tạo ra một quần thể mới và cải tiến các từ quần thể cũ. Một thuật toán di truyền đơn giản (Simple Geneticric Algorithm - SGA), bao gồm ba hoạt động cơ bản: sinh sản (reproduction), lai ghép (crossover) và đột biến (mutation). Thông qua các hoạt động dân số mới của các điểm được đánh giá. Dân số được lặp đi lặp lại dựa trên ba hoạt động trên và đánh giá cho đến khi đạt được các tiêu chí mục tiêu hay chấm dứt được đáp ứng. Một chu kỳ của các hoạt động và thủ tục đánh giá tiếp theo được gọi là thế hệ trong GA.

Sinh sản (Reproduction)

Sinh sản thường thường là hoạt động đầu tiên được áp dụng trên một dân số. Sinh sản chọn chuỗi theo các giá trị thích nghi (giá trị có xác suất đóng góp cao cho thế hệ sau) trong một dân số và hình thành một mating pool. Chuỗi thứ i trong dân số được chọn với một tỷ lệ xác suất . Vì kích thước dân số thường được giữ cố định trong một GA đơn giản, tổng xác suất của mỗi chuỗi được lựa chọn cho các mating pool phải là một. Vì vậy, xác suất để lựa chọn các chuỗi thứ i là :

Ở đây, n : quy mô dân số.

Vì chu vi của bánh xe được đánh dấu theo chuỗi thích nghi, cơ chế dự kiến sẽ làm cho Fi/F bản sao của chuỗi thứ i trong mating pool. Giá trị trung bình của dân số được tính:

F =

Hình 1.1 Cho thấy một roulette-wheel cho các cá thể tốt có giá trị thích nghi khác nhau. Từ khi cá thể thứ ba có một giá trị thích nghi cao hơn so với bất kỳ cá thể khác khác. Lược đồ lựa chọn roulette-wheel có thể được mô phỏng một cách dễ dàng. Sử dụng giá trị thích nghi Fi của tất cả các chuỗi, xác suất lựa chọn một chuỗi Pi có thể được tính toán. Do đó, xác suất tích lũy (Pi) của mỗi chuỗi có thể được sao chép được tính bằng cách cộng các xác suất cá thể từ đỉnh của danh sách.

Hình 1.1. Vòng Roulette-Wheel cho 5 cá thể với các giá trị thích nghi của nó.

Lai ghép (Crossover)

Mục tiêu chính của crossover là để trao đổi thông tin giữa những nhiễm sắc thể trong bồn lai được lựa chọn một cách ngẫu nhiên nhằm không làm mất bất kỳ thông tin quan trọng nào (làm giảm tối thiểu sự phá vỡ cấu trúc của những nhiễm sắc thể được lựa chọn cho hoạt động Genetictic). Thật sự, việc lai kết hợp nguyên liệu “Genetic” của hai nhiễm sắc thể cha để tạo nhiễm sắc thể mới (con cái) cho thế hệ kế tiếp. Hoạt động crossover có thể được xem như là một quá trình có ba bước:

Bước 1: Cặp nhiễm sắc thể (được gọi là cặp ghép đôi) được lựa chọn từ bồn lai “mating pool”.
Bước 2: Dựa trên cơ sở xác suất lai (crossover probability) (bằng cách tạo một số ngẫu nhiên trong đoạn [0,1] và kiểm tra liệu số này có có nhỏ hơn xác suất crossover không), để quyết định liệu những cặp nhiễm sắc thể này sẽ được dùng cho crossover hay không.
Bước 3: Thực hiện trao đổi những đoạn nhiễm sắc thể giữa hai cặp được ghép đôi. Số đoạn trao đổi và chiều dài của đoạn thay đổi tùy vào từng kỹ thuật crossover, có thể là: crossover một điểm, hai điểm, đa điểm, trao đổi xáo trộn (shuffle-exchange crossover), trao đổi đều (uniform crossover) v.v... Thông thường, chỉ trao đổi một đọan “Genetic” (lai một điểm).

Đột biến (Mutation )

Hình 1.2. Sơ đồ tổng quát các bước của giải thuật di truyền

Mục tiêu chính của mutation là đưa ra nhiều dạng “Genetic” khác vào trong dân số. Đôi khi, nó giúp khôi phục lại thông tin đã bị mất trong những thế hệ trước. Giống như những hệ thống Genetic trong tự nhiên, đột biến trong GAs cũng được thực hiện một cách thỉnh thoảng. Một vị trí ngẫu nhiên của một chuỗi ngẫu nhiên được lựa chọn và được thay thế bởi những ký tự khác từ bảng tra đang dùng. Trong trường hợp sự biểu diễn bằng số nhị phân, nó thay đổi giá trị bit đó và được xem như là bit đột biến.

Thông thường, tốc độ đột biến được giữ cố định. Để giữ vững được tính năng đa dạng (có thể bị mất bởi sự lai tạo và tốc độ đột biến quá chậm) trong dân số. Whitley[21] đưa ra một kỹ thuật được gọi là đột biến thích ứng (adaptive mutation), nơi mà xác suất để thực hiện hoạt động đột biến được tạo ra để tăng (thay vì giữ nó cố định) với sự gia tăng “Genetic” giống nhau trong dân số. Hoạt động đột biến không phải lúc nào cũng tốt cả. Tốc độ đột biến cao có thể dẫn đến sự tìm kiếm Genetictic đến một Genetictic ngẫu nhiên. Nó có thể làm thay đổi giá trị của một bit quan trọng và làm ảnh hưởng đến độ hội tụ nhanh đến một giải pháp tốt. Ngoài ra, nó có thể làm giảm quá trình hội tụ tại giai đoạn cuối cùng (final stage) của GAs. Gần đây, Bhandari đã đưa ra một kỹ thuật đột biến mới gọi là đột biến trực tiếp (directed mutation) [4]. Hình 1.2 là sơ đồ thuật toán cho thuật toán di truyền.

1.4.3. Cơ sở toán học của thuật toán di truyền

Ở đây ta xét cơ sở toán học của GA qua các hoạt động reproduction (sinh sản), crossover (lai ghép) và mutation (đột biến). Hoạt động của giải thuật Genetic (GA) là thẳng tới. Trước hết ta bắt đầu với một population có những strings, copy các string theo khuynh hướng tiến về cái tốt nhất, ghép đôi và trao đổi cục bộ các đoạn con (substring) và đột biến một vài giá trị bit một cách thỉnh thoảng.

Xét các string, không làm mất tổng quát, được cấu tạo bằng các phần tử của tập V={0,1}. Ta xem các string bằng các chữ hoa, gồm các ký tự riêng với số thứ tự ghi nhỏ bên dưới.

A= a aa aa aa

A(t): dân số tại thời điểm (thế hệ) t, (t N) .

Các phần tử A(t) j=1,2,…n-1 A(t)

Xét cá thể đồng dạng H (schema H) cấu tạo từ tập Vt= {0,1,*}

Ví dụ: A = 0 1 1 1 0 0 0 là một ví dụ (mẫu) của H = * 1 1 * 0 * *

Nói chung, một tập ký tự có k ký tự thì sẽ có (k+1) schemata, l= length(string).

Mỗi string có thể đại diện cho 2 schemata. Suy ra, một dân số với những phần tử sẽ đại diện cho khoảng n. 2 schemata (n.2schemata là số lớn nhất). Tính toán này cho chúng ta thấy độ lớn của khối lượng thông tin được xử lý trong thuật toán GA.

Không phải tất cả các schemata đều như nhau mà có một số schemata này đặc biệt hơn mợt số schemata khác, schema 101*1** thì rõ ràng hơn schema 1*1****. Hơn nữa, schema 1****1* thì “nhảy“ qua một đoạn dài hơn schema 1*1****. Từ đây ta định nghĩa hai loại đặc tính của schema: “schema order” và “schema defining length” (cấp schema và chiều dài xác định của schema).

+Cấp của schema: ký hiệu o(H)

Ví dụ: o(011*1**) = 4.

o(1******) = 1.

+Chiều dài định nghĩa của schema ; ký hiệu (H).

Ví dụ: (1**01**) = 4.

(0******) = 0.

Giả sử, tại thời điểm t, có m ví dụ (mẫu) của một schema H nào đó trong population A(t), ta viết: m = m(H,t).

Chú ý, tại các thời điểm t khác nhau, các schema H giống nhau có số lượng khác nhau.

Trong suốt quá trình reproduction (tái tạo) để tạo nên một thế hệ mới, một chuỗi sẽ được sao ra tùy thuộc vào vào “fitness” (sức khỏe, độ thích nghi) của nó. Chuỗi A_i sẽ có xác suất lựa chọn là : p_i =

Sau khi ccó thế hệ mới tại thời điểm (t+1), ta sẽ có m(H,t+1) đại diện cho schema H:

m(H, t+1)=m(H,t).n.

f(H): độ thích nghi (fitness) trung bình của các chuỗi đại diện cho cho schema H tại thời điểm t.

m(h,t+1) = m(H,t).; Trong đó : (=).

m sẽ tăng với những schema có giá trị fitness trên trung bình và có giá trị giảm fitness dưới trung bình (m là số mẫu của schemata H). Những hoạt động làm tăng giảm m dối với từng loại schema diễn ra một cách đồng thời. (song song với mỗi schemata). Schemata được tăng hay giảm phụ thuộc vào fitness của schemata so với mức fitness trung bình.

Giả sử, f(H) luôn luôn lớn hơn một lượng c.

với c = const f(H) = +c

m(H, t+1) = m(H,t).(+c) =(1+c). m(H, t)

m(H, t)= m(H, 0).(1+c)^t : tăng theo hàm mũ.

Tuy nhieen, chỉ reproduction thôi không đủ: Do chỉ copy lại các cấu trúc mà không có cái mới, nên phải lai tạo (crossover).

Crossover (lai tạo): Tạo ra cấu trúc mới nhưng ảnh hưởng rất ít đến sự thực hiện việc tái tạo (reproduction ) riêng lẽ. Nên schemata thích nghi tốt cũng tăng tuyến tính.

Vậy qua crossover, schema nào sẽ tăng, schema nào sẽ giảm?

Xét ví dụ:

A = 0 1 1 1 0 0 0

H= * 1 * * * * 0

H=* * * 1 0 * *

Nếu A được chọn để crossover, suy ra có 6 cách để chọn substring (chuỗi con). Ở đây, H₁ có cấu trúc dễ bị hủy hơn H₂ vì xác suất làm hỏng H₁ là 5/6; xác suất làm hỏng H₂ là 1/6. Khi bị hỏng, H sẽ truyền lại cho con cái (offspring) nguêyn vẹn sẽ ít hơn. Nhắc lại: (H) =5; (H) = 1.

Tổng quát :

Ta có thể tính được xác suất tồn tại của một schema khi lai l Ps (s: survival)

p_S = 1- ; p_c =1.

Nếu crossover được thực hiện bằng cách chọn ngẫu nhin với xác suất để ghép đôi là p_c thì:

p_S 1- p_c

Xét sự kết hợp của crossover với reproduction:

Giả sử có sự độc lập giữa crossover và reproduction:

m(H, t+1) m(H,t).[ 1-p.]

Vậy:

M phụ thuộc hai yếu tố: f(H) trên hay dưới mức trung bình, (H) dài hay ngắn.
Sự kết hợp hai yếu tố trên f(H) trên mức trung bình v(H) ngắn sẽ tồn tại và tăng theo hàm mũ.

Hoạt động cuối cùng là mutation (đột biến): là sự thay đổi ngẫu nhin một vị trí đơn (single position) với xác suất là p_m.

Để cho một schema H được sống sót, tất cả các vị trí đặc biệt (special position) phải được tồn tại. Do đó, vì một cái “allele” đơn tồn tại với xác suất l (1-p) và vì các đột biến là độc lập thống ke. Nên schema sẽ tồn tại khi mỗi vị trí có o(H) cố định trong schema tồn tại. Nhân xác suất này lên với o(H) lần ta có xác suất đột biến tồn tại (surving mhtation) = (1-p)^o(H)

Với p_m nhỏ, khả năng tồn tại schema:

Schema survival probability 1-p_m.o(H)

Kết luận: Shema sẽ nhận được một lượng (ước tính được) các bản sao (copies) qua các hoạt động reproduction, crossover, và mutation :

m(H,t+1)m(H,t).[1-p_c.-o(H).p_m]

1.4.4 Khảo sát bài toán ứng dụng với giải thuật di truyền

Để có thể hiểu được, cách để triển khai giải thuật di truyền vào các bài toán ứng dụng như thế nào, ta hãy xét bài toán “ Tìm giá trị lớn nhất của hàm nhiều biến “. Ví dụ : Tìm giá trị lớn nhất của hàm nhiều biến : F=f (x,y,z) Với x,y,z Î[ a,b].

Khởi tạo dân số ban đầu

Chọn N,G,p_c,p_m.K=0

Lưu đồ thuật giải

Hình 1.3. Sơ đồ bài toán ứng dụng giải thuật di truyền

Phân tích

Tạo dân số ban đầu: có kích thước N

Mỗi cá thể đại diện cho một giải pháp ( một tập giá trị của x, y,z)

A_i ={x_i , y_i , z_i } ; 1£ i £ N

Mỗi giải pháp A_i được mã hóa thành một chuỗi các số nhị phân B_i đại diện cho một nhiễm sắc thể như sau:

Giả sử, số bit mã hóa cho mỗi biến x,y,z là n. Ta có:

a « 0 0 0 ..0 ( có n số 0)

b « 1 1 1 ...1 ( có n số 1)

a < c < b « số nhị phân n bit tương ứng trong khoảng (0 – 2ⁿ-1)

ÞB_j = t₁t₂ ...t_nt_1+nt_2+n...t_2nt_1+2nt_2+2n....t_3n.Trong đó t ={0,1}.

+N cá thể B_itạo nên dân số có kích thước N.

+Chiều dài của 1 cá thể (nhiễm sắc thể) là: L = 3*n

ÞKhông gian giải pháp là: 2^3*n

+Độ phân giải:

D =

-Xây dựng hàm mục tiêu (hàm tính giá trị thích nghi):

F_fitness =f(x,y,z)

-Reproduction:

Chọn lọc để tái tạo, tạo bồn lai (mating pool) bằng hàm đối tượng.

-Crossover:

Các cá thể được chọn để ghép lai theo xác suất p_c

+Chọn hai cá thể bất kỳ trong mating pool:

+Chọn vị trí lai ( có thể là một vị trí hay nhiều hơn)

+Trao đổi đoạn

Ví dụ: Trong trường hợp n=4,L=12, crossover tại một điểm.Vị trí lai là 6.

B = 0 0 1 0 1 1 0 0 1 1 0 1

B’= 1 0 1 0 1 0 1 1 0 0 1 1

Þ B = 0 0 1 0 1 1 1 1 0 0 1 1

B’= 1 0 1 0 1 0 0 0 1 1 0 1

-Mutation:

Một bit trong cá thể có xác suất thay đổi là p_m .

c.Nhận xét

Số bit mã hóa càng cao thì không gian giải pháp càng lớn (2^3*n), nhưng độ phân giải càng nhỏ, kết quả thu được càng chính xác.
Áp dụng GA phải biết trước khoảng giá trị của các biến x,y,z.
Các thông số phải chọn là:số thế hệ G, kích thước dân số N, xác suất lai p_c, xác suất đột biến p_m.

1.4.5. Các ứng dụng của giải thuật di truyền

Hiện nay, GA đã được hòan thiện nhiều hơn, được nghiên cứu cải thiện và phối hợp với các cách giải quyết vấn đề khác nhau nên đã đạt được vô số thành tựu to lớn. Ta có thể kể ra đây một vài thành tựu nghiên cứu và ứng dụng:

Trong sinh học:

Mô phỏng sự tiến hóa của những tập hợp tổ chức từ tế bào đơn (Rosenberg- 1967).
GA thích ứng với những cấu trúc tương ứng với khả năng có sẵn thức ăn theo không gian và thời gian ( Sannier and Goodman – 1987).

Lĩnh vực máy tính:

Giải thuật nhóm dựa trên GA ( Raghavan and Birchard –1979).
Nỗ lực xác định sự tự động theo xác suất ( Gerardy –1982).
Mô tả tài liệu thích ừng sử dụng GA. (Gordon –1984)
Tìm kiếm bằng GA cho hàm ước lượng trò chơi (Rendel –1985).

Kỹ thuật và nghiên cứu:

Thiết kế bộ lọc thích nghi sử dụng một Ga đơn giản (Etter, Hicks, and Cho –1982)
Tối ưu hóa trạng thái quá độ và xác lập của ống dẫn gas sử dụng GA (GoldBerg – 1983).
Sắp xếp mạch VLSI thông qua GA (Davis and Smith – 1985).
Tối ưu hóa trạng thái xác lập, on-off của hệ thống ống bơm dầu sử dụng GA (Goldberg and Kuo –1985)..
Thiết kế cấu hình keyboard sử dụng GA (Glover –1986).
Tối ưu hóa kích thước liên kết mạng truyền thông dùng GA và các công cụ mới (Davis and Coombs – 1987).
Sự chọn lựa của bộ dò trong việc phân loại những bức ảnh nổi tiếng bằng GA (Englander – 1985).
Tìm kiếm cho bộ dò tìm đặc tính ảnh bằng GA ( Gillies – 1985).
Sự thực hiện song song mô phỏng của việc sắp xếp tuyến tính tối ưu ( Cohoon, Hedge, Martin, Richards – 1987).
GA song song chạy trên bộ xử lý 64-NCUBE (Tanese – 1987).

Lĩnh vực vật lý.

Giải phương trình không tuyến tính với GA cho việc thích ứng những mặt điện thế (Shaefer -1985).

Lĩnh vực xã hội:

Dùng GA trong việc tạo mẫu hành vi săn theo đàn thời tiền sử (Reynolds-1979).
Mô phỏng sự tiến hóa của tiêu chuẩn hành vi dùng GA (Axelrod- 1985).
Giải quyết những khó khăn lặp đi lặp lại của tù nhân bằng GA (Axelrod- 1985).
Sự thực hiện những giải thuật Genetictic thích ứng –mờ ( fuzzy-adaptive GA) trong môi trường MatLab (R. Matousek – 1998)

(CÒN TIẾP)

» Tin mới nhất: