BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP-HCM

Danh sách nhóm:

VŨ ĐỨC TOÀN
LÊ VĂN NHÀNH
--------- oOo ---------
Báo cáo :

GIẢI THUẬT ĐÀN KIẾN
TRÍ THÔNG MINH CỦA BẦY ĐÀN
GIẢI THUẬT ĐÀN KIẾN


Đầu tiên kiến tìm thức ăn ngẫu nhiên sau khi tìm được thức ăn để lại dấu vết phocmon trên đường về.

Sau 1 thời gian lượng dấu chân (pheromone) của mỗi chặng đường sẽ khác nhau.

Do sự tích lũy dấu chân của mỗi chặngñường cũng khác nhau đồng thời với sự bay hơi của dấu chân ở những đoạn đường kiến đi . sự tích lũy càng lớn thì cũng đồng nghĩa với việc những đoạn đường đó ngắn nhất từ tổ kiến ñến nơi có thức ăn.

Phương pháp này đưa ra để giải quyết các bài toán có không
gian nghiệm lớn để tìm ra lời giải có nghiệm là tối ưu nhất trong không gian nghiệm đó với thời gian cho phép hay không tìm ra cấu trúc tối ưu hơn thì dừng.
Tổ kiến
Mồi số 1
Mồi số 2
Tổ kiến
Mồi số 1
Mồi số 2
khởi tạo
Đặt mỗi kiến trong một nơi (lựa chọn ngẫu nhiên)
Mỗi kiến tự chọn đường tìm mồi ngẫu nhiên
Tìm thấy mồi
dấu vết pheromone
Xuất kết quả
không
Đường tìm mồi ngắn nhất
có
không
có
GIẢI THUẬT ĐÀN KIẾN


Nguyên lý Chuyển trạng thái
Nguyên lý cập nhật cục bộ
Nguyên lý cập nhật toàn cục
Thuật toán đàn kiến
Nguyên lý Chuyển trạng thái


Xác suất xảy ra (con đường hay đi hoặc vị trí nút đóng cắt ij)
Nguyên lý cập nhật cục bộ và toàn cục


Nguyên lý cập nhật cục bộ và toàn cục


Bằng sự hướng dẫn của cường độ dấu chân, những con kiến sẽ lựa chọn những đường đi thích hợp. Cuối cùng, đường ưa thích nhất giàu pheromone trở thành hành trình tốt nhất, đó chính là lời giải cho vấn ñề.

Khái niệm này nói lên sự xuất hiện của phương pháp ACA:
Đầu tiên, mỗi con kiến trong đàn kiến được đặt ở trạng thái xuất phát, mỗi thành viên sẽ xây dựng trọn vẹn một đường đi từ những điểm bắt ñầu cho đến điểm kết thúc thông qua việc áp dụng lặp đi lặp lại nguyên lý chuyển trạng thái.

Trong khi xây dựng hành trình, mỗi con kiến cũng làm thay đổi lượng pheromone trên đoạn đường nó đi qua bằng cách áp dụng nguyên lý cập nhật cục bộ.

Khi tất cả những con kiến đã hoàn thành hành trình của chúng, lượng pheromone trên đường đi sẽ được hiệu chỉnh trở lại theo nguyên lý cập nhật toàn cục.
Điều kiện ràng buộc


5. KẾT LUẬN VỀ GIẢI THUẬT ĐÀN KIẾN

Thuật toán đàn kiến tìm lời giài tối ưu được xây dựng dựa trên 3 nguyên lý cơ bản: nguyên lý chuyển trạng thái (nguyên lý xác suất), nguyên lý cập nhật cục bộ và nguyên lý cập nhật toàn cục với lời giài ban đầu là hoàn toàn ngẫu nhiên và các hệ số tương quan do người dùng thiết lập tùy theo điều kiện bài toán.

Thông qua việc tìm hiểu lý thuyết về thuật toán và áp dụng để xây dựng mô hình và giài bài toán tái cấu trúc lưới điện phân phối đã mở ra một phương pháp mới để giải quyết các bài toán tối ưu hóa trong quá trinh vận hành hệ thống điện.
5. áp dụng thuật toán đàn kiến giải bài toán tái cấu trúc lưới diện phân phối
khởi tạo
Tạo các khóa điện (ngẫu nhiên)
Cấu hình hình tia
Lưu giá trị tổn thất vào bộ nhớ
Xuất cấu hình đường dây
không
Tổn thất bé nhất
có
không
có
Tính giá trị tổn thất
5. áp dụng thuật toán đàn kiến giải bài toán tái cấu trúc lưới diện phân phối
Thay đổi cắu trúc chính là thay đổi các trạng thái đóng cẳt của các thiết bị liên lạc, phân đoạn trên lưới điện.
Mỗi một thiết bị liên lạc, phân đoạn (ký hiệu - S) được biểu thị bẳng hai trạng thái đóng hoặc mờ (1,0).
Bước 1: tạo một số cấu trúc ban đầu cho mạng phân phối
Mỗi một thiết bị liên lạc, phân đoạn (ký hiệu - S) được biểu thị bẳng hai trạng thái đóng hoặc mờ (1,0).
Bước 2: tính toán hàm mục tiêu cho mỗi cấu trúc
Hàm mục tiêu : tổn thất công suất tác dụng bé nhất.
f = min (ΔP)
Bước 3: cập nhật ma trận dấu chân cho mỗi cấu trúc
Ma trận pheromone là một ma trận kích thước m x n, m hàng biểu diễn cho các vị trí đóng cắt của phân đoạn, n cột biểu diễn cho đoạn đường đi của phần tử kiến. Những phẩn từ của ma trận pheromone Tij được gán một giá trị đó là mức pheromone mô tả khả năng đóng mỡ của các thiết bị đóng cẳt.
Bước 4: Xây dựng danh sách cấu trúc dựa theo dấu chân
Lựa chọn cấu hình đường dây dựa theo những khóa có xác suất
lớn
Bước 5: kiểm tra thời gian cho phép
Nếu thời gian cho phép vẫn còn
và các cấu trúc chọn vẫn còn
thì ta quay lại bước 2.

Bước 6: kiểm tra thời gian cho phép
Nếu thời gian cho phép chấm
dứt hay cấu trúc được chọn
không còn thì ta dừng chương
trình và xuất ra kết quả.



Con đường ngắn nhất
How to choose next city?
A
E
D
C
B
Path and Trace Update
L1 =300
L2 =450
L3 =260
L4 =280
L5 =420
Ant System (Ant Cycle) Dorigo [1] 1991
t = 0; NC = 0; τij(t)=c for ∆τij=0
Place the m ants on the n nodes
Update tabuk(s)

Compute the length Lk of every ant
Update the shortest tour found

=
For every edge (i,j)
Compute
For k:=1 to m do


Initialize
Choose the city j to move to. Use probability
Tabu list management
Move k-th ant to town j. Insert town j in tabuk(s)
Set t = t + n; NC=NC+1; ∆τij=0
NC && not stagn.
Yes
End
No
Yes