On Uniform Covering, Adaptive Random Search and Raspberries

The problem of generating a random sample over a level set, called Uniform Covering, is considered. A variant is discussed of an algorithm known as Pure Adaptive Search which is a global optimisation ideal with a desirable complexity. The algorithm of Uniform Covering by Probabilistic Rejection is discussed as an approach to the practical realisation of PAS. Consequences for the complexity and practical performance in comparison to other algorithms are illustrated.     

Towards Pure Adaptive Search

The algorithm known as Pure Adaptive Search is a global optimisation ideal with desirable complexity. In this paper we temper it to a framework we term Somewhat Adaptive Search. This retains the desirable complexity, but allows scope for a practical realisation. We introduce a new algorithm termed Pure Localisation Search which attempts to reach the practical ideal. For a certain class of one variable functions the gap is bridged.     

On success rates for controlled random search

Controlled Random Search (CRS) is a simple population based algorithm which despite its attractiveness for practical use, has never been very popular among researchers on Global Optimization due to the difficulties in analysing the algorithm. In this paper, a framework to study the behaviour of algorithms in general is presented and embedded into the context of our view on questions in Global Optimization. By using as a reference a theoretical ideal algorithm called N-points Pure Adaptive Search (NPAS) some new analytical results provide bounds on speed of convergence and the Success Rate of CRS in the limit once it has settled down into simple behaviour. To relate the performance of the algorithm to characteristics of functions to be optimized, constructed simple test functions, called extreme cases, are used.     

Performance Analysis of Cyclical Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Measures for assessing the finite-time performance of GHC algorithms have been developed using this framework, including the expected number of iterations to visit a predetermined objective function value level. This paper analyzes how the expected number of iterations to visit a predetermined objective function value level can be estimated for cyclical simulated annealing. Cyclical simulated annealing uses a cooling schedule that cycles through a set of temperature values. Computational results with traveling salesman problem instances taken from TSPLIB show how the expected number of iterations to visit solutions with predetermined objective function levels can be estimated for cyclical simulated annealing.AMS 2000 Subject Classification 90-08 Computational Methods: Local Search, 90C59 Heuristics: Simulated Annealing     

Approximated algorithms for the minimum dilation triangulation problem

The complexity status of the minimum dilation triangulation (MDT) problem for a general point set is unknown. Therefore, we focus on the development of approximated algorithms to find high quality triangulations of minimum dilation. For an initial approach, we design a greedy strategy able to obtain approximate solutions to the optimal ones in a simple way. We also propose an operator to generate the neighborhood which is used in different algorithms: Local Search, Iterated Local Search, and Simulated Annealing. Besides, we present an algorithm called Random Local Search where good and bad solutions are accepted using the previous mentioned operator. For the experimental study we have created a set of problem instances since no reference to benchmarks for these problems were found in the literature. We use the sequential parameter optimization toolbox for tuning the parameters of the SA algorithm. We compare our results with those obtained by the OV-MDT algorithm that uses the obstacle value to sort the edges in the constructive process. This is the only available algorithm found in the literature. Through the experimental evaluation and statistical analysis, we assess the performance of the proposed algorithms using this operator.     

Stopping and restarting strategy for stochastic sequential search in global optimization

Two common questions when one uses a stochastic global optimization algorithm, e.g., simulated annealing, are when to stop a single run of the algorithm, and whether to restart with a new run or terminate the entire algorithm. In this paper, we develop a stopping and restarting strategy that considers tradeoffs between the computational effort and the probability of obtaining the global optimum. The analysis is based on a stochastic process called Hesitant Adaptive Search with Power-Law Improvement Distribution (HASPLID). HASPLID models the behavior of stochastic optimization algorithms, and motivates an implementable framework, Dynamic Multistart Sequential Search (DMSS). We demonstrate here the practicality of DMSS by using it to govern the application of a simple local search heuristic on three test problems from the global optimization literature.     

Global Optimization Using Diffusion Perturbations with Large Noise Intensity

This work develops an algorithm for global optimization.The algorithm is of gradient ascent typeand uses random perturbations.In contrast to the annealing type procedurcs,the perturbation noise intensityis large.We demonstrate that by properly varying the noise intensity,approximations to the global maximumcan be achieved.We also show that the expected time to reach the domain of attraction of the global maximum,which can be approximated by the solution of a boundary value problem,is finite.Discrete-time algorithmsare proposed;recursive algorithms with occasional perturbations involving large noise intensity are developed.Numerical examples are provided for illustration.     

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.     

A novel hybrid algorithm combining hunting search with harmony search algorithm for training neural networks

Neural networks (NNs) are one of the most widely used techniques for pattern classification. Owing to the most common back-propagation training algorithm of NN being extremely computationally intensive and it having some drawbacks, such as converging into local minima, many meta-heuristic algorithms have been applied to training of NNs. This paper presents a novel hybrid algorithm which is the integration of Harmony Search (HS) and Hunting Search (HuS) algorithms, called h_HS-HuS, in order to train Feed-Forward Neural Networks (FFNNs) for pattern classification. HS and HuS algorithms are recently proposed meta-heuristic algorithms inspired from the improvisation process of musicians and hunting of animals, respectively. Harmony search builds up the main structure of the hybrid algorithm, and HuS forms the pitch adjustment phase of the HS algorithm. The performance proposed algorithm is compared to conventional and meta-heuristic algorithms. Empirical tests are carried out by training NNs on nine widely used classification benchmark problems. The experimental results show that the proposed hybrid harmony-hunting algorithm is highly capable of training NNs.     

Comparing local search metaheuristics for the maximum diversity problem

The Maximum Diversity Problem (MDP) requires to extract a subset M of given cardinality from a set N, maximising the sum of the pair-wise diversities between the extracted elements. The MDP has recently been the subject of much research, and several sophisticated heuristics have been proposed to solve it. The present work compares four local search metaheuristics for the MDP, all based on the same Tabu Search procedure, with the aim to identify what additional elements provide the strongest improvement. The four metaheuristics are an Exploring Tabu Search, a Scatter Search, a Variable Neighbourhood Search and a simple Random Restart algorithm. All of them prove competitive with the best algorithms proposed in the literature. Quite surprisingly, the best ones are the simple Random Restart algorithm and a Variable Neighbourhood Search algorithm with an unusual parameter setting, which makes it quite close to random restart. Although this is probably related to the elementary structure of the MDP, it also suggests that, more often than expected, simpler algorithms might be better.     

Balancing global and local search in parallel efficient global optimization algorithms

Most parallel efficient global optimization (EGO) algorithms focus only on the parallel architectures for producing multiple updating points, but give few attention to the balance between the global search (i.e., sampling in different areas of the search space) and local search (i.e., sampling more intensely in one promising area of the search space) of the updating points. In this study, a novel approach is proposed to apply this idea to further accelerate the search of parallel EGO algorithms. In each cycle of the proposed algorithm, all local maxima of expected improvement (EI) function are identified by a multi-modal optimization algorithm. Then the local EI maxima with value greater than a threshold are selected and candidates are sampled around these selected EI maxima. The results of numerical experiments show that, although the proposed parallel EGO algorithm needs more evaluations to find the optimum compared to the standard EGO algorithm, it is able to reduce the optimization cycles. Moreover, the proposed parallel EGO algorithm gains better results in terms of both number of cycles and evaluations compared to a state-of-the-art parallel EGO algorithm over six test problems.     

基于偏最小二乘变换与Kriging模型的全局优化方法

针对传统Kriging模型在多变量(高维)输入全局优化中因超参数过多而引发收敛速度慢,精度低,建模效率不高问题,提出了基于偏最小二乘变换技术和Kriging模型的有效全局优化方法.首先,构造偏最小二乘高斯核函数;其次,借助差分进化算法寻找满足期望改进准则最大化条件的新样本点;然后,将不同核函数和期望改进准则组合,构建四种有效全局优化算法并进行比较;最后,数值算例结果表明,基于偏最小二乘变换的Kriging全局优化方法在解决高维全局优化问题方面相比于标准的全局优化算法在收敛精度及收敛速度方面更具优势.     

Are Branch and Bound and A* Algorithms Identical?

Heuristic Search and Branch and Bound algorithms have many similarities. In this paper, we address the question of the extent to which they are similar. We firstly show that these algorithms apply the same principles, although generating graphs with different properties: Heuristic Search can explore any kind of graphs, whereas the Branch and Bound algorithm generates particular graphs with a restrictive inheritance property. Nevertheless, we show that the Branch and Bound principles can be used to perform Heuristic Search. We conclude that the two types of algorithms are therefore essentially identical; they only differ at the interpretation level.     

The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSAT problems

Heuristic algorithms, especially hill-climbing algorithms, are prone to being trapped by local optimization. Many researchers have focused on analyzing convergence and runtime of some heuristic algorithms on SAT-solving problems. However, there is rare work on analyzing success ratio (the ratio of the number of runs that find the global maxima of optimization versus the total runs) and expected fitness at each generation. Expected fitness at each generation could lead us to better understand the expected fitness of a heuristic algorithm could find on the problem to be solve at a certain generation. Success ratio help us understand with what a probability a heuristic algorithm could find the global optimization of the problem to be solved. So, this paper analyzed expected fitness and success ratio of two hill-climbing algorithms on two bimodal MaxSAT problems by using Markov chain. The theoretical and experimental results showed that though hill-climbing algorithms (both hill-climbing RandomWalk and Local (1+1)EA) converged faster, they could not always find global maxima of bimodal SAT-solving problems. The success ratios of hill-climbing algorithms usually have their own limits. The limit of success ratio is dependent on the SAT-solving problem itself and the expected distribution of initial bit string, and independent on whether hill-climbing RandomWalk or Local (1+1)EA is used.     

Pure adaptive search for finite global optimization

Pure Adaptive Search is a stochastic algorithm which has been analyzed for continuous global optimization. When a uniform distribution is used in PAS, it has been shown to have complexity which is linear in dimension. We define strong and weak variations of PAS in the setting of finite global optimization and prove analogous results. In particular, for then-dimensional lattice {1,,k} ⁿ , the expected number of iterations to find the global optimum is linear inn. Many discrete combinatorial optimization problems, although having intractably large domains, have quite small ranges. The strong version of PAS for all problems, and the weak version of PAS for a limited class of problems, has complexity the order of the size of the range.The authors would like to thank the Department of Mathematics and Statistics at the University of Canterbury for support of this research.     

Hesitant adaptive search for global optimisation

Pure adaptive search is a stochastic algorithm which has been analysed in distinct ways for finite and continuous global optimisation. In this paper, motivated by the behaviour of practical algorithms such as simulated annealing, we extend these ideas. We present a unified theory which yields both the finite and continuous results for pure adaptive search. At the same time, we allow our extended algorithm to hesitate before improvement continues. Results are obtained for the expected number of iterations to convergence for such an algorithm. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

基于引力搜索和粒子群混合优化算法的证券投资组合问题研究

本文研究考虑交易成本的投资组合模型,分别以风险价值(VAR)和夏普比率(SR)作为投资组合的风险评价指标和效益评价指标。为有效求解此模型,本文在引力搜索和粒子群算法的基础上提出了一种混合优化算法(IN-GSA-PSO),将粒子群算法的群体最佳位置和个体最佳位置与引力搜索算法的加速度算子有机结合,使混合优化算法充分发挥单一算法的开采能力和探索能力。通过对算法相关参数的合理设置,算法能够达到全局搜索和局部搜索的平衡,快速收敛到模型的最优解。本文选取上证50股2014年下半年126个交易日的数据,运用Matlab软件进行仿真实验,实验结果显示,考虑交易成本的投资组合模型可使投资者得到更高的收益率。研究同时表明,基于PSO和GSA的混合算法在求解投资组合模型时比单一算法具有更好的性能,能够得到满意的优化结果。     

A Mixed Heuristic for Circuit Partitioning

As general-purpose parallel computers are increasingly being used to speed up different VLSI applications, the development of parallel algorithms for circuit testing, logic minimization and simulation, HDL-based synthesis, etc. is currently a field of increasing research activity. This paper describes a circuit partitioning algorithm which mixes Simulated Annealing (SA) and Tabu Search (TS) heuristics. The goal of such an algorithm is to obtain a balanced distribution of the target circuit among the processors of the multicomputer allowing a parallel CAD application for Test Pattern Generation to provide good efficiency. The results obtained indicate that the proposed algorithm outperforms both a pure Simulated Annealing and a Tabu Search. Moreover, the usefulness of the algorithm in providing a balanced workload distribution is demonstrated by the efficiency results obtained by a topological partitioning parallel test-pattern generator in which the proposed algorithm has been included. An extented algorithm that works with general graphs to compare our approach with other state of the art algorithms has been also included.     

基于乌鸦喝水的元启发式优化算法

启发式优化算法已成为求解复杂优化问题的一种有效方法,可用于解决传统的优化方法难以求解的问题.受乌鸦喝水寓言故事启发,提出一种新型元启发式优化算法—乌鸦喝水算法,首先建立了乌鸦喝水算法数学模型;其次,给出实现该算法的详细步骤;最后,将该算法用于基准函数优化,并将该算法与乌鸦搜索算法、粒子群优化算法、多元宇宙优化算法、花授粉算法、布谷鸟算法等群智能算法进行了比较.仿真实验结果表明,乌鸦喝水算法优于其他算法.     

Analysis of recursive batched interpolation search

For an ordered file of records with uniformly distributed key values, we examine an existing batched searching algorithm based on recursive use of interpolation searches. The algorithm, called Recursive Batched Interpolation Search (RBIS) in this paper, uses a divide-and-conquer technique for batched searching. The expected-case complexity of the algorithm is shown to beO(m loglog (2n/m) +m), wheren is the size of the file andm is the size of the query batch. Simulations are performed to demonstrate the savings of batched searching using RBIS. Also, simulations are performed to compare alternative batched searching algorithms which are based on either interpolation search or binary search. When the file's key values are uniformly distributed, the simulation results confirm that interpolation-search based algorithms are superior to binary-search based algorithms. However, when the file's key values are not uniformly distributed, a straight-forward batched interpolation search deteriorates quickly as the batch size increases, but algorithm RBIS still outperforms binary-search based algorithms when the batch size passes a threshold value.