Hội nghị Khoa học công nghệ lần thứ XXII

Trường Đại học Giao thông vận tải

THIẾT KẾ GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN TỐI ƯU PHI
TUYẾN ĐA RÀNG BUỘC
Phạm Thanh Hà
Trường Đại học Giao thông vận tải
Số 3 Cầu Giấy, Hà Nội
Tác giả liên hệ:

Tóm tắt
Bài báo tập trung nghiên cứu cơ sở toán học của tối ưu phi tuyến từ đó thiết kế các
tốn tử di truyền phục vụ việc xây dựng giải thuật di truyền giải bài toán tối ưu phi
tuyến.
Các kết quả của bài báo là cơ sở để thiết kế các giải thuật di truyền ứng dụng cho
các bài toán tối ưu số đa ràng buộc như bài toán vận tải, bài toán lập kế hoạch, tối ưu
hóa lộ trình, pha trộn hợp chất.
Từ khóa: Giải thuật di truyền, tối ưu phi tuyến, đa ràng buộc.
1. Đặt vấn đề
Cho đến nay đã có nhiều thuật tốn tìm lời giải tối ưu cho nhiều lĩnh vực bài tốn,
ví dụ như trong bài tốn tìm kiếm trên danh sách, cây, đồ thị các nhà khoa học đã đưa
ra thuật tốn tìm kiếm quay lui, vét cạn. Các thuật tốn này tuy tìm được nghiệm tối ưu
nhưng chỉ áp dụng được cho các bài tốn có khơng gian tìm kiếm nhỏ [3].
Để khắc phục các hạn chế như trên các nhà khoa học cũng đã đưa ra các thuật
tốn tìm kiếm heurictics, đây là thuật tốn có sử dụng các tri thức về lĩnh vực bài toán
để nhằm giảm thời gian tìm kiếm. Tuy nhiên các thuật tốn này lại vấp phải một vấn
đề là các tri thức thường là kinh nghiệm của con người, do đó nó có thể chưa chính
xác, đầy đủ và điều này có thể dẫn tới sự chệch hướng trong quá trình tìm kiếm [3].
Giải thuật tiến hóa cung cấp những kỹ thuật tìm kiếm tối ưu giúp ta giải quyết
được những vấn đề đã đặt ra ở trên, nó cho phép ta tìm kiếm lời giải tối ưu trên các

khơng gian lớn, nguyên tắc cơ bản của giải thuật tiến hóa là mơ phỏng q trình tiến
hóa của tự nhiên. Cho đến nay lĩnh vực nghiên cứu về giải thuật tiến hóa đã thu được
nhiều thành tựu, giải thuật tiến hóa được ứng dụng trong nhiều lĩnh vực phức tạp, các
vấn đề khó có thể giải quyết được bằng phương pháp thơng thường [1,2].
Với khả năng tiềm tàng của giải thuật di truyền, bài báo tập trung nghiên cứu cơ
sở toán học và xây dựng giải thuật di truyền để giải bài toán tối ưu phi tuyến.
2. Giải thuật di truyền
-290-


Hội nghị Khoa học công nghệ lần thứ XXII

Trường Đại học Giao thông vận tải

Giải thuật di truyền thuộc lớp các giải thuật tìm kiếm tiến hố. Khác với phần lớn
các giải thuật khác tìm kiếm theo điểm, giải thuật di truyền thực hiện tìm kiếm ngẫu
nhiên trên một tập được gọi là quần thể các lời giải có thể [4,6,7].
Thơng qua việc áp dụng các tốn tử di truyền, giải thuật di truyền tráo đổi thông tin
giữa các cực trị và do đó làm giảm thiểu khả năng kết thúc giải thuật tại một cực trị địa
phương.
Giải thuật di truyền duy trì một quần thể các lời giải có thể của bài tốn tối ưu hố.
Thơng thường, các lời giải này được mã hoá dưới dạng một chuỗi các gien. Giá trị của
các gien có trong chuỗi được lấy từ một bảng các ký tự được định nghĩa trước. Mỗi
chuỗi gien được liên kết với một giá trị được gọi là độ thích nghi. Độ thích nghi được
dùng trong quá trình chọn lọc [1,2].
Cơ chế chọn lọc đảm bảo các cá thể có độ thích nghi tốt hơn có xác suất được lựa
chọn cao hơn. Quá trình chọn lọc sao chép các bản sao của các cá thể có độ thích nghi
tốt vào một quần thể tạm thời được gọi là quần thể bố mẹ. Các cá thể trong quần thể bố
mẹ được ghép đôi một cách ngẫu nhiên và tiến hành lai ghép tạo ra các cá thể con. Điều
đáng lưu ý là giải thuật không yêu cầu tốn tử lai ghép ln xảy ra đối với hai cá thể bố

mẹ được chọn. Sự lai ghép chỉ xảy ra khi số ngẫu nhiên tương ứng với cặp cá thể bố mẹ
được sinh ra trong khoảng [0, 1) không ln hơn một tham số pc (gọi là xác suất lai ghép).
Nếu số ngẫu nhiên này lớn hơn pc, toán tử lai ghép khơng xảy ra. Khi đó hai cá thể con
là bản sao trực tiếp của hai cá thể bố mẹ.

Hình 1. Sơ đồ giải thuật di truyền
Sau khi tiến hành quá trình lai ghép, giải thuật di truyền mơ phỏng một q trình
khác trong tự nhiên là q trình đột biến. Tốn tử đột biến duyệt từng gien của từng cá
-291-


Hội nghị Khoa học công nghệ lần thứ XXII

Trường Đại học Giao thông vận tải

thể con được sinh ra sau khi tiến hành toán tử lai ghép và tiến hành biến đổi giá trị trong
miền xác định với một xác suất pm được gọi là xác suất đột biến.
Trong giải thuật di truyền, quần thể con được sinh ra từ quần thể hiện tại thơng qua
3 tốn tử là chọn lọc, lai ghép và đột biến thay thế hoàn toàn quần thể hiện tại và trở
thành quần thể hiện tại của thế hệ tiếp theo.
Giải thuật di truyền phụ thuộc vào các tham số như: số cá thể trong quần thể; xác
suất lai ghép; xác suất đột biến; số thế hệ cần tiến hố. Cá thể có giá trị hàm mục tiêu tốt
nhất của mọi thế hệ là lời giải cuối cùng của giải thuật. Quần thể đầu tiên được khởi tạo
một cách ngẫu nhiên.
3.Tối ưu phi tuyến và xử lý ràng buộc
Xét bài toán tối ưu phi tuyến tổng quát:
Tìm x để hàm f(x), x=(x1,…,xq) Rq đạt giá trị tối ưu thỏa:
p≥0 phương trình gj(x)=0, j=0,..,p và
m-p bất phương trình hj(x), j=p+1,..,m
Cho đến nay vẫn chưa có phương pháp nào giúp xác định cực trị cho bài toán

này, chỉ khi hàm mục tiêu và các ràng buộc gj và hj thỏa một số tính chất nào đó thì đơi
khi mới tìm được tối ưu tồn cục.
Như chúng ta đã biết giải thuật di truyền có thể giải quyết bài tồn tối ưu số [3],
tuy nhiên các bài tốn tối ưu này chỉ bị ràng buộc theo miền D Rq với
D=
nghĩa là mỗi biến xk bị giới hạn trong khoảng
cho trước.
Tuy nhiên những bài toán tối ưu tổng quát thường gặp trong thực tế hầu hết lại là
bài toán tối ưu có ràng buộc [5,8].
Trong bài tốn tối ưu có ràng buộc, dạng hình học của tập lời giải trong Rq là đặc
trưng quan trọng nhất của bài toán. Hiện chỉ có tập lồi là có lý thuyết phát triển nhất.
Trong phần này ta quan tâm đến bài toán tối ưu hàm f(x), x=(x1,…,xq)D, D 
R và D là tập lồi.
q

Miền D được xác định từ các khoảng giá trị lk ≤xk≤rk với k=1…q và từ tập ràng
buộc C. Do tính chất lồi của D mà với mỗi điểm x=(x1,…,xq)  D trong khơng gian
tìm kiếm tồn tại 1 đoạn <left(k), right(k)> của biến xk, trong đó các biến xi (i=1,..,k1,k+1,…,q) khác vẫn cố định, nói cách khác điểm điểm x’=(x1,… ,xk-1,y,xk+1,..,xq)  D
với y  <left(k), right(k)>
Ví dụ nếu DR2 được xác định như sau
-3≤ x1 ≤3
0≤ x2 ≤8
x12 ≤ x2 ≤ x1+4
-292-


Hội nghị Khoa học công nghệ lần thứ XXII

Trường Đại học Giao thơng vận tải


Thì đối với điểm (2,5)  D cho tước ta có
left(1) = 1, right(1) =
left(2) = 4, right(2) = 6
Điều này có nghĩa là thành phần thứ nhất của véc tơ (2,5) có thể thay đổi từ 1 đến
(trong khi x2 = 5 không đổi) và thành phần thứ 2 của véc tơ này có thể thay đổi từ 4
đến 6 (trong khi x1 = 2 vẫn giữ ngun)
Nếu tập ràng buộc C khơng rỗng thì khơng gian tìm kiếm D =
lồi, hơn nữa left(k)=lk, right(k)=rk và như thế kết quả ln thỏa ràng buộc.

là

Tính chất trên là cơ sở để xây dựng các toán tử đột biến, nếu biến xk bị đột biến
thì khoảng đột biến phải là <left(k), right(k)> và như thế kết quả ln thỏa ràng buộc.
Một tính chất khác của khơng gian tìm kiếm lồi là bảo đảm với hai điểm x1, x2
bất kỳ trong không gian lời giải D, tổ hợp tuyến tính ax1+(1-a)x2 với a  [0,1] cũng là
điểm trong D. Tính chất này sẽ được sử dụng khi ta xây dựng phép lai số học.
Ta xét một lớp bài toán tối ưu được xác định trên một miền lồi, lớp bài tốn này
được hình thức hóa như sau:
Tối ưu hàm f(x1,…,xq) với tập ràng buộc tuyến tính
1. Ràng buộc về miền l ≤ x ≤ u với x=(x1,…,xq), l=(l1,…,lq), u=(u1,…,uq)
2. Ràng buộc đẳng thức Ax=b, x=(x1,…,xq), b=(b1,…,bp), A=(aij), 1 ≤ i≤ p và 1 ≤
j ≤ q với p là số phương trình
3. Ràng buộc bất đẳng thức Cx ≤ d, x=(x1,…,xq), d=(d1,…,dm), C=(cij), 1 ≤ i≤ q, 1
≤ j ≤ m với m là số bất đẳng thức
Cách hình thức hóa như vậy đủ để xử lý một lớp lớn các bài toán tối ưu với ràng
buộc tuyến tính của một hàm mục tiêu bất kỳ.
Trong một số kỹ thuật tối ưu hóa như quy hoạch tuyến tính, các ràng buộc về
đẳng thức rất dễ cho việc giải bài tốn tối ưu vì nếu lời giải tối ưu tồn tại nó sẽ thuộc
bề mặt của tập lồi và như vậy các bất đẳng thức sẽ được chuyển thành các đằng thức
bằng cách thêm vào các biến tạm, khi đó phương pháp lời giải tiến hành bằng cách di

chuyển từ đỉnh này sang đỉnh khác trên bề mặt [1,2].
Ngược lại đối với phương pháp phát sinh các lời giải ngẫu nhiên như GA, thì các
ràng buộc đẳng thức như vậy lại rất khó xử lý. Tuy nhiên ta có thể dễ ràng loại bỏ các
ràng buộc đẳng thức này nhờ vào việc thế và đặt lại biến.
Ví dụ: Giả sử ta muốn tối ưu hóa hàm 6 biến f(x1,x2,x3,x4,x5,x6) với
2x1+x2+x3=6
x3+x5=10; x1+x4=3; x2+x5≤120
-40 ≤ x1 ≤ 120; 50 ≤ x2 ≤ 75
-293-


Hội nghị Khoa học công nghệ lần thứ XXII

Trường Đại học Giao thông vận tải

0 ≤ x3 ≤ 10; 5 ≤ x4 ≤ 15
0≤ x5 ≤ 20; -5≤ x6 ≤ 5
Có 3 phương trình và 6 biến như vậy sẽ có 3 biến tự do và ta sẽ dung 3 phương
trình độc lập và biểu diễn các biến qua 3 biến cịn lại.
x1=3-x4
x2=-10+8x4+x5-3x6
x3=10-x5+3x6
Như vậy bài tốn gốc trở thành bài tốn tối ưu hóa hàm 3 biến x4, x5, x6
g(x4, x5, x6)=f(3-x4, -10+8x4+x5-3x6, 10-x5+3x6) với ràng buộc
-10+8x4+x5-3x6≤ 120 vì x2+x5≤120
-40≤3-x4≤20 vì -40 ≤ x1 ≤ 120
0≤x3=10-x5+3x6≤ 10 vì 0 ≤ x3 ≤ 10
5 ≤ x4 ≤ 15
0≤ x5 ≤ 20
-5≤ x6 ≤ 5

Như vậy nhờ thế và đặt lại biến, ta đã loại được các đẳng thức, đương nhiên
không gian tìm kiếm là khơng gian lồi. Với mỗi điểm có được (x4, x5, x6) sẽ có một
khoảng <left(k), right(k)> tương ứng, trong đó hai biến cịn lại được giữ ngun. Ví dụ
đối với khơng gian xác định như trên với 1 điểm cho trước (10, 2, 8) ta có:
left(1)=7.25, right(1)=10.375
left(2)=6, right(2)=11
left(3)=1, right(3)=2.666
4. Thiết kế các toán tử di truyền cho bài toán tối ưu đa ràng buộc
Như đã đề cập ở mục 3, để giải bài toán tối ưu phi tuyến đa ràng buộc thì các
tốn tử di truyền phải đảm bảo lời giải được sinh ra sau lai ghép, đột biến phải đảm
bảo ràng buộc của bài toán
4.1. Toán tử đột biến
Toán tử đột biến cần một cá thể x và tạo ra một con duy nhất x’. Phép toán này
chọn một thành phần ngẫu nhiên k  (1…q) của véc tơ x=(x1,…,xq) và sinh ra ,
x’=(x1,…,xk’,…,xq), trong đó xk’ là giá trị ngẫu nhiên trong khoảng <left(k), right(k)>
Toán tử này đóng vai trị quan trong trong những giai đoạn đầu của q trình tiến
hóa khi các lời giải được phép di chuyển tự do trong khơng gian tìm kiếm. Đặc biệt
toán tử cần thiết trong trường hợp quần thể ban đầu gồm nhiều bản sao của cùng một
điểm.
-294-


Hội nghị Khoa học công nghệ lần thứ XXII

Trường Đại học Giao thơng vận tải

Tình trạng như thế thường xun xảy ra trong những bài tốn tối ưu có ràng buộc
mà người sử dụng đặc tả điểm khởi đầu của tiến trình. Hơn nữa điểm khởi đầu duy
nhất này có một thuận lợi to lớn, nó cho phép phát triển một tiến trình lặp mà lần lặp
kế tiếp bắt đầu tại một điểm tốt nhất của lần lặp trước

Có 2 phép đột biến giải quyết được vấn đề ràng buộc như đề cập trên đó là đột
biến biên và đột biến khơng đồng dạng sau đây.
Đột biến biên
Tốn tử này cần một cá thể x và tạo ra một con duy nhất x’. Toán tử này là biến
thể của toán tử đột biến đồng dạng với xk’ hoặc là left(k) hoặc là right(k) với cùng xác
suất.
Toán tử được xây dựng cho các bài toán tối ưu mà lời giải tối ưu nằm trên hoặc
gần biên của khơng gian tìm kiếm khả thi. Do đó nếu tập ràng buộc C rỗng và biên thật
lớn thì các tốn tử này gây phiền tối.
Đột biến khơng đồng dạng
Đột biến khơng đồng dạng là một trong những tốn tử có nhiệm vụ về tìm độ
chính xác của hệ thống.
Tốn tử đột biến cần một cá thể x và tạo ra một con duy nhất x’. Phép toán này
chọn một thành phần ngẫu nhiên k  (1…q) của véc tơ x=(x1,…,xq) và sinh ra ,
x’=(x1,…,xk’,…,xq), trong đó xk’ được xác định như sau:

 x + (t , right(k ) − xk ) neu chu so ngau nhienla 0
xk' =  k
 xk − (t , xk − left(k )) neu chu so ngau nhienla1
Hàm (t, y) trả về giá trị trong khoảng [0, y] sao cho xác suất của (t, y) gần bằng
0 sẽ tăng khi t tăng. Xác suất này buộc tốn tử tìm kiếm không gian thoạt đầu là đồng
dạng (khi t nhỏ) và rất cục bộ ở những giai đoạn sau. Ta sử dụng hàm sau:
t
(1− ) b

 (t , y ) = y  (1 − r T ) , với r là số ngẫu nhiên trong khoảng [0..1], T là số thế
hệ tối đa và b là tham số hệ thống xác định mức độ khơng đồng dạng.

4.2. Tốn tử lai ghép cho bài toán tối ưu đa ràng buộc
Cũng như toán tử đột biến, toán tử lai ghép phải đảm bảo các nghiệm được sinh

ra thỏa mẵng ràng buộc của bàn toán, bài báo đưa ra 2 toán tử lai ghép thỏa mãn điều
kiện trên, đó là lai ghép số học và lai ghép đơn giản.
Lai số học
Phép lai số học đơn được xác định như sau:
Nếu stv =<v1, …, vm> và stw =<w1, …, wm> được lai ghép thì kết quả là:
st+1v =<v1, …, v’k, …, vm> và st+1w =<w1, …, w’k, …, wm>,
-295-


Hội nghị Khoa học công nghệ lần thứ XXII

Trường Đại học Giao thơng vận tải

ở đó 1  k  m, v’k = avk + (1 - a)vk và w’k = awk + (1 - a)wk, a là giá trị
động được xác định theo véc tơ sv và sw. Chính xác hơn a được chọn trong phạm vi:
[max(  ,  ), min( ,  )]

a
[0,0]
if vk = wk
 max( ,  ), min( ,  )


Trong đó:

 = (lk–wk)/(vk–wk),  = (uk–vk)/(wk–vk)
 = (lk–vk)/(wk–vk),  = (uk–wk)/(vk–wk)
Lai đơn giản
Lai ghép số học tồn cục là tổ hợp tuyến tính của hai véc tơ được xác định như
sau:

Nếu stv =<v1, …, vm> và stw =<w1, …, wm> được lai ghép thì kết quả là:
st+1v = astw+(1- a)stv và st+1w = astv+(1- a)stw,
với a là một tham số tĩnh nằm trong đoạn [0, 1].
Kết luận
Bài báo đã đi sâu nghiên cứu cơ chế hoạt động của giải thuật di truyền, tìm hiểu
các cơ chế mã hóa lời giải và các tốn tứ di truyền cũng như nghiên cứu bài toán tối ưu
số đa ràng buộc, cơ sở toán học của việc xây dựng các toán tử di truyền xử lý đa ràng
buộc của bài toán tối ưu số.
Các kết quả của bài báo là cơ sở để thiết kế giải thuật di truyền giải các bài toán
tối ưu số đa ràng buộc như bài toán lập kế hoạch, bài toán vận tải, bài tốn tối ưu hóa
lộ trình, pha trộn hợp chất.
Tài liệu tham khảo
[1] Các mơ hình xác suất và ứng dụng, Nguyễn Duy Tiến, Đại học Quốc gia Hà Nội,
2002
[2] Giải thuật di truyền – Cách giải tự nhiên các bài tốn trên máy tính, Hồng Kiếm,
Nhà xuất bản khoa học kỹ thuật, 2000
[3] Trí tuệ nhân tạo - Lập trình tiến hố, Nguyễn Đình Thúc, Nhà xuất bản giáo dục,
2001
[4] An Introduction to Genetic Algorithms. Mitchell Melanie. A Bradford Book The
MIT Press. Cambridge, Massachusetts London, England. Fifth printing, 1999.
[5] Multi-Criteria Genetic Algorithms for Solving Pig Food Problems,
A,
International Journal on Computer Science and Engineering (IJCSE). ISSN : 09753397 Vol. 3 No. 1 Jan 2011

-296-


Hội nghị Khoa học công nghệ lần thứ XXII

Trường Đại học Giao thông vận tải


[6] Practical Genetic Algorithms, Randy L. Haupt, Sue Ellen Haupt, Second Edition,
Copyright © 2004 John Wiley & Sons, Inc.
[7] Genetic Algorithms in Applications, Rustem Popa, Publisher: IN-TECH (March,
2012)
[8] A directional crossover (DX) operator for real parameter optimization using
genetic algorithm, Amit Kumar Das & Dilip Kumar Pratihar, Applied
Intelligence volume 49, pages1841–1865 (2019)

-297-