Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 1

Đề Tài: Giải thuật di truyền – Generic Algorithms
MỤC LỤC

LỜI CẢM ƠN 3

A - MỞ ĐẦU 4



Đề tài 4



Lý do chọn đề tài 4



Đối tượng và phạm vi nghiên cứu 4



Mục đích của đề tài 4



Cấu trúc của đồ án 5

B - NỘI DUNG 6

Chương I: Cơ sở Lý Thuyết về giải thuật di truyền 6

1.

Giới thiệu giải thuật di truyền 6

2.

Ứng dụng của giải thuật di truyền 7

3.

Giải thuật di truyền tiêu chuẩn 8

3.1.

Hàm mục tiêu 8

3.2.

Toán tử lai ghép 8

3.3.

Toán tử đột biến 9


3.4.

Toán tử tái tạo 9

3.5.

Sơ đồ tổn thể của giải thuật 10

3.6.

Ví dụ áp dụng giải thuật di truyền 11

4.

Cơ chế hoạt động của giải thuật di truyền 12

5.

Các phương pháp biểu diễn nhiễm sắc thể 13

Chương II: Bài toán “Người đưa thư”, ứng dụng giải thuật di truyền để giải
bài toán “Người đưa thư”. 20

1.

Bài toán “Người đưa thư” 20

1.1.


Lịch sử 20

1.2.

Phát biểu bài toán như sau 20

1.3.

Phần tích độ phức tạp 20




Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 2

Đề Tài: Giải thuật di truyền – Generic Algorithms
2.

Ứng dụng giải thuật di truyền để giải bài toán người đưa thư, biểu diễn
nhiễm sắc thể bằng ký tự 21

2.1.

Ghép chéo riêng từng phần (Partailly matched crossover – PMX) 22

2.2.

Ghép chéo có thứ tự (Order crossover – OX) 23


2.3.

Phép đảo vị trí (Inversion operator) 24

2.4.

Phép đột biết 25

Chương III: Môi trường cài đặt ứng dụng và công cụ hỗ trợ lập trình 26

1.

Giới thiệu môi trường cài đặt thuật toán 26

2.

Ngôn ngữ sử dụng để cài đặt 26

3.

Công cụ hỗ trợ lập trình 28

Chương IV: Thiết kế và cài đặt ứng dụng 29

1.

Mô tả ứng dụng 29

2.


Thiết kế ứng dụng 29

2.1.

Thiết kế giao diện người dùng 29

2.2.

Thiết kế các đối tượng của bài toán 32

3.

Cài đặt ứng dụng 33

3.1.

Cài đặt các đối tượng 33

3.1.1.

Đối tượng Gene 33

3.1.2.

Đối tượng Chromosome 34

3.1.3.

Đối tượng Populations 38


3.2.

Cài đặt chương trình 41

3.2.1.

Cài đặt lớp thao tác cơ sở dữ liệu 41

3.2.2.

Cài đặt các form 42

4.

Kiểm thử ứng dụng 46

4.1.

Bộ dữ liệu 1 46

4.2.

Bộ dữ liệu 2 47

4.3.

Bộ dữ liệu 3 48

C - KẾT LUẬN 49


TÀI LIỆU THAM KHẢO 50





Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 3

Đề Tài: Giải thuật di truyền – Generic Algorithms
LỜI CẢM ƠN
Em xin chân thành cảm ơn sự giúp đỡ TS.Phạm Thanh Hà người đã trực tiếp
hướng dẫn, chỉ bảo tận tình và tạo điều kiện, giúp đỡ em hoàn thành khóa luận đúng
thời hạn.
Em xin chân thành cảm ơn tất cả các thầy, cô giáo trong khoa Công nghệ thông
tin – trường Đại Học Giao Thông Vận Tải, những người đã nhiệt tình giảng dạy và
truyền đạt những kiến thức trong suốt thời gian em học tập tại trường, để em hoàn
thành tốt khóa luận.
Cuối cùng em xin cảm ơn tất cả các bạn đã góp ý kiến, trao đổi hỗ trợ em trong
suốt thời gian vừa qua.
Em xin chân thành cảm ơn!

Hà Nội, tháng 05 năm 2014
Sinh viên

Hà Văn Tân





Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 4

Đề Tài: Giải thuật di truyền – Generic Algorithms
A - MỞ ĐẦU
 Đề tài
Nghiên cứu và xây dựng giải thuật di truyền giải bài toán người đưa thư.
 Lý do chọn đề tài
Hiện nay và trong tương lai, trí tuệ nhân tạo (Artifiticial Intelligent) đã và
đang được nghiên cứu, phát trển mạnh mẽ và được ứng dụng rộng rãi trong cuộc
sống. Ví dụ như: các tập đoàn hàng đầu về công nghệ như Microsoft, Google…
cũng đã ứng dụng trí tuệ nhân tạo lên những sản phẩm của họ thành công như
công nghệ Google Now Của Google, hay Cortana của Microsoft…
Trí tuệ nhân tạo còn được ứng dụng trong các lĩnh vực dự báo thảm thọa
thiên tai, cũng như trong lĩnh vực y tế và còn nhiều lĩnh vực khác trong đó có
lĩnh vực tính toán thông minh (Computational Intelligent). Trong đó có giải
thuật di truyền (Generic Algorithms) đã đem lại những phương pháp mới để giải
các bài toán mà nếu áp dụng phương pháp truyền thống sẽ gặp nhiều khó khăn.
 Đối tượng và phạm vi nghiên cứu
 Đối tượng nghiên cứu
 Giải thuật di truyền
 Bài toán người đua thư
 Phạm vi nghiên cứu
 Ứng dụng giải thuật di truyền thiết kế giải thuật tìm tru trình ngắn nhất để
giải bài toán người đưa thư.
 Nghiên cứu và cài đặt giải thuật di truyền bằng phương pháp lập trình
hướng đối tượng.

 Mục đích của đề tài
Mục đích của đề tài là muốn tìm một hướng tiếp cận mới bằng giải thuật di
truyền để giải bài toán người đưa thư.





Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 5

Đề Tài: Giải thuật di truyền – Generic Algorithms
 Cấu trúc của đồ án
Nội dung của đồ án được trình bày trong 4 chương:
 Chương I: Cơ sở lý thuyết về giải thuật di truyền
 Chương II: Bài toán “Người đưa thư” Ứng dụng giải thuật di truyền
để giải bài toán “Người đưa thư”.
 Chương III: Môi trường cài đặt ứng dụng và công cụ hỗ trợ lập trình.
 Chương IV: Thiết kế và cài đặt ứng dụng.




Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 6

Đề Tài: Giải thuật di truyền – Generic Algorithms
B - NỘI DUNG

Chương I: Cơ sở lý thuyết về giải thuật di truyền
1. Giới thiệu giải thuật di truyền
Giải thuật di truyền (Generic 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 toá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 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ể, nó đặc trưng cho mỗi loài và quyết định sự sống còn của cơ thể
đó.
Một loài muốn tồn tại phải thích nghi với môi trường sống, cơ thể nào thích
nghi với môi trường hơn thi sẽ tồn tại và sinh sản với số lượng ngày càng nhiều ,
trái lại những loài không thích nghi với môi trường sống sẽ dần bị diệt chủng.
Môi trường tự nhiên luôn 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 luôn 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 giữa
môi trường bên ngoài và 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
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 gi truyền.
Các nguyên lý cơ bản của giải thuật được tác giả Holland đề xuất vào năm
1962. Nền tảng toán học của giải thuật GA được tác giả công bố trong quấ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
ngẫu nhiên mang tính tổng quát để giải các bài toán tối ưu hóa.
Giải thật GA thuộc lớp các giải thuật tiến hóa. Khác với phần lớn các giải
thuật tìm kiếm theo điểm khác, giải thuật GA thực hiện tìm kiếm song song trên
một tập hợp gọi là quần thể các lời giải có thể.
Thông qua việc áp dụng các toán tử di truyền, Giải thuật GA trao đổ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 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ảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 7

Đề Tài: Giải thuật di truyền – Generic Algorithms
Giải thuật GA mô phỏng quá trình tồn tại của các cá thể có độ phù hợp tốt
nhất thông qua quá 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óa 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 toán tối ưu hóa.
Thông thường, các lời giải này được mã hóa dưới dạng một chuỗi các gene. Giá
trị của các gene có trong chuỗi được lấy từ một bảng các ký tự được định nghĩa
trước. Mỗi chuỗi gene được liên kết với một giá trị được gọi là độ phù hợp, giá
trị này được dùng trong quá trình chọn lọc.
Cơ chế chọn lọc đảm bảo các cá thể có độ phù hợp tốt hơn có xác suất được
chọn cao hơn. Quá trình chọn lọc sao chép các bản sao của các cá thể có độ phù
hợp tốt vào quần thể tạm thời được gọi là quần thể bố mẹ. Các cá thể trong quần
thể bố mẹ được gép đôi một cách ngẫu nhiên và tiến hành lai ghép tạo ra các cá
thể con.
Sau khi tiến hành quá trình lai ghép, giải thuật GA mô phỏng quá trình khác
trong tự nhiên là quá trình đột biến, trong các gene của các cá thể con tự thay đổi
vị 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 toán, cụ thể là:
 Mã hóa lời giải thành các 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ẹ.
 Toán tử lai ghép.
 Toán tử đột biến.

 Chiến lược thay thế hay còn gọi là toá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ác lựa chọn theo J.H. Holland khi thiết kế phiên bản giải thuật GA đầu tiên gọi
là giải thuật di truyền tiêu chuẩn (Standard Generic Algorithm gọi tắt là SGA).
2. Ứng dụng của giải thuật di truyền
Ban đầu giải thuật di truyền được ứng dụng chủ yếu trong lĩnh vực tối ưu hóa
và máy học. Đến nay nó đã phát triển mạnh mẽ và có nhiều ứng dụng thực tế,
đặc biệt là trong lĩnh vực trí tuệ nhân tạo. Ví dụ: năm 1967 Beglay xây dựng



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 8

Đề Tài: Giải thuật di truyền – Generic Algorithms
máy chơi cờ Hexapawn dựa trên giải thuật di truyền và nhận ra rằng giải thuật di
truyền có thể thực hiện tốt mà không phụ thuộc vào độ phức tạp của trò chơi.
Trong lĩnh vực tối ưu hóa có nhiều bài toán được áp dụng giải thuật di truyền
và đã thành công như tối ưu hóa hàm một hay nhiều biến, bài toán người đưa
thư, bài toán hộp đen, bài toán nhận dạng…
Trong lĩnh vực trí tuệ nhân tạo giải thuật di truyền được ứng dụng vào việc
thiết kế mạng nơron, kiến trúc lẫn trọng số, quỹ đạo cho người máy, các hệ phi
tuyến động như phỏng đoạn và phần tích dữ iệu.
3. Giải thuật di truyền tiêu chuẩn
Trong giải thuật di truyền của mình J.H Holland sử dụng mã hóa nhị phân để
biểu diễn các cá thể, lý do là phần lớn các bài toán tối ưu hóa đều có thể được
mã hóa thành chuỗi nhị phân đơn giản.
3.1. Hàm mục tiêu
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 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 lựa chọn


=

/
∑




, ở đây N là số cá thể trong quần thể.
3.2. Toán tử lai ghép
Toán tử lai ghép trong giải thuật SGA là toán tử lai ghép một điểm cắt.
Giả sử chuỗi cá thể có độ dài L(có L bit), toá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 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ự j+1
đến L.



Giảng viên hướng dẫn: TS.Phạm Thanh Hà

Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 9

Đề Tài: Giải thuật di truyền – Generic Algorithms

Điều đáng lưu ý là giải thuật GA không yêu cầu toán tử lai ghép luôn xảy
ra đối với 2 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ố p
c
(gọi là xác suất lai ghép). Nếu số ngẫu nhiên
này lớn hơn p
c
, toán tử lai ghép không xảy ra. Khi đó cá thể con là bản sao
trực tiếp của hai cá thể bố mẹ.
3.3. Toán tử đột biến
Tiếp theo, J.H. Holland xây dựng toán tử đột biến cho giải thuật SGA.
Toán tử này được gọi là toán tử đột biến tiêu chuẩn. Toán tử đột biến duyệt
từng gene của cá thể con được sinh ra sau khi tiến hành toán tử lai ghép và
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 p
m

được gọi là xuất đột biến.
3.4. Toán tử tái tạo
Cuối cùng là chiến lược thay thế hay còn gọi là toán tử tái tạo. Trong giải
thuật SGA, quần thể con được sinh ra từ quần thể hiện tại thông qua ba toán
tử là chọn lọc, lai ghép và đột biến và thay thế hoàn toà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.
Hình 1




Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 10

Đề Tài: Giải thuật di truyền – Generic Algorithms
3.5. Sơ đồ tổn thể của giải thuật
ThuTuc_SGA(input N,p
c
,p
m
,G)
{
k = 0;
//khởi tạo quần thể P
0
một cách ngẫu nhiên với N cá thể
KhoiTao(P
k
,N);
//tính giá trị hàm mục tiêu cho từng cá thể
TinhHamMucTieu(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
= TotNhat(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
= ChonLoc(P
k
);
/*tiến hành lai ghép với xác suất p
c
và đột biến với xác
suất p
m
tạo ra quần thể cá thể con P
child
*/
P
child
= LaiGhep(P
k
,p
c
);
P
child

= DotBien(P
k
,p
m
);
/*thay thế quần thể hiện tại bằng quần thể cá thể con*/
k = k + 1;
P
k
= P
child
;
/*nếu giá trị hàm mục tiêu obj(X) của cá thể tốt nhất X
trong quần thể P
k
lớn hơn giá trị hàm mục tiêu của X
best

thì thay thế lời giải*/
X = TotNhat(P
k
);
if(obj(X) > obj(X
best
)) X
best
= X;
} while(k < G);//tiến hành G thế hệ
Return Xbest;//trả về lời giải tốt nhất của giải thuật SGA
}

Giả thuật di truyền phụ thuộc vào 4 tham số (N,p
c
,p
m
,G), trong đó:
 N là số cá thể trong quần thể
 p
c
là xác suất lai ghép
 p
m
là xác suất đột biến
 G là số thế hệ cần tiến hóa
Đây chính là các tham số điều khiển của giải thuật di truyền tiêu chuẩn
SGA.



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 11

Đề Tài: Giải thuật di truyền – Generic Algorithms
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.
3.6. Ví dụ áp dụng giải thuật di truyền
Ví dụ: xét bài toán tìm Max của hàm f
(x)
= x

2
với x là số nguyên trên
đoạn [0,31].
Để sử dụng giải thuật di truyền ta mã hóa số nguyên 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ã số nguyên 24.
Hàm thích nghi được xác định chính là hàm f
(x)
= x
2
, quần thể ban đầu
gồm 4 cá thể ( kích thước quần thể n = 4) thực hiện quá trình chọn lọc ta có
bảng sau:
Số hiệu
cá thể
Quần thể ban
đầu
x Độ thích nghi f
(x)
= x
2
Số lần được
chọn
1 01101 13 169 1
2 11000 24 576 2
3 01000 8 64 0
4 10011 19 361 1
Trong bảng này ta thấy cá thể 2 có độ thích nghi cao nhất nên nó được
chọn 2 lần, cá thể 3 có độ thích nghi thấp nhất nên nó không được chọn lần
nào, mỗi cá thể 1 và 4 được chọn 1 lần.
Thực hiện quá 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ả như sau:
Quần thể
chọn lọc
Điểm ghép Quần thể sau
lai ghép
x Độ thích nghi
f
(x)
= x
2

0110|1 4 01100 12 144
1100|0 4 11001 25 625
11|000 2 11011 27 729
10|011 2 10000 16 256



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 12

Đề Tài: Giải thuật di truyền – Generic Algorithms
Trong bảng này, chuỗi thứ nhất được lai ghép với chuỗi thứ 2 với điểm
lai ghép là 4, 2 chuỗi còn lại được lai ghép với nhau tại điểm ghép là 2.
Để thực hiện quá trình đột biến, ta chọn xác suất đột biến p
m
= 0.001 hay

là 1%, tức là ta hy vọng có 5 x 4 x 0.001 = 0.02 bit được đột biến. Như vậy
thế hệ quần thể mới là thế hệ quần thể sau lai ghép.
Ta thấy rằng trong thế hệ ban đầu độ thích nghi cao nhất là 576 và độ
thích nghi trung bình là 292. Còn trong thế hệ mới, độ thích nghi cao nhất là
729 và độ thích nghi trung bình là 438. Như vậy chỉ qua một thế hệ, các cá
thể đã “tốt lên” rất nhiều.
4. Cơ chế hoạt động của giải thuật di truyền
Giống như quá trình tiến hóa của sinh vật giải thuật di truyền cũng hoạt động
dựa vào cơ chế chọn lọc tự nhiên và quá trình tiến hóa.
 Chọn lọc tự nhiên
Quá trình chọn lọc tự nhiên đơn dựa trên phương pháp dùng bánh
xe Roulette, ở đây mỗi chuỗi nhiễm sắc thể (cá thể) chiếm một khe
nhất định trong vòng tròn Roulette có độ rộng tỷ lệ với giá trị hàm
mục tiêu của chuỗi. Mỗi lần quay vòng tròn Roulette ta nhận được
một chuỗi và coi như đó là cách lựa chọn cho việc tái tạo quần thể.
Các bước thực hiện như sau:
 Tính giá trị hàm mục tiêu của từng cá thể gọi la F
i

 Tính tổng các giá trị hàm mục tiêu của các các thể trong quần
thể gọi là S
f
.
 Tính xác suất chọn cho mỗi nhiễm sắc thể


=







 Tính xác xuất vị trí cho mỗi nhiễm sắc thể


=
∑



 

Tiến hành tiến trình chọn lọc bằng cách quay bánh xe Roulette n
lần (n là kích thước quần thể), mỗi lần chọn một nhiễm sắc thể từ
quần thể hiện hành vào quần thể mới theo cách sau:
 Chọn một số ngẫu nhiên r trong khoản [0,1]



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 13

Đề Tài: Giải thuật di truyền – Generic Algorithms
 Nếu r < q
1
thì chọn nhiễm sắc thể đầu tiên v
1
, ngược lại thì

chọn nhiễm sắc thể thứ i thuộc đoạn [2,n] sao cho
q
i-1
< r < q
i

Như vậy có thể một nhiễm sắc thể có thể được chọn nhiều lần,
điều này là phù hợp vì các nhiễm sắc thể tốt nhất cần có nhiều bản sao
hơn các nhiễm sắc thể trung bình, còn cá thể kép nhất thì chết đi.

 Quá trình tiến hóa
Thông qua cơ chế chọn lọc tự nhiên và thực hiện các toán tử lai
ghép, đột biến cho nên quần thể ở thế hệ sau sẽ tốt hơn thế hệ trước,
quá trình này lặp di lặp lại ở nhiều thế hệ dẫn đến sự tiến hóa, làm cho
làm cho các cá thể hội tụ gần tới lời giải của bài toán hơn.
5. Các phương pháp biểu diễn nhiễm sắc thể
Giải thuật di truyền với phương pháp biểu diễn nhiễm sắc thể bằng mã hóa
nhị phân đã được đề cập chi tiết trong mục 2 (Giải thuật di tryền tiêu chuẩn).
Ở mục này chúng ta sẽ tìm hiểu một số phương pháp phương pháp biểu diễn
nhiễm sắc thể khác và các toán tử di truyền ứng với từng phương pháp biểu diễn
nhiễm sắc thể đó, nhằm đa dạng khả năng tối ưu hóa của giải thuật di truyền
trong nhiều lớp bài toán khác nhau.
Hình 2



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 14


Đề Tài: Giải thuật di truyền – Generic Algorithms
5.1. Giải thuật di truyền với biểu diễn nhiễm sắc thể bằng số thực
Trong biểu diễn thực, mỗi nhiễm sắc thể được mã hóa thành vector thực
có cùng chiều dài với vector lời giải. Mỗi phần tử được chọn lúc khởi tạo
sao cho thuộc miền xác định của nó, và các toán tử được thiết kế để bảo toàn
các ràng buộc này (không có vấn đề như vậy trong biểu diễn nhị phân,
nhưng thiết kế của các toán tử này khá đơn giản, ta không thấy điều đó là
bất lợi, mặt khác nó lại đem lại những lợi ích khác được trình bày dưới đây)
Ví dụ: Xét bài toán cực đại hàm 4 biến f(x
1
,x
2
,…,x
4
) với nhiều ràng buộc
sau:
x
1
∈ [-0.481,0.519], x
2
є [-1.851,-0.815]
x
3
∈ [-4.631,-3.631], x
4
є [-0.053,0.053]
Giả sử kích thước quần thể pop_size = 10, thì tập hợp các vector biểu
diễn là:
s
1

= (-0.470,-1.811,-4.301,-0.051)
s
2
= (-0.130,-1.420,-4.090,-0.031)
s
3
= (-0.221,-0.901,-4.361,-0.010)
s
4
= (-0.370,-0.950,-4.071,-0.051)
s
5
= (-0.320,-0.930,-3.950,-0.031)
s
6
= (-0.351,-0.970,-4.410,-0.011)
s
7
= (-0.471,-0.991,-3.710,-0.030)
s
8
= (-0.030,-0.920,-3.971,-0.011)
s
9
= (-0.071,-0.911,-4.520,-0.011)
s
10
= (-0.361,-0.901,-4.160,-0.001)
Sự chính xác của cách tiếp cận như thế tùy thuộc vào máy tính nhưng nói
chung là tốt hơn nhiều so với biểu diễn nhị phân. Đương nhiên là ta luôn có

thể tăng độ chính xác của biểu diễn nghị phân khi tăng thêm các bit, nhưng
điều đó làm giải thuật chậm đi đáng kể.



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 15

Đề Tài: Giải thuật di truyền – Generic Algorithms
Hơn nữa biểu diễn thực có khả năng biểu diễn một miền rất rộng (hoặc
các trường hợp miền xác định không cụ thể). Mặt khác trong biểu diễn nhị
phân độ chính xác sẽ giảm khi tăng kích thước miền, do chiều dài chuỗi
nghị phân cố định cho trước.
Các toán tử ta sẽ sử dụng rất khác các toán tử cổ điển, vì chúng làm việc
trong một không gian khác (có giá trị thực). Hơn nữa một vài toán tử không
đồng bộ, nghĩa là hành động của chúng phụ thuộc vào tuổi của quần thể
(tuổi của quần thể hiện tại là số thứ tự của thế hệ đang xét).
5.1.1. Nhóm toán tử lai ghép
 Lai đơn giản: Phép lai đơn giản được xác định như sau:
Nếu s
t
v
= <v
1
,…,v
m
> và
s
t

w
= <w
1
,…,w
m
> được lai ghép ở vị trí k kết quả là:
s
t
v
= <v
1
,…,v
k
,w
k+1
,…,w
m
> và
s
t
w
= <w
1
,…,w
k
,v
k+1
,…,v
m
>

Ví dụ: chọn hai nhiễm sắc thể:
s
5
= (-0.320,-0.930,-3.950,-0.031) và
s
6
= (-0.351,-0.970,-4.410,-0.011)
Cho lai ghép ở vị trí thứ 3, ta có kết quả sau:
S’
5
= (-0.320,-0.930,-3.950,-0.011) và
S’
6
= (-0.351,-0.970,-4.410,-0.031)
 Lai số học đơn: Phép lai số học đơn xác định như sau:
Nếu s
t
v
= <v
1
,…,v
m
> và
s
t
w
= <w
1
,…,w
m

> được lai ghép kết quả là:
s
t+1
v
= <v
1
,…,v’
k
,…,v
m
> và
s
t+1
w
= <w
1
,…,w’
k
,…,w
m
>



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 16

Đề Tài: Giải thuật di truyền – Generic Algorithms
Trong đó 1 ≤ k ≤ m, v’

k
= a × v
k
+ (1 – a) × v
k
và
w’
k
= a × w
k
+ (1 – a) × w
k
, a là giá trị động được xác định theo
vector s
v
và s
w
.
chính xác hơn là a được chọn trong phạm vi:
a ∈

[max
(
,
)
,min (,)]
[0,0]
[max (,),min
(
,

)
]
 

=


Trong đó:
α = (l
k
- w
k
) / (v
k
- w
k
), β = (u
k
- v
k
) / (w
k
- v
k
)
γ = (l
k
- v
k
) / (w

k
- v
k
), δ = (u
k
- w
k
) / (v
k
- w
k
)
Ví dụ: chọn 2 nhiễm sắc thể:
s
5
= (-0.320,-0.930,-3.950,-0.031) và
s
6
= (-0.351,-0.970,-4.410,-0.011)
Cho lai ghép tại vị trí thứ 3 biết x3 ∈ [-4.631,-3.631], ta có:
α = (-4.631 + 4.410) / (-3950 + 4.410) = -0.48
β = (-3.631 + 3.950) / (-4.410 + 3.950) = -0.69
γ = (-4.631 + 3.950) / (-4.410 + 3.950) = 1.48
δ = (-3.631 + 4.410) / (-3.950 + 4.410) = 1.69
a ∈ [-0.48,1.69]
Giả sử a = 1, ta có:
s’
5
= (-0.320,-0.930,-4.410,-0.031) và
s’

6
= (-0.351,-0.970,-3.950,-0.011)
 Lai ghép số học toàn cục: Lai ghép số học toàn cục là tổ hợp
tuyến tính của hai vector được xác định như sau:



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 17

Đề Tài: Giải thuật di truyền – Generic Algorithms
Nếu s
t
v
= <v
1
,…,v
m
> và
s
t
w
= <w
1
,…,w
m
> được lai ghép kết quả là:
s
t+1

v
= × 


+
(
1 − 
)
× 


và
s
t+1
w
= × 


+
(
1 − 
)
× 



với a là một tham số nằm trong đoạn [0,1].
Ví dụ: chọn 2 nhiễm sắc thể:
s
5

= (-0.320,-0.930,-3.950,-0.031) và
s
6
= (-0.351,-0.970,-4.410,-0.011)
Cho lai ghép, giả sử a = 0.6
Ta có các phần tử của s’
5
là:
Pt1 = 0.351×0.6+0.4×(-0.320)=0.083
Pt2 =(-0.970)×0.6+0.4×(-0.930)=-0.954
Pt3 = (-4.410)×0.6+0.4×(-0.950)=-4.226
Pt4 = (-0.011)×0.6+0.4×0.031=0.006
 s’
5
= (0.083,-0.954,-4.226,0.006)
Ta có các phần tử của s’
6
là:
Pt1 = -0.320×0.6+0.4×0.351=-0.052
Pt2 =(-0.930)×0.6+0.4×(-0.970)=-0.946
Pt3 = (-0.950)×0.6+0.4×(-4.410)=-4.134
Pt4 = 0.031×0.6+0.4×(-0.011)=0.014
 s’
5
= (-0.052,-0.946,-4.134,0.014)
5.1.2. Nhóm toán tử đột biến



Giảng viên hướng dẫn: TS.Phạm Thanh Hà

Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 18

Đề Tài: Giải thuật di truyền – Generic Algorithms
 Đột biến đồng bộ:
Đột biến đồng bộ được định nghĩa tương tự với định nghĩa của
phiên bản cổ điển: nếu s
v
= <v
1
,…,v
m
> là nhiễm sắc thể, thì mỗi
phần tử v
k
có cơ hội trải qua tiến trình đột biến ngang nhau.
Kết quả của một lần ứng dụng toán tử này là vector
s
t
v
= <v
1
,…,v
k
,…,v
m
> và v
k
là giá trị ngẫu nhiên trong miền tham
số tương ứng.

Ví dụ: Giả sử phần tử thứ 3 của vector
s
3
= (-0.221,-0.901,-4.361,-0.010) được chọn để đột biến
Biết x
3
∈ [-4.361,-3.361]
Do đó x’
3
được chọn ngẫu nhiên trong khoảng [-4.361,-3.361],
chẳng hạn x’
3
= -4.12
 Đột biến không đồng bộ:
Đột biến không đồng bộ là một trong những toán tử có nhiệm
vụ tìm về độ chính của hệ thống. Nó được định nghĩa như sau:
Nếu s
v
= <v
1
,…,v
m
> là nhiễm sắc thể và phần tử vk được chọn
đột biến này (miền của v
k
là [l
k
,u
k
]).

Kết quả của đột biến không đồng bộ là một vector
s
t+1
v
= <v
1
,…,v’
k
,…,v
m
> với k ∈ [1,…,n] và
v
k
=



+ ∆(,

− 
)
ế ℎữ ố ẫ ℎê à 0


− ∆(,

− 
)
ế ℎữ ố ẫ ℎê à 1


Trong đó hàm ∆(,) trả về trong khoảng [0,y] sao cho xác
suất của ∆(,) gần bằng 0 sẽ tăng khi t tăng. Xác suất này buộc
toán tử tìm kiếm không gian thoạt đầu là đồng bộ (khi t nhỏ) và
rất cục bộ ở những giai đoạn sau. Ta sử dụng hàm sau:



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 19

Đề Tài: Giải thuật di truyền – Generic Algorithms
∆(,) = × 
(


)

, với r là số ngẫu nhiên trong khoảng
[0,…,1], T là số thế hệ tối đa và b là tham số hệ thống xác định
mức độ không đồng bộ.
Hình trên biểu diễn giá trị của ∆ đối với hai lần được chọn nó
hiển thị rõ ràng cách ứng xử của toán tử.
Hơn nữa ngoài cách áp dụng đột biến chuẩn ta có một số cơ
chế mới: đột biết không đồng bộ cũng được áp dụng cho vector
lời giải thay vì chỉ một phần tử duy nhất của nó
Ví dụ: Giả sử phần tử thứ 2 của vector
S4 = (-0.370,-0.950,-4.071,-0.051) được chọn đột biến
Biết x2 ∈ [-1.851,-0.815], lúc đó
Vì k chẵn nên:




= 

− ∆
(
,0.950—1.815
)
=

− ∆(,0.865)

Giả sử =0.4,


=0.5,=2 ta có:
∆
(
,0.865
)
=0.865× 1 − 0.4
.

=0.865 × 0.6=0.519
Do đó 


=−0.950 − 0.519=−1.469 ∈
[

−1.851,−0.815
]

5.2. 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ự
Đễ tránh việc trùng lặp về nội dung chi tiết về phương pháp biểu diễn
nhiễm sắc thể bằng mã hóa ký tự sẽ được trình bày chi tiết ở chương II.





Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 20

Đề Tài: Giải thuật di truyền – Generic Algorithms
Chương II: Bài toán “Người đưa thư”, ứng dụng giải thuật di truyền để giải
bài toán “Người đưa thư”.
1. Bài toán “Người đưa thư”
1.1. Lịch sử
Thử đặt ra một vấn đề đơn giản sau: bạn là một nhân viên đưa thư và
khách hàng của bạn lại nằm rải rác trên một loạt các thành phố. Bạn biết
chính xác khoảng cách giữa mỗi 2 thành phố và muốn tìm con đường ngắn
nhất để có thể đến thăm mỗi thành phố một lần và sau đó trở về nhà, nơi bạn
xuất phát.
Trong khoa học máy tính, ví dụ trên được gọi là "bài toán người đưa
thư" hay bài toán “người bán hàng” (traveling salesman problem). Đây là
một vấn đề rất cơ bản và ứng dụng của nó thì nhiều vô kể. Một ứng dụng rất
điển hình là hoạt động hàng ngày của các công ty chuyển phát. Công việc
của họ là phải phân phát và tiếp nhận hàng hóa sao cho ít tốn thời gian và

chi phí nhiên liệu nhất trong khi vẫn đảm bảo không bỏ sót bất cứ điểm đến
nào. Ngoài ra, vấn đề trên còn được các nhà sản xuất điện tử áp dụng để tạo
ra những con chíp siêu nhỏ tốt hơn hay được các nhà di truyền học sử dụng
vào chuỗi DNA.
Vấn đề trên không phải dễ và phương pháp trực tiếp nhằm tìm ra lời giải
phổ biến là kiểm tra tất cả các tổ hợp. Tuy nhiên, trên thực tế phương pháp
này không thật sự khả thi bởi nếu lấy mẫu chỉ gồm 20 thành phố thì sẽ có
gần 60,8 triệu tỉ phép so sánh để tìm ra hành trình có lợi nhất.
1.2. Phát biểu bài toán như sau
Cho đồ thị đầy đủ đỉnh vô hướng, có trọng số G = (V,E). Tìm chu trình


→ 

→⋯ →

→ 

ớ 

∈à  ∈[1,] sao cho tổng trọng số
hành trình trên các cạnh (v
i
,v
i+1
) và (v
n
,v
1
) là nhỏ nhất.

Một chu trình như vậy gọi là chu trình Hamilton, nó đi qua tất cả các
đỉnh của đồ thị đúng một lần, đồ thị đầy đủ luôn tồn tại chu trình Hamilton.
1.3. Phần tích độ phức tạp
Bài toán người đưa thư thuộc lớp bài toán NP-Khó (lớp các bài toán
không có giải thuật trong thời gian đa thức).



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 21

Đề Tài: Giải thuật di truyền – Generic Algorithms
Việc thực hiện liệt kê hết tất cả các chu trình là điều gần như không thể
với số đỉnh lớn (đồ thị n đỉnh phải duyệt n! chu trình). Số chu trình phải
duyệt tăng rất nhanh khi số đỉnh n càng lớn. Ngay với 1 đồ thị 100 đỉnh,
việc duyệt toàn bộ cũng là điều rất khó thực hiện.
2. Ứng dụng giải thuật di truyền để giải bài toán người đưa thư, biểu diễn
nhiễm sắc thể bằng ký tự
Giải thuật di truyền mô phỏng sự tiến hóa của thế giới tự nhiên, ở đó thông
tin về một cấu trúc sống được mã hóa dưới dạng nhiễm sắc thể. Do đó áp dụng
giải thuật di truyền vào bài toán người đưa thư, ta cũng phải tìm cách mã hóa các
lời giải của bài toán dưới dạng chuỗi các gene tạo thành các nhiễm sắc thể và xây
dựng quy tắc đánh giá độ thích nghi cũng như xây dựng các toán tử di truyền của
nó theo ngữ cảnh của bài toán. Với bài toán này em lựa chọn phương pháp mã
hóa nhiễm sắc thể bằng ký tự.
Kí hiệu các địa điểm là A,B,C,… mỗi địa điểm là 1 gene của nhiễm sắc thể,
nhiễm sắc thể đại diên cho một cá thể trong một quần thể. Mỗi nhiễm sắc thể là
sự mã hóa của lời giải biểu diễn lộ trình mà người đưa thư đi qua.
Ví dụ: GFHBACDE sẽ là kí hiệu của hành trình từ:

G -> F -> H -> B -> A -> C -> D -> E
Mỗi địa điểm(gene) sẽ chỉ xuất hiện trong danh sách này chỉ một lần. Vấn đề
này dẫn tới khó khăn không thể áp dụng các kỹ thuật sinh sản, đột biến thường
được sử dụng trong giải thuật di truyền tiêu chuẩn.
Ví dụ: với ý nghĩa lai ghép chéo thông thường ta nhận được kết quả như sau:
 Ghép chéo tại 1 điểm


 Ghép chép tại 2 điểm:
Hình 3



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 22

Đề Tài: Giải thuật di truyền – Generic Algorithms


Điều kiện chỉ xuất hiện một trong danh sách hoàn vị ở hai ví dụ trên đã bị vi
phạm. Do đó đòi hỏi phải xây dựng các kỹ thuật ghép chéo mới phù hợp với ý
nghĩa của bài toán.
2.1. Ghép chéo riêng từng phần (Partailly matched crossover – PMX)
PMX được cải tiến từ phương pháp lai ghép thông thường. Bước đầu
tiên là sao chép cấu trúc nhiễm sắc thể của cha và mẹ tạo ra một cặp cá thể
con giống cặp cá thể bố mẹ.

Sao chép để tạo 2 cá thể con:


Bước tiếp theo PMX chọn ngẫu nhiên 2 vị trí, vi dụ: 2 và 5:
PMX nhận thấy gene H trong nhiễm sắc thể 2 được thấy thế gene C
trong nhiễm sắc thể 1, vì vậy nó sẽ chuyển đổi H của nhiễm sắc thể 1 thành
C và C trong nhiễm sắc thể 2 thành H. Quá trình được thực hiện tượng tự với
2 gene còn lại và cuối cùng ta nhận được con cái như sau:
Hình 4
Hình 6
Hình 7



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 23

Đề Tài: Giải thuật di truyền – Generic Algorithms


2.2. Ghép chéo có thứ tự (Order crossover – OX)
Bước đầu tiên OX cũng thực hiện sao chép cấu trúc nhiễm sắc thể của
cha và mẹ tạo ra một cặp cá thể con giống cặp cá thể bố mẹ.

Sao chép để tạo 2 cá thể con:

Bước tiếp theo OX chọn ngẫu nhiên 2 vị trí, vi dụ: 2 và 5: và thực hiện
hoàn đổi các gene trong doạn được chọn và bỏ trống một số gene trùng lặp ở
các đoạn còn lại như sau.

Hình 8
Hình 9

Hình 10
Hình 11



Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 24

Đề Tài: Giải thuật di truyền – Generic Algorithms
Tiếp đó OX dịch chuyển dịch chuyển các chỗ trống đếm khi chúng gặp
nhau tại miền giao nhau (trong đoạn đã chọn ở trên).

Cuối cùng OX thực hiện sao chép các gene trong đoạn được chọn từ cá
thể bố mẹ sang cá thể con cái ta được các con cái như sau:


2.3. Phép đảo vị trí (Inversion operator)
Để tăng tính đa dạng của quần thể có thể đưa thêm vào bài toán phép
hoàn vị, thực hiện việc đảo ngược vị trí các gene trong nhiễm sắc thể.
Ví dụ:
Đảo vị trí tại 1 điểm:

Đảo vị trí tại 2 điểm:


Hình 12
Hình 13
Hình 14
Hình 15




Giảng viên hướng dẫn: TS.Phạm Thanh Hà
Sinh viên: Hà Văn Tân – Lớp LT.CNTT-K16A
Trang 25

Đề Tài: Giải thuật di truyền – Generic Algorithms
2.4. Phép đột biết
Phép đột biến được định nghĩa lại rất đơn giản dưới dạng hoán vị vị trí
của 2 gene bất kỳ trong nhiễm sắc thể.
Ví dụ chọn 2 vị trí ngẫu nhiên là 2 và 6:








Hình 16