BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
(The Traveling Salesman Problem - TSP)
I/ GIỚI THIỆU BÀI TOÁN
Đây là một bài toán cổ điển: Một thương gia phải đi qua nhiều thành phố. Hãy vạch lộ
trình đi qua tất cả các thành phố đó sao cho quãng đường đi là ngắn nhất. Biết rằng mỗi
thành phố chỉ đi qua một lần.
Bài toán TSP khó giải quyết, vì để tìm được lời giải ta phải tiến hành tìm kiếm trên tất cả
lộ trình có thể, và như vậy dẫn tới phí tổn thời gian tính toán rất lớn. Backtracking và các
kỹ thuật khác có thể rút ngắn phạm vi tìm kiếm trong một số điều kiện nhưng vẫn chỉ là sự
hoàn thiện của giải pháp tìm kiếm toàn diện. Khoa học máy tính vẫn chưa tìm ra được một
giải thuật cụ thể có hiệu quả để giải những bài toán tương tự như TSP có kích thước lớn.
Giải thuật Gene tỏ ra hiệu quả trong việc giải các bài toán có thông tin không đầy đủ. Vì
vậy giải thuật này sẽ được sử dụng để hiện thực chương trình.
II/ CÁC KỸ THUẬT GHÉP CHÉO MỚI
Giải thuật Gene mô phỏng sự tiến hoá của thế giới tự nhiên, ở đó thông tin về một cấu trúc
sống được mã hoá dưới dạng nhiễm sắc thể. Do đó để áp dụng giải thuật Gene vào bài toán
TSP, ta cũng phải tìm cách mã hoá các lời giải của bài toán dưới dạng các chuỗi nhiễm sắc
thể và xây dựng qui tắc đánh giá độ thích nghi của nó theo ngữ cảnh của bài toán.
Kí hiệu các thành phố là A, B, C, ... mỗi nhiễm sắc thể - sự mã hoá của lời giải - sẽ là một
danh sách hoán vị của A, B, C ... biểu diễn lộ trình mà người thương gia đã đi qua. Thí dụ
GFHBACDE sẽ là kí hiệu của hành trình từ G -> F -> H -> ... -> E. Mỗi thành phố (gene)
sẽ chỉ xuất hiện trong danh sách này chỉ một lần. Vấn đề này dẫn tới khó khăn không thể
áp dụng các kĩ thuật sinh sản, đột biến thường được sử dụng trong giải thuật Gene chuẩn.
Thí dụ: Với ý nghĩa ghép chéo thông thường ta nhận được từ cặp bố mẹ 1, 2 các con cái
sau:
- Ghép chéo tại một điểm:Bố mẹ Con cái
----------------------------------------------------
#1 ABC|DEFGH ABC|BACDE

trống đoạn hoán đổi:
Con cái 1: BA|---|FGH
Con cái 2: DE|---|GFC
Cuối cùng OX sẽ hoán đổi đoạn ghép chéo nằm giữa hai điểm, tạo ra các con cái mới:
Con cái 1: BA|CDE|FGH
Con cái 2: DE|HBA|GFC
Trong khi PMX giữ nguyên vị trí của gene trong chuỗi nhiễm sắc thể, thì OX lại duy trì thứ
tự các gene trong chuỗi.
2.3- GHÉP CHÉO CÓ CHU KÌ (Cycle crossover - CX)
Nguyên tắc làm việc của CX hoàn toàn khác, nó thực hiện việc hoán đổi một tập hợp cụ
thể các gen. Thí dụ:
Cha mẹ 1: ABCDEFGH
Cha mẹ 2: GFHBACDE
Để tạo con cái, CX bắt đầu với các thành phố đầu tiên trong các nhiễm sắc thể bố mẹ:
Con cái 1: G-------
Con cái 2: A-------
Tìm trong cha mẹ 1, CX thấy G ở vị trí 7 và thực hiện hoán đổi ở vị trí đó:
Con cái 1: G-----D-
Con cái 2: A-----G-
Quá trình tìm và hoán đổi tiếp tục cho đến khi gene bị thay thế đầu tiên trong cha mẹ 1, A,
được bắt gặp. Cuối cùng con cái nhận được như sau:
Con cái 1: GECBAFDH
Con cái 2: ABHDECGE
2.4- PHÉP ĐẢO VỊ TRÍ (Inversion operator)
Để tăng tính đa dạng có thể đưa thêm vào bài toán phép hoán vị, thực hiện việc đảo ngược
vị trí các gene trong chuỗi nhiễm sắc thể. Thí dụ:
ABC|DEFGH đảo thành ABCHGFED
G|FHB|ACDE đảo thành GBHFACDE
2.5- PHÉP ĐỘT BIẾN
Được định nghĩa lại dưới dạng hoán vị vị trí của hai gene. Thí dụ: Hoán vị các gene A và E

Mutation, Inversion, PM Crossover, Order
Crossover:
Nếu đánh dấu checkbox thì các phép
toán sinh sản tương ứng sẽ được chọn
theo xác xuất tương ứng.
Linear Normalization Các thông số này dùng để điều chỉnh lại
các fitness của các thành viên trong
cộng đồng vì chúng có thể chênh lệch
không nhiều.Sơ đồ giải thuật Gene của bài toán TSP ở trên có thể hiện thực bằng đoạn chương trình
chính sau đây:
typedef size_t CityChrom[10];
static const size_t CSZ = 10 * sizeof(size_t);
const size_t POP_SZ = PopSize;
static const char *cityName[10] =
{
"A ", "E ",
"G ", "I ",
"C ", "F ",
"D ", "H ",
"B ", "E "
};
static const double distance[10][10] =
{
{0.0, 220.0, 90.0, 155.0, 133.0, 123.0, 182.0, 89.0, 105.0, 141.0},
{220.0,0.0, 135.0, 55.0, 173.0, 117.0, 124.0, 122.0, 222.0, 85.0},
{90.0, 135.0, 0.0, 92.0, 69.0, 34.0, 95.0, 56.0, 98.0, 57.0},
{155.0,55.0, 92.0, 0.0, 145.0, 84.0, 116.0, 68.0, 184.0, 54.0},

else
operwt[1] = 0.0;
if (PMX)
operwt[2] = WeightP;
else
operwt[2] = 0.0;
if (CX)
operwt[3] = WeightC;
else
operwt[3] = 0.0;
if (OX)
operwt[4] = WeightO;
else
operwt[4] = 0.0;
RouletteWheel ow(5,operwt);
// khởi tạo cộng đồng ban đầu bằng phép hoán vị Josephus
for (i = 0; i < POP_SZ; ++i)
{
int plist[10];
memset(plist,0,CSZ);
s = size_t(devgen() * 8.0) + 1;
j = size_t(devgen() * 10.0);
k = 0;
while (1)
{
pop[i][k] = j;
plist[j] = 1;
if (k == 9)
break;
for (l = 0; l < s; ++l)