CT 2

I. ĐẶT VẤN ĐỀ
1.1. Xác định nhiệm vụ của bài toán tối ưu
Trong kỹ thuật, khi giải quyết bất kỳ nhiệm vụ nào chúng ta đều mong muốn có phương án
tốt nhất theo một hoặc một vài tiêu chí nào đó. Có thể liệt kê rất nhiều những ví dụ cụ thể như:
tiết kiệm thời gian nhất, chi phí nhỏ nhất, năng suất lớn nhất, quãng đường đi ngắn nhất, thiết kế
kết cấu với trọng lượng vật liệu nhỏ nhất… Để giải được những bài toán này, toán học đã cho ra
đời một ngành là “Quy hoạch toán học” hay “tối ưu hóa” [1], [3].
Bài toán tối ưu nói chung được viết dưới dạng toán học như sau:
Tìm giá trị cực tiểu (hoặc cực đại) hàm:

n
f(x) min(max);x R
 
(1)
Với các điều kiện:
g
i
(x) ≥ 0; i = 1,2, , m
h
i
(x) = 0; i = 1,2, , l
SO SÁNH MỘT SỐ PHƯƠNG PHÁP TÌM KIẾM TỐI ƯU
ỨNG DỤNG TRONG KỸ THUẬT TS. NGUYỄN QUÁN THĂNG

Hàm f(x) trong biểu thức (1) được gọi là hàm mục tiêu hoặc tiêu chuẩn tối ưu, biểu diễn
mối quan hệ giữa tiêu chuẩn chất lượng của quá trình khảo sát và các biến độc lập x.
Các hàm số g
i
(x), h
i
(x) là các điều kiện ràng buộc của bài toán tối ưu dưới dạng đẳng thức
và bất đẳng thức. Trong không gian các biến, các hàm số này tạo ra miền giới hạn D các khả
năng cho phép của hàm f(x).
Nếu như D  R
n
(với R là số chiều của hàm mục tiêu), có nghĩa là không tồn tại bất kỳ một
điều kiện giới hạn nào ta nói rằng bài toán quy hoạch phi tuyến không có điều kiện ràng buộc.
Tuy nhiên trong phần lớn các bài toán tối ưu, người sử dụng thường có băn khoăn đó là:
kết quả nhận được từ quá trình tính đã thật sự là phương án tốt nhất chưa. Để minh họa vấn đề
này ta có thể xét ví dụ như hàm Peaks (2) - hai biến là hàm đơn điệu đa cực trị, được biểu diễn
bằng đồ thị như trên hình 1.

2 2 2 2 2 2
x
(-x -(x +1) ) (-x -x ) (-(x +1) -x )
1
2 3 5
1
1 2 1 2 1 2
f(x) = 3.(1- x ) .e -10.( - x - x ).e - .e
1 1 2
5 3
(2)


phù hợp với môi trường hơn) thế hệ trước. Xuyên suốt quá trình tiến hoá, các thế hệ mới được
sinh ra để bổ sung, thay thế thế hệ cũ, trong quá trình này cá thể nào phát triển hơn thích ứng
hơn với môi trường sẽ tồn tại, cá thể nào kém thích ứng hơn sẽ bị đào thải. Như vậy thuật toán
di truyền đều mô phỏng bốn quá trình tiến hoá cơ bản: lai ghép, đột biến, sinh sản, chọn lọc tự
nhiên.
b. Xây dựng sơ đồ thuật toán
Sơ đồ thuật toán được trình bày trên hình 2a.
Mã hoá các biến và xây dựng quần thể ban đầu (khối 1, 2): Ký hiệu npop_size là số cá thể
trong một quần thể; nếu bài toán có n biến độc lập và mỗi biến được biểu diễn bởi mi(j) bit thì
mỗi phương án cần
n
j 1
nx mi(j)



bit để biểu diễn. Tương ứng, toàn bộ bài toán cần
(npop_size*nx) bit. Để có quần thể ban đầu ta chọn ngẫu nhiên npop_size cá thể trong phạm vi
cho phép.
Quá trình chọn lọc các cá thể (khối 4) trong GA dựa trên độ thích nghi của chúng (khối 3)
thông qua xác suất lựa chọn như định nghĩa bởi biểu thức (4). Để tính xác suất lựa chọn thực
hiện các bước sau:
- Tính độ thích nghi eval(v
i
) cho mỗi cá thể; v
i
(i = 1,2,…, npop_size)
- Tính tổng giá trị thích nghi cho toàn bộ quần thể:

npop_size

(i = 1,2,…, npop_size)

i
q = p
j=1
i j

(5)
Tiến trình chọn lọc được thực hiện bằng cách quay bánh xe Rulet npop_size lần; mỗi một
lần sẽ chọn được một cá thể để đưa vào quần thể mới.
Như vậy sẽ có một số cá thể được chọn hơn một lần và có cá thể đã bị loại bỏ.
Trong quá trình lai ghép (khối 5), thông số có ý nghĩa đối với việc lai ghép là xác suất lai
ghép p
c
, tham số này cho biết số cá thể sẽ tham gia lai ghép trong quần thể là (p
c
*npop_size).
Thường p
c
=0.25 [1], [2], [4].
- Chọn ngẫu nhiên (p
c
*npop_size) cá thể trong quần thể, tiếp tục lại chọn ngẫu một cặp cá
thể trong số các cá thể sẽ lai ghép.
- Chọn ngẫu nhiên điểm lai ghép và tiến hành lai ghép.
Đối với quá trình đột biến (khối 6), thông số khác điều khiển quá trình là xác suất đột biến
p
m
. Tham số này cho biết số bit sẽ đột biến là (p
m

 = f(XP) - f(X). (6)
Giá trị này được sử dụng để xem xét đánh giá nhằm xác định hướng chuyển động tiếp theo
trong quá trình tìm nghiệm (khối 5). Trong bài toán tìm Max, chuyển động đi lên (>0 - uphill)
được chấp nhận, thì điểm mới sẽ thay thế điểm cũ [X(i)=XP(i)] - (khối 7). Một bước đi xuống
(<0 dowhill), cũng có thể được chấp nhận nếu thỏa mãn tiêu chuẩn kiểm tra Metropolis (khối
8, 9). Bằng cách như vậy thuật toán có thể thoát khỏi những cực trị cục bộ và sẽ dừng lại khi
thoả mãn điều kiện dừng (khối 10).
2.3. Thuật tiến hoá vi phân
a. Nguyên lý hoạt động
Trên cơ sở ý tưởng của thuật toán GA, vào năm 1995, Rainer Storn và Kenneth Price đã
hoàn thiện cơ chế đột biến và lai ghép để tạo ra một thuật toán mới tin cậy, hiệu quả hơn. Điểm
khác biệt lớn nhất của DE so với GA là luôn duy trì và bổ sung một cặp 2 véctơ bao gồm
(n_popsize) quần thể với (m) chiều các tham số thực và đã ứng dụng thành công cho nhiều bài
toán tối ưu ở các lĩnh vực khác nhau.
b. Xây dựng sơ đồ thuật toán
Sơ đồ thuật toán được trình bày trên hình 2c.
Cũng như thuật toán GA đã trình bày ở trên, thuật toán tiến hoá vi phân cũng khởi tạo quần
thể các điểm ban đầu P(t) theo quy luật ngẫu nhiên phân bố đều trong miền xác định bài toán
sau khi cho các thông số ban đầu (khối 1, 2). Mỗi phần tử trong quần thể ban đầu này cũng được
DE thực hiện trên miền tham số thực với công thức sau [5]:

x = rand(0,1)*(BU -BL ) + BL
ij ij ij ij
(7)
Trong đó: x
ij
- giá trị của phần tử ij với: i - số cá thể xem xét của bài toán; j - số biến của bài
toán tối ưu; BU
ij
, BL

Trong quá trình lai ghép (khối 4), DE cũng tiến hành lai ghép theo kiểu cặp đôi (dual
crossover) tạo ra một quần thể lai ghép [U] có giá trị các tham số được lựa chọn ngẫu nhiên từ
các quần thể [X] và [V] ban đầu. Kỹ thuật lai ghép sử dụng trong lập trình của DE có thể biểu
diễn như sau:

v ; if rand(0,1) £ C or j= rand(j)
r
ij
u =
x ; otherwise
ij
ij





(9)
Trong đó: C
r
- xác suất lai ghép. C
r
 (0,1) được người sử dụng định nghĩa nhằm điều
khiển một phần các tham số được sao chép từ quần thể đột biến. Thêm vào đó giá trị của phần
tử lai ghép u
ij
với chỉ số chọn ngẫu nhiên j = rand(j) được lấy từ quần thể đột biến [V] sẽ đảm
bảo chắc chắn phần tử lai ghép không trùng với phần tử ban đầu x
ij
.

F(x) - £
ε;
min
N
p

(11)
Trong đó: F(x)
min
- giá trị nhỏ nhất của hàm mục tiêu tại thế hệ xét; F(x)
i
- giá trị hàm mục
tiêu của cá thể thứ i; N
p
(= n_popsize) - tổng số cá thể trong quần thể đang xét;  - giá trị vô cùng
bé cho trước (thường chọn = 10
-4
 10
-6
tùy theo loại bài toán).
CT 2Hình 2. Sơ đồ các thuật toán GA, SA và DE
III. MỘT SỐ BÀI TOÁN THỬ NGHIỆM VÀ SO SÁNH
3.1. Một số bài toán thử nghiệm
a. Bài toán 1: Tìm cực tiểu hàm Generalized Rosenbrock

j
 30; j = 0,1,2, …, D - 1; D > 1
Đồ thị hàm Ackley với 2 biến được biểu diễn như hình 4.
a) b) c)
CT 2Hình 4. Đồ thị hàm Ackley
c. Bài toán 3: Tìm cực đại hàm Zbigniew Michalewicz
Tìm cực đại hàm số sau:
f(x) = 21,5+ x sin 4
πx + x sin 20πx
1 1 2 2
   
   
   

Các điều kiện hạn chế có dạng:
-3.0  x
1
 12.1; 4.1  x
2
 5.8
Đồ thị hàm Zbigniew Michalewicz được biểu diễn như hình 5.

Hình 5. Đồ thị hàm Zbigniew Michalewicz
d. Kết quả tính toán các bài toán thử nghiệm

38,850
Trong đó: nf - số lần tính giá trị hàm; t - thời gian tính toán (% sec); x* - giá trị tối ưu của
các biến; f(x*) - giá trị hàm ở điểm tối ưu.
CT 2

3.2. So sánh khả năng của các phương pháp
Từ các tài liệu tham khảo và kết quả lập trình, tính toán cụ thể cho các bài toán thử nghiệm,
nhận thấy ưu nhược điểm của ba phương pháp trên như sau:
GA SA DE
Ưu
điểm
- Thuộc lớp thuật toán Monte-
Carlo và do xem xét nhiều cá thể
trong một quần thể nên có thể
vượt qua cực trị địa phương,
tiệm cận điểm tối ưu của bài
toán.
- Thuộc lớp thuật toán
Monte - Carlo, có khả
năng tạo ra các đột biến
để tiệm cận điểm tối ưu
của bài toán.
- Có tiêu chuẩn dừng rõ
ràng.
- Có đầy đủ các ưu
điểm của GA và SA.
- Thời gian tính rất

sự không đơn giản đặc biệt với bài toán kỹ thuật. Tuy vậy, các phương pháp nêu trên cũng chỉ
ra cho chúng ta một bức tranh khá tốt về tìm kiếm nghiệm tối ưu trong không gian lớn của bài
toán đa cực trị, không liên tục khá phổ biến trong kỹ thuật. Với cả ba phương pháp đã trình bầy
thì nghiệm đạt được chí ít cũng là phương án tốt nhất (theo một tiêu chuẩn xác định) trong tất cả
các phương án đã xem xét.
- Thông thường để giải các bài toán tối ưu thực tế trong kỹ thuật quá trình tính toán thường
mất rất nhiều thời gian. Ví dụ dùng thuật toán GA để giải bài toán tối ưu kết cấu trong môi
trường Matlab thường mất nhiều tiếng. Do đó, việc rút ngắn được thời gian trong tính toán tối
ưu của thuật toán DE là một ưu điểm vượt trội so với các thuật toán khác trong quá trình tìm
nghiệm, đặc biệt với bài toán mà giá trị hàm không thể biểu diễn được bằng những hàm đại số
tường minh và với số biến lớn.

Tài liệu tham khảo
[1]. Hoàng Kiếm, Thuật giải di truyền, NXB Giáo dục, Hà nội, 2000.
[2]. Nguyễn Đình Thúc, Trí tuệ nhân tạo - Lập trình tiến hóa, NXB Giáo dục, Hà nội, 2001.
[3]. Bùi Minh Trí, Bài tập tối ưu hoá, NXB Khoa học Kỹ thuật, Hà nội, 2002.
[4]. Zbigniew Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer,
Verlag, 1994.
[5]. Kenneth Price, Rainer Storn, Jouni Lampinen, Differiential Evolution A Practical Approach to
Global Optimization, Springer, Verlag, 2005