Nghiên cứu Khoa học
Cấu trúc liên kết vùng lân cận của PSO
Hai cấu trúc liên kết lân cận phổ biến là hình sao (hoặc bánh xe) và cấu trúc liên kết vòng (hoặc vòng tròn). Đối với cấu trúc liên kết sao, một hạt được chọn làm trung tâm, được kết nối với tất cả các hạt khác trong bầy đàn tuy nhiên, tất cả các hạt khác chỉ được kết nối với trung tâm. Đối với cấu trúc liên kết vòng, các hạt được sắp xếp trong một vòng. Mỗi hạt có một số hạt ở bên phải và bên trái là vùng lân cận của nó. Đối với cấu trúc liên kết Von Neumann, các hạt được kết nối bằng cách sử dụng một mạng lưới (mạng 2 chiều) trong đó mỗi hạt được kết nối với bốn các hạt lân cận (các hạt bên trên, bên dưới, bên phải và bên trái).
(a) Liên kết dạng sao (b)Liên kết dạng vòng (c) Liên kết dạng Von Neumann
Hình 1: Một biểu diễn sơ đồ của cấu trúc liên kết lân cận
Việc lựa chọn cấu trúc liên kết lân cận có ảnh hưởng sâu sắc đến việc truyền bá của giải pháp tốt nhất được tìm thấy bởi bầy đàn. Sử dụng mô hình gbest, sự lan truyền là rất nhanh (tức là tất cả các hạt trong bầy sẽ bị ảnh hưởng bởi giải pháp tốt nhất được tìm thấy trong lần lặp t, ngay lập tức trong lần lặp t+1). Sự lan truyền nhanh này có thể dẫn đến vấn đề hội tụ sớm. Tuy nhiên, sử dụng vòng và cấu trúc liên kết Von Neumann sẽ làm chậm tốc độ hội tụ vì tốt nhất giải pháp được tìm thấy phải lan truyền qua một số vùng lân cận trước khi ảnh hưởng đến tất cả các hạt trong bầy đàn. Sự lan truyền chậm này sẽ cho phép các hạt khám phá thêm vùng trong không gian tìm kiếm và do đó làm giảm khả năng hội tụ sớm.
Trong PSO các giá trị thành phần và vector bị giới hạn trong khoảng (1;0).
Vận tốc được hiểu là xác xuất thay đổi từ 1 thành 0 và ngược lại từ 0 thành 1 khi cập nhật vị trí của các hạt. Do đó vector vận tốc vẫn có giá trị liên tục.
PSO và các thuật toán tìm kiếm ngẫu nhiên có hai nhược điểm chính. Hạn chế đầu tiên của PSO và các thuật toán tìm kiếm ngẫu nhiên là bầy đàn có thể hội tụ sớm, mặc dù PSO tìm ra giải pháp tốt nhanh hơn nhiều so với các thuật toán tiến hóa khác, nó thường không thể cải thiện chất lượng của các giải pháp khi số lần lặp tăng lên. PSO thường bị hội tụ sớm khi các vấn đề đa phương thức mạnh đang được tối ưu hóa. Cơ sở lý luận đằng sau vấn đề này là, đối với PSO tốt nhất, các hạt hội tụ tại một điểm duy nhất, nằm trên ranh giới giữa vị trí tốt nhất toàn cục và vị trí cá nhân tốt nhất. Điểm này thậm chí không được đảm bảo là tối ưu cục bộ. Một lý do khác cho vấn đề này là tốc độ nhanh của luồng thông tin giữa các hạt, dẫn đến việc tạo ra các hạt tương tự (mất tính đa dạng) làm tăng khả năng bị mắc kẹt trong tối ưu cục bộ. Một số cải tiến của PSO đã được đề xuất để giải quyết vấn đề này. Hai trong số những cải tiến này là trọng lượng quán tính và mô hình lbest.
Hạn chế thứ hai là phương pháp tiếp cận ngẫu nhiên phụ thuộc vào vấn đề hiệu năng. Sự phụ thuộc này thường xuất phát từ cài đặt tham số của từng thuật toán. Do đó, sử dụng các cài đặt tham số khác nhau cho một thuật toán tìm kiếm ngẫu nhiên dẫn đến phương sai hiệu suất cao. Nói chung, không có cài đặt tham số nào tồn tại mà có thể được áp dụng cho tất cả các vấn đề. Vấn đề này được thể hiện rõ trong PSO nơi sửa đổi tham số PSO có thể dẫn đến hiệu ứng tương ứng lớn. Ví dụ, tăng giá trị của trọng lượng quán tính, w, sẽ tăng tốc độ của các hạt dẫn đến khám phá nhiều hơn (tìm kiếm toàn cục) và khai thác ít hơn (tìm kiếm cục bộ). Mặt khác, việc giảm giá trị của w sẽ làm giảm tốc độ của hạt dẫn đến khai thác nhiều hơn và thăm dò ít hơn. Do đó, việc tìm giá trị tốt nhất cho w không phải là một nhiệm vụ dễ dàng và nó có thể khác nhau tùy từng bài toán. Do đó, có thể kết luận rằng hiệu suất PSO phụ thuộc vào vấn đề. Một giải pháp cho hiệu suất phụ thuộc vào vấn đề của PSO là sử dụng các tham số tự thích nghi. Trong chế độ tự điều chỉnh, các tham số của thuật toán được điều chỉnh dựa trên về phản hồi từ quá trình tìm kiếm.
KHOA ĐIỆN - ĐIỆN TỬ ĐẠI HỌC DUY TÂN
Phòng 503 - K7/25 Quang Trung, Tp Đà Nẵng
(0236) 3827111(Ext 503)
feee@duytan.edu.vn
