A particle swarm pattern search method for bound constrained global optimization

In this paper we develop, analyze, and test a new algorithm for the global minimization of a function subject to simple bounds without the use of derivatives. The underlying algorithm is a pattern search method, more specifically a coordinate search method, which guarantees convergence to stationary points from arbitrary starting points. In the optional search phase of pattern search we apply a particle swarm scheme to globally explore the possible nonconvexity of the objective function. Our extensive numerical experiments showed that the resulting algorithm is highly competitive with other global optimization methods also based on function values. Support for Luís N. Vicente was provided by Centro de Matemática da Universidade de Coimbra and by FCT under grant POCI/MAT/59442/2004.     

Experimental Testing of Advanced Scatter Search Designs for Global Optimization of Multimodal Functions

Scatter search is an evolutionary method that, unlike genetic algorithms, operates on a small set of solutions and makes only limited use of randomization as a proxy for diversification when searching for a globally optimal solution. The scatter search framework is flexible, allowing the development of alternative implementations with varying degrees of sophistication. In this paper, we test the merit of several scatter search designs in the context of global optimization of multimodal functions. We compare these designs among themselves and choose one to compare against a well-known genetic algorithm that has been specifically developed for this class of problems. The testing is performed on a set of benchmark multimodal functions with known global minima.     

A novel three-phase trajectory informed search methodology for global optimization

A new deterministic method for solving a global optimization problem is proposed. The proposed method consists of three phases. The first phase is a typical local search to compute a local minimum. The second phase employs a discrete sup-local search to locate a so-called sup-local minimum taking the lowest objective value among the neighboring local minima. The third phase is an attractor-based global search to locate a new point of next descent with a lower objective value. The simulation results through well-known global optimization problems are shown to demonstrate the efficiency of the proposed method.     

Continuous functions minimization by dynamic random search technique

Random search technique is the simplest one of the heuristic algorithms. It is stated in the literature that the probability of finding global minimum is equal to 1 by using the basic random search technique, but it takes too much time to reach the global minimum. Improving the basic random search technique may decrease the solution time. In this study, in order to obtain the global minimum fastly, a new random search algorithm is suggested. This algorithm is called as the Dynamic Random Search Technique (DRASET). DRASET consists of two phases, which are general search and local search based on general solution. Knowledge related to the best solution found in the process of general search is kept and then that knowledge is used as initial value of local search. DRASET’s performance was experimented with 15 test problems and satisfactory results were obtained.     

Multiobjective Search Algorithm with Subdivision Technique

This paper presents a multiobjective search algorithm with subdivision technique (MOSAST) for the global solution of multiobjective constrained optimization problems with possibly noncontinuous objective or constraint functions. This method is based on a random search method and a new version of the Graef-Younes algorithm and it uses a subdivision technique. Numerical results are given for bicriterial test problems.     

Lipschitzian optimization without the Lipschitz constant

We present a new algorithm for finding the global minimum of a multivariate function subject to simple bounds. The algorithm is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. This is done by carrying out simultaneous searches using all possible constants from zero to infinity. On nine standard test functions, the new algorithm converges in fewer function evaluations than most competing methods.The motivation for the new algorithm stems from a different way of looking at the Lipschitz constant. In particular, the Lipschitz constant is viewed as a weighting parameter that indicates how much emphasis to place on global versus local search. In standard Lipschitzian methods, this constant is usually large because it must equal or exceed the maximum rate of change of the objective function. As a result, these methods place a high emphasis on global search and exhibit slow convergence. In contrast, the new algorithm carries out simultaneous searches using all possible constants, and therefore operates at both the global and local level. Once the global part of the algorithm finds the basin of convergence of the optimum, the local part of the algorithm quickly and automatically exploits it. This accounts for the fast convergence of the new algorithm on the test functions.     

变测度的积分型全局优化算法

郑权等首先提出积分-水平集求总极值的方法,实现算法中采用Monte-Carlo 随机投点产生近似水平集来缩小搜索区域范围,但这一算法可能失去总极值点．此后,邬 冬华等给出了一种修正的积分－水平集的方法,一种区域不收缩的分箱方法以保证总极 值点不被丢失．本文在此基础上采取对不同的箱子采用不同的测度这一策略,使水平值 更充分的下降,更快的达到全局极小值,以提高修正算法的计算效率．最后给出的数值算 例说明了算法是有效的．     

Global search algorithms for minimum concave-cost network flow problems

We present algorithms for the single-source uncapacitated version of the minimum concave cost network flow problem. Each algorithm exploits the fact that an extreme feasible solution corresponds to a sub-tree of the original network. A global search heuristic based on random extreme feasible initial solutions and local search is developed. The algorithm is used to evaluate the complexity of the randomly generated test problems. An exact global search algorithm is developed, based on enumerative search of rooted subtrees. This exact technique is extended to bound the search based on cost properties and linear underestimation. The technique is accelerated by exploiting the network structure.     

A novel metaheuristics approach for continuous global optimization

This paper proposes a novel metaheuristics approach to find the global optimum of continuous global optimization problems with box constraints. This approach combines the characteristics of modern metaheuristics such as scatter search (SS), genetic algorithms (GAs), and tabu search (TS) and named as hybrid scatter genetic tabu (HSGT) search. The development of the HSGT search, parameter settings, experimentation, and efficiency of the HSGT search are discussed. The HSGT has been tested against a simulated annealing algorithm, a GA under the name GENOCOP, and a modified version of a hybrid scatter genetic (HSG) search by using 19 well known test functions. Applications to Neural Network training are also examined. From the computational results, the HSGT search proved to be quite effective in identifying the global optimum solution which makes the HSGT search a promising approach to solve the general nonlinear optimization problem.     

A hybrid optimization technique coupling an evolutionary and a local search algorithm

Evolutionary algorithms are robust and powerful global optimization techniques for solving large-scale problems that have many local optima. However, they require high CPU times, and they are very poor in terms of convergence performance. On the other hand, local search algorithms can converge in a few iterations but lack a global perspective. The combination of global and local search procedures should offer the advantages of both optimization methods while offsetting their disadvantages. This paper proposes a new hybrid optimization technique that merges a genetic algorithm with a local search strategy based on the interior point method. The efficiency of this hybrid approach is demonstrated by solving a constrained multi-objective mathematical test-case.     

Desarrollo de un algoritmo de optimización global en colonias de hormigas con selección de región factible para espacios continuos

This study introduces a new algorithm for the ant colony optimization (ACO) method, which has been proposed to solve global optimization problems with continuous decision variables. This algorithm, namely ACO-FRS, involves a strategy for the selection of feasible regions during optimization search and it performs the exploration of the search space using a similar approach to that used by the ants during the search of food. Four variants of this algorithm have been tested in several benchmark problems and the results of this study have been compared with those reported in literature for other ACO-type methods for continuous spaces. Overall, the results show that the incorporation of the selection of feasible regions allows the performing of a global search to explore those regions with low level of pheromone, thus increasing the feasibility of ACO for finding the global optimal solution.     

Multistart method with estimation scheme for global satisfycing problems

We present a multistart method for solving global satisfycing problems. The method uses data generated by linearly converging local algorithms to estimate the cost value at the local minimum to which the local search is converging. When the estimate indicates that the local search is converging to a value higher than the satisfycing value, the local search is interrupted and a new local search is initiated from a randomly generated point. When the satisfycing problem is difficult and the estimation scheme is fairly accurate, the new method is superior over a straightforward adaptation of classical multistart methods.     

Global Optimization by Monotonic Transformation

This paper addresses the problem of global optimization by means of a monotonic transformation. With an observation on global optimality of functions under such a transformation, we show that a simple and effective algorithm can be derived to search within possible regions containing the global optima. Numerical experiments are performed to compare this algorithm with one that does not incorporate transformed information using several benchmark problems. These results are also compared to best known global search algorithms in the literature. In addition, the algorithm is shown to be useful for several neural network learning problems, which possess much larger parameter spaces.     

On Convergence of a P-Algorithm Based on a Statistical Model of Continuously Differentiable Functions

This paper is a study of the one-dimensional global optimization problem for continuously differentiable functions. We propose a variant of the so-called P-algorithm, originally proposed for a Wiener process model of an unknown objective function. The original algorithm has proven to be quite effective for global search, though it is not efficient for the local component of the optimization search if the objective function is smooth near the global minimizer. In this paper we construct a P-algorithm for a stochastic model of continuously differentiable functions, namely the once-integrated Wiener process. This process is continuously differentiable, but nowhere does it have a second derivative. We prove convergence properties of the algorithm.     

The convergence of conjugate gradient method with nonmonotone line search

The conjugate gradient method is a useful and powerful approach for solving large-scale minimization problems. Liu and Storey developed a conjugate gradient method, which has good numerical performance but no global convergence under traditional line searches such as Armijo line search, Wolfe line search, and Goldstein line search. In this paper we propose a new nonmonotone line search for Liu-Storey conjugate gradient method (LS in short). The new nonmonotone line search can guarantee the global convergence of LS method and has a good numerical performance. By estimating the Lipschitz constant of the derivative of objective functions in the new nonmonotone line search, we can find an adequate step size and substantially decrease the number of functional evaluations at each iteration. Numerical results show that the new approach is effective in practical computation.     

Global Optimization using Dynamic Search Trajectories

Two global optimization algorithms are presented. Both algorithms attempt to minimize an unconstrained objective function through the modeling of dynamic search trajectories. The first, namely the Snyman–Fatti algorithm, originated in the 1980's and still appears an effective global optimization algorithm. The second algorithm is currently under development, and is denoted the modified bouncing ball algorithm. For both algorithms, the search trajectories are modified to increase the likelihood of convergence to a low local minimum. Numerical results illustrate the effectiveness of both algorithms.     

Extended Global Convergence Framework for Unconstrained Optimization

An extension of the global convergence framework for unconstrained derivative-free optimization methods is presented. The extension makes it possible for the framework to include optimization methods with varying cardinality of the ordered direction set. Grid-based search methods are shown to be a special case of the more general extended global convergence framework. Furthermore,the required properties of the sequence of ordered direction sets listed in the definition of grid-based methods are relaxed and simplified by removing the requirement of structural equivalence.     

Axiomatic characterization of a global optimization algorithm and investigation of its search strategy

A new axiomatic characterization of a rational algorithm for global minimization based on a statistical model of the objective function is suggested. The globality of the search strategy of such an algorithm is investigated as well as the convergence of the algorithm.     

Cutting Angle Method and a Local Search

The paper deals with combinations of the cutting angle method in global optimization and a local search. We propose to use special transformed objective functions for each intermediate use of the cutting angle method. We report results of numerical experiments which demonstrate that the proposed approach is very beneficial in the search for a global minimum.     

A niche hybrid genetic algorithm for global optimization of continuous multimodal functions

A niche hybrid genetic algorithm (NHGA) is proposed in this paper to solve continuous multimodal optimization problems more efficiently, accurately and reliably. It provides a new architecture of hybrid algorithms, which organically merges the niche techniques and Nelder–Mead's simplex method into GAs. In the new architecture, the simplex search is first performed in the potential niches, which likely contain a global optimum, to locate the promising zones within search space, quickly and reliably. Then another simplex search is used to quickly discover the global optimum in the located promising zones. The proposed method not only makes the exploration capabilities of GAs stronger through niche techniques, but also has more powerful exploitation capabilities by using simplex search. So it effectively alleviates premature convergence and improves weak exploitation capacities of GAs. A set of benchmark functions is used to demonstrate the validity of NHGA and the role of every component of NHGA. Numerical experiments show that the NHGA may, efficiently and reliably, obtain a more accurate global optimum for the complex and high-dimension multimodal optimization problems. It also demonstrates that the new hybrid architecture is potential and can be used to generate more potential hybrid algorithms.