共查询到20条相似文献,搜索用时 15 毫秒
1.
Global Optimization by Multilevel Coordinate Search 总被引:3,自引:0,他引:3
Inspired by a method by Jones et al. (1993), we present a global optimization algorithm based on multilevel coordinate search. It is guaranteed to converge if the function is continuous in the neighborhood of a global minimizer. By starting a local search from certain good points, an improved convergence result is obtained. We discuss implementation details and give some numerical results. 相似文献
2.
We propose in this paper a novel integration of local search algorithms within a constraint programming framework for combinatorial optimization problems, in an attempt to gain both the efficiency of local search methods and the flexibility of constraint programming while maintaining a clear separation between the constraints of the problem and the actual search procedure. Each neighborhood exploration is performed by branch-and-bound search, whose potential pruning capabilities open the door to more elaborate local moves, which could lead to even better approximate results. Two illustrations of this framework are provided, including computational results for the traveling salesman problem with time windows. These results indicate that it is one order of magnitude faster than the customary constraint programming approach to local search and that it is competitive with a specialized local search algorithm. 相似文献
3.
M. De Santis P. Festa G. Liuzzi S. Lucidi F. Rinaldi 《Mathematical Programming Computation》2016,8(3):271-309
A greedy randomized adaptive search procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as the new current solution. In this paper, we propose a variant of the GRASP framework that uses a new “nonmonotone” strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems: the maximum cut problem (MAX-CUT), the weighted maximum satisfiability problem (MAX-SAT), and the quadratic assignment problem (QAP). 相似文献
4.
A DERIVATIVE-FREE ALGORITHM FOR UNCONSTRAINED OPTIMIZATION 总被引:1,自引:0,他引:1
Peng Yehui Liu Zhenhai 《高校应用数学学报(英文版)》2005,20(4):491-498
In this paper a hybrid algorithm which combines the pattern search method and the genetic algorithm for unconstrained optimization is presented. The algorithm is a deterministic pattern search algorithm,but in the search step of pattern search algorithm,the trial points are produced by a way like the genetic algorithm. At each iterate, by reduplication,crossover and mutation, a finite set of points can be used. In theory,the algorithm is globally convergent. The most stir is the numerical results showing that it can find the global minimizer for some problems ,which other pattern search algorithms don't bear. 相似文献
5.
The purpose of this paper is twofold: (1) to examine strengths and weaknesses of recently developed optimization methods for selecting radiation treatment beam angles and (2) to propose a simple and easy-to-use hybrid framework that overcomes some of the weaknesses observed with these methods. Six optimization methods—branch and bound (BB), simulated annealing (SA), genetic algorithms (GA), nested partitions (NP), branch and prune (BP), and local neighborhood search (LNS)—were evaluated. Our preliminary test results revealed that (1) one of the major drawbacks of the reported algorithms was the limited ability to find a good solution within a reasonable amount of time in a clinical setting, (2) all heuristic methods require selecting appropriate parameter values, which is a difficult chore, and (3) the LNS algorithm has the ability to identify good solutions only if provided with a good starting point. On the basis of these findings, we propose a unified beam angle selection framework that, through two sequential phases, consistently finds clinically relevant locally optimal solutions. Considering that different users may use different optimization approaches among those mentioned above, the first phase aims to quickly find a good feasible solution using SA, GA, NP, or BP. This solution is then used as a starting point for LNS to find a locally optimal solution. Experimental results using this unified method on five clinical cases show that it not only produces consistently good-quality treatment solutions but also alleviates the effort of selecting an initial set of appropriate parameter values that is required by all of the existing optimization methods. 相似文献
6.
V. L. Beresnev E. N. Goncharov A. A. Mel’nikov 《Journal of Applied and Industrial Mathematics》2012,6(1):22-30
In the optimization problem for pseudo-Boolean functions we consider a local search algorithm with a generalized neighborhood.
This neighborhood is constructed for a locally optimal solution and includes nearby locally optimal solutions. We present
some results of simulations for pseudo-Boolean functions whose optimization is equivalent to the problems of facility location,
set covering, and competitive facility location. The goal of these experiments is to obtain a comparative estimate for the
locally optimal solutions found by the standard local search algorithm and the local search algorithm using a generalized
neighborhood. 相似文献
7.
Shunji Umetani Mutsunoti Yagiura Toshihide Ibaraki 《Journal of Mathematical Modelling and Algorithms》2006,5(1):43-64
One-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises
in many industrial applications. Since the setup costs for switching different cutting patterns become more dominant in recent
cutting industry, we consider a variant of 1D-CSP, called the pattern restricted problem (PRP), to minimize the number of
stock rolls while constraining the number of different cutting patterns within a bound given by users. For this problem, we
propose a local search algorithm that alternately uses two types of local search processes with the 1-add neighborhood and
the shift neighborhood, respectively. To improve the performance of local search, we incorporate it with linear programming
(LP) techniques, to reduce the number of solutions in each neighborhood. A sensitivity analysis technique is introduced to
solve a large number of associated LP problems quickly. Through computational experiments, we observe that the new algorithm
obtains solutions of better quality than those obtained by other existing approaches. 相似文献
8.
In this paper we explore the influence of adaptive memory in the performance of heuristic methods when solving a hard combinatorial
optimization problem. Specifically, we tackle the adaptation of tabu search and scatter search to the bandwidth minimization
problem. It consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements
in a band that is as close as possible to the main diagonal. This is a classic problem, introduced in the late sixties, that
also has a well-known formulation in terms of graphs. Different exact and heuristic approaches have been proposed for the
bandwidth problem. Our contribution consists of two new algorithms, one based on the tabu search methodology and the other
based on the scatter search framework. We also present a hybrid method combining both for improved outcomes. Extensive computational
testing shows the influence of the different elements in heuristic search, such as neighborhood definition, local search,
combination methods and the use of memory. We compare our proposals with the most recent and advanced methods for this problem,
concluding that our new methods can compete with them in speed and running time. 相似文献
9.
实现快速全局优化的跨越函数方法 总被引:1,自引:0,他引:1
本文提出了一种快速求解全局优化问题的跨越函数方法,与以填充函数法为代表的一类全局优化方法相比,本文定义的跨越函数直接凸显了在求解全局优化问题时构造辅助函数的目的,更重要的是跨越函数方法能够一步跨过函数值比当前局部极小值高的区域,而直接找到原函数f(x)的位于函数值比当前局部极小值低的区域中的局部极小点,加快了全局寻优的过程,并且通过有限次迭代,找到全局最优解. 相似文献
10.
The Newton method is one of the most used methods for solving nonlinear system of equations when the Jacobian matrix is nonsingular. The method converges to a solution with Q-order two for initial points sufficiently close to the solution. The method of Halley and the method of Chebyshev are among methods that have local and cubic rate of convergence. Combining these methods with a backtracking and curvilinear strategy for unconstrained optimization problems these methods have been shown to be globally convergent. The backtracking forces a strict decrease of the function of the unconstrained optimization problem. It is shown that no damping of the step in the backtracking routine is needed close to a strict local minimizer and the global method behaves as a local method. The local behavior for the unconstrained optimization problem is investigated by considering problems with two unknowns and it is shown that there are no significant differences in the region where the global method turn into a local method for second and third order methods. Further, the final steps to reach a predefined tolerance are investigated. It is shown that the region where the higher order methods terminate in one or two iteration is significantly larger than the corresponding region for Newton’s method. 相似文献
11.
We consider a generalization of the well-known capacitated facility location problem with single source constraints in which
customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based
heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality
efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying
optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood
search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can
be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems. 相似文献
12.
Jack Brimberg Nenad Mladenović Raca Todosijević Dragan Urošević 《Optimization Letters》2017,11(2):377-388
In this paper we propose a general variable neighborhood search heuristic for solving the uncapacitated single allocation p-hub center problem (USApHCP). For the local search step we develop a nested variable neighborhood descent strategy. The proposed approach is tested on benchmark instances from the literature and found to outperform the state-of-the-art heuristic based on ant colony optimization. We also test our heuristic on large scale instances that were not previously considered as test instances for the USApHCP. Moreover, exact solutions were reached by our GVNS for all instances where optimal solutions are known. 相似文献
13.
引入了集值集值C-τ-半预不变凸概念,证明了集值集值C-τ-半预不变凸优化问题的局部弱有效元是弱有效元,给出了集值预不变凸变分不等式作为集值C-τ-半预不变凸优化问题的充分条件和必要条件,这些结果推广了文[1-4]的相应结果。 相似文献
14.
Dionne M. Aleman Arvind Kumar Ravindra K. Ahuja H. Edwin Romeijn James F. Dempsey 《Journal of Global Optimization》2008,42(4):587-607
The intensity modulated radiation therapy (IMRT) treatment planning problem consists of several subproblems which are typically
solved sequentially. We seek to combine two of the subproblems: the beam orientation optimization (BOO) problem and the fluence
map optimization (FMO) problem. The BOO problem is the problem of selecting the beam orientations to deliver radiation to
the patient. The FMO problem is the problem of determining the amount of radiation intensity, or fluence, of each beamlet
in each beam. The solution to the FMO problem measures the quality of a beam set, but the majority of previous BOO studies
rely on heuristics and approximations to gauge the quality of the beam set. In contrast with these studies, we use an exact
measure of the treatment plan quality attainable using a given beam set, which ensures convergence to a global optimum in
the case of our simulated annealing algorithm and a local optimum in the case of our local search algorithm. We have also
developed a new neighborhood structure that allows for faster convergence using our simulated annealing and local search algorithms,
thus reducing the amount of time required to obtain a good solution. Finally, we show empirically that we can generate clinically
acceptable treatment plans that require fewer beams than in current practice. This may reduce the length of treatment time,
which is an important clinical consideration in IMRT. 相似文献
15.
Arnaud Liefooghe Jérémie Humeau Salma Mesmoudi Laetitia Jourdan El-Ghazali Talbi 《Journal of Heuristics》2012,18(2):317-352
This paper discusses simple local search approaches for approximating the efficient set of multiobjective combinatorial optimization
problems. We focus on algorithms defined by a neighborhood structure and a dominance relation that iteratively improve an
archive of nondominated solutions. Such methods are referred to as dominance-based multiobjective local search. We first provide
a concise overview of existing algorithms, and we propose a model trying to unify them through a fine-grained decomposition.
The main problem-independent search components of dominance relation, solution selection, neighborhood exploration and archiving
are largely discussed. Then, a number of state-of-the-art and original strategies are experimented on solving a permutation
flowshop scheduling problem and a traveling salesman problem, both on a two- and a three-objective formulation. Experimental
results and a statistical comparison are reported in the paper, and some directions for future research are highlighted. 相似文献
16.
It is proved that the iterative sequence constructed by the Basic Trust-Region Algorithm (see Conn et al. in Trust-region methods, MPS-SIAM series on optimization, Philadelphia, 2000), which uses the Cauchy point method, is locally stable and linearly convergent in a neighborhood of a nonsingular local minimizer. 相似文献
17.
The design of effective neighborhood structures is fundamentally important for creating better local search and metaheuristic
algorithms for combinatorial optimization. Significant efforts have been made to develop larger and more powerful neighborhoods
that are able to explore the solution space more effectively while keeping computation complexity within acceptable levels.
The most important advances in this domain derive from dynamic and adaptive neighborhood constructions originating in ejection
chain methods and a special form of a candidate list design that constitutes the core of the filter-and-fan method. The objective
of this paper is to lay out the general framework of the ejection chain and filter-and-fan methods and present applications
to a number of important combinatorial optimization problems. The features of the methods that make them effective in these
applications are highlighted to provide insights into solving challenging problems in other settings. 相似文献
18.
Patric R. J.
stergrd 《组合设计杂志》1997,5(1):71-80
The problem of finding good covering codes in Hamming spaces is considered. Many different local search methods have been used to find packing codes (the dual problem), whereas practically all published results on searches for covering codes are based on simulated annealing. In this article tabu search is evaluated and compared against the simulated annealing method. A novel neighborhood function is also presented. The combination of a new optimization method and a new neighborhood function turns out to speed up the search for covering codes remarkably compared to the traditional simulated annealing approach. Using the new approach, the best known upper bound for the football pool problem for 9 matches is improved to 1341. © 1997 John Wiley & Sons, Inc. 相似文献
19.
《Mathematical Methods in the Applied Sciences》2018,41(9):3414-3429
This work studies a nonlinear inverse problem of reconstructing the diffusion coefficient in a parabolic‐elliptic system using the final measurement data, which has important application in a large field of applied science. Being different from other works, which are governed by single partial differential equations, the underlying mathematical model in this paper is a coupled parabolic‐elliptic system, which makes theoretical analysis rather difficult. On the basis of the optimal control framework, the identification problem is transformed into an optimization problem. Then the existence of the minimizer is proved, and the necessary condition that must be satisfied by the minimizer is also given. Since the optimal control problem is nonconvex, one may not expect a unique solution universally. However, the local uniqueness and stability of the minimizer are deduced in this paper. 相似文献
20.
The effectiveness of local search algorithms on discrete optimization problems is influenced by the choice of the neighborhood function. A neighborhood function that results in all local minima being global minima is said to have zero L-locals. A polynomially sized neighborhood function with zero L-locals would ensure that at each iteration, a local search algorithm would be able to find an improving solution or conclude that the current solution is a global minimum. This paper presents a recursive relationship for computing the number of neighborhood functions over a generic solution space that results in zero L-locals. Expressions are also given for the number of tree neighborhood functions with zero L-locals. These results provide a first step towards developing expressions that are applicable to discrete optimization problems, as well as providing results that add to the collection of solved graphical enumeration problems. 相似文献