Giải thuật Chaotic Vortex Search cho bài toán tối ưu toàn cục
Tạp chí Khoa học và Công nghệ, Số 45A, 2020
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN
TỐI ƯU TOÀN CỤC
TRƯƠNG KHẮC TÙNG1, ĐỖ HÀ PHƯƠNG1, DƯƠNG ĐỨC HƯNG2
1 Khoa Công Nghệ Thông Tin, Trường Đại Học Công Nghiệp Tp Hồ Chí Minh, Việt Nam
2 Đại học Huế, 03 Lê Lợi, Huế, Việt Nam
Abstract. Trong bài báo này, dựa trên nghiên cứu lý thuyết về giải thuật tìm kiếm tối ưu Vortex Search
(VS), lý thuyết và ứng dụng lý thuyết Chaos vào họ giải thuật MetaHeuristics. Chúng tôi đề xuất cải tiến
giải thuật VS bằng cách lai quy luật phát sinh tập ứng viên giải thuật VS với hàm Chaotic Bernoulli Map.
Kết quả kiểm chứng trên tập 20 hàm Benchmark cho thấy giải thuật mới có kết quả tốt hơn so với nguyên
bản trên các tiêu chí đánh giá.
Keywords. Global optimization; Artificial intelligence; Chaotic number; Hybrid algorithm;
CHAOTIC VORTEX SEARCH ALGORITHM FOR GLOBAL NUMERICAL
OPTIMIZATION
Abstract. In this paper, based on theoretical studies of the optimal search algorithm Vortex Search (VS),
the theory and application of Chaos theory to the Metaheuristics. We propose to improve the VS
algorithm by hybridization of the rule for generating the candidate solutions algorithm of VS wiith
chaotic function by using the Bernoulli map. Simulation results on a set of 20 Benchmark validation
algorithms show that the new algorithm has better results than the old algorithm on the evaluation
criterias.
Keywords. Global optimization; Artificial intelligence; Chaotic number; Hybrid algorithm;
1 MỞ ĐẦU
Trong những năm gần đây, đã có rất nhiều nghiên cứu lý thuyết, ứng dụng và cải tiến các giải thuật tìm
kiếm xấp xỉ tối ưu họ Metaheuristics[1][2][3][4][5]. Hai vấn đề chính của giải thuật luôn gặp phải[2] là
chi phí thực thi và dễ rơi vào bẫy cục bộ địa phương làm ảnh hưởng trực tiếp đến chất lượng lời giải. Đối
với việc giải quyết vấn đề cục bộ địa phương thì ngoài hướng tiếp cận nghiên cứu tìm cảm hứng bầy
đàn[2][5][6] trong tự nhiên, hướng đa bầy đàn Multi-Swarm[7] còn có một cách tiếp cận cải tiến các giải
thuật này là ứng dụng lý thuyết hỗn loạn[1][3][4] cũng đang rất được quan tâm nghiên cứu. Trong số các
hàm chaos thì hàm Chaotic Bernoulli Map được sử dụng khá phổ biến trong việc tạo ra chuỗi số thay thế
bộ sinh số ngẫu nhiên. Trong bài báo này chúng tôi tập trung vào kết hợp hàm Chaotic Bernoulli Map vào
giải thuật VS và chứng minh tính hiệu quả của giải thuật mới thông qua 20 hàm Benchmark. Trong mục
này, chúng tôi trình bày tóm lược về các nội dung: Bài toán tối ưu toàn cục hàm đại số, tóm lược về
Metaheuristics, giải thuật Vortex Search và Lý thuyết hỗn loạn.
1.1 Bài toán tìm kiếm giải pháp tối ưu toàn cục
Cho hàm số f: D → R, D ⊂ Rn; Tìm x ∈ D để f(x) đạt cực đại - Max hay cực tiểu – Min.
trong đó, Rn: Không gian số thực n chiều, D: miền ràng buộc hay chính là không gian tìm kiếm lời giải
của bài toán.
Vectơ x = (x1, x2, ..., xn)T ∈ D ⊂ Rn được gọi là một giải pháp – Solution (một lời giải của bài toán tìm
kiếm giải pháp tối ưu).
*
*
*
*
Giá trị x* = (x1 , x2 , ..., xn ) ∈ Rn được gọi là giải pháp tối ưu toàn cục nếu x ∈ D và f(x*) ≥ f(x), ∀x ∈
D với bài toán cực đại hóa hay f(x*) ≤ f(x), ∀x ∈ D với bài toán cực tiểu hóa.
Vectơ x’ ∈ Rn được gọi là giải pháp tối ưu địa phương nếu x’∈ D và tồn tại một lân cận Nε đủ nhỏ của
điểm x’ sao cho f(x’) ≥ f(x), ∀x ∈ Nε ∩ D với bài toán cực đại hoá hay f(x’) ≤ f(x), ∀x ∈ Nε ∩ D với bài
toán cực tiểu hóa.
Dễ dàng nhận thấy điểm cực trị toàn cục cũng là một cực trị địa phương nhưng điều ngược lại không
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
4
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
hẳn đúng. Hàm chỉ có một cực trị duy nhất thuộc nhóm U: Unimodal, hàm có nhiều cực trị thuộc nhóm
M: Multimodal. Nhóm Multimodal khiến bài toán tìm kiếm lời giải tối ưu khó hơn rất nhiều khi gặp vấn
đề bẫy cục bộ địa phương.
Hàm phân tách được (Separate) có thể áp dụng tính toán tối ưu bằng cách tập trung hướng tìm kiếm
vào từng biến thành phần và thực hiện xoay vòng trên từng biến. Trong khi đó, hàm không phân tách
được (Non-Separate) phức tạp hơn rất nhiều khi hướng tìm kiếm phụ thuộc vào 2 hay nhiều biến thành
phần.
Bộ 20 hàm số kiểm chuẩn (Benchmark) đầu vào kiểm chứng kết quả bài báo được phân bổ trên các nhóm
hàm: U: Unimodal, M: Multimodal, S: Separable, N: Non-Separable.
1.2 Tóm lược về Metaheuristics
Trở lại bài toán tối ưu toàn cục hàm đại số, có hai vấn đề chính của việc tìm kiếm giải pháp tối ưu toàn
cục hàm đại số đó là vấn đề chi phí thực thi (thời gian, tài nguyên máy tính) và vấn đề bẫy cục bộ địa
phương.
Đối với vấn đề chi phí thực thi, tiếp cận theo hướng xấp xỉ được nghiên cứu để giải quyết vấn đề. Thay
vì tìm kiếm lời giải tối ưu chính xác thì sẽ đưa ra một giải pháp tốt nhất chấp nhận được đáp ứng được
yêu cầu về thời gian cũng như năng lực máy tính[2][8].
Đối với vấn đề bẫy cục bộ địa phương, các tiếp cận như giải thuật tiến hóa, siêu tri thức
Metaheuristic[2][8][9] được nghiên cứu để giải quyết vấn đề. Thay vì việc tìm kiếm các quy luật để phát
hiện ra lời giải, các giải thuật Metaheuristics xác định không gian tìm kiếm lời giải, sau đó khởi tạo tập
giải pháp ban đầu và thực hiện tiến hóa để làm tốt dần lên qua các thế hệ. Kết quả tốt nhất từ tập giải pháp
sau cùng là lời giải của bài toán.
Họ giải thuật Metaheuristics tiến hành theo chiến lược thăm dò kết hợp với chiến lược khai thác. Thăm
dò nhằm tránh bỏ sót các vùng tìm kiếm tiềm năng được thực hiện bằng cách đưa yếu tố ngẫu nhiên tham
gia vào xây dựng quần thể cá thể tìm kiếm mới trong thế hệ kế tiếp. Khai thác nhằm tiếp cận nhanh nhất
điểm cực trị vùng tìm kiếm có nghĩa là việc xây dựng quần thể tìm kiếm mới dựa trên những thông tin tốt
nhất ở thế hệ hiện tại.
Vấn đề chính của Metaheuristic là cân bằng giữa việc thăm dò và khai thác, quá tập trung vào thăm dò
khiến lời giải không chất lượng và ngược lại nếu quá tập trung vào khai thác lại khiến giải thuật dễ rơi
vào bẫy cục bộ địa phương. Việc này được thực hiện bằng cách cố gắng cân bằng xác xuất hướng vào
việc thăm dò và hướng vào việc khai thác. Họ Metaheuristics gồm 2 lớp giải thuật: Single-Solution Based
(Simulated Annealing SA[10], Random Search[11], Pattern Search[12], Vortex Search[5][13]…) và
Population Based (Genetic Algorithm[8][9], Particle Swarm Optimization PSO[3][6][7], Social Spider
Algorithm[14]…). Lớp giải thuật Single-Solution Based chỉ khởi tạo một cá thể tìm kiếm ban đầu, trong
khi đó với Population Based là khởi tạo bầy đàn - một tập cá thể tìm kiếm.
1.3 Giải thuật Vortex Search
Giải thuật tìm kiếm xoáy Vortex Search (VS) được hai đồng tác giả Berat Doğan, Tamer Ölmez nghiên
cứu và xuất bản[5][13] thuộc lớp giải thuật Single-Solution Based của họ giải thuật Metaheuristics. VS
ngoài các điểm mạnh như thời gian thực thi nhanh và tốc độ hội tụ cao còn có các vấn đề về bẫy cục bộ
địa phương.
Dưới đây là đoạn mã giã Psuedo-Code cho lớp giải thuật Single-Solution Based họ giải thuật
Metaheuristics:
Input:
Khởi tạo cá thế giải pháp ban đầu s0;
Bộ đếm thế hệ, ban đầu t = 0;
Repeat
Phát sinh tập cá thể ứng viên C(st) dựa vào cá thể st;
Chọn cá thể ứng viên tốt nhất st: st+1=Select(C(st));
st+1 = best(st, st+1);
Cập nhật thế hệ mới t = t + 1;
Until Thỏa điều kiện dừng;
Output: Giải pháp tối ưu st.
Single-Solution đại diện cho lời giải bài toán, các giải thuật họ Single-Solution Based Metaheuristics
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
5
gây dựng một cá thể Single-Solution ban đầu và làm tốt dần lên qua các thế hệ. Tại mỗi thế hệ, giải thuật
phát sinh ra tập các cá thể giải pháp ứng viên theo một quy luật nào đó dựa vào Single-Solution và chọn
ra ứng viên tốt nhất cho thế hệ đó, nếu ứng viên này tốt hơn lời giải bài toán hiện hành thì được bầu chọn
thay thế làm lời giải bài toán.
Ý tưởng này áp dụng chung cho các giải thuật phát triển dựa trên Single-Solution Based
Metaheuristics. Các giải thuật Single-Solution Based (Pattern Search (PS), Random Search (RS), Vortex
Search (VS)…) phát triển Single-Solution dựa vào việc đưa ra quy luật phát sinh tập ứng viên như thế
nào.
Giải thuật VS sử dụng quy luật phân phối chuẩn Gaussian-Distribution để phát sinh ra tập cá thể ứng
viên. Phân bố Gaussbảo đảm rằng xác xuất để phát sinh ra cá thể ứng viên tìm kiếm ở gần vị trí gần tâm
là cao hơn xác xuẩt phát sinh cá thể ở xa tâm tìm kiếm.
Dưới đây là đoạn mã giả Psuedo-Code giải thuật VS:
Inputs:
Khởi tạo µ0 tâm tìm kiếm ban đầu;
Khởi tạo r0 bán kính tìm kiếm ban đầu;
Khởi tạo giá trị f(sbest ) = inf hàm mục tiêu toàn cục;
Khởi tạo bộ đếm lặp, ban đầu t = 0;
Repeat
Phát sinh tập cá thể ứng viên Ct(s) sử dụng quy luật phân bố Gauss dựa vào tâm
tìm kiếm µt;
Điều chỉnh các cá thể Ct(s) ngoài phạm vi vào vùng tìm kiếm;
Chọn giải pháp s* tốt nhất từ tập ứng viên;
IF s* tốt hơn sbest
THEN
ELSE
Cặp nhật sbest = s*;
Giữ sbest
;
END
Cập nhật tâm tìm kiếm µt = sbest
Giảm bán kính tìm kiếm rt+1 cho thế hệ t+1;
Tăng thế hệ tìm kiếm t = t + 1;
;
Until: Đạt số vòng lặp tối đa của giải thuật;
Output: Giá trị tối ưu f(sbest) giải thuật tìm được.
Dưới đây là các công thức được sử dụng cho giải thuật VS:
ꢂꢃꢃꢄꢅꢆꢇꢈꢇꢉ + ꢆꢊꢋꢄꢅꢆꢇꢈꢇꢉ
(1)
(2)
ꢀꢁ =
2
(
)
ꢎꢏꢐ ꢂꢃꢃꢄꢅꢆꢇꢈꢇꢉ − ꢎꢑꢒ(ꢆꢊꢋꢄꢅꢆꢇꢈꢇꢉ)
ꢌꢁ ≈ ꢍꢁ =
2
ꢕ
ꢕ
ꢕ
ꢕ
ꢕ
ꢕ
(
)
ꢌꢏꢒꢗ ꢘꢙꢙꢚꢌꢛꢑꢎꢑꢜ − ꢛꢝꢞꢚꢌꢛꢑꢎꢑꢜ + ꢛꢝꢞꢚꢌꢛꢑꢎꢑꢜ ; ꢓꢔ < ꢛꢝꢞꢚꢌꢛꢑꢎꢑꢜ
ꢓꢔꢕ = ꢖ
ꢓꢔꢕ ; ꢛꢝꢞꢚꢌꢛꢑꢎꢑꢜꢕ ≤ ꢓꢔꢕ ≤ ꢘꢙꢙꢚꢌꢛꢑꢎꢑꢜꢕ
(3)
ꢕ
ꢕ
ꢕ
ꢕ
(
)
ꢌꢏꢒꢗ ꢘꢙꢙꢚꢌꢛꢑꢎꢑꢜ − ꢛꢝꢞꢚꢌꢛꢑꢎꢑꢜ + ꢛꢝꢞꢚꢌꢛꢑꢎꢑꢜ ; ꢓꢔ ≥ ꢘꢙꢙꢚꢌꢛꢑꢎꢑꢜ
Trong đó ꢓꢔꢕ là giá trị đặc trưng thứ i của cá thể thứ k.
1
ꢌ = ꢍꢁ. ꢠ ꢡ . ꢢꢏꢎꢎꢏꢑꢒꢣꢑꢒꢤ(ꢐ, ꢏꢟ)
ꢟ
(4)
(5)
ꢐ
ꢜ
ꢏꢟ = ꢏꢁ −
ꢥꢏꢐꢦꢒꢜ
1
1
ꢙ(ꢧ|ꢀ, ∑ ) =
ꢚꢐꢙ ꢫ− (ꢧ − ꢬ)ꢭ∑ꢮꢯ(ꢧ − ꢬ)ꢰ
2
(6)
(7)
ꢨ(2ꢩ)ꢪ|∑|
ꢱ
[ ]
∑ = ꢍ . ꢦ
ꢪꢲꢪ
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
6
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
1.4 Lý thuyết Chaos
Lý thuyết Chaos được Henri Poincaré[15] phát hiện khi nghiên cứu về chuyển động của một tập đối
tượng. Bài toán đặt ra là cho biết vị trí hiện tại và quy luật chuyển động, xác định vị trí của tập đối tượng
tại một thời điểm trong tương lai. Gọi x là vị trí hiện tại của đối tượng, giả sử đối tượng chuyển động theo
một hàm tác động còn gọi là hàm quy luật g, khi đó hàm quy luật chuyển động có dạng: xt+1 =g(xt); t ∈ N.
Trong đó t + 1 là thời điểm kế tiếp thời điểm t.
Khi nghiên cứu để xây dựng hệ thống dự báo từ những thông số đầu vào (vị trí hiện tại x0, các quy luật
- tham số mô tả hàm f) có thể tiên đoán được kết quả trong tương lai (ứng dụng trong nghiên cứu dự báo),
các nhà nghiên cứu đã phát hiện ra rằng ngoài đa số hàm quy luật có thể tiên đoán kết quả tương lai (hàm
hội tụ về 1 giá trị hoặc vô cực) còn tồn tại những hàm rất nhạy cảm với đầu vào khiến cho kết quả rất hỗn
độn trong một khoảng giá trị (không tiên đoán được).
Một hàm chuyển động Chaos có tính chất hỗn độn trong một khoảng xác định T là một ánh xạ liên tiếp
từ T lên chính nó mà không tiên đoán được tương lai. Có nghĩa là không tiên đoán được sau một khoảng
ꢴ
( )
thời gian N thì chuyển động quay trở lại vị trí xuất phát ꢳ = ꢢ (ꢢꢵ… ꢢ ꢳ ꢶ). Các hàm số Chaotic map
được xây dựng là hàm có ánh xạ hỗn độn trong khoảng (0,1).
Lý thuyết Chaos được ứng dụng trong các hệ thống tính toán có yếu tố ngẫu nhiên tham gia. Ứng dụng
lý thuyết Chaos với việc cải tiến quy luật hình thành yếu tố ngẫu nhiên là một hướng nghiên cứu trong
những năm gần đây cho các giải thuật tìm kiếm tối ưu[1][4][5].
2 ĐỀ XUẤT GIẢI THUẬT CHAOTIC VORTEX SEARCH
Tìm hiểu về giải thuật VS cho thấy, việc nghiên cứu đề xuất giải thuật mới hay cải tiến các giải thuật họ
Single-Solution Based Metaheuristic chính là việc phát hiện mới hay cải tiến các quy luật phát sinh tập
ứng viên.
Những nghiên cứu ứng dụng lý thuyết Chaos vào cải tiến giải thuật Metaheuristic[1][3][4] cho thấy sự
kết hợp Chaotic vào quy luật phát sinh làm cho giải thuật mới có kết quả tốt hơn hơn dựa trên một số tiêu
chí đánh giá. Từ việc nghiên cứu ứng dụng và cải tiến giải thuật VS, chúng tôi đề xuất giải thuật Chaotic
Vortex Search (CHAOVS) dựa vào việc bổ sung quy luật Chaos vào hàm quy luật phát sinh tập ứng viên.
Hàm Chaotic được chọn là Bernoulli Map, được định nghĩa như sau:
s(n+1)= fB(s(n))
Với điều kiện khởi tạo s(0) [-1,1] và fB là một ánh xạ chaotic fB: [-1,1][-1,1] được định nghĩa:
ꢱ
ꢯꢮꢷ
ꢷꢸꢯ
ꢓ +
; −1 ≤ ꢓ < ꢹ
fB(s)=ꢖꢷꢸꢯ
ꢱ
ꢯꢮꢷ
ꢯꢮꢷ ꢓ −
; ꢹ ≤ ꢓ ≤ 1
ꢯꢸꢷ
Trong đó tham số (-1,1). Giá trị s(0) và được sử dụng cho mô phỏng kết quả là s(0) = 0.5 và = 0.8.
2.1 Quy luật phát sinh tập ứng viên Cs giải thuật VS
Gọi μ0 là tâm tìm kiếm ban đầu, μt là tâm tìm kiếm thế hệ thứ t.
Khi đó tâm ꢀꢁ = [ꢬ10, ꢬ02, … , ꢬ0ꢺ], D là số chiều không gian tìm kiếm
ꢛꢝꢞꢚꢌꢛꢑꢎꢑꢜꢻꢸꢼꢽꢽꢾꢿꣀꢕꣁꢕ
ꢻ
Trong đó: ꢬꢁꢕ =
;
ꢱ
[lowerlimiti, upperlimiti] là ràng buộc cận dưới và cận trên không gian chiều thứ i. Các cận dưới và cận
trên trên tất cả các chiều không gian với bộ hàm chuẩn Benchmark được thiết lập giá trị chung lowerlimit
và upplimit (xem bảng 4).
Tại mỗi thế hệ tìm kiếm, sử dụng hàm quy luật phân phối chuẩn phát sinh ma trận CPsize,D có Psize dòng
(kích thước quần thể) mỗi dòng chứa các giá trị số ngẫu nhiên theo quy luật phân phối Gauss (dựa theo
công thức số (6), (7)) có giá trị trung bình Mean bằng 0, phương sai bằng 1:
ꣃꢯꢯ
⋯
⋱
ꣃꢯ꣄
⋮
C = ꣂ ⋮
ꣃꢯꣅꢕꢾ ⋯ ꣃ꣄ꣅꢕꢾ
Ma trận C được sử dụng như một mặt nạ tìm kiếm để xây dựng ma trận công cụ tìm kiếm Ct cho tâm
tìm kiếm Mean bằng 0 độ lệch chuẩn ꢌ (là bán kính tìm kiếm thế hệ t):
ꢟ
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
7
ꢌ ꣃꢯ
⋯
⋱
ꢌ ꣃ꣄
ꢟ
ꢟ
ꢯ
ꢯ
ꢟ = ꣂ
⋮
⋮
ꢌ ꣃꢯ
⋯ ꢌ ꣃ꣄
ꢟ
ꢟ
ꣅꢕꢾ
ꣅꢕꢾ
Trong đó bán kính ban đầu ꢌꢁ được tính theo công thức (2):
(
)
ꢎꢏꢐ ꢘꢙꢙꢚꢌꢛꢑꢎꢑꢜ − ꢎꢑꢒ(ꢛꢝꢞꢚꢌꢛꢑꢎꢑꢜ)
ꢌꢁ =
2
Bán kính tìm kiểm được điều chỉnh giảm dần qua các thế hệ theo công thức điều chỉnh:
ꢌ = ꢌꢁ. ꢯ . ꢢꢏꢎꢎꢏꢑꢒꢣꢑꢒꢤ(ꢐ, ꢏꢟ); Với ꢏꢁ = 1 ꢤà ꢏꢟ = 1 −
;
ꢟ
ꢟ
ꢲ
ꢲ꣎꣏ꢟ
MaxInt là số lượng thế hệ giải thuật thực hiện tìm kiếm. Tham số x được hiểu như độ uốn của hệ số
giảm bán kính. (Tham số x được sử dụng cho mô phỏng giải thuật là x = 0.1)
Ma trận công cụ tìm kiếm Ct được dịch chuyển tới vị trí tâm tìm kiếm thực sự (với tâm tìm kiếm ꢬꢟꢮꢯ
sử dụng để phát sinh tập ứng viên thế hệ t):
ꢬꢟꢯꢮꢯ + ꢌ ꣃꢯ
⋯
⋱
ꢬꢟꢯꢮꢯ + ꢌ ꣃ꣄
ꢟ
ꢯ
ꢟ
ꢯ
C(st) =
ꣂ
ꢬ
⋮
⋮
+ ꢌ ꣃꢯ
⋯ ꢬꢟ꣄ꢮꢯ + ꢌ ꣃ꣄
ꣅꢕꢾ
ꢟꢮꢯ
ꢟ
ꢟ
ꣅꢕꢾ
ꣅꢕꢾ
Trong đó ꢬꢟꢮꢯ = [ꢬ1ꢜ−1, ꢬꢜ2−1, … , ꢬꢜꢺ−1
thế hệ mới C(st).
] là tâm tìm kiếm hiện tại sử dụng cho phát sinh tập ứng viên ở
Đặt ꢓꢔꢕ = ꢬꢟꢕꢮꢯ + ꢌ ꣃꢕꢔ; các cá thể nếu vi phạm ràng buộc về chiều không gian thứ i (ràng buộc cận
ꢟ
dưới và cận trên) sẽ được thực hiện điều chỉnh theo công thức (3).
Sau khi thực hiện điều chỉnh các cá thể vi phạm, ta có tập cá thể ứng viên thế hệ t giải thuật VS (gọi là
CVS(st) ):
ꢓꢯꢯ
⋯
⋱
ꢓꢯ꣄
⋮
CVS(st) = ꣂ ⋮
ꢓꣅꢯꢕꢾ ⋯ ꢓꣅ꣄ꢕꢾ
CVS(st) là một ma trận Psize×D trong đó Psize là kích thước quần thể và D là số chiều không gian. Trong
đó ꢓꢕ = (ꢓꢕꢯ ꢓꢕꢱ, … , ꢓꢕ꣄)ꢭ chính là cá thể ứng viên thứ i trong tập quần thể Psize cá thể.
,
2.2 Quy luật phát sinh tập ứng viên Cs giải thuật CHAOVS
Sử dụng hàm Bernoulli map, phát sinh ma trận sử dụng để xây dựng quy luật phát sinh tập ứng viên
mới:
ꢣꢯꢯ
⋯
⋱
ꢣꢯ꣄
⋮ trong đó các ꢣꢕ là các giá trị số Chaotic phát sinh từ
Bernoulli_map(Psize, D) = ꣂ ⋮
꣐
ꢣꣅꢯꢕꢾ ⋯ ꢣꣅ꣄ꢕꢾ
hàm Bernoulli map.
Chúng tôi thực hiện lai ghép với CVS(st) để tạo ra quy luật phát sinh tập ứng viên mới:
ꢓꢯꢯꢣꢯꢯ
⋮
⋯
⋱
ꢓꢯ꣄ꢣꢯ꣄
⋮
CCHAOVS(st) =
ꣂ
ꢓꣅꢯꢕꢾꢣꣅꢯꢕꢾ ⋯ ꢓꣅ꣄ꢕꢾꢣꣅ꣄ꢕꢾ
3
KẾT QUẢ THỰC NGHIỆM
3.1 Đầu vào giải thuật
Để kiểm tra kết quả thực nghiệm để so sánh đối chiếu giải thuật cũ, chúng tôi kiểm chứng trên đầu vào
là 20 hàm số lấy từ bộ dữ liệu Benchmark Function[16]. Kiểm chứng thực thi giải thuật được thực hiện
trên phần mềm MATLAB R2013a, cấu hình máy CPU: Intel Core I5 5300u 2.3GHz, bộ nhớ đệm 3MB
Cache, RAM: 8GB - DDR3 1600MHz.
Bộ 20 hàm kiểm chứng được chọn ngẫu nhiên nhưng chứa các đặc điểm khác nhau trong bộ hàm chuẩn
Benchmark: U-Unimodal (Hàm đơn cực trị), M-Multimodal (Hàm đa cực trị), S-Seperable (Hàm phân tách
được), N-Non_Seperable (Hàm không phân tách được).
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
8
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
Bảng 1: 20 Hàm Benchmark kiểm chứng kết quả giải thuật dựa vào U: Unimodal, M: Multimodal, S: Separable, N:
Non-Separable
C C:
Characteristics
Func.
F1
Name
Sphere
Quartic
Mô tả
꣏
ꢧ = ꣑ (ꢐꢕ)ꢱ
( )
US
ꢕ꣒ꢯ
꣏
ꢧ = ꣑ (ꢑꢐꢕ)꣓ + random[0,1)
( )
F2
US
ꢕ꣒ꢯ
ꢱ
ꢱ
F3
F4
Easom
UN
( )
(
)
(
)
(
)
ꢧ = − ꢣꢝꢓ ꢐꢯ ꢣꢝꢓ ꢐꢱ ꢚꢐꢙ(−(ꢐꢯ − ꢩ) − ꢐꢱ − ꢩ
)
ꢱ
ꢱ
ꢱ
ꢱ
ꢱ
ꢱ
( ) )
(
)
(
)
(
)
(
ꢧ = 100 ꢐꢯ − ꢐꢱ + ꢐꢯ − 1 + ꢐ꣔ − 1 + 90 ꢐ꣔ − ꢐ꣓
ꢱ
Colville
Trid6
UN
((
)
(
)ꢱ)
+ 10.1 ꢐꢱ − 1 + ꢐ꣓ − 1
+ 19.8 ꢐꢱ − 1 ꢐ꣓ − 1
(
)(
)
꣏
꣏
ꢱ
( )
(
)
F5
F6
F7
UN
UN
UN
ꢧ = ꣑
ꢐꢕ − 1 − ꣑ ꢐꢕꢐꢕꢮꢯ
ꢕ꣒ꢯ
꣏
ꢕ꣒ꢱ
꣏
꣏
ꢧ = ꣑ ꢐꢕꢱ + (꣑ 0.5ꢑꢐꢕ)ꢱ + (꣑ 0.5ꢑꢐꢕ)꣓
( )
Zakharov
ꢕ꣒ꢯ
ꢕ꣒ꢯ
ꢕ꣒ꢯ
꣏
꣏
Schwefel 1.2
( )
ꢐ = ꣑
| |
ꢐꢕ + ꣕
| |
ꢐꢕ
ꢕ꣒ꢯ
ꢕ꣒ꢯ
ꢮꢯ
ꢱ꣘
1
1
F8
F9
Foxholes
Rastrigin
MS
MS
( )
ꢧ = ꣖
+ ꣑
꣙
ꢱ
500
∑
꣐꣒ꢯ ꣗ + ꢕ꣒ꢯꢵꢐꢕ − ꢏꢕ꣐ ꢶ6
꣏
ꢐ = ꣑ [ꢐꢕꢱ − 10 ꢣꢝꢓ 2ꢩꢐꢕ + 10]
( )
(
)
ꢕ꣒ꢯ
꣏
ꢱ
ꢧ = − ꣑ ꢓꢑꢒ(ꢐꢕ)(ꢓꢑꢒ(ꢑꢐꢕ / ꢩ))ꢱꣁ
( )
Michalewicz2
F10
F11
MS
ꢕ꣒ꢯ
m = 10
1
Six Hump
Camel Back
ꢧ = 4ꢐꢯ − 2.1ꢐꢯ + ꢐꢯ + ꢐꢯꢐꢱ − 4ꢐꢱꢱ + 4ꢐꢱ꣓
3
ꢱ
꣓
MN
( )
꣘
꣘
( )
ꢧ = ꢠ꣑
(
)
(
)
ꢑ ꢣꢝꢓꢵ ꢑ + 1 ꢐꢯ + ꢑꢶꢡ ꢠ꣑
ꢑ ꢣꢝꢓꢵ ꢑ + 1 ꢐꢱ
ꢕ ꣒ ꢯ
ꢕ ꣒ ꢯ
F12
Shubert
MN
MN
+ ꢑꢶꢡ
ꢱ
(
)
1 + ꢐꢯ + ꢐꢱ + 1
( )
ꢧ =
.
ꢱ
ꢱ
(
)
19 − 14ꢐꢕ + 3ꢐꢯ − 14ꢐꢱ + 6ꢐꢯꢐꢱ + 3ꢐꢱ
F13
Goldstein-Price
Shekel5
ꢱ
(
)
30 + 2ꢐꢯ − 3ꢐꢱ
ꢱ
ꢱ
(
)
18 − 32ꢐꢕ + 12ꢐꢯ + 48ꢐꢱ − 36ꢐꢯꢐꢱ + 27ꢐꢱ
꣘
꣓
( )
ꢧ = − ꣑
F14
F15
F16
MN
MN
MN
꣑
ꢵꢐ꣐ − ꢏꢕ꣐ ꢶ ꢵꢐ꣐ − ꢏꢕ꣐ ꢶꢭ + ꢣꢕꢮꢯ
ꢕ꣒ꢯ
꣐꣒ꢯ
꣏
ꢱ
꣏
(꣑
ꢐꢕꢔ) − ꣠ꢔ
Powersum
Hartman3
( )
ꢧ = ꣑
ꢔ ꣒ ꢯ
ꢕ ꣒ ꢯ
꣓
꣔
ꢣꢕ exp ꣖− ꣑
ꢏꢕ꣐ ꢵꢐ꣐ − ꢙꢕ꣐ ꢶꢱ꣙
( )
ꢧ = − ꣑
ꢕ ꣒ ꢯ
꣐ ꣒ ꢯ
꣏
1
ꢒ
1
ꢐꢕꢱ )
( )
꣡
ꢧ = −20exp(−0.2
꣑
ꢕ ꣒ ꢯ
F17
Ackley
MN
MN
꣏
− exp( ꣑
ꢒ
cos(2ꢩꢐꢕ)) + 20 + ꢚ
ꢕ ꣒ ꢯ
10ꢓꢑꢒꢱ ꢩ꣢ꢯ
(
)
ꢩ
ꢒ
꣏ ꢮ ꢯ
( )
ꢧ =
ꢖ
ꢱ꣣
ꢱ
ꢱ
(꣢ꢕ − 1) 1 + 10ꢓꢑꢒ ꢩ꣢ꢕꢸꢯ + ꣢꣏ − 1
[
(
)]
(
)
+ ꣑
ꢕ ꣒ ꢯ
꣏
F18
Penalized
( )
ꢘ ꢐꢕ, 10,100,4
+ ꣑
ꢕ ꣒ ꢯ
1
(
)
꣢ꢕ = 1 + ꢐꢕ + 1
4
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
9
꣤ ꢐꢕ − ꢏ ꣁ, ꢐꢕ > ꢏ
0, − ꢏ ≤ ꢐꢕ ≤ ꢏ
(
)
(
)
ꢘ ꢐꢕ, ꢏ, ꣤, ꢎ = ꢖ
꣤ −ꢐꢕ − ꢏ ꣁ, ꢐꢕ < −ꢏ
(
)
ꣁ
꣏
꣏
1
ꢵꢐ − ꢏꢕ꣐ ꢶꢱ)ꢣꢝꢓ(ꢩ ꣑ (ꢐ꣐
( )
ꢧ = − ꣑ ꢣꢕ(ꢚꢐꢙ(−
꣑
Langerman5
꣐
F19
MN
MN
ꢩ
ꢕ꣒ꢯ
꣐꣒ꢯ
꣐꣒ꢯ
− ꢏꢕ꣐)ꢱ))
꣏
ꢱ
( )
ꢧ = ꣑
(
)
꣥ꢕ − ꣦ꢕ
ꢕ꣒ꢯ
꣏
Fletcherpowell10
꣥ꢕ = ꣑ ꢵꢏꢕ꣐ꢓꢑꢒ + ꣠ꢕ꣐ ꢣꢝꢓꢹ꣐ꢶ; ꣦ꢕ
F20
꣐
꣐꣒ꢯ
꣏
= ꣑ ꢵꢏꢕ꣐ꢓꢑꢒꢐ꣐ + ꣠ꢕ꣐ ꢣꢝꢓꢐ꣐ꢶ
꣐꣒ꢯ
Để đánh giá khách quan giải thuật CHAOVS so với giải thuật VS nguyên bản, cả hai giải thuật sử dụng
cùng các tham số đầu vào và cùng các tham số đầu vào các hàm sử dụng để kiểm chứng giải thuật (xem
bảng 2 và bảng 3).
Bảng 2: Các tham số đầu vào giải thuật
Parameter
Variable name
Value
50
Số cá thể ứng viên
Số thế hệ
Psize
maxIter
30000
Bảng 3: Các tham số đầu vào hàm kiểm chứng giải thuật
Func.
F1
Name
Lowerlimit
Upperlimit
Dim
Sphere
-100
-1.28
-100
-10
-36
-5
100
1.28
100
10
30
30
2
F2
Quartic
F3
Easom
F4
Colville
4
F5
Trid6
36
6
F6
Zakharov
Schwefel 1.2
Foxholes
10
10
30
2
F7
-100
-65.536
-5.12
0
100
65.536
5.12
F8
F9
Rastrigin
30
2
F10
F11
F12
F13
F14
F15
Michalewicz2
Six Hump Camel Back
Shubert
-5
5
2
-10
-2
10
2
Goldstein-Price
Shekel5
2
2
0
10
4
Powersum
0
4
4
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
10
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
F16
F17
F18
F19
F20
Hartman3
Ackley
0
-32
-50
0
1
3
32
50
10
30
30
5
Penalized
Langerman5
Fletcherpowell10
10
-
3.2 Kết quả mô phỏng
Số liệu ở bảng 5 là bảng tổng hợp kết quả đối chiếu thực thi giải thuật CHAOVS và VS:
Bảng 4: Bảng tổng hợp số liệu kiểm chứng kết quả giải thuật
CHAOVS
Std
VS
Std
Run =
30.000
Mean
Best
Mean
Best
F1
F2
4.81958E-33
0.005177838
8.6119E-33
4.64173E-35
0.001938333
5.65858E-25 2.06199E-24 9.32348E-28
0.008928602 0.004382526 0.002712584
0.002357641
F3
-1
0
-1
-1
0
-1
F4
3.69103E-10
-50
7.13386E-10
4.08389E-14
9.80624E-43
2.75272E-09
1.16624E-16
18.17844465
9.03362E-16
6.04589E-16
3.61826E-14
1.59267E-15
2.606047823
0.000141825
2.61169E-15
0.450418703
1.97398E-13
-50
2.39655E-09 6.59171E-09 3.74019E-14
F5
-50
5.19466E-14
1.3095E-35
-50
F6
1.88195E-43
2.61934E-09
0.998003838
74.29008899
-1.80130341
-1.031628453
-186.7309088
3
9.67224E-51
9.28824E-11
0.998003838
39.79830178
-1.80130341
6.35407E-36
3.23658E-44
F7
8.23833E-05 7.18908E-05 5.80718E-06
0.998003838 1.23698E-16 0.998003838
24.67497051 10.01251071 1.989918114
-1.80130341 9.03362E-16 -1.80130341
F8
F9
F10
F11
F12
F13
F14
F15
F16
F17
-1.031628453 -1.031628453 6.1849E-16 -1.031628453
-186.7309088 -186.7309088 4.12208E-14 -186.7309088
3
3
2.05668E-15
-10.15319968 -10.15319968 6.14463E-15 -10.15319968
3.40091E-07 0.000191344 0.000137016 4.1363E-07
-3.862782148 -3.862782148 2.53907E-15 -3.862782148
2.22045E-14 9.69299E-14 5.54126E-14 5.06262E-14
3
-8.900922997
0.000139549
-3.862782148
0.10827178
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
11
F18
F19
F20
5.481639022
-1.408932528
13.49358084
9.703396842
0.207328704
36.43413327
3.9261E-31
-1.499999223 -1.410832488 0.202791383 -1.499999223
4.21614E-08 23.47632067 63.71754452 7.80379E-05
2.444523822 3.201759124 9.25384E-28
Bảng số liệu so sánh các tiêu chí rút ra từ bảng tổng hợp kết quả, trong đó dấu +, =, - thể hiện
CHAOVS có kết quả tốt hơn, ngang bằng và xấu hơn VS.
Bảng 5: Bảng tổng hợp so sánh trên các tiêu chí đánh giá
CHAOVS&VS
Run = 30.000
Mean
+
+
=
+
=
+
+
=
-
Std
+
+
=
+
+
+
+
+
-
Best
+
+
=
-
F1
F2
F3
F4
F5
=
+
+
=
-
F6
F7
F8
F9
F10
F11
F12
F13
F14
F15
F16
F17
F18
F19
F20
=
=
=
+
-
=
+
+
+
-
=
=
-
-
=
=
=
+
+
=
+
+
=
-
-
-
-
-
-
-
-
+
+
Kết quả bảng 5 cho thấy ngoài một số hàm tương đồng về kết quả so sánh trên các tiêu chí đánh giá (F1,
F2, F3, F6, F7, F9, F10, F20), các hàm còn lại có sự khác nhau như hàm F4 thắng trên tiêu chí giá trị bình
quân Mean, tiêu chí độ lệch chuẩn nhưng lại thua ở tiêu chí về giá trị min tốt nhất Best.
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
12
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
Từ bảng tổng hợp so sánh tiêu chí giá trị bình quân, độ lệch chuẩn và giá trị tối ưu tốt nhất chúng tôi rút
ra được bảng 6 tổng kết kết quả mô phỏng hai giải thuật.
Bảng 6: Bảng tổng hợp kết quả
CHAOVS&VS
(+/=/-)
Run = 30.000
Mean
Std
Best
2/0/0
2/2/1
0/2/1
3/5/2
7/9/4
US
2/0/0
2/0/0
4/1/0
1/1/1
4/2/6
11/2/7
UN
3/2/0
MS
0/2/1
MN
3/3/4
Total
8/7/5
Kết quả cho thấy dựa vào tiêu chí giá trị bình quân Mean, giải thuật CHAOVS tốt hơn VS với 8 hàm so
với 5 của VS. Tiêu chí giá trị tối ưu tốt nhất Best của CHAOVS khá tương đồng với VS.
4 KẾT LUẬN
Trong bài báo này, chúng tôi đã đưa ra các tóm lược lý thuyết về các vấn đề và giải quyết bài toán tối
ưu toàn cục, lý thuyết hỗn độn Chaos, giải thuật VS ứng dụng cho bài toán tối ưu toàn cục. Chúng tôi đã
đưa ra một cách tiếp cận mới để cải tiến giải thuật VS bằng cách ứng dụng lý thuyết Chaos và đề xuất giải
thuật mới Chaotic Vortex Search Algorithm và đã đạt được những kết quả nhất định. Những kết quả này là
cơ sở để chúng tôi tiếp tục ứng dụng những hàm Chaos khác và kiểm chứng thực nghiệm để tiếp tục đi sâu
vào hướng nghiên cứu đề xuất cải tiến giải thuật VS.
TÀI LIỆU THAM KHẢO
[1]
Sheikholeslami, R., and A. Kaveh. "A survey of chaos embedded meta-heuristic algorithms." Int J Optim
Civil Eng 3.4 (2013): 617-33..
[2]
Rothlauf, Franz. Design of modern heuristics: principles and application. Springer Science & Business
Media, 2011.
[3]
Li, Jun-wei, Yong-mei Cheng, and Ke-zhe Chen. "Chaotic particle swarm optimization algorithm based on
adaptive inertia weight." The 26th Chinese Control and Decision Conference (2014 CCDC). IEEE, 2014.
[4]
Applications. Vol 37, pp. 5682–5687, 2010.
[5] Doğan B., Ölmez T. "A new Metaheuristic for numerical function optimization: Vortex Search algorithm,"
Information Sciences. Vol 293, pp. 125-145, ISSN 0020-0255, 1 February 2015.
[6] Eberhart, Russell, and James Kennedy. "Particle swarm optimization." Proceedings of the IEEE
international conference on neural networks. Vol. 4. 1995.
[7] Zhao, Shi-Zheng, et al. "Dynamic multi-swarm particle swarm optimizer with local search for large scale
Bilal Alatas, "Chaotic bee colony algorithms for global numerical optimization," Expert Systems with
global optimization." 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational
Intelligence). IEEE, 2008.
[8]
Xing, Bo, and Wen-Jing Gao. "Introduction to Computational Intelligence." Innovative Computational
Intelligence: A Rough Guide to 134 Clever Algorithms. Springer, Cham, 2014. 3-17.
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
GIẢI THUẬT CHAOTIC VORTEX SEARCH CHO BÀI TOÁN TỐI ƯU TOÀN CỤC
13
[9]
Mitchell, Melanie, "An Introdution to Genetic Algorithms," Cambridge, MA: MIT Press, ISBN
9780585030944, 1996.
[10]
Granville, Vincent, Mirko Krivánek, and J-P. Rasson. "Simulated annealing:
A proof of
convergence." IEEE transactions on pattern analysis and machine intelligence 16.6 (1994): 652-656.
[11]
parameter system," Automation and Remote Control. Vol 24 (10), pp. 1337–1342, 1963.
[12] Hooke R., Jeeves T. A. "Direct search” solution of numerical and statistical problems,'' Journal of the
Association for Computing Machinery (ACM). Vol 8 (2), pp. 212–229, 1961.
[13] Doğan B., Ölmez T. "Modified Off-lattice AB Model for Protein Folding Problem Using the Vortex Search
Algorithm," International Journal of Machine Learning and Computing. Vol. 5(4), pp. 329-333, 2015.
[14] Dang, Binh Thanh, Minh Cong Vo, and Tung Khac Truong. "Social spider algorithm-based spectrum
Rastrigin L.A.. "The convergence of the random search method in the extremal control of a many
allocation optimization for cognitive radio networks." International Journal of Applied Engineering Research 12.13
(2017): 3879-3887.
[15]
Diacu, Florin, and Philip Holmes. Celestial encounters: the origins of chaos and stability. Vol. 22.
Princeton University Press, 1999.
[16]
Liang, J. J., B. Y. Qu, and P. N. Suganthan. "Problem definitions and evaluation criteria for the CEC 2014
special session and competition on single objective real-parameter numerical optimization." Computational
Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological
University, Singapore 635 (2013).
Ngày nhận bài: 29/03/2019
Ngày chấp nhận đăng: 03/01/2020
© 2020 Trường Đại học Công nghiệp thành phố Hồ Chí Minh
11 trang
21460
Free
Bạn đang xem tài liệu "Giải thuật Chaotic Vortex Search cho bài toán tối ưu toàn cục", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giai_thuat_chaotic_vortex_search_cho_bai_toan_toi_uu_toan_cu.pdf
