GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA KHOA HỌC MÁY TÍNH
Tiểu luận môn : THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN
ĐỀ
Đề tài:
GIẢI THUẬT DI TRUYỀN VÀ ỨNG
DỤNG VÀO BÀI TOÁN NGƯỜI ĐƯA
THƯ
GVHD: PGS. TS Đỗ Văn Nhơn
HVTH: Nguyễn Thị Kim Anh
Mã Số HV: CH1301078
TP HCM 10/2014
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
MỤC LỤC
MỞ ĐẦU
Cùng với sự phát triển của ngành khoa học máy tính, nhu cầu tìm kiếm lời giải tối ưu
ngày càng được quan tâm. Với khả năng hiện nay, máy tính đã giúp giải được rất nhiều bài
toán khó mà trước kia thường bó tay. Mặc dù vậy, vẫn còn một số lớn các bài toán rất thú vị
nhưng chưa có thuật giải hợp lý để giải chúng. Trong số đó, các bài toán tối ưu là những bài
toán thường xuyên gặp phải trong các ứng dụng thực tiễn.
Trong thực tiễn, có nhiều bài toán tối ưu quan trọng đòi hỏi những thuật giải chất lượng cao.
Nói chung, bài toán tối ưu có thể được xem như bài toán tìm kiếm giải pháp (tốt nhất) trong
không gian (vô cùng lớn) các giải pháp. Khi không gian tìm kiếm nhỏ, các phương pháp cổ
điển như trên cũng đủ thích hợp; nhưng khi không gian lớn cần phải dùng đến những kỹ thuật
Trí Tuệ Nhân Tạo đặc biệt. Thuật giải Di Truyền (GA) là một trong những kỹ thuật đó.
Thuật giải di truyền được ứng dụng rất rộng rãi trong các lĩnh vực phức tạp, ứng dụng khá
nhiều trong các lĩnh vực như khoa học, kinh doanh và giải trí. Đầu tiên phải kể đến là các bài
toán tối ưu bao gồm tối ưu số và tối ưu tổ hợp.

thể và cá thể chính là gen nên ta sẽ dùng lẫn lộn thuật ngữ gen và cá thể từ đây về sau.
Ban đầu, ta sẽ phát sinh một số lượng lớn, giới hạn các cá thể có gen ngẫunhiên - nghĩa là
phát sinh một tập hợp các chuỗi bit ngẫu nhiên. Tập các cá thểnày được gọi là quần thể ban
đầu (initial population). Sau đó, dựa trên mộthàm nào đó, ta sẽ xác định được một giá trị gọi
là độ thích nghi - Fitness. Giátrị này, để đơn giản cho bạn đọc lúc đầu, có thể tạm hiểu chính
là độ "tốt" củalời giải hay độ cao trong tìm kiếm theo kiểu leo đồi. Vì phát sinh ngẫu nhiên
nênđộ "tốt" của lời giải hay tính thích nghi của các cá thể trong quần thể ban đầu làkhông xác
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
định.Để cải thiện tính thích nghi của quần thể, người ta tìm cách tạo ra quần thể mới.Có hai
thao tác thực hiện trên thế hệ hiện tại để tạo ra một thế hệ khác với độ thích nghi tốt hơn.
Thao tác đầu tiên là sao chép nguyên mẫu một nhóm các cá thể tốt từ thế hệ trước rồi đưa
sang thế hệ sau (selection). Thao tác này đảm bảo độ thích nghi của thế hệ sau luôn được giữ
ở một mức độ hợp lý. Các cá thể được chọn thông thường là các cá thể có độ thích nghi cao
nhất.
Thao tác thứ hai là tạo các cá thể mới bằng cách thực hiện các thao tác sinh sản trên một
số cá thể được chọn từ thế hệ trước – thông thường cũng là những cá thể có độ thích nghi
cao. Có hai loại thao tác sinh sản : một là lai tạo tác lai tạo (crossover), hai là đột biến
(mutation). Trong thao tác lai tạo, từ gen của hai cá thể được chọn trong thế hệ trước sẽ được
phối hợp với nhau (theo một số quy tắc nào đó) để tạo thành hai gen mới. Thao tác chọn lọc
và lai tạo giúp tạo ra thế hệ sau. Tuy nhiên, nhiều khi do thế hệ khởi tạo ban đầu có đặc tính
chưa phong phú và chưa phù hợp nên các cá thể không rải đều được hết không gian của bài
toán (tương tự như trường hợp leo đồi, các người leo đồi tập trung dồn vào một góc trên vùng
đất). Từ đó, khó có thể tìm ra lời giải tối ưu cho bài toán. Thao tác đột biến sẽ giúp giải quyết
được vấn đề này. Đó là sự biến đổi ngẫu nhiên một hoặc nhiều thành phần gen của một cá thể
ở thế hệ trước tạo ra một cá thể hoàn toàn mới ở thế thệ sau. Nhưng thao tác này chỉ được
phép xảy ra với tần suất rất thấp (thường dưới 0.01), vì thao tác này có thể gây xáo trộn và
làm mất đi những cá thể đã chọn lọc và lai tạo có tính thích nghi cao, dẫn đến thuật toán
không còn hiệu quả.
Thế hệ mới được tạo ra lại được xử lý như thế hệ trước (xác định độ thích nghi và tạo thế

số trong khoảng [32,63] chỉ cần 5 bit là đủ. Tại sao vậy? Vì với 5 bit, ta chỉ có thể biểu diễn
được một số Y trong khoảng [0,31]? Nhưng ta nhận xét rằng, với mọi số X trong khoảng
[32,63] ta đều xác định được một quy tắc để tương ứng với một số Y trong khoảng [0,31]. Cụ
thể là Y = X – 32. Và thay vì biểu diễn trực tiếp số X, ta biểu diễn thông qua trung gian Y.
Khi đã có Y ta sẽ dễ dàng suy ra X thông qua quy tắc trên.
Để biểu diễn chuỗi nhị phân, ta thường dùng các cách sau : mảng byte, mảng bit biểu
diễn bằng mảng byte, mảng bit biểu diễn bằng mảng INTEGER.3.1.1 Mảng byte:
Đối với mảng byte, mỗi byte chính là một bit và chỉ nhận hai giá trị 0 và 1. Nếu
byte trong mảng có giá trị khác, chương trình sẽ xem đó là lỗi trầm trọng. Cách
biểu diễn này có lợi điểm là truy xuất nhanh hơn phương pháp, nhưng lượng
bộ nhớ sẽ tốn gấp 8 lần so với phương pháp không nén (vì một byte gồm 8 bit,nhưng ta chỉ
dùng 1 bit nên 7 bit còn lại sẽ bị phí).
II.1.2 Mảng byte nén
Đối với kiểu biểu diễn này, một byte trong mảng sẽ biểu diễn cho 8 bit củachuỗi nhị
phân. Bit 0 đến bit thứ 7 sẽ nằm trong byte thứ 0, bit 8 đến 15 sẽ nằmtrong byte thứ 1, và
cứ thế. Một cách tổng quát, bit thứ n sẽ nằm trong bytethứ (n DIV 8). Trong đó, DIV là toán
tử chia lấy phần nguyên).
Kiểu biểu diễn này là kiểu biểu diễn ít tốn kém bộ nhớ nhất nhưng ngược lại, thao tác truy
xuất lại chậm hơn rất nhiều so với phương pháp mảng byte. Để lấy được một bit thứ n, ta
phải thực hiện hai thao tác : đầu tiên là là xác định bit đó nằm ở byte thứ mấy (bằng cách thực
hiện phép chia n DIV 8), kế đến là xác định xem bit đó nằm ở vị trí bit thứ mấy trong byte
vừa lấy ra (bằng phép chia n MOD 8), bước cuối cùng là thực hiện một vài thao tác trên bit
để lấy ra giá trị bit cần tính. Cho dù có tối ưu bằng cách nào đi chăng nữa, việc truy xuất trên
mảng bit luôn chậm hơn rất nhiều so với thao tác trên mảng byte. Để thực hiện thật nhanh 3
thao tác này, ta dùng các thao tác trên bit (hai phép toán AND, OR và dịch trái, dịch phải trên
bit).
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
II.1.3 Mảng INTEGER nén để tối ưu truy xuất
Trong các máy tính ngày nay, thông thường thì đơn vị truy xuất hiệu quả nhất không còn

II.1.5 Biễu diễn gen bằng chuỗi số thực
Đối với những vấn đề-bài toán có nhiều tham số, việc biểu diễn gen bằng chuỗi số nhị
phân đôi lúc sẽ làm cho kiểu gen của cá thể trở nên quá phức tạp. Dẫn đến việc thi hành cách
thao tác trên gen trở nên kém hiệu quả. Khi đó, người ta sẽ chọn biểu diễn kiểu gen dưới dạng
một chuỗi số thực. Tuy nhiên, chọn biểu diễn kiển gen bằng chuỗi số thực, bạn cần lưu ý quy
tắc sau :
Quy tắc biểu diễn kiểu gen bằng chuỗi số thực : Biểu diễn kiểu gen bằng số thực phải
đảm bảo tiết kiệm không gian đối với từng thành phần gen.
Quy tắc này lưu ý chúng ta phải tiết kiệm về mặt không gian bộ nhớ đối với các từng
thành phần gen. Giả sử nghiệm của bài toán được cấu thành từ 3 thành phần, thành phần X
thực có giá trị trong khoảng [1.0, 2.0], thành phần Y nguyên trong khoảng [0,15] và thành
phần Z trong khoảng [5,8]. Thì chúng ta rất không nên chọn biểu diễn kiểu gen bằng một
chuỗi 3 thành phần số thực. Vì như chúng ta đã biết, ít nhất mỗi số thực được phải được biểu
diễn bằng 6 byte. Chỉ với 3 số thực, ta đã tốn hết 18 byte. Như vậy với trường hợp cụ thể này,
ta nên chọn biểu diễn bằng chuỗi nhị phân, trong đó dùng khoảng 10bit cho thành phần X (độ
chính xác khoảng 0.001), 4 bit cho thành phần Y và 2 bit cho thành phần Z. Tổng cộng chỉ
chiếm có 16 bit = 2 byte. Chúng ta đã tiết kiệm được rất nhiều bộ nhớ!Chuỗi số thực được
biểu diễn thông qua mảng số thực.
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
II.1.6 Cấu trúc cây
Cấu trúc cây thường được dùng trong trường hợp bản thân CTDL của bài toán cũng có
dạng cây. Đây là một trường hợp phức tạp nên hiếm khi được sử dụng. Trong phạm vi cuốn
sách này, ta sẽ không khảo sát nhiều về kiểu dữ liệu này mà chỉ đưa ra một ví dụ minh họa cụ
thể để bạn đọc có được một số khái niệm ban đầu về CTDL dạng cây. Ngay cả các thao tác
trên cây của thuật giải di truyền thường phụ thuộc nhiều vào bài toán đang xét. Do đó, ở đây
ta sẽ không trình bày một cách tổng quát.
Một loại cây thường được sử dụng trong thuật giải di truyền là dạng cây hai nhánh (ở đây
chúng tôi dùng chữ hai nhánh để phân biệt với loại cây nhị phân – thường dùng trong sắp xếp
và tìm kiếm).

thích nghi sẽ ứng với khả năng được chọn lọc trong việc sinh ra thế hệ sau nên người ta
thường chọn cách tính sao cho độ thích nghi cuối cùng là một xác suất, nghĩa là tổng độ thích
nghi của các cá thể phải nhỏ hơn hoặc bằng 1.
II.2.2 Độ thích nghi xếp hạng (rank method)
Cách tính độ thích nghi tiêu chuẩn như trên chỉ thực sự hiệu quả đối với nhữngquần thể
có độ tốt tương đối đồng đều giữa các cá thể. Nếu, vì một lý do nàođó – có thể do chọn hàm
mục tiêu không tốt - có một cá thể có độ tốt quá cao,tách biệt hẳn các cá thể còn lại thì các cá
thể của thế hệ sau sẽ bị “hút” về phíacá thể đặc biệt đó. Do đó, sẽ làm giảm khả năng di
truyền đến thế sau của cáccá thể xấu, tạo nên hiện tượng di truyền cục bộ, từ đó có thể làm
giảm khảnăng dẫn đến lời giải tốt nhất (vì cá thể đặc biệt đó chưa chắc đã dẫn đến lờigiải tốt
nhất).
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
Phương pháp xác định độ thích nghi xếp hạng sẽ loại bỏ hiện tượng di truyềncục bộ này.
Phương pháp này không làm việc trên giá trị độ lớn của hàm mụctiêu G mà chỉ làm việc dựa
trên thứ tự của các cá thể trên quần thể sau khi đãsắp xếp các thể theo giá trị hàm mục tiêu G.
Chính vì vậy mà ta gọi là độ thíchnghi xếp hạng. Phương pháp này sẽ cho ta linh động đặt
một trọng số để xácđịnh sự tập trung của độ thích nghi lên các cá thể có độ tốt cao, mà vẫn
luônđảm bảo được quy luật : cá thể có độ thích nghi càng cao thì xác suất được tồntại và di
truyền càng cao.
Một cách ngắn gọn, ta có độ thích nghi (hay xác suất được chọn) của cá thể thứi được tính
theo công thức sau :
F(i) = p*(1-p)i-1
với p là một hằng số trong khoảng [0,1].
Công thức trên được xây dựng dựa trên quy tắc được trình bày ngay sau đâyvà chúng ta sẽ
xem phần giải thích quy tắc này như một tư liệu tham khảo.
QUY TẮC
1) Sắp xếp các cá thể của quần thể giảm dần theo thứ tự của giá trị hàm mụctiêu.
2) Chọn một con số p trong khoảng [0,1]. Đây chính là trọng số xác định độ “hút”của các cá
thể tốt.

Giá trị p càng nhỏ thì độ giảm của tính thích nghi càng nhỏ. Dựa vào đặc tính này, ta có
thể dễ dàng kiểm soát được tính “hút” của các cá thể tốt trong quần thể bằng cách tăng hoặc
giảm trị p tương ứng.
II.2.3 Độ thích nghi xếp hạng dựa trên độ phân ly
Hiện nay, khi xác định tính thích nghi của một cá thể (hay lời giải) ta chỉ mới quan tâm
đến độ tốt của cá thể đó mà thôi, nghĩa là ta chỉ sắp hạng theo độ tốt, mà chưa quan tâm đến
mối quan hê giữa cá thể đó đối với quần thể xung quanh nó. Như vậy, những cá thể ngay từ
đầu có chất lượng rất kém (phân ly quá xa so với những cá thể có chất lượng tương đối đều
nhau) đều có xu hướng bị loại bỏ ngay. Mà những cá thể đặc biệt này, trong một số trường
hợp vẫn có thể tiềm tàng dẫn đến lời giải. Trong tự nhiên, các cá thể trông có vẻ không thích
nghi trong tự nhiên vẫn sống sót khá tốt trong các vùng sinh thái nằm ngoài vùng của các cá
thể có độ thích nghi tương đối tốt. Chính vì vậy, khi sắp hạng để các cá thể có độ thích nghi
rất thấp (phân ly) vẫn có cơ hội phát triển, người ta đưa thêm yếu tố độ phân ly của một cá
thể.
Công thức để đo độ phân ly của một cá thể là:
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
II.3 Nguyên lý về chọn lọc các cá thể có độ thích nghi tốt
Khả năng được chọn vào quá trình sinh sản thế hệ kế tiếp đồng biến với tính thích nghi
của cá thế.
Để xây dựng thế hệ quần thể tiếp theo, ta phải chọn lọc các cá thể có độ thích nghi tốt để
tham gia vào quá trinh lai ghép, đột biến. Ở đây, một khi đả xác định được độ thích nghi của
các cá thể thì việc chọn lọc cá thể chỉ việc tuân theonguyên tắc : càng thích nghi cao thì càng
có xác suất được chọn lọc trong quá trình sinh sản thế hệ kế tiếp cao hơn.
Lưu ý : Đừng nhầm lẫn độ thích nghi và hàm mục tiêu
Độ thích nghi là mộtgiá trị, được xây dựng dựa trên hàm mục tiêu. Khi xây dựng cách
tính độ thích nghi ta đã xem xét mọi khả năng để ngay cả những cá thể trông có vẻ không tốt
(giá trị hàm mục tiêu thấp) cũng có thể có độ thích nghi cao. Do đó, bạn nên luôn nhđ rằng độ
thích nghi quy định khả năng đượcchọn lọc vào quá trình sinh sản thế hệ sau. Độ thích nghi
sẽ đồng biến với khả năng được lựa chọn.

1
, B
2
. Hai gen mới được tạo ra bằng cách ghép phần đầu của cá thể A với phần
cuối của cá thể В (A
1
B
2
) và ngược lại, ghép phần đầu của cá thể B với phần cuối của cá thể A
(B
1
A
2
).
Ví dụ, giả sử hai cá thể được lựa chọn để lai ghép có gen là hai chuỗi nhị phân sau :
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
II.3.3 Lai ghép đa điểm
Lai ghép đa điểm là một dạng tổng quát hơn của lai ghép đơn điểm. Trong lai ghép đơn
điểm, thay vì chỉ chọn một điểm lai ghép, ta chọn nhiều điểm lai ghép к
i
, k
j
, k
m
. m điểm lai
ghép này sẽ chia gen của hai cá thể cha mẹ А, в thành m+1 đoạn. Hai gen mới sẽ được tạo ra
bằng cách ghép các đoạn này cùa hai gen A,B theo quy tắc : các đoạn ở vị trí lẻ được giữ
nguyên, các đoạn ở vị trí chẵn được hoán chuyển với nhau (như ở lai ghép đơn điểm).
Ví dụ, giả sử hai cá thể được lựa chọn để lai ghép có gen là hai chuỗi nhị phân sau :

GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
III.1 Mô hình hóa vấn đề
Khảo sát và thu thập dữ liệu, thông tin và tri thức (DIK):
Thông tin về các thành phố
Thuộc tính đường: độ dài, 1 chiều hay 2 chiều
Số con đường đi qua thành phố
Chọn lọc vấn đề và chuẩn hóa DIK + Xác định cơ sở DIK cho vấn đề
Độ dài
Đường 1 chiều/ 2 chiều
Mô tả giả thiết của vấn đề
Điểm đầu/ xuất phát: thành phố (bắt đầu).
Điểm cuối: quay trở lại điểm xuất phát.
Mô tả mục tiêu hay kết luận của vấn đề:
Tìm chu trình ngắn nhất.
III.2 Xây dựng mô hình:
Mô hình cho DIK
Trong bài toán người đưa thư có liên quan chặt chẽ đến bài toán chu trình hamilton,
một nhân viên thư tín phải ghé thăm n thành phố. Mô hình hóa bài toán như là một
đồ thị đầy đủ có n đỉnh, ta có thể nói rằng người đưa thư muốn làm một tour, hoặc chu trình
Hamilton, đến thăm mỗi thành phố đúng một lần và kết thúc ở thành phố anh ta bắt đầu.
Các nhân viên đưa thư phải gánh chịu một chi phí số nguyên không âm c(i;j) đi từ
thành phố i đến thành phố j, và các nhân viên đưa thư muốn thực hiện các tour có chi phí
tổng cộng là tối thiểu, tổng chi phí là tổng các chi phí riêng lẻ dọc theo các cạnh của tour.
TSP = {<G,c,k> : G = (V,E) là một đồ thị đầy đủ,
c là một hàm từ V x X -> Z,
k ∈ Z, và
G có một tua người đưa thư du hành với mức hao phí tối đa k }.
Mô hình cho giả thiết
Input: a ∈ V; z ∈ V
Output: Đường đi P nối a tới z sao cho:

n
> biểu diễn một lộ trình: từ i
1
; đến i
2
từ i
n-1
đến
i
n
, và trở vể iI (v là một hoán vị của vectơ <1, 2,n>).
Vấn đề thứ hai là khởi tạo quần thề đầu. Đối với tiến trình khởi tạo, ta có thể sử một số
thuật giải heuristic (chẳng hạn như dùng thuật giải Greedy áp dụng nguyên lý “tham lam” vào
bài toán TSP. Ta sẽ áp dụng thuật giải Greedy nhiều lần, mỗi lần từ một thành phố đầu khác
nhau); hoặc đơn giản hơn là khởi tạo quần thể bằng cách tạo ngẫu nhiên các mẫu từ các hoán
vị của <1, 2,n>.
Việc lượng giá một nhiễm sắc thể rất dễ dàng: cho trước chi phí của chuyến đi giữa các
thành phố, ta có thể dễ dàng tính tổng chi phí của trọn lộ trình.
Về các phép toán di truyền, trước hết, ta xây dựng phép lai OX như sau: cho trước hai cá thể
cha-mẹ, cá thể con có được bằng cách chọn thứ tự lộ trình từ một cá thế và bảo toàn thứ tự
tương đối giữa các thành phố trong cá thế kia. Thí dụ. Nếu cha-mẹ là:
<1 2 3 4 5 6 7 8 9 10 11 12> và
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
<7 3 1 11 4 12 5 2 10 9 6 8>
và khúc được chọn là (4 5 6 7), cá thể con của phép lai sẽ là:
<1 11 12 4 5 6 7 2 10 9 8 3>
Như yêu cầu, cá thể con có quan hệ cấu trúc đối với cả hai cá thể cha-mẹ. Vai trò của
cha và mẹ có thể hoán đổi khi xây dựng cá thể con thứ hai.
Phép đột biến thực hiện đơn giản hơn: ta chỉ cần hoán vị hai vị trí bất kỳ trong cá thể được

if mỗi đỉnh có mộtđỉnh trước đó
then mạng lưới khả thi: stop,
else chọn một đỉnh vđộ ưu tiên cao nhấtcác đỉnh không có đỉnh đầutrước đó; que

v;
xóa v và tất cả các cạnh hang đầu của v từ đồ thị có hường;
end_while.
end_procedure.
Lai ghép
procedure: moon crossover
begin
osp

null;
k  0;
Lựa chọn hai nhiễm sắc thể ngẫu nhiên p
a
and p
b
, khi p
a
= g
1
g
2
g
3
g
4
…gj*

- osp;
end_if
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
Khởi tạo thuật giải di truyền
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
III.5 Tính toán độ phức tạp
Về nguyên tắc, tổng chi phí được áp dụng cho tất cả các vấn đề tối ưu hóa số nguyên với
một không gian giải pháp hữu hạn: Tất cả các điểm của giải pháp không gian S được đánh giá
bắng một hàm mục tiêu lưu trữ các giải pháp tốt nhất đến hiện tại.
TSP có độ phức tạp xấu nhất là O(n!) tổng chi phí chỉ áp dụng
để các trường hợp vấn đề rất nhỏ.
Ví dụ: Thậm chí với một số rất nhỏ khá nhỏ và đơn giản như 30 thành phố đối xứng thì TSP
xem xét (n-1)!/ 2 = (29)!/2.
IV. CÀI ĐẶT THUẬT GIẢI
Để minh họa cho thuật giải di truyền trình bày ở trên, ta sẽ tiến hành cài đặt trực tiếp bằng
ngôn ngữ C#.
Đây là 1 ứng dụng sử dụng giải thuật di truyền để giải bài toán người đưa thư TSP.
Dưới đây là một vài đoạn mã chính của chương trình.
IV.1 Tạo quần thể, tính độ thích nghi
public class Population
{
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
// Holds population of tours
Tour[] tours;
// Construct a population
public Population(int populationSize, Boolean initialise)
{

{
Tour fittest = tours[0];
// Loop through individuals to find fittest
for (int i = 1; i < populationSize2(); i++)
{
if (fittest.getFitness() <= getTour(i).getFitness())
{
fittest = getTour(i);
}
}
return fittest;
}
// Gets population size
public int populationSize2()
{
return tours.Length ;
}
}
IV.2 Quản lý các thành phần của quần thể (ở đây là các tour đường)
public class Tour{
// Holds our tour of cities
private ArrayList tour = new ArrayList();
// Cache
private double fitness = 0;
private int distance = 0;
HVTH: CH1301078 – Nguyễn Thị Kim Anh
GVHD: PGS. TS Đỗ Văn Nhơn TT&PPGQVD - 2014
// Constructs a blank tour
public Tour(){
for (int i = 0; i < TourManager.numberOfCities(); i++) {