Genetic Algorithms and Knapsack 02 problem Lý Thanh Bình – TH46
Giải thuật gene
và
Bài toán chiếc ba lô loại 2
1
Genetic Algorithms and Knapsack 02 problem Lý Thanh Bình – TH46
I. Giới thiệu chung.
Xuất phát từ khái niệm lý thuyết Darwin của sự tồn tại thích hợp
nhất và được John Holland đưa ra lần đầu tiên vào năm 1975.
Thuật toán gene (GAs – Genetic Algorithms) là thuật toán tìm
kiếm, chọn lựa giải pháp tối ưu để giải quyết các bài toán khác
nhau dựa trên mô phỏng cơ chế tiến hoá của tự nhiên.
Trong cơ thể sinh vật, các gene liên kết với nhau theo cấu trúc
dạng chuỗi gọi là nhiễm sắc thể (Chromosomes), nó đặc trưng co
mỗi loài và quyết định sự sống còn của cơ thể đó. Trong tự nhiên
một loà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 tốt thì tồn tại và phát triển,
ngược lại với những loài không thích nghi với môi trường sống
sẽ bị đào loại bỏ và dần dần tuyệt chủng. Môi trường tự nhiên
thay đổ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 nên thế hệ sau luôn có độ thích nghi cao hơn thế
hệ trước. Dựa vào đó các nhà khoa học máy tính xây dựng nên
môi trường giải thuật tìm kiếm dựa trên cơ sở chọn lọc tự nhiên
và quy luật tiến hoá, gọi là giải thuật gene.
Năm 1989, Goldberg chỉ ra sự khác nhau chủ yếu giữa GAs và
phương pháp tối ưu truyền thống như sau:
- GAs sử dụng theo xác suất, không phải theo quyết định, để tìm
kiếm các quy tắc.
- GAs sử dụng các thông tin từ hàm mục tiêu, không sư dụng
thông tin biết được khác.
- Đăc trưng của GAs là sử dụng chính sự mã hoá của tập hợp

thích nghi.
- Toán tử lại ghép (Crossover):
o Hai cá thể cha mẹ trao đổi các Gen để tạo ra 2 cá thể con.
- Toán tử đột biến (Mutation):
o Một cá thể thay đổi 1 số Gen không theo quy luật để tạo ra thế hệ
mới.
3
Genetic Algorithms and Knapsack 02 problem Lý Thanh Bình – TH46
2. Cấu trúc cơ bản của GAs.
4
Cài đặt hàm
Procedure GA
begin
t := 0 ;
initialize P(t) ;
evaluate P(t) ;
while (not termination-condition) do
begin
t := t + 1 ;
select P(t) from P(t-1) ;
alter P(t) ;
evaluate P(t) ;
end;
end;
Genetic Algorithms and Knapsack 02 problem Lý Thanh Bình – TH46
a. Mã hoá (Encoding).
- Mã hoá nhị phân (Binary Encoding – BE):
o Là kiểu mã hoá thông dụng nhất bởi vì: nghiên cứu đầu tiên về
thuật toán Gen sử dụng kiểu mã hóa này và bởi vì nó đơn giản.
o Trong BE, mọi nhiễm sắc thể là chuỗi bits - 0 or 1.

o TE thường được dùng đối với các bìa tóan suy luận hoặc các cấu
trúc có thể biểu diễn bằng cây.
o Các phép lai ghép và đột biến đối với kiểu mã hóa này cũng
tương đối dễ thực hiện.
b. Khởi tạo quần thể.
- Thường được chọn random dựa vào yêu cầu bài toán.
5
Genetic Algorithms and Knapsack 02 problem Lý Thanh Bình – TH46
c. Hàm thích nghi.
- Hàm thích nghi định nghĩa tiêu chuẩn để xếp hạng các giả thuyết
tiềm ẩn và để chọn lọc chúng theo xác suất để đưa vào quần thể thế
hệ kế tiếp.
- Mỗi bài toán có một hàm thích nghi riêng.
d. Chọn lọc.
- Các nhiễm sắc thể được chọn từ quần thể là các cha cho lai ghép
(crossover).
- Theo thuyết tiến hoá của Darwin những cá thể tốt nhất sẽ được họn
để lai ghép.
- Có nhiều phương pháp lựa chọn như:
o Roulette Wheel Selection:
 

  !"#
 $%&''!'(
 )*!+, roulette wheel
 /0123131-44544-6%0
!37
 $89-:3131-44544-%+,;
<=-2->
 +,%0!37-0?&

Genetic Algorithms and Knapsack 02 problem Lý Thanh Bình – TH46
 I<Q(@+,";-RSTA!
+,L!3"->
 NL4-412FF.%;
+,D-2!377U9C2

 +,V"?;-1K+,V6-2
4%+,"?;-N+
31F#
o Elitism:
 /21F09W311%431*1K;
-"!"
 X'!'Elitism1'Y'1'ZP!
1*%!#F0
 ,'F8-2F21=!L!
 X'!'Elitism;:1[\K%A;:
L-"!
o Steady-State Selection.
 ,31"!@M?;%+,I0
1#21+,10
 $%+,V%0"'#?97 ;9]%!
+,10?Z@^
 XF8-2F213@M0
o Boltzman selection.
o …
e. Lai ghép và đột biến.
- Đây là 2 phép toán cơ bản của thuật toán gen. Sự hình thành luật
của GAs phụ thuộc rất nhiều vào 2 phép toán này.
- Kiểu và sự thể hiện của các toán tử này phụ thuộc vào kiểu mã hóa
và cũng phụ thuộc vào bài toán.

a. Mã hoá:
Đối với bài toán knapsack 02, do mỗi vật có thể được chọn nhiều lần nên
ta dùng mã hoá giá trị cho các nhiễm sắc thể.
– VD: Có 1 đoạn gen: 0498392
• Số 0 đầu tiên có nghĩa là vật 1 được chọn 0 lần.
• Số 4 thứ 2 có nghĩa là vật 2 được chọn 4 lần.
• ….
b. Khởi tạo quần thể.
Sau khi mã hoá ta được quần thể với các gen ngẫu nhiên nên sẽ có những
cá thể không thoả mãn yêu cầu đề bài là khối lượng. Những cá thể thoả
mãn sẽ được giữ lại tạo thành 1 quần thể mới. Quần thể này dung để chọn
lọc và lai ghép.
c. Hàm thích nghi.
9
• Đơn vị đ/c chuẩn bị hành
quân.
• Ngoài những quân dụng bắt
buộc phải mang theo, đ/c còn
phải chọn một số vật dụng
khác phải mang theo để phục
vụ sinh hoạt
• Tuy nhiên balo của đ/c có hạn
và chỉ để được một khối
lượng k. Giả sử 1 đồ dùng có
khối lượng w và giá trị sử
dụng c, 1 vật có nhiều số
lượng và có thể chọn nhiều
lần.
• Đ/c phải chọn đồ để bỏ vào
balo sao cho không vượt quá

Đối với bài toán mã hoá theo giá trị ta cộng hoặc trừ đi 1 số từ các giá
trị được chọn trong cá thể đột biến.
Về tỉ lệ đột biến: Nếu ta chọn tỉ lệ quá cao thì kết quả sẽ khó có thể hội
tụ được. Còn nếu quá thấp thì cũng sẽ có ít khả năng ảnh hưởng đến bài
toán.
Trong chương trình, ta lấy tỉ lệ đột biến mặc định là 1%.
g. Điều kiện dừng.
10
Genetic Algorithms and Knapsack 02 problem Lý Thanh Bình – TH46
Nếu đủ thời gian ta sẽ cho thuật toán chạy đến khi các cá thể không
thay đổi theo thời gian hoặc các cá thể sinh ra là giống hệt nhau.
Nếu không có đủ thời gian ta sẽ lấy kết quả tốt nhất trong thời gian
chạy thuật toán để làm lời giải cho bài toán.
Trong chương trình, tôi để mặc định là chạy 1000 lần thì dừng thuật
toán.
IV. Ưu và nhược điểm.
1. Ưu điểm.
- GAs có khả năng chạy song song.
- Ít bị rơi vào cực trị địa phương (Giải quyết bằng đột biến).
- Với cùng cách mã hoá có thể thay đổi hàm thích nghi.
- Khi đã có thuật toán gene cơ bản, chỉ cần viết 1 nhiễm sắc thể mới để
xử lý một bài toán khác.
2. Nhược điểm.
- Thời gian tính toán có thể chậm hơn các thuật toán khác.
- Quá trình tính toán có thể kết thúc bất cứ lúc nào, không có kế hoạch
trước.
- Giống như tiến hoá tự nhiên, cha mẹ tốt chưa chắc đã sinh ra con tốt.
Nên dùng giải thuật gene để giải bài toán này khi giữ lại những cá thể
tốt trong quần thể chưa chắc sau khi lai ghép đã sinh ra được cá thể tốt
hơn.