ĐẠ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

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Ngun - 2014

Số hóa bởi Trung tâm Học liệu

ĐHTN

/>

ĐẠ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


Thái Ngun, tháng 04 năm 2014
Học viên thực hiện

Lục Trọng Hiếu

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


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
2.2. Giải thuật di truyền với biểu diễn thực ................................................. 26
2.2.1 Biểu diễn nhiễm sắc thể bằng số thực ............................................. 26
2.2.2 Nhóm tốn tử đột biến ...................................................................... 27
2.2.3. Nhóm tốn tử lai tạo......................................................................... 29
2.3. Giải thuật di truyền với biểu diễn nhiễm sắc thể bằng mã hóa ký tự 32
2.3.1. Bài tốn người du lịch...................................................................... 32
2.3.2. Mã hóa ký tự và các kỹ thuật ghéo chép mới ............................... 32
Chương 3.ỨNG DỤNG GIẢI THUẬT DI TRUYỀN TRONG BÀI TỐN
TỐI ƯU HĨA KHẨU PHẦN THỨC ĂN CHĂN NI............................... 37
3.1. Bài tốn tối ưu hóa khẩu phần thức ăn chăn ni ............................... 37
3.2. Vấn đề tối ưu số và xử lý ràng buộc ..................................................... 43
3.2.1 Bài tốn tối ưu số ............................................................................... 43
3.2.2 Đột biến đồng dạng ........................................................................... 47
3.2.3 Đột biến biên ...................................................................................... 47
3.3.1 Đột biến khơng đồng dạng ............................................................... 47
3.3.2 Lai số học ........................................................................................... 48
3.3.3 Lai đơn giản ....................................................................................... 48

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

1.1. Mở đầu
Giải thuật di truyền (Gennetic Algorithm, viết tắt là GA) là giải thuật tìm
kiếm, chọn lựa các giải pháp tối ưu để giải quyết các bài tốn khác nhau dựa
trên cơ chế chọn lọc tự nhiên của ngành di truyền học.
Trong cơ thể sinh vật, các gen liên kiết với nhau theo cấu trúc dạng chuỗi
gọi là nhiễm sắc thể, nó đặc trưng cho mỗi lồi và quyết định sự sống còn của
cơ thể đó.
Một lồi muốn tồn tại phải thích nghi với mơi trường, cơ thể sống nào
thích nghi với mơi trường hơn thì sẽ tồn tại và sinh sản với số lượng ngày
càng nhiều hơn, trái lại những lồi khơng thích nghi với mơi trường sẽ dần
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

/>



/>

5

Sau khi tiến hành q trình lai ghép, giải thuật GA mơ phỏng một q
trình khác trong tự nhiên là q trình đột biến, trong đó các gien của các cá
thể con tự thay đổi giá trị với một xác suất nhỏ.
Tóm lại, có 6 khía cạnh cần được xem xét, trước khi áp dụng giải thuật
GA để giải một bài tốn [1,3,4], cụ thể là:
+ Mã hố lời giải thành cá thể dạng chuỗi.
+ Hàm xác định giá trị độ phù hợp.
+ Sơ đồ chọn lọc các cá thể bố mẹ.
+ Tốn tử lai ghép.
+ Tốn tử đột biến.
+ Chiến lược thay thế hay còn gọi là tốn tử tái tạo.
Có nhiều lựa chọn khác nhau cho từng vấn đề trên. Phần tiếp theo sẽ đưa
ra cách lựa chọn theo J.H. Holland khi thiết kế phiên bản giải thuật GA đầu
tiên. Giải thuật này được gọi là giải thuật di truyền đơn giản (SGA).
1.2.2. Giải thuật di truyền đơn giản
Trong giải thuật di truyền của mình J. H. Holland sử dụng mã hố nhị
phân để biểu diễn các cá thể, lý do là phần lớn các bài tốn tối ưu hố đều có
thể được mã hố thành chuỗi nhị phân khá đơn giản [3].
Hàm mục tiêu, hàm cần tối ưu, được chọn làm cơ sở để tính độ phù hợp
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 f i có xác suất chọn lựa
pi


1 0 0 1 1 1 0 1 1 0

0 1 0 0 1 1 1 1 1 0

0 1 0 0 1 1 1 1 0 1

Vị trí lai
ghép

Hình 1.1. Sơ đồ lai ghép 1 điểm cắt
Điều đáng lưu ý là giải thuật GA khơng u cầu tốn tử lai ghép ln xảy
ra đối với hai cá thể bố mẹ được chọn. Sự lai ghép chỉ xảy ra khi số ngẫu
nhiên tương ứng với cặp cá thể bố mẹ được sinh ra trong khoảng [0, 1) khơng
lớn hơn một tham số pc (gọi là xác suất lai ghép). Nếu số ngẫu nhiên này lớn
hơn pc, tốn tử lai ghép khơng xảy ra. Khi đó hai cá thể con là bản sao trực
tiếp của hai cá thể bố mẹ.
Tiếp theo, J. H. Holland xây dựng tốn tử đột biến cho giải thuật SGA.
Tốn tử này được gọi là tốn tử đột biến chuẩn. Tốn tử đột biến duyệt từng
gien của từng cá thể con được sinh ra sau khi tiến hành tốn tử lai ghép và

Số hóa bởi Trung tâm Học liệu

ĐHTN

/>

7

tiến hành biến đổi giá trị từ 0 sang 1 hoặc ngược lại với một xác suất pm được
gọi là xác suất đột biến.

8

Pk = Pchild;
tính_hàm_mục_tiêu (Pk);
// Nếu giá trị hàm mục tiêu obj của cá thể tốt nhất X trong quần
// thể Pk lớn hơn giá trị hàm mục tiêu của Xbest thì thay thế lời giải
X = tốt_nhất (Pk);
if ( obj (X) > obj (Xbest) ) Xbest = X;
} while ( k < G); /* Tiến hành G thế hệ */
return (Xbest); /* 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, pc, pm, G), trong đó:
N - số cá thể trong quần thể; pc - xác suất lai ghép; pm - 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) = x2 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ố
ngun 24
Hàm thích nghi được xác định chính là hàm f(x)=x2
Quần thể ban đầu gồm 4 cá thể (kích thước quần thể n=4).

Số hóa bởi Trung tâm Học liệu

ĐHTN

/>