Search

Search algorithms are often compared by the optimization speed achieved on some sets of cost functions. Here some properties of algorithms' optimization speed are introduced and discussed. In particular, we show that determining whether a set of cost functions F admits a search algorithm having given optimization speed is an NP-complete problem. Further, we derive an explicit formula to calculate the best achievable optimization speed when F is closed under permutation. Finally, we show that the optimization speed achieved by some well-know optimization techniques can be much worse than the best theoretical value, at least on some sets of optimization benchmarks. © 2012 Springer Science+Business Media, LLC.

El Proyecto tiene como objetivo generar oportunidades de comercialización justa y estable para los productores de Estaquinha, así como proveer servicios agropecuarios y de transformación de alimentos a la comunidad rural de la zona. Se espera contribuir al desarrollo económico y social de la región, impactando negativamente en la migración campo-ciudad. También se busca contribuir a la sustentabilidad financiera de la Asociación mozambicana ESMABAMA a través de una reinversión de parte de los beneficios en el sector agropecuario de la organización. La base del Proyecto es establecer una relación comercial entre los productores agrícolas de la zona y una empresa social gestionada por ESMABAMA dedicada a la comercialización de granos básicos, de tal forma que las partes incrementen sus ingresos a los largo del año. Es decir, se espera que el Proyecto contribuya a asegurar un ingreso a los campesinos y a estabilizar los precios de los granos básicos de la zona al gestionar un almacén que se dedique a la comercialización de alimentos no perecederos fuera de temporada. La relación comercial se ratificará a través de la firma por ambas partes de unos contratos comerciales en los cuales se indicará la producción que será comprada por la empresa y el precio que pagará por esa. Objetivo de esta empresa es también la de ofrecer servicios a la comunidad del puesto administrativo de Estaquinha poniendo en funcionamiento un molino y una descascadora de grano que dará servicio a las familias de la zona. En el ámbito más estrictamente agrícola, la empresa donará servicios a aquellos agricultores con los cuales trabajará a través de la estipulación de un contrato. Este prevé la donación de algunos insumos y la asistencia técnica. Más en general, para los agricultores del distrito la empresa pondrá en marcha una tienda que venda productos agropecuarios en la localidad de Estaquinha y alquilará los servicios de un tractor.

Postprint (published version)

The Sharpened No Free Lunch theorem states that all optimization algorithms have the same performance on sets of functions that are closed under permutation, independently of the considered performance measure. However, not all performance measures are informative on how fast or how accurately an algorithm can solve a given problem. In this paper we focus on a particular performance measure, called optimization speed, that quanti fies how fast a search algorithm is able to find an optimal solution, and we try to characterize the set of functions on which all possible search algorithms have the same optimization speed. We call fair these sets, and we prove some results about their structure, the number of such sets and the computational complexity of checking fairness.

We present a framework based on genetic algorithms to automatically generate cellular automata rules under four different asynchronous update models (fixed random sweep, random new sweep, clock and independent random ordering). We consider four different rules with well known dynamics under synchronous update scheme. We try to reconstruct the same dynamics by means of a genetic algorithm using asynchronous update schemes. We show that in many cases it is impossible, by means of an asynchronous update scheme, to perfectly reconstruct these dynamics. Nevertheless, we show that the genetic algorithm finds the rules that more closely approximate the target behavior and the dynamics of the rules found by the genetic algorithm are rather similar to the target ones. In particular, we can always recognize a similar pattern and we can also identify some differences in small details. This paves the way to a deeper investigation on this track: does using asynchronous updates allow us to find more stable rules, i.e. rules that are less affected by noise, and thus do not overfit training data? This question remains open and answering it is one of the main goals of our current research.

We show that a deterministic single-tape Turing machine, operating in polynomial space with respect to the input length, can be efficiently simulated (both in terms of time and space) by a semi-uniform family of P systems with active membranes and three polarizations, using only communication rules. Then, basing upon this simulation, we prove that a result similar to the space hierarchy theorem can be obtained for P systems with active membranes: the larger the amount of space we can use during the computations, the harder the problems we are able to solve. © 2010 Springer-Verlag.

Fitness-Proportional Negative Slope Coefficient is a fitness landscapes measure that has recently been introduced as a potential indicator of problem hardness for optimisation. It is inspired to an older measure, the Negative Slope Coefficient, and it has been theoretically modelled. Preliminary experiments have suggested that it may be a good predictor of problem hardness. However, this measure has not undergone any convincing and comprehensive empirical testing. Our objective is to fill this gap. So, we perform empirical tests using a large set of invertible functions of unitation. We find that while this measure may correctly predict the degree of evolvability of a landscape, this does not necessarily correlate with the difficulty of problems. Some landscapes may show, for example, limited evolvability and yet be easy to solve because either solutions are already present in the initial population or the computational resources provided exceed evolvability obstacles. Or it may be impossible to solve them irrespective of their evolvability simply because they are far too vast for the computational resources provided. These situations are hardly captured by the Fitness-Proportional Negative Slope Coefficient.

We introduce the concept of "minimal" search algorithm for a set of functions to optimize. We investigate the structure of closed under permutation (c.u.p.) sets and we calculate the performance of an algorithm applied to them. We prove that each set of functions based on the distance to a given optimal solution, among which trap functions, onemax or the recently introduced onemix functions, and the NK-landscapes are not c.u.p. and thus the thesis of the sharpened No Free Lunch Theorem does not hold for them. Thus, it makes sense to look for a specific algorithm for those sets. Finally, we propose a method to build a "good" (although not necessarily minimal) search algorithm for a specific given set of problems. The algorithms produced with this technique show better average performance than a genetic algorithm executed on the same set of problems, which was expected given that those algorithms are problem-specific. Nevertheless, in general they cannot be applied for real-life problems, given their high computational complexity that we have been able to estimate. © 2008 Springer-Verlag Berlin Heidelberg.