Giới hạn mô-đun tối ưu hóa Mathematica

Question

Tôi có một câu hỏi liên quan đến khả năng tối ưu hóa toàn cầu của Mathematica. Tôi đi qua văn bản này liên quan đến hộp công cụ NAG (kind of white paper).

Bây giờ tôi đã cố gắng giải quyết vỏ thử nghiệm từ giấy. Đúng như dự đoán, Mathematica khá nhanh trong việc giải quyết nó.

n=2; 
fun[x_,y_]:=10 n+(x-2)^2-10Cos[2 Pi(x-2)]+(y-2)^2-10 Cos[2 Pi(y-2)]; 
NMinimize[{fun[x,y],-5<= x<= 5&&-5<= y<= 5},{x,y},Method->{"RandomSearch","SearchPoints"->13}]//AbsoluteTiming 

Output là

{0.0470026,{0.,{x->2.,y->2.}}} 

Người ta có thể nhìn thấy những điểm viếng thăm bởi những thói quen tối ưu hóa.

{sol, pts}=Reap[NMinimize[{fun[x,y],-5<= x<= 5&&-5<= y<= 5},{x,y},Method->`{"RandomSearch","SearchPoints"->13},EvaluationMonitor:>Sow[{x,y}]]];Show[ContourPlot[fun[x,y],{x,-5.5,5.5},{y,-5.5,5.5},ColorFunction->"TemperatureMap",Contours->Function[{min,max},Range[min,max,5]],ContourLines->True,PlotRange-> All],ListPlot[pts,Frame-> True,Axes-> False,PlotRange-> All,PlotStyle-> Directive[Red,Opacity[.5],PointSize[Large]]],Graphics[Map[{Black,Opacity[.7],Arrowheads[.026],Arrow[#]}&,Partition[pts//First,2,1]],PlotRange-> {{-5.5,5.5},{-5.5,5.5}}]]` 

Bây giờ tôi nghĩ đến việc giải quyết cùng một vấn đề về chiều cao. Đối với các vấn đề của năm biến mathematica bắt đầu rơi vào bẫy của tối thiểu địa phương ngay cả khi số lượng lớn các điểm tìm kiếm được cho phép.

n=5;funList[x_?ListQ]:=Block[{i,symval,rule}, 
i=Table[ToExpression["x$"<>ToString[j]],{j,1,n}];symval=10 n+Sum[(i[[k]]-2)^2-10Cos[2Pi(i[[k]]-2)],{k,1,n}];rule=MapThread[(#1-> #2)&,{i,x}];symval/.rule]val=Table[RandomReal[{-5,5}],{i,1,n}];vars=Table[ToExpression["x$"<>ToString[j]],{j,1,n}];cons=Table[-5<=ToExpression["x$"<>ToString[j]]<= 5,{j,1,n}]/.List-> And;NMinimize[{funList[vars],cons},vars,Method->{"RandomSearch","SearchPoints"->4013}]//AbsoluteTiming 

Đầu ra không phải là những gì chúng tôi muốn xem. Mất 49 giây trong máy core2duo của tôi và nó vẫn là tối thiểu địa phương.

{48.5157750,{1.98992,{x$1->2.,x$2->2.,x$3->2.,x$4->2.99496,x$5->1.00504}}} 

Sau đó thử SimulatedAnealing với 100000 lần lặp lại.

NMinimize[{funList[vars],cons},vars,Method->"SimulatedAnnealing",MaxIterations->100000]//AbsoluteTiming 

Đầu ra vẫn không dễ chịu.

{111.0733530,{0.994959,{x$1->2.,x$2->2.99496,x$3->2.,x$4->2.,x$5->2.}}} 

Bây giờ Mathematica có thuật toán tối ưu hóa chính xác được gọi là Thu nhỏ. Mà như mong đợi phải thất bại trên thực tế nhưng nó không thành công rất nhanh khi kích thước vấn đề tăng lên.

n=3;funList[x_?ListQ]:=Block[{i,symval,rule},i=Table[ToExpression["x$"<>ToString[j]],{j,1,n}];symval=10 n+Sum[(i[[k]]-2)^2-10Cos[2 Pi(i[[k]]-2)],{k,1,n}];rule=MapThread[(#1-> #2)&,{i,x}];symval/.rule]val=Table[RandomReal[{-5,5}],{i,1,n}];vars=Table[ToExpression["x$"<>ToString[j]],{j,1,n}];cons=Table[-5<=ToExpression["x$"<>ToString[j]]<= 5,{j,1,n}]/.List-> And;Minimize[{funList[vars],cons},vars]//AbsoluteTiming 

đầu ra hoàn toàn ổn.

{5.3593065,{0,{x$1->2,x$2->2,x$3->2}}} 

Nhưng nếu thay đổi kích thước bài toán thêm một bước với n = 4 bạn sẽ thấy kết quả. Giải pháp không xuất hiện trong thời gian dài trong sổ ghi chép của tôi.

Bây giờ câu hỏi đơn giản có ai ở đây nghĩ rằng có một cách để numerically giải quyết vấn đề này một cách hiệu quả trong Mathematica cho các trường hợp chiều cao hơn? Cho phép chia sẻ ý tưởng và kinh nghiệm của chúng tôi. Tuy nhiên người ta nên nhớ rằng nó là một vấn đề tối ưu hóa phi tuyến toàn cầu chuẩn. Hầu hết các thuật toán tìm kiếm/giảm thiểu gốc số thường tìm kiếm số tối thiểu cục bộ.

BR

P

Answer 1

Tăng điểm ban đầu cho phép tôi để có được cực tiểu toàn cục:

n = 5; 

funList[x_?ListQ] := Total[10 + (x - 2)^2 - 10 Cos[2 Pi (x - 2)]] 

val = Table[RandomReal[{-5, 5}], {i, 1, n}]; 
vars = Array[Symbol["x$" <> ToString[#]] &, n]; 
cons = Apply[And, Thread[-5 <= vars <= 5]]; 

Đây là những cuộc gọi. Tuy nhiên, thời gian có thể không quá hiệu quả, nhưng với các thuật toán ngẫu nhiên, một thuật toán phải có đủ các mẫu ban đầu, hoặc một cảm giác tốt cho hàm.

In[27]:= NMinimize[{funList[vars], cons}, vars, 
    Method -> {"DifferentialEvolution", 
    "SearchPoints" -> 5^5}] // AbsoluteTiming 

Out[27]= {177.7857768, {0., {x$1 -> 2., x$2 -> 2., x$3 -> 2., 
    x$4 -> 2., x$5 -> 2.}}} 

In[29]:= NMinimize[{funList[vars], cons}, vars, 
    Method -> {"RandomSearch", "SearchPoints" -> 7^5}] // AbsoluteTiming 

Out[29]= {609.3419281, {0., {x$1 -> 2., x$2 -> 2., x$3 -> 2., 
    x$4 -> 2., x$5 -> 2.}}} 

Answer 2

Bạn đã thấy this page của tài liệu? Nó đi qua các phương thức được hỗ trợ bởi NMinimize, với các ví dụ cho mỗi. Một trong những ví dụ SimulatedAnnealing là chức năng của Rastgrin (hoặc một cái rất giống nhau), và các tài liệu gợi ý rằng bạn cần tăng kích thước nhiễu loạn để có được kết quả tốt.