1
HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO MÔN HỌC
TRÍ TUỆ NHÂN TẠO
Giáo viên hướng dẫn: Ngô Hữu Phúc
HÀ NỘI 3/2010
Nguyễn Thị Ánh Hồng - Tin học 5A Giáo viên hướng dẫn: Ngô Hữu Phúc
2
Lời nói đầu
Em chân thành cảm ơn thầy giáo Ngô Hữu Phúc đã giảng dạy và hướng dẫn
môn học.
Do hạn chế về trình độ, nên bài tập còn nhiều thiếu sót, em mong thầy góp ý và chỉ
bảo thêm.

Nguyễn Thị Ánh Hồng - Tin học 5A Giáo viên hướng dẫn: Ngô Hữu Phúc
3
Mục lục
I. Khái quát
Chúng ta giả sử gene bước đầu tiếp cận cho giải thuật gene. Nó mạnh
hơn nếu được so sánh với cách tiếp cận truyền thống trong giải thuật gene.
Sự tiếp cận được ứng dụng cho bài toán 0/1 kapsack .Giải thuật này tìm ra
được kết quả cận tối ưu trong tất cả kết quả đặc biệt được biểu diễn trong tài
liệu này, trong khi các cách tiếp cận truyền thống thất bại phần lớn các ví dụ
bởi những đặc điểm lợi thế riêng biệt của các cá thể trong quần thể. Trong sự
kết hợp giữa toán tử tìm kiếm đột biến , phương pháp này cung cấp một kết
quả tốt hơn cho tất cả các vấn đề của các thực thể đã được nghiên cứu.
1. Giới thiệu Genetic Algorithms (GAs)
Nguyễn Thị Ánh Hồng - Tin học 5A Giáo viên hướng dẫn: Ngô Hữu Phúc
4
Giải thuật Gene (GAs) cơ bản dựa trên thuyết chọn lọc tự nhiên

• Áp dụng GAs đệ quy để tiếp cận với cách giải quyết 0/1
knapsack
Nguyễn Thị Ánh Hồng - Tin học 5A Giáo viên hướng dẫn: Ngô Hữu Phúc
5
Vấn đề bài toán 0/1 knapsack được xác định như sau
Đưa ra vector giá trị : P
i
Vector khối nượng : w
i
Giá trị cực đại : ∑
n
i=1
p
i
x
i

Số vật thể phải thỏa mãn điều kiện : ∑
n
i=1
w
i
x
i ≤ C
x
i
nhận giá trị 0 hoặc 1 ,( i= 1,… ,n) n là số các phần tử
0 : đồ vật ( nhiễm sắc thể ) không được chọn .
1 : đồ vật ( nhiễm sắc thể ) được chọn .
Số thứ tự đồ vật được tính từ trái sang phải .

*Hàm thích nghi xây dựng dựa trên phép toán tính tổng giá trị
và khối lượng để xác đình cá thể tốt.
*Ngưỡng để so sánh thử nghiệm là :
- Giá trị của cá thể : ∑
n
i=1
p
i
x
i
≥ 22
-Khối lượng cá thể : ∑
n
i=1
w
i
x
i
≤ 20
4. Sự lựa chọn cho sự kết hợp lại (selection for recombination)
Có rất nhiều thuật toán để lựa chọn cá thể để tham gia
vào quá trình lai ghép ( crossover ) và đột biến (mutation). Ví
dụ như :Roulette wheel selection, rank selection , Elitism,
Steady-state, v.v.v.
Bài tập này đi sâu vào thuật toán lựa chọn : Steady-state.
Thuật toán được mô tả như sau
Steady-state selection
Với giải thuật gene steady-state,mỗi lần một thành viên của
quần thể bị thay đổi. Lựa chọn một cá thể của quần thể phải dựa trên
hàm thích nghi ( fitness).Nó được sao chép và những bản sao biến

Lai ghép có thể có rất nhiều cách. Cụ thể trong có
3 cách được áp dụng để giải quyết bài toán :
i. Lai ghép một điểm
Xem xét ví dụ sau
parent 1 1 0 0 | 0 1 1 1
Parent 2 1 1 1 1| 0 0 0
Offspring1 1 0 0 1 0 0 0
Offspring2 11 1 1 1 1 1
Trong ví trên điểm lai ghép là ở vị trí thứ 3 ( tính từ trái sang )
của 2 cá thể cha mẹ. Cá thể con thứ kế thừa nhiễm sắc thể ở vị trí 1
,2 và 3 từ cá thể parent1 , và các nhiễm sắc thể ở vì trí 4, 5, 6 và 7
của cá thể parent2. Đối với cá thể con thứ 2 nhận các nhiễm sắc thể
1, 2, 3 từ cá thể parent2 còn các nhiễm sắc thể 4, 5, 6, và 7 thì kế
thừa ở cả thể parent1.
ii. Lai ghép 2 điểm
Nguyễn Thị Ánh Hồng - Tin học 5A Giáo viên hướng dẫn: Ngô Hữu Phúc
8
parent 1 1 0 0 | 0 1 | 1 1
Parent 2 1 1 1 | 1 0 | 0 0
Offspring1 1 0 0 1 0 0 0
Offspring2 111 0 1 1 1
Trong ví trên điểm lai ghép là ở vị trí thứ 3 và thứ 5 ( tính từ
trái sang ) của 2 cá thể cha mẹ.
+ Cá thể con thứ kế thừa nhiễm sắc thể ở vị trí 1 ,2, 3 và 6,7 từ
cá thể parent1 , còn các nhiễm sắc thể ở vị trí 4, 5 của cá thể
parent2.
+Đối với cá thể con thứ 2 nhận các nhiễm sắc thể 1, 2, 3 và 6,7
từ cá thể parent2 còn các nhiễm sắc thể 4, 5, thì kế thừa ở cả thể
parent1.
iii. Tính toán ngẫu nhiên điểm lai ghép

gen, cái thường thực hiện chỉ trên mã hóa nhị phân.
 Ưu điểm
• Chính là khả năng song song của thuật toán .
• GAs duyệt qua không gian tìm kiếm sử dụng nhiều cá thể (and
with genotype rather than phenotype) và ít mắc phải cực trị địa
phương như các thuật toán khác
• Dễ thể hiện .
• Khi đã có thuật toán gen cơ bản, chỉ cần viết một NST mới (just
one object) để xử lý bài toán khác.
• Với cùng cách mã hóa bạn có thể thay đổi hàm thích nghi .
• Mặc dù vậy, trong một số trường hợp chọn và thể hiện mã hóa
sẽ gặp khó khăn.
 Nhược điểm
• Nhược điểm chính của Gas là thới gian tính toán
• GAs có thể chậm hơn các thuật toán khác
• Có thể kết thúc tính toán bất cứ lúc nào
b) Nhận xét về hàm lựa chọn steady-state :
Trong quá trình lựa chọn, thuật toán chỉ lựa chọn những cá thể có độ
thích nghi cao để tạo ra quần thể mới. Xong trên thực tế đây không phải
là sự lựa chọn đúng đắn, bởi trong nhiều trường hợp sự lai ghép 1 cá thể
Nguyễn Thị Ánh Hồng - Tin học 5A Giáo viên hướng dẫn: Ngô Hữu Phúc
10
tồi với 1 cá thể có đặc tính gene cao lại tạo nên một cá thể con có độ
thích nghi cao hơn cả .Và cũng không loại trừ trương hợp : sự kết hợp
của 2 gene tốt là cho ra một cá thể chứa toàn bộ nhiễm sắc thể lặn và hình
thành nên cá thể có độ thích nghi thấp.
IV. Flowchart của chương trình chính :
Nguyễn Thị Ánh Hồng - Tin học 5A Giáo viên hướng dẫn: Ngô Hữu Phúc
11
Nguyễn Thị Ánh Hồng - Tin học 5A Giáo viên hướng dẫn: Ngô Hữu Phúc