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 ∇0 ∇1 ∇0 ∇1 ∇2 α1 α2 α3 s0 s1 s2 TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 15/20 lßng khe vμ sù chuyÓn dÞch däc theo nã dÉn tíi ®iÓm cùc tiÓu chÝnh x¸c x* cña hμm hai biÕn. Mét c¸ch tæng qu¸t, ®Ó b¸m s¸t theo lßng khe cña hμm môc tiªu trong kh«ng gian n chiÒu cÇn dùa trªn c¬ së n vÐct¬ ®èi gradien thu ®−îc t¹i c¸c b−íc tr−íc ®ã thùc hiÖn theo nguyªn lý v−ît khe. Trªn c¬ së t− t−ëng ®ã cã thÓ x©y dùng mét ph−¬ng ph¸p rÊt hiÖu qu¶ vμ v¹n n¨ng ®Ó tèi −u ho¸ c¸c lo¹i hμm d¹ng khe tæng qu¸t. Ph−¬ng ph¸p cã tªn gäi lμ thuËt to¸n v−ît khe h−íng chiÕu Afine (VAF). Qu¸ tr×nh tèi −u ho¸ theo thuËt to¸n VAF viÕt cho b−íc thø k+1 cã d¹ng: xk+1 = xk + αk+1sk, s0 = −∇J(x0), k=0,1,... (7.1) trong ®ã, αk+1=αv- b−íc v−ît khe; sk- h−íng chiÕu affine hay h−íng chuyÓn ®éng tùa theo ®−êng vu«ng gãc cña h×nh chãp (trong kh«ng gian n chiÒu) t¹o bëi r vÐct¬ ®èi gradien nhËn ®−îc trªn c¸c b−íc lÆp liªn tiÕp tr−íc ®ã. Trªn c¸c b−íc ®Çu tiªn, r t¨ng dÇn tõ 1 ®Õn n. Qu¸ tr×nh lÆp theo thuËt to¸n VAF cã thÓ gi¶i thÝch nh− sau (h×nh 7.1). B¾t ®Çu tõ x0, ®iÓm t×m kiÕm chuyÓn dÞch theo h−íng s0 ≡∇0 = −∇J(x0) víi b−íc v−ît khe α1 ®Õn x1. KÕt thóc, ghi l¹i ∇0. T¹i ®iÓm x1 x¸c ®Þnh ®èi gradien ∇1 vμ h−íng s1 xuÊt ph¸t tõ ®Ønh x1 cña h×nh chãp 2 chiÒu; s1 vu«ng gãc víi ®¸y ∇1−∇0. Tõ x1, chuyÓn dÞch theo h−íng s1 víi b−íc v−ît khe α2 ®Õn ®iÓm x2. L−u thªm mét ®èi gradien ∇1 n÷a ®Ó dùng h×nh chãp tiÕp theo. T¹i ®iÓm x2, x¸c ®Þnh ®èi gradien ∇2. C¸c vÐct¬ ∇0,∇1,∇2 t¹o thμnh h×nh chãp víi ®Ønh t¹i ®iÓm x2. Dùng ®−êng vu«ng gãc cña h×nh chãp, th× nhËn ®−îc vÐct¬ s2 b¾t ®Çu tõ ®Ønh vμ kÕt thóc t¹i ®¸y cña nã. Theo h−íng s2 thùc hiÖn chuyÓn dÞch theo nguyªn lý v−ît khe tíi ®iÓm x3. VÐct¬ ∇2 ®−îc ghi l¹i cïng víi c¸c ®èi gradien tr−íc ®Ó dùng h×nh chãp trong c¸c b−íc lÆp tiÕp theo. Qu¸ tr×nh t×m kiÕm trªn ®©y thùc hiÖn cho ®Õn khi sè b−íc t¨ng dÇn tõ 1 (k=0) ®Õn n (k=n-1). TiÕp theo, khi sè b−íc k>n-1, chØ gi÷ l¹i n vÐct¬ ®èi gradien cña nh÷ng b−íc cuèi cïng ®Ó dùng h×nh chãp vμ ®−êng vu«ng gãc, tøc h−íng t×m kiÕm. Qu¸ tr×nh lÆp theo thuËt to¸n VAF diÔn ra cho ®Õn khi tho¶ m·n c¸c ®iÒu kiÖn dõng hoÆc theo lÖnh dõng cña ng−êi thao t¸c. H−íng chuyÓn ®éng sk cña thuËt to¸n VAF trªn mçi b−íc x¸c ®Þnh nh− d−íi ®©y. Ta biÓu diÔn sk d−íi d¹ng tæ hîp tuyÕn tÝnh: ∑ +∇= r 1=i 1i-k i k λs , r ≤ n, (7.2) trong ®ã, λi tho¶ ®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 16/20 1 1=i i =∑r λ . (7.3) Ngoμi ra, v× sk trïng víi ®−êng cao cña h×nh chãp, nªn nã trùc giao víi ®¸y cña h×nh chãp, tøc trùc giao víi Ýt nhÊt r-1 vÐct¬ hiÖu: ∇k-j+1 −∇k-j, j=1,2,...,r-1. §iÒu ®ã cã nghÜa lμ c¸c tÝch v« h−íng gi÷a sk vμ c¸c vÐct¬ hiÖu b»ng 0. ThiÕt lËp ®iÒu kiÖn trùc giao trªn c¬ së (1.15), ta ®−îc r-1 ph−¬ng tr×nh quan hÖ: 1,1 =j , 0, 1=i j-k1j-k1i-k i −=∇−∇∇∑ ++ rr λ , (7.4) KÕt hîp (1.16) víi (1.17), ta nhËn ®−îc hÖ ph−¬ng tr×nh tuyÕn tÝnh ®èi víi c¸c biÕn λ i. Gi¶i hÖ nμy sau ®ã thay c¸c nghiÖm λ i, i=1,...,r vμo (1.15), ta ®−îc h−íng t×m kiÕm cña b−íc thø k+1. HÖ ph−¬ng tr×nh (1.15)-(1.16) cã thÓ viÕt d−íi d¹ng matrËn: Aλ = b, (7.5) trong ®ã: ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ∇∇∇ ∇∇∇ ∇∇∇= ++++ + + 2r-k1r-k2r-k1-k2r-kk 1-k1r-k1-k1-k1-kk k1r-kk1-kkk ,...,, ,...,, ,...,, 1...11 δδδ δδδ δδδ A (7.6) ( 1,1j,j-k1j-kj-k −=∇−∇= + rδ ) (7.7) ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = r 2 1 ... λ λ λ λ ; ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = 0 ... 0 1 b ; (7.8) HÖ ph−¬ng tr×nh (7.5) víi ®iÒu kiÖn (7.6)-(7.8) dÔ dμng gi¶i ®−îc b»ng ph−¬ng ph¸p Gausse. §Ó ý r»ng theo (7.6) – (7.7), mçi khi chuyÓn tõ b−íc k sang k+1, trong ma trËn A chØ thay ®æi mét hμng vμ mét cét. Do ®ã, khi viÕt ch−¬ng tr×nh m¸y tÝnh cã thÓ rót gi¶m ®¸ng kÓ khèi l−îng tÝnh to¸n, nÕu x¸c ®Þnh ®−îc lêi gi¶i cña b−íc sau suy ra trªn c¬ së kÕt qu¶ cña b−íc tr−íc theo c«ng thøc truy to¸n. §iÒu ®ã cã ý nghÜa rÊt lín ®èi víi c¸c bμi to¸n qui ho¹ch kÝch th−íc lín h¬n. 8. S¬ ®å khèi vµ m« t¶ nguyªn t¾c lµm viÖc cña thuËt to¸n V−ît khe – h−íng chiÕu Affine. Sù kÕt hîp qui t¾c ®iÒu chØnh b−íc theo nguyªn lý v−ît khe víi h−íng chuyÓn ®éng ®−îc x¸c ®Þnh theo c¸ch nμo ®ã ®Òu t¹o thμnh mét thuËt to¸n tèi TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 17/20 −u ho¸ kiÓu vù¬t khe. Chóng t¹o thμnh mét líp c¸c thuËt to¸n “v−ît khe” vμ cã tÕn gäi chung lμ ph−¬ng ph¸p tèi −u ho¸ “v−ît khe”. §©y lμ ph−¬ng ph¸p tèi −u ho¸ v« ®iÒu kiÖn, cã logic ®¬n gi¶n nh− h×nh d−íi ®©y: T¹i b−íc lÆp ®Çu tiªn (k=0), cho ®iÓm xuÊt ph¸t x0, gia sè ban ®Çu δ x vμ b−íc (thÝch nghi) ban ®Çu αA=0,1. VÐct¬ chuyÓn ®éng ban ®Çu th−êng x¸c ®Þnh lμ ®èi gradien cña hμm môc tiªu t¹i ®iÓm xuÊt ph¸t: s0= −∇J(x0). Qu¸ tr×nh tèi −u ho¸ lÆp theo ph−¬ng ph¸p v−ît khe x¶y ra ë b−íc thø k+1 gåm hai giai ®o¹n chÝnh: 1. TÝnh gradien ∇J(xk) vμ x¸c ®Þnh h−íng c¶i tiÕn ®−îc sk (theo h−íng ®ã hμm môc tiªu cùc tiÓu ho¸ gi¶m). 2. ChuyÓn dÞch ®iÓm t×m kiÕm theo h−íng sk cho ®Õn khi ®¹t s−ên dèc lªn cña khe. Khi ®ã ®é dμi b−íc chuyÓn dÞch tho¶ m·n ®iÒu kiÖn v−ît khe. KÕt thóc b−íc lÆp k+1, nhËn ®−îc ®iÓm xÊp xØ míi: xk+1 = xk + αk+1sk, trong ®ã αk+1=αv lμ b−íc v−ît khe. Qu¸ tr×nh lÆp tiÕp diÔn cho ®Õn khi tho¶ m·n c¸c ®iÒu kiÖn dõng ®· ®Þnh tr−íc. VÝ dô ®èi víi hμm môc tiªu tr¬n th−êng dïng c¸c ®iÒu kiÖn sau ®©y: Dõng Khëi ®éng x0, J(x0), k = 0 ∇J(xk) hoÆc t−¬ng ®−¬ng C¸c ®iÒu kiÖn dõng tho¶ m·n ? X¸c ®Þnh h−íng t×m kiÕm: sk - h−íng c¶i tiÕn ®−îc. X¸c ®Þnh “b−íc v−ît khe” αv theo ®iÒu kiÖn (1.12) hoÆc (1.13). Cho αk+1=αv vμ tÝnh: xk+1 = xk +αk+1sk. Yes H×nh 8.1 S¬ ®å khèi cña thuËt to¸n v−ît khe. TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 18/20 ||∇J(xk)||1, < ε 1 ||xk+n - xk||2, < ε 2 ||J(xk+n) - J(xk)||3 , ε 3 trong ®ã ||.|| - ®é dμi hay chuÈn cña vÐct¬ trong kh«ng gian ¥clÝt; ε 1, ε 2, ε 3 - c¸c sè d−¬ng cho tr−íc trªn c¬ së c¸c th«ng tin tiªn nghiÖm (kiÕn thøc chuyªn gia) vÒ líp bμi to¸n cÇn gi¶i. Ta cã thÓ thÊy r»ng t×m kiÕm tèi −u theo nguyªn lý v−ît khe t¹o kh¶ n¨ng cho c¸c thuËt to¸n nghiªn cøu tÝnh chÊt hμm môc tiªu t¹i vïng khe. ThuËt to¸n cã kh¶ n¨ng thÝch nghi vμ x¸c ®Þnh ®−îc quÜ ®¹o chuyÓn dÞch hiÖu qu¶ nhÊt, tiÕn nhanh ®Õn nghiÖm tèi −u mμ kh«ng bÞ r¬i vμo “lßng khe” tr−íc thêi h¹n. Qui t¾c t×m b−íc v−ît khe còng kh¸ ®¬n gi¶n vÒ mÆt l«gÝc thùc hiÖn, thËm chÝ cã thÓ tÝnh b»ng tay vμ cho phÐp dÔ dμng ¸p dông ®Ó tèi −u ho¸ hÖ thèng ®ang ho¹t ®éng. 9. ¸p dông thuËt to¸n tèi −u ho¸ “v−ît khe” b»ng phÇn mÒm Optest Do giíi h¹n cña bμi tiÓu luËn, nªn trong bμi nμy chØ tr×nh bμy bμi to¸n ®¬n gi¶n ¸p dông thuËt to¸n v−ît khe ®Ó t×m cùc trÞ hμm hai biÕn víi c¸c ®iÒu kiÖn r»ng buéc ®Ó thÊy râ tÝnh −u viÖt thuËt to¸n “v−ît khe” so víi c¸c ph−¬ng ph¸p kh¸c. Ta gi¶ thiÕt ®Æt bμi to¸n nh− sau f(x) = 12x1 + 5x2 3 – 7x1 + 15x2 min (9.1) Víi ®iÒu kiÖn: ⎩⎨ ⎧ ≤+ ≤+ 302 2020 2 2 2 1 21 xx xx (9.2) Sö dông phÇn mÒm Optest víi c¸c b−íc tuÇn tù nh− sau: B−íc 1 ta chuyển về bài toán tối ưu hóa tương đương nhờ kỹ thuật hàm phạt: J7(x) = e2x1+5x2 +2x1 – 5x2 + 106(||x1 |+ | x2 |-2| + |x1 |+ | x2 |-2 +|(x1 + x2)2 -1.5| + (x1 + x2)2 -1.5) Hệ số phạt chọn ở đây là p = 106 Kết quả thực hiện bằng phần mềm Optest cho hàm f7(x): TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 19/20 Đường mức sau khi tối ưu hóa: TỐI ƯU HOÁ HỆ THỐNG NHIỆT - LẠNH LÊ PHẤN DŨNG KỸ THUẬT NHIỆT - LẠNH 20/20 TÀI LIỆU THAM KHẢO 1. Nguyễn Văn Mạnh; Bài giảng tối ưu hóa công nghệ nhiệt 2. Nguyễn Văn Mạnh; Phần mềm Optest tối ưu hóa hàm đa biến bất kỳ