On The Use of Genetic Algorithm with Elitism in Robust and Nonparametric Multivariate Analysis

Biman Chakraborty; Probal Chaudhuri

doi:10.17713/ajs.v32i1&2.447

Authors

Biman Chakraborty National University of Singapore, Singapore
Probal Chaudhuri Indian Statistical Institute, Kolkata, India

DOI:

https://doi.org/10.17713/ajs.v32i1&2.447

Abstract

In this paper, we provide a general formulation for the problems that arise in the computation of many robust and nonparametric estimates in terms of a combinatorial optimization problem. There is virtually no hope for solving such optimization problems exactly for high dimensional data, and people usually resort to various approximate algorithms many of which are based on heuristic search strategies. However, for such algorithms it is not guaranteed that they will converge to the global optimum as the number of iterations increases, and there are always possibilities for such algorithms getting trapped in some local optimum. Here we propose genetic algorithm with elitism as a way to solve that general problem by probabilistic search method. We establish convergence of our algorithm to the global optimal solution and demonstrate the performance of this algorithm using some numerical examples.

References

J. Besag. On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, Series B, 48:259–302, 1986.

D. Bhandari, C.A. Murthy, and S.K. Pal. Genetic algorithms with elitist model and its convergence. International Journal of Pattern Recognition and Artificial Intelligence,

:731–747, 1996.

P. Boček and P. Lachout. Linear programming approach to LMS–estimation. Computational Statistics & Data Analysis, 19:129–134, 1995.

B. Chakraborty and P. Chaudhuri. On a transformation and re-transformation technique for constructing affine equivariant multivariate median. Proceedings of the American Mathematical Society, 124:2539–2547, 1996.

B. Chakraborty and P. Chaudhuri. On an adaptive transformation retransformation estimate of multivariate location. Journal of the Royal Statistical Society, Series B, 60: 145–157, 1998.

B. Chakraborty and P. Chaudhuri. A note on robustness of multivariate median. Statistics and Probability Letters, 45:269–276, 1999.

B. Chakraborty, P. Chaudhuri, and H. Oja. Operating transformation retransformation on spatial median and angle test. Statistica Sinica, 8:767–784, 1998.

P. Chaudhuri and D. Sengupta. Sign tests in multidimension: Inference based on the geometry of the data cloud. Journal of the American Statistical Association, 88:1363–1370, 1993.

T. E. Davis and J.C. Principe. A simulated annealing-like convergence theory for the simple genetic algorithm. In R. K. Belew and L. B. Booker, editors, Proceedings of

the Fourth International Conference on Genetic Algorithms, pages 174–181. Morgan Kaufmann, San Mateo, CA, 1991.

M.R. Garey and D.S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco, 1979.

D.E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, New York, 1989.

J.L. Hodges. A bivariate sign test. The Annals of Mathematical Statistics, 26:523–527, 1955.

Z. Michalewicz. Genetic Algorithms + Data Structure = Evolution Programs. Springer, New York, 1996.

C.F. Olson. An approximation algorithm for least median of squares regression. Information Processing Letters, 63:237–241, 1997.

P.J. Rousseeuw. Least median of squares regression. Journal of the American Statistical Association, 79:871–880, 1984.

P.J. Rousseeuw and M. Hubert. Recent developments in progress. In Y. Dodge, editor, L1-Statistical Procedures and Related topic, pages 201–214. Institute of Mathematical

Statistics, Hayward, California, 1997.

P.J. Rousseeuw and A.M. Leroy. Robust Regression and Outlier Detection. Wiley, New York, 1987.

P.J. Rousseeuw and I. Ruts. As 307: Bivariate location depth. Applied Statistics, 45: 516–526, 1996.

P.J. Rousseeuw and I. Ruts. Constructing the bivariate Tukey median. Statistica Sinica, 8:827–839, 1998.

P.J. Rousseeuw and K. van Driessen. A fast algorithm for the minimum covariance determinant estimator. Technometrics, 41:212–223, 1999.

I. Ruts and P.J. Rousseeuw. Computing depth contours of bivariate point clouds. Computational Statistics and Data Analysis, 23:153–168, 1996.

A. Struyf and P.J. Rousseeuw. High-dimensional computation of the deepest location. Computational Statistics and Data Analysis, 34:415–426, 2000.

P. Tichavský. Algorithm for and geometrical character of solutions in the LMS and the LTS linear regression. Computational Statistics Quarterly C, 6:139–151, 1991.

V. Todorov. Computing the minimum covariance determinant estimator (MCD) by simulated annealing. Computational Statistics & Data Analysis, 14:515–525, 1992.

J.W. Tukey. Mathematics and the picturing of data. In R.D. James, editor, Proceedings of the International Congress of Mathematicians, vol. 2, pages 523–531. Canadian

Mathematical Congress, Vancouver, 1975.

G.Winkler. Image Analysis, Random Fields and Dynamic Monte Carlo Methods. A Mathematical Introduction. Springer, New York, 1995.

D.L. Woodruff and D.M. Rocke. Heuristic search algorithms for the minimum volume ellipsoid. Journal of Computational and Graphical Statistics, 2:69–95, 1993.