Tối ưu hóa nhiều thông số với nhiều minima địa phương

Question

Tôi đang tìm các thuật toán để tìm một tập hợp các giá trị tham số "tốt nhất". Hàm trong câu hỏi có rất nhiều minima địa phương và thay đổi rất nhanh. Để làm cho vấn đề thậm chí còn tồi tệ hơn, việc kiểm tra một tập hợp các tham số là rất chậm - theo thứ tự 1 phút - và tôi không thể tính toán gradient trực tiếp.

Có bất kỳ thuật toán nổi tiếng nào cho loại tối ưu hóa này không?

Tôi đã đạt được thành công vừa phải chỉ bằng cách thử các giá trị ngẫu nhiên. Tôi tự hỏi nếu tôi có thể cải thiện hiệu suất bằng cách làm cho lựa chọn tham số ngẫu nhiên có cơ hội thấp hơn để chọn các thông số gần với những thông số đã tạo ra kết quả xấu trong quá khứ. Có tên cho phương pháp này để tôi có thể tìm kiếm lời khuyên cụ thể không?

Thông tin thêm:

• thông số là liên tục
• Có vào thứ tự của 5-10 tham số. Chắc chắn không quá 10.

Answer 1

Tôi đã thử mô phỏng luyện kim và tối ưu bầy đàn. (Như một lời nhắc nhở, tôi không thể sử dụng gradient descent vì gradient không thể được tính toán).

Tôi cũng đã thử một thuật toán nào sau đây:

• Chọn một điểm ngẫu nhiên và một hướng ngẫu nhiên
• Đánh giá chức năng
• Giữ di chuyển theo hướng ngẫu nhiên cho miễn là kết quả tiếp tục cải thiện, tăng tốc trên mọi lần lặp thành công.
• Khi kết quả ngừng cải thiện, hãy lùi lại và thay vào đó cố gắng di chuyển sang hướng trực giao bằng cùng khoảng cách.

này "trực giao hướng" được tạo ra bằng cách tạo ra một ma trận trực giao ngẫu nhiên (chuyển thể this code) với số lượng cần thiết của kích thước.

Nếu di chuyển theo hướng trực giao đã cải thiện kết quả, thuật toán chỉ tiếp tục theo hướng đó. Nếu không có hướng nào cải thiện kết quả, khoảng cách nhảy được giảm đi một nửa và một tập hợp các hướng trực giao mới sẽ được thử. Cuối cùng thuật toán kết luận nó phải ở mức tối thiểu cục bộ, nhớ nó và khởi động lại toàn bộ lô tại một điểm ngẫu nhiên mới.

Cách tiếp cận này thực hiện tốt hơn đáng kể so với mô phỏng ủ và hạt Part Swarm: nó yêu cầu đánh giá ít hơn (rất chậm) chức năng để đạt được kết quả của cùng một chất lượng.

Tất nhiên, việc triển khai S.A. và P.S.O. cũng có thể thiếu sót - đây là những thuật toán phức tạp với rất nhiều chỗ cho các thông số tinh chỉnh. Nhưng tôi chỉ nghĩ rằng tôi muốn đề cập đến những gì đã kết thúc tốt nhất cho tôi.

Answer 2

Tôi thực sự không thể giúp bạn tìm được thuật toán cho vấn đề cụ thể của bạn.

Tuy nhiên liên quan đến việc chọn ngẫu nhiên các thông số, tôi nghĩ rằng những gì bạn đang tìm kiếm là genetic algorithms. Các thuật toán di truyền nói chung dựa trên việc lựa chọn một số đầu vào ngẫu nhiên, chọn những cái phù hợp nhất (cho đến nay) cho vấn đề và ngẫu nhiên biến đổi/kết hợp chúng để tạo ra một thế hệ tiếp theo.

Nếu hàm ít nhiều liên tục (đó là đột biến nhỏ của đầu vào tốt thường sẽ không tạo ra đầu vào xấu (nhỏ là hơi chung chung)), điều này sẽ làm việc tốt cho vấn đề của bạn.

Answer 3

Có bao nhiêu tham số - ví dụ: có bao nhiêu thứ nguyên trong không gian tìm kiếm? Chúng liên tục hay rời rạc - ví dụ, số thực, hoặc số nguyên, hay chỉ là một vài giá trị có thể?

Phương pháp tiếp cận mà tôi đã thấy được sử dụng cho các loại vấn đề này có cấu trúc tổng thể tương tự - lấy một số lượng lớn các điểm mẫu và điều chỉnh tất cả các vùng có câu trả lời "tốt". Vì bạn có rất nhiều điểm, sự khác biệt tương đối của chúng phục vụ như là một gradient tạm thời.

• Simulated Annealing: Cách tiếp cận cổ điển. Mất một loạt các điểm, probabalistically di chuyển một số đến một điểm lân cận được chọn tại một cách ngẫu nhiên tùy thuộc vào nó tốt hơn nhiều.
• Particle Swarm Optimization: Lấy một "bầy" các hạt có vận tốc trong không gian tìm kiếm, ngẫu nhiên ngẫu nhiên di chuyển một hạt; nếu đó là một sự cải tiến, hãy để toàn bộ đàn biết.
• Genetic Algorithms: Điều này hơi khác một chút. Thay vì sử dụng các thông tin hàng xóm như trên, bạn sẽ có kết quả tốt nhất mỗi lần và "lai tạo" họ hy vọng sẽ có được những đặc điểm tốt nhất của mỗi loại.

Liên kết wikipedia có mã giả cho hai đầu tiên; Các phương thức GA có rất nhiều sự khác nhau nên thật khó để liệt kê chỉ một thuật toán, nhưng bạn có thể theo các liên kết từ đó. Lưu ý rằng có các triển khai cho tất cả các điều trên mà bạn có thể sử dụng hoặc lấy làm điểm bắt đầu.

Lưu ý rằng tất cả những điều này - và thực sự là bất kỳ cách tiếp cận nào với thuật toán tìm kiếm chiều rộng này - đều là phỏng đoán, có nghĩa là chúng có các thông số cần được điều chỉnh theo vấn đề cụ thể của bạn. Mà có thể được tẻ nhạt.

Nhân tiện, việc đánh giá chức năng quá tốn kém có thể được thực hiện để làm việc cho bạn một chút; vì tất cả các phương pháp trên liên quan đến nhiều đánh giá chức năng độc lập, đoạn thuật toán đó có thể song song với OpenMP hoặc một cái gì đó tương tự như sử dụng nhiều lõi như bạn có trên máy của mình.

Answer 4

Tình huống của bạn có vẻ tương tự như áp phích Software to Tune/Calibrate Properties for Heuristic Algorithms và tôi sẽ cung cấp cho bạn lời khuyên tương tự I gave there: xem xét Metropolis-Hastings như cách tiếp cận với nhiều người đi bộ và mô phỏng các kích thước bước.

Khó khăn trong việc sử dụng phương pháp Monte Carlo trong trường hợp của bạn là đánh giá tốn kém của từng ứng cử viên. Làm thế nào đắt tiền, so với thời gian bạn có trong tầm tay? Nếu bạn cần một câu trả lời tốt trong một vài phút, điều này sẽ không đủ nhanh. Nếu bạn có thể để nó chạy qua đêm, nó sẽ hoạt động khá tốt.

Với không gian tìm kiếm phức tạp, tôi khuyên bạn nên phân phối ngẫu nhiên ban đầu. Câu trả lời cuối cùng của bạn có thể đơn giản là kết quả cá nhân tốt nhất được ghi lại trong suốt quá trình chạy, hoặc vị trí trung bình của khung tập đi với kết quả tốt nhất.

Không được đưa ra rằng tôi đã thảo luận về việc tối đa hóa ở đó và bạn muốn giảm thiểu: con số của công đức có thể được phủ nhận hoặc đảo ngược.

Answer 5

Không có cách tổng quát để trả lời câu hỏi của bạn. Có rất nhiều sách/giấy tờ về vấn đề này, nhưng bạn sẽ phải chọn con đường của bạn theo nhu cầu của bạn, mà không được nói rõ ở đây.

Một số điều cần biết, tuy nhiên - 1 phút/thử nghiệm là quá nhiều đối với bất kỳ thuật toán nào để xử lý. Tôi đoán rằng trong trường hợp của bạn, bạn thực sự phải thực hiện một trong các cách sau:

• nhận được 100 máy tính để cắt giảm thời gian kiểm tra thông số của bạn để một thời gian hợp lý
• thật sự cố gắng để làm việc ra thông số của bạn bằng tay và tâm trí. Phải có một số dự phòng và ít nhất là kiểm tra sanity để bạn có thể kiểm tra trường hợp của mình trong < 1min
• cho các tập hợp kết quả có thể, cố gắng tìm ra một số 'hoạt động' thay đổi nó một chút thay vì chỉ ngẫu nhiên hóa nó. Ví dụ, trong TSP một số toán tử cơ bản là lambda, hoán đổi hai nút và do đó tạo ra tuyến mới. Bạn có thể thay đổi một số số lên/xuống cho một số giá trị.
• sau đó, tìm cho mình một số thuật toán tốt đẹp, điểm xuất phát của bạn có thể ở đâu đó here. Cuốn sách là nguồn tài nguyên vô giá cho bất kỳ ai bắt đầu giải quyết vấn đề.