MỤC LỤC
1 CHƯƠNG 1: GIẢI THUẬT DI TRUYỀN 2
1.1 GIỚI THIỆU 2
1.2 CÁC KHÁI NIỆM CƠ SỞ 3
1.2.1 Lai ghép 3
1.2.2 Đột biến 3
1.2.3 Chọn lọc 4
1.2.4 Nhiễm sắc thể 4
1.2.5 Cá thể 4
1.2.6 Quần thể 4
1.3 SƠ ĐỒ CHUNG CỦA GIẢI THUẬT DI TRUYỀN 5
1.4 CÁC PHƯƠNG PHÁP MÃ HÓA VÀ KHỞI TRỊ 6
1.4.1 Mã hóa dạng nhị phân 7
1.4.2 Mã hóa dạng số thực 8
1.4.3 Mã hoá hoán vị: 9
1.4.4 Tạo lập lời giải ban đầu (khởi tạo quần thể) 9
1.5 XÂY DỰNG HÀM THÍCH NGHI (hàm phù hợp) 9
1.6 CÁC TOÁN TỬ DI TRUYỀN 10
1.6.1 Toán tử chọn lọc (Selection) 11
1.6.2 Toán tử lai ghép (crossover) 13
1.6.3 Toán tử đột biến (Mutation) 17
2 CHƯƠNG2: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN RA ĐỀ THI TỐI
ƯU 21
2.1 Bài toán 21
2.2 Các yêu cầu chung của việc ra đề: 22
Các yêu cầu của đề thi: 22
2.3 Mô hình bài toán ra đề thi: 24
2.3.1 Phân tích bài toán: 24
2.3.2 Bài toán tìm đề thi tối ưu thuộc vào lớp bài toán NP-đầy đủ 25
2.3.3 Xây dựng cá thể, hàm thích nghi và các phép toán di truyền 25
1

ngẫu nhiên với môi trường bên ngoài hoặc giữa các NST với nhau.
Từ ý tưởng đó, các nhà khoa học đã nghiên cứu và xây dựng nên giải
thuật di truyền dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hoá. Giải thuật
di truyền sử dụng các thuật ngữ được lấy từ di truyền học như: lai ghép, đột
biến, NST, cá thể Ở đây mỗi cá thể được đặc trưng bởi một tập nhiễm sắc thể,
nhưng để đơn giản khi trình bày, ta xét trường hợp tế bào mỗi cá thể chỉ một
NST. Các NST được chia nhỏ thành các gen được sắp xếp theo một dãy tuyến
tính. Mỗi cá thể (hay NST) biểu diễn một lời giải có thể của bài toán. Một xử lý
tiến hoá duyệt trên tập các NST tương đương với việc tìm kiếm lời giải trong
không gian lời giải của bài toán. Quá trình tìm kiếm phải đạt được hai mục tiêu:
+ Khai thác những lời giải tốt nhất
+ Xem xét trên toàn bộ không gian tìm kiếm
1.2 CÁC KHÁI NIỆM CƠ SỞ
1.2.1 Lai ghép
Lai ghép trong tự nhiên là sự kết hợp các tính trạng của bố mẹ để sinh ra
thế hệ con. Trong giải thuật di truyền, lai ghép là quá trình hình thành nhiễm sắc
thể mới trên cơ sở của 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ể của cha mẹ với nhau.
1.2.2 Đột biến
Đột biến là một sự biến đổi tại một (hay một số) gen của nhiễm sắc thể
ban đầu để tạo ra một nhiễm sắc thể mới. Đột biến có xác suất xảy ra thấp hơn
lai ghép. Đột biến có thể tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban
đầu. Tuy nhiên trong giải thuật di truyền thì ta luôn muốn tạo ra những phép đột
biến cho phép cải thiện lời giải qua từng thế hệ.
3
1.2.3 Chọn lọc
Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay đổi
các cá thể trong quần thể. Những cá thể tốt, thích nghi được với điều kiện sống
thì có khả năng đấu tranh lớn hơn, do đó có thể tồn tại và sinh sản. Các cá thể
không thích nghi được với điều kiện sống thì dần mất đi. Dựa vào nguyên lý của

Lai ghép
Đột biến
Kiểm tra điều kiện
Kết quả
Kết thúc
Không
Thỏa
Hình: Sơ đồ cấu trúc giải thuật di truyền
Giải thích các khối trong sơ đồ:
1. [Bắt đầu ] Nhận các tham số cho thuật toán.
2. [Khởi tạo quần thể] Sinh ngẫu nhiên một quần thể gồm M cá thể (là M
lời giải cho bài toán)
3. 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
a.[Đánh giá độ thích nghi] Đánh giá độ thích nghi eval(x) của mỗi
cá thể trong quần thể.
b.[Chọn lọc] Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích
nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả
năng được chọn).
c.[Lai ghép] Với một xác suất lai ghép được chọn, lai ghép hai cá
thể bố mẹ để tạo ra một cá thể mới.
d.[Đột biến] Với một xác suất đột biến được chọn, biến đổi cá thể
mới.
e.[Kiểm tra điều kiện] Kiểm tra điều kiện kết thúc giải thuật.
4. [Kết quả] Nếu điều kiện dừng được thỏa mãn thì thuật toán kết thúc và
trả về lời giải tốt nhất trong quần thể hiện tại.
1.4 CÁC PHƯƠNG PHÁP MÃ HÓA VÀ KHỞI TRỊ
Việc mô tả di truyền cho lời giải cho bài toán gồm hai phần cơ bản:
+ Xây dựng cấu trúc gen cho mỗi lời giải của bài toán để từ mỗi lời giải
ta có thể mã hoá thành một NST (chuỗi các gen).

x = l
x
+ decimal(NST) * g
trong đó, decimal(NST) là giá trị thập phân của chuỗi NST nhị phân.
Chẳng hạn ta muốn tìm cực tiểu 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
i
]
⊆
R và f(x
1
,…,x
k
)
> 0 với mọi x
i
thuộc D
i

- 1
Như vậy, mỗi biến x
i
đượ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 yê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
).01 1100(
2
−
−
+=
i
m
ii
ii
ab
decimalaX
trong đó decimal(chuỗi
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 chuỗi nhị
phân có chiều dài L=
∑
k
i=1
m

1
, a
2
, , a
m
) với các a
i
∈ R. Cách mã hoá này thường tự nhiên đối với các bài
toán tối ưu số và được phát triển rất mạnh trong thời gian gần đây.
Ví dụ:
Nhiễm sắc thể A 1,2324 5,3243 0,4556 2,3293 2,4545
Nhiễm sắc thể B 3,134 5,234 0,245 2,976
8
1.4.3 Mã hoá hoán vị:
Mỗi cá thể tương ứng với một hoán vị của tập n ký hiệu nào đó. Chẳng
hạn cách biểu diễn này đã được áp dụng cho bài toán người du lịch:
Một thương gia phải đi qua nhiều thành phố (n). Hãy vạch lộ trình đi qua
tất cả các thành phố đó sao cho quãng đường đi là ngắn nhất. Biết rằng mỗi
thành phố chỉ đi qua một lần.
Kí hiệu các thành phố là T
1
, T
2
, , T
n
mỗi cá thể - sự mã hoá của lời giải -
sẽ là một danh sách hoán vị của T
1
, T
2

Với phương pháp mã hoá hoán vị: xây dựng NST ban đầu bằng cách
hoán vị ngẫu nhiên các thứ tự.
Với mã hoá số thực: tạo ngẫu nhiên N vecto thực trong R
m
.
1.5 XÂY DỰNG HÀM THÍCH NGHI (hàm phù hợp)
Hàm phù hợp đánh giá khả năng phù hợp của tập lời giải theo yêu cầu bài
toán. Hàm này được xây dựng cho từng bài toán với yêu cầu cụ thể. Thông
thường trong các bài toán tối ưu hàm này chính là hàm mục tiêu của bài toán.
9
Biến đổi hàm mục tiêu thành hàm phù hợp:
Do giá trị phù hợp trong giải thuật di truyền là không âm, nên để áp dụng
GA cho bài toán tối ưu ta cần phải chuyển giá trị hàm mục tiêu thành hàm phù
hợp.
Nếu bài toán tối ưu là cực tiểu hàm mục tiêu g(x) thì ta chuyển sang hàm
phù hợp như sau:



<−
=
lainguoc
CxgxgC
xf
0
)()(
)(
maxmax
Trong đó, C
max

nhỏ hơn nhiều so với hiện tượng di truyền. Các thuật toán tiến hóa, tuy có
những điểm khác biệt, nhưng đều mô phỏng ba toán tử cơ bản: lai ghép, đột
biến và chọn lọc.
10
1.6.1 Toán tử chọn lọc (Selection)
Phép chọn lọc được mô tả như sau:
Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần.
Loại bỏ các cá thể cuối dãy chỉ để lại các cá thể tốt nhất.
Có các toán tử chọn lọc sau:
 Chọn lọc tỷ lệ: Được sử dụng thường xuyên nhất
trong GA. Xác xuất lựa chọn của mỗi cá thể tỉ lệ thuận với giá trị độ thích hợp
của nó, được tính theo công thức:
P
i
= f(v
i
) / F (i = 1…m ~ kích cỡ của quần thể) gọi là xác suất chọn cho
mỗi nhiễm sắc thể v
i
Trong đó: f(v
i
) là hàm thích nghi của mỗi cá thể v
i
.
F là tổng của các giá trị thích nghi của quần thể.
Việc chọn lọc cá thể nào phụ thuộc vào xác suất q
i
của mỗi nhiễm sắc thể
v
i

Hiển nhiên, có thể sẽ có một số nhiễm sắc thể được chọn nhiều lần. Điều
này phù hợp với lý thuyết sơ đồ (Nguyễn Đình Thúc, [1]): các nhiễm sắc thể tốt
nhất có nhiều bản sao hơn, các nhiễm sắc thể trung bình không thay đổi, các
nhiễm sắc thể kém nhất thì mất đi.
Ví dụ: Với quần thể gồm 4 cá thể cho trong bảng sau chúng ta có vòng tròn
Roulette như hình dưới.
Bảng Ví dụ về quần thể gồm 4 cá thể
STT Chuỗi v
i
Sức khoẻ f(v
i
) Tỷ lệ % P
i
Tổng chạy q
i
1
2
3
4
01101
11000
01000
10011
169
576
64
361
14.4
49.2
5.5

∑
=
−
=
N
k
jN
k
j
p
1
.
Các bước tiến hành của thủ tục là:
- Sắp xếp các chuỗi theo thứ tự giảm dần của hàm mục tiêu (bài toán cực
đại) hoặc theo thứ tự tăng dần của hàm mục tiêu (bài toán cực tiểu).
- Sử dụng thủ tục quay Roulette để chọn chuỗi sao chép sang quần thể tạm
thời.
1.6.2 Toán tử lai ghép (crossover)
Toán tử lai ghép được gán với một xác suất p
c
. Quá trình được mô tả như
sau:
13
- Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kỳ trong quần thể (để làm cha
mẹ). 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 (gọi là điểm lai ghép).
Điểm lai ghép chia nhiễm sắc thể cha mẹ ra thành hai chuỗi con có độ dài m1 và
m2. Hai chuỗi nhiễm sắc thể con mới sẽ là : m
11
+m

, , y
k
, x
k+1
, , x
m
)
Ví dụ: P
1
= (1 1 1 0 0 0 1 0 1 0) P
2
= (0 1 0 1 1 0 0 1 1 1)
là hai chuỗi nhị phân độ dài 10, giả sử điểm cắt đã chọn là k=7, thế thì hai
con được sinh ra là :
C
1
= (1 1 1 0 0 0 1 1 1 1) C
2
= (0 1 0 1 1 0 0 0 1 0)
14
Thủ tục lai ghép đơn giản như sau :
Procedure lai1diem(k; P1, P2; var C1, C2);
Begin
For i:=1 to k do
Begin
C1[i] := P1[i];
C2[i] := P2[i];
End;
For i:=k+1 to L do
Begin

- y’
i
lấy bằng x
i
tại những đoạn có số hiệu lẻ và bằng y
i
tại những đoạn có
số hiệu chẵn.
ví dụ: P
1
= (1 1 1 0 0 0 1 0 1 0) P
2
= (0 1 0 1 1 0 0 1 1 1)
là hai chuỗi nhị phân độ dài 10, giả sử các điểm cắt đã chọn là 2, 5, 8 thế thì hai
con được sinh ra là :
C
1
= (1 1 1 0 0 0 1 1 1 1) C
2
= (0 1 0 1 1 0 0 0 1 0)
 Lai ghép đều hay lai ghép mặt nạ (Uniform Crossover)
Loại lai ghép này còn gọi là lai ghép đều; với hai cá thể cha mẹ đã chọn P
1
, P
2
trước hết phát sinh một chuỗi nhị phân ngẫu nhiên cũng có độ dài L gọi là chuỗi
mặt nạ. Sau đó các con được tạo ra dựa trên chuỗi mặt nạ này để quyết định lấy
thành phần của cá thể cha hay mẹ. Chẳng hạn gen thứ i của cá thể con C
1
được

10001000100
01101011001
00111110000
11101001000 11101011000
Các chuỗi ban đầu Mặt nạ lai ghép Các cá thể con
Lai ghép điểm đơn:
Lai ghép điểm kép:
Lai ghép đồng nhất:
Đột biến điểm:
Thủ tục lai ghép như sau :
Procedure lai_mat_na(U, P1, P2; var C1, C2);
Begin
For i:=1 to L do
Begin
If U[i]=1 then
Begin
C1[i] := P1[i]; C2[i] := P2[i];
End
Else
Begin
C1[i] := P2[i]; C2[i] := P1[i];
End;
End;
End;
1.6.3 Toán tử đột biến (Mutation)
Toán tử đột biến được gán xác suất p
m
(nhỏ hơn nhiều so với xác suất lai
ghép p
c

0
= (b
10
, b
20
, , b
m0
);
{Đánh giá độ thích nghi}
WHILE (not (điều kiện dừng)) DO
BEGIN
{
chọn lọc tỷ lệ
}
FOR i:=1 TO m DO
BEGIN
r:=random[0,1];
k:=1;
WHILE (k<m and
∑
∑
=
=
<
m
j
tj
i
j
tj

[k] ;
b
it+1
[k] := b
i+1t+1
[k];
b
i+1t+1
[k] := tg;
END;
END;
END;
{
đột biến
}
FOR i:=1 TO m DO
FOR k:=1 TO n DO
IF random[0,1]<p
m
THEN
invert(b
it+1
[k]);
t := t+1;
END;
Như vậy, bản chất GA là một giải thuật lặp, nhằm giải quyết các bài toán
tìm kiếm dựa trên cơ chế chọn lọc nhân tạo và sự tiến hoá của các gen. Trong
quá trình đó, sự sống còn của cá thể phụ thuộc vào hoạt động của các NST và
quá trình chọn lọc (tham gia vào việc tái tạo ra các chuỗi NST mới bằng cách
giải mã các chuỗi NST và tạo ra mối liên kết giữa các NST trong các cá 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, quá trình tìm kiếm này cần cân đối giữa 2 mục tiêu là: 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. Thuật giải di truyền
(GA) là phương pháp tìm kiếm tạo được sự cân đối giữa việc khai thác và khảo
sát không gian tìm kiếm.
Giải thuật di truyền thuộc lớp các giải thuật xác suất, nhưng chúng lại
khác các giải thuật ngẫu nhiên vì GA 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 (một quần thể), tất cả
các phương pháp khác chỉ xử lý một điểm trong không gian tìm kiếm, chính bởi
vậy, GA mạnh hơn các phương pháp tìm kiếm hiện có rất nhiều.
20
2 CHƯƠNG2: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN GIẢI BÀI
TOÁN RA ĐỀ THI TỐI ƯU
2.1 Bài toán
Chúng ta hãy xét một ngân hàng câu hỏi để kiểm tra kiến thức, sự hiểu biết,
kinh nghiệm về môn học thuộc một lĩnh vực hay về một chủ đề nào đó. Mỗi câu
hỏi đề cập đến một chủ đề của lĩnh vực cần kiểm tra với một mức độ khó - dễ
được các giáo viên thống nhất đánh giá. Ngoài nội dung của câu hỏi, thời gian
tối đa dự kiến trả lời cũng cần được xác định trước.
Tập các câu hỏi có thể được tổ chức thành quan hệ CauHoi với các thuộc tính
của quan hệ này như sau:
CauHoi = (Ma, NoiDung, ChuDe, DoKho, ThoiGian)
Trong đó:
- Ma: Thuộc tính khóa (có thể là các số nguyên, số thứ tự của các câu hỏi)
- NoiDung: Nội dung câu hỏi
- ChuDe: Chủ đề, lĩnh vực của câu hỏi
- DoKho: Chỉ số xác định độ khó của câu hỏi: 1: rất khó; 2: khó; 3: trung bình;
4: dễ, …
- ThoiGian: Thời gian tối đa được phép trả lời câu hỏi (tính bằng phút). Trong

đánh giá chất lượng đào tạo hiện thời.
Các yêu cầu của đề thi:
Sau đây là hai ví dụ về yêu cầu của người ra đề.
Yêu cầu ra đề 1: Với quan hệ CauHoi 10 câu đã cho ở trên, hãy soạn một đề
Tin học 10 thỏa mãn tối ưu các yêu cầu sau:
o Thời gian làm bài khoảng: 90 phút
o Nằm trong các chủ đề: Tin học 10 (Chương 1), Tin học 10 (Chương 2),
Tin học 10 (Chương 3), Tin học 10 (Chương 4).
22
o Độ khó, tỷ lệ phân bổ kiến thức của các chủ đề cho trong bảng dưới đây:
Tên chủ đề cần ra Tỷ lệ phân bổ kiến thức Độ khó yêu cầu
Tin học 10 (Chương 1) chiếm 10% 2
Tin học 10 (Chương 2) chiếm 40% 5
Tin học 10 (Chương 3) chiếm 10% Tùy ý
Tin học 10 (Chương 4) Tùy ý 4
Yêu cầu ra đề 2: Với quan hệ CauHoi 10 câu đã cho ở trên, hãy soạn một đề
Tin học 10 thỏa mãn tối ưu các yêu cầu sau:
o Thời gian làm bài khoảng: 180 phút
o Nằm trong các ChuDe: Tin học 10 (Chương 3), Tin học 10 (Chương
2),Tin học 10 (Chương 1), Tin học 10 (Chương 4)
o Tỷ lệ phân bổ kiến thức của các chủ đề cho như trong bảng dưới đây:
Tên chủ đề cần ra Tỷ lệ phân bổ kiến thức
Tin học 10 (Chương 3) Tùy ý
Tin học 10 (Chương 2) chiếm 40%
Tin học 10 (Chương 1) chiếm 10%
Tin học 10 (Chương 4) Tùy ý
o Số lượng câu khó, dễ có tỉ lệ như sau:
Khó (DoKho = 4) chiếm 20%; TB (DoKho = 3) chiếm 30%
Nhận xét:
• Đề thi được tạo ra bằng cách tổ hợp các câu hỏi của quan hệ CauHoi.

1
,T
2
,…, T
n
}
+ L: tập độ khó của các chủ đề yêu cầu tương ứng L =
},,,{
21 n
TTT
LLL 
+ K: tập các tỉ lệ % phân bổ kiến thức yêu cầu tương ứng,
K =
},,,{
21 n
TTT
KKK 

+ I: thời gian làm bài tối đa của đề.
Trong lời giải sau đây chúng tôi thường sử dụng khái niệm hai tập hợp
tiệm cận với nhau theo nghĩa chúng giao nhau nhiều nhất có thể. Để tiện chúng
ta ký hiệu P ≅ Q nếu tập |P ∩ Q| là cực đại.
Lời giải của (*) là một quan hệ q (một đề thi tối ưu), q ⊆ CauHoi có các các giá
trị: (t, l, k, i) tương ứng với các tham số (T, L, K, I), trong đó
t: tập chủ đề t = {T
1
, T
2
,…, T
m

i
T
k
≅
i
T
K
24
i: thời gian làm bài, i thỏa mãn i ≈ I.
Vấn đề chủ yếu ở đây là tìm ánh xạ f (giải thuật phù hợp) để giải quyết bài
toán nêu trên.
2.3.2 Bài toán tìm đề thi tối ưu thuộc vào lớp bài toán NP-đầy đủ
Tìm hàm mục tiêu:
Như trên đã khẳng định, lời giải của bài toán nêu trên là một quan hệ q tối
ưu, nghĩa là quan hệ q phải thỏa mãn đồng thời các mục tiêu:
(i) E
1
= (
∑
=
m
T
i
1
|
i
T
k
-
i

với
i
T
l
∈ l,
i
T
L
∈ L
(iii) E
3
= (|m - n|)
với m = |t| và n = |T|
(iv) E
4
= (|i

– I|)
Nói cách khác, phải tìm một quan hệ q từ CauHoi để thoả mãn hàm mục tiêu
sau:
Fitness(q) = - E
1
* E
2
* E
3
*E
4

Hiển nhiên đây là bài toán tối ưu đa mục tiêu. Theo lý thuyết độ phức tạp