Luận văn thạc sĩ: Ứng dụng giải thuật di truyền tối ưu giao thông Vĩnh Long

Luận văn thạc sĩ trình bày ứng dụng giải thuật di truyền để tìm đường đi tối ưu cho mạng lưới giao thông đường thủy phức tạp tại tỉnh Vĩnh Long.

• Tác giả: Lê Hoàng An
• Người hướng dẫn: Ts. Phạm Minh Tuấn
• Trường học: Đại học Đà Nẵng - Trường Đại học Bách Khoa
• Chuyên ngành: Khoa học máy tính
• Đề tài: Ứng Dụng Giải Thuật Di Truyền Tìm Đường Đi Tối Ưu Trong Giao Thông Đường Thủy Tại Tỉnh Vĩnh Long
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: Đà Nẵng

Tóm tắt

I. Khám phá giải thuật di truyền tối ưu hóa đường thủy Vĩnh Long

Vĩnh Long, một tỉnh trung tâm của Đồng bằng sông Cửu Long (ĐBSCL), sở hữu một mạng lưới giao thông thủy chằng chịt, tạo nên tiềm năng to lớn cho phát triển kinh tế và logistics và quản lý chuỗi cung ứng. Tuy nhiên, việc khai thác hiệu quả mạng lưới này đòi hỏi các giải pháp thông minh để tìm ra lộ trình vận tải ngắn nhất, tiết kiệm nhất. Giải thuật di truyền (Genetic Algorithm - GA), một nhánh của thuật toán tiến hóa, nổi lên như một công cụ mạnh mẽ để giải quyết bài toán tối ưu hóa tổ hợp phức tạp này. Không giống các thuật toán cổ điển như thuật toán Dijkstra hay thuật toán Bellman-Ford chỉ tìm đường đi giữa hai điểm, giải thuật di truyền có khả năng giải quyết các bài toán định tuyến phức tạp hơn, chẳng hạn như tìm đường đi tối ưu phải qua nhiều điểm định trước. Bài viết này sẽ phân tích sâu về ứng dụng của giải thuật di truyền trong việc tìm kiếm đường đi tối ưu cho vận tải thủy nội địa tại Vĩnh Long, dựa trên các nghiên cứu khoa học thực tiễn, nhằm mục tiêu tối ưu hóa chi phí vận chuyển và nâng cao hiệu quả vận hành.

1.1. Giới thiệu tổng quan về giải thuật di truyền GA

Giải thuật di truyền là một kỹ thuật tìm kiếm và tối ưu hóa dựa trên nguyên lý chọn lọc tự nhiên và di truyền học của Darwin. Phương pháp này hoạt động trên một quần thể các lời giải tiềm năng, mỗi lời giải được mã hóa thành một 'nhiễm sắc thể'. Qua các thế hệ, các lời giải tốt nhất sẽ được lựa chọn để 'lai ghép' và 'đột biến', tạo ra thế hệ mới ngày càng ưu việt hơn. Quá trình này mô phỏng sự tiến hóa sinh học, nơi các cá thể thích nghi tốt nhất sẽ tồn tại và sinh sản, truyền lại những gen tốt cho đời sau. Trong bối cảnh giao thông đường thủy, mỗi 'nhiễm sắc thể' đại diện cho một lộ trình khả thi. Mục tiêu của thuật toán là tìm ra lộ trình có 'độ thích nghi' cao nhất, tức là tổng quãng đường hoặc chi phí thấp nhất.

1.2. Vai trò của việc tối ưu hóa trong vận tải thủy nội địa

Vận tải thủy nội địa đóng vai trò huyết mạch trong nền kinh tế ĐBSCL. Việc tối ưu hóa chi phí vận chuyển không chỉ giúp doanh nghiệp giảm thiểu chi phí nhiên liệu, thời gian mà còn góp phần giảm tải cho hệ thống đường bộ, bảo vệ môi trường. Một lộ trình được quy hoạch tốt sẽ giúp tăng số vòng quay của phương tiện, cải thiện hiệu quả chuỗi cung ứng và nâng cao năng lực cạnh tranh. Các bài toán tối ưu trong lĩnh vực này thường rất phức tạp, tương tự như bài toán người du lịch (TSP) hoặc bài toán định tuyến xe (VRP), đòi hỏi các công cụ tính toán mạnh mẽ như giải thuật di truyền để tìm ra lời giải hiệu quả trong một khoảng thời gian hợp lý.

II. Thách thức tối ưu đường đi trên mạng lưới sông ngòi Vĩnh Long

Hệ thống sông ngòi Vĩnh Long, dù là một lợi thế, cũng đặt ra nhiều thách thức cho bài toán quy hoạch tuyến đường vận tải. Mạng lưới giao thông thủy tại đây bao gồm hàng trăm nút giao, cảng, bến bãi, tạo ra một không gian tìm kiếm lộ trình khổng lồ. Các phương pháp tìm đường truyền thống tỏ ra không hiệu quả khi phải xử lý các ràng buộc phức tạp trong thực tế. Ví dụ, một chuyến tàu cần giao hàng tại nhiều đại lý khác nhau trước khi đến điểm cuối cùng. Bài toán này không còn là tìm đường đi ngắn nhất giữa hai điểm đơn thuần. Nó trở thành một bài toán tối ưu hóa tổ hợp đòi hỏi phải xác định thứ tự các điểm đến sao cho tổng quãng đường là tối thiểu. Theo luận văn của Lê Hoàng An (2017), 'việc tìm đường đi giữa hai địa điểm với ràng buộc phải qua một số địa điểm khác, các giải thuật cổ điển này chưa giải quyết được'. Đây chính là lỗ hổng mà giải thuật di truyền được đề xuất để giải quyết, mang lại một phương pháp linh hoạt và mạnh mẽ hơn.

2.1. Phân tích sự phức tạp của mạng lưới giao thông thủy

Mạng lưới đường thủy Vĩnh Long được mô hình hóa như một đồ thị phức tạp. Các đỉnh của đồ thị là các nút giao sông, cảng, và bến hàng hóa. Các cạnh là các đoạn sông nối liền các đỉnh, với trọng số là khoảng cách hoặc thời gian di chuyển. Sự phức tạp không chỉ nằm ở số lượng đỉnh và cạnh mà còn ở các yếu tố động như thủy triều, dòng chảy, và các quy định về luồng lạch. Việc xây dựng một bản đồ số hóa sông ngòi chính xác, kết hợp với dữ liệu từ hệ thống thông tin địa lý (GIS), là nền tảng quan trọng để áp dụng bất kỳ thuật toán tối ưu nào. Số lượng các lộ trình khả thi tăng theo giai thừa với số điểm cần đi qua, khiến cho việc tìm kiếm vét cạn là bất khả thi.

2.2. Hạn chế của các thuật toán tìm đường cổ điển A Dijkstra

Các thuật toán kinh điển như thuật toán Dijkstra và thuật toán A* rất hiệu quả trong việc tìm đường đi ngắn nhất giữa một điểm xuất phát và một điểm đích duy nhất. Tuy nhiên, chúng không được thiết kế để xử lý ràng buộc 'phải đi qua một tập hợp các điểm trung gian'. Khi áp dụng cho bài toán này, các thuật toán cổ điển buộc phải chia bài toán lớn thành nhiều bài toán con và thử tất cả các hoán vị của các điểm trung gian. Cách tiếp cận này có độ phức tạp tính toán rất cao, tương đương với phương pháp vét cạn, và trở nên không thực tế khi số lượng điểm cần đi qua tăng lên, đặc biệt trong các hệ thống logistics và quản lý chuỗi cung ứng quy mô lớn.

III. Nguyên lý cốt lõi của giải thuật di truyền trong tối ưu hóa

Giải thuật di truyền hoạt động dựa trên việc mô phỏng quá trình tiến hóa. Nó bắt đầu với một 'quần thể' gồm nhiều lộ trình ngẫu nhiên. Mỗi lộ trình được đánh giá bằng một hàm thích nghi (fitness function), thường là tổng chiều dài quãng đường. Các lộ trình ngắn hơn (thích nghi tốt hơn) có xác suất cao hơn được chọn để tạo ra thế hệ tiếp theo thông qua hai toán tử chính: toán tử lai ghép và đột biến. Lai ghép kết hợp các phần tốt của hai lộ trình 'cha mẹ' để tạo ra lộ trình 'con' mới, hy vọng kế thừa những đặc tính ưu việt. Đột biến thay đổi một phần nhỏ của một lộ trình một cách ngẫu nhiên để tạo ra sự đa dạng và tránh việc thuật toán bị mắc kẹt ở các giải pháp tối ưu cục bộ. Quá trình này lặp đi lặp lại qua nhiều thế hệ, dần dần hội tụ về một lộ trình gần như tối ưu. Đây là bản chất của một thuật toán tiến hóa ứng dụng vào mô phỏng và mô hình hóa.

3.1. Thiết kế hàm thích nghi Fitness Function cho bài toán

Hàm thích nghi là trái tim của giải thuật di truyền. Nó định lượng mức độ 'tốt' của một lời giải (một lộ trình). Trong bài toán tìm đường tối ưu, hàm thích nghi đơn giản nhất là nghịch đảo của tổng khoảng cách. Lộ trình càng ngắn, giá trị hàm thích nghi càng cao. Theo nghiên cứu, hàm đánh giá được thiết kế để phạt nặng các cá thể không hợp lệ. Ví dụ, nếu một lộ trình có hai điểm liên tiếp không thể đi trực tiếp cho nhau hoặc bỏ sót một điểm bắt buộc phải đi qua, nó sẽ được gán một giá trị thích nghi cực thấp (hoặc một khoảng cách vô cùng lớn). Điều này đảm bảo rằng quá trình chọn lọc tự nhiên sẽ nhanh chóng loại bỏ các lộ trình sai, chỉ giữ lại những lộ trình hợp lệ và tối ưu.

3.2. Vai trò của toán tử lai ghép và toán tử đột biến

Toán tử lai ghép (Crossover) và toán tử đột biến (Mutation) là hai động lực chính của sự tiến hóa trong GA. Lai ghép cho phép thuật toán khám phá các vùng không gian lời giải mới bằng cách kết hợp thông tin từ các lời giải tốt hiện có. Trong bài toán định tuyến, một điểm cắt chung trên hai lộ trình cha mẹ được chọn, và các đoạn lộ trình được hoán đổi để tạo ra hai lộ trình con mới. Ngược lại, đột biến có vai trò duy trì sự đa dạng di truyền trong quần thể. Nó thực hiện một thay đổi nhỏ, ngẫu nhiên trên một lộ trình, ví dụ như hoán đổi vị trí của hai điểm đến. Điều này giúp thuật toán thoát khỏi các điểm tối ưu cục bộ và có cơ hội tìm ra lời giải tối ưu toàn cục.

IV. Phương pháp mô hình hóa và xây dựng ứng dụng thực tiễn

Để ứng dụng giải thuật di truyền, bước đầu tiên là mô phỏng và mô hình hóa mạng lưới giao thông thủy Vĩnh Long. Dữ liệu về các nút giao sông, cảng, bến và khoảng cách giữa chúng được thu thập từ Sở Giao thông Vận tải Vĩnh Long. Dữ liệu này được cấu trúc hóa dưới dạng danh sách cạnh của một đồ thị có trọng số. Mỗi cá thể trong quần thể của giải thuật là một chuỗi các mã định danh (ID) của các nút, biểu diễn một lộ trình hoàn chỉnh từ điểm đầu đến điểm cuối và đi qua tất cả các điểm trung gian bắt buộc. Nghiên cứu của Lê Hoàng An đã triển khai ứng dụng bằng ngôn ngữ lập trình (có thể là lập trình Python cho khoa học dữ liệu hoặc các ngôn ngữ tương tự) để khởi tạo quần thể, thực hiện các vòng lặp tiến hóa, và cuối cùng xuất ra kết quả là lộ trình tối ưu nhất tìm được. Quá trình này cho thấy sự kết hợp chặt chẽ giữa lý thuyết thuật toán và dữ liệu thực tế.

4.1. Khảo sát số hóa dữ liệu hệ thống sông ngòi Vĩnh Long

Quá trình xây dựng ứng dụng bắt đầu bằng việc khảo sát và phân tích dữ liệu. Toàn bộ hệ thống sông ngòi, bao gồm 91 tuyến sông, kênh, rạch đã được khảo sát, được biểu diễn thành một đồ thị. Các nút giao, cảng và bến hàng hóa được gán một mã ID duy nhất. Khoảng cách giữa các nút liền kề được lưu trữ trong một tệp dữ liệu, đóng vai trò là trọng số của các cạnh trong đồ thị. Việc tạo ra một bản đồ số hóa sông ngòi chi tiết và chính xác là yếu tố quyết định sự thành công của mô hình. Dữ liệu này là đầu vào không thể thiếu cho thuật toán để tính toán và đánh giá các lộ trình.

4.2. Triển khai các bước của giải thuật di truyền vào ứng dụng

Ứng dụng được xây dựng theo các bước chuẩn của một giải thuật di truyền. Đầu tiên, một quần thể ban đầu gồm N lộ trình hợp lệ được tạo ngẫu nhiên. Sau đó, vòng lặp chính bắt đầu: (1) Đánh giá độ thích nghi của từng lộ trình trong quần thể. (2) Lựa chọn các lộ trình tốt nhất để làm 'cha mẹ'. (3) Áp dụng toán tử lai ghép và đột biến để tạo ra thế hệ con mới. (4) Thay thế thế hệ cũ bằng thế hệ mới. Vòng lặp này tiếp tục cho đến khi đạt được một điều kiện dừng, chẳng hạn như sau một số thế hệ nhất định hoặc khi chất lượng lời giải không còn cải thiện đáng kể. Lộ trình tốt nhất trong quần thể cuối cùng được chọn làm kết quả.

V. Kết quả nghiên cứu và đánh giá hiệu quả của giải thuật

Kết quả thử nghiệm từ nghiên cứu khoa học của Lê Hoàng An (2017) đã chứng minh hiệu quả vượt trội của giải thuật di truyền trong việc tìm đường đi tối ưu. Trong các thử nghiệm cụ thể, ứng dụng đã tìm ra các lộ trình có tổng khoảng cách ngắn hơn đáng kể so với các lộ trình ban đầu được tạo ngẫu nhiên. Một điểm đáng chú ý là thuật toán thể hiện khả năng 'học hỏi' và 'cải thiện' qua các thế hệ. Ví dụ, trong một thử nghiệm, thế hệ đầu tiên có thể tìm ra một lộ trình dài 76km, nhưng sau chỉ vài thế hệ, thuật toán đã hội tụ về một lộ trình tối ưu hơn chỉ còn 54km. Điều này cho thấy khả năng khám phá không gian lời giải rộng lớn và tìm ra các giải pháp chất lượng cao của GA. Các kết quả này cung cấp bằng chứng thực tiễn mạnh mẽ về tiềm năng ứng dụng của giải thuật này trong quy hoạch tuyến đường vận tải tại Đồng bằng sông Cửu Long.

5.1. Phân tích các kịch bản thử nghiệm và kết quả đạt được

Nhiều kịch bản đã được thử nghiệm, từ bài toán đơn giản (tìm đường giữa hai điểm không có ràng buộc) đến các bài toán phức tạp (đi qua nhiều điểm trung gian). Trong trường hợp đi từ nút 001 đến nút 030, thuật toán đã nhanh chóng tìm ra đường đi tối ưu dài 54km chỉ sau 4 thế hệ, thay vì lộ trình 76km của thế hệ đầu. Kết quả này cho thấy tốc độ hội tụ nhanh và hiệu quả của thuật toán. Các biểu đồ kết quả trong nghiên cứu cho thấy độ dài quãng đường giảm dần qua các thế hệ, minh chứng cho quá trình tối ưu hóa đang diễn ra. Mỗi thử nghiệm đều khẳng định tính đúng đắn và hiệu quả của phương pháp đề xuất.

5.2. So sánh và đánh giá ưu điểm so với phương pháp truyền thống

So với các thuật toán cổ điển, ưu điểm lớn nhất của giải thuật di truyền là tính linh hoạt và khả năng giải quyết các bài toán tối ưu hóa tổ hợp phức tạp với nhiều ràng buộc. Trong khi Dijkstra chỉ có thể tìm đường đi điểm-tới-điểm, GA có thể xử lý các bài toán tương tự VRP một cách tự nhiên. Mặc dù GA không đảm bảo tìm ra lời giải tối ưu tuyệt đối 100% trong mọi trường hợp, nó có khả năng tìm ra các lời giải rất tốt trong một khoảng thời gian hợp lý, điều mà các phương pháp vét cạn không thể làm được với dữ liệu lớn. Đây là sự đánh đổi hợp lý giữa tính tối ưu và hiệu quả tính toán trong các ứng dụng thực tế.

VI. Tương lai giải thuật di truyền trong logistics và vận tải thủy

Thành công của việc áp dụng giải thuật di truyền để tìm đường tối ưu tại Vĩnh Long đã mở ra nhiều hướng phát triển đầy hứa hẹn cho ngành logistics và quản lý chuỗi cung ứng đường thủy. Trong tương lai, thuật toán này có thể được cải tiến và mở rộng để giải quyết các bài toán phức tạp hơn. Việc tích hợp dữ liệu thời gian thực từ hệ thống thông tin địa lý (GIS), chẳng hạn như tình hình thời tiết, thủy triều, hay mật độ giao thông, sẽ giúp mô hình trở nên năng động và chính xác hơn. Hơn nữa, giải thuật di truyền có thể được áp dụng cho vận tải đa phương thức, tối ưu hóa toàn bộ chuỗi cung ứng kết hợp giữa đường thủy, đường bộ và đường biển. Điều này sẽ góp phần xây dựng một hệ thống vận tải thủy nội địa thông minh, hiệu quả và bền vững cho toàn vùng Đồng bằng sông Cửu Long.

6.1. Hướng phát triển tích hợp GIS và dữ liệu thời gian thực

Một hướng phát triển quan trọng là kết hợp mô hình hiện tại với hệ thống thông tin địa lý (GIS) và các nguồn dữ liệu thời gian thực. Thay vì chỉ dựa trên khoảng cách địa lý tĩnh, hàm thích nghi có thể được điều chỉnh để tính toán chi phí dựa trên các yếu tố động như tốc độ dòng chảy, điều kiện thời tiết, hoặc các khu vực cấm tạm thời. Điều này sẽ cho phép hệ thống đề xuất các lộ trình tối ưu thích ứng với điều kiện thực tế, mang lại hiệu quả cao hơn trong việc tối ưu hóa chi phí vận chuyển và đảm bảo an toàn.

6.2. Mở rộng ứng dụng cho bài toán vận tải đa phương thức

Tiềm năng của giải thuật di truyền không chỉ giới hạn ở vận tải thủy nội địa. Nó hoàn toàn có thể được mở rộng để giải quyết bài toán vận tải đa phương thức, một thách thức lớn trong logistics và quản lý chuỗi cung ứng. Bài toán này yêu cầu tối ưu hóa một hành trình bao gồm nhiều chặng vận chuyển bằng các phương tiện khác nhau (tàu, xe tải, v.v.). Bằng cách mô hình hóa toàn bộ mạng lưới vận tải đa phương thức và điều chỉnh hàm thích nghi để tính toán tổng chi phí (bao gồm cả chi phí chuyển tải), GA có thể tìm ra chuỗi phương thức và lộ trình tối ưu nhất từ điểm đầu đến điểm cuối, tạo ra một cuộc cách mạng trong hiệu quả logistics.

Trích đoạn nội dung tài liệu

Đặt vấn đề Trong đời sống, chúng ta thường gặp những tình huống như sau: để đi từ địa điểm A đến địa điểm B trong thành phố, có nhiều đường đi, nhiều cách đi; có lúc ta chọn đường đi ngắn nhất (theo nghĩa cự ly), có lúc lại cần chọn đường đi nhanh nhất (theo nghĩa thời gian) và có lúc phải cân nhắc để chọn đường đi rẻ tiền nhất (theo nghĩa chi phí), v. Ta có thể đồ thị hóa bài toán bằng cách xem các nút giao thông là đỉnh của đồ thị, đoạn đường giữa các nút giao thông là cạnh nối giữa hai đỉnh tương ứng. Trên mỗi cạnh của đồ thị này, ta gán một số dương, ứng với chiều dài của đoạn đường, thời gian đi qua đoạn đường hoặc cước phí vận chuyển trên đoạn đường đó,. một đồ thị như vậy được gọi là đồ thị có trọng số.

Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh (hoặc cung) được gán một giá trị gọi là trọng số ứng với cạnh (hoặc cung) đó. Phát biểu bài toán a. Đường đi ngắn nhất giữa hai đỉnh Cho đơn đồ thị liên thông có trọng số G=(V,E), tìm đường đi ngắn nhất từ một đỉnh s cho trước đến một đỉnh f trong G. Kết quả của bài toán này là đường đi ngắn nhất giữa một cặp đỉnh cụ thể là s và f.

Nếu như đồ thị không có chu trình âm thì ta có thể chứng minh được rằng một trong những đường đi ngắn nhất là đường đi cơ bản. Việc tìm đường đi ngắn nhất giữa 2 đỉnh s và f có thể áp dụng thuật toán sau: Gọi a[u,v] là trọng số của cạnh (u,v). Qui ước a[v,v]=0 với v V Đặt d[s,v] là khoảng cánh từ s tới v. Để tìm đường đi từ s tới f ta nhận thấy rằng luôn tồn tại f1≠ f sao cho d[s,f]=d[s,f1]+a[f1,f].

10 Đỉnh f1 đó là đỉnh liền trước trong đường đi từ s tới f. Nếu f 1≡ s thì kết thúc trái lại ta tìm đỉnh f2 sao cho d[s,f1]=d[s,f2]+a[f2,f]. Cứ tiếp tục như vậy sau hữu hạn bước ta xác định được đường đi ngắn nhất từ s tới f. Đường đi ngắn nhất từ một định đến mọi đỉnh còn lại Cho đơn đồ thị liên thông có trọng số G=(V,E), tìm đường đi ngắn nhất từ một đỉnh s cho trước đến mọi đỉnh trong G.

Đối với bài toán này, ta cần tìm đường đi ngắn nhất từ đỉnh đang xét s lần lượt đến tất cả các đỉnh còn lại. Kết quả của bài toán là n-1 đường đi ngắn nhất có đỉnh bắt đầu là s, đỉnh kết thúc lần lượt là các đỉnh còn lại trong đồ thị. Đường đi ngắn nhất giữa mọi cặp đỉnh bất kỳ Cho đơn đồ thị liên thông có trọng số G=(V,E), tìm đường đi ngắn nhất giữa mọi cặp đỉnh u, v trong G. Đối với bài toán này, ta cần tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị.

Kết quả của bài toán là 𝐶𝑛2 đường đi ngắn nhất có đỉnh bắt đầu và đỉnh kết thúc khác nhau. Các thuật toán tìm đường đi ngắn nhất 1. Thuật toán Dijsktra Thuật toán do E.Dijkstra, nhà toán học người Hà Lan, đề xuất năm 1959. Giả sử đồ thị là vô hướng, các trọng số là dương.

Thuật toán bao gồm các bước như sau: Bước 1: Khởi tạo Xuất phát từ đỉnh s. Gọi d[v] là khoảng cánh từ s tới v khởi tạo: 1. Cố định nhãn: Tìm đỉnh u trong các đỉnh có nhãn tự do có d[u] là nhỏ nhất. Cố định nhãn cho đỉnh u.

Sửa nhãn: Dùng đỉnh u xét tất cả những đỉnh tự do v và sửa lại nhãn các d[v] theo công thức: d[v] = min(d[v],d[u]+a[u,v]), nếu d[v]=d[u]+a[u,v] thì t[v]=u. Lặp lại Bước 2 đến khi đỉnh f được cố định nhãn. Thuật toán có thể được mô tả bằng mã giả như sau: Procedure Dijsktra; Begin d[s]:=0; free[s]:=false; for ( v V) do begin d[v]:=a[s,v]; free[v]:=true; t[v]:=s; end; repeat u:=min(d[v], ( v V) 11 free[u]:=false; if (u=f) or (d[u]= ∞) then break; for ( v V) and (free[v]) do begin d[v]:= min(d[v], d[u]+ a[u,v]); if d[v]=d[u]+a[u,v] then t[v]:=u; end; until false; End; Ví dụ 1. Tìm đường đi ngắn nhất từ đỉnh A đến F.

Đồ thị có hướng G và giải thuật Dijsktra Ta kí hiệu t[v] là đỉnh trước của v trên đường đi từ A tới F. Minh họa kết quả tính toán của thuật toán Dijsktra qua bảng sau: Bảng 1. Kết quả giải thuật Dijsktra Bước d[a], t[a] d[b], t[b] d[c], t[c] d[d], t[d] d[e], t[e] d[f], t[f] 1 0,a 2,a* 7,a ∞,a ∞,a ∞,a 2 - - 6,b* ∞,a ∞,a ∞,a 3 - - - 7,c* 10,c ∞,a 4 - - - - 9,d* ∞,a 5 - - - - - 12,e* Trong tường hợp tồn tại cung (u,v) có trọng số âm trong đồ thị, việc đi qua cung (u,v) sẽ làm cho tổng trọng số đường đi giảm xuống, nghĩa là cứ mỗi lần đi qua cung này, ta lại được đường đi tối ưu hơn, do đó vòng lặp tìm kiếm đường đi sẽ không thể dừng. Để giải quyết vấn đề này người ta sẽ tiếp cận theo một hướng khác, đó là thuật toán Bellman - Ford 1.

Thuật toán Bellman-Ford Bước 1: Khởi tạo Xuất phát từ đỉnh s. Gọi d[v] là khoảng cánh từ s tới v. Lặp lại Bước 2 đến khi không thể tối ưu thêm bất kì một nhãn d[v] nào nữa, dùng biến stop để kiểm soát quá trình này. 12 Thuật toán có thể được mô tả bằng mã giả như sau: Procedure Ford_Bellman; Begin for ( v V) do begin d[v]:=a[s,v]; t[v]:=s; end; d[s]:=0; repeat stop := true; for ( u V) do for ( v V) and (u,v) E do if d[v]>d[u]+ a[u,v] then begin d[v]:=d[u]+ a[u,v]; stop:=false; t[v]:=u; end; until stop; End; Ví dụ 1.

Tìm đường đi ngắn nhất từ đỉnh A đến F. Đồ thị có hướng G và giải thuật Ford - Bellman Ta kí hiệu t[v] là đỉnh trước của v trên đường đi từ A tới F. Minh họa kết quả tính toán của thuật toán Ford-Bellman qua bảng sau: Bảng 1. Kết quả giải thuật Ford – Bellman Bước d[a], t[a] d[b], t[b] d[c], t[c] d[d], t[d] d[e], t[e] d[f], t[f] 0 ∞,a ∞,a ∞,a ∞,a ∞,a ∞,a 1 0,a 2,a 7,a ∞,a ∞,a ∞,a 2 0,a 2,a 6,b ∞,a ∞,a ∞,a 3 0,a 2,a 6,b 7,c 10,c ∞,a 4 0,a 2,a 6,b 7,c 9,d ∞,a 5 0,a 2,a 6,b 7,c 9,d 12,e 13 Ta dễ dàng nhận ra rằng cả hai thuật toán trên đều cho ra đường đi tối ưu nhưng chỉ giải quyết được vấn đề tìm đường giữa hai đỉnh.

Để có thể giải quyết được vấn đề tìm đường giữa hai đỉnh với ràng buộc phải đi qua một số đỉnh cho trước cần pahri mở rộng thuật toán, tuy nhiên, thời gian tìm kiếm sẽ tương đương thuật toán vét cạn. GIẢI THUẬT DI TRUYỀN 1. Giới thiệu Giải thuật di truyền (GAs-Genetic Algorithms) là kỹ thuật phỏng theo quá trình thích nghi tiến hóa của các quần thể sinh học dựa trên học thuyết Darwin. GAs là phương pháp tìm kiếm tối ưu ngẫu nhiên bằng cách mô phỏng theo sự tiến hóa của con người hay của sinh vật.

Tư tưởng của GAs là mô phỏng các hiện tượng tự nhiên, là kế thừa và đấu tranh sinh tồn. Thuật toán di truyền được ứng dụng đầu tiên trong hai lĩnh vực chính: tối ưu hóa và máy học. Trong lĩnh vực tối ưu hóa thuật toán di truyền được phát triển nhanh chóng và ứng dụng trong nhiều lĩnh vực khác nhau như tối ưu hàm, xử lý ảnh, bài toán hành trình người bán hàng, nhận dạng hệ thống và điều khiển. Thuật toán di truyền cũng như các thuật toán tiến hóa nói chung, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu.

Quan niệm này có thể xem như một tiên đề, không chứng minh được, nhưng phù hợp với thực tế khách quan. Quá trình tiến hóa thể hiện tính tối ưu ở chỗ, thế hệ sau bao giờ cũng tốt hơn (phát triển hơn, hoàn thiện hơn) thế hệ trước nhờ tính kế thừa và đấu tranh sinh tồn. Nguyên tắc thiết kế giải thuật di truyền Khác biệt quan trọng giữa tìm kiếm của GAs và các phương pháp tìm kiếm khác là GAs duy trì và xử lý trên một tập các lời giải ứng viên, gọi là quần thể (population). Trong GAs, việc tìm kiếm lời giải thích hợp được bắt đầu với một quần thể, hay một tập hợp có chọn lọc của các giả thuyết ban đầu của lời giải.

Các cá thể của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt động lai ghép và đột biến ngẫu nhiên – được lấy mẫu sau các quá trình tiến hóa sinh học. Ở mỗi bước, các giả thuyết trong quần thể hiện tại được ước lượng bằng hàm đánh giá độ thích nghi. Các giả thuyết phù hợp nhất được chọn cho việc sản sinh thế hệ kế tiếp, gọi là cá thể (individual). Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại và ngược lại sẽ bị đào thải.

GAs có thể dò tìm thế hệ mới có độ thích nghi tốt hơn. GAs giải quyết các bài toán quy hoạch toán học thông qua các quá trình cơ bản: lựa chọn (selection), tái sinh (reproduction), lai ghép (crossover) và đột biến (mutation) cho các cá thể trong quần thể. GAs bao gồm các bước: khởi tạo quần thể ban đầu, đánh giá các lời giải theo mức độ thích nghi – hàm mục tiêu, sử dụng các toán tử di truyền tạo thế hệ kế tiếp. Các toán tử di truyền a.

Lai ghép Quá trình này diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai cá thể cha- mẹ để hình thành cá thể mới mang đặc tính của cả cha lẫn mẹ. Phép lai này có thể mô tả như sau: - Chọn ngẫu nhiên hai hay nhiều cá thể trong quần thể. Giả sử chuỗi nhiễm sắc thể của cha (m1) và mẹ (m2) đều có chiều dài là m. - Tìm điểm lai bằng cách tạo ngẫu nhiên một con số từ 1 đến m-1.

Như vậy, điểm lai này sẽ chia chuỗi nhiễm sắc thể cha thành hai đoạn nhiễm sắc thể con là m11, m12 và chuỗi nhiễm sắc thể mẹ thành m21, m22. Từ các đoạn nhiễm sắc thể này ta ghép lại tạo thành hai cá thể con là m11+m22 và m21+m12. Sau đó, đưa hai cá thể con vào quần thể để tiếp tục tham gia quá trình tiến hóa. Lựa chọn và tái sinh Phép lựa chọn: là quá trình loại bỏ các cá thể có độ thích nghi thấp, chỉ giữ lại những cá thể có độ thích nghi cao.