12/08/2018, 15:50
Thuật toán di truyền - Ứng dụng giải một số bài toán kinh điển (phần 2)
Trong bài viết trước mình đã giới thiệu về thuật toán di truyền , ở bài viết này mình sẽ demo giải quyết một bài toán kinh điển là "Người bán hàng" Phát biểu bài toán 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 thăm mỗi thành phố đúng một lần. Ở ...
Trong bài viết trước mình đã giới thiệu về thuật toán di truyền, ở bài viết này mình sẽ demo giải quyết một bài toán kinh điển là "Người bán hàng"
Phát biểu bài toán
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 thăm mỗi thành phố đúng một lần. Ở đây mình sẽ ví dụ với danh sách các thành phố và khoảng cách như sau:
| Thành phố | A | B | C | D | E |
|---|---|---|---|---|---|
| A | max | 5 | 6 | 9 | max |
| B | 5 | max | 10 | 2 | 7 |
| C | 6 | 10 | max | max | 15 |
| D | 9 | 2 | max | max | 1 |
| E | max | 7 | 15 | 1 | max |
Những thành phố không có đường đi nối nhau hoặc cùng thành phố sẽ mặc định để khoảng cách là max, vì mình sẽ đánh giá độ thích nghi theo khoảng cách, khoảng cách càng thấp thì độ thích nghi càng cao.
Code nào :v
Mình sẽ viết bằng Java nha (hehe)
Các biến sẽ sử dụng
public int max = 10000;
public int khoangcach[][] = {{max,5,6,9,max},{5,max,10,2,7},{6,10,max,max,15},{9,2,max,max,1},{max,7,15,1,max}};
public Random ran = new Random();
public static int n = 1000;
int[][] nghiem = new int [n][];
int[] thichnghi = new int[n];
- max: mình mặc định nó sẽ là 10000, lấy cái số thiệt to rứa thôi (yaoming)
- khoangcach[][]: cái mảng để mình lưu cái khoảng cách trong đề bài thui
