Một số kỹ thuật điều chỉnh tham số trong giải thuật di truyền

52(4): 69 - 71 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
1 
MỘT SỐ KỸ THUẬT ĐIỀU CHỈNH THAM SỐ TRONG GIẢI THUẬT DI TRUYỀN 
Vũ Mạnh Xuân (Trường ĐH Sư phạm – ĐH Thái Nguyên), 
 Lê Quang Hùng, Lê Thị Thuỷ (Khoa Công nghệ thông tin – ĐH Thái Nguyên) 
Tóm tắt. 
Giải thuật di truyền với các toán tử chọn lọc, lai ghép, đột biến là giải thuật tìm kiếm lời giải của bài toán mô 
phỏng quá trình tiến hoá tự nhiên. Bài báo này nghiên cứu và đề xuất một số kỹ thuật hiệu chỉnh tham số của giải 
thuật ngay trong quá trình tiến hoá. 
Mở đầu 
Giải thuật di truyền (GA - Genetic Algorithm) 
thực hiện việc tìm kiếm lời giải dựa trên sự mô 
phỏng quá trình tiến hoá của tự nhiên. GA sử dụng 
các toán tử chọn lọc (Selection), lai ghép 
(Crossover), đột biến (Mutation) và các tham số 
khác như kích cỡ quần thể, xác suất lai ghép, xác 
suất đột biến. Tự thích nghi là một đặc tính quan 
trọng của tự nhiên và lẽ tất nhiên cũng được sớm 
quan tâm trong giải thuật di truyền. Điều chỉnh các 
tham số của giải thuật ngay trong quá trình tiến hoá 
là một trong những vấn đề được chú ý và phát triển. 
 Kích cỡ quần thể (Population Size) là tham số đầu 
tiên cần chú ý, nếu kích cỡ quần thể quá nhỏ thì 
tính đa dạng của quần thể bị hạn chế; còn nếu quá 
lớn sẽ hao phí tài nguyên của máy tính và làm 
chậm quá trình. Trong hầu hết các nghiên cứu về 
GA người tathường chọn kích cỡ là một số cố định 
trong suốt quá trình thực hiện. Gần đây, giải thuật 
di truyền mã hoá số thực RCGA (Real-Coded 
Genetic Algorithm) phát triển mạnh và một số giải 
pháp biến đổi kích cỡ quần thể được giới thiệu [1], 
[2], với cách tiếp cận chủ yếu dựa trên cơ chế định 
tuổi của cá thể. Bài báo này đề xuất một vài kỹ 
thuật điều chỉnh kích cỡ quần thể trong quá trình 
thực hiện giải thuật dựa trên độ thích nghi trung 
bình của quần thể. 
1. Một số kết quả liên quan 
GAVaPS (Genetic Algorithm with Varying 
Population Size) được giới thiệu bởi Arabas, 
Michalewicz và Mulawka năm 1994. Thuật toán 
này biến đổi kích cỡ quần thể dựa trên độ tuổi của 
cá thể. Cụ thể là cá thể khi sinh ra được gắn với độ 
tuổi (age) và thời gian sống (lifetime), sau mỗi 
bước tạo sinh, độ tuổi này được tăng lên và khi 
đến ngưỡng thì cá thể đó sẽ bị đào thải [1]. 
APGA (Genetic Algorithm Adaptive Population 
Size) được giới thiệu bởi Back, Eiben và van de 
Vaart năm 2000. Thuật toán này cũng sử dụng độ 
tuổi của cá thể song việc chọn lọc tạo sinh duy trì 
phần tử ưu tú. Cơ chế đánh giá thời gian sống 
(lifetime) của cá thể mềm dẻo hơn bởi việc đánh 
giá thời gian duy trì cá thể (RLT – Remaining 
LifeTime) và chiến lược chọn lọc tạo sinh có tính 
tinh hoa [1], [2]. 
2.Thay đổi kích cỡ quần thể dựa trên độ thích 
nghi trung bình 
Chúng tôi đề xuất một kỹ thuật biến đổi kích 
cỡ quần thể ngay trong quá trình tiến hoá dựa trên 
độ thích nghi trung bình của quần thể. Với kỹ 
thuật này ta sử dụng thêm một tham số là độ thích 
nghi trung bình của quần thể. Độ thích nghi trung 
bình của quần thể được tính theo công thức sau: 
popsize
veval
nessAverageFit i
i
SizePopulation
1
trong đó PopulationSize là kích cỡ quần thể, vi 
là các cá thể trong quần thể tại thế hệ hiện tại, hàm 
eval là hàm lượng giá. Thuật toán cụ thể như sau: 
procedure BaseOnAverageFitness{ 
 Khởi tạo quần thể; 
 startpopsize=popsize; 
 Tính độ thích nghi của các cá thể eval (vi); 
 Tính AverageFitness; 
 While (chưa thỏa điều kiện dừng) do 
 Begin 
Lựa chọn ngẫu nhiên 2 cá thể P1 và P2 trong quần 
thể ; 
52(4): 64 - 68 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
2 
Lai ghép (P1, P2) được 2 con là C1 và C2; 
 Đột biến (C1, C2); 
 Tính độ thích nghi của C1 và C2; 
If (độ thích nghi của P1 và P2 < 
AverageFitness) then 
Đào thải P1 và P2 ra khỏi quần thể; 
If (độ thích nghi của C1 và C2 > 
AverageFitness) then 
 Bổ sung C1 và C2 vào quần thể; 
 If (popsize =2* startpopsize) then 
 Tạo sinh lại quần thể; 
 Tính lại AverageFitness của quần thể mới; 
 End; 
 End; 
Các mô hình thử nghiệm 
Chúng tôi sử dụng 6 hàm sau đây để tiến hành 
thử nghiệm [6]. Các hàm thử nghiệm đều được xét 
với số chiều n = 30; miền S được giới hạn cho mỗi 
biến xi và cho trong bảng. Giá trị fmin là giá trị đúng 
tính trên miền xác định tương ứng với mỗi hàm. 
Trong thử nghiệm, chúng tôi sử dụng giải 
thuật di truyền mã hóa số thực (RCGA), với kích 
cỡ quần thể ban đầu là popsize=50, không gian tìm 
kiếm có số chiều là n=30, xác suất lai ghép pc=1, 
xác suất đột biến pm=0.01, và số lần lặp là 2000 
lần. Để tiện so sánh, chỉ một toán tử lai ghép được 
sử dụng, đó là toán tử lai ghép số học – toán tử có 
độ ổn định cao và khả năng hội tụ tương đối tốt 
[1], [5], [6]. Khi thực hiện chương trình, chỉ có một 
cá thể con được đột biến theo xác suất đột biến pm, tỉ 
lệ hai con C1 và C2 được chọn để đột biến là như 
nhau. Sau đây giới thiệu 3 mô hình tạo sinh quần thể 
khi kích cỡ quần thể đạt đến giới hạn cho phép. 
Mô hình 1 
Bước 1: Sắp xếp các cá thể trong quần thể hiện 
tại giảm dần theo độ thích nghi 
Bước 2: Đưa popsize-1 cá thể có độ thích nghi 
cao nhất trong quần thể cũ vào quần thể mới 
Bước 3: Đưa ngẫu nhiên 1 cá thể trong số các 
cá thể còn lại của quần thể cũ vào quần thể mới. 
Như vậy quần thể mới sẽ bao gồm gần như 
tuyệt đối các cá thể có độ thích nghi cao nhất sau 
một quá trình tiến hóa xác định. 
Hình 1: Đồ thị kích cỡ quần thể mô hình 1 
Mô hình 2 
Bước 1: Sắp xếp các cá thể trong quần thể hiện 
tại giảm dần theo độ thích nghi 
Bước 2: Đưa popsize/2 cá thể có độ thích nghi 
cao nhất trong quần thể cũ vào quần thể mới 
Bước 3: Tiếp tục đưa popsize - popsize/2 cá thể 
có độ thích nghi thấp nhất trong quần thể cũ vào 
quần thể mới. Trong trường hợp này, quần thể mới 
không bao gồm hầu hết các cá thể tốt nhất của 
quần thể cũ nhưng tính đa dạng trong quần thể lại 
được đảm bảo hơn. 
Bảng 1. Các hàm thử nghiệm 
Hàm thử nghiệm n S fmin 
n
i
ixf
1
2
1
30 [-100, 100] 0 
n
i
ixf
1
2
2 )5.0(
 30 [-100, 100] 0 
n
i
n
i
ii xxf
1 1
3 ||||
 30 [-10, 10] 0 
1
1
222
14 ))1()(100(
n
i
iii xxxf
30 [-30, 30] 0 
n
i
ii xxf
1
5 )||sin(
 30 [-500, 500] -12569 
52(4): 64 - 68 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
66 
n
i
ii xxf
1
2
6 )10)2cos(10(
30 [-5, 5] 0 
Hình 2: Đồ thị kích cỡ quần thể mô hình 2 
Mô hình 3 
Bước 1: Xét ngẫu nhiên 2 cá thể trong trong 
quần thể hiện tại, cá thể nào có độ thích nghi cao 
hơn sẽ được đưa vào quần thể mới. 
Bước 2: Loại bỏ 2 cá thể đã được xét ra khỏi 
quần thể hiện tại. 
Bước 3: Quay lại bước 1 cho đến khi các cặp 
cá thể đều được xem xét. 
Với mô hình này, tính cạnh tranh, đấu tranh 
sinh tồn giữa các cá thể trong quần thể được thể 
hiện rõ nhất. Cá thể nào có độ thích nghi tốt hơn 
trong cặp cá thể được chọn có cơ hội sống sót đến 
thế hệ sau. Tính đa dạng của quần thể cũng được 
được đảm bảo. 
Hình 3: Đồ thị kích cỡ quần thể mô hình 3 
Kết quả thử nghiệm 
Tại mỗi lần chạy, cá thể có độ thích nghi cao 
nhất (giá trị hàm mục tiêu nhỏ nhất) được ghi nhận 
lại. Sau 20 lần chạy độc lập trên cùng một cấu 
hình máy tính, giá trị tốt nhất tìm được, trung bình 
cộng, cũng như thời gian chạy trung bình của các 
lần chạy này được tính và trình bày trong các bảng 
số liệu kết xuất dưới đây. 
Bảng 2 trình bày kết quả thử nghiệm sau 20 
lần chạy độc lập. Với mỗi hàm, chương trình thử 
nghiệm theo cả ba mô hình đề xuất trên, giá trị 
trung bình của cá thể tốt nhất tìm được sau mỗi lần 
chạy được ghi trong cột tương ứng. Dưới đây là 
hình minh hoạ độ biến đổi của đồ thị giá trị của các 
hàm tương ứng với các mô hình đã đề xuất trên 
Hình 4: Đồ thị giá trị hàm f1 
Hình 5: Đồ thị giá trị hàm f2 
Bảng 2: Kết quả thử nghiệm thuật toán biến đổi kích cỡ quần thể dựa trên độ thích nghi trung bình 
Hàm thử nghiệm Kích cỡ cố định Mô hình 1 Mô hình 2 Mô hình 3 
f1 361.7346 638.9141 535.2382 649.8801 
f2 431.1500 651.5500 562.7500 604.5500 
f3 4.8268 6.1828 11.7998 7.2641 
f4 36424.8180 50776.1510 31100.1967 39853.0663 
f5 -2674.3462 -2874.3432 -2541.4488 -2770.4161 
Kết quả hội tụ - Hàm f1
0.0000
200.0000
400.0000
600.0000
800.0000
1000.0000
1200.0000
1400.0000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Lần chạy
G
iá
 t
r
ị 
h
à
m
Cố định
Mô hình 1
Mô hình 2
Mô hình 3
Kết quả hội tụ - Hàm f2
0.0000
200.0000
400.0000
600.0000
800.0000
1000.0000
1200.0000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Lần chạy
G
iá
 t
r
ị 
h
à
m
Cố định
Mô hình 1
Mô hình 2
Mô hình 3
52(4): 64 - 68 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
67 
f6 100.5761 83.2940 104.5281 85.0702 
Hình 6: Đồ thị giá trị hàm f3 
Hình 7: Đồ thị giá trị hàm f4 
Hình 8. Đồ thị giá trị hàm f5 
Hình 9. Đồ thị giá trị hàm f6 
Chúng tôi đưa vào kết quả chạy bởi thuật toán 
có kích cỡ quần thể cố định để so sánh. Dựa vào 
bảng dữ liệu kết xuất cũng như đồ thị kết quả trên 
ta có thể rút ra một số nhận xét như sau: 
Đối với các hàm f1, f2, và f3, các mô hình thay 
đổi kích cỡ quần thể đã đề xuất đều cho kết quả 
trung bình, cũng như kết quả tốt nhất giữa các lần 
thử nghiệm không tốt bằng kết quả của mô hình 
kích cỡ quần thể cố định. Đồng thời độ ổn định 
của các giải thuật là như nhau (độ lệch giữa kết 
quả tốt nhất và kết quả trung bình). Thời gian chạy 
giữa các giải thuật cũng là tương đương nhau (độ 
chênh lệch là không đáng kể). Các hàm f4, f5 và f6 
có rất nhiều cực trị địa phương, khi đó kết quả của 
việc biến đổi kích cỡ quần thể đều cho kết quả tốt 
hơn thuật toán với kích cỡ quần thể cố định. 
3) Thay đổi kích cỡ quần thể dựa trên số lần lặp 
Với kỹ thuật này chúng tôi cũng sử dụng tham 
số độ thích nghi trung bình của quần thể, nhưng 
điểm khác biệt của thuật toán này như sau: 
Trong repTime thế hệ đầu tiên ta để kích cỡ 
quần thể thay đổi theo cách như trên. (repTime là 
một số nguyên bất kỳ nằm trong khoảng (0..số lần 
lặp)). Trong repTime thế hệ tiếp theo kích cỡ quần 
thể lại được giữ cố định như giải thuật di truyền 
thông thường. Lặp lại quá trình trên cho đến khi 
thỏa điều kiện thì dừng thuật toán. 
Thuật toán cụ thể như sau: 
procedure BaseOnRepeatTime 
 Begin 
 Khởi tạo quần thể; 
Tính độ thích nghi của các cá thể: eval (vi); 
Tính độ thích nghi trung bình của quần thể 
AverageFitness; 
 raise=true; i=0; 
 While (i<RepeatTime) do 
 Begin 
 i=i+1 
 if (i mod repTime=0) 
 if (raise) then 
Chọn PopulationSize cá thể có độ thích nghi tốt nhất 
đưa vào quần thể mới; raise=false; 
 else raise=true; 
Lựa chọn ngẫu nhiên 2 cá thể P1 và P2 trong quần thể ; 
Lai ghép (P1, P2) được 2 con là C1 và C2; 
Đột biến (C1, C2); 
Tính độ thích nghi của C1 và C2; 
if (raise) then 
if (độ thích nghi của P1 và P2 < AverageFitness) then 
Loại P1 và P2 ra khỏi quần thể; 
if (độ thích nghi của C1 và C2 > AverageFitness) then 
Bổ sung C1 và C2 vào quần thể; 
else 
Kết quả hội tụ - Hàm f3
0.0000
5.0000
10.0000
15.0000
20.0000
25.0000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Lần chạy
G
iá
 t
r
ị 
h
à
m Cố định
Mô hình 1
Mô hình 2
Mô hình 3
Đồ thị hội tụ - Hàm f4
0.0000
20000.0000
40000.0000
60000.0000
80000.0000
100000.0000
120000.0000
140000.0000
160000.0000
180000.0000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Lần chạy
G
iá
 t
r
ị 
h
à
m Cố định
Mô hình 1
Mô hình 2
Mô hình 3
Đồ thị hội tụ - Hàm f5
-4000.0000
-3500.0000
-3000.0000
-2500.0000
-2000.0000
-1500.0000
-1000.0000
-500.0000
0.0000
1 3 5 7 9 11 13 15 17 19
Lần chạy
G
iá
 t
r
ị 
h
à
m
Cố định
Mô hình 1
Mô hình 2
Mô hình 2
Đồ thị hội tụ - Hàm f6
0.0000
20.0000
40.0000
60.0000
80.0000
100.0000
120.0000
140.0000
160.0000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Lần chạy
G
iá
 t
r
ị 
h
à
m Cố định
Mô hình 1
Mô hình 2
Mô hình 3
52(4): 64 - 68 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
68 
Loại P1 và P2 ra khỏi quần thể; 
Bổ sung C1 và C2 vào quần thể; 
 End 
 End 
Hình 10: Đồ thị kích cỡ quần thể 
Các tham số thực nghiệm 
Thuật toán trên sử dụng giải thuật di truyền mã 
hóa số thực (RCGA), với kích cỡ quần thể ban đầu 
là popsize=50, không gian tìm kiếm có số chiều là 
n=30, xác suất lai ghép pc=1, xác suất đột biến 
pm=0.01, số lần lặp là 2000 lần, 
thuật toán sử dụng toán tử lai ghép số học. Biến 
raise được sử dụng để xác định trong giai đoạn 
hiện tại, kích cỡ quần thể là cố định hay thay đổi, 
repTime=50. 
Thử nghiệm được tiến hành với 6 hàm BenchMark 
đã được trình bày ở trên. Kết quả thử nghiệm được 
cho trong bảng 3. Các cột 2 và 3 cho giá trị hàm 
mục tiêu của cá thể tốt nhất tìm được sau 20 lần 
chạy. Các cột 4 và 5 cho giá trị trung bình của cá 
thể tốt nhất trong 20 lần chạy. 
Nhận xét: 
Tương tự như kỹ thuật biến đổi kích cỡ quần thể 
dựa trên độ thích nghi trung bình, kỹ thuật này chỉ 
cho kết quả tốt hơn thuật toán với kích cỡ quần thể 
cố định đối với hàm có nhiều cực trị địa phương. 
IV. Thảo luận và kết luận 
Nhìn vào những kết quả trên, ta thấy các mô 
hình đưa ra chưa hoàn toàn cho kết quả tốt với tất 
cả các hàm thử nghiệm mà chỉ cho kết quả tốt với 
các hàm đa cực trị. Tuy nhiên những kết quả đó chỉ 
là những nghiên cứu ban đầu về giải thuật di truyền 
với kích cỡ quần thể thay đổi, chỉ sử dụng một loại 
toán tử lai ghép. Những mô hình đưa ra cần có thời 
gian nghiên cứu sâu hơn để có thể cho kết quả tốt 
hơn, chẳng hạn sử dụng các dạng toán tử lai ghép 
khác, các dạng toán tử chọn lọc khác, cũng như việc 
lựa chọn các tham số đầu vào phù hợp hơn. 
Bảng 3. Kết quả thử nghiệm khi thay đổi kích cỡ quần thể dựa trên số lần lặp 
Hàm thử nghiệm Giá trị tốt nhất Giá trị trung bình 
Kích cỡ cố định Kích cỡ biến đổi Kích cỡ cố định Kích cỡ biến đổi 
f1 155.6121 252.4066 361.7346 457.6235 
f2 208.0000 226.0000 431.1500 452.2500 
f3 2.3487 2.7201 4.8268 5.7816 
f4 11605.4258 9812.4921 36424.8180 25168.4229 
f5 -3235.2783 -4054.1986 -2674.3462 -3332.0388 
f6 62.4577 53.9499 100.5761 84.8775 
Tài liệu tham khảo 
[1] A.E. Eiben, E. Marchiori, V.A. Valkó, Evolutionary 
Algorithms with on-the-fly Population Size Adjustmen, 
Parallel Problem Solving from Nature PPSN VI, LNCS 
1917, Springer, 2004. 
[2] Fernando G. Lobo, Claudio F. Lima, Revisiting 
Evolutionary Algorithms with on-the-fly Population 
Size Adjustmen, UALG-ILAB Technical Report 
N.200602, 2006. 
[3] Ulrich Bodemhofer, Generic Algorithms: Theory 
and Application, Lecture Notes, 2004 
[4] Nguyễn Hoàng Phương, Nadipuram R.Prasad, Lê Linh 
Phong, Nhập môn trí tuệ tính toán, NXB KH&KT, 2002. 
[5] Nguyễn Đình Thúc, Lập trình tiến hoá, NXBGD, 
2001. 
[6] Vũ Mạnh Xuân, Nguyễn Thanh Thủy, Biểu diễn 
toán tử lai ghép trong giải thuật di truyền mã hóa số 
thực, Tạp chí Khoa Học & Công Nghệ, ĐHTN. 
52(4): 3 - 12 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009 
69 
Summary 
Genetic algorithm with selection, crossover, mutation operators is used to found the solution of the natural 
evolutionary simulation problems. This paper studies and proposes several techniques in order to adjust 
parameters in the evolutionaryprocess. 
 Keyword: Genetic algorithm, population size, crossover.