MỤC LỤC
1
LỜI NÓI ĐẦU
Với khả năng hiện nay, máy tính đã giúp giải được rất nhiều bài toán khó mà
trước đây thường bó tay. Mặc dù vậy vẫn có một số lớn các bài toán thú vị mà chưa
có giải thuật hợp lý để giải chúng. Trong đó các bài toán tối ưu là những bài toán
thường gặp trong thực tiễn.
Bài toán tối ưu hóa tổ hợp có thể xem như bài toán tìm kiếm giải pháp tốt nhất
trong không gian vô cùng lớn các giải pháp. Khi không gian tìm kiếm nhỏ, những
phương pháp cổ điển như trên cũng đủ thích hợp, nhưng khi không gian tìm kiếm lớn
phải dùng kỹ thuật trí tuệ nhân tạo đặc biệt. Thuật giải di truyền (GA) là một trong
những kỹ thuật đó.
Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải
pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật
di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến
hóa như di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo.
Ngày nay, giải thuật di truyền được dùng phổ biến trong một số ngành như tin sinh
học, khoa học máy tính, trí tuệ nhân tạo, tài chính và một số ngành khác.
Bài toán xếp ba lô (một số sách ghi là bài toán cái túi) là một bài toán tối ưu hóa tổ
hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào
trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài
toán tương tự thường xuất hiện trong kinh doanh, toán tổ hợp, lý thuyết độ phức tạp
tính toán, mật mã học và toán ứng dụng.
Chính vì ứng dụng lớn của giải thuật di truyền( GA) và bài toán xếp ba lô, với sự
giúp đỡ của thầy Trần Thanh Hùng giáo viên bộ môn Giải thuật di truyền, chúng
em tiến hành đi tìm hiểu về giải thuật di truyền và ứng dụng của giải thuật di truyền
trong bài toán xếp ba lô với đề tài “Tìm hiều và ứng dụng của thuật giải di truyền trong
bài toán xếp ba lô”.
Sinh viên thực hiện:
Trần Quang Hợp.
MSSV: 0441060068.

thể nói về các cá thể (hay kiểu gen, cấu trúc) trong một quần thể, những cá thể này
cũng còn được gọi là chuỗi hay các nhiễm sắc thể.
Mỗi kiểu gen (ta gọi là một nhiễm sắc thể) sẽ biểu diễn một lời giải của bài toán
đang giải (ý tưởng của một nhiễm sắc thể cụ thể được người sử dụng xác định trước),
một tiến trình tiến hóa được thực hiện trên một quần thể các nhiễm sắc thể tương ứng
với một quá trình tìm kiếm lời giải trong không gian lời giải. Tìm kiếm đó cần cân
đối hai mục tiêu: Khai thác những lời giải tốt nhất và khảo sát không gian tìm kiếm.
Leo đồi là một ví dụ về chiến lược cho phép khai thác và cải thiện lời giải tốt nhất
hiện hành nhưng leo đồi lại bỏ qua việc khảo sát không gian tìm kiếm. Ngược lại, tìm
kiếm ngẫu nhiên là một ví dụ điển hình của chiến lược khảo sát không gian tìm
3
kiếm mà không chú ý đến việc khai thác những vùng đầy hứa hẹn của không gian.
Thuật toán di truyền (GA) là phương pháp tìm kiếm (độc lập miền) tạo được sự cân
đối đáng kể giữa việc khai thác và khảo sát không gian tìm kiếm.
Thực ra, GA thuộc lớp các thuật giải xuất sắc, nhưng lại rất khác những thuật giải
ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên. Khác biệt
quan trọng giữa tìm kiếm của GA và các phương pháp tìm kiếm khác là GA duy trì
và xử lý một tập các lời giải (ta gọi là một quần thể)
Theo đề xuất của giáo sư John Holland, một vấn đề bài toán đặt ra sẽ được mã hóa
thành các chuỗi với chiều dài bit cố định. Nói một cách chính xác là các thông số của
bài toán sẽ được chuyển đổi và biểu diễn lại dưới dạng các chuỗi nhị phân. Các thông
số này có thể là các biến của một hàm hoặc hệ số của một biểu thức toán học. Người
ta gọi các chuỗi bít này là mã genome ứng với mỗi cá thể, các genome đều có
cùng chiều dài. Nói ngắn gọn, một lời giải sẽ được biểu diễn bằng một chuỗi bít,
cũng như mỗi cá thể đều được quy định bằng gen của cá thể đó vậy. Như vậy, đối
với thuật giải di truyền, một cá thể chỉ có một gen duy nhất và mọt gen cũng chỉ
phục vụ cho một cá thể duy nhât. Do đó, gen chính là cá thể và cá thể chính là gen.
Ban đầu, ta sẽ phát sinh một số lượng lớn, giới hạn các cá thể có gen ngẫu nhiên -
nghĩa là phát sinh một tập hợp các chuỗi bit ngẫu nhiên. Tập các cá thể này được gọi
là quần thể ban đầu (initial population). Sau đó, dựa trên một hàm nào đó, ta sẽ xác

Cấu trúc của giải thuật di truyền như sau:
T=0
Initialize P(t)
evaluate structures in P(t)
While not end do
T= t + 1
Select C(t) from P(t - 1)
5
Recombine structures in C(t) forming C'(t)
Mutate structures in C' (t) forming C'' (t)
Evaluate structures in C''(t)
Replace P(t) from C''(t) and/or P (t - 1)
2. Các bước của giải thuật di truyền
2.1. Khởi tạo quần thể (initialize )
Quần thể đầu tiên được khởi tạo một cách ngẫu nhiên từ tập hợp những cá thể
riêng lẻ. Kích cỡ của quần thể đầu tiên phụ thuộc vào yếu tố tự nhiên của bài toán,
nhưng nhìn chung thì một bài toán có đến hàng trăm hay hàng nghìn giải pháp hợp lý.
Tập hợp những giải pháp hợp lý cho vấn đề được gọi là không gian tìm kiếm (search
space). Trước một bài toán áp dụng thuật toán di truyền, ta cần phải xác định rõ
nhiễm sắc thể và cá thể cho vấn đề, và thông thường đó sẽ là kết quả cuối cùng.
Việc phân tích sẽ dựa trên kết quả cơ bản tốt nhất.
Ví dụ:
v1:1 0 0 0 1 1 1
v2:1 1 1 1 0 0 0
v3:1 0 1 0 1 0 1
v4:1 1 0 0 0 1 1
v5:1 1 1 0 0 0 1
v6:0 1 0 1 1 1 0
2.2. Tính toán độ thích nghi(evaluate)
Các quá trình tiến hóa diễn ra trong vòng lặp While, tại thế hệ thứ t, thuật toán di

Rơi random càng nhiều xác suất rơi chủ yếu vào các phần lớn càng lớn. Từ đó xác
định được các nhiễm sắc thể tốt.
2.4. Quá trình sinh sản
Có hai loại thao tác sinh sản
- Phép lai tạo (Crossover): là quá trình hình thành nhiễm sắc thể mới trên cơ sở
nhiễm sắc thể cha mẹ bằng cách ghép một hay nhiều đoạn gen của hai hay nhiều
nhiễm sắc thể cha mẹ với nhau.
Có những phương pháp lai ghép sau:
- Lai ghép ánh xạ từng phần (PMX Partial Mapped Crossover).
- Lai ghép có trật tự (OX order Crossover).
- Lai ghép dựa trên vị trí (Position Based Crossover).
- Lai ghép dựa trên thứ tự (Order Base Crossover).
- Lai ghép có chu trình (CX cycle Crossover).
- Lai ghép thứ tự tuyến tính (LOX Linear order Crossover).
Phép lai tạo xảy ra với xác suất p
c
, được mô phỏng như sau:
7
Chọn ngẫu nhiên một hay nhiều cá thể bất kỳ trong quần thể. Giả sử các nhiễm sắc
thể của cha mẹ đều có m
gen.
Tạo một số ngẫu nhiên trong khoảng từ 1 đến m - 1 (được gọi là điểm lai). Điểm
lai chia các chuỗi cha mẹ có độ dài m thành hai nhóm chuỗi con với độ dài m
1
, m
2
hai chuỗi nhiễm sắc thể mới là m
11
+ m
12

trình tiến hóa tiếp theo.
Một thuật giải di truyền, giải một bài toán được cho phải có năm thành phần:
- Một cấu trúc dữ liệu biểu diễn không gian lời giải của bài toán.
- Phương pháp khởi tạo quần thể ban đầu P(0).
- Hàm định nghĩa độ thích nghi evaluate đóng vai trò môi trường.
- Các phép toán di truyền như đã mô phỏng trên.
- Và các tham số thuật toán di truyền sử dụng (kích thước, quần thể, xác suất
lai, đột biến…)
Điều kiện kết thúc
Thoát ra quá trình tiến hóa quần thể, dựa vào bài toán mà có các cách kết thúc
vấn đề khác nhau, một khi đã đạt đến mức yêu cầu. Một vài trường hợp thông thường
như sau:
- Kết thúc theo kết quả: một khi đạt đến mức giá trị yêu cầu thì chấm dứt ngay
quá trình thực hiện.
- Kết thúc dựa vào số thế hệ: chọn số thế hệ, quá trình sẽ dừng lại đúng ngay
số thế hệ đã qui định trước, không cần biết kết quả như thế
nào.
9
- Tính theo thời gian: Không cần biết đã bao nhiêu thế hệ hay kết quả thế nào,
chỉ cần dựa vào số giờ qui định mà kết thúc.
- Tổ hợp: dung nhiều phương án khác nhau cho vấn đề, chẳng hạn như: chạy
theo số thế hệ xong sau đó đánh giá cho chạy theo kết quả, hoặc ngược lại.
CHƯƠNG II - BÀI TOÁN XẾP BA LÔ
1. Giới thiệu
Bài toán xếp ba lô (một số sách ghi là bài toán cái túi) là một bài toán tối ưu hóa
tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào
trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài
toán tương tự thường xuất hiện trong kinh doanh, toán tổ hợp, lý thuyết độ phức tạp
tính toán, mật mã học và toán ứng dụng.
Bài toán xếp ba lô thường được giải bằng quy hoạch động, tuy chưa có một thuật

Tức là:
v1=10011010 (mã nhị phân 8 bit tương ứng với 8 đồ vật)
Đồ vật 1 được chọn.
Đồ vật 3 không được chọn.
Đồ vật 4 được chọn.
Đồ vật 5 được chọn.
Đồ vật 6 không được chọn.
Đồ vật 7 được chọn.
Đồ vật 8 không được chọn.
Áp dụng vào hàm ta sẽ được giá trị và khối lượng của lần chọn này là:
11
- Giá trị:
100x1+ 30x0+ 250x0+ 150x1+ 50x1+75x0+ 50x1+ 50x0 = 350
- Khối lượng:
5x1+ 3x0 +10x0 +6x1 +5x1 +5x0 +5x1 +4x1 +4x0 = 25 (thỏa mãn)
CHƯƠNG III - ỨNG DỤNG GIẢI THUẬT DI TRUYỀN TRONG
BÀI TOÁN XẾP BA LÔ
1. Tiếp cận giải thuật di truyền trong bài toán ba lô
Có 3 mặt hàng tiềm năng: A, B, C có khối lượng và giá trị tương ứng
A B C
Khối lượng 6 7 8
Giá trị 4 3 5
Khối lượng tối đa ba lô có thể chứa là: 13.
Hàm tính giá trị lớn nhất:
Điều kiện thỏa mãn:
X=0 or X=1, for i= 1, 2, …, n.
Từ 3 đồ vật được đưa ra ta có 8 trạng thái của ba lô như sau:
A B C Tổng khối lượng Tổng giá trị
0 0 0 0 0
0 0 1 8 5

cố gắng tìm phương án đúng nhất mà đi tìm các phương án gần đúng với phương án
đúng nhất, nhưng vẫn đảm bảo về thời gian thực hiện.
2. Sử dụng giải thuật di truyền để giải bài toán xếp ba lô
Để hiểu việc áp dụng giải thuật di truyền để giải bài toán ba lô như thế nào? Ta tiến
hành giải ví dụ về bài toán ba lô dưới đây:
2.1. Khởi tạo dữ liệu
13
Bài toán:
Cho bảng các đồ vật có khối lượng và giá trị tương ứng như sau:
1 2 3 4 5 6 7
Khối lượng 7 8 4 10 4 6 4
Giá trị 5 8 3 2 7 9 4
Khối lượng tối đa của ba lô có thể chứa là 22.
Sơ đồ bài toán xếp ba lô giải theo giải thuật di truyền như sau:
Điều kiện chấm dứt của sơ đồ là:
- 90% các NST của dân số có cùng độ thích nghi.
14
15
Kiểm tra tỷ lệ giống nhau của
độ thích nghi trong dân số
Khởi tạo dữ liệu( đồ vât, khối lượng & giá trị tương ứng
Mã hóa dữ liệu. Khởi tạo số lượng dân số ngẫu nhiên
Thực hiện đột biến trên 2 NST thu được
Thực hiện chéo giữa 2 NST
Lựa chọn ngẫu nhiên 2 NST
Tỷ lệ >90%
Tính tổng khối lượng, tổng giá trị của các
NST. Từ đó tính độ thích nghi của mỗi NST
Tỷ lệ > 90% & số lượng thế
hệ lớn hơn giới hạn

Nếu tổng KL> giới hạn
khối lượng của ba lô
Tính tổng khối lượng và tổng giá trị của
NST
Đối với mỗi NST ta tiến hành:
Ví dụ:
1 2 3 4 5 6 7 T. KL T. GT
v1 0 1 0 1 0 1 0 24 19
v2 1 1 0 0 1 0 0 19 20
v3 0 1 0 0 1 1 1 22 28
v4 1 0 0 1 0 0 1 21 11
v5 0 1 1 0 1 0 0 16 18
v6 1 0 1 0 1 0 0 15 15
Trong bảng: v1 có T.KL = 24 > khối lượng tối đa của ba lô có thể chứa
Đổi 1 bit 1 thành bit 0 trong các mục của NST v1, ta được bảng dân số mới( thỏa
mãn điều kiện khối lượng tối đa của ba lô).
1 2 3 4 5 6 7 T. KL T. GT
v1 0 0 0 1 0 1 0 16 16
v2 1 1 0 0 1 0 0 19 20
v3 0 1 0 0 1 1 1 22 28
v4 1 0 0 1 0 0 1 21 11
v5 0 1 1 0 1 0 0 16 18
v6 1 0 1 0 1 0 0 15 15
Độ thích nghi = T.GT của từng NST.
Eval(v1)= 16
Eval(v2)= 20
Eval(v3)= 28
Eval(v4)= 11
Eval(v5)= 18
Eval(v6)= 15

q3= 14,8+ 18.5+ 25,9 = 59.2% = 0.592.
q4= 14,8+ 18.5+ 25,9+ 10,2 = 69.4 % = 0.694.
q5= 14,8+ 18.5+ 25,9+ 10,2+ 16,7 = 86.1 % = 0.861.
q6= 14,8+ 18.5+ 25,9+ 10,2+ 16,7+ 13,9 = 100% = 1.000.
Giả sử quay 6 lần bánh xe Roulette, mỗi lần chọn 1 NST cho quần thể mới, và đạt
được các giá trị ngẫu nhiên trong khoảng từ [0,1] như sau:
NST cũ Số lần quay bánh xe Vị trí rơi Giải thích NST mới
V1 Lần 1 0.277 0.148<0.277<0.333 V2
V2 Lần 2 0.521 0.333<0.521<0.592 V3
V3 Lần 3 0.811 0.694<0.811<0.861 V5
V4 Lần 4 0.111 0<0.111<0.148 V1
V5 Lần 5 0.498 0.333<0.498<0.592 V3
V6 Lần 6 0.602 0.592<0.602<0.694 V4
Như vậy ta sẽ có quần thể mới là:
NST
mới
1 2 3 4 5 6 7 NST
cũ
V’1 1 1 0 0 1 0 0 V2
V’2 0 1 0 0 1 1 1 V3
V’3 0 1 1 0 1 0 0 V5
V’4 1 0 0 1 0 0 1 V1
V’5 0 1 0 0 1 1 1 V3
V’6 1 0 0 1 0 0 1 V4
2.5. Lai ghép
Sử dụng lai ghép, lai những NST có trong quần thể mới. Vì xác suất lai là pc=0.67
nên sẽ có nhiều nhất là 6*0.67= 4 cặp NST tham gia lai ghép. Ta tiến hành theo cách:
Đối với mỗi NST trong quần thể mới, ta phát sinh ngẫu nhiên 1 số r thuộc [0,1], nếu r
<0.67 thì NST đó được chọn để lai tạo.
Giả sử các số ngẫu nhiên là:

21
V’’3
0 1 0 0 1 0 0
V’4
1 0 0 1 0 0 1
V’5
0 1 0 0 1 1 1
Con cái(V’’4,V’’5) pos=4
V’’4
1 0 0 1 1 1 1
V’’5
0 1 0 0 0 0 1
Còn 1 số phương pháp nữa có thể sử dụng như:
- Lai ghép hai điểm cắt:
V’1:
1 1 0 0 1 0 0
V’3:
0 1 0 0 1 1 1
Con cái:
1 1 0 0 1 1 0
22
0 1 0 0 1 0 1
- Lai ghép đồng nhất
+ Có một mặt nạ sao chép là một chuỗi nhị phân có chiều dài bằng chiều dài NST.
+ Xây dựng NST mới: Duyệt qua mặt nạ, bit có giá trị một thì sao chép gen tại vị trí đó
từ NST cha sang con, bit có giá trị 0 thì sao chép từ mẹ.
+ Mặt nạ được phát sinh ngẫu nhiên đối với từng cặp cha mẹ.
V’1:
1 1 0 0 1 0 0
V’3:

V’3 0 1 0 0 1 0 0
V’4 1 0 0 1 1 1 1
V’5 0 1 0 0 0 0 1
V’6 1 0 0 1 0 0 1
2.6. Đột biến
Phép đột biến được thực hiện trên 1 bit của NST. Bit đó sẽ được đổi từ 0 sang 1
hoặc từ 1 sang 0. Xác suất đột biến là pm = 0.1 .Sẽ có nhiều nhất 1/10 số bit được đột
biến. Có tổng công 7*6= 42 bit trong toàn bộ quần thể nên sẽ có nhiều nhất 4,2 bit
được đột biến. Mỗi bit có cơ hội đột biến là như nhau nên ta phát sinh ngẫu nhiên 1 số
r với r thuộc [0,1]. Nếu r < 0.1 thì chọn bit đó làm vị trí đột biến. Ta Phát sinh ngẫu
nhiên 42 số thuộc [0,1], giả sử xác định được 4 vị trí đột biến như sau:
Vị trí bit Sô ngẫu nhiên
11 0.04
20 0.07
24
26 0.09
34 0.02
Quần thể sau khi đột biến. Những vị trí đột biến sẽ in đậm
NST 1 2 3 4 5 6 7
V’1 1 1 0 0 1 1 1
V’2 0 1 0 1 1 1 1
V’3 0 1 0 0 1 1 0
V’4 1 0 0 1 0 1 1
V’5 0 1 0 0 0 1 1
V’6 1 0 0 1 0 0 1
Ta vừa hoàn thành 1 thế hệ của giải thuật di truyền. Sau khi kết thúc vòng lặp kết
quả được đưa lên bước 2 tạo quần thể và tiếp tục kiểm tra điều kiện. Nếu thỏa mãn thì
sẽ dừng đưa ra kết quả tối ưu, nếu không sẽ tiếp tục thế hệ tiếp theo cho tới khi thỏa
mãn điều kiện
Kiểm tra độ thích nghi của quần thể mới so với quần thể cũ