Many-Objective Neuroevolution for Testing Games

• URL: http://arxiv.org/abs/2501.07954v1
• Date: Tue, 14 Jan 2025 09:18:34 GMT
• Title: Many-Objective Neuroevolution for Testing Games
• Authors: Patric Feldmeier, Katrin Schmelz, Gordon Fraser,
• Abstract summary: Test generator NEATEST tackles challenges by combining search-based software testing principles with neuroevolution. We transform NEATEST into a many-objective search algorithm that targets several program states simultaneously. Our experiments show that extending NEATEST to target several objectives simultaneously increases the average branch coverage from 75.88% to 81.33%.
• Score: 8.422309223970302
• License:
• Abstract: Generating tests for games is challenging due to the high degree of randomisation inherent to games and hard-to-reach program states that require sophisticated gameplay. The test generator NEATEST tackles these challenges by combining search-based software testing principles with neuroevolution to optimise neural networks that serve as test cases. However, since NEATEST is designed as a single-objective algorithm, it may require a long time to cover fairly simple program states or may even get stuck trying to reach unreachable program states. In order to resolve these shortcomings of NEATEST, this work aims to transform the algorithm into a many-objective search algorithm that targets several program states simultaneously. To this end, we combine the neuroevolution algorithm NEATEST with the two established search-based software testing algorithms, MIO and MOSA. Moreover, we adapt the existing many-objective neuroevolution algorithm NEWS/D to serve as a test generator. Our experiments on a dataset of 20 SCRATCH programs show that extending NEATEST to target several objectives simultaneously increases the average branch coverage from 75.88% to 81.33% while reducing the required search time by 93.28%.

Related papers

• Searching Latent Program Spaces [0.0]
  We propose an algorithm for program induction that learns a distribution over latent programs in a continuous space, enabling efficient search and test-time adaptation. We show that can generalize beyond its training distribution and adapt to unseen tasks by utilizing test-time adaptation mechanisms.
  arXiv  Detail & Related papers  (2024-11-13T15:50:32Z)
• Touchstone Benchmark: Are We on the Right Way for Evaluating AI Algorithms for Medical Segmentation? [90.30635552818875]
  We present Touchstone, a large-scale collaborative segmentation benchmark of 9 types of abdominal organs. This benchmark is based on 5,195 training CT scans from 76 hospitals around the world and 5,903 testing CT scans from 11 additional hospitals. We invited 14 inventors of 19 AI algorithms to train their algorithms, while our team, as a third party, independently evaluated these algorithms on three test sets.
  arXiv  Detail & Related papers  (2024-11-06T05:09:34Z)
• Combining Neuroevolution with the Search for Novelty to Improve the Generation of Test Inputs for Games [9.465831527115235]
  As games challenge traditional automated white-box test generators, Neatest generates test suites consisting of neural networks that exercise the source code by playing the games. We investigate whether the issue of challenging fitness landscapes can be addressed by promoting novel behaviours during the search.
  arXiv  Detail & Related papers  (2024-07-06T07:36:44Z)
• Towards the coherent control of robust spin qubits in quantum algorithms [0.0]
  We run one-spin-qubit gate-based algorithms subject to relaxation. We evaluate the impact of relaxation and potential experimental imperfections in the calculated fidelities. This work will stimulate the study of many-spin-qubit systems in quantum algorithms.
  arXiv  Detail & Related papers  (2023-03-10T16:21:06Z)
• NEVIS'22: A Stream of 100 Tasks Sampled from 30 Years of Computer Vision Research [96.53307645791179]
  We introduce the Never-Ending VIsual-classification Stream (NEVIS'22), a benchmark consisting of a stream of over 100 visual classification tasks. Despite being limited to classification, the resulting stream has a rich diversity of tasks from OCR, to texture analysis, scene recognition, and so forth. Overall, NEVIS'22 poses an unprecedented challenge for current sequential learning approaches due to the scale and diversity of tasks.
  arXiv  Detail & Related papers  (2022-11-15T18:57:46Z)
• CrossBeam: Learning to Search in Bottom-Up Program Synthesis [51.37514793318815]
  We propose training a neural model to learn a hands-on search policy for bottom-up synthesis. Our approach, called CrossBeam, uses the neural model to choose how to combine previously-explored programs into new programs. We observe that CrossBeam learns to search efficiently, exploring much smaller portions of the program space compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2022-03-20T04:41:05Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
  We study the problem of learning efficient algorithms that strongly generalize in the framework of neural program induction. By carefully designing the input / output interfaces of the neural model and through imitation, we are able to learn models that produce correct results for arbitrary input sizes.
  arXiv  Detail & Related papers  (2020-07-07T17:03:02Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
  arXiv  Detail & Related papers  (2020-07-06T15:20:17Z)
• Fast and stable MAP-Elites in noisy domains using deep grids [1.827510863075184]
  Deep-Grid MAP-Elites is a variant of the MAP-Elites algorithm that uses an archive of similar previously encountered solutions to approximate the performance of a solution. We show that this simple approach is significantly more resilient to noise on the behavioural descriptors, while achieving competitive performances in terms of fitness optimisation.
  arXiv  Detail & Related papers  (2020-06-25T08:47:23Z)
• Evolving Neural Networks through a Reverse Encoding Tree [9.235550900581764]
  This paper advances a method which incorporates a type of topological edge coding, named Reverse HANG Tree (RET), for evolving scalable neural networks efficiently. Using RET, two types of approaches -- NEAT with Binary search encoding (Bi-NEAT) and NEAT with Golden-Section search encoding (GS-NEAT) -- have been designed to solve problems in benchmark continuous learning environments.
  arXiv  Detail & Related papers  (2020-02-03T02:29:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.