Title: GWW metaheuristic to solve constraints on floating point numbers and application to test case generation
Authors: Mohamed Sayah; Yahia Lebbah
Addresses: University of Oran 1, Laboratoire LITIO, BP 1524, El-M'Naouer, 31000, Oran, Algeria ' University of Oran 1, Laboratoire LITIO, BP 1524, El-M'Naouer, 31000, Oran, Algeria
Abstract: We propose a population-based local search approach to generate automatically test cases for programs having floating point statements. The proposed approach, called GWW-MLFP (go with the winners using multi-precision arithmetic and local search for floating point constraints), adopts the GWW metaheutistic to solve constraints on floating point numbers which have a huge cardinality (e.g., 252 numbers in [0.5, 1.0]) and huge values (e.g., 10300): the search space is of exponential nature, motivating using an approximate approach. GWW-MLFP is a population-based metaheuristic which uses a set of candidates as a diversification mechanism. A set of B particles are maintained in each iteration. Consequently, different initial candidates are considered and different regions in the search space are explored. First, particles are randomly generated. Second, a dedicated local search algorithm on floating point numbers, called MLFP, is applied on each particle. In the following iterations of GWW-MLFP, the particles are processed until no particle remains under some given objective value. We have implemented the GWW-MLFP approach, and we have shown its usefulness on various non-trivial floating point programs.
Keywords: floating-point computation; local search; go with winners; GWW; metaheuristics; test case generation; floating point constraints; floating point numbers.
International Journal of Mathematical Modelling and Numerical Optimisation, 2016 Vol.7 No.2, pp.121 - 137
Received: 02 Feb 2015
Accepted: 02 Oct 2015
Published online: 18 Jun 2016 *