Đồ án Tối ưu hoá hệ thống nhiệt - Lạnh

TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 1/20 MỤC LỤC TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 2/20 1. Đặt vấn đề Bài toán tối ưu hoá ngày càng trở nên cần thiết trong mọi hoạt động của con người và được áp dụng sâu rộng vào các nghành kinh tế, kỹ thuật, công nghệ và các lĩnh vực xã hội… Các bài toán tuyến tính và phi tuyến đơn giản đã có rất nhiều cách giải quyết đem lại kết quả khả quan và nhanh chóng. Song đến các bài toán phi tuyến phức tạp, các hàm tối ưu hoá có dạng khe, khe sâu, các phương pháp này trở nên khó khăn để giải quyết và cho kết quả không tin cậy. Việc tìm ra phương pháp giải cho các bài toán phi tuyến phức tạp đã và đang được các nhà khao học hoàn thiện. Nhất là với công nghệ máy tính hiện đại phát triển như ngày nay, là một công cụ rất hữu ích giúp đỡ cho công việc tìm lời giải tối ưu đó. Tiểu luận sau đây trình bày phương pháp tìm lời giải tối ưu hoá bằng phương pháp tối ưu hoá “vượt khe” của tác giả PGS.TSKH.VS Nguyễn Văn Mạnh. 2. Khái niệm về bài toán tối ưu hoá và ý nghĩa thực tiễn Trong những năm gần đây lĩnh vực áp dụng các phương pháp của quy hoạch phi tuyến phát triển rất nhanh. Nếu trước đây, quy hoạch điều khiển các đối tượng kinh tê thì hiện nay xuất hiện ngày càng nhiều các bài toán cự trị phi tuyến trong các nghiên cứu kinh tế toán, như lập kế hoạch cho các ngành, các hệ thống điều khiển các xí nghiệp… Trong quá trình lập dự án thiết kế, vận hành và điều khiển hệ thống, người ta thường mong muốn biết được phương án tốt nhất có thể đạt trong những điều kiện nhất định. Đó là lời giải cực tiểu (cực đại) của bài toán tối ưu hóa, cho phép tiết kiệm tiền vốn, chi phí sản xuất, tiết kiệm thời gian và nâng cao sản phẩm,… Bài toán tối ưu hóa là bài toán tìm điểm cực tiểu (cực đại) của hàm f(x) trong một miền D nào đó đã cho. Bài toán được phát biểu: nEx xf ∈ → min)( (2.1) với các điều kiện: gi(x) ≤ 0, i = 1,n (2.2) hj(x) ≤ 0, j = 1,q (2.3) nEXx ∈∈ (2.4) trong đó, x = {x1,x2,…,xn} – vectơ cần tối ưu hóa; En – không gian Ơclit n chiều; X – là hình hộp khống chế các khoảng biến; f(x) – gọi là hàm mục tiêu; gi(x) – gọi là ràng buộc. Nếu bài toán ban đầu là cực đại hóa: f(x) Æ max, thì đổi sang cực tiểu hóa tương đương là; -f(x) Æ min. Ngoài ra, nếu gặp ràng buộc: gi(x) ≥ 0, thì có thể đổi sang: -gi(x) ≤ 0. TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 3/20 Tập hợp các điểm x thỏa mãn các điều kiện (2.1) – (2.3) tạo thành miền D, gọi là miền ràng buộc hay miền lời giải cho phép kí hiệu. D = {x∈X | gi(x) ≤ 0, i=1,n; hj(x) ≤ 0, j = 1,q } (2.5) Mỗi điểm x ∈ D gọi là một lời giải chấp nhận đuợc. Điểm x*∈ D đạt điểm cực tiểu của hàm mục tiêu (tức f(x*) ≤ f(x) ∀x ∈D) gọi là lời giải tối ưu, còn f(x*) – giá trị tối ưu bài toán. Việc nghiên cứu phương pháp giải các bài toán tối ưu hóa là nội dung chính của môn tối ưu hóa hay Quy hoạch toán học và áp dụng chúng vào các bài toán kỹ thuật Nhiệt nói riêng và kỹ thuật nói chung có một ý nghĩa thực tiễn to lớn: như giải quyết bài toán chế độ vận hành tối ưu các tổ máy năng lượng trong các nhà máy nhiệt điện trong điều kiện khác nhau sẽ đem lại những lợi ích kinh tế to lớn, hay các bài toán về tối ưu các tham số của hệ thống điều khiển – đây là những bài toán lớn trong thực tế. 3. Sơ lược về bài toán tối ưu hóa hàm một biến và phương pháp giải Xét bài toán cực tiểu hóa hàm một biến f(x) trong không gian Ơclit n chiều En: nEx xf ∈ → min)( (3.1) Trong đó f(x) liên tục, có thể không khả vi (không tồn tại đạo hàm tại điểm nào đó). Phương pháp tổng quát để tìm cực trị hàm một biến là: -Phương pháp chia đôi -Phương pháp lát cắt vàng. -Phương pháp xấp xỉ hàm. -Phương pháp dây cung. -phương pháp tiếp tuyến. Trong đó ba phương pháp cuối yêu cầu hàm trơn và có đạo hàm liên tục, hai phương pháp đầu yêu cầu duy nhất đối với hàm mục tiêu là không bị đứt đoạn. Đây là những phương pháp kinh điển, sau đó PGS.TSKH.VS Nguyễn Văn Mạnh đã đưa ra một phương pháp mới là phương pháp “ vượt khe” đây là một phương pháp rất mạnh nó cũng chỉ có yêu cầu là hàm mục tiêu không bị đứt đoạn, và hiệu quả cao đối với những hàm trơn từng khúc so với tất cả các phương pháp đã biết. Sau đây giới thiệu một số phương pháp nêu trên. 3.1. Xét phương pháp chia đôi Chia trục x ra thành m khoảng đủ nhỏ để bắt được những khoảng chứa điểm cực trị. Thông thường ta chia theo cấp số nhân (để mở rộng khoảng được xét): xi+1 = xi q (q>1). Sau đó tính f(x) tại các điểm mút xi với giả thiết các khoảng chia đủ nhỏ thì điểm cực tiểu sẽ nằm trong đoạn (xk-1, xk) nếu thoả mãn điều kiện TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 4/20 f(xk)≤f(xk+1) và f(xk)≥f(xk-1). Đối với mỗi khoảng sẽ tìm điểm cực tiểu chính xác hơn. Với khoảng đủ nhỏ có thể coi hàm trong khoảng đó là lồi. Thuật toán được thể hiện cụ thể như sau: Tính c:=(a+b)/2; Các trường hợp xảy ra: • f(a) < f(c) < f(b) Gán b:=c Î miền [a, b] mới • f(a) > f(c) > f(b) Gán a:=c Î miền [a, b] mới • f(c) < f(a) và f(c) < f(b) d:= (a+c)/2; tính f(d) Nếu f(c) > f(d) gán b:=c Nếu f(c) < f(d) gán a:=d Nếu f(c) = f(d) gán a:=d; b:=c 3.2. Phương pháp “lát cắt vàng” Phương pháp này dựa trên tỉ lệ chia khoảng tối ưu của đoạn chia tìm điểm tối ưu tỉ lệ chia tối ưu = 618,0 2 15 =− a, b cho trước: Tính [a,c] = 0,382[a,b] = γ[a,b] [a,d] = 0,681[a,b] = (1-γ)[a,b] Tính f(a), f(b), f(c), với c = γ(b-a)+a Nếu: f(a) > f(c) > f(b) → a:=c; f(a) < f(c) < f(b) → b:=c; f(c) < f(a) và f(c) < f(b); d:= c+γ(b-c); tính f(d); Nếu f(c) < f(d) < f(b) → b:=d; f(c) > f(d) → a:=c; f(c) = f(d) → a:=c; b:=d; Và trình tự quay lại từ đầu, nếu ta biết rằng trong [a,b] có một điểm thấp nhất nhưng không có cực trị địa phương thì hai thuật toán trên sẽ hội tụ về Hình 3.1 Hình 3.2 f(b x f(x) f(a x* d c e f(b) x f(x) f(a) c x* d a b TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 5/20 điểm thấp nhất đó. Nếu có nhiều điểm cực trị địa phương thì nghiệm tối ưu sẽ rơi vào một trong những điểm cực tiểu địa phương đó. 3.3. Phương pháp xấp xỉ bậc hai Phương trình bậc hai: f(x) = ax2 + bx + c (3.2) Nếu biết 3 điểm x1, x2, x3 thì thay vào (3.2) Viết lại dưới dạng: f(x) = a0 + a1(x-x1) + a2(x-x1)(x-x2) ՜ f(x1) = a0 f(x2)= a0 + a1(x2 – x1) Vậy 12 12 2 xx ffa − −= f(x3)= a0 + a1(x3 – x1) +a2(x3 – x1)(x3 – x2) Vậy 23 12 12 13 13 3 xx xx ff xx ff a − − −−− − = f’(x) = a1 + a2(x-x1) + a2(x-x2) = 0 → 2 121 22 a axxx −+= Nếu ε<− 31 xx thì dừng lại Nếu không tính 2 121 22 a axxx −+= • Nếu x2 ≤ x ≤ x3 thì tính f( x ) - Nếu f( x ) < f(x2) thì bỏ x1, gán x1 = x2, x = x - Nếu f( x ) ≥ f(x2) thì gán x3 = x rồi quay về bước đầu tiên. • Nếu x1 > x ≥ x2 thì tính f( x ) - Nếu f( x ) < f(x2) thì bỏ x3, gán x3 = x2, x2 = x - Nếu f( x ) ≥ f(x2) thì gán x1 = x rồi quay về bước đầu tiên. 4. Khái quát về hàm tối ưu hóa đa biến Hình 3.3 x f(x) f1 x1 x2 x3 f2 f3 x TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 6/20 Xét bài toán cực tiểu hàm nhiều biến f(X) trong không gian Euclide n chiều En nEX Xf ∈ → min)( (4.1) với các điều kiện: gi(X) ≤ 0, i = 1,n nEX ∈ Nếu một trong những hàm f(X), gi(X) là phi tuyến, thì phương pháp giải gọi là thuật toán tối ưu hóa phi tuyến. Phương pháp giải là dùng hàm phạt chuyển bài toán về bài toán tối ưu hóa tương đương: ∑Ψ+= )()()( XpXfXJ i 2|])(|)([)( XgXgX iii ==Ψ p>0 J(X) là hàm mục tiêu tương đương, nhưng điểm cực tiểu của nó trùng với nghiệm bài toán ban đầu (p đủ lớn). Hầu hết các phương pháp tối ưu hóa phi tuyến xây dựng theo nguyên tắc lặp, tức thay đổi vectơ tối ưu hóa theo từng bước, từ điểm bắt đầu xo , đến điểm tối ưu x*. Phương trình lặp của thuật toán tối ưu hóa lặp: xk+1 = xk + αk+1sk, k= 0,1,..., (4.2) xk+1 , xk – điểm đầu và điểm cuối của bước lặp thứ k+1; sk – hướng dịch chuyển; αk+1- độ dài bước thứ k+1; xk+1 , xk ,sk∈En; En – không gian Ơclit n chiều. Khi số bước lặp tăng dần: k=0,1,…theo phương trình (4.2) sẽ hình thành trong không gian một quỹ đạo chuyển dịch có hình gấp khúc, bao gồm các điểm tiến dần đến nghiệm tối ưu: x → x1 → …xk → xk+1 …→x*. Với ý nghĩa phải tính toán xác định quỹ đạo từng bước trong không gian để đi đến điểm tối ưu, người ta gọi đó là quỹ đạo tìm kiếm tối ưu với: xk – là các điểm tìm kiếm, sk – các hướng tìm kiếm, αk+1 – các bước tìm kiếm. Những vấn đề đáng quan tâm nhất của mỗi thuật toán tối ưu hoá phi tuyến là tốc độ hội tụ, độ chính xác của lời giải, và phạm vi áp dụng của thuật toán. Quỹ đạo đi tìm điểm tối ưu của thuật toán “hạ nhanh nhất” 5. Các quy tắc xác định bước chuyển dịch oxo J1 x1 x2 x* TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 7/20 Gi¶ sö ta cã bμi to¸n cùc tiÓu ho¸ hμm ®a biÕn v« ®iÒu kiÖn nh− sau: nEx xf ∈ → min)( (5.1) Trong ®ã, En – lμ kh«ng gian ¬clÝt n chiÒu. C¸c thuËt to¸n tèi −u ho¸ lÆp ®−îc x©y dùng trªn c¬ së hai kh¸i niÖm c¬ b¶n lμ h−íng t×m kiÕm (h−íng thay ®æi c¸c biÕn) vμ qui t¾c ®iÒu chØnh ®é dμi b−íc lÆp. Qóa tr×nh tèi −u ho¸ lÆp liªn tiÕp tõ b−íc thø k sang b−íc thø k+1 thùc hiÖn theo quan hÖ: xk+1 = xk + αk+1sk, k= 0,1,..., (5.2) trong đó: xk+1 , xk∈En – điểm đầu và điểm cuối (còn gọi là điểm tìm kiếm) của bước lặp thứ k+1; sk ∈En– hướng dịch chuyển; αk+1- độ dài bước thứ k+1. NÕu xÐt mét c¸ch tæng thÓ vÒ vÊn ®Ò x©y dùng thuËt to¸n tèi −u ho¸ hμm ®a biÕn d−íi d¹ng tæng qu¸t, th× kh¸i niÖm h−íng t×m kiÕm vμ ®é dμi b−íc chuyÓn ®éng cã ý nghÜa t−¬ng ®−¬ng trong viÖc ®¶m b¶o sù héi tô vμ tèc ®é héi tô cña mét qu¸ tr×nh lÆp. ChØ khi kÕt hîp mét c¸ch hîp lý gi÷a h−íng chuyÓn ®éng vμ nguyªn t¾c x¸c ®Þnh ®é dμi b−íc míi ®¶m b¶o hiÖu qu¶ héi tô thùc tÕ cao. Cã thÓ kÕt hîp mét ph−¬ng thøc x¸c ®Þnh h−íng chuyÓn ®éng víi nhiÒu qui t¾c ®iÒu chØnh b−íc hoÆc ng−îc l¹i kÕt hîp mét qui t¾c ®iÒu chØnh b−íc víi nhiÒu ph−¬ng thøc x¸c ®Þnh h−íng chuyÓn ®éng, sÏ t¹o ra nhiÒu thuËt to¸n kh¸c nhau. HiÖn nay sè l−îng nh÷ng thuËt to¸n tèi −u ho¸ ®· ®Ò xuÊt ®¹t tíi con sè hμng tr¨m, mμ chóng chñ yÕu kh¸c nhau vÒ ph−¬ng thøc x¸c ®Þnh h−íng t×m kiÕm. Song sè l−îng nh÷ng qui t¾c ®iÒu chØnh b−íc th× l¹i rÊt Ýt, kh«ng qu¸ 6 qui t¾c c¬ b¶n. 5.1. Qui t¾c ®iÒu chØnh b−íc thø nhÊt Lμ c¸ch ®¬n gi¶n nhÊt lμ c¸ch ®iÒu chØnh b−íc chØ c¨n cø theo ®iÒu kiÖn sao cho hμm môc tiªu lu«n lu«n gi¶m sau kÕt qu¶ t×m kiÕm trªn mçi b−íc lÆp nh− sau: (xk+1) = J(xk + αk+1sk) < J(xk), k =0,1,... (5.3) §©y lμ mét ®iÒu kiÖn qu¸ yÕu, kh«ng ®ñ ®Ó ®¶m b¶o sù héi tô vμ, h¬n n÷a, cμng kh«ng thÓ cã t¸c dông t¨ng tèc ®é héi tô cña hÇu hÕt c¸c thuËt to¸n tèi −u ho¸ hμm tr¬n vμ kh«ng tr¬n. Qui t¾c ®iÒu chØnh b−íc nãi trªn kh¸ th« thiÓn nªn chØ ¸p dông trong c¸c thuËt to¸n ®¬n gi¶n, vÝ dô thuËt to¸n tôt theo to¹ ®é. Trong thuËt to¸n ®a diÖn biÕn d¹ng, qui t¾c ®iÒu chØnh b−íc (5.3) thÓ hiÖn mét c¸ch Èn th«ng qua ba phÐp to¸n ®Æc biÖt lµ ph¶n x¹, kÐo d·n vµ co ®a diÖn. §©y lµ nh÷ng phÐp biÕn ®æi h×nh häc thuÇn tuý, kh«ng cã mèi liªn hÖ TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 8/20 chÆt chÏ víi tÝnh chÊt h×nh häc cña hµm cùc tiÓu ho¸. Do vËy, viÖc chøng minh sù héi tô cña thuËt to¸n gÆp nhiÒu khã kh¨n. VÒ mÆt thùc tÕ, nhiÒu tr−êng hîp ¸p dông cho thÊy thuËt to¸n nµy héi tô kh¸ nhanh, nh−ng l¹i cã nhiÒu tr−êng hîp thuËt to¸n bÞ m¾c ë khe hoÆc hoµn toµn kh«ng héi tô 5.2. Qui t¾c ®iÒu chØnh thø hai Lμ chän cè ®Þnh theo ®iÒu kiÖn Lipchits, vÝ dô: α k+1=α , 0<α <1/L, k =0,1,..., (5.4) trong ®ã L lμ h»ng sè Lipchits, lμ “®é dèc” lín nhÊt cña hμm môc tiªu. Qui t¾c ®iÒu chØnh b−íc (5.4) th−êng ¸p dông ®èi víi c¸c thuËt to¸n gradien ®¬n gi¶n ®Ó cùc tiÓu ho¸ c¸c hμm tr¬n, tu©n theo ph−¬ng tr×nh lÆp (5.2). §iÒu kiÖn (5.4) ®ñ ®Ó ®¶m b¶o tÝnh ®¬n ®iÖu vμ sù héi tô lý thuyÕt cña qu¸ tr×nh tèi −u ho¸, khi h−íng t×m kiÕm lμ vÐct¬ ®èi gradien cña hμm môc tiªu. Nh−îc ®iÓm thø nhÊt cña qui t¾c ®iÒu chØnh b−íc nãi trªn lµ vÊn ®Ò h»ng sè Lipchits mµ trong ®a sè c¸c tr−êng hîp thùc tÕ lµ kh«ng biÕt tr−íc vµ kh«ng thÓ x¸c ®Þnh ®−îc. Nh−îc ®iÓm thø hai, mét nh−îc ®iÓm cã b¶n cña qui t¾c ®iÒu chØnh b−íc kiÓu nµy lµ chØ ®¶m b¶o h×nh thµnh nh÷ng thuËt to¸n héi tô chËm 5.3. Qui t¾c ®iÒu chØnh b−íc thø ba Dùa trªn sù tËn dông triÖt ®Ó kh¶ n¨ng gi¶m cña hμm môc tiªu trong mçi b−íc, tøc lμ ®iÓm t×m kiÕm ®¹t cùc tiÓu cña hμm môc tiªu theo h−íng chuyÓn dÞch. §iÒu kiÖn ®¹t cùc tiÓu theo h−íng viÕt nh− sau: ).(minarg kk 0 1k sx αα α += ≥+ J , k = 0,1,... (5.5) §é dμi b−íc x¸c ®Þnh theo ®iÒu kiÖn (1.5) cã tªn gäi lμ b−íc “triÖt ®Ó”.Trong c¸c tr−êng hîp hμm môc tiªu khe râ rÖt, víi b−íc chuyÓn dÞch “triÖt ®Ó”, ®iÓm t×m kiÕm th−êng ®¹t tíi ®óng “lßng khe”. Do ®ã cã thÓ gäi lμ “b−íc tíi khe” hay “b−íc khe”. Qui t¾c ®iÒu chØnh (5.5) kh«ng chØ ®¶m b¶o héi tô cho c¸c thuËt to¸n gradien thuÇn tuý ®èi víi c¸c hμm tr¬n, mμ cßn ®¶m b¶o tèc ®é héi tô cao so víi c¸c thuËt to¸n gradien kh¸c. Khi qu¸ tr×nh tèi −u ho¸ xuÊt ph¸t tõ vÞ trÝ n»m c¸ch xa l©n cËn tèi −u, th× c¸c hµm môc tiªu th−êng kh«ng ph¶i lµ toµn ph−¬ng vµ thËm chÝ lµ kh«ng låi, qui t¾c ®iÒu chØnh b−íc “triÖt ®Ó” kh«ng mang l¹i hiÖu qu¶ héi tô cao nhÊt. §Æc biÖt, khi hµm cùc tiÓu ho¸ cã “khe cong” hoÆc lµ kh«ng tr¬n, b−íc TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 9/20 “triÖt ®Ó” thÓ hiÖn lµ “b−íc khe” râ rÖt vµ do ®ã dÔ lµm cho quÜ ®¹o t×m kiÕm bÞ t¾c ë lßng khe 5.4. Qui t¾c ®iÒu chØnh b−íc thø t− Cã thÓ ®−îc xÐt lμ do Gelfand ®Ò xuÊt. Theo qui t¾c nμy, ®é dμi b−íc x¸c ®Þnh bëi phÐp ngo¹i suy tùa theo h−íng lßng khe, c¸c thuËt to¸n khe cña Gelfand chØ ¸p dông hiÖu qu¶ cho nh÷ng tr−êng hμm sè cã lßng khe kh«ng qu¸ hai chiÒu. 5.5. Qui t¾c thø n¨m Lμ c¸ch ®iÒu chØnh b−íc theo qui luËt chuçi sè ®Þnh tr−íc. Qui t¾c kiÓu nμy ¸p dông chñ yÕu trong c¸c thuËt to¸n lÆp tèi −u ho¸ hμm kh«ng tr¬n vμ c¸c hμm ngÉu nhiªn. §é dμi b−íc ë ®©y x¸c ®Þnh theo ®iÒu kiÖn §voreskyi d−íi nhiÒu d¹ng kh¸c nhau sao cho ®¶m b¶o sù héi tô theo nghÜa x¸c xuÊt: 0lim , , kk1k 2 k 1k k =∞<∞= ∞→ ∞ = ∞ = ∑∑ ααα . (5.6) C¸c phÇn tö αk trong chuçi sè tho¶ m·n ®iÒu kiÖn (1.6) cã thÓ chän theo qui luËt: 5,0 ,0 , )1(k >>+= cbk b cα . (5.7) LuËt ®iÒu chØnh b−íc chuçi sè tho¶ m·n ®iÒu kiÖn (5.6)-(5.7) do Robins- Monro ®Ò xuÊt ®Ó x©y dùng thuËt gi¶i x¸c ®Þnh hμm håi qui theo c¸c sè liÖu ngÉu nhiªn. ThuËt gi¶i nμy cã tªn gäi lμ ph−¬ng ph¸p “xÊp xØ ngÉu nhiªn. Qui t¾c nμy còng ®−îc ¸p dông më réng ®èi víi c¸c hμm kh«ng tr¬n vμ kh«ng låi. Trªn c¬ së kh¸i niÖm “hμm tr¬n ho¸” vμ “gradien tr¬n ho¸”, Gupal ®Ò xuÊt mét biÕn thÓ cña qui t¾c ®iÒu chØnh b−íc kiÓu chuçi sè nh− sau. ,0 ,0 ,0 ,0lim , , k k1k k k k k kk1k 2 k 1k k →−→Δ→ →∞<∑∞=∑ + ∞→ ∞ = ∞ = β αα ββ α ααα (5.8) trong ®ã: Δk lμ gia sè biÕn ®Ó tÝnh gradien cña hμm tr¬n ho¸ theo c«ng thøc sai ph©n h÷u h¹n. Th−êng th−êng nã ®−îc tÝnh nh− gradien th«ng th−êng t¹i ®iÓm tùa k~x , mμ k~x mét ®iÓm ngÉu nhiªn trong h×nh hép víi t©m t¹i xk vμ c¹nh b»ng βk, xk lμ vÐct¬ c¸c biÕn tèi −u ho¸, nhËn ®−îc sau b−íc lÆp thø k. TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 10/20 Ph−¬ng tr×nh lÆp tèi −u ho¸ hμm kh«ng tr¬n cã h×nh thøc gièng nh− ®èi víi hμm tr¬n, nh−ng gradien ®−îc thay bëi gradien tr¬n ho¸, tøc gradien cña hμm môc tiªu t¹i ®iÓm k~x . Qui t¾c nµylµ c¬ së ®Ó x©y dùng c¸c thuËt to¸n tèi −u ho¸ hµm kh«ng tr¬n, víi sù ®¶m b¶o héi tô tiÖm cËn. Nh−ng c¸c qui t¾c ®iÒu chØnh b−íc theo kiÓu chuçi sè ®Þnh tr−íc ®−îc thiÕt lËp trªn c¬ së hÕt søc chung vµ sö dông l−îng th«ng tin rÊt nghÌo nµn vÒ tÝnh chÊt cña hµm môc tiªu. V× vËy, c¸c thuËt to¸n tèi −u ho¸ dùa trªn c¬ së qui t¾c ®iÒu chØnh b−íc trªn nãi chung cã tèc ®é héi tô chËm vµ cã hiÖu qu¶ øng dông thÊp. 5.6. Qui t¾c ®iÒu chØnh b−íc thø s¸u Lμ qui t¾c “v−ît khe” nh»m lμm c¬ së x©y dùng nh÷ng thuËt to¸n tèi −u ho¸ thÝch hîp vμ cã hiÖu qu¶ nhÊt ®Ó tèi −u ho¸ c¸c hμm khe. Trong c¸c bμi to¸n tèi −u ho¸ thùc tÕ, ®Æc biÖt trong c¸c nghμnh kü thuËt vμ c«ng nghÖ, c¸c hμm cùc tiÓu ho¸ thÓ hiÖn hoÆc lμ hμm tr¬n, hoÆc lμ hμm kh«ng tr¬n t¹i nh÷ng tËp ®iÓm giíi h¹n nμo ®ã, hoÆc lμ hμm ngÉu nhiªn râ nÐt trong miÒn hÑp nμo ®ã bao quanh ®iÓm tèi −u. Nh−ng trong hÇu hÕt c¸c tr−êng hîp chóng ®Òu cã tÝnh chÊt khe râ rÖt. Theo qui t¾c ®iÒu chØnh b−íc v−ît khe, ®é dμi b−íc αk+1 trong mçi lÇn lÆp kh«ng nhá h¬n ®é dμi b−íc “triÖt ®Ó” ®· nãi ë trªn. Qui t¾c nμy t¹o cho c¸c thuËt to¸n v−ît khe cã kh¶ n¨ng nghiªn cøu tæng thÓ vïng khe cña hμm môc tiªu vμ x¸c ®Þnh chiÕn l−îc chuyÓn dÞch ®Õn nghiÖm tèi −u mét c¸ch hiÖu qu¶ nhÊt. D−íi ®©y sÏ tr×nh bÇy tØ mØ vÒ quan ®iÓm ®iÒu chØnh b−íc theo nguyªn lý “v−ît khe”. 6. Nguyªn lý tèi −u ho¸ v−ît khe vµ thuËt to¸n x¸c ®Þnh b−íc v−ît khe Nh− mét thuËt to¸n gradien th«ng th−êng, ph−¬ng ph¸p “v−ît khe” x©y dùng trªn c¬ së hai kh¸i niÖm: h−íng thay ®æi hμm môc tiªu vμ qui t¾c ®iÒu chØnh b−íc. Theo nguyªn lý “v−ît khe”, ®iÓm ®Çu vμ ®iÓm cuèi cña mçi b−íc lÆp lu«n lu«n n»m vÒ hai phÝa ®iÓm cùc tiÓu cña hμm môc tiªu xÐt däc theo h−íng chuyÓn ®éng cña ®iÓm t×m kiÕm, t¹i mçi b−íc. Sù chuyÓn ®éng ®ã t¹o ra bøc tranh h×nh häc tùa nh− trªn mçi b−íc lÆp, ®iÓm t×m kiÕm lu«n lu«n “b−íc” qua “lßng khe” cña hμm môc tiªu. Sù chuyÓn ®éng v−ît qua ®iÓm cùc tiÓu (theo h−íng) trªn mçi b−íc lÆp t¹o ra kh¶ n¨ng kh¶o s¸t “®Þa h×nh” vïng khe vμ nhËn ®−îc th«ng tin cô thÓ vÒ ®Æc tÝnh khe cña hμm môc tiªu. §iÒu ®ã cho phÐp x©y dùng chiÕn l−îc t×m kiÕm hiÖu qu¶ nhÊt dÉn ®Õn nghiÖm tèi −u. §é dμi b−íc lÆp x¸c ®Þnh theo nguyªn lý “v−ît khe” cã tªn gäi lμ “b−íc v−ît khe” Gi¶ sö ta cã hμm cùc tiÓu ho¸ J(x), x∈En. XÐt hμm mét biÕn x¸c ®Þnh t¹i b−íc lÆp thø k+1 nh− sau: h(α) = J(xk + α.sk), (6.1) trong ®ã xk - ®iÓm ®Çu; sk - h−íng t×m kiÕm; α - ®é dμi b−íc TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 11/20 NÕu hμm cùc tiÓu ho¸ J(x) kh¶ vi liªn tôc kh¾p mäi n¬i th× hμm h(α) còng kh¶ vi liªn tôc. V× sk lμ h−íng gi¶m hμm môc tiªu nªn ®¹o hμm theo h−íng tho¶ m·n ®iÒu kiÖn: 0),()()(' kk 0 kk 0 <∇=+= == sxsx JJd dh αα ααα , (6.2) trong ®ã, 〈u,v〉 - ký hiÖu tÝch v« h−íng cña hai vÐct¬ u vμ v. BÊt ®¼ng thøc (6.2) cã nghÜa lμ t¹i l©n cËn α ≈ 0 hμm mét biÕn h(α) lu«n lu«n gi¶m theo α. NÕu J(x) bÞ chÆn d−íi th× h(α) còng bÞ chÆn d−íi. Ngoμi ra, nÕu ∞=∞→ )(lim xx J th× lu«n lu«n tån t¹i b−íc “triÖt ®Ó”: )(minarg* 0 αα α h > = , (6.3) tøc tån t¹i ®iÓm cùc tiÓu ®Þa ph−¬ng α* cña hμm h(α). Tõ ®©y, theo nguyªn lý “v−ît khe”, ta cã ®iÒu kiÖn x¸c ®Þnh b−íc: ).0()( ,0)( v' v hhh ≤>= αα αα (6.4) trong ®ã, αv - gäi lμ “b−íc v−ît khe”. Qu¸ tr×nh chuyÓn dÞch theo nguyªn lý “v−ît khe” t¹i mçi b−íc lÆp x¶y ra nh− thÓ hiÖn trªn h×nh 6.1 DÔ thÊy trªn ®å thÞ h×nh 1.4 r»ng, theo ®iÒu kiÖn (6.4) ®iÓm t×m kiÕm chuyÓn dÞch tõ xk, v−ît qua ®iÓm cùc tiÓu trong h−íng sk tíi ®iÓm cuèi xk+1, theo ph−¬ng tr×nh: xk+1 = xk + αk+1sk, αk+1=αv. §å thÞ h×nh 6.1 còng chØ râ r»ng, tÝnh theo h−íng chuyÓn ®éng th× ®iÓm cuèi xk+1 lu«n lu«n n»m trªn s−ên dèc lªn (s−ên t¨ng). Nh− vËy quÜ ®¹o tèi −u ho¸ lu«n lu«n v−ît qua lßng khe, kh«ng cho phÐp ®iÓm t×m kiÕm r¬i vμo lßng khe tr−íc khi ®¹t lêi gi¶i tèi −u. H×nh 6.1 X¸c ®Þnh b−íc v−ît khe αv; h(α) = J(xk +αsk). α h(α) h(αvk) αvα*0 h(α*) TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 12/20 §Ó t¹o ra nh÷ng hiÖu qu¶ t¨ng tèc ®é héi tô kh¸c nhau cña thuËt to¸n cã thÓ ¸p ®Æt thªm mét sè ®iÒu kiÖn kh¸c ®èi víi ®iÒu kiÖn x¸c ®Þnh b−íc v−ît khe. D−íi ®©y lμ ®iÒu kiÖn x¸c ®Þnh b−íc v−ît khe, cho hiÖu qu¶ héi tô vμ ®é æn ®Þnh cao cña qu¸ tr×nh lÆp: ],)0([)(])0([ ),(minarg* ba hhhhhh h −≤−≤− =≥ λαλ ααα α v v (6.5) trong ®ã, 0≤ λa ≤ λb ≤1 lμ c¸c hÖ sè v−ît trªn vμ d−íi. Trong c¸c thÓ hiÖn ch−¬ng tr×nh m¸y tÝnh, gi¸ trÞ *)(αhh = th−êng ®−îc thay b»ng c¸c ®¸nh gi¸ gÇn ®óng. Theo c¸c ®iÒu kiÖn x¸c ®Þnh b−íc v−ît khe võa tr×nh bÇy ë trªn vμ theo (6.5), cã thÓ dÉn ra d−íi ®©y c¸ch x¸c ®Þnh b−íc v−ît khe, ®iÒu kiÖn ®¹t s−ên t¨ng cña khe ®−îc kiÓm tra b»ng c¸ch so s¸nh c¸c gi¸ trÞ hμm h(α) t¹i ba ®iÓm liªn tiÕp. ThuËt to¸n x¸c ®Þnh b−íc v−ît khe theo c¸ch nãi trªn cã thÓ m« t¶ theo hai c¸ch nh− sau: C¸ch 1 Cho tr−íc: εP>0, β>1, 00. 1. Cho p1=0, p2=αA vμ t¨ng liªn tiÕp theo qui t¾c: p1:=p2, p2:=βp2 cho ®Õn khi h(p2)≥h(p1). NhËn ®−îc ®o¹n (p1,p2), g¸n p:=p1 cuèi cïng vμ chuyÓn xuèng b−íc 2. 2. KiÓm tra ®iÒu kiÖn h’(p)≥0, NÕu tho¶ m·n, nhËn αv:=p vμ kÕt thóc vμ quay vÒ ch−¬ng tr×nh chÝnh. Tr¸i l¹i, chuyÓn sang b−íc 3. 3. KiÓm tra ®iÒu kiÖn kho¶ng nhá: p2−p1≤εP. NÕu ®iÒu kiÖn tho¶ m·n, tøc lμ kh«ng t×m ®−îc b−íc v−ît khe víi ®é chÝnh x¸c εP. NhËn αv:=p2 vμ kÕt thóc vμ quay vÒ ch−¬ng tr×nh chÝnh. Tr¸i l¹i, chuyÓn sang b−íc 4. 4. TÝnh p:= p1+γ(p2−p1).nÕu h(p)>h(0), th× g¸n p2:=p vμ chuyÓn sang b−íc 3. Tr¸i l¹i g¸n p1:=p vμ quay vÒ b−íc 2. S¬ ®å thuËt to¸n p1:=p2, p2:=βp2 h(p2) ≥ h(p1) Trë vÒ ch−¬ng tr×nh chÝnh. p2 - p1≤ εp h(p) − h(p1) >λbΔ p = p1 + γ(p2 − p1), Δ = h(0) − h(p1). p1:= p αv:=p p2 := p Yes Yes h(p) −h(p1) >λaΔ Yes Gäi tõ ch−¬ng tr×nh chÝnh sau khi g¸n p2:=αA No TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 13/20 C¸ch 2 Cho tr−íc: εP>0, β>1, 00. 1. Cho p1=0, p2=αA vμ t¨ng liªn tiÕp theo qui t¾c: p1:=p2, p2:=βp2 cho ®Õn khi h(p2)≥h(p1). NhËn ®−îc ®o¹n (p1,p2) cuèi cïng vμ chuyÓn xuèng b−íc 2. 2. KiÓm tra: NÕu p2−p1≤εP tho¶ m·n, tøc lμ kh«ng t×m ®−îc b−íc v−ît khe víi ®é chÝnh x¸c εP. NhËn αv:=p vμ kÕt thóc vμ quay vÒ ch−¬ng tr×nh chÝnh. Tr¸i l¹i, chuyÓn sang b−íc 3. 3. TÝnh p:= p1+γ(p2−p1) vμ Δ=[h(0)−h(p1)], chuyÓn sang b−íc 4. 4. NÕu h(p)−h(p1)>λbΔ, th× g¸n p2:=p; nÕu h(p)−h(p1)<λaΔ, th× g¸n p1:=p; quay l¹i b−íc 2. Tr−êng hîp cßn l¹i, t×m ®−îc b−íc v−ît khe: NhËn αv=p, ®æi αA:=p vμ trë vÒ ch−¬ng tr×nh chÝnh. Ch−¬ng tr×nh con lËp trªn m¸y tÝnh ®èi víi c¸ch thø hai ®¬n gi¶n h¬n c¸ch thø nhÊt. Ngoμi ra, c¸ch nμy cã thÓ øng dông cho c¶ tr−êng hîp hμm tr¬n vμ kh«ng tr¬n. §é chÝnh x¸c t×m b−íc v−ît khe th−êng cho: εP=δx, trong ®ã δx lμ gia sè cho tr−íc (dïng khi tÝnh c¸c ®¹o hμm riªng theo c«ng thøc sai ph©n h÷u h¹n) hay ®é chÝnh x¸c lêi gi¶i (nÕu gradien x¸c ®Þnh b»ng c«ng thøc gi¶i tÝch). B−íc thö ban ®Çu αA th−êng thay ®æi theo nguyªn t¾c thÝch nghi, tøc lμ b»ng gi¸ trÞ ®é dμi b−íc nhËn ®−îc ë lÇn lÆp tr−íc. Do vËy, cã thÓ cho gi¸ trÞ xuÊt ph¸t cña nã b»ng cè ®Þnh trong mäi tr−êng hîp. VÝ dô th−êng cho αA=0,1=const. HÖ sè t¨ng tr−ëng b−íc chän cè ®Þnh lμ 1.5 H×nh 6.3 S¬ ®å khèi x¸c ®Þnh b−íc v−ît khe theo c¸ch thø hai. p1:=p2, p2:=βp2 h(p2) ≥ h(p1) Trë vÒ ch−¬ng tr×nh chÝnh. p2 - p1≤ εp h(p) − h(p1) >λbΔ p = p1 + γ(p2 − p1), Δ = h(0) − h(p1). p1:= p αv:=p p2 := p Yes Yes h(p) −h(p1) >λaΔ Yes Gäi tõ ch−¬ng tr×nh chÝnh sau khi g¸n p2:=αA No H×nh 6.2 S¬ ®å khèi x¸c ®Þnh b−íc v−ît khe theo c¸ch thø nhÊt. TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 14/20 C¸c tham sè hiÖu chØnh cña ph−¬ng ph¸p lμ c¸c hÖ sè v−ît phÝa trªn vμ phÝa d−íi: λa, λb vμ hÖ sè ph©n chia: γ. C¸c bé gi¸ trÞ kh¸c nhau cña chóng sÏ t¹o cho thuËt to¸n tèi −u ho¸ nh÷ng tÝnh chÊt kh¸c nhau ®èi víi c¸c líp hμm cã trong thùc tÕ. VÝ dô, ®Ó t¨ng kh¶ n¨ng nghiªn cøu tæng thÓ ®Þa h×nh khe th−êng chän λa, λb, γ lín. §èi víi hÇu hÕt c¸c bμi to¸n thùc tÕ, nhËn ®−îc hiÖu qu¶ cao nÕu:λa = 0; λb= 0,5; γ = 0,13. 7. H−íng chiÕu Afine vµ ph−¬ng ph¸p tÝnh to¸n Trong thuËt to¸n v−ît khe theo h−íng chiÕu Afine (VAF), h−íng t×m kiÕm trong thuËt to¸n VAF ®−îc x¸c ®Þnh tùa theo ®−êng vu«ng gãc h¹ tõ ®Ønh cña h×nh chãp t¹o bëi c¸c vÐct¬ ®èi gradien x¸c ®Þnh trªn c¸c b−íc lÆp tr−íc, trong kh«ng gian ¥clÝt n chiÒu. H×nh tam gi¸c lμ tr−êng hîp riªng cña h×nh chãp trong kh«ng gian hai chiÒu. ChiÕu ®−êng vu«ng gãc cña h×nh chãp lªn tæ hîp tuyÕn tÝnh cña c¸c ®èi gradien nãi trªn gièng nh− chiÕu mét vÐct¬ lªn kh«ng gian Afine. Tõ ®ã mμ xuÊt hiÖn tªn gäi h−íng chiÕu Afine cña thuËt to¸n. H×nh 7.1 Sù h×nh thμnh h−íng chiÕu Afine theo b−íc lÆp ,∇i = −∇J(xi). H×nh 7.2 Sù h×nh thμnh h−íng chiÕu Afine m« h×nh tuyÕn tÝnh tõng phÇn. H−íng chuyÓn dÞch sk lu«n lu«n song song víi “lßng khe”. §iÒu nμy ®· chøng minh mét c¸ch chÆt chÏ ®èi víi tr−êng hîp tæng qu¸t cña hμm tuyÕn tÝnh tõng phÇn. NÕu sù chuyÓn dÞch tõ ®iÓm xk-1 ®Õn xk theo yªu cÇu sao cho ®iÓm xk ®· v−ît qua nh−ng n»m s¸t lßng khe, th× h−íng sk cña b−íc tiÕp theo sÏ trïng víi x0 x1 x2 x3