Artificial Bee Colony Algorithm To Software Testing Computer Science Essay

Published:

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

Abstract: Swarm intelligence is an emerging area in the field of optimization. Many researchers have developed various meta-heuristics algorithms by modeling the behaviors of different swarm of animals and insects such as ants, termites, bees, birds, fishes. The Artificial Bee Colony (ABC) algorithm which is also a swarm based meta-heuristic algorithm, based on the intelligent foraging behavior of honey bees, which have been introduced for optimizing various numerical problems. This paper presents a review of application of artificial bee colony algorithm in the field of software testing.

Keywords: Swarm Intelligence, Artificial Bee colony algorithm, software testing.

INTRODUCTION

Swarm intelligence is the discipline which deals with the natural and artificial systems composed of many individuals which coordinate using decentralized control and self-organization. The discipline mainly focuses on the collective behaviors that result from the local interactions of the individuals with each other and with their environment. Examples of swarm based meta heuristics algorithms are Ant colony Optimization, Particle Swarm Optimization, Artificial Bee colony Optimization etc. Artificial bee colony is one of the most recently defined algorithms by Dervis Karaboga in 2005, which is based on the intelligent foraging behavior of honey bees. Artificial bee colony algorithm has been applied in various fields. It also finds application in the field of software testing. Software testing is one of the most indispensible process of the software development lifecycle for ensuring the quality of software product.

This paper, in the first section first gives a brief introduction about the nature of bees. Section 2 describes the artificial bee colony algorithm. Section 3 presents a review of application of artificial bee colony algorithm in the field of software testing.

I. BEES IN NATURE

A. Components of Bee Colony

The bee ( Apis Mellifera ) is a social and domestic animal native to Europe and Africa. Bees are adapted for feeding on nectar and pollen. Nectar is a prime source of energy and pollens are primarily for protein and other nutrients. Most pollen is used as food for larvae. [1]. Generally the bee colony consists of a female bee called Queen bee, thousands of males called drones, a several thousands of sterile females called workers and many young bee larvae called broods.

B. Bees Dance and Communication

Bees returning to the beehive after finding a good supply of food will communicate to other bees by dancing in the comb on the dance floor. When a foraging bee finds food close to the beehive, it performs its simplest dance, the round dance. This dance indicates only the direction. When the food source is far from the beehive, bees perform another type of dance, the waggle dance. It is a dance which forms an eight figure. This dance indicates distance and direction of the food source. The distance between the food source and the hive is communicated by the speed of the dance. If the dance is faster then the food distance is smaller. The direction ( angle between the food source and sun, relative to hive) is shown by the inclination of the dance[2].

II Artificial bee colony algorithm

In the ABC algorithm, the colony of artificial bees contains three types of bees: employed bees, onlookers and scouts. A bee waiting on the dance area for making decision to choose a food source, is called an onlooker bee and a bee going to the food source visited by itself previously is named an employed bee. A bee carrying out random search is called a scout bee. In the ABC algorithm, the first half of the colony consists of employed artificial bees and the second half consist of the onlooker bees. For every food source, there is only one employed bee. In other words, the number of employed bees is equal to the number of food sources around the hive. The employed bee whose food source is exhausted by the employed and onlooker bees becomes a scout [3]. After locating the food source, the bee utilizes its own capability to memorize the location and then immediately starts exploiting it. The foraging bee takes a load of nectar from the source and returns to the hive and unloads the nectar to a food store. After unloading the food, the bee has the following three options [4]:

It becomes an uncommitted follower after abandoning the food source.

It dances and then recruits nest mates before returning to the same food source.

It continues to forage at the food source without recruiting other bees.

The basic steps of the algorithm are as follows [4]:

1. Send the scouts onto the initial food sources

2. REPEAT

Send the employed bees onto the food sources and determine their nectar amounts.

Calculate the probability value of the sources with which they are preferred by the onlooker bees.

Send the onlooker bees onto the food sources and determine their nectar amounts.

Stop the exploitation process of the sources exhausted by the bees.

Send the scouts into the search area for discovering new food sources, randomly.

Memorize the best food source found so far

3. UNTIL (requirements are met).

The search consists a cycle of three steps: moving the employed and onlooker bees onto the food sources and calculating their nectar amounts and determining the scout bees and directing them onto possible food sources. At the beginning a set of food source positions are randomly selected by the bees and the amount of nectar is determined. Then, these bees come back to the hive and share the information of the sources with onlooker bees. In the next stage, after sharing the information, every employed bee goes to the food source visited by her in the previous cycle and then chooses a new food source by means of visual information in the neighborhood of the present one. In the third stage, an onlooker bee visits a food source area depending on the nectar information distributed by the employed bees. The onlooker bee selects a food source with maximum nectar quantity. After arriving at the selected area, she chooses a new food source in the neighborhood of the one in the memory depending on visual information positions. When the nectar of a food source is abandoned by the bees, a new food source is randomly determined by a scout bee and replaced with the abandoned one.

An onlooker bee chooses a food source depending on the probability value associated with that food source, pi, calculated by the following expression [3]:

fiti

pi = ----------

SN

∑ finn

n=1

where fiti is the fitness value of the solution i evaluated by its employed bee, which is proportional to the nectar amount of the food source in the position i and SN is the number of food sources which is equal to the number of employed bees ( BN) .

In order to produce a candidate food position from the old one, the ABC uses the following expression [3]:

vij = xij + φij(xij − xkj),

where k € {1, 2, . . . , BN} and j € {1, 2, . . . ,D} are randomly chosen indexes. Although k is determined randomly, it has to be different from i, φi, j is a random number between [−1, 1]. It controls the production of a neighbour food source position around xi,j and the modification represents the comparison of the neighbour food positions visually by the bee.

III. APPLICATION OF ABC ALGORITHM TO SOFTWARE TESTING

The ABC algorithm was proposed for unconstrained optimization problems and showed that it has superior performance on these kinds of problems [3].

Software testing is one of the multi-variable optimization problems in which generation and selection of efficient test cases cannot be solved within bounded times. Hence meta-heuristic search algorithms have been applied to solve these types of problems to find near optimal solutions in reasonable running times. The artificial bee colony based swarm intelligence algorithm is a search algorithm capable of locating good solutions efficiently. The algorithm is inspired by the food foraging behavior of honey bees. The major objective of software testing is to uncover as many errors as possible in a given timeline, as this would help in demonstrating that the product is matching its requirement specifications and to validate the quality of a software testing using minimum cost and efforts and to generate high quality test cases which would perform effective tests, and issue correct and helpful problem reports [5].

D Jeya Mala [6] applied the artificial bee colony algorithm for test suite optimization, in which each test case represents a possible solution in the optimization problem and happiness value which is a heuristics introduced to each test case corresponds to the quality or fitness of the associated solution. In this model the employed, onlooker and scout bees were replaced by search agent, optimizer agent and selector agent. Agents exhibit autonomy, social ability and inter operability to perform the task [7].

The three agents help in selecting efficient test cases among near infinite number of test cases. All the three agents' works in parallel, hence the solution generation becomes faster and makes this approach very efficient. The test adequacy criteria used in this is based on path coverage. Initially random population of test cases is generated for all test sequence. The search agent monitors each test case as it goes to an executable state in the test path and determines a neighbor state. Then it updates the happiness value of each test case depending upon its feasibility. If a node is not feasible or not covered by the particular test case then the node is removed from memory and the selector starts a new search. Based on that, a happiness value or coverage measure is associated with each test case. A test case with highest happiness value or coverage measure is remembered and all the other test cases are removed. The Optimizer Agent watches the happiness value of each test case and chooses one of them. After choosing a neighbor around that, it evaluates its happiness value. Abandoned test cases are determined and then, they are replaced with the new test cases discovered by the Selector Bee. The best test case found so far is stored in the optimized test case repository for regression testing. Repeat until all the nodes have been visited at least once.

D Jaya Mala compared this approach with Ant colony Optimization and proved that the ABC based approach provides consistent results and does not have any problem as compared to the problems in ACO like continuous pheromone updation, computational time and memory overheads.

James D McCaffrey [8] generated pairwise test sets using a simulated bee colony algorithm. He then compared the results to the published results of seven benchmark problems and found that the simulated bee colony approach produced test sets which were comparable or better in terms of size for all the seven problems. However, the simulated bee colony approach took significantly longer generation time than deterministic approaches in all cases. Pairwise testing is a combinatorial technique which selects a subset of all possible test case input combinations [9]. A pairwise test set consists of a collection of test vectors which capture all possible combinations of pairs of values from different parameters. The pseudo-code logic for an active foraging bee is as follows [8]:

-------------------------------------------------------------------------

if (role == Active)

(leave hive, go to food source)

examine a neighbor food source

if (quality >= current quality)

current memory := neighbor location

numberVisits := 0

else

numberVisits := numberVisits + 1

endif

(return to hive)

if (numberVisits == maxNumberVisits)

role := Inactive

numberVisits := 0

else

perform waggle dance to hive

endif

endif

-------------------------------------------------------------------------

An individual bee is modeled as a bee object with four data fields [8]. The first field is an enumeration type which specifies the role of the bee object is currently in. Different role types are Active, Scout, and Inactive. The second field in the Bee object definition is a two-dimensional array which represents a bee's memory, which in turn helps in representing a potential solution to the test set generation problem. The third field in a Bee object definition is an integer value which represents the quality of the food source associated with the data in the bee's memory. The fourth field represents the number of times the Bee object has visited a particular food source, without finding a neighbor food source which has a higher quality value. The algorithm in this study used a fixed value for the maximum number of times any active foraging bee will visit a food source. Although the proposed algorithm yielded good results in terms of test set size, but the performance was significantly slower than deterministic algorithms in all cases.

D Jeya Mala [ 10] proposed the use of parallel behavior of the three bees for software test optimization. Since the ABC system combines local search methods carried out by employed and onlooker bees with global search methods conducted by scouts, the approach attains global or near-global optima. Here, the parallel behavior of the three bees is used to reach the solution generation faster. The performance of the proposed approach is investigated based on coverage-based test adequacy criteria by comparing it with sequential ABC, random testing and genetic algorithm-based approaches. The agents used in the proposed model are search agent, selector agent and replace agent.

After the experiments it has been confirmed that the proposed parallel ABC outperforms all the other approaches. The experimental results show the problems with GA which includes nonmemorisation of individuals, non-linear optimisation, risk of suboptimal solution and delayed convergence. Also, there is no guarantee for global optimal solution even when it may be reached. The problem with sequential ABC is that it forces a sequential selection approach in the optimization process, which makes it to perform poorly when compared to GA. On the other hand, parallel ABC-based test suite optimization generates global or near-global optimal results and it converges within less number of test runs.

S S Dahiya [11] presented an artificial bee colony based approach for automatic generation of structural software tests. Test cases are symbolically generated by measuring fitness of individuals with the help of branch distance based objective function. The paper presented an Artificial Bee Colony (ABC) based search algorithm for generating test data using symbolic execution method. The working of the honeybee colony is reported as robust and adaptive by [12]. This motivates them to use ABC for path testing. The pseudo code for honey bee algorithm is as follows [11].

-------------------------------------------------------------------------

1. Initialize the random population of solutions Xij (flower patch positions).

2. Evaluate the population

3. Produce new solutions Yij in the neighborhood of Xij for the employed bees by using following equation.

Yij = Xij + φij * ( X ij - Xkj )

Where φij is a random number between 0 to 1 and Xkj is a

randomly selected solution.

4. Apply the greedy selection process between Yij and Xij.

5. Calculate the probability values pi for the solutions Xi by

means of their fitness values,

fitnessi

pi = ------------------

∑n fitness i

j=1

6. Produce new solutions (new positions) for the onlookers from the solutions Xi depending on probability pi and evaluate them.

7. Apply the greedy selection process between the new and old solution.

8. Determine the abandoned solution (source), if exists, and

replace it with a new randomly produced solution for the scout.

9. Memorize the best food source position (solution) achieved so far.

10. Repeat step 3 to 9 until the termination criterion is reached.

-------------------------------------------------------------------------

For test data generation, initially a random population of candidate solutions is generated from the inputs' domains [11]. In ABC the solutions are represented by the position of flower patches. The optimum positions of flower patches are searched out in such a way so that positions of these can satisfy the targeted path constraint system. Corresponding to each flower patch, its profitability is measured. In computer modeling, this profitability is represented by the fitness of the position. The ABC algorithm works in three phases. First phase is called the employed phase, where employed bees modify the position of elite flower patches (where profitability is higher) in neighborhood. The second phase is executed by onlookers, who modify their patches' positions with influence from elite positions. These positions are known as selected patches. After every phase a greedy selection process is repeated, where solutions (flower patch

positions) compete themselves for retention in the elite or selected patches based on their fitness. In this process some of the sources may migrate from one category to another or some may be abandoned in favor of randomly generated sources, which are simulated by the scout phase of the algorithm. Subsequently, these search processes of the employed, onlooker, and scout phases are repeated in cycles until the termination criterion is met. Experiments were performed on ten real world problems. Static testing based symbolic execution method has been used in which first, the target path is selected from the CFG of program and then inputs are generated using the ABC method to satisfy composite predicate corresponding to the target path. The technique has performed satisfactorily for most of the program except programs with large input domains and many equality based path constraints.

CONCLUSION

In this research artificial bee colony algorithm has been studied and a review based on the application of the artificial bee colony algorithm in the field of software testing has been performed. It was found out that the current application of ABC algorithm is in the field of structural testing and for test suite optimization.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.