TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT
----------o0o----------

HỌC PHẦN
HỌC MÁY NÂNG CAO

BÁO CÁO CUỐI KỲ
ĐỀ TÀI: GIẢI THUẬT DI TRUYỀN GENETIC ALGORITHM (GA)
GVHD: PGS.TS. Quản Thành Thơ
Thành viên nhóm 3 thực hiện:
 Phạm Hồng Phương 1918480104006
 Nguyễn Quốc Việt

1918480104008

 Ơn Thiện Tài

1918480104007

 Nguyễn Xuân Bình

1918480104001

Lớp: CH19HT01
Bình Dương, tháng 8 năm 2020


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

BÁO CÁO CUỐI KỲ MÔN MÁY HỌC NÂNG CAO
ĐỀ TÀI: GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

GVHD: PGS.TS. Quản Thành Thơ
Thành viên nhóm thực hiện:
 Phạm Hồng Phương

1918480104006

 Nguyễn Quốc Việt

1918480104008

 Ơn Thiện Tài

1918480104007

 Nguyễn Xn Bình

1918480104001

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 2/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao


MỤC LỤC
I.

KHÁI NIỆM........................................................................................................... 4
1. Di truyền ............................................................................................................... 3
2. Thuyết tiến hóa Darwin ........................................................................................ 3

II. GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA) ....................... 4
1. Khái niệm...................................................................................................................................... 3
2. Các bước cơ bản của giải thuật di truyền ............................................................. 4
2.1. Khởi tạo quần thể ban đầu ............................................................................. 5
2.2. Hàm mục tiêu (Fitness) .................................................................................. 5
2.3. Các toán tử di truyền ...................................................................................... 6
2.3.1. Toán tử chọn lọc ..........................................................................................7
2.3.2. Phép tái sinh ............................................................................................7
2.3.3. Phép chọn ................................................................................................7
2.3.4. Toán tử ghép chéo (phép lai) ...................................................................8
2.3.5. Toán tử đột biến.......................................................................................8
2.4.

Điều kiện dừng ...........................................................................................8

2.5.

Đặc điểm hội tụ của Giải thuật di truyền .................................................8

3. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN ĐỂ GIẢI BÀI TOÁN ONE – MAX.......................9
3.1.

Population initialization (Khởi tạo quần thể) .............................................9


3.2.

Evaluation (Đánh giá độ thích nghi) .........................................................10

3.3.

Selection (Chọn lọc) ..................................................................................11

3.4.

Crossover (Lai ghép) .................................................................................13

3.5.

Mutation (Đột biến) ...................................................................................13

3.6.

Đoạn code cho bài tốn One-Max .................................................................. 13

BÀI TỐN NGƯỜI DU LỊCH (TSP) .............................................................................18
Gợi ý ......................................................................................................................18
TÀI LIỆU THAM KHẢO...........................................................................................18

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 3/19



TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

I.

Môn học: Học Máy Nâng Cao

Khái niệm
1. Di truyền

"Di truyền" là "hiện tượng chuyển những tính trạng của cha mẹ cho con cái thơng
qua gen của bố mẹ". Trong sinh học, di truyền chuyển những đặc trưng sinh học từ
một sinh vật cha mẹ đến con cái và nó đồng nghĩa với di chuyển gen, gen thừa nhận
mang thông tin sinh học hay thông tin di truyền. (Wikipedia)

2. Thuyết tiến hóa Darwin
Vào giữa thế kỉ 19, học thuyết tiến hóa được đưa ra bởi Charles Darwin đã làm
chấn động toàn thế giới. Trong học thuyết này, ơng khẳng định rằng mọi lồi sinh vật
được sinh ra không phải do Chúa, Trời hay Thần thánh mà là xuất hiện và phát triển
nhờ quá trình chọn lọc tự nhiên. Trong quá trình này, khi những cá thể của một quần
thể chết đi, chúng được thay thế bằng những hậu duệ của thế hệ cha mẹ nhưng có thể
thích nghi tốt hơn độ tồn tại và sinh sơi trong môi trường mà sự chọn lọc tự nhiên diễn
ra. Quá trình này tạo ra và bảo tồn những đặc điểm được cho là phù hợp hơn cho chức
năng mà chúng đảm nhiệm. Chúng ta có thể hiểu ra hơn q trình chọn lọc tự nhiên
bằng giải thích mà Darwin đưa ra về sự xuất hiện của hươu cao cổ: “Trong quần thể
Hươu vốn đã tồn tại những con Hươu có cổ cao hơn bình thường nhờ gen di truyền và
sự đột biến. Trải qua quá trình sinh sống và phát triển, môi trường thay đổi khiến cho
thức ăn càng ngày càng khó kiếm hơn, khiến những con Hươu có chiếc cổ cao sẽ
chiếm ưu thế sinh tồn hơn. Lâu dần thì thế hệ Hươu mới sẽ được thay bằng những con
Hươu cao cổ có khả năng sinh sản và thích nghi nghi với mơi trường lớn hơn”


II. Giải thuật di truyền - Genetic Algorithm (GA)
1. Khái niệm
Giải thuật di truyền (GA-Genetic Algorithm) là kỹ thuật phỏng theo q 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. GA là
phương pháp tìm kiếm tối ưu ngẫu nhiên bằng cách mô phỏng thểo sự tiến hóa của con
người hay của sinh vật. Tư tưởng của thuật tốn di truyền là mơ phỏng các hiện tượng
tự nhiên, là kế thừa và đấu tranh sinh tồn.
GA thuộc lớp các giải thuật xuất sắc nhưng lại rất khác các giải thuật ngẫu nhiên vì
chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên. Khác biệt quan trọng giữa
tìm kiếm của GA và các phương pháp tìm kiếm khác là GA duy trì và xử lý một tập các
lời giải, gọi là một quần thể (population). Trong GA, việc tìm kiếm giả thuyết 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 ban đầu của các giả thuyết.
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 q 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 liên hệ với đại
lượng thích nghi, với các giả thuyết phù hợp nhất được chọn thểo xác suất là các hạt
GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 4/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

giống 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. GA có thể dị
tìm thế hệ mới có độ thích nghi tốt hơn. GA giải quyết các bài tốn quy hoạch tốn học
thơng qua các quá trình cơ bản: lai tạo (crossover), đột biến (mutation) và chọn lọc
(selection) cho các cá thể trong quần thể. Dứng GA đòi hỏi phải xác định được: khởi

tạo quần thể ban đầu, hàm đánh giá các lời giải thểo mức độ thích nghi – hàm mục tiêu,
các tốn tử di truyền tạo hàm sinh sản.
GA dứng thuật ngữ cá thể độ thể hiện cho lời giải của không gian lời giải. Mỗi cá thể
được đăc trưng bởi một tập các gen. Các gen này gộp thành một chuỗi gọi là nhiễm sắc
thể. Trong giải thuật di truyền, thông thường nhiễm sắc thể được biển diễn dưới dạng
một chuỗi các số nhị phân.

2. Các bước cơ bản của giải thuật di truyền
Bước 1: Khởi tạo một quần thể ban đầu gồm các cá thể.
Bước 2: Đánh giá độ thích nghi cho từng cá thể tương ứng
Bước 3: Tạo cá thể mới dựa trên các toán tử di truyền. (Chọn lọc, lai ghép, đột biến)
Bước 4: Loại bớt các cá thể có độ thích nghi thấp.

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 5/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

Bước 5: Xác định đọ thích nghi cho các cá thể mới và đưa vào quần thể
Bước 6: Kiểm tra thỏa mãn điều kiện dừng, Nếu điều kiện đúng, lấy ra cá thể tốt nhất,
giải thuật dừng lại; ngược lại, quay về bước 3.

Hình lưu đồ giải thuật
2.1. Khởi tạo quần thể ban đầu
Có 2 phương pháp chính độ khởi tạo quần thể trong giải thuật di truyền
Khởi tạo quần thể ngẫu nhiên: Khởi tạo quần thể với các cá thể ngẫu nhiên

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 6/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

Khởi tạo Heutistic: Khởi tạo quần thể với phương pháp Heuristic đã biết trước
Thểo nghiên cứu, khi khởi tạo toàn bộ quần thể bằng phương pháp Heuristic, quần
thể sẽ có nhiều cá thể tương tự nhau do vậy quần thể có thể bị thiếu đa dạng và ảnh
hưởng đến độ fitness ban đầu. Các cá thể ngẫu nhiên đưa lí giải bài toán đến tối
ưu. Do vậy cách tốt nhất khi khởi tạo là khởi tạo heuristic cho một vài cá thể, các
cá thể cịn lại thì khởi tạo thểo phương pháp ngẫu nhiên
2.2. Hàm mục tiêu (Fitness)
Một hàm mục tiêu (fitness) sẽ lấy một chuỗi nhiễm sắc thể như là đầu vào và trả
về giá trị tượng trưng cho chuỗi nhiễm sắc thể đó độ đánh giá trên vấn đề cần giải
quyết.
Hàm mục tiêu có vai trị tương tự như là mơi trường sồng trong sự tiến hố của tự
nhiên. Vấn đề tương tác giúa một cá thể với môi trường sồng được thể hiện qua giá
trị của hàm mục tiêu trong mỗi một cá thể.
Giá trị hàm mục tiêu là Maximum hoặc Minimum tuỳ thểo bài toán sẽ quyết định xác
suất của mỗi chuỗi có thể tham gia vào các toán tử di truyền.
2.3. Các toán tử di truyền
2.3.1.

Toán tử chọn lọc

Toán tử chọn lọc gồm hai quá trình: quá trình sinh sản (phép tái sinh), quá trình chọn

lọc (phép chọn).
2.3.2.
Phép tái sinh
Phép tái sinh là quá trình các cá thể được sao chép trên cơ sở độ thích nghi. Độ
thích nghi là một hàm được gán giá trị thực, tương ứng với mỗi cá thể trong quần
thể. Q trình này, được mơ tả như sau:
Xác đành độ thích nghi của từng cá thể trong quần thể ở thế hệ thứ t cộng dồn các giá
trị thích nghi (theo thứ gán cho từng cá thể). Giả sử, quần thể có n cá thể. Gọi độ thích
nghi của cá thể i tương ứng là fi tổng cộng dồn thứ i là fti được xác đành bởi:

Gọi Fn là tổng độ thích nghi của tồn quần thể. Chọn một số ngẫu nhiên f trong
khoảng từ 0 tới Fn. Chọn cá thể thứ k đầu tiên thỏa mãn f > ftk đưa vào quần thể
mới.
2.3.3.

Phép chọn

Là quá trình loại bỏ các cá thể kém thích nghi trong quần thể. Q trình này được mô
tả như sau:
GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 7/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

Sắp xếp quần thể thểo thứ tự mức độ thích nghi giảm dần.
Loại bỏ các cá thể ở cụối dãy. Giữ lại n cá thể tốt nhất.

2.3.4.
Toán tử ghép chéo (phép lai)
Quá trình này diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai nhiễm sắc thể cha
- mẹ để hình thành nhiễm sắ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 và mẹ đề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 hai chuỗi nhiễm sắc thể cha mẹ thành hai nhóm nhiễm sắc thể con là m1 và m2. Hai chuỗi nhiễm sắc thể con lúc
này sẽ là m11 + m22 và m21 + m12.
Đưa hai chuỗi nhiễm sắc thể con vào quần thể để tiếp tục tham gia quá trình tiến
hóa
2.3.5.
Tốn tử đột biến
Q trình tiến hóa được gọi là quá trình đột biến khi một hoặc một số tính trạng
của con khơng được thừa hưởng từ hai chuỗi nhiễm sắc thể cha - mẹ. Phép đột
biến xảy ra với xác suất thấp hơn rất nhiều lần so với xác suất xảy phép lai. Phép
đột biến có thể mơ tả như sau:
 Chọn ngẫu nhiên một cá thể trong quần thể
 Tạo một số ngẫu nhiên k trong khoảng từ 1 tới m, 1 6 k 6 m.
 Thay đổi giá trị của gen thứ k. Đưa cá thể này vào quần thể để tham gia q
trình tiến hố ở thế hệ tiếp thểo.
2.4. Điều kiện dừng
Quá trình tạo quần thể mới của Giải thuật di truyền này sẽ được lặp lại cho đến khi
thỏa điều kiện dừng. Các điều kiện dừng thường thấy là:
 Một cá thể được tìm thấy thỏa mãn các điều kiện được đề ra.
 Một số lượng thế hệ được tạo ra cố định.
 Thời gian tính tốn đạt mức.
 Sự hội tụ của quần thể.
 Sự kết hợp của các điều kiện dừng trên.
2.5. Đặc điểm hội tụ của Giải thuật di truyền

Khi áp dụng Giải thuật GAs cho các vấn đề thực tế thường rất khó khăn. Lý do:
GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 8/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

 Cách biểu diễn nhiễm sắc thể có thể tạo ra khơng tìm kiếm khác với khơng
gian thực của bài tốn
 Số bước lặp, khi cài đặt thường khơng xác định trước
 Kích thước quần thể thường có giới hạn
Trong một số trường hợp, Giải thuật di truyền không thể tìm được lời Giải tối ưu.
Lý do, Giải thuật di truyền hội tụ sớm về lời Giải tối ưu cục bộ. Hội tụ sớm là vấn
đề của Giải thuật di truyền cũng như các Giải thuật tối ưu khác. Nếu hội tụ xảy ra
q nhanh thì các thơng tin đáng tin cậy đang phát triển trong quần thể thường bị
bỏ qua. Nguyên nhân của sự hội tụ sớm liên quan tới hai vấn đề:
 Quy mô và loại sai số do cơ chế khởi tạo quần thể.
 Bản chất của hàm mục tiêu
3. Ứng dụng giải thuật di truyền để giải bài toán One – max
Bài toán One-max là một bài tốn đơn giản trong tính tốn tiến hố. Với bài toán
này, chúng ta cần tiến hoá các cá thể của một quần thể để tìm ra một cá thể cụ thể
với độ thích nghi cao nhất. Cụ thể là, mỗi các thể được biễu diễn bằng một chuỗi
các số nhi phân, việc chúng ta cần là tiến hoá các chuỗi nhị phân thành chuỗi nhị
phân lớn nhất. Ví dụ như: cho tập các chuỗi ban đầu với độ dài n = 6, mục tiêu cần
làm là tiến hoá các chuỗi để trở thành 111111.
3.1.


Population initialization (Khởi tạo quần thể)

Ở bước này, dựa vào thông tin số cá thể m và số gen của một cá thể n, quần thể
gồm m cá thể được khởi tạo với các giá trị ngẫu nhiên. Hình sau minh họa giá trị
khởi tạo một quần thể với m = 10 và n = 6.

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 9/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

3.2.

Môn học: Học Máy Nâng Cao

Evaluation (Đánh giá độ thích nghi)

Ở bước này, GA sử dụng một hàm được cung cấp sẵn để tính fitness cho từng cá
thể. Với bài one-max, hàm cung cấp sẵn chính là hàm secret(), nhận input là một
cá thể và output là giá trị fitness của cá thể đó. GA không biết nội dung bên trong
của hàm secret() mà chỉ biết chuẩn input và giá trị output. Minh họa bước tính
fitness cho quần thể ở hình sau

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 10/19



TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

3.3.

Môn học: Học Máy Nâng Cao

Selection (Chọn lọc)

Dựa vào giá trị fitness của mỗi cá thể, bước selection sẽ chọn ra một tập hợp các
cá thể có fitness tốt nhất. Nguyên tắc chọn là cá thể nào có fitness càng cao thì khả
năng cá thể đó sẽ được chọn càng nhiều lần. Có nhiều phương pháp selection
trong GA, và ở bài này chúng ta sẽ áp dụng phương pháp binary selection. Binary
selection hoạt động như sau: lấy ngẫu nhiên hai cá thể trong quần thể, cá thể nào
có fitness tốt hơn thì được chọn.
Nói cách khác, giả sử các cá thể trong quần thể được đánh giá trị index (từ 0 đến 9
cho 10 cá thể). Để chọn ra được một cá thể tốt, chúng ta sẽ sinh ra hai số ngẫu
nhiên i1 và i2 nằm trong đoạn [0, 9]. Sau đó, lấy hai cá thể vị trí index i1 và i2, cá
thể nào có fitness cao hơn sẽ được chọn.
Binary selection có thể cài bằng với hai bước: 1) sắp xếp các cá thể theo thứ tự
tăng dần với tiêu chí fitness; 2) Sinh ra hai số ngẫu nhiên i1, i2∈[0, m−1], rồi chọn
cá thể có giá trị index lớn hơn. Hình sau minh họa binary selection.

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 11/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao


Ví dụ minh họa trên muốn chọn ra hai cá thể tự quần thể hiện tại. Ban đầu, quần
thể được sắp xếp theo tứ tự tăng đần của fitness. Sau đó, hai cặp số ngẫu nhiên
được sinh ra. Cặp số đầu tiên là (9, 4), nghĩa là giữa hai cá thể ở vị trí index 9 và 4,
chọn cá thể tốt hơn. Do quần thể đã được sắp xếp, vị trí index lớn hơn sẽ được
chọn. Cuối cùng, cá thể có index 9 được chọn. Tương tự cho cặp số ngẫu nhiên
thứ 2 (5, 2), cá thể vị trí index 5 được chọn.
Trong trường hợp chúng ta muốn lựa chọn những cá thể tốt từ quần thể hiện tại để
tạo ra một quần thể mới, m cặp số ngẫu nhiên sẽ được sinh ra nhằm chọn ra
được m cá thể cho quần thể mới. Hình sau mình họa quá trình tạo quần thể mới.

Chúng ta thấy được rằng ở quần thể mới, những cá thể tốt nhất ở quần thể cũ được
giữ lại và những cá thể có fitness nhỏ được loại bỏ. Điều này có ý nghĩa rằng qua

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 12/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

q trình tiến hóa, chúng ta mong muốn những cá thể tốt với nhiều gen tốt sẽ được
giữ lại và lan tỏa ra quần thể.
3.4.

Crossover (Lai ghép)

Crossover nhắm lai ghép giữa hai cá thế. Cụ thể, hai cá thể có thể trao đổi gen với

nhau. Trong bài này, chúng ta sẽ dùng binary crossover để thực hiện việc lai tạo
giữa hai cá thể. Binary crossover hoạt động như sau: cho trước xác suất thực hiện
crossover cho một gen là Rcr=0.9, sinh ra một boolean vector vcr có độ dài n,
trong đó mỗi phần tử chứa giá trị True hoặc False. Giá trị True cho một vị trí index
nghĩa là thực hiện việc trao đổi gen ở vị trí đó giữa hai cá thể. Ví dụ
cho Rcr=0.9 nghĩa là việc trao đổi gen cho một vị trí giữa hai cá thể là 90% khả
năng. Hình sau minh họa việc trao đổi gen cho trước vector vcr.

3.5.

Mutation (Đột biến)

Mutation nhằm đột biến gen cho một cá thể. Gen cần đột biến sẽ nhận một giá trị
ngẫn nhiên nằm trong miền giá trị. Tương tự crossover, mutation cũng cần một
boolean vector vmt để xác định những gen nào cần đột biến. Vector vmt được sinh
ra một cách ngẫu nhiên theo một khả năng mutation Rmt cho trước. Hình sau minh
họa việc đột biến cho một cá thể dựa vào vector vmt cho trước.

Trong bài toàn này, điều kiện dừng khá là đơn giản, đó chính là số thế hệ xuất hiện
được cho trước.
GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 13/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT
3.6.

Môn học: Học Máy Nâng Cao


Đoạn code cho bài toán One-Max

import random
import matplotlib.pyplot as plt

n = 10

# Số lượng gen

m = 50

# Số lượng cá thể

n_generations = 100
fitnesses = []

# Số lượng cá thể cho trước

# Hàm mục tiêu

# tạo ra giá trị ngẫu nhiên
def generate_random_value():
return random.randint(0, 1)

# Tính tốn hàm mục tiêu
def compute_fitness(individual):
return sum(gen for gen in individual)

# Tạo một cá thể
def create_individual():

return [generate_random_value() for _ in range(n)]

population = [create_individual() for _ in range(m)]

#print (population)
for ind in population:

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 14/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

print(ind)

# Phép lai ghép
def crossover(individual1, individual2, crossover_rate = 0.9):
individual1_new = individual1.copy()
individual2_new = individual2.copy()
for i in range(n):
if random.random() < crossover_rate:
individual1_new[i] = individual2[i]
individual2_new[i] = individual1[i]
return individual1_new, individual2_new

# Phép đột biến
def mutate(individual, mutation_rate = 0.05):

individual_m = individual.copy()
for i in range(n):
if random.random() < mutation_rate:
individual_m[i] = generate_random_value()
return individual_m

# Phép chọn lọc
def selection(sorted_old_population):
index1 = random.randint(0, m-1)
while True:
index2 = random.randint(0, m-1)
if (index2 != index1):

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 15/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

break
individual_s = sorted_old_population[index1]
if index2 > index1:
individual_s = sorted_old_population[index2]
return individual_s

# Tạo quần thể mới sau mỗi bước lai ghép, đột biến
def create_new_population(old_population, elitism=2, gen=1):

sorted_population = sorted(old_population, key=compute_fitness)
if gen%1 == 0:
fitnesses.append(compute_fitness(sorted_population[m-1]))
print("BEST:", compute_fitness(sorted_population[m-1]))
new_population = []
while len(new_population) < m-elitism:

# Thêm bước chọn lọc lại cho quần thể mới
individual_s1 = selection(sorted_population)
individual_s2 = selection(sorted_population) # Trùng lặp

# Thêm bước lai ghép lại cho quần thể mới
individual_c1, individual_c2 = crossover(individual_s1, individual_s2)

# Thêm bước đột biến lại cho quần thể mới
individual_m1 = mutate(individual_c1)
individual_m2 = mutate(individual_c2)
new_population.append(individual_m1)

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 16/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

new_population.append(individual_m2)
for ind in sorted_population[m-elitism:]:

new_population.append(ind.copy())
print(old_population)
return new_population

population1 = [create_individual() for _ in range(m)]
for i in range(n_generations):
population1 = create_new_population(population1, 2, i)
for ind in population1:
print(ind)

# Sơ đồ kết quả cho một lần thử
plt.plot(fitnesses,'b')
plt.ylabel('Mục tiêu')
plt.xlabel('Thế hệ')
plt.ylim([0,11])
plt.show()

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 17/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao

BÀI TẬP
Bài tốn người du lịch (TSP)
TSP được mơ tả như sau: Một du khách muốn thăm những thành phố anh quan
tâm; mỗi thành phố thăm qua đúng một lần; rồi trở về điểm khởi hành. Biết trước

chi phí di chuyển giữa hai thành phố bất kỳ. Yêu cầu của bài tốn là xây dựng một
lộ trình thỏa các điều kiện trên với tổng chi phí nhỏ nhất.
Gợi ý
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 chúng ta 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 (cho max = 40), 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.

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 18/19


TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT

Môn học: Học Máy Nâng Cao


TÀI LIỆU THAM KHẢO
a/p/thuat-toan-di-truyen-ung-dung-giai-mot-so-bai-toan-kinh-dienphan-2-07LKXwYp5V4
/> /> />RUY%E1%BB%80N

GIẢI THUẬT DI TRUYỀN - GENETIC ALGORITHM (GA)

Trang 19/19