Các bước cơ bản của giải thuật di truyền
Bƣớc 1: Khởi tạo một quần thể ban đầu là một tập lời giải tƣợng trƣng cho toàn bộ các lời giải. Mỗi lời giải là một cá thể.
Bƣớc 2: Xác định hàm số thích nghi và tính độ thích nghi cho từng cá thể Bƣớc 3: Tạo các cá thể mới dựa trên các toán tử di truyền
- Lựa chọn (Selection): Việc lựa chọn ra các cá thể đƣợc thực hiện khi cần một số
cá thể để thực hiện sinh sản ra thế hệ sau. Mỗi cá thể có một giá trị thích nghi (fitness). Quá trình này đƣợc mô tả nhƣ sau:
+ Sắp xếp các cá thể theo thứ tự độ thích nghi giảm dần. + Loại bỏ các cá thể ở cuối dãy, giữ lại n cá thể tốt nhất.
- Lai ghép (Crossover): Toán tử lai ghép đƣợc áp dụng nhằm sinh ra các nhiễm sắc
thể con mới từ các cặp nhiễm sắc thể cha mẹ, thừa hƣởng các đặc tính tốt từ cha mẹ. Quá trình này diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai nhiễm sắc thể cha-mẹ với nhau. Quá trình đƣợc mô tả nhƣ sau:
Tạo một số ngẫu nhiên trong khoảng từ 1 tới m-1 (gọi là điểm ghép chéo)
Tại điểm ghép chéo chia nhiễm sắc thể thành hai chuỗi con có độ dài m1, m2 (m1+m2 = m)
Thực hiện ghép chéo hai chuỗi con của cha mẹ để tạo thành nhiễm sắc thể mới m11+m22 và m21+m12
- Đột biến (Mutation): Quá trình tiến hóa đƣợc gọi là đột biến khi một hoặc một số
tính trạng của con không đƣợc thừa hƣởng từ hai chuỗi nhiễm sắc thể cha-mẹ. Kết quả đột biến thƣờng sinh ra các cá thể mới khác biệt so với các cá thể cha mẹ. Trong ngữ cảnh tìm kiếm, toán tử đột biến nhằm đƣa quá trình tìm kiếm ra khỏi khu vực cục bộ địa phƣơng. Phép đột biến có thể mô tả nhƣ sau:
- Chọn ngẫu nhiên một số k từ khoảng 1 ≥ k ≥ m - Thay đổi giá trị của gen thứ k
- Đƣa cá thể con vào quần thể để tham gia quá trình tiến hóa tiếp theo. Bƣớc 4: Đánh giá các các thể mới bằng cách:
- Tính độ thích nghi cho các cá thể mới.
- Loại bớt các cá thể có độ thích nghi thấp, thay thế bằng các cá thể có độ thích nghi cao
Bƣớc 5: Kiểm tra nếu chƣa tìm đƣợc lời giải tối ƣu hay tƣơng đối tốt nhất, quay lại bƣớc 3 để tìm lời giải mới
Bƣớc 6: Kết thúc giải thuật và báo cáo kết quả tìm đƣợc
Hiện nay giải thuật di truyền đã đƣợc áp dụng một cách hiệu quả để giải quyết các bài toán tối ƣu nhƣ bài toán toán ngƣời đi du lịch, bài toán ba lô, bài toán cắt vật tƣ một chiều, giải một số bài toán thống kê, lập thời khoá biểu, lập lịch công tác… Và trong lĩnh vực kiểm thử, giải thuật di truyền cũng đƣợc áp dụng một cách hiệu quả để sinh bộ dữ liệu kiểm thử một cách tự động.
2.5.3. Sinh dữ liệu kiểm thử áp dụng giải thuật di truyền
Bài toán
Cho một phần mềm có chứa form nhập dữ liệu. Quá trình thực hiện kiểm thử là ngƣời dùng nhập dữ liệu đầu vào, theo dõi kết quả trả về từ chƣơng trình và báo cáo. Mục tiêu của quá trình thực hiện kiểm thử là cần tìm những dữ liệu đầu vào mà kết quả trả về là lỗi, kiểm thử đến khi nào tìm hết đƣợc các dữ liệu đầu vào mà kết quả trả về là lỗi.
Giải pháp
Đối với những tập dữ liệu lớn và không phải là những dãy có logic, thì việc thực hiện kiểm thử sẽ mất rất nhiều thời gian hoặc không bao giờ kết thúc. Ví dụ nhƣ
nghiệm mới nghĩ ra đƣợc, hơn thế nữa tập các chuỗi SQL Injection là nhiều, con ngƣời không thể lƣờng hết đƣợc các trƣờng hợp. Chính vì vậy, cần tìm một giải pháp để tối ƣu hóa việc tìm kiếm những dữ liệu mà kết quả trả về là chƣơng trình có lỗi. Nhƣ đã giới thiệu ở trên, giải thuật GA là một giải thuật rất mạnh trong việc tìm kiếm tối ƣu với những không gian tìm kiếm lớn. Vì vậy, để giải quyết bài toán này chúng tôi sử dụng giải thuật GA.
Các bước của giải thuật GA cho bài toán sinh dữ liệu kiểm thử
- Bƣớc 1: Khởi tạo một quần thể ban đầu là một tập dữ liệu đầu vào tƣợng trƣng cho toàn bộ các dữ liệu đầu vào. Một dữ liệu đầu vào để kiểm thử có dạng (x1, x2, …, xN) là một cá thể. Với x1, x2, …, xN là các giá trị để nhập vào form và đƣợc gọi là nhiễm sắc thể.
- Bƣớc 2: Hàm số thích nghi là hàm trả ra kết quả của kiểm thử. Sau khi thực hiện kiểm thử với dữ liệu đầu vào ở bƣớc 1 sẽ xác định đƣợc giá trị của hàm số thích nghi đƣợc gọi là độ thích nghi f(x1, x2, …, xN).
+ Độ thích nghi f(x1, x2, …, xN) = 1 có nghĩa là kiểm thử có lỗi
+ Độ thích nghi f(x1, x2, …, xN) = 0 có nghĩa là kiểm thử không có lỗi
→ Cần xác định các dữ liệu đầu vào (x1, x2, …, xN) sao cho việc thực hiện kiểm thử có lỗi tức là f(x1, x2, …, xN) = 1
- Bƣớc 3: Tạo các cá thể mới dựa trên các toán tử di truyền
- Lựa chọn (Selection): Lựa chọn các cá thể tốt bằng cách
- Sắp xếp các cá thể theo thứ tự độ thích nghi giảm dần
- Loại bỏ các cá thể ở cuối dãy, giữ lại n cá thể tốt nhất.
- Lai ghép (Crossover): Lai ghép các nhiễm sắc thể bằng cách
Chọn ngẫu nhiên một cặp nhiễm sắc thể cha-mẹ trong quần thể. Giả sử, nhiễm sắc thể cha-mẹ x1, x2 có cùng độ dài m.
Tạo một số ngẫu nhiên trong khoảng từ 1 tới m-1 (gọi là điểm ghép chéo)
Tại điểm ghép chéo chia nhiễm sắc thể thành hai chuỗi con có độ dài m1, m2 (m1+m2 = m)
Thực hiện ghép chéo hai chuỗi con của cha mẹ để tạo thành nhiễm sắc thể mới m11+m22 và m21+m12
- Đột biến (Mutation): Đột biến trên nhiễm sắc thể cha mẹ bằng cách
- Chọn ngẫu nhiên một số k từ khoảng 1 ≥ k ≥ m - Thay đổi giá trị gen thứ k của nhiễm sắc thể xi
- Đƣa cá thể con vào quần thể để tham gia quá trình tiến hóa tiếp theo - Bƣớc 4: Đánh giá các các thể mới bằng cách:
- Thực hiện kiểm thử với các giá trị con mới → độ thích nghi cho các cá thể mới.
- Loại bớt các cá thể có độ thích nghi thấp, thay thế bằng các cá thể có độ thích nghi cao
- Bƣớc 5: Kiểm tra nếu chƣa tìm đƣợc lời giải tối ƣu hay tƣơng đối tốt nhất, quay lại bƣớc 3 để tìm lời giải mới
Chƣơng 3. MÔ HÌNH TRIỂN KHAI THỰC TẾ
3.1. GIỚI THIỆU BÀI TOÁN
Phát triển trang web bán hàng online gồm có các chức năng: đăng ký ngƣời dùng, đăng nhập, đăng xuất, giới thiệu sản phẩm, dịch vụ, chi tiết hàng hóa, mua hàng, giỏ hàng, và một số chức năng khác
Trang web: http://bagasse.vn/