Lựa chọn hàng xóm trong thuật toán ủ mô phỏng

Question

Khi chọn hàng xóm nên xem xét nhiệt độ của thuật toán? Vì vậy, ví dụ nếu nhiệt độ cao khi chọn một người hàng xóm nên hoán vị được thực hiện? Hay nhiệt độ chỉ ảnh hưởng đến xác suất chấp nhận?

Answer 1

Điều sau là đúng: Chỉ xác suất chấp nhận bị ảnh hưởng bởi nhiệt độ. Nhiệt độ càng cao, càng có nhiều động thái "xấu" được chấp nhận để thoát khỏi optima địa phương. Nếu bạn chọn trước các nước láng giềng với các giá trị năng lượng thấp, về cơ bản bạn sẽ mâu thuẫn với ý tưởng Mô phỏng và biến nó thành một tìm kiếm tham lam.

Mã giả từ Wikipedia:

s ← s0; e ← E(s)         // Initial state, energy. 
sbest ← s; ebest ← e        // Initial "best" solution 
k ← 0            // Energy evaluation count. 
while k < kmax and e > emax      // While time left & not good enough: 
    T ← temperature(k/kmax)       // Temperature calculation. 
    snew ← neighbour(s)        // Pick some neighbour. 
    enew ← E(snew)         // Compute its energy. 
    if P(e, enew, T) > random() then    // Should we move to it? 
    s ← snew; e ← enew       // Yes, change state. 
    if enew < ebest then       // Is this a new best? 
    sbest ← snew; ebest ← enew     // Save 'new neighbour' to 'best found'. 
    k ← k + 1          // One more evaluation done 
return sbest          // Return the best solution found. 

Answer 2

Tôi cũng có cùng một câu hỏi, nhưng tôi nghĩ câu trả lời từ một bài Basics of Simulated Annealing in Python cho thấy T có thể liên quan đến việc lựa chọn các nước láng giềng là khá hợp lý.

Chọn hàng xóm cũng sẽ phụ thuộc vào sự cố của bạn. Lý do chính để giới hạn khu phố là khi bạn đã tìm được một giải pháp tốt, ngay cả khi sau đó bạn chuyển sang giải pháp tồi tệ hơn, bạn ít nhất cũng ở trong khu vực lân cận. Trực giác là hầu hết các chức năng khách quan đều hơi trơn tru, vì vậy các giải pháp tốt sẽ nằm gần các giải pháp tốt khác. Vì vậy, bạn cần một khu phố đủ nhỏ để giữ cho bạn gần các giải pháp tốt, nhưng đủ lớn để cho bạn tìm thấy chúng một cách nhanh chóng. Một điều bạn có thể thử là giảm vùng lân cận theo thời gian (ví dụ: làm cho tỷ lệ thuận với nhiệt độ). - hunse Nov 4 '13 at 20:58

Answer 3

Dưới đây là mô tả từ wikipedia cho biết nhiệt độ nên được tính toán thực tế trong một số vấn đề.

thế hệ thí sinh hiệu quả

Một tuyên bố chính xác hơn của heuristic là người ta nên cố gắng bang ứng cử viên đầu tiên mà P (E (s), E (s'), T) s là lớn. Đối với hàm chấp nhận "chuẩn" P ở trên, nó có nghĩa là E (s ') - E (s) là theo thứ tự T hoặc nhỏ hơn. Như vậy, trong ví dụ nhân viên bán hàng đi du lịch ở trên, người ta có thể sử dụng một người hàng xóm() chức năng hoán đổi hai thành phố ngẫu nhiên, nơi xác suất của việc lựa chọn một cặp thành phố biến mất tựa như khoảng cách của họ tăng vượt T.

này không ngụ ý Nhiệt độ đó có thể là yếu tố liên quan khi xác định hàng xóm.

Đọc hữu ích hơn về cách viết chức năng lân cận: How to efficiently select neighbour in 1-dimensional and n-dimensional space for Simulated Annealing