Tiểu luận thuật toán di truyền thích nghi song song

A. GIỚI THIỆU Thuật toán di truyền là một sự thể hiện của một lớp các phương pháp dựa trên kỹ thuật tìm kiếm ngẫu nhiên Heuristic. Thuật toán di truyền khi thực hiện đòi hỏi một lượng lớn thời gian tính toán. Song song hóa thuật toán di truyền là một thử nghiệm đầu tiên để tăng tốc thuật toán mà không ảnh hưởng đến các tính chất của nó. Trong tiểu luận này, kỹ thuật đa luồng được sử dụng để chuyển đổi thuật toán di truyền thành dạng song song. Vấn đề mấu chốt để nâng cao hiệu suất trong tính toán song song là phải giảm truyền thông giữa các tiến trình. Sức mạnh của thuật toán di truyền chủ yếu là ở khả năng xác định vị trí tối ưu toàn cục trong một môi trường đa phương thức. Tuy nhiên, cho dù hiệu quả của thuật toán di truyền là thế nào đi chăng nữa thì lời giải của phương pháp này cũng không chính xác một cách tuyệt đối. Nhiều công trình đang nghiên cứu để tìm cách tăng thêm độ chính xác đó. Để đạt được mục tiêu này, hai hướng tiếp cận chính có thể được chấp nhận: hướng thứ nhất là thiết kế một thuật toán di truyền cho một lớp các bài toán mà ta đang giải quyết. Khuynh hướng này bao gồm việc tạo ra cấu trúc dữ liệu và đặc tả các phép toán di truyền cho một bài toán, tạo ra một chương trình tiến hóa. Hướng tiếp cận thứ hai hoạt động trực tiếp trên thuật toán và cố gắng để tăng hiệu quả bằng cách thay đổi cấu trúc nội tại của nó. Phương pháp thích nghi được giới thiệu ở đây là một ví dụ của tiếp cận này. Tiểu luận được viết trong cấu trúc bốn phần. Phần 1: Trình bày tổng quan về thuật toán di truyền và hoạt động của các toán tử di truyền. Phần 2: Trình bày thuật toán di truyền song song. Trong đó nhấn mạnh trên thuật toán di truyền song song song song với các luồng bằng nhau. Phần 3: Trình bày các toán tử di truyền thích nghi. Phần 4: Giới thiệu một sự thực hiện của thuật toán di truyền song song thích nghi, trong đó mô tả sự thực hiện của một thuật toán di truyền song song kết hợp với kỹ thuật thích nghi. B. NỘI DUNG I. THUẬT TOÁN DI TRUYỀN VÀ CÁC TOÁN TỬ DI TRUYỀN 1.1-Thuật toán di truyền Thuật toán di truyền là thuật toán bắt chước chọn lọc tự nhiên và di truyề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 ở thế hệ sau. Mỗi có thể có cấu trúc gien đặc trưng cho phẩm chất của cá thể đó. Trong quá trình sinh sản, các cá thể con có thể thừa hưởng các phẩm chất của cha và mẹ, cấu trúc gien của nó mang một phần cấu trúc gien của cha và mẹ. Ngoài ra trong quá trình tiến hóa, có thể xảy ra hiện tượng đột biến, cấu trúc gien của cá thể con có thể chứa các gien mà cả cha và mẹ đều không có. Trong thuật toán di truyền, mỗi cá thể được mã hóa bởi một cấu trúc dữ liệu mô tả cấu trúc gien của cá thể đó, ta gọi đó là nhiễm sắc thể. Mỗi nhiễm sắc thể được tạo thành từ các đơn vị được gọi là gien. Chẳng hạn trong các thuật toán di truyền cổ điển, mỗi nhiễm sắc thể (tương ứng với mỗi cá thể) được biểu diễn bằng một chuỗi nhị phân. Thuật toán di truyền sẽ làm việc trên các quần thể gồm nhiều cá thể. Mỗi quần thể ứng với một giai đoạn phát triển sẽ được gọi là một thế hệ. Từ thế hệ ban đầu được tạo ra, thuật toán di truyền bắt chước chọn lọc tự nhiên và di truyền để biến đổi các thế hệ, trong đó nó sử dụng các toán tử cơ bản sau đây: -Toán tử chọn lọc (còn được gọi là toán tử tái sinh): 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 thực hiện dựa vào độ thích nghi với môi trường của mỗi cá thể. Ta gọi hàm ứng với mỗi cá thể với độ thích nghi của nó là hàm thích nghi. -Toán tử lai ghép: hai cá thể cha mẹ trao đổi các gien để tạo ra hai cá thể con. -Toán tử đột biến: Một cá thể thay đổi một số gien để tạo thành 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 GA; Begin t <- 0; Khởi tạo thế hệ ban đầu P(t); Đánh giá P(t) theo hàm thích nghi; Repeat t<-t+1; Sinh ra thế hệ mới p(t) từ P(t-1) bởi +Chọn lọc +Lai ghép +Đột biến Đánh giá P(t); 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ác cá thể tốt nhất trong các thế hệ kế tiếp nhau là 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ùng được chọn làm nghiệm cần tìm. 1.2-Các toán tử di truyền a/ 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 trên độ 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. 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. Quá trình chọn lọc được thực hiện theo kỹ thuật quay bánh xe. Giả sử thế hệ hiện thời P(t) gồm có n cá thể {x1,x2,...,xn}. Số n được gọi là kích cở của quần thể. Với mỗi cá thể xi, ta tính độ thích nghi của nó f(xi). Tính tổng các độ thích nghi của tất cả các cá thể trong quần thể F(n)= f(x1)+f(x2)+...+f(xn) Mỗi lần chọn lọc, ta thực hiện hai bước sau: -Sinh ra một số thực ngẫu nhiên q trong khoảng (0,F); -xk là cá thể được chọn, nếu k là số nhỏ nhất sao cho F(k)>=4 Việc chọn lọc theo hai bước trên có thể minh họa như sau: Ta có một bánh xe được chia thành n phần, mỗi phần ứng với độ thích nghi của một cá thể. Một mũi tên chỉ vào bánh xe. Quay bánh xe, khi bánh xe dừng, mũi tên chỉ vào phần nào thì có thể ứng với phần đó được chọn. Hình minh họa cho kỹ thuật chọn lọc theo kiểu quay bánh xe Rõ ràng với cách chọn này, các cá thể có độ thích nghi càng cao càng có khả nă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 ở thế hệ sau. b/ Toán tử lai ghép: Trên cá thể được chọn lọc, ta tiến hành lai ghép. Đầu tiên ta cần đưa ra xác suất lai ghép pc. Xác suất này cho ta hy vọng có npc cá thể được lai ghép (n là kích cở của quần thể) Với mỗi cá thể ta thực hiện hai bước sau: +Sinh ra số thực ngẫu nhiên r trong đoạn [0..1]; +Nếu r<pc thì cá thể đó được chọn để lai ghép; Từ các cá thể được chọn để lai ghép, người ta cặp đôi chúng một cách ngẫu nhiên. Trong trường hợp các nhiễm sắc thể là các chuỗi nhị phân có độ dài cố định m ta có thể thực hiện lai ghép như sau: Với mỗi cặp sinh ra một số nguyên ngẫu nhiên p trên đoạn từ [0,m-1], p là vị trí điểm ghép. Cặp gồm hai nhiễm sắc thể a=(a1,...,ap,ap+1,...,am) b=(b1,...,bp,bp+1,...,bm) được thay bởi hai con là: a’=(a1,...,ap, bp+1,...,bm) b’=(b1,...,bp, ap+1,...,am) c/ Toán tử đột biến: Ta thực hiện đột biến trên các cá thể có được sau quá trình lai ghép. Đột biến là thay đổi trạng thái một số gien nào đó trong nhiễm sắc thể. Mỗi gien chịu đột biến với xác suất pm. Xác suất đột biến pm do ta xác định và là xác suất thấp. Sau đây minh họa toán tử đột biến trên các nhiễm sắc thể chuỗi nhị phân. Với mỗi vị trí i trong nhiễm sắc thể a=(a1,...,ai,...,am), ta sinh ra một số thực ngẫu nhiên pi trong [0,1]. Qua đột biến a được biến thành a’ như sau: a’=(a’1,...,a’i,...,a’m) trong đó: a’i =ai nếu pi >= pm 1-ai 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 di truyền chỉ là lặp lại các bước trên. Nói chung thuật ngữ thuật toán di truyền là để chỉ thuật toán di truyền cổ điển, khi mà cấu trúc của các nhiễm sắc thể được biểu diễn dưới dạng các chuỗi nhị phân với các toán tử di truyền đã được mô tả ở trên. Song trong nhiều vấn đề thực tế, để thuận tiện hơn ta có thể biểu diễn nhiễm sắc thể bởi các cấu trúc khác như: véc tơ thực, mảng hai chiều, cây.... Tương ứng với cấu trúc của nhiễm sắc thể, có thể có nhiều cách xác định các toán tử di truyền. Quá trình sinh ra thế hệ mới p(t) từ thế hệ cũ p(t-1) cũng có nhiều cách lựa chọn. Người ta gọi chung các thuật toán này là các thuật toán tiến hóa. II-THUẬT TOÁN DI TRUYỀN SONG SONG Thuật toán di truyền là một phương pháp tìm kiếm ngẫu nhiên Heuristic dựa trên sự tiến hóa tự nhiên trong đó đòi hỏi một lượng lớn thời gian CPU. Vì bài toán tối ưu phải được giải quyết trong giới hạn thời gian và tính toán đã cho nên thuật toán di truyền song song là một thử nghiệm để tăng tốc chương trình mà không ảnh hưởng đến các tính chất khác của thuật toán. Có thể chia thành hai nhóm thuật toán di truyền mà thưc hiện song song: +Những thuật toán di truyền phân tán (mô hình song song độc lập) Trong loại thuật toán này các quần thể con khác nhau tiến hóa một cách song song. +Những thuật toán di truyền song song. Trong thuật toán này các tiến trình song song khác nhau làm việc trên một quần thể chung. Thuật toán di truyền song song được thực hiện với đa luồng Thuật toán di truyền song song (PGA) có thể được thực hiện thông qua việc dùng những luồng khác nhau. Lợi ích chính từ đa luồng là: cấu trúc chương trình tốt hơn (bất kỳ chương trình nào mà trong đó các hoạt động không phụ thuộc vào nhau có thể được thiết kế lại sao cho mỗi hoạt động được thực hiện như một luồng) và sử dụng đa bộ xử lý một cách hiệu quả. Để áp dụng kỹ thuật đa luồng cho một thuật toán, trước hết ta phải xác định được các phần độc lập và gán chúng cho mỗi luồng. Một hoặc nhiều luồng có thể được gán vào mỗi toán tử di truyền (phép chọn lọc, phép lai ghép và phép đột biến). Ngoài ra, ta có thể gán một luồng cho giao diện người dùng, một luồng cho điều khiển tham số, một luồng để so sánh những kết quả với những phương pháp khác (ví dụ, ta có thể thực hiện một cơ chế tìm kiếm ngẫu nhiên và so sánh kết quả với thuật toán di truyền). 2.1-Các loại phép chọn lọc Một số phép chọn lọc được liệt kê trong bảng dưới đây. Để trình bày ngắn gọn, trong tiểu luận ta sử dụng một thuật ngữ tiếng Anh cho một loại phép chọn lọc. Tham số M Loại toán tử chọn lọc Mô tả M=POP_SIZE Chọn Generation Thay thế toàn bộ quần thể 1£M£POP_SIZE Chọn Steady-state Thay thế M cá thể M=1 Chọn tournament Thay thế chỉ một cá thể (cá thể xấu nhất của ba cái được chọn) Tham số M và sự tái sinh Steady-state (POP_SIZE là kích cở của quần thể) Phép chọn lọc steady-state có một tham số M (là số lượng nhiễm sắc thể mới được tạo ra). Phép chọn lọc Generation là trường hợp đặc biệt của phép chọn lọc steady-state trong đó tham số M bằng kích cở của quần thể. Phép chọn lọc tournament cũng là trường hợp đặc biệt của phép chọn lọc steady-state trong đó tham số M bằng 1. Phép chọn lọc Steady-state thay thế M cá thể trong mỗi lần lặp của quá trình tiến hóa. Ta chia thuật toán thành ba phần độc lập và gán mỗi phần cho một luồng. Luồng thứ nhất chỉ thực hiện lai ghép và tạo ra các cá thể mới. Luồng thứ hai thực hiện chọn lọc và xóa những cá thể được chọn. Luồng thứ ba chỉ thực hiện đột biến. Nếu không có sự đồng bộ hóa thì kích thước quần thể sẽ bị thay đổi. Nếu luồng xóa là nhanh hơn luồng tạo ra thì sau một lúc quần thể sẽ gồm có một cá thể (cá thể cuối cùng không thể bị xóa vì nó là cái tốt nhất tại thời điểm đó). Toán tử lai ghép cần hai cá thể để tạo ra một con và nó chờ cho sự tạo ra cá thể khác mãi mãi, bởi vì không có cá thể nào tạo ra nó. Kết quả là gây ra sự tắc nghẽn (deadlock). Khả năng khác là tràn bộ nhớ nếu luồng tạo ra nhanh hơn luồng xóa. Vấn đề đó có thể được giải quyết bởi một cơ chế đồng bộ đơn giản. Nếu kích thước quần thể quá nhỏ, luồng xóa chờ, nếu kích thước quần thể quá lớn, luồng tạo ra chờ. Sự thay đổi của biến POP_SIZE phải được gán vào một phần tới hạn để ngăn chặn sự thay đổi nó một cách đồng thời của nhiều luồng khác nhau. Một số thí nghiệm chỉ ra rằng thuật toán di truyền song song được mô tả ở trên tốn nhiều thời gian cho sự đồng bộ hóa hơn so với sự tối ưu. Kết quả là có thể chương trình song song chậm hơn chương trình tuần tự. Đối với phép toán chọn lọc steady-state với tham số M=1, phép chọn cá thể xấu bằng kỹ thuật quay bánh xe không phải là sự lựa chọn tốt. Vì mỗi vòng quay xác suất lựa chọn đối với toàn bộ quần thể phải được tính toán nên phép chọn quay bánh xe làm chậm thuật toán. Trong trường hợp đó, giải pháp là sử dụng phép chọn tournament. Trong phép chọn cá thể xấu tournament, mỗi bước của sự tiến hóa chọn ba cá thể với xác suất bằng nhau. Sau đó xóa cá thể yếu nhất trong ba cá thể đó. Hai cá thể còn lại sẽ sinh ra một cá thể con và thay thế cá thể bị xóa 2.2-Các phép toán di truyền Trong sự thực hiện của thuật toán di truyền steady-state song song với phép chọn cá thể xấu tournament gồm có hai luồng: một luồng thực hiện phép chọn tournament và lai ghép; luồng khác dùng để đột biến. Procedure TTDT_song_song_đơn_giản; Begin Khởi tạo quần thể; Repeat Chọn_loc; {Tạo luồng cho toán tử chọn lọc tournament và lai ghép} Đột_biến; {Tạo luồng cho toán tử đột biến} Until điều kiện dừng đạt được; Xóa; {Xóa tất cả các luồng} End; Procedure Đột_biến; {Luồng cho toán tử đột biến} Begin Chọn ngẫu nhiên một cá thể; Đột biến nó; End; Procedure Chọn_lọc; {Luồng cho toán tử chọn tournament và lai ghép} Begin Chọn ngẫu nhiên ba cá thể; Xóa cá thể xấu nhất của ba cá thể được chọn; Cá thể mới:=lai ghép của hai cá thể còn lại; End; Cấu trúc của thuật toán di truyền song song đơn giản Vấn đề chính của sự thực hiện song song đơn giản là nó không có sự điều khiển trên xác suất đột biến. Kết quả, thuật toán này tương đối tốt so với tìm kiếm ngẫu nhiên, nhưng cũng không hiệu quả. Nếu những luồng được giao cho thực hiện song song mà không có sự điều khiển, một trong hai luồng có thể bỏ phí một số thời gian để chờ thời gian bộ xử lý. Khi đó, một trong hai khả năng xảy ra: +Luồng đột biến làm việc và luồng chọn lọc và lai ghép chờ. Đây là tìm kiếm ngẫu nhiên hoàn toàn, nghĩa là xác suất đột biến được đặt là 1. Nếu không áp dụng sự phát triển tầng lớp ưu tú thì những cá thể tốt nhất thu được trong các lần lặp ở quá khứ sẽ bị mất. Vì vậy, trong luồng đột biến phải thêm vào sự phát triển tầng lớp ưu tú. Procedure Đột_biến; {Luồng cho toán tử đột biến} Begin Chọn ngẫu nhiên một cá thể; Nếu cá thể này không tốt nhất thì đột biến nó; End; Luồng cho đột biến mở rộng với cơ chế phát triển +Luồng chọn lọc và lai ghép thực hiện còn luồng đột biến chờ. Xác suất đột biến được đặt là 0. Trong hàng trăm lần lặp khác nhau thuật toán di truyền sinh ra một quần thể đồng dạng (gồm POP_SIZE-1 cá thể giống nhau). Ngay cả khi ta điều khiển xác suất đột biến, trong suốt sự thực hiện của thuật toán di truyền khoảng một nửa nhiễm sắc thể được tạo ra hai lần. Nếu quần thể là thuần nhất hơn thì xác suất đột biến phải tăng. Việc điều khiển của xác suất đột biến có thể được giải quyết dễ dàng bằng một số kỹ thuật đồng bộ hóa, nhưng nó lại làm chậm thuật toán. Một giải pháp khác là bổ sung thêm xác suất đột biến thích nghi. Trước khi toán tử lai ghép được thực hiện phải kiểm tra hai cá thể bố và mẹ. Nếu bố mẹ là bằng nhau, thì đột biến một trong hai cá thể đó và sinh ra con của chúng hoàn toàn ngẫu nhiên. Vậy ta sửa lại luồng cho phép toán chọn lọc tournament và lai ghép như sau: Procedure Chọn_lọc; {Luồng cho toán tử chọn lọc tournament và lai ghép} Begin Chọn ngẫu nhiên ba cá thể; Xóa cá thể xấu nhất của ba cá thể được chọn; Nếu những cá thể còn lại là bằng nhau Begin Đột biến một cá thể; Tạo một cá thể mới một cách ngẫu nhiên; End; ngược lại: Cá thể mới:=Lai ghép hai cá thể còn lại End; Luồng cho toán tử chọn lọc tournament và lai ghép mở rộng với kỹ thuật xóa cá thể giống nhau và xác suất đột biến Hai luồng được mở rộng này có thể được thực hiện một cách song song mà không cần đồng bộ hóa. Các thử nghiệm đã chỉ ra rằng: luồng chọn lọc tournament và lai ghép sử dụng 69.4% thời gian tối ưu và luồng đột biến tiêu tốn thời gian tối ưu còn lại (30.6%). Trên một hệ thống hai bộ xử lý, toàn bộ thời gian tối ưu là khoảng 30% ngắn hơn so với trên hệ thống một bộ xử lý. Thuật toán di truyền song song mở rộng đã mô tả (EPGA_1) được chia thành hai luồng là phù hợp cho việc thực hiện trên hệ thống hai bộ xử lý. 2.3-Thuật toán di truyền song song với các luồng bằng nhau Nếu ta muốn tạo một cách sử dụng tốt của hệ thống với hai hoặc nhiều hơn hai bộ vi xử lý, thuật toán di truyền phải được chia thành nhiều hơn hai luồng. Ý tưởng xuất phát từ việc chia thuật toán di truyền thành nhiều phần độc lập và bằng nhau. Thuật toán này giống với EPGA_1, nhưng nó được chia theo một cách khác. Mỗi luồng thực hiện tất cả các phép toán di truyền như thuật toán di truyền không song song. Một luồng chỉ hoạt động trên một phần của quần thể, bởi vì phép chọn tournament chỉ làm việc trên ba nhiễm sắc thể trong mỗi bước lặp. Luồng khác có thể làm việc đồng thời trên các nhiễm sắc thể giống nhau (một, hai hoặc cả ba) mà không cần một sự đồng bộ hóa nào. Loại thuật toán song song này làm việc giống như với một hoặc nhiều luồng. Procedure TTDT_song_song_mở_rộng_2; Begin Khởi tạo quần thể; Repeat Tiến_hóa; {Tạo các luồng tiến hóa} Untill điều kiện dừng đạt được; Xóa; {Xóa tất cả các luồng} End; Procedure Tiến_hóa; {Luồng tiến hóa} Begin Thực hiện toán tử chọn lọc tournament và xóa một cá thể; Thực hiện lai ghép và thay thế cá thể bị xóa Thực hiện đột biến End; Cấu trúc thuật toán di truyền song song với các luồng bằng nhau (EPGA_2) Nếu số lượng bộ xử lý lớn hơn hoặc bằng số lượng luồng thì thời gian tối ưu bằng thời gian tồn tại của luồng dài nhất. Thời gian tối ưu cho SPGA và EPGA_1 trên một hệ thống hai bộ xử lý bằng thời gian tồn tại của luồng để lai ghép và chọn lọc (khoảng 70% của tổng thời gian CPU). Trên một hệ thống có nhiều hơn hoặc bằng ba bộ xử lý, chương trình thực hiện không nhanh hơn bởi vì thuật toán chỉ được chia thành hai luồng. EPGA_2 được chia thành NT luồng đúng bằng NP bộ xử lý. Thời gian tối ưu cho EPGA_2 bằng thời gian tối ưu cho cùng thuật toán di truyền không song song được chia theo số lượng bộ xử lý. III-CÁC TOÁN TỬ DI TRUYỀN THÍCH NGHI Có hai đặc tính cần được thiết lập trong thuật toán di truyền để tối ưu hóa các hàm đa phương thức. Đặc tính thứ nhất là khả năng hội tụ về sự tối ưu cục bộ hoặc toàn cục, sau khi đã định vị vùng chứa nó. Đặc tính thứ hai là khả năng để thăm dò những vùng mới của không gian lời giải trong tìm kiếm tối ưu toàn cục. Nhờ các toán tử di truyền, lai ghép và đột biến, ta mới đạt được các đặc tính đó. Phép toán lai ghép chịu trách nhiệm chính cho đặc tính thứ nhất, trong khi đó đặc tính thứ hai được tạo ra bằng đột biến. Sự cân bằng giữa các đặc tính có thể thu được bởi sự ảnh hưởng cách thức thực hiện của những phép toán di truyền. Thực chất của việc tìm kiếm đa phương thức là phải giữ lại quần thể được phân tán trong không gian bài toán. Ta không cần toàn bộ quần thể cùng hội tụ về một giá trị tối ưu, nhưng ta cần phải duy trì độ hội tụ nhanh tại một tối ưu cục bộ. Tại cùng một thời điểm ta phải để cho thuật toán thăm dò những vùng có triển vọng và xác định sự tối ưu với độ chính xác mong muốn. Có thể duy trì tính đa dạng của quần thể bằng việc tăng tỷ lệ đột biến, trong khi có thể tăng tốc độ hội tụ bằng việc chấp nhận những cá thể tốt hơn để tham gia trong phép lai ghép. Trước khi áp dụng những kỹ thuật thích nghi, ta phải xác định mức độ tính đa dạng của quần thể. Để có được một hình ảnh khá tốt về trạng thái quần thể ta theo dõi hai giá trị đặc tính của nó: fmax-giá trị thích nghi của thành viên tốt nhất, và f-giá trị thích nghi trung bình của tập hợp các lời giải, cả hai được gán vào một thế hệ hiện tại. Biểu thức fmax-f có thể bé hơn đối với một quần thể mà đã hội tụ so với một quần thể rải rác trong không gian lời giải. Để xác định mức độ đa dạng của quần thể, người ta đưa ra biểu thức: (fmax - f)/( fmax - fmin) (1) Trong đó: fmin biểu diễn giá trị thích nghi xấu nhất. Nếu giá trị này thấp thì quần thể là đồng dạng, nếu nó nhận giá trị cao hơn quần thể là đa dạng hơn. Tuy nhiên, trong các bài toán tối ưu hóa với một không gian nghiệm lớn (xâu nhị phân dài) giá trị này có khuynh hướng là rất thấp ở thời điểm bắt đầu và tăng chậm trong suốt quá trình. Điều này là do những hàm mà có giá trị xấp xỉ trung bình trong hầu hết không gian tìm kiếm đã xác định, trong khi những giá trị hàm số cao hơn được tìm thấy trong một phạm vi tương đối nhỏ hơn. Đ