Made available in DSpace on 2015-05-14T12:36:37Z (GMT). No. of bitstreams: 1 ArquivoTotalDaniel.pdf: 2752447 bytes, checksum: 5dbeb5dd6c935f25f004b1edb1df7d70 (MD5) Previous issue date: 2013-03-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Problems of traffic jam, lack of vacancies in garages and cars underutilized are part of the current scenario of big cities. In this work is created a module for creating efficient routes for a system using the approach Dial-a-Ride Problem. The DARP is a vehicle routing problem that belongs to NP-complete class. It aims is to minimize operating costs while maintaining quality of service to the client. It is presented an algorithm that uses the metaheuristics Iterated Local Search with the Variable Neighborhood Search to solve the DARP. Compared to related work in the area, the results were better regarding to distance traveled and average travel time of customers. / Problemas de congestionamentos, falta de vagas em garagens e carros subutilizados fazem parte do cenário atual das grandes cidades. Neste trabalho é criado um módulo para criação de rotas eficiente para sistemas de caronas utilizando a abordagem Dial-a-Ride Problem. O DARP é um problema de roteamento pertencente a classe NP-Completo. Este tem como objetivo minimizar os custos operacionais, mas mantendo uma qualidade de serviço para o usuário. É apresentado um algoritmo que utiliza as metaheurística Iterated Local Search juntamente com a Variable Neighborhood Search para solucionar o DARP. Comparados com outros trabalhos relevantes na área, os resultados encontrados foram melhores no que se refere à distância percorrida e no tempo médio de viagem dos clientes.

[pt] Este trabalho tem como objetivo propor uma metaheurística Iterated Local Search para minimizar o tempo de término ponderado de jobs em problemas de escalonamento de máquinas idênticas paralelas. O objetivo secundário do trabalho é propor uma solução prática para um problema real da companhia estudada em questão. A motivação para o trabalho consiste em uma aplicação prática na indústria de óleo e gás, onde os navios PLSV realizam operações em poços de forma ordenada e visando a antecipação dos poços de petróleo mais produtivos. As características do problema, tais quais: elegibilidade entre navio e operações, tempos de setup relativos à família de atividades, associações entre operações e poços e setups que dependem da chegada de material se adequam a modelagem baseada em escalonamento de máquinas paralelas idênticas. No trabalho uma introdução à respeito do tema é apresentada, em seguida é feita uma revisão da literatura sobre problemas de máquinas paralelas idênticas, a formulação matemática com a descrição do problema é apresentada, a metodologia contemplando representação da solução, heuristica construtiva, vizinhanças exploradas, busca local e Iterated Local Search é exposta, por fim são apresentados os resultados do método e as conclusões sobre o trabalho. / [en] This work objective is to propose an Iterated Local Search metaheuristic to minimize the weighted completion time of jobs on identical parallel machines scheduling problems. The secondary objective of this work is to propose a practical solution to the real problem of the studied company. The motivation of this work consists on a practical application in the Oil and Gas industry, where the PLSV vessels perform ordered operations in a set of wells aiming to maximize the oil production. The characteristics of the problem such as: eligibility between vessels and operations, setup times related to the family of activities, association between operations and wells and setup times depending on the material arrival fit well the identical parallel machine schedule modelling. In this work, an introduction about the theme is presented, followed by a literature review on identical parallel machine scheduling problems, the mathematical formulation with the problem description is presented, the methodology, including the solution representation, constructive heuristic, neighborhood structures, local search and Iterated Local Search is exposed, at last, the method results and conclusions of the work are summarized.

[pt] O transporte escolar é fundamental para garantir o acesso e permanência dos alunos nas escolas públicas, principalmente nas áreas rurais, onde os estudantes estão localizados em uma grande área com baixa densidade e as estradas encontram-se em situações precárias. O presente trabalho tem como objetivo aplicar a metaheurística Iterated Local Search para o roteamento de 13.664 alunos da zona rural do estado do Rio de Janeiro. Para isso, considerouse o problema de roteamento de veículo escolares, do inglês School Bus Routing Problem (SBRP), com frota heterogênea e escola única, com o objetivo de minimizar o custo total considerando as restrições de capacidade dos veículos e distância máxima de percurso. Para aplicação do método, foram considerados os dados fornecidos pela Secretaria de Estado de Educação do Rio de Janeiro (SEEDUC-RJ). Os resultados são apresentados em dois cenários, o primeiro considera os dados de 79 rotas utilizadas pela SEEDUC-RJ para comparação dos resultados obtidos com o ILS. O método mostrou uma redução de 40,5 por cento no custo médio das rotas e 46 or cento na quilometragem média por aluno. O segundo cenário considera o roteamento da totalidade dos alunos, que foram divididos em 506 instâncias considerando escola e turno. A maior instância roteada possui 534 alunos. Os resultados consolidados por município são apresentados e mostram a concentração de municípios com maior custo médio por rota no noroeste fluminense. A implementação das rotas propostas pode trazer economia significativa com as despesas relacionadas ao transporte escolar rural, além de indicar um aumento no nível de serviço para os estudantes, com redução da quilometragem média por aluno. / [en] School transport is essential to ensure access and permanence of students in public schools, especially in rural areas, where students are located in a large area with low density and roads are in precarious conditions. This work aims to apply the Iterated Local Search metaheuristic to route 13.664 rural students in the state of Rio de Janeiro. For this, we considered the School Bus Routing Problem (SBRP), with heterogeneous fleet and single school, in order to minimize the total cost considering the vehicles capacity constraints and maximum travel distance. To apply the method, the data provided by Secretaria de Estado de Educação do Rio de Janeiro (SEEDUCRJ) were considered. The results are presented in two scenarios, the first considers data from 79 routes used by SEEDUC-RJ to compare the results obtained with the ILS. The method showed a reduction of 40.5 percent in the average cost of routes and 46 percent in the average mileage per student. The second scenario considers the routing of all students, who were divided into 506 instances considering school and shift. The largest routed instance has 534 students. The results consolidated by municipality are presented and show the concentration of municipalities with the highest average cost per route in northwestern Rio de Janeiro. The implementation of the proposed routes can bring significant savings with expenses related to rural school transport, in addition to indicating an increase in the level of service for students, with a reduction in the average mileage per student.

The term quantization refers to the process of estimating a given probability by a discrete probability supported on a finite set. The quantization dimension Dr of a probability is related to the asymptotic rate at which the expected distance (raised to the rth power) to the support of the quantized version of the probability goes to zero as the size of the support is allowed to go to infinity. This assumes that the quantized versions are in some sense ``optimal'' in that the expected distances have been minimized. In this dissertation we give a short history of quantization as well as some basic facts. We develop a generalized framework for the quantization dimension which extends the current theory to include a wider range of probability measures. This framework uses the theory of thermodynamic formalism and the multifractal spectrum. It is shown that at least in certain cases the quantization dimension function D(r)=Dr is a transform of the temperature function b(q), which is already known to be the Legendre transform of the multifractal spectrum f(a). Hence, these ideas are all closely related and it would be expected that progress in one area could lead to new results in another. It would also be expected that the results in this dissertation would extend to all probabilities for which a quantization dimension function exists. The cases considered here include probabilities generated by conformal iterated function systems (and include self-similar probabilities) and also probabilities generated by graph directed systems, which further generalize the idea of an iterated function system.

O contínuo Tempo Randon Walk desenvolvido por Scher e Montroll é generalizado a fim de incluir as transições de taxas de espaço e o tempo. Tomando o limite contínuo, no passeio de equações aleatórias, uma equação geral de uma carga espacial transportada é obtida. A equivalência entre hopping e transporte através de estados expandidos com armadilhas é mostrado para realizar no espaço uma carga caso. Uma análise dos transportes um processo com dois processos simultâneos condução, por um armadilhagem e alargado a outros estados e por hopping através de armadilhas, é realizada. O Método Substituição Funcional (EFM) é introduzida a fim de obter resultados semi-markofian de Markofian soluções. Soluções específicas são obtidas em campo caso o alto e aproximadas queridos no espaço cobrar caso. Uma aproximação analítica de solução para o potencial superficial de decadência de uma sólida com armadilhas cobrado pela Corona é dada pela utilização do FSM. / The continuous Time Randon Walk developed by Scher and Montroll is generalized in order t o include space and time transitions rates. Taking the continuum limit in the random walk equations a general equation for space charge transport is obtained. The equivalence between hopping and transport via extended states with traps is shown to hold in the space charge case. An analysis of a transport process with two simultaneous conduction process, one by trapping and extended states and the other by hopping via traps, is carried out. The Functional Substitution Method (FSM) is introduced in order to get semi-markofian results from Markofian solutions. Specific exact solutions are obtained in the high field case and approximated ones in the space charge case. An approximated analytical solution for the superficial potential decay of a solid with traps charged by Corona is given by use of FSM.

Escalonamento de processos é um tipo de problema de otimização combinatória no qual devemos alocar máquinas à tarefas por períodos específicos de tempo. A literatura contém diversos estudos propondo técnicas para resolver modelos de escalonamento de processos como o job shop e o open shop. Esses modelos permitem que os passos no processo produtivo sejam ou completamente ordenados ou sem ordenação alguma. Com o aumento da complexidade das aplicações industriais no encontramos, mais recentemente, diversos trabalhos que propõe problemas de escalonamento de processos mais gerais para modelar mais precisamente os processos produtivos. O mixed shop, group shop e partial shop são exemplos de tais modelos. Nesse trabalho nós propomos uma busca tabu iterada para o partial shop, que é um modelo geral que inclui diversos modelos mais restritivos. Os componentes novos mais importantes da técnica são o gerador de solução inicial, a vizinhança e o limite inferior para a vizinhança. Em experimentos computacionais nós conseguimos demonstrar que a heurística genérica e única é capaz de competir, e as vezes superar, as técnicas de estado de arte desenvolvidas especificamente para partial, open, mixed e group shop. Algumas vezes uma máquina é o gargalo de um processo produtivo, e é replicada. Na literatura o caso das máquinas paralelas foi incluído em diversas extensões de problemas de escalonamento de processos. Nessa tese nós também propomos uma técnica para escalonar as máquinas paralelas, sem incluí-las explicitamente na representação do problema. Nós usamos técnicas gerais para os casos sem máquinas paralelas para produzir uma busca heurística tabu rápida, e estado da arte, para o caso do job shop com máquinas paralelas. / Shop scheduling is a combinatorial optimization type of problem in which we must allocate machines to jobs for specific periods time. A set of constraints defines which schedules are valid, and we must select one that minimizes or maximizes an objective function. In this work we use the makespan, which is the time the last job finishes. The literature contains several studies proposing techniques to solve shop problems such as the job shop and open shop. These problems allow the steps of the production processes to be either fully ordered or not ordered at all. With increasing complexity and size of industrial applications we find, more recently, several works which propose more general shop problems to model the production processes more accurately. The mixed shop, group shop and partial shop are examples of such problems In this work we propose an iterated tabu search for the partial shop, which is a general problem and includes several other more restrictive shop problems. The most important novel components of the solver are the initial solution generator, the neighbourhood, and the lower bound for the neighbourhood. In computational experiments we were able to show that the general partial shop solver is able to compete with, and sometimes surpass, the state-of-the-art solvers developed specifically for the partial, open, mixed and group shops. Sometimes a machine is a bottleneck in the production process, and is replicated. In the literature the parallel machines case has being included in several extensions of shop problems. In this thesis we also propose a technique to schedule the parallel machines heuristically, without including them explicitly in the representation of the problem. We use general techniques for the non-parallel machine cases to produce a fast tabu search heuristic results for the job shop with parallel machines.

This thesis addresses a major problem facing any attempt to account for language structure through a cultural mechanism: The processes required by such a mechanism are only possible if we assume the existence of a range of preconditions. These preconditions are not trivial, and themselves require an explanation. In this thesis I address the nature and origin of these preconditions. I approach this topic in three stages. In the first stage, I pull-apart the functioning of one prominent cultural account of language evolution—the Iterated Learning Model —to identify the preconditions it assumes. These preconditions cluster into two main groups. The first concerns the traditional transmission of the communication system. The second relates to the emergence of particular skills of social cognition that make learned symbols and language-like communication a possibility. In the second stage, I turn to comparative evidence, looking for evolutionary analogies that might shed light on the emergence of these preconditions. Two case studies—the Bengalese finch and the domestic dog—are considered in detail, both of which show aspects of one of the preconditions emerging in the context of domestication. In each case I examine what it is about the domestication process that led to this outcome. In the final stage, I consider whether this same context might explain the emergence of these preconditions in humans. The claim that humans are a self-domesticated species has a long history, and is increasingly invoked in contemporary discussions of language evolution. However, it is often unclear exactly what this claim entails. I present a synthesis and critique of a range of empirical and theoretical perspectives on self-domestication. I conclude that human self-domestication is a coherent concept, and that there are several plausible accounts of how it might have occurred. The realisation that humans are a self-domesticated species can, therefore, provide some insight into how a cultural account of language structure might be possible at all.

Languages are culturally transmitted through a repeated cycle of learning and communicative interaction. These two aspects of cultural transmission impose (at least) three interacting pressures that can shape the evolution of linguistic structure: a pressure for learnability, a pressure for expressivity, and a pressure for coordination amongst users in a linguistic community. This thesis considers how these sometimes competing pressures impact linguistic complexity across cultural time. Using artificial language and iterated learning experimental paradigms, I investigate the conditions under which complexity in morphological and syntactic systems emerges, spreads, and reduces. These experiments illustrate the interaction of transmission, learning and use in hitherto understudied domains - morphosyntax and word order. In a first study (Chapter 2), I report the first iterated learning experiments to investigate the evolution of complexity in compositional structure at the word and sentence level. I demonstrate that a complex meaning space paired with pressures for learnability and communication can result in compositional hierarchical constituent structure, including fixed combinatorial rules of word formation and word order. This structure grants a productive and productively interpretable language and only requires learners to acquire a finite lexicon and a finite set of combinatorial rules (i.e., a grammar). In Chapter 3, I address the unique effect of communicative interaction on linguistic complexity, by removing language learning completely. Speakers use their native language to express novel meanings either in isolation or during communicative interaction. I demonstrate that even in this case, communicative interaction leads to more efficient and overall simpler linguistic systems. These first two studies provide support for the claim that morphological and syntactic complexity are shaped by an overarching drive towards simplicity (or learnability) in language learning and communication. Chapter 4 reports a series of experiments assessing the possibility that the simplicity bias found in the first two studies operates at a different strength depending on the linguistic level. Studies in natural language learning and in pidgin/creole genesis suggest that while morphological variation seems to be highly susceptible to regularisation, variation in other syntactic features, like word order, appears more likely to be reproduced. I test this experimentally by comparing regularisation of unconditioned variation across morphology and word order in the context of artificial language learning. I show that language users in fact regularise unconditioned variation in a similar way across linguistic levels, suggesting that the simplicity bias may be driven by a single, non-level-specific mechanism. Taken together, the experimental evidence presented in this thesis supports the hypothesis that the cultural and cognitive pressures acting on language users during learning and communicative interaction - for learnability, expressivity and coordination - are at least partially responsible for the evolution of linguistic complexity. Specifically, they are responsible for the emergence of linguistic complexity which maximises learnability and communicative efficiency, and for the reduction of complexity which does not. More generally, the approach taken in this thesis promotes a view of complexity in linguistic systems as an evolving variable determined by the biases of language learners and users as languages are culturally transmitted.

D'abord, on étudie trois façons d'associer une C*-algèbre à une transformation continue. Ensuite, nousdonnons une nouvelle définition de l'entropie. Nous trouvons des relations entre les états KMS des algèbrespréalablement définies et les états d'équilibre, donné par un principe variationnel. Dans la seconde partie,nous étudions les algèbres de Kajiwara-Watatani associées à un système des fonctions itérées. Nouscomparons ces algèbres avec l'algèbre de Cuntz et le produit croisé. Enfin, nous étudions les états KMS desalgèbres de Kajiwara-Watatani pour les actions provenant d'un potentiel et nous trouvouns des relationsentre ces états et les mesures trouvée dans une version de le théorème de Ruelle-Perron-Frobenius pour lessystèmes de fonctions itérées. / First, we study three ways of associating a C*-algebra to a continuous map. Then, we give a new definitionof entropy. We relate the KMS states of the previously defined algebras with the equilibrium states, givenby a variational principle. In the second part, we study the Kajiwara-Watatani algebras associated toiterated function system. We compare these algebras with the Cuntz algebra and the crossed product.Finally, we study the KMS states of the Kajiwara-Watatani algebras for actions coming from a potentialand we relate such states with measures found in a version of the Ruelle-Perron-Frobenius theorem foriterated function systems.

Probabilistic models of text are a useful tool for enabling the analysis of large collections of digital text. For example, Latent Dirichlet Allocation can quickly produce topical summaries of large collections of text documents. Many important uses cases of such models include human interaction during the inference process for these models of text. For example, the Interactive Topic Model extends Latent Dirichlet Allocation to incorporate human expertiese during inference in order to produce topics which are better suited to individual user needs. However, interactive use cases of probabalistic models of text introduce new constraints on inference - the inference procedure must not only be accurate, but also fast enough to facilitate human interaction. If the inference is too slow, then the human interaction will be harmed, and the interactive aspect of the probalistic model will be less useful. Unfortunately, the most popular inference algorithms in use today either require strong approximations which can degrade the quality of some models, or require time-consuming sampling. We explore the use of Iterated Conditional Modes, an algorithm which is able to obtain locally optimal maximum a posteriori estimates, as an alternative to popular inference algorithms such as Gibbs sampling or mean field variational inference. Iterated Conditional Modes algorithm is not only fast enough to facilitate human interaction, but can produce better maximum a posteriori estimates than sampling. We demonstrate the superior performance of Iterated Conditional Modes on a wide variety of models. First we use a DP Mixture of Multinomials model applied to the problem of web search result cluster, and show that not only can we outperform previous methods in clustering quality, but we can achieve interactive runtimes when performing inference with Iterated Conditional Modes. We then apply Iterated Conditional Modes to the Interactive Topic Model. Not only is Iterated Conditional Modes much faster than the previous published Gibbs sampler, but we are better able to incorporate human feedback during inference, as measured by accuracy on a classification task using the resultant topic model. Finally, we utilize Iterated Conditional Modes with MomResp, a model used to aggregate multiple noisy crowdsourced data. Compared with Gibbs sampling, Iterated Conditional Modes is better able to recover ground truth labels from simulated noisy annotations, and runs orders of magnitude faster.