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
I. Thuật toán di truyền.
Thuật toán di truyền (TTDT) là thuật toán bắt chước sự chọn lọc tự nhiên và di truyền. Trong tự
nhiên, các cá thể khỏe, có khả năng thích nghi tốt với môi trường sẽ được tái sinh và nhân bản ở
các thế hệ sau. Mỗi cá thể có cấu trúc gien đặc trưng cho phẩm chất của cá thể đó. Trong quá
trình sinh sản, các cá thể con có thể thừa hưởng các phẩm chất của cả cha và mẹ, cấu trúc gien
của nó mang một phần cấu trúc gien của cha và mẹ. Ngoài ra, trong quá trình tiến hóa, có thể xảy
ra hiện tượng đột biến, cấu trúc gien của cá thể con có thể chứa các gien mà cả cha và mẹ đều
không có.
Trong TTDT, mỗi cá thể được mã hóa bởi một cấu trúc dữ liệu mô tả cấu trúc gien của cá thể đó,
ta sẽ gọi nó là nhiễm sắc thể (chroniosome). Mỗi nhiễm sắc thể được tạo thành từ các đơn vị
được gọi là gien. Chẳng hạn, trong các TTDT cổ điển, các nhiễm sắc thể là các chuỗi nhị phân,
tức là mỗi cá thể được biểu diễn bởi một chuỗi nhị phân.
TTDT sẽ làm việc trên các quần thể gồm nhiều cá thể. Một quần thể ứng với một giai đoạn phát
triển sẽ được gọi là một thế hệ. Từ thế hệ ban đầu được tạo ra, TTDT bắt chước chọn lọc tự
nhiên và di truyền để biến đổi các thế hệ. TTDT sử dụng các toán tử cơ bản sau đây để biến đổi
các thế hệ.
• Toán tử tái sinh (reproduction) (còn được gọi là toán tử chọn lọc (selection)). 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ể. Ta sẽ gọi hàm ứng mỗi cá thể với độ thích nghi của nó là hàm
thích nghi (fitness function).
• Toán tử lai ghép (crossover). Hai cá thể cha và mẹ trao đổi các gien để tạo ra hai cá thể
con.
• Toán tử đột biến (mutation). Một cá thể thay đổi một số gien để tạo thành cá thể mới.
Tất cả các toán tử trên khi thực hiện đều mang tính ngẫu nhiên.
**Các bước cơ bản của giải thuật di truyền:

Dễ giao phối. (mating)
Biểu diễn nhiễm sắc thể với 1 số ít gen.
*Khuyết điểm:
Không thể giới hạn các thay đổi dễ dàng.
Tiến hành hiệu chỉnh sau khi mate.
VD: A: 0101101100010011
B: 1011010110110101
 Mã hóa hoán vị
Nhiễm sắc thể là 1 chuỗi số thực, được biểu diễn theo thứ tự.
*Ưu điểm: hữu dụng cho các vấn đề thứ tự.
*Khuyết điểm: có thể phải hiệu chỉnh sau khi mate.
VD: A:8549102367
B: 9102438576
 Mã hóa giá trị
Mỗi nhiễm sắc thể là chuỗi giá trị.
Giá trị là bất cứ thứ gì liên quan đến vấn đề như: số, ký tự, đối tượng…
VD:
A: [red], [black], [blue], [yellow], [red], [green]
B: 1.8765, 3.9821, 9.1283, 6.8344, 4.116, 2.192
C: ABCKDEIFGHNWLSWWEKPOIKNGVCI
 Mã hóa cây
Được dùng chủ yếu để rút ra các biểu thức chương trình
*Ưu điểm: biểu diễn không gian tìm kiếm không giới hạn (open-ended)
*Khuyết điểm: xảy ra lỗi tiềm tàng,phát triển theo hướng không thể kiểm soát, khi phát
triển lớn thì rất khó hiểu và không để đơn giản hóa
2. Chọn lọc: Việc chọn lọc các cá thể từ một quần thể dựa trên độ thích nghi của mỗi cá thể. Các
cá thể có độ thích nghi cao có nhiều khả năng được chọn. Cần nhấn mạnh rằng, hàm thích nghi
chỉ cần là một hàm thực dương, nó có thể không tuyến tính, không liên tục, không khả vi. Quá
trình chọn lọc được thực hiện theo kỹ thuật quay bánh xe.
Giả sử thế hệ hiện thời P(t) gồm có n cá thể {x

c
thì cá thể đó được chọn để lai ghép
Từ các cá thể được chọn để lai ghép, người ta cặp đôi chúng một cách ngẫu nhiên.Trong
trường hợp các nhiễm sắc thể là các chuỗi nhị phân có độ dài cố định m, ta có thể thực
hiện lai ghép như sau: với mỗi cặp,sinh ra một số nguyên ngẫu nhiên p trên đoạn [0,m-1],
p là vị trí điểm ghép. Cặp gồm 2 nhiễm sắc thể:
∑
=
=
n
1i
f(xi)F
∑
=
≥
k
i
xif
1
4)(
a = (a
1,
, a
p,
a
p+1,
, a
m
)
a = (b

m
. Xác suất đột biến p
m
do ta xác định và là xác suất thấp. Sau đây là toán tử đột biến trên các
nhiễm sắc thể chuỗi nhị phân.
Với mỗi vị trí i trong nhiễm sắc thể:
a = (a
1,
, a
i,
, a
m
)
Ta sinh ra một số thực nghiệm ngẫu nhiên p
i
trong [0,1]. Qua đột biến a được biến thành a’ như
sau:
a' = (a'
1,
, a'
i,
, a'
m
)
Trong đó:
a'
i
= a
i
nếu p

kết thúc.
Dựa trên ý nghĩa đặc biệt của 1 nhiễm sắc thể: đo tiến bộ của giải thuật trong một số
thế hệ cho trước.Nếu tiến bộ này nhỏ hơn một hằng số ɛ xác định,kết thúc tìm kiếm.
II Chương trình.
1. Class Knapsack.
*Properties:
+ knapsackMaxWeight: khối lượng tối đa của balô.
+ knapsackCurrentWeight: khối lượng hiện thời của balô.
+ knapsackValue: giá trị của balô.
+ fitness: chỉ số Fitness
*Method:
+ Overload: để kiểm tra xem khối lượng hiện tại của túi đã vượt quá khối lượng
max chưa.
+ ShowItem: in số lượng các đồ vật trong túi dưới dạng gene.
public class Knapsack
{
private int knapsackMaxWeight, knapsackCurrentWeight = 0, knapsackValue = 0, fitness;
private Item[] listItem = null;
public int[] listItemAmount;
public string strItems = "";
public int Fitness
{
get { return fitness; }
}

public int KnapsackCurrentWeight
{
get { return knapsackCurrentWeight; }
}
public int KnapsackValue

{
fitness = knapsackValue - knapsackCurrentWeight;
}
}
public Boolean overload()
{
if (knapsackCurrentWeight > knapsackMaxWeight) return true;
else return false;
}
public string showItem()
{
string s = "";
int i;
for (i = 0; i < listItemAmount.Length - 1; i++)
s += listItemAmount[i] + ", ";
s += listItemAmount[i].ToString();
return s;
}
}
2.Class Item.
*Properties
itemValue: giá trị của đồ vật.
itemWeight: khối lượng của đồ vật.
itemAmount: số lượng đồ vật.

public class Item
{
private int itemValue, itemWeight, itemAmount;
public int ItemWeight
{

public Knapsack ksBestCurrent;
//constructor
public GAs(int knapsackWeight, int knapsackAmount, Item[] listItem, int mutationProp, int
TotalGeneration)
{
this.knapsackWeight = knapsackWeight;
this.knapsackAmount = knapsackAmount;
this.mutationProp = mutationProp;
this.listItem = listItem;
rand = new Random();
initialize();
selectionForNewGeneration(listKnapsack);
}
//method
private void initialize()
{
// Thế hệ đầu tiên: tất cả các gene đều được chấp nhận
int i = 0;
listKnapsack = new Knapsack[knapsackAmount];
Knapsack knapsack;
while (i < knapsackAmount)
{
Item[] newList = listItem;
foreach (Item item in newList)
{
item.ItemAmount = rand.Next(0, Convert.ToInt32(knapsackWeight /
(item.ItemWeight)));
}
knapsack = new Knapsack(knapsackWeight, newList);
if ((!knapsack.overload()) && (knapsack.KnapsackValue > 0))

}
}
}
int count = 0;
while (count < knapsackAmount)
{
listKnapsack[count++] = oldListKnapsack[oldListKnapsack.Length - 1 -
knapsackAmount + count];
}
}

public Knapsack[] selectionForRecombination()
{
int fitnessTotal = 0, i = 0, times;
foreach (Knapsack knapsack in listKnapsack)
{
if (knapsack != null)
fitnessTotal += knapsack.Fitness;
}
times = rand.Next(knapsackAmount - 10, knapsackAmount + 10);
if (times < 0) times = knapsackAmount;
if (times % 2 != 0) times += 1;
Knapsack[] selectedKnapsacks = new Knapsack[times];
while (i < times)
{
int randNumber = rand.Next(1, fitnessTotal);
int currentTotal = 0, pos = 0;
while (currentTotal <= randNumber)
{
currentTotal += listKnapsack[pos++].Fitness;

{
for (int j = 0; j < encodedListKnapsack.GetLength(1); j++)
{
if (j < startPart2)
{
encodedNewGeneration[i, j] = encodedListKnapsack[i, j];
encodedNewGeneration[i + 1, j] = encodedListKnapsack[i + 1, j];
}
else if (j < startPart3)
{
encodedNewGeneration[i, j] = encodedListKnapsack[i + 1, j];
encodedNewGeneration[i + 1, j] = encodedListKnapsack[i, j];
}
else
{
encodedNewGeneration[i, j] = encodedListKnapsack[i, j];
encodedNewGeneration[i + 1, j] = encodedListKnapsack[i + 1, j];
}
}
}

return encodedNewGeneration;
}
public int[,] mutation(int[,] crossoverListKnapsack)
{
Random rand = new Random();
int times = mutationProp * crossoverListKnapsack.GetLength(0) / 100;
for (int i = 0; i < times; i++)
{
int chooseInvidiual = rand.Next(0, crossoverListKnapsack.GetLength(0) - 1);

{
newListKnapsack[i++] = listKnapsack[j++];
}
return newListKnapsack;
}
public void gene(Knapsack[] oldListKnapsack, int times)
{
while (times > 0)
{
selectionForNewGeneration(oldListKnapsack);
times ;
gene(evaluation(mutation(crossover(encoding(selectionForRecombination())))), times);
}
}
III.Kết quá thu được từ chương trình.
Đồ án này chỉ giới hạn trong việc minh họa cho thuật toán Gene với phương pháp chọn bánh xe
Roulette cho bài toán balo2, chứ chưa hướng tới việc áp dụng trong thực tế.
Để áp dụng cho thực tế thì sẽ cần nhiều thời gian và quá trình tìm hiểu sâu hơn, sau khi kết thúc
môn học này, em mong thầy có thể giúp đỡ em để hoàn thành chương trình 1 cách hoàn thiện
hơn.
Em xin cám ơn !
IV.Tài liệu tham khảo:
Slide và bài giảng của thầy Ngô Hữu Phúc