Submitted by CARLA MARIA GOULART DE MORAES (carlagm) on 2015-04-01T18:43:13Z No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) / Made available in DSpace on 2015-04-01T18:43:13Z (GMT). No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) Previous issue date: 2011 / CNPQ – Conselho Nacional de Desenvolvimento Científico e Tecnológico / Este trabalho aborda o Problema de Roteamento de Veículos Capacitado com Janelas de Tempo, onde devem ser atendidas as restrições de capacidade do veículo e as janelas de tempo de atendimento do cliente. Para resolver tal problema serão utilizadas as metaheurísticas Busca Tabu e Algoritmos Genéticos, além do desenvolvimento de um Algoritmo Híbrido baseado nas duas metaheurísticas. Busca-se contribuir com o desenvolvimento de um Algoritmo Híbrido focado no Problema de Roteamento de Veículos que utilize o poder de intensificação da Busca Tabu e o poder de diversificação do Algoritmo Genético, objetivando a obtenção de soluções de boa qualidade sem comprometer o tempo computacional. Nos experimentos, no que tange a Busca Tabu, analisa-se o processo de busca da através da variação do tamanho da Lista Tabu e do número máximo de iterações sem melhora do valor da função objetivo, como critério de parada, aplicados a uma política de intensificação. Para o Algoritmo Genético, é analisada a influência e o comportamento da busca com base em três operadores de cruzamento aplicados a duas políticas de elitismo. Ainda assim, para o Algoritmo Híbrido, analisa-se o impacto do tamanho da Lista Tabu e das taxas de Mutação e Cruzamento. Por fim, os resultados obtidos são comparados com os melhores métodos heurísticos encontrados na literatura e com métodos exatos, onde o Algoritmo Híbrido mostra-se robusto, obtendo soluções ótimas para diversas instancias de problemas. / This paper approaches the Capacitated Vehicle Routing Problem with Time Windows, which must obey the restrictions on vehicle capacity and time windows for customer service. To solve this problem will be used two metaheuristics, Tabu Search and Genetic Algorithms, and are developed an hybrid algorithm based on this two metaheuristics. The aim is to contribute with the development of a Hybrid Algorithm focused on Vehicle Routing Problem that uses the Tabu Search intensification power and the Genetic Algorithms diversification power, in order to obtain good quality solutions without compromising the computational time. In the experiments, with respect to Tabu Search, we analyze the search process by varying the size of the Tabu List and the maximum number of iterations without improvement in objective function value, such as stopping criterion, applied to an intensification policy. For the genetic algorithm are analyzed the influence and the search behavior on the basis of three crossover operators, applied to two elitism policies. Still, for the hybrid algorithm, we analyze the impact of the Tabu List size and rates of mutation and crossover. Finally, the results are compared with the best heuristics in the literature and with exact methods, where the Hybrid Algorithm shows robust, getting several optimal solutions.

Le nombre de robot humanoïde s’est accru ces dernières années pour pouvoir collaborer avec l’homme ou le remplacer dans des tâches fastidieuses. L’objectif de cette thèse est de transférer aux robots humanoïdes, des habilités ou compétences humaines, en particulier pour des mouvements impliquant une coordination entre les deux bras. Dans la première partie de la thèse, un processus de conversion d’un mouvement humain vers un mouvement de robot, dans un objectif d’imitation est proposé. Comme les humains possèdent beaucoup plus de degrés de liberté qu’un robot humanoïde, les mouvements identiques ne peuvent pas être produits, les caractéristiques(longueurs des corps) peuvent aussi être différentes. Notre processus de conversion prend en compte l’enregistrement des localisations de marqueurs attachés aux corps de l’humain et des articulations pour améliorer les processus d’imitation. La deuxième partie de la thèse vise à analyser les stratégies de génération du mouvement utilisées par l’homme. Les mouvements humains sont supposés optimaux et notre objectif est de trouver un critère à minimiser pendant les manipulations. Nous faisons l’hypothèse que ce critère est une combinaison de critères classiquement utilisés en robotique et nous recherchons les poids de chaque critère qui représente au mieux le mouvement humain. De cette façon, une approche de commande cinématique optimale peut ensuite être utilisée pour générer des mouvements du robot humanoïde. / The number of humanoid robots has increased in recent years to be able to collaborate with humans or replace them in tedious tasks. The objective of this thesis is to transfer to humanoid robots, skills or human competences, in particular for movements involving coordination between the two arms. In the first part of the thesis, a process of conversion from a human movement to a robot movement, with the aim of imitation is proposed. Since humans have much more freedom than a humanoid robot, identical movements cannot be produced, the characteristics (body lengths) canal so be different. Our conversion process takes into account the recording of marker locations attached to human bodies and joints to improve the imitation processes. The second part of the thesis aims at analyzing the strategies used by humans to generate movement. Human movements are assumed to be optimal and our goal is to find criteria minimized during manipulations. We hypothesize that this criterion is a combination of classical criteria used in robotics and we look for the weights of each criterion that best represents human movement. In this way, an optimal kinematic control approach can then be used to generate movements of the humanoid robot.

Estimation of Distribution Algorithm (EDA) is a branch of evolutionary computation that learn a probabilistic model of good solutions. Probabilistic models are used to represent relationships between solution variables which may give useful, human-understandable insights into real-world problems. Also, developing an effective PM has been shown to significantly reduce function evaluations needed to reach good solutions. This is also useful for real-world problems because their representations are often complex needing more computation to arrive at good solutions. In particular, many real-world problems are naturally represented as permutations and have expensive evaluation functions. EDAs can, however, be computationally expensive when models are too complex. There has therefore been much recent work on developing suitable EDAs for permutation representation. EDAs can now produce state-of-the-art performance on some permutation benchmark problems. However, models are still complex and computationally expensive making them hard to apply to real-world problems. This study investigates some limitations of EDAs in solving permutation and scheduling problems. The focus of this thesis is on addressing redundancies in the Random Key representation, preserving diversity in EDA, simplifying the complexity attributed to the use of multiple local improvement procedures and transferring knowledge from solving a benchmark project scheduling problem to a similar real-world problem. In this thesis, we achieve state-of-the-art performance on the Permutation Flowshop Scheduling Problem benchmarks as well as significantly reducing both the computational effort required to build the probabilistic model and the number of function evaluations. We also achieve competitive results on project scheduling benchmarks. Methods adapted for solving a real-world project scheduling problem presents significant improvements.

O campo da Biometria abarca uma grande variedade de tecnologias usadas para identificar e verificar a identidade de uma pessoa por meio da mensuração e análise de vários aspectos físicos e/ou comportamentais do ser humano. Diversas modalidades biométricas têm sido propostas para reconhecimento de pessoas, como impressões digitais, íris, face e voz. Estas modalidades biométricas possuem características distintas em termos de desempenho, mensurabilidade e aceitabilidade. Uma questão a ser considerada com a aplicação de sistemas biométricos em mundo real é sua robustez a ataques por circunvenção, repetição e ofuscação. Esses ataques estão se tornando cada vez mais frequentes e questionamentos estão sendo levantados a respeito dos níveis de segurança que esta tecnologia pode oferecer. Recentemente, sinais biomédicos, como eletrocardiograma (ECG), eletroencefalograma (EEG) e eletromiograma (EMG) têm sido estudados para uso em problemas envolvendo reconhecimento biométrico. A formação do sinal do ECG é uma função da anatomia estrutural e funcional do coração e dos seus tecidos circundantes. Portanto, o ECG de um indivíduo exibe padrão cardíaco único e não pode ser facilmente forjado ou duplicado, o que tem motivado a sua utilização em sistemas de identificação. Entretanto, a quantidade de características que podem ser extraídas destes sinais é muito grande. A seleção de característica tem se tornado o foco de muitas pesquisas em áreas em que bases de dados formadas por dezenas ou centenas de milhares de características estão disponíveis. Seleção de característica ajuda na compreensão dos dados, reduzindo o custo computacional, reduzindo o efeito da maldição da dimensionalidade e melhorando o desempenho do preditor. O foco da seleção de característica é selecionar um subconjunto de característica a partir dos dados de entrada, que pode descrever de forma eficiente os dados de entrada ao mesmo tempo reduzir os efeitos de ruídos ou características irrelevantes e ainda proporcionar bons resultados de predição. O objetivo desta dissertação é analisar o impacto de algumas técnicas de seleção de característica tais como, Busca Gulosa, Seleção \\textit, Algoritmo Genético, Algoritmo Memético, Otimização por Enxame de Partículas sobre o desempenho alcançado pelos sistemas biométricos baseado em ECG. Os classificadores utilizados foram $k$-Vizinhos mais Próximos, Máquinas de Vetores Suporte, Floresta de Caminhos Ótimos e classificador baseado em distância mínima. Os resultados demonstram que existe um subconjunto de características extraídas do sinal de ECG capaz de fornecer altas taxas de reconhecimento / The field of biometrics includes a variety of technologies used to identify and verify the identity of a person by measuring and analyzing various physical and/or behavioral aspects of the human being. Several biometric modalities have been proposed for recognition of people, such as fingerprints, iris, face and speech. These biometric modalities have distinct characteristics in terms of performance, measurability and acceptability. One issue to be considered with the application of biometric systems in real world is its robustness to attacks by circumvention, spoof and obfuscation. These attacks are becoming more frequent and more questions are being raised about the levels of security that this technology can offer. Recently, biomedical signals, as electrocardiogram (ECG), electroencephalogram (EEG) and electromyogram (EMG) have been studied for use in problems involving biometric recognition. The ECG signal formation is a function of structural and functional anatomy of the heart and its surrounding tissues. Therefore, the ECG of an individual exhibits unique cardiac pattern and cannot be easily forged or duplicated, that have motivated its use in various identification systems. However, the amount of features that can be extracted from this signal is very large. The feature selection has become the focus of much research in areas where databases formed by tens or hundreds of thousands of features are available. Feature Selection helps in understanding data, reducing computation requirement, reducing the effect of curse of dimensionality and improving the predictor performance. The focus of feature selection is to select a subset of features from the input which can efficiently describe the input data while reducing effects from noise or irrelevant features and still provide good prediction results. The aim of this dissertation is to analyze the impact of some feature selection techniques, such as, greedy search, Backward Selection, Genetic Algorithm, Memetic Algorithm, Particle Swarm Optimization on the performance achieved by biometric systems based on ECG. The classifiers used were $k$-Nearest Neighbors, Support Vector Machines, Optimum-Path Forest and minimum distance classifier. The results demonstrate that there is a subset of features extracted from the ECG signal capable of providing high recognition rates

Feeder reconfiguration is performed by changing the open/close status of two types of switches: normally open tie switches and normally closed sectionalizing switches. A whole feeder or part of a feeder may be served from another feeder by closing a tie switch linking the two while an appropriate sectionalizing switch must be opened to maintain the radial structure of the system. Feeder reconfiguration is mainly aiming to reduce the system overall power losses and improve voltage profile. In this dissertation, several approaches have been proposed to reconfigure the radial distribution networks including the potential impact of integrating Distributed Energy Resources (DER) into the grid. These approaches provide a Fast-Genetic Algorithm “FGA” in which the size and convergence speed is improved compared to the conventional genetic algorithm. The size of the population matrix is also smaller because of the simple way of constructing the meshed network. Additionally, FGA deals with integer variable instead of a binary one, which makes FGA a unique method. The number of the mesh/loop is based on the number of tie switches in a particular network. The validity of the proposed FGA is investigated by comparing the obtained results with the one obtained from the most recent approaches. The second the approach is the implementation of the Differential Evolution (DE) algorithm. DE is a population-based method using three operators including crossover, mutation, and selection. It differs from GA in that genetic algorithms rely on crossover while DE relies on mutation. Mutation is based on the differences between randomly sampled pairs of solutions in the population. DE has three advantages: the ability to find the global optimal result regardless of the initial values, fast convergence, and requirement of a few control parameters. DE is a well-known and straightforward population-based probabilistic approach for comprehensive optimization. In distribution systems, if a utility company has the right to control the location and size of distributed generations, then the location and size of DGs may be determined based on some optimization methods. This research provides a promising approach to finding the optimal size and location of the planned DER units using the proposed DE algorithm. DGs location is obtained using the sensitivity of power losses with respect to real power injection at each bus. Then the most sensitive bus is selected for installing the DG unit. Because the integration of the DG adds positive real power injections, the optimal location is the one with the most negative sensitivity in order to get the largest power loss reduction. Finally, after the location is specified, the proposed Differential Evolution Algorithm (DEA) is used to obtain the optimal size of the DG unit. Only the feasible solutions that satisfy all the constraints are considered. The objective of installing DG units to the distribution network is to reduce the system losses and enhance the network voltage profile. Nowadays, these renewable DGs are required to equip with reactive power devices (such as static VAR compensators, capacitor banks, etc.), to provide reactive power as well as to control the voltage at their terminal bus. DGs have various technical benefits such as voltage profile improvement, relief in feeder loading, power loss minimization, stability improvement, and voltage deviation mitigation. The distributed generation may not achieve its full potential of benefits if placed at any random location in the system. It is necessary to investigate and determine the optimum location and size of the DG. Most distribution networks are radial in nature with limited short-circuit capacity. Therefore, there is a limit to which power can be injected into the distribution network without compromising the power quality and the system stability. This research is aiming to investigate this by applying DG technologies to the grid and keeping the system voltage within a defined boundary [0.95 - 1.05 p.u]. The requirements specified in IEEE Standard 1547 are considered. This research considers four objectives related to minimization of the system power loss, minimization of the deviations of the nodes voltage, minimization of branch current constraint violation, and minimization of feeder’s currents imbalance. The research formulates the problem as a multi-objective problem. The effectiveness of the proposed methods is demonstrated on different revised IEEE test systems including 16 and 33-bus radial distribution system.

In this thesis three methods LMGS, TQR and GR are applied to solve an inverseeigenvalue problem. We list the numerical results and compare the accuracy of the computed Jacobi matrix $T$ and the associated orthogonal matrix $Q$, wherethe columns of $Q^T$ are the eigenvectors of $T$. In the application of this inverse eigenvalue problem, the Fourier coefficients of $h(x)=e^x$ relative to the orthonormal polynomials associatedwith $T$ are evaluated, and these values are used to compute the least squarescoefficients of $h$ relative to the Chebyshev polynomials. We list thesenumerical results and compare them as our conclusion.

The conventional Verlet table neighbor list algorithm is improved to reduce the number of unnecessary inter-atomic distance calculations in molecular simulations involving large amount of atoms. Both of the serial and parallelized performance of molecular dynamics simulation are evaluated using the new algorithm and compared with those using the conventional Verlet table and cell-linked list algorithm. Results show that the new algorithm significantly improved the performance of molecular dynamics simulation compared with conventional neighbor list maintaining and utilizing algorithms in serial programs as well as parallelized programs. / Singapore-MIT Alliance (SMA)

Random walks describe diffusion processes, where movement at every time step is restricted only to neighbouring locations. Classical random walks are constructed using the non-relativistic Laplacian evolution operator and a coin toss instruction. In quantum theory, an alternative is to use the relativistic Dirac operator. That necessarily introduces an internal degree of freedom (chirality), which may be identified with the coin. The resultant walk spreads quadratically faster than the classical one, and can be applied to a variety of graph theoretical problems. We study in detail the problem of spatial search, i.e. finding a marked site on a hypercubic lattice in d-dimensions. For d=1, the scaling behaviour of classical and quantum spatial search is the same due to the restriction on movement. On the other hand, the restriction on movement hardly matters for d ≥ 3, and scaling behaviour close to Grover’s optimal algorithm(which has no restriction on movement) can be achieved. d=2 is the borderline critical dimension, where infrared divergence in propagation leads to logarithmic slow down that can be minimised using clever chirality flips. In support of these analytic expectations, we present numerical simulation results for d=2 to d=9, using a lattice implementation of the Dirac operator inspired by staggered fermions. We optimise the parameters of the algorithm, and the simulation results demonstrate that the number of binary oracle calls required for d= 2 and d ≥ 3 spatial search problems are O(√NlogN) and O(√N) respectively. Moreover, with increasing d, the results approach the optimal behaviour of Grover’s algorithm(corresponding to mean field theory or d → ∞ limit). In particular, the d = 3 scaling behaviour is only about 25% higher than the optimal value.

The Steiner Tree problem has appeared in the Karp's list of the first 21 NP-hard problems and is well known as one of the most fundamental problems in Network Design area. We study the Node-Weighted version of the Prize Collecting Steiner Tree problem. In this problem, we are given a simple graph with a cost and penalty value associated with each node. Our goal is to find a subtree T of the graph minimizing the cost of the nodes in T plus penalty of the nodes not in T. By a reduction from set cover problem it can be easily shown that the problem cannot be approximated in polynomial time within factor of (1-o(1))ln n unless NP has quasi-polynomial time algorithms, where n is the number of vertices of the graph. Moss and Rabani claimed an O(log n)-approximation algorithm for the problem using a Primal-Dual approach in their STOC'01 paper \cite{moss2001}. We show that their algorithm is incorrect by providing a counter example in which there is an O(n) gap between the dual solution constructed by their algorithm and the optimal solution. Further, evidence is given that their algorithm probably does not have a simple fix. We propose a new algorithm which is more involved and introduces novel ideas in primal dual approach for network design problems. Also, our algorithm is a Lagrangian Multiplier Preserving algorithm and we show how this property can be utilized to design an O(log n)-approximation algorithm for the Node-Weighted Quota Steiner Tree problem using the Lagrangian Relaxation method. We also show an application of the Node Weighted Quota Steiner Tree problem in designing algorithm with better approximation factor for Technology Diffusion problem, a problem proposed by Goldberg and Liu in \cite{goldberg2012} (SODA 2013). In Technology Diffusion, we are given a graph G and a threshold θ(v) associated with each vertex v and we are seeking a set of initial nodes called the seed set. Technology Diffusion is a dynamic process defined over time in which each vertex is either active or inactive. The vertices in the seed set are initially activated and each other vertex v gets activated whenever there are at least θ(v) active nodes connected to v through other active nodes. The Technology Diffusion problem asks to find the minimum seed set activating all nodes. Goldberg and Liu gave an O(rllog n)-approximation algorithm for the problem where r and l are the diameter of G and the number of distinct threshold values, respectively. We improve the approximation factor to O(min{r,l}log n) by establishing a close connection between the problem and the Node Weighted Quota Steiner Tree problem.

Prostate segmentation is a required step in determining the volume of a prostate, which is very important in the diagnosis and the treatment of prostate cancer. In the past, radiologists manually segment the two-dimensional cross-sectional ultrasound images. Typically, it is necessary for them to outline at least a hundred of cross-sectional images in order to get an accurate estimate of the prostate's volume. This approach is very time-consuming. To be more efficient in accomplishing this task, an automated procedure has to be developed. However, because of the quality of the ultrasound image, it is very difficult to develop a computerized method for defining boundary of an object in an ultrasound image. The goal of this thesis is to find an automated segmentation algorithm for detecting the boundary of the prostate in ultrasound images. As the first step in this endeavour, a semi-automatic segmentation method is designed. This method is only semi-automatic because it requires the user to enter four initialization points, which are the data required in defining the initial contour. The discrete dynamic contour (DDC) algorithm is then used to automatically update the contour. The DDC model is made up of a set of connected vertices. When provided with an energy field that describes the features of the ultrasound image, the model automatically adjusts the vertices of the contour to attain a maximum energy. In the proposed algorithm, Mallat's dyadic wavelet transform is used to determine the energy field. Using the dyadic wavelet transform, approximate coefficients and detailed coefficients at different scales can be generated. In particular, the two sets of detailed coefficients represent the gradient of the smoothed ultrasound image. Since the gradient modulus is high at the locations where edge features appear, it is assigned to be the energy field used to drive the DDC model. The ultimate goal of this work is to develop a fully-automatic segmentation algorithm. Since only the initialization stage requires human supervision in the proposed semi-automatic initialization algorithm, the task of developing a fully-automatic segmentation algorithm is reduced to designing a fully-automatic initialization process. Such a process is introduced in this thesis. In this work, the contours defined by the semi-automatic and the fully-automatic segmentation algorithm are compared with the boundary outlined by an expert observer. Tested using 8 sample images, the mean absolute difference between the semi-automatically defined and the manually outlined boundary is less than 2. 5 pixels, and that between the fully-automatically defined and the manually outlined boundary is less than 4 pixels. Automated segmentation tools that achieve this level of accuracy would be very useful in assisting radiologists to accomplish the task of segmenting prostate boundary much more efficiently.