Chương 4-2
Các phương pháp tìm kiếm
có sử dụng thông tin
Biên soạn: TS Ngô Hữu Phúc
Bộ môn Khoa học máy tính
ĐT: 098 56 96 580
eMail: ngohuuphuc76@gmail.com
Chương 4-2: Giải thuật Gene
1
Nhập môn Trí tuệ nhân tạo
Nội dung
Chương 4-2: Giải thuật Gene
2
Thuật toán Gen
Các thành phần cơ bản của thuật toán gen
Các khuyến cáo khi sử dụng thuật toán gen
Ưu và nhược điểm của thuật toán gen
10.4.1. Thuật Toán Gene (GAs)
Chương 4-2: Giải thuật Gene
3
GAs (John Holland, 1975)mô phỏng tiến hóa tự nhiên
(Darwinian Evolution) ở mức gen sử dụng tư tưởng của
chọn lọc tự nhiên (survival of the fittest)
Một cá thể (nhiễm sắc thể) (chromosome) mô tả một lời giải
ứng viên của bài toán.
Một tập các cá thể “alive”, gọi là quần thể (population) được
tiến hóa từ thế hệ này tới thế hệ khác phụ thuộc vào sự thích
nghi của các cá thể.
Kỳ vọng (Hope): Thế hệ mới sinh ra sẽ chứa lời giải tốt của
bài toán.
10.4.2. Mô tả thuật toán Gene
Chương 4-2: Giải thuật Gene
4
Ban đầu, sinh ra thế hệ khởi tạo với quần thể 𝐏(𝟎),chỉ số ichỉ ra thế hệ
thứ i.
Lặp cho đến khi quần thể hội tụ hoặc tiêu chuẩn kết thúc đạt được.
Đánh giá độ thích nghi của mỗi cá thể trong 𝐏(𝐢).
Lựa chọn các cha từ 𝐏(𝐢) dựa trên độ thích nghi của chúng trong
𝐏(𝐢).
Áp dụng các toán tử Gen (crossover, mutation) từ các cha đã chọn để
sinh ra các con (offspring)
Đạt được thế hệ tiếp theo 𝐏(𝐢 + 𝟏) từ các con và các cá thể ở thế hệ
𝐏(𝐢)
10.4.3. Cài đặt GA
Chương 4-2: Giải thuật Gene
5
Procedure GA
begin
t := 0 ;
initialize P(t) ;
evaluate P(t) ;
while (not termination-condition) do
begin
t := t + 1 ;
select P(t) from P(t-1) ;
alter P(t) ;
evaluate P(t) ;
end;
end;
Step 1 : Initialization
Step 2 : Selection
Step 3-1 : Crossover
Step 3-2 : Mutation
Step 5 : Termination Test
Step 6 : End
Step 4 : Evaluation