Competence Models and the Maintenance Problem

Case-based reasoning (CBR) systems solve problems by retrieving and adapting the solutions to similar problems that have been stored previously as a case base of individual problem solving episodes or cases. The maintenance problem refers to the problem of how to optimize the performance of a CBR system during its operational lifetime. It can have a significant impact on all the knowledge sources associated with a system (the case base, the similarity knowledge, the adaptation knowledge, etc.), and over time, any one, or more, of these knowledge sources may need to be adapted to better fit the current problem-solving environment. For example, many maintenance solutions focus on the maintenance of case knowledge by adding, deleting, or editing cases. This has lead to a renewed interest in the issue of case competence, since many maintenance solutions must ensure that system competence is not adversely affected by the maintenance process. In fact, we argue that ultimately any generic maintenance solution must explicitly incorporate competence factors into its maintenance policies. For this reason, in our work we have focused on developing explanatory and predictive models of case competence that can provide a sound foundation for future maintenance solutions. In this article we provide a comprehensive survey of this research, and we show how these models have been used to develop a number of innovative and successful maintenance solutions to a variety of different maintenance problems.     

Optimization via intermittency with a self-organizing neural network

One of the major obstacles in using neural networks to solve combinatorial optimization problems is the convergence toward one of the many local minima instead of the global minima. In this letter, we propose a technique that enables a self-organizing neural network to escape from local minima by virtue of the intermittency phenomenon. It gives rise to novel search dynamics that allow the system to visit multiple global minima as meta-stable states. Numerical experiments performed suggest that the phenomenon is a combined effect of Kohonen-type competitive learning and the iterated softmax function operating near bifurcation. The resultant intermittent search exhibits fractal characteristics when the optimization performance is at its peak in the form of 1/f signals in the time evolution of the cost, as well as power law distributions in the meta-stable solution states. TheN-Queens problem is used as an example to illustrate the meta-stable convergence process that sequentially generates, in a single run, 92 solutions to the 8-Queens problem and 4024 solutions to the 17-Queens problem.     

Configuration landscape analysis and backbone guided local search.: Part I: Satisfiability and maximum satisfiability

Boolean satisfiability (SAT) and maximum satisfiability (Max-SAT) are difficult combinatorial problems that have many important real-world applications. In this paper, we first investigate the configuration landscapes of local minima reached by the WalkSAT local search algorithm, one of the most effective algorithms for SAT. A configuration landscape of a set of local minima is their distribution in terms of quality and structural differences relative to an optimal or a reference solution. Our experimental results show that local minima from WalkSAT form large clusters, and their configuration landscapes constitute big valleys, in that high quality local minima typically share large partial structures with optimal solutions. Inspired by this insight into WalkSAT and the previous research on phase transitions and backbones of combinatorial problems, we propose and develop a novel method that exploits the configuration landscapes of such local minima. The new method, termed as backbone-guided search, can be embedded in a local search algorithm, such as WalkSAT, to improve its performance. Our experimental results show that backbone-guided local search is effective on overconstrained random Max-SAT instances. Moreover, on large problem instances from a SAT library (SATLIB), the backbone guided WalkSAT algorithm finds satisfiable solutions more often than WalkSAT on SAT problem instances, and obtains better solutions than WalkSAT on Max-SAT problem instances, improving solution quality by 20% on average.     

Metric Learning for Image Alignment

Image alignment has been a long standing problem in computer vision. Parameterized Appearance Models (PAMs) such as the Lucas-Kanade method, Eigentracking, and Active Appearance Models are commonly used to align images with respect to a template or to a previously learned model. While PAMs have numerous advantages relative to alternate approaches, they have at least two drawbacks. First, they are especially prone to local minima in the registration process. Second, often few, if any, of the local minima of the cost function correspond to acceptable solutions. To overcome these problems, this paper proposes a method to learn a metric for PAMs that explicitly optimizes that local minima occur at and only at the places corresponding to the correct fitting parameters. To the best of our knowledge, this is the first paper to address the problem of learning a metric to explicitly model local properties of the PAMs’ error surface. Synthetic and real examples show improvement in alignment performance in comparison with traditional approaches. In addition, we show how the proposed criteria for a good metric can be used to select good features to track.     

Multimodal function optimization using minimal representation size clustering and its application to planning multipaths

A novel genetic algorithm (GA) using minimal representation size cluster (MRSC) analysis is designed and implemented for solving multimodal function optimization problems. The problem of multimodal function optimization is framed within a hypothesize-and-test paradigm using minimal representation size (minimal complexity) for species formation and a GA. A multiple-population GA is developed to identify different species. The number of populations, thus the number of different species, is determined by the minimal representation size criterion. Therefore, the proposed algorithm reveals the unknown structure of the multimodal function when a priori knowledge about the function is unknown. The effectiveness of the algorithm is demonstrated on a number of multimodal test functions. The proposed scheme results in a highly parallel algorithm for finding multiple local minima. In this paper, a path-planning algorithm is also developed based on the MRSC_GA algorithm. The algorithm utilizes MRSC_GA for planning paths for mobile robots, piano-mover problems, and N-link manipulators. The MRSC_GA is used for generating multipaths to provide alternative solutions to the path-planning problem. The generation of alternative solutions is especially important for planning paths in dynamic environments. A novel iterative multiresolution path representation is used as a basis for the GA coding. The effectiveness of the algorithm is demonstrated on a number of two-dimensional path-planning problems.     

一种求解企业员工指派问题的离散状态转移算法

员工指派问题是运筹学中的一类整数规划问题,为了寻找最佳的员工指派方案,使得完成所有任务的总成本代价最小,本文研究了一种新的离散状态转移算法.在一次状态转移的基础上提出了二次状态转移的概念,从而扩大了候选解集的范围,并提高候选解集的多样性.为了克服算法在迭代后期更新缓慢的缺点,提出了停滞回溯策略,即当算法陷入局部最优解时进行回溯操作,从历史停滞解中随机选择一个更新当前最优解.通过与模拟退火算法进行测试比较实验,证明了本文所提出算法的有效性,同时该算法提高了求解员工指派问题的成功率与稳定性.     

Multimodal optimization using a bi-objective evolutionary algorithm

In a multimodal optimization task, the main purpose is to find multiple optimal solutions (global and local), so that the user can have better knowledge about different optimal solutions in the search space and as and when needed, the current solution may be switched to another suitable optimum solution. To this end, evolutionary optimization algorithms (EA) stand as viable methodologies mainly due to their ability to find and capture multiple solutions within a population in a single simulation run. With the preselection method suggested in 1970, there has been a steady suggestion of new algorithms. Most of these methodologies employed a niching scheme in an existing single-objective evolutionary algorithm framework so that similar solutions in a population are deemphasized in order to focus and maintain multiple distant yet near-optimal solutions. In this paper, we use a completely different strategy in which the single-objective multimodal optimization problem is converted into a suitable bi-objective optimization problem so that all optimal solutions become members of the resulting weak Pareto-optimal set. With the modified definitions of domination and different formulations of an artificially created additional objective function, we present successful results on problems with as large as 500 optima. Most past multimodal EA studies considered problems having only a few variables. In this paper, we have solved up to 16-variable test problems having as many as 48 optimal solutions and for the first time suggested multimodal constrained test problems which are scalable in terms of number of optima, constraints, and variables. The concept of using bi-objective optimization for solving single-objective multimodal optimization problems seems novel and interesting, and more importantly opens up further avenues for research and application.     

Snapshot ensembles of non-negative matrix factorization for stability of topic modeling

Recently many topic models such as Latent Dirichlet Allocation (LDA) and Non-negative Matrix Factorization (NMF) have made important progress towards generating high-level knowledge from a large corpus. However, these algorithms based on random initialization generate different results on the same corpus using the same parameters, denoted as instability problem. For solving this problem, ensembles of NMF are known to be much more stable and accurate than individual NMFs. However, training multiple NMFs for ensembling is computationally expensive. In this paper, we propose a novel scheme to obtain the seemingly contradictory goal of ensembling multiple NMFs without any additional training cost. We train a single NMF algorithm with the cyclical learning rate schedule, which can converge to several local minima along its optimization path. We save the results to the ensemble when the model converges, and then restart the optimization with a large learning rate that can help escape the current local minimum. Based on experiments performed on text corpora using a number of measures to assess, our method can reduce instability at no additional training cost, while simultaneously yields more accurate topic models than traditional single methods and ensemble methods.     

Multiscale Minimization of Global Energy Functions in Some Visual Recovery Problems

Many image analysis and computer vision problems have been expressed as the minimization of global energy functions describing the interactions between the observed data and the image representations to be extracted in a given task. In this note, we investigate a new comprehensive approach to minimize global energy functions using a multiscale relaxation algorithm. The energy function is minimized over nested subspaces of the original space of possible solutions. These subspaces consist of solutions which are constrained at different scales. The constrained relaxation is implemented via a coarse-to-fine multiresolution algorithm that yields fast convergence towards high quality estimates when compared to standard monoresolution or multigrid relaxation schemes. It also appears to be far less sensitive to local minima than standard relaxation algorithms. The efficiency of the approach is demonstrated on a highly nonlinear combinatorial problem which consists of estimating long-range motion in an image sequence on a discrete label space. The method is compared to standard relaxation algorithms on real world and synthetic image sequences.     

Bayesian object matching

Matching of object refers to the problem of inferring unknown co-occurrence or alignment between observations or samples in two data sets. Given two sets of equally many samples, the task is to find for each sample a representative sample in the other set, without prior knowledge on a distance measure between the sets. Given a distance measure, the problem would correspond to a linear assignment problem, the problem of finding a permutation that re-orders samples in one set to minimize the total distance. When no such measure is available, we need to consider more complex solutions. Typical approaches maximize statistical dependency between the two sets, whereas in this work we present a Bayesian solution that builds a joint model for the two sources. We learn a Bayesian canonical correlation analysis model that includes a permutation parameter for re-ordering the samples in one of the sets. We provide both variational and sampling-based inference for approximative Bayesian analysis, and demonstrate on three data sets that the resulting methods outperform the earlier solutions.     

Design of the Inverse Function Delayed Neural Network for Solving Combinatorial Optimization Problems

We have already proposed the inverse function delayed (ID) model as a novel neuron model. The ID model has a negative resistance similar to Bonhoeffer–van der Pol (BVP) model and the network has an energy function similar to Hopfield model. The neural network having an energy can converge on a solution of the combinatorial optimization problem and the computation is in parallel and hence fast. However, the existence of local minima is a serious problem. The negative resistance of the ID model can make the network state free from such local minima by selective destabilization. Hence, we expect that it has a potential to overcome the local minimum problems. In computer simulations, we have already shown that the ID network can be free from local minima and that it converges on the optimal solutions. However, the theoretical analysis has not been presented yet. In this paper, we redefine three types of constraints for the particular problems, then we analytically estimate the appropriate network parameters giving the global minimum states only. Moreover, we demonstrate the validity of estimated network parameters by computer simulations.      

A knowledge infrastructure for intelligent query answering in location-based services

Intelligent query answering in Location-based Services refers to their capability to provide mobile users with personalized and contextualized answers. Personalization is expected to lead to answers that better match user’s interests, as inferable from the user’s profile. Contextualization aims at not selecting answers that for some reason would not be appropriate at the time and place of the user query. These goals are beyond the current state of art in LBS, or are provided based on ad hoc solutions specific to the application at hand. This paper reports on the results of an investigation aiming at defining the knowledge infrastructure that should be developed within the LBS to make it capable of returning intelligent answers. We first discuss the data management features that make LBS different from other query answering systems. Next we propose a data infrastructure that builds on the idea of modular ontologies. We explain how the relevant knowledge may be incrementally set up and dynamically maintained based on an application-independent approach. Last we show how this knowledge is used to reformulate user’s queries via personalized and contextualized rewriting.     

Hohmann transfer via constrained optimization

Inspired by the geometric method proposed by Jean-Pierre MAREC, we first consider the Hohmann transfer problem between two coplanar circular orbits as a static nonlinear programming problem with an inequality constraint. By the Kuhn-Tucker theorem and a second-order sufficient condition for minima, we analytically prove the global minimum of the Hohmann transfer. Two sets of feasible solutions are found: one corresponding to the Hohmann transfer is the global minimum and the other is a local minimum. We next formulate the Hohmann transfer problem as boundary value problems, which are solved by the calculus of variations. The two sets of feasible solutions are also found by numerical examples. Via static and dynamic constrained optimizations, the solution to the Hohmann transfer problem is re-discovered, and its global minimum is analytically verified using nonlinear programming.     

Multicriteria programming in medical diagnosis and treatments

This paper deals with a special case of multicriteria optimization problems. The problems studied come from the medical domain and are of a very important practical relevance. One of the problems refers to the ranking of treatments for the Trigeminal Neuralgia. The second problem refers to a hierarchy of risk factors for Bronchial Asthma. The most common way to deal with a multiobjective optimization problem is to apply Pareto dominance relationship between solutions. But in the cases studied here, a decision cannot be made just by using Pareto dominance. In one of the experiments, all the potential solutions are nondominated (and we need to clearly find a hierarchy of these solutions) and in the second experiment most of the solutions are nondominated between them. We propose a novel multiple criteria procedure and then an evolutionary scheme is applied for solving the problems. Results obtained by the proposed approach in a very simple way are same as the results (or even better) obtained by applying weighted-sum method. The advantage of the proposed technique is that it does not require any additional information about the problem (like weights for each criteria in the case of weighted-sumapproach).     

Neural versus traditional approaches to the location of interacting hub facilities

In this paper we consider the optimal location of interacting hub facilities. Using the well-known quadratic integer programming formulation of the uncapacitated, single allocation, p-hub median problem (USApHMP), we demonstrate a mapping onto a Hopfield neural network which guarantees feasibility of the final solution. We also propose a novel modification to the Hopfield network which enables escape from local minima, thus improving final solution quality. A practical application of the USApHMP—a postal delivery network—is used to demonstrate that the quality of these Hopfield network solutions compares favorably to those obtained using both exact methods and simulated annealing. Well-known data sets from the literature are also tested using the Hopfield network approaches, and provide further evidence that optimal or near-optimal solutions can consistently be obtained. The speed advantages which can be attained when implementing neural networks in hardware make the Hopfield neural network a very attractive potential alternative to the existing solution techniques.     

Optimal Structure from Motion: Local Ambiguities and Global Estimates

Structure From Motion (SFM) refers to the problem of estimating spatial properties of a three-dimensional scene from the motion of its projection onto a two-dimensional surface, such as the retina. We present an analysis of SFM which results in algorithms that are provably convergent and provably optimal with respect to a chosen norm.In particular, we cast SFM as the minimization of a high-dimensional quadratic cost function, and show how it is possible to reduce it to the minimization of a two-dimensional function whose stationary points are in one-to-one correspondence with those of the original cost function. As a consequence, we can plot the reduced cost function and characterize the configurations of structure and motion that result in local minima. As an example, we discuss two local minima that are associated with well-known visual illusions. Knowledge of the topology of the residual in the presence of such local minima allows us to formulate minimization algorithms that, in addition to provably converge to stationary points of the original cost function, can switch between different local extrema in order to converge to the global minimum, under suitable conditions. We also offer an experimental study of the distribution of the estimation error in the presence of noise in the measurements, and characterize the sensitivity of the algorithm using the structure of Fisher's Information matrix.     

Boundary Gap Based Reactive Navigation in Unknown Environments

Due to the requirements for mobile robots to search or rescue in unknown environments, reactive navigation which plays an essential role in these applications has attracted increasing interest. However, most existing reactive methods are vulnerable to local minima in the absence of prior knowledge about the environment. This paper aims to address the local minimum problem by employing the proposed boundary gap (BG) based reactive navigation method. Specifically, the narrowest gap extraction algorithm (NGEA) is proposed to eliminate the improper gaps. Meanwhile, we present a new concept called boundary gap which enables the robot to follow the obstacle boundary and then get rid of local minima. Moreover, in order to enhance the smoothness of generated trajectories, we take the robot dynamics into consideration by using the modified dynamic window approach (DWA). Simulation and experimental results show the superiority of our method in avoiding local minima and improving the smoothness.      

Pickup and delivery problem using metaheuristics techniques

Dial-a-ride problem (DARP) is an optimization problem which deals with the minimization of the cost of the provided service where the customers are provided a door-to-door service based on their requests. This optimization model presented in earlier studies, is considered in this study. Due to the non-linear nature of the objective function the traditional optimization methods are plagued with the problem of converging to a local minima. To overcome this pitfall we use metaheuristics namely Simulated Annealing (SA), Particle Swarm Optimization (PSO), Genetic Algorithm (GA) and Artificial Immune System (AIS). From the results obtained, we conclude that Artificial Immune System method effectively tackles this optimization problem by providing us with optimal solutions.     

A basis for local minima of a symmetric frame topography

Optimization of indeterminate frames involves non-convex stress constraint functions which form a non-convex design space that results in multiple local minima, unknown in number to begin with. The current state-of-the-art in this field recommends employment of different arbitrary initial designs to have a reasonable assurance of reaching every local minimum which, under a particular load, is associated with a specific material distribution. In this study a basis is laid down for (a) determination, at the very outset, of the number of local minima that possibly may exist in a frame of symmetric topography, (b) definition, in terms of relative member stiffnesses, of the material distribution pattern associated with each local minimum, and (c) a guideline for evaluation of member forces for initial proportioning of the pattern, The application of the proposed method for evaluation of local minima is illustrated with an example problem.     

A local minimum for the 2-3-1 XOR network.

It was assumed proven that two-layer feedforward neural networks with t-1 hidden nodes, when presented with t input patterns, can not have any suboptimal local minima on the error surface. In this paper, however, we shall give a counterexample to this assumption. This counterexample consists of a region of local minima with nonzero error on the error surface of a neural network with three hidden nodes when presented with four patterns (the XOR problem). We will also show that the original proof is valid only when an unusual definition of local minimum is used.