LỜI MỞ ĐẦU
Ngày nay cùng với sự phát triển không ngừng của khoa học máy tính
thì việc ứng dụng nó vào các ngành khoa học khác cũng đạt được những
hiệu quả hết sức to lớn.
Một ứng dụng cụ thể của máy tính vào cơ học đó là tối ưu hoỏ cỏc
hệ cơ học. Với các modul tối ưu có sẵn trờn mỏy thỡ ta có thể dễ dàng
triển khai chúng vào một modul riêng biệt trong quá trình giải trọn vẹn
một hệ cơ học.
Mục đích chính của đồ án này là xây dựng các modul tối ưu để gắn
vào một chương trình hoàn chỉnh giải một hệ cơ học. Do phạm vi để sử
dụng như vậy nên trong đồ án này tôi chỉ trình bày những phương pháp
tối ưu mà có thể dễ dàng ứng dụng để đạt được mục đích trên, mặc dù
còn nhiều phương pháp nhanh và chính xác hơn nhưng việc áp dụng
chúng vào dạng bài toán như trên thỡ nú trở nên phức tạp hơn.
Những phương pháp tối ưu được trình bày sau đây là những phương
pháp tối ưu trực tiếp không có sử dụng đạo hàm, còn những phương
pháp có sử dụng đạo hàm không được nói đến do việc gắn nó vào các
modul khác mà tính đến đạo hàm thì chương trình rất khó thực hiện do
hàm mục tiêu được xác định trong quá trình tính toán từ các modul khỏc
nờn khú xác định được đạo hàm của chúng và các ràng buộc.
Chương I giới thiệu sơ qua các khái niệm về tối ưu và bài toán cơ
học đặt ra. Chương II, III, IV trình bày cụ thể các phương pháp tối ưu.
Chương V là sử dụng các modul xây dựng từ các phương pháp đã giới
thiệu để giải một vài bài toán cụ thể.
Tôi xin chân thành cảm ơn sự hướng dẫn tận tình của thầy giáo Đinh
Văn Phong, cảm ơn sự giúp đỡ tham khảo của thầy Nguyễn Nhật Lệ và
thầy Phan Mạnh Dần.
1
Chương I.
BÀI TOÁN TỐI ƯU TRONG CƠ HỌC
I. BÀI TOÁN TỐI ƯU TỔNG QUÁT
(x)
≥
0 với i=m+1,…,p
2
Hàm f(x) ở đây được gọi là hàm mục tiêu, x
∈
E
n
là biến trạng thái.
Nếu x
∈
E thì ta nói f(x) là hàm một biến (n=1), còn với n>1 thì f(x) là
hàm nhiều biến. Trong các hàm đó thì phải có Ýt nhất một hàm là phi
tuyến.
II. MỘT SỐ BÀI TOÁN CƠ HỌC
Bõy giê ta sẽ đi xét một số ví dụ dùng để minh hoạ cho việc sử dụng
các modul tối ưu. Với mỗi hệ cơ học sẽ chỉ đặt ra bài toán tối ưu, còn ta
sẽ xem xét cụ thể vào chương V của đồ án này.
1. Bài toán 1: Tối ưu tần số
(Xem [5]).
Hình II-1. Hệ dao động n bậc tự do
Với hệ cho trờn hỡnh II-1, bài toán đặt ra là tỡm cỏc giá trị m
i
, c
i
, b
i
sao cho hàm:
F=
∑
i
, c
i
, b
i
bằng một modul tính toán khác.
2. Bài toán 2: Tối ưu biên độ
Hình II-2
Với mô hình cơ học như trên thì bài toán đặt ra là xác định các khối
lượng m
i
, độ cứng c
i
, giảm chấn b
2
sao cho biên độ dao động của vật 1
và 2 là nhỏ nhất.
Nếu ta đưa vào cỏc kớ hiệu:
x
0
=
1
0
c
F
: di chuyển tĩnh của m
1
dưới tác dụng của lực F
0
.
ω
Ω
: tần số kích động
μ
=
1
2
m
m
;
ξ
=
(0)
1
(0)
2
ω
ω
;
4
D=
(0)
12
ω2m
b
Thì giải hệ trên ta được các hàm khuếch đại nh sau:
V
1
=
0
tương ứng. Có 2
bài toán tối ưu biên độ đặt ra nh sau:
Bài toán 2.1:
Tìm: f(x) = V
1
(D,
ξ
,
η
)
→
min
Thoả món cỏc ràng buộc:
≤
−
η)ξ,(D,V
η)ξ,(D,Vη)ξ,(D,V
1
12
Q
max
D
min
≤
D
≤
D
max
ξ
η)ξ,(D,Vη)ξ,(D,V
1
12
Q
max
D
min
≤
D
≤
D
max
ξ
min
≤
ξ
≤
ξ
max
Để có thể sử dụng được các modul tối ưu trên ta phải tiến hành gián
đoạn hoá tần số kích động
η
. Giới hạn trên của hàm mục tiêu trong
đoạn a
≤
η
≤
b được coi là biến thiết kế giả tạo – kí hiệu là d.
i1
i1i2
Q
max
i=1 m
D
min
≤
D
≤
D
max
ξ
min
≤
ξ
≤
ξ
max
Nh vậy là có 2m+4 ràng buộc bất đẳng thức.
6
Chương II.
TỐI ƯU HOÁ HÀM MỘT BIẾN
I. GIỚI THIỆU
Phần này ta chỉ xét hàm mục tiêu chỉ có một biến:
y=f(x) với x
∈
R
0
. Ta sẽ luôn luôn có kết quả giá trị
tối ưu nằm trong hai khoảng, ở đây đó là [x
0
; x
1
] và (x
1
;+
∞
).
Gọi x
0
là điểm xuất phát để tìm kiếm, s là giá trị độ dài khởi tạo. Đặt:
x
1
=x
0
+s và tính f(x
1
), f(x
0
). Có 3 trường hợp sau:
- Nếu f(x
1
) = f(x
0
) thì max nằm trong khoảng x
0
< x < x
f(x
0
)< f(x
1
) <f(x
2
)<…< f(x
k-1
) và f(x
k-1
)
≥
f(x
k
)
d/2=x
k-1
-x
k-2
=2
k-2
s (2.1.1)
(2.1.1)
Do đó giá trị max của hàm mục tiêu sẽ nằm trong khoảng (x
k-2
;x
k
) và
độ dài khoảng này là:
x
;x
k-2
).
Đến đây đó xỏc định được khoảng tối ưu, việc tìm giá trị tối ưu cho
hàm mục tiêu sẽ chuyển thành tìm giá trị tối ưu cho hàm mục tiêu có
giới hạn.
b. Chọn độ dài khởi tạo s
Bài toán đặt ra đầu tiên trong bất kì việc tìm kiếm giá trị tối ưu là
chọn dé dài khởi tạo s, trong phương pháp số trên máy tính thỡ nú quyết
định số lượng tính toán nhiều hay Ýt. Trong phần trước, tổng khoảng
8
cách dịch chuyển trong quá trình tìm kiếm giá trị max của hàm mục tiêu
đến bước thứ k-1 là tổng của
∑
−
=
1
0
s2
k
i
i
, đến bước k hàm mục tiêu sẽ giảm.
Ta có:
x
*
-x
0
< x
k
k-2
s theo (2.1.2) và với k tính theo (2.2.2).
c. Ước lượng gần đúng giá trị tối ưu
Từ 3 điểm (x
k-2
, x
k-1
, x
k
) đã tính được với 3 giá trị của hàm mục tiêu
tương ứng, hàm f(x) có thể được tính xấp xỉ thành hàm bậc 2 nh sau:
f(x)=
0
β
+
1
β
(x-x
k-2
)+
11
β
(x-x
k-2
) (x-x
k-1
) (2.3.1)
(2.3.1)
Với:
0
Do đó bài toán tối ưu bõy giờ trở thành bài toán tìm cực trị của hàm
bậc hai một biến. Ta chỉ cần giải phương trình f’(x)=0, kết quả cho như
sau:
x
*
=(x
k-2
+x
k-1
-
1
β
/
11
β
)/2
III. TỐI ƯU VỚI HÀM MỤC TIÊU Cể GIỚI HẠN
Trong phần này ta sẽ tìm giá trị tối ưu cho hàm mục tiêu có giới hạn:
a
≤
x
≤
b. Phương pháp được trình bày chủ yếu ở đõy là phương pháp
Fibonacci.
1. Phương pháp Fibonacci
a. Cơ sở tìm kiếm trờn dóy số Fibonacci
Để dễ dàng, ta xét một miền được giới hạn bởi đoạn AB có độ dài L
j
.
Hai điểm dùng để thử có thể được thêm vào là C và D nh hình vẽ dưới
-l
j
’, do đó để thu được những đoạn bằng nhau ta nên đặt l
j
=l
j
’.
Bước tiếp theo là ta thay đoạn AB bằng đoạn CB hoặc AD bằng cách
loại trừ một trong hai đoạn. Giả sử ta thu được đoạn CB và nú cú chứa
điểm D, do đó ta chỉ việc thêm vào điểm E và quan hệ về độ dài là:
CD=EB=l
j+1
Nếu ta đặt:
j
σ
=
j
j
L
l
(3.1.1)
(3.1.1)
thì ở vòng thứ j+1 ta có:
1j
σ
+
=
1
1
L
j
=L
j
-
j
σ
L
j
=L
j
(1-
j
σ
) và l
j
=
j
σ
L
j
Ta có: L
j
(1-
j
σ
)(1-
1j
σ
+
)=
và
j
γ
là hai số nguyên thì biểu thức
(3.1.2) trở thành:
j
j
γ
β
=
11
11
β2γ
β-γ
++
++
−
jj
jj
(3.1.3)
Điều đó được thoả mãn khi:
j
β
=
1
γ
+
j
-
1
j
+
2
β
+
j
(3.1.4a)
1
β
−N
=
2
β
−
N
=1(3.1.4b)
(3.1.4b)
11
Bõy giê ta hãy chú ý tới dãy số nguyên Fibonacci:
F
0
=F
1
=1(3.1.5a)
(3.1.5a)
Và với n>1:
F
n
=F
n-1
)1(
)1(
F
F
−−
+−
jN
jN
với j=1,2,…,N-1
Đến đây ta đó cú tất cả những thành phần cần thiết cho phương pháp
tìm kiếm Fibonacci.
b. Phương pháp tìm kiếm Fibonacci
Trong phương pháp này, đoạn đầu tiên ta phải tính 2 giá trị (bước 1)
để chia đoạn đó thành 3 đoạn, sau đó chọn 2 đoạn để thực hiện việc tìm
kiếm tiếp theo. Ở bước tiếp theo ta chỉ việc tớnh thờm 1 giá tri do giá trị
thứ 2 trùng với 1 trong 2 giá trị ở bước trước. Do đó từ bước thứ 2 trở đi
ta chỉ phải tớnh thờm 1 giá trị để thử.
Có thể tóm tắt các bước của phương pháp nh sau:
- Bước 1: Thay hai giá trị đầu tiên.
Với đoạn a
1
≤
x
≤
b
1
có độ dài L
1
=b
1
(3.1.6)
Ta có:
x
1
= a
1
+l
1
x
2
= b
1
-l
1
=a
1
+L
1
-
N
N
F
F
2−
L
1
=a
1
+
1
-l
1
=b
1
-x
1
(hoặc x
2
-a
1
)
Thay l
1
ở (3.1.6) vào ta có:
L
2
=L
1
-
N
N
F
F
2−
L
1
=L
1
(1-
kN
kN
L
k
(3.1.7)
(3.1.7)
- Bước 3: Hai điểm để thử trong đoạn thứ hai.
Trên đoạn L
2
ta sẽ thêm vào 2 điểm x
3
’và x
3
’’
. Ta có:
l
2
=
1
3
F
F
−
−
N
N
L
2
Đến đây ta phải xét tới 2 trường hợp:
+ Trường hợp thứ nhất: đoạn (a
L
2
=(a
1
+ L
1
N
N
F
F
2−
)+
1
3
F
F
−
−
N
N
( L
1
N
N
F
F
1
−
)
=a
2
=x
1
+L
2
-
1
3
F
F
−
−
N
N
L
2
=(a
1
+ L
1
N
N
F
F
2−
)+
1
31
F
F-F
+ Trường hợp thứ hai: đoạn (x
2
,b
1
) bị loại trừ còn lại đoạn (a
1
,x
2
),
giá trị tối ưu sẽ nằm trong đoạn (a
1
,x
2
): còng tương tù nh trường hợp
trên, chỉ phải tính một giá trị x
3
.
Tổng quát cho bước lặp thứ m ta có:
L
m
=
N
mN
F
F
)1( −−
L
1
(3.1.8)
(3.1.8)
L
k
=
j
j
F
F
2
−
L
k
Khi j là giá trị lớn thì tỉ số F
j-2
/F
j
sẽ dần đến 0.3820.
Khi đó: l
k
=0.3820L
k
.
Ta sẽ áp dụng kết quả này để xây dựng một thuật toán cụ thể để áp
dụng cho các phần sau.
IV. TỔNG KẾT
Cuối cùng chúng ta có thể viết cụ thể giải thuật của phương pháp
Fibonacci theo các bước nh sau:
Tìm min f(x) với x
∈
R.
14
0
) và s>e thì quay lại a.
Bước 2: Xác định khoảng tối ưu
a. Gán: x
t
=x
0
+s và s=2s.
b. Nếu f(x
t
) < f(x
0
) thì quay lại a.
Bước 3: Thuật toán Fibonacci
a. Gán:
a= x
0
+(x
t
- x
0
)p
b= x
t
-(x
t
- x
0
)p
Nếu f(a) < f(b) thỡ gỏn: x
).
Thuật toán Fibonacci có tốc độ hội tụ rất nhanh so với việc chia
khoảng tối ưu thành nhiều điểm bằng nhau đồng thời số lượng tính toán
Ýt do ở mỗi vòng lặp chỉ phải thực hiện một phép tính.
Thủ tục tính toán được viết bằng ngôn ngữ C++ ứng dụng trong
thuật toán Powell trong tệp “Powell.cpp” trong phần phụ lục.
15
Chương III.
Tối ưu hoá hàm Nhiều biến không có ràng
buộc
I. GIỚI THIỆU
Hàm mục tiêu nhiều biến là hàm mà biến trạng thái x
∈
R
n
với n>1.
Phương pháp Fibonacci cho hàm một biến không thể áp dụng được cho
hàm nhiều biến, ta sẽ phải tìm ra các phương pháp khác phù hợp để tìm
lời giải tối ưu. biến không thể áp dụng được cho hàm nhiều biến, ta sẽ
phải tìm ra các phương pháp khác phù hợp để tìm lời giải tối ưu.
16
Ta có thể phân loại thành hai phương pháp chính cho lời giải bài
toán tối ưu: đó là phương pháp có sử dụng đạo hàm và phương pháp
không sử dụng đạo hàm.
Phương pháp có sử dụng đạo hàm có ưu điểm là hội tụ nhanh và
chính xác nhưng yêu cầu phải tính đạo hàm của hàm mục tiêu. Còn
phương pháp không sử dụng đạo hàm thì không phải tính đạo hàm mà
chỉ cần tính giỏ trị của hàm mục tiêu và so sánh các giá trị với nhau tùy
theo từng phương pháp tìm kiếm.
Tuy nhiên trong ứng dụng các phương pháp vào từng líp bài toán cụ
Trong chương này ta sẽ xét đến các hàm mục tiêu không có các ràng
buộc. Việc tối ưu các hàm mục tiêu có ràng buộc ta sẽ nói đến ở chương
sau, nhưng về cơ bản vẫn phải sử dụng đến các phương pháp sẽ trình
bày ở chương này.
II. PHƯƠNG PHÁP TỐI ƯU CỦA HOOK VÀ JEEVES
Theo khái niệm thì đây là phương pháp đơn giản nhất, nó được thực
hiện nh sau: tại một thời điểm chỉ thay đổi một biến trong khi giữ
nguyên giá trị của các biến còn lại cho tới khi tìm được giá trị tối ưu.
Lấy một ví dụ để minh hoạ: với hàm mục tiêu f(x
1
,x
2
) ban đầu giữ
nguyên x
2
và thay đổi x
1
cho tới khi tìm được giá trị tối ưu ứng với x
1
.
Sau đó giữ nguyên giá trị x
1
tìm được ở trên rồi cho x
2
thay đổi để tìm
giá trị tối ưu ứng với nó. Tuy nhiên quá trình này sẽ không chính xác
nếu có sự ảnh hưởng lẫn nhau giữa x
1
và x
2
)
Nếu s < e
Kết thúc
Giảm s
Lấy x làm điểm cơ sở mới
x
0
=x
Tối u theo mẫu hình
Thực hiện tối u lần II, thu đợc x.
Kiểm tra: f(x) < f(x
0
)
Sai Đúng
Sai
Đúng
Đúng Sai
Hình II-1. Sơ đồ thuật toán tối ưu của Hook Jeeves
Thuật toán tối ưu trực tiếp được thực hiện theo các bước nh sau:
- Cho trước các giá trị khởi tạo:
x
0
(0)
=( x
1
(0)
,x
2
(0)
,…, x
được thay đổi bởi s
1
(0)
: x
1
(1)
= x
1
(0)
+s
1
(0)
.
Nếu f(x) giảm thì giữ nguyên thành phần x
1
(0)
.
Nếu f(x) không giảm thì thay x
1
(1)
= x
1
(0)
-s
1
(0)
. Nếu f(x) giảm thì ta
chấp nhận thành phần x
1
(1)
hiện) ta định nghĩa một vector trong không gian R
n
thể hiện hướng
tối ưu thành công. Gọi m là số lần tối ưu thành công thì thực hiện tối
ưu theo mẫu hình theo công thức sau:
x
(k+1)
=m.x
(k)
-x
(0)
(i=1 n)
x
(0)
là điểm cơ sở để thực hiện bước tối ưu thứ nhất.
Việc tối ưu theo mẫu hỡnh cú thành công hay không ta chưa thể
kết luận ngay được mà còn phải thực hiện tối ưu lần II xong mới kết
luận được.
- Tối ưu lần II:
Sau khi tối ưu theo mẫu hình kết thúc thì ta thực hiện tối ưu lần
II, các bước cũng tương tự như lần I.
Nếu f(x) không giảm sau khi tối ưu lần II thì ta kết luận việc tối
ưu theo mẫu hình là thất bại, quay lại tối ưu từ lần I để tìm hướng tối
ưu thành công mới.
- Kiểm tra điều kiện dõng:
Nếu việc tối ưu ngay từ lần I đã thất bại, hướng tối ưu mới không
được tìm thấy thì ta giảm dần các thành phần của s (là một vector)
cho tới khi tìm được hướng tối ưu mới hoặc tất cả các thành phần
của nó bằng không (trong máy tính số thì nhỏ hơn sai sè e) thì thuật
toán kết thúc.
) thì một đơn hình đều sẽ là
một tam giác đều (3 đỉnh), với hàm 3 biến thì là một khối tứ diện đều (4
đỉnh) (hai trường hợp này được minh họa bằng hình III-1 ở dưới),…,
22
tương tự với hàm mục tiêu n biến thì đơn hình là khối đa diện (n+1)
đỉnh.
Hình III-1. Đơn hình đều với 2 và 3 biến độc lập
Trong quá trình tối ưu hàm mục tiêu f(x), vector x dùng để thử có thể
được chọn tại các điểm trong không gian E
n
xác định các đỉnh của đơn
hình như đã giới thiệu ở trên do Spendley, Hext và Himsworth. Từ
những phân tích hình học như trên ta có thể chỉ ra toạ độ của các điểm
của đơn hình đều được cho bởi ma trận D, trong đó các cột biểu diễn
các thành phần của các đỉnh được đánh số từ 1 đến (n+1) và các hàng
biểu diễn các toạ độ được đánh số từ 1 đến n:
D =
1)(nn
d dd0
d dd0
d dd0
d dd0
122
222
212
221
+×
(
1n
+
-1)
t : khoảng cách giữa hai đỉnh.
Hàm mục tiêu có thể được tính tại mỗi đỉnh của đơn hình, một phép
chiếu được thực hiện từ đỉnh mà hàm mục tiêu có giá trị lớn nhất qua
trọng tâm của đơn hình, trong hình III-1 thì đó là đỉnh A và B là đỉnh
tạo thành sau phép chiếu. Thông thường thì ta thực hiện phép chiếu là
phép ánh xạ hệ số bằng 1, tức là phép lấy đối xứng. Đơn hình mới được
tạo nên sau khi bỏ đi đỉnh A và thêm một đỉnh mới là B. Tiếp tục với
23
Träng t©m
Träng t©m
A
B
A
B
1
2
3
2
3
4
thủ tục này ta luôn luôn loại được đỉnh mà hàm mục tiêu có giá trị lớn
nhất, đồng thời thêm vào quy tắc giảm kích thước của đơn hình sau mỗi
lần thực hiện để tránh dẫn tới giá trị vô hạn. Chúng ta thừa nhận rằng
phương pháp tối ưu bằng đạo hàm thì ở một vòng lặp nào đó độ dài
dùng để tối ưu là cố định nhưng hướng tối ưu đã chọn lại thay đổi.
Một vài khó khăn trong thủ tục đơn hình đều là hội tụ chậm (do phải
,…, x
in
(k)
]
T
là đỉnh thứ i của khối đa diện tại
bước tính thứ k. Thuật toán Nelder và Mead là thực hiện trên khối đa
diện (n+1) đỉnh bất kỡ nờn ta phải cho trước toạ độ của (n+1) đỉnh, tức
là phải nhập trên máy tính n
×
(n+1) giá trị khởi tạo ban đầu. Để thuận
24
tiện và đơn giản ta xây dựng luôn khối đa diện ban đầu là một đơn hình
đều như đã trình bày ở trên, khi đó ta chỉ phải cho trước một đỉnh, tức là
chỉ phải nhập vào máy n giá trị, điều đó đơn giản hơn rất nhiều và bảo
đảm khối đa diện ban đầu luôn thoả mãn để tính toán không phải kiểm
tra.
Thuật toán được trình bày cụ thể như sau:
- Bước 1: Cho trước đỉnh khởi tạo: x
0
(0)
rồi xây dựng khối đa diện
ban đầu là một đơn hình đều với kích thước t cho trước như phần
trình bày ma trận D ở trên:
x
1
(0)
= x
0
(0)
= x
1j
(0)
+d
2
nếu: j
≠
i+1
với: i=2,3,…,n+1 và j=1,2,…,n.
Sau đó tính giá trị của hàm mục tiêu tại các đỉnh vừa tính được:
f(x
i
(0)
)
- Bước 2: Bắt đầu từ k=0.
Tìm:
f(x
h
(k)
)=max{ f(x
1
(k)
), f(x
2
(k)
),…, f(x
n+1
(k)
)}
tương ứng với x
(k)
)} (với g
≠
h)
tương ứng với x
g
(k)
.
Tính giá trị các thành phần của trọng tâm khi bá x
h
(k)
đi:
25
Copyright: Tài liệu đại học ©