A global optimization method for the molecular replacement problem in X-ray crystallography

The primary technique for determining the three-dimensional structure of a protein molecule is X-ray crystallography, from which the molecular replacement (MR) problem often arises as a critical step. The MR problem is a global optimization problem to locate an optimal position of a model protein so that at this position the model will produce calculated intensities closest to those observed from an X-ray crystallography experiment involving a protein with unknown but similar atomic structure. Improving the applicability and robustness of MR methods is an important research topic because commonly used traditional MR methods, though often successful, have their limitations in solving difficult problems.We introduce a new global optimization strategy that combines a coarse-grid search, using a surrogate function, with extensive multi-start local optimization. A new MR code, called SOMoRe, based on this strategy is developed and tested on four realistic problems, including two difficult problems that traditional MR codes failed to solve directly. SOMoRe was able to solve each test problem without any complication, and SOMoRe solved an MR problem using a less complete model than the models required by three other programs. These results indicate that the new method is promising and should enhance the applicability and robustness of the MR methodology.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

A self-adaptive global best harmony search algorithm for continuous optimization problems

This paper presents a self-adaptive global best harmony search (SGHS) algorithm for solving continuous optimization problems. In the proposed SGHS algorithm, a new improvisation scheme is developed so that the good information captured in the current global best solution can be well utilized to generate new harmonies. The harmony memory consideration rate (HMCR) and pitch adjustment rate (PAR) are dynamically adapted by the learning mechanisms proposed. The distance bandwidth (BW) is dynamically adjusted to favor exploration in the early stages and exploitation during the final stages of the search process. Extensive computational simulations and comparisons are carried out by employing a set of 16 benchmark problems from literature. The computational results show that the proposed SGHS algorithm is more effective in finding better solutions than the state-of-the-art harmony search (HS) variants.     

SPT: a stochastic tunneling algorithm for global optimization

A stochastic approach to solving unconstrained continuous-function global optimization problems is presented. It builds on the tunneling approach to deterministic optimization presented by Barhen and co-workers (Bahren and Protopopescu, in: State of the Art in Global Optimization, Kluwer, 1996; Barhen et al., Floudas and Pardalos (eds.), TRUST: a deterministic algorithm for global optimization, 1997) by combining a series of local descents with stochastic searches. The method uses a rejection-based stochastic procedure to locate new local minima descent regions and a fixed Lipschitz-like constant to reject unpromising regions in the search space, thereby increasing the efficiency of the tunneling process. The algorithm is easily implemented in low-dimensional problems and scales easily to large problems. It is less effective without further heuristics in these latter cases, however. Several improvements to the basic algorithm which make use of approximate estimates of the algorithms parameters for implementation in high-dimensional problems are also discussed. Benchmark results are presented, which show that the algorithm is competitive with the best previously reported global optimization techniques. A successful application of the approach to a large-scale seismology problem of substantial computational complexity using a low-dimensional approximation scheme is also reported.     

A counterexample to a global optimization algorithm

A counterexample to an algorithm of Dien (1988) for solving a minimization problem with a quasiconcave objective function and both linear and a reverse-convex constraint shows that this algorithm needn't lead to a solution of the given problem.     

A new genetic algorithm for global optimization of multimodal continuous functions

In this paper a new genetic algorithm is developed to find the near global optimal solution of multimodal nonlinear optimization problems. The algorithm defined makes use of a real encoded crossover and mutation operator. The performance of GA is tested on a set of twenty-seven nonlinear global optimization test problems of variable difficulty level. Results are compared with some well established popular GAs existing in the literature. It is observed that the algorithm defined performs significantly better than the existing ones.     

A Metropolis algorithm combined with Hooke-Jeeves local search method applied to global optimization

A hybridization of a recently introduced Metropolis algorithm named the Particle Collision Algorithm (PCA) and the Hooke-Jeeves local search method is applied to a testbed of global optimization functions and to real-world chemical equilibrium nonlinear systems. The results obtained by this method, called HJPCA, are compared against those achieved by two state-of-the-art global optimization methods, C-GRASP and GLOBAL. HJPCA performs better than both algorithms, thus demonstrating its potential for other applications.     

Convergence guarantees for generalized adaptive stochastic search methods for continuous global optimization

This paper presents some simple technical conditions that guarantee the convergence of a general class of adaptive stochastic global optimization algorithms. By imposing some conditions on the probability distributions that generate the iterates, these stochastic algorithms can be shown to converge to the global optimum in a probabilistic sense. These results also apply to global optimization algorithms that combine local and global stochastic search strategies and also those algorithms that combine deterministic and stochastic search strategies. This makes the results applicable to a wide range of global optimization algorithms that are useful in practice. Moreover, this paper provides convergence conditions involving the conditional densities of the random vector iterates that are easy to verify in practice. It also provides some convergence conditions in the special case when the iterates are generated by elliptical distributions such as the multivariate Normal and Cauchy distributions. These results are then used to prove the convergence of some practical stochastic global optimization algorithms, including an evolutionary programming algorithm. In addition, this paper introduces the notion of a stochastic algorithm being probabilistically dense in the domain of the function and shows that, under simple assumptions, this is equivalent to seeing any point in the domain with probability 1. This, in turn, is equivalent to almost sure convergence to the global minimum. Finally, some simple results on convergence rates are also proved.     

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.     

A global optimization problem in portfolio selection

This paper deals with the issue of buy-in thresholds in portfolio optimization using the Markowitz approach. Optimal values of invested fractions calculated using, for instance, the classical minimum-risk problem can be unsatisfactory in practice because they lead to unrealistically small holdings of certain assets. Hence we may want to impose a discrete restriction on each invested fraction y _i such as y _i >  y _min or y _i =  0. We shall describe an approach which uses a combination of local and global optimization to determine satisfactory solutions. The approach could also be applied to other discrete conditions—for instance when assets can only be purchased in units of a certain size (roundlots).     

Imperialist competitive algorithm combined with chaos for global optimization

A novel chaotic improved imperialist competitive algorithm (CICA) is presented for global optimization. The ICA is a new meta-heuristic optimization developed based on a socio-politically motivated strategy and contains two main steps: the movement of the colonies and the imperialistic competition. Here different chaotic maps are utilized to improve the movement step of the algorithm. Seven different chaotic maps are investigated and the Logistic and Sinusoidal maps are found as the best choices. Comparing the new algorithm with the other ICA-based methods demonstrates the superiority of the CICA for the benchmark functions.     

Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints

In this paper, Lipschitz univariate constrained global optimization problems where both the objective function and constraints can be multiextremal are considered. The constrained problem is reduced to a discontinuous unconstrained problem by the index scheme without introducing additional parameters or variables. A Branch-and-Bound method that does not use derivatives for solving the reduced problem is proposed. The method either determines the infeasibility of the original problem or finds lower and upper bounds for the global solution. Not all the constraints are evaluated during every iteration of the algorithm, providing a significant acceleration of the search. Convergence conditions of the new method are established. Extensive numerical experiments are presented.     

Optimality condition and algorithm with deviation integral for global optimization

To study the integral global minimization, a general form of deviation integral is introduced and its properties are examined in this work. In terms of the deviation integral, optimality condition and algorithms are given. Algorithms are implemented by a properly designed Monte Carlo simulation. Numerical tests are given to show the effectiveness of the method.     

A Bayesian algorithm for global optimization

A crucial step in global optimization algorithms based on random sampling in the search domain is decision about the achievement of a prescribed accuracy. In order to overcome the difficulties related to such a decision, the Bayesian Nonparametric Approach has been introduced. The aim of this paper is to show the effectiveness of the approach when an ad hoc clustering technique is used for obtaining promising starting points for a local search algorithm. Several test problems are considered.     

Optimal and sub-optimal stopping rules for the Multistart algorithm in global optimization

In this paper the problem of stopping the Multistart algorithm for global optimization is considered. The algorithm consists of repeatedly performing local searches from randomly generated starting points. The crucial point in this algorithmic scheme is the development of a stopping criterion; the approach analyzed in this paper consists in stopping the sequential sampling as soon as a measure of the trade-off between the cost of further local searches is greater than the expected benefit, i.e. the possibility of discovering a better optimum.Stopping rules are thoroughly investigated both from a theoretical point of view and from a computational one via extensive simulation. This latter clearly shows that the simple1-step look ahead rule may achieve surprisingly good results in terms of computational cost vs. final accuracy.The research of the second author was partially supported by Progetto MPI 40% Metodi di Ottimizzazione per le Decisioni.     

A fast Pareto genetic algorithm approach for solving expensive multiobjective optimization problems

We present a new multiobjective evolutionary algorithm (MOEA), called fast Pareto genetic algorithm (FastPGA), for the simultaneous optimization of multiple objectives where each solution evaluation is computationally- and/or financially-expensive. This is often the case when there are time or resource constraints involved in finding a solution. FastPGA utilizes a new ranking strategy that utilizes more information about Pareto dominance among solutions and niching relations. New genetic operators are employed to enhance the proposed algorithm’s performance in terms of convergence behavior and computational effort as rapid convergence is of utmost concern and highly desired when solving expensive multiobjective optimization problems (MOPs). Computational results for a number of test problems indicate that FastPGA is a promising approach. FastPGA yields similar performance to that of the improved nondominated sorting genetic algorithm (NSGA-II), a widely-accepted benchmark in the MOEA research community. However, FastPGA outperforms NSGA-II when only a small number of solution evaluations are permitted, as would be the case when solving expensive MOPs.     

On initial populations of a genetic algorithm for continuous optimization problems

Genetic algorithms are commonly used metaheuristics for global optimization, but there has been very little research done on the generation of their initial population. In this paper, we look for an answer to the question whether the initial population plays a role in the performance of genetic algorithms and if so, how it should be generated. We show with a simple example that initial populations may have an effect on the best objective function value found for several generations. Traditionally, initial populations are generated using pseudo random numbers, but there are many alternative ways. We study the properties of different point generators using four main criteria: the uniform coverage and the genetic diversity of the points as well as the speed and the usability of the generator. We use the point generators to generate initial populations for a genetic algorithm and study what effects the uniform coverage and the genetic diversity have on the convergence and on the final objective function values. For our tests, we have selected one pseudo and one quasi random sequence generator and two spatial point processes: simple sequential inhibition process and nonaligned systematic sampling. In numerical experiments, we solve a set of 52 continuous test functions from 16 different function families, and analyze and discuss the results.     

A multiobjective evolutionary algorithm for approximating the efficient set

In this article, a new framework for evolutionary algorithms for approximating the efficient set of a multiobjective optimization (MOO) problem with continuous variables is presented. The algorithm is based on populations of variable size and exploits new elite preserving rules for selecting alternatives generated by mutation and recombination. Together with additional assumptions on the considered MOO problem and further specifications on the algorithm, theoretical results on the approximation quality such as convergence in probability and almost sure convergence are derived.     

On the convergence of global methods in multiextremal optimization

A general class of derivative-free optimization procedures is presented including the corresponding convergence theory. This theory turns out to be very constructive, in the sense that the convergence conditions not only can be verified easily for many existing algorithms, but also allow one to construct new procedures. It is shown that popular methods such as branch-and-bound concepts, Pintér's general class of procedures, the algorithms of Pijavskii, Shubert, and Mladineo, and the approach of Zheng and Galperin can not only be subsumed under this class of methods, but also partly be improved by regarding them within the framework presented.     

A dynamic clustering based differential evolution algorithm for global optimization

A dynamic clustering based differential evolution algorithm (CDE) for global optimization is proposed to improve the performance of the differential evolution (DE) algorithm. With population evolution, CDE algorithm gradually changes from exploring promising areas at the early stages to exploiting solution with high precision at the later stages. Experiments on 28 benchmark problems, including 13 high dimensional functions, show that the new method is able to find near optimal solutions efficiently. Compared with other existing algorithms, CDE improves solution accuracy with less computational effort.