Làm thế nào để thiết kế chức năng xác suất chấp nhận cho mô phỏng ủ với nhiều chi phí riêng biệt?

Question

Tôi đang sử dụng simulated annealing để giải quyết vấn đề lập kế hoạch tài nguyên NP hoàn chỉnh. Đối với mỗi đơn đặt hàng ứng cử viên của các nhiệm vụ tôi tính toán một số chi phí khác nhau (hoặc giá trị năng lượng). Một số ví dụ là (mặc dù các chi tiết cụ thể có thể không liên quan đến câu hỏi):

• global_finish_time: Tổng số ngày mà lịch biểu kéo dài.
• split_cost: Số ngày mà mỗi tác vụ bị trì hoãn do gián đoạn bởi các tác vụ khác (điều này có nghĩa là để ngăn cản gián đoạn công việc khi nó đã bắt đầu).
• deadline_cost: Tổng số bình phương số ngày mà mỗi thời hạn bị trễ là quá hạn.

Chức năng chấp nhận khả năng truyền thống trông như thế này (bằng Python):

def acceptance_probability(old_cost, new_cost, temperature): 
    if new_cost < old_cost: 
     return 1.0 
    else: 
     return math.exp((old_cost - new_cost)/temperature) 

Cho đến nay tôi đã kết hợp hai chi phí đầu tiên của tôi vào một bằng cách thêm họ, vì vậy mà tôi có thể ăn các kết quả vào acceptance_probability. Nhưng điều tôi thực sự muốn là dành cho deadline_cost để luôn được ưu tiên hơn global_finish_time và cho global_finish_time để được ưu tiên hơn split_cost. Vì vậy, câu hỏi của tôi để Stack Overflow là: làm thế nào tôi có thể thiết kế một chức năng xác suất chấp nhận có nhiều năng lượng vào tài khoản nhưng luôn luôn xem xét năng lượng đầu tiên là quan trọng hơn năng lượng thứ hai, và như vậy? Nói cách khác, tôi muốn chuyển qua số old_cost và new_cost dưới dạng một số chi phí và trả về một giá trị hợp lý.

Chỉnh sửa: Sau một vài ngày thử nghiệm các giải pháp được đề xuất, tôi đã kết luận rằng cách duy nhất hoạt động tốt đủ cho tôi là đề xuất của Mike Dunlavey, mặc dù điều này tạo ra nhiều khó khăn khác với các thành phần chi phí có đơn vị khác . Tôi thực tế buộc phải so sánh táo với cam.

Vì vậy, tôi đặt một số nỗ lực vào việc "chuẩn hóa" các giá trị. Đầu tiên, deadline_cost là tổng của các ô vuông, vì vậy nó tăng theo cấp số nhân trong khi các thành phần khác phát triển tuyến tính. Để giải quyết vấn đề này, tôi sử dụng căn bậc hai để có tốc độ tăng trưởng tương tự. Thứ hai, tôi đã phát triển một hàm tính toán sự kết hợp tuyến tính của các chi phí, nhưng tự động điều chỉnh các hệ số theo thành phần chi phí cao nhất cho đến nay.

Ví dụ: nếu bộ chi phí cao nhất là (A, B, C) và vectơ chi phí đầu vào là (x, y, z), kết hợp tuyến tính là BCx + Cy + z. Bằng cách đó, bất kể giá trị z cao bao nhiêu sẽ không bao giờ quan trọng hơn giá trị x 1.

Điều này tạo ra "răng cưa" trong hàm chi phí khi phát hiện chi phí tối đa mới. Ví dụ, nếu C tăng lên thì BCx và Cy sẽ cao hơn cho đầu vào (x, y, z) cho trước và do đó sẽ khác nhau giữa các chi phí. Chênh lệch chi phí cao hơn có nghĩa là xác suất chấp nhận sẽ giảm, như thể nhiệt độ đột ngột giảm thêm một bước nữa. Trong thực tế mặc dù đây không phải là một vấn đề bởi vì chi phí tối đa được cập nhật chỉ một vài lần trong đầu và không thay đổi sau đó. Tôi tin rằng điều này thậm chí có thể được lý thuyết chứng minh để hội tụ với một kết quả chính xác vì chúng ta biết rằng chi phí sẽ hội tụ về phía giá trị thấp hơn.

Một điều mà tôi vẫn còn hơi bối rối là những gì xảy ra khi chi phí tối đa là 1.0 và thấp hơn, nói 0.5. Với vectơ cực đại (0,5, 0,5, 0,5), điều này sẽ cho kết hợp tuyến tính 0,5 * 0,5 * x + 0,5 * y + z, tức làthứ tự ưu tiên đột nhiên đảo ngược. Tôi cho rằng cách tốt nhất để đối phó với nó là sử dụng vectơ tối đa để chia tỷ lệ tất cả các giá trị thành các phạm vi nhất định, sao cho các hệ số luôn có thể giống nhau (giả sử, 100x + 10y + z). Nhưng tôi vẫn chưa thử.

Answer 1

mbeckish là đúng.

Bạn có thể tạo kết hợp tuyến tính của các nguồn năng lượng khác nhau và điều chỉnh các hệ số không?

Có thể ghi nhật ký chuyển đổi chúng vào và ra?

Tôi đã thực hiện một số MCMC bằng Metropolis-Hastings. Trong trường hợp đó, tôi xác định khả năng đăng nhập (không chuẩn hóa) của một tiểu bang cụ thể (được trao cho các thầy tế lễ), và tôi thấy rằng một cách để làm rõ suy nghĩ của tôi về những gì tôi muốn.

Answer 2

Điều đó tùy thuộc vào ý bạn là "được ưu tiên". Ví dụ: Ví dụ: nếu deadline_cost giảm 0,001, nhưng chi phí global_finish_time tăng lên 10.000? Bạn có trở lại 1.0, bởi vì số tiền deadline_cost giảm và có được ưu tiên hơn bất kỳ thứ gì khác không? Điều này có vẻ như đó là một cuộc gọi phán xét mà chỉ bạn mới có thể thực hiện, trừ khi bạn có thể cung cấp đủ thông tin cơ bản về dự án để những người khác có thể đề xuất cuộc gọi thông báo riêng của họ.

Answer 3

tôi sẽ xem xét cái gì đó dọc theo dòng:

If (new deadline_cost > old deadline_cost) 
    return (calculate probability) 

else if (new global finish time > old global finish time) 
    return (calculate probability) 

else if (new split cost > old split cost) 
    return (calculate probability) 

else 
    return (1.0) 

Tất nhiên mỗi người trong số ba vị trí bạn tính toán xác suất có thể sử dụng một chức năng khác nhau.

Answer 4

Tôi sẽ lấy một gợi ý từ thuật toán tiến hóa đa mục tiêu (MOEA) và chuyển đổi nó nếu tất cả các mục tiêu đồng thời truyền với hàm acceptance_probability bạn đã cung cấp. Điều này sẽ có tác dụng khám phá mặt trước Pareto giống như việc ủ mô phỏng tiêu chuẩn khám phá cao nguyên của các giải pháp cùng năng lượng.

Tuy nhiên, điều này không bỏ qua ý tưởng có ưu tiên đầu tiên.

Có thể bạn sẽ phải tinh chỉnh thông số của mình, chẳng hạn như cho nhiệt độ ban đầu cao hơn.