Catálogo de publicaciones - libros

Identifying and exploiting hidden problem structures is recognized as a fundamental way to deal with the intractability of combinatorial problems. Recently, a particular structure called (strong) backdoor has been identified in the context of the satisfiability problem. Connections has been established between backdoors and problem hardness leading to a better approximation of the worst case time complexity. Strong backdoor sets can be computed for any tractable class. In [1], a method for the approximation of strong backdoor sets for the Horn-Sat fragment was proposed. This approximation is realized in two steps. First, the best Horn renaming of the original CNF formula, in term of number of clauses, is computed. Then a Horn strong backdoor set is extracted from the non Horn part of the renamed formula. in this article, we propose computing Horn strong backdoor sets using the same scheme but minimizing the number of positive literals in the non Horn part of the renamed formula instead of minimizing the number of non Horn clauses. Then we extend this method to the class of ordered formulas [2] which is an extension of the Horn class. This method insure to obtain ordered strong backdoor sets of size less or equal than the size of Horn strong backdoor sets (never greater). Experimental results show that these new methods allow to reduce the size of strong backdoor sets on several instances and that their exploitation also allow to enhance the efficiency of satisfiability solvers.

Due to the big success of the Pareto’s Optimality Criteria for multi–objective problems, an increasing number of algorithms that use it have been proposed. The goal of these algorithms is to find a set of non–dominated solutions that are close to the True Pareto front. As a consequence, a new problem has arisen, how can the performance of different algorithms be evaluated? In this paper, we present a novel system to evaluate non–dominated sets, based on a few assumptions about the preferences of the decision maker. In order to evaluate the performance of our approach, we build several test cases considering different topologies of the Pareto front. The results are compared with those of another popular metric, the S–metric, showing equal or better performance.

In this paper we develop a framework for the approximation of the entire set of -efficient solutions of a multi-objective optimization problem with stochastic search algorithms. For this, we propose the set of interest, investigate its topology and state a convergence result for a generic stochastic search algorithm toward this set of interest. Finally, we present some numerical results indicating the practicability of the novel approach.

Multicriterion classification methods traditionally employed in the spatial decision-making penalize the complex phenomena of interaction between the criteria. Indeed, the most classical procedure in the multicriterion evaluation consists in considering a simple weighted arithmetical average to incorporate information characterizing decision maker’s preferences on the set of criteria. However, in reality, the criteria interact (correlation, interchangeability, complementarity, ...) and the preferential independence hypothesis is rarely checked. The ultimate goal of this study is to optimize the quality of decision in the land management context. Therefore, a decision support model is designed to meet this objective and to claim with an extensible, generic and deterministic model based on the axiomatic of decision strategies authorizing the interactions between criteria. We define a new approach replacing the additivity property in the performance aggregation phase by a more reliable property: the growth using non-additive discriminant operators resulting from the fuzzy theory: Choquet’s Integral. Also, the suggested model allows the professionals to carry out diagnostics and proposes adapted actions by modelling the multi-actor negotiation and participation using multi-agents systems.

In this paper we present a new type of Radial Basis Function (RBF) Neural Network based in order statistics for image classification applications. The proposed neural network uses the Median M-type (MM) estimator in the scheme of radial basis function to train the neural network. The proposed network is less biased by the presence of outliers in the training set and was proved an accurate estimation of the implied probabilities. From simulation results we show that the proposed neural network has better classification capabilities in comparison with other RBF based algorithms.

Artificial neural networks are used to solve problems that are difficult for humans and computers. Unfortunately, artificial neural network training is time consuming and, because it is a random process, several cold starts are recommended. Neural network training is typically a two step process. First, the network’s weights are initialized using a no greedy method to elude local minima. Second, an optimization method (i.e., conjugate gradient learning) is used to quickly find the nearest local minimum. In general, training must be performed to reduce the mean square error computed between the desired output and the actual network output. One common method for network initialization is simulated annealing; it is used to assign good starting values to the network’s weights before performing the optimization. The performance of simulated annealing depends strongly on the cooling process. A cooling schedule based on temperature cycling is proposed to improve artificial neural network training. It is shown that temperature cycling reduces training time while decreasing the mean square error on auto-associative neural networks. Three auto-associative problems: The Trifolium, The Cardioid, and The Lemniscate of Bernoulli, are solved using exponential cooling, linear cooling and temperature cycling to verify our results.

Self-organizing neural networks (SONN) driven by softmax weight renormalization are capable of finding high quality solutions of difficult assignment optimization problems. The renormalization is shaped by a temperature parameter - as the system cools down the assignment weights become increasingly crisp. It has been recently observed that there exists a critical temperature setting at which SONN is capable of powerful intermittent search through a multitude of high quality solutions represented as meta-stable states of SONN adaptation dynamics. The critical temperature depends on the problem size. It has been hypothesized that the intermittent search by SONN can occur only at temperatures close to the first (symmetry breaking) bifurcation temperature of the autonomous renormalization dynamics. In this paper we provide a rigorous support for the hypothesis by studying stability types of SONN renormalization equilibria.

A plug-in for the Machine Learning Environment Yale has been developed that automatically structures digital music corpora into similarity clusters using a SOM on the basis of features that are extracted from files in a test corpus. Perceptionally similar music files are represented in the same cluster. A human user was asked to rate music files according to their subjective similarity. Compared to the user’s judgment, the system had a mean accuracy of 65.7%. The accuracy of the framework increases with the size of the music corpus to a maximum of 75%. The study at hand shows that it is possible to categorize music files into similarity clusters by taking solely mathematical features into account that have been extracted from the files themselves. This allows for a variety of different applications like lowering the search space in manual music comparison, or content-based music recommendation.

Most heteroassociative memories models intend to achieve the recall of the entire trained pattern. The Alpha-Beta associative memories only ensure the correct recall of the trained patterns in autoassociative memories, but not for the heteroassociative memories. In this work we present a new algorithm based on the Alpha-Beta Heteroassociative memories that allows, besides correct recall of some altered patterns, perfect recall of all the trained patterns, without ambiguity. The theoretical support and some experimental results are presented.

There are several challenges for AI models of higher cognitive abilities like the profusion of knowledge, different forms of reasoning, the gap between neuro-inspired approaches and conceptual representations, the problem of inconsistent data, and the manifold of computational paradigms. The I-Cog architecture – proposed as a step towards a solution for these problems – consists of a reasoning device based on analogical reasoning, a rewriting mechanism operating on the knowledge base, and a neuro-symbolic interface for robust learning from noisy data. I-Cog is intended as a framework for human-level intelligence (HLI).