Tiểu luận Môn xử lý song song: 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. Để khai thác một cách hiệu quả biểu thức (1) ở trên, một kỹ thuật hiệu chỉnh được thực hiện trong mỗi thế hệ. Trong bước đầu của quá trình, biểu thức được lượng giá và giá trị của nó được lưu trong một biến. Biểu thức này được tính toán trong mỗi thế hệ và so sánh với giá trị được lưu trong biến đó. Nếu giá trị mới tốt hơn giá trị cũ thì giá trị của biến được thay bằng giá trị mới. Nếu nó là nhỏ hơn, biến không thay đổi. Ta gọi giá trị của (1) trong thế hệ hiện tại là curr_val và trong biến là prev_val. Ta xây dựng biểu thức giữa curr_val và prev_val như sau: W = (2) Nếu ta không muốn quần thể trở thành thuần nhất thì curr_val nhỏ hơn prev_val và vì vậy w giảm. Lũy thừa 2 được thêm vào để tăng độ nhạy. Trước khi tính toán w, nếu prev_val<curr_val thì thay thế prev_val bằng giá trị mới. Trong trường hợp đó, quần thể trở thành đa dạng hơn và w bằng 1. Kỹ thuật thích nghi ảnh hưởng đến cách thức nhiễm sắc thể được chọn để lai ghép. Với mỗi lời giải có một giá trị đặc tính v được tính như sau: v = (f - fmin)(2w - 1) - (fmax - fmin)(w - 1) (3) Trong đó f là giá trị thích nghi của một nhiễm sắc thể. Phương pháp quay bánh xe được dùng để chọn các nhiễm sắc thể để lai ghép, có tính đến những giá trị đặc tính của chúng. Một cá thể được chọn trước đây được thay thế bởi sản phẩm lai ghép, trong khi bố mẹ không bị thay đổi. Một nhiễm sắc thể có thể tham gia trong phép lai ghép hơn một lần, phụ thuộc vào giá trị thích nghi của nó. Nếu một quần thể được phân tán trong không gian bài toán, giá trị của w sẽ cao hơn. Vì vậy theo (3), những lời giải với giá trị thích nghi tốt hơn sẽ có một cơ hội cao hơn để lai ghép và sinh con cái. Nếu w thấp hơn, phép chọn lọc trở thành đồng dạng hơn. Khi áp dụng vào một thuật toán steady-state bằng phép chọn loại trừ thì phương thức thích nghi tính toán biểu thức (2) trong bước khởi đầu của mọi thế hệ. Nếu thuật toán sử dụng phép chọn lọc tournament, như đã mô tả trong phần 2 thì ta phải xác định khi nào tính toán giá trị mới của w. Cuối cùng, kỹ thuật thích nghi làm thay đổi số lượng toán tử đột biến trong mỗi thế hệ. Số lượng toán tử đột biến được tính là: n = POP_SIZE * [2*(1 - w) + 0.1] (4) Số lượng toán tử đột biến tăng tuyến tính với sự giảm của (1) trong thế hệ hiện tại. Mặt khác, nếu ta dùng toán tử chọn lọc tournament, toán tử đột biến được thực hiện trong mỗi bước của quá trình thích nghi. Chiến lược thích nghi làm tăng khả năng thăm dò các lời giải ưu thế vì thế tăng tốc độ hội tụ. Ngoài ra nó cũng có thể giúp ngăn chặn quần thể trong việc bị mắc kẹt tại một tối ưu cục bộ. Để cải tiến, ta còn đưa ra một loại toán tử đột biến đó là toán tử đột biến không đồng dạng. Trong toán tử đột biến không đồng dạng có sự xem xét giá trị thích nghi của một lời giải và chọn phạm vi trong đó nghiệm sẽ bị thay đổi. Điều này được thực hiện trong thực tiễn bằng cách hạn chế số lượng các bít mà toán tử đột biến có thể làm ảnh hưởng trong một nhiễm sắc thể đơn. Trong biểu diễn nhị phân, chỉ một tập số của những bít bên phải (ít quan trọng hơn) có thể bị đột biến. Độ dài những bít có thể thay đổi từ một xâu con bên phải của một nhiễm sắc thể được tính là: Bits = 1 + chrom_length * f > f (5) trong đó chrom_length là tổng số các bít trong một nhiễm sắc thể và f là giá trị thích nghi của cá thể được chọn. Giới hạn này chỉ làm cho giá trị thích nghi của lời giải lớn hơn giá trị trung bình của quần thể. Kỹ thuật tương tự như thế đối với biểu diễn dấu phẩy động được thực hiện dễ dàng bằng cách định nghĩa sự khác nhau lớn nhất giữa nghiệm cũ và nghiệm mới sau khi đột biến. Toán tử đột biến không đồng dạng đã cải tiến đáng kể khả năng điều chỉnh của thuật toán. Nhưng nói chung, kết quả tốt nhất thu được khi cả hai loại toán tử đồng dạng và không đồng dạng được tính đến. IV-THUẬT TOÁN DI TRUYỀN SONG SONG THÍCH NGHI. Trong phần này ta 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. Mô hình song song được dùng là thuật toán di truyền song song với các luồng bằng nhau (EPGA_2). Mỗi luồng thực hiện một cách độc lập và hoạt động trên toàn bộ quần thể, nhưng không nhiều hơn ba cá thể trong cùng một lúc. Một luồng thực hiện một toán tử chọn lọc tournament và xóa cá thể được chọn. Sau đó thực hiện kỹ thuật chọn lọc quay bánh xe để xác định hai bố mẹ tham gia trong lai ghép. Sản phẩm của phép lai ghép thay thế cá thể bị xóa. Sau POP_SIZE phép lai ghép, thuật toán xác định tính đa dạng quần thể (3) và cập nhật giá trị đặc tính của nhiễm sắc thể. Cuối cùng thực hiện pha đột biến và chu trình thế hệ chấm dứt. Cấu trúc của thuật toán di truyền song song thích nghi như sau: Procedure TTDT_song_song_thích_nghi Begin Khởi tạo quần thể; Repeat Tiến_hóa; {Tạo các luồng tiến hóa bằng nhau} Until điều kiện dừng đạt được; End; Procedurre Tiến_hóa; {Luồng tiến hóa} Begin Thực hiện toán tử chọn lọc Tournament; Xóa cá thể được chọn; Thực hiện chọn lọc bố mẹ bằng kỹ thuật quay bánh xe; Thực hiện lai ghép; Thay thế cá thể bị xóa; Tính toán các ước lượng mọi POP_SIZE w và vi; Thực hiện toán tử đột biến; End; Cấu trúc của thuật toán di truyền song song thích nghi với những luồng bằng nhau (PAGA) PAGA có thể được thực hiện trên một hệ thống có một hặc nhiều bộ xử lý, với một hoặc nhiều luồng. Điều kiện dừng được dùng ở đây là một tập các hàm lượng giá được thực hiện bởi thuật toán. C. KẾT LUẬN Tiểu luận đã tìm hiểu một sự thực hiện hiệu quả của thuật toán di truyền song song với các toán tử di truyền thích nghi. Một mặt nó mở rộng thuật toán di truyền kinh điển với cơ chế song song, mặt khác mở rộng phương pháp các toán tử thích nghi. Sự song song hóa của một thuật toán đạt được thông qua cơ chế đa luồng đó là một kỹ thuật thực hiện dễ dàng và rất hiệu quả. Bằng sự song song hóa ta có thể nhận được một chương trình có cấu trúc tốt hơn và làm giảm đáng kể thời gian tính toán trên một hệ thống đa xử lý. Phương pháp thích nghi được giới thiệu ở đây xác định phương thức áp dụng những toán tử di truyền, mà không ảnh hưởng đến chính bản thân những phép toán này. Nó dùng những giá trị đặc tính quần thể nhất định để đánh giá tính đa dạng của lời giải trong không gian bài toán và hành động dựa vào việc ngăn chặn trước độ hội tụ tạm thời hoặc thăm dò những vùng có nhiều triển vọng. Với kỹ thuật thích nghi, thuật toán được thiết kế thực hiện tốt hơn trên một phạm vi của những miền xác định và người sử dụng cũng cảm thấy nhẹ nhàng hơn trong việc xác định những tham số của nó. Thuật toán di truyền song song thích nghi được áp dụng cho sự tối ưu hóa những hàm đa phương thức với nhiều mức độ phức tạp. Ngoài ra, tiểu luận còn giới thiệu một toán tử đột biến không đồng dạng và tác dụng của nó trên hiệu suất của thuật toán. Trong hầu hết các trường hợp test, PAGA thực hiện tốt hơn các phiên bản chuẩn. Kỹ thuật thích nghi làm cho thuật toán có thể để thực hiện một cách tương tự với thuật toán mà những tham số của nó tự điều chỉnh cho một bài toán cụ thể. Một số vấn đề vẫn còn tồn tại cần được giải đáp, chẳng hạn sự lựa chọn kích cở của quần thể hoặc sự lựa chọn các kiểu của toán tử di truyền. Để hoàn thành được tiểu luận này, ngoài sự nỗ lực và cố gắng của bản thân, tác giả đã nhận được sự giúp đỡ qúy báu của Quý Thầy GS.TS Đoàn Văn Ban. Là một học viên chuyên ngành Tin học và dù rất tâm đắc với đề tài đang nghiên cứu nhưng với thời gian có hạn và khối lượng kiến thức của bản thân còn ít ỏi nên chắc chắn tiểu luận không tránh khỏi những hạn chế trong việc tiếp cận, nghiên cứu và trình bày. Tôi xin kính trọng cảm ơn sự giúp đỡ quý báu của Quý Thầy và mong được đón nhận từ Quý Thầy sự góp ý để bản thân tôi có được hiểu biết đúng hơn đối với vấn đề đang nghiên cứu đồng thời mong được sự lượng thứ cho những sơ suất trong tiểu luận này. TÀI LIỆU THAM KHẢO. [1] Đoàn Văn Ban, Nguyễn Mậu Hân - “Xử lý song song và phân tán” [2] Joseph JoJo - “An Introduction to Parallel Algrithms” Addison-Wesley-1992 [3] Seyed H. Roosta - “Parallel Processing and Parallel Algorithms, Theory and Computation” Springer 1999. [4] Marin Golub, Domagoj Jacobovic - “A Few Implementation of Parallel Genetic Algorithm” [5] Jacobovic - “Adaptive Genetic Operators in Elimination Genetic Algorithm” -1997 [6] Leo Budin, Marin Golub, Domagoj Jacobovic - “Parallel Adaptive Genetic Algorithm” MỤC LỤC Nội dung Trang Giới thiệu ................................................................................................................................................................. 1 Nội dung ................................................................................................................................................................... 2 I-Thuật toán di truyền và các toán tử di truyền.............................................................. 2 1.1-Thuật toán di truyền...................................................................................................................... 2 1.2-Các toán tử di truyên..................................................................................................................... 3 II-Thuật toán di truyền song song................................................................................................. 5 2.1-Các loại phép chọn lọc................................................................................................................ 6 2.2-Các phép toán di truyền............................................................................................................. 7 2.3-Thuật toán di truyền song song với các luồng bằng nhau................... 9 III-Các toán tử di truyền thích nghi............................................................................................. 10 IV-Thuật toán di truyền song song thích nghi................................................................. 13 Kết luận ..................................................................................................................................................................... 14 Tài liệu tham khảo ........................................................................................................................................ 15