HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP LỚN MÔN HỌC
TRÍ TUỆ NHÂN TẠO Đề Tài
Nghiên Cứu Giải Thuật GA
Giải Bài Toán Chiếc Balô Loại 2



LỜI CẢM ƠN
Trước hết, cho em gửi lời cảm ơn chân thành nhất đến
TS NGÔ HỮU PHÚC - Giảng viên Bộ môn Khoa Học Máy Tính. Người đã
giảng dạy và truyền đạt chúng em kiến thức về môn học đồng thời là người
hướng dẫn và định hướng cho em trong quá trình hoàn thiện Bài tập này.
Em đã cố gắng thật nhiều để hoàn thành Bài tập. Tuy nhiên, kết quả tìm
hiểu chưa hoàn thiện còn nhiều thiếu sót. Rất mong Thầy xem xét và đ
óng góp ý
kiến để kết quả tìm hiểu được hoàn thiện hơn./.
Học Viên Thực Hiện
Giảng Thanh Trọn
NỘI DUNG TÌM HIỂU
Nội dung nghiên cứu của Bài Tập bao gồm những thành phần sau:
1. Giới Thiệu Bài Toán Chiếc Ba Lô Loại 2.

nhân tạo vào giải quyết bài toán là rất cần thiết đặc biệt với những bài toán có
không gian tìm kiếm lớn. Thuật giải di truyền - Genetic Algorithm là một trong
những thuật giải tìm kiếm lời giải tối
ưu đã đáp ứng được yêu cầu của nhiều bài
toán và ứng dụng. Hiện nay, thuật toán di truyền được ứng dụng rất rộng rãi
trong các lĩnh vực phức tạp, nó chứng tỏ được hiệu quả trong các vấn đề khó có
thể giải quyết bằng các phương pháp thông thường hay các phương pháp cổ
điển, nhất là trong các bài toán cần có sự lượng giá, đánh giá sự tối ưu của
kế
t quả thu được. Chính vì vậy, thuật giải di truyền đã trở thành đề tài
nghiên cứu thú vị và đem đến nhiều ứng dụng trong thực tế.
Trong khuôn khổ của đề tài này, em xin trình bày nội dung của giải thuật di
truyền - Genetic Algorithm và ứng dụng của nó trong việc giải quyết bài toán
Chiếc ba lô loại 2 với phương pháp lựa chọn.
2. Tìm Hiểu Giải thuật Di Truyền Genetic Algorithm - GA
2.1. Khái quát về giải thuật Di Truyền
Lịch sử ra đời của giải thuật di truyền
Trước tiên, ý niệm về giải thuật di truyền đã được một số nhà sinh vật
học đưa ra từ những năm 50-60, thế kỉ XX. A.S. Fraser là người tiên phong
nêu lên sự tương đồng giữa sự tiến hóa của sinh vật và chương trình tin học
giả tưởng về Genetic Algorithms – viết tắc là GA.
Tuy nhiên, chính John Henry Holland mới là người triển khai ý tưởng
và phương pháp giải quy
ết vấn đề dựa theo sự tiến hóa. Từ những
bài giảng, bài báo của mình, ông đã đúc kết các ý tưởng vào trong
cuốn sách đầu tay Adaptation in Natural and Artificial Systems, xuất bản
năm 1975. Dựa trên lý thuyết cơ bản về GA của Holand, Keneth De Jong
đã triển khai và chứng minh những thành quả do ông thực hiện đã góp phần
quan trọng trong việc tạo ra nền tảng toán học cho lý thuyết GA


Quá trình được thực hiện bằng cách tạo ngẫu nhiên một số cá thể
chấp nhận được để được một quần thể phù hợp với kích thước
quần thể được quy định sẵn. 2. Hàm thích nghi - Fitness Function
Gán giá trị thích nghi cho mỗi cá thể. Giá trị thích nghi càng sát
với thực tế thì độ chính xác sẽ càng cao.
3. Lựa chọn để kết hợp lại - Selection For Recombine
Có nhiều phương pháp để chọn các nhiễm sắc thể tốt nhất, như:
chọn lọc roulette wheel, chọn lọc xếp hàng, chọn lọc cạnh tranh:
 Roulette wheel selection
Các cá thể cha mẹ được chọn theo độ thích nghi của chúng.
Nhiễm sắc thể tốt h
ơn có cơ hội cao hơn để tham dự vào thế hệ
tiếp theo.
Thuật giải chọn lọc roulette của Davis, như sau:
Tính tổng giá trị thích nghi của tất cả thành viên quần thể và
gọi nó là tổng thích nghi - total fitness.
Phát sinh một số n là số ngẫu nhiên trong khoảng từ 0 đến
tổng thích nghi.
Trả lại thành viên quần thể đầu tiên mà độ thích nghi của nó
cộng với độ thích nghi của các thành viên quần thể trước đ
ó lớn
hơn hay bằng n…
 Tournament selection
Chọn lọc cạnh tranh 2 – 2 - tournament selection
Hai nhiễm sắc thể khác nhau được chọn ngẫu nhiên và được
so sánh với nhiễm sắc thể tồn tại. Nếu nhiễm sắc thể I1 không tốt
hơn nhiễm sắc thể I2 nghĩa là: f(I1) ≤ f(I2), thì nhiễm sắc thể I1

giá trị của 1 đoạn gene nào đó.
7. Đánh giá cá thể
Khi đã có quần thể mới, ta tiến hành kiểm tra đánh giá xem
cá thể nào tốt nhất, cá thể nào tồi. Loạ
i bỏ bớt những cá thể tồi để
lặp lại các bước trên đó Chắc chắn rằng việc chọn cá thể sẽ thông qua
kết quả, hay mục đích của vấn đề. Các cá thể tốt được chọn lọc để đưa vào thế hệ sau. Sự lựa chọn này được thực hiện dựa vào độ thích
nghi với môi trường của mỗi cá thể.
8. Tiêu chuẩn kết thúc
Không có quá trình nào là không thể kết thúc. Quá trình tiến hóa
có thể dừng lại sau một khoảng tgian được quy định - một số thế hệ
hoặc sau khi đã hội tụ - không thể tìm thêm được cá thể tốt hơn.
Thoát khỏi quá trình tiến hóa quần thể, dựa vào bài toán
mà có các cách kết thúc v
ấn đề khác nhau một khi đạt đến mức
yêu cầu. Một vài trường hợp thông thường như sau:
 Kết thúc theo kết quả: một khi đạt đến mức giá trị yêu cầu thì
chấm dứt ngay quá trình thực hiện.
 Kết thúc dựa vào số thế hệ: chọn số thế hệ, quá trình sẽ dừng
đúng ngay số thế hệ đã qui định trước, không cần biết kết quả

như thế nào.
 Tính theo thời gian: không cần biết đã bao nhiêu thế hệ hay
kết quả nào, chỉ dựa vào số giờ qui định mà kết thúc.
 Tổ hợp: dùng nhiều phương án khác nhau cho vấn đề, chẳng hạn
như: chạy theo số thế hệ xong sau đó đánh giá cho chạy theo
kết quả, hoặc ngược lại.

Chọn hai vị trí ngẫu nhiên trong một nhiễm sắc thể và sau
đó, nghịch đảo chuỗi giữa hai vị trí này.
Ví dụ:
Nhi
ễm sắc thể : 9 3 8 5 7 1 6 4 2
Sau khi đột biến : 9 3 1 7 5 8 6 4 2
Đột biến chèn - Insertion Mutation Chọn ngẫu nhiên một gen và sau đó chèn nó vào vị trí
ngẫu nhiên.
Ví dụ:
Nhiễm sắc thể : 9 3 8 5 7 1 6 4 2
Sau đột biến: 9 3 5 7 8 1 6 4 2
Đột biến thay thế - Displacement Mutation
Chọn ngẫu nhiên một chuỗi con và chèn nó vào một vị trí
ngẫu nhiên. Đột biến chèn có thể được xem như trường hợp đặc
biệt của đột biến thay, trong đó, chuỗi con chỉ chứa một gen.
Ví dụ:
Nhiễm sắc thể: 9 3 8 5 7 1 6 4 2
Sau đột biến: 9 3 6 8 5 7 1 4 2
Đột biến tương hỗ - Reciprocal Exchange Mutation
Chọn ngẫu nhiên hai vị trí và sau đó hoán vị gen trên những
vị trí này.
Ví dụ:
Nhiễm sắc thể: 9 3 8 5 7 1 6 4 2
Sau đột biến: 9 3 1 5 7 8 6 4 2
Đột biến chuyển dịch - Shift Mutation
Trước tiên, chọn ngẫu nhiên một gen, sau đó, dịch chuyển
nó đến một vị trí ngẫu nhiên bên phải hoặc bên trái vị trí của gen.

Step 1 : Initialization
Step 2 : Selection
Step 3-1 : Crossover
Step 3-2 : Mutation
Step 5 : Termination Test
Step 6 : End
Step 4 : Evaluation
3. Ứng dụng giải thuật Di Truyền vào Bài toán chiếc Ba lô 2
Ta có thể hình dung mô hình bài toán được giải quyết trong giải thuật di
truyền như sau: Gồm một quần thể chứa tất cả các kết quả có thể có được của
bài toán, rồi từ đó chọn ra kết quả tốt nhất.

Các bước thực hiện:
 Khởi tạo đồ vật và trọng lượng tối đa ba lô:
 Tạo ra x đồ vật với khối lượng và giá trị khác nhau (ngẫu nhiên).
 Ấn định khối lượng tối đa của ba lô.
 Khởi tạo quần thể:
 Tạo ra n chiếc ba lô, mỗi ba lô chứa số lượng các vật là khác
nhau, không ba lô nào vượt quá khối lượng tối đa củ
a ba lô.
 Số lượng mỗi vật trong balô là một số ngẫu nhiên trong khoảng
từ 0 đến thương số khối lượng của balô với khối lượng của vật.
 Tìm balô tốt nhất.
 Lựa chọn:
 Xếp các balô từ thế hệ trước theo thứ tự và được xếp rank.
Quá tải Không quá tải
Thứ tự

định nên phải đánh giá để chọn ra
n cá thể tốt cho thế hệ kế tiếp.
 Lặp lại các bước trên đến khi quần thể hội tụ hoặc sau k thế hệ.
Kết Luận:
Tuy giải thuật Genetic Algorithm - GA có thể chậm hơn một số thuật
toán khác, song GA lại có các ưu điểm nổi trội như: Dễ thể hiện, không bị
rơi vào trạng thái cực trị
địa phương, dễ thay đổi hàm thích nghi, … Vì
vậy, thuật toán Genetic Algorithm là một lựa chọn thích hợp cho dạng bài
toán quyết định. Ví dụ như bài toán tìm đường, bài toán chiếc balô.
4. Cài Đặt Ứng Dụng.