Global optimization algorithms for a CAD workstation

This paper describes two new versions of the controlled random search procedure for global optimization (CRS). Designed primarily to suit the user of a CAD workstation, these algorithms can also be used effectively in other contexts. The first, known as CRS3, speeds the final convergence of the optimization by combining a local optimization algorithm with the global search procedure. The second, called CCRS, is a concurrent version of CRS3. This algorithm is intended to drive an optimizing accelerator, based on a concurrent processing architecture, which can be attached to a workstation to achieve a significant increase in speed. The results are given of comparative trials which involve both unconstrained and constrained optimization.This work was funded by the Science and Engineering Research Council.     

Some Variants of the Controlled Random Search Algorithm for Global Optimization

We suggested some modifications to the controlled random search (CRS) algorithm for global optimization. We introduce new trial point generation schemes in CRS, in particular, point generation schemes using linear interpolation and mutation. Central to our modifications is the probabilistic adaptation of point generation schemes within the CRS algorithm.A numerical study is carried out using a set of 50 test problems many of which are inspired by practical applications. Numerical experiments indicate that the resulting algorithms are considerably better than the previous versions. Thus, they offer a reasonable alternative to many currently available stochastic algorithms, especially for problems requiring direct search type methods.     

Two Strategies of Adaptive Cluster Covering with Descent and Their Comparison to Other Algorithms

Two strategies of randomized search, namely adaptive cluster covering (ACCO), and adaptive cluster covering with descent (ACD), are introduced and positioned in the group of the global optimization techniques. Several algorithms based on these new strategies are compared with other techniques of global randomized search in terms of effectiveness, efficiency and reliability. The other techniques include two versions of multistart, two versions of the controlled random search (CRS2 and CRS4) and the canonical genetic algorithm. Thirteen minimization problems including two parameter identification problems (for a flexible membrane mirror model and a hydrologic model) are solved. The algorithm ACCO, and a version of CRS4 algorithm (Ali and Storey 1994) show the highest efficiency, effectiveness and reliability. The second new algorithm, ACD, is in some runs very efficient and effective, but its reliability needs further improvement.     

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.     

General variable neighborhood search for the continuous optimization

We suggest a new heuristic for solving unconstrained continuous optimization problems. It is based on a generalized version of the variable neighborhood search metaheuristic. Different neighborhoods and distributions, induced from different metrics are ranked and used to get random points in the shaking step. We also propose VNS for solving constrained optimization problems. The constraints are handled using exterior point penalty functions within an algorithm that combines sequential and exact penalty transformations. The extensive computer analysis that includes the comparison with genetic algorithm and some other approaches on standard test functions are given. With our approach we obtain encouraging results.     

基于模拟退火的CRS算法

本文是对非线性规划问题提出的一种算法,该算法把模拟退火算法应用到CRS算法中,根据模拟退火算法每一次迭代都体现集中和扩散两个策略的平衡的特点,使CRS算法更能够搜索到全局最优解,而不会陷入局部最优解。最后把提出的算法应用到两个典型的函数优化问题中,结果表明,算法是可行的、有效的     

Speeding up continuous GRASP

Continuous GRASP (C-GRASP) is a stochastic local search metaheuristic for finding cost-efficient solutions to continuous global optimization problems subject to box constraints (Hirsch et al., 2007). Like a greedy randomized adaptive search procedure (GRASP), a C-GRASP is a multi-start procedure where a starting solution for local improvement is constructed in a greedy randomized fashion. In this paper, we describe several improvements that speed up the original C-GRASP and make it more robust. We compare the new C-GRASP with the original version as well as with other algorithms from the recent literature on a set of benchmark multimodal test functions whose global minima are known. Hart’s sequential stopping rule (1998) is implemented and C-GRASP is shown to converge on all test problems.     

Shuffled complex evolution approach for effective and efficient global minimization

The degree of difficulty in solving a global optimization problem is in general dependent on the dimensionality of the problem and certain characteristics of the objective function. This paper discusses five of these characteristics and presents a strategy for function optimization called the shuffled complex evolution (SCE) method, which promises to be robust, effective, and efficient for a broad class of problems. The SCE method is based on a synthesis of four concepts that have proved successful for global optimization: (a) combination of probabilistic and deterministic approaches; (b) clustering; (c) systematic evolution of a complex of points spanning the space, in the direction of global improvement; and (d) competitive evolution. Two algorithms based on the SCE method are presented. These algorithms are tested by running 100 randomly initiated trials on eight test problems of differing difficulty. The performance of the two algorithms is compared to that of the controlled random search CRS2 method presented by Price (1983, 1987) and to a multistart algorithm based on the simplex method presented by Nelder and Mead (1965).This work was partially funded by the National Science Foundation, Grant ECE-86-10584, and by the National Weather Service, Grant NA85AA-H-HY088.     

A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems

In this paper, a computational algorithm, named RST2ANU algorithm, has been developed for solving integer and mixed integer global optimization problems. This algorithm, which primarily is based on the original controlled random search approach of Price [22i], incorporates a simulated annealing type acceptance criterion in its working so that not only downhill moves but also occasional uphill moves can be accepted. In its working it employs a special truncation procedure which not only ensures that the integer restrictions imposed on the decision variables are satisfied, but also creates greater possibilities for the search leading to a global optimal solution. The reliability and efficiency of the proposed RST2ANU algorithm has been demonstrated on thirty integer and mixed integer optimization problems taken from the literature. The performance of the algorithm has been compared with the performance of the corresponding purely controlled random search based algorithm as well as the standard simulated annealing algorithm. The performance of the method on mathematical models of three realistic problems has also been demonstrated.     

A real coded genetic algorithm for solving integer and mixed integer optimization problems

In this paper, a real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep, M. Thakur, A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation 188 (2007) 895-912; K. Deep, M. Thakur, A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation 193 (2007) 211-230]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. Performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of genetic algorithm and also with random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered.