A Bee Colony Optimization Algorithm Biology Essay

Published:

Regression testing is the verification process of modified software in the maintenance phase. Due to budget and time constraints regression test suite size and its selection is a critical issue. A Bee Colony Optimization (BCO) algorithm for the regression test suite prioritization has been developed and is presented in this paper. The behavior of two types of bees; scout bees and forager bees have been used to prioritize the test suite. The proposed algorithm has been explained using examples on total fault detection in time constrained environment and total code coverage. Average Percentage of Fault Detection (APFD) metric has been used to show the effectiveness of algorithm proposed.

After development and release, software undergo regress maintenance phase of ten to fifteen years. Modifications in software may be due to change in customer's requirements or change in technology/platform. These reasons lead to the release of numerous versions/editions of the existing software. Development time and budget of a software permits for its thorough testing but same is not the case for regression testing. Also in case of the version/edition's test only modified and affected parts are to be tested to impart confidence in the modified software. So effective and intelligent reordering/prioritization of the actual software's test suite has to be done to make remarkable savings of time and budget, in the testing of the modified software's version.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Several attempts have been made in finding techniques/algorithms for the regression test suite prioritization. Many algorithms such as Greedy algorithms, non-evolutionary algorithms, evolutionary algorithms, searching algorithms etc have been used. Searching Algorithms are algorithms in which we search the required piece of information (based some criteria which is the solution to our problem) in the available sample space. So searching algorithms will be very useful and helpful in searching the test cases for regression test suite. One system which is based on searching algorithm is the Bee Colony System which have been studied and mapped to find the ordering of the modified software test suite.

Automated software testing has long been an area of concern for big software development companies. In automation testing development and execution of test cases can be done unattended. Also, comparison of actual results to expected results and logging status can be determined. It is the automation of the manual testing process. It improves accuracy; increases test coverage, saves time and money and helps developers and testers to develop test cases quickly and efficiently. This algorithm automates the test suite prioritization process as per the bee colony optimization criteria.

Organization of the paper is as follow. Related work is presented in section 3, BCO method has been explained in section 4. Section 5 presents the formalised BCO algorithm for regression test suite prioritization, in section 5.1 the explanation of the algorithm is given, 5.2 presents the prioritization of test cases based on total fault coverage with examples, 5.3 presents the prioritization of test cases based on total code coverage with an example demonstrating the working of the BCO algorithm. Section 6 gives the comparision of various prioritization approaches to BCO. And finally in the succeeding sections threats to validity, conclusion and futute work are presented.

3. RELATED WORK

Bee Colony Optimization is an emerging field for researchers. It has been applied to areas like "Optimization Algorithms"[18],"Travelling Salesman Problem"[20],"Job Shop Scheduling problem"[22],"Combinatorial Techniques like Generation of pair-wise test sets"[23]," Solving Sudoku Puzzles "[27]," Routing Algorithm" [29].

4. BEE COLONY OPTIMIZATION (Natural Phenomenon of Bee Colony)

Bee Colony Optimization is the name given to the colony formed by the mutual understanding of the natural bees in the food foraging process. In spite all the creatures on this earth follow one or the other mechanism/process to find food that suite them and these mechanism are found in insects like ants, bees or cockroaches.

Honey bee comb build-up and management is a classic example of teamwork, experience, co-ordination and synchronization. The way the honey bees find, build and maintain their comb and hive is remarkable. These are the factors which have given rise to interest of researchers to find solutions to their problems.

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

In a natural honey bee hive there are a variety of bees with specific role(s) to perform. There are three types of bees:

Queen Bee (one)

She is responsible to lay eggs which are used to build new colonies.

Male Drone Bees(many)

These are responsible for mating with the queen bee.

Worker Bees(thousands)

These bees perform all the maintenance and management jobs in the hive. There are two types of worker bees, namely scout bees and forager bees, which perform the scout behavior and forager behavior respectively, which are collectively responsible for the working of the honey bee colonies.

1. The Scout Behavior

In the scout behavior there are following steps:

The scout bees start from the hive in search of food source randomly.

They keep on this exploration process until they are out of energy/tired and return back to the hive.

When they return back to the hive, they share their experience and knowledge with the forager bees by performing the mechanism called "waggle dance".

It is the means by which the bees communicate. It is used to convey the parameters like foods Source Quality, distance of food source from hive, Location of food source w.r.t. sun, to guide the path to the available forager bees.

These steps of the scout bees constitute the first step of the BCO process called the "Path Construction".

2. The Forager Behavior

In the Forager behavior, the forger bees do the following:

The Forager bees observe and learn the steps done by the scout bees while waggling so as to ease their journey.

Then these forager bees go to the food sources as guided by the scout bees to exploit them

These forms the second step of the BCO process called the "Path Restructuring".

5. PROPOSED ALGORITHM

Artificial bee colony system has been modeled in [1]. This paper presents a new optimization algorithm that maps the food foraging behavior of natural bees as a procedure to prioritize regression test suite's test cases. This algorithm takes the test cases as food sources, the number of faults detected upon execution time of each test case as the food source quality and number of test cases as the number of scout bee plus number of forager bees which makes the initial population.

Following is the basic flow of the BCO Algorithm:

Figure1. Basic flow of BCO Algorithm

Following is the list of notations that are being used in the proposed algorithm

Nbee : Total number of bees (Initial Population)

NSB : Number of scout bees

NFB : Number of forager bee

Ei : Energy at ith iteration

FSQi : ith Food Source Quality

SBi : ith Socut Bee

FBi : ith Forager Bee

PSBi : Path of SBi

PFBi : Path of FBi

ET : Execution time of test case

FC : Number of Faults covered

In the execution of the algorithm two tables will be formed.

PSB Table

Path of Scout Bee table, as seen in table 2, 5, 8 contains all the paths visited (explored) by the SB. It is used for the path construction phase of SB. This table will act as input for the path restructuring phase which is done by FB.

PFB Table

Path of Forager Bee table, as seen in table 3, 6, 9 contains all the paths selected (exploited) by the FB. An account of the total ET of each path is also kept in this table. This table helps in final path selection.

Following are the proposed algorithm's main steps

1) Initializations

Nbee = NSB + NFS

NSB = NFB = number of test cases in the test suite under test.

E0 = 100%.

2) Assumptions

The food sources have been identified.

The distance between hive to food source, food source to food source, food source to hive is unity.

Any food source is visited only once.

Each SBi will start the random search from ith food source.

Each FBi will exploit only SBi path.

E0 (Initial energy level of of SB and FB) is 100%.

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

Energy reduction rate is set up such that only 50% of the test suite gets executed.

FSQi==

Stopping criteria

Total number of faults covered

Ei = 0 ; Ei =1- i*energy reduction rate

3) Algorithm

START

Repeat NSB times(Path construction)

{

Repeat until stopping criteria is met

Each SBi starts exploring from ith food source and forms PSBi (table 1).

}

(2) Repeat NFB times (Path Structuring)

Each FBi starts exploiting PSBi to form PFBi (table 2)

(3) Final Path Selection

Choose path PFBi with minimum ET

STOP

Explanation of the BCO algorithm

1. Path construction

This is the first step in the execution of the algorithm. This step is executed by the scout bees, NSB times, in order to explore all the food sources (Test Case) available. The SBi starts its exploration process from the ith food source (Test Case). After this they explore the Test Cases randomly until any one of the stopping criterion is met. Each path PSBi constructed by the SBi is entered into the PSB table.

2. Path Restructuring

In the next step the forager bees exploit the PSBs. This step uses the PSB table as input. Each FBi starts exploiting the PSBi to form the PFBi. Here each FBi chooses the test case (food source) with best FSQi value. The succeeding test cases are chosen such that which detects faults those are not detected by the existing test cases. The condition makes sure that only those test cases are executed which are effective in fault detection and total fault coverage (stopping criteria). Also the summation of the ET of all the test cases present in a particular PFBi is done to get that path's total ET. All these entries are maintained in PFB table.

3. Path Selection

This is the final step of the algorithm done by the FBi. From the PFB table select the PFBi with minimum Total ET.

5.1 Prioritization of test cases based on total fault coverage

In this technique the test cases are prioritized in such a manner so as to achieve total fault coverage within minimum execution time. To ensure that all the faults are covered by the test cases selected in the prioritized ordering we use mutation testing. In this we deliberately alter a program's code, then re-run a suite of valid tests against the mutated program.  A good test will detect the change (fault) in the program and fail accordingly. Thus, the proposed algorithm's effectiveness is measured using mutation testing. This is illustrated by two examples in which mutants are created.

5.1.1 Example 1 (Based on Total Fault Detection)

The problem taken is "college program for admission in courses". The problem specification is available at website http://www.planet-source-code.com.

In this example a test suite has been developed which consisted of 35 test cases. For simplified explanation of the working of the algorithm, a test suite with 9 test cases is considered in it, covering a total of 5 faults.

The regression test suite contains 9 test cases with default ordering {T1, T2, T3, T4, T5, T6, T7, T8, T9}, the faults covered (FC) by each test case, the execution time (ET) required by each test case in finding faults and food source quality (FSQ) are as shown in Table 1. Equal priority is given to the number of faults covered and minimum execution time in selecting test cases.

Table 1: Test cases with the faults covered, execution time and Food Source Quality.

Test Case

F1

F2

F3

F4

F5

FC

ET

FSQi

T1

X

X

X

X

4

11.5

.34

T2

X

X

2

11.5

.17

T3

X

X

X

3

12.33

.24

T4

X

X

X

3

10.66

.28

T5

X

1

15

.06

T6

X

X

X

3

8.33

.36

T7

X

1

15

.06

T8

X

X

X

3

10

.30

T9

X

1

11

.09

Step 1. Scout Bee Performs Path Construction and creates PSB TABLE 2

Table 2:Path Constructed by scout bee. (Path of scout bee table).

SBi

PSBi

SB1

T1

T6

T7

T4

SB2

T2

T1

T9

T4

SB3

T3

T1

T6

T8

SB4

T4

T3

T5

T7

T2

SB5

T5

T1

T4

SB6

T6

T3

T5

T7

T2

T4

SB7

T7

T6

T3

T9

T1

T8

SB8

T8

T1

SB9

T9

T5

T7

T8

T3

Step 2. Forger Bee Performs Path Restructuring and creates PFB TABLE 3

Table 3:Path restructured by Forager bee. (Path of forager bee table).

FBi

PFBi

Total ET

FB1

T6

T1

T4

30.49

FB2

T1

T4

22.16

FB3

T6

T1

T8

29.83

FB4

T4

T3

T2

34.49

FB5

T1

T4

22.16

FB6

T6

T4

T2

30.49

FB7

T6

T1

T8

29.83

FB8

T1

T8

21.5

FB9

T8

T3

22.33

Step 3. Forger Bee Performs Final Path selection

Hence PFB8 with test cases T1 T8 forms the prioritized test suite for the given problem.

5.1.2 Example 2 (Based on Total Fault Detection)

Another problem specification for "Hotel Reservation" which reserves the rooms in hotel and maintains the record. The complete problem specification is available at the website http://www.planet-source-code.com.

In this example a test suite has been developed which consisted of 40 test cases. For simplified explanation of the working of the algorithm, a test suite with 5 test cases is considered in it, covering a total of 5 faults.

The regression test suite contains 5 test cases with default ordering {T1, T2, T3, T4, T5}, the faults covered (FC) by each test case, the execution time (ET) required by each test case in finding faults and food source quality (FSQ) are as shown in Table 4. Equal priority is given to the number of faults covered and minimum execution time in selecting test cases.

Table 4: Test cases with the faults covered, execution time and Food Source Quality.

Test Case

F1

F2

F3

F4

F5

FC

ET

FSQi

T1

x

x

x

3

12.2

.2459

T2

x

1

10

.10

T3

x

x

x

3

10.67

.28

T4

x

1

7

.14

T5

x

x

x

x

4

9.97

.40

Step 1. Scout Bee Performs Path Construction and creates PSB TABLE 5

Table 5:Path Constructed by scout bee. (Path of scout bee table).

SBi

PSBi

SB1

T1

T2

T3

T4

SB2

T2

T3

T5

SB3

T3

T1

T2

T5

SB4

T4

T3

T2

T5

SB5

T5

T3

Step 2. Forger Bee Performs Path Restructuring and creates PFB TABLE 6

Table 6:Path restructured by Forager bee. (Path of forager bee table).

FBi

PFBi

Total ET

FB1

T3

T1

22.87

FB2

T5

T3

20.64

FB3

T5

T3

20.64

FB4

T5

T3

20.64

FB5

T5

T3

20.64

Step 3. Forger Bee Performs Final Path selection

Hence PFB2 with test cases T5 T3 forms the prioritized test suite for the given problem.

5.2 Prioritization based on Total Code Coverage

Prioritization based on structural testing allows prioritize/reorder the test cases based on the internal workings of the code. Structural testing is also called path testing since test cases are chosen that cause paths to be taken from different parts (structure) of the program. There are certain levels of coverage in path testing namely statement coverage, branch coverage, condition coverage and path coverage. Each level of coverage indicates the level of testing. As we move towards the higher level, more difficult and complete the testing process becomes. The aim of path testing is to attain the highest level of coverage that is condition coverage.

The logical flow of a program can be analysed using graphical representation known as the flow graph. Flow graph generation is the first step of path testing. Then the decision to decision (DD) path graph is generated from the flow graph. It is used to find independent paths. In DD path graph all the sequential nodes are clubbed into a single node leaving behind the decision nodes. An independent path is any path through the DD path graph that introduces at least one new statement node or condition node. Therefore, we need to execute all the independent paths at least once during the process of path testing.

5.2.1. Example 1(based on Total Code Coverage)

The example taken for code coverage is the triangle problem which takes the three sides (a positive integer in the range of 0 to 100) of the triangle as input and gives the output as scalene, isosceles, equilateral, not a triangle and invalid inputs according to the input. [3].The test cases are generated according to robust value testing. The test cases, outputs, statements, conditions and independent paths covered are shown in the table 7.

Table 7: Test cases with inputs and outputs

TEST CASE NO.

X

Y

Z

EXPECTED OUTPUT

INDEPENDENT PATH

CONDITION COVERED

NODES COVERED

STATEMENT COVERED

1

50

50

0

INVALID INPUT

abfgnpqr

3

8

21

2

50

50

1

ISO

abcdeghjkmqr

5

12

23

3

50

50

2

ISO

abcdeghjkmqr

5

12

23

4

50

50

50

EQUI

abcdeghimqr

4

11

22

5

50

50

99

ISO

abcdeghjkmqr

5

12

23

6

50

50

100

NT A TRI

abcdegnoqr

4

10

21

7

50

50

101

INVALID INPT

abcegnpqr

4

9

20

8

50

0

50

INVALID INPT

abfgnpqr

3

8

21

9

40

20

30

SCALENE

abcdeghjlmqr

5

12

24

10

50

1

50

ISO

abcdeghjkmqr

5

12

23

11

50

2

50

ISO

abcdeghjkmqr

5

12

23

12

50

99

50

ISO

abcdeghjkmqr

5

12

23

13

50

100

50

NT A TRI

abfgnoqr

3

8

20

14

50

101

50

INVALID INPT

abcegnpqr

4

9

21

15

0

50

50

INVALID INPT

abfgnpqr

3

8

21

16

1

50

50

ISO

abcdeghjkmqr

5

12

23

17

20

40

30

SCALENE

abcdeghjlmqr

5

12

24

18

80

50

80

EQUI

abcdeghimqr

4

11

22

19

100

50

50

NT A TRI

abcdegnoqr

4

9

21

20

101

50

50

INVALID INPT

abcegnpqr

4

9

21

Step 1. Scout Bee Performs Path Construction and creates PSB TABLE 8

Table 8:Path Constructed by scout bee. (Path of scout bee table).

SBi

PSBi

SB1

T1

T3

T19

T17

T18

T13

T14

SB2

T2

T15

T4

T6

T7

T9

T13

T18

T16

SB3

T3

T1

T13

T9

T20

T19

T18

T12

SB4

T4

T13

T17

T20

T19

T18

T2

T15

T8

SB5

T5

T6

T7

T8

T10

T12

T18

T20

13

T16

SB6

T6

T19

T1

T8

T15

T2

T3

T5

T10

T12

SB7

T7

T1

T8

T16

T20

T18

T13

T9

T2

SB8

T8

T2

T4

T6

T7

T9

T13

SB9

T9

T17

T1

T8

T15

T10

T11

T12

T16

T19

SB10

T10

T20

T1

T5

T15

T13

T16

T17

T18

T2

SB11

T11

T1

T2

T3

T6

T8

T9

T10

T7

T13

SB12

T12

T1

T12

T4

T19

T7

T17

T18

T13

SB13

T13

T9

T7

T6

T18

T5

T8

SB14

T14

T1

T2

T8

T6

T8

T9

T10

T7

T13

SB15

T15

T20

T13

T3

T5

T7

T11

T17

T18

T9

SB16

T16

T15

T14

T19

T18

T13

T17

T20

SB17

T17

T6

T13

T18

T20

T2

T1

SB18

T18

T1

T2

T3

T4

T18

T6

T19

T13

T17

SB19

T19

T16

T9

T1

T18

T13

T20

SB20

T20

T2

T3

T5

T13

T19

T18

T16

T1

T3

Step 2. Forger Bee Performs Path Restructuring and creates PFB TABLE 9

Table 9:Path restructured by Forager bee. (Path of forager bee table).

FBi

PFBi

FB1

T3

T17

T18

T19

T14

T1

T13

FB2

T2

T9

T4

T6

T7

T15

T13

FB3

T3

T9

T20

T19

T18

T1

T13

FB4

T2

T17

T18

T19

T20

T15

T13

FB5

FB6

FB7

FB8

T2

T9

T4

T6

T7

T8

T13

FB9

FB10

FB11

FB12

FB13

T9

T5

T18

T6

T7

T13

T8

FB14

FB15

FB16

FB17

T17

T2

T18

T20

T6

T13

T1

FB18

FB19

T9

T16

T19

T18

T20

T1

T13

FB20

Step 3. Forger Bee Performs Final Path selection

Hence following are the final prioritization

FB1 T3 T17 T18 T19 T14 T1 T13

FB2 T2 T9 T4 T6 T7 T15 T13

FB3 T3 T9 T20 T19 T18 T1 T13

FB4 T2 T17 T18 T19 T20 T15 T13

FB8 T2 T9 T4 T6 T7 T8 T13

FB13 T9 T5 T18 T6 T7 T13 T8

FB17 T17 T2 T18 T20 T6 T13 T1

FB19 T9 T16 T19 T18 T20 T1 T13

We are getting so many paths because there is no ET in this example. Otherwise the path with mini ET could have been chosen.

6. COMPARISION

The examples mentioned in sections 5.1 and 5.2 are compared with respect to the following ordering: No order, Reverse order, Random order, Optimal order of the test cases. The orderings with respect to these approaches for example 1 and 2 are listed in Table 10 and 11 respectively. These approaches are compared by calculating Average Percentage of Faults Detected (APFD) [4] which is given by APFD =

Where, T - The test suite under evaluation

m - The number of faults contained in the program under test P

n - The total number of test cases and

TFi - The position of the first test in T that exposes fault i.

The results are shown in fig. 2 to fig. 11. It shows that the APFD values for the prioritization achieved using BCO are comparable to that obtained with the optimum ordering.

Table 10. Order of test cases for various prioritization approaches for example 1.

No Order

Reverse Order

Random Order

Optimum Order

BCO

Order

T1

T9

T3

T8

T1

T2

T8

T7

T6

T8

T3

T7

T1

T5

T6

T4

T6

T5

T4

T3

T5

T5

T4

T1

T5

T6

T4

T2

T7

T2

T7

T3

T6

T3

T4

T8

T2

T9

T2

T9

T9

T1

T8

T9

T7

Fig. 2 APFD chart for original ordering of test cases of example 1. Fig. 3.APFD chart for random ordering of test cases of example 1.

Fig. 4.APFD for reverse ordering of test cases of example 1. Fig. 5.APFD chart for optimal ordering of test cases of example 1.

Fig. 6.APFD chart for ordering using BCO Prioritization order of test cases of example 1.

Table 11.Order of test cases for various prioritization approaches for example 2.

No Order

Random Order

Reverse Order

Optimum Order

BCO

Order

T1

T2

T5

T5

T3

T2

T1

T4

T3

T5

T3

T5

T3

T4

T2

T4

T3

T2

T1

T1

T5

T4

T1

T2

T4

Fig. 7 APFD chart for original ordering of test cases of example 2 Fig. 8 APFD chart for random order of example 2

Fig. 9 APFD chart for optimal order of example 2 Fig. 10 APFD chart for reverse of example 2

Fig. 11 APFD chart for BCO of example 2

7. THREATS TO VALIDITY

The artificial BCO algorithm which has been presented here has certain short comings which are as follows:

In the natural BCO the number of scout bees is 5-10% of forager bees which are assumed to be equal in the algorithm proposed here.

The concept of waggle dance was not required so has not been incorporated in the algorithm which is used s a means of communication in the natural BCO.

The energy reduction rate has been chosen such that only 50% of the test suite gets executed which leaves the remaining test suite unexplored. Since it executes upto 50% of the test suite, manual execution of small test suites is possible. As the size of test suite increases the manual execution of the test suite becomes difficult and cumbersome.

8. CONCLUSION and FUTURE WORK

An artificial bee colony optimization algorithm for the regression test suite prioritization has been developed. This algorithm makes effective use the path construction (exploration) and path structuring (exploitation) phenomenon of scout bees and forager bees for the prioritization of the test suite of the modified code. The effectiveness of this algorithm has well been demonstrated using APFD values which are comparable to the optimal ordering values.

Firstly, all the shortcomings mentioned above will be overcome. Due to the manual execution of the algorithm, it has been applied to test suites with less number of test cases. But it has also been observed that this algorithm's results are comparable to optimal ordering results. So to apply it in real situation/ larger programs, there is a need to automate this algorithm. Therefore an automation tool for the complete usage of the algorithm is being developed.

9. REFRENCES

[1]Hussein Owaied, Saif Saab: Modeling Artificial Bees Colony System.IC-AI: pp.443-446 (2008).

[2] Dorigo, M.; Maniezzo, V.; Colorni, A. (1991): The Ant System: An Autocatalytic Optimizing Process, Technical Report TR91-016, Politecnico di Milano.

[3] Aggarwal, K.K.; Singh, Y.: A book on software engineering.

[4]Kristen R.Walcott, Gregory M.Kapfhammer, Mary Lou Soffa, Robert S. Roos"Time-aware test suite prioritization".

[29] Rahmatizadeh, Sh., H. Shah-Hosseini and H. Torkaman, 2009. The ant-bee routing algorithm: A new agent based nature-inspired routing algorithm. J. Applied Sci,983- 987.

[20] li-pei wong, Malcolm yoke hean low, chin soon chong,"A bee colony optimization algorithm for travelling salesman problem", Second Asia International Conference on Modelling & Simulation.

[22] Chin Soon Chong, Appa Iyer Sivakumar, Malcolm Yoke Hean Low, Kheng Leng Gay, "A bee colony optimization algorithm to job shop scheduling", Winter Simulation Conference.

[18] Saif Mahmood Saab, Dr. Nidhal Kamel Taha El-Omari, Dr. Hussein H. Owaied," Developing Optimization Algorithm Using Artificial Bee Colony System."

[23] James D. McCaffrey,"Generation of pairwise test sets using a simulated bee colony algorithm" 10th IEEE international conference, 2009.

[27] Jaysonne A. Pacurib, Glaiza Mae M. Seno, John Paul T. Yusiong, "Solving Sudoku Puzzles Using Improved Artificial Bee Colony Algorithm," Innovative Computing, "Information and Control, International Conference on, pp. 885-888, 2009 Fourth International Conference on Innovative Computing, Information and Control, 2009.

[19] Dervis Karaboga, Bahriye Basturk,"A powerful and efficient algorithm for numerica function optimization: artificial bee colony (ABC) algorithm", J Glob Optim (2007)