CHƯƠNG 8: TỐI ƯU HOÁ

Chia sẻ: Hikaru Hikaru | Ngày: | Loại File: PDF | Số trang:33

1
212
lượt xem
95
download

CHƯƠNG 8: TỐI ƯU HOÁ

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

TÀI LIỆU THAM KHẢO VỀ TỐI ƯU HOÁ

Chủ đề:
Lưu

Nội dung Text: CHƯƠNG 8: TỐI ƯU HOÁ

  1. CHƯƠNG 8: TỐI ƯU HOÁ §1. KHÁI NIỆM CHUNG VỀ TỐI ƯU HOÁ    Tối ưu hoá là thuật ngữ thường được dùng để cực tiểu hoá hay cực đại  hoá một hàm. Thông thường ta chỉ cần tìm cực tiểu một hàm là đủ. Việc tìm  cực đại của f(x) thực hiện một cách đơn giản bằng cách tìm cực tiểu của hàm  −f(x) . Hàm f là hàm giá trị hay hàm đối tượng, cần được giữ cực tiểu. Biến x  là biến có thể hiệu chỉnh tự do.    Các thuật toán cực tiểu hoá là các thủ thuật lặp đòi hỏi một giá trị ban  đầu của biến x. Nếu f(x) có nhiều cực tiểu địa phương, việc chọn giá trị đầu sẽ  xác định cực tiểu nào được tính. Ta không có cách nào bảo đảm là tìm được  cực tiểu toàn cục.    Các  biến  có  thể  bị  ràng  buộc  bằng  các  đẳng  thức  hay  bất  đẳng  thức.  Phần lớn các phương pháp là tìm cực tiểu không ràng buộc, nghĩa là không có  hạn chế nào đối với biến x. Các bài toán này bao gồm tìm cực tiểu của hàm,  tìm điểm tĩnh ‐ điểm có gradient triệt tiêu. Các bài toán tìm cực tiểu có ràng  buộc khó hơn và thuật toán khá phức tạp.     Trong chương này chúng ta sẽ lần lượt xét các thuật toán tìm cực tiểu  không ràng buộc và có ràng buộc.    §2. PHƯƠNG PHÁP TIẾT DIỆN VÀNG   Ta xét bài toán tìm cực tiểu của hàm một biến f(x). Điểm cực tiểu được  xác  định  theo  điều  kiện  df/dx  =  0.  Do  có  thể  có  nhiều  điểm  cực  tiểu  nên  ta  phải vây điểm cực tiểu(xác định lân cận chứa điểm cực tiểu) trước. Thủ thuật  vây điểm cực tiểu khá đơn giản: cho điểm đầu x0 và tính giá trị của hàm đang  đi  xuống  tại  các  điểm  tiếp  theo  x1,  x2,  x3,...  cho  đến  tại  xn  hàm  tăng  lại  thì  dừng. Điểm cực tiểu bị vây trong khoảng (xn‐2, xn). Khoảng (xi+1, xi) không nên  chọn là hằng số vì như vậy cần nhiều bước tính. Hợp lí nhất là nên tăng kích  thước bước tính để đạt được cực tiểu nhanh hơn, ngay cả khi cực tiểu bị vây  trong  một  đoạn  khá  rộng.  Ta  chọn  kích  thước  tăng  theo  dạng  hằng  số:  h i+1 = ch i với  c > 1 .  ta  xây  dựng  hàm  goldbracket()  để  vây  điểm  cực  tiểu  của  hàm:    function [a, b] = goldbracket(func, x1, h)  % vay diem cuc tieu cua f(x).  c = 1.618033989;  370
  2. f1 = feval(func, x1);  x2 = x1 + h;   f2 = feval(func,x2);  if f2 > f1      h = ‐h;      x2 = x1 + h;       f2 = feval(func, x2);      if f2 > f1          a = x2;           b = x1 ‐ h;           return      end  end  for i = 1:100      h = c*h;      x3 = x2 + h;       f3 = feval(func, x3);      if f3 > f2          a = x1;           b = x3;           return      end      x1 = x2;       f1 = f2;       x2 = x3;      f2 = f3;  end  error(ʹGoldbracket khong tim thay diem cuc tieuʹ)      Tiết diện vàng là một biến thể của phương pháp chia đôi dùng khi tìm  nghiệm của phương trình f(x) = 0. Giả sử điểm cực tiểu bị vây trong khoảng  (a,  b)  có  độ  dài  h.  Để  thu  nhỏ  khoảng  (a,  b)  ta  tính  giá  trị  của  hàm  tại  x1 = b − rh  và  x 2 = a + rh  như hình vẽ. Nếu f1 = f(x1) lớn hơn f2 = f(x2) như hình  a  thì  cực  tiểu  nằm  trong  khoảng  (x1,  b)  nếu  ngược  lại  cực  tiểu  nằm  trong  khoảng (a, x2).  371
  3.   Giả sử f1  > f2  , ta đặt a = x1 và và x1 =  x2 và có khoảng (a, b) mới như hình b. Để  2rh‐h  thực  hiện  bước  thu  gọn  tiếp  theo  ta  lại  rh  tính giá trị của hàm tại x2 = a + rh’ và lặp  rh  lại  quá  trình.  Quá  trình  làm  việc  chỉ  nếu  a x1  x2  b hình a và hình b tương tự,  nghĩa là hằng  h  số  r  không  đổi  khi  xác  định  x1  và  x2  ở  cả  hai hình. Từ hình a ta thấy:  a    x 2 − x1 = 2rh − h   Cùng một khoảng cách đó từ hình b ta có:  rh’    x1 ‐ a = h’ ‐ rh’  rh’  Cân bằng các khoảng này ta được:  a x1  x2  b   2rh ‐ h = h’ ‐ rh’  Thay h’ = rh và khử h:  h’    2r ‐ 1 = r(1 ‐ r)  b  Giải phương trình này ta nhận được tỉ lệ vàng:  5 −1   r= = 0.618033989...   2 Chú ý là mỗi lần thu gọn khoảng chứa điểm cực tiểu thì khoảng (a, b) giảm tỉ  lệ với r. Điều này làm số lần tính lớn hơn phương pháp chia đôi. Tuy nhiên  phương pháp tỉ lệ vàng chỉ đòi hỏi tính giá trị hàm một lần trong khi phương  pháp chia đôi cần tính giá trị hàm 2 lần. Số lần tính xác định bằng:    b − a rn = ε   ε ln b−a ε hay:  n = = −2.078087 n   ln b−a     h = b ‐ a = 0.382  Ta xây dựng hàm golden() để thực hiện thuật toán này:    function [xmin, ymin] = golden(f, a, b, delta, epsilon)  % a va b la doan tim cuc tieu  % delta sai so cua x  % epsilon sai so cua y  r1 = (sqrt(5) ‐ 1)/2;  r2 = r1^2;  h = b ‐ a;  372
  4. fa = f(a);  fb = f(b);  x1 = a + r2*h;  x2 = a + r1*h;  f1 = f(x1);  f2 = f(x2);  k = 1;  while (abs(fb‐fa) > epsilon)|(h > delta)     k = k + 1;     if (f1 
  5. ymin = yp;    Để tìm cực tiểu của hàm ta dùng chương trình ctgolden.m:    clear all, clc  f = inline(ʹ1.6*x^3 + 3*x^2 ‐2*xʹ);  x = 0;   delta = 1e‐8;  epsilon = 1e‐10;  [a, b] = goldbracket(f, x, 0.2);  [xmin, ymin] = golden(f, a, b, delta, epsilon)    §3. PHƯƠNG PHÁP XẤP XỈ BẬC HAI    Ý tưởng của phương pháp này là:    ‐  xấp  xỉ  hàm  đối  tượng  f(x)  bằng  một  hàm  bậc  2  p2(x)  qua  3  điểm  cho  trước    ‐  cập  nhật  3  điểm  này  bằng  cách  thay  một  trong  3  điểm  bằng  cực  tiểu  của hàm p2(x)    Qua 3 điểm:   {[(x0 ,f(x0 )] , [(x1 ,f(x1 )] , [(x2 ,f(x2 )]}   x0 
  6.   Ta xây dựng hàm optquad() để thực hiện thuật toán này.    function [xo, fo] = optquad(f, x0, tolx, tolfun, maxiter)  %Tim cuc tieu cua f(x) bang phuong phap xap xi bac 2  if length(x0) > 2      x012 = x0(1:3);  else      if length(x0) == 2          a = x0(1);           b = x0(2);      else           a = x0 ‐ 10;           b = x0 + 10;      end      x012 = [a (a + b)/2  b];  end  f012 = f(x012);  [xo, fo] = optquad0(f, x012, f012, tolx, tolfun, maxiter);    function [xo, fo] = optquad0(f, x012, f012, tolx, tolfun, k)  x0 = x012(1);   x1 = x012(2);   x2 = x012(3);  375
  7. f0 = f012(1);   f1 = f012(2);   f2 = f012(3);  nd = [f0 ‐ f2 f1 ‐ f0 f2 ‐ f1]*[x1*x1 x2*x2 x0*x0; x1 x2 x0]ʹ;  x3 = nd(1)/2/nd(2);   f3 = feval(f, x3); %Pt.(1)  if k 
  8. %f = inline(ʹ(x.^2 ‐ 4).^2/8 ‐ 1ʹ);  a = 0;   b = 3;  delta = 1e‐8;  epsilon = 1e‐10;  maxiter = 100;  [xmin, ymin] = optquad(f, [a  b], delta, epsilon, maxiter)    §4. PHƯƠNG PHÁP NELDER ‐ MEAD    Phương pháp Nelder ‐ Mead có thể dùng để tìm cực tiểu của hàm nhiều  biến  mà  phương  pháp  tiết  diện  vàng  hay  phương  pháp  xấp  xỉ  bậc  2  không  dùng được. Thuật toán Nelder ‐ Mead gồm các bước như sau:  Bước 1: Cho 3 điểm đầu tiên a, b, c với f(a) 
  9. if n == 1 %truong hop ham 1 bien      [xo,fo] = optquad(f, x0, tolx, tolfun);       return  end  S = eye(n);  for i = 1:n       i1 = i + 1;       if i1 > n          i1 = 1;       end      abc = [x0; x0 + S(i,:); x0 + S(i1,:)];       fabc = [feval(f, abc(1, :)); feval(f,abc(2, :)); feval(f,abc(3, :))];      [x0, fo] = neldermead0(f, abc, fabc, tolx, tolfun, maxiter);      if n 
  10.     m = (a + b)/2;       e = 3*m ‐ 2*c;       fe = feval(f, e);      if fe 
  11. b = 1;  delta = 1e‐8;  epsilon = 1e‐10;  maxiter = 100;  [xmin, ymin] = neldermead(f, x0, delta, epsilon, maxiter)    §5. PHƯƠNG PHÁP ĐỘ DỐC LỚN NHẤT    Phương  pháp  này  tìm  điểm  cực  tiểu  của  hàm  n  biến  theo  hướng  gradient âm:  ⎡ ∂f(x) ∂f(x) ∂f(x) ⎤   −g([ x ]) = −∇f([ x ]) = − ⎢ L   ⎣ ∂x1 ∂x 2 ∂x n ⎥ ⎦ với kích thước bước tính αk tại lần lặp thứ k được hiệu chỉnh sao cho giá trị  hàm cực tiểu theo hướng tìm. Thuật toán gồm các bước sau:    • Tại lần lặp thứ k = 0, tìm giá trị hàm f(x0) với điểm khởi đầu x0  • Tại lần lặp thứ k, tìm αk theo hướng ‐g(x)    α k −1 = f ( x k−1 − αg k−1 / g k−1 )             (1)  • Tính giá trị xk:    x k = x k −1 − α k −1g k−1 / g k−1             (2)  • Nếu xk  ≈ xk‐1 và f(xk)  ≈ f(xk‐1) thì coi là cực tiểu, nếu không thì quay về  bước 2.      function [xo, fo] = steepest(f, x0, tolx, tolfun, alpha0,maxiter)  if nargin 
  12. fx0 = feval(f, x0);   fx = fx0;  alpha = alpha0;   kmax1 = 25;  warning = 0;   for k = 1:maxiter      g = grad(f, x);       g = g/norm(g); %gradient la vec to hang      alpha = alpha*2; %de thu di theo huong gradient am      fx1 = feval(f, x ‐ alpha*2*g);      for k1 = 1:kmax1 %tim buoc toi uu          fx2 = fx1;        fx1 = feval(f, x ‐ alpha*g);          if fx0 > fx1+ tolfun & fx1  fx1 = kmax1          warning = warning + 1; %kg tim duoc buoc toi uu      else           warning = 0;      end      if warning >= 2|(norm(x ‐ x0) 
  13. if k ==maxiter      fprintf(ʹDay la ket qua tot nhat sau  %d lan lapʹ, maxiter)  end    function g = grad(func, x)  % Tinh gradient cua ham f(x).  h = 1.0e‐6;  n = length(x);  g = zeros(1, n);  f0 = feval(func, x);  for i = 1:n      temp = x(i);      x(i) = temp + h;      f1 = feval(func, x);      x(i) = temp;      g(1, i) = (f1 ‐ f0)/h;  end    Để tìm cực tiểu của hàm ta dùng chương trình ctsteepest.m:    clear all, clc  f = inline(ʹx(1)*x(1) ‐ x(1)*x(2) ‐ 4*x(1) + x(2) *x(2) ‐ x(2)ʹ);  x0 = [0.5  0.5];  tolx = 1e‐4;   tolfun = 1e‐9;   alpha0 = 1;   maxiter = 100;  [xo, fo] = steepest(f, x0, tolx, tolfun, alpha0, maxiter)    §6. PHƯƠNG PHÁP NEWTON    Việc tìm điểm cực tiểu của hàm f(x) tương đương với việc xác định x để  cho gradient g(x) của hàm f(x) bằng zero. Nghiệm của g(x) = 0 có thể tìm được  bằng cách dùng phương pháp Newton cho hệ phương trình phi tuyến. Hàm  newtons(x) dùng để tìm nghiệm của phương trình g(x) = 0 là:    function [x, fx, xx] = newtons(f, x0, tolx, maxiter)  382
  14. h = 1e‐4;   tolfun = eps;   EPS = 1e‐6;  fx = feval(f, x0);  nf = length(fx);   nx = length(x0);  if nf ~= nx      error(ʹKich thuoc cua g va x0 khong tuong thich!ʹ);   end  if nargin 
  15. x = x(:).ʹ;   I = eye(n);  for n = 1:n      g(:, n) = (feval(f, x + I(n, :)*h) ‐ feval(f, x ‐ I(n,:)*h))ʹ/h2;  end    Để tìm cực tiểu của hàm bằng phương pháp Newtons ta dùng chương trình  ctnewtons.m:    clear all, clc  f = inline(ʹx(1).^2 ‐ x(1)*x(2) ‐ 4*x(1) + x(2).^2 ‐ x(2)ʹ);  g = inline(ʹ[(2*x(1) ‐ x(2) ‐4)  ( 2*x(2) ‐ x(1) ‐ 1)]ʹ);  x0 = [0.1  0.1];  tolx = 1e‐4;   maxiter = 100;  [xo, fo] = newtons(g, x0, tolx, maxiter)    §7. PHƯƠNG PHÁP GRADIENT LIÊN HỢP  1. Khái niệm chung: Một trong các phương pháp giải bài tón tìm cực tiểu của  hàm nhiều biến là tìm cực  tiểu theo một biến liên tiếp để đến gần điểm cực  tiểu. Chiến thuật chung là:    • chọn điểm [x0]  • lặp với i = 1, 2, 3,...    ‐ chọn vec tơ [vi]  ‐ cực tiểu hoá f([x]) dọc theo đường [xi‐1] theo hướng [vi]. Coi [xi]   là cực tiểu. Nếu  [ xi ] − [ xi−1 ] < ε  thì kết thúc lặp  • kết thúc   2. Gradient liên hợp: Ta khảo sát hàm bậc 2:  1 1 T f ([ x ]) = c − ∑ bi xi + ∑∑ A i ,jxi x j = c − [ b] [ x ] + [ x ] [ A ][ x ]   T   (1)  i 2 i j 2 đạo hàm của hàm theo xi cho ta:  ∂f   = − bi + ∑ A i ,jx j   ∂x i j Viết dưới dạng vec tơ ta có:    ∇f = − [ b ] + [ A ][ x ]                 (2)  384
  16. với ∇f là gradient của f.    Bây  giờ  ta  khảo  sát  sự  thay  đổi  gradient  khi  ta  di  chuyển  từ  [x0]  theo  hướng của vec tơ [u] dọc theo đường:    [x] = [x0] + s[u]  với s là khoảng cách di chuyển. Thay biểu thức này vào (2) ta có gradient dọc  theo [u]:      ∇f [x0 ]+s[u] = − [ b ] + [ A ] ([ x0 ] + s [ u ]) = ∇f [x0 ] + s [ A ][ u ]   Như vậy sự thay đổi gradient là s[A][u]. Nếu ta di chuyển theo hướng vuông  góc với vec tơ [v], nghĩa là   [v]T[u] = 0 hay [v]T[A][u] = 0              (3)  thì hướng của [u] và [v] là liên hợp. Điều này cho thấy khi ta muốn cực tiểu  hoá f(x) theo hướng [v], ta cần di chuyển theo hướng [u] để không làm hỏng  cực tiểu trước đó. Với hàm bậc hai n biến độc lập ta có thể xây dựng n hướng  liên  hợp.  Các  phương  pháp  gradient  liên  hợp  khác  nhau  dùng  các  kỹ  thuật  khác nhau để tìm hướng liên hợp.  3. Phương pháp Powell: Phương pháp Powell là phương pháp bậc zero, chỉ  đòi hỏi tính f([x]). Thuật toán gồm các bước:    • chọn điểm [x0]  •  chọn  vec  tơ  [vi],  thường  lấy  [vi]  =  [ei]  với  [ei]  là  vec  tơ  đơn  vị  theo  hướng [xi]  • vòng tròn    ‐ lặp với i = 1, 2,...  ∗  tìm  cực  tiểu  của  f([x])  dọc  theo  đường  đi  qua  [xi‐1]  theo  hướng [vi]; coi [xi] là cực tiểu       ‐ kết thúc lặp  ‐ [vn+1] = [x0] ‐ [xn]; tìm cực tiểu của f([x]) dọc theo đường đi qua[x0]  theo hướng [vn+1]; coi [xn+1] là cực tiểu  ‐ nếu  [ x n +1 ] − [ x n ] < ε  thì kết thúc vòng lặp    ‐ lặp  ∗ [vi+1] = [v]    • kết thúc vòng tròn  Ta xây dựng hàm powell() để thực hiện thuật toán trên:    function [xmin, fmin, ncyc] = powell(h, tol)  % Phuong phap Powell de tim cuc tieu cua ham f(x1,x2,...,xn).  385
  17. global x func v  if nargin 
  18.             imax = i;               dfmax = df(i);          end      end      for i = imax:n‐1          u(1:n, i) = u(1:n, i+1);      end      u(1:n, n) = v;      end  error(ʹPhuong phap Powell khong hoi tuʹ)    function z = fiine(s) % f theo huong cua v  global x func v  z = feval(func, x+s*v);      function y = f(x)  y = 100.0*(x(2) ‐ x(1).^2).^2 + (1.0 ‐ x(1)).^2;    Để tìm điểm cực tiểu ta dùng chương trình ctpowell.m:    clear all, clc  global x  func   func = @f;  x = [‐1.0; 1.0];  [xmin, fmin, numcycles] = powell  fminsearch(func, x)    3. Phương pháp Fletcher ‐ Reeves: Phương pháp Powell cần n đường cực tiểu  hoá. Ta có thể chỉ cần dùng một đường với phương pháp bậc 1. Phương pháp  này  có  2  phương  án:  thuật  toán  Fletcher  ‐  Reeves(FR)  và  thuật  toán  Polak  ‐  Ribiere(PR). Thuật toán tóm tắt như sau:    ‐ cho [x0], tính f([x0])     ‐ khởi gán x(n) = xk; tính [g0] = ‐∇f([x0]); s(k) = ‐ g(xk)   ‐ lặp k = 0, 1, 2,...    • [xk+1] = [xk] + αk[sk]   387
  19.   •  βk = ([g k +1 ] −[g k ] )[g k+1 ] T T (FR)  hay  βk = [g k+1 ] [g k+1 ] (PR)   T [g k ] [g k ] [g k ] [g k ] T T   •  [ s k+1 ] = − [g k +1 ] + βk [ s k ]     • cập nhật [xk]   cho đến khi hội tụ  Ta xây dựng hàm conjugate() để thực hiện thuật toán trên:    function [xo, fo] = conjugate(f, x0, tolx, tolfun, alpha0, maxiter, KC)  %KC = 1:  Phuong phap gradient lien hop Polak–Ribiere  %KC = 2: Phuong phap gradient lien hop Fletcher–Reeves   if nargin 
  20.     alpha = alpha0;      g = grad(f, x);       s = ‐g;      for n = 1:n          alpha = alpha0;          fx1 = feval(f, x + alpha*2*s);           for n1 = 1:nmax1               fx2 = fx1;               fx1 = feval(f, x+alpha*s);              if (fx0 > fx1 + tolfun) & ( fx1  fx1 
Đồng bộ tài khoản