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.
Häc viªn: Lª Thñy Th¹ch-Líp cao häc Tin häc khãa 2004-2006
1
B. NỘI DUNG

Đánh giá P(t) theo hàm thích nghi;
Repeat
Häc viªn: Lª Thñy Th¹ch-Líp cao häc Tin häc khãa 2004-2006
2
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ể {x
1
,x
2
, ,x
n
}. Số n được gọi là
kích cở của quần thể. Với mỗi cá thể x

. Xác suất này cho ta hy vọng có np
c
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<p
c
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=(a
1
, ,a
p
,a
p+1
, ,a
m
)
b=(b
1
, ,b
p
,b
p+1
, ,b
m

, ,a
i
, ,a
m
), ta sinh ra một số thực
ngẫu nhiên p
i
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
=a
i
nếu p
i
>= p
m
1-a
i
nếu p
i
< p
m
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

Để á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ể

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ó;
Häc viªn: Lª Thñy Th¹ch-Líp cao häc Tin häc khãa 2004-2006
7
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

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à
Häc viªn: Lª Thñy Th¹ch-Líp cao häc Tin häc khãa 2004-2006
9
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}

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ó: f
max
-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 f
max
-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:
(f
max
- f)/( f
max
- f
min
) (1)
Trong đó: f
min
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

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 - f
min
)(2w - 1) - (f
max
- f
min
)(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ị

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
Häc viªn: Lª Thñy Th¹ch-Líp cao häc Tin häc khãa 2004-2006
13
Thực hiện toán tử chọn lọc Tournament;
Xóa cá thể được chọ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.
Häc viªn: Lª Thñy Th¹ch-Líp cao häc Tin häc khãa 2004-2006
14
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”
Häc viªn: Lª Thñy Th¹ch-Líp cao häc Tin häc khãa 2004-2006
15