Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
Khoa học máy tính
---------------------*---------------------
BÀI TẬP LỚN
MÔN: MỘT SỐ PHƯƠNG PHÁP
TÍNH TOÁN MỀM
Đề tài: Ứng dụng giải thuật di truyền giải bài toán người du lịch.
Giảng viên hướng dẫn:
Ths. Đỗ Văn Tuấn
Sinh viên thực hiện:
Trần Văn Ngọc
MSV: 1174162010
Nguyễn Ngọc Khánh
MSV: 1174162015
Lớp:
KHMT2-K11
HÀ NỘI 2017
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
MỤC LỤC
LỜI NÓI ĐẦU ........................................................................................................2
CHƯƠNG I : GIẢI THUẬT DI TRUYỀN (Genetic Algorithm - GA) .................3
1. Khái nệm ........................................................................................................ 3
2. Thuật giải di truyền ........................................................................................3
3. Các toán tử di truyền ..................................................................................... 3
3.1: Lai ghép.................................................................................................6
3.2: Đột biến................................................................................................6
4. Đấu tranh sinh tồn ......................................................................................... 7
CHƯƠNG II : BÀI TOÁN NGƯỜI DU LỊCH (PROBLEM OF TOURISM)
…….. ........………………………………………………............…..8
1. Lịch sử bài toán : ......................................................................................... 8
2. Phát biểu bài toán : ...................................................................................... 9
3. Phân tích độ phức tạp : ................................................................................ 10
4.Tổng quan về Matlab: ................................................................................... 10
4.1. Khái niệm về Matlab:......................................................................... 10
4.2. Tổng quan về cấu trúc dữ liệu Matlab, các ứng dụng........................ 10
CHƯƠNG III :GIẢI BÀI TOÁN NGƯỜI DU LỊCH........………………....…...12
TỔNG KẾT ................................................................................................. ........18
TÀI LIỆU THAM KHẢO ................................................................................... 19
1
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
LỜI NÓI ĐẦU
Bài toán người du lịch là một trong những bài toán được nghiên cứu sâu
nhất trong lĩnh vực tối ưu hóa. Báo cáo này sẽ trình bày 1 hướng tiếp cận giải
quyết bài toán người du lịch sử dụng giải thuật di truyền.
Giải thuật di truyền về cơ bản muốn mô phỏng lại quá trình tiến hóa của
sinh vật trong tự nhiên vào các bài toán tối ưu hóa từ đó đưa ra lời giải tốt (có thể
không là tối ưu nhất) khi mà không thể đưa ra được 1 giải thuật chính xác hay
việc vét cạn các trường hợp là bất khả thi.
Mặc dù đã rất cố gắng nhưng vẫn không thể tránh khỏi những sai sót,
mong thầy giáo chỉ bảo thêm.
2
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
CHƯƠNG I : GIẢI THUẬT DI TRUYỀN (Genetic Algorithm - GA)
Giải thuật di truyền cũng như tiến hóa dựa trên khái niệm cho rằng quá
trình tiến hóa tự nhiên là hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu.
Sự tối ưu đó được thể hiện ở chỗ thế hệ sau bao giờ cũng phát triển tốt hơn thế hệ
trước. Tiến hóa tự nhiên được duy trì nhờ hai quá trình cơ bản: sinh sản và chọn
lọc tự nhiên, xuyên suốt quá trình tiến hóa tự nhiên, các thế hệ mới luôn được
sinh ra để bổ sung thay thế thế hệ cũ, cá thể nào thích ứng với môi trường sẽ tồn
tại, ngược lại sẽ bị đào thải.
Giải thuật di truyền bao gồm 4 bước chính: Mã hóa lời giải, khởi tạo quần
thể, sử dụng các phép toán di truyền và đánh giá độ thích nghi. Sau đó, chúng ta
lại sinh ra một quần thể mới bằng phép chọn lọc rồi tiếp tục sử dụng các phép
toán di truyền và đánh giá độ thích nghi của các cá thể (điển hình bởi nhiễm sắc
thể - NST) trong quần thể. Thuật giải được thực hiện qua càng nhiều thế hệ thì
lời giải đưa ra càng tối ưu.
1. Khái niệm
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.
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.
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
3
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấ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)
{
// 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, PS
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 PS. Xác suất Pr(hi) của giả thuyết hi thuộc P được tính bởi công thức:
Fitness (hi)
Pr(hi)=
p
∑ Fitness(hj )
j =1
2. Lai ghép: chọn lọc theo xác suất
r∗p
cặp giả thuyết từ quần thể P, theo
2
Pr(hi) đã tính ở bước trên. Ứng với mỗi cặp
, 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 PS.
4
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
3. Đột biến: Chọn m% cá thể của Ps 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 Ps .
5. Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)
• Trả về giả thuyết trong P có độ thích nghi cao nhất.
}
Các bước cơ bản của giải thuật
Khởi tạo quần thể
Lựa chọn cha mẹ
Lai ghép
Đột biến
Đấu tranh sinh tồn
FALSE
Điều kiện dừng
TRUE
Các cá thể tốt nhất
Lưu đồ giải thuật cơ bản
3. Các toán tử di truyền
3.1 Lai ghép :
5
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
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ì.
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
6
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
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ể.
7
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
CHƯƠNG II : BÀI TOÁN NGƯỜI DU LỊCH (PROBLEM OF TOURISM)
1. Lịch sử bài toán :
Bài toán người du lịch (tiếng Anh: PROBLEM OF TOURISM) 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
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à
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ọ đã
8
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
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
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$.
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 v1 → v 2 →… v n→ v1 với vi ∈ V, i=1,n sao cho tổng trọng số hành
trình trên các cạnh ( vi , v i +1 )và ( v n , v 1) 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 :
9
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
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.
4. Tổng quan về Matlab
4.1. Khái niệm về Matlab
Matlab là một ngôn ngữ lập trình thực hành bậc cao được sử dụng để giải các
bài toán về kỹ thuật. Matlab tích hợp được việc tính toán, thể hiện kết quả, cho
phép
lập trình, giao diện làm việc rất dễ dàng cho người sử dụng. Dữ liệu cùng với thư
viện
được lập trình sẵn cho phép người sử dụng có thể có được những ứng dụng sau
đây.
• Sử dụng các hàm có sẵn trong thư viện, các phép tính toán học thông thường
• Cho phép lập trình tạo ra những ứng dụng mới.
• Cho phép mô phỏng các mô hình thực tế.
• Phân tích, khảo sát và hiển thị dữ liệu.
• Với phần mềm đồ hoạ cực mạnh
• Cho phép phát triển, giao tiếp với một số phần mềm khác như C++, Fortran.
4.2. Tổng quan về cấu trúc dữ liệu của MATLAB, các ứng dụng
Matlab là một hệ thống tương giao, các phần tử dữ liệu là một mảng( mảng này
không đòi hỏi về kích thước). Chúng cho phép giải quyết các vấn đề liên quan
đến lập
trình bằng máy tính, đặc biệt sử dụng các phép tính về ma trận hay véc tơ và có
thể sử
dụng ngôn ngữ C hoặc Fortran lập trình rồi thực hiện ứng dụng lập trình đó bằng
các
câu lệnh gọi từ MATLAB. MATLAB được viết tắt từ chữ matrix laboratory tức
là thư
10
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
viện về ma trận, từ đó phần mềm MATLAB được viết nhằm cung cấp cho việc
truy
cập vào phần mềm ma trận một cách dễ dàng, phần mềm ma trận này được phát
triển
bởi các công trình Linpack và Eispack. Ngày nay MATLAB được phát triển bởi
Lapack và Artpack tạo nên một nghệ thuật phần mềm cho ma trận.
11
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
CHƯƠNG III :GIẢI BÀI TOÁN NGƯỜI DU LỊCH
Các vấn đề nhân viên bán hàng đi du lịch là một vấn đề tối ưu hóa, nơi có một số
hữu hạn các thành phố, và chi phí đi lại giữa mỗi thành phố được biết đến. Mục
đích là để tìm một tập có thứ tự của tất cả các thành phố cho các nhân viên bán
hàng đến thăm như vậy mà chi phí được giảm thiểu. Để giải quyết vấn đề nhân
viên bán hàng đi du lịch, chúng ta cần một danh sách các địa điểm thành phố và
khoảng cách, hoặc chi phí, giữa mỗi người.
Nhân viên bán hàng của chúng tôi đến thăm thành phố ở Hoa Kỳ. Các tập
tin usborder.mat chứa một bản đồ của Hoa Kỳ trong các biến x và y , và một
phiên bản đơn giản hóa hình học của cùng một bản đồ trong các biến xx và yy .
load ( 'usborder.mat' , 'x' , 'y' , 'xx' , 'yy' );
lô (x, y, 'Color' , 'đỏ' ); giữ trên ;
Chúng ta sẽ tạo ra địa điểm ngẫu nhiên của các thành phố bên trong biên giới của
Hoa Kỳ. Chúng ta có thể sử dụng các inpolygon chức năng để đảm bảo rằng tất
cả các thành phố bên trong hoặc rất gần với biên giới Mỹ.
cities = 40;
locations = zeros(cities,2);
n = 1;
while (n <= cities)
xp = rand*1.5;
yp = rand;
if inpolygon(xp,yp,xx,yy)
locations(n,1) = xp;
locations(n,2) = yp;
n = n+1;
end
end
plot(locations(:,1),locations(:,2),'bo');
vòng tròn màu xanh đại diện cho các vị trí của thành phố, nơi các nhân viên bán
hàng cần để đi du lịch và cung cấp hàng hoá pickup. Đưa ra danh sách các địa
điểm thành phố, chúng ta có thể tính toán ma trận khoảng cách cho tất cả các
thành phố.
12
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
Tùy biến các thuật toán di truyền cho một kiểu dữ liệu
Theo mặc định, các thuật toán giải di truyền giải quyết vấn đề tối ưu hóa dựa trên
các loại dữ liệu chuỗi đôi và nhị phân. Các chức năng để tạo, crossover, và đột
biến giả dân số là một ma trận các loại tăng gấp đôi, hay hợp lý trong trường hợp
của các chuỗi nhị phân. Các thuật toán giải di truyền cũng có thể làm việc trên
các vấn đề tối ưu hóa liên quan đến các kiểu dữ liệu tùy ý. Bạn có thể sử dụng bất
kỳ cấu trúc dữ liệu mà bạn muốn cho dân số của bạn. Ví dụ, một kiểu dữ liệu tùy
chỉnh có thể được xác định bằng cách sử dụng mảng di động MATLAB®. Để sử
dụng ga với dân số mảng loại tế bào mà bạn phải cung cấp một chức năng sáng
tạo, một chức năng chéo, và một chức năng đột biến sẽ làm việc trên kiểu dữ liệu
của bạn, ví dụ, một mảng di động.
Chức năng bắt buộc đối với các vấn đề Traveling Salesman
Phần này cho thấy làm thế nào để tạo và đăng ký ba chức năng yêu cầu. Một cá
nhân trong dân số cho các vấn đề nhân viên bán hàng đi du lịch là một tập có thứ
tự, và do đó người dân có thể dễ dàng được biểu diễn bằng một mảng di
động. Các chức năng tạo tùy chỉnh cho vấn đề nhân viên bán hàng đi du lịch sẽ
tạo ra một mảng di động, nói P , nơi mà mỗi phần tử đại diện cho một tập có thứ
tự của các thành phố như một vector hoán vị. Đó là, các nhân viên bán hàng sẽ đi
theo thứ tự quy định tại P {i} . Các chức năng tạo sẽ trả về một mảng di động của
kích thước PopulationSize .
type create_permutations.m
function pop = create_permutations(NVARS,FitnessFcn,options)
totalPopulationSize = sum(options.PopulationSize);
n = NVARS;
pop = cell(totalPopulationSize,1);
for i = 1:totalPopulationSize
pop{i} = randperm(n);
end
13
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
type crossover_permutation.m
function xoverKids = crossover_permutation(parents,options,NVARS, ...
FitnessFcn,thisScore,thisPopulation)
nKids = length(parents)/2;
xoverKids = cell(nKids,1); % Normally zeros(nKids,NVARS);
index = 1;
for i=1:nKids
parent = thisPopulation{parents(index)};
index = index + 2;
% Flip a section of parent1.
p1 = ceil((length(parent) -1) * rand);
p2 = p1 + ceil((length(parent) - p1- 1) * rand);
child = parent;
child(p1:p2) = fliplr(child(p1:p2));
xoverKids{i} = child; % Normally, xoverKids(i,:);
end
type mutate_permutation.m
function mutationChildren = mutate_permutation(parents ,options,NVARS, ...
FitnessFcn, state, thisScore,thisPopulation,mutationRate)
mutationChildren = cell(length(parents),1);% Normally zeros(length(parents),NVARS);
for i=1:length(parents)
parent = thisPopulation{parents(i)}; % Normally thisPopulation(parents(i),:)
p = ceil(length(parent) * rand(1,2));
child = parent;
14
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
child(p(1)) = parent(p(2));
child(p(2)) = parent(p(1));
mutationChildren{i} = child; % Normally mutationChildren(i,:)
end
Chúng ta cũng cần một chức năng tập thể dục cho các vấn đề nhân viên bán hàng
đi du lịch. Các phòng tập thể dục của một cá nhân là tổng quãng đường đi cho
một tập có thứ tự của các thành phố. Các chức năng tập thể dục cũng cần sự ma
trận khoảng cách để tính toán tổng khoảng cách.
loại traveling_salesman_fitness.m
function scores = traveling_salesman_fitness(x,distances)
scores = zeros(size(x,1),1);
for j = 1:size(x,1)
p = x{j};
f = distances(p(end),p(1));
for i = 2:length(p)
f = f + distances(p(i-1),p(i));
end
scores(j) = f;
end
ga sẽ gọi chức năng tập thể dục chỉ với một đối số x , nhưng chức năng tập thể
dục của chúng ta có hai đối số: x , khoảng cách . Chúng ta có thể sử dụng một
chức năng ẩn danh để nắm bắt các giá trị của các đối số bổ sung, ma trận khoảng
cách. Chúng ta tạo ra một chức năng xử lýFitnessFcn đến một chức năng vô danh
mà phải mất một đầu vào x , nhưng các cuộc
gọi traveling_salesman_fitness với x , và khoảng cách. Các biến, khoảng cách có
giá trị khi các chức năng xử lý FitnessFcn được tạo ra, do đó, những giá trị này
được chụp bởi chức năng ẩn danh.
%distances defined earlier
FitnessFcn = @(x) traveling_salesman_fitness(x,distances);
15
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
Chúng ta có thể thêm một chức năng cốt truyện tùy chỉnh để âm mưu trí của các
thành phố và các tuyến đường tốt nhất hiện nay. Một vòng tròn màu đỏ đại diện
cho một thành phố và các dòng màu xanh đại diện cho một đường dẫn hợp lệ giữa
hai thành phố.
type traveling_salesman_plot.m
function state = traveling_salesman_plot(options,state,flag,locations)
persistent x y xx yy
if strcmpi(flag,'init')
load('usborder.mat','x','y','xx','yy');
end
plot(x,y,'Color','red');
axis([-0.1 1.5 -0.2 1.2]);
hold on;
[unused,i] = min(state.Score);
genotype = state.Population{i};
plot(locations(:,1),locations(:,2),'bo');
plot(locations(genotype,1),locations(genotype,2));
hold off
Một lần nữa, chúng ta sẽ sử dụng một chức năng ẩn danh để tạo ra một chức năng
để xử lý một chức năng ẩn danh trong đó kêu gọitraveling_salesman_plot với các
đối số bổ sung địa điểm .
Cài đặt Genetic Algorithm
Đầu tiên, chúng ta sẽ tạo một container tùy chọn để chỉ một kiểu dữ liệu tùy chỉnh
và phạm vi dân số.
options = optimoptions(@ga, 'PopulationType', 'custom','InitialPopulationRange', ...
[1;cities]);
16
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
Chúng ta lựa chọn các chức năng tùy chỉnh tạo, crossover, đột biến, và cốt truyện
mà chúng ta đã tạo ra, cũng như thiết lập một số điều kiện dừng.
options = optimoptions(options,'CreationFcn',@create_permutations, ...
'CrossoverFcn',@crossover_permutation, ...
'MutationFcn',@mutate_permutation, ...
'PlotFcn', my_plot, ...
'MaxGenerations',500,'PopulationSize',60, ...
'MaxStallGenerations',200,'UseVectorized',true);
Cuối cùng, chúng ta gọi là thuật toán di truyền với thông tin vấn đề của chúng tôi.
numberOfVariables = cities;
[x,fval,reason,output] = ...
ga(FitnessFcn,numberOfVariables,[],[],[],[],[],[],[],options)
Kết quả
17
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
TỔNG KẾT
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. Kết quả giải thuật đã cài
đặt vẫn còn nhiều hạn chế khi thời gian giải quyết các bộ dữ liệu lớn hơn cỡ
10~20 nghìn đỉnh. Trong tương lai nhóm sẽ tiếp tục cải tiến thuật toán bằng các
giải thuật heuristic hỗ trợ tìm đường, cải tiến giải thuật di truyền bằng cơ chế đa
quần thể có tương tác.
18
Trường Đại Học Công nghiệp Hà Nội
Ths:Đôỗ Văn Tuấấn
TÀI LIỆU THAM KHẢO
1. N. Đ. Thúc (2001), Trí tuệ nhân tạo-Lập trình tiến hóa, NXB Giáo Dục.
2. S. N. Sivanandam, S. N. Deepa (2008), Introduction to Genetic Algorithms,
Springer.
3. Freisleben, P. Mers (1996), New genetic local search operator for the
travelling, University of Siegen.
19
- Xem thêm -