Les développements continus en micro-spectroscopie vibrationnelle IR et en analyse numérique de données multidimensionnelles ont permis récemment l'émergence de l'histologie spectrale. A l'échelle tissulaire et sur une base biomoléculaire, cette nouvelle approche représente un outil prometteur pour une meilleure analyse et caractérisation de différents états physiopathologiques, et potentiellement une aide au diagnostic clinique. Dans ce travail, en utilisant un modèle tissulaire de côlon normal chez la Souris et chez l’Homme, nous avons apporté des améliorations à la chaîne de traitements des données afin d'automatiser et d'optimiser cette histologie spectrale.En effet, dans un premier temps, le développement d’une double application hiérarchique d'indices de validité a permis de déterminer le nombre optimal de classes nécessaire à une caractérisation complète des structures histologiques. Dans un second temps, cette méthode a été généralisée à l'échelle interindividuelle par couplage d'un prétraitement par EMSC (Extended Multiplicative Signal Correction) et d'une classification non-supervisée k-Means; ce couplage étant appliqué conjointement à toutes les images spectrales IR. Enfin, compte tenu de l'essor des métaheuristiques et de leur capacité à résoudre des problèmes complexes d'optimisation numérique, nous avons transposé un algorithme mémétique aux données spectrales IR. Ce nouvel algorithme se compose d'un algorithme génétique et d'un raffinement par classification non-supervisée k-Means. Comparé aux méthodes classiques de clustering, cet algorithme mémétique appliqué aux images spectrales IR, a permis de réaliser une classification non-supervisée optimale et indépendante de l'initialisation. / Recent developments in IR vibrational microspectroscopy and numerical multidimensional analysis have led to the emergence of spectral histology. At the tissue level, this new approach represents an attractive tool for a better analysis and characterization of pathophysiological states and for diagnostic challenges. Here, using normal murine and human colon tissues, data processing steps have been improved for automating and optimizing this spectral histology. First, the development of a hierarchical double application of validity indices permitted to determine the optimal number of clusters that correctly identified the different colon histological components. Second, this method has been improved to perform spectral histology at the inter-individual level. For this, EMSC (Extended Multiplicative Signal Correction) preprocessing has been successfully combined to k-Means clustering. Finally, given the ability of metaheuristics to solve complex optimization problems, a memetic algorithm has been developed for IR spectral data clustering. This algorithm is composed of a genetic algorithm and a k-Means clustering refinement. Compared with conventional clustering methods, our memetic algorithm allowed to generate an optimal and initialization-independent clustering.

Local search algorithms have been proved to be effective in refining solutions that have been found by other algorithms. Evolutionary algorithms, in particular global search algorithms, have shown to be successful in producing approximate solutions for optimisation and classification problems in acceptable computation times. A relatively new method, memetic algorithms, uses local search to refine the approximate solutions produced by global search algorithms. This thesis develops such a memetic algorithm. The global search algorithm used as part of the new memetic algorithm is a genetic program that implements the building block hypothesis by building simplistic decision trees representing valid solutions, and gradually increases the complexity of the trees. The specific building block hypothesis implementation is known as the building block approach to genetic programming, BGP. The effectiveness and efficiency of the new memetic algorithm, which combines the BGP algorithm with a local search algorithm, is demonstrated. / Dissertation (MSc)--University of Pretoria, 2006. / Computer Science / unrestricted

The Vehicle Routing Problem has been around for more than 50 years and has been of major interest to the operations research community. The VRP pose a complex problem with major benefits for the industry. In every supply chain transportation occurs between customers and suppliers. In this thesis, we analyze the use of a multiple pheromone trial in using Ant Systems to solve the VRP. The goal is to find a reasonable solution for data environments of derivatives of the basic VRP. An adaptive object model approach is followed to allow for additional constraints and customizable cost functions. A parallel method is used to improve speed and traversing the solution space. The Ant System is applied to the local search operations as well as the data objects. The Tabu Search method is used in the local search part of the solution. The study succeeds in allowing for all of the key performance indicators, i.e. efficiency, effectiveness, alignment, agility and integration for an IT system, where the traditional research on a VRP algorithm only focuses on the first two. / Thesis (PhD)--University of Pretoria, 2010. / Industrial and Systems Engineering / unrestricted

As social media has emerged to become a key site for contemporary communications and cultural production, the internet meme has penetrated every level of social networking online. Albeit being a global phenomenon with pervasive discursive power in a number of fields ranging from humour to international politics and cyber warfare, comparatively little research has been made into how internet memes work on the discursive level of identity formation and their influence on the formation of internet-based social movements. Using Reddit stock market anarchists r/WallStreetBets as case study, this thesis will use Critical Discourse Analysis to analyze how internet memes work on the level of socio-political formations and how their function can be understood in relation to entropic social environments online. This thesis investigates how internet memes are used as a tool for creation of motifs for action, identity markers, connective action, and social narrativization within an ambivalent social movement online. Introducing the novel term ”memetic discourse” as a way to understand memes as transferable units of memetically programmed content, this study shows the potential of memes to act as effective yet unstable modes of communication within networked environments.

Résumé indisponible. / In this thesis we have concerned ourselves with university timetabling problems both course timetabling and examination timetabling problems. Most of the timetabling problems are computationally NP-complete problems, which means that the amount of computation required to find solutions increases exponentially with problem size. These are idiosyncratic nature problems, for example different universities have their own set of constraints, their own definition of good timetable, feasible timetable and their own choice about the use of constraint type (as a soft or hard constraint). Unfortunately, it is often the case that a problem solving approach which is successfully applied for one specific problem may not become suitable for others. This is a motivation, we propose a generalized problem which covers many constraints used in different universities or never used in literature. Many university timetabling problems are sub problems of this generalized problem. Our proposed algorithms can solve these sub problems easily, moreover constraints can be used according to the desire of user easily because these constraints can be used as reference to penalty attached with them as well. It means that give more penalty value to hard constraints than soft constraint. Thus more penalty value constraints are dealt as a hard constraint by algorithm. Our algorithms can also solve a problem in two phases with little modification, where in first phase hard constraints are solved. In this work we have preferred and used two phase technique to solve timetabling problems because by using this approach algorithms have broader search space in first phase to satisfy hard constraints while not considering soft constraints at all. Two types of algorithms are used in literature to solve university timetabling problem, exact algorithms and approximation algorithms. Exact algorithms are able to find optimal solution, however in university timetabling problems exact algorithms constitute brute-force style procedures. And because these problems have the exponential growth rates of the search spaces, thus these kinds of algorithms can be applied for small size problems. On the other side, approximation algorithms may construct optimal solution or not but they can produce good practically useable solutions. Thus due to these factors we have proposed approximation algorithms to solve university timetabling problem. We have proposed metaheuristic based techniques to solve timetabling problem, thus we have mostly discussed metaheuristic based algorithms such as evolutionary algorithms, simulated annealing, tabu search, ant colony optimization and honey bee algorithms. These algorithms have been used to solve many other combinatorial optimization problems other than timetabling problem by modifying a general purpose algorithmic framework. We also have presented a bibliography of linear integer programming techniques used to solve timetabling problem because we have formulated linear integer programming formulations for our course and examination timetabling problems. We have proposed two stage algorithms where hard constraints are satisfied in first phase and soft constraints in second phase. The main purpose to use this two stage technique is that in first phase hard constraints satisfaction can use more relax search space because in first phase it does not consider soft constraints. In second phase it tries to satisfy soft constraints when maintaining hard constraints satisfaction which are already done in first phase. (...)

Submitted by Fabricia Fialho Reginato (fabriciar) on 2015-07-28T22:46:54Z No. of bitstreams: 1 JamesBrum.pdf: 2178179 bytes, checksum: 22c4d2e31ff012df7823bad3151fc4de (MD5) / Made available in DSpace on 2015-07-28T22:46:54Z (GMT). No. of bitstreams: 1 JamesBrum.pdf: 2178179 bytes, checksum: 22c4d2e31ff012df7823bad3151fc4de (MD5) Previous issue date: 2014 / PROCERGS – Cia de Processamento Dados do Estado Rio Grande Sul / Este trabalho apresenta o desenvolvimento de um protótipo de software, utilizando metaheurísticas por meio de um Algoritmo Memético, para a Geração de Grade de Programação de intervenções comerciais aplicada à TV Digital e a IPTV. O problema apresenta-se como uma linha de tempo na grade televisiva com sua programação onde estão definidos horários de intervenção em que grupos de comerciais devem ser exibidos. A organização destes comerciais nas intervenções obedecem a um conjunto de requisitos que devem ser otimizados como: a taxa de retorno, adequação ao público alvo, e utilização da largura de banda do servidor e também de restrições como: a classificação indicativa, número de exibições do comercial e adequação à programação. Neste contexto são considerados os problemas de Seleção de Partes e de Timetabling para a elaboração do protótipo, abordando sua solução com a utilização de um Algoritmo Memético, desenvolvido aplicando as metaheurísticas de Algoritmos Genéticos e de Busca Tabu. O resultado obtido foi a geração de uma ferramenta computacional que viabilizou o gerenciamento da inserção de comerciais nas grades de programação, através da obtenção de soluções de boa qualidade. / This paper shows the development of a software prototype using metaheuristics via a memetic algorithm to generation of the Grid Programming of ads interventions applied to Digital TV and IPTV. This problem is presented as a timeline in a TV programing with intervals of interventions where ads groups should be displayed. The organization of these interventions ads groups follow a set of requirements that must be optimized as: the rate of return, appropriateness to the target audience, and use of the bandwidth of the server, and also restrictions like: parental rating, number of views of each ad, time box of the intervention and fitness programming. In this context are considered the problems of Selection Parties and Timetabling for build the prototype and approach the solution using a memetic algorithm developed by applying the metaheuristic Genetic Algorithms and Tabu Search. The resulted was the generation of a computational tool that allows the insertion of ads management in grids programming, by obtaining good quality solutins.

The automatic recognition of individuals through the iris characteristics is an e±cient biometric technique that is widely studied and applied around the world. Many image processing stages are necessary to make possible the representation and the interpretation of the iris information. This work presents the state of the art in iris recognition systems where the most re- markable works and the di®erent techniques applied to perform each process- ing stage are quoted. The implementations of each processing stage using traditional techniques are presented and, afterwards, two innovator methods are proposed with the common objective of bringing bene¯t to the system. The ¯rst processing stage should be the localization of the iris region in an eye image. The ¯rst method proposed in this work presents an algorithm to achieve the iris localization through the utilization of the called Memetic Algorithms. The new method is compared to a classical method and the obtained results show advantages concerning e±ciency and processing time. In another processing stage there must be a pixels sampling from the iris region, from where the information used to di®erentiate the individuals is extracted. Traditionally, this sampling process is accomplished in an uni- form way along the whole iris region. It is proposed a pre-processing method which suggests a non uniform pixels sampling from the iris region with the objective of selecting the group of pixels which carry more information about the iris structure. The search for this group of pixels is done through Ge- netic Algorithms. The application of the new method improves the e±ciency of the system and also, allows the generation of smaller templates. In this work, a study on the called Active Shape Models is also accomplished and its application to perform the iris region segmentation is evaluated. To execute the simulations and the evaluation of the methods, it was used two public and free iris images database: UBIRIS database and MMU database. / O reconhecimento automático de pessoas utilizando-se características da íris é uma eficiente técnica biométrica que está sendo largamente estudada e aplicada em todo o mundo. Diversas etapas de processamento são necessárias para tornar possível a representação e a interpretação da informação contida na íris. Neste trabalho é apresentado o estado da arte de sistemas de reconhecimento de íris onde são citados os trabalhos de maior destaque e as diferentes técnicas empregadas em cada etapa de processamento. São apresentadas implementações de cada etapa de processamento utilizando técnicas tradicionais e, posteriormente, são propostos dois métodos inovadores que têm o objetivo comum de trazer benefícios ao sistema. A primeira etapa de processamento é a localização da região da íris na imagem. O primeiro método proposto neste trabalho apresenta um algoritmo para realizar a localização da íris utilizando os chamados Algoritmos Meméticos. O novo método é comparado a um método clássico e os resultadosnobtidos demonstram vantagens no que diz respeito à eficiência e ao tempo de processamento. Em uma outra etapa de processamento deve haver uma amostragem de pixels na região da íris, de onde são retiradas as informações utilizadas para diferenciar os indivíduos. Tradicionalmente, esta amostragem é realizada de maneira uniforme ao longo de toda a região da íris. É proposto um método de pré-processamento que sugere uma amostragem não uniforme de pixels na região da íris com o objetivo de selecionar o conjunto de pixels que carregam mais informações da estrutura da íris. A busca por esse conjunto de pixels é realizada utilizando-se Algoritmos Genéticos. A aplicação deste novo método aumenta a eficiência do sistema e ainda possibilita a geração de templates binários menores. Neste trabalho é realizado, ainda, um estudos dos chamados Active Shape Models e a sua aplicação para segmentar a região da íris é avaliada. Para a simulação e avaliação dos métodos, foram utilizados dois bancos de imagens de íris públicos e gratuitos: o banco de imagens UBIRIS e o banco de imagens MMU. / Doutor em Ciências

Made available in DSpace on 2014-12-17T15:48:00Z (GMT). No. of bitstreams: 1 GustavoAS_DISSERT.pdf: 3060399 bytes, checksum: 659289bc757f2443a1b6902094747b13 (MD5) Previous issue date: 2012-02-27 / This work approaches the Scheduling Workover Rigs Problem (SWRP) to maintain the wells of an oil field, although difficult to resolve, is extremely important economical, technical and environmental. A mathematical formulation of this problem is presented, where an algorithmic approach was developed. The problem can be considered to find the best scheduling service to the wells by the workover rigs, taking into account the minimization of the composition related to the costs of the workover rigs and the total loss of oil suffered by the wells. This problem is similar to the Vehicle Routing Problem (VRP), which is classified as belonging to the NP-hard class. The goal of this research is to develop an algorithmic approach to solve the SWRP, using the fundamentals of metaheuristics like Memetic Algorithm and GRASP. Instances are generated for the tests to analyze the computational performance of the approaches mentioned above, using data that are close to reality. Thereafter, is performed a comparison of performance and quality of the results obtained by each one of techniques used / O trabalho em quest?o aborda o Problema da Programa??o das Sondas de Produ??o (PPSP) para atender os po?os de um campo de petr?leo. Embora de dif?cil resolu??o, ele ? de extrema import?ncia econ?mica, t?cnica e ambiental. Uma formula??o matem?tica deste problema ? apresentada, assim como desenvolvida uma abordagem algor?tmica. O problema abordado pode ser considerado como o de encontrar o melhor escalonamento de atendimento aos po?os pelas sondas, levando em considera??o a minimiza??o da composi??o dos custos relativos ?s sondas e da perda total da produ??o de petr?leo associada aos po?os que est?o aguardando por atendimento. Tal problema assemelha-se ao Problema de Roteamento de Ve?culos (PRV), que ? classificado como pertencente ? classe de problemas NP-Dif?cil. O objetivo da presente pesquisa ? desenvolver uma abordagem algor?tmica para resolver o PPSP, utilizando os fundamentos de metaheur?sticas como o Algoritmo Mem?tico e o GRASP. Inst?ncias s?o geradas para a realiza??o dos testes computacionais para an?lise do desempenho das abordagens acima citadas, utilizando dados que se aproximam da realidade. A partir da?, ? realizada uma compara??o de desempenho e qualidade dos resultados obtidos por cada uma das t?cnicas utilizadas

Made available in DSpace on 2014-12-17T15:48:07Z (GMT). No. of bitstreams: 1 CamilaNOT_DISSERT.pdf: 4321465 bytes, checksum: d103bd2da647997e8dfd0a8784c2060d (MD5) Previous issue date: 2013-02-01 / Nonogram is a logical puzzle whose associated decision problem is NP-complete. It has applications in pattern recognition problems and data compression, among others. The puzzle consists in determining an assignment of colors to pixels distributed in a N  M matrix that satisfies line and column constraints. A Nonogram is encoded by a vector whose elements specify the number of pixels in each row and column of a figure without specifying their coordinates. This work presents exact and heuristic approaches to solve Nonograms. The depth first search was one of the chosen exact approaches because it is a typical example of brute search algorithm that is easy to implement. Another implemented exact approach was based on the Las Vegas algorithm, so that we intend to investigate whether the randomness introduce by the Las Vegas-based algorithm would be an advantage over the depth first search. The Nonogram is also transformed into a Constraint Satisfaction Problem. Three heuristics approaches are proposed: a Tabu Search and two memetic algorithms. A new function to calculate the objective function is proposed. The approaches are applied on 234 instances, the size of the instances ranging from 5 x 5 to 100 x 100 size, and including logical and random Nonograms / O Nonograma ? um jogo l?gico cujo problema de decis?o associado ? NP-completo. Ele possui aplica??o em problemas de identifica??o de padr?es e de compacta??o de dados, dentre outros. O jogo consiste em determinar uma aloca??o de cores em pixels distribu?dos em uma matriz N  M atendendo restri??es em linhas e colunas. Um Nonograma ? codificado atrav?s de vetores cujos elementos especificam o n?mero de pixels existentes em cada coluna e linha de uma figura, sem especificar suas coordenadas. Este trabalho apresenta abordagens exatas e heur?sticas para solucionar o Nonograma. A Busca em Profundidade foi uma das abordagens exatas escolhida, por ser um exemplo t?pico de algoritmo de for?a bruta de f?cil implementa??o. Outra abordagem exata implementada foi baseada no algoritmo Las Vegas, atrav?s do qual se pretende investigar se a aleatoriedade introduzida pelo algoritmo Las Vegas traria algum benef?cio em rela??o ? Busca em Profundidade. O Nonograma tamb?m ? transformado em um Problema de Satisfa??o de Restri??es. Tr?s abordagens heur?sticas s?o propostas: uma Busca Tabu e dois algoritmos Mem?tico. Uma nova abordagem para o c?lculo da fun??o objetivo ? proposta neste trabalho. As abordagens s?o testadas em 234 casos de teste de tamanho entre 5 x 5 e 100 x 100, incluindo Nonogramas l?gicos e aleat?rios

Made available in DSpace on 2014-12-17T14:52:43Z (GMT). No. of bitstreams: 1 AnaCGS.pdf: 4192359 bytes, checksum: 28eb36354363672f88a28074f9df8b42 (MD5) Previous issue date: 2008-12-23 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Telecommunications play a key role in contemporary society. However, as new technologies are put into the market, it also grows the demanding for new products and services that depend on the offered infrastructure, making the problems of planning telecommunications networks, despite the advances in technology, increasingly larger and complex. However, many of these problems can be formulated as models of combinatorial optimization, and the use of heuristic algorithms can help solving these issues in the planning phase. In this project it was developed two pure metaheuristic implementations Genetic algorithm (GA) and Memetic Algorithm (MA) plus a third hybrid implementation Memetic Algorithm with Vocabulary Building (MA+VB) for a problem in telecommunications that is known in the literature as Problem SONET Ring Assignment Problem or SRAP. The SRAP arises during the planning stage of the physical network and it consists in the selection of connections between a number of locations (customers) in order to meet a series of restrictions on the lowest possible cost. This problem is NP-hard, so efficient exact algorithms (in polynomial complexity ) are not known and may, indeed, even exist / As telecomunica??es desempenham um papel fundamental na sociedade contempor?nea. Mas ? medida que novas tecnologias s?o introduzidas ao mercado, cresce tamb?m a demanda por novos produtos e servi?os que dependem da infra-estrutura oferecida, tornando os problemas de planejamento de redes de telecomunica??es, apesar da evolu??o tecnol?gica, cada vez maiores e complexos. No entanto, muitos desses problemas podem ser formulados como modelos de otimiza??o combinat?ria, e o uso de algoritmos heur?sticos podem ajudar a solucionar essas quest?es da fase de planejamento. Neste trabalho, foram desenvolvidas duas implementa??es metaheur?sticas puras Algoritmo Gen?tico (AG) e Algoritmo Mem?tico (AM) al?m de uma terceira implementa??o h?brida Algoritmo Mem?tico com Vocabulary Building (AM+VB) para um problema de telecomunica??es que ? conhecido na literatura por Problema de Atribui??o de Localidades a An?is SONET ou SRAP (do ingl?s, SONET Ring Assignment Problem). O SRAP surge durante a etapa do planejamento f?sico da rede e consiste na determina??o das conex?es entre um conjunto de localidades (clientes), de modo a satisfazer uma s?rie de restri??es ao menor custo poss?vel. Esse problema ? NP-dif?cil e portanto algoritmos exatos eficientes (de complexidade polinomial) n?o s?o conhecidos, podendo, inclusive, nem existir