Tiểu Luận
Đề Tài :
Nghiên Cứu Giải Thuật GA Giải Bài
Toán Chiếc Balo Loại 1
Lớp: Cao học KHMT
Khóa 23 – Cơ Sở 2 GVHD: Thầy TS Ngô Hữu Phúc
HVTH: Trần Đắc Tốt MS : 11870261

BỘ GIÁO DỤC VÀ ĐÀO TẠO
BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
HVTH: Trần Đắc Tốt; Page 2

Mục lục:
1. Giải thuật di truyền 3
1.1 Giới thiệu về giải thuật di truyền 3
1.1.1 Lịch sử phát triển: 3
1.2 Các khái niệm cơ bản 4
1.2.1 Cá thể, nhiễm sắc thể 4
1.2.2 Quần thể 4
1.2.3 Các toán tử di truyền 4
1.3 Mô hình giải thuật di truyền 5
1.4 Các tham số của GA 6
Xác suất lai ghép 6
Xác suất đột biến 6
Kích thước quần thể 6
1.5 Các cách mã hoá NST 6

quá trình tiến hoá của một tập hợp những đại diện trừu tượng (gọi là những nhiễm sắc thể)
của các giải pháp có thể (gọi là những cá thể) cho bài toán tối ưu hóa vấn đề. Tập hợp này sẽ
tiến triển theo hướng chọn lọc những giải pháp tốt hơn.
Thông thường, những giải pháp được thể hiện dưới dạng nhị phân với những chuỗi 0 và 1,
nhưng lại mang nhiều thông tin mã hóa khác nhau. Quá trình tiến hóa xảy ra từ một tập hợp
những cá thể hoàn toàn ngẫu nhiên ở tất cả các thế hệ. Trong từng thế hệ, tính thích nghi của
tập hợp này được ước lượng, nhiều cá thể được chọn lọc định hướng từ tập hợp hiện thời
(dựa vào thể trạng), được sửa đổi (bằng đột biến hoặc tổ hợp lại) để hình thành một tập hợp
mới. Tập hợp này sẽ tiếp tục được chọn lọc lặp đi lặp lại trong các thế hệ kế tiếp của giải
thuật.
Như đã nói ở trên, GA là một thành phần của EC- một lĩnh vực được coi là có tốc độ phát
triển nhanh của trí tuệ nhân tạo. EC được chia ra thành 5 nhóm :
 Giải thuật di truyền (Genetic Algorithm - GA): Dựa vào quá trình di truyền trong tự
nhiên để cải tiến lời giải qua các thế hệ bắt nguồn từ một tập các lời giải ban đầu.
 Quy hoạch tiến hoá (Evolutionary Programming -EP): Dựa vào quy luật tiến hoá,
tìm phương pháp liên hợp đủ khả năng giải quyết trọn vẹn một bài toán từ một lớp các
phương pháp giải quyết được một số phần của bài toán.
 Các chiến lược tiến hoá ( Evolutionary Strategies -ES): Dựa trên một số chiến lược
ban đầu, tiến hoá để tạo ra những chiến lược mới phù hợp với môi trường thực tế một
cách tốt nhất.
 Lập trình di truyền (Genetic Programming -GP): Mở rộng giải thuật di truyền trong
lĩnh vực các chương trình của máy tính. Mục đích của nó là để sinh ra một cách tự
động các chương trình máy tính giải quyết một cách tối ưu một vấn đề cụ thể.
 Các hệ thống phân loại (Classifier Systems- CS): Các GA đặc biệt được dùng trong
việc học máy và việc phát hiện các quy tắc trong các hệ dựa trên các quy tắc.
Giải thuật di truyền cũng như các thuật toán tiến hoá đều được hình thành dựa trên một quan
niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm "Quá trình
tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu". Quá
trình tiến hoá thể hiện tính tối ưu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước.
Quá trình phát triển của giải thuật di truyền có thể được chỉ ra qua các mốc thời gian sau :

Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay đổi các cá thể
trong quần thể. Những cá thể tốt, thích nghi được với điều kiện sống thì có khả năng đấu
tranh lớn hơn, do đó có thể tồn tại và sinh sản. Các cá thể không thích nghi được với điều
kiện sống thì dần mất đi. Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh sinh tồn
trong tự nhiên, chọn lựa các cá thể trong GA chính là cách chọn các cá thể có độ thích nghi
tốt để đưa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục đích là sinh ra các cá thể mới
tốt hơn. Có nhiều cách để lựa chọn nhưng cuối cùng đều nhằm đáp ứng mục tiêu là các cá
thể tốt sẽ có khả năng được chọn cao hơn.
1.2.3.2 Lai ghép
Lai ghép trong tự nhiên là sự kết hợp các tính trạng của bố mẹ để sinh ra thế hệ con.
Trong giải thuật di truyền, lai ghép được coi là một sự tổ hợp lại các tính chất (thành phần)
trong hai lời giải cha mẹ nào đó để sinh ra một lời giải mới mà có đặc tính mong muốn là tốt
hơn thế hệ cha mẹ. Đây là một quá trình xảy ra chủ yếu trong giải thuật di truyền.
HVTH: Trần Đắc Tốt; Page 5

1.2.3.3 Đột biến
Đột biến là một sự biến đổi tại một ( hay một số ) gen của nhiễm sắc thể ban đầu để
tạo ra một nhiễm sắc thể mới. Đột biến có xác suất xảy ra thấp hơn lai ghép. Đột biến có thể
tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban đầu. Tuy nhiên trong giải thuật di
truyền thì ta luôn muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua từng thế
hệ.
1.3 Mô hình giải thuật di truyền
Với các khái niệm được giới thiệu ở trên, giải thuật di truyền được mô tả như sau :
Nhận các tham số
của bài toán
Khởi tạo quần thể
ban đầu
Tính giá trị thích nghi
Sinh sản
Lai ghép

, khi đó khả năng để một cá thể được lai
ghép là p
c
. Nếu không thực hiện lai ghép, con sinh ra sẽ giống hoàn toàn bố mẹ. Nếu được lai
ghép, con sinh ra sẽ có một phần giống bố và một phần giống mẹ.
Xác suất đột biến
Xác suất đột biến cho biết tính thường xuyên của việc các gen của NST thay đổi như
thế nào. Nếu xác suất đột biến là p
m
, khi đó khả năng để mỗi gen của một NST bất kỳ bị đột
biến là p
m
. Tác dụng của toán tử đột biến là ngăn ngừa giải thuật di truyền rơi vào tình trạng
cực trị địa phương, tuy nhiên nếu thực hiện đột biến với xác suất quá cao sẽ biến giải thuật di
truyền thành giải thuật tìm kiếm ngẫu nhiên.
Kích thước quần thể
Kích thước quần thể cho biết có bao nhiêu cá thể trong một quần thể trong mỗi thế
hệ). Các nghiên cứu và các thử nghiệm đã cho thấy kích thước quần thể không nên quá bé
cũng như không quá lớn. Nếu có quá ít cá thể thì sẽ làm giảm không gian tìm kiếm của giải
thuật và dễ rơi vào các cục bộ địa phương, như vậy sẽ dễ xảy ra trường hợp bỏ qua các lời
giải tốt. Tuy nhiên nếu có quá nhiều cá thể cũng sẽ làm cho giải thuật chạy chậm đi, ảnh
hưởng đến hiệu quả tính toán của giải thuật. Các nghiên cứu cũng đã chỉ ra không có lợi khi
tăng kích thước quần thể lên quá một giới hạn cho phép.
1.5 Các cách mã hoá NST
Trong giải thuật di truyền cách mã hóa NST rất quan trọng nó không chỉ quyết định
đến hiệu quả của giải thuật mà còn ảnh hưởng đến việc lựa chọn các toán tử trong các bước
lai ghép và đột biến. Với mỗi kiều bài toán khác nhau có nhiều cách mã hóa NST .
Cách mã hoá NST được đánh giá là một trong hai yếu tố quyết định trong xây dựng
giải thuật di truyền. Phần sau đây sẽ trình bày một số cơ chế mã hoá nhiễm sắc thể hay dùng
cho giải thuật di truyền. Tuy nhiên, tuỳ thuộc vào các tri thức riêng của từng bài toán mà ta sẽ

dùng một nhiễm sắc thể mà trình tự các số trong chuỗi cho biết thứ tự các thành phố mà
người du lịch đi qua.
Mã hoá theo giá trị
Mã hoá trực tiếp theo giá trị có thể được dùng trong các bài toán sử dụng giá trị phức
tạp như trong số thực. Trong đó, mỗi nhiễm sắc thể là một chuỗi các giá trị. Các giá trị có thể
là bất cứ cái gì liên quan đến bài toán, từ số nguyên, số thực, kí tự cho đến các đối tượng
phức tạp hơn.
Ví dụ:
Nhiễm sắc thể 1: 1.23 5.32 0.34 2.98 3.54
Nhiễm sắc thể 2: (back), (back), (right), (forward), (left)
Mã hoá theo giá trị thường dùng cho các bài toán đặc biệt. Trong cách mã hoá này ta
thường phải phát triển các toán tử đột biến và lai ghép cho phù hợp với từng bài toán.
1.6 Khởi tạo quần thể ban đầu
Quần thể ban đầu ảnh hưởng khá nhiều đến hiệu quả giải thuật, tuy nhiên trong nhiều bài toán
thì quần thể ban đầu thường được lựa chọn ngẫu nhiên
Hàm tính độ thích nghi
Hàm độ thích nghi(fitness function) là hàm đánh giá hay hàm mục tiêu thể hiện tính
thích ngi của cá thể hay độ tốt của lời giải
HVTH: Trần Đắc Tốt; Page 8

Cơ chế lựa chọn
Cơ chế lựa chọn được áp dụng khi quần thể P(t+1) được tạo ra từ việc chọn các cá
thể từ quần thể P(t) để thực hiện việc lai ghép và đột biến. Có nhiều cách để lựa chọn các cá
thể từ một quần thể. Sau đây sẽ giới thiệu một số cơ chế hay áp dụng.
Để tiện mô tả các cơ chế lựa chọn ta đưa ra một số kí hiệu sau :
Cách biểu diễn các nhiễm sắc thể thứ i là v
i
.
Hàm tính độ thích nghi của nhiễm sắc thể v
i

của mỗi nhiễm sắc thể :



i
j
ji
Pq
1

Cơ chế lựa chọn theo bánh xe Roulet được thực hiện bằng cách quay bánh xe Roulet
N lần. Mỗi lần chọn một nhiễm sắc thể từ quần thể hiện hành vào quần thể mới bằng cách sau
:
 Phát sinh ngẫu nhiên một số r trong khoảng [0,1].
 Nếu r < q
1
thì chọn nhiễm sắc thể v
1
; ngược lại thì chọn nhiễm sắc thể thứ i ( 2  i 
pop_size ) sao cho q
i-1
 r  q
i
.
Với cơ chế lựa chọn như thế này thì có một số nhiếm sắc thể sẽ được chọn nhiều lần.
Điều này phù hợp với lý thuyết lược đồ: Các nhiễm sắc thể tốt nhất thì có nhiều bản sao,
nhiễm sắc thể trung bình thì không đổi , nhiễm sắc thể kém thì chết đi [11].
Lựa chọn xếp hạng
Cơ chế lựa chọn xếp hạng được mô tả như sau:
 Sắp xếp các nhiễm sắc thể trong quần thể theo độ thích nghi từ thấp đến cao.

Lai ghép đơn điểm cắt :
 Một điểm cắt được chọn tại một vị trí thứ k trên NST.
 Từ đầu NST đến vị trí k, NST con sao chép từ cha, phần còn lại sao chép từ
mẹ.
Lai ghép hai điểm cắt :
 Hai điểm cắt được chọn .
 Từ đầu cho đến điểm cắt thứ nhất được sao chép từ cha, từ điểm cắt thứ nhất
đến điểm cắt thứ hai sao chép từ mẹ và phần còn lại sao chép từ cha.
Lai ghép đồng nhất :
 Có một mặt nạ sao chép là một chuỗi nhị phân có chiếu dài bằng chiều dài
NST.
 Xây dựng NST mới: Duyệt qua mặt nạ, bit có giá trị một thì sao chép gen tại
vị trí đó từ NST cha sang con, bit có giá trị 0 thì sao chép từ mẹ.
 Mặt nạ được phát sinh ngẫu nhiên đối với từng cặp cha mẹ.

Lai ghép số học: NST con được tạo thành bằng cách thực hiện một phép toán logic
nào đó như AND, OR, … với cặp NST bố mẹ.
1.7.1.2 Toán tử đột biến
Phép đảo bit : Bit được chọn sẽ bị đảo
Mã hoá hoán vị
1.7.1.3 Toán tử lai ghép
Toán tử lai ghép đơn điểm cắt :
HVTH: Trần Đắc Tốt; Page 10

 Một điểm cắt được chọn.
 Từ đầu đến điểm cắt được lấy từ cha, phần còn lại duyệt qua mẹ, đưa những
gen chưa có vào.
1.7.1.4 Toán tử đột biến
Thay đổi thứ tự : Hai số được chọn hoán đổi vị trí cho nhau.
Ví dụ : (Số được chọn có gạch chân)

bị thay thế. Tuy chiến lược không kiểm tra các NST con cháu nạp vào có tốt hơn bố
mẹ bị loại đi hay không nhưng chắc chắn là những NST con cháu nạp vào nếu là tồi
HVTH: Trần Đắc Tốt; Page 11

thì sẽ bị loại trong thế hệ tiếp. Như vậy nó vẫn đảm bảo qua nhiều thế hệ thì tính chất
của quần thể sẽ được cải thiện dần dần.
2. Áp Dụng Giải Thuật Ga Giải Bài Toán Chiếc Balo Loại 1
Phát biểu Bài toán ba lô:
Cho trước một tập thực thể cùng các giá trị và kích thước của chúng. Cần chọn được một hay
nhiều tập con rời nhau sao cho tổng kích thước trong mỗi tập con không vượt quá giới hạn
cho phép và tổng giá trị đã chọn là lớn nhất.
Vấn đề bài toán đượ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

Hàm elitism: Chọn trong các cá thể của quần thể đang xét có cá thể nào có tổng giá trị
là lớn nhất và khối lượng là nhỏ nhất thì lưu lại và đưa vào quần thể sau.
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(chọn cá thể có khối lượng không vượt quá 50 nhưng phải lớn hơn 40
và giá trị không được thấp hơn 30 để đưa vào quần thể lai hóa).
private void Ham_thich_nghi(string[] str_p_)
{
int sum1 = 0;
int sum2 = 0;
lb_rank.Items.Clear();
string tmp = "";
count = 0;
for (int i = 0; i < 30; i++)
{
tmp = str_p_[i];
for (int j = 0; j < 10; j++)
{
if (Convert.ToInt16(tmp[j]) == 49)
{
sum1 += balo[j, 0];
sum2 += balo[j, 1];
}
}
if (sum2 <= 49 && sum1 >= 50 && sum2 >= 40)
{
lb_rank.Items.Add(tmp);
str_f[count] = tmp;
count++;
}
sum2 = 0;

temp1 = 0;
}
Random rnd = new Random();
int r = rnd.Next(0, temp2);
int sum3 = 0, sum4 = 0, ret = 0, tmp1 = 0, tmp2 = 0;
for (int i = 0; i < 30; i++)
{
tmp = str_p_[i];
for (int j = 0; j < 10; j++)
{
if (Convert.ToInt16(tmp[j]) == 49)
{
sum3 += balo[j, 1];
sum4 += balo[j, 0];
tmp1 = sum4 - sum3;
}
}
tmp2 += tmp1;
sum3 = 0;
sum4 = 0;
tmp1 = 0;
if (sum4 > r)
{
ret = i;
goto end;
}
}
end: return ret;
}
e. Lai ghép ( crossover )

{
string temp = "";
for (int i = 0; i < str1.Length; i++)
{
temp += Convert.ToString(Convert.ToByte(str1[i]) ^ Convert.ToByte(str2[i]));
}
return temp;
}
f. Đột biến ( Mutation)
Đột biến được thực thi sau tiến trình lai ghép ( crossover) để đảm bảo không bị dừng
lại ở giá trị cực trị địa phương ( a local optimum) trong quá trình giải quyết bài toán. (
Đột biến trên 1 gene nào đó, với giá trị 0 sẽ chuyển thành 1, và ngược lại ).
Hàm Đột biến (Mutation)
private void Mutation(string[] str)
{
Random rnd = new Random();
int index_str = rnd.Next(0, 30);
HVTH: Trần Đắc Tốt; Page 15

string tmp = str[index_str];
int num = rnd.Next(1, 3);
for (int i = 0; i < num; i++)
{
int index = rnd.Next(0, 9);
if (tmp[index].Equals("0"))
{
tmp.Remove(index, 1);
tmp.Insert(index, "1");
}
else