Much recent work in bioinformatics has focused on the inference of various types of biological networks, representing gene regulation, metabolic processes, protein-protein interactions, etc. A common setting involves inferring network edges in a supervised fashion from a set of high-confidence edges, possibly characterized by multiple, heterogeneous data sets (protein sequence, gene expression, etc.). Here, we distinguish between two modes of inference in this setting: direct inference based upon similarities between nodes joined by an edge, and indirect inference based upon similarities between one pair of nodes and another pair of nodes. We propose a supervised approach for the direct case by translating it into a distance metric learning problem. A relaxation of the resulting convex optimization problem leads to the support vector machine (SVM) algorithm with a particular kernel for pairs, which we call the metric learning pairwise kernel (MLPK). We demonstrate, using several real biological networks, that this direct approach often improves upon the state-of-the-art SVM for indirect inference with the tensor product pairwise kernel.

We consider methods for aggregating preferences that are base d on the resolution of discrete optimization problems. For a review and references see Cook and Kress (1992), and Belkin and Levin (1990), and also David (1988) and Van B lokland-Vogelesang (1991). Some algorithmic aspects can be found in Barth elemy (1989) and Litvak (1982). The preferences are represented by arbitra ry binary relations (possibly weighted) or incomplete paired comparison matrices. The o utcome of an aggregation method is a set of "optimal" rankings (linear or weak ord ers) of the alternatives. Namely, a ranking is said to be optimal if it provides an ex tremum of some chosen objective function that expresses the connectio n (or proximity) between an arbitrary ranking and the original preferences.

Evolutionary processes proved very useful for solving optimization problems. In this work, we build a formalization of the notion of cooperation and competition of multiple systems working toward a common optimization goal of the population using evolutionary computation techniques. It is justified that evolutionary algorithms are more expressive than conventional recursive algorithms. Three subclasses of evolutionary algorithms are proposed here: bounded finite, unbounded finite and infinite types. Some results on completeness, optimality and search decidability for the above classes are presented. A natural extension of Evolutionary Turing Machine model developed in this paper allows one to mathematically represent and study properties of cooperation and competition in a population of optimized species.

In this paper we propose a method that learns to play Pac-Man. We define a set of high-level observation and action modules. Actions are temporally extended, and multiple action modules may be in effect concurrently. A decision of the agent is represented as a rule-based policy. For learning, we apply the cross-entropy method, a recent global optimization algorithm. The learned policies reached better score than the hand-crafted policy, and neared the score of average human players. We argue that learning is successful mainly because (i) the policy space includes the combination of individual actions and thus it is sufficiently rich, (ii) the search is biased towards low-complexity policies and low complexity solutions can be found quickly if they exist. Based on these principles, we formulate a new theoretical framework, which can be found in the Appendix as supporting material.

In evolutionary algorithms, the fitness of a population increases with time by mutating and recombining individuals and by a biased selection of more fit individuals. The right selection pressure is critical in ensuring sufficient optimization progress on the one hand and in preserving genetic diversity to be able to escape from local optima on the other hand. Motivated by a universal similarity relation on the individuals, we propose a new selection scheme, which is uniform in the fitness values. It generates selection pressure toward sparsely populated fitness regions, not necessarily toward higher fitness, as is the case for all other selection schemes. We show analytically on a simple example that the new selection scheme can be much more effective than standard selection schemes. We also propose a new deletion scheme which achieves a similar result via deletion and show how such a scheme preserves genetic diversity more effectively than standard approaches. We compare the performance of the new schemes to tournament selection and random deletion on an artificial deceptive problem and a range of NP-hard problems: traveling salesman, set covering and satisfiability.

In this paper we propose a Multi-Objective Ant Colony Optimization (MOACO) algorithm called CHAC, which has been designed to solve the problem of finding the path on a map (corresponding to a simulated battlefield) that minimizes resources while maximizing safety. CHAC has been tested with two different state transition rules: an aggregative function that combines the heuristic and pheromone information of both objectives and a second one that is based on the dominance concept of multiobjective optimization problems. These rules have been evaluated in several different situations (maps with different degree of difficulty), and we have found that they yield better results than a greedy algorithm (taken as baseline) in addition to a military behaviour that is also better in the tactical sense. The aggregative function, in general, yields better results than the one based on dominance.

Definitions First we recall relevent definitions. This objective function is piece-wise linear and convex. This objective function is piece-wise linear and convex. A matrix game is given by a (payoff) matrix A. To solve a matrix game is to find a row p (an optimal strategy for the row player), a column q (an optimal strategy for the column player), and a number v such that p = ( p The number v is known as the value of game. The pair ( p, q) is known as an equilibrium for the matrix game.

An approach to the classification problem of machine learning, based on building local classification rules, is developed. The local rules are considered as projections of the global classification rules to the event we want to classify. A massive global optimization algorithm is used for optimization of quality criterion. The algorithm, which has polynomial complexity in typical case, is used to find all high--quality local rules. The other distinctive feature of the algorithm is the integration of attributes levels selection (for ordered attributes) with rules searching and original conflicting rules resolution strategy. The algorithm is practical; it was tested on a number of data sets from UCI repository, and a comparison with the other predicting techniques is presented.

Abstract-- This article proposes the first known algorithm that achieves a constant-factor approximation of the minim um length tour for a Dubins' vehicle through n points on the plane. By Dubins' vehicle, we mean a vehicle constrained to move at constant speed along paths with bounded curvature without reversing direction. The Traveling Salesperson Problem (TSP) with its variations is one of the most widely known combinatorial optimization problems. While extensively studied in the literature, these problems continue to attract great inter est from a wide range of fields, including Operations Research, Mathematics and Computer Science. It is quite natural to formulate this problem in context of Dubins' vehicle, i.e., a non-holonomic vehicl e that is constrained to move along paths of bounded curvature, without reversing direction.

The problem of designing optimal trajectory for redundant manipulators has attracted many researchers for the last three decades. One of the main reasons is the use of kinematically redundant robots is expected to increase in the future due to their increased flexibility. Some of the extra capabilities include the ability to avoid internal singularities or exte rnal obstacles over their entire workspace (Parket et al.,1989). Also, the inverse kinematics problem is underdetermined and admits an infinite number of distinct feasible solutions, meaning that a given end-effector pos es can be realized by an infinite number of distinct manipulator configurations (McAvoy, et al, 2000). In order to overcome the shortcomings inherent in non-redundant robots, redundant robots have been utilized in industrial applications to increase fl exibility and dexterity around a restricted task space in pres ence of obstacle.