Received date: February 20, 2016; Accepted date: March 17, 2016; Published date: March 24, 2016
Citation: Mann M, Tomar P, Sangwan OmP, Nature-Inspired Metaheuristic Search Strategies. Electronic J Biol, 12:2
Research on metahurestic for solving optimization problems has been appeared as a great subject of interest during last few years. It involves modeling the natural phenomena of various species foraging for the food and as well as theory of natural evolution of species. In this paper we discuss three major metahurestic approaches for optimization problems appeared in software testing such as path prioritization, automatic test case generation, test case selection etc. First we discuss Ant colony optimization as suggested by Grasse in 1959 and later modeled by Dorigo, Maniezzo, and Colorni in 1996 as one of the optimization algorithm for solving optimization problems. Second focus is on natural inspired phenomena of Honey bee colony suggested by V. Tereshko, based on Reaction–diffusion diffusion model of a honeybee colony’s foraging behavior. Finally we end up with genetic algorithm inspired by theory of evolution for solving optimization problems. The survey results the potential use of mentioned metahurestic approaches in software testing.
Ant colony optimization (ACO); Artificial bee colony (ABC); Genetic algorithm (GA).
The process of testing a software system before its actual use is essential for delivering error free software. The system is checked by comparing the expected output with the actual output after executing sample input(s) . If both expected and actual outputs are same then there is no error else the system contains an error. Thus the aim of software testing is to find faults within the system by executing it with sample input data. There are number of software testing techniques such test case optimization and prioritization [2-9] which are proposed in preceding years to reduce various resources such as time, human Intervention in testing phase.
A major area of research is in Structural Testing which takes into account the code, structure of code and internal design. Commonly used techniques for structural testing [8-12] are that include control flow/ coverage testing, basic path testing, loop testing, and data flow testing . Recent studies in testing indicate that a major work is in area of test case generation and prioritization based on experimental proofing. The techniques that are used in such studies are inspired from Artificial intelligence [2-5,14-16]. Therefore a part from the above mentioned techniques a new focus for the researchers is how to map natural intelligence to Artificial intelligence for solving NP hard problems, one such nature inspired intelligence called metahurestic search gives us optimized solutions for a problem in hand. In this paper we discuss various metahurestic techniques on which research work is going on very rapidly.
Ant algorithms are one of the most attracting areas of research in optimization of software testing. The natural foraging behaviour of real ant’s in wild space was first modelled by Dorigo, Maniezzo, and Colorni . The indirect communication between ants within the colony using pheromone secretion provide a most powerful path for optimization methods. The ant colony algorithms are considered to be a part of Swarm intelligence i.e. multi- agent systems are based on the behavior of natural real world insects acting as swarm and collectively forming optimization behavior while foraging. A number of such swarm based algorithms has been proposed such as artificial bee colony, artificial bee colony optimization and particle swarm optimization. In this section a details discussion on the idea behind ACO is put forwarded to solve software testing problems in much easy way as compared to the traditional approach.
In 1959 Grasse  first introduced a term known as Stigmergy to the indirect form of communication among multi-agents evolving as a self-organized single system while modifying their local environment. In 1990 Deneubourg, Aron, Goss, and Pasteels  studied the ant colonies Stigmergy nature in which each ant communicate indirectly by depositing a chemical known as pheromone on their path and the ant then tends to follow that path. Goss, Aron, Deneubourg, and Pasteels  with their experiment show that ants converge to the trail having higher concentration on pheromone deposit. Let us demonstrate a simple - Shortest bridge experiment ? as conducted by (Goss et al.) . Figure 1 shows the diagrammatic view of setup in which two possible paths from source (nest) to destination (food) are shown. Path A is shorter than path B. Initially as the ant move from the nest foraging for food, it follow a random path but as the time passes we observed that all ants following the path A. This is due to the fact that when initially an ant move from her nest following path A and after collecting food she will reach to nest again in less time than an ant which had followed the path B due to the distance parameter and in this way it had deposited a pheromone before the second ant following the path B. Thus a convergence to a shortest path is achieved (Figure 1). The experiment shows the exploration to exploitation due to pheromone deposition tendency of ants in real world.
In the following section, we briefly explain how the ants’ behavior, as well as pheromone evaporation can implement.
In ACO, there are two mode of working, the first is called forward move and the other is called backward move. In forward mode the ant’s movement is from nest (i.e. the source) to the food (destination) and Vice-versa in backward mode. After reaching to food source the ant reverse its direction .i.e. a shift to backward direction in order to reach to the source. The solution in forward moves is built by taking a probabilistic decision for next node to move to among those in the neighborhood of graph node on which they are located. (Given a graph G = (N,A), two nodes i, j~N if there exists an arc i, j~A). This probabilistic choice is particularly biased on pheromone deposited and Heuristic value between two nodes.
The use of an explicit memory allows an ant to repeat the path it had followed while building solutions. While moving backward, PP-ACO ants leave pheromone trail on the arcs they traverse.
In ACO the ants memorize all nodes that are traced through forward move, as well as the associated arc’s cost if the graph is weighted. They can therefore evaluate the cost of the solutions they build and use this evaluation to modulate the amount of pheromone and heuristic they deposit while in backward mode. Making pheromone and heuristic update as function of the generated solution quality ensure in directing future ants more strongly toward better solutions.
In Ant systems, the tour in a control flow graph (path) is concurrently builds by m number of ants. An ant start from an initial node and by using random proportional rule the ant decides the next node to be visited upon. The probability with which ant k, at node i, chooses the node j is given as
Where Nij=1/dij is called heuristic which is priori available and it indicates the visibility of a path so that an ant can follow a path having higher heuristic. Nik is the feasible neighbourhood of ant k at node i i.e. the set of node in CFG which an ant has not visited (PijK for choosing a node outside Nik is 0). The effect of pheromone and heuristic on next move is determined by the value of α and β. Setting α=0, will select the most closet node, if β=0 then only deposited pheromone trail influence the next move and it may leads to poor solutions. In situations when a>1, a stagnation situation occurs in which all the ants follow the same path and construct the same tour, which, results in sub-optimal solutions . Thus it is extremely important to choose these parameters very carefully. Good parameter values for the various ant Algorithms are given in Table 1 . In the following section, we briefly explain how the ants’ behaviour, as well as pheromone evaporation can implement.
|ACO algorithm||α||β||Pheromone Evaporation (ρ)||Number of ants m||Initial Pheromone t0|
|Ant systems||1||2 to 5||0.5||n||m/cnn|
|EAS||1||2 to 5||0.5||N||(e+m)/ ρ cnn|
|ASrank||1||2 to 5||0.1||N||0.5r(r-1)/ ρ cnn|
|MMAS||1||2 to 5||0.02||N||1/ ρ cnn|
|ACS||-||2 to 5||0.1||10||1/ncnn|
Table 1: Parameter setting for various ACO algorithms.
After an ant has constructed its tour, the updation in pheromone is completed by lowering the pheromone value on all arcs visited by the ant by a constant amount (or factor). This is also called as pheromone evaporation. The left pheromone value is then added to the nodes an ant has visited in their tour. Pheromone evaporation is given as
Where 0<ρ<1, and ρ is the pheromone evaporation rate. ρ controls the indefinite addition of the pheromone thus permitting the algorithm to overlook previously taken bad decisions. The pheromone deposition after evaporation is defined as
tij←tij +Δ tkij
Where Δ tkij is the pheromone deposited by kth ant on the visited node, which is defined as:
Where Clk is the tour’s length built by the kth ant, which is given by the summation of arc’s length which belongs to Tk.
The heuristic updation is given as Δ nij←no/Cik
|Reference||Pub. year||Topic||Author||Thrust area||Published in.|
|||2013||A survey on optimization metahurestic||Ilhem Boussaïd, Julien Lepagnot and Patrick Siarry||survey of some of the main metahurestic||Elsevier|
|||2009||Adaptable Learning Pathway Generation with Ant Colony Optimization||Lung-Hsiang Wong and Chee- Kit Looi||modeling learning pathways that combines rule-based prescriptive planning||International Forum of Educational Technology & Society (IFETS).|
|||2005||An Ant Colony Optimization Approach to Test Sequence Generation for State based Software Testing||Huaizhong LI and C. Peng LAM||Automatic test Sequence generation for state- based software testing||IEEE|
|||2006||Artificial Ants as a Computational Intelligence Technique||Marco Dorigo, Mauro Birattari, and Thomas St¨utzle||Computational intelligence||IEEE|
|||2007||Classification With Ant Colony Optimization||David Martens, Manu De Backer, Raf Haesen||Classification||IEEE|
|||2009||Automatic Test Data Generation Based On Ant Colony Optimization||Kewen Li, Zilu Zhang and Wenying Liu||generating test data based||IEEE|
|||2009||Building Prioritized Pairwise Interaction Test Suites with Ant Colony Optimization||Xiang Chen, Qing Gu, Xin Zhang and Daoxu Chen||test generation algorithms||IEEE|
|||2009||An Approach of Optimal Path Generation using Ant Colony Optimization||Praveen Ranjan Srivastava, Km Baby and G Raghurama||optimal path identification||IEEE|
|||2006||Automated Software Testing Using Metahurestic Technique Based on An Ant Colony Optimization||Praveen Ranjan Srivastava and Km Baby||ant colony theory understanding and application||(IRIDIA) Technical Report series Book chapter in Approximation Algorithms and Metaheuristics|
|||2007||Automatic Mutation Test Input Data Generation via Ant Colony||K. Ayari, S. Bouktif and G. Antoniol||Automatic test input data generation in the context of mutation testing||ACM|
|||2005||Software Test Data Generation using Ant Colony Optimization||Huaizhong Li and C. Peng Lam||Test data generation for the state based software testing.||World Academy of Science, Engineering and Technology, 2005|
|||2002||A Review on the Ant Colony Metaheuristics: Basis, Models and New Trends||Oscar Cordon, Frencisco Herrera and Thomas Stutzle||application of ACO to challenging combinatorial problems||Mathware and Soft Computing|
|||2010||Test Case Prioritization using Ant Colony Optimization||Yogesh Singh, Arvinder Kaur and Bharti Suri||regression test prioritization technique||ACM|
|||2005||Comparison among five evolutionary-based optimization algorithms||Emad Elbeltagi, Tarek Hegazy and Donald Grierson||comparison of five recent evolutionary- based algorithms: genetic algorithms, memetic algorithms, particle swarm, ant-colony systems, and shuffled frog leaping||Elsevier|
|||2009||A review of ant algorithms||R.J. Mullen, D. Monekosso, S. Barman and P. Remagnino||a critical review of ACO algorithm||Elsevier|
|||2005||Ant colony optimization theory: A survey||Marco Dorigo and Christian Blum||discuss ACO algorithm and various open research question||Elsevier|
Table 2: Survey on Ant colony approach in automated software testing.
Reaction diffusion model of a honeybee colony’s foraging behavior . Tereshko was the first who mapped the foraging behavior of honeybee based on reaction diffusion equations which results in collective exploration and exploitation of food source (i.e. candidate solutions) by swarm (honeybees) . The model has three basic components as
• Food Sources: In order to select a food source, a forager bee evaluates several properties related with the food source such as its closeness to the hive, richness of the food, taste of its nectar, and the ease or difficulty of extracting this food. For the simplicity, the quality of a food source can be represented by only one quantity although it depends on various parameters.
• Employed foragers: An employed forager is the bee who is currently exploiting the food source i.e. hunting the food source. After collecting the nectar (food) from the food source she gives the information about the various parameters such as food quality, distance of food source from hive, direction of food source to the bees in the hives (onlooker).
• Unemployed foragers: These are the bees that are continuously looking for the food to exploit it. They are either the scout bees that are searching the space near to hive randomly or the onlooker bees that are waiting for the employed bee to transfer the information about the food source and once they get information they went out of the hive to go in the direction of food. After leaving the hive they themselves act as an employed bee once they get the food source. On an average there are about 5-10 % of scout bees.
The exchange of information about the food is totally depends on the dance of employed bees in the hive, once the employed bee get the food and return to the hive , she dances on the floor called as waggle dance. The onlookers closely watch this waggle dance on the dancing floor and get employ herself at the most profitable source depending on the dance. In this way a recruitment process has been started i.e. onlookers are recruited to become employed bees.
Let us try to understand the whole process using Figure 2. We assume that there are two food sources A and B. The source A is more rich i.e. higher nectar than source B. Initially assume that two bees act as forger (searching for food) about 5-10% are scouts and the rest are onlooker bees in the hive. So these initial two bees act as a scout bees and let bee (B1) goes to food source A and the other bee (B2) goes to food source B. Once they find the food source and collect the nectar from it they become employed bee E1 and E2 for B1 and B2 respectively. After collecting the food she returns to the hive and start dancing on the dancing floor. As two bee collect different information about the food source so there dance is different. Onlooker’s bees carefully watch the dance of these two bees and decide which food source they choose and in this way onlooker bees become employed bees and reached to the food source.
An Artificial Bee Colony Algorithm: A simple ABC algorithm is given in Listing 1.
|Reference||Pub. year||Topic||Author||Published in|
|||2012||A Recombination Based Hybridization of Particle Swarm Optimization||Mustafa Servet Kiran and Mesut Gunuz||Elsevier|
|||2010||A Modified Artificial Bee Colony Algorithm for Real-Parameter Optimization||Bahriye Akay and Dervis Karaboga||Elsevier|
|||2009||A New Design Method Based on Artificial Bee Colony Algorithm for Digital IIR Filters||Nurhan Karaboga||Elsevier|
|||2005||Comparison Among Five Evolutionary-based Optimization Algorithms||Emad Elbeltagi, Tarek Hegazy and Donald Grierson||Elsevier|
|||2007||On the Performance of Artificial Bee Colony (ABC) Algorithm||D. Karaboga and B. Basturk||Elsevier|
|||2008||An Artificial Bee Colony Algorithm for the Leaf-Constrained Minimu Spanning Tree Problem||Alok Singh||Elsevier|
|||2012||Block Matching Algorithm for Motion Estimation Based on Artificial Bee Colony||Erik Cuevas, Daniel Zaldivar, Marco Perez- Cisneros||Elsevier|
|||2012||Water Cycle Algorithm- A Novel Metaheuristic Optimization Method for Solving Constrained||Hadi Eskandar, Ali Sadollah, Ardeshir Bahreininejad||Elsevier|
|||2012||Comparative Performance Analysis of Artificial ABC Algorithm in Automatic Generation Control||Haluk Gozde, M. Cengiz Taplamacioglu and illah Kocaarslan||Elsevier|
|||2011||Automated Generation of Independent Paths and Test Suite Optimization Using Artificial Bee Colony||Soma Sekhara Babu Lam and M L Hari Prasad Raju||Elsevier|
|||2012||The Further Research on the Application of ABC to the Optimization and Control of Project||Cui Qiao and Hengshan Wang||Canadian Center of Science and Education|
|||2007||Artificial Bee Colony Algorithm and Its Application to Generalized Assignment Problem||Adil Baykaso�lu, Lale Özbakır and Pınar Tapkan||N/M|
|||2010||Application of Artificial Bee Colony Algorithm to Software Testing||Surender Singh Dahiya, Jitender Kumar Chhabra and Shakti Kumar||IEEE|
|||2011||Search-Based Software Testing: Past, Present and Future||Phil McMinn||IEEE|
|||2012||Overview of Artificial Bee Colony (ABC) Algorithm and Its Applications||Fahad S. Abu-Mouti and Mohamed E. El-Hawary||IEEE|
|||2012||A Discrete Artificial Bee Colony Algorithm for the Traveling Salesman Problem with Time Windows||Korhan Karabulut and M. Fatih Tasgetiren||IEEE|
|||2011||A Survey of Combinatorial Testing||Changhai Nie Hareton Leung||ACM|
|||2012||A Comprehensive Survey: Artificial Bee Colony (ABC) Algorithm and Aplications||Dervis Karaboga, Beyza Gorkemli and Celal Ozturk||Springer|
|||2007||A Powerful and Efficient Algorithm for Numerical Function Optimization: (ABC) algorithm||Dervis Karaboga and Bahriye Basturk||Springer|
|||2009||A Comparative Study of Artificial Bee Colony Algorithm||Dervis Karaboga and Bahriye Basturk||Elsevier|
|||2011||A Survey on the Applications of Bee Colony Optimization Techniques||Dr. Arvinder Kaur and Shivangi Goyal||IJCSE|
|||1995||Removing the Genetics from the Standard Genetic Algorithm||Shumeet Baluja and Rich Caruana|
|||2009||ABC Tester - Artificial Bee Colony Based Software Test Suite Optimization Approach||D. Jeya Mala and V. Mohan||IJCSE|
|||2012||Hybrid Harmony Search and ArtificialBee Colony Algorithm for Global Optimization Problems||Bin Wu, Cunhua Qian, Weihong Ni and Shuhai Fan||Elsevier|
|||2012||Artificial Bee Colony Programming for Symbolic Regression||Dervis Karaboga, Celal Ozturk, Nurhan Karaboga and Beyza Gorkemli||Elsevier|
|||2011||Collaborative Artificial Bee Colony Optimization Clustering Using SPNN||D.Shanthi and R.Amalraj||Elsevier|
|||2011||Nature Inspired Cooperative Strategies for Optimization (NICSO 2011)||David Alejandro Pelta,Natalio Krasnogor, Dan Dumitrescu||Springer|
|||2012||Artificial Bee Colony Algorithm with Improved Explorations for Numerical Function Optimization||Mohammad Shafiul Alam, Md. Monirul Islam and Kazuyuki Murase||Springer|
Table 3: Survey on bee colony approach in automated software testing.
From the literature survey it has been clear that ABC has potential to solve many problems in automated software testing domain. a critical insight from the survey suggest that ABC has been used to make software testing more reliable, time efficient and better resource utilization. It is thus again an open research area in automated software testing.
Genetic Algorithm was proposed by Holland . GA is heuristic search algorithms that is inspired by natural biological evolution of species and solve a variety of optimization problems to improve the quality of the search. A simple GA algorithm is shown in Listing 2.
|Ref No||Pub.year||Topic||Author||Published in.|
|||2011||Diversity oriented test data generation using Metaheuristics search techniques||Paulo M.S. Bueno , Mario Jino, W. Eric Wong||Elsevier|
|||2006||Automatic test data generation using genetic algorithm and program dependence graphs||James Miller, Marek Reformat, Howard Zhang||Elsevier|
|||2009||Application of Genetic Algorithm in Software Testing||Praveen Ranjan Srivastava and Tai- hoon Kim||International Journal of Software Engineering and Its Applications|
|||2010||Using Genetic Algorithms and Dominance Concepts for Generating Reduced Test Data||Ahmed S. Ghiduk Moheb R. Girgis||Informatica|
|||2009||Eccentric Test Data Generation for Path Testing Using Genetic Algorithm||Punam Mishra, Bhabani Shankar Prasad Mishra||International Conference on Computer Engineering and Applications|
|||2004||Search-based software test data generation: a survey||Phil McMinn||Software Testing, verification and reliability|
|||2007||Automatic software test data generation for spanning sets coverage using genetic algorithms||Abdelaziz M. Khamis,Moheb R. Girgis,Ahmed S. Ghiduk||Computing and Informatics,|
|||1996||Automatic structural testing using genetic algorithms||B. F. Jones, H.-H. Sthamer and D. E. Eyres||Software Engineering Journal|
|||1997||Genetic Algorithms for Dynamic Test Data Generation||Christoph C. Michael, Gary E. McGraw ,Michael A. Schatz ,Curtis C. Walton||IEEE|
|||Automated Software Test Data Generation for Complex Programs||Christoph Michael & Gary McGraw||not mentioned|
|||2000||Using Genetic Algorithms for Test Case Generation in Path Testing||Jin-Cherng Lin and Pu-Lin Yeh||IEEE|
|||2001||Generating Software Test Data by Evolution||Christoph C. Michael, Gary McGraw,Michael A. Schatz||IEEE TRANSACTIONS ON SOFTWARE ENGINEERING,|
|||2002||Breeding Software Test Cases with Genetic Algorithms||D. Berndt, J. Fisher, L. Johnson, J. Pinglikar, and A. Watkins||Proceedings of the 36th Hawaii International Conference on System Sciences( IEEE)|
|||2004||Investigating the Performance of Genetic Algorithm-Based Software Test Case Generation||Donald J. Berndt and Alison Watkins||Proceedings of the Eighth IEEE International Symposium on High Assurance Systems Engineering|
|||2003||Genetic Algorithm Based Test Data Generator||Irman Hermadi AND Moataz A. Ahmed||IEEE|
|||2004||Using a Genetic Algorithm and Formal Concept Analysis to Generate Branch Coverage Test Data Automatically||Susan Khor and Peter Grogono||Proceedings of the 19th International Conference on Automated Software Engineering (|
|||2008||Automatic Path-oriented Test Data Generation Using a Multi-population Genetic Algorithm||Yong Chen and Yong Zhong||Fourth International Conference on Natural Computation(IEEE)|
|2012||A Concept of Out Degree in CFG for Optimal Test Data Using Genetic Algorithm||Shadab Irfan and Prabhat Ranjan||1st Int’l Conf. on Recent Advances in Information Technology (IEEE)|
|||2012||Automatic Program Instrumentation in Generation of Test Data using Genetic Algorithm for Multiple Paths Coverage||P .Maragathavalli ,S.Kanmani||IEEE-International Conference On Advances In Engineering, Science And Management|
|||2012||Genetic algorithm based software testing specifically structural testing for software reliability enhancement||NIRPAL P.B. AND KALE K.V.||International Journal of Computational Intelligence Techniques|
|||2000||Automated test-data generation for exception conditions||N. Tracey, J. Clark, K. Mander§ and J. McDermid||SOFTWARE— PRACTICE AND EXPERIENCE|
|2012||Program test data generation for branch coverage with genetic algorithm||AnkurPachauriand Gursaran||CS & IT-CSCP 2012|
|||2005||Automatic Test Data Generation for Data Flow Testing Using a Genetic Algorithm||Moheb R. Girgis||Journal of Universal Computer Science|
Table 4: Survey on genetic algorithm approach in automated software testing.
A Literature survey study among the various metahurestic techniques used in automated software testing has been discuss above which clearly indicate frequently used metahurestic for automated software testing during the last few years. The survey also indicates the potential of using metahurestic as a search technique in software testing [86-89].
In this paper we analyze scope of research that can be carried out in computer science especially in field of software testing using nature inspired algorithms such as ACO, ABC AND GA. From the survey we conclude that during the last few decades there has been a significant change in testing approaches. Metahurestic approaches are slowly replacing the Manual and traditional testing activities. We have a strong observation that these nature inspired algorithms are not only useful on computer science but also in other related filed such as electronics (making optimized control flow, load balancing, circuit optimization and related optimization problems) and biology such as protein folding prediction. Thus metahurestic is growing area for research and is open to carry out new researches. We have observed that researchers are moving from traditional algorithms to natural inspired algorithms in solving NP hard problems.
This Work was supported by university grant commission (UGC), Government of India for Doctoral Research Study under Grant No. F./201415/ NFO201415OBCDEL16123. The authors are very grateful to the anonymous reviewers for providing valuable and detailed comments that have greatly improved the paper.