Empirical Evaluation of Hill Climbing Algorithm

Empirical Evaluation of Hill Climbing Algorithm

Manju Khari (Department of Computer Science and Engineering, Guru Gobind Singh Indraprastha University, Delhi, India) and Prabhat Kumar (Department of Computer Science and Engineering, National Institute of Technology Patna, Patna, India)
Copyright: © 2017 |Pages: 14
DOI: 10.4018/IJAMC.2017100102
OnDemand PDF Download:


The software is growing in size and complexity every day due to which strong need is felt by the research community to search for the techniques which can optimize test cases effectively. The current study is inspired by the collective behavior of finding paths from the colony of food and uses different versions of Hill Climbing Algorithm (HCA) such as Stochastic, and Steepest Ascent HCA for the purpose of finding a good optimal solution. The performance of the proposed algorithm is verified on the basis of three parameters comprising of optimized test cases, time is taken during the optimization process, and the percentage of optimization achieved. The results suggest that proposed Stochastic HCA is significantly average percentage better than Steepest Ascent HCA in reducing the number of test cases in order to accomplish the optimization target.
Article Preview

1. Introduction

Software testing is defined as a process of executing a program with the intent of finding the errors. It is an investigation technique conducted to provide stakeholders the information about the quality of the product/ service under test. Since the testing process accounts for nearly 50% of the total project development in terms of the time, effort and cost, it is essential that testing has to be performed within the stipulated time period. Any impediment in the testing process would ultimately delay the completion of the project and hamper the growth of the industry in the software market. Exhaustive testing is never possible because it would be an extremely time-consuming task. In order to test the software within stipulated time period, often the testing criteria are used which help the process of optimization and helps the tester to finish their testing process within a time bound (Souze et al., 2016).

Researcher defines optimization as hard problems because they cannot achieve guaranteed optimal solution within a reasonable time limit by using any deterministic method known till date to the community. These problems can be divided into several categories such as continuous versus discrete, constrained versus unconstrained, mono versus multi-objective and static versus dynamic. In order to find reasonably optimal solution for these optimization problems within specific time limits, often metaheuristics techniques are used since there does not exist problem-specific heuristics algorithms for them. Heuristic by nature, these techniques are capable of solving a wide range of hard optimization problems at a higher level without deeply endorsing in them (Hoffmann, 2000; Reeves, 1993). Hence emerged in last three decades, they are successfully used in industries to solve complex problems related to finance, production management, engineering (Chalup and Maire, 1999) etc. There exist three main characteristics which make the metaheuristics algorithms powerful as well as popular. Firstly, they are nature-inspired and based on some well-established principles of physics, biology or ethology. Secondly, they make use of the stochastic components involving random variables. Thirdly, and most importantly, instead of the using gradient or hessian matrix for the objective function; it tries to fit various parameters such as optimized test data, the percentage of optimized test data and duration to the problem at hand.

In test data generation paradigm, various heuristic and metaheuristic techniques have been applied to the local and global maxima problem in the past research. Demilli and Offut (1991) and Ali et al. (2010) present a recent review on the application of evolutionary algorithms in software testing. Most of the papers included use of genetic algorithms (GAs) to find test data. In fact, only a few articles listed in the review include other techniques such as firefly algorithm (Kumar et al., 2016; Chakraborty et al., 2016), simulated annealing, tabu search, cuckoo search algorithm, artificial bee colony, hill climbing and ant colony algorithm.

Test data generation is one of the most critical, time-consuming, expensive and labour-intensive activity. Even after several years of research to be able to generate test data automatically, existing techniques are yet not able to produce results satisfactorily. Hence, it is performed manually which is very much susceptible to errors (DeMilli and Offutt, 1991). Although test data generation is an undecidable problem, however, in the current study an effort has been made to find the near optimal solution in the given specific time limits using one of the most efficient metaheuristics technique known as ‘Hill Climbing Algorithm (HCA) (Reeves, 1993; Tsamardinos et al., 2006)’.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing