Munich Personal RePEc Archive

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.

[img]
Preview
PDF
MPRA_paper_543.pdf

Download (413Kb) | Preview

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.

UB_LMU-Logo
MPRA is a RePEc service hosted by
the Munich University Library in Germany.