Giới thiệu thuật toán Di truyền
1. Sự chọn lọc tự nhiên và Di truyền
- Trong một khu nhà bỏ trống có nhiều mèo và chuột. Ban đầu chuột có hai loại: lông trắng hoặc đen. Sau thời gian sống với mèo ban đêm chuột đen ít bị mèo nhìn thấy nên sống lâu hơn và sinh đẻ thêm do đó phát triển, trong đó chuột trắng ngày càng tuyệt giống vì bị mèo ăn thịt và không có nhiều để sinh đẻ thêm.
- Trong thực tế chỉ có những sinh vật biết tiến hóa để thích nghi với hoàn cảnh sẽ tồn tại và phát triển
- Trong tự nhiên, các cá thể khỏe, có khả năng thích nghi tốt với môi trường sẽ được tái sinh và nhân bản ở các thế hệ sau.
- Mỗi cá thể có một cấu trúc gen đặc trưng cho phẩm chất của cá thể đó, gọi là nhiễm sắc thể (chroniosome). Như vậy mỗi nhiễm sắc thể được tạo thành từ các đơn vị gen.
- Trong quá trình sinh sản, các cá thể con thừa hưởng các phẩm chất của cả cha và mẹ, cấu trúc gen của nó mang một phần cấu trúc gen của cha và mẹ (gọi là lai ghép).
- Trong quá trình tiến hóa, có thể xảy ra hiện tượng đột biến, nghĩa là trong cấu trúc gen của cá thể con có thể chứa các gen mà cả cha và mẹ đều không có.
- Lai ghép và đột biến được gọi chung là di truyền.
- Trong quá trình tiến hóa của một giống loài, có các quần thể, mỗi một quần thể sẽ gồm nhiều cá thể. Một quần thể ứng với một giai đoạn phát triển gọi là một thế hệ.
- Sự chọn lọc tự nhiên và di truyền là quá trình biến đổi các thế hệ theo xu hướng các thế hệ càng về sau thì càng “khỏe mạnh” và “thích nghi” tốt với môi trường nhiều hơn.
- Môi trường thay đổi dẫn đến thích nghi cao hơn, do đó đặc trưng của quần thể cũng có thể thay đổi theo hướng “cao hơn” hoặc thậm chí ngược lại hoàn toàn là bị tuyệt chủng.
.jpg)
- Genetic Algorithms tạm dịch là Thuật giải di truyền (ngắn gọn gọi là GA) bắt nguồn từ ý niệm tiến hóa để tồn tại và phát triển trong tự nhiên.
- GA là phương thức giải quyết vấn đề bắt chước lối hành xử của con người để tồn tại và phát triển. Nó giúp tìm ra giải pháp tối ưu hay tốt nhất trong điều kiện thời gian và không gian cho phép.
- GA xét đến toàn bộ các giải pháp, bằng cách xét trước nhất một số giải pháp sau đó loại bỏ những thành phần không thích hợp và chọn những thành phần thích nghi hơn để tạo sinh và biến hóa nhằm mục đích tạo ra nhiều giải pháp mới có hệ số thích nghi ngày càng cao
- Hệ số thích nghi để dùng làm tiêu chuẩn đánh giá các giải pháp.
2. Thuật toán di truyền (TTDT - GA)
- TTDT cho máy tính thực hiện là bắt trước sự chọn lọc tự nhiên và di truyền nhằm thực hiện bài toán dự báo với một mục đích nào đấy không nhất thiết ứng dụng trong lĩnh vực y học. TTDT đã có nhiều thành công trong lĩnh vực tối ưu (optimization) và học máy (machine learning).
- Trong TTDT, mỗi một cá thể được mã hóa bởi một cấu trúc dữ liệu (tức là cách biểu diễn nhiễm sắc thể trong máy tính) mô tả một cấu trúc gen cho từng cá thể.
- Trong TTDT cổ điển, nhiễm sắc thể là một chuỗi nhị phân. Nghĩa là mỗi một cá thể là một chuỗi nhị phân.
- TTDT sử dụng các toán tử sau đây để làm việc trên các quần thể (để bắt chước sự chọn lọc và di truyền của tự nhiên trong việc biến đổi các thế hệ):
+ Toán tử tái sinh (reproduction), còn gọi là toán tử chọn lọc (selection). Các cá thể tốt được chọn lọc để đưa vào thế hệ sau. Sự chọn lọc này căn cứ vào độ thích nghi với môi trường của mỗi cá thể. Vậy ta cần đến một hàm cho biết độ thích nghi ứng với từng cá thể, hàm này gọi là hàm thích nghi (fitness function)
+ Toán tử lai ghép (crossover). Hai cá thể cha và mẹ trao đổi các gen với nhau để tạo ra cá thể con.
+ Toán tử đột biến (mutation). Một cá thể thay đổi một số gen để biến đổi thành một cá thể mới.
Tất cả các toán tử trên khi thực hiện đều mang tính ngẫu nhiên.
Cấu trúc cơ bản của thuật toán di truyền như sau:
Procedure Genetic_Algorithm;
Begin
t =0;
Khởi tạo thế hệ ban đầu P(t);
Đánh giá P(t) (theo hàm thích nghi)
Repeat
(1) t = t + 1;
(2) Sinh ra thế hệ mới P(t) từ thế hệ P(t-1) bởi
(i) Chọn lọc;
(ii) Lai ghép;
(iii) Đột biến;
(3) Đánh giá P(t) (theo hàm thích nghi);
Until điều kiện kết thúc được thỏa mãn;
Procedure Genetic_Algorithm;
Begin
t =0;
Khởi tạo thế hệ ban đầu P(t);
Đánh giá P(t) (theo hàm thích nghi)
Repeat
(1) t = t + 1;
(2) Sinh ra thế hệ mới P(t) từ thế hệ P(t-1) bởi
(i) Chọn lọc;
(ii) Lai ghép;
(iii) Đột biến;
(3) Đánh giá P(t) (theo hàm thích nghi);
Until điều kiện kết thúc được thỏa mãn;
End;
Trong thủ tục trên, điều kiện kết thúc vòng lặp có thể là một số thế hệ đủ lớn nào đó, hoặc độ thích nghi của cá thể tốt nhất trong các thế hệ kế tiếp nhau thì khác nhau không đáng kể. Khi thuật toán dừng, cá thể tốt nhất trong thế hệ cuối được chọn làm “nghiệm” cần tìm. Nghiệm này thường dùng để dự báo.
Tiếp theo ta sẽ nghiên cứu về các toán tử chọn lọc, di truyền (lai ghép và đột biến) trong các lệnh (i), (ii), (iii) của thuật toán di truyền.
3. Toán tử Chọn lọc
Việc chọn lọc các cá thể từ một quần thể dựa vào độ thích nghi của mỗi cá thể. Các cá thể có độ thích nghi cao có nhiều khả năng được chọn lựa (những cá thể khỏe mạnh có nhiều khả năng được phối giống). Hàm thích nghi chỉ cần là một hàm thực dương, nó có thể không tuyến tính, không liên tục, không khả vi.
Giả sử thế hệ hiện thời là P(t) gồm n cá thể { x[1], x[2], ..., x[n] }.
Số n được gọi là cỡ của quần thể.
Với cá thể x[*], ta tính độ thích nghi f(x[*]). Tính tổng độ thích nghi của toàn bộ quần thể:
F = f(x[1]) + f(x[2]) + ... + f(x[n]);
Mỗi lần chọn lọc, ta thực hiện hai bước sau:
Bước 1: Sinh một giá trị thích nghi ngẫu nhiên là một số thực q trong khoảng (0, F);
Bước 2: x[k] là cá thể được chọn nếu k là số nhỏ nhất sao cho tổng độ thích nghi của k cá thể đầu tiên không nhỏ hơn q, tức là f(x[1]) + f(x[2]) + ... + f(x[k]) >= q.
Rõ ràng với cách chọn này, các cá thể có độ thích nghi càng cao (gây ra tổng lớn hơn q) thì càng được chọn. Các cá thể có độ thích nghi cao có thể có một hay nhiều bản sao, các cá thể có độ thích nghi thấp có thể không có mặt trong thế hệ sau (nó bị chết đi).
4. Toán tử lai ghép
Trên các cá thể được chọn lọc (sau khi thực hiện xong toán tử chọn lọc), ta tiến hành toán tử lai ghép. Với cỡ của quần thể là n, ta đưa ra một xác suất lai ghép là pc. Xác suất này đưa ra hy vọng là có n.pc cá thể được lai ghép.
Với mỗi cá thể, ta thực hiện hai bước sau đây:
Bước 1: Sinh ra một xác suất lai ghép là số thực r nào đó trong đoạn [0, 1]
Bước 2: Nếu r < pc thì cá thể đó được chọn để lai ghép
Từ các cá thể được chọn để lại ghép, ta cặp đôi chúng một cách ngẫu nhiên. Trong trường hợp nhiễm sắc thể là các chuỗi nhị phân có độ dài cố định, giả sử là m, ta có thể thực hiện phép lai ghép như sau:
Với mỗi cặp, sinh ra một vị trí ngẫu nhiên làm điểm bắt đầu ghép là một số nguyên p trong đoạn [0, m-1].
Tổng quát, giả sử có hai cặp nhiễm sắc thể của hai cá thể được chọn lai ghép:
a = (a[1], ..., a[p], a[p+1], ..., a[m])
b = (b[1], ..., b[p], b[p+1], ..., b[m])
Cặp này được thay thế bởi hai đoạn con của nhau từ vị trí thứ p+1:
a’ = (a[1], ..., a[p], b[p+1], ..., b[m])
b’ = (b[1], ..., b[p], a[p+1], ..., a[m])
5. Toán tử đột biến
Ta thực hiện đột biến trên các cá thể sau khi đã lai ghép. Đột biến là thay đổi trạng thái của một số gen nào đó trong nhiễm sắc thể. Một gen chịu một xác suất đột biến là pm. Xác suất đột biến pm do ta xác định và là xác suất thấp.
Tổng quát với nhiễm sắc thể là chuỗi nhị phân. Với mỗi vị trí i trong nhiễm sắc thể:
a = (a[1], ..., a[p], a[p+1], ..., a[m])
ta sinh ra một số thực ngẫu nhiên pi trong đoạn [0,1]. Đột biến a được biến thành á như sau:
a’ = (a’[1], ..., a’[*], ..., a’[m])
trong đó:
a’[*] = a[*] nếu pi >= pm và a’[*] = 1 – a[*] nếu pi < pm.
Sau quá trình chọn lọc, lai ghép, đột biến, một thế hệ mới được sinh ra. Công việc còn lại của thuật toán là chỉ việc lặp lại các bước trên.
Mỗi lần chọn lọc, ta thực hiện hai bước sau:
Bước 1: Sinh một giá trị thích nghi ngẫu nhiên là một số thực q trong khoảng (0, F);
Bước 2: x[k] là cá thể được chọn nếu k là số nhỏ nhất sao cho tổng độ thích nghi của k cá thể đầu tiên không nhỏ hơn q, tức là f(x[1]) + f(x[2]) + ... + f(x[k]) >= q.
Rõ ràng với cách chọn này, các cá thể có độ thích nghi càng cao (gây ra tổng lớn hơn q) thì càng được chọn. Các cá thể có độ thích nghi cao có thể có một hay nhiều bản sao, các cá thể có độ thích nghi thấp có thể không có mặt trong thế hệ sau (nó bị chết đi).
4. Toán tử lai ghép
Trên các cá thể được chọn lọc (sau khi thực hiện xong toán tử chọn lọc), ta tiến hành toán tử lai ghép. Với cỡ của quần thể là n, ta đưa ra một xác suất lai ghép là pc. Xác suất này đưa ra hy vọng là có n.pc cá thể được lai ghép.
Với mỗi cá thể, ta thực hiện hai bước sau đây:
Bước 1: Sinh ra một xác suất lai ghép là số thực r nào đó trong đoạn [0, 1]
Bước 2: Nếu r < pc thì cá thể đó được chọn để lai ghép
Từ các cá thể được chọn để lại ghép, ta cặp đôi chúng một cách ngẫu nhiên. Trong trường hợp nhiễm sắc thể là các chuỗi nhị phân có độ dài cố định, giả sử là m, ta có thể thực hiện phép lai ghép như sau:
Với mỗi cặp, sinh ra một vị trí ngẫu nhiên làm điểm bắt đầu ghép là một số nguyên p trong đoạn [0, m-1].
Tổng quát, giả sử có hai cặp nhiễm sắc thể của hai cá thể được chọn lai ghép:
a = (a[1], ..., a[p], a[p+1], ..., a[m])
b = (b[1], ..., b[p], b[p+1], ..., b[m])
Cặp này được thay thế bởi hai đoạn con của nhau từ vị trí thứ p+1:
a’ = (a[1], ..., a[p], b[p+1], ..., b[m])
b’ = (b[1], ..., b[p], a[p+1], ..., a[m])
5. Toán tử đột biến
Ta thực hiện đột biến trên các cá thể sau khi đã lai ghép. Đột biến là thay đổi trạng thái của một số gen nào đó trong nhiễm sắc thể. Một gen chịu một xác suất đột biến là pm. Xác suất đột biến pm do ta xác định và là xác suất thấp.
Tổng quát với nhiễm sắc thể là chuỗi nhị phân. Với mỗi vị trí i trong nhiễm sắc thể:
a = (a[1], ..., a[p], a[p+1], ..., a[m])
ta sinh ra một số thực ngẫu nhiên pi trong đoạn [0,1]. Đột biến a được biến thành á như sau:
a’ = (a’[1], ..., a’[*], ..., a’[m])
trong đó:
a’[*] = a[*] nếu pi >= pm và a’[*] = 1 – a[*] nếu pi < pm.
Sau quá trình chọn lọc, lai ghép, đột biến, một thế hệ mới được sinh ra. Công việc còn lại của thuật toán là chỉ việc lặp lại các bước trên.