Search algorithms for automated validation

A novel search technique called highway search is introduced. The search technique relies on a highway simulation which takes several homogeneous walks through a (possibly infinite) state space. Furthermore, we provide a memory-efficient algorithm that approximates a highway search and we prove that, under particular conditions, they coincide. The effectiveness of highway search is compared to two mainstream search techniques, viz. random search and randomised depth-first search. Our results demonstrate that randomised depth-first search explores the least amount of states in the effort of finding states of interest, whereas a highways search yields the shortest witnessing traces to such states.     

A note on risk-sensitive control of invariant models

According to Assaf, a dynamic programming problem is called invariant if its transition mechanism depends only on the chosen action. This paper studies properties of risk-sensitive invariant problems with a general state space. The main result establishes the optimality equation for the risk-sensitive average cost criterion without any restrictions on the risk factor. Moreover, a practical algorithm is provided for solving the optimality equation in case of a finite action space.     

Solving scheduling problems by untimed model checking

In this article, we show how scheduling problems can be modelled in untimed process algebra, by using special tick actions. A minimal-cost trace leading to a particular action, is one that minimises the number of tick steps. As a result, we can use any (timed or untimed) model checking tool to find shortest schedules. Instantiating this scheme to μCRL, we profit from a richer specification language than timed model checkers usually offer. Also, we can profit from efficient distributed state space generators. We propose a variant of breadth-first search that visits all states between consecutive tick steps, before moving to the next time slice. We experimented with a sequential and a distributed implementation of this algorithm. In addition, we experimented with beam search, which visits only parts of the search space, to find near-optimal solutions. Our approach is applied to find optimal schedules for test batches of a realistic clinical chemical analyser, which performs several kinds of tests on patient samples.     

A fault tolerant peer-to-peer spatial data structure

In recent years, many layered indexing techniques over distributed hash table (DHT)-based peer-to-peer (P2P) systems have been proposed to realize distributed range search. In this paper, we present a fault tolerant constant degree dynamic Distributed Spatial Data Structure called DSDS that supports orthogonal range search on a set of N d-dimensional points published on n nodes. We describe a total order binary relation algorithm to publish points among supernodes and determine supernode keys. A non-redundant rainbow skip graph is used to coordinate message passing among nodes. The worst case orthogonal range search cost in a d-dimensional DSDS with n nodes is \(O\left (\log n+m+\frac {K}{B}\right )\) messages, where m is the number of nodes intersecting the query, K is the number of points reported in range, and B is the number of points that can fit in one message. A complete backup copy of data points stored in other nodes provides redundancy for our DSDS. This redundancy permits answering a range search query in the case of failure of a single node. For single node failure, the DSDS routing system can be recovered to a fully functional state at a cost of O(log n) messages. Backup sets in DSDS nodes are used to first process a query in the most efficient dimension, and then used to process a query containing the data in a failed node in d-dimensional space. The DSDS search algorithm can process queries in d-dimensional space and still tolerate failure of one node. Search cost in the worst case with a failed node increases to \(O\left (d\log n+dm+\frac {K}{B}\right )\) messages for d dimensions.     

An upper bound on the time complexity of iterative-deepening-A*

This paper establishes an upper bound on the time complexity of iterative-deepening-A^* (IDA^*) in terms of the number of states that are surely-expanded by A^* during a state space tree search. It is shown that given an admissible evaluation function, IDA^* surely-expands in the worst caseN(N+1)/2 states, whereN is the number of states that are surely-expanded by A^*. The conditions that give rise to the worst case performance of IDA^* on any state space tree are described. Worst case examples are also given for uniform and non-uniform state space trees.This work was supported in part by the Canadian Natural Sciences and Engineering Research Council Grant NSERC3599.     

A beam search approach to the container loading problem

The single container loading problem is a three-dimensional packing problem in which a container has to be filled with a set of boxes. The objective is to maximize the space utilization of the container. This problem has wide applications in the logistics industry. In this work, a new constructive approach to this problem is introduced. The approach uses a beam search strategy. This strategy can be viewed as a variant of the branch-and-bound search that only expands the most promising nodes at each level of the search tree. The approach is compared with state-of-the-art algorithms using 16 well-known sets of benchmark instances. Results show that the new approach outperforms all the others for each set of instances.     

Genetic hybrid tuning of VARMAX and state space algorithms

The aim of the study was to monitor the system theoretic exogenous variables augmented state space algorithm of Aoki (State space modelling of time series. Springer, Heidelberg, 1987) and the VARMAX algorithm of Spliid (J Am Stat Assoc 78(384):843–849, 1983) within a geno-mathematical framework towards optimal parametric conditions/search intervals. Both algorithms were implemented as an integrated support library for a general computational platform, the Genetic Hybrid Algorithm (GHA), where some key parameters of the algorithms are defined in a search process utilizing a mixed geno-mathematical search technique. The empirical results of our tests using real economic data from the European stock market are encouraging. Specifically, the information criteria used in the VARMAX-search (Vector Autoregressive Moving Average algorithm with Exogenous variables) algorithm tend to favor parsimonious model representations automatically. Furthermore, the state space algorithm captures almost the same dynamics as the complex VARMAX-model estimated in the study. Both algorithms have encouraging in sample properties. When generating k-steps forecasts out-of-sample, k > 1, the state space algorithm seems to deteriorate faster than the VARMAX algorithm, however. The results suggest that more empirical testing is needed, especially in different situations with different degrees of model order and stationarity conditions, in order to provide more evidence on the suitability of the competing methods in particular cases. We demonstrated that the Genetic Hybrid Algorithm can be used as a generic platform for parametric search in vector valued time series modelling. Efficient procedures for optimal grouping of the individual time series processes and recognition of heteroskedasticity may improve the performance of the algorithms further.     

Abstraction-based verification of codiagnosability for discrete event systems

In this paper, we investigate the verification of codiagnosability for discrete event systems (DES). That is, it is desired to ascertain if the occurrence of system faults can be detected based on the information of multiple local sites that partially observe the overall DES. As an improvement of existing codiagnosability tests that resort to the original DES with a potentially computationally infeasible state space, we propose a method that employs an abstracted system model on a smaller state space for the codiagnosability verification. Furthermore, we show that this abstraction can be computed without explicitly evaluating the state space of the original model in the practical case where the DES is composed of multiple subsystems.     

Characterizing reinforcement learning methods through parameterized learning problems

The field of reinforcement learning (RL) has been energized in the past few decades by elegant theoretical results indicating under what conditions, and how quickly, certain algorithms are guaranteed to converge to optimal policies. However, in practical problems, these conditions are seldom met. When we cannot achieve optimality, the performance of RL algorithms must be measured empirically. Consequently, in order to meaningfully differentiate learning methods, it becomes necessary to characterize their performance on different problems, taking into account factors such as state estimation, exploration, function approximation, and constraints on computation and memory. To this end, we propose parameterized learning problems, in which such factors can be controlled systematically and their effects on learning methods characterized through targeted studies. Apart from providing very precise control of the parameters that affect learning, our parameterized learning problems enable benchmarking against optimal behavior; their relatively small sizes facilitate extensive experimentation. Based on a survey of existing RL applications, in this article, we focus our attention on two predominant, ??first order?? factors: partial observability and function approximation. We design an appropriate parameterized learning problem, through which we compare two qualitatively distinct classes of algorithms: on-line value function-based methods and policy search methods. Empirical comparisons among various methods within each of these classes project Sarsa(??) and Q-learning(??) as winners among the former, and CMA-ES as the winner in the latter. Comparing Sarsa(??) and CMA-ES further on relevant problem instances, our study highlights regions of the problem space favoring their contrasting approaches. Short run-times for our experiments allow for an extensive search procedure that provides additional insights on relationships between method-specific parameters??such as eligibility traces, initial weights, and population sizes??and problem instances.     

Reasoning and predicting POMDP planning complexity via covering numbers

Partially observable Markov decision processes (POMDPs) provide a rich mathematical framework for planning tasks in partially observable stochastic environments. The notion of the covering number, a metric of capturing the search space size of a POMDP planning problem, has been proposed as a complexity measure of approximate POMDP planning. Existing theoretical results are based on POMDPs with finite and discrete state spaces and measured in the l ₁-metric space. When considering heuristics, they are assumed to be always admissible. This paper extends the theoretical results on the covering numbers of different search spaces, including the newly defined space reachable under inadmissible heuristics, to the l _n-metric spaces. We provide a simple but scalable algorithm for estimating covering numbers. Experimentally, we provide estimated covering numbers of the search spaces reachable by following different policies on several benchmark problems, and analyze their abilities to predict the runtime of POMDP planning algorithms.     

Optimal control of a single-link flexible manipulator

This paper deals with an exact state space dynamic model for manipulators with flexible links. We use the Bernoulli-Euler beam equations to derive a frequency domain matrix transfer function. This transfer function is then used to compute the Laplace transform of the state vector as a function of the lateral position along a single link manipulator. The problem of optimal end point control of the beam is then addressed. A sixth-order state space model is derived for the manipulator and the controller is based on this model. Several control laws are studied for this model. Next, the manipulator is modeled as eighth order but the control law based on the sixth-order model is retained. We then estimate the six states from the output of the eighth-order model and feed these states back to the controller to derive the control torque used to drive the manipulator. A filter is introduced to compensate for spillover. The results are very satisfactory, and are illustrated by simulated case studies.     

Computation, approximation and stability of explicit feedback min-max nonlinear model predictive control

This paper presents an approximate multi-parametric Nonlinear Programming (mp-NLP) approach to explicit solution of feedback min-max NMPC problems for constrained nonlinear systems in the presence of bounded disturbances and/or parameter uncertainties. It is based on an orthogonal search tree structure of the state space partition and consists in constructing a piecewise nonlinear (PWNL) approximation to the optimal sequence of feedback control policies. Conditions guaranteeing the robust stability of the closed-loop system in terms of a finite l₂-gain are derived.     

Exact controllability of a Rayleigh beam with a single boundary control

We prove exact boundary controllability for the Rayleigh beam equation ${\varphi_{tt} -\alpha\varphi_{ttxx} + A\varphi_{xxxx} = 0, 0 < x < l, t > 0}$ with a single boundary control active at one end of the beam. We consider all combinations of clamped and hinged boundary conditions with the control applied to either the moment ${\varphi_{xx}(l, t)}$ or the rotation angle ${\varphi_{x}(l, t)}$ at an end of the beam. In each case, exact controllability is obtained on the space of optimal regularity for L ²(0, T) controls for ${T > 2l\sqrt{\frac{\alpha}{A}}}$ . In certain cases, e.g., the clamped case, the optimal regularity space involves a quotient in the velocity component. In other cases, where the regularity for the observed problem is below the energy level, a quotient space may arise in solutions of the observed problem.     

Nonlinear continuous multi-response problems: a novel two-phase hybrid genetic based metaheuristic

Generally the most real world production systems are tackling several different responses and the problem is optimizing these responses concurrently. This study strives to present a new two-phase hybrid genetic based metaheuristic for optimizing nonlinear continuous multi-response problems. Premature convergence and getting stuck in local optima, which makes the algorithm time consuming, are common problems dealing with genetic algorithms (GAs). So we hybridize GA with a clustering approach and particle swarm optimization algorithm (PSO) to make a balanced relationship between time consuming and premature termination. The proposed algorithm also tries to find Ideal Points (IPs) for response functions. IPs are considered as improvement measures that determine when PSO should start. PSO based local search exploit Pareto archive solutions to enhance performance of the algorithm by expanding the search space. Since there is no standard benchmark in this field, we use two case studies from distinguished paper in multi-response optimization and compare the results with some of the mentioned algorithms in the literature. Results show the outperformance of the proposed algorithm than all of them.     

求解非线性方程组的元胞自动机方法及其全局收敛性证明

为了求得非线性方程组所有精确解,根据元胞自动机的特点构造了求解非线性方程组的全局收敛算法。在该算法中,将非线性方程组解的理论搜索空间划分为离散搜索空间,将离散搜索空间定义为元胞空间;离散搜索空间的每个点就是一个元胞,而一个元胞对应着非线性方程组的一个试探解;元胞的状态由其空间位置及位置修正量构成。将元胞空间划分为若干个非空子集,所有元胞的状态从一个非空子集转移到另一个非空子集的状态演化过程实现了元胞空间对理论搜索空间的搜索。在元胞状态演化过程中,元胞从一个状态转移到另一个状态的状态转移概率可以计算出来;元胞演化过程中的每个状态对应于有限Markov链上的一个状态。利用可归约随机矩阵的稳定性条件证明了该算法具有全局收敛性。仿真实例表明该算法是高效的。     

Incremental Beam search

Beam search is a heuristic search algorithm that explores a state-space graph by expanding w most promising nodes at each level (depth) of the graph, where w is called the beam-width which is taken as input from the user. The quality of the solution produced by beam search does not always monotonically improve with the increase in beam-width making it difficult to choose an appropriate beam-width for effective use. We present an algorithm called Incremental Beam Search (IncB) which guarantees monotonicity, and is also anytime in nature. Experimental results on the sliding-tile puzzle, the traveling salesman, and the single-machine scheduling problems show that IncB significantly outperforms basic monotonic methods such as iterative widening beam search as well as some of the state-of-the-art anytime heuristic search algorithms in terms of the quality of the solution produced at the end as well as the anytime performance.     

Quantum Mechanical Search and Harmonic Perturbation

Perturbation theory in quantum mechanics studies how quantum systems interact with their environmental perturbations. Harmonic perturbation is a rare special case of time-dependent perturbations in which exact analysis exists. Some important technology advances, such as masers, lasers, nuclear magnetic resonance, etc., originated from it. Here we add quantum computation to this list with a theoretical demonstration. Based on harmonic perturbation, a quantum mechanical algorithm is devised to search the ground state of a given Hamiltonian. The intrinsic complexity of the algorithm is continuous and parametric in both time T and energy E. More precisely, the probability of locating a search target of a Hamiltonian in N-dimensional vector space is shown to be 1/(1 + c N E⁻²T⁻²) for some constant c. This result is optimal. As harmonic perturbation provides a different computation mechanism, the algorithm may suggest new directions in realizing quantum computers.      

GPU-based parallel vertex substitution algorithm for the p-median problem

We introduce a GPU-based parallel vertex substitution (pVS) algorithm for the p-median problem using the CUDA architecture by NVIDIA. pVS is developed based on the best profit search algorithm, an implementation of vertex substitution (VS), that is shown to produce reliable solutions for p-median problems. In our approach, each candidate solution in the entire search space is allocated to a separate thread, rather than dividing the search space into parallel subsets. This strategy maximizes the usage of GPU parallel architecture and results in a significant speedup and robust solution quality. Computationally, pVS reduces the worst case complexity from sequential VS’s O(p · n²) to O(p · (n ? p)) on each thread by parallelizing computational tasks on GPU implementation. We tested the performance of pVS on two sets of numerous test cases (including 40 network instances from OR-lib) and compared the results against a CPU-based sequential VS implementation. Our results show that pVS achieved a speed gain ranging from 10 to 57 times over the traditional VS in all test network instances.     

A new nonlinear classifier with a penalized signed fuzzy measure using effective genetic algorithm

This paper proposes a new nonlinear classifier based on a generalized Choquet integral with signed fuzzy measures to enhance the classification accuracy and power by capturing all possible interactions among two or more attributes. This generalized approach was developed to address unsolved Choquet-integral classification issues such as allowing for flexible location of projection lines in n-dimensional space, automatic search for the least misclassification rate based on Choquet distance, and penalty on misclassified points. A special genetic algorithm is designed to implement this classification optimization with fast convergence. Both the numerical experiment and empirical case studies show that this generalized approach improves and extends the functionality of this Choquet nonlinear classification in more real-world multi-class multi-dimensional situations.