4
Nguyễn Thị Thanh Huyền – TH5A Bài tập lớn môn trí tuệ nhân tạo
BỘ MÔN KHOA HỌC MÁY TÍNH– KHOA CNTT
HỌC VIỆN KỸ THUẬT QUÂN SỰ
BÀI TẬP LỚN MÔN TRÍ TUỆ NHÂN TẠO
Đề bài: Xây dựng chương trình mô tả không gian trạng thái của toán chiếc
balô loại 2 giải quyết theo giải thuật Gene với phương pháp chọn Rank.
Sinh viên thực hiện: Nguyễn Thị Thanh Huyền
Lớp: Tin học 5A
Khóa 5
4
Nguyễn Thị Thanh Huyền – TH5A Bài tập lớn môn trí tuệ nhân tạo
Hà Nội, 2010
Giới thiệu
Trong ngành khoa học máy tính, tìm kiếm lời giải tối ưu cho các bài
toán là vấn đề được các nhà khoa học máy tính đặc biệt rất quan tâm.
Mục đích chính của các thuật toán tìm kiếm lời giải là tìm ra lời giải
tối ưu nhất cho bài toán trong thời gian nhỏ nhất. Các thuật toán như
tìm kiếm không có thông tin / vét cạn (tìm kiếm trên danh sách, trên
cây hoặc đồ thị) sử dụng phương pháp đơn giản nhất và trực quan nhất
hoặc các thuật toán tìm kiếm có thông tin sử dụng heurictics để áp
dụng các tri thức về cấu trúc của không gian tìm kiếm nhằm giảm thời
gian cần thiết cho việc tìm kiếm được sử dụng nhiều nhưng chỉ với
không gian tìm kiếm nhỏ và không hiệu quả khi tìm kiếm trong không
gian tìm kiếm lớn. Tuy nhiên, trong thực tiễn có rất nhiều bài toán tối
ưu với không gian tìm kiếm rất lớn cần phải giải quyết. Vì vậy, việc
đòi hỏi thuật giải chất lượng cao và sử dụng kỹ thuật trí tuệ nhân tạo
đặc biệt rất cần thiết khi giải quyết các 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
kỹ thuật 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 với logic

đạt đến tiêu chuẩn kết thúc
+ Đánh giá độ thích nghi của
mỗi cá thể trong P(i)
+ Lựa chọn các cha từ P(i) dựa
trên độ thích nghi của chúng trong P(i).
+ Áp dụng các toán tử Gen
(crossover, mutation) từ các cha đã
chọn để sinh ra các con
+ Đạt được thế hệ tiếp theo
P(i + 1) gồm các cá thể con và cha P(i)
2. Các thành phần cơ bản của Gas
a. Khởi tạo (Initializetion)
4
Nguyễn Thị Thanh Huyền – TH5A Bài tập lớn môn trí tuệ nhân tạo
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
b. 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 càng cao.
c. Lựa chọn để kết hợp lại (Selection For Recombine)
Có nhiều kiểu lựa chọn
+ roulette wheel selection
+ Boltzman selection
+ Tournament selection
+ rank selection
+ steady state selection
+ Elitism
d. Mã hóa
Mã hóa chuỗi gene của mỗi cá thể thành dạng thích hợp (nhị
phân, mã hóa giá trị, mã hóa hoán vị)

nhiên)
- Ấn định khối lượng tối đa của túi
* 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 bị quá tải.
Số lượng mỗi vật trong balô là một số ngẫu nhiên
trong khoảng từ 0 → KL balô/KL 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
Thứ tự Quá tải Không quá tải
Giá trị tăng dần Giá trị tăng dần
Rank 1 2 … maxRank
Tính tổng các rank
Xác định số cá thể con định tạo ra
4
Nguyễn Thị Thanh Huyền – TH5A Bài tập lớn môn trí tuệ nhân tạo
Lặp đến khi đủ số cá thể con
Lấy ngẫu nhiên 1 số thuộc khoảng (1; tổng Rank)
Cộng các Rank đến khi đc giá trị > giá trị ngẫu
nhiên
Xác định Gene được chọn và đưa vào mảng để lai
* Mã hóa:
Với các Gene được chọn để đem lai, mã hóa chúng
thành dạng chuỗi bằng phương pháp mã hóa giá trị
* Lai:
Phương pháp lai được chọn là lai 2 điểm.
Chuỗi gen được chia thành 3 phần, phần 1 có độ dài = ¼ chuỗi
gene, phần 2 có độ dài = ½ chuỗi gene, phần 3 là phần còn lại

Properties và Methods in class
Item
ItemWeight Khối lượng vật
ItemValue Giá trị vật
Knapsack
knapsackMaxWeight KL tối đa của túi
KnapsackCurrentWeight KL hiện tại của túi
KnapsackValue Giá trị hiện tại
Rank Rank trong quần thể
4
Nguyễn Thị Thanh Huyền – TH5A Bài tập lớn môn trí tuệ nhân tạo
ListItemAmount Mảng chứa sl mỗi vật
overload() Kiểm tra túi quá tải
showItem()
Hiển thị sl các vật dạng
string
GAs
KnapsackWeight KL tối đa của túi
knapsackAmount SL túi trong 1 thế hệ
mutationProp tỉ lệ đột biến
listItem dsách các đồ vật
listKnapsack
dsách các cá thể trong 1 thế
hệ
newListKnapsack danh sách cá thể cũ và mới
ksBestCurrent chiếc túi tốt nhất
maxValue giá trị của túi tốt nhất
goodGeneration thế hệ có túi tốt nhất
encodedListKnapsack mảng các gene đc mã hóa
initialize() khởi tạo quần thể