Metodologia estatística na solução do problema do caixeiro viajante e na avaliação de algoritmos : um estudo aplicado à transgenética computacional

The problems of combinatory optimization have involved a large number of researchers in search of approximative solutions for them, since it is generally accepted that they are unsolvable in polynomial time. Initially, these solutions were focused on heuristics. Currently, metaheuristics are used more for this task, especially those based on evolutionary algorithms. The two main contributions of this work are: the creation of what is called an -Operon- heuristic, for the construction of the information chains necessary for the implementation of transgenetic (evolutionary) algorithms, mainly using statistical methodology - the Cluster Analysis and the Principal Component Analysis; and the utilization of statistical analyses that are adequate for the evaluation of the performance of the algorithms that are developed to solve these problems. The aim of the Operon is to construct good quality dynamic information chains to promote an -intelligent- search in the space of solutions. The Traveling Salesman Problem (TSP) is intended for applications based on a transgenetic algorithmic known as ProtoG. A strategy is also proposed for the renovation of part of the chromosome population indicated by adopting a minimum limit in the coefficient of variation of the adequation function of the individuals, with calculations based on the population. Statistical methodology is used for the evaluation of the performance of four algorithms, as follows: the proposed ProtoG, two memetic algorithms and a Simulated Annealing algorithm. Three performance analyses of these algorithms are proposed. The first is accomplished through the Logistic Regression, based on the probability of finding an optimal solution for a TSP instance by the algorithm being tested. The second is accomplished through Survival Analysis, based on a probability of the time observed for its execution until an optimal solution is achieved. The third is accomplished by means of a non-parametric Analysis of Variance, considering the Percent Error of the Solution (PES) obtained by the percentage in which the solution found exceeds the best solution available in the literature. Six experiments have been conducted applied to sixty-one instances of Euclidean TSP with sizes of up to 1,655 cities. The first two experiments deal with the adjustments of four parameters used in the ProtoG algorithm in an attempt to improve its performance. The last four have been undertaken to evaluate the performance of the ProtoG in comparison to the three algorithms adopted. For these sixty-one instances, it has been concluded on the grounds of statistical tests that there is evidence that the ProtoG performs better than these three algorithms in fifty instances. In addition, for the thirty-six instances considered in the last three trials in which the performance of the algorithms was evaluated through PES, it was observed that the PES average obtained with the ProtoG was less than 1% in almost half of these instances, having reached the greatest average for one instance of 1,173 cities, with an PES average equal to 3.52%. Therefore, the ProtoG can be considered a competitive algorithm for solving the TSP, since it is not rare in the literature find PESs averages greater than 10% to be reported for instances of this size.

O problema do caixeiro viajante alugador : um estudo algorítmico

The Car Rental Salesman Problem (CaRS) is a variant of the classical Traveling Salesman Problem which was not described in the literature where a tour of visits can be decomposed into contiguous paths that may be performed in different rental cars. The aim is to determine the Hamiltonian cycle that results in a final minimum cost, considering the cost of the route added to the cost of an expected penalty paid for each exchange of vehicles on the route. This penalty is due to the return of the car dropped to the base. This paper introduces the general problem and illustrates some examples, also featuring some of its associated variants. An overview of the complexity of this combinatorial problem is also outlined, to justify their classification in the NPhard class. A database of instances for the problem is presented, describing the methodology of its constitution. The presented problem is also the subject of a study based on experimental algorithmic implementation of six metaheuristic solutions, representing adaptations of the best of state-of-the-art heuristic programming. New neighborhoods, construction procedures, search operators, evolutionary agents, cooperation by multi-pheromone are created for this problem. Furtermore, computational experiments and comparative performance tests are conducted on a sample of 60 instances of the created database, aiming to offer a algorithm with an efficient solution for this problem. These results will illustrate the best performance reached by the transgenetic algorithm in all instances of the dataset

Algoritomos transgenéticos aplicados ao problema da árvore geradora biobjetivo

The Multiobjective Spanning Tree is a NP-hard Combinatorial Optimization problem whose application arises in several areas, especially networks design. In this work, we propose a solution to the biobjective version of the problem through a Transgenetic Algorithm named ATIS-NP. The Computational Transgenetic is a metaheuristic technique from Evolutionary Computation whose inspiration relies in the conception of cooperation (and not competition) as the factor of main influence to evolution. The algorithm outlined is the evolution of a work that has already yielded two other transgenetic algorithms. In this sense, the algorithms previously developed are also presented. This research also comprises an experimental analysis with the aim of obtaining information related to the performance of ATIS-NP when compared to other approaches. Thus, ATIS-NP is compared to the algorithms previously implemented and to other transgenetic already presented for the problem under consideration. The computational experiments also address the comparison to two recent approaches from literature that present good results, a GRASP and a genetic algorithms. The efficiency of the method described is evaluated with basis in metrics of solution quality and computational time spent. Considering the problem is within the context of Multiobjective Optimization, quality indicators are adopted to infer the criteria of solution quality. Statistical tests evaluate the significance of results obtained from computational experiments

Otimização em braquiterapia de alta taxa de dose com algoritmo transgenético

Este trabalho aborda o problema de otimização em braquiterapia de alta taxa de dose no tratamento de pacientes com câncer, com vistas à definição do conjunto de tempos de parada. A técnica de solução adotada foi a Transgenética Computacional apoiada pelo método L-BFGS. O algoritmo desenvolvido foi empregado para gerar soluções não denominadas cujas distribuições de dose fossem capazes de eiminar o câncer e ao mesmo tempo preservar as regiões normais

O problema do caixeiro alugador com coleta de bonus: um estudo algoritmico

This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-two instances. The proposed problem is also subject of an experimental study based on the algorithmic application of four metaheuristics representing the best adaptations of the state of the art of the heuristic programming.We also provide new local search operators which exploit the neighborhoods of the problem, construction procedures and adjustments, created specifically for the addressed problem. Comparative computational experiments and performance tests are performed on a sample of 80 instances, aiming to offer a competitive algorithm to the problem. We conclude that memetic algorithms, computational transgenetic and a hybrid evolutive algorithm are competitive in tests performed

Sistematização do dimensionamento técnico e econômico de sistemas fotovoltaicos isolados por meio de programa computacional

One of the main referring subjects to the solar energy is how to compare it economically with other sources of energy, as much alternatives as with conventionals (like the electric grid). The purpose of this work was to develop a software which congregates the technical and economic main data to identify, through methods of microeconomic analysis, the commercial viability in the sizing of photovoltaic systems, besides considering the benefits proceeding from the proper energy generation. Considering the period of useful life of the components of the generation system of photovoltaic electricity, the costs of the energy proceeding from the conventional grid had been identified. For the comparison of the conventional sources, electric grid and diesel generation, three scenes of costs of photovoltaic panels and two for the factor of availability of diesel generation had been used. The results have shown that if the cost of the panels is low and the place of installation is more distant of the electric grid, the photovoltaic system becomes the best option.

Uma perspectiva computacional sobre catálise enzimática

Enzymes are extremely efficient catalysts. Here, part of the mechanisms proposed to explain this catalytic power will be compared to quantitative experimental results and computer simulations. Influence of the enzymatic environment over species along the reaction coordinate will be analysed. Concepts of transition state stabilisation and reactant destabilisation will be confronted. Divided site model and near-attack conformation hypotheses will also be discussed. Molecular interactions such as covalent catalysis, general acid-base catalysis, electrostatics, entropic effects, steric hindrance, quantum and dynamical effects will also be analysed as sources of catalysis. Reaction mechanisms, in particular that catalysed by protein tyrosine phosphatases, illustrate the concepts.

Propriedades dinâmicas de fluidos por simulação computacional: métodos híbridos atomístico-contínuo

Computational methods for the calculation of dynamical properties of fluids might consider the system as a continuum or as an assembly of molecules. Molecular dynamics (MD) simulation includes molecular resolution, whereas computational fluid dynamics (CFD) considers the fluid as a continuum. This work provides a review of hybrid methods MD/CFD recently proposed in the literature. Theoretical foundations, basic approaches of computational methods, and dynamical properties typically calculated by MD and CFD are first presented in order to appreciate the similarities and differences between these two methods. Then, methods for coupling MD and CFD, and applications of hybrid simulations MD/CFD, are presented.

A investigação da construção de modelos no estudo de um tópico de física utilizando um ambiente de modelagem computacional qualitativo

A integração de tecnologias de informação e comunicação no contexto educacional tem sido tema de diversos congressos e simpósios ao redor do mundo e no Brasil. Neste sentido, vários estudos têm sido realizados com o objetivo de se obter metodologias que tornem efetivo o emprego das novas tecnologias no ensino. Este artigo mostra um estudo que investigou a interação entre estudantes universitários da área de ciências exatas e um ambiente de modelagem computacional qualitativo em atividades de modelagem expressiva. Os resultados obtidos mostram que os estudantes foram capazes de criar e modificar o modelo do sistema proposto a partir de suas próprias concepções.

A utilização da modelagem computacional semiquantitativa no estudo do sistema mola-massa

O artigo apresenta resultados da investigação sobre a integração de ambientes de modelagem computacional ao aprendizado exploratório de Física. Os resultados aqui apresentados são relativos ao estudo da interação e desempenho de alunos de ensino superior durante a utilização do ambiente de modelagem computacional semiquantitativo WLinkIt em uma atividade de conteúdo específico em Física: o sistema mola-massa. Os resultados mostram que os estudantes apresentaram habilidades para desenvolver um modelo sobre a situação proposta e relacionar o comportamento apresentado pelo modelo com o esperado por eles, alterar o modelo e explicar o comportamento apresentado pelas variáveis. Os resultados mostram também que as dificuldades apresentadas foram relacionadas à delimitação do sistema a ser estudado, ao entendimento da influência de uma variável sobre a outra, ao entendimento de quem é o agente causal do sistema, ao entendimento da função de uma ligação entre duas variáveis e ao entendimento dos conceitos envolvidos. Assim, o mapeamento desses aspectos é fundamental para o delineamento de pesquisas futuras no sentido de promover, na prática, a integração de Ambientes de Modelagem Computacional Semiquantitativos na sala de aula, mais especificamente para o estudo de tópicos de Física.

Metodologia para obtenção do hidrograma de escoamento superficial em encostas e canais. Parte II: modelo computacional e análise de sensibilidade

Estimativas de vazão máxima de escoamento superficial são necessárias para o projeto de obras hidráulicas em bacias urbanas e rurais. A dificuldade em aplicar os procedimentos disponíveis para calcular a variação do escoamento superficial com o tempo e de seu valor máximo deve-se à inexatidão dos métodos usados para esse objetivo e à variabilidade nos resultados que podem ser obtidos por profissionais que usem o mesmo procedimento. Dessa forma, a investigação de um método que produza estimativas confiáveis da vazão máxima e do hidrograma de escoamento superficial é de grande interesse. Neste trabalho, desenvolveu-se e avaliou-se a sensibilidade de um software (HIDROGRAMA 2.1) que permite a obtenção do hidrograma de escoamento superficial, da vazão máxima e seu tempo de ocorrência, da altura e da velocidade máximas do escoamento, do volume e da lâmina de escoamento superficial em encosta e em canais. O modelo apresentou grande sensibilidade ao período de retorno, à taxa de infiltração estável e ao comprimento da encosta e do canal.

Proposta de um algoritmo GPC adaptativo com baixo custo computacional

Esta dissertação propõe um algoritmo do Controlador Preditivo Generalizado (GPC) com horizonte de controle igual a um para ser aplicado em plantas industriais com modelos variantes no tempo, simples o su ficiente para ser implementado em Controlador Lógico Programável (PLC). A solução explícita do controlador é obtida em função dos parâmetros do modelo e dos parâmetros de sintonia do GPC (horizonte nal de predição hp e o fator de supressão do sinal de controle ), além das entradas e saídas presentes e passadas. A sintonia do fator de supressão e do horizonte de previsão GPC é feita através do lugar das raízes da equação característica do sistema em malha fechada, sempre que os parâmetros do modelo da planta industrial (estável ou instável em malha aberta) forem modificados.

Tecnologia assistiva e computacional : contribuições para o atendimento educacional especializado e desafios na formação de professores

Neste trabalho, analisamos aspectos relacionados a como a tecnologia computacional é utilizada no Atendimento Educacional Especializado (AEE) e como se deu a formação de professores para utilizar esses recursos. Para tanto, delimitamos os seguintes objetivos específicos: investigar a utilização da tecnologia assistiva (TA) computacional no âmbito das salas de recursos multifuncionais (SRM); problematizar as tensões, dificuldades e possibilidades relacionadas à TA com ênfase na tecnologia computacional para o AEE; analisar a formação do professor de educação especial para o AEE tendo como recurso a TA com ênfase na tecnologia computacional, visando à mediação dos processos de aprendizagem. O aporte teórico deste trabalho foi a abordagem histórico-cultural, tomando por referência os estudos de Vigotski e seus colaboradores. Trata-se de uma pesquisa qualitativa que fez uso de diferentes instrumentos metodológicos como, os grupos focais, o questionário online e a entrevista semiestruturada. Para desenvolvê-lo, realizamos a coleta de dados em diferentes contextos, começando pelos grupos focais da pesquisa inaugural do Oneesp, que serviram como dispositivo para esta pesquisa, seguida da aplicação de um questionário aos professores participantes da pesquisa-formação desenvolvida como um desdobramento no estado do Espírito Santo da pesquisa inaugural do Oneesp pelos integrantes do Oeeesp e da aplicação in loco de entrevistas semiestruturadas com professores de educação especial, de uma SRM do Tipo II. Foram oitenta e nove professores participantes na pesquisa do Oneesp, trinta professores na pesquisa-formação do Oeeesp e dois professores para aplicação da entrevista semiestruturada in loco, respectivamente. Esses dois professores participaram tanto da pesquisa do Oneesp como da pesquisa do Oeeesp. Analisamos esses três momentos, dos quais emergiram os apontamentos que nos proporcionaram pensar, com base nas narrativas orais e escritas dos professores: sua formação para uso da TA computacional; seu entendimento sobre sua formação para este fim; seus anseios por uma formação mais direcionada; a forma como utilizam a tecnologia na sala de recursos; seus entendimentos sobre as dificuldades e possibilidades relacionadas a TA com ênfase na tecnologia computacional para o AEE. Após essas análises, concluímos que poucos professores que atuam nas SRM tiveram uma formação que possibilitasse a aplicação das tecnologias computacionais em sua mediação pedagógica, aliando teoria e prática, com momentos de formação que privilegiassem os momentos presenciais e em laboratórios, onde possam interagir com os computadores e suas ferramentas simbólicas. Sem essa familiaridade com os recursos computacionais, os professores acabam sentindo-se inseguros para utilizá-los, deixando de potencializar, pela via desses recursos, os processos de ensinoaprendizagem do aluno com deficiência. Faz-se necessário um investimento nesse tipo de formação e, mais do que isso, que se viabilize para os professores que atuam ou que pretendem atuar nas SRM. A partir de uma formação apropriada é possível fazer com que os professores utilizem os recursos computacionais como mediadores dos processos de ensino-aprendizagem de seus alunos.

Programa computacional para calcular a potência requerida de máquinas e implementos agrícolas

O uso de programas computacionais no setor agrícola permite atingir objetivos específicos na área. Dentre esses, um dos mais complexos é a seleção adequada de máquinas e implementos agrícolas visando à otimização de operações agrícolas, devido, principalmente, à grande variedade de equipamentos existentes no mercado e a gama de tarefas e situações de trabalho que estas são submetidas no campo. O objetivo deste trabalho foi desenvolver um programa computacional para calcular a potência requerida de máquinas e implementos agrícolas normalmente utilizados na condução de operações de campo, desde o preparo do solo até as operações de implantação de culturas. Desenvolvido em linguagem PHP, o programa computacional baseia-se na norma ASAE D497.4 - Agricultural Machinery Management Data como referência para desenvolvimento de cálculos. A partir do programa desenvolvido, tornou-se possível a execução de tarefas para cálculos de avaliação da demanda de potência de máquinas e implementos agrícolas de forma simplificada pela internet.

Sistema computacional para índices de cárie dentária: banco de dados e análise estatística

Apresenta-se um sistema computacional, denominado ICADPLUS, desenvolvido para elaboração de banco de dados, tabulação de dados, cálculo do índice CPO e análise estatística para estimação de intervalos de confiança e comparação de resultados de duas populações.Tem como objetivo apresentar método simplificado para atender necessidades de serviços de saúde na área de odontologia processando fichas utilizadas por cirurgiões dentistas em levantamentos epidemiológicos de cárie dentária. A característica principal do sistema é a dispensa de profissional especializado na área de odontologia e computação, exigindo o conhecimento mínimo de digitação por parte do usuário, pois apresenta "menus" simples e claros como também relatórios padronizados, sem possibilidade de erro. Possui opções para fichas de CPO segundo Klein e Palmer, CPO proposto pela OMS, CPOS segundo Klein, Palmer e Knutson, e ceo. A validação do sistema foi feita por comparação com outros métodos, permitindo recomendar sua adoção.