HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG NGUYỄN THỊ QUỲNH NGA

ÁP DỤNG THUẬT TOÁN DI TRUYỀN TRONG SINH CÁC DỮ
LIỆU KIỂM THỬ PHẦN MỀM Chuyên ngành : Khoa học máy tính
Mã số: 60.48.01.01 TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI – 2013
Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: PGS.TS Huỳnh Quyết Thắng


Vì thế, em chọn đề tài " áp dụng thuật toán di truyền trong sinh các dữ liệu kiểm thử
phần mềm". Nội dung của luận văn sẽ gồm 04 chương.
Chương 1: Bài toán áp dụng thuật toán di truyền sinh dữ liệu kiểm thử phần mềm.
Chương 2: Các kỹ thuật kiểm thử phần mềm
Chương 3: Thuật toán di truyền
Chương 4: Áp dụng thuật toán di truyền sinh các dữ liệu kiểm thử tự động
2
CHƯƠNG 1: BÀI TOÁN ÁP DỤNG THUẬT TOÁN DI TRUYỀN
SINH DỮ LIỆU KIỂM THỬ PHẦN MỀM
1.1 Đặt vấn đề
Việc xác minh và xác thực phần mềm thông qua kiểm thử động là một lĩnh vực kỹ thuật
phần mềm mà tiến triển theo hướng tự động hóa đang bị chậm lại. Đặc biệt là tự động thiết kế
và sinh ra dữ liệu kiểm thử. Kiểm thử phần mềm vẫn là kỹ thuật chính được sử dụng để đạt
được sự tin tưởng của người tiêu dùng. Quá trình kiểm thử hệ thống phần mềm là một nhiệm
vụ lớn và tốn nhiều thời gian. Theo Tai [1980], Ince [1987]: 50% chi phí phát triển phần mềm
là dành cho phần thử nghiệm [4]. Vì vậy mà có nhiều nghiên cứu nhằm tìm ra các công cụ
kiểm thử phần mềm tự động để giảm chi phí phát triển phần mềm. Do đó, sinh dữ liệu kiểm thử
tự động là một công cụ hỗ trợ và giúp thử nghiệm chương trình để sản xuất dữ liệu thử nghiệm
cho phần mềm. Lý tưởng nhất, phần mềm kiểm tra đảm bảo không có lỗi phần mềm, nhưng
trong thực tế, nó cho thấy lỗi của phần mềm vẫn xuất hiện. Thậm chí bằng cách phát hiện các
phản ứng của chúng, kiểm thử hệ thống không thể chứng minh hoàn toàn không có lỗi. Một
mục tiêu của kiểm thử phần mềm là tìm lỗi và tìm lỗi cấu trúc chương trình. Tuy nhiên, vấn đề
đó có thể được quyết định khi nào ngừng thử nghiệm phần mềm, ví dụ như nếu không có lỗi
được tìm thấy hay sau một khoảng thời gian tìm kiếm, nếu một số lỗi được tìm thấy.
Trong ngành kỹ nghệ phần mềm, năm 1979, có một quy tắc nổi tiếng là: “Trong một dự
án lập trình điển hình, thì xấp xỉ 50% thời gian và hơn 50% tổng chi phí được sử dụng trong
kiểm thử các chương trình hay hệ thống đã được phát triển” [2]. Và cho đến nay, sau gần một
phần 3 thế kỷ, quy tắc đó vẫn còn đúng. Đã có rất nhiều ngôn ngữ, hệ thống phát triển mới với
các công cụ tích hợp cho các lập trình viên sử dụng phát triển ngày càng linh động. Nhưng
kiểm thử vẫn đóng vai trò hết sức quan trọng trong bất kỳ dự án phát triển phần mềm nào [15].

của GA là ở việc xử lý dữ liệu đầu vào có cấu trúc là số phức, vị từ phức tạp, hàm chưa biết của
các biến đầu vào. Vì vậy, vấn đề sinh dữ liệu kiểm thử là một vấn đề tối ưu hóa.
Kiểm thử ngẫu nhiên được sử dụng như một so sánh về hiệu quả dữ liệu kiểm thử được
sinh ra bởi GA. Lợi thế của GA là thông qua việc tìm kiếm và quá trình tối ưu hóa, các bộ kiểm
thử được nâng cao và như vậy chúng đang ở gần biên miền con. Thuật toán di truyền đưa ra
nhiều cải tiến so với kiểm thử ngẫu nhiên khi miền con là nhỏ. Phân tích đột biến được sử dụng
để thiết lập chất lượng dữ liệu kiểm thử được sinh ra và những ưu điểm, nhược điểm của
chúng.
4
Thủ tục phần mềm là khác nhau với cấu trúc dữ liệu đầu vào (số nguyên, ký tự, mảng,
bản ghi), cấu trúc chương trình với điều kiện 'if' và vòng lặp.
Nhiều thử nghiệm cho thấy, GA cần ít thời gian để CPU đạt giải pháp toàn cục so với
kiểm thử ngẫu nhiên.
1.2 Đối tượng nghiên cứu
- Các kỹ thuật kiểm thử phần mềm: kiểm thử hộp trắng, kiểm thử hộp đen và kiểm thử
hộp xám; trong đó, kiểm thử hộp trắng được nhấn mạnh hơn.
- Lý thuyết cơ sở về thuật toán di truyền.
- Thủ tục không có điều kiện vòng lặp và hàm có cấu trúc phức tạp như: thủ tục giải
phương trình bậc hai và hàm tìm kiếm nhị phân.
1.3 Giải pháp công nghệ
Luận văn sử dụng ngôn ngữ lập trình pascal để viết chương trình cho các thủ tục và
hàm.
1.4 Kết chương
Chương I đã trình bày lợi thế của việc sử dụng thuật toán di truyền sinh ra dữ liệu kiểm
thử tự động so với kiểm thử tự động. Và trong chương này cũng đưa ra đối tượng nghiên cứu
và giải pháp công nghệ.
5
CHƯƠNG 2: CÁC KỸ THUẬT KIỂM THỬ PHẦN MỀM
Mục tiêu của kiểm thử là phải thiết kế các trường hợp kiểm thử có khả năng cao nhất
trong việc phát hiện nhiều lỗi với thời gian và công sức tối thiểu. Do đó, có thể chia các kỹ

Điểm xuất phát của kiểm thử dữ liệu là từ đặc tả dữ liệu nằm trong phương thức kiểm
thử hộp đen. Phương thức này sẽ tạo ra ca kiểm thử và dữ liệu kiểm thử.
2.2.3 Kiểm thử ngẫu nhiên
Kiểm thử ngẫu nhiên lựa chọn tùy ý dữ liệu kiểm thử từ miền đầu vào và sau đó dữ liệu
kiểm thử được áp dụng cho chương trình được thử nghiệm. Ưu điểm của nó là thực hiện đơn
giản và tốn ít thời gian chạy.
2.3 Kết chương
Kiểm thử phần mềm được sử dụng rộng rãi trong nhiều ứng dụng với việc nghiên cứu
thử nghiệm khác nhau. Trong chương 2 tác giả đã tập hợp các tài liệu nội để trình bày tổng
quan về sự khác biệt cơ bản giữa một số kỹ thuật kiểm thử phần mềm như: kiểm thử hộp đen,
kiểm thử hộp trắng, kiểm thử hộp xám và các phương pháp sinh dữ liệu kiểm thử tự động.
Kiểm thử hộp đen chú trọng vào việc kiểm tra các quan hệ vào ra và những chức năng giao
diện bên ngoài, nó thích hợp hơn cho các hệ thống phần mềm lớn hay các thành phần quan
trọng của chúng. Kiểm thử hộp trắng xem xét chương trình ở mức độ chi tiết và phù hợp khi
kiểm tra các mô-đun nhỏ. Kiểm thử hộp trắng có thể không đầy đủ vì kiểm thử hết các lệnh
không chứng tỏ là chúng ta đã kiểm thử hết các trường hợp có thể. Ngoài ra chúng ta không thể
kiểm thử hết các đường đi đối với các vòng lặp lớn.
Trong chương này cũng cho ta thấy tư tưởng việc sinh dữ liệu kiểm thử bằng thuật toán
di truyền hiệu quả hơn so với sử dụng kiểm thử ngẫu nhiên.
7
CHƯƠNG 3: THUẬT TOÁN DI TRUYỀN
Những vấn đề về tối ưu hóa xảy ra ở mọi lĩnh vực, đặc biệt là trong lĩnh vực kĩ thuật.
Chính vì vậy, rất nhiều phương pháp tối ưu hóa đã được phát triển. Tuy nhiên, những phương
pháp này thường mắc lỗi với những hàm không liên tục hoặc không tính được đạo hàm ở mọi
điểm hoặc những hàm bị nhiễu. Chính vì vậy, những phương pháp tốt hơn có thể xử lý được
những hàm này đang được phát triển. Trong quá khứ, những cách tiếp cận sinh học và vật lí
đang thu hút được sự chú ý trong việc giúp đỡ phát triển các phương pháp tối ưu hóa, bao gồm
cả hệ thống thần kinh, thuật toán di truyền. Chương này sẽ giải thích những đặc điểm và
phương thức của Thuật toán di truyền. Ngay sau đó sẽ là một ví dụ về tối ưu hóa sử dụng Thuật
toán di truyền.

trình lai ghép sẽ tìm kiếm những gen vượt trội trong vật liệu di truyền. Mục đích của quá trình
này là để tạo ra những cá thể tốt hơn dựa trên sự kết hợp thông tin di truyền từ 2 cá thể bố mẹ
từ thế hệ trước.
3.3.4.1 Lai ghép đơn
3.3.4.2 Lai ghép kép
3.3.4.3 Lai ghép đồng loạt
3.3.5 Sự đột biến
Quá trình đột biến là sự thay đổi ngẫu nhiên 1 giá trị bit, từ đó thay đổi ngẫu nhiên 1 số
đặc tính. Trong mã nhị phân, điều này đơn giản có nghĩa là thay đổi trạng thái của gen từ 0
sang 1 hoặc ngược lại.
3.3.5.1 Đột biến thông thường
3.3.5.2 Đột biến được tính toán trước
3.3.6 Sự tồn tại
Phương pháp tồn tại quyết định xem nhiễm sắc thể nào trong các cá thể mới và cũ được
tồn tại hoặc bị loại bỏ. Để hoàn thành công việc này, quá trình có thể sao chép 1 phần của các
cá thể mới tới quần thể bố mẹ, dựa trên phẩm chất của các cá thể tương tự như trong quá trình
chọn lọc.
3.3.6.1 SURVIVE_1
3.3.6.2 SURVIVE_2
9
3.3.6.3 SURVIVE_3
3.3.6.4 SURVIVE_4
3.3.6.5 SURVIVE_5
3.4 Cấu trúc của thuật toán di truyền
Cấu trúc của GA được thể hiện trong Hình 3.1, mã tương ứng như trong Hình 3.2, trong
đó t là số thế hệ và P là quần thể .


và đột biến
Tồn tại
t:= t + 1
{Hết lặp}
end.

Hình 3.1 Sơ đồ cấu trúc thuật toán GA Hình 3.2 Mô phỏng thuật toán GA
3.5 Kết chương
Thủ tục tồn tại
Khởi tạo quần
thể
Đánh giá sự
thích nghi
Chọn lọc
Lai ghép
Đột biến
Điều kiện
dừng
Bắt đầu
Không
Thỏa
Kết thúc
10
Như ví dụ trong phần này đã miêu tả, mục tiêu chính là đạt được phương án tối ưu cho 1
hàm. Cách thức làm việc của GA cũng đã được miêu tả kỹ với ví dụ cơ bản.
Những đặc điểm chính của GA được nêu ra dưới đây:
 Tập trung vào những nhiễm sắc thể với sự thích nghi trên trung bình.
 Lợi dụng thông tin về 1 số lượng lớn các giá trị trong khi xử lí 1 tập thể nhỏ.
 Ngăn chặn việc tìm kiếm bị tắc nghẽn ở những điểm tối ưu tạm thời.
 Lợi dụng những kiến thức cũ được lưu trữ trong quần thể những phương thức để tạo ra

12

if A <= B then Read (2);
if A = B then Read (3)
Else
if A < B then read (4)
else read (5);

Hình 4. 1 Ví dụ về đồ thị luồng điều khiển
Để kiểm tra xem các nhánh có được đi qua hay không thì ta sẽ sử dụng thủ tục
CHECK_BRANCH và LOOKING_BRANCH. Trong đó, CHECK_BRANCH sẽ thực hiện để
ghi lại việc các nhánh đã được thực hiện. LOOKING_BRANCH tính toán giá trị fitness trong
trường hợp nút anh chị em hoặc một trong những nút kế cận tiếp theo nó không được thực hiện.
Thông số thiết lập cho GA:
Chọn lọc cha mẹ để kết hợp lại là ngẫu nhiên
Các gen (bit) đột biến được tô đậm trong quần thể con
Sự thích nghi được tính toán theo hàm fitness nghịch đảo
Lai ghép đơn
Xác suất tồn tại P
S
= 0.5
Xác suất đột biến P
m
= 0.1
Ta có các bảng kết quả thể hiện các thế hệ của quần thể thông qua thuật toán di truyền
Bảng 4.1 Thế hệ đầu tiên
P
i

A

2
1, 5
11101 11111
0.0156
0.205
0.570

P
3

8
15
2
1, 2, 4
00010 11110
0.0204
0.268
0.838

P
4

3
-6
2
1, 5
11000 01101
0.0123
0.162
1.0

i,accu

P
1

4
10
3
1, 2, 4
00100 01010
0.0278
0.365
0.365

P
2

-7
-15
3
1, 5
11101 11111
0.0156
0.205
0.570

P
3

8

i

Số
nút
Đường
dẫn
Nhiễm sắc
thể
fitness
f
i,norn
f
i,accu
A
B
k
O
1

P
2

P
4

3
1, 5
11101 01111
0.0204
0.289

0
-6
3
O
4

3
1, 2, 4
11000 01010
0.0204
0.289
1.0
3
10
F
t
= 0.071

Bảng 4.4 Sự tồn tại của cá thể con cái

Cá thể 1
Cá thể 1
Cá thể 1
Cá thể 1
Cha mẹ và con cái
0.678
0.298
0.978
0.457
Tồn tại của cha mẹ

vào được sử dụng, giá trị của vị từ trong thời gian thực thi và toán tử quan hệ được sử dụng.
Tính đầy đủ của bộ kiểm thử liên quan trực tiếp tới giá trị fitness và một số nút nhất định thu
được thông qua vị từ.
14
4.2 Áp dụng thuật toán di truyền cho kiểm thử thủ tục không có điều kiện
vòng lặp
Mục đích của phần này là để giải thích các nghiên cứu thực nghiệm vào kiểm thử phần
mềm bằng cách sử dụng thủ tục được kiểm thử là phương trình bậc hai.
4.2.1 Phương trình bậc hai
Một loạt các thử nghiệm được thực hiện bằng việc áp dụng thuật toán di truyền để sinh
ra dữ liệu kiểm thử cho phần mềm thử nghiệm. Trong phần này thì giải phương trình bậc hai
(hay được gọi là thủ tục được thử nghiệm) được chọn. Cây luồng điều khiển được hiển thị và
chương trình phần mềm pascal được thể hiện trong hình 4.2. Trong thủ tục này có 3 biến đầu
vào (A,B,C) là số nguyên và 4 đường dẫn đến các thủ tục được thử nghiệm.


Else
If (D=0) then
Writeln (‘phuong trinh co
nghiem kep’)
Else
Writeln (‘phuong trinh vo
nghiem’);
End;
Hình 4.2 Cây luồng điều khiển và chương trình phần mềm cho thủ tục bậc hai
1
2
3
4
5
6
7
A = 0
A ≠ 0
D > 0
D <= 0
D = 0
D ≠ 0
15
Vấn đề của giải phương trình bậc hai bắt đầu từ việc tìm nghiệm một phương trình bậc
hai của phương trình dạng 4.1. Và nghiệm của nó được thể hiện trong 4.2.
0
2
 CBxAx
(4.1)
A

hằng số (A=0) và kết quả là nó không phải là phương trình bậc hai vì hạng tử đầu tiên của
phương trình 4.1 là số 0.
4.2.1.1 Thủ tục chọn lọc
4.2.1.2 Kích thước quần thể Psz
Kích thước quần thể Psz được lựa chọn theo kích thước của nhiễm sắc thể. Bình thường
có nhiều nhiễm sắc thể trong quần thể giống như là có nhiều bit (gen) trong một nhiễm sắc thể.
Nhiễm sắc thể có chiều dài là (S) là tổng của số bit (n
i
), n
i
là kiểu dữ liệu đại diện cho số lượng
các biến đầu vào (N) được tối ưu hóa bằng thuật toán di truyền. Ví dụ, nếu chỉ có các biến đầu
vào như nhau thì số lượng bit có thể tính bằng phương trình:



N
i
i
nS
4.4

16
Bảng 4.5 Kết quả của kích thước dân số
Thử nghiệm
Quần thể với kích thước P
SZ
Kết quả
P
1

Lai ghép đồng đều
0.1
96.4% trong 19.5
95.4% trong 19.5
99.1% trong 15.9
0.2
97.6% trong 17.9
96.7% trong 18.9
99.6% trong 16
0.3
97.5% trong 16.8
97% trong 18.8
100% trong 14.9
0.4
98% trong 16.9
97.5% trong 17.4
100% trong 14.8
0.5
98.4% trong 16.4
98.2% trong 18.2
100% trong 13.4
0.75
98.6% trong 17.2
98.3% trong 16.3
99.4% trong 15.4
0.9
98.1% trong 17.4
98% trong 16.8
99% trong 16.2
Kết quả thử nghiệm cho thấy rằng lai ghép đồng đều đạt phủ nhánh tốt hơn so với hai

Nhiều thử nghiệm được tiến hành để nghiên cứu sự kết hợp của các toán tử, xác suất và
phương pháp tốt nhất cho thuật toán di truyền thể hiện qua vấn đề sau:
- Lai ghép đồng đều với P
c
=0.5, kích thước của quần thể P
SZ
=96, xác suất đột biến
P
m
=0.01, SURVIVE_5 với P
S
=0.5 . , xác suất equality P
E
=0.3, hàm fitness, mã nhị phân và
cường độ đại diện đã được tìm thấy cách thiết lập tốt nhất.
4.2.3 Tiểu kết
Để so sánh hiệu quả của việc sử dụng thuật toán di truyền, thử nghiệm ngẫu nhiên thuần
túy được đưa ra. Nếu các bộ đầu vào được tạo ra trong phạm vi ± 100 với một xác suất thống
nhất thì 7354 cuộc kiểm tra ngẫu nhiên mới có thể đạt phủ nhánh đầy đủ (100% trong 76,6 thế
hệ. Trong khi đó, nếu sử dụng thuật toán di truyền thì trong 1287 cuộc thử nghiệm, phủ nhánh
đầy đủ đạt 100% trong 13,4 thế hệ. Do đó thời gian đạt phủ nhánh khi sử dụng phương pháp di
truyền sẽ nhanh hơn so với kiểm thử ngẫu nhiên.và khi sử dụng thuật toán di truyền thì các tối
ưu toàn cục (D=0) cũng được tìm thấy sớm hơn.
4.3 Áp dụng thuật toán di truyền trong kiểm thử hàm/thủ tục có cấu trúc
phức tạp
4.3.1. Tìm kiếm nhị phân
18

mã
5 bit
10 bit
5 bit
10 bit

66.4% trong 53
98.8% trong 45.4
61.6% trong 66.6
95.6% trong 45.7
A(MID)<x
A(MID)>x
1
2
5
3
C
4
End
binary
L
While lặp
Node L = 6: 1 lần
Node L = 7 : 2 lần
Node L = 8 : > 2 lần
A(MID)=x
return
19
>6503 thử
nghiệm

quả xác định bằng thực nghiệm. khi NITS = 10 có 512 giải pháp toàn cục đòi hỏi 79 ca kiểm
thử. Để thử nghiệm đầy đủ về vòng lặp có 48640 ca kiểm thử được yêu cầu so với 871 thử
nghiệm đạt được với GA, do đó kiểm thử với thuật toán di truyền thì cuộc thử nghiệm sẽ ít hơn
so với kiểm thử ngẫu nhiên và tốc độ đạt phủ cũng nhanh hơn.
20
KẾT LUẬN
Việc nghiên cứu và áp dụng thuật toán di truyền vào nhiều lĩnh vực đã được thực hiện
trong một thời gian dài, nhưng vẫn rất được quan tâm do tầm quan trọng, sự cần thiết của nó
trong các lĩnh vực, đặc biệt là trong ngành công nghiệp kiểm thử phần mềm GA đang được sử
dụng để giải quyết một loạt các vấn đề hàng ngày trong kỹ thuật học máy và hàm tối ưu. Luận
văn của tác giả với đề tài: “áp dụng thuật toán di truyền trong sinh các dữ liệu kiểm thử phần
mềm” đã cơ bản hoàn thành. Đề tài đã giải quyết được các vấn đề sau:
1. Trình bày những khái niệm cơ bản về các kỹ thuật kiểm thử phần mềm và sinh dữ liệu
kiểm thử tự động.
2. Tìm hiểu những đặc điểm, đặc trưng, ứng dụng về thuật toán di truyền và đưa ra được
một ví dụ về tối ưu hóa khi sử dụng thuật toán di truyền.
3. Luận văn đã áp dụng thuật toán di truyền vào các thủ tục và hàm không có điều kiện
vòng lặp, có cấu trúc phức tạp để sinh ra dữ liệu kiểm thử phần mềm và chứng minh tính khả
thi của nó. Thủ tục giải phương trình bậc hai và hàm tìm kiếm nhị phân được sử dụng cho thấy
dữ liệu kiểm thử được tạo ra do GA tốt hơn so với kiểm thử ngẫu nhiên tạo ra.
4. Việc dữ liệu kiểm thử được sinh ra đi qua các nút và đạt phủ nhánh nhanh hơn khi sử
dụng GA so với kiểm thử ngẫu nhiên.
Trong tương lai luận văn được phát triển theo các hướng sau:
 Tiếp tục nghiên cứu cơ sở lý thuyết về thuật toán di truyền và các vấn đề nghiên
cứu tối ưu khác.
 Nghiên cứu việc áp dụng GA vào thủ tục giải bài toán tam giác, tìm kiếm tuần tự
và tuyến tính để có cách nhìn sâu hơn về hiệu quả của GA so với kiểm thử ngẫu
nhiên.
 Tìm hiểu hàm fitness Hamming được sử dụng cho GA để so sánh với hàm fitness
nghịch đảo mà GA hay sử dụng.