CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Bounded-Diameter MST Instances with Hybridization of Multi-Objective EA

by Soma Saha, Rajeev Kumar
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 18 - Number 4
Year of Publication: 2011
Authors: Soma Saha, Rajeev Kumar
10.5120/2273-2938

Soma Saha, Rajeev Kumar . Bounded-Diameter MST Instances with Hybridization of Multi-Objective EA. International Journal of Computer Applications. 18, 4 ( March 2011), 17-25. DOI=10.5120/2273-2938

@article{ 10.5120/2273-2938,
author = { Soma Saha, Rajeev Kumar },
title = { Bounded-Diameter MST Instances with Hybridization of Multi-Objective EA },
journal = { International Journal of Computer Applications },
issue_date = { March 2011 },
volume = { 18 },
number = { 4 },
month = { March },
year = { 2011 },
issn = { 0975-8887 },
pages = { 17-25 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume18/number4/2273-2938/ },
doi = { 10.5120/2273-2938 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:05:25.186636+05:30
%A Soma Saha
%A Rajeev Kumar
%T Bounded-Diameter MST Instances with Hybridization of Multi-Objective EA
%J International Journal of Computer Applications
%@ 0975-8887
%V 18
%N 4
%P 17-25
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Bounded Diameter (a.k.a Diameter Constraint) Minimum Spanning Tree (BDMST/DCMST) is a well-known combinatorial optimization problem. In this paper, we recast a few well-known heuristics, which are evolved for BDMST problem to a Bi-Objective Minimum Spanning Tree (BOMST) problem and then obtain Pareto fronts. After examining Pareto fronts, it is concluded that none of the heuristics provides the superior solution across the complete range of the diameter. We have used a Multi-Objective Evolutionary Algorithm (MOEA) approach, Pareto Converging Genetic Algorithm (PCGA), to improve the Pareto front for BOMST, which in turn provides better solution for BDMST instances. We have considered edge-set encoding to represent MST and then applied recombination operators having strong heritability and mutation operators having negligible complexity to improve the solutions. Analysis of MOEA solutions confirms the improvement of Pareto front solutions across the complete range of the diameter over Pareto front solutions generated from individual heuristics. We have considered multi-island scheme using Inter-Island rank histogram and performed multiple run of the algorithm to avoid from trapping into local-optimal solution-set.

References
  1. Abdalla, A. 2001. Computing a Diameter-Constrained Minimum Spanning Tree. Doctoral thesis, The School of Electrical Engineering and Computer Science, University of Central Florida, Florida.
  2. Bala, K., Petropoulos, K., and Stern, T. E. 1993. Multicasting in a linear lightwave network. In IEEE INFOCOM'93, 1350–1358.
  3. Binh, H. T. T., McKay, R. I., Hoai, N. X., and Nghia, N. D. 2009. New Heuristic and Hybrid Genetic Algorithm for Solving the Bounded Diameter Minimum Spanning Tree Problem. ACM.
  4. Bookstein, A. and Klein, S. T. 1996. Compression of correlated bit-vectors. Information Systems, 16:110–118.
  5. Deb, K. 2001. Multi-Objective Optimization using Evolutionary Algorithms. Jon Wiley Sons, Chichester.
  6. Deb, K. and Jain, S. 2002. Running performance metrices for evolutionary multiobjective optimization. SEAL'02, 13–20.
  7. Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197.
  8. Deo, N. and Abdalla, A. 2000. Computing a diameter-constrained minimum spanning tree in parallel. Lecture Notes in Computer Science, 1767:17–31.
  9. Garey, M. R., and Johnson, D. S. 1979. Computers and interactibility: A guide to the theory of NP- Completeness. W. H. Freeman, New York.
  10. Julstrom, B. A. 2009. Greedy heuristics for the bounded diameter minimum spanning tree problem. JOURNAL of Experimental Algorithmics (JEA), 14:1.1:1–1.1:14.
  11. Julstrom, B. A., and Raidl, G. R. 2003. A Permutation Coded Evolutionary Algorithm for the Bounded Diameter Minimum Spanning Tree Problem. In GECCO'03: Proceedings of the Genetic and Evolutionary Computation Conference, 2–7.
  12. Knowles, J. D. and Corne, D. W. 2000. Approximating the non-dominated front using the Pareto achieved evolution strategy. Evolutionary Computation, 8(2):149–172.
  13. Knowles, J. D. and Corne, D. W. 2002. On metrices for comparing nondominated sets. In Congress Evolutionary Computation (CEC'02), volume I, 711–716, Honolulu, Hawaii, IEEE.
  14. Kumar, R., Bal, B. K., and Rockett, P. I. 2009. Multiobjective Genetic Programming Approach to Evolving Heuristics for the Bounded Diameter Minimum Spanning Tree Problem. GECCO'09.
  15. Kumar, R. and Rockett, P. I. 1997. Assessing the convergence of rank-based multiobjective genetic algorithms. In IEE/ IEEE 2ndInt. Conf. Genetic Algorithms in Engineering Systems: Innovations Applications (GALESIA-97), 19–23, Glasgow, UK. IEE Conference Publication No. 446.
  16. Kumar, R. and Rockett, P. I. 2002. Improved sampling of the Pareto-front in multiobjective genetic optimization by steady-state evolution: A Pareto converging genetic algorithm. MIT press, 10(3):283–314.
  17. Kumar, R. and Singh, P. K. 2007. On quality performance of heuristic and evolutionary algorithms for biobjective minimum spanning trees. In GECCO '07: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, 2259, New York,m USA. ACM Press.
  18. Kumar, R., Singh, P. K., and Chakrabarti, P. P. 2005. Multiobjective EA Approach for Improved Quality of Solutions for Spanning Tree Problem. In EMO-05: 3rd International Conference on Evolutionary Multi- Criterion Optimization, 811–825, Guanajuato, Mexico. Springer Berlin, Heidelberg.
  19. Neumann, F. and Wegener, I. 2006. Minimum spanning trees made easier via multi-objective optimization. Natural Computing, 5:305–319.
  20. Nghia, N. D. and Binh, H. T. T. 2008. Heuristic Algorithms for Solving Bounded Diameter Minimum Spanning Tree Problem and Its Application to Genetic Algorithm Development. Advances in Greedy Algorithms, 586.
  21. Raidl, G. R. and Julstrom, B. A. 2003. Greedy heuristics and an Evolutionary Algorithm for the Bounded-Diameter Minimum Spanning Tree Problem. SAC'03:18th ACM Symposium on Applied Computing, 747–752.
  22. Raymond, K. 1989. A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7:61–77.
  23. Saha, S., Aslam, M., and R. Kumar. 2010. Assessing the Performance of Bi-Objective MST for Euclidean and Non-Euclidean Instances. In Proceedings of International Conference of Contemporary Computing (IC'03), volume I, 229–240, Noida, India. Springer.
  24. Saha, S. and Kumar, R. 2011. Improvement of Bounded-Diameter MST Instances with Hybridization of Multi-Objective EA. In Proceedings of International Conference on Communication, Computing & Security (ICCCS'11), Odissa, India. ACM.
  25. Singh, A. and Gupta, A. K. 2007. Impoved Heuristics for the Bounded-Diameter Minimum Spanning Tree Problem. JOURNAL Soft Computing, 11:911–921.
  26. Zitzler, E., Laumanns, M., and Thiele, L. 2002. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In Evolutionary Methods for Design, Optimization and Control, 95–100, CIMNE, Bercelona, Spain.
  27. Zitzler, E. and Thiele, L. 1999. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3(4):257–271.
Index Terms

Computer Science
Information Sciences

Keywords

Combinatorial optimization multi-objective optimization heuristics MST BDMST problem evolutionary algorithm Pareto front Edge list encoding

Powered by PhDFocusTM