Giảm thiểu f (x, y) trong đó x và y là số nguyên

Question

Tôi đã tự hỏi nếu có ai có bất kỳ đề xuất nào để giảm thiểu hàm, f (x, y), trong đó x và y là số nguyên. Tôi đã nghiên cứu rất nhiều kỹ thuật tối ưu hóa và tối ưu hóa, như BFGS và các kỹ thuật khác trong GSL, và những thứ trong số Công thức số. Cho đến nay, tôi đã thử implenting một vài đề án khác nhau. Các công trình đầu tiên bằng cách chọn hướng lớn nhất f (x + 1, y), f (x-1, y), f (x, y + 1), f (x, y-1), và làm theo hướng đó với giảm thiểu dòng. Tôi cũng đã thử sử dụng phương thức downhill simplex (Nelder-Mead). Cả hai phương pháp đều bị kẹt ở mức tối thiểu. Cả hai đều xuất hiện để làm việc trên các chức năng đơn giản, như tìm tối thiểu paraboloid, nhưng tôi nghĩ rằng cả hai, và đặc biệt là trước đây, được thiết kế cho các chức năng trong đó x và y có giá trị thực (tăng gấp đôi). Một vấn đề nữa là tôi cần gọi f (x, y) càng ít lần càng tốt. Nó nói chuyện với phần cứng bên ngoài, và mất một vài giây cho mỗi cuộc gọi. Bất kỳ ý tưởng cho điều này sẽ được đánh giá rất nhiều.

Dưới đây là ví dụ về chức năng lỗi. Xin lỗi tôi đã không đăng bài này trước đây. Hàm này mất một vài giây để đánh giá. Ngoài ra, thông tin chúng tôi truy vấn từ thiết bị không thêm vào lỗi nếu nó thấp hơn giá trị mong muốn của chúng tôi, chỉ khi nó ở trên

double Error(x,y) 
{ 
    SetDeviceParams(x,y); 
    double a = QueryParamA(); 
    double b = QueryParamB(); 
    double c = QueryParamC(); 
    double _fReturnable = 0; 
    if(a>=A_desired) 
    { 
    _fReturnable+=(A_desired-a)*(A_desired-a); 
    } 
    if(b>=B_desired) 
    { 
    _fReturnable+=(B_desired-b)*(B_desired-b); 
    } 
    if(c>=C_desired) 
    { 
    _fReturnable+=(C_desired-c)*(C_desired-c); 
    } 
    return Math.sqrt(_fReturnable) 
} 

Answer 1

Làm thế nào để bạn xác định f (x, y)? Giảm thiểu là một vấn đề khó, tùy thuộc vào độ phức tạp của chức năng của bạn.

Thuật toán di truyền có thể là một ứng cử viên tốt.

Resources:

Genetic Algorithms in Search, Optimization, and Machine Learning

Implementing a Genetic Algorithms in C#

Simple C# GA

Answer 2

Bạn đã xem thuật toán di truyền chưa? Họ rất, rất giỏi trong việc tìm kiếm tối thiểu và tối đa, trong khi tránh tối thiểu/tối đa địa phương.

Answer 3

Nếu đó là một chức năng tùy ý, không có cách nào để thực hiện việc này một cách gọn gàng.

Giả sử chúng ta có một chức năng được xác định như sau:

f(x, y) = 0 for x==100, y==100 
      100 otherwise 

Làm thế nào có thể bất kỳ thuật toán thực tế tìm (100, 100) là tối thiểu? Nó có thể là bất kỳ sự kết hợp nào của các giá trị.

Bạn có biết bất kỳ điều gì về chức năng bạn đang thử nghiệm không?

Answer 4

Có rất nhiều, rất nhiều giải pháp ở đây. Trong thực tế, có toàn bộ sách và môn học dựa trên chủ đề. Tôi đang đọc một tài liệu xuất sắc ngay bây giờ: How to Solve It: Modern Heuristics.

Không có giải pháp nào đúng - các giải pháp khác nhau có những ưu điểm khác nhau dựa trên kiến ​​thức cụ thể về chức năng của bạn. Nó thậm chí đã được chứng minh rằng không có một heuristic mà thực hiện tốt nhất ở tất cả các nhiệm vụ tối ưu hóa.

Nếu bạn biết rằng hàm của bạn là bậc hai, bạn có thể sử dụng Newton-Gauss để tìm số tiền tối thiểu trong một bước. Một thuật toán di truyền có thể là một công cụ đa năng tuyệt vời, hoặc bạn có thể thử ủ mô phỏng, ít phức tạp hơn.

Answer 5

Điều bạn thường tìm kiếm được gọi là optimisation technique trong toán học.Nói chung, chúng áp dụng cho các hàm có giá trị thực, nhưng nhiều hàm có thể được điều chỉnh cho các hàm có giá trị tích phân.

Cụ thể, tôi khuyên bạn nên xem xét non-linear programming và gradient descent. Cả hai sẽ có vẻ khá thích hợp cho ứng dụng của bạn.

Nếu bạn có thể cung cấp thêm bất kỳ chi tiết nào, tôi có thể đề xuất một chút cụ thể hơn một chút.

Answer 6

Câu trả lời của Jon Skeet là chính xác. Bạn thực sự cần thông tin về f và dẫn xuất của nó ngay cả khi f là ở khắp mọi nơi liên tục. Cách dễ nhất để đánh giá cao những khó khăn của những gì bạn yêu cầu (chỉ giảm thiểu f ở các giá trị số nguyên) chỉ là suy nghĩ về một hàm f: R-> R (f là một hàm thực giá trị thực của một biến). làm cho chuyến du ngoạn lớn giữa các số nguyên riêng lẻ. Bạn có thể dễ dàng xây dựng một hàm như vậy để KHÔNG có sự sửa đổi giữa các mức tối thiểu cục bộ trên đường thực và mức tối thiểu ở các số nguyên cũng như không có mối quan hệ với đạo hàm đầu tiên.

Đối với một chức năng tùy ý, tôi không thấy cách nào ngoại trừ sức mạnh vũ phu.

Answer 7

Rất tiếc, định dạng này quá tệ trước đó. Dưới đây là ví dụ về hàm lỗi

double Error(x,y) 
{ 
SetDeviceParams(x,y); 
double a = QueryParamA(); 
double b = QueryParamB(); 
double c = QueryParamC(); 
double _fReturnable = 0; 
if(a>=A_desired) 
{ 
    _fReturnable+=(A_desired-a)*(A_desired-a); 
} 
if(b>=B_desired) 
{ 
_fReturnable+=(B_desired-b)*(B_desired-b); 
} 
if(c>=C_desired) 
{ 
    _fReturnable+=(C_desired-c)*(C_desired-c); 
} 
return Math.sqrt(_fReturnable) 
} 

Answer 8

Vì vậy, hãy xem xét vấn đề của bạn khi nói toán. Đây là tất cả giả sử tôi hiểu hoàn toàn về vấn đề của bạn . Vui lòng sửa tôi nếu tôi nhầm.

chúng tôi muốn giảm thiểu sau đây:

\ sqrt ((a-a_desired)^2 + (b-b_desired)^2 + (c-c_desired)^2)

hoặc trong ký hiệu khác || Pos (x - x_desired) || _2

trong đó x = (a, b, c) và Pos (y) = max (y, 0) có nghĩa là chúng tôi muốn "phần dương" (tài khoản này cho các câu lệnh if của bạn). Cuối cùng, chúng tôi muốn hạn chế chính mình đến các giải pháp trong đó x là số nguyên có giá trị.

Không giống như các áp phích trên, tôi không nghĩ rằng thuật toán di truyền là những gì bạn muốn.
Thực tế, tôi nghĩ giải pháp dễ dàng hơn nhiều (giả sử tôi hiểu vấn đề của bạn).

1) Chạy bất kỳ thường trình tối ưu hóa nào trên hàm ở trên. Điều này sẽ cung cấp cho bạn giải pháp x^* = (a^*, b^*, c^*). Khi hàm này tăng lên với các tham số cho các biến, giải pháp số nguyên tốt nhất bạn có thể hy vọng là (ceil (a^*), ceil (b^*), ceil (c^*)).

Bây giờ bạn nói rằng chức năng của bạn có thể khó đánh giá. Có tồn tại các công cụ cho điều này không dựa trên chẩn đoán. Việc đi theo tên Derivative-Free Tối ưu hóa. Mọi người sử dụng những công cụ này để tối ưu hóa mục tiêu dựa trên mô phỏng (tôi có thậm chí còn nghe về một trường hợp mà chức năng mục tiêu dựa trên sản lượng thu hoạch cây trồng!)

Mỗi phương pháp này có các tính chất khác nhau, nhưng nói chung họ cố gắng giảm thiểu không chỉ mục tiêu mà còn là số lượng đánh giá chức năng khách quan.