Uma abordagem por nuvem de partículas para problemas de otimização combinatória

Combinatorial optimization problems have the goal of maximize or minimize functions defined over a finite domain. Metaheuristics are methods designed to find good solutions in this finite domain, sometimes the optimum solution, using a subordinated heuristic, which is modeled for each particular problem. This work presents algorithms based on particle swarm optimization (metaheuristic) applied to combinatorial optimization problems: the Traveling Salesman Problem and the Multicriteria Degree Constrained Minimum Spanning Tree Problem. The first problem optimizes only one objective, while the other problem deals with many objectives. In order to evaluate the performance of the algorithms proposed, they are compared, in terms of the quality of the solutions found, to other approaches

Evolutionary computation of forests with Degree- and Role-Constrained Minimum Spanning Trees

Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode these forests. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight different evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm, generational genetic algorithm, steady-state genetic algorithm, covariance matrix adaptation evolution strategy, differential evolution, elitist evolution strategy, non-elitist evolution strategy and particle swarm optimization. The best results are for the estimation of distribution algorithms and both types of genetic algorithms, although the genetic algorithms are significantly faster.

Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design

The design of a network is a solution to several engineering and science problems. Several network design problems are known to be NP-hard, and population-based metaheuristics like evolutionary algorithms (EAs) have been largely investigated for such problems. Such optimization methods simultaneously generate a large number of potential solutions to investigate the search space in breadth and, consequently, to avoid local optima. Obtaining a potential solution usually involves the construction and maintenance of several spanning trees, or more generally, spanning forests. To efficiently explore the search space, special data structures have been developed to provide operations that manipulate a set of spanning trees (population). For a tree with n nodes, the most efficient data structures available in the literature require time O(n) to generate a new spanning tree that modifies an existing one and to store the new solution. We propose a new data structure, called node-depth-degree representation (NDDR), and we demonstrate that using this encoding, generating a new spanning forest requires average time O(root n). Experiments with an EA based on NDDR applied to large-scale instances of the degree-constrained minimum spanning tree problem have shown that the implementation adds small constants and lower order terms to the theoretical bound.

Computación evolutiva de bosques de expansión mínimos con restricción de grado y de rol

Encontrar el árbol de expansión mínimo con restricción de grado de un grafo (DCMST por sus siglas en inglés) es un problema NP-complejo ampliamente estudiado. Una de sus aplicaciones más importantes es el dise~no de redes. Aquí nosotros tratamos una nueva variante del problema DCMST, que consiste en encontrar el árbol de expansión mínimo no solo con restricciones de grado, sino también con restricciones de rol (DRCMST), es decir, a~nadimos restricciones para restringir el rol que los nodos tienen en el árbol. Estos roles pueden ser nodo raíz, nodo intermedio o nodo hoja. Por otra parte, no limitamos el número de nodos raíz a uno, por lo que, en general, construiremos bosques de DRCMSTs. El modelado en los problemas de dise~no de redes puede beneficiarse de la posibilidad de generar más de un árbol y determinar el rol de los nodos en la red. Proponemos una nueva representación basada en permutaciones para codificar los bosques de DRCMSTs. En esta nueva representación, una permutación codifica simultáneamente todos los árboles que se construirán. Nosotros simulamos una amplia variedad de problemas DRCMST que optimizamos utilizando ocho algoritmos de computación evolutiva diferentes que codifican los individuos de la población utilizando la representación propuesta. Los algoritmos que utilizamos son: algoritmo de estimación de distribuciones (EDA), algoritmo genético generacional (gGA), algoritmo genético de estado estacionario (ssGA), estrategia evolutiva basada en la matriz de covarianzas (CMAES), evolución diferencial (DE), estrategia evolutiva elitista (ElitistES), estrategia evolutiva no elitista (NonElitistES) y optimización por enjambre de partículas (PSO). Los mejores resultados fueron para el algoritmo de estimación de distribuciones utilizado y ambos tipos de algoritmos genéticos, aunque los algoritmos genéticos fueron significativamente más rápidos.---ABSTRACT---Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode the forest of DRCMSTs. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problems which we optimize using eight diferent evolutionary computation algorithms encoding individuals of the population using the proposed representation. The algorithms we use are: estimation of distribution algorithm (EDA), generational genetic algorithm (gGA), steady-state genetic algorithm (ssGA), covariance matrix adaptation evolution strategy (CMAES), diferential evolution (DE), elitist evolution strategy (ElististES), non-elitist evolution strategy (NonElististES) and particle swarm optimization (PSO). The best results are for the estimation of distribution algorithm and both types of genetic algorithms, although the genetic algorithms are significantly faster. iv

The evolutionary value of recombination is constrained by genome modularity

Genetic recombination is a fundamental evolutionary mechanism promoting biological adaptation. Using engineered recombinants of the small single-stranded DNA plant virus, Maize streak virus (MSV), we experimentally demonstrate that fragments of genetic material only function optimally if they reside within genomes similar to those in which they evolved. The degree of similarity necessary for optimal functionality is correlated with the complexity of intragenomic interaction networks within which genome fragments must function. There is a striking correlation between our experimental results and the types of MSV recombinants that are detectable in nature, indicating that obligatory maintenance of intragenome interaction networks strongly constrains the evolutionary value of recombination for this virus and probably for genomes in general.

Bricolage as a path to innovativeness for resource constrained new firms

Evidence suggests that both nascent and young firms (henceforth: “new firms”)—despite typically being small and resource-constrained—are sometimes able to innovate effectively. Such firms are seldom able to invest in lengthy and expensive development processes, which suggests that they may frequently rely instead on other pathways to generate innovativeness within the firm. In this paper, we develop and test arguments that “bricolage,” defined as making do by applying combinations of the resources at hand to new problems and opportunities, provides an important pathway to achieve innovation for new resource-constrained firms. Through bricolage, resource-constrained firms engage in the processes of “recombination” that are core to creating innovative outcomes. Based on a large longitudinal dataset, our results suggest that variations in the degree to which firms engage in bricolage behaviors can provide a broadly applicable explanation of innovativeness under resource constraints by new firms. We find no general support for our competing hypothesis that the positive effects may level off or even turn negative at high levels of bricolage..

Flow of metal in constrained plane-strain extrusion forging- Part II

With many innovations in process technology, forging is establishing itself as a precision manufacturing process: as forging is used to produce complex shapes in difficult materials, it requires dies of complex configuration of high strength and of wear-resistant materials. Extensive research and development work is being undertaken, internationally, to analyse the stresses in forging dies and the flow of material in forged components. Identification of the location, size and shape of dead-metal zones is required for component design. Further, knowledge of the strain distribution in the flowing metal indicates the degree to which the component is being work hardened. Such information is helpful in the selection of process parameters such as dimensional allowances and interface lubrication, as well as in the determination of post-forging operations such as heat treatment and machining. In the presently reported work the effect of aperture width and initial specimen height on the strain distribution in the plane-strain extrusion forging of machined lead billets is observed: the distortion of grids inscribed on the face of the specimen gives the strain distribution. The stress-equilibrium approach is used to optimise a model of flow in extrusion forging, which model is found to be effective in estimating the size of the dead-metal zone. The work carried out so far indicates that the methodology of using the stress-equilibrium approach to develop models of flow in closed-die forging can be a useful tool in component, process and die design.

A finite element analysis of quasistatic crack growth in a pressure sensitive constrained ductile layer

Polymeric adhesive layers are employed for bonding two components in a wide variety of technological applications, It has been observed that, unlike in metals, the yield behavior of polymers is affected by the state of hydrostatic stress. In this work, the effect of pressure sensitivity of yielding and layer thickness on quasistatic interfacial crack growth in a ductile adhesive layer is investigated. To this end, finite deformation, finite element analyses of a cracked sandwiched layer are carried out under plane strain, small-scale yielding conditions for a wide range of mode mixities. The Drucker-Prager constitutive equations are employed to represent the behavior of the layer. Crack propagation is simulated through a cohesive zone model, in which the interface is assumed to follow a prescribed traction-separation law. The results show that for a given mode mixity, the steady state Fracture toughness [K](ss) is enhanced as the degree of pressure sensitivity increases. Further, for a given level of pressure sensitivity, [K](ss) increases steeply as mode Il loading is approached. (C) 2000 Elsevier Science Ltd. All rights reserved.

instability of standing wave, global existence and blowup for the klein-gordon-zakharov system with different-degree nonlinearities

This paper discusses the Klein–Gordon–Zakharov system with different-degree nonlinearities in two and three space dimensions. Firstly, we prove the existence of standing wave with ground state by applying an intricate variational argument. Next, by introducing an auxiliary functional and an equivalent minimization problem, we obtain two invariant manifolds under the solution flow generated by the Cauchy problem to the aforementioned Klein–Gordon–Zakharov system. Furthermore, by constructing a type of constrained variational problem, utilizing the above two invariant manifolds as well as applying potential well argument and concavity method, we derive a sharp threshold for global existence and blowup. Then, combining the above results, we obtain two conclusions of how small the initial data are for the solution to exist globally by using dilation transformation. Finally, we prove a modified instability of standing wave to the system under study.

A Significance-Driven Programming Framework for Energy-Constrained Approximate Computing

Approximate execution is a viable technique for energy-con\-strained environments, provided that applications have the mechanisms to produce outputs of the highest possible quality within the given energy budget.
We introduce a framework for energy-constrained execution with controlled and graceful quality loss. A simple programming model allows users to express the relative importance of computations for the quality of the end result, as well as minimum quality requirements. The significance-aware runtime system uses an application-specific analytical energy model to identify the degree of concurrency and approximation that maximizes quality while meeting user-specified energy constraints. Evaluation on a dual-socket 8-core server shows that the proposed
framework predicts the optimal configuration with high accuracy, enabling energy-constrained executions that result in significantly higher quality compared to loop perforation, a compiler approximation technique.

Exploiting Significance of Computations for Energy-Constrained Approximate Computing

Approximate execution is a viable technique for environments with energy constraints, provided that applications are given the mechanisms to produce outputs of the highest possible quality within the available energy budget. This paper introduces a framework for energy-constrained execution with controlled and graceful quality loss. A simple programming model allows developers to structure the computation in different tasks, and to express the relative importance of these tasks for the quality of the end result. For non-significant tasks, the developer can also supply less costly, approximate versions. The target energy consumption for a given execution is specified when the application is launched. A significance-aware runtime system employs an application-specific analytical energy model to decide how many cores to use for the execution, the operating frequency for these cores, as well as the degree of task approximation, so as to maximize the quality of the output while meeting the user-specified energy constraints. Evaluation on a dual-socket 16-core Intel platform using 9 benchmark kernels shows that the proposed framework picks the optimal configuration with high accuracy. Also, a comparison with loop perforation (a well-known compile-time approximation technique), shows that the proposed framework results in significantly higher quality for the same energy budget.

A spatial approach to network generation for three properties:Degree distribution, clustering coefficient and degree assortativity

Social networks generally display a positively skewed degree distribution and higher values for clustering coefficient and degree assortativity than would be expected from the degree sequence. For some types of simulation studies, these properties need to be varied in the artificial networks over which simulations are to be conducted. Various algorithms to generate networks have been described in the literature but their ability to control all three of these network properties is limited. We introduce a spatially constructed algorithm that generates networks with constrained but arbitrary degree distribution, clustering coefficient and assortativity. Both a general approach and specific implementation are presented. The specific implementation is validated and used to generate networks with a constrained but broad range of property values. © Copyright JASSS.

A simple method for choosing the parameters of a two degree-of-freedom tuned vibration absorber

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Constrained intervals and interval spaces

Constrained intervals, intervals as a mapping from [0, 1] to polynomials of degree one (linear functions) with non-negative slopes, and arithmetic on constrained intervals generate a space that turns out to be a cancellative abelian monoid albeit with a richer set of properties than the usual (standard) space of interval arithmetic. This means that not only do we have the classical embedding as developed by H. Radström, S. Markov, and the extension of E. Kaucher but the properties of these polynomials. We study the geometry of the embedding of intervals into a quasilinear space and some of the properties of the mapping of constrained intervals into a space of polynomials. It is assumed that the reader is familiar with the basic notions of interval arithmetic and interval analysis. © 2013 Springer-Verlag Berlin Heidelberg.

Displacement Analysis of Under-Constrained Cable-Driven Parallel Robots

This dissertation studies the geometric static problem of under-constrained cable-driven parallel robots (CDPRs) supported by n cables, with n ≤ 6. The task consists of determining the overall robot configuration when a set of n variables is assigned. When variables relating to the platform posture are assigned, an inverse geometric static problem (IGP) must be solved; whereas, when cable lengths are given, a direct geometric static problem (DGP) must be considered. Both problems are challenging, as the robot continues to preserve some degrees of freedom even after n variables are assigned, with the final configuration determined by the applied forces. Hence, kinematics and statics are coupled and must be resolved simultaneously. In this dissertation, a general methodology is presented for modelling the aforementioned scenario with a set of algebraic equations. An elimination procedure is provided, aimed at solving the governing equations analytically and obtaining a least-degree univariate polynomial in the corresponding ideal for any value of n. Although an analytical procedure based on elimination is important from a mathematical point of view, providing an upper bound on the number of solutions in the complex field, it is not practical to compute these solutions as it would be very time-consuming. Thus, for the efficient computation of the solution set, a numerical procedure based on homotopy continuation is implemented. A continuation algorithm is also applied to find a set of robot parameters with the maximum number of real assembly modes for a given DGP. Finally, the end-effector pose depends on the applied load and may change due to external disturbances. An investigation into equilibrium stability is therefore performed.