Search

We provide upper bounds for the Vapnik-Chervonenkis dimension of classes of subsets of that can be recognized by computer programs built from arithmetical assignments, infinitelydifferentiable algebraic operations (like k-root extraction and, more generally, operations defined by algebraic series of fractional powers), conditional statements and while instructions. This includes certain classes of GP-trees considered in Genetic Programming for symbolic regression and bi-classification. As a consequence we show explicit quantitative properties that can help to design the fitness function of a GP learning machine. [ABSTRACT FROM AUTHOR]

Many regularity properties of strings, like those appearing in hardware specification and verification, can be expressed in terms of word equations. The solvability problem of word equations is NP-hard and the first algorithm to find a solution for a word equation, when this solution exists, was given by Makanin in 1977. The time complexity of Makanin's algorithm is triple exponential in the length of the equations. In this paper we present an evolutionary algorithm with a local search procedure that is efficient for solving word equation systems. The fitness function of our algorithm is based on Levensthein distance considered as metric for the set of 0-1 binary strings. Our experimental results evidence that this metric is better suited for solving word equations than other edit metrics like, for instance, Hamming distance. [ABSTRACT FROM AUTHOR]

In this paper we present an evolutionary strategy for the multidimensional 0-1 knapsack problem. Our algorithm incorporates a flipping local search process in order to locally improve the obtained individuals and also, a heuristic operator which computes problem-specific knowledge, based on the surrogate multipliers approach introduced in [12]. Experimental results show that our evolutionary algorithm is capable of obtaining high quality solutions for large size problems and that the local search procedure significatively improves the final obtained result. Keywords: Evolutionary computation, genetic algorithms, knapsack problem, linear 0-1 integer programming. [ABSTRACT FROM AUTHOR]

Semi-algebraic objects are subsets or functions that can be described by finite boolean combinations of polynomials with real coefficients. In this paper we provide sharp estimates for the the precision and the number of trials needed in the MonteCarlo integration method to achieve a given error with a fixed confidence when approximating the mean value of semi-algebraic functions. Our study extends to the functional case the results of P. Koiran ([7]) for approximating the volume of semi-algebraic sets. Keywords: MonteCarlo algorithms, discrepancy bounds, learning theory, Chebyshev inequalities, semi-algebraic geometry. [ABSTRACT FROM AUTHOR]

In this paper we present an evolutionary algorithm for the multidimensional 0-1 knapsack problem. Our algorithm incorporates a heuristic operator which computes problem-specific knowledge. The design of this operator is based on the general technique used to design greedy-like heuristics for this problem, that is, the surrogate multipliers approach of Pirkul (see [7]). The main difference with work previously done is that our heuristic operator is computed following a genetic strategy -suggested by the greedy solution of the one dimensional knapsack problem- instead of the commonly used simplex method. Experimental results show that our evolutionary algorithm is capable of obtaining high quality solutions for large size problems requiring less amount of computational effort than other evolutionary strategies supported by heuristics founded on linear programming calculation of surrogate multipliers. Keywords: Evolutionary computation, genetic algorithms, knapsack problem, 0-1 integer programming, combinatorial optimization. [ABSTRACT FROM AUTHOR]