Nguyễn Như Nam.
Lớp :Tin 5A Báo cáo : Nhập môn trí tuệ nhân tạo


******************
 !"#$%&'
(#)
* Không gian trạng thái được mô tả là bài toán n-
queens. Hãy xây dựng chương trình giải quyết bài toán theo
giải thuật gene với phương pháp chọn là Elitism.
Giảng viên hướng dẫn*+",&

Người thực hiện *+&/0#123
Lớp *#4.56

Nguyễn Như Nam.
Lớp :Tin 5A Báo cáo : Nhập môn trí tuệ nhân tạo
Hà Nội- 2010
Mở Đầu
7.+83.. 9#*
1. Giải thuật Gene với phương pháp chọn Elitism.
2. Ý tưởng của bài toán N-queens.
3. Mô tả thuật toán.
4. Chương trình DEMO
5. Chương trình được viết bằng:
+Ngôn ngữ:C-sharp.
+Trình biên dịch: Microsoft Visual Studio 2005.
+Nền tảng.net frame work 3.5
Nguyễn Như Nam.
Lớp :Tin 5A Báo cáo : Nhập môn trí tuệ nhân tạo
:;<=&=>#>?@ 1A#+  .4#BC=D3:

chọn là Elitism.
• Ý tưởng: Ta tiến hành xếp N hậu lên các vị trí bất kì ứng với mỗi
trạng thái của bàn cờ ta mã hóa chúng thành các gen (gọi là các mảng 1 chiều)
cho các gen đó lai ghép vói nhau để tạo ra các gen mới kiểm tra trong số các
gen của chúng ta xem có gen nào là trạng thái kết thúc chưa(trạng thái chứa lời
giải) nếu có thì dừng vòng lặp, nếu chưa thì cho lai ghép tiếp. Trong quá trình
kiểm tra trong số các gen của chúng ta sử dụng phương pháp chọn Elitism để
cop các cá thể tốt phù hợp với yêu cầu đó là số lượng các quân hậu ăn nhau là
ít nhất.
M;!"=<=&==#*
Từ thế hệ ban đầu được tạo ra bằng phương pháp mã hóa nhị phân, thuật
toán gene bắt chước chọn lọc tự nhiên và di truyền để biến đổi các thế hệ. Cấu
trúc cơ bản của thuật toán là như sau:
procedure Genetic_Algorithm;
begin
t
←
0N
Khởi tạo thế hệ ban đầu P(t)N
Đánh giá P(t) (theo hàm thích nghi)N
repeat
t
←
t + 1;
Nguyễn Như Nam.
Lớp :Tin 5A Báo cáo : Nhập môn trí tuệ nhân tạo
Sinh ra thế hệ mới P(t) từ P(t-1) bởi
-Chọn lọc
-Lai ghép
Đánh giá P(t);

phương pháp chọn Elitism. Sau khi so sánh các cá thể với hàm thích nghi ta sẽ
có được các cá thể tốt nhất trong một quần thể, sau đó ta sẽ xây dựng hàm
Nguyễn Như Nam.
Lớp :Tin 5A Báo cáo : Nhập môn trí tuệ nhân tạo
Elitism để copy các cá thể tốt để từ đó tạo các quần thể tạo thành một quần thể
mới (có phương pháp sắp xếp các quân hậu một cách tốt nhất trên bàn cờ).
d) Trên cơ sở cấu trúc của nhiễm sắc thể, thiết kế các toán tử di truyền
(lai ghép, đột biến) cho phù hợp với các vấn đề cần giải quyết.
e) Xác định cỡ của quần thể và khởi tạo quần thể ban đầu.
f) Xác định xác suất lai ghép pc và xác suất đột biến. Xác suất đột biến
cần là xác suất thấp. Người ta (Goldberg, 1989) khuyên rằng nên chọn xác suất
lai ghép là 0,6 và xác suất đột biến là 0,03. Tuy nhiên cần qua thử nghiệm để tìm
ra các xác suất thích hợp cho vấn đề cần giải quyết.
g) Thuật toán dừng khi quần thể hội tụ, i.e. cá thể tốt nhất trong quần thể
giống với kết quả mong muốn. Kết thúc khi số thế hệ sinh ra đạt đến số sinh ra
trước. Kết thúc khi các cả thể trở lên giống nhau. Kết thúc khi cá thể tốt nhất
trong quần thể không thay đổi theo thời gian.
=> Trong thủ tục trên, điều kiện kết thúc vòng lặp có thể là một số thế hệ đủ
lớn nào đó, hoặc độ thích nghi của các cá thể tốt nhất trong các thế hệ kế tiếp
nhau khác nhau không đáng kể. Khi thuật toán dừng, cá thể tốt nhất trong thế hệ
cuối cùng được chọn làm nghiệm cần tìm.
O;1A#+=$P#QB!R*
2E2S'#*
Nguyễn Như Nam.
Lớp :Tin 5A Báo cáo : Nhập môn trí tuệ nhân tạo
Giao diện chương trình gồm 3 phần:
 Khu vực bàn cờ và khu vực thể hiện kết quả lai ghép.
 Kết quả lai ghép: kết quả mã hóa, Số quân hậu ăn nhau,quần thể mới
 Các nút chức năng: Giới thiệu, khởi tạo quần thể (innitial population
generation),Value(số quân hậu ăn nhau), Elitism Gene(quần thể mới, kết

Lớp :Tin 5A Báo cáo : Nhập môn trí tuệ nhân tạo
7E.3[WC\*
* Class Taomang:
class taomang
{
public int[] arrqueens;
public taomang(int N)
{
arrqueens = new int[N];
for (int i = 0; i < N; i++)
{
arrqueens[i] = i;
}
}
public taomang(int[] arr)
{
arrqueens = new int[arr.Length];
arr.CopyTo(arrqueens, 0);
}

}
Hàm tạo giao diện bàn cờ:
Graphics g;
Bitmap bm;
Pen p;
float W, H;
Random r;
//cac bien dung cho thuat toan
int N;
public gene(int n)

for (int i = 0; i < N; i++)
{
st.arrqueens[i] = r.Next(0, N);

}
}
else
str += tmp.ToString();
}
return str;
}