Dark Forest Algorithm:A Novel Metaheuristic Algorithm for Global Optimization Problems

Metaheuristic algorithms,as effective methods for solving optimization problems,have recently attracted considerable attention in science and engineering fields.They are popular and have broad applications owing to their high efficiency and low complexity.These algorithms are generally based on the behaviors observed in nature,physical sciences,or humans.This study proposes a novel metaheuristic algorithm called dark forest algorithm(DFA),which can yield improved optimization results for global optimization problems.In DFA,the population is divided into four groups:highest civilization,advanced civilization,normal civilization,and low civilization.Each civilization has a unique way of iteration.To verify DFA’s capability,the performance of DFA on 35 well-known benchmark functions is compared with that of six other metaheuristic algorithms,including artificial bee colony algorithm,firefly algorithm,grey wolf optimizer,harmony search algorithm,grasshopper optimization algorithm,and whale optimization algorithm.The results show that DFA provides solutions with improved efficiency for problems with low dimensions and outperforms most other algorithms when solving high dimensional problems.DFAis applied to five engineering projects to demonstrate its applicability.The results show that the performance of DFA is competitive to that of current well-known metaheuristic algorithms.Finally,potential upgrading routes for DFA are proposed as possible future developments.

ANew Theoretical Framework forAnalyzing Stochastic Global Optimization Algorithms

In this paper, we develop a new theoretical framework by means of the absorbing Markov process theory for analyzing some stochastic global optimization algorithms. Applying the framework to the pure random search, we prove that the pure random search converges to the global minimum in probability and its time has geometry distribution. We also analyze the pure adaptive search by this framework and turn out that the pure adaptive search converges to the global minimum in probability and its time has Poisson distribution.

A New Stochastic Algorithm of Global Optimization ——Region's Walk and Contraction

This paper presents a new stochastic algorithm for box constrained global optimization problem. Bacause the level set of objective function is always not known, the authors designed a region containing the current minimum point to replace it, and in order to fit the level set well, this region would be walking and contracting in the running process. Thus, the new algorithm is named as region's walk and contraction(RWC). Some numerical experiments for the RWC were conducted, which indicate good property of the algorithm.

Improvement of Pure Random Search in Global Optimization

In this paper, the improvement of pure random search is studied. By taking some information of the function to be minimized into consideration, the authors propose two stochastic global optimization algorithms. Some numerical experiments for the new stochastic global optimization algorithms are presented for a class of test problems.

Hybridizing grey wolf optimization with differential evolution for global optimization and test scheduling for 3D stacked SoC

A new meta-heuristic method is proposed to enhance current meta-heuristic methods for global optimization and test scheduling for three-dimensional （3D） stacked system-on-chip （SoC） by hybridizing grey wolf optimization with differential evo- lution （HGWO）. Because basic grey wolf optimization （GWO） is easy to fall into stagnation when it carries out the operation of at- tacking prey, and differential evolution （DE） is integrated into GWO to update the previous best position of grey wolf Alpha, Beta and Delta, in order to force GWO to jump out of the stagnation with DE＇s strong searching ability. The proposed algorithm can accele- rate the convergence speed of GWO and improve its performance. Twenty-three well-known benchmark functions and an NP hard problem of test scheduling for 3D SoC are employed to verify the performance of the proposed algorithm. Experimental results show the superior performance of the proposed algorithm for exploiting the optimum and it has advantages in terms of exploration.

Metamodel-based Global Optimization Using Fuzzy Clustering for Design Space Reduction

High fidelity analysis are utilized in modern engineering design optimization problems which involve expensive black-box models.For computation-intensive engineering design problems,efficient global optimization methods must be developed to relieve the computational burden.A new metamodel-based global optimization method using fuzzy clustering for design space reduction(MGO-FCR) is presented.The uniformly distributed initial sample points are generated by Latin hypercube design to construct the radial basis function metamodel,whose accuracy is improved with increasing number of sample points gradually.Fuzzy c-mean method and Gath-Geva clustering method are applied to divide the design space into several small interesting cluster spaces for low and high dimensional problems respectively.Modeling efficiency and accuracy are directly related to the design space,so unconcerned spaces are eliminated by the proposed reduction principle and two pseudo reduction algorithms.The reduction principle is developed to determine whether the current design space should be reduced and which space is eliminated.The first pseudo reduction algorithm improves the speed of clustering,while the second pseudo reduction algorithm ensures the design space to be reduced.Through several numerical benchmark functions,comparative studies with adaptive response surface method,approximated unimodal region elimination method and mode-pursuing sampling are carried out.The optimization results reveal that this method captures the real global optimum for all the numerical benchmark functions.And the number of function evaluations show that the efficiency of this method is favorable especially for high dimensional problems.Based on this global design optimization method,a design optimization of a lifting surface in high speed flow is carried out and this method saves about 10 h compared with genetic algorithms.This method possesses favorable performance on efficiency,robustness and capability of global convergence and gives a new optimization strategy for engineering design optimization problems involving expensive black box models.

Global Optimization Method Using SLE and Adaptive RBF Based on Fuzzy Clustering

High fidelity analysis models,which are beneficial to improving the design quality,have been more and more widely utilized in the modern engineering design optimization problems.However,the high fidelity analysis models are so computationally expensive that the time required in design optimization is usually unacceptable.In order to improve the efficiency of optimization involving high fidelity analysis models,the optimization efficiency can be upgraded through applying surrogates to approximate the computationally expensive models,which can greately reduce the computation time.An efficient heuristic global optimization method using adaptive radial basis function（RBF） based on fuzzy clustering（ARFC） is proposed.In this method,a novel algorithm of maximin Latin hypercube design using successive local enumeration（SLE） is employed to obtain sample points with good performance in both space-filling and projective uniformity properties,which does a great deal of good to metamodels accuracy.RBF method is adopted for constructing the metamodels,and with the increasing the number of sample points the approximation accuracy of RBF is gradually enhanced.The fuzzy c-means clustering method is applied to identify the reduced attractive regions in the original design space.The numerical benchmark examples are used for validating the performance of ARFC.The results demonstrates that for most application examples the global optima are effectively obtained and comparison with adaptive response surface method（ARSM） proves that the proposed method can intuitively capture promising design regions and can efficiently identify the global or near-global design optimum.This method improves the efficiency and global convergence of the optimization problems,and gives a new optimization strategy for engineering design optimization problems involving computationally expensive models.

A Parameter-Free Filled Function for Unconstrained Global Optimization

The filled function method is an approach for finding a global minimum of multi-dimensional functions. With more and more relevant research, it becomes a promising way used in unconstrained global optimization. Some filled functions with one or two parameters have already been suggested. However, there is no certain criterion to choose a parameter appropriately. In this paper, a parameter-free filled function was proposed. The definition of the original filled function and assumptions of the objective function given by Ge were improved according to the presented parameter-free filled function. The algorithm and numerical results of test functions were reported. Conclusions were drawn in the end. Key words global optimization - filled function method - local minimizer MSC 2000 90C30

A New Subdivision Algorithm for the Bernstein Polynomial Approach to Global Optimization

In this paper, an improved algorithm is proposed for unconstrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems. The proposed algorithm is based on the Bernstein polynomial approach. Novel features of the proposed algorithm are that it uses a new rule for the selection of the subdivision point, modified rules for the selection of the subdivision direction, and a new acceleration device to avoid some unnecessary subdivisions. The performance of the proposed algorithm is numerically tested on a collection of 16 test problems. The results of the tests show the proposed algorithm to be superior to the existing Bernstein algorithm in terms of the chosen performance metrics.

GLOBAL OPTIMIZATION OF PUMP CONFIGURATION PROBLEM USING EXTENDED CROWDING GENETIC ALGORITHM

An extended crowding genetic algorithm (ECGA) is introduced for solvingoptimal pump configuration problem, which was presented by T. Westerlund in 1994. This problem hasbeen found to be non-convex, and the objective function contained several local optima and globaloptimality could not be ensured by all the traditional MINLP optimization method. The concepts ofspecies conserving and composite encoding are introduced to crowding genetic algorithm (CGA) formaintain the diversity of population more effectively and coping with the continuous and/or discretevariables in MINLP problem. The solution of three-levels pump configuration got from DICOPT++software (OA algorithm) is also given. By comparing with the solutions obtained from DICOPT++, ECPmethod, and MIN-MIN method, the ECGA algorithm proved to be very effective in finding the globaloptimal solution of multi-levels pump configuration via using the problem-specific information.

Chaos-enhanced moth-flame optimization algorithm for global optimization

Moth-flame optimization(MFO)is a novel metaheuristic algorithm inspired by the characteristics of a moth’s navigation method in nature called transverse orientation.Like other metaheuristic algorithms,it is easy to fall into local optimum and leads to slow convergence speed.The chaotic map is one of the best methods to improve exploration and exploitation of the metaheuristic algorithms.In the present study,we propose a chaos-enhanced MFO(CMFO)by incorporating chaos maps into the MFO algorithm to enhance its performance.The chaotic map is utilized to initialize the moths’population,handle the boundary overstepping,and tune the distance parameter.The CMFO is benchmarked on three groups of benchmark functions to find out the most efficient one.The performance of the CMFO is also verified by using two real engineering problems.The statistical results clearly demonstrate that the appropriate chaotic map(singer map)embedded in the appropriate component of MFO can significantly improve the performance of MFO.

Multi-swingby optimization of mission to Saturn using global optimization algorithms

Based on the trajectory design of a mission to Saturn, this paper discusses four different trajectories in various swingby cases. We assume a single impulse to be applied in each case when the spacecraft approaches a celestial body. Some optimal trajectories ofEJS, EMS, EVEJS and EVVEJS flying sequences are obtained using five global optimization algorithms： DE, PSO, DP, the hybrid algorithm PSODE and another hybrid algorithm, DPDE. DE is proved to be supe- rior to other non-hybrid algorithms in the trajectory optimi- zation problem. The hybrid algorithm of PSO and DE can improve the optimization performance of DE, which is vali- dated by the mission to Saturn with given swingby sequences. Finally, the optimization results of four different swingby sequences are compared with those of the ACT of ESA.

MODIFIED INTEGRAL-LEVEL SET METHOD FOR THE CONSTRAINED SOLVING GLOBAL OPTIMIZATION

The constrained global optimization problem being considered, a modified integral_level set method was illustrated based on Chew_Zheng's paper on Integral Global Optimization and (Wu's) paper on Implementable Algorithm Convergence of Modified Integral_Level Set Method for Global Optimization Problem. It has two characters: 1) Each phase must construct a new function which has the same global optimal value as that of primitive objective function; 2) Comparing it with (Zheng's) method, solving level set procedure is avoided. An implementable algorithm also is given and it is proved that this algorithm is convergent.

A LEVEL-VALUE ESTIMATION METHOD FOR SOLVING GLOBAL OPTIMIZATION

A level-value estimation method was illustrated for solving the constrained global optimization problem. The equivalence between the root of a modified variance equation and the optimal value of the original optimization problem is shown. An alternate algorithm based on the Newton＇s method is presented and the convergence of its implementable approach is proved. Preliminary numerical results indicate that the method is effective.

Modified evolutionary algorithm for global optimization

A modification of evolutionary programming or evolution strategies for ndimensional global optimization is proposed. Based on the ergodicity and inherentrandomness of chaos, the main characteristic of the new algorithm which includes two phases is that chaotic behavior is exploited to conduct a rough search of the problem space in order to find the promising individuals in Phase I. Adjustment strategy of steplength and intensive searches in Phase II are employed. The population sequences generated by the algorithm asymptotically converge to global optimal solutions with probability one. The proposed algorithm is applied to several typical test problems. Numerical results illustrate that this algorithm can more efficiently solve complex global optimization problems than evolutionary programming and evolution strategies in most cases.

Global Optimization of Nonlinear Blend-Scheduling Problems

The scheduling of gasoline-blending operations is an important problem in the oil refining industry. Thisproblem not only exhibits the combinatorial nature that is intrinsic to scheduling problems, but alsonon-convex nonlinear behavior, due to the blending of various materials with different quality properties.In this work, a global optimization algorithm is proposed to solve a previously published continuous-timemixed-integer nonlinear scheduling model for gasoline blending. The model includes blend recipe optimi-zation, the distribution problem, and several important operational features and constraints. The algorithmemploys piecewise McCormick relaxation （PMCR） and normalized multiparametric disaggregation tech-nique （NMDT） to compute estimates of the global optimum. These techniques partition the domain of oneof the variables in a bilinear term and generate convex relaxations for each partition. By increasing the num-ber of partitions and reducing the domain of the variables, the algorithm is able to refine the estimates ofthe global solution. The algorithm is compared to two commercial global solvers and two heuristic methodsby solving four examples from the literature. Results show that the proposed global optimization algorithmperforms on par with commercial solvers but is not as fast as heuristic approaches.

Analysis and Improvement of TCP Congestion Control Mechanism Based on Global Optimization Model

Network flow control is formulated as a global optimization problem of user profit. A general global optimization flow control model is established. This model combined with the stochastic model of TCP is used to study the global rate allocation characteristic of TCP. Analysis shows when active queue management is used in network TCP rates tend to be allocated to maximize the aggregate of a user utility functionU s (called,U s fairness). The TCP throughput formula is derived An improved TCP congestion control mechanism is proposed. Simulations show its throughput is TCP friendly when competing with existing TCP and its rate change is smoother. Therefore, it is suitable to carry multimedia applications.

IRKO:An Improved Runge-Kutta Optimization Algorithm for Global Optimization Problems

Optimization is a key technique for maximizing or minimizing functions and achieving optimal cost,gains,energy,mass,and so on.In order to solve optimization problems,metaheuristic algorithms are essential.Most of these techniques are influenced by collective knowledge and natural foraging.There is no such thing as the best or worst algorithm;instead,there are more effective algorithms for certain problems.Therefore,in this paper,a new improved variant of a recently proposed metaphorless Runge-Kutta Optimization(RKO)algorithm,called Improved Runge-Kutta Optimization(IRKO)algorithm,is suggested for solving optimization problems.The IRKO is formulated using the basic RKO and local escaping operator to enhance the diversification and intensification capability of the basic RKO version.The performance of the proposed IRKO algorithm is validated on 23 standard benchmark functions and three engineering constrained optimization problems.The outcomes of IRKO are compared with seven state-of-the-art algorithms,including the basic RKO algorithm.Compared to other algorithms,the recommended IRKO algorithm is superior in discovering the optimal results for all selected optimization problems.The runtime of IRKO is less than 0.5 s for most of the 23 benchmark problems and stands first for most of the selected problems,including real-world optimization problems.

A Level-Value Estimate Method for Solving Constrained Global Optimization

The penalty method is a popular method for solving constrained optimization problems, which can change the constrained optimization to the unconstrained optimization. With the integral-level set method, a new approach was proposed, which is briefer than the penalty method, to achieve the transform by constructing a simple function, then a level-value function was introduced to construct the equivalence between the unconstrained optimization and a nonlinear equality. By studying the properties of the function, a level-value estimate algorithm and an implementation algorithm were given by means of the uniform distribution of the good point set. Key words global optimization - constrained optimization - integral-level set - level-value estimate MSC 2000 90C05

Hybrid method for global optimization using more accuracy interval computation

In this paper, a novel hybrid method is presented for finding global optimization of an objective function. Based on the interval computation, this hybrid method combines interval deterministic method and stochastic evolution method. It can find global optimization quickly while ensuring the deterministic and stability of the algorithm. When using interval computation, extra width constraints accuracy of interval computation results. In this paper, a splitting method to reduce the extra width is introduced. This method is easy and it can get a more precise interval computation result. When finding the global optimization, it can increase the efficiency of pruning. Several experiments are given to illustrate the advantage of the new hybrid method.