Tổng hợp Thuật Toán Simulated Annealing | Môn Trí tuệ nhân tạo - Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

lOMoAR cPSD| 58778885
THUẬT TOÁN SIMULATED ANNEALING
I. Sơ lượt giải thuật Leo Đồi (Hill Climbing) 1. Giới thiệu
Thuật toán Hill Climbing là thuật toán tìm kiếm cục bộ được sử dụng để tìm giá trị tối ưu
trong một không gian tìm kiếm. Thuật toán này bắt đầu với một giá trị khởi đầu và cố gắng tìm
kiếm các giá trị lân cận tốt hơn, tìm kiếm đến khi không thể tìm thấy giá trị lân cận tốt hơn. 2. Hạn chế
Hill Climbing có các hạn chế như:
- Rơi vào cực trị địa phương: không thể tìm ra giá trị tối ưu toàn cục
- Không thể xử lý các không gian tìm kiếm lớn: Khi kích thước không gian
tìm kiếmlớn, việc tìm kiếm các giá trị lân cận để đưa ra quyết định có thể trở nên quá
phức tạp và thời gian tính toán cao.
- Không có tính đa dạng: Thuật toán Hill Climbing có xu hướng hội tụ đến
một giá trịtối ưu nhất định, nên có thể bỏ qua không gian tìm kiếm tốt hơn.
Vì có các hạn chế về giá trị cục bộ nên việc sử dụng bước đi ngẫu nhiên để chuyển sang
trạng thái kế tiếp mà không quan tâm giá trị hiện tại có thể làm cho chúng ta tìm được giá trị toàn
cục (nó có thể kém hiệu quả vì là xác suất nhưng vẫn có thể đem lại giá trị chính xác và sai số
không quá cao). Do đó, bây giờ chúng ta sẽ tìm hiểu một thuật toán mới hiệu quả hơn thuật toán
Hill Climbing và có sử dụng bước đi ngẫu nhiên (nhưng có ràng buộc).
II. Thuật toán Simulated Annealing 1. Giới thiệu
Thuật toán simulated Annealing có tiền thân là thuật toán Monte Carlo năm 1953 của nhóm Metropolis.
Thuật toán simulated annealing được đề xuất bởi S. Kirk_ partrick năm 1982 và được công
bố năm 1983 trước công chúng. 2. Nội dung
Simulated annealing là thuật toán tìm kiếm xác suất di truyền, là phương pháp tối ưu hóa có
thể áp dụng để tìm kiếm tối ưu hóa toàn cục của một hàm chi phí và tránh được tối ưu hóa địa
phương bằng việc chấp nhận một kế quả tệ hơn với xác suất phụ thuộc vào nhiệt độ T.
Thuật toán Simulated Annealing sử dụng một hàm mất mát để đánh giá chất lượng của một
giải pháp. Thuật toán bắt đầu với một giải pháp ngẫu nhiên và sử dụng một hàm xác suất để xác
định xem liệu giải pháp mới có tốt hơn giải pháp hiện tại hay không. Hàm xác suất này được tính
toán bằng cách sử dụng nhiệt độ và sự khác biệt về giá trị của hàm mất mát giữa giải pháp hiện tại
và giải pháp mới. Khi nhiệt độ giảm dần, thuật toán dần chuyển sang chế độ tìm kiếm cục bộ để
tìm kiếm giá trị tối ưu toàn cục.
Ưu điểm, bao gồm khả năng tránh được các giá trị cực trị địa phương và khả năng khám phá
nhiều giải pháp khác nhau trong không gian tìm kiếm. Tuy nhiên, thuật toán cũng có một số hạn
chế, bao gồm cần phải điều chỉnh các tham số và tốc độ giảm nhiệt độ để đạt được hiệu quả tối ưu
và việc tính toán có thể tốn kém nếu không thích hợp. lOMoAR cPSD| 58778885
Nhược điểm: Tốc độ hội tụ chậm cần nhiều thời gian để tìm ra giải pháp tối ưu, độ chính xác
mang tính tương đối, điều chỉnh tham số gặp khó khăn (Heuristic).
3. Các bước để giải quyết để giải quyết một bài toán bằng thuật toán Simulated Annealing
Video:https://en.wikipedia.org/wiki/Simulated_annealing#/media/
File:Hill_Climbing_with_Simulated_Annealing.gif
Input: Điểm khởi đầu, lịch trình nhiệt độ (schedule)
Output: Tọa độ điểm global minima/global maxima Thực hiện:
Điểm hiện tại <- ( gán bằng ) điểm khởi đầu
Dùng vòng lặp từ t = 1 đến ∞ ( ∞ là độ dài mảng nhiệt độ schedule ) Gán T= schedule(t)
Nếu T = 0 (kết thúc quá trình rèn là nhiệt độ của lò = 0) thì in ra điểm hiện tại
Chọn random một điểm bất kỳ trong đoạn [a,b] và gán giá trị cho next (a,b là khoảng tìm
global maxima/minima cho trước)
Kiểm tra xem điểm mới random có tốt hơn điểm hiện tại hay ko:
- Nếu tìm global maxima thì f(current) < f(next) deltaE = f(current)-f(next) <0
- Nếu tìm global minima thì f(current) > f(next) deltaE = f(current)-f(next) >0
Nếu tốt hơn thì điểm hiện tại ( current ) <- điểm mới random ( next )
Nếu không thì sẽ xét xác suất chấp nhận thông qua phân phối Boltzmann
(Hàm Boltzmann dùng để đo lường mức độ khác biệt về năng lượng giữa trạng thái mới và
trạng thái hiện tại, và được sử dụng để tính xác suất chấp nhận trạng thái mới. P(deltaE, T) =
exp(-deltaE / T) hoặc exp(deltaE / T) Trong đó:
deltaE là sự khác biệt về năng lượng giữa trạng thái mới và trạng thái hiện tại.
T là nhiệt độ hiện tại.
Hàm Boltzmann cho biết xác suất chấp nhận trạng thái mới dựa trên mức độ khác biệt về
năng lượng giữa trạng thái mới và trạng thái hiện tại. Khi nhiệt độ cao, tức là T lớn, mức độ khác
biệt về năng lượng được giảm bớt và xác suất chấp nhận trạng thái mới sẽ cao hơn, cho phép
thuật toán di chuyển nhiều hơn trong không gian tìm kiếm. Khi nhiệt độ thấp, tức là T nhỏ, mức
độ khác biệt về năng lượng lớn hơn (p rất nhỏ) và xác suất chấp nhận trạng thái mới sẽ giảm,
giúp thuật toán tập trung vào các giải pháp tốt hơn và tránh các giải pháp kém hơn.
Cho n = random.random() ( random giá trị từ 0 đến 1 ) , xác suất chấp nhận (P) > n => chấp nhận di chuyển
Với xác suất chấp nhận được tính như sau:
- Nếu tìm global maxima: e^(-deltaE/T)
- Nếu tìm global minima: e^(deltaE/T)
Bởi vì để cho xác suất chấp nhận nằm trong khoảng [0,1] thì số mũ phải < 0 nên ở global maxima là -deltaE/T III. ỨNG DỤNG lOMoAR cPSD| 58778885
Vấn đề là chúng ta thực hiện N công việc bằng M máy.Mỗi công việc bao gồm một chuỗi
hoạt động (Oi,1, Oi,2 ,Oi,3 ,Oi,4 ,…). Tập hợp M=(M1, M2, M3,.., Mm,) là tập hợp các máy thực hiện
các chi tiết. Bài toán có một số điều kiện sau: -
Các máy thực hiện độc lập và không bị ảnh hướng các yếu tố bên ngoài -
Các chi tiết độc lập với nhau, không ràng buộc về thứ tự thực hiện các hoạt động -
Thời gian thiết lập của máy và di chuyển giữa các hoạt động là không đáng kể -
Tại một thời điểm nhất định mỗi máy chỉ thực hiện được một hoạt động -
Mỗi hoạt động thực hiện chi tiết phải được hoàn thành mà không bị gián đoạn khi nóbắt đầu
Vấn đề được đưa ra là sắp xếp thứ tự thực hiện các công việc cho các máy để đưa ra được
thời gian hoàn thành tất cả cong việc ngắn nhất. Máy Hoạt động M1 M2 M3 M4 O1,1 4 7 6 5 O1,2 2 6 ∞ 5 O2,1 4 5 7 ∞ O2,2 5 ∞ 6 3 O2,3 ∞ 5 4 7 O3,1 5 3 ∞ 6 O3,2 ∞ ∞ 4 ∞ O4,1 2 4 ∞ 5 O4,2 ∞ 4 2 ∞ O4,3 5 4 6 3
(kí hiệu vô cùng là máy không thực hiện được hoạt động đó) Áp dụng thuật toán SA:
Chúng ta chọn một giải pháp ban đầu bất kì là (s0) và khởi tạo nhiệt độ ban đầu (T0) Set T T0 và s s0
Khởi tạo trạng thái ban đầu: Xác định trạng thái ban đầu là một hoán vị ngẫu nhiên của các công
việc trên các máy for t=I to ∞ do: if T=0 Trả về s
s’ là một giải pháp được lấy ngẫu nhiên từ tập hợp các giải pháp
->Ta có thể lấy ngẫu nhiêu bằng cách thay đổi ngẫu nhiên 1 máy đang xử lí công việc đó bằng một máy khác deltaS f(s) - f(s’)
-> Hàm f(s) là hàm dùng đẻ tính toán thời gian hoành thành khi sử dụng giải pháp s if(deltaS>0):
thì việc dùng giải pháp s’ tối ưu hơn giải phap hiện tại là s thì ta cập nhập
giải pháp tối ưu nhất là hiện tại là s’ : gán kết quả = f(s’)
else: lấy ngẫu nhiên một giá trị R thuộc (0,1) if(R lOMoAR cPSD| 58778885
Thực hiện cho đến khi T giảm đến 0 thì dừng lại ta sẽ được giải pháp tối ưu nhất là s s = (O3,1,
M2), (O2,1, M1), (O3,2, M3), (O4,1, M1), (O2,2, M4), (O4,2, M3), (O1,1, M4), (O1,2, M1), (O4,3, M2), (O2,3, M3) = 14 M O4, 1 O2,1 1 O1,2 M 2 O3,1 O4,3 M O4, 3 O3,2 2 O2,3 M 4 O2,2 O1,1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
Như vậy qua việc giải bài toán trên ta có thể áp dụng thuật SA vào việc
Tối ưu lập lịch sản xuất: Trong các nhà máy sản xuất, việc tối ưu lập lịch sản xuất là rất quan
trọng để đảm bảo rằng việc sản xuất được thực hiện một cách hiệu quả và tiết kiệm chi phí. Thuật
toán Simulated Annealing có thể được sử dụng để tìm kiếm lịch sản xuất tối ưu nhất bằng cách
thay đổi thứ tự sản xuất, thời gian sản xuất và số lượng sản phẩm.
Ngoài ra chúng ta có thể áp dụng thuật toán này vào để giải quyết bài toán thực tế khác như là : 1.
Tối ưu vận tải và định tuyến: Trong các hệ thống vận tải và định tuyến, việc tối ưu
hóaquãng đường và thời gian di chuyển của các phương tiện cũng là rất quan trọng. Thuật toán
Simulated Annealing có thể được sử dụng để tìm kiếm lộ trình vận tải và định tuyến tối ưu nhất
bằng cách thay đổi quãng đường và thời gian di chuyển của các phương tiện. 2.
Tối ưu hóa các hệ thống điện: Trong các hệ thống điện, việc tối ưu hóa việc phân
phốiđiện và mức độ tiêu thụ cũng là rất quan trọng. Thuật toán Simulated Annealing có thể được
sử dụng để tìm kiếm cách phân phối điện và mức độ tiêu thụ tối ưu nhất bằng cách thay đổi vị trí
và công suất của các đầu nối và tải điện. 3.
Tạo ra phần mềm giúp phân chia, sử dụng tối ưu các phòng học và giáo viên để
mọi người được về sớm.
IV. (Bài tập về nhà): Áp dụng thuật toán Simulated annealing để tìm
a. Global maxima và global minima của hàm số:
f ( x )=x3−3x2−9x+35trênđoạn[−4;4]
Đáp án test: min tại x = -4 max tại x = -1
b. Global minima của hàm số:
f ( x )=ex −2x 200
+3x3−9x2−xtrênđoạn[−1;1] lOMoAR cPSD| 58778885
Sau đó dùng Matplotlib vẽ đồ thị cho hàm số trên
Đáp án test: min tại x=1