Página 1 dos resultados de 5427 itens digitais encontrados em 0.039 segundos

Local search multiuser detection

OLIVEIRA, Leonardo D.; Neto, Fernando Ciriaco Dias; ABRAO, Taufik; Jeszensky, Paul Jean Etienne
Fonte: ELSEVIER GMBH, URBAN & FISCHER VERLAG Publicador: ELSEVIER GMBH, URBAN & FISCHER VERLAG
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
66.840117%
In this work, a wide analysis of local search multiuser detection (LS-MUD) for direct sequence/code division multiple access (DS/CDMA) systems under multipath channels is carried out considering the performance-complexity trade-off. It is verified the robustness of the LS-MUD to variations in loading, E(b)/N(0), near-far effect, number of fingers of the Rake receiver and errors in the channel coefficients estimates. A compared analysis of the bit error rate (BER) and complexity trade-off is accomplished among LS, genetic algorithm (GA) and particle swarm optimization (PSO). Based on the deterministic behavior of the LS algorithm, it is also proposed simplifications over the cost function calculation, obtaining more efficient algorithms (simplified and combined LS-MUD versions) and creating new perspectives for the MUD implementation. The computational complexity is expressed in terms of the number of operations in order to converge. Our conclusion pointed out that the simplified LS (s-LS) method is always more efficient, independent of the system conditions, achieving a better performance with a lower complexity than the others heuristics detectors. Associated to this, the deterministic strategy and absence of input parameters made the s-LS algorithm the most appropriate for the MUD problem. (C) 2008 Elsevier GmbH. All rights reserved.

Heurística com busca local para solução do problema de cobertura de rotas com cardinalidade restrita.; Heuristic with local search to solve the cardinality constraint lane covering problem.

Rosin, Rafael Alzuguir
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 19/12/2011 Português
Relevância na Pesquisa
67.09505%
A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local.; The growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation...

Meta-heurísticas Iterated Local Search, GRASP e Artificial Bee Colony aplicadas ao Job Shop Flexível para minimização do atraso total.; Meta-heuristics Iterated Local Search, GRASP and Artificial Bee Colony applied to Flexible Job Shop minimizing total tardiness.

Melo, Everton Luiz de
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 07/02/2014 Português
Relevância na Pesquisa
67.273086%
O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta-heurísticas de diferentes categorias. Essas meta-heurísticas são: Iterated Local Search (ILS)...

Combining global tabu search with local search for solving systems of equalities and inequalities

Ramadas, Gisela C. V.; Fernandes, Edite Manuela da G. P.
Fonte: AIP Conference Proceedings Publicador: AIP Conference Proceedings
Tipo: Conferência ou Objeto de Conferência
Publicado em /09/2011 Português
Relevância na Pesquisa
57.064663%
This papers aims at providing a combined strategy for solving systems of equalities and inequalities. The combined strategy uses two types of steps: a global search step and a local search step. The global step relies on a tabu search heuristic and the local step uses a deterministic search known as Hooke and Jeeves. The choice of step, at each iteration, is based on the level of reduction of the l2-norm of the error function observed in the equivalent system of equations, compared with the previous iteration; Fundação para a Ciência e a Tecnologia (FCT)

Self-adaptive combination of global tabu search and local search for nonlinear equations

Ramadas, Gisela C. V.; Fernandes, Edite Manuela da G. P.
Fonte: Taylor and Francis Publicador: Taylor and Francis
Tipo: Artigo de Revista Científica
Publicado em //2012 Português
Relevância na Pesquisa
56.81867%
Solving systems of nonlinear equations is a very important task since the problems emerge mostly through the mathematical modeling of real problems that arise naturally in many branches of engineering and in the physical sciences. The problem can be naturally reformulated as a global optimization problem. In this paper, we show that a self-adaptive combination of a metaheuristic with a classical local search method is able to converge to some difficult problems that are not solved by Newton-type methods; Fundação para a Ciência e a Tecnologia (FCT)

Genetic algorithm with a local search strategy for discovering communities in complex networks

Liu, Dayou; Di, Jin; Baquero, Carlos; He, Dongxiao; Yang, Bo; Yu, Qiangyuan
Fonte: Atlantis Press Publicador: Atlantis Press
Tipo: Artigo de Revista Científica
Publicado em /03/2013 Português
Relevância na Pesquisa
67.18775%
In order to further improve the performance of current genetic algorithms aiming at discovering communities, a local search based genetic algorithm GALS is here proposed. The core of GALS is a local search based mutation technique. In order to overcome the drawbacks of traditional mutation methods, the paper develops the concept of marginal gene and then the local monotonicity of modularity function Q is deduced from each nodes local view. Based on these two elements, a new mutation method combined with a local search strategy is presented. GALS has been evaluated on both synthetic benchmarks and several real networks, and compared with some presently competing algorithms. Experimental results show that GALS is highly effective and efficient for discovering community.

Targeting the Cell Broadband Engine for constraint-based local search

Diaz, Daniel; Abreu, Salvador; Codognet, Philippe
Fonte: Universidade de Évora Publicador: Universidade de Évora
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
66.981665%
We investigated the use of the Cell Broadband Engine (Cell/BE) for constraint-based local search and combinatorial optimization applications. We presented a parallel version of a constraint-based local search algorithm that was chosen because it fits very well the Cell/BE architecture because it requires neither shared memory nor communication among processors. The performance study on several large optimization benchmarks shows mostly linear time speedups, sometimes even super linear. These experiments were carried out on a dual-Cell IBM (Armonk, NY, USA) blade with 16 processors. Besides getting speedups, the execution times exhibit a much smaller variance that benefits applications where a timely reply is critical. Copyright © 2011 John Wiley & Sons, Ltd.

Constraint reasoning with local search for continuous optimization

Saleh, Amr Hany
Fonte: Universidade Nova de Lisboa Publicador: Universidade Nova de Lisboa
Tipo: Dissertação de Mestrado
Publicado em /07/2014 Português
Relevância na Pesquisa
67.258633%
Optimization is a very important field for getting the best possible value for the optimization function. Continuous optimization is optimization over real intervals. There are many global and local search techniques. Global search techniques try to get the global optima of the optimization problem. However, local search techniques are used more since they try to find a local minimal solution within an area of the search space. In Continuous Constraint Satisfaction Problems (CCSP)s, constraints are viewed as relations between variables, and the computations are supported by interval analysis. The continuous constraint programming framework provides branch-and-prune algorithms for covering sets of solutions for the constraints with sets of interval boxes which are the Cartesian product of intervals. These algorithms begin with an initial crude cover of the feasible space (the Cartesian product of the initial variable domains) which is recursively refined by interleaving pruning and branching steps until a stopping criterion is satisfied. In this work, we try to find a convenient way to use the advantages in CCSP branchand- prune with local search of global optimization applied locally over each pruned branch of the CCSP. We apply local search techniques of continuous optimization over the pruned boxes outputted by the CCSP techniques. We mainly use steepest descent technique with different characteristics such as penalty calculation and step length. We implement two main different local search algorithms. We use “Procure”...

Application of substructural local search in the MAXSAT problem

Gonzalez, Pedro Frazão
Fonte: Universidade do Algarve Publicador: Universidade do Algarve
Tipo: Dissertação de Mestrado
Publicado em //2011 Português
Relevância na Pesquisa
56.981665%
Dissertação de mest., Engenharia Informática, Faculdade de Ciências e Tecnologia, Univ. do Algarve, 2011; Genetic Algorithms (GAs) are stochastic optimizers usually applied to problems where the use of deterministic methods is not practical or when information about how to solve the problem is scarce. Although traditional GAs show good results in a broad range of problems, they do not take into account the dependencies that may exist among the variables of a given problem. Without respecting these links, achieving the optimum can be very hard or even impossible. Estimation of Distribution Algorithms (EDAs) are methods inspired on GAs that are able to learn the linkage between variables without providing any information about the problem structure. These methods use machine learning techniques to build a probabilistic model that captures the regularities present in the population (a set of candidate solutions for our problem). The learned model is used to generate new solutions similar to those present in the population but also with some innovation. The Substructural Local Search (SLS) is a method recently proposed that takes advantage from the model built by the EDA and performs local search in each substructure of the model...

An experimental study of variable depth search algorithms for the quadratic assignment problem

Goldbarg,Elizabeth Ferreira Gouvêa; Goldbarg,Marco Cesar
Fonte: Sociedade Brasileira de Pesquisa Operacional Publicador: Sociedade Brasileira de Pesquisa Operacional
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/04/2012 Português
Relevância na Pesquisa
57.04166%
This paper introduces a new variable depth search method for the Quadratic Assignment Problem. The new method considers the cost of edges assignment as the criterion to decide which vertices to exchange during local search moves. It also presents the results of an extensive experimental study that compares the performance of local search and variable depth search algorithms for the Quadratic Assignment Problem. The investigation presented here contributes to a better understanding of the potential of these techniques, which are widely used as intensification tools in more sophisticated heuristic methods, such as evolutionary algorithms. Different algorithms presented in the literature were implemented and compared to the proposed methods. The results of a computational experiment with 161 benchmark instances are reported. Different statistical tests are applied in order to analyze the results provided by the experiments.

Approximate Local Search in Combinatorial Optimization

Orlin, James B.; Punnen, Abraham P.; Schulz, Andreas S.
Fonte: MIT - Massachusetts Institute of Technology Publicador: MIT - Massachusetts Institute of Technology
Tipo: Trabalho em Andamento Formato: 173594 bytes; application/pdf
Português
Relevância na Pesquisa
67.077075%
Local search algorithms for combinatorial optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of epsilon-local optimality and show that an epsilon-local optimum can be identified in time polynomial in the problem size and 1/epsilon whenever the corresponding neighborhood can be searched in polynomial time, for epsilon > 0. If the neighborhood can be searched in polynomial time for a delta-local optimum, we present an algorithm that produces a (delta+epsilon)-local optimum in time polynomial in the problem size and 1/epsilon. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if it has a fully polynomial-time augmentation schem

Witness-Isomorphic Reductions and Local Search

Fischer, Sophie ; Hemaspaandra, Lane A. ; Torenvliet, Leen
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Relatório
Português
Relevância na Pesquisa
66.840117%
We study witness-isomorphic reductions, a type of structure-preserving reduction between NP decision problems. We completely determine the relative power of the different models of witness-isomorphic reduction, and we show that witness-isomorphic reductions can be used in a uniform approach to the local search problem.

A feature-based comparison of local search and the Christofides algorithm for the travelling salesperson Problem

Nallaperuma, S.; Wagner, M.; Neumann, F.; Bischi, B.; Mersmann, O.; Trautmann, H.
Fonte: ACM; online Publicador: ACM; online
Tipo: Conference paper
Publicado em //2013 Português
Relevância na Pesquisa
66.840117%
Understanding the behaviour of well-known algorithms for classical NP-hard optimisation problems is still a difficult task. With this paper, we contribute to this research direction and carry out a feature based comparison of local search and the well-known Christofides approximation algorithm for the Traveling Salesperson Problem. We use an evolutionary algorithm approach to construct easy and hard instances for the Christofides algorithm, where we measure hardness in terms of approximation ratio. Our results point out important features and lead to hard and easy instances for this famous algorithm. Furthermore, our cross-comparison gives new insights on the complementary benefits of the different approaches.; http://www.sigevo.org/foga-2013/; Samadhi Nallaperuma, Markus Wagner, Frank Neumann, Bernd Bischl, Olaf Mersmann, Heike Trautmann

Genetic algorithm with local search for community mining in complex networks

Di Jin; Dongxiao He; Dayou Liu; Baquero, Carlos
Fonte: IEEE; IEEE Publicador: IEEE; IEEE
Tipo: Conferência ou Objeto de Conferência
Publicado em //2010 Português
Relevância na Pesquisa
67.07755%
Detecting communities from complex networks has triggered considerable attention in several application domains. Targeting this problem, a local search based genetic algorithm (GALS) which employs a graph-based representation (LAR) has been proposed in this work. The core of the GALS is a local search based mutation technique. Aiming to overcome the drawbacks of the existing mutation methods, a concept called marginal gene has been proposed, and then an effective and efficient mutation method, combined with a local search strategy which is based on the concept of marginal gene, has also been proposed by analyzing the modularity function. Moreover, in this paper the percolation theory on ER random graphs is employed to further clarify the effectiveness of LAR presentation; A Markov random walk based method is adopted to produce an accurate and diverse initial population; the solution space of GALS will be significantly reduced by using a graph based mechanism. The proposed GALS has been tested on both computer-generated and real-world networks, and compared with some competitive community mining algorithms. Experimental result has shown that GALS is hig y effective and efficient for discovering community structure.

Combining global tabu search with local search for solving systems of equalities and inequalities

Ramadas, Gisela C. V.; Fernandes, Edite M. G. P.
Fonte: AIP Conference Proceedings Publicador: AIP Conference Proceedings
Tipo: Artigo de Revista Científica
Publicado em //2011 Português
Relevância na Pesquisa
57.064663%
This papers aims at providing a combined strategy for solving systems of equalities and inequalities. The combined strategy uses two types of steps: a global search step and a local search step. The global step relies on a tabu search heuristic and the local step uses a deterministic search known as Hooke and Jeeves. The choice of step, at each iteration, is based on the level of reduction of the l2-norm of the error function observed in the equivalent system of equations, compared with the previous iteration.

Backbone Fragility and the Local Search Cost Peak

Gent, I. P.; Singer, J.; Smaill, A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 01/06/2011 Português
Relevância na Pesquisa
47.18731%
The local search algorithm WSat is one of the most successful algorithms for solving the satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances near the so-called `satisfiability threshold', but still shows a peak in search cost near the threshold and large variations in cost over different instances. We make a number of significant contributions to the analysis of WSat on high-cost random instances, using the recently-introduced concept of the backbone of a SAT instance. The backbone is the set of literals which are entailed by an instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We show a very strong correlation between search cost and the Hamming distance to the nearest solution early in WSat's search. This pattern leads us to introduce a measure of the backbone fragility of an instance, which indicates how persistent the backbone is as clauses are removed. We propose that high-cost random instances for local search are those with very large backbones which are also backbone-fragile. We suggest that the decay in cost beyond the satisfiability threshold is due to increasing backbone robustness (the opposite of backbone fragility). Our hypothesis makes three correct predictions. First...

When Gravity Fails: Local Search Topology

Frank, J.; Cheeseman, P.; Stutz, J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/11/1997 Português
Relevância na Pesquisa
47.276387%
Local search algorithms for combinatorial search problems frequently encounter a sequence of states in which it is impossible to improve the value of the objective function; moves through these regions, called plateau moves, dominate the time spent in local search. We analyze and characterize plateaus for three different classes of randomly generated Boolean Satisfiability problems. We identify several interesting features of plateaus that impact the performance of local search algorithms. We show that local minima tend to be small but occasionally may be very large. We also show that local minima can be escaped without unsatisfying a large number of clauses, but that systematically searching for an escape route may be computationally expensive if the local minimum is large. We show that plateaus with exits, called benches, tend to be much larger than minima, and that some benches have very few exit states which local search can use to escape. We show that the solutions (i.e., global minima) of randomly generated problem instances form clusters, which behave similarly to local minima. We revisit several enhancements of local search algorithms and explain their performance in light of our results. Finally we discuss strategies for creating the next generation of local search algorithms.; Comment: See http://www.jair.org/ for any accompanying files

Local-Search based Approximation Algorithms for Mobile Facility Location Problems

Ahmadian, Sara; Friggstad, Zachary; Swamy, Chaitanya
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/01/2013 Português
Relevância na Pesquisa
47.21714%
We consider the {\em mobile facility location} (\mfl) problem. We are given a set of facilities and clients located in a common metric space. The goal is to move each facility from its initial location to a destination and assign each client to the destination of some facility so as to minimize the sum of the movement-costs of the facilities and the client-assignment costs. This abstracts facility-location settings where one has the flexibility of moving facilities from their current locations to other destinations so as to serve clients more efficiently by reducing their assignment costs. We give the first {\em local-search based} approximation algorithm for this problem and achieve the best-known approximation guarantee. Our main result is $(3+\epsilon)$-approximation for this problem for any constant $\epsilon>0$ using local search. The previous best guarantee was an 8-approximation algorithm based on LP-rounding. Our guarantee {\em matches} the best-known approximation guarantee for the $k$-median problem. Since there is an approximation-preserving reduction from the $k$-median problem to \mfl, any improvement of our result would imply an analogous improvement for the $k$-median problem. Furthermore, {\em our analysis is tight} (up to $o(1)$ factors) since the tight example for the local-search based 3-approximation algorithm for $k$-median can be easily adapted to show that our local-search algorithm has a tight approximation ratio of 3. One of the chief novelties of the analysis is that in order to generate a suitable collection of local-search moves whose resulting inequalities yield the desired bound on the cost of a local-optimum...

Local Search and Rescue Teams in the United States

Denver, Megan; Perez, Jaime; Aguirre, Benigno E.
Fonte: Disaster Research Center Publicador: Disaster Research Center
Tipo: Outros Formato: 12697659 bytes; application/pdf
Português
Relevância na Pesquisa
57.023726%
Arguably one of the least appreciated actors in disaster response is local search and rescue (SAR) teams, despite their importance in saving lives. In contrast to fire and police departments, federal Urban Search and Rescue (US&R) taskforces, the Red Cross, the Salvation Army, and other well known disaster response organizations, local SAR teams have not received much recognition or support at the national level. This is the case even in the contemporary context in which "homeland security" and "improvements of resiliency" in American institutions are buzzwords. Their "invisibility" is also reflected in the dearth of research literature about them in the field of emergency management and the social sciences of disasters. An exception to this is the work by Lois (1999), who looked at the dynamics of a local SAR team and provided an in-depth view of the authority structure and the slow advancement of new members in the hierarchy of the group. Earlier, Drabek (1981) also provided insights by surveying local SAR teams in Washington and Wyoming to better understand attitudes towards regulations, agency jurisdictions, SAR funding, and issues of legal liability. While these efforts begin to explore important questions in this understudied field...

Enhanced Differential Evolution Based on Adaptive Mutation and Wrapper Local Search Strategies for Global Optimization Problems

Lu,Chun-Liang; Chiu,Shih-Yuan; Hsu,Chih-Hsu; Yen,Shi-Jim
Fonte: UNAM, Centro de Ciencias Aplicadas y Desarrollo Tecnológico Publicador: UNAM, Centro de Ciencias Aplicadas y Desarrollo Tecnológico
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/01/2014 Português
Relevância na Pesquisa
66.91957%
Differential evolution (DE) is a simple, powerful optimization algorithm, which has been widely used in many areas. However, the choices of the best mutation and search strategies are difficult for the specific issues. To alleviate these drawbacks and enhance the performance of DE, in this paper, the hybrid framework based on the adaptive mutation and Wrapper Local Search (WLS) schemes, is proposed to improve searching ability to efficiently guide the evolution of the population toward the global optimum. Furthermore, the effective particle encoding representation named Particle Segment Operation-Machine Assignment (PSOMA) that we previously published is applied to always produce feasible candidate solutions for solving the Flexible Job-shop Scheduling Problem (FJSP). Experiments were conducted on comprehensive set of complex benchmarks including the unimodal, multimodal and hybrid composition function, to validate performance of the proposed method and to compare with other state-of-the art DE variants such as JDE, JADE, MDE_PBX etc. Meanwhile, the hybrid DE model incorporating PSOMA is used to solve different representative instances based on practical data for multi-objective FJSP verifications. Simulation results indicate that the proposed method performs better for the majority of the single-objective scalable benchmark functions in terms of the solution accuracy and convergence rate. In addition...