Tài liệu Áp dụng thuật toán di truyền trong các dữ liệu kiểm thử phần mềm

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 Phản biện 1: ……………………………………………………………… Phản biện 2: ……………………………………………………………… Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 MỞ ĐẦU 1.1 Lý do chọn đề tài Thuật toán di truyền được lập dựa trên cơ sở lý thuyết Darwin và đã được giới thiệu lần đầu tiên bởi Holland (1975), sau đó Goldberg (1989). Đến năm 1992 Michalewicz đã phát triển và hoàn thiện phương pháp này; từ đó thuật toán di truyền đã được áp dụng trong các lĩnh vực khác nhau. Kiểm thử phần mềm là quá trình thực hiện một chương trình hoặc hệ thống với mục đích tìm kiếm lỗi. Không giống như các hệ thống vật lý, hầu hết các lỗi trong phần mềm là lỗi do thiết kế. Xây dựng dữ liệu thử nghiệm trong kiểm thử phần mềm đòi hỏi chi phí lớn và biết sử dụng phương pháp để tạo ra các dữ liệu thử nghiệm là rất quan trọng. Theo các nghiên cứu: 50% chi phí phát triển phần mềm là dành cho phần thử nghiệm. Vì vây, việc sinh dữ liệu tự động sẽ giúp chương trình thử nghiệm cung cấp các dữ liệu thử nghiệm cho phần mềm do đó sẽ hiệu quả đối với việc giảm chi phí và tăng chất lượng kiểm thử. 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]. Nói chung mục tiêu của kiểm thử phần mềm là thiết kế một bộ số lượng tối thiểu của các ca kiểm thử để cho biết các lỗi của phần mềm. Như đã đề cập kiểm thử phần mềm rất tốn thời gian vì thế, kiểm thử phần mềm tự động có thể làm giảm đáng kể chi phí phát triển phần mềm. Ngoài ra nó còn có một số lợi ích sau: việc chuẩn bị thử nghiệm có thể được thực hiện trước, các lần chạy thử nghiệm sẽ nhanh đáng kể và sự tự tin của các kết quả thử nghiệm có thể được tăng lên. Tuy nhiên, kiểm thử phần mềm tự động không phải là một quá trình đơn giản. Trong nhiều năm qua, nhiều nhà nghiên cứu đã đề xuất phương pháp khác nhau để tạo ra dữ liệu kiểm 3 thử tự động, tức là phương pháp khác nhau cho phát triển dữ liệu thử nghiệm[16]. Sự phát triển của kỹ thuật cũng sẽ hỗ trợ việc tự động hóa kiểm thử phần mềm và dẫn đến tiết kiệm chi phí đáng kể. Như ứng dụng của kỹ thuật nhân tạo trong công nghệ phần mềm. Một số nhà nghiên cứu đã sử dụng ứng dụng trên để kiểm thử phần mềm, để làm được điều này thì phải có thuật toán tìm kiếm phù hợp như mô phỏng luyện kim, thuật toán di truyền, tối ưu hóa đàn kiến là lựa chọn tốt cho sinh dữ liệu kiểm thử tự động [16]. Một số nhà nghiên cứu đã áp dụng thuật toán di truyền trong sinh các dữ liệu kiểm thử phần mềm, và trong ngành khoa học máy tính, tìm kiếm lời giải tối ưu cho các bài toán là vấn đề đặc biệt được các nhà nghiên cứu quan tâm. Mục đích chính của các thuật toán là tìm ra lời giải tốt nhất trong thời gian nhỏ nhất. Các thuật toán như tìm kiếm trên danh sách, trên cây hoặc đồ thị sử dụng phương pháp đơn giản và trực quan nhất hoặc các thuật toán tìm kiếm metaheuristic áp dụng các tri thức về cấu trúc của không gian tìm kiếm nhằm giảm thời gian cần thiết cho việc tìm kiếm được sử dụng nhiều nhưng chỉ với không gian tìm kiếm nhỏ [5]. Tuy nhiên, trong thực tiễn có rất nhiều bài toán tối ưu với không gian tìm kiếm rất lớn cần phải giải quyết. Vì vậy, việc đòi hỏi thuật giải chất lượng cao và sử dụng kỹ thuật trí tuệ nhân tạo đặc biệt rất cần thiết khi giải quyết các bài toán có không gian tìm kiếm lớn. GA là một trong những kỹ thuật tìm kiếm lời giải tối ưu đã đáp ứng được yêu cầu của nhiều bài toán và ứng dụng. Thuật toán di truyền (GA) đã được sử dụng thành công để tự động sinh ra các dữ liệu kiểm thử cho phát triển phần mềm trong ADA83. Các dữ liệu kiểm thử được lấy ra từ cấu trúc chương trình với mục đích là đi qua được các nhánh. Các nghiên cứu sử dụng hàm fitness, các biến đầu vào được thể hiện trong mã nhị phân giống như hình ảnh bộ nhớ của máy. Điểm mạnh 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ỹ thuật kiểm thử thành ba loại: - Kỹ thuật kiểm thử hộp đen (Black - box Testing) hay còn gọi là kỹ thuật kiểm thử chức năng (Functional Testing). - Kỹ thuật kiểm thử hộp trắng (White - box Testing) hay còn gọi là kỹ thuật kiểm thử cấu trúc (Structural Testing). - Kỹ thuật kiểm thử hộp xám (Gray - box Testing). 2.1 Các kỹ thuật kiểm thử phần mềm 2.1.1 Kiểm thử hộp đen Trong kiểm thử hộp đen, cấu trúc và cách xử lý trong chương trình được kiểm tra không quan trọng. Mục đích là đặc tả các điều kiện vào ra của chương trình mà không cần quan tâm đến đặc điểm kỹ thuật của nó. Trong phương pháp này, dữ liệu thử nghiệm cho phần mềm xây dựng từ các đặc điểm kỹ thuật của nó. 2.1.2 Kiểm thử hộp trắng Đây là một ca thiết kế theo phương pháp sử dụng cấu trúc điều khiển của thiết kế thủ tục để lấy ca kiểm thử. 2.1.3 Kiểm thử hộp xám Kiểm thử hộp xám đòi hỏi phải có sự truy cập tới cấu trúc dữ liệu và giải thuật bên trong giống như kiểm thử hộp trắng cho những mục đích thiết kế các ca kiểm thử, nhưng là kiểm thử ở mức người sử dụng hay mức hộp đen. Việc thao tác tới dữ liệu đầu vào và định dạng dữ liệu đầu ra là không rõ ràng, giống như một chiếc “hộp xám”. Do đó, kiểm thử hộp xám là dạng kiểm thử tốt, có sự kết hợp các kỹ thuật của cả kiểm thử hộp đen và hộp trắng. 2.2 Sinh dữ liệu kiểm thử tự động Kiểm thử tự động sẽ kiểm thử được toàn diện, mang lại những lợi ích như: giảm thời gian, công sức, nhân lực và chi phí cho kiểm thử phần mềm. 2.2.1 Sinh các đường dẫn kiểm thử 6 Sinh dữ liệu kiểm thử đường dẫn là kiểm thử hệ thống phần mềm sử dụng một tiêu chí kiểm thử mà có thể phủ đường dẫn, phủ lệnh, phủ nhánh…Hệ thống tự động sinh ra dữ liệu kiểm thử phù hợp với yêu cầu lựa chọn. 2.2.2 Đặc tả dữ liệu Đ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. 3.1 Giới thiệu về thuật toán di truyền Thuật toán di truyền là đại diện điển hình cho những phương pháp và quá trình tìm kiếm mới dựa trên sự phân tích gen và thuyết của Darwin về sự tồn tại của kẻ mạnh nhất (thuyết chọn lọc tự nhiên). Có một sự trao đổi ngẫu nhiên các cấu trúc thông tin trong một quần thể các nhiễm sắc thể nhân tạo. GA là một phiên bản trên máy tính của thuyết tiến hóa sinh học và đã tạo ra được kết quả tốt trong việc giải quyết các vấn đề tối ưu hóa. Trong việc kiểm thử phần mềm, về cơ bản, ý tưởng là tìm kiếm miền cho những biến đầu vào mà thỏa mãn mục tiêu của việc kiểm thử. 3.2 Ứng dụng của thuật toán di truyền Thuật toán di truyền được ứng dụng trong nhiều lĩnh vực. 3.3 Đặc trưng của thuật toán di truyền 3.3.1 Quần thể Một quần thể giống như 1 danh sách có rất nhiều khách (database – cơ sở dữ liệu). Nó chứa các thông tin về những cá thể thành viên. 3.3.1.1 Sự giao thoa và các phương án tối ưu hóa ở mức thấp 3.3.1.2 Chuẩn bị 3.3.1.3 Đại diện/Cách biểu diễn các nhiễm sắc thể 3.3.2 Sự thích nghi Sự thích nghi thể hiện chất lượng của 1 nhiễm sắc thể so với mức tối ưu toàn cục. 8 3.3.3 Sự chọn lọc Toán tử chọn lọc sẽ chọn ra 2 cá thể từ 1 thế hệ để trở thành bố mẹ cho quá trình kết hợp lại bao gồm lai ghép và đột biến. Có nhiều cách khác nhau để chọn lựa cá thể, ví dụ như bằng phương pháp ngẫu nhiên hoặc dựa trên giá trị thích nghi. 3.3.3.1 Chọn lọc dựa trên giá trị phẩm chất 3.3.3.2 Chọn lọc ngẫu nhiên 3.3.4 Lai ghép Lai ghép diễn ra ở mức độ cá nhân. Trước khi quá trình này diễn ra, cá thể có thể được biểu diễn dưới dạng nhị phân. Trong khi lai ghép, 2 bố mẹ sẽ trao đổi các thông tin dưới dạng chuỗi – vật liệu di truyền trong 1 vị trí bất kì trong nhiễm sắc thể để tạo ra 2 chuỗi mới. Quá 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ể . t:= 0 Bắt đầu {Khởi tạo quần thể ngẫu nhiên } Khởi tạo P(t) Khởi tạo quần thể {Khi điều kiện dừng chưa thỏa thì lặp} While not kết thúc Đánh giá sự thích nghi Đánh giá độ thích nghi P(t) Chọn lọc P(t+1) từ P(t) {Kết hợp các gen của cha mẹ Chọn lọc được chọn lọc} Kết hợp P(t+1) với việc sử dụng lai ghép Lai ghép Đột biến và đột biến Tồn tại t:= t + 1 Thủ tục tồn tại {Hết lặp} end. Điều kiện dừng Thỏa Kết thúc Không Hình 3.1 Sơ đồ cấu trúc thuật toán GA 3.5 Kết chương Hình 3.2 Mô phỏng thuật toán GA 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 phương thức mới có hiệu quả và chất lượng cao hơn. Trong trường hợp một quá trình chọn lọc dựa 1 phần trên sự phù hợp thì một quần thể ban đầu được tạo ra ngẫu nhiên với kích thước N sẽ nhanh chóng tạo ra 1 tập hợp với N bản sao của cá thể tốt nhất. GA cân bằng lại sức ép chọn lọc này bằng phương pháp di truyền (lai ghép và đột biến) tiến tới sự đồng hóa bằng cách tạo ra sự đa dạng hóa trong những dạng mới của alen và những tập hợp lại của chúng. 11 CHƯƠNG 4: ÁP DỤNG THUẬT TOÁN DI TRUYỀN SINH CÁC DỮ LIỆU KIỂM THỬ TỰ ĐỘNG 4.1 Áp dụng thuật toán di truyền và số ngẫu nhiên trong kiểm thử phần mềm Thuật toán di truyền hình thành một phương pháp tìm kiếm thích nghi theo nghĩa là thay đổi dữ liệu thử nghiệm từ một thế hệ tiếp theo, để tối ưu hóa hàm fitness. Nó ngược lại với kiểm thử ngẫu nhiên, kiểm thử ngẫu nhiên là tạo ra dữ liệu thử nghiệm mà không cần bất cứ khái niệm nào của dữ liệu trước đó. Trong phần này mô tả sự giao tiếp giữa phần mềm được kiểm tra và công cụ được kiểm tra trong đó sử dụng một trong hai phương pháp: thuật toán di truyền và số ngẫu nhiên. Phương pháp số ngẫu nhiên được sử dụng như là việc thử nghiệm chiến lược để so sánh với thuật toán di truyền. 4.1.1 Thử nghiệm sử dụng kiểm thử ngẫu nhiên Để đo lường hiệu quả của thử nghiệm sử dụng thuật toán di truyền, thử nghiệm ngẫu nhiên được thực hiện. Các thế hệ ngẫu nhiên của kiểm thử được kiểm tra để xác định thành viên của miền con nào đó, với một xác suất đồng nhất liên quan đến lực lượng của miền con. Trong một số trường hợp, cơ hội của kiểm tra hàm, miền con có liên quan tới toàn bộ miền được giảm thiểu. Lúc này, số ngẫu nhiên được sử dụng nhằm sinh ra dữ liệu thử nghiệm mà không sử dụng các thông tin phản hồi từ cuộc thử nghiệm trước đó. Các thủ tục sẽ được thử nghiệm với mong muốn rằng các nhánh sẽ được thông qua. 4.1.2 Cây và đồ thị luồng điều khiển Cấu trúc một chương trình hay thủ tục có thể được thể hiện bằng biểu đồ luồng điều khiển. Xét ví dụ được đưa ra trong hình 4.1 mô tả như sau: 12 1 if A <= B then Read (2); A>B A <= B if A = B then Read (3) Else 5 2 if A < B then read (4) else read (5); A0 4 bac 2 hai’) D <= 0 Else 5 3 D:= B*B-4*A*C; If (D>0) then D≠ 0 D=0 6 7 Writeln 4 (‘phuong trinh 2 (‘phuong trinh co (‘phuong trinh vo nghiem pb’); Else If (D=0) then 5 Writeln nghiem kep’) 6 Else Writeln nghiem’); 7 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 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. Ax 2  Bx  C  0 (4.1) B   2A (4.2) x1, 2 B 2  4 AC 2A D  B 2  4 AC (4.3) Kết quả của phương trình bậc hai phụ thuộc vào mối quan hệ của đại diện trong 4.3. Các nút của cây luồng điều khiển thể hiện cho một chuỗi mã tuyến tính của câu lệnh được chọn lọc. Các nút lá 2, 4, 6 và 7 sẽ kết thúc và cuối cùng sẽ thoát khỏi thủ tục. Các nút quyết định cho lựa chọn thay thế khác nhau mà có kiểu số thực hoặc số phức sẽ được quyết định bởi phương trình 4.3. Nếu các điều kiện là đúng thì các nút con trái sẽ được thực hiện, ngược lại thì nút con phải sẽ được thực hiện. Nút 1, 3, 5 là các nút nhánh và chúng xác định các nhánh tiếp theo được thực hiện hay không là tùy vào điều kiện và dữ liệu đầu vào. Điểm cần chú ý về thủ tục trên là: - Một trong những biến đầu vào là A, tham gia trực tiếp vào điều kiện đẳng thức (A=0) - D là một hàm phi tuyến tính của các biến đầu vào và tham gia hai điều kiện của tổng ba đường dẫn. - D tham gia vào đẳng thức (D=0). Nếu điều kiện A=0 là đúng, nút 2 được thực hiện, nghĩa là biến đầu vào A có giá trị là 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 (ni), ni 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: S N  ni i 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 PSZ Kết quả P1 32 91% trong 31.8 >1214 P2 64 99% trong 19.4 >1294 P3 96 100% trong 13.4 1286 P4 128 100% trong 11.8 1510 P5 160 100% trong 9.1 1456 Ta có thể thấy, với kích thước khác nhau thì kết quả là khác nhau. Việc thực hiện các thử nghiệm khác nhau đưa đến điều tốt là số lượng của các cuộc thử nghiệm là cần thiết nhằm thỏa mãn tất cả các nhánh. 4.2.1.3 So sánh các lai ghép Bảng 4.6 Kết quả sử dụng toán tử lai ghép Xác suất Lai ghép đơn Lai ghép kép 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 phương pháp kia. 4.2.1.4 Đột biến Bảng 4.7 Kết quả sử dụng xác suất đột biến Pm Xác suất của Pm Kết quả Thử nghiệm 0.05 82.2% trong 36.9 >4621 0.025 95.6% trong 28.2 >3011 0.01 100% trong 13.4 1287 0.005 87.4% trong 17.3 >2662 17 0.002 63.2% trong 14.4 >4407 Có thể thấy, xác suất đột biến làm tăng khả năng không tốt, điều này tương tự như việc sinh dữ liệu ngẫu nhiên vì thuật toán di truyền không thể sử dụng điểm mạnh của mình để tạo ra kết quả tốt hơn do sự thay đổi của nhiễm sắc thể là quá lớn. 4.2.1.5 Sử dụng đột biến 4.2.2 Kết quả của phương trình bậc 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 Pc=0.5, kích thước của quần thể PSZ=96, xác suất đột biến Pm=0.01, SURVIVE_5 với PS =0.5 . , xác suất equality PE =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 Function BINARY_SEARCH(x:integer):integer; Var Low, High, Mid: integer; 1 C A(MID)=x return 5 Tim_thay: boolean; Begin A(MID)x While (Low <= High) and not (Tim_thay) do 4 Begin Mid := (Low + High) div 2; L End binary While lặp Node L = 6: 1 lần Node L = 7 : 2 lần Node L = 8 : > 2 lần If A[Mid] = x then Tim_thay:= true Else If a[Mid] < x then Low := Mid +1 Else High := Mid – 1; End; If Tim_thay then BINARY_SEARCH := Mid Else BINARY_SEARCH := 0; End; Hình 4.3 Cây luồng điều khiển và chương trình phần mềm cho tìm kiếm nhị phân 4.3.2. Kết quả của thủ tục tìm kiếm Khi điều kiện vòng lặp ‘while…do’ phụ thuộc vào chỉ số mảng, nó không thể kiểm tra cho 0 lần lặp trừ khi định nghĩa về mảng thay đổi. Chiến lược của thử nghiệm là lặp đi lặp lại 1 lần, 2 lần hoặc nhiều hơn 2 lần lặp. Kết quả của những thí nghiệm này được mô tả trong bảng 4.8 Bảng 4.8 Kết quả của thủ tục tìm kiếm nhị phân cho kiểm thử vòng lặp Hàm fitness nghịch đảo SELECTION_R mã 5 bit 66.4% trong 53 SELECTION_F 10 bit 5 bit 98.8% trong 45.4 61.6% trong 66.6 10 bit 95.6% trong 45.7