Áp dụng Genetic Algorithm để giải quyết bài toán Travelling Salesman Problem – TSP

Nếu bạn chưa biết gì về giải thuật di truyền (Genetic Algorithm) thì xin mời bạn tham khảo lại bài viết trước tại đây.
Bài viết này, mình muốn giới thiệu các bạn một ứng dụng của giải thuật di truyền để giải bài toán về người bán hàng.

Bài toán được phát biểu như sau:
Có một người giao hàng cần đi giao hàng tại n thành phố. Anh ta xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, và khoảng cách từ một thành phố đến các thành phố khác đã được biết trước. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất.
(Theo wiki)

Để giải bài toán này bằng phương pháp di truyền, mình vẫn giữ nguyên tinh thần của bài trước, code gần như nguyên vẹn. Tuy nhiên, có một số vấn để phải giải quyết như sau:
– Làm sao để mã hóa đầu vào thành một chromosome bao gồm chuỗi các gene?
– Mô tả sự lai tạo
– Mô tả sự biến dị

1. Mã hóa đầu vào thành một chuỗi gene.

Đầu tiên, ta đặt tên các thành phố trên bản đồ từ 1..n. Như vậy một hành trình của người bán hàng là một chuỗi số có độ dài n, mỗi số của chuỗi chỉ xuất hiện duy nhất một lần và có giá trị trong khoảng từ 1 đến n. Ứng với một hành trình ta luôn có một chuỗi thành phố tương ứng. Xin xem hình minh họa dưới:

Ta có thể coi đây chính là chuỗi gene cho bài toán.

2. Sự lai tạo

Để lai tạo 2 chuỗi gene A và chuỗi gene B trong bài toán này, ta không thể áp dụng cách bắt chéo 2 chuỗi gene thông thường vì có sự đụng độ.

Ví dụ:
[1,2,4,5,3] bắt chéo với [2,5,1,4,3] tại vị trí thứ 3 sẽ trở thành => [1,2,4,4,3] => số 4 bị trùng và số 5 lại bị thiếu.

Để giải quyết sự đụng độ này, mình xin giới thiệu các bạn một phương pháp khác như sau:

  • Tạo một chuỗi rỗng L {}
  • Chọn một thành phố bất kỳ C của chuỗi gene A.
  • Lần lượt tiến hành tìm kiếm các thành phố CA và CB nằm cạnh thành phố A ứng với mỗi gene.
  • Loại C khỏi chuỗi gene A và chuỗi gene B.
  • So sánh khoảng cách C → CA và C → CB. Khoảng cách nào ngắn hơn thì chọn thành phố ấy đưa vào L.
  • Tiếp tục quá trình với thành phố mới được chọn cho đến khi chuỗi gene A hoặc chuỗi gene B rỗng.

Mời bạn xem hình mô tả quá trình chọn lựa ở dưới

Và đây là đoạn code thực hiện trên C#

3. Sự biến dị

Sự biến dị thực chất chỉ là sự đảo lộn 2 vị trí bất kỳ của chuỗi thành phố.
Ví dụ: 0,1,4,5,2,3 => đảo 1 và 2 => 0,2,4,5,1,3.

Dưới đây là chương trình demo, bạn có thể download toàn bộ code tại đây

No Comments

Post A Comment