Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-01-30Bitstream added on 2014-06-13T20:55:42Z : No. of bitstreams: 1 lopes_am_me_sjrp.pdf: 648692 bytes, checksum: 6aa3a670ac391b9033fe7de1566f1648 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho trata do problema de corte de estoque unidimensional inteiro, que consiste em cortar um conjunto de objetos disponíveis em estoque para a produção de itens menores demandados, de tal forma que se otimize uma ou mais funções objetivos. Foi estudado o caso em que existe apenas um tipo de objeto em estoque em quantidades suficiente para atender a demanda. Três adaptações de um método heurístico baseadas nos conceitos dos algoritmos evolutivos multiobjetivo são propostas para resolver o problema considerando duas funções objetivo conflitantes, a minimização do número de objetos cortados e a minimização do número de diferentes padrões de corte. As adaptações utilizam as idéias presentes no método da Soma Ponderada, no Vector Evaluated Genetic Algorithm e no Multiple Objective Genetic Algorithm. Estas heurísticas são analisadas resolvendo-se instâncias geradas aleatoriamente. / This work deals with the one-dimensional integer cutting stock problem, which consist of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to optimize one or more objective functions. On the case studied there is just one type of object in stock available in sufficient quantity to satisfy the demand. Three adaptations of a heuristic method based on the multi-objective evolutionary algorithms concepts are proposed to solve the problem considering two conflicting objective functions, the minimization of the number of objects to be cut and the minimization of the number of different cutting patterns. The adaptations consider the ideas from the Weighted Sum method, the Vector Evaluated Genetic Algorithm and the Multiple Objective Genetic Algorithm. These heuristics are analyzed by solving randomly generated instances.

This research proposes, implements and analyses a novel framework for multiobjective optimisation through evolutionary computing aimed at, but not restricted to, real-world problems in the engineering design domain. Evolutionary algorithms have been used to tackle a variety of non-linear multiobjective optimisation problems successfully, but their success is governed by key parameters which have been shown to be sensitive to the nature of the particular problem, incorporating concerns such as the number of objectives and variables, and the size and topology of the search space, making it hard to determine the best settings in advance. This work describes a real-encoded multi-objective optimising evolutionary algorithm framework, incorporating a genetic algorithm, that uses self-adaptive mutation and crossover in an attempt to avoid such problems, and which has been benchmarked against both standard optimisation test problems in the literature and a real-world airfoil optimisation case. For this last case, the minimisation of drag and maximisation of lift coefficients of a well documented standard airfoil, the framework is integrated with a freeform deformation tool to manage the changes to the section geometry, and XFoil, a tool which evaluates the airfoil in terms of its aerodynamic efficiency. The performance of the framework on this problem is compared with those of two other heuristic MOO algorithms known to perform well, the Multi-Objective Tabu Search (MOTS) and NSGA-II, showing that this framework achieves better or at least no worse convergence. The framework of this research is then considered as a candidate for smart (electricity) grid optimisation. Power networks can be improved in both technical and economical terms by the inclusion of distributed generation which may include renewable energy sources. The essential problem in national power networks is that of power flow and in particular, optimal power flow calculations of alternating (or possibly, direct) current. The aims of this work are to propose and investigate a method to assist in the determination of the composition of optimal or high-performing power networks in terms of the type, number and location of the distributed generators, and to analyse the multi-dimensional results of the evolutionary computation component in order to reveal relationships between the network design vector elements and to identify possible further methods of improving models in future work. The results indicate that the method used is a feasible one for the achievement of these goals, and also for determining optimal flow capacities of transmission lines connecting the bus bars in the network.

Le test est une approche efficace pour détecter des bogues d'implémentation ayant un impact sur la sécurité, c.a.d. des vulnérabilités. Lorsque le code source n'est pas disponible, il est nécessaire d'utiliser des techniques de test en boîte noire. Nous nous intéressons au problème de détection automatique d'une classe de vulnérabilités (Cross Site Scripting alias XSS) dans les applications web dans un contexte de test en boîte noire. Nous proposons une approche pour inférer des modèles de telles applications et frelatons des séquences d'entrées générées à partir de ces modèles et d'une grammaire d'attaque. Nous inférons des automates de contrôle et de teinte, dont nous extrayons des sous-modèles afin de réduire l'espace de recherche de l'étape de frelatage. Nous utilisons des algorithmes génétiques pour guider la production d'entrées malicieuses envoyées à l'application. Nous produisons un verdict de test grâce à une double inférence de teinte sur l'arbre d'analyse grammaticale d'un navigateur et à l'utilisation de motifs de vulnérabilités comportant des annotations de teinte. Nos implémentations LigRE et KameleonFuzz obtiennent de meilleurs résultats que les scanneurs boîte noire open-source. Nous avons découvert des XSS ``0-day'' (c.a.d. des vulnérabilités jusque lors inconnues publiquement) dans des applications web utilisées par des millions d'utilisateurs. / Testing is a viable approach for detecting implementation bugs which have a security impact, a.k.a. vulnerabilities. When the source code is not available, it is necessary to use black-box testing techniques. We address the problem of automatically detecting a certain class of vulnerabilities (Cross Site Scripting a.k.a. XSS) in web applications in a black-box test context. We propose an approach for inferring models of web applications and fuzzing from such models and an attack grammar. We infer control plus taint flow automata, from which we produce slices, which narrow the fuzzing search space. Genetic algorithms are then used to schedule the malicious inputs which are sent to the application. We incorporate a test verdict by performing a double taint inference on the browser parse tree and combining this with taint aware vulnerability patterns. Our implementations LigRE and KameleonFuzz outperform current open-source black-box scanners. We discovered 0-day XSS (i.e., previously unknown vulnerabilities) in web applications used by millions of users.

Ma thèse s'inscrit dans le domaine de l'ingénierie de l'interaction homme-machine. Elle traite de la conception d'interfaces hommes machine (IHM). La créativité n'y est souvent considérée que de manière marginale. Pourtant l'effervescence technologique et la diversité résultante des contextes d'usage appellent à de plus en plus de créativité. Ma thèse soutient le principe que l'innovation passe par l'application de processus créatifs. Dès lors, le défi est de savoir explorer largement et efficacement l'espace de conception dès les phases amont du processus. Il convient donc d'intégrer et d'enseigner la créativité dans les processus de conception d'IHM, en particulier pour les concepteurs débutants.Ce positionnement sur le sujet provient d'une double approche : d'une part théorique, avec un état de l'art explorant les dimensions de la créativité et les outils informatiques de support à la créativité ; d'autre part empirique, avec quatre mises en pratique de la créativité dans des domaines de conception différents comme l'architecture, la conception de produit et la conception de systèmes interactifs. Je construis ma contribution sur les principes suivants : (1) la créativité n'est pas réservée à une élite, mais peut être travaillée et renforcée par des outils informatiques ; (2) ces outils doivent soutenir la motivation, la recherche d'inspiration, l'exploration en largeur, et les connaissances relatives au domaine et aux processus de conception. Selon une démarche réflexive, j'applique ces mêmes principes dans ma thèse. Je propose une exploration en largeur du support à la créativité via cinq contributions logicielles complémentaires : Maestro et Bank pour la capitalisation des connaissances ; WebGallery, BrianStorming et Magellan pour l'inspiration et l'exploration de l'espace de conception. Plus précisément, Maestro traite de la capitalisation des processus de conception tandis que BANK assure la structuration et la capitalisation des connaissances en IHM via un graphe de modèles. WebGallery est une galerie de sites web pour inspirer les concepteurs : je conduis une expérimentation sur la perception humaine du style d'un site web. BrianStorming est un assistant au brainstorming : il fournit des suggestions pendant une séance de brainstorming électronique. Magellan est un environnement interactif à base d'algorithmes génétiques qui génèrent et transforment automatiquement des IHM pour un problème de conception donné. Par ce positionnement et ces contributions logicielles, l'ordinateur change de statut : de simple outil, il devient un concepteur assistant, partenaire du processus de créativité. / My PhD thesis contributes to the engineering of Human Computer Interaction (HCI). It deals with the design of User Interfaces (UI). I claim that creative processes should be better considered, and supported by tools especially for novice designers. The challenge is to speed up the exploration of the design space at the early stages of the process. This claim is grounded in both a theoretical state of the art in creativity and creativity support tools, and in practice of the topic with four hands-on experiences of creativity in different areas of design such as architecture, product design and UI design. I build my contribution on the following principles: (1) creativity is not reserved for the elite, but can be tailored and fostered by software tools; (2) the tools must leverage motivation, inspiration, wide exploration, and knowledge in UI and design processes. Through a reflective process, I apply these principles to my thesis. I explore a wide range of creativity support tools through five complementary software contributions: Maestro and Bank for supporting knowledge capitalization; WebGallery, BrianStorming and Magellan for fostering inspiration and exploration of the design space. Maestro addresses the capitalization of design processes whilst BANK gathers knowledge in HCI as a graph of models. WebGallery is a gallery of websites to inspire designers: I report an experiment on human perception of websites styles. BrianStorming is a brainstorming assistant: it provides suggestions in a electronic brainstorming session. Magellan is an interactive environment based on genetic algorithms that automatically generate and transform UIs for a given design problem. This changes the role of the computer: from a simple tool, it becomes a designer's partner in the creative process.

Made available in DSpace on 2014-06-11T19:22:32Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-02-20Bitstream added on 2014-06-13T19:28:05Z : No. of bitstreams: 1 zini_eoc_me_ilha.pdf: 1142984 bytes, checksum: 4ff93a7fe459a5a56e15da26b7a6dd45 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho apresenta uma metodologia composta de duas fases para resolver problemas de otimização com restrições usando uma estratégia multiobjetivo. Na primeira fase, o esforço concentra-se em encontrar, pelo menos, uma solução factível, descartando completamente a função objetivo. Na segunda fase, aborda-se o problema como biobjetivo, onde se busca a otimização da função objetivo original e maximizar o cumprimento das restrições. Na fase um propõe-se uma estratégia baseada na diminuição progressiva da tolerância de aceitação das restrições complexas para encontrar soluções factíveis. O desempenho do algoritmo é validado através de 11 casos testes bastantes conhecidos na literatura especializada. / This work presents a two-phase framework for solving constrained optimization problems using a multi-objective strategy. In the first phase, the objective function is completely disregarded and entire search effort is directed toward finding a single feasible solution. In the second phase, the problem is treated as a bi-objective optimization problem, where the technique converts constrained optimization to a two-objective optimization: one is the original objective function; the other is the degree function violating the constraints. In the first phase a methodology based on progressive decrease of the tolerance of acceptance of complex constrains is proposed in order to find feasible solutions. The approach is tested on 11 well-know benchmark functions.

Este trabalho propõe o desenvolvimento de Algoritmos Evolutivos (AEs) para estimação dos parâmetros que modelam sinais elétricos (frequência, fase e amplitude) em tempo-real. A abordagem proposta deve ser robusta a ruídos e harmônicos em sinais distorcidos, por exemplo devido à presença de faltas na rede elétrica. AEs mostram vantagens para lidar com tais tipos de sinais. Por outro lado, esses algoritmos quando implementados em software não possibilitam respostas em tempo-real para uso da estimação como relé de frequência ou Unidade de Medição Fasorial. O desenvolvimento em FPGA apresentado nesse trabalho torna possível paralelizar o cálculo da estimação em hardware, viabilizando AEs para análise de sinal elétrico em tempo real. Além disso, mostra-se que AEs multiobjetivos podem extrair informações não evidentes das três fases do sistema e estimar os parâmetros adequadamente mesmo em casos em que as estimativas por fase divirjam entre si. Em outras palavras, as duas principais contribuições computacionais são: a paralelização do AE em hardware por meio de seu desenvolvimento em um circuito de FPGA otimizado a nível de operações lógicas básicas e a modelagem multiobjetiva do problema possibilitando análises dos sinais de cada fase, tanto independentemente quanto de forma agregada. Resultados experimentais mostram superioridade do método proposto em relação ao estimador baseado em transformada de Fourier para determinação de frequência e fase / This work proposes the development of Evolutionary Algorithms (EAs) for the estimation of the basic parameters from electrical signals (frequency, phase and amplitude) in real time. The proposed approach must be robust to noise and harmonics in signals distorted, for example, due to the presence of faults in the electrical network. EAs show advantages for dealing with these types of signals. On the other hand, these algorithms when implemented in software cant produce real-time responses in order to use their estimations as frequency relay or Phasor Measurement Unit. The approach developed on FPGA proposed in this work parallelizes in hardware the process of estimation, enabling analyses of electrical signals in real time. Furthermore, it is shown that multi-objective EAs can extract non-evident information from the three phases of the system and properly estimate parameters even when the phase estimates diverge from each other. This research proposes: the parallelization of an EA in hardware through its design on FPGA circuit optimized at level of basic logic operations and the modeling of the problem enabling multi-objective analyses of the signals from each phase in both independent and aggregate ways. Experimental results show the superiority of the proposed method compared to an estimator based on Fourier transform for determining frequency and phase

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T20:59:25Z (GMT). No. of bitstreams: 1 Azuma_ReginaMitsue_M.pdf: 2321816 bytes, checksum: 44c4417bf2a4fad2a8241c7189e4d04a (MD5) Previous issue date: 2011 / Resumo: A classe de problemas de estoque e roteamento está presente em várias áreas, incluindo indústria automobilística e gerência de numerário no reabastecimento de caixas eletrônicos. Supondo que o fornecedor é responsável pela estocagem e distribuição dos produtos, sujeito a um conjunto de restrições, o desafio que se apresenta é a determinação de uma política ótima, mais especificamente quais clientes atender, qual quantidade a ser fornecida a cada cliente e qual rota empregar visando a minimização dos custos. Este trabalho apresenta uma proposta de solução para uma das mais comuns formulações do problema: um produto é distribuído a partir de um fornecedor para vários clientes em um horizonte de tempo definido. O transporte é realizado por um veículo de capacidade limitada. Para produzir a otimização simultânea de ambos os objetivos, minimização dos custos de transporte e estoque, a proposta segue uma abordagem multiobjetivo e se baseia no uso do algoritmo SPEA2 (do inglês, Strength Pareto Evolutionary Algorithm 2), incluindo inovações na representação de soluções-candidatas, nos operadores genéticos e de busca local. A fronteira de Pareto estimada é então composta de múltiplas soluções não-dominadas, representando compromissos distintos entre custos de transporte e estoque. Como casos de estudo, são tomadas instâncias de médio porte extraídas da literatura e são geradas instâncias de grande porte. Para as instâncias de médio porte, as fronteiras de Pareto estimadas em cada caso são comparadas com as respectivas soluções ótimas da versão mono-objetivo de cada problema, pois já existe um algoritmo exato de solução para a formulação mono-objetivo de instâncias de médio porte / Abstract: The class of inventory routing problems (IRP) is present in several areas, including automotive industry and cash management for ATM networks. Given that the supplier is responsible for managing the product inventory and replenishment, subject to a set of restrictions, the challenge here is to determine an optimal policy, more specifically which retailers to serve, the quantity to deliver to each retailer and which routes to employ in order to minimize the cost. This work presents a proposal to solve one version of the IRP usually found in the scientific literature: a product is distributed from a supplier to several retailers in a defined time horizon. Shipment is performed by a vehicle with limited capacity. To perform the simultaneous optimization of both objectives, minimization of transportation and inventory costs, the proposal follows a multi-objective approach based on SPEA2 (Strength Pareto Evolutionary Algorithm 2), including innovative aspects mainly associated with the representation of candidate solutions, genetic operators and local search. The Pareto front is then composed of multiple non-dominated solutions with distinct trade-offs between transportation and inventory costs. As case studies, medium size instances extracted from the literature are considered and large size instances are generated. For the medium size instances, the estimated Pareto fronts are compared, in each case, with the corresponding optimal solutions associated with the single-objective version of each problem, given that there is already an exact algorithm to solve such medium size single-objective instances / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Philosophiae Doctor - PhD / This research study investigates optimization of IRS to individual information needs in order of relevance. The research addressed development of algorithms that optimize the ranking of documents retrieved from IRS. In this thesis, we present two aspects of context-awareness in IR. Firstly, the design of context of information. The context of a query determines retrieved information relevance. Thus, executing the same query in diverse contexts often leads to diverse result rankings. Secondly, the relevant context aspects should be incorporated in a way that supports the knowledge domain representing users’ interests. In this thesis, the use of evolutionary algorithms is incorporated to improve the effectiveness of IRS. A context-based information retrieval system is developed whose retrieval effectiveness is evaluated using precision and recall metrics. The results demonstrate how to use attributes from user interaction behaviour to improve the IR effectiveness

abstract: In order to deploy autonomous multi-robot teams for humanitarian demining in Colombia, two key problems need to be addressed. First, a robotic controller with limited power that can completely cover a dynamic search area is needed. Second, the Colombian National Army (COLAR) needs to increase its science, technology and innovation (STI) capacity to help develop, build and maintain such robots. Using Thangavelautham's (2012, 2017) Artificial Neural Tissue (ANT) control algorithm, a robotic controller for an autonomous multi-robot team was developed. Trained by a simple genetic algorithm, ANT is an artificial neural network (ANN) controller with a sparse, coarse coding network architecture and adaptive activation functions. Starting from the exterior of open, basic geometric grid areas, computer simulations of an ANT multi-robot team with limited time steps, no central controller and limited a priori information, covered some areas completely in linear time, and other areas near completely in quasi-linear time, comparable to the theoretical cover time bounds of grid-based, ant pheromone, area coverage algorithms. To mitigate catastrophic forgetting, a new learning method for ANT, Lifelong Adaptive Neuronal Learning (LANL) was developed, where neural network weight parameters for a specific coverage task were frozen, and only the activation function and output behavior parameters were re-trained for a new coverage task. The performance of the LANL controllers were comparable to training all parameters ab initio, for a new ANT controller for the new coverage task. To increase COLAR's STI capacity, a proposal for a new STI officer corps, Project ÉLITE (Equipo de Líderes en Investigación y Tecnología del Ejército) was developed, where officers enroll in a research intensive, master of science program in applied mathematics or physics in Colombia, and conduct research in the US during their final year. ÉLITE is inspired by the Israel Defense Forces Talpiot program. / Dissertation/Thesis / Doctoral Dissertation Applied Mathematics for the Life and Social Sciences 2019

This thesis deals with image filter design using coevolutionary algorithms. It contains a description of evolutionary algorithms, focusing on genetic programming, cartesian genetic programming and coevolution, the reader can learn about image filters too. The next chapters contain the design of image filters and noise detectors using cooperative coevolution, and the implementation and testing of the proposed filter. In the last chapter the proposed filter is compared to other filters created using evolutionary algorithms but without coevolution.