Test Problems for iSight

Abstract: In order to test the efficiency and capability of iSight, some standard test problems listed below are tested. All of those functions have a certain number of local minima which are widely used for test of all kind of global optimization methods. Because of the slow runs of computer and the low efficiency of certain optimization method, only several test runs are carried out for each test problem. The results are list after a brief introduction of the test function.

Key Words: Test function, global optimization, iSight, Rastrigin function, Schwefel function, Ackley Function, Shekel function, Genetic Algorithm, Simulated Annealing

1. Introduction of Optimization method used by iSight

1.1 local optimization methods

More local optimization methods are available than global optimization methods and most of them are very sophisticated and with good performance in searching a local optima.

All the test functions are designed for global optimization, so only one local optimization methods suggested by iSight’s Task Plan Advisor are tested. For most cases, local optimization method serves as the last step in the Task Plan.

1.2 Global optimization method

All Global optimization methods are tested with a local optimization method as the last step to avoid lingering around a minimum without reaching it. By default, this local optimization method is Sequential Quadratic Programming (NLPQL).

1.2.1 Genetic Algorithm

A so-called Multi-island Genetic Algorithm is used by iSight. No detail of this GA is offered in iSight’s online help and no exact search results can be found on internet. However, there are some kinds of Island-based Genetic Algorithm, IGA for short. In IGA, there are some populations developing independently each like an evolution in a desolated island.

Several parameters of GA that can be modified in iSight are listed below:

Parameters	default	GA(I)	GA(III)	GA(IV)	GA(V)	GA(VI)	GA(8)
Size of subpopulation	10	15	20	10	10	50	20
Number of islands	10	15	20	50	10	10	10
Number of generations	10	15	20	10	50	10	50

Above are the basic parameters which control the size of the evolution.

The rest parameters not listed here are the advanced parameters which control the searching capability of the method, e.g. Rate of Mutation controls the capability of jumping out of local minima. Most of them are not changed.

It is suggest that typically larger values of basic parameters produce more accurate solutions, meanwhile consume larger resource and time. For lack of time, details of the other GA parameters are not tested.

1.2.2 Simulated Annealing

When first introduced by Kirkpatrick in 1983, SA was a very simple optimization method and could be coded in a small group of lines. However, many modifications were patched on the original one in order to improve the efficiency and capability for searching global optima.

Adaptive Simulated Annealing is used by iSight for Global Optimization. There are many articles about modified SA and many of them claim an adaptive feature.

Several parameters of SA that can be modified in iSight are listed below:

Max. Number of Generated Designs: 10000

Number of Designs for Convergence Check: 5

Convergence Epsilon: 10e-8

Etc.

The default values are used in the test runs.

For more details, see iSight online help or search the internet.

2 Test Results

All of the tests begin with a vector away from the border and center of the searching domain and stop by the default termination criteria of the optimization method set by iSight. Every step of the optimization process takes about 0.5~2 s according to the calculation of the test function, the integration and optimization process of iSight.

2.1 Rastrigin function

A highly multimodal test function with many regularly distributed local minima, whose values increase as the distance from the global optimum point increases. The function defined as:

Parameters: n - the dimension of the function, A - the steepness of the local optima.

Global minimum = 0.0 at .

Local minima: Grid points with x_i=0.0 except one coordinate, where x_i=1.0, give F(x) =1.0.

2D Plots

Fig. 1. n=2, A=0	Fig. 2. n=2, A=0.5	Fig. 3. n=2, A=1
Fig. 4. n=2, A=2	Fig. 5. n=2, A=3	Fig. 6. n=2, A=5
Fig. 7. n=2, A=10	Fig. 8. n=2, A=50	Fig. 9. n=2, A=100

A bigger view of n=2, A=10

All the tests are run for a 10 dimensional Rastrigin function with A=10. Some of the test runs begin from , f(x)=258.5136.

Algorithm	Objective
Algorithm	Initial value	Optimum found (Before last local optimization step)	improvement	Steps run
NLPQL	258.513649	159.1925	38.42%	137+
SA(default)	159.1925	0.99496(1.18)	99.37%	10129
GA(default)	159.1925	35.8184(35.8184)	77.5%	1172
GA(default)	193.0346	49.7483(49.7483)	74.23%	1026
GA(I)	49.7483	9.9496(19.1)	80%	3564
GA(III)	213.4526	4.9748(7.02)	97.67%	8195
GA(IV)	258.5136	32.6378(32.6378)	87.37%	5307
GA(V)	258.5136	2.9849(3.7026)	98.85%	5084
GA(VI)	258.5136	8.9546(13.4459)	96.54%	5120
GA(VIII)	258.5136	1.9899(2.1866)	99.23%	10069

The improvement equals (Initial value-Optima found)/Initial value.

+ in the steps run of a local optimization method means the method stops here automatically and the result does not improve with more steps.

The local optimization step after the global optimization step plays an important role in improving the optimum found. And due to the statistical nature of GA and SA, the more steps it takes, the better improvement obtained.

The following three plots of evolution history of GA(IV), GA(V), GA(VI) shows different influence of three basic parameters on GA.

GA(IV) with Number of islands set to 50.

GA(V) with Number of generations set to 50

GA(VI) with size of subpopulation set to 50

From the above three plots, Number of generations makes the optimization process steeper however the rest two make it more fluctuant. And a bigger number of islands does not help much.

So in GA(VIII), the basic parameters are set as 20,10,50 respectively. At last, the result is better though not better the SA result. The GA basic parameters affect results greatly and all of the parameters should be tuned together in order to obtain a good improvement.

2.2 Schwefel function

With a second best minimum far away from the global minimum, this function was designed to trap optimization algorithms in this suboptimal valley.

Global minimum = 0, at

A 4-Dimensional problem is tested.

Initial from , f(x)= 1779.1723.

Algorithm	Objective
Algorithm	Initial value	Optimum found	improvement	Steps run
NLPQL	1779.1723	473.7534	73.37%	96+
SA(default)*	1779.1723	5.1048×10^-5(5.1048×10^-5)	100%	3543
GA(default)	1779.1723	335.5782(335.5782)	81.14%	1064
GA(III)	1620.41	1.7234×10^-4	100%	8023

The plot below shows the searching process of SA. We can see that before about 1500 steps, the function value was trapped in a larger local minimum. However, the SA process managed to jump out of it and found the global minimum at last.

For the GA(III), it managed into the deepest valley at last:

2.3. Shekel function (Shekel’s foxholes)

Correlations exist between multiple input variables. The definition is

It has m minima whose distribution and amplitudes are determined by A and c. So the distribution can be irregular.

For a 4 dimensional problem,

for m=10: f^* = -10.5364, X^* = (4.00075,4.00059,3.99966,3.99951 ) , n_loc = 10

Graphical 3D-representation of an instance of a

2-dimensional Shekel-function with 10 maximum points

Density plot of the Shekel-function

A 4-dimensional Shekel-function with 10 maximum point are tested with results listed below, initial value is x = (7.5, 7.5, 7.5, 7.5), f(x) =-1.0829 for some cases.

Algorithm	Objective
Algorithm	Initial value	Optimum found	improvement	Steps run
NLPQL	-1.0829	-5.1756	-377.94%	91+
SA(default)*	-1.0829	-10.5364	-872.98%	1500
GA(default)	-1.0829	-10.5364	-872.98%	1058

* The SA was forced to stop.

The plot below shows the GA process, from which we could clearly see the statistical method’s capability of jumping out of local minima.

The plot below shows the SA process, from which we could see more random jumping out of and into local minima. For some steps, this method just jump out of the deepest hole without reach the bottom and waste time searching elsewhere. From this, we could say, the SA is not effective for a problem with so few local minima (in this case 10) due to its poor neighborhood searching ability. (SA first reaches -10.536 at step about 800 and -10.5364 at step 1177)

3. Conclusion

As show in the tables and plots above, given enough runs for two global optimization methods provided by iSight, GA and SA, acceptable optimum of the test problems can be found though not exactly the analytic value. The iSight optimization is sufficient especially for low dimensional problems. Running time is determined by the nature of the problem and the solution method chosen.

Local optimization method does not work well for global optimization independently. However, as a hybrid part of GA/SA, it improves the optimum found effectively in most of the cases.

Tuning, i.e. setting a proper group of parameters, of an optimization method may affect the optimization process greatly, especially for higher dimensional problems.

Due to time and resources, only above 3 functions are tested briefly. And only several settings of certain optimization method are tested. So the above report is just offered as a reference for evaluating the capability of iSight for a certain depth. The practical optimization problems may be easier or harder than the test functions listed in this paper.

The better solution and the shorter calculating time are two contradict elements. However, a deeper knowledge of the optimization method and the problem to be optimized may play a role of lever, with which, tuning of the optimization method to fit a certain problem may play an even bigger role in improving the optimization process which produces better optima and consumes less.

Reference:

[TZ89] A. Törn and A. Zilinskas. "Global Optimization". Lecture Notes in Computer Science, Nº 350, Springer-Verlag, Berlin,1989.

[MSB91] H. Mühlenbein, D. Schomisch and J. Born. "The Parallel Genetic Algorithm as Function Optimizer ". Parallel Computing, 17, pages 619-632,1991.

[Ack87] D. H. Ackley. "A connectionist machine for genetic hillclimbing". Boston: Kluwer Academic Publishers, 1987.

[Sch81] Schwefel, H.-P.: Numerical optimization of computer models. Chichester: Wiley & Sons, 1981.

[She71] Shekel, J. 1971. "Test Functions for Multimodal Search Techniques." Fifth Annual Princeton Conference on Information Science and Systems.

GEA Toolbox - Examples of Objective Functions, www.geatbx.com