Performance of the Barter, the Differential Evolution and the Simulated Annealing Methods of Global Optimization on Some New and Some Old Test Functions

Mishra, SK (2006): Performance of the Barter, the Differential Evolution and the Simulated Annealing Methods of Global Optimization on Some New and Some Old Test Functions.

Abstract

In this paper we compare the performance of the Barter method, a newly introduced population-based (stochastic) heuristic to search the global optimum of a (continuous) multi-modal function, with that of two other well-established and very powerful methods, namely, the Simulated Annealing (SA) and the Differential Evolution (DE) methods of global optimization.

In all, 87 benchmark functions have been optimized 89 times. The DE succeeds in 82 cases, the Barter succeeds in 63 cases, while the Simulated Annealing method succeeds for a modest number of 51 cases. The DE as well as Barter methods are unstable for stochastic functions (Yao-Liu#7 and Fletcher-Powell functions). In particular, Bukin-6, Perm-2 and Mishra-2 functions have been hard for all the three methods.

Seen as such, the barter method is much inferior to the DE, but it performs better than SA. A comparison of the Barter method with the Repulsive Particle Swarm method has indicated elsewhere that they are more or less comparable.

The convergence rate of the Barter method is slower than the DE as well as the SA. This is because of the difficulty of ‘double coincidence’ in bartering. Barter activity takes place successfully in less than one percent trials.

It may be noted that the DE and the SA have a longer history behind them and they have been improved many times. In the present exercise, the DE version used here employs the latest (available) schemes of crossover, mutation and recombination. In comparison to this, the Barter method is a nascent one. We need a thorough investigation into the nature and performance of the Barter method. We have found that when the DE optimizes, the terminal population is homogenous while in case of the Barter method it is not so. This property of the Barter method has several implications with respect to the Agent-Based Computational Economics

• Item Type: MPRA Paper
• Language: English
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling

References

· Bauer, J.M.: “Harnessing the Swarm: Communication Policy in an Era of Ubiquitous Networks and Disruptive Technologies”, Communications and Strategies, 45, 2002. · Box, M.J.: “A New Method of Constrained Optimization and a Comparison with Other Methods”. Comp. J. 8, pp. 42-52, 1965. · Bukin, A. D.: New Minimization Strategy For Non-Smooth Functions, Budker Institute of Nuclear Physics preprint BUDKER-INP-1997-79, Novosibirsk 1997. · Cerny, V.: "Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm", J. Opt. Theory Appl., 45, 1, 41-51, 1985. · Eberhart R.C. and Kennedy J.: “A New Optimizer using Particle Swarm Theory”, Proceedings Sixth Symposium on Micro Machine and Human Science, pp. 39–43. IEEE Service Center, Piscataway, NJ, 1995. · Fleischer, M.: “Foundations of Swarm Intelligence: From Principles to Practice”, Swarming Network Enabled C4ISR, arXiv:nlin.AO/0502003 v1 2 Feb 2005. · G.E.P. Box, “Evolutionary operation: A Method for Increasing Industrial Productivity”, Applied Statistics, 6 , pp. 81-101, 1957. · Glover F.," Future paths for Integer Programming and Links to Artificial Intelligence", Computers and Operations Research, 5:533-549, 1986. · Hayek, F.A.: The Road to Serfdom, Univ. of Chicago Press, Chicago, 1944. · Holland, J.: Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, 1975. · Karush, W. Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois, 1939. · Kirkpatrick, S., Gelatt, C.D. Jr., and Vecchi, M.P.: "Optimization by Simulated Annealing", Science, 220, 4598, 671-680, 1983. · Kuhn, H.W. and Tucker, A.W.: “Nonlinear Programming”, in Neymann, J. (ed) Proceedings of Second Berkeley Symposium on Mathematical Statistics and Probability, Univ. of California Press, Berkrley, Calif. pp. 481-492, 1951. · Metropolis, N. The Beginning of the Monte Carlo Method. Los Alamos Science, No. 15, Special Issue, pp. 125-130, 1987. · Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E.: "Equation of State Calculations by Fast Computing Machines", J. Chem. Phys.,21, 6, 1087-1092, 1953. · Mishra, S.K.: “Some Experiments on Fitting of Gielis Curves by Simulated Annealing and Particle Swarm Methods of Global Optimization”, Social Science Research Network (SSRN): http://ssrn.com/abstract=913667, Working Papers Series, 2006 (a). · Mishra, S.K.: “Least Squares Fitting of Chacón-Gielis Curves by the Particle Swarm Method of Optimization”, Social Science Research Network (SSRN), Working Papers Series, http://ssrn.com/abstract=917762 , 2006 (b). · Mishra, S.K.: “Performance of Repulsive Particle Swarm Method in Global Optimization of Some Important Test Functions: A Fortran Program” , Social Science Research Network (SSRN), Working Papers Series, http://ssrn.com/abstract=924339 , 2006 (c). · Mishra, S.K.: “Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method”, Social Science Research Network (SSRN) Working Papers Series, http://ssrn.com/abstract=927134, 2006 (d). · Mishra, S.K.: “Repulsive Particle Swarm Method on Some Difficult Test Problems of Global Optimization” ,SSRN: http://ssrn.com/abstract=928538 , 2006 (e). · Mishra, SK.: "Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions" SSRN: http://ssrn.com/abstract=933827 ,2006 (f) · Mishra, SK.: " The Barter Method: A New Heuristic for Global Optimization and its Comparison with the Particle Swarm and the Differential Evolution Methods" SSRN: http://ssrn.com/abstract=939180 , 2006(g) · Nagendra, S.: Catalogue of Test Problems for Optimization Algorithm Verification, Technical Report 97-CRD-110, General Electric Company, 1997. · Nelder, J.A. and Mead, R.: “A Simplex Method for Function Minimization” Computer Journal, 7: pp. 308-313, 1964. · Parsopoulos, K.E. and Vrahatis, M.N., “Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization”, Natural Computing, 1 (2-3), pp. 235- 306, 2002. · Prigogine, I. and Strengers, I.: Order Out of Chaos: Man’s New Dialogue with Nature, Bantam Books, Inc. NY, 1984. · Silagadge, Z.K.: “Finding Two-Dimensional Peaks”, Working Paper, Budkar Insttute of Nuclear Physics, Novosibirsk, Russia, arXive:physics/0402085 V3 11 Mar 2004. · Simon, H.A.: Models of Bounded Rationality, Cambridge Univ. Press, Cambridge, MA, 1982. · Smith, A.: The Theory of the Moral Sentiments, The Adam Smith Institute (2001 e-version), 1759. · Storn, R. and Price, K: "Differential Evolution - A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces" : Technical Report, International Computer Science Institute, Berkley, 1995. · Sumper, D.J.T.: “The Principles of Collective Animal Behaviour”, Phil. Trans. R. Soc. B. 361, pp. 5-22, 2006. · Takayama, A.: Mathematical Economics, The Dryden Press, Hinsdale, Illinois, 1974. · Tesfatsion, L.: “Agent-Based Computational Economics: Growing Economies from the Bottom Up”, SSRN Working Papers Series, http://ssrn.com/abstract=305080, 2002. · Törn, A.A and Viitanen, S.: “Topographical Global Optimization using Presampled Points”, J. of Global Optimization, 5, pp. 267-276, 1994. · Törn, A.A.: “A search Clustering Approach to Global Optimization” , in Dixon, LCW and Szegö, G.P. (Eds) Towards Global Optimization – 2, North Holland, Amsterdam, 1978. · Tsallis, C. and Stariolo, D.A.: “Generalized Simulated Annealing”, ArXive condmat/9501047 v1 12 Jan, 1995. · Valentine, R.H.: Travel Time Curves in Oblique Structures, Ph.D. Dissertation, MIT, Mass, 1937. · Veblen, T.B.: "Why is Economics Not an Evolutionary Science" The Quarterly Journal of Economics, 12, 1898. · Veblen, T.B.: The Theory of the Leisure Class, The New American library, NY. (Reprint, 1953), 1899. · Vesterstrøm, J. and Thomsen, R.: “A comparative Study of Differential Evolution, Particle Swarm Optimization, and Evolutionary Algorithms on Numerical Benchmark Problems”, Congress on Evolutionary Computation, 2004. CEC2004, 2, pp. 1980-1987, 2004. · Whitley, D., Mathias, K., Rana, S. and Dzubera, J.: “Evaluating Evolutionary Algorithms”, Artificial Intelligence, 85, pp. 245-276, 1996. · Yao, X. and Liu, Y.: “Fast Evolutionary Programming”, in Fogel, LJ, Angeline, PJ and Bäck, T (eds) Proc. 5th Annual Conf. on Evolutionary programming, pp. 451-460, MIT Press, Mass, 1996.