Luận văn Ứng dụng các phương pháp tính toán tiến hóa để giải quyết bài toán tối ưu công thức dược phẩm

10 CHƯƠNG 2. TỔNG QUAN VÀ CƠ SỞ LÝ THUYẾT 2.1. Kỹ thuật tính toán tiến hóa [7], [9] Tính toán tiến hóa là kỹ thuật tính toán dựa trên nguyên lý tiến hóa của quá trình chọn lọc tự nhiên trong thuyết tiến hóa của Darwin. Các kỹ thuật tính toán tiến hóa bao gồm: Chiến lược tiến hóa (evolution strategies), lập trình tiến hóa (evolutionary programming), thuật giải di truyền (genetic algorithms) và lập trình di truyền (genetic programming). Trong tự nhiên sự tiến hóa là một quá trình không điều khiển, các sinh vật tốt hơn sẽ thích nghi nhiều hơn với môi trường, sinh vật sống sót sẽ sinh sản... Đó là quá trình chọn lọc và tiến hóa tự nhiên. Trong cơ thể con người và sinh vật nói chung bao gồm nhiều tế bào, Trong mỗi tế bào có chứa các hoá chất liên quan đến tính di truyền, đó là các nhiễm sắc thể (chromosome). Các nhiễm sắc thể là các chuỗi ADN, các gen. Mỗi gen mã hóa một loại protein riêng biệt, nói một cách đơn giản, mỗi gen mã hóa một đặc điểm của cơ thể, ví dụ : màu mắt, màu da… Những thiết lập có thể cho một đặc điểm được gọi là các gen tương ứng (allele), ví dụ : màu mắt thì có thể là mắt xanh hay mắt đen hay mắt nâu. Tất cả các nhiễm sắc thể trong một cơ thể được gọi là bộ gen (genome). Một tập hợp riêng biệt của các gen trong một bộ gen được gọi là kiểu gen (genotype). Kiểu gen với quá trình phát triển sau này cho ra một kiểu hình (phenotype) của cơ thể, các đặc điểm vật lý và trí tuệ… Ý tưởng áp dụng các nguyên tắc của sự tiến hóa trong tự nhiên vào hệ thống trí tuệ nhân tạo đã được đề cập cách đây khoảng 3 thập niên. Hình 2.1 mô tả quá trình xử lý cơ bản của các kỹ thuật tính toán tiến hóa và có thể được chi tiết thành các bước sau: Bước 1: Với bài toán cụ thể, khởi tạo ngẫu nhiên tập các giải pháp cho bài toán. 11 Bước 2: Đánh giá các giải pháp của bài toán bằng cách sử dụng các hàm tính giá trị thích nghi (fitness). Ứng với mỗi giải pháp sẽ có 1 hệ số thích nghi tương ứng. Nếu 1 trong các giải pháp chính là kết quả cần tìm, đi đến Bước 6. Bước 3: Dựa trên hệ số thích nghi của các giải pháp để thực hiện sự tạo sinh (reproduction) và biến hoá các giải pháp. Các phương thức biến hóa gồm: lai ghép (cross over), đột biến (mutation). Bước 4: Tính các hệ số thích nghi cho các giải pháp mới và loại bỏ những giải pháp kém nhất để chỉ còn giữ lại một số nhất định các giải pháp tốt. Bước 5: Nếu chưa tìm được giải pháp tối ưu hay tương đối khá nhất hay chưa hết hạn kỳ ấn định, trở lại Bước 3 để tìm giải pháp mới. Bước 6: Tìm được giải pháp tối ưu hoặc nếu thời gian cho phép đã chấm dứt thì báo cáo kết quả tìm được. Hình 2.1. Minh họa quá trình chọn lọc của tính toán tiến hóa Tạo quần thể ban đầu Chọn phần tử tốt nhất Đánh giá hàm mục tiêu Kết thúc Lai ghép Tạo quần thể mới Đạt Không đạt Bắt đầu Sinh sản Đột biến Kiểm tra điều kiện tối ưu Thao tác tiến hóa Formatted: Line spacing: 1.5 lines Formatted: Line spacing: 1.5 lines Formatted: Noi dung, Widow/Orphan control Formatted: Indent: Left: -7.1 pt, Right: -7.15 pt Formatted: Vietnamese Deleted: Tạo quần thể mới Deleted: Deleted: Deleted: Lai ghép Deleted: Deleted: Deleted: Lai ghép Deleted: Deleted: 12 2.2. Thuật giải di truyền (Genetic Algorithms) [1], [3], [7], [9] 2.2.1. Khái niệm Đến sau năm 1970 thuật giải di truyền (Genetic Algorithms – gọi tắt là GA) chính thức được giới thiệu bởi John Holland (Đại học Michigan) dựa trên nền tảng của tính toán tiến hoá. GA là giải thuật với mục tiêu không phải là đưa ra lời giải chính xác, tối ưu, mà là đưa ra lời giải tương đối tối ưu (tối ưu trong điều kiện và thời gian cho phép). Thuật giải di truyền được thực hiện trên quần thể bao gồm các cá thể là các lời giải cho bài toán. Có hai cách để biểu diễn một lời giải (một cá thể trong quần thể) là sử dụng chuỗi nhị phân hay là chuỗi các số thực với một chiều dài cố định tùy thuộc vào lĩnh vực của bài toán, giống như mỗi cá thể được quy định bằng một bộ gen. Bảng 2.1: Hai cách biểu diễn một lời giải trong thuật giải di truyền Chuỗi nhị phân Chuỗi số thực Cá thể A: 1101100100101101 Cá thể B: 0110100110001100 Cá thể A: 4.2 1.5 0.8 71.6 Cá thể B: 16.7 5.2 1.8 50.9 2.2.2. Cấu trúc Các bước thực hiện thuật giải di truyền: Ban đầu, ta sẽ phát sinh 1 số lượng lớn (giới hạn, thường là khoảng 1000 ) các cá thể có gen ngẫu nhiên (phát sinh 1 tập hợp các chuỗi bit ngẫu nhiên), được gọi là quần thể ban đầu. Sau đó, ta sẽ xác định được độ thích nghi (fitness : độ tốt của lời giải) của từng cá thể. Để cải thiện tính thích nghi của quần thể, người ta tìm cách tạo ra quần thể mới bằng 2 thao tác : 13 • Thao tác 1 : Sao chép nguyên mẫu 1 nhóm các cá thể tốt (có độ thích nghi cao) từ thế hệ trước rồi đưa sang thế hệ sau (selection). • Thao tác 2 : Tạo các cá thể mới bằng cách thực hiện các thao tác sinh sản trên 1 số cá thể được chọn từ thế hệ trước. Có 2 loại thao tác sinh sản : lai ghép (crossover) với xác suất lai ghép pc và đột biến (mutation) với xác suất đột biến pm. Nếu quần thể ban đầu chưa phong phú và phù hợp, thì chọn lọc và lai ghép khó có thể đưa ra lời giải tối ưu. Thao tác đột biến sẽ giúp giải quyết vấn đề này. Đột biến chỉ nên xảy ra với tần suất rất thấp ( khoảng 0.5%) vì có thể gây ra xáo trộn và làm mất đi những cá thể đã chọn lọc và lai ghép có độ thích nghi cao, dẫn đến thuật toán không còn hiệu quả. Thế hệ mới được tạo ra lại được xử lý như thế hệ trước (xác định độ thích nghi và tạo thế hệ mới) cho đến khi có 1 cá thể đạt được giải pháp mong muốn hay đạt đến thời gian tới hạn. Có hai thao tác cơ bản gây ảnh hưởng đến lời giải cuối cùng của thuật giải di truyền là lai ghép và đột biến. Việc lựa chọn và thi hành những thao tác này tùy thuộc vào cách biểu diễn cá thể và cũng tùy thuộc vào từng bài toán. 2.2.2.1. Lai ghép Là việc chọn lựa những đoạn gen của các cá thể cha mẹ và tạo thành các cá thể con. Lai ghép đơn điểm là quy tắc lai ghép đơn giản nhất, được thực hiện như sau: • Đầu tiên chọn hai cá thể cha mẹ A,B. • Xác định một vị trí lai ghép k ngẫu nhiên thuộc đoạn [2, N-1] với N là chiều dài gen. Điểm k này chia gen của cha mẹ A thành A1, A2 và B thành B1, B2. • Hai gen mới được tạo ra là (A1 B2) và (B1 A2). 14 Bảng 2.2: Thao tác lai ghép đơn điểm trong giải thuật di truyền. Chuỗi nhị phân k=9 Chuỗi số thực k=3 Cá thể A: 1101100100101101 Cá thể B: 0110100110001100 Cá thể con 1: 1101100100001100 Cá thể con 2: 0110100110101101 Cá thể A: 4.2 1.5 0.8 71.6 5.9 Cá thể B: 16.7 5.2 1.8 50.9 8.2 Cá thể con 1: 4.2 1.5 0.8 50.9 8.2 Cá thể con 2: 16.7 5.2 1.8 71.6 5.9 Ngoài ra, còn có thêm một số kỹ thuật lai ghép khác: - Lai ghép đa điểm: Là 1 dạng tổng quát của lai ghép đơn điểm. Thay vì chọn 1 điểm lai ghép, ta chọn nhiều điểm lai ghép k1, k2, k3…. Bảng 2.3: Thao tác lai ghép đa điểm trong giải thuật di truyền. Chuỗi nhị phân k1=3, k2=7 Chuỗi số thực k1=2, k2=4 Cá thể A: 1101100100101101 Cá thể B: 0110100110001100 Cá thể con 1: 1100100100101101 Cá thể con 2: 0111100110001100 Cá thể A: 4.2 1.5 0.8 71.6 5.9 Cá thể B: 16.7 5.2 1.8 50.9 8.2 Cá thể con 1: 4.2 1.5 1.8 50.9 5.9 Cá thể con 2: 16.7 5.2 0.8 71.6 8.2 - Lai ghép mặt nạ: Hai cá thể cha mẹ liên kết với mặt nạ M (là chuỗi nhị phân có cùng chiều dài với A, B). Giá trị bit của mặt nạ sẽ quyết định thành phần gen nào của cá thể con sẽ được trích ra từ gen của cha mẹ. o Giá trị bit thứ i = 1 thì thành phần thứ i trong gen của cá thể con thứ nhất được sao chép từ thành phần gen của cá thể cha mẹ thứ nhất. o Ngược lại thì thành phần thứ i trong gen của cá thể con thứ nhất sẽ được sao chép từ thành phần gen của cá thể cha mẹ thứ hai. o Tương tự cho cá thể con thứ hai. 15 Bảng 2.4: Thao tác lai ghép mặt nạ trong giải thuật di truyền. Chuỗi nhị phân Chuỗi số thực Cá thể A: 1101100100101101 Cá thể B: 0110100110001100 Mặt nạ: 1000001000101010 Cá thể con 1: 1110100110101100 Cá thể con 2: 0101100100001101 Cá thể A: 4.2 1.5 0.8 71.6 5.9 Cá thể B: 16.7 5.2 1.8 50.9 8.2 Mặt nạ: 1 0 1 0 1 Cá thể con 1: 4.2 5.2 0.8 50.9 5.9 Cá thể con 2: 16.7 1.5 1.8 71.6 8.2 2.2.2.2. Đột biến Là việc chọn ra một hay nhiều gen trong nhiễm sắc thể và thay đổi giá trị của chúng. Nếu nhiễm sắc thể là một chuỗi nhị phân thì thao tác đột biến sẽ làm thay đổi một vài vị trí được chọn ngẫu nhiên từ 0 thành 1 hay từ 1 thành 0. Nếu nhiễm sắc thể là một chuỗi số thực thì đột biến sẽ làm sẽ thay thế giá trị của một số vị trí được chọn ngẫu nhiên bằng các giá trị khác thuộc giới hạn cho phép của bài toán. Bảng 2.5: Thao tác đột biến trong giải thuật di truyền. Chuỗi nhị phân Chuỗi số thực Cá thể A: 10010110 Cá thể con: 10110110 Cá thể A: 4.2 1.5 0.8 71.6 Cá thể con A: 4.2 1.5 1.2 71.6 2.2.2.3. Các yếu tố khác của thuật giải di truyền. Trong GA, lai ghép và đột biến là những thao tác quan trọng nhất. Tuy nhiên, để áp dụng thành công GA cho một bài toán, việc lựa chọn các nhân tố khác như chọn lọc, tạo sinh và tính độ thích nghi phù hợp cũng rất cần thiết. Phương pháp chọn lọc thực hiện việc chọn ra các cá thể trong quần thể để thực hiện các thao tác lai ghép, đột biến hay tạo sinh. Tạo sinh là thao tác sinh sản đơn giản nhất, thực hiện việc sao 16 chép một cá thể từ thế trước sang thế hệ sau. Hàm tính giá trị thích nghi dùng để đánh giá độ tốt của một cá thể đối với môi trường của bài toán. Mọi cá thể trong quần thể được gán cho một giá trị thích nghi, để dựa vào đó, phương pháp chọn lọc sẽ chọn ra những cá thể để thực hiện lai ghép, đột biến hay tạo sinh. 2.3. Lập trình di truyền (Genetic Programming) [4], [6], [7], [8], [10], [11] Lập trình di truyền (Genetic Programming – gọi tắt là GP) là một kỹ thuật với ý tưởng chính là các chương trình máy tính có khả năng tự tiến hóa để thực hiện một công việc nào đó, được đưa ra bởi Koza vào năm 1992. Kỹ thuật này cung cấp một nền tảng cho việc tạo ra những chương trình máy tính một cách tự động. Lập trình di truyền đạt được mục đích này bằng việc phát sinh ra một quần thể các chuơng trình máy tính, sử dụng thuyết tiến hóa của Darwin để chọn ra chương trình tốt nhất để thực hiện công việc. Kỹ thuật này được phát triển dựa trên thuật giải di truyền của Holland, nên nó cũng bao gồm tất cả các thao tác và hàm chức năng được sử dụng trong thuật giải di truyền. GP khác những thuật toán tiến hóa khác ở phạm vi ứng dụng: những thuật toán tiến hóa khác thường được áp dụng cho các bài toán tìm lời giải tối ưu, trong khi GP được xếp vào nhóm các thuật toán máy học: tìm mô hình phù hợp nhất dựa trên dữ liệu đưa vào. Hình 2.2. Minh họa một cá thể trong kỹ thuật lập trình di truyền (GP) Cá thể này biểu diễn công thức A*B + C + * A B C Phép tính (Nodes) Nút lá (Terminals) 17 Tiến trình thực hiện của GP được thể hiện trong hình sau: Hình 2.3. Sơ đồ hoạt động của GP Điểm khác nhau chính giữa GP và GA là cấu trúc dữ liệu được sử dụng để biểu diễn một cá thể trong quần thể. Trong GA, người ta thường sử dụng chuỗi nhị phân hay vector các số thực với chiều dài cố định, còn trong GP thì sử dụng cấu trúc cây Số thế hệ = Số thế hệ + 1 Số thế hệ = 0 Khởi tạo ngẫu nhiên quần thể ban đầu Đạt điều kiện dừng Tính độ thích nghi của từng cá thể trong quần thể Số cá thể = 0 Lựa chọn thao tác di truyền dựa vào xác suất Chọn 2 cá thể dựa trên độ thích nghi Thực hiện lai ghép Thêm 2 cá thể con vào quần thể mới Số cá thể = Số cá thể + 2 Trình bày kết quả Kết thúc Chọn 1 cá thể dựa trên độ thích nghi Chọn 1 cá thể dựa trên độ thích nghi Thực hiện đột biến Thêm cá thể đột biến vào quần thể Sao chép cá thể ban đầu vào quần thể Số cá thể = Số cá thể + 1Số cá thể = Số cá thể + 1 Số cá thể = M Có Không Có Không Thực hiện sinh sản Deleted: ¶ 18 (tree) với chiều cao không cố định, đó là những chương trình mà khi thực thi sẽ là những ứng cử viên cho lời giải của bài toán. Có hai phần chính trong một mô hình của GP, đó là các node và terminal như được minh họa trong Hình 2.2. Các node (nút trong) là các phép tính, trong khi các terminal (nút lá) là các giá trị hằng số hay các biến. Việc lựa chọn các node và các terminal là một trong những thao tác chính trong GP để tìm được lời giải cho vấn đề. Có 5 bước chính trong việc sử dụng GP là: - Lựa chọn các terminal. - Lựa chọn các phép tính (node). - Định nghĩa hàm tính giá trị thích nghi. - Lựa chọn các tham số điều khiển của thuật toán. - Xác định điều kiện dừng. Các phép tính có thể được sử dụng là: - Các phép tính số học như +, - , *, /. - Các hàm toán học như sin, cos, exp, log. - Các toán tử logic như AND, OR, NOT. - Các toán tử điều kiện như if – then – else. - Các hàm thực hiện lặp như do – while. - Các hàm thực hiện đệ quy. - Và những hàm đặc biệt khác được định nghĩa trong phạm vi của bài toán. GP phát sinh ra những chương trình máy tính để giải quyết bài toán bằng việc thực hiện các bước sau: - Tạo quần thể ban đầu bằng việc kết hợp ngẫu nhiên các phép tính và các terminal của bài toán. - Lặp lại các bước con sau cho đến khi đạt điều kiện dừng: i. Thực thi từng chương trình trong quần thể và gán cho nó 1 giá trị thích nghi dựa vào hàm tính giá trị thích nghi. ii. Tạo ra quần thể các chương trình mới bằng việc áp dụng các thao tác sau: 19 ƒ Sinh sản: sao chép chương trình được chọn vào quần thể mới. ƒ Lai ghép: Tạo ra hai chương trình mới từ hai chương trình có sẵn bằng việc hoán vị một phần chương trình ban đầu tại một nút được chọn ngẫu nhiên trong từng chương trình. ƒ Đột biến: Tạo ra một chương trình mới từ một chương trình có sẵn bằng cách thay thế một phần chương trình được chọn ngẫu nhiên. - Chương trình được đánh giá là tốt nhất sau khi thực hiện sẽ là kết quả của thuật toán. Đây cũng chính là lời giải của bài toán. 2.3.1. Tạo cấu trúc cây: Để tạo một cấu trúc cây, GP lựa chọn ngẫu nhiên 1 phép tính hay 1 terminal từ tập các phép tính và tập các terminal của bài toán. Tuy nhiên, sự lựa chọn cũng phải dựa vào tập các tham số điều khiển và phương pháp để phát sinh một cá thể. Có 3 phương pháp có thể dùng để tạo một cấu trúc cây ngẫu nhiên (xem Hình 2.4) (a) (b) (c) Hình 2.4. Cây được tạo thành bởi phương pháp (a)Full, (b) Half - and – Half, (c) Grow (với chiều cao là 3). Full: Phương pháp này tạo nên những cây đầy đủ, là những cây có tất cả các terminal ở mức lớn nhất của cây. Grow: Lựa chọn ngẫu nhiên các phép tính và các terminal cho nút gốc. Nếu nút gốc là một terminal, một terminal ngẫu nhiên sẽ được chọn. Nếu nút gốc là một phép tính, một phép tính ngẫu nhiên sẽ được chọn, và nút này sẽ có số lượng nhánh con bằng với số lượng đối số của phép tính. Với mỗi nhánh con này, thật toán grow sẽ + * A B C + A C + * - A B DC 20 lại bắt đầu cho đến khi nhánh con ở mức lớn nhất của cây. Trong trường hợp này, nhánh con sẽ được tạo thành bằng cách chọn một terminal ngẫu nhiên. Half – and – Half: phương pháp này là sự kết hợp của 2 phương pháp trên. 2.3.2. Các thao tác di truyền Theo thuyết tiến hóa của Darwin, một quần thể sẽ trải qua nhiều thế hệ, và các cá thể của thế hệ mới là kết quả của sự kết hợp các cá thể trong thế hệ trước. Nói cách khác, đó là sự chuyển giao các cá thể cho thế hệ mới trong quần thể, sử dụng các thao tác di truyền. Lai ghép, đột biến, và sinh sản là các thao tác di truyền được sử dụng để tạo nên các các thể mới trong mỗi thế hệ. 2.3.2.1. Lai ghép Thao tác lai ghép tạo ra hai cá thể mới từ hai cá thể cha mẹ được lựa chọn từ quần thể dựa vào giá trị thích nghi. Trong mỗi cấu trúc cây cha mẹ, một nút ngẫu nhiên sẽ được chọn, và những nhánh con bên dưới nút được chọn sẽ được hoán vị để tạo thành 2 cây mới. Tiến trình thực hiện thao tác lai ghép được thể hiện ở hình 2.5. Hình 2.5. Thao tác lai ghép + * - 2 8 54 + / 5 2 7 Hoán vị + * / 2 8 25 + - 4 5 7 Các nhánh con được hoán vị để tạo thành các cây mới 21 2.3.2.2. Đột biến Thao tác đột biến tạo ra một cá thể mới từ một cá thể có sẵn trong quần thể bằng việc thay thế một nút của cây bằng một nút khác trong tập tương ứng (một phép tính sẽ được thay thế bằng một phép tính, và một terminal sẽ được thay thế bằng một terminal). Hình 2.6 thể hiện tiến trình thực hiện thao tác đột biến. Hình 2.6. Thao tác đột biến. 2.3.2.3. Sinh sản Thao tác sinh sản lựa chọn những cá thể từ quần thể dựa trên gía trị thích nghi và sao chép nguyên mẫu chúng vào quần thể mới. 2.3.3. Hàm tính giá trị thích nghi Để lựa chọn các cá thể cho thao tác lai ghép, sinh sản và đột biến, cũng như đánh giá độ tốt của từng cá thể trong việc giải quyết bài toán, hàm tính giá trị thích nghi (gọi tắt là hàm thích nghi) là phương pháp để đánh giá độ thích nghi của từng cá thể trong quần thể. Những hàm thích nghi được sử dụng trong nhiều hệ thống tìm kiếm và tối ưu hóa là MSE, SRM, MDL, AIC, CV, FPE [10]. 2.3.3.1. MSE – Mean Square Error Đây là phương pháp ước lượng đơn giản nhất, được tính theo công thức sau: (2.1) - A B DC - A B DC Nút được chọn Đột biến* + / + ∑ = −= n 1i 2 ii )yˆ(yn 1MSE 22 Với: n : số lượng dữ liệu mẫu. yi : giá trị của mẫu luyện thứ i tương ứng của biến phụ thuộc. iyˆ : giá trị dự đoán thứ i của biến phụ thuộc. 2.3.3.2. SRM – Structural Risk Minimisation SRM là một phương pháp tính toán khá phức tạp cho phép lựa chọn mô hình dựa trên việc tối htiểu hoá các rủi ro cũng như xác suất sai số của mô hình . Công thức: SRM = MSE/[1-T(h,n)]∞ (2.2) Trong đó T(h,n) = C1* [(h.ln(2n) – ln(h!) + C2 /n]1/2 (2.3) [ ] ⎩⎨⎧∞=∞ ZZ (2.4) Với n: số lượng dữ liệu mẫu. h: số lượng biến độc lập Việc chọn giá trị thích hợp cho C1 và C2 cần dựa vào kiến thức và kinh nghiệm. Mô hình SRM bị ảnh hưởng lớn bởi C1, chỉ cần một điều chỉnh nhỏ trên C1 thì cũng làm cho mô hình thay đổi rất nhiều. 2.3.3.3. AIC – Akaike’s Information Criterion Akaike's Information Criterion (AIC) Cho phép lựa chọn mô hình dựa trên công thức sau: AIC = ln(MSE) + k*h/n (2.5) AIC thường dùng k = 2, hay k = ln(n), với n là số lượng dữ liệu mẫu thì được gọi là BIC. (Bayesian Information Criterion) or SBC (Schwarz's Bayesian Criterion). Khi so sánh với những đối tượng phù hợp, AIC càng nhỏ thì càng phù hợp. nếu Z ≥ 0 nếu Z < 0 23 2.3.3.4. MDL – Minimum Description Length Quy tắc MDL là một phương pháp mới được đưa ra gần đây dựa trên suy diễn quy nạp với công thức: MDL = ln(MSE) + h*ln(n)/n (2.6) Phương pháp này tạo ra những mô hình ít tham số hơn khi so sánh với phương pháp AIC và FPE, bởi vì MDL sử dùng tỷ tham số tỷ lệ là ln(n), trong khi AIC và PFE sử dụng 1/n. 2.3.3.5. FPE – Final Prediction Error FPE tương tự AIC và MDL nhưng theo đánh giá có độ chính xác cao hơn 2 phương pháp trên với công thức: FPE = MSE (1+h/n)/(1-h/n) (2.7) 2.3.4. Phương pháp chọn lọc Sự tiến hóa trong GP có thể làm những cấu trúc phát triển rất lớn. Do đó, cần phải đặt ra giới hạn về độ sâu của cây hay giới hạn số lượng các nút. Trong những bài toán có những cá thể được tạo nên từ nhiều cây, giới hạn riêng có thể được đặt ra cho từng cây thành phần, cũng như cho từng cá thể. Có 3 phương pháp chọn lọc thường được sử dụng là [11]: 2.3.4.1. Chọn lọc dựa vào độ thích nghi: Phương pháp này chọn ra một cá thể dựa vào tỷ lệ thích nghi của cá thể khi so sánh với giá trị thích nghi của toàn bộ quần thể. Khi có n cá thể trong quần thể, một cá thể i sẽ được chọn với xác suất pi: (2.8) Với: f : hàm thích nghi. i, j : cá thể thứ i, j. n : kích thước quần thể. ∑= = = nj j i jf ifp 1 )( )( α α 24 Phương pháp này cũng được biết đến với tên gọi quy tắc chọn lọc theo vòng quay Roulette (Roulette Wheel) [8]. Mỗi cá thể được xem là một cung trên vòng quay Roulete, độ lớn của cung được tính dựa vào công thức ở trên. Cá thể có độ thích