Composite panel structure optimization is commonly decomposed into panel optimization subproblems, with specified local loads, resulting in manufacturing incompatibilities between adjacent panel designs. Using genetic algorithms to optimize local panel stacking sequences allows panel populations of stacking sequences to evolve in parallel and send migrants to adjacent panels, so as to blend the local panel designs globally. The blending process is accomplished using the edit distance between individuals of a population and the set of migrants from adjacent panels. The objective function evaluating the fitness of designs is modified according to the severity of mismatches detected between neighboring populations. This lays the ground work for natural evolution to a blended global solution without leaving the paradigm of genetic algorithms. An additional method applied here for constructing globally blended panel designs uses a parallel decomposition antithetical to that of earlier work. Rather than performing concurrent panel genetic optimizations, a single genetic optimization is conducted for the entire structure with the parallelism solely within the fitness evaluations. A guide based genetic algorithm approach is introduced to exclusively generate and evaluate valid globally blended designs, utilizing a simple master-slave parallel implementation, implicitly reducing the size of the problem design space and increasing the quality of discovered local optima. / Ph. D.

Combinatorial methods are utilized to examine preimage iterations of topologically glued polynomials. In particular, this paper addresses using finite subdivision rules and Hubbard trees as tools to model the dynamic behavior of mated quadratic functions. Several methods of construction of invariant structures on modified degenerate matings are detailed, and examples of parameter-based families of matings for which these methods succeed (and fail) are given. / Ph. D.

Optimization problems of location-assignment correspond to a wide range of real situations, such as factory network design. However most of the previous works seek in most cases at minimizing a cost function. Traffic incidents routinely impact the performance and the safety of the supply. These incidents can not be totally avoided and must be regarded. A way to consider these incidents is to design a network on which multiple assignments are performed. Precisely, the problem we focus on deals with power supplying that has become a more and more complex and crucial question. Many international companies have customers who are located all around the world; usually one customer per country. At the other side of the scale, power extraction or production is done in several sites that are spread on several continents and seas. A strong willing of becoming less energetically-dependent has lead many governments to increase the diversity of supply locations. For each kind of energy, many countries expect to deal ideally with 2 or 3 location sites. As a decrease in power supply can have serious consequences for the economic performance of a whole country, companies prefer to balance equally the production rate among all sites as the reliability of all the sites is considered to be very similar. Sharing equally the demand between the 2 or 3 sites assigned to a given area is the most common way. Despite the cost of the network has an importance, it is also crucial to balance the loading between the sites to guarantee that no site would take more importance than the others for a given area. In case an accident happens in a site or in case technical problems do not permit to satisfy the demand assigned to the site, the overall power supply of this site is still likely to be ensured by the one or two available remaining site(s). It is common to assign a cost per open power plant and another cost that depends on the distance between the factory or power extraction point and the customer. On the whole, such companies who are concerned in the quality service of power supply have to find a good trade-off between this factor and their overall functioning cost. This situation exists also for companies who supplies power at the national scale. The expected number of areas as well that of potential sites, can reach 100. However the targeted size of problem to be solved is 50. This thesis focuses on devising an efficient methodology to provide all the solutions of this bi-objective problem. This proposal is an investigation of close problems to delimit the most relevant approaches to this untypical problem. All this work permits us to present one exact method and an evolutionary algorithm that might provide a good answer to this problem. / Master of Science

In metabolic engineering of prokaryotes, combinatorial approaches have developed recently that induce random genetic perturbations to achieve a desired cell phenotype. A screening strategy follows the randomized genetic manipulations to select strain(s) with the more optimal phenotype of interest. This screening strategy is often divided into two categories: (i) a growth competition assay and (ii) selection by high-throughput screening. The growth competition assay involves culturing strains together. The strain with the highest growth rate will ultimately dominate the culture. This strategy is ideal for selecting strain with cellular fitness (e.g., solvent tolerance), but it does not work for selecting a strain that can over-produce a product (e.g., an amino acid). For the case of selecting highly productive phenotypes, high-throughput screening is used. This method analyzes strains individually and is costly and time-consuming. In this research, a synthetic genetic circuit was developed to select highly productive phenotypes using a growth competition assay rather than high-throughput screening. This novel system is called Feed-back Inhibition of Transcription for Growth Selection (FITSelect), and it uses a natural feedback inhibition mechanism in the L-arginine production pathway to select strains (transformed with a random genomic library) that can over-produce L-arginine in E. coli DH10B. With FITSelect, the cell can thrive in the growth competition assay when L-arginine is over-produced (i.e., growth is tied to L-arginine production). Cell death or reduced growth results if L-arginine is not over-produced by the cell. This system was created by including an L-arginine concentration responsive argF promoter to control a ccdB cell death gene in the FITSelect system. The effects of ccdB were modulated by the antidote ccdA gene under control of an L-tryptophan responsive trp promoter. Several insights and construction strategies were required to build a system that ties the growth rate of the cell to L-arginine concentrations. / Master of Science

Combinatorial control of transcription is a well established phenomenon in the cell. Multiple transcription factors often bind to the same transcriptional control region of a gene and interact with each other to control the expression of the gene. It is thus necessary to consider the joint conservation of sequence pairs in order to identify combinations of binding sites to which the transcription factors bind. Conventional motif finding algorithms fail to address this issue. We propose a novel biclustering algorithm based on random sampling to identify candidate binding site combinations. We establish bounds on the various parameters to the algorithm and study the conditions under which the algorithm is guaranteed to identify candidate binding sites. We analyzed a yeast cell cycle gene expression data set using our algorithm and recovered certain novel combinations of binding sites, besides those already reported in the literature. / Master of Science

Composite panel structure optimization is commonly decomposed into panel optimization subproblems, with specified local loads, resulting in manufacturing incompatibilities between adjacent panel designs. Using genetic algorithms to optimize local panel stacking sequences allows panel populations of stacking sequences to evolve in parallel and send migrants to adjacent panels, so as to blend the local panel designs globally. The blending process is accomplished using the edit distance between individuals of a population and the set of migrants from adjacent panels. The objective function evaluating the fitness of designs is modified according to the severity of mismatches detected between neighboring populations. This lays the ground work for natural evolution to a blended global solution without leaving the paradigm of genetic algorithms. An additional method proposed here for constructing globally blended panel designs uses a parallel decomposition antithetical to that of earlier work. Rather than performing concurrent panel genetic optimizations, a single genetic optimization is conducted for the entire structure with the parallelism solely within the fitness evaluations. A guide based genetic algorithm approach is introduced to exclusively generate and evaluate valid globally blended designs, utilizing a simple master-slave parallel implementation, implicitly reducing the size of the problem design space and increasing the quality of discovered local optima. / Master of Science

Submitted by admin tede (tede@pucgoias.edu.br) on 2017-06-29T13:39:22Z No. of bitstreams: 1 Emerson de Souza Campos.pdf: 5716166 bytes, checksum: 5ece2fef286c7d6b282f34feaaf709e4 (MD5) / Made available in DSpace on 2017-06-29T13:39:22Z (GMT). No. of bitstreams: 1 Emerson de Souza Campos.pdf: 5716166 bytes, checksum: 5ece2fef286c7d6b282f34feaaf709e4 (MD5) Previous issue date: 2017-03-29 / Telecommunication systems are in constant development and the increasing demand of users and new services have enabled the emergence of new technologies. Planning has become indispensable due to the competitiveness and the large amount of financial resources involved. This work aims to propose and evaluate a genetic optimization algorithm for the planning of telecommunications networks. Because it is a combinatorial problem, the objective is to evaluate the advantages and disadvantages of the model based on the genetic algorithm. The graphs representing the networks were encoded in incidence matrices and the genetic operators of crossing and mutation were designed to act on matrices. MATLAB® software was used as a computational tool to implement the algorithms. The proposed model minimizes cost, considering the constraints of demand and technical capacity. The results found are compared to the published results in the SNDlib network instance library. The evaluation of the first version of the algorithm was based on a small PDH (Plesiochronous Digital Hierarchy) instance. The gain obtained in the cost of this network, compared to the solution presented in the library using linear programming with an arc-path approach, is 15.15%. In the second step, the algorithm for the optimization of a larger SDH (Synchronous Digital Hierarchy) network was applied. In this case, the need to hybridize the initial algorithm with a postoptimization algorithm was identified. The results obtained for the larger network were close to that of the SNDlib network library, although they were not better. The results found are promising because they approach similar solutions at a substantially shorter execution time than the SNDlib reference time. New research must be done so that the proposed algorithm can give good answers to large networks due to this being the reality of this area of research. / Os sistemas de telecomunicações estão em constante desenvolvimento e a demanda crescente de usuários e novos serviços possibilitaram o surgimento de novas tecnologias. O planejamento tornou-se indispensável devido à competividade e a grande quantidade de recursos financeiros envolvidos. Este trabalho visa propor e avaliar um algoritmo genético de otimização para o planejamento de redes de telecomunicações. Por se tratar de um problema combinatorial o objetivo é avaliar as vantagens e desvantagens do modelo com base no algoritmo genético. Os grafos que representam as redes foram codificados em matrizes de incidência e os operadores genéticos de cruzamento e mutação foram projetados para atuarem sobre matrizes. O software MATLAB® foi utilizado como ferramenta computacional para implementação dos algoritmos. O modelo proposto minimiza o custo, considerando as restrições de demanda e capacidade técnica. Os resultados encontrados são comparados com os resultados publicados na biblioteca de instâncias de rede SNDlib. A avaliação da primeira versão do algoritmo foi feita com base em uma instância PDH (Plesiochronous Digital Hierarchy), de pequeno porte. O ganho obtido no custo da rede, em relação à solução apresentada na biblioteca usando programação linear com abordagem arco-caminho, é de 15,15%. Na segunda etapa aplicou-se o algoritmo para otimização de uma rede SDH (Synchronous Digital Hierarchy), de maior porte. Identificou-se a necessidade de hibridizar o algoritmo inicial com um algoritmo de pós-otimização. Os resultados encontrados são promissores porque se aproximam de soluções similares em um tempo de execução substancialmente menor que o tempo de referência da SNDlib. Novas pesquisas devem ser feitas para que o algoritmo proposto possa dar boas respostas para redes de grande porte em função de ser esta a realidade desta área de pesquisa.

This research explores the idea that for certain optimization problems there is a way to parallelize the algorithm such that the parallel efficiency can exceed one hundred percent. Specifically, a parallel compiler, PC, is used to apply shortcutting techniquest to a metaheuristic Ant Colony Optimization (ACO), to solve the well-known Traveling Salesman Problem (TSP) on a cluster running Message Passing Interface (MPI). The results of both serial and parallel execution are compared using test datasets from the TSPLIB.

A combinatorial game is a game in which all players have perfect information and there is no element of chance; some well-known examples include othello, checkers, and chess. When people play combinatorial games they develop strategies, which can be viewed as a function which takes as input a game position and returns a move to make from that position. A strategy is winning if it guarantees the player victory despite whatever legal moves any opponent may make in response. The classical complexity of deciding whether a winning strategy exists for a given position in some combinatorial game has been well-studied both in general and for many specific combinatorial games. The vast majority of these problems are, depending on the specific properties of the game or class of games being studied, complete for either PSPACE or EXP. In the parameterized complexity setting, Downey and Fellows initiated a study of "short" (or k-move) winning strategy problems. This can be seen as a generalization of "mate-in-k" chess problems, in which the goal is to find a strategy which checkmates your opponent within k moves regardless of how he responds. In their monograph on parameterized complexity, Downey and Fellows suggested that AW[*] was the "natural home" of short winning strategy problems, but there has been little work in this field since then. In this thesis, we study the parameterized complexity of finding short winning strategies in combinatorial games. We consider both the general and several specific cases. In the general case we show that many short games are as hard classically as their original variants, and that finding a short winning strategy is hard for AW[P] when the rules are implemented as succinct circuits. For specific short games, we show that endgame problems for checkers and othello are in FPT, that alternating hitting set, hex, and the non-endgame problem for othello are in AW[*], and that short chess is AW[*]-complete. We also consider pursuit-evasion parameterized by the number of cops. We show that two variants of pursuit-evasion are AW[*]-hard, and that the short versions of these problems are AW[*]-complete.

We will survey some of the major directions of research in arithmetic combinatorics and their connections to other fields. We will then discuss three new results. The first result will generalize a structural theorem from Balog and Szemerédi. The second result will establish a new tool in incidence geometry, which should prove useful in attacking combinatorial estimates. The third result evolved from the famous sum-product problem, by providing a partial categorization of bivariate polynomial set functions which induce exponential expansion on all finite sets of real numbers.