Tài liệu ứng dụng giải thuật di truyền giải bài toán ngưới du lịch

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