Giải thuật di truyền với bài toán người du lịch

Bài tập lớn môn học Trí tuệ nhân tạo 4

• GA có thể tìm kiếm trên các không gian giả thuyết có các phần tương
tác phức tạp, ở đó ảnh hưởng của mỗi phần lên toàn thể độ thích nghi
giả thuyết khó có thể mô hình.
• Thuật giải GA có thể được thực hiện song song và có thể tận dụng
thành tựu của phần cứng máy tính mạnh.

2. Thuật giải di truyền
Bài toán dành cho GAs 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 GAs “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.
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 quần thể được ước lượng tương ứng với hàm thích nghi. Rồi
quần thể mới được tạo ra bằng cách lựa chọn có xác suất các cá thể thích nghi tốt
nhất từ quần thể hiện tại. Một số trong những cá thể được chọn được đưa nguyên
vẹn vào quần thể kế tiếp. Những cá thể khác được dùng làm cơ sở để tạo ra các
cá thể con bằng cách áp dụng các tác động di truyền: lai ghép và đột biến.

GA( Fitness, Fitness_threshold, p, r, m)

Bài tập lớn môn học Trí tuệ nhân tạo 5

{
// Fitness: hàm gán thang điểm ước lượng cho một giả thuyết
// Fitness_threshold: Ngưỡng xác định tiêu chuẩn dừng giài thuật tìm kiếm
// p: Số cá thể trong quần thể giả thuyết
// r: Phân số cá thể trong quần thể được áp dụng toán tử lai ghép ở mỗi
bước
// m: Tỉ lệ cá thể bị đột biến

• Khởi tạo quần thể: P  Tạo ngẫu nhiên p cá thể giả thuyết
• Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)
• while [max Fitness(h)] < Fitness_threshold do
Tạo thế hệ mới, P
S

1. Chọn cá thể: chọn theo xác suất (1 – r)p cá thể trong quần thể P
thêm vào P
S
. Xác suất Pr(h
i
) của giả thuyết h
i
thuộc P được tính
bởi công thức:
1
( )
Pr( )
( )
i
i
p
j
j
Fitness h
h
Fitness h
=
=
∑

2. Lai ghép: chọn lọc theo xác suất
2
r p×
cặp giả thuyết từ quần thể
P, theo Pr(h
i
) đã 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ác
con vào P
S
.
3. Đột biến: Chọn m% cá thể của 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)

Bài tập lớn môn học Trí tuệ nhân tạo 6

• Trả về giả thuyết trong P có độ thích nghi cao nhất.
}
Figure 1 : Các bước cơ bản của giải thuật



Bài tập lớn môn học Trí tuệ nhân tạo 7




Khởi tạo quần thể
Lựa chọn cha mẹ
Lai ghép
Đột biến
Điều kiện dừng
Đấu tranh sinh tồn
Các cá thể tốt nhất
TRUE
FALSE
Figure 2 : Lưu đồ giải thuật cơ bản


Bài tập lớn môn học Trí tuệ nhân tạo 8

3. Các toán tử di truyền
3.1 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.

3.2 Độ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.
• 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ì.

Bài tập lớn môn học Trí tuệ nhân tạo 9

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 mới.
• Chọn những cá thể ưu tú nhất trong quần thể.



Bài tập lớn môn học Trí tuệ nhân tạo 10

CHƯƠNG II : BÀI TOÁN NGƯỜI DU LỊCH (Travelling Salesman
Problem - TSP)

1. Lịch sử bài toán :
Bài toán người bán hàng (tiếng Anh: travelling salesman problem - TSP) là
một bài toán NP-Hard thuộc thể loại tối ưu tổ hợp được nghiên cứu trong lý
thuyết khoa học máy tính. Nội dung bài toán có thể hiểu khái quát như sau : Cho
trước một danh sách các thành phố và khoảng cách giữa chúng, tìm chu trình
ngắn nhất đi qua tất cả các thành phố đúng 1 lần.

Figure 3 22,775 Cities in Vietnam, derived from data from the National Imagery and Mapping Agency database of
geographic feature names.

Bài toán được nêu ra lần đầu tiên năm 1930 và là một trong những bài toán
được nghiên cứu sâu nhất trong tối ưu hóa. Nó thường được dùng làm thước đo
cho nhiều phương pháp tối ưu hóa. Mặc dù bài toán rất khó giải trong trường hợp
tổng quát, có nhiều phương pháp giải chính xác cũng như heuristic đã được tìm
ra để giải quyết một số trường hợp có tới hàng chục nghìn thành phố.
Ngay trong hình thức phát biểu đơn giản nhất, bài toán TSP đã có nhiều
ứng dụng trong lập kế hoạch, hậu cần, cũng như thiết kế vi mạch, …
Nguồn gốc của bài toán người bán hàng vẫn chưa được biết rõ. Một cuốn sổ
tay dành cho người bán hàng xuất bản năm 1832 có đề cập đến bài toán này và

Bài tập lớn môn học Trí tuệ nhân tạo 11

có ví dụ cho chu trình trong nước Đức và Thụy Sĩ, nhưng không chứa bất kì nội
dung toán học nào.
Bài toán người bán hàng được định nghĩa trong thế kỉ 19 bởi nhà toán học
Ireland William Rowan Hamilton và nhà toán học Anh Thomas Kirkman.
Trường hợp tổng quát của TSP có thể được nghiên cứu lần đầu tiên bởi các nhà
toán học ở Vienna và Harvard trong những năm 1930.
Hassler Whitney ở đại học Princeton đưa ra tên bài toán người bán hàng
ngay sau đó.
Trong những năm 1950 và 1960, bài toán trở nên phổ biến trong giới
nghiên cứu khoa học ở Châu Âu và Mỹ. George Dantzig, Delbert Ray Fulkerson
và Selmer M. Johnson ở công ty RAND tại Santa Monica đã có đóng góp quan
trọng cho bài toán này, biểu diễn bài toán dưới dạng quy hoạch nguyên và đưa ra
phương pháp mặt phẳng cắt để tìm ra lời giải. Với phương pháp mới này, họ đã
giải được tối ưu một trường hợp có 49 thành phố bằng cách xây dựng một chu
trình và chứng minh rằng không có chu trình nào ngắn hơn. Trong những thập
niên tiếp theo, bài toán được nghiên cứu bởi nhiều nhà nghiên cứu trong các lĩnh
vực toán học, khoa học máy tính, hóa học, vật lý, và các ngành khác.
Năm 1972, Richard M. Karp chứng minh rằng bài toán chu trình Hamilton
là NP-đầy đủ, kéo theo bài toán TSP cũng là NP-đầy đủ. Đây là một lý giải toán
học cho sự khó khăn trong việc tìm kiếm chu trình ngắn nhất.
Một bước tiến lớn được thực hiện cuối thập niên 1970 và 1980 khi
Grötschel, Padberg, Rinaldi và cộng sự đã giải được những trường hợp lên tới
2392 thành phố, sử dụng phương pháp mặt phẳng cắt và nhánh cận.
Trong thập niên 1990, Applegate, Bixby, Chvátal, và Cook phát triển một
chương trình mang tên Concorde giải được nhiều trường hợp có độ lớn kỉ lục
hiện nay. Gerhard Reinelt xuất bản một bộ dữ liệu các trường hợp có độ khó
khác nhau mang tên TSPLIB năm 1991, và nó đã được sử dụng bởi nhiều nhóm

Bài tập lớn môn học Trí tuệ nhân tạo 12

nghiên cứu để so sánh kết quả. Năm 2005, Cook và cộng sự đã giải được một
trường hợp có 33810 thành phố, xuất phát từ một bài toán thiết kế vi mạch. Đây
là trường hợp lớn nhất đã được giải trong TSPLIB.
Đến nay bài toán TSP vẫn được tiếp tục nghiên cứu tìm ra lời giải cho các
bộ dữ liệu lớn hơn. Chẳng hạn bộ dữ liệu của nước Mĩ với 115,475 thành phố
người giải ra chu trình tối ưu được trao thưởng 500$ (thông tin chi tiết tại
http://www.tsp.gatech.edu/).

2. Phát biểu bài toán :
(*) Các khái niệm cơ bản về đồ thị sẽ không được trình bày trong báo cáo.
Phát biểu bài toán : Cho đồ thị đầy đủ n đỉnh vô hướng, có trọng số G = (V,
E). Tìm chu trình ݒ
ଵ
→ݒ
ଶ
→...ݒ
௡
→ݒ
ଵ
với ݒ
௜
∈ܸ,݅ = 1,݊
തതതതത
sao cho tổng trọng
số hành trình trên các cạnh (ݒ
௜
,ݒ
௜ାଵ
) và (ݒ
௡
,ݒ
ଵ
) là nhỏ nhất.
Một chu trình như vậy còn gọi là chu trình Hamilton, nó đi qua tất cả các
đỉnh của đồ thị đúng 1 lần. Đồ thị đầy đủ, luôn tồn tại chu trình Hamilton.

3. Phân tích độ phức tạp :
Bài toán TSP 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).
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.


Bài tập lớn môn học Trí tuệ nhân tạo 13

CHƯƠNG III : ĐỀ XUẤT GIẢI THUẬT DI TRUYÊN GIẢI BÀI TOÁN
NGƯỜI DU LỊCH

1. Giải thuật đề xuất :
Nhóm đề xuất giải thuật di truyền đơn giản giải bài toán người du lịch. Giải
thuật được cài đặt bằng ngôn ngữ java.
Các bộ dữ liệu kiểm thử được lấy tại http://www.tsp.gatech.edu/ (cung cấp
các bộ dữ liệu chuẩn trên thực tế)

1.1 Mã hóa bài toán :
1.1.1 Mã hóa đồ thị :
Đồ thị được mã hóa bằng danh sách mảng các điểm và tọa độ tương ứng
của chúng. Dưới đây là ví dụ về bộ dữ liệu đồ thị chuẩn.
NAME : xit1083
COMMENT : Bonn VLSI data set with 1083 points
COMMENT : Uni Bonn, Research Institute for Discrete Math
COMMENT : Contributed by Andre Rohe
TYPE : TSP
DIMENSION : 1083
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
1 0 105
2 0 111
3 0 15
… … …

Xem chi tiết: Giải thuật di truyền với bài toán người du lịch