ĐẠI HỌC THÁI NGUN
TRƯỜNG ĐẠI HỌC CƠNG NGHỆ THƠNG TIN VÀ TRUYỀN THƠNG LỤC TRỌNG HIẾU GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG

ĐẠI HỌC THÁI NGUN
TRƯỜNG ĐẠI HỌC CƠNG NGHỆ THƠNG TIN VÀ TRUYỀN THƠNG LỤC TRỌNG HIẾU GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG
TRONG BÀI TỐN TỐI ƯU HĨA KHẨU PHẦN
THỨC ĂN CHĂN NI

CHUN 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. Phạm Thanh Hà Số hóa bởi Trung tâm Học liệu –ĐHTN />ii

LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tơi.
Các kết quả nêu trong luận văn là trung thực và chưa từng được ai cơng
bố trong bất kỳ cơng trình nào Thái Ngun, ngày 12 tháng 04 năm 2014
Tác giả luận văn
Lục Trọng Hiếu
Số hóa bởi Trung tâm Học liệu –ĐHTN />iii


Số hóa bởi Trung tâm Học liệu –ĐHTN />v

MỤC LỤC
MỞ ĐẦU 1
Chương 1.CÁC KHÁI NIỆM CƠ BẢN VỀ GIẢI THUẬT DI TRUYỀN 3
1.1. Mở đầu 3
1.2. Các khái niệm cơ bản của giải thuật di truyền 4
1.2.1. Giới thiệu chung 4
1.2.2. Giải thuật di truyền đơn giản 5
Chương 2.VẤN ĐỀ BIỂU DIỄN NHIỄM SẮC THỂ TRONG GIẢI THUẬT
DI TRUYỀN 11
2.1. Phương pháp biểu diễn nhiễm sắc thể bằng mã hóa nhị phân 11

thuộc vào sự hiểu biết về mơi trường, y tế, sự quản lý, và dinh
dưỡng. Tuy nhiên, thực ăn gia súc chiếm từ 60 đến 70% của tổng chi
phí của chăn ni lợn. [5]
Vì vậy trong chăn ni cơng nghiệp, hầu hết trang trại cần phải lập khẩu
phần thức ăn cho lợn càng rẻ càng tốt. Năng lượng, chất béo, protein, khống
chất và vitamin phải được cung cấp và cân bằng để đáp ứng các u cầu về
tiêu chuẩn dinh dưỡng của lợn. Ngồi ra, một số trang trại ni lợn có các
loại lợn ni khác nhau do đó cần chế độ dinh dưỡng khác nhau. [5,6]
Bài tốn lập khẩu phần thức ăn cho lợn là bài tốn tối ưu về giá thành
nhưng phải đảm bảo các tiêu chuẩn dinh dưỡng. Xét về tổng thể đây là bài
tốn tối ưu với nhiều ràng buộc.
Giải thuật di truyền là một trong những kỹ thuật tìm kiếm tối ưu giúp ta
giải quyết được những vấn đề đã đặt ra ở trên, nó cho phép ta tìm kiếm lời
giải tối ưu trên các khơng gian lớn, ngun tắc cơ bản của giải thuật di truyền
là mơ phỏng q trình chọn lọc của tự nhiên. Cho đến nay lĩnh vực nghiên
cứu về giải thuật di truyền đã thu được nhiều thành tựu, giải thuật di truyền
được ứng dụng trong nhiều lĩnh vực phức tạp, các vấn đề khó có thể giải
quyết được bằng phương pháp thơng thường [3,4].
Với những khả năng tiềm tàng của giải thuật di truyền đã là động lực và
lý do chính để tác giả chọn đề tài “Giải thuật di truyền và ứng dụng trong bài
tốn tối ưu hóa khẩu phần thức ăn chăn ni”.
Mục tiêu của đề tài
- Nghiên cứu các khái niệm cơ bản của giải thuật di truyền
Số hóa bởi Trung tâm Học liệu –ĐHTN />2

- Nghiên cứu một số phương pháp biểu diễn nhiễm sắc thể trong giải
thuật di truyền và các tốn tử di truyền tương ứng
- Ứng dụng giải thuật di truyền để giải quyết bài tốn tối ưu hóa khẩu
phần thức ăn chăn ni.
Phạm vi của đề tài

dần bị diệt chủng.
Mơi trường tự nhiên ln biến đổi, nên cấu trúc nhiễm sắc thể cũng thay
đổi để thích nghi với mơi trường, và ở thế hệ sau ln có độ thích nghi cao
hơn ở thế hệ trước. Cấu trúc này có được nhờ vào sự trao đổi thơng tin ngẫu
nhiên với mơi trường bên ngồi hay giữa chúng với nhau.
Dựa vào đó các nhà khoa học máy tính xây dựng nên một giải thuật tìm
kiếm tinh tế dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hóa, gọi là giải
thuật di truyền.
Các ngun lý cơ bản của giải thuật được tác giả Holland đề xuất lần đầu
vào năm 1962. Nền tảng tốn học của giải thuật GA được tác giả cơng bố
trong cuốn sách “Sự thích nghi trong các hệ thống tự nhiên và nhân tạo” xuất
bản năm 1975.
Giải thuật GA được xem như một phương pháp tìm kiếm có bước chuyển
Số hóa bởi Trung tâm Học liệu –ĐHTN />4

ngẫu nhiên mang tính tổng qt để giải các bài tốn tối ưu hố [1,3,4].
1.2. Các khái niệm cơ bản của giải thuật di truyền
1.2.1. Giới thiệu chung
Giải thuật GA ,[3,4] thuộc lớp các giải thuật tìm kiếm tiến hố. Khác với
phần lớn các giải thuật khác tìm kiếm theo điểm, giải thuật GA thực hiện tìm
kiếm song song trên một tập được gọi là quần thể các lời giải có thể.
Thơng qua việc áp dụng các tốn tử di truyền, giải thuật GA tráo đổi
thơng tin giữa các cực trị và do đó làm giảm thiểu khả năng kết thúc giải thuật
tại một cực trị địa phương. Trong thực tế, giải thuật GA đã được áp dụng
thành cơng trong nhiều lĩnh vực.
Giải thuật GA lần đầu được tác giả Holland giới thiệu vào năm 1962. Giải
thuật GA mơ phỏng q trình tồn tại của các cá thể có độ phù hợp tốt nhất
thơng qua q trình chọn lọc tự nhiên, sao cho khi giải thuật được thực thi,
quần thể các lời giải tiến hố tiến dần tới lời giải mong muốn.
Giải thuật GA duy trì một quần thể các lời giải có thể của bài tốn tối ưu

của từng chuỗi cá thể. Giá trị độ phù hợp của từng cá thể sau đó được dùng để
tính tốn xác suất chọn lọc.
Sơ đồ chọn lọc trong giải thuật SGA là sơ đồ chọn lọc tỷ lệ. Trong sơ đồ
chọn lọc này, cá thể có độ phù hợp
i
f
có xác suất chọn lựa
N
j
jii
ffp
1
/
, ở đây N là số cá thể có trong quần thể.
Số hóa bởi Trung tâm Học liệu –ĐHTN />6

Tốn tử lai ghép trong giải thuật SGA là tốn tử lai ghép một điểm cắt.
Giả sử chuỗi cá thể có độ dài L (có L bít), tốn tử lai ghép được tiến hành qua
hai giai đoạn là:
+ Hai cá thể trong quần thể bố mẹ được chọn một cách ngẫu nhiên với
phân bố xác suất đều.
+ Sinh một số ngẫu nhiên j trong khoảng [1, L - 1] . Hai cá thể con được
tạo ra bằng việc sao chép các ký tự từ 1 đến j và tráo đổi các ký tự từ j + 1 đến
L.

thuật SGA, quần thể con được sinh ra từ quần thể hiện tại thơng qua 3 tốn tử
là chọn lọc, lai ghép và đột biến thay thế hồn tồn quần thể hiện tại và trở
thành quần thể hiện tại của thế hệ tiếp theo.
Sơ đồ tổng thể của giải thuật được thể hiện qua thủ tục GSA() trình bày
dưới đây.
Thủ tục SGA() /* Giải bài tốn tối ưu */
{ k = 0;
// Khởi tạo quần thể P
0
một cách ngẫu nhiên.
khởi_tạo (P
k
);
// Tính giá trị hàm mục tiêu cho từng cá thể.
tính_hàm_mục_tiêu (P
k
);
// Đặt lời giải của giải thuật bằng cá thể có giá trị hàm mục tiêu tốt nhất.
X
best
= tốt_nhất (P
k
);
do { // Chuyển đổi giá trị hàm mục tiêu thành giá trị độ phù hợp và
// tiến hành chọn lọc tạo ra quần thể bố mẹ P
parent

P
parent
= chọn_lọc (P

if ( obj (X) > obj (X
best
) ) X
best
= X;
} while ( k < G); /* Tiến hành G thế hệ */
return (X
best
); /* Trả về lời giải của giải thuật GA*/
}
Giải thuật di truyền phụ thuộc vào bộ 4 (N, p
c
, p
m
, G), trong đó:
N - số cá thể trong quần thể; p
c
- xác suất lai ghép; p
m
- xác suất đột biến;
G - số thế hệ cần tiến hố
Đó chính là các tham số điều khiển của giải thuật SGA. Cá thể có giá trị
hàm mục tiêu tốt nhất của mọi thế hệ là lời giải cuối cùng của giải thuật SGA.
Quần thể đầu tiên được khởi tạo một cách ngẫu nhiên.
Ví dụ: xét bài tốn tìm max của hàm f(x) = x
2
với x là số ngun trên đoạn
[0,31].
Để sử dụng giải thuật di truyền ta mã hóa mỗi số ngun x trong đoạn
[0,31] bởi một số nhị phân có độ dài 5, chẳng hạn chuỗi 11000 là mã của số

3
0 1 0 0 0 8
64
0
4
1 0 0 1 1 19
361
1

Thực hiện q trình lai ghép với xác suất lai ghép p
c
=1, cả 4 cá thể sau
chọn lọc đều được lai ghép.
Kết quả lai ghép được cho trong bảng sau, trong bảng này, chuỗi thứ nhất
được lai ghép với chuỗi thứ hai với điểm lai ghép là 4, hai chuỗi còn lại được
lai ghép với nhau với điểm ghép là 2.
Bảng 1.2. Minh họa q trình lai ghép
Quần thể sau
chọn lọc
Điểm
ghép
Quần thể sau
lai ghép
x
Độ thích nghi
f(x)=x
2

0 1 1 0|1
4

đã “tốt lên” rất nhiều.
Số hóa bởi Trung tâm Học liệu –ĐHTN />11

Chương 2
VẤN ĐỀ BIỂU DIỄN NHIỄM SẮC THỂ
TRONG GIẢI THUẬT DI TRUYỀN
2.1. Phương pháp biểu diễn nhiễm sắc thể bằng mã hóa nhị phân
Giải thuật di truyền với biểu diễn nhiễm sắc thể bằng mã hóa nhị phân đã
được đề cập sơ bộ trong chương 1. Trong phần này chúng ta sẽ tìm hiểu sâu
hơn về giải thuật di truyền này thơng qua một bài tốn tối ưu số [4].
Khơng làm mất tính tổng qt, ta giả định bài tốn tối ưu là bài tốn tìm
cực đại của hàm nhiều biến f. Bài tốn tìm cực tiểu hàm g chính là bài tốn
tìm cực đại hàm f = -g, hơn nữa ta có thể giả định hàm mục tiêu f có giá trị
dương trên miền xác định của nó, nếu khơng ta có thể cộng thêm một hằng số
C dương
Cụ thể bài tốn được đặt ra như sau: Tìm cực đại một hàm k biến f(x
1
, ,
x
k
): R
k
R. Giả sử thêm là mỗi biến x
i
có thể nhận giá trị trong miền D
i
=
[a
i
,b

được biểu diễn bằng một chuỗi nhị phân có chiều dài
m
i
. Biểu diễn như trên rõ ràng thoả mãn điều kiện về độ chính xác theo u
cầu. Cơng thức sau tính giá trị thập phân của mỗi chuỗi nhị phân biểu diễn
biến x
i
12
)(
2
i
m
ii
ii
ab
stringdecimalax
(1.1)

Số hóa bởi Trung tâm Học liệu –ĐHTN />12

Trong đó hàm decimal(string
2
) cho biết giá trị thập phân của chuỗi nhị
phân đó.
Bây giờ, mỗi nhiễm sắc thể (là một lời giải) được biểu diễn bằng một
chuỗi nhị phân có chiều dài
k
i
i
mm

+ Tính độ thích nghi eval(v
i
) của mỗi nhiễm sắc thể v
i
(i = 1,…, pop_size)
+ Tìm tổng giá trị thích nghi tồn quần thể:
sizepop
i
i
vevalF
1
)(
(1.2)
+ Tính xác suất chọn p
i
cho mỗi nhiễm sắc thể v
i
, (i = 1,…, pop_size):

Fvevalp
ii
/)(

(1.3)
Số hóa bởi Trung tâm Học liệu –ĐHTN />13

+ Tính vị trí xác suất q
i
của mỗi nhiễm sắc thể v
i
Hình 2.1. Minh họa bánh xe rulet
Bây giờ ta có thể áp dụng phép tốn di truyền: kết hợp và lai ghép các cá
thể trong quần thể vừa được chọn từ quần thể cũ như trên.
eval(v
n
)

eval(v
2
)
eval(v
1
)
Số hóa bởi Trung tâm Học liệu –ĐHTN />14

Một trong những tham số của giải thuật là xác suất lai p
c
. Xác suất này
cho ta số nhiếm sắc thể pop_size p
c
mong đợi, các nhiễm sắc thể này được
dùng trong tác vụ lai tạo. Ta tiến hành theo cách sau đây:
Đối với mỗi nhiễm sắc thể trong quần thể mới:
+ Phát sinh ngẫu nhiên một số r trong khoảng [0,1]
+ Nếu r p

b
2
…b
pos
c
pos+1
…c
m
) và (c
1
c
2.
…c
pos
b
pos+1
…b
m
)
Phép tốn kế tiếp là phép đột biến, được thực hiện trên cơ sở từng bit. Một
tham số khác của giải thuật là xác suất đột biến p
m
, cho ta số bit đột biến
p
m
m pop_size mong đợi. Mỗi bit (trong tất cả các nhiễm sắc thể trong quần
thể) có cơ hội bị đột biến như nhau, nghĩa là đổi từ 0 thành 1 hoặc ngược lại.
Vì thế ta tiến hành theo cách sau đây:
Đối với mỗi nhiễm sắc thể trong quần thể hiện hành (nghĩa là sau khi lai)
và đối với mỗi bit trong nhiễm sắc thể:

18

Miền của biến x
2
có chiều dài là 1.7, điều kiện chính xác đòi hỏi đoạn
[4.1,5.8] cần được chia thành các khoảng có kích thước bằng nhau là
1.7 10000 khoảng, điều này nghĩa là cần 15 bit làm thành phần cuối của
nhiễm sắc thể: 2
14
17000 2
15

Chiều dài tồn bộ nhiễm sắc thể (vectơ lời giải) là m =18+15 = 33
Để cực đại hố hàm f bằng giải thuật di truyền ta tạo ra một quần thể có
pop_size = 20 nhiễm sắc thể. Cả 33 bit trong tất cả các nhiễm sắc thể đều
được khởi tạo ngẫu nhiên
Giả sử sau tiến trình khởi tạo ta có quần thể sau đây:
v
1
= (100110100000001111111010011011111)
v
2
= (111000100100110111001010100011010)
v
3
= (000010000011001000001010111011101)
v
4
= (100011000101101001111000001110010)
Số hóa bởi Trung tâm Học liệu –ĐHTN />16

= (010010011000001010100111100101001)
v
15
= (111011101101110000100011111011110)
v
16
= (110011110000011111100001101001011)
v
17
= (011010111111001111010001101111101)
v
18
= (011101000000001110100111110101101)
v
19
= (000101010011111111110000110001100)
v
20
= (101110010110011110011000101111110)
Trong giai đoạn lượng giá ta giải mã từng nhiễm sắc thể và tính giá trị
hàm thích nghi từ các giá trị (x
1
, x
2
) mới giải mã, ta có
eval(v
1
) = f(6.084492,5.652242) = 26.019600
eval(v
2

eval(v
12
) = f(9.356179,4.239457) = 15.011619
eval(v
13
) = f(11.134646,5.378671) = 27.316702
eval(v
14
) = f(1.335944,5.151378) = 19.876294
eval(v
15
) = f(11.089025,5.054515) = 30.060205
eval(v
16
) = f(9.211598,4.993762) = 23.967227
eval(v
17
) = f(3.367514,4.571343) = 13.696165
eval(v
18
) = f(3.843020,5.158226) = 15.414128
eval(v
19
) = f(-1.746635,5.395584) = 20.095903
eval(v
20
) = f(7.935998,4.757338) = 13.666916
Rõ ràng nhiễm sắc thể v
15
mạnh nhất và nhiễm sắc thể v