Reach Us +12 184512974

Nature-Inspired Metaheuristic Search Strategies

Mukesh Mann1*, Pradeep Tomar1, Om Praksah Sangwan2, Shivani Singh1

1School of Information and Communication Technology Gautam Buddha University, Greater Noida, Uttar Pradesh, India

2Department of Computer Science and Engineering, Guru Jambheshwar University of Science and Technology, Hisar, Haryana, India

Corresponding Author:
Tel: +91 9873106374
E-mail: [email protected]

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

 
Visit for more related articles at Electronic Journal of Biology

Abstract

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.

Keywords

Ant colony optimization (ACO); Artificial bee colony (ABC); Genetic algorithm (GA).

1. Introduction

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) [1]. 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 [13]. 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.

1.1 The ant colony: Metahurestic

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 [8]. 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.

1.2 Ant in the real world-a wild metaphor

In 1959 Grasse [17] 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 [18] 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 [18] 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.) [17]. 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.

Figure

Figure 1: Two possible path for foraging.

1.3 From nature to artificial computers

In the following section, we briefly explain how the ants’ behavior, as well as pheromone evaporation can implement.

1.4 Probabilistic forward ants and solution construction

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.

1.5 Deterministic backward ants and pheromone update

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.

1.6 Pheromone updates based on solution quality

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.

1.7 Tour building

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

image

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 [8]. Thus it is extremely important to choose these parameters very carefully. Good parameter values for the various ant Algorithms are given in Table 1 [19]. 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.

1.8 Pheromone updation: A sequential way

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

tij←(1-ρ) tij

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:

image

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

In the Table 2 [20-35] we briefly discuss the various works that has been contributed by various researchers in field of software testing using ACO

Reference Pub. year Topic Author Thrust area Published in.
[20] 2013 A survey on optimization metahurestic Ilhem Boussaïd, Julien Lepagnot and Patrick Siarry survey of some of the main metahurestic Elsevier
[21] 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).
[22] 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
[23] 2006 Artificial Ants as a Computational Intelligence Technique Marco Dorigo, Mauro Birattari, and Thomas St¨utzle Computational intelligence IEEE
[24] 2007 Classification With Ant Colony Optimization David Martens, Manu De Backer, Raf Haesen Classification IEEE
[25] 2009 Automatic Test Data Generation Based On Ant Colony Optimization Kewen Li, Zilu Zhang and Wenying Liu generating test data based IEEE
[26] 2009 Building Prioritized Pairwise Interaction Test Suites with Ant Colony Optimization Xiang Chen, Qing Gu, Xin Zhang and Daoxu Chen test generation algorithms IEEE
[27] 2009 An Approach of Optimal Path Generation using Ant Colony Optimization Praveen Ranjan Srivastava, Km Baby and G Raghurama optimal path identification IEEE
[28] 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
[29] 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
[30] 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
[31] 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
[32] 2010 Test Case Prioritization using Ant Colony Optimization Yogesh Singh, Arvinder Kaur and Bharti Suri regression test prioritization technique ACM
[33] 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
[34] 2009 A review of ant algorithms R.J. Mullen, D. Monekosso, S. Barman and P. Remagnino a critical review of ACO algorithm Elsevier
[35] 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.

1.9 Artificial bee colony optimization

Reaction diffusion model of a honeybee colony’s foraging behavior [36]. 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) [37]. 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.

Figure

Figure 2: Honey bee wangle dance sharing information.

An Artificial Bee Colony Algorithm: A simple ABC algorithm is given in Listing 1.

ABC has been used in number of ways in different automated software testing approaches. A detail list of the survey is illustrated in the Table 3 [38-64].

Reference Pub. year Topic Author Published in
[38] 2012 A Recombination Based Hybridization of Particle Swarm Optimization Mustafa Servet Kiran and Mesut Gunuz Elsevier
[39] 2010 A    Modified Artificial Bee Colony Algorithm for Real-Parameter Optimization Bahriye Akay and Dervis Karaboga Elsevier
[40] 2009 A New Design Method Based on Artificial Bee Colony Algorithm for Digital IIR Filters Nurhan Karaboga Elsevier
[33] 2005 Comparison Among Five Evolutionary-based Optimization Algorithms Emad    Elbeltagi,    Tarek Hegazy  and  Donald Grierson Elsevier
[41] 2007 On the Performance of Artificial Bee Colony (ABC) Algorithm D.    Karaboga    and B. Basturk Elsevier
[42] 2008 An Artificial Bee Colony Algorithm for the Leaf-Constrained Minimu Spanning Tree Problem Alok Singh Elsevier
[43] 2012 Block Matching Algorithm for Motion Estimation Based on Artificial Bee Colony Erik  Cuevas,  Daniel Zaldivar,    Marco    Perez- Cisneros Elsevier
[44] 2012 Water Cycle Algorithm- A Novel Metaheuristic Optimization Method for Solving Constrained Hadi   Eskandar,   Ali Sadollah, Ardeshir Bahreininejad Elsevier
[45] 2012 Comparative Performance Analysis of Artificial ABC Algorithm in Automatic Generation Control Haluk Gozde, M. Cengiz Taplamacioglu and illah Kocaarslan Elsevier
[46] 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
[47] 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
[48] 2007 Artificial Bee Colony Algorithm and Its Application to Generalized Assignment Problem Adil Baykaso�lu, Lale Özbakır and Pınar Tapkan N/M
[49] 2010 Application of Artificial Bee Colony Algorithm to Software Testing Surender Singh Dahiya, Jitender Kumar Chhabra and Shakti Kumar IEEE
[50] 2011 Search-Based Software Testing: Past, Present and Future Phil McMinn IEEE
[51] 2012 Overview of Artificial Bee Colony (ABC) Algorithm and Its Applications Fahad S. Abu-Mouti and Mohamed E. El-Hawary IEEE
[52] 2012 A Discrete Artificial Bee Colony Algorithm for the Traveling Salesman Problem with Time Windows Korhan Karabulut and M. Fatih Tasgetiren IEEE
[53] 2011 A Survey of Combinatorial Testing Changhai Nie Hareton Leung ACM
[54] 2012 A Comprehensive Survey: Artificial Bee Colony (ABC) Algorithm and Aplications Dervis Karaboga, Beyza Gorkemli and Celal Ozturk Springer
[55] 2007 A Powerful and Efficient Algorithm for Numerical Function Optimization: (ABC) algorithm Dervis Karaboga and Bahriye Basturk Springer
[56] 2009 A Comparative Study of Artificial Bee Colony Algorithm Dervis Karaboga and Bahriye Basturk Elsevier
[57] 2011 A Survey on the Applications of Bee Colony Optimization Techniques Dr. Arvinder Kaur and Shivangi Goyal IJCSE
[58] 1995 Removing the Genetics from the Standard Genetic Algorithm Shumeet Baluja and Rich Caruana  
[59] 2009 ABC Tester - Artificial Bee Colony Based Software Test Suite Optimization Approach D. Jeya Mala and V. Mohan IJCSE
[60] 2012 Hybrid Harmony Search and ArtificialBee Colony Algorithm for Global Optimization Problems Bin Wu, Cunhua Qian, Weihong Ni and Shuhai Fan Elsevier
[61] 2012 Artificial Bee Colony Programming for Symbolic Regression Dervis Karaboga, Celal Ozturk, Nurhan Karaboga and Beyza Gorkemli Elsevier
[62] 2011 Collaborative Artificial Bee Colony Optimization Clustering Using SPNN D.Shanthi and R.Amalraj Elsevier
[63] 2011 Nature Inspired Cooperative Strategies for Optimization (NICSO 2011) David Alejandro Pelta,Natalio Krasnogor, Dan Dumitrescu Springer
[64] 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.

1.10 Genetic algorithm

Genetic Algorithm was proposed by Holland [2]. 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.

The general flow chart for the same is shown in Figure 3. A research survey on the use of genetic algorithm in automated software testing has been conducted as shown in Table 4 [65-85].

Figure

Figure 3: Flowchart of a simple genetic algorithm.

Ref No Pub.year Topic Author Published in.
[65] 2011 Diversity oriented test data generation using Metaheuristics search techniques Paulo M.S. Bueno , Mario Jino, W. Eric Wong Elsevier
[66] 2006 Automatic test data generation using genetic algorithm and program dependence graphs James Miller, Marek Reformat, Howard Zhang Elsevier
[67] 2009 Application of Genetic Algorithm in Software Testing Praveen Ranjan Srivastava and Tai- hoon Kim International Journal of Software Engineering and Its Applications
[68] 2010 Using Genetic Algorithms and Dominance Concepts for Generating Reduced Test Data Ahmed S. Ghiduk Moheb R. Girgis Informatica
[69] 2009 Eccentric Test Data Generation for Path Testing Using Genetic Algorithm Punam Mishra, Bhabani Shankar Prasad Mishra International Conference on Computer Engineering and Applications
[70] 2004 Search-based software test data generation: a survey Phil McMinn Software Testing, verification and reliability
[71] 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,
[72] 1996 Automatic structural testing using genetic algorithms B. F. Jones, H.-H. Sthamer and D. E. Eyres Software Engineering Journal
[73] 1997 Genetic Algorithms for Dynamic Test Data Generation Christoph C. Michael, Gary E. McGraw ,Michael A. Schatz ,Curtis C. Walton IEEE
[74]   Automated Software Test Data Generation for Complex Programs Christoph Michael & Gary McGraw not mentioned
[75] 2000 Using Genetic Algorithms for Test Case Generation in Path Testing Jin-Cherng Lin and Pu-Lin Yeh IEEE
[76] 2001 Generating Software Test Data by Evolution Christoph C. Michael, Gary McGraw,Michael A. Schatz IEEE TRANSACTIONS ON SOFTWARE ENGINEERING,
[77] 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)
[78] 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
[79] 2003 Genetic Algorithm Based Test Data Generator Irman Hermadi AND Moataz A. Ahmed IEEE
[80] 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 (
[71] 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)
[81] 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
[82] 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
[83] 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
[84] 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].

2. Conclusion

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.

Acknowledgements

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.

References

Select your language of interest to view the total content in your interested language

Viewing options

Flyer image
journal indexing image

Share This Article