Spelling suggestions: "subject:"metaheuristic.""
231 |
Um estudo algor?tmico de problemas log?sticos na ind?stria de petr?leo e g?s natural / An algorithmic study of logistic problems on petroleum and natural gas industryDuarte, Herbert de Melo 16 November 2006 (has links)
Made available in DSpace on 2014-12-17T15:48:08Z (GMT). No. of bitstreams: 1
HerbertMD.pdf: 1096047 bytes, checksum: 6cf0c7d90914e2c3fd03f494b71cfa3a (MD5)
Previous issue date: 2006-11-16 / This work consists on the study of two important problems arising from the operations of petroleum and natural gas industries. The first problem the pipe dimensioning problem on constrained gas distribution networks consists in finding the least cost combination of diameters from a discrete set of commercially available ones for the pipes of a given gas network, such that it respects minimum pressure requirements at each demand node and upstream pipe conditions. On its turn, the second problem the piston pump unit routing problem comes from the need of defining the piston pump unit routes for visiting a number of non-emergent wells in on-shore fields, i.e., wells which don t have enough pressure to make the oil emerge to surface. The periodic version of this problem takes into account the wells re-filling equation to provide a more accurate planning in the long term. Besides the mathematical formulation of both problems, an exact algorithm and a taboo search were developed for the solution of the first problem and a theoretical limit and a ProtoGene transgenetic algorithm were developed for the solution of the second problem. The main concepts of the metaheuristics are presented along with the details of their application to the cited problems. The obtained results for both applications are promising when compared to theoretical limits and alternate solutions, either relative to the quality of the solutions or to associated running time / Este trabalho consiste do estudo de dois importantes problemas oriundos das opera??es das ind?strias de petr?leo e g?s natural. O primeiro problema do dimensionamento de dutos em uma rede urbana de distribui??o de g?s natural consiste em encontrar a combina??o de di?metros de menor custo, a partir de um conjunto de op??es comercialmente dispon?veis, para os dutos de uma dada rede de distribui??o de g?s, de forma a respeitar requisitos de press?o m?nima em cada n? de demanda e condi??es de upstream. Por sua vez, o segundo problema do roteamento da unidade m?vel do pistoneio decorre da necessidade de se definir as rotas de visita??o da dita unidade m?vel do pistoneio aos diversos po?os n?o surgentes do campo de explora??o, ou seja, po?os que n?o possuem press?o suficiente para fazer o ?leo emergir ? superf?cie. A vers?o peri?dica do problema leva em considera??o a equa??o de re-enchimento dos po?os, de forma a possibilitar um planejamento mais acurado num horizonte de tempo maior. Al?m da formula??o matem?tica dos dois problemas, para a solu??o do primeiro foram desenvolvidos um algoritmo exato e uma busca tabu e para o segundo, um limite superior e um algoritmo transgen?tico ProtoGene. Os principais conceitos das metaheur?sticas s?o apresentados, juntamente com os detalhes da aplica??o destas aos problemas citados. Os resultados obtidos para ambas as aplica??es s?o promissores quando comparados com limites te?ricos e solu??es alternativas, tanto relativamente ? qualidade das solu??es como ao tempo computacional envolvido
|
232 |
Algoritmos cient?ficosFelipe, Denis 14 February 2014 (has links)
Made available in DSpace on 2014-12-17T15:48:10Z (GMT). No. of bitstreams: 1
DenisF_DISSERT.pdf: 776997 bytes, checksum: c0d801fdcf21ff4f335f115d3918ed93 (MD5)
Previous issue date: 2014-02-14 / The Scientific Algorithms are a new metaheuristics inspired in the scientific research process. The new method introduces the idea of theme to search the solution space of hard problems. The inspiration for this class of algorithms comes from the act of researching that comprises thinking, knowledge sharing and disclosing new ideas. The ideas of the new method are illustrated in the Traveling Salesman Problem. A computational experiment applies the proposed approach to a new variant of the Traveling Salesman Problem named Car Renter Salesman Problem. The results are compared to state-of-the-art algorithms for the latter problem / Os algoritmos cient?ficos s?o uma nova metaheur?stica inspirada no processo da pesquisa cient?fica. O novo m?todo introduz a ideia de tema para buscar o espa?o de solu??es de problemas dif?ceis. A inspira??o para esta classe de algoritmos vem do ato de pesquisar, que compreende pensar, compartilhar conhecimento e descobrir novas ideias. As ideias do novo m?todo s?o ilustradas no Problema do Caixeiro Viajante. Um experimento computacional aplica a abordagem proposta a uma nova variante do Problema do Caixeiro Viajante intitulada Problema do Caixeiro Alugador. Os resultados s?o comparados aos algoritmos do estado da arte para o ?ltimo problema
|
233 |
Um novo método híbrido aplicado à solução de sistemas não-lineares com raízes múltiplas / A new hybrid method applied to the solution of nonlinear systems with multiple rootsMaurício Rodrigues Silva 22 June 2009 (has links)
Este trabalho tem como objetivo apresentar soluções de sistemas não-lineares com raízes múltiplas, através de um algoritmo híbrido. Para esta finalidade foi desenvolvido
e implementado um algoritmo de busca aleatória baseado no método proposto por Luus e Jaakola (1973) como etapa de busca aleatória dos pontos iniciais, que são refinados
através do algoritmo de Hooke e Jeeves. O diferencial deste trabalho foi propor um algoritmo híbrido, utilizando as características dos algoritmos Luus-Jaakola e Hooke e
Jeeves como etapas de busca e refinamento respectivamente. Para isso, os algoritmos acima são encapsulados em funções no algoritmo híbrido. Além destas duas etapas, o algoritmo híbrido possui duas outras características importantes, que é a execução repetida até que se alcance um número suficiente de soluções distintas, que são então submetidas a um processo de classificação de soluções por intervalo, onde cada intervalo gera um conjunto de soluções próximas, que por sua vez, são submetidas à etapa final de minimização, resultando em apenas um valor de solução por classe. Desta forma cada classe produz uma única solução, que faz parte do conjunto final de soluções do problema, pois este algoritmo é aplicado a problemas com múltiplas soluções. Então, o algoritmo híbrido desenvolvido foi testado, tendo como padrão, vários problemas clássicos de programação não-linear, em especial os problemas irrestritos com múltiplas soluções. Após os testes, os resultados foram comparados com o algoritmo Luus-Jaakola, e o Método de Newton Intervalar / Bisseção Generalizada (IN/GB - Interval Newton/Generalized Bisection), com a finalidade de se obter uma
análise quantitativa e qualitativa de seu desempenho. Por fim comprovou-se que o algortimo Híbrido obteve resultados superiores quando comparados com os demais. / This paper aims to present solutions for nonlinear systems with multiple roots, using a hybrid algorithm. For this purpose was developed and implemented an algorithm based on random search method proposed by Luus and Jaakola (1973) as a step in search of random starting points, which will be refined through the algorithm of Hooke and Jeeves. The differential of this work is to propose a hybrid algorithm, using the characteristics of the Luus-Jaakola algorithm and Hooke and Jeeves as a search and refinement stages respectively. For this, the above algorithms are encapsulated in functions in the hybrid algorithm. Besides these two steps, the hybrid algorithm has two other important characteristics, which is the execution repeated until to reach a sufficient number of distinct solutions, which is then undergo a process of classification of solutions by
interval, where each interval generates a set solutions to close, which in turn is subject to the final stage of minimization, resulting in only one value per class of solution. Thus each class provides a unique solution, which is part of the final set of solutions of the problem, because this algorithm is applied to problems with multiple solutions. So, the hybrid algorithm developed was tested, with the standard, several problems of classical non-linear programming, in particular the unrestricted problems with multiple solutions. After the tests, the results were compared with algorithm Luus-Jaakola, and the Interval
Newton/Generalized Bisection method (IN/GB), in order to obtain a quantitative and qualitative analysis of their performance. Finally it was found that the hybrid algortimo achieved higher when compared to the others.
|
234 |
Solução de problemas inversos de transferência radiativa em meios heterogêneos unidimensionais e uma e duas camadas utilizando o algoritmo dos vagalumes / Solution for radiative transfer inverse problems in one-dimensional heterogeneous media in one and two layers using the firefly algorithmRubens Luiz Cirino 14 March 2014 (has links)
Esta tese apresenta um estudo sobre modelagem computacional onde são
aplicadas meta-heurísticas de otimização na solução de problemas inversos de
transferência radiativa em meios unidimensionais com albedo dependente da
variável óptica, e meios unidimensionais de duas camadas onde o problema inverso
é tratado como um problema de otimização. O trabalho aplica uma meta-heurística
baseada em comportamentos da natureza conhecida como algoritmo dos
vagalumes. Inicialmente, foram feitos estudos comparativos de desempenho com
dois outros algoritmos estocásticos clássicos. Os resultados encontrados indicaram
que a escolha do algoritmo dos vagalumes era apropriada. Em seguida, foram
propostas outras estratégias que foram inseridas no algoritmo dos vagalumes
canônico. Foi proposto um caso onde se testou e investigou todas as potenciais
estratégias. As que apresentaram os melhores resultados foram, então, testadas em
mais dois casos distintos. Todos os três casos testados foram em um ambiente de
uma camada, com albedo de espalhamento dependente da posição espacial. As
estratégias que apresentaram os resultados mais competitivos foram testadas em
um meio de duas camadas. Para este novo cenário foram propostos cinco novos
casos de testes. Os resultados obtidos, pelas novas variantes do algoritmo dos
vagalumes, foram criticamente analisados. / This thesis presents a study on computational modeling where optimization
metaheuristics are applied to the solution of inverse radiative transfer problems in
heterogeneous media: in one-layer media with space-dependent single scattering
albedo, and two-layer media, where the inverse problem is formulated as an
optimization problem. It is applied a metaheuristic based on the natural behavior of
fireflies, known as the firefly algorithm. Initially, comparative studies of performance
were made with two other classic stochastic algorithms. The results indicated that the
choice of the firefly algorithm was appropriate. Then, it was proposed other strategies
that have been inserted into the original firefly algorithm. A first case was proposed
where all the strategies were investigated and tested. The strategies with the best
results were investigated in other two different cases. All the three proposed cases
involved one-layer media with space-dependent scattering albedo. The strategies
have been tested and evaluated, and those which presented the best competitive
results were then implemented for radiative problems in two-layer media. For this
new scenario five test cases were investigated, and the results obtained with the new
strategies developed in this work were critically analyzed.
|
235 |
HIBRIDIZAÇÃO DE MÉTODOS EXATOS E HEURÍSTICOS PARA RESOLUÇÃO DE PROBLEMAS DE OTIMIZAÇÃO COMBINA / HYBRIDIZATION OF EXACT AND HEURISTIC METHODS TO SOLVE COMBINATORIAL OPTIMIZATION PROBLEMStefanello, Fernando 04 March 2011 (has links)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The evolution of computer hardware as well as new applications of mathematical programming techniques, efficiently implemented in many commercial solvers, has given rise to new algorithms called hybrid metaheuristic, which have been applied to solve combinatorial problems. This work presents several approaches which try to deal with the hybridization of local search based metaheuristics with exact algorithms to solve two problems of combinatorial optimization. More specifically, the first problem, capacitated p-median problem, the proposed approach considers heuristic elimination of variable of the original mathematical model, that produce solutions of very good quality in a short amount of time, and a combination with an iterative procedure in which only a certain subset of points is considered. As regards the second problem, unrelated parallel machine scheduling with sequence and machine dependent setup time problem of minimizing makespan, is proposed a mathematical model to search the neighborhood of a solution and identify movement sequences to minimize the objective function. In both cases, mathematical models are solved using a commercial solver. Extensive computational experiments are carried out to demonstrate the good performance of the proposed approaches. / A recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.
|
236 |
Modelagem e meta-heurísticas para o problema de roteamento de veículos com janelas de tempo, múltiplos entregadores e múltiplas viagens em uma empresa de distribuição de bebidasSouza Neto, José Ferreira de 21 March 2016 (has links)
Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-06T17:59:08Z
No. of bitstreams: 1
DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:08Z (GMT) No. of bitstreams: 1
DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:14Z (GMT) No. of bitstreams: 1
DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Made available in DSpace on 2016-10-20T13:51:20Z (GMT). No. of bitstreams: 1
DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5)
Previous issue date: 2016-03-21 / Não recebi financiamento / Vehicle routing problems occur in many practical situations where the pickup and/or delivery
of goods is required. In this context, the present research aims to contribute to the study of
logistic operations that arise in companies that deliver products on a regular basis to
customers in densely populated urban areas. The problem consists in designing minimal cost
daily routes serving the maximal number of customers. To this end, the crew of each vehicle
comprise multiple deliverymen as means to reduce service times. Based on a case study in a
drinks producer and distributor in the state of São Paulo, it is proposed a mixed integer linear
programming model that comprise costs with own and chartered vehicles and the number of
deliverymen, and various operational constraints such as time windows in customers, multiple
daily trips, time limitations for the circulation of some vehicle types in specific areas,
compatibility between vehicles and customers, maximum load in each vehicle, maximum
route time and minimum load for the realization of a second trip. Results obtained by solving
the model with real instances through exact (branch&cut), heuristic (constructive, local
search, GRASP and Simulated Annealing) and hybrid (GRASP and branch&cut) approaches
demonstrate the good quality of the generated solutions, and indicate the potential of
application of some of these methods in practice. / Problemas de roteamento de veículos ocorrem em diversas situações práticas onde se faz
necessária a distribuição e/ou coleta de produtos. Nesse contexto, a presente pesquisa visa o
estudo das operações logísticas presentes em empresas que entregam produtos em base
regular a clientes localizados em áreas urbanas de alta densidade demográfica. O problema
consiste na obtenção de rotas de mínimo custo visando o atendimento do maior número de
clientes da carteira diária. Para tal, a tripulação de cada veículo pode contemplar múltiplos
entregadores para redução dos tempos de serviço. Com base em um estudo de caso em uma
distribuidora de bebidas do interior do Estado de São Paulo, é proposto um modelo de
programação linear inteira mista que considera custos com frota própria e fretada e com o
número de entregadores, e diversas restrições operacionais, tais como janelas de tempo em
clientes, múltiplas viagens diárias, limitações de horários de circulação de tipos de veículos,
compatibilidade entre veículos e clientes, capacidade máxima de carga a ser transportada em
cada veículo, tempo máximo de rota e carga mínima para realização da segunda viagem.
Resultados da resolução do modelo para instâncias reais por meio de abordagens exatas
(branch&cut), heurísticas (construtiva, busca local, GRASP e Simulated Annealing) e híbrida
(GRASP e branch&cut), demonstram a boa qualidade das soluções geradas, e evidenciam o
potencial de uso dessas metodologias na prática.
|
237 |
Uma Abordagem para Recomendação de Módulos para Projetos de Desenvolvimento Distribuído de Linhas de Produto de SoftwarePereira, Thaís Alves Burity 28 February 2011 (has links)
Made available in DSpace on 2015-05-14T12:36:28Z (GMT). No. of bitstreams: 1
arquivototal.pdf: 2198784 bytes, checksum: 572b347cf59107b757a2f48f47d938a2 (MD5)
Previous issue date: 2011-02-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Software Product Line (SPL) has been adopted by software industry in recent years, mainly
by promoting software reuse in a systematic and predictable way, and supporting product
development for global markets. Despite the benefits, SPL requires a high initial effort and
the involvement of domain experts, which are not always available in a local team. In such a
scenario, Global Software Development (GSD) approaches would be applied to find domain
experts and more qualified teams for SPL projects. Moreover, such work strategy reinforces
some of the benefits already offered by SPL approach, such as reducing development cost and
increasing product quality. Nonetheless, GSD approaches also present some obstacles, which
are mainly related to communication between dispersed development teams. Assuming that
dependencies between software components greatly influence the need for communication
between their respective development teams, in this work it is presented an approach to
identify candidates for modules to be developed in a (partially) independent manner by
geographically dispersed teams, in which a module is a clustering of components. To do so,
the approach defines: quantitative measures that describe the dependence between software
components in SPL projects; an algorithm based on metaheuristics for clustering components
into modules, dealing with clustering as an optimization problem; and a quantitative measure
that describe the dependencies between modules, which must be employed to guide the
allocation of the development teams to the modules. / Linhas de Produto de Software (LPS) tem ganhado bastante espaço na indústria de software
nos últimos anos, principalmente por promover o reuso de maneira sistemática e previsível, e
oferecer apoio ao desenvolvimento de produtos para mercados globais. No entanto, o
desenvolvimento de LPS exige das organizações grande investimento inicial e a participação
de profissionais qualificados, os quais nem sempre estão disponíveis localmente. Nesse
cenário, o Desenvolvimento Distribuído de Software (DDS) pode ser empregado para
encontrar especialistas do domínio e equipes mais qualificadas para o desenvolvimento de
LPS. Além disso, essa forma de trabalho reforça alguns dos benefícios já oferecidos por LPS,
tais como redução de custo de desenvolvimento e aumento da qualidade dos produtos. Apesar
disso, abordagens de DDS também têm suas limitações, relacionadas principalmente à
comunicação entre as equipes participantes de um mesmo projeto. Partindo da premissa de
que dependências entre componentes de software exercem grande influência sobre a
necessidade de comunicação entre suas respectivas equipes de desenvolvimento, neste
trabalho é apresentada uma abordagem para identificar candidatos à módulos para serem
desenvolvidos de forma (parcialmente) independente por equipes geograficamente dispersas,
sendo um módulo um agrupamento de componentes. Para tanto, a abordagem define: medidas
quantitativas que descrevem a dependência entre componentes de software em projetos de
LPS; um algoritmo baseado em metaheurísticas para agrupar componentes em módulos,
tratando o agrupamento como um problema de otimização; e uma medida quantitativa que
descreve as dependências entre módulos, que deve ser empregada para guiar a alocação das
equipes de desenvolvimento aos módulos.
|
238 |
Uma col?nia de formigas para o caminho mais curto multiobjetivoBezerra, Leonardo Cesar Teon?cio 07 February 2011 (has links)
Made available in DSpace on 2015-03-03T15:47:46Z (GMT). No. of bitstreams: 1
LeonardoCTB_DISSERT.pdf: 2119704 bytes, checksum: 5bdd21de8bfa668bba821593cdd5289f (MD5)
Previous issue date: 2011-02-07 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / Multi-objective combinatorial optimization problems have peculiar characteristics that
require optimization methods to adapt for this context. Since many of these problems are
NP-Hard, the use of metaheuristics has grown over the last years. Particularly, many
different approaches using Ant Colony Optimization (ACO) have been proposed. In this
work, an ACO is proposed for the Multi-objective Shortest Path Problem, and is compared
to two other optimizers found in the literature. A set of 18 instances from two
distinct types of graphs are used, as well as a specific multiobjective performance assessment
methodology. Initial experiments showed that the proposed algorithm is able
to generate better approximation sets than the other optimizers for all instances. In the
second part of this work, an experimental analysis is conducted, using several different
multiobjective ACO proposals recently published and the same instances used in the first
part. Results show each type of instance benefits a particular type of instance benefits a
particular algorithmic approach. A new metaphor for the development of multiobjective
ACOs is, then, proposed. Usually, ants share the same characteristics and only few works
address multi-species approaches. This works proposes an approach where multi-species
ants compete for food resources. Each specie has its own search strategy and different
species do not access pheromone information of each other. As in nature, the successful
ant populations are allowed to grow, whereas unsuccessful ones shrink. The approach introduced
here shows to be able to inherit the behavior of strategies that are successful
for different types of problems. Results of computational experiments are reported and
show that the proposed approach is able to produce significantly better approximation
sets than other methods / Problemas de otimiza??o combinat?ria multiobjetivo apresentam caracter?sticas peculiares
que exigem que t?cnicas de otimiza??o se adaptem a esse contexto. Como muitos
desses problemas s?o NP-?rduos, o uso de metaheur?sticas tem crescido nos ?ltimos anos.
Particularmente, muitas abordagens que utilizam a Otimiza??o por Col?nias de Formigas
t?m sido propostas. Neste trabalho, prop?e-se um algoritmo baseado em col?nias de formigas
para o Problema do Caminho mais Curto Multiobjetivo, e compara-se o algoritmo
proposto com dois otimizadores encontrados na literatura. Um conjunto de 18 inst?ncias
oriundas de dois tipos de grafos ? utilizado, al?m de uma metodologia espec?fica para a
avalia??o de otimizadores multiobjetivo. Os experimentos iniciais mostram que o algoritmo
proposto consegue gerar conjuntos de aproxima??o melhores que os demais otimizadores
para todas as inst?ncias. Na segunda parte do trabalho, uma an?lise experimental de diferentes
abordagens publicadas para col?nias de formigas multiobjetivo ? realizada, usando
as mesmas inst?ncias. Os experimentos mostram que cada tipo de inst?ncia privilegia uma
abordagem algor?tmica diferente. Uma nova met?fora para o desenvolvimento deste tipo
de metaheur?stica ? ent?o proposta. Geralmente, formigas possuem caracter?sticas comuns
e poucos artigos abordam o uso de m?ltiplas esp?cies. Neste trabalho, uma abordagem
com m?ltiplas esp?cies competindo por fontes de comida ? proposta. Cada esp?cie possui
sua pr?pria estrat?gia de busca e diferentes esp?cies n?o tem acesso ? informa??o dada
pelo ferom?nio das outras. Como na natureza, as popula??es de formigas bem sucedidas
tem a chance de crescer, enquanto as demais se reduzem. A abordagem apresentada aqui
mostra-se capaz de herdar o comportamento de estrat?gias bem-sucedidas em diferentes
tipos de inst?ncias. Resultados de experimentos computacionais s?o relatados e mostram
que a abordagem proposta produz conjuntos de aproxima??o significativamente melhores
que os outros m?todos
|
239 |
Um novo método híbrido aplicado à solução de sistemas não-lineares com raízes múltiplas / A new hybrid method applied to the solution of nonlinear systems with multiple rootsMaurício Rodrigues Silva 22 June 2009 (has links)
Este trabalho tem como objetivo apresentar soluções de sistemas não-lineares com raízes múltiplas, através de um algoritmo híbrido. Para esta finalidade foi desenvolvido
e implementado um algoritmo de busca aleatória baseado no método proposto por Luus e Jaakola (1973) como etapa de busca aleatória dos pontos iniciais, que são refinados
através do algoritmo de Hooke e Jeeves. O diferencial deste trabalho foi propor um algoritmo híbrido, utilizando as características dos algoritmos Luus-Jaakola e Hooke e
Jeeves como etapas de busca e refinamento respectivamente. Para isso, os algoritmos acima são encapsulados em funções no algoritmo híbrido. Além destas duas etapas, o algoritmo híbrido possui duas outras características importantes, que é a execução repetida até que se alcance um número suficiente de soluções distintas, que são então submetidas a um processo de classificação de soluções por intervalo, onde cada intervalo gera um conjunto de soluções próximas, que por sua vez, são submetidas à etapa final de minimização, resultando em apenas um valor de solução por classe. Desta forma cada classe produz uma única solução, que faz parte do conjunto final de soluções do problema, pois este algoritmo é aplicado a problemas com múltiplas soluções. Então, o algoritmo híbrido desenvolvido foi testado, tendo como padrão, vários problemas clássicos de programação não-linear, em especial os problemas irrestritos com múltiplas soluções. Após os testes, os resultados foram comparados com o algoritmo Luus-Jaakola, e o Método de Newton Intervalar / Bisseção Generalizada (IN/GB - Interval Newton/Generalized Bisection), com a finalidade de se obter uma
análise quantitativa e qualitativa de seu desempenho. Por fim comprovou-se que o algortimo Híbrido obteve resultados superiores quando comparados com os demais. / This paper aims to present solutions for nonlinear systems with multiple roots, using a hybrid algorithm. For this purpose was developed and implemented an algorithm based on random search method proposed by Luus and Jaakola (1973) as a step in search of random starting points, which will be refined through the algorithm of Hooke and Jeeves. The differential of this work is to propose a hybrid algorithm, using the characteristics of the Luus-Jaakola algorithm and Hooke and Jeeves as a search and refinement stages respectively. For this, the above algorithms are encapsulated in functions in the hybrid algorithm. Besides these two steps, the hybrid algorithm has two other important characteristics, which is the execution repeated until to reach a sufficient number of distinct solutions, which is then undergo a process of classification of solutions by
interval, where each interval generates a set solutions to close, which in turn is subject to the final stage of minimization, resulting in only one value per class of solution. Thus each class provides a unique solution, which is part of the final set of solutions of the problem, because this algorithm is applied to problems with multiple solutions. So, the hybrid algorithm developed was tested, with the standard, several problems of classical non-linear programming, in particular the unrestricted problems with multiple solutions. After the tests, the results were compared with algorithm Luus-Jaakola, and the Interval
Newton/Generalized Bisection method (IN/GB), in order to obtain a quantitative and qualitative analysis of their performance. Finally it was found that the hybrid algortimo achieved higher when compared to the others.
|
240 |
Solução de problemas inversos de transferência radiativa em meios heterogêneos unidimensionais e uma e duas camadas utilizando o algoritmo dos vagalumes / Solution for radiative transfer inverse problems in one-dimensional heterogeneous media in one and two layers using the firefly algorithmRubens Luiz Cirino 14 March 2014 (has links)
Esta tese apresenta um estudo sobre modelagem computacional onde são
aplicadas meta-heurísticas de otimização na solução de problemas inversos de
transferência radiativa em meios unidimensionais com albedo dependente da
variável óptica, e meios unidimensionais de duas camadas onde o problema inverso
é tratado como um problema de otimização. O trabalho aplica uma meta-heurística
baseada em comportamentos da natureza conhecida como algoritmo dos
vagalumes. Inicialmente, foram feitos estudos comparativos de desempenho com
dois outros algoritmos estocásticos clássicos. Os resultados encontrados indicaram
que a escolha do algoritmo dos vagalumes era apropriada. Em seguida, foram
propostas outras estratégias que foram inseridas no algoritmo dos vagalumes
canônico. Foi proposto um caso onde se testou e investigou todas as potenciais
estratégias. As que apresentaram os melhores resultados foram, então, testadas em
mais dois casos distintos. Todos os três casos testados foram em um ambiente de
uma camada, com albedo de espalhamento dependente da posição espacial. As
estratégias que apresentaram os resultados mais competitivos foram testadas em
um meio de duas camadas. Para este novo cenário foram propostos cinco novos
casos de testes. Os resultados obtidos, pelas novas variantes do algoritmo dos
vagalumes, foram criticamente analisados. / This thesis presents a study on computational modeling where optimization
metaheuristics are applied to the solution of inverse radiative transfer problems in
heterogeneous media: in one-layer media with space-dependent single scattering
albedo, and two-layer media, where the inverse problem is formulated as an
optimization problem. It is applied a metaheuristic based on the natural behavior of
fireflies, known as the firefly algorithm. Initially, comparative studies of performance
were made with two other classic stochastic algorithms. The results indicated that the
choice of the firefly algorithm was appropriate. Then, it was proposed other strategies
that have been inserted into the original firefly algorithm. A first case was proposed
where all the strategies were investigated and tested. The strategies with the best
results were investigated in other two different cases. All the three proposed cases
involved one-layer media with space-dependent scattering albedo. The strategies
have been tested and evaluated, and those which presented the best competitive
results were then implemented for radiative problems in two-layer media. For this
new scenario five test cases were investigated, and the results obtained with the new
strategies developed in this work were critically analyzed.
|
Page generated in 0.0495 seconds