Modied Genetic Algorithm with Greedy Heuristic for Continuous and Discrete p-Median Problems

Lev Aleksandrovich Kazakovtsev, Victor Orlov, Aljona Aleksandrovna Stupina, Vladimir Kazakovtsev

DOI Number
-
First page
89
Last page
106

Abstract


Genetic algorithm with greedy heuristic is an efficient method for solvinglarge-scale location problems on networks. In addition, it can be adapted for solvingcontinuous problems such as k-means. In this article, authors propose modicationsto versions of this algorithm on both networks and continuous space improving itsperformance. The Probability Changing Method was used for initial seeding of thecenters in case of the p-median problem on networks.Results are illustrated by numerical examples and practical experience of clusteranalysis of semiconductor device production lots.

Keywords


Genetic algorithms, p-median problem, k-means

Full Text:

PDF

References


M. R. Ackermann et al: StreamKM: A Clustering Algorithm for Data Streams, J. Exp. Algorithmics, 2012, 17, Article 2.4 (May 2012), published online, DOI: 10.1145/2133803.2184450

O. Alp, E. Erkut and Z. Drezner: An Ecient Genetic Algorithm for the p-Median Problem, Annals of Operations Research, 2003, 122 (1-4), 21-42.

A. Antamoshkin: On Optimal Algorithms of Optimization of Functionals with Boolean Variables, In: Trans. Ninth Prague Conference on Inform. Theory, Statist. Dec. Functions, Random Processes. Academia, Prague 1983, 137-141.

A. Antamoshkin: Optimization of functionals with Boolean variables, Izd. Tomsk, un-ta, Tomsk 1987.

A. N. Antamoshkin and L. A. Kazakovtsev: Random Search Algorithm for the p-median Problem, Informatica, 2013, 37(3), 267-278

D. Arthur and S. Vassilvitskii: k-Means++: The Advantages of Careful Seeding, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete algorithms, ser. SODA '07, 2007, 1027-1035.

P. Avella, A. Sassano and I. Vasilev: Computational Study of Large-Scale p-Median Problems, Mathematical Programming, 2007, 109(1), 89-114.

P. Avella, M. Boccia, S. Salerno and I. Vasilyev: An Aggregation Heuristic for Large Scale p-median Problem, Computers & Operations Research, 2012, 39 (7), 1625-1632, doi 10.1016/j.cor.2011.09.016

J. E. Beasley: OR-Library: Distributing Test Problems by Electronic Mail, Journal of the Operational Research Society, 1990, 41(11), 1069-1072.

J. F. P. Borg: Modern Multidimensional Scaling: Theory and Applications, Springer, 2005, 207-212.

B. Bozkaya, J. Zhang and E. Erkut: A Genetic Algorithm for the p-Median Problem, Drezner Z., Hamacher H. (eds.), Facility Location: Applications and Theory, Springer, 2002.

L. Cooper: Location-allocation problem, Oper. Res., 1963, 11, 331-343.

Z. Drezner: The Fortied Weiszfeld Algorithm for Solving the Weber Problem, IMA Journal of Management Mathematics, 2013, published online. DOI: 10.1093/ima-man/dpt019

J. Fathali, N. J. Rad, S. R. Sherbaf: The p-median and p-center Problems on Bipartite Graphs, Iranian Journal of Matematical Sciences and Informatics, 2014, 9 (2), 37-43

C. M. Hosage and M. F. Goodchild: Discrete Space Location-Allocation Solutions from Genetic Algorithms, Annals of Operations Research, 1986, 6, 35-46.

S. L. Hakimi: Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph, Operations Research, May/June 1964, 12(3), 450-459.

T. Kanungo, D. Mount, N. Netanyahux, C. Piatko, R. Silverman, A. Wu: A Local Search Approximation Algorithm for k-Means Clustering, Computational Geometry, 2004, 28, 89-112.

O. Kariv and S. L. Hakimi: An Algorithmic Approach to Network Location Problems. II. The p-medians, SIAM Journal on Applied Mathematics, 1979, 37(3), 539-560.

L. A. Kazakovtsev, A. N. Antamoshkin and M. N. Gudyma: Parallelny algoritm dlya p-mediannoy zadachi (Parallel Algorithm for the p-Median Problem), Control Systems and Information Technologies, 2013, 52 (2.1), 124-128.

L. A. Kazakovtsev: Adaptation of the Probability Changing Method for Weber Problem with an Arbitrary Metric, Facta Universitatis (Nis) Ser. Math. Inform., V.27(2), 2012, 239-254.

L. Kazakovtsev: Algorithm for Approximate Solution of the Generalized Weber Problem with an Arbitrary Metric, Computer Modeling and Simulation (EMS), 2012 Sixth UKSim/AMSS European Symposium on, Malta, 2012, 109-114.

L. A. Kazakovtsev and A. N. Antamoshkin: Gnetic Algorithm with Fast Greedy Heuristic for Clustering and Location Problems, Informatica, 2014, 38(3), 229-240

L. A. Kazakovtsev and A. A. Stupina: Fast Genetic Algorithm with Greedy Heuristic for p-Median and k-Means Problems, IEEE 2014 6th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 6-8 October 2014, St.-Petersburg, 2014, 702-706.

N. V. Koplyarova, V. I. Orlov, N. A. Sergeeva, V. V. Fedosov: On Non-Parametric Models in the Problem of Performance Diagnostics of Electronic Components, Zavodskaya Laboratoriya, 2014, 80(7), 37-77 (in Russian).

H. P. Kriegel, K. P. Kroeger and A. Zimek: Outlier Detection Techniques (Tutorial), 13th Pacic Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2009), Bangkok, Thailand, 2009.

J. B. MacQueen: Some Methods of Classication and Analysis of Multivariate Observations, Proceedings of the 5th Berkley Symposium on Mathematical Statistics and Probability, 1967, Vol.1, 281-297.

S. Masuyama, T. Ibaraki and T. Hasegawa: The Computational Complexity of the m-Center Problems on the Plane, The Transactions of the Institute of Electronics and Comunication Engineers of Japan, 1981, 64E, 57-64.

N. Mishra, D. Oblinger and L. Pitt: Sublinear Time Approximate Clustering, 12th SODA, 2001, 439-447.

M. N. Neema, K. M. Maniruzzaman and A. Ohgai: New Genetic Algorithms Based Approaches to Continuous p-Median Problem, Netw. Spat. Econ., 2011, 11, 83-99, DOI:10.1007/s11067-008-9084-5.

M. Rabbani: A Novel Approach for Solving a Constrained Loca-

tion Allocation Problem, International Journal of Industrial Engineer-

ing Computations, 2013, published online, doi 10.5267/j.ijiec.2013.02.003.

M. G. C. Resende, C. C. Ribeiro, F. Glover and R. Marti: Scatter search and path-relinking: Fundamentals, advances, and applications, Handbook of Metaheuristics, 2nd

Edition, M. Gendreau and J.-Y. Potvin, Eds. Springer, 2010, 87-107.

M. G. C. Resende: Metaheuristic Hybridization with Greedy Randomized Adaptive Search Procedures, in TutORials in Operations Research, Zhi-Long Chen and S. Raghavan (Eds.), INFORMS, 2008, 295-319.

P. S. Stanimirovic, M. Ciric, L. A. Kazakovtsev and I. A. Osinuga: Single-facility Weber Location Problem Based on the Lift Metric, Facta Universitatis series Mathematics and Informatics, 2012, 27(2), 175-190.

Zh. Sun, G. Fox, W. Gu and Zh. Li: A Parallel Clustering Method Combined Information Bottleneck Theory and Centroid Based Clustering, The Journal of Supercomputing, 2014, 69(1), 452-467, DOI: 10.1007/s11227-014-1174-1.

P.-N. Tan, M. Steinbach and V. Kumar: Cluster Analysis: Basic Concepts and Algorithms, Chapter 8 / Introduction to Data Mining, Addison-Wesley, 2006, 487-567.

V. Subbotin and V. Steshenko: Problemy obespecheniya bortovoy kosmicheskoy apparatury kosmicheskikh apparatov elektronnoy komponentnoy basoy (in Russian: Problems of Supply on-Board Space Equipment of Spaceships with Components), Kompo-

nenty i tekhnologii, 2011, 11, 10-12.

A. Weber: Uber den Standort der Industrien, Erster Teil: Reine Theorie des Standortes, 1922, Tubingen, Mohr.

E. Weiszfeld: Sur le point sur lequel la somme des distances de n points donnes est minimum, Tohoku Mathematical Journal, 1937, 43(1), 335-386.

G.Wesolowsky: The Weber problem: History and perspectives, Location Science, 1982, 1, 5-23.

UCI Machine Learning Repository, URL: ttps://archive.ics.uci.edu/ml/datasets.html


Refbacks

  • There are currently no refbacks.




© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)