Improved Multi–Objective Firefly Algorithms to Find Optimal Golomb Ruler Sequences for Optimal Golomb Ruler Channel Allocation

Authors: Shonak Bansal, Prince Jain, Arun Kumar Singh, Neena Gupta

Abstract:

Recently nature–inspired algorithms have widespread use throughout the tough and time consuming multi–objective scientific and engineering design optimization problems. In this paper, we present extended forms of firefly algorithm to find optimal Golomb ruler (OGR) sequences. The OGRs have their one of the major application as unequally spaced channel–allocation algorithm in optical wavelength division multiplexing (WDM) systems in order to minimize the adverse four–wave mixing (FWM) crosstalk effect. The simulation results conclude that the proposed optimization algorithm has superior performance compared to the existing conventional computing and nature–inspired optimization algorithms to find OGRs in terms of ruler length, total optical channel bandwidth and computation time.

Keywords: Channel allocation, conventional computing, four–wave mixing, nature–inspired algorithm, optimal Golomb ruler, Lévy flight distribution, optimization, improved multi–objective Firefly algorithms, Pareto optimal.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1125555

References:

[1] W. C. Kwong, and G. C. Yang, “An Algebraic Approach to the Unequal–Spaced Channel–Allocation Problem in WDM Lightwave Systems”, IEEE Transactions on Communications, Vol. 45, No. 3, pp. 352–359, March–1997.
[2] V. L. L. Thing, P. Shum, and M. K. Rao, “Bandwidth–Efficient WDM Channel Allocation for Four–Wave Mixing–Effect Minimization”, IEEE Transactions on Communications, Vol. 52, No. 12, pp. 2184–2189, December 2004.
[3] O. K. Tonguz and B. Hwang, “A Generalized Suboptimum Unequally Spaced Channel Allocation Technique—Part II: In coherent WDM systems”, IEEE Transactions on Communications, Vol. 46, pp. 1186–1193, September–1998.
[4] R. Randhawa, J. S. Sohal, R. S. Kaler, “Optimum Algorithm for WDM Channel Allocation for Reducing Four–Wave Mixing Effects”, Optik 120 (2009), pp. 898–904, 2009.
[5] G. S. Bloom and S. W. Golomb, “Applications of Numbered Undirected Graphs”, Proceedings of the IEEE, Vol. 65, No. 4, pp. 562–570, April–1977.
[6] J. B. Shearer, “Some New Disjoint Golomb Rulers”, IEEE Transactions on Information Theory, Vol. 44, No. 7, pp. 3151–3153, November–1998.
[7] Distributed.net, “Project OGR”. Available at http://www.distributed.net/ogr.
[8] K. Drakakis and S. Rickard, “On the Construction of Nearly Optimal Golomb Rulers by Unwrapping Costas Arrays”, Contemporary Engineering Sciences, Vol. 3, No. 7, pp. 295–309, July–2010.
[9] S. Bansal, “Optimal Golomb Ruler Sequence Generation for FWM Crosstalk Elimination: Soft Computing Versus Conventional Approaches”, Applied Soft Computing, Vol. 22, pp. 443–457, September–2014.
[10] http://mathworld.wolfram.com/PerfectRuler.html.
[11] http://mathworld.wolfram.com/GolombRuler.html.
[12] C. Meyer and P. A. Papakonstantinou, “On the complexity of constructing Golomb Rulers”, Discrete Applied Mathematics, Vol. 157, pp. 738–748, 2009.
[13] N. Memarsadegh, “Golomb Patterns: Introduction, Applications, and Citizen Science Game”, Information Science and Technology (IS&T), Seminar Series NASA GSFC, September 11, 2013. Available at http://istcolloq.gsfc.nasa.gov/fall2013/presentations/memarsadeghi.pdf.
[14] J. P. Robinson, “Optimum Golomb Rulers”, IEEE Transactions on Computers, Vol. 28, No. 12, pp. 183–184, December–1979.
[15] J. B. Shearer, “Some New Optimum Golomb Rulers”, IEEE Transactions on Information Theory, Vol. 36, pp. 183–184, January–1990.
[16] C. Cotta, I. Dotú, A. J. Fernández, and P. V. Hentenryck, “A Memetic Approach to Golomb Rulers”, Parallel Problem Solving from Nature–PPSN IX, Lecture Notes in Computer Science, Vol. 4193, pp. 252–261, Springer–Verlag Berlin Heidelberg, September 9–13, 2006.
[17] S. W. Soliday, A. Homaifar and Gary L. Lebby, “Genetic Algorithm Approach to the Search for Golomb Rulers”, Proceedings of the Sixth International Conference on Genetic Algorithms (ICGA–95), Morgan Kaufmann, pp. 528–535, 1995.
[18] J. P. Robinson, “Genetic Search for Golomb Arrays”, IEEE Transactions on Information Theory, Vol. 46, No. 3, pp. 1170–1173, May–2000.
[19] I. Dotú, P. V. Hentenryck, “A Simple Hybrid Evolutionary Algorithm for Finding Golomb Rulers”, Evolutionary Computation, 2005, The 2005 IEEE Congress on, Vol. 3, pp. 2018–2023, September 2–5, 2005.
[20] N. Ayari; Thé Van Luong and A. Jemai, “A Hybrid Genetic Algorithm for Golomb Ruler Problem”, ACS/IEEE International Conference on Computer Systems and Applications (AICCSA–2010), pp.1–4, May 16–19, 2010.
[21] S. Bansal, S. Kumar and P. Bhalla, “A Novel Approach to WDM Channel Allocation: Big Bang–Big Crunch Optimization”, In the Proceeding of Zonal Seminar on Emerging Trends in Embedded System Technologies (ETECH–2013) organized by The Institution of Electronics and Telecommunication Engineers (IETE)”, Chandigarh Centre, Chandigarh, pp. 80–81, 2013.
[22] S. Bansal and K. Singh, “A Novel Soft–Computing Algorithm for Channel Allocation in WDM Systems”, International Journal of Computer Applications (IJCA), Vol. 85, No. 9, pp. 19–26, January–2014.
[23] K. Singh, “Soft Computing Algorithms fot WDM Channel Allocation for Reducing FWM Crosstalk”, M.Tech. Thesis, Department of Electronics and Communication Engineering, Institute of Science and Technology, Klawad, India, December–2013.
[24] S. Bansal, R. Chauhan and P. Kumar, “A Cuckoo Search based WDM Channel Allocation Algorithm”, International Journal of Computer Applications (IJCA), Vol. 96, No. 20, pp. 6–12, June–2014.
[25] S. Bali, S. Bansal and A. Kamboj, “A Novel Hybrid Multi–objective BB–BC Based Channel Allocation Algorithm to Reduce FWM Crosstalk and its Comparative Study”, International Journal of Computer Applications (IJCA), Vol. 124, No. 12, pp. 38–45, August–2015.
[26] P. Jain, S. Bansal, A. K. Singh, and N. Gupta, “Golomb Ruler Sequences Optimization for FWM Crosstalk Reduction: Multi–population Hybrid Flower Pollination Algorithm”, Progress in Electromagnetics Research Symposium (PIERS), Prague, Czech Republic, pp. 2463–2467, July 06–09, 2015.
[27] S. Bali, S. Bansal, and A. Kamboj, “A Novel Hybrid Multi–objective BB–BC Based Channel Allocation Algorithm to Reduce FWM Crosstalk and its Comparative Study”, International Journal of Computer Applications (IJCA), Vol. 124, No. 12, pp. 38–45, August–2015.
[28] X.–S. Yang, “Flower Pollination Algorithm for Global Optimization”, in: Unconventional Computation and Natural Computation, Lecture Notes in Computer Science, Vol. 7445, Springer, Berlin, pp. 240–249, 2012.
[29] R. Storn and K. V. Price, “Differential Evolution—A Simple and Efficient Heuristic for Global Optimization Over Continuous Spaces,” Journal of Global Optimization, Vol. 11, No. 4, pp. 341–359, December–1997.
[30] S. Koziel and X.–S. Yang, “Computational Optimization, Methods and Algorithms”, Studies in Computational Intelligence, Vol. 356, Springer, 2011.
[31] X.–S. Yang, “Multiobjective Firefly Algorithm for Continuous Optimization”, Engineering with Computers, Vol. 29, No. 2, pp. 175–184, 2013.
[32] X.–S. Yang, “Firefly Algorithms for Multimodal Optimization”, in: Stochastic Algorithms: Foundations and Applications (SAGA–2009), Lecture Notes in Computer Science, Vol. 5792, Springer–Verlag, Berlin, pp. 169–178, 2009.
[33] X.–S. Yang, “Review of Metaheuristics and Generalized Evolutionary Walk Algorithm”, International Journal of Bio–Inspired Computation (IJBIC), Vol. 3, No. 2, pp. 77–84, 2011.
[34] A. Dollas, W. T. Rankin, and D. McCracken, “A New Algorithm for Golomb Ruler Derivation and Proof of the 19 Mark Ruler”, IEEE Transactions on Information Theory, Vol. 44, No. 1, pp. 379–382, January–1998.
[35] J. B. Shearer, “Golomb Ruler Table”, Mathematics Department, IBM Research. Available at http://www.research.ibm.com/people/s/shearer/grtab.html, 2001.