The Barter Method: A New Heuristic for Global Optimization and its Comparison with the Particle Swarm and the Differential Evolution Methods

Mishra, SK (2006): The Barter Method: A New Heuristic for Global Optimization and its Comparison with the Particle Swarm and the Differential Evolution Methods.

Abstract

The objective of this paper is to introduce a new population-based (stochastic) heuristic to search the global optimum of a (continuous) multi-modal function and to assess its performance (on a fairly large number of benchmark functions) vis-à-vis that of two other well-established and very powerful methods, namely, the Particle Swarm (PS) and the Differential Evolution (DE) methods of global optimization. We will call this new method the Barter Method of global optimization.

This method is based on the well-known proposition in welfare economics that competitive equilibria, under fairly general conditions, tend to be Pareto optimal In its simplest version, implementation of this proposition may be outlined as follows:

Let there be a fairly large number of individuals in a population and let each individual own (or draw from the environment) an m-element real vector of resources, xi = (xi1, xi2, …, xim). For every xi there is a (single-valued) function f(x) that may be used as a measure of the worth of xi that the individual would like to optimize. The optimand function f(.) is unique and common to all the individuals. Now, let the individuals in the (given) population enter into a barter of their resources with the condition that (i) a transaction is feasible across different persons and different resources only, and (ii) the resources will change hands (materialize) only if such a transaction is beneficial to (more desired by) both the parties (in the barter). The choice of the individuals, (i ,k) and the resources, (j, l) in every transaction and the quantum of transaction would be stochastic in nature. If such transactions are allowed for a large number of times, then at the end of the session: (a) every individual would be better off than what he was at the initial position, and (b) at least one individual would reach the global optimum.

We have uses 75 test functions. The DE succeeds in 70 cases, the RPS succeeds in 60 cases, while the Barter 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 eight cases, the Barter method could not converge in 10000 iterations (due to slow convergence rate), while in 4 cases the MRPS could not converge. Seen as such, the barter method is inferior to the other two methods. Additionally, the convergence rate of the Barter method is slower than the DE as well as the MRPS. However, the DE and the RPS have a history of a full decade behind them and they have been improved many times. In the present exercise, the RPS is a modified version (MRPS) that has an extra ability for local search. The DE version used here uses 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.

• Item Type: MPRA Paper
• Language: English
• Keywords: Barter method; Differential Evolution; Repulsive Particle Swarm; Global optimization; non-convex functions; local optima; Fortran; computer program; benchmark; test functions
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis

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) · 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. · 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.