1
BỘ GIÁO DỤC & ĐÀO TẠO VIỆN KH & CN VIỆT NAM
VIỆN CÔNG NGHỆ THÔNG TIN
VŨ MẠNH XUÂN
PHÁT TRIỂN MỘT SỐ KỸ THUẬT
TRONG TÍNH TOÁN MỀM
Chuyên ngành: Bảo đảm toán học cho máy tính
và hệ thống tính toán
Mã số: 62.46.35.01
TÓM TẮT LUẬN ÁN TIẾN SĨ
HÀ NỘI - 2007
2
Công trình được hoàn thành tại: Viện Công nghệ thông tin
thuộc Viện Khoa học và Công nghệ Việt Nam
Người hướng dẫn khoa học:
1. PGS.TS Nguyễn Thanh Thủy
2. PGS.TS Lương Chi Mai
Phản biện 1: . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
Phản biện 2: . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
Phản biện 3: . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp nhà nước
họp tại: . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
vào hồi giờ ngày tháng năm 200
Có thể tìm hiểu luận án tại: Thư viện Quốc gia
Viện Công nghệ thông tin - Viện KH & CN Việt nam
Khoa Khoa học Tự nhiên – Đại học Thái Nguyên
3

Mục tiêu của luận án là nghiên cứu vấn đề thích nghi và tự thích nghi trong
tính toán tiến hóa; đề xuất các giải pháp cải tiến thuật toán và ứng dụng cơ
chế thích nghi giải các bài toán tối ưu.
Như vậy, đối tượng chính của luận án là các thuật toán tiến hóa bao
gồm giải thuật di truyền, chiến lược tiến hóa, giải thuật mô phỏng tôi luyện,
áp dụng để giải một lớp bài toán tối ưu số và ứng dụng. Phương pháp làm
việc là nghiên cứu các tài liệu trong và ngoài nước về tính toán tiến hóa,
trọng tâm là giải thuật di truyền; khảo sát, đề xuất một số giải pháp nhằm
nâng cao hiệu quả của giải thuật, tiến hành thử nghiệm trên một số bài toán
mẫu và ứng dụng các kỹ thuật này trong bài toán tối ưu đa mục tiêu thực tế.
Nội dung luận án gồm ba chương không kể các phần mở đầu, kết luận.
Chương một nêu khá chi tiết về giải thuật di truyền (GA) và tính toán
tiến hóa nói chung. Trước hết là GA kinh điển với các toán tử di truyền cơ
bản và minh họa bằng một ví dụ cụ thể. Phần kế tiếp trình bày nền tảng toán
học của GA với hai nội dung chính là định lý sơ đồ của Holland và mô hình
xích Markov của GA. Giải thuật di truyền mã hóa số thực (RCGA – Real-
Coded Genetic Algorithm) với các toán tử di truyền được đề cập đến một
cách chi tiết. Toán tử lai ghép với nhiều dạng khác nhau kể cả các dạng lai
ghép nhiều cá thể cha mẹ cũng được mô tả một cách cẩn thận. Phần này cũng
nêu lên một số mô hình tiến hóa được giới thiệu trong thời gian gần đây.
Phần cuối của chương đề cập đến các dạng tính toán tiến hóa khác là chiến
lược tiến hóa (ES – Evolutionary Straitegy) và quy hoạch tiến hóa (EP -
5
Evolutionary Programming). Giải thuật mô phỏng tôi luyện (SA-Simulated
Annealing) cũng được trình bày làm cơ sở cho việc tích hợp với các kỹ thuật
khác.
Chương hai tập trung trình bày các kết quả nghiên cứu của tác giả về
vấn đề tự thích nghi trong giải thuật di truyền mã hóa số thực và tính toán
tiến hóa nói chung. Cụ thể trong chương này đưa ra một số kết quả sau:
1) Phân tích tác động các tham số của RCGA đến sự hội tụ của giải thuật, tập

Chương 1
MỘT SỐ VẤN ĐỀ CƠ BẢN
Chương này trình bày chủ yếu về giải thuật di truyền (GA), bao gồm
GA kinh điển, nền tảng toán học của GA, GA mã hóa số thực (RCGA), chiến
lược tiến hóa (ES) và quy hoạch tiến hóa (EP). GA kinh điển được trình bày
chi tiết từ việc mã hóa, các toán tử di truyền đến mô tả tường minh trong một
ví dụ cụ thể. Nền tảng toán học của GA được trình bày thông qua định lý sơ
đồ của Holland và mô hình Markov của GA dựa trên các kết quả của
Rudolph và Suzuki. Phần tiếp theo trình bày giải thuật di truyền mã hóa số
thực (RCGA) khá tường tận, đặc biệt là những dạng khác nhau của toán tử
lai ghép. Phần cuối chương là chiến lược tiến hóa (ES), quy hoạch tiến hóa
(EP) và một số dạng của giải thuật mô phỏng tôi luyện (SA).
7
Chương 2
NGHIÊN CỨU CƠ CHẾ TỰ THÍCH NGHI
TRONG TÍNH TOÁN TIẾN HÓA
Chương này trình bày những kết quả nghiên cứu và đề xuất một số kỹ
thuật tự thích nghi trong tính toán tiến hóa. Trước tiên là khái quát về vấn đề
tự thích nghi trong tính toán tiến hóa, phân tích tác động của các tham số sử
dụng trong giải thuật di truyền chủ yếu là kích cỡ quần thể. Tiếp theo là
nghiên cứu về toán tử lai ghép SBX, cùng với các phiên bản tính tham số
điều khiển sử dụng các biến ngẫu nhiên với các phân phối xác suất khác
nhau. Tiếp theo là một thuật toán đề xuất cho phép chọn lựa thích nghi toán
tử lai ghép ngay trong quá trình thực hiện. Phần cuối chương là một phương
pháp tích hợp giải thuật di truyền, chiến lược tiến hóa và giải thuật mô phỏng
tôi luyện nhằm làm tăng hiệu quả tính toán. Các kết quả chính được trình bày
trong chương hai gồm:
2.1. TỰ THÍCH NGHI TRONG TÍNH TOÁN TIẾN HÓA
Phần này trình bày khái quát về vấn đề thích nghi và tự thích nghi
trong tính toán tiến hóa.

i
i
xxxf
π

với n = 30, -5.12 x
i
5.12.
Hàm này có rất nhiều cực trị địa phương trong miền đang xét, số cực
trị này tăng theo lũy thừa khi số chiều tăng. Hình 2.12 là kết quả thực hiện
chương trình.
Trong đồ thị trên, trục tung là giá trị hàm mục tiêu, trục hoành ứng với
các mốc lặp 1000, 2000, , 10000. Mỗi đường đồ thị biểu diễn giá trị trung
bình hàm mục tiêu của quần thể ứng với kích cỡ chọn từ dưới lên là 10, 20,
, 100. Kết quả phù hợp với nhận xét trên.
-
100.00
200.00
300.00
400.00
500.00
600.00
1 2 3 4 5 6 7 8 9 10
Hình 2.12. Hàm Rastringin sử dụng
lai ghép một điểm
9
2.2.2. Quan hệ giữa kích cỡ quần thể và số chiều không gian tìm kiếm
Phần này khảo sát mối quan hệ giữa kích cỡ quần thể và số chiều
không gian tìm kiếm trên các hàm khác nhau với các dạng toán tử lai ghép
khác nhau. Kết quả cho thấy giá trị trung bình hàm mục tiêu của quần thể

600
800
1000
1200
1400
1600
1 2 3 4 5
Hình 2.17 Lai ghép mặt nạ với hàm
Rastringin
10
thể con tạo được sau lai ghép là X’ = (x’
1
, x’
2
, , x’
m
) và Y’ = (y’
1
, y’
2
, , y’
m
).
Khi đó quan hệ giữa (X’, Y’) và (X, Y) được biểu diễn bởi phép nhân ma
trận:
(X', Y') = (X, Y). F(a, b)
trong đó




),(
1
BAI
BIA
baF
ở đây A' và B' là các ma trận đường chéo cấp m với các phần tử trên đường
chéo tương ứng là các a'
i
và b'
i
, trong đó:
1
';
1
'
−+
=
−+
=
ii
i
i
ii
i
i
ba
a
b
ba
b

ZZ
=
.
Do z > > 0 nên xác suất chuyển có thể gộp lại như sau:
2* *f
Z
(z + ) P{0 (z - , z + )} 2* *f
Z
(z - ) (2.1)
Như vậy, xác suất lai ghép thành công (tạo được con có xu hướng
chuyển từ tối ưu cục bộ đến tối ưu toàn cục) tại bước thứ k là:
p
k
= P{0 (z - , z + ) tại bước k} q
k
= 2* *f
Z
(z + )
(2.2)
Do đó, xác suất chuyển đến lân cận (z - , z + ) của z sau t bước lặp
(t 0) là:
∏∏
==
−−≥−−
t
k
k
t
k
k

1
, x
2
, x
n
) và y = (y
1
, y
2
, , y
n
) là hai cá thể cha mẹ đã
chọn để tạo sinh. Khi đó hai cá thể con c
1
= (c
1
1
, , c
1
n
) và c
2
= (c
2
1
, , c
2
n
)
được sinh ra theo công thức

otherwise
u
uifu
1
1
1
1
)
)1(*2
1
(
5.0)*2(
η
η
β
(2.6)
với u là số ngẫu nhiên trong [0, 1]; là tham số điều khiển.
Toán tử SBX có thể mô tả vắn tắt như sau:
Bước 1. Chọn ngẫu nhiên số thực u [0, 1].
Bước 2. Tính theo công thức (2.6), tham số này có thể tính riêng với mỗi
thành phần hoặc dùng chung.
Bước 3. Tính các con c
1
và c
2
theo công thức (2.4) và (2.5).
Nghiên cứu toán tử này, ta có một số nhận xét sau
a) SBX có thể biểu diễn nhiều dạng toán tử lai ghép khác
+ Lai ghép 1 điểm với điểm lai ghép là t (1 t n-1) ứng với cách chọn
k

k
+ d*(x
k
– y
k
).
13
+ Lai ghép BLX- ứng với cách đặt
k
= 2*r – 1, trong đó r là số ngẫu
nhiên được lấy trong [- , 1+ ].
b) Tác động của tham số
Từ các công thức (2.4) và (2.5), ta thấy ngay khoảng cách mỗi thành
phần của các cá thể con sinh ra tỷ lệ với khoảng cách tương ứng của cha mẹ
chúng. Thật vậy trừ theo từng vế (2.4) và (2.5) ta được:
c
1
i
– c
2
i
= *(x
i
– y
i
)
Kết quả này rất quan trọng vì ở đây chúng ta quan tâm đến việc cá thể
con sinh ra gần hay xa nhau nhằm đảm bảo tính đa dạng của quần thể.
2.3.4 Toán tử SBX sử dụng phân phối Cauchy
Xét biến ngẫu nhiên Z theo phân phối Cauchy có hàm mật độ xác suất:

luyện và toán tử lai ghép với sơ đồ tôi luyện là T
k
= 1/k.
Bảng 2.3 dưới đây cho kết quả trung bình sau năm lần chạy độc lập đối
với mỗi hàm thử nghiệm, mỗi lần chạy thực hiện tạo sinh 500 thế hệ cho một
dạng toán tử đã nêu.
Bảng 2.3 Kết quả thử nghiệm với các toán tử khác nhau
Hàm số Giá trị
khởi tạo
Lai ghép
số học
Lai ghép
1 điểm
Lai ghép
mặt nạ
Lai ghép
BLX-0.5
Lai SBX-
Cauchy
f
1
68223 16075.8 22405.4 7602.7 3026.2 1373.6
f
3
3.04E+12 45.237 67.223 29.793 18.832 17.041
f
4
233230 13223.9 53038.6 6133.9 1914.5 492.3
f
5

2
1
σ
πσ
β
x
(2.7)
15
Phân phối này có kỳ vọng EX = 0 và phương sai VX =
2
. Đường cong
mật độ có dạng hình chuông nhận trục hoành làm tiệm cận. Trong tự nhiên,
nhiều quy luật biến đổi theo phân phối chuẩn, chẳng hạn trọng lượng, chiều
cao của người lớn, chỉ số thông minh của trẻ em, các sai số đo đạc, độ bền
dẻo của máy móc, .
- Phân phối Loga chuẩn: Tương tự như phân phối chuẩn, một dạng khác
được quan tâm đến là phân phối loga chuẩn. Trong trường hợp này được
tính theo số ngẫu nhiên x bởi công thức:






−=
2
2
2
)(ln
exp

16
Kết quả thử nghiệm
Dưới đây chỉ trình bày kết quả thử nghiệm đối với một bài toán.
Bài toán 2.3.5: Hàm Griewangk
1)cos(
4000
1
)(
1
1
2
6
+−=
∏
∑
=
=
n
i
i
n
i
i
i
x
xxf

với n = 30, -5.12 x
i
5.12

nếu tiếp tục tăng số lần tạo sinh.
- Khi tiến hành thử nghiệm tác động của kích cỡ quần thể đối với toán tử
SBX sử dụng các phân phối xác suất nêu trên, kết quả là SBX với phân
phối mũ trong hầu hết các hàm thử nghiệm đều cho kết quả tốt nhất khi
kích cỡ quần thể khoảng 20 đến 30 cá thể. Giá trị này không phụ thuộc
vào số lần lặp như các dạng lai ghép kinh điển khác.
- Khi tiến hành thử nghiệm cùng các hàm trên với miền xác định của mỗi
biến không đối xứng như trường hợp trên và lời giải đúng không nằm giữa
mà gần biên của miền xác định (chẳng hạn -1 x
i
12 với mọi i) thì kết
quả cũng không biến động mấy so với các bảng đã trình bày ở trên. Nói
chung biến đổi theo phân phối mũ vẫn cho kết quả tốt nhất.
2.4. CƠ CẤU LỰA CHỌN THÍCH NGHI TOÁN TỬ LAI GHÉP
Phần này đề xuất một cơ cấu lựa chọn thích nghi toán tử lai ghép thích
hợp ngay trong quá trình tiến hóa. Để tiện việc trình bày, ta xem xét trường
hợp sử dụng hai toán tử lai ghép. Với hai toán tử lai ghép đã được thiết kế
trước, tại mỗi lần lặp, thuật toán sẽ quyết định sử dụng toán tử nào phụ thuộc
vào tỷ lệ áp dụng thành công của toán tử đó. Ký hiệu LG1 và LG2 là hai toán
tử lai ghép,
apply
LG
P
1
và
apply
LG
P
2
là xác suất áp dụng LG1 hay LG2, các giá trị này

LG
P
1
và
success
LG
P
2
là tỷ lệ để toán tử lai ghép tương ứng tạo được con
tốt hơn cha mẹ trong lần áp dụng cuối cùng của LG1 hay LG2 tương ứng.
Thuật toán đề xuất tạm gọi là OAGA (Operator Adaptive Genetic
Algorithm) được mô tả như sau:
Input : Quần thể có m cá thể được khởi tạo ngẫu nhiên.
Output : Cá thể có độ thích nghi (theo giá trị hàm mục tiêu F) cao nhất.
Algorithm:
B1) Tạo sinh quần thể ban đầu:
Tạo ngẫu nhiên m véc tơ thực (mỗi véc tơ ứng với một cá thể).
Khởi tạo
apply
LG
P
1
bởi người sử dụng. Đặt
apply
LG
apply
LG
PP
12
1−=

apply
LG
P
1
. Ký hiệu toán tử
được chọn là LG.
- Áp dụng toán tử LG trên Parent1 và Parent2 tạo ra hai con Child1 và
Child2.
- N
i
= N
i
+ 1 (trong đó N
i
tương ứng LG)
Chọn cá thể sống sót:
19
Chọn hai cá thể từ quần thể chứa cả cha mẹ và các con của chúng như
sau: cá thể thứ nhất là cá thể có độ thích nghi cao nhất, cá thể thứ hai được
chọn từ các cá thể còn lại theo cách chọn tỷ lệ.
Thay thế hai cha mẹ bởi hai cá thể vừa chọn.
Nếu có con tốt hơn cả hai cha mẹ thì TC
i
= TC
i
+1 (TC
i
tương ứng với
toán tử LG đã chọn).
B4) Tính lại xác suất chọn toán tử

toán tử trong quá trình thực hiện giải thuật. Dưới đây đưa ra kết quả thử
nghiệm với một bài toán cụ thể.
Bài toán 2.4.4. Min
∑
=
+=
n
i
iin
xxnxxxf
1
21
))||sin(*(*9828.418), ,,(
với n = 30; -500 x
i
500 với i = 1, ,30
Bảng 2.12 Kết quả thử nghiệm bài toán 2.4.4
Lần
chạy
Cá thể tốt
nhất khởi tạo
Cá thể tốt
nhất khi lai
BLX-0.5
Cá thể tốt
nhất khi lai
mặt nạ
Cá thể tốt nhất theo
cơ chế chọn thích
nghi

bằng cách:
- Chọn ngẫu nhiên một cặp cha mẹ.
- Thực hiện toán tử lai ghép, tạo thêm hai cá thể mới đưa vào Q.
Quá trình này tiến hành (M div 2) lần.
Bước 3) Với mỗi cá thể của quần thể trung gian Q, thực hiện toán tử sinh cá
thể mới theo phương pháp của SA:
- Child(i) = generate(X
i
, T
k
).
- Nếu Child(i) tốt hơn X
i
thì thay X
i
bởi Child(i).
Bước 4) Trong Q chọn (m-1) cá thể tốt nhất; cá thể thứ m được chọn theo
cách chọn tỷ lệ trong các cá thể còn lại đưa vào quần thể thế hệ kế tiếp.
T
k+1
= Update(T
k
). {cập nhật lại nhiệt độ}
k = k+1.
Bước 5) Nếu T
k
< T
dong
hoặc số lần lặp đủ lớn thì chuyển sang Bước 6, còn
nếu không quay lại Bước 2.

f
6
37.51 410.86 401.08 174.16
Rõ ràng thuật toán mới cho kết quả tốt hơn các thuật toán sử dụng
riêng lẻ. Mặt khác, tư tưởng chính của thuật toán là sử dụng cả hai toán tử di
truyền nhằm tăng tính đa dạng của quần thể. Điều này cũng cho thấy trong
các thuật toán tiến hoá, tính đa dạng của quần thể có một vai trò quan trọng.
Chương 3
MỘT SỐ ỨNG DỤNG TRONG
BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU
Chương này trình bày một ứng dụng cụ thể của giải thuật di truyền
trong lĩnh vực khí tượng thủy văn. Phần đầu của chương này dành để giới
thiệu vắn tắt giải thuật di truyền đa mục tiêu. Phần kế tiếp trình bày các thuật
toán đề xuất và kết quả thực nghiệm giải một số bài toán trong khí tượng thủy
văn là bài toán thiết kế hồ chứa nước (Rei-Vemuri), bài toán phân bố dòng
chảy và bài toán bốn hồ chứa.
3.1. GIẢI THUẬT DI TRUYỀN ĐA MỤC TIÊU
Phần này trình bày những vấn đề cơ bản của bài toán tối ưu đa mục
tiêu và giải thuật di truyền đa mục tiêu dựa trên xếp hạng không trội các cá
thể.
3.2. TỐI ƯU ĐA MỤC TIÊU SỬ DỤNG TÀI NGUYÊN NƯỚC
Sau đây sẽ trình bày một số bài toán cụ thể trong lĩnh vực này.
22
3.2.1. Bài toán Reid-Vemuri
Phát biểu bài toán: Cần thiết kế hồ chứa nước với thời gian lao động x
1
và bán kính mặt nước là x
2
. Ba vấn đề (mục tiêu) cần quan tâm là:
Tổng giá thành công trình f

) = 0.5 * x
2
2
(3.9)
Dung tích hồ chứa f
3
(x
1
, x
2
) tính theo công thức:
f
3
(x
1
, x
2
) = e
0.005*x1
* x
1
0.01
* x
2
2
(3.10)
Cần tính các giá trị x
1
và x
2

2
= 423; f
3
= 1973.
Lời giải đã biết của bài toán này là: x
1
= 200; x
2
= 26.24; giá trị các
hàm mục tiêu tương ứng là f
1
= 5656.36; f
2
= 344.27; f
3
= 1973.
Ta tiến hành giải bài toán như sau:
a) Sử dụng phương pháp vét cạn:
Tiến hành chạy chương trình với các mục tiêu cần đạt cho trước là
A = 4800; B = 400; C = 2000 (các giá trị này đều chọn “tốt hơn” giá trị trung
bình cần đạt) và ngưỡng sai số đối với mỗi hàm mục tiêu đều là 40. Với độ
chính xác của lời giải là 0.1, các lời giải cho cả ba mục tiêu nằm trong
ngưỡng sai số cho phép được ghi lại để theo dõi, chương trình chạy mất 3.9
giây, có 191 lời giải nằm trong ngưỡng. Lời giải có sai số tổng cộng nhỏ nhất
23
thu được là 21.42 với các giá trị cụ thể: x
1
= 165.4; x
2
= 28.8; giá trị các hàm

thời lại thải nước ở hạ lưu. Hồ chứa với dung tích S có tác dụng cấp nước và
thông rửa dòng chảy ở hạ lưu.
Giả sử các biến quyết định x
i
(i=1,2,…,N) là lượng chất thải phải xử lý
cần thỏa mãn điều kiện 0.45 x
i
0.99. Gọi y là lượng nước cần thông rửa
mà hồ chứa sẽ cung cấp cho hệ thống. Khi đó các mục tiêu cần đạt được là:
1) Cực tiểu hóa giá thành xử lý nước thải
2) Cực đại hóa lượng nước trữ trong hồ chứa.
3) Cực tiểu hóa nồng độ nhiễm bẩn ở dòng chảy.
Tổng giá thành xử lý nước thải f
1
được tính theo công thức:
24
∑
=
−+++=
N
i
i
xqqf
1
2
111
))45.0(*)*7.2557.640(*7.268.160(
(3.11)
trong đó q
i

, b
2
, c
1
, c
2
là các tham số được xác định
tùy thuộc vào vị trí và điều kiện cụ thể của dòng chảy. Giá trị các biến x
i
và y
cần thỏa mãn: 0.45 x
i
0.99 (i=1, …, N) và 0 y S = 3.47.
Kết quả đã biết của bài toán này là:
X=(0.52,0.45,0.7,0.518,0.642,0.542,0.58,0.83,0.51,0.85,0.61,0.65,0.53,0.71,
0.861) và y=0.178; với giá trị các hàm mục tiêu tương ứng là
f
1
= 6422.7; f
2
= 3.292; f
3
= 6.233.
Một số phương pháp giải bài toán này đã được đề xuất như sau:
1) Cho trước các giá trị cần đạt được ứng với từng mục tiêu, thuật toán
cho phép tìm các nghiệm mà giá trị hàm mục tiêu tương ứng gần nhất
với các giá trị này với thời gian rất ngắn.
2) Thuật toán có thể tự ước lượng giá trị căn cứ vào các hàm mục tiêu và
quần thể khởi tạo, sau đó trong quá trình tiến hóa, các giá trị này được
định kỳ cập nhật lại.

3.3197 3.3232 3.3391 3.3594 3.4156
f
3
6.2554 6.2289 6.2343 6.2511 6.2301
Rõ ràng so với các kết quả đã biết thì các lời giải này đều tốt hơn.
3.2.3. Bài toán bốn hồ chứa
Giả sử có bốn hồ chứa nước S
i
(i=1 4) với mục đích sản xuất điện và
tưới tiêu ở hạ lưu. Lợi ích của toàn hệ thống được tính như sau:
∑∑∑∑
=== =
++=
4
1
12
1
45
4
1
12
1
)),13(()().()().(
i
iii
ki k
ii
dsgkukbkukbB
(3.21)
Giả sử các dòng chảy đến S

< 4; 0 < u
4
< 7 (3.18)
Bài toán đặt ra là điều khiển các u
i
(i = 1, 2, 3, 4) để tổng lợi ích thu
được theo công thức (3.21) đạt giá trị cực đại, đồng thời tại thời điểm k = 13
hệ thống cần thỏa mãn điều kiện S
1
= S
2
= S
3
= 5; S
4
= 7 (3.19). Phương trình
cân bằng của hệ thống tại thời điểm (k+1) có thể tính bởi công thức (3.20):
S
1
(k+1) = S
1
(k) + q
1
– u
1
(k)
S
2
(k+1) = S
2