[Q] Hoi ve thuat toan

[noname2003]

Chào các bạn !!
Bạn nào rành về thuật toán Simulated Annealing thì chỉ cho mình với !!
Cám ơn nhiều

[hiensmart]

Xin lỗi cho hỏi Simulated Annealing là kí rì dzậy

[noname2003]

Đó là tên một thuật toán được dùng trong lập trình mà mình đang muốn tìm tài liệu để đọc thêm về nó.

[hiensmart]

Dịch ra Tiếng Việt đi

[noname2003]

Hi!
Mình không biết dịch cái tên riêng này ra tiếng Việt thế nào (bạn có thể tra từ điển), nhưng mình chỉ có thể nói qua một chút về ý tưởng của nó thôi (vì mình cũng chỉ đang học nó mà)
Simulated Annealing là một thuật toán xuất phát từ nghành luyện kim. ý tưởng của nó là giảm dần nhiệt độ trong một khoảng nhất định trong một thời gian để nhận được một cấu trúc kim loại mong muốn. Nhưng các nhà lập trình đã phát triển ý tưởng này thành một thuật toán. Nếu bạn học về nghành máy tính tính này chắc đã gặp thuật toán evolution algorithm, đó cũng là một biến thể hay có thể gọi là một phát triển của thuật toán này.

[duong_hoang]

Simulated Annealing về thực chất không phải là một thuật toán xuất phát từ ngành luyện kim như ban Noname2003 nói mà đây là một thuật toán mô phỏng quá trình diễn ra giống như các hiện tượng có trong tự nhiên (mà luyện kim là một ví dụ). Đây là một thuật toán tối ưu dưa trên ý tưởng cơ bản là khi ta nung nóng một vật đến nhiệt độ nóng chảy rồi dần dần hạ nhiệt độ xuống một cách rất chậm thì cuối cùng các tinh thể trong vật đó sẽ sắp xếp theo cấu trúc có mức năng lượng nhỏ nhất.
Tương tự như vậy, đối với một bài toán tối ưu, người ta dùng một tham số điều khiển được gọi là nhiệt độ, T để điều khiển quá trình làm lạnh của vật. Tất cả các bài toán giải băng SA đều thực hiện như sau:
- Trước tiên, tìm điểm xuất phát của bài toán (starting feasible solution).
- Liệt kê tập các láng giềng có thể có của lời giải hiện tại.
- Tiến hành ước lượng hàm mục tiêu hiện tại và hàm mục tiêu của láng giềng vừa tìm được.
- Sinh một biến ngẫu nhiên, thường là phân bố mũ có các tham số phụ thuộc vào hiệu của các giá trị hàm mục tiêu và tham số T.
- Nếu biến ngẫu nhiên lớn hơn/nhỏ hơn một ngưỡng cho trước thì chấp nhận láng giềng vưa tìm được làm phương án hiện tại.
- Giảm nhiệt độ T
- Quay trở lại từ đầu
Trên Internet có rất nhiều tài liệu về vấn đề này. Cách đây vài năm tôi có làm về network planning tôi có nghiên cứu thuật toán này trong vài tháng. Theo quan điểm cá nhân tôi thì thuật toán này có khả năng giải quyết được một lớp khá lớn các bài toán quy hoạch nguyên. Ưu điểm lớn nhất của thuật toán là có thể dễ dàng biểu diễn các bài toán một cách dễ dàng. Người ta đã chứng minh được rằng khi thời gian -> vô cùng (T->0) thì có thể tìm được giá trị tối ưu toàn cục.
Do thời gian khá lâu nên tài liệu còn lại của tôi chác cũng không còn nhiều nhưng nếu bạn cần thông tin gì thì có thể mail cho tôi theo địa chỉ duong@ript.edu.vn

[noname2003]

Cam on duong_hoang !!!
Mac du bai tra loi cua ban den voi minh hoi muon, nhung du sao no cung giup duoc minh hieu ro hon ve thuat toan nay.
Cam on