ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN QUANG LẬP
THUẬT TOÁN BẦY ĐÀN PSO, GIẢI THUẬT
DI TRUYỀN VÀ ỨNG DỤNG GIẢI CÁC BÀI TOÁN
TỐI ƢU ĐA MỤC TIÊU
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Ngƣời hƣớng dẫn khoa học: TS. VŨ VINH QUANG
Số hóa bởi trung tâm học liệu
ii
LỜI CAM ĐOAN
Em xin cam đoan luận văn tốt nghiệp: “Thuật toán bầy đàn PSO, giải thuật di
truyền và ứng dụng giải các bài toán tối ưu đa mục tiêu” do em tự thực hiện dưới sự
hướng dẫn của thầy giáo Vũ Vinh Quang. Các kết quả và số liệu hoàn toàn trung thực.
Ngoài các tài liệu tham khảo đã dẫn ra ở cuối luận văn em đảm bảo rằng
không sao chép các công trình hay luận văn tốt nghiệp của người khác. Nếu phát
hiện có sự sai phạm với điều cam đoan trên, em xin hoàn toàn chịu trách nhiệm.
1.3.8 Phương pháp trọng số 11
CHƢƠNG 2: CƠ SỞ THUẬT TOÁN DI TRUYỀN 13
2.1 Các khái niệm cơ bản 14
2.1.1 Cá thể, nhiễm sắc thể 14
2.1.2 Quần thể 14
2.1.3 Chọn lọc (Selection) 14
2.1.4 Lai ghép (Cross-over) 15
2.1.5 Đột biến (Mutation) 15
2.1.6 Mô hình GA 15
Số hóa bởi trung tâm học liệu
iv
2.1.7 Các tham số của GA 16
2.2 Cơ chế thực hiện GA 17
2.2.1 Mã hóa 17
2.2.2 Khởi tạo quần thể ban đầu 18
2.2.3 Xác định hàm thích nghi 19
2.2.4 Cơ chế lựa chọn 19
2.2.5 Các toán tử di truyền 20
2.3. Thuật toán di truyền kinh điển 22
2.3.1. Mã hóa 22
2.3.2. Toán tử chọn lọc 23
2.3.3. Toán tử lai ghép 24
2.3.4. Toán tử đột biến 25
2.3.5. Thuật toán di truyền mã hóa số thực (RCGA) 27
2.4 Thuật toán tối ưu bầy đàn PSO 33
2.4.1 Giới thiệu 33
2.4.2 Khái niệm về bầy đàn thông minh 34
2.4.3 Thuật toán PSO truyền thống 35
2.5 Một số kết quả cải tiến đối với PSO 43
Hình 2.3: Phân bố của
ci
j
x
31
Hình 2.4: Toán tử lai ghép SX 32
Hình 2.5: Mô tả cách thức tìm kiếm thức ăn của bầy kiến 34
Hình 2.6: Mô tả cách thức tìm đường của đàn chim 35
Hình 2.7: Bầy đàn với 10 cá thể trong không gian tìm kiếm 2 chiều 36
Hình 2.8: Quan hệ vị trí – vận tốc trong không gian 2 chiều 37
Hình 2.9: Một bầy đàn toàn cục và lân cận cục bộ 38
Hình 2.10: Các topology lân cận đơn giản 38
Hình 2.11:Chuyển động của cá thể 42
Hình 2.12: Áp dụng kỹ thuật làm lệch cho hàm (2.13) tại điểm
*
4.60095589x
, với λ=1 46
Hình 2.13 Áp dụng kỹ thuật làm lệch cho hàm (2.13) tại điểm
*
4.60095589x
,với λ=10 46
Hình 2.14:Áp dụng kỹ thuật làm lệch cho hàm (2.13) tại điểm
*
4.60095589x
,với λ=0.1. 47
Hình 2.15: Áp dụng kỹ thuật làm lệch cho hàm (2.14) tại điểm
*
()
2
x
MỞ ĐẦU
Trong thực tế, rất nhiều ngành khoa học phải giải quyết các bài toán tối ưu
đa mục tiêu đặc biệt là trong ngành kinh tế. Chẳng hạn, người chế tạo sản phẩm
thường phải đưa ra phương án sao cho vừa tiết kiệm vật liệu, chi phí sản xuất thấp
và lại muốn giá trị sản phẩm là cao nhất. Nghiên cứu giải bài toán tối ưu đa mục
tiêu là một vấn đề không đơn giản vì chưa chắc có lời giải thỏa mãn đồng thời các
mục tiêu đặt ra (thường là các mục tiêu đối nghịch như ví dụ trên) mà không vi
phạm các ràng buộc nào đó. Đã có nhiều phương pháp giải bài toán tối ưu đa mục
tiêu được đề xuất, việc nghiên cứu phát triển các phương pháp này và ứng dụng
chúng để giải quyết các bài toán thực tế là một vấn đề đang được quan tâm.
Trong nhiều bài toán tối ưu thực tế, việc trọng tâm là tìm vị trí cực tiểu toàn
cục của hàm mục tiêu giá trị thực f: E R, nghĩa là tìm điểm
*
xE
sao cho
*
( ) ( ),f x f x x E
với tập đóng
d
ER
, trong đó d là số chiều.
Đã có nhiều phương pháp tối ưu toàn cục (Global Optimization - GO) được
phát triển để giải quyết vấn đề như trên như: Mô phỏng việc luyện thép (Simulated
Annealing), Tabu search, Tính toán tiến hóa (Evolutionary computation). Về mặt lý
thuyết tổng quát, các phương pháp GO có tính hội tụ mạnh, hay ít ra về nguyên tắc
cũng dễ hiểu trong việc thực hiện và ứng dụng.
Tính toán tiến hóa (Evolutionary computation) là kỹ thuật đặc biệt trong số
các phương pháp GO. Phương pháp này làm việc trên một tập hợp những lời giải
tiềm năng, được gọi là quần thể (population) và tìm lời giải tối ưu thông qua việc
Số hóa bởi trung tâm học liệu
3
CHƢƠNG 1
MÔ HÌNH BÀI TOÁN TỐI ƢU
Trong chương này, luận văn sẽ trình bày một số kiến thức cơ bản về mô hình
tổng quát của bài toán tối ưu hóa, việc phân loại các bài toán tối ưu và một số
phương pháp giải bài toán tối ưu đa mục tiêu, các kiến thức của chương này được
tham khảo từ các tài liệu [1,2].
1.1 Mô hình bài toán tối ƣu hóa
1.1.1 Mô hình tổng quát
Tối ưu hóa là một trong những lĩnh vực quan trọng của toán học có ảnh
hưởng đến hầu hết các lĩnh vực khoa học, công nghệ và kinh tế và xã hội. Việc tìm
giải pháp tối ưu cho một bài toán thực tế nào đó chiếm một vai trò hết sức quan
trọng như việc tiến hành lập kế hoạch sản xuất hay thiết kế hệ thống điều khiển các
quá trình … Nếu sử dụng các kiến thức trên nền tảng của toán học để giải quyết các
được gọi là hàm mục tiêu, Các điều kiện (1.1) được gọi là
ràng buộc đẳng thức. Các điều kiện (1.2), (1.3) được gọi là ràng buộc bất đẳng thức.
Các điều kiện (1.4) được gọi là ràng buộc về dấu.
12
( , , , )
n
X x x x
là véc tơ thuộc
không gian
n
R
. Tập các véc tơ
X
thỏa mãn hệ ràng buộc lập nên một miền
D
được
Số hóa bởi trung tâm học liệu
4
gọi là miền phương án (hay miền chấp nhận được), mỗi điểm
XD
gọi là một
phương án. Một phương án
*
XD
làm cho hàm mục tiêu
()fX
đạt max (min) được
gọi là phương án tối ưu.
1.1.2 Phân loại bài toán tối ưu
Qui hoạch rời rạc: Bài toán tối ưu được gọi là qui hoạch rời rạc nếu miền
ràng buộc
D
là tập hợp rời rạc. Trong trường hợp riêng khi các biến chỉ nhận
giá trị nguyên thì ta có qui hoạch nguyên.
Qui hoạch đa mục tiêu: Nếu trên cùng một miền ràng buộc ta xét đồng thời
các hàm mục tiêu khác nhau.
Trong các lĩnh vực kinh tế kỹ thuật thì qui hoạch phi tuyến, qui hoạch tuyến tính
là những bài toán thường gặp.
1.2 Bài toán quy hoạch tuyến tính
Từ một số các mô hình trong thực tế, ta có mô hình tổng quát cho bài toán
quy hoạch tuyến tính như sau:
Xác định các biến
( 1,2, , )
j
x j n
sao cho:
j
1
( ) ax( )
n
j
j
F x c x M Min
ij 1
1
n
ji
j
D
. Phương án thỏa mãn điều kiện để hàm mục tiêu đạt
Max(min) được gọi là phương án tối ưu.
Dạng chính tắc:
j
1
()
n
j
j
F x c x Min
ij
1
n
ji
j
a x b i M
0( )
j
x j N
Dạng chuẩn tắc:
j
1
()
n
j
j
11 12 1
21 22 2
12
n
n
m m mn
a a a
a a a
A
a a a
,
1
2
n
x
x
X
x
,
1
2
m
b
b
()GX
được gọi là các biểu thức ràng buộc
+
X
là phương án của bài toán
Tập tất cả các phương án thỏa mãn hệ điều kiện ràng buộc được gọi là miền
phương án, phương án thỏa mãn điều kiện để
( ) ( ax)F X Min M®
được gọi là
phương án tối ưu.
Rõ ràng so đối với bài toán tối ưu 1 mục tiêu, việc tìm nghiệm của bài toán
tối ưu nhiều mục tiêu khó khăn hơn rất nhiều và đại đa số, chúng ta không thể xác
định được phương án tối ưu thật sự.
Sau đây chúng ta sẽ nghiên cứu một số phương pháp giải bài toán tối ưu đa
mục tiêu.
1.3.1 Phương pháp ràng buộc
Xét bài toán
( )
12
( ) ( ), ( ), , ( ) ,
( ) ( , ) 0.
p
F X f X f X f X Min
GX
=®
> = = < =Số hóa bởi trung tâm học liệu
7
k
x
tương ứng. Kí hiệu là
1 1 2 2
( ), ( ), , ( )
k k k
pp
f x f x f x
.
+ Sắp xếp p giá trị ứng với p mục tiêu vừa tính được ở trên vào bảng thỏa hiệp.
1
()
k
fx
2
()
k
fx
……
()
k
p
fx
1
x
….
….
….
….
p
x
1
()
p
fx
2
()
p
fx()
p
p
fx
+ Xác định số lớn nhất và nhỏ nhất trọng cột thứ k, kí hiệu lần lượt là
, ,( 1,2, , ).
kk
M m k p=
k k k k
t
L n M m t r
r
= + - = -
-
.
Bước 4: Ứng với mỗi giá trị của
k
L
, ta giải bài toán đơn mục tiêu tương ứng
và mỗi bài toán cho một nghiệm chấp nhận được. Trong những nghiệm này ta sẽ
chọn nghiệm tối ưu nhất.
1.3.2 Phương pháp tổng trọng số
( )
12
( ) ( ), ( ), , ( ) ,
( ) ( , ) 0.
p
F X f X f X f X Min
GX
=®
> = = < =
Ta chuyển bài toán trên thành bài toán
1 1 2 2
( ) w ( ) w ( ) w ( ) ,
( ) ( , ) 0.
pp
F X f X f X f X Min
và giải bài toán:
2
ax ( )M Y X
với
0
1 1 1
; ( )X D Y X Y YÎ ³ - D
Giả sử
*
2
Y
là giá trị tối ưu của bài toán này, chuyển sang bước 3
Bước 3: Căn cứ vào
0
2
Y
và
*
2
Y
buộc
2
Y
nhượng bộ lượng
2
YD
và giải bài toán:
3
ax ( )M Y X
k
M Y X
với
0 * *
1 1 1 2 2 2 1 1 1
; ( ) ; ( ) ; ; ( ) ;
k k k
X D Y X Y Y Y X Y Y Y X Y Y
- - -
Î ³ - D ³ - D ³ - D
Nghiệm của bài toán cuối cùng này được lấy làm nghiệm của bài toán ban đầu.
Số hóa bởi trung tâm học liệu
9
1.3.4 Phương pháp thoả hiệp
Bước 1: Giải k bài toán 1 mục tiêu riêng rẽ, giả sử nghiệm tối ưu là
( 1,2, . )
i
X i k=
.
Đặt
()
i i i
M Y X=
và đưa vào biến phụ
w
:
()
W
nhỏ hơn của
2
X
.
1.3.5 Phương pháp tìm nghiệm có khoảng cách nhỏ nhất đến nghiệm lý tưởng
Phương pháp này giả định có một nghiệm lý tưởng,
1
X
là tốt hơn
2
X
nếu
khoảng cách từ
1
X
đến nghiệm lý tưởng nhỏ hơn khoảng cách tương ứng của
2
X
Định nghĩa: Giả sử
1
X
,
2
X
Î
R
n
, khoảng cách giữa
Y X Y
a
-
å
Vấn đề xác định tham số
a
phụ thuộc vào từng bài toán.
1.3.6 Phương pháp giải theo dãy mục tiêu đã được sắp
Trong phương pháp này, thứ tự của các hàm mục tiêu thể hiện sự quan trọng
của các tiêu chuẩn, các mục tiêu xếp trước được ưu tiên hơn.
Bước 0: Sắp xếp thứ tự các mục tiêu
12
, , ,
k
Y Y Y
Bước 1: Giải bài toán
1
ax( ( ))M Y X
với
XDÎ
, ký hiệu
{ }
1 1 1
11
( ) axY ( ),D X Y X m X X D D= = Î ÍSố hóa bởi trung tâm học liệu
k k k k k
k
D X Y X m X X D D
= = Î Í
Ta có dãy bao hàm thức:
1
k
D D DÊ Ê Ê
. Khi đó tập các nghiệm thuộc
k
D
sẽ
thỏa mãn tính chất tối ưu của bài toán đa mục tiêu.
1.3.7 Phương pháp từng bước của Benayoun
Phương pháp này gần giống phương pháp tìm nghiệm xấp xỉ nghiệm lý
tưởng. Thường có hai biến dạng sau:
- Các độ lệch tương đối của hàm mục tiêu được gắn với một bộ trọng số.
Trọng số này được xác định dựa trên khoảng biến động của từng mục tiêu.
- Miền chấp nhận được của nó có thể thay đổi qua các bước giải
Hàm lợi ích và các quan hệ xác định như phương pháp tìm nghiệm xấp xỉ
nghiệm lý tưởng.
Bài toán cơ bản mà phương pháp này xét là:
*
()
i i i
M Y X d
Õ
:
1
12
1
1
*
()
ii
i
n
j
j
Mm
M
C
Với
i
j
C
là các hệ số của hàm mục tiêu thứ i. Đặt i=0 chuyển sang bước 3
Số hóa bởi trung tâm học liệu
11
Bước 3: Tính
1
1
i
D
+
1i
XD
( ) ( )
II
Y X Y X i
*
ii¹
*
*
( ) ( )
Ii
I
Y X Y X i
Coi
*
*
00
I
I
Với
*
ii¹
.
Số hóa bởi trung tâm học liệu
12
Về mặt thực tiễn, có thể xem các trọng số
i
p
là
tỷ lệ quy đổi thứ nguyên của
mục tiêu thứ i. Chẳng hạn quy đổi tất cả các mục tiêu về dạng tiền tệ thì
i
p
biểu
hiện cho số đơn vị tiền tệ của mục tiêu thứ i. Đây cũng là phương pháp quy đa mục
tiêu về một mục tiêu phụ thuộc tham số.
Kết luận: Nội dung chương 1 đã trình bày một số kiến thức cơ bản về mô
hình của bài toán tối ưu tổng quát, mô hình của bài toán tối ưu đa mục tiêu cùng
một số phương pháp giải. Các kiến thức này là cơ sở để trình bày các kết quả trong
chương 2 và chương 3 của luận văn.
các chương trình máy tính giải quyết một cách tối ưu một vấn đề cụ thể.
- Các hệ thống phân loại (Classifier Systems- CS): Các GA đặc biệt được
dùng trong việc học máy và việc phát hiện các quy tắc trong các hệ dựa trên các
quy tắc.
GA cũng như các thuật toán tiến hoá đều được hình thành dựa trên một quan
niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm
"Quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã
mang tính tối ưu". Quá trình tiến hoá thể hiện tính tối ưu ở chỗ thế hệ sau bao giờ
cũng tốt hơn thế hệ trước.
Số hóa bởi trung tâm học liệu
14
Sự hình thành và phát triển của GA trên thế giới có thể được điểm qua các
mốc thời gian quan trọng như sau:
Năm 1960, ý tưởng đầu tiên về Tính toán tiến hoá được Rechenberg giới
thiệu trong công trình “Evolution Strategies” (Các chiến lược tiến hoá). Ý tưởng
này sau đó được nhiều nhà nghiên cứu phát triển.
Năm 1975, Giải thuật gen do John Holland phát minh và được phát triển bởi
ông cùng với các đồng nghiệp và những sinh viên. Cuốn sách "Adaption in Natural
and Artificial Systems" (Sự thích nghi trong các hệ tự nhiên và nhân tạo) đã tổng
hợp các kết quả của quá trình nghiên cứu và phát triển đó.
Năm 1992, John Koza đã dùng GA để xây dựng các chương trình giải quyết
một số bài toán và gọi phương pháp này là “lập trình gen”.
Ngày nay GA càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu hoá,
một lĩnh vực có nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng
thường khó và chưa có giải thuật hiệu quả để giải .
2.1 Các khái niệm cơ bản
2.1.1 Cá thể, nhiễm sắc thể
Trong GA, một cá thể biểu diễn một phương án của bài toán. Trong trường
hợp tổng quát, một cá thể có nhiều NST (NST), ở đây ta quan niệm một cá thể chỉ
2.1.6 Mô hình GA
Với các khái niệm được giới thiệu ở trên, GA được mô tả bởi sơ đồ sau đây
Nhận các tham số
của bài toán
Khởi tạo quần thể
ban đầu
Tính giá trị thích nghi
Sinh sản
Lai ghép
Đột biến
Điều kiện
dừng
Kết
thúc
Bắt đầu
Lựa chọn giải pháp tốt
nhất
Hình 2.1: Sơ đồ mô tả GA
Số hóa bởi trung tâm học liệu
16
1. Xác lập các tham số ban đầu của bài toán.
2. Khởi tạo: Sinh ngẫu nhiên một quần thể gồm n cá thể (là n lời giải ban
đầu của bài toán).
3. Xác lập quần thể mới: tạo quần thể mới bằng cách lặp lại các bước sau
cho đến khi quần thể mới hoàn thành, bao gồm:
3.1 Tính độ thích nghi của mỗi cá thể.
3.2 Kiểm tra điều kiện kết thúc giải thuật.
3.3 Chọn lọc các cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng
Xác suất đột biến cho biết các gen của NST thay đổi thường xuyên như thế
nào. Nếu xác suất đột biến là p
m
, khi đó khả năng để mỗi gen của một NST bất kỳ bị
đột biến là p
m
. Toán tử đột biến có tác dụng ngăn ngừa GA rơi vào tình trạng cực trị
địa phương, tuy nhiên nếu thực hiện đột biến với xác suất quá cao sẽ biến GA thành
giải thuật tìm kiếm ngẫu nhiên.
Nhận xét:
Xuất phát từ sơ đồ thực hiện GA, chúng ta có thể có một số nhận xét như sau:
+ GA lập luận mang tính chất ngẫu nhiên để tìm giải pháp tối ưu cho những
vấn đề phức tạp, thay vì xác định như toán học giải tích. Tuy nhiên đây là hình thức
ngẫu nhiên có hướng dẫn bởi trị số thích nghi. Chính hàm thích nghi giúp GA tìm
giải pháp tối ưu trong rất nhiều giải pháp có thể có.
+ GA không để ý đến chi tiết vấn đề, trái lại chỉ chú ý đến giải pháp cho vấn đề,
hay tìm điều kiện tối ưu cho việc điều hành và phân nhóm những giải pháp có được.
+ GA được sử dụng đặc biệt cho những bài toán yêu cầu tìm kiếm tối ưu toàn
cục với không gian tìm kiếm lớn và không thể kiểm soát nhờ khả năng duyệt qua
không gian tìm kiếm đại diện mà không thực sự đi qua từng điểm của toàn bộ
không gian.
2.2 Cơ chế thực hiện GA
2.2.1 Mã hóa
Để có thể thực hiện GA, vấn đề đầu tiên là xuất phát từ bài toán thực tế, ta
cần phải mô tả các phương án của bài toán dưới một dạng nào đó (mô hình toán
học, tin học, …). Vấn đề mô tả đó được gọi là các phương pháp mã hóa. Thông
thường người ta sử dụng một trong các phương pháp như sau:
+ Mã hoá nhị phân
Mã hoá nhị phân là phương pháp mã hoá NST phổ biến nhất. Trong mã hoá
nhị phân, mỗi NST là một chuỗi nhị phân, mỗi bit trong nó có thể biểu diễn một đặc
Khởi tạo quần thể ban đầu là bước đầu tiên trong GA. Thông thường để khởi
tạo quần thể trong bài toán tối ưu, ta tạo ra một cách ngẫu nhiên các lời giải có thể
(thường là các lời giải thỏa mãn ràng buộc của bài toán nhưng chưa biết là đại
Copyright: Tài liệu đại học ©