We present a novel multi-parent crossover operator in genetic algorithms (GAs) called "Deep Neural Crossover" (DNC). Unlike conventional GA crossover operators that rely on a random selection of parental genes, DNC leverages the capabilities of deep reinforcement learning (DRL) and an encoder-decoder architecture to select the genes. Specifically, we use DRL to learn a policy for selecting promising genes. The policy is stochastic, to maintain the stochastic nature of GAs, representing a distribution for selecting genes with a higher probability of improving fitness. Our architecture features a recurrent neural network (RNN) to encode the parental genomes into latent memory states, and a decoder RNN that utilizes an attention-based pointing mechanism to generate a distribution over the next selected gene in the offspring. The operator's architecture is designed to find linear and nonlinear correlations between genes and translate them to gene selection. To reduce computational cost, we present a transfer-learning approach, wherein the architecture is initially trained on a single problem within a specific domain and then applied to solving other problems of the same domain. We compare DNC to known operators from the literature over two benchmark domains, outperforming all baselines.

One of the benefits of using executable specifications such as Behavioral Programming (BP) is the ability to align the system implementation with its requirements. This is facilitated in BP by a protocol that allows independent implementation modules that specify what the system may, must, and must not do. By that, each module can enforce a single system requirement, including negative specifications such as “don't do X after Y.” The existing BP protocol, however, allows only the enforcement of safety requirements and does not support the execution of liveness properties such as “do X at least three times.” To model liveness requirements in BP directly and independently, we propose idioms for tagging states with “must-finish;’ indicating that tasks are yet to be completed. We show that this idiom allows a direct specification of known requirements patterns from the literature. We also offer semantics and two execution mechanisms, one based on a translation to Büchi automata and the other based on a Markov decision process (MDP). The latter approach offers the possibility of utilizing deep reinforcement learning (DRL) algorithms, which bear the potential to handle large software systems effectively. This paper presents a qualitative and quantitative assessment of the proposed approach using a proof-of-concept tool. A formal analysis of the MDP-based execution mechanism is given in an appendix.

We present Provengo, a comprehensive suite of tools designed to facilitate the implementation of Scenario-Driven Model-Based Testing (SDMBT), an innovative approach that utilizes scenarios to construct a model encompassing the user's perspective and the system's business value while also defining the desired outcomes. With the assistance of Provengo, testers gain the ability to effortlessly create natural user stories and seamlessly integrate them into a model capable of generating effective tests. The demonstration illustrates how SDMBT effectively addresses the bootstrapping challenge commonly encountered in model-based testing (MBT) by enabling incremental development, starting from simple models and gradually augmenting them with additional stories.

We present a new model-based approach for testing systems that use sequences of actions and assertions as test vectors. Our solution includes a method for quantifying testing quality, a tool for generating high-quality test suites based on the coverage criteria we propose, and a framework for assessing risks. For testing quality, we propose a method that specifies generalized coverage criteria over sequences of actions, which extends previous approaches. Our publicly available tool demonstrates how to extract effective test suites from test plans based on these criteria. We also present a Bayesian approach for measuring the probabilities of bugs or risks, and show how this quantification can help achieve an informed balance between exploitation and exploration in testing. Finally, we provide an empirical evaluation demonstrating the effectiveness of our tool in finding bugs, assessing risks, and achieving coverage.

We identify and demonstrate a weakness of Petri Nets (PN) in specifying composite behavior of reactive systems. Specifically, we show how, when specifying multiple requirements in one PN model, modelers are obliged to specify mechanisms for combining these requirements. This yields, in many cases, over-specification and incorrect models. We demonstrate how some execution paths are missed, and some are generated unintentionally. To support this claim, we analyze PN models from the literature, identify the combination mechanisms, and demonstrate their effect on the correctness of the model. To address this problem, we propose to model the system behavior using behavioral programming (BP), a software development and modeling paradigm designed for seamless integration of independent requirements. Specifically, we demonstrate how the semantics of BP, which define how to interweave scenarios into a single model, allow for avoiding the over-specification. Additionally, while BP maintains the same mathematical properties as PN, it provides means for changing the model dynamically, thus increasing the agility of the specification. We compare BP and PN in quantitative and qualitative measures by analyzing the models, their generated execution paths, and the specification process. Finally, while BP is supported by tools that allow for applying formal methods and reasoning techniques to the model, it lacks the legacy of PN tools and algorithms. To address this issue, we propose semantics and a tool for translating BP models to PN and vice versa.

Modern systems require programmers to develop code that dynamically adapts to different contexts, leading to the evolution of new context-oriented programming languages. These languages introduce new software-engineering challenges, such as: how to maintain the separation of concerns of the codebase? how to model the changing behaviors? how to verify the system behavior? and more. This paper introduces Context-Oriented Behavioral Programming (COBP) — a novel paradigm for developing context-aware systems, centered on natural and incremental specification of context-dependent behaviors. As the name suggests, we combine behavioral-programming (BP) — a scenario-based modeling paradigm — with context idioms that explicitly specify when scenarios are relevant and what information they need. The core idea is to connect the behavioral model with a data model that represents the context, allowing an intuitive connection between the models via update and select queries. Combining behavioral-programming with context-oriented programming brings the best of the two worlds, solving issues that arise when using each of the approaches in separation. We begin with providing abstract semantics for COBP and two implementations for the semantics, laying the foundations for applying reasoning algorithms to context-aware behavioral programs. Next, we exemplify the semantics with formal specifications of systems, including a variant of Conway’s Game of Life. Then, we provide two case studies of real-life context-aware systems (one in robotics and another in IoT) that were developed using this tool. Throughout the examples and case studies, we provide design patterns and a methodology for coping with the above challenges. The case studies show that the proposed approach is applicable for developing real-life systems, and presents measurable advantages over the alternatives — behavioral programming alone and context-oriented programming alone. We present a paradigm allowing programmers and system engineers to capture complex context-dependent requirements and align their code with such requirements.

In this paper, we evolve heuristics to guide staged deepening search for the hard game of FreeCell, obtaining top-notch solvers for this human-challenging puzzle. We first devise several novel heuristic measures using minimal domain knowledge and then use them as building blocks in two evolutionary setups involving a standard genetic algorithm and policy-based, genetic programming. Our evolved solvers outperform the best FreeCell solver to date by three distinct measures: 1) number of search nodes is reduced by over 78%; 2) time to solution is reduced by over 94%; and 3) average solution length is reduced by over 30%. Our top solver is the best published FreeCell player to date, solving 99.65% of the standard Microsoft 32 K problem set. Moreover, it is able to convincingly beat high-ranking human players.

We evolve heuristics to guide staged deepening search for the hard game of FreeCell, obtaining top-notch solvers for this NP-Complete, human-challenging puzzle. We first devise several novel heuristic measures and then employ a Hillis-style coevolutionary genetic algorithm to find efficient combinations of these heuristics. Our results significantly surpass the best published solver to date by three distinct measures: 1) Number of search nodes is reduced by 87%; 2) time to solution is reduced by 93%; and 3) average solution length is reduced by 41%. Our top solver is the best published FreeCell player to date, solving 98% of the standard Microsoft 32K problem set, and also able to beat high-ranking human players.

We use genetic algorithms to evolve highly successful solvers for two puzzles: FreeCell and the Sliding-Tile Puzzle.

We use genetic programming to evolve highly successful solvers for two puzzles: Rush Hour and FreeCell.

We evolve heuristics to guide IDA* search for the 6x6 and 8x8 versions of the Rush Hour puzzle, a PSPACE-Complete problem, for which no efficient solver has yet been reported. No effective heuristic functions are known for this domain, and--before applying any evolutionary thinking--we first devise several novel heuristic measures, which improve (non-evolutionary) search for some instances, but hinder search substantially for many other instances. We then turn to genetic programming (GP) and find that evolution proves immensely efficacious, managing to combine heuristics of such highly variable utility into composites that are nearly always beneficial, and far better than each separate component. GP is thus able to beat both the human player of the game and also the human designers of heuristics.