Neste projeto estudamos algoritmos de aproximação para o problema da árvore de Steiner com coleta de prêmios. Trata-se de uma generalização do problema da árvore de Steiner, onde é dado um grafo com custos positivos nas arestas e penalidades positivas nos vértices. O objetivo é encontrar uma subárvore do grafo que minimize a soma dos custos das arestas mais a soma das penalidades dos vértices que não pertencem à subárvore. Em 2009, os autores Archer, Bateni, Hajiaghayi e Karloff obtiveram pela primeira vez um algoritmo com fator de aproximação estritamente menor do que 2. Além de analisarmos este algoritmo, estudamos também a implementação de algoritmos 2-aproximação para o problema da árvore de Steiner e da árvore de Steiner com coleta de prêmios. / In this project we analyze approximation algorithms for the prize-collecting Steiner tree problem. This is a generalization of the Steiner tree problem, in which it is given a graph with positive costs in edges and positive penalties in vertices. The goal is to find a subtree of the graph that minimizes the sum of costs of edges plus the sum of the penalties of the vertices that don\'t belong to the subtree. In 2009, the authors Archer, Bateni, Hajiaghayi e Karloff described, for the first time an algorithm with approximation factor strictly less than 2. Besides analyzing this algorithm, we also study the implementation of 2-approximation algorithms to the Steiner tree problem and prize-collecting Steiner tree problem.

[pt] Esta dissertação apresenta o desenvolvimento e os resultados deste projeto de mestrado, cujo objetivo, de caráter multidisciplinar, foi desenvolver uma metodologia e uma ferramenta para segmentação do fígado, seus vasos e subregiões a partir de imagens de tomografia computadorizada da região abdominal, utilizando procedimentos de segmentação automática de imagens e visualização tridimensional de dados. A metodologia sugerida segmenta primeiramente o fígado, utilizando uma abordagem de modelos deformáveis implícitos, chamada level sets, estimando os seus parâmetros através do uso de algoritmos genéticos. Inicialmente, o contorno do fígado é manualmente definido em um tomo como solução inicial, e então o método segmenta automaticamente o fígado em todos os outros tomos, sequencialmente. Os vasos e nódulos do fígado são então identificados utilizando um modelo de mistura de funções proporcionais a gaussianas, e um método de segmentação de crescimento de regiões por histerese. As veias hepáticas e portas são classificadas dentro do conjunto de vasos, e utilizadas em uma modelagem matemática que finalmente divide o fígado em oito sub-regiões de Couinaud. Esta metodologia foi testada em 20 diferentes exames e utilizando cinco diferentes medidas de performance, e os resultados obtidos confirmam o potencial do método. Casos com baixo desempenho são apresentados para promover desenvolvimentos futuros. / [en] This dissertation presents the development and results of this M.Sc project, whose multidisciplinary objective, was to develop a methodology and a tool to segment the liver, its vessels and subregions from abdominal computed tomography images, using procedures of automatic image segmentation and visualization of three-dimensional data. The suggested methodology segments initially the liver, using an approach based on implicit deformable models, called level sets, estimating its parameters using genetic algorithms. Initially, the liver boundary is manually set in one slice an initial solution, and then the method automatically segments the liver in all other slices, sequentially. Then the vessels and nodules of the liver are identified using both a model of mixture of functions proportional to Gaussians, and a segmentation method called region growing that uses hysteresis information. The hepatic and portal veins are classified within the set of vessels, and used in a mathematical modeling that eventually divides the liver into the eight subregions of Couinaud. The methodology was tested to segment the liver using 20 different exams and five different measures of performance, and the results obtained confirm the potential of the method. The cases in which the method presented a poor performance are also discussed in order to instigate further research.

Estudamos um sistema de dois níveis acoplados como um modelo que imita o comportamento de líquidos super-resfriados. Em equilíbrio o modelo apresenta uma fase líquida e uma fase cristalina com diversos estados fundamentais. O modelo é definido numa rede quadrada e a cada sítio é associada uma variável estocástica de Ising. A característica que torna este modelo particularmente interessante é que ele apresenta estados metaestáveis duráveis que podem desaparecer dentro do tempo acessível para as simulações numéricas. Para imitar o processo de formação dos vidros, realizamos simulações de Monte Carlo a taxas de resfriamento constante. Apresentamos também simulações para resfriamentos súbitos a temperatura abaixo da temperatura de fusão. / We study a coupled two level systems as a model that imitate the behavior of supercooled liquids that become structural glasses under cooling. In the equilibrium the model shows a liquid phase and a crystalline phase with many grouond states. The model is defined on a square lattice and to each site a stochastic Ising variable is associated. The feature that makes this model particularly interesting is that it display durable metastables states which can vanish within the time available for numerical simulations. In order to imitate the glass former process, we perform Monte Carlo simulations at constant cooling rate. We present also simulations for quenchs to temperatures below the melting temperature.

Orientador: Liciana Vaz de Arruda Silveira / Resumo: Os objetivos deste trabalho foram apresentar modelos de classificação (Regressão Logística, Naive Bayes, Árvores de Classificação, Random Forest, k-Vizinhos mais próximos e Redes Neurais Artificiais) e a comparação destes utilizando processos de reamostragem em um conjunto de dados da área de geriatria (diagnóstico de demência). Analisar as pressuposições de cada metodologia, vantagens, desvantagens e cenários em que cada metodologia pode ser melhor utilizada. A justificativa e relevância desse projeto se baseiam na importância e na utilidade do tema proposto, visto que a população idosa aumenta em todo o mundo (nos países desenvolvidos e nos em desenvolvimento como o Brasil), os modelos de classificação podem ser úteis aos profissionais médicos, em especial aos médicos generalistas, no diagnóstico de demências, pois em diversos momentos o diagnóstico não é simples. / Doutor

La congestión vehicular en Lima es caótica dada la escaza infraestructura vial y el acelerado aumento del parque automotor. En contraste, esta investigación propone implementar el sistema de semaforización inteligente, Ramp Meter, basado en el algoritmo AMS-AG, para reducir los tiempos de viaje vehicular en el óvalo Habich, ubicado en el distrito de San Martín de Porres. La metodología propuesta consta en la recolección de datos estáticos y registro de una lista de verificaciones. Luego se procede con la toma de datos de entrada para construir el modelo, tales como; flujos, velocidades y tiempos de viaje. El primer paquete de datos es utilizado para la construcción y calibración del modelo en el software de microsimulación PTV Vissim 9.0, y el segundo para la validación del modelo. De acuerdo con los resultados de los parámetros de performance vehicular (demora, tiempo de viaje y velocidad) y peatonal (tiempo de viaje, velocidad) de la situación actual y lista de verificaciones, se realiza la propuesta de solución. Del mismo modo, a una proyección a 15 años se estima su funcionalidad en el mediano plazo. Se concluye que la propuesta de mejora a través de la implementación del Ramp Meter, basado en el algoritmo AMS-AG, ofrece mejoras en relación con el performance vehicular, sin embargo, pierde rendimiento a medida que incrementa el flujo vehicular. Cumple con el objetivo principal de la investigación de reducirse los tiempos de viaje vehicular. Por último, se afirma que la inversión económica que demanda es una alternativa viable y rentable. / Vehicle congestion in Lima is chaotic given the lack of road infrastructure and the rapid increase in the number of vehicles. In contrast, this research proposes to implement the intelligent traffic light system, Ramp Meter, based on the AMS-AG algorithm, to reduce vehicle travel times at the Habich roundabout, in San Martin de Porres district. The proposed methodology consists of the collection of static data and registering a checklist. Then, we proceed with taking input data to build the model, such as flows, speed and travels times. The first data packet is used for the construction and calibration of the model in the PTV Vissim 9.0 microsimulation software, and the second one is used for model validation. According to the results of the parameters of vehicular performance (delay, travel time and speed) and pedestrian (travel time and speed) of the current situation and checklist, the proposed solution for roundabout is made. Similarly, at a projection to 15 years its functionality is estimated in the medium term. It is concluded that the improvement proposal through the implementation of the Ramp Meter, based on the AMS-AG algorithm, offers improvements in relation to vehicle performance, however, it loses performance as vehicle flow increases. It fulfills the main objective of the research to reduce vehicle travel times. Finally, it is stated that economic investment that it demands is viable and profitable alternative. / Tesis

[pt] Esta dissertação apresenta o desenvolvimento de um sistema híbrido, baseado em Algoritmos Genéticos (AG) e Redes Neurais (RN), no processo de seleção de ações, na determinação do percentual a investir em cada ativo também denominado peso do ativo na carteira e gerenciamento de carteiras de investimento. O objetivo do trabalho é avaliar o desempenho de Algoritmos Genéticos e Redes neurais para a montagem e gerenciamento de carteiras de investimento. A construção e gerenciamento de carteiras de investimento é um problema de múltiplos objetivos (retorno e risco) onde deseja-se escolher um conjunto de ações de empresas com perspectivas de lucro para formar a carteira de investimento. Esta escolha é difícil devido ao grande número de possibilidades e parâmetros a serem considerados, como: retorno, risco, correlação, volatilidade, entre outros; razão pela que é considerado como problema do tipo NP-completo. O trabalho de pesquisa foi desenvolvido em 5 etapas principais: um estudo sobre a área de carteiras de investimento; um estudo sobre os modelos com técnicas de inteligência computacional empregados nesta área; a definição de um modelo híbrido Genético-Neural para a seleção e gerenciamento da carteira para o caso estacionário; a definição de um modelo híbrido Genético- Neural para a seleção e gerencia de carteira para o caso variante no tempo; e o estudo de casos. O estudo sobre a área de carteiras de investimento envolveu toda a teoria necessária para a construção e gerenciamento de carteiras de investimento. O estudo sobre as técnicas de inteligência computacional, define-se os conceitos principais de Algoritmos Genéticos e Redes Neurais empregados nesta dissertação. A modelagem híbrida Genético-Neural para o caso clássico ou estacionário, constituiu fundamentalmente mo emprego de um Algoritmo Genético para selecionar os ativos da carteira a partir de um subconjunto de ativos noticiados na Bolsa de Valores de São Paulo - Brasil (BOVESPA). Uma Rede Neural auxilia na gerência da carteira, fazendo previsões dos retornos dos ativos para o próximo período de avaliação da carteira. Na seleção de ativos, dois algoritmos genéticos são modelados: o primeiro procura escolher 12 dentre 137 ativos negociados na BOVESPA, que apresentem maior expectativa de retorno, com menor risco e que apresentem baixa correlação com os demais ativos; e o segundo procura escolher os ativos empregando o modelo de Makowitz e o critério de Fronteira eficiente. A previsão de retornos da as ações é uma estratégia que visa melhorar o desempenho de carteiras de investimento que, tipicamente, consideram apenas o retorno médio do ativo. Diferentes modelos de redes neurais foram testados, como: Backpropagation, Redes Neurais Bayesianas, Sistema Neuro-Fuzzy Hierárquico e Redes Neurais com Filtros de Kalman; os melhores resultados de previsão foram obtidos com redes neurais com Filtros de Kalman. Para o caso estacionário foram usadas como entradas da rede neural os retornos semanais, tanto do ativo como do índice do mercado, empregando-se o método de janela deslizante para a previsão um passo a frente. A modelagem híbrida Genético-Neural para o caso variante no tempo, constituiu no emprego de 3 modelos: um AG para fazer a escolha dos ativos da carteira; o modelo GARCH para fazer as previsões da volatilidade dos ativos e o cálculo do risco de cada um deles dado pelo VAR (medida de risco que tenta quantificar a perda máxima que uma carteira (ou ativo) pode ter em um horizonte de tempo e com um intervalo de confiança); e uma RN para fazer as previsões dos retornos dos ativos para o próximo período de avaliação de carteira. Na montagem da carteira, empregou-se o Critério de Fronteira eficiente para a seleção dos ativos, também dentre os 137 negociados na BOVESPA. A previsão da volatilidade das ações é uma forma de indicar quanto pode variar o preço da ação, medida útil para determinar o risco de um ativo representado pelo VAR. / [en] This dissertation presents the development of a hybrid system, based in Algorithms Genetics (AG) and Neural Networks (RN), for the selection of stocks, for the determination of the percentage to invest in each asset called weight of the stocks on the portfolio and investmet portfolio management. The objective multiples (return and risk) where desired to choose a set of actions of compaines with profit perspectives to form the investment portfolio. This choice difficult must to the great number of possiblities and parameters be considered, as: return, risk, correlation volatility, among others; reason by which it is considered as problem NP-Complete. The research work was developed in 5 main stages: a study on the investment portfolio area; a study on the models that use techniques of computacinal intelligence in this area; the dffinition of a hybrid model Genetic-Neural for the selection and manages of portfolio for the variant case in the time; and the study of cases. The study of the investment portfolio area it involved all the necessary theory for the construction and investment portfolio management. The study the techniques of computacional intelligence it defines the main concepts of Genetic Algorithms and Neural Networks used in this dissertation. The hybrid modeling Genetic-Neural for the classic or stationary case, consisted basically in the use of a Genetic Algorithm to select the stocks of the portfolio from a subgroup of assets negotiated in the Stock exchange of São Paulo - Brazil (BOVESPA). A Neural Network assists in the management of the portfolio, making forecasts of the returns of the assets for the next period to evaluation of the portfolio. In the asset seletion, two genetic algorithm are shaped: the first selects 12 amongst 137 assets negotiated in the São Paulo Stock Exchange, that present greater return expectation, with lesser risk and that they present low correlation with the others assets; and the second selects the assets using the model of Markowitz and the Criterion of Efficient Frontier. The forecast of returns of the stocks is a strategy that it aims at to improve the investment portfolio performance, typically, they consider only the average return of the asset. Diferent models of neural networks had been tested as: Neural Back Propagation, Networks Bayesianas, Hierarchic Neuro-Fuzzy System and Neural Networks with Filters of Kalman. The best ones resulted of forecast had been gotten with the neural network the weekly returns, as Filters of Kalman. For the stationary case they had been used as entred of the neural network the weekly returns, as much of the asset as of the index of the market, using itself the method of sliding window to make the forecast a step the front. The hybrid modeling Genetic-Neural for the variant case in the time, consisted of the use of 3 models: a AG to make the choice of the assets of the portfolio; model GARCH to make the forecasts of the volatility of the assets and the calculation of the risk of each asset is given by the VAR (measured of risk that tries to quantify the maximum loss that portfolio (or asset) can have in a horizon of time and with a confidence interval); e a RN to make the forecasts of the returns of the assets for the next period to evaluation of the portfolio. In the construction of the portfolio, the Criterion of Efficient Frontier for the selection of the assets was used, also amongst the 137 negotiated in the São Paulo Stock Exchange. The forecast of the volatility of the assets is a form to indicate how much it can vary the price of the assets, measured useful to determine the risk of an asset represented for the VAR. For this case job model GARCH to make this forecast. For the forecast of the returns os the assets they had been used as inputs of the Neural Networks Back Propagation the 10 last weekly returns of the assets and the volatily of the asset, using itself also the method of sliding win

[pt] Nesta tese, é apresentado e analisado em termos da propriedade de convergência global um novo algoritmo para problemas de otimização quadrática sujeitos ou a restrições de desigualdades matriciais bilineares (BMIs) ou a restrições de desigualdades matriciais lineares (LMIs) dependentes da freqüência, estes problemas são muito relevantes para a teoria de controle porque uma ampla classe de controladores (por exemplo, controladores H2/Hinf de ordem fixa, síntese de controladores descentralizados, análise do desempenho robusto H2 ou Hinf, etc.) pode ser computada a partir da solução de problemas de otimização desta natureza. Infelizmente, estes problemas são reconhecidamente de difícil solução, pois envolvem, entre outras coisas, não convexidade (restrição BMI), não diferenciabilidade da restrição, etc. em função dessa complexibilidade, algumas alternativas para a obtenção de soluções aproximadas têm sido adotada na literatura especializada recente (Safonov, 1994; Paganini, 1996). O algoritmo proposto neste trabalho de tese é uma alternativa para as abordagens atuais com vantagens no sentido de permitir a obtenção de melhores aproximações assim como a possibilidade de explorar a estrutura particular de cada problema de interesse e, com isso, viabilizar do ponto de vista computacional o projeto de controladores envolvendo plantas de ordem mais elevada. Este algoritmo pode ser visto como a generalização de um algoritmo anterior com boas propriedades proposto por Corrêa & Sales (1998) para problemas quadráticos sujeitos a restrições envolvendo LMIs canônicas. De forma bastante genética, a solução do problema original (um problema envolvendo um número infinito de restrições é substituído por uma única) onde, em cada passo do algoritmo, a restrição é interativamente modificada. Demonstrar-se-á que para problemas quadráticos envolvendo restrições BMIs (problemas não convexos) a seqüência de soluções geradas pelo algoritmo convergirá para a solução ótima global do problema original. Por outro lado, no caso dos problemas quadráticos envolvendo restrições LMIs dependentes da freqüência, a seqüência gerada de custos auxiliares é monótona crescente e, adicionalmente, se a seqüência de matrizes de ponderação for limitada superiormente (uma condição suficiente), demonstrar-se-á que a seqüência de soluções geradas pelo algoritmo convergirá para a solução ótima global do problema original. Finalmente, são apresentadas algumas aplicações a problemas de controle acompanhadas de alguns exemplos numéricos ilustrativos. / [en] In this thesis, it is proposed and analysed in terms of the global-convergence property a new algorithm for solving quadratic optimisation problems under either a BMI (bilinear matrix inequality) or a frequency-dependent LMI (linear matrix inequality) constraints. These problems are of special interest in the control literature a some very important control problems such as the H2/H(infinite) fixed-order controller, multiobjectives, H2 and H (infinite) robust performance analysis among others problems can be posed as problems of this kind for which does not still exist yet a reliable global convergent algorithm. Nowadays, approximate solutions to those problems are based upon grid and interpolation techniques as suggested by Paganini (1996) in the case of frequency- wise LMI constraints or branch and bound algorithms or branch and bound algorithms mainly and alternating LMIs as far as BMIs constraints are involved (Safonov, 1994). All of those approaches suffer, of course, from obvious numerical difficulties. In fact, those approaches were introduced as preliminary attempts in solving the problems just mentioned. The algorithm to presented here, which can be seen as a generalisation of an earlier algorithm proposed by Corrêa e Sales (1998) for solving standard feasibility LMIs problems, is a step forward in an attempt of handling difficulties not faced properly by those methodologies. In a broaden sense, the proposed algorithm solves the original problem (a problem subject to an infinite number of constraints is replaced by a single one properly chosen. It is worth noting that this basic idea was introduced by Lawson (1961) in a rather different context, namely, the problem of computing Tchebycheff approximations by means of sequences of weighted quadratic problems. It is pointed out here that in the case of quadratic problems under a BMI constraint (a nonconvex problem); it is proved that the sequence of auxiliary solutions generated by the algorithm converges to the global optimal solution of the original one. On the other hand, as for quadratic problems under a frequency-dependent LMI constraint (an infinite-dimensional problem) it is proved that the auxiliary cost-sequence values increases asymptotically and, If the weight updating sequence is bounded from above (a sufficient condition), the sequence of auxiliary solutions will converge to the optimal solution of the original problem as well. Finally, some applications to control problem are presented accompanied by some numerical examples.

[pt] Desde 2015, a França tem empreendido um processo de normalização de práticas anunciadas quando do estado de emergência, por meio da promulgação do Pacote de Lei sobre a Vigilância e a Lei Antiterrorista de 2017. Tais instrumentos propunham o fortalecimento da segurança interna e o combate ao terrorismo sob uma lógica de antecipação do risco, com técnicas de vigilância e controle informadas por dados e metadados. Este trabalho investiga os efeitos do crescente uso de tecnologias computacionais em práticas voltadas à prevenção de possíveis futuros perigosos, buscando explorar, mais precisamente, como afetam processos de responsabilização. O artigo se divide em três movimentos analíticos principais. Primeiro, analisarei a consubstanciação de uma arquitetura institucional e normativa que consolida o monopólio da supervisão em benefício dos serviços de inteligência; e como a prática de construção de perfis suspeitos através dos algoritmos veio a ser afirmada como uma necessidade para lidar com as contingências e incertezas na França face à ameaça do terrorismo e da radicalização. Em seguida, discutirei as condições de possibilidade do uso de algoritmos na produção de conhecimento de inteligência, em particular na produção de evidências que informam as medidas individuais de controle e vigilância. A proposta é analisar as conexões entre, de um lado, práticas de mensuração do perigo em um discurso técnico ancorado no imperativo da eficiência das práticas de vigilância; de outro, os efeitos de controle sobre os indivíduos com a flexibilização de salvaguardas processuais e garantias de direitos. O terceiro movimento terá seu ponto de gravidade nas camadas de práticas humanas e não humanas presentes nas medidas de controle e vigilância para entender seus efeitos sobre processos de responsabilização. Para tal, analisarei a relação entre a produção de conhecimento e a promulgação do não-conhecimento, através do sigilo e incerteza, nos processos de contestação das medidas individuais de controle e vigilância na França. O objetivo geral aqui é analisar como dispositivos de controle administrativo, como a aplicação das medidas administrativas de controle e vigilância (MICA semelhante a prisão domiciliar), no contexto do combate ao terrorismo na França, exemplifica um sistema de validação de autoridade e dispersão dos processos de responsabilização. O trabalho argumenta que tais processos implicam uma ativa desresponsabilização dos profissionais de segurança através da dispersão de responsabilidade entre humanos e não humanos e também favorecem a promulgação do não-conhecimento, em especial através do sigilo. / [en] Since 2015, France has undertaken a process of normalizing practices announced during the state of emergency, through the promulgation of the Surveillance and Anti-Terrorism Law Package of 2017. Such instruments proposed the strengthening of internal security and the fight against terrorism under a logic of risk anticipation, with surveillance and control techniques informed by data and metadata. This work investigates the effects of the increasing use of computer technologies in practices aimed at preventing possible dangerous futures, seeking to explore, more precisely, how they affect responsabilization processes. The article is divided into three main analytical movements. First, I will analyze the consolidation of an institutional and normative architecture that consolidates the monopoly of supervision for the benefit of intelligence services. In addition, how the practice of building suspicious profiles through the algorithms came to be affirmed as a necessity to deal with the contingencies and uncertainties in France in the face of the threat of terrorism and radicalization. Then, I will discuss the conditions for the possibility of using algorithms in the production of intelligence knowledge, in particular, in the production of evidence that inform individual control and surveillance measures. The proposal is to analyze the connections between, on the one hand, hazard measurement practices in a technical discourse anchored on the imperative of efficiency in surveillance practices; on the other hand, the effects of control over individuals with the easing of procedural safeguards and guarantees of rights. The third movement will have its point of gravity in the layers of human and non-human practices present in control and surveillance measures to understand its effects on accountability processes. To this end, I will analyze the relationship between the production of knowledge and the enactment of non-knowledge, through secrecy and uncertainty, in the processes of contesting individual control and surveillance measures in France. The general objective here is to analyze how administrative control devices, such as the application of administrative control and surveillance measures (MICA similar to house arrest), in the context of combating terrorism in France, exemplify a system of validation of authority and dispersion responsabilization processes. The paper argues that such processes imply an active desresponsabilization of security professionals through the dispersion of responsibility between humans and nonhumans and favor the promulgation of non-knowledge, especially through secrecy.

Un algoritmo para problemas de optimización no lineal con restricciones de igualdad y de caja es presentado. En el marco del método de programación cuadrática secuencial, con una estrategia de globalización de región de con- fianza, se evita el uso de parámetros de penalización en funciones de mérito mediante el uso de un filtro inclinado con memoria. Los subproblemas de región de cofianza son resueltos mediante el uso del método de gradiente espectral proyectado (SPG), un método no monótono para problemas convexos de gran escala. El paso de prueba es evaluado mediante una condición no monótona sobre el Lagrangiano de la función objetivo, que puede ser considerado una generalización de la condición de fracción decrecimiento de Cauchy y la condición no monótona para búsqueda lineal de Grippo, Lampariello y Lucidi. Las propiedades de buena definición y convergencia global del algoritmo son analizadas bajo hipótesis estándar para problemas de optimización no lineal con restricciones de igualdad y de caja, basados en una estrategia de región de cofianza. Resultados numéricos son reportados para validar la eficiencia y robustez del algoritmo en problemas de variado tama~no, y un problema de ajuste de observaciones con ruido a una solución de una ecuación diferencial de segundo orden, que genera un problema no diferenciable. La condición de decrecimiento no monótona es comparada con la tradicional condición monótona mediante perfiles de rendimiento. / An algorithm based on nonmonotone trust-region- lter method for a nonlinear problem with equality and box constraints is presented. In the frame of sequential quadratic programming with a strategy for global convergence based on the trust region approach the use of a slanting lter with memory avoid the pitfalls of penalty parameters of merit functions. The trust region subproblems are solved by the Spectral Projected Gradient (SPG), a nonmonotone method for large-scale convex constrained problems. The trial step is evaluated by a nonmonotone condition in the Lagrangian of the objetive function, which can be considered not only a generalization of the fraction of Cauchy decrease condition, but also a generalization of the nonmonotone line search proposed by Grippo, Lampariello y Lucidi. Well definition and global convergence properties are analyzed under mild conditions for the non linear problems with equality and box restrictions based on trust region. Numerical results are reported to validate the robustness and eficiency of the algorithm on varied size test problems, and for fit a set of noisy observations to a second order diferential equation solution wich generate a non diferential problem. The nonmonotone rule is compared to the traditional monotone rule through performance profiles.

En las últimas décadas, debido la importancia de sus aplicaciones, se han propuesto muchas investigaciones sobre la planificación de caminos y trayectorias para los manipuladores, algunos de los ámbitos en los que pueden encontrarse ejemplos de aplicación son; la robótica industrial, sistemas autónomos, creación de prototipos virtuales y diseño de fármacos asistido por ordenador. Por otro lado, los algoritmos evolutivos se han aplicado en muchos campos, lo que motiva el interés del autor por investigar sobre su aplicación a la planificación de caminos y trayectorias en robots industriales. En este trabajo se ha llevado a cabo una búsqueda exhaustiva de la literatura existente relacionada con la tesis, que ha servido para crear una completa base de datos utilizada para realizar un examen detallado de la evolución histórica desde sus orígenes al estado actual de la técnica y las últimas tendencias. Esta tesis presenta una nueva metodología que utiliza algoritmos genéticos para desarrollar y evaluar técnicas para la planificación de caminos y trayectorias. El conocimiento de problemas específicos y el conocimiento heurístico se incorporan a la codificación, la evaluación y los operadores genéticos del algoritmo. Esta metodología introduce nuevos enfoques con el objetivo de resolver el problema de la planificación de caminos y la planificación de trayectorias para sistemas robóticos industriales que operan en entornos 3D con obstáculos estáticos, y que ha llevado a la creación de dos algoritmos (de alguna manera similares, con algunas variaciones), que son capaces de resolver los problemas de planificación mencionados. El modelado de los obstáculos se ha realizado mediante el uso de combinaciones de objetos geométricos simples (esferas, cilindros, y los planos), de modo que se obtiene un algoritmo eficiente para la prevención de colisiones. El algoritmo de planificación de caminos se basa en técnicas de optimización globales, usando algoritmos genéticos para minimizar una función objetivo considerando restricciones para evitar las colisiones con los obstáculos. El camino está compuesto de configuraciones adyacentes obtenidas mediante una técnica de optimización construida con algoritmos genéticos, buscando minimizar una función multiobjetivo donde intervienen la distancia entre los puntos significativos de las dos configuraciones adyacentes, así como la distancia desde los puntos de la configuración actual a la final. El planteamiento del problema mediante algoritmos genéticos requiere de una modelización acorde al procedimiento, definiendo los individuos y operadores capaces de proporcionar soluciones eficientes para el problema. / Abu-Dakka, FJM. (2011). Trajectory planning for industrial robot using genetic algorithms [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/10294