Luận văn thạc sĩ
MỞ ĐẦU
1. Lý do chọn đề tài.
Trong các dây chuyền sản xuất công nghiệp hiện nay đa số các hệ thống có nhiều tín
hiệu đầu vào và nhiều tín hiệu đầu ra, do vậy các bài toán điều khiển gắn với thực tế là là
các bài toán tối ưu đa mục tiêu. Tuy nhiên chưa có nhiều nghiên cứu về các bài toán này.
Hiện nay các đề tài khoa học chủ yếu mới chỉ giải quyết và ứng dụng các bài toán tối ưu
một mục tiêu. Ví dụ ta xét công nghệ gia nhiệt phôi kim loại trong lò nung là một trong
những quá trình có tham số biến đổi chậm, trong đó các hàm mục tiêu đặt ra với lò gia nhiệt
như sau: nung nhanh nhất, nung chính xác nhất, nung ít bị ôxi hóa nhất; hoặc trong các bài
toán điều khiển mức của dây truyền sản xuất nước ngọt thì các hàm mục tiêu có thể là: ổn
định mức dung dịch H chính xác nhất, thời gian ổn định nhanh nhất
Đã có nhiều phương pháp tiếp cận khác nhau nhằm giải quyết các loại bài toán này,
song gần đây việc ứng dụng các giải thuật tính toán tiến hóa hứa hẹn nhiều triển vọng. Hiện
nay nghiên cứu về lĩnh vực này trong nước ta chưa nhiều, nhất là chưa đưa ra được những
mô hình ứng dụng thực tế cụ thể trong khi nhu cầu ứng dụng lại rất cao.
Xuất phát từ tình hình thực tế và góp phần vào công cuộc CNH - HĐH đất nước nói
chung và phát triển ngành Tự động hóa nói riêng, trong khuôn khổ của khóa học Cao học,
chuyên ngành Tự động hóa tại trường Đại học Kỹ thuật Công nghiệp Thái nguyên, được sự
tạo điều kiện giúp đỡ của nhà trường, khoa sau Đại học và PGS. TS Lại Khắc Lãi, tác giả
đã lựa chọn đề tài tập trung chủ yếu vào việc xây dựng bài toán tối ưu nhiều mục tiêu cho
dây chuyền công nghệ thực tế và ứng dụng giải thuật di truyền (Genetic Algorithm – GA)
để giải quyết bài toán tối ưu đó, nhằm tiết kiệm thời gian và đảm bảo chất lượng sản phẩm
đầu ra là tốt nhất với tên đề tài là: “Nghiên cứu ứng dụng giải thuật di truyền cho bài toán
điều khiển tối ưu đa mục tiêu”.
2. Mục đích của đề tài
- Xây dựng bài toán tối ưu đa mục tiêu gắn liền với các hệ thống thực hiện nay.
- Ứng dụng giải thuật gen di truyền (GA) để tìm lời giải tối ưu cho bài toán tối ưu đa mục tiêu.
- Tiếp tục nghiên cứu và hoàn thiện hơn nữa việc lựa chọn và tính toán phương án nâng cao
chất lượng điều khiển mức cho dây chuyền sản xuất nước ngọt.
3. Đối tượng và phạm vi nghiên cứu
và cơ chế song song ẩn, giải pháp này sẽ cho ra kết quả tối ưu, nhanh nhất và có tính linh hoạt cao.
5. Cấu trúc của luận văn
Luận văn gồm 3 chương, 94 trang, 15 tài liệu tham khảo, 21 hình vẽ và bảng biểu.
Trường Đại học Kỹ thuật Công nghiệp TN Đặng Ngọc Trung
2
Luận văn thạc sĩ
Chương 1
TỔNG QUAN VỀ GIẢI THUẬT DI TRUYỀN
(Genetic Algorithm - GA)
1.1. CÁC GIẢI THUẬT TÍNH TOÁN TIẾN HÓA-GIẢI THUẬT DI TRUYỀN
1.1.1. Khái quát.
Giải thuật di truyền ( GA – Genetic Algorithm) là giải thuật tìm kiếm, chọn lựa các
giải pháp tối ưu để giải quyết các bài toán thực tế khác nhau, dựa trên cơ chế chọn lọc của
tự nhiên: Từ tập lời giải ban đầu, thông qua nhiều bước tiến hóa, hình thành tập lời giải mới
phù hợp hơn, và cuối cùng dẫn đến lời giải tối ưu toàn cục.
Trong tự nhiên, mỗi cá thể muốn tồn tại và phát triển phải thích nghi với môi trường,
cá thể nào thích nghi hơn thì tồn tại, cá thể nào kém thích nghi thì bị tiêu diệt. Từ ý tưởng
đó, các nhà khoa học đã nghiên cứu và xây dựng nên giải thuật di truyền dựa trên cơ sở
chọn lọc tự nhiên và quy luật tiến hóa. Giải thuật di truyền sử dụng các thuật ngữ được lấy
từ di truyền học như: lai ghép, đột biến, NST, cá thể,… Ở đây mỗi cá thể được đặc trưng bởi
một tập nhiễm sắc thể, nhưng để đơn giản khi trình bày, ta xét trường hợp tế bào mỗi cá thể
chỉ một NST. Các NST được chia nhỏ thành các gen được sắp xếp theo một dãy tuyến tính.
Mỗi cá thể (hay NST) biểu diễn một lời giải có thể của bài toán. Một xử lý tiến hóa duyệt
trên tập các NST tương đương với việc tìm kiếm lời giải trong không gian lời giải của bài
toán. Quá trình tìm kiếm phải đạt được hai mục tiêu:
• Khai thác lời giải tốt nhất.
• Xem xét trên toàn bộ không gian tìm kiếm.
GA sử dụng các toán tử: chọn lọc, lai ghép, đột biến trên các NST để tạo ra chuỗi mới.
Những toán tử này thực chất là việc sao chép chuỗi, hoán vị các chuỗi con và sinh số ngẫu
nhiên.
sẽ được ánh xạ lên giá trị thực thuộc miền
[ ]
; .
x x
l u
Nhờ đó, ta có thể kiểm soát miền giá trị của các biến và tính chính xác của chúng. Tỷ lệ co
giãn của ánh xạ được tính như sau:
Giá trị x tương ứng với chuỗi NST nhị phân là:
( )
* .
x
x l decimal NST g= +
Trong đó,
( )
decimal NST
là giá trị thập phân của chuỗi NST nhị phân và
2
x x
L
u l
g
−
=
.
Bây giờ, mỗi NST (là một lời giải) được biễu diễn bằng chuỗi nhị phân có chiều dài
1
.
k
định tùy thuộc vào điều kiện về tốc độ về tài nguyên máy tính.
1.1.2.2. Toán tử chọn lọc.
a) Sử dụng bánh xe Roulette.
Có nhiều cách để thực hiện toán tử chọn lọc, nói chung đều theo tư tưởng cá thể có độ
thích nghi cao hơn thì khả năng được chọn nhiều hơn. Nhưng có lẽ đơn giản và hiệu quả
nhất là sử dụng bánh xe Roulette (roulette wheet), mỗi cá thể trong quần thể chiếm một khe
Trường Đại học Kỹ thuật Công nghiệp TN Đặng Ngọc Trung
4
Luận văn thạc sĩ
có độ rộng tỷ lệ thuận với giá trị phù hợp. Độ rộng của khe được tính bằng tỷ lệ phần trăm
giá trị phù hợp của một cá thể trên tổng giá trị phù hợp của toàn quần thể.
Gọi
i
f
là độ phù hợp của cá thể thứ i trong quần thể gồm N cá thể. Khi đó, cá thể i sẽ
được chọn với xác suất
1
.
i
N
i
i
i
f
p
f
=
=
∑
Trên vòng tròn Roulette, mỗi chuỗi trong quần thể
theo thứ tự tăng đần của hàm mục tiêu (bài toán cực tiểu).
• Tính độ phù hợp của chuỗi
• Sử dụng thủ tục quay Rulet chọn chuỗi để sao chép sang quần thể tạm thời.
c) Chọn lọc cạnh tranh
• Chọn t cá thể từ quần thể hiện tại một cách ngẫu nhiên và chọn cá thể tốt nhất trong t
cá thể đó để sao chép sao chép sang quần thể tạm thời.
• Lặp lại bước trên N lần chúng ta sẽ có quần thể tạm thời.
Giá trị t được gọi là kích cỡ của chọn lọc cạnh tranh. Khi
2t =
chúng ta chọn lọc cạnh
tranh nhị phân.
Trường Đại học Kỹ thuật Công nghiệp TN Đặng Ngọc Trung
5
Luận văn thạc sĩ
1.1.2.3. Toán tử lai ghép.
• Lai ghép một điểm
Lai ghép một điểm được thực hiện rất đơn giản. Với hai cá thể cha mẹ đã chọn
1 2
, ;P P
toán
tử này cần sinh một vị trí ngẫu nhiên k
( )
1 k L< <
, sau đó hai cá thể con được tạo thành
bằng cách tráo đổi các gen của cặp cha mẹ tính từ điểm cắt.
• Lai ghép nhiều điểm
Lai ghép nhiều điểm được thực hiện tương tự như lai ghép một điểm. Với hai cá thể
cha mẹ đã chọn P
1
, P
nếu bit mặt nạ là 0. Cá thể con C
2
được tạo ngược lại.
1.1.2.4. Toán tử đột biến.
Toán tử đột biến làm thay đổi các thông tin của quần thể ở mức bit (gen). Đột biến
làm thay đổi giá trị của một bit bất kỳ theo xác suất p
m
. Mỗi bit đều có cơ hội đột biến như
nhau.
1.1.2.5. Hàm phù hợp.
Biến đổi hàm mục tiêu thành hàm phù hợp:
Do giá trị phù hợp trong giải thuật di truyền là không âm, nên để áp dụng GA cho bài
toán tối ưu ta cần phải chuyển giá trị hàm mục tiêu thành hàm phù hợp.
Nếu bài toán tối ưu là cực tiểu hàm mục tiêu
( )
g x
thì ta chuyển sang hàm phù hợp
như sau:
( )
( ) ( )
( )
0
max max
max
C g x g x C
f x
g x C
− <
g x C
+ + >
=
+ <
Trong đó,
min
C
là tham số đầu vào,
min
C
có thể là giá trị tuyệt đối bé nhất của các hàm
mục tiêu trong tập hiện tại hoặc trong k vòng lặp cuối.
1.1.3. Giải thuật di truyền mã hóa số thực.
Trong phần này chỉ nghiên cứu giải thuật di truyền mã hóa số thực (RCGA – Real –
Coded Genetic Algorithm ) để giải các bài toán tối ưu giá trị thực trong không gian
n
¡
và
không có các ràng buộc đặc biệt.
Một cách tổng quát, bài toán tối ưu số thực có thể xem là một cặp
( )
,S f
, trong đó
n
S ⊆ ¡
và
xem một quần thể kích cỡ m như một ma trận thực cấp
( )
m n×
, đây là cách mã hóa tự nhiên
và thuận tiện trong việc thực hiện các toán tử tiến hóa. Sau đây ta xem xét cụ thể hơn các
toán tử này trong giải thuật di truyền mã hóa số thực.
1.1.3.1. Toán tử chọn lọc.
Ta thấy toán tử chọn lọc đã trình bày trong GA kinh điển không cần một đòi hỏi đặc
biệt nào trong việc mã hóa số thực, vì vậy trong GA mã hóa số thực, toán tử chọn lọc vẫn
được áp dụng như đối với GA kinh điển. Cụ thể gồm các dạng: chọn lọc tỷ lệ, chọn lọc xếp
hạng hay chọn lọc cạnh tranh.
1.1.3.2. Toán tử lai ghép.
GA mã hóa số thực cũng được áp dụng các toán tử lai ghép như GA kinh điển bao
gồm lai ghép một điểm, lai ghép nhiều điểm, lai ghép mặt nạ. Ngoài ra do cách mã hóa quần
thể, người ta còn nghiên cứu và đề xuất nhiều dạng khác nhau của toán tử lai ghép trong
RCGA. Dưới đây là một số dạng toán tử lai ghép thường được sử dụng với giả thiết cặp cá
thể cha mẹ chọn để tiến hành lai ghép là:
Trường Đại học Kỹ thuật Công nghiệp TN Đặng Ngọc Trung
7
Luận văn thạc sĩ
( )
1
, ,
m
X x x=
và
( )
1
, ,
m
Toán tử lai ghép đa điểm được mô tả như sau:
Chọn ngẫu nhiên k điểm j
1
, …, j
k
(1≤ j
1
< j
2
< ….< j
k
< m), lai ghép đa điểm tạo ra cặp
con (X
’
, Y’) bằng cách đánh số các đoạn [ j
t
, j
t+1
] từ 0 trở đi sau đó:
x
’
i
lấy bằng x
i
tại các đoạn có số hiệu chẵn và bằng y
i
tại các đoạn có số hiệu lẻ.
y
’
i
∈ ∈
= =
∉ ∉
.
d) Lai số học (Arithmetic Crosover).
Phép lai này chọn một số thực a (0< a <1); các con X
’
, Y
’
được tính bởi:
' '
* (1 )* , * (1 ) * .
i i i i i i
x a x a y y a y a yx= + − = + −
e) Lai ghép Heuristic.
Giả sử với cặp bố mẹ (X, Y) đã chọn, trong đó cá thể X có độ thích nghi (giá trị hàm
mục tiêu) tốt hơn các thể Y thì toán tử này tạo một con duy nhất X
’
từ
cặp X, Y bởi:
'
*( )
i i i i
x a x y x= − +
với 0< a < 1.
, y
i
) – min (x
i
, y
i
) với mỗi i.
Khi đó thành phần thứ i của cá thể con tạo ra là một số ngẫu nhiên chọn trong khoảng
[ ]
( , ) * ( , ) * .
i i i i
min x y I max x y I− α, + α
Toán tử BLX - α đã được thử nghiệm và chứng minh tính hiệu quả của nó với giá trị tốt
nhất là
α = 0.5
.
g) Toán tử lai ghép SBX .
Toán tử SBX là toán tử lai ghép áp dụng cho giải thuật di truyền mã hóa số thực
(RCGA), tại hai cá thể con từ một cặp cá thể cha mẹ chọn lọc . SBX được Deb và Agrawal
giới thiệu năm 1995 và đã được chọn làm toán tử tạo sinh cơ bản trong nhiều nghiên cứu
khác.
1.1.3.3. Toán tử đột biến.
Toán tử đột biến trong RCGA được giới thiệu đa dạng hơn trong GA kinh điển. Sau
đây sẽ giới thiệu một số dạng điển hình.
Đột biến đều: với mỗi gen i được chọn ngẫu nhiên để đột biến từ cá thể
( )
1 2
, , , ,
n
b x x x
i
được thay
thế bởi một trong hai giá trị tính theo các công thức sau:
, ,,
( , ) ( , )
i i i i i i i i
x x t b x x x t x a= + ∆ − = − ∆ −
Việc chọn giá trị nào được tiến hành tùy theo giá trị ngẫu nhiên khởi tạo với xác suất 1/2.
Biến ngẫu nhiên
( , )t x
∆
được xác định một bước đột biến trong khoảng [0, x] theo công
thức
ax
(1 / )
( , ) (1 ) .
m
t t
t x x
τ
λ
−
∆ = −
Trong công thức này,
λ
là số ngẫu nhiên phân bố đều trong khoảng đơn vị. Tham số
τ
xác
định ảnh hưởng của lần tạo sinh thứ t phân bố đột biến trong miền [0, x].
ưu theo một tiêu chuẩn chất lượng nào đó (đạt được giá trị cực trị). Trạng thái tối ưu có đạt
Trường Đại học Kỹ thuật Công nghiệp TN Đặng Ngọc Trung
10
Luận văn thạc sĩ
được hay không tùy thuộc vào yêu cầu chất lượng đặt ra, vào sự hiểu biết về đối tượng và
các tác động lên đối tượng, vào điều kiện làm việc của hệ điều khiển …
Hình 2.1 Sơ đồ hệ thống điều khiển .
Hệ thống điều khiển như hình trên bao gồm các phần tử chủ yếu: đối tượng điều khiển
(ĐTĐK), cơ cấu điều khiển (CCĐK) và vòng hồi tiếp (K).Với các ký hiệu :
r : tín hiệu đầu vào, mục tiêu điều khiển, đáp ứng mong muốn của hệ thống.
u : tín hiệu điều khiển, luật điều khiển.
x : tín hiệu đầu ra, đáp ứng ra của hệ thống.
ε
= r – x : sai lệch của hệ thống.
f : tín hiệu nhiễu
Chỉ tiêu chất lượng J của một hệ thống có thể được đánh giá theo sai lệch của đại
lượng được điều khiển x so với trị đáp ứng mong muốn r, lượng quá điều khiển (trị số cực
đại x
max
so với trị số xác lập
( )
x ∞
tính theo phần trăm), thời gian quá độ … hay theo một chỉ
tiêu hỗn hợp trong điều kiện làm việc nhất định như hạn chế về công suất tốc độ, gia tốc …
Do đó việc chọn một luật điều khiển và cơ cấu điều khiển để đạt được chế độ làm việc tối
ưu J đạt cực trị còn tùy thuộc vào lượng thông tin ban đầu mà ta có được.
Ở đây chúng ta có thể thấy được sự khác biệt về kết quả nhận được chất lượng tối ưu
khi lượng thông tin ban đầu thay đổi ( Hình 2.2 ) .
2.1.3.2. Phương pháp quy hoạch động Bellman.
a. Giới thiệu
Phương pháp quy hoạch động được dựa trên nguyên lý tối ưu sơ khai của Bellman:
Một chiến lược tối ưu có tính chất không phụ thuộc vào những quyết định trước đó
(ví dụ như những luật điều khiển) song các quyết định còn lại phải cấu thành nên chiến
lược tối ưu có liên quan với kết quả của những quyết định truớc đó.
Nguyên lý tối ưu của Bellman: “Bất kỳ một đoạn cuối cùng nào của quỹ đạo tối ưu
cũng là một quỹ đạo tối ưu ”.
Nguyên lý này giới hạn xem xét trên một số các chỉ tiêu tối ưu. Nó chỉ ra rằng
phương án tối ưu phải được xác định từ trạng thái cuối đi ngược về trước đó.
Điều kiện áp dụng: nguyên lý tối ưu Bellman là một phương pháp số, chỉ áp dụng được khi
hệ thống có phân cấp điều khiển và ta biết trước sơ đồ mắt lưới được xây dựng bằng thực
nghiệm.
b. Hệ rời rạc
Phương pháp quy hoạch động cũng có thể dễ dàng áp dụng cho hệ phi tuyến. Ngoài ra,
nếu có càng nhiều điều kiện ràng buộc đối với tín hiệu điều khiển và biến trạng thái thì ta có
được lời giải càng đơn giản.
2.1.3.3. Nguyên lý cực tiểu Pontryagin _ Hamilton
a. Nguyên lý cực tiểu của Pontryagin
Cho hệ thống:
( , , ).x f x u t=
&
(2.82)
Kết hợp hàm chỉ tiêu chất lượng:
( )
( )
0
0
( ) , ( , , ) .
T
Giả sử hàm điều khiển u(t) là ràng buộc trong một vùng giới hạn cho phép, có nghĩa
là giá trị yêu cầu có độ lớn nhỏ hơn giá trị đã cho. Điều kiện dừng thay bằng điều kiện tổng
quát:
( , , , ) ( , , , )H x u t H x u u t
λ λ
∗ ∗ ∗ ∗ ∗ ∗
≤ +∂
thỏa mãn tất cả giá trị
δ
u.
Dấu * thể hiện chỉ số chất lượng tối ưu. Mà bất kỳ sự biến thiên nào trong bộ điều khiển tối
ưu xảy ra tại thời điểm t (trong khi trạng thái và biến trạng thái nếu được duy trì) sẽ tăng đến
giá trị của hàm Hamilton. Điều kiện này được viết như sau:
( , , , ) ( , , , )H x u t H x u t
λ λ
∗ ∗ ∗ ∗ ∗
≤
thỏa mãn tất cả giá trị u. (2.87)
Yêu cầu tối ưu biểu thức (2.87) được gọi nguyên lý cực tiểu Pontryagin:“Hàm
Hamilton phải được cực tiểu hóa ở tất cả các giá trị u cho giá trị tối ưu của trạng thái và
biến trạng thái”.
Chúng ta sẽ thấy nguyên lý cực tiểu hữu dụng như thế nào. Đặc biệt chú ý không thể nói
rằng biểu thức
( , , ) ( , , , )H x u H x u t
λ λ
∗ ∗ ∗
≤
chắc chắn phải đúng.
b. Điều khiển Bang-Bang
Chúng ta hãy thảo luận bài toán tối thiểu thời gian tuyến tính với ngõ vào ràng buộc.
(2.84) của hàm
ψ
.
Hàm Hamilton cho vấn đề này là:
1 ( ).
T T
H L f Ax Bu
λ λ
= + = + +
(2.91)
Điều kiện dừng được tìm thấy là: 0 =
=
∂
∂
u
H
B
T
λ
. (2.92)
Nó không chứa u bởi vì hàm Hamilton tuyến tính đối với u. Rõ ràng, để H cực tiểu
chúng ta nên chọn u(t) sao cho
λ
T
(t)Bu(t) càng nhỏ càng tốt (có nghĩa là giá trị càng xa về
phía bên trái trên trục tọa độ thực;
λ
T
Bu = -
∞
Đặt u(t) là một đại lượng vô hướng và đặt b tượng trưng cho véctơ ngõ vào. Trong
trường hợp này dễ dàng chọn u
*
(t) để tối thiểu
λ
T
(t) Bu(t). (Chú ý: giá trị nhỏ nhất nghĩa là
λ
T
(t)Bu(t) nhận một giá trị càng gần -
∞
càng tốt ).
Nếu
λ
T
(t)B là giá trị dương, chúng ta nên chọn u(t) = -1 làm cho
λ
T
(t)Bu(t) có giá trị âm
nhất. Mặt khác, nếu
λ
T
(t)B là giá trị âm, chúng ta nên chọn u(t) ở giá trị cực đại là giá trị 1
để giá trị
λ
T
(t)Bu(t) càng âm càng tốt. Nếu giá trị
λ
T
(t)Bu(t) bằng zero tại thời điểm t, khi đó
tBtu
T
λ
−=
(2.95)
Ta có u* được biểu diễn dưới dạng biến trạng thái, với hệ tuyến tính dạng toàn phương. Giá
trị B
T
λ
(t) được gọi là hàm chuyển đổi. Một hàm chuyển đổi mẫu và bộ điều khiển tối ưu
được diễn tả ở hình 2.5. Khi hàm chuyển đổi này đổi dấu, bộ điều khiển chuyển từ cực trị
này đến cực trị khác. Bộ điều khiển trong hình được chuyển đổi bốn lần. Điều khiển thời
gian tối thiểu tuyến tính tối ưu luôn bão hòa khi nó chuyển đổi tại vị trí giữa các giá trị cực
trị, cho nên được gọi là điều khiển Bang-bang .
Nếu bộ điều khiển là một véctơ có m phần tử, theo nguyên lý cực tiểu ta chọn các thành
phần u
i
(t) bằng 1, nếu các thành phần B
i
T
λ
(t) là giá trị âm; và bằng -1 nếu B
i
T
λ
(t) là giá trị
dương, với B
i
là cột thứ i của B. Phương pháp điều khiển này tạo thành một giá trị:
)()()()(
= sgn(w) cho mỗi i (2.98)
Trong đó v
i
, w
i
là những thành phần của v và w.
Thành phần B
i
T
λ
(t) của hàm chuyển đổi B
T
λ
(t) có thể bằng zero trên một khoảng thời
gian hữu hạn. Nếu điều đó xảy ra, thành phần u
i
(t) của bộ điều khiển tối ưu không định
nghĩa được bởi biểu thức (2.93). Đó gọi là điều kiện kỳ dị. Nếu điều đó không xảy ra, thì bộ
điều khiển thời gian tối ưu được gọi là bình thường.
Trường Đại học Kỹ thuật Công nghiệp TN Đặng Ngọc Trung
14
Luận văn thạc sĩ
Nếu hệ thống là bất biến theo thời gian, ta sẽ có được quả đơn giản và bộ điều khiển
thời gian tối ưu là duy nhất.
Hình 2.5 Hàm chuyển đổi mẫu và bộ điều khiển tối ưu .
Hệ thống bất biến theo thời gian trong biểu thức (2.88) có thể đạt được nếu chỉ có một
ma trận vuông cấp n:
1n
n
U B AB A B
hàm điều khiển thỏa
[ ]
1)( ≤tu
. Khi đó:
1. Nếu trạng thái cuối x(T) bằng zero, khi đó sẽ tồn tại bộ điều khiển thời gian tối thiểu
nếu hệ thống không có cực với phần thực dương (ví dụ không có cực trên mặt phẳng phía
bên phải).
2. Cho bất kỳ giá trị x(T) cố định, nếu tồn tại đáp án cho bài toán tối ưu thời gian thì nó
là duy nhất.
3. Cuối cùng, nếu hệ thống có n cực thực và nếu tồn tại bộ điều khiển tối ưu thời gian thì
mỗi thành phần u
i
(t) của bộ điều khiển tối ưu thời gian thay đổi n-1 lần.
2.2. TỐI ƯU ĐA MỤC TIÊU
2.2.1. Quy hoạch đa mục tiêu.
Trong nhiều ứng dụng thực tế gắn liền với thiết kế, kế hoạch hóa các nghành kinh tế
kỹ thuật, điều khiển sản xuất, ta thường gặp các bài toán liên quan đến việc phân tích, lựa
chọn định hướng vào nhiều mục tiêu khác nhau. Chẳng hạn một dây truyền sản xuất của
một nhà máy bất kỳ thường đối mặt với các mục tiêu như: Hạ giá thành sản phẩm, năng
lượng tiêu hao ít nhất, năng suất lao động cao nhất… Các dạng bài toán trên gọi là quy
hoạch đa mục tiêu. Mô hình toán học của bài toán này như sau:
Có k hàm mục tiêu, ký hiệu
1
, ,
K
Y Y
với
:
i
Y D → ¡
tuyến tính một mục tiêu bởi Charnes, Cooper và Ferguson, song nó chỉ đạt tới sự phổ biến
sau các công trình của Ignizio, Lee và những người khác. Remeo đã đưa ra một cách nhìn
toàn diện và danh mục các ứng dụng kỹ thuật sử dụng quy hoạch đa mục tiêu. Quan điểm
chính của quy hoạch đa mục tiêu là tìm lời giải đạt tới mục tiêu xác định trước thỏa mãn
một hay một số hàm điều kiện. Có thể minh họa điều này trong ví dụ sau:
Quy hoạch đa mục tiêu hiếm khi sử dụng cho các bài toán một điều kiện mà thường
chỉ quan tâm đến các bài toán nhiều điều kiện. Các dạng cơ bản bao gồm:
i) Nhỏ hơn hay bằng: f(x) ≤ T.
ii) Lớn hơn hay bằng: f(x) ≥ T.
iii) Bằng nhau: f(x) = T.
iv) Trong khoảng: f(x) ∈ [t
l
, t
u
].
Nói chung, người ta thường sử dụng hai biến không âm đo độ lệch mục tiêu cần đạt
với giá trị của hàm. Chẳng hạn với dạng i) độ lệch dương p là
( )
f x p T
− ≤
, khi đó mục tiêu
là hàm cực tiểu p. Tương tự ii) ta sử dụng biến n sao cho
( )
f x n T
+ ≥
. Trường hợp bằng
nhau thì dùng cả hai biến, nghĩa là f(x) – p + n =T.
+) Tập lời giải tối ưu Pareto
Các bài toán tối ưu đa mục tiêu hầu hết liên quan đến tập lời giải tối ưu của Pareto, nó
xuất phát từ việc bài toán đa mục tiêu có nhiều hàm mục tiêu với các ràng buộc khác nhau,
,…,Y
k
gọi là các hàm mục tiêu.
Khi xử lý tập nghiệm Pareto, vai trò của người sử dụng (NSD) hay người nhận lời giải
của bài toán đóng vai trò quan trọng. NSD sẽ căn cứ vào lợi ích của mình để chọn phương
án cho hợp lý, cách đó gọi là kết hợp QHĐMT với NSD. Có thể nói lợi ích ở đây là một
hàm
( )
:U Y D → ¡
thường được giả thiết thỏa mãn một vài điều kiện nào đó dùng để đo sở
thích của NSD.
Trường Đại học Kỹ thuật Công nghiệp TN Đặng Ngọc Trung
17
Rủi ro
Giá
Hình 2.6 Minh họa tập Pareto
A
C
B
Luận văn thạc sĩ
2.2.2.2. Phương pháp nhượng bộ dần.
Bước 1: Giải k bài toán một mục tiêu riêng rẽ, sau đó lập bảng thưởng phạt.
Bước 2: Căn cứ vào bảng thưởng phạt, với giá trị
0
1
Y
NSD buộc Y
1
nhượng bộ một lượng
∆Y
( )
3
maxY X
với X∈D; Y
1
(X) ≥
0
1
Y
- ∆Y
1
; Y
2
(X) ≥Y
2
*
- ∆Y
2
;
Giả sử Y
3
*
là trị tối ưu của bài toán này, chuyển tiếp sang bước tiếp….
Bước k: NSD căn cứ vào
0
1k
Y
−
và
(X
i
) và đưa vào biến phụ W:
( )
i i i
i
M Y X
W
M
−
≤
với mọi i = 1,…, k.
Vế trái trong công thức trên gọi là độ lệch tương đối chung.
Bước 2: Giải bài toán minW với X∈D từ đó tìm được nghiệm tối ưu X
0
và W
0
Trong trường hợp này, lợi ích tỷ lệ với độ lệch tương đối, phương án X
1
là tốt hơn X
2
nếu độ
lệch tương đối chung của X
1
nhỏ hơn X
2
.
2.2.2.4. Phương pháp tìm nghiệm có khoảng cách nhỏ nhất đến nghiệm lý tưởng.
Phương pháp này giả định có một nghiệm lý tưởng, X
α
− ≤ ∈
∏
trong đó
( )
i i
M maxY X=
2.2.3. Giải thuật di truyền đa mục tiêu.
Sau đây giới thiệu giải thuật di truyền tuyển chọn không trội NSGA do Srinivas và
Deb đề xuất [3]. Quan điểm cơ bản của NSGA là phương pháp chọn lọc xếp hạng và
phương pháp hàm chia sẻ nhằm duy trì tính đa dạng của quần thể. NSGA sử dụng mã hóa số
thực và làm việc trực tiếp trên các hàm số thực.
Trong NSGA các toán tử di truyền (Selection, Crossover và Mutation) đã được mô tả
trong phần trước. Ở đây chỉ mô tả cụ thể thủ tục xếp hạng không trội là tư tưởng chính của
NSGA.
Thủ tục xếp hạng không trội (Non – Dominated Ranking)
Xét quần thể gồm N cá thể, mỗi cá thể có M (M > 1) giá trị hàm mục tiêu. Thủ tục sau
được sử dụng để tìm tập các lời giải không trội được.
Bước 1: Đặt i = 1;
Bước 2: Với mỗi j = 1,…, N và j ≠ i, so sánh x
(i)
và x
(j)
theo hai điều kiện của tính trội i) và
ii) nêu trên;
Bước 3: Nếu với mỗi j nào đó, x
(i)
được trội bởi x
(j)
thì đánh dấu x
) được xem là giá trị
mục tiêu “lý tưởng” (có thể không có cá thể nào đạt được giá trị này). Tiêu chuẩn đánh giá
các cá thể là độ lệch của nó so với giá trị mục tiêu “lý tưởng” vừa xác định. Trong quá trình
tạo sinh, các cá thể cạnh tranh với nhau tùy theo độ lệch giữa các hàm mục tiêu tương ứng
của nó với các giá trị MT
i
. Sau một số lần lặp xác định trước, các giá trị mục tiêu mới lại
được cập nhật theo cách trên.
2.2.4.2. Thuật toán tối ưu từng mục tiêu.
Thuật toán này cũng nhằm xác định các giá trị đối với mỗi hàm mục tiêu của bài toán
ngay trong quá trình chạy chương trình sau một số lần lặp định trước. Song ở đây sau mỗi
thời điểm định trước chỉ cập nhật lại một giá trị mục tiêu cho một hàm. Độ thích nghi của
mỗi cá thể vì vậy cũng được tính lại theo từng giai đoạn thực hiện theo công thức:
( )
( ) ( ) (*)
x k k j j
j k
h f x MT f x MT
≠
= − + −
∑
Ở đây MT
j
là giá trị đã xác định đối với hàm mục tiêu thứ j; riêng đối với mục tiêu
thứ k là tìm min (đối với mục tiêu k mà cần tìm max thì thay lại số hạng thứ k là MT
k
– f
k
(x)).
Với công thức tính độ thích nghi trên, chẳng hạn với mục tiêu tìm là min hàm mục
3
/h).
X
1
, X
2
– Nồng độ, thành phần của hai dòng nguyên liệu.
Q – lưu lượng của dòng sản phẩm ra (m
3
/h).
X – Nồng độ, thành phần của sản phẩm ra.
H – mức chất lỏng trong bình (m).
Qua phân tích các mục đích điều khiển và tìm hiểu lưu đồ công nghệ, ta có thể thấy
ngay hai biến cần điều khiển là thành phần X và giá trị mức H. Thành phần X liên quan đến
chất lượng sản phẩm, trong khi H liên quan tới sự vận hành ổn định và sự an toàn của hệ
thống. Ta cũng dễ dàng nhận thấy lưu lượng Q
1
, Q
2
, Q, X
1
, X
2
là các biến vào, trong đó lưu
lượng ra Q còn phụ thuộc vào yêu cầu quá trình tiếp theo, vì vậy còn gọi là nhiễu. Thành
phần của dòng vào X
1
, X
2
cũng là các đại lượng nhiễu quá trình. Trong luận văn này chỉ
H
Đo lường
Sensor
U
H
R
L
Đặt
Bộ điều khiển
Nhiễu
Q x
1
x
2
Biến
điều khiển
Q
1
Q
2
Biến cần
điều khiển
H
x
QUÁ TRÌNH
KHUẤY TRỘN
Hình 3.1 Các biến của quá trình khuấy trộn
Luận văn thạc sĩ
`
2
.
Như vậy, thiết bị này có hàm truyền là một khâu khuếch đại với hệ số khuếch đại:
=
−
−
=
∆
∆
=
mA
mmKG
I
P
K
2
max
max
/
5,0
420
002,001,0
3.1.3. Hàm truyền đạt của van.
K
sW
v
v
v
+
=
1
)(
Trong đó: K
V
: hệ số khuếch đại của van
T
V
: thời gian trễ của van, thường lấy
T=10 ms = 0,01s.
Khi tín hiệu vào thay đổi từ 0,02
÷
0,1
KG/mm
2
thì độ mở của van thay đổi từ 0
÷
80%, khi đó hệ số khuếch đại được xác định như
sau:
80
100
0.1 0,02
V
− −
Kết hợp các hàm truyền ở trên ta có hàm truyền đạt với tín hiệu vào là áp suất khí nén
và tín hiệu ra là lưu lượng nước cấp thông qua cơ cấu van:
1 1 2 2
50 125
W ( ) ( ) , W ( ) ( ) .
1 0,01 1 0,01
V T V T
s W s s W s
s s
− −
= = = =
+ +
3.1.4. Hàm truyền đạt của thiết bị đo mức.
Thiết bị đo mức là bộ chuyển đổi EJA 210A của hãng YOKOGAWA có dải đo 0 ÷
1000mm, tương ứng cho tín hiệu đầu ra dạng dòng điện liên tục từ 4 ÷ 20 mA. Thiết bị này
có hàm truyền đạt là môt khâu quán tính bậc nhất.
W ( ) .
1
H
K
s
Ts
=
+
Trong đó:
K – là hệ số khuếch đại của thiết bị đo, được xác định như sau:
Dung dịch
Lưu lương
Áp suất
khí nén
Van khí nén
Hình 3.5 Van khí nén
Luận văn thạc sĩ
3.2.THIẾT LẬP BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU ĐIỀU KHIỂN MỨC H TRONG
BÌNH TRỘN
3.2.1. Đặt bài toán.
Giả định đây là một khâu pha trộn dung dịch trong dây truyền sản xuất nước ngọt. Các
biến cần điều khiển là nồng độ, thành phần các chất, nhiệt độ, và mức dung dịch trong bình
trộn để đảm bảo cho chất lượng sản phẩm đầu ra là cao nhất và đảm bảo an toàn trong
suốt quá trình sản xuất. Có rất nhiều bài toán được đặt ra trong dây truyền công nghệ sản
xuất này đó có thể là bài toán điều khiển nhiệt độ dung dịch trong bình ổn định đảm bảo
được sự lên men và đồng nhất các thành phần hóa học trong dung dịch hoặc là bài toán điều
khiển tối ưu lượng nguyên liệu cấp ban đầu sao cho tỷ lệ các chất trong dung dịch là phù
hợp nhất và tiết kiệm nguyên liệu nhất Trong luận văn này chỉ đề cập tới việc điều khiển
mức dung dịch H sao cho ổn định nhất nhằm đảm bảo sự ổn định và an toàn của dây truyền
sản xuất trong suốt quá trình vận hành.
Bài toán đặt ra là có hai dòng dung dịch độc lập, một là hỗn hợp dòng nhiên liệu
gồm: đường, chất phụ gia, hương liệu và dòng thứ hai là nước tinh khiết cùng được điều
chỉnh lưu lượng Q
1
, Q
2
qua van khí nén đổ vào bể trộn khuấy liên tục. Đầu ra của bình trộn
là lưu lượng dung dịch Q
3
thay đổi liên tục và phụ thuộc vào sự vận hành nhanh hay chậm
D
của bộ điều khiển PID). Sau
đó lấy nghiệm của bài toán tối ưu hai mục tiêu trên lắp vào bộ điều khiển từ đó mô phỏng
kết quả điều khiển mức dung dich H trên Matlab Simulink và quan sát và đánh giá kết quả.
Trường Đại học Kỹ thuật Công nghiệp TN Đặng Ngọc Trung
25
Copyright: Tài liệu đại học ©