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:

1.      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”.

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

3.      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:

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

o   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].

a.     

Khởi tạo dân số ban đầu Chọn N,G,pc,pm.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

 

b.      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+n t_2+n...t_2nt_1+2n t_2+2n....t_3n. Trong đó t ={0,1}.

+N cá thể B_i tạ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)