Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUsing simulated annealing for locating array construction
145
0
0.0
(
0
)
Added by
Tatsuhiro Tsuchiya
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Context: Combinatorial interaction testing is known to be an efficient testing strategy for computing and information systems. Locating arrays are mathematical objects that are useful for this testing strategy, as they can be used as a test suite that enables fault localization as well as fault detection. In this application, each row of an array is used as an individual test. Objective: This paper proposes an algorithm for constructing locating arrays with a small number of rows. Testing cost increases as the number of tests increases; thus the problem of finding locating arrays of small sizes is of practical importance. Method: The proposed algorithm uses simulation annealing, a meta-heuristic algorithm, to find locating array of a given size. The whole algorithm repeatedly executes the simulated annealing algorithm by dynamically varying the input array size. Results: Experimental results show 1) that the proposed algorithm is able to construct locating arrays for problem instances of large sizes and 2) that, for problem instances for which nontrivial locating arrays are known, the algorithm is often able to generate locating arrays that are smaller than or at least equal to the known arrays. Conclusion: Based on the results, it is concluded that the proposed algorithm can produce small locating arrays and scale to practical problems.
rate research
Read More
Combinatorial interaction testing is an efficient software testing strategy. If all interactions among test parameters or factors needed to be covered, the size of a required test suite would be prohibitively large. In contrast, this strategy only requires covering $t$-wise interactions where $t$ is typically very small. As a result, it becomes possible to significantly reduce test suite size. Locating arrays aim to enhance the ability of combinatorial interaction testing. In particular, $(overline{1}, t)$-locating arrays can not only execute all $t$-way interactions but also identify, if any, which of the interactions causes a failure. In spite of this useful property, there is only limited research either on how to generate locating arrays or on their minimum sizes. In this paper, we propose an approach to generating minimum locating arrays. In the approach, the problem of finding a locating array consisting of $N$ tests is represented as a Constraint Satisfaction Problem (CSP) instance, which is in turn solved by a modern CSP solver. The results of using the proposed approach reveal many $(overline{1}, t)$-locating arrays that are smallest known so far. In addition, some of these arrays are proved to be minimum.
In this paper we consider the use of certain classical analogues to quantum tunneling behavior to improve the performance of simulated annealing on a discrete spin system of the general Ising form. Specifically, we consider the use of multiple simultaneous spin flips at each annealing step as an analogue to quantum spin coherence as well as modifications of the Boltzmann acceptance probability to mimic quantum tunneling. We find that the use of multiple spin flips can indeed be advantageous under certain annealing schedules, but only for long anneal times.
JPEG is one of the most widely used image formats, but in some ways remains surprisingly unoptimized, perhaps because some natural optimizations would go outside the standard that defines JPEG. We show how to improve JPEG compression in a standard-compliant, backward-compatible manner, by finding improved default quantization tables. We describe a simulated annealing technique that has allowed us to find several quantization tables that perform better than the industry standard, in terms of both compressed size and image fidelity. Specifically, we derive tables that reduce the FSIM error by over 10% while improving compression by over 20% at quality level 95 in our tests; we also provide similar results for other quality levels. While we acknowledge our approach can in some images lead to visible artifacts under large magnification, we believe use of these quantization tables, or additional tables that could be found using our methodology, would significantly reduce JPEG file sizes with improved overall image quality.
We propose a new stochastic algorithm (generalized simulated annealing) for computationally finding the global minimum of a given (not necessarily convex) energy/cost function defined in a continuous D-dimensional space. This algorithm recovers, as particular cases, the so called classical (Boltzmann machine) and fast (Cauchy machine) simulated annealings, and can be quicker than both. Key-words: simulated annealing; nonconvex optimization; gradient descent; generalized statistical mechanics.
In a two-dimensional arrangement of closely spaced elliptical nanomagnets with in-plane magnetic anisotropy, whose major axes are aligned along columns and minor axes along rows, dipole coupling will make the magnetic ordering ferromagnetic along the columns and anti-ferromagnetic along the rows. Noise and other perturbations can drive the system out of this ground state configuration and pin it in a metastable state where the magnetization orientations will not follow this pattern. Internal energy barriers, sufficiently larger than the thermal energy kT, will prevent the system from leaving the metastable state and decaying spontaneously to the ground state. These barriers can be temporarily eroded by globally straining the nanomagnets with time-varying strain if the nanomagnets are magnetostrictive, which will allow the system to return to ground state after strain is removed. This is a hardware emulation of simulated annealing in an interacting many body system. Here, we demonstrate this function experimentally.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
