ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
TIỂU LUẬN MÔN HỌC
THUẬT TOÁN VÀ PHƯƠNG PHÁP
GIẢI QUYẾT VẤN ĐỀ
ĐỀ TÀI
ỨNG DỤNG THUẬT TOÁN DI TRUYỀN VÀO BÀI
TOÁN NGƯỜI DU LỊCH
Giảng viên hướng dẫn : PGS.TS Đỗ Văn Nhơn
Học viên thực hiện: Trần Văn Cường
MSHV : CH1301083
TP.HCM 10/2014
MỤC LỤC
MỤC LỤC 2
LỜI CẢM ƠN 1
LỜI MỞ ĐẦU 2
PHẦN I. CƠ SỞ LÝ THUYẾT 3
I. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN 3
II. TỔNG QUAN BÀI TOÁN NGƯỜI DU LỊCH 13
PHẦN II. ỨNG DỤNG THUẬT GIẢI DI TRUYỀN VÀO BÀI TOÁN NGƯỜI DU LỊCH
16
I. MÃ HÓA BÀI TOÁN 16
II. KHỞI TẠO QUẦN THỂ 16
III. LAI GHÉP 17
IV. ĐỘT BIẾN 18
V. CHỌN LỌC TỰ NHIÊN 19
VI. TIẾN HOÁ 20
KẾT LUẬN 21
TÀI LIỆU THAM KHẢO 22
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
LỜI CẢM ƠN

I. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN
1. Giới thiệu
Trong thuật giải di truyền người ta dùng thuật ngữ vay mượn của di truyền
học như: cá thể, nhiễm sắc thể (nhiễm sắc thể), gen, quần thể, độ thích nghi, chọn
lọc, lai ghép, đột biến, v.v… Trong đó cá thể (individual, genotypes, structure) biểu
diễn một lời giải, giải pháp của bài toán, không giống như trong tự nhiên một cá thể
có thể có nhiều nhiễm sắc thể, ở đây chúng ta quy ước mỗi cá thể chỉ có một nhiễm
sắc thể (chromosome). Các nhiễm sắc thể là một có thể là một chuỗi tuyến tính, trong
nhiễm sắc thể có thể có các đơn vị nhỏ hơn đó là gen. Mỗi gen đại diện một thuộc
tính, tính chất và có vị trí nhất định trong nhiễm sắc thể. Quần thể (population) là
một tập hợp hữu hạn xác định các cá thể, trong thuật giải di truyền quần thể là một
tập
- Xây dựng hàm thích nghi làm tiêu chuẩn đánh giá các cá thể theo độ thích
nghi của chúng.
- Xác định xác suất lai tạo, xác suất đột biến, …
- Xây dựng các phép toán lai tạo, chọn lọc, đột biến.
2. Thuật giải di truyền
Bài toán dành cho GA là tìm kiếm trên không gian các giả thuyết ứng cử để xác
định giả thuyết tốt nhất. Trong GA “giả thuyết tốt nhất” được định nghĩa như là một
giả thuyết tối ưu hóa một đại lượng số được định nghĩa trước cho bài toán sắp tới, được
gọi là độ thích nghi của giả thuyết. Ví dụ, nếu tác vụ học hỏi là bài toán xấp xỉ một
hàm chưa biết cho tập mẫu huấn luyện gồm dữ liệu đầu vào và dữ liệu đầu ra, thì độ
thích nghi có thể được định nghĩa như là độ chính xác của giả thuyết trên dữ liệu huấn
luyện này. Nếu tác vụ là học chiến lược chơi cờ, độ thích nghi có thể là số ván thắng
của chiến lược này khi đấu với các chiến lược khác trong quần thể hiện tại.
HV: Trần Văn Cường – MSHV: CH1301083 Trang 3
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
Mặc dù các thuật giải di truyền được thực hiện thay đổi theo bài toán cụ thể,
nhưng chúng chia sẻ chung cấu trúc tiêu biểu sau: Thuật giải hoạt động bằng cách cập
nhật liên tục tập giả thuyết - được gọi là quần thể. Ở mỗi lần lặp, tất cả các cá thể trong

) đã tính ở bước trên. Ứng với mỗi cặp <h
1
, h
2
>, tạo ra hai con bằng
cách áp dụng toán tử lai ghép. Thêm tất cả các con vào P
S
.
3. Đột biến: Chọn m% các thể P
S
với xác suất cho mỗi cá thể là như nhau. Ứng
với mỗi cá thể biến đổi một bit được chọn ngẫu nhiên trong cách thể hiện của nó.
4. Cập nhật: P  P
S
5. Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)
• Trả về giả thuyết P có độ thích nghi cao nhất
}
Hình: Các bước cơ bản của giải thuật
HV: Trần Văn Cường – MSHV: CH1301083 Trang 5
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
Sơ đồ mô tả giải thuật di truyền
3. Các toán tử di truyền
a. Biểu diễn cá thể
Công việc đầu tiên khi thực hiện việc giải bài toán bằng giải thuật di truyền là
chọn cách biểu diễn các cá thể. Đó là việc ánh xạ các tham số của bài toán lên một
chuỗi có chiều dài xác định. Tuỳ theo từng bài toán cụ thể mà có những cách biểu diễn
khác nhau sao cho phù họp, thuận lợi khi giải toán. Trong đó có hai cách biểu diễn
thông dụng nhất là biểu diễn nhị phân và biểu diễn sử dụng các hoán vị.
Biểu diễn nhị phân
HV: Trần Văn Cường – MSHV: CH1301083 Trang 6

Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
kỳ liên quan đến bài toán, từ số nguyên, số thực, ký tự cho đến các đối tượng
phức tạp hơn.
Một ví dụ cho cách mã hóa này là bài toán tìm trọng số mạng nơron.
Biểu diễn theo cây
Mã hóa theo cây được dùng chủ yếu cho các chương trình (hoặc biểu
thức) tiến hóa, cho lập trình gen. Trong mã hóa theo cây mọi nhiễm sắc thể là
một cây chứa các đối tượng chẳng hạn như hàm hoặc lệnh trong một ngôn ngữ
lập trình nào đó.
Ví dụ: bài toán tìm hàm từ những giá trị cho trước. Cho trước một số đầu
vào và đầu ra. Tìm hàm cho ra kết quả tốt nhất với mọi đầu vào.
Mã hóa: Nhiễm sắc thể là các hàm được biểu diễn bằng cây.
=> Sau khi đã biếu diễn được các cá thể cho bài toán rồi thì có thể bắt
tay ngay vào việc thực hiện giải thuật di truyền theo sơ đồ đã có trong phần
trước. Bước đầu tiên là cần có một quần thể ban đầu. Nó có thể có được bằng
cách chọn ngẫu nhiên các cá thể; hoặc có thể dùng chiến thuật lựa chọn thông
qua hàm mục tiêu sẽ được trình bày ngay sau đây.
b. Hàm mục tiêu Fitness
Một hàm mục tiêu (fitness) sẽ lấy một chuỗi nhiễm sắc thể như là đầu vào và trả
về giá trị tượng trưng cho chuỗi nhiễm sắc thể đó đế đánh giá trên vấn đề cần giải
quyết.
Hàm mục tiêu có vai trò tương tự như là môi trường sống trong sự tiến hóa của
tự nhiên, vấn đề tương tác giữa một cá thể với môi trường sống được thể hiện qua giá
trị cuả hàm mục tiêu trong mỗi một cá thể.
Giá trị hàm mục tiêu là Maximum hay Minimum tùy theo bài toán sẽ quyết định
xác suất của mỗi chuỗi có thể tham gia vào các toán tử di truyền.
c. Toán tử tái tạo
Là một quá trình mà trong đó các chuỗi được lựa chọn tùy thuộc vào giá trị hàm
mục tiêu. Hàm mục tiêu f(i) được gán cho mỗi cá thể trong một quần thể, và những cá
HV: Trần Văn Cường – MSHV: CH1301083 Trang 8

Chọn lọc loại bỏ
Các làm rất đơn giản: dùng một ngưỡng lựa chọn đế xác định các cá thể
được lựa chọn. Theo đó các cá thể có giá trị hàm mục tiêu nhỏ hơn ngưỡng thì
sẽ bị loại bỏ, còn các cá thể có giá trị hàm mục tiêu lớn hơn ngưỡng thì được
lựa chọn.
d. Lai ghép
Phép lai là quá trình hình thành NST mới trên cơ sở NST cha mẹ, bằng cách
ghép một hay nhiều đoạn gen của hai (hay nhiều) NST cha mẹ khác nhau.
Các cặp cha mẹ được lựa chọn ngẫu nhiên và xác suất xảy ra lai ghép với mỗi
cặp được quy định từ trước.
Có nhiều cách lai ghép khác nhau:
• Lai ghép một điểm cắt, nhiều điểm cắt
• Lai ghép nhiều đoạn
e. Đột biến
Đột biến là tình trạng NST con không có một (hoặc một số) tính trạng có trong
mã di truyền của cha mẹ.
Các cặp cha mẹ được lựa chọn ngẫu nhiên và xác suất xảy ra đột biến với mỗi
cặp được quy định từ trước, thường là rất nhỏ.
Các phép đột biến thường được sử dụng:
• Đảo bit
HV: Trần Văn Cường – MSHV: CH1301083 Trang 10
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
• Hoán vị: Đổi vị trí của các gen với nhau
• Đổi giá trị: Thay đổi giá trị tại một điểm gen
• Đảo đoạn: Đảo thứ tự của một đoạn NST bất kì.
4. Đấu tranh sinh tồn
Chọn những NST từ quần thể kết quả theo một quy tắc nào đó thay thế cho cha
mẹ để sinh ra thế hệ mới. Một số phương thức đấu tranh sinh tồn cơ bản:
• Tráo đổi hoàn toàn cha mẹ bằng con.
• Tráo đổi ngẫu nhiên: Chọn ngẫu nhiên k cha mẹ và thay thế bằng k con

- Chọn lọc xếp hạng
- Chọn lọc cạnh tranh
Phương pháp lai ghép
- Lai ghép một điểm
- Lai ghép đa điểm
- Lai ghép ánh xạ từng phần
- Lai ghép có trật tự
- Lai ghép dựa trên vị trí
- Lai ghép thứ tự tuyến tính
- Lai ghép có chu trình
Toán tử đột biến
Điều kiện dừng của thuật giải
Một số điều kiện dừng của thuật giải:
Kết thúc theo kết quả, tức khi giá trị thích nghi của cá thể trong quần thể có giá
trị sai số nhỏ hơn một giá trị cho trước, thì dừng thuật toán.
Kết thúc dựa trên số thế hệ, một số vấn đề dựa vào số thế hệ trong quần thể.
Khi số lượng tiến hoá của quần thể đến một giới hạn cho phép thì thuật toán sẽ dừng,
HV: Trần Văn Cường – MSHV: CH1301083 Trang 12
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
mà trong khi không quan tâm đến chất lượng của cá thể trong quần thể như thế nào.
Tính theo thời gian, phụ thuộc vào thời gian chạy chương trình được quy định
trước và thuật toán dừng.
Kết hợp nhiều phương pháp khác nhau, thuật giải cũng có thể sử dụng kết hợp
nhiều phương pháp khác nhau để giải quyết vấn đề.
Các tham số của thuật giải di truyền
- Kích thước quần thể
- Xác suất lai ghép
- Xác suất đột biến
II. TỔNG QUAN BÀI TOÁN NGƯỜI DU LỊCH
1. Lịch sử bài toán

Điều này giải thích một cách khoa học cho độ phức tạp tính toán của việc tìm lời giải
tối ưu cho bài toán .
Nhiều thành tựu đã đạt được trong suốt những năm cuối thập kỷ 1970 và 1980,
khi Grötschel, Padberg, Rinaldi và những người khác cố gắng giải một cách chính
xác một thể hiện của bài toán với 2392 thành phố, sử dụng phương thức cắt và
branch-and-bound.
Trong những năm 1990 Applegate, Bixby, Chvátal, và Cook đã phát triển
chương trình Concorde mà đã được sử dụng nhiều trong việc giải các bài toán TSP
cho đến nay . Gerhard Reinelt đã công bố thư viện TSPLIB vào năm 1991, đó là một
tập các thể hiện của bài toán TSP với nhiều độ khó khác nhau, và đã được sử dụng
bởi nhiều nhóm nghiên cứu khác nhau để so sánh kết quả. Năm 2005, Cook và những
người khác đã tính được độ dài tối ưu cho chu trình với thể hiện của bài toán TSP lên
tới 33,810 thành phố , được lấy ra từ bài toán xây dựng layout cho microchip, cho tới
nay vẫn là thể hiện lớn nhất trong các thể hiện ở TSPLIB .Nhiều thể hiện khác với
HV: Trần Văn Cường – MSHV: CH1301083 Trang 14
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
hàng triệu thành phố , lời giải tìm được có thể chứng minh nằm sai khác 1% so với
lời giải tối ưu.
2. Mô tả bài toán
TSP có thể được mô hình như một đồ thị , các đỉnh của đồ thị tương ứng với các
thành phố và các cạnh thì tương ứng với đường nối giữa các thành phố, chiều dài của
một cạnh tương ứng với khoang cách giữa 2 thành phố. Một đường đi trong bài toán
TSP là một chu trình Hamilton trên đồ thị và một lời giải tối ưu của bài toán là chu
trình Hamilton ngắn nhất.
Thường thì đồ thị là đồ thị đầy đủ , vì vậy mọi cặp cạnh đều được nối bởi các
cạnh. Đây là bước đơn giản hóa bài toán vì việc tìm chu trình Hamilton trong một đồ
thị đầy đủ là dễ. Các bài toán mà không phải 2 thành phố nào cũng được nối với nhau
có thể được chuyển đổi thành đồ thị đầy đủ bằng cách thêm những cạnh có độ dài lớn
giữa cách thành phố này , những cạnh sẽ không xuất hiện trong chu trình tối ưu.
3. Phân tích độ phức tạp

(theo công thức tính khoảng cách ở trên).
Mỗi chu trình là một lời giải, trong giải thuật di truyền coi đó như một cá thể.
Việc tiến hoá về sau ta sẽ dựa trên tập chu trình khởi tạo ban đầu và tìm ra kết quả tốt
nhất sau một số thế hệ.
II. Khởi tạo quần thể
Quần thể ban đầu được khởi tạo bằng cách sinh ngẫu nhiên các chu trình, số
lượng chu trình khởi tạo là một nửa số kích thước cá thể tối đa. Việc sinh ngẫu nhiên
HV: Trần Văn Cường – MSHV: CH1301083 Trang 16
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
sử dụng hàm đột biến. Số kích thước cá thể tối đa có thể tùy biến theo số đỉnh của đồ
thị cần giải, có thể chọn kích thước của quần thể là 100 cá thể.
III. Lai ghép
Phương thức lai ghép được thực hiện dựa trên 2 cá thể đầu vào:
C1 1 3 2 4 6 9 8 7 5 10
C2 10 7 9 6 4 2 8 3 1 5
Thực hiện lai ghép một điểm cắt với vị trí cắt là ngẫu nhiên:
- Cắt từ điểm p đến hết chu trình của C2 đưa vào chu trình mới, lấy một ví
dụ p=5;
Con 2 8 3 1 5
- Xét từ đầu đến cuối chu trình 1, nạp dần các điểm chưa có trong con lai
theo thứ tự duệt ta được chu trình mới
Con 2 8 3 1 5 4 6 9 7 10
- Tính lại chi phí cho chu trình mới sinh.
Thuật toán:
private Circle hybridize(Circle c1, Circle c2) {
Circle child = new Circle(c1.getLength());
Random rand = new Random();
int p = rand.nextInt(child.length - 1);
int i = 0, j = 0, k = 0;
for (i = p; i < child.length; i++)

{
int n = c.getLength();
Circle nextgen = new Circle(n);
HV: Trần Văn Cường – MSHV: CH1301083 Trang 18
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
nextgen.setCircle(n, c.getCircle());
Random rand = new Random();
int count = rand.nextInt(mutateCoefficient) + 1;
int p1, p2, temp;
while (count > 0)
{
p1 = rand.nextInt(n);
p2 = rand.nextInt(n);
temp = nextgen.vertex[p1];
nextgen.vertex[p1] = nextgen.vertex[p2];
nextgen.vertex[p2] = temp;
count ;
}
return nextgen;
}
V. CHỌN LỌC TỰ NHIÊN
- Sắp xếp quần thể theo chi phí tăng dần.
- Lựa chọn ngẫu nhiên 1 chỉ số a (0<a<1)
- Loại cá thể thứ a[Kích thước mặc định] kém thích nghi nhất từ [Kích thước
mặc định] cá thể đứng đầu danh sách quần thể.
- Loại đến khi số cá thể còn lại bằng kích thước mặc định.
Thuật toán:
private void sortList() { // Selection sort
int i = 0, j = 0, min;
Circle temp;

Trong thời gian nghiên cứu, tìm hiểu thuật toán để giải quyết bài toán người du lịch,
đề tài đã đạt được các kết quả sau:
− Báo cáo đã làm rõ các khái niệm về giải thuật di truyền và các bước thực
hiện khi áp dụng vào giải quyết bài toán người du lịch
− Nghiên cứu tìm hiểu nội dung, lịch sử, mô tả về bài toán người du lịch.
− Từ đó rút ra những ưu nhược điểm của phương pháp trong giải bài toán
người du lịch.
Từ kết quả nghiên cứu lý thuyết và thực tiển, bài tiểu luận đề ra các vấn đề cần tiếp
tục hoàn thiện, phát triển và nghiên cứu như sau:
− Tiếp tục nghiên cứu thêm các thuật toán khác áp dụng giải bài toán người du
lịch. Từ đó rút ra nhận xét và đánh giá về tính hiệu quả các thuật toán.
− Tiếp tục nghiên cứu thực nghiệm để tìm ra lời giải tối ưu áp dụng cho bài toán
người du lịch.
Với khả năng và thời gian có hạn, bài tiểu luận chắc chắn còn những thiếu sót trong
phần trình bày và nội dung, kính mong Thầy góp ý để tác giả hoàn thiện hơn
HV: Trần Văn Cường – MSHV: CH1301083 Trang 21
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
TÀI LIỆU THAM KHẢO
[1] PGS.TS Đỗ Văn Nhơn (2014), slide bài giảng môn Phương pháp giải quyết vấn đề;
[2] TS Nguyễn Đình Thúc (2008), Giáo trình Trí Tuệ Nhân Tạo – Lập trình
tiến hóa
[3] h

t t p

: //

v

i .


ư

ờ

i _

b á

n_

h à

n

g (10/2014)
HV: Trần Văn Cường – MSHV: CH1301083 Trang 22
Phương pháp và Thuật toán giải quyết vấn đề GVHD: PGS.TS Đỗ Văn Nhơn
NHẬN XÉT CỦA GIÁO VIÊN