Frequency assignment problem in satellite communications using differential evolution. (English) Zbl 1231.90212
Summary: Satellite communications technology has a tremendous impact in refining our world. The frequency assignment problem is of a fundamental importance when it comes to providing high-quality transmissions in satellite communication systems. The NP-complete frequency assignment problem in satellite communications involves the rearrangement of frequencies of one set of carriers while keeping the other set fixed in order to minimize the largest and total interference among carriers. In this paper, we present a number of algorithms, based on differential evolution, to solve the frequency assignment problem. We investigate several schemes ranging from adaptive differential evolution to hybrid algorithms in which heuristic is embedded within differential evolution. The effectiveness and robustness of our proposed algorithms is demonstrated through solving a set of benchmark problems and comparing the results with a number of previously proposed techniques that solve the same problem. Experimental results show that our proposed algorithms, in general, and hybrid ones in particular, outperform the existing algorithms both in terms of the quality of the solutions and computational time.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
combinatorial optimization; differential evolution; evolutionary computations; frequency assignment problem; NP-complete; satellite communicationSoftware:
CALMAReferences:
| [1] | Pelton, J. N.; Oslund, R. J.; Marshall, P., Communications satellites: global change agents (2004), Mahwah, NJ: Lawrence Erlbaum |
| [2] | Whalen DJ. Communications satellites: making the global village possible, \(2008 \langle\) http://www.hq.nasa.gov/office/pao/History/satcomhistory.html \(\rangle \); Whalen DJ. Communications satellites: making the global village possible, \(2008 \langle\) http://www.hq.nasa.gov/office/pao/History/satcomhistory.html \(\rangle \) |
| [3] | Jeruchim M. A survey of interference problems and applications to geostationary satellite networks. In: Proceedings of the IEEE, vol. 65, 1977. p. 317-31.; Jeruchim M. A survey of interference problems and applications to geostationary satellite networks. In: Proceedings of the IEEE, vol. 65, 1977. p. 317-31. |
| [4] | Murphy, R. A.; Pardalos, P. M.; Resende, M. G.C., Frequency assignment problems (1999), Norwell: Norwell Kluwer, MA · Zbl 1253.90137 |
| [5] | Aardal, K. I.; van Hoesel, S. P.M.; Koster, A. M.C. A.; Mannino, C.; Sassano, A., Models and solution techniques for frequency assignment problems, Annals of Operations Research, 153, 1, 79-129 (2007) · Zbl 1157.90005 |
| [6] | Mizuike, T.; Ito, Y., Optimum frequency assignment for reduction of cochannel interference, Transactions on IEICE, J69-B, 9, 921-932 (1986) |
| [7] | Mizuike, T.; Ito, Y., Optimization of frequency assignment, IEEE Transactions on Communications, 37, 10, 1031-1041 (1989) |
| [8] | Kurokawa, T.; Kozuka, S., A proposal of neural network for the optimum frequency assignment problem, Transactions on IEICE Journal, 76-B-II, 10, 811-819 (1993) |
| [9] | Funabiki, N.; Nishikawa, S., A gradual neural-network approach for frequency assignment in satellite communication systems, IEEE Transactions on Neural Networks, 8, 6, 1359-1370 (1997) |
| [10] | Sanz, S. S.; Mozos, R. S.; Calzon, C. B., A hybrid Hopfield network-simulated annealing approach for frequency assignment problem in satellite communications systems, IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, 34, 2, 1108-1116 (2004) |
| [11] | Sanz, S. S.; Calzon, C. B., A hybrid neural-genetic algorithm for the frequency assignment problem in satellite communications, Applied Intelligence, 3, 22, 207-217 (2005) · Zbl 1086.90503 |
| [12] | Liu W, Shi H, Wang L. Minimizing interference in satellite communications using chaotic neural networks. In: IEEE third international conference on natural computation (ICNC 2007), 2007. p. 441-4.; Liu W, Shi H, Wang L. Minimizing interference in satellite communications using chaotic neural networks. In: IEEE third international conference on natural computation (ICNC 2007), 2007. p. 441-4. |
| [13] | Wang, L.; Liu, W.; Shi, H., Noisy chaotic neural networks with variable thresholds for the frequency assignment problem in satellite communications, IEEE Transactions on Systems, Man, and Cybernetics—Part C: Applications and Reviews, 38, 2, 209-217 (2008) |
| [14] | Storn R, Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical report TR 95-012, International Computer Science Institute, Berkeley, CA; 1995.; Storn R, Price K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical report TR 95-012, International Computer Science Institute, Berkeley, CA; 1995. · Zbl 0888.90135 |
| [15] | Storn, R. M.; Price, K. V., Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11, 4, 341-359 (1997) · Zbl 0888.90135 |
| [16] | Rae, A.; Parameswaran, S., Synthesizing application-specific heterogeneous multiprocessor using differential evolution, IEICE Transactions on Fundamentals E, 84-A, 12, 3125-3131 (2001) |
| [17] | Rzadca K, Seredynshi F. Heterogeneous multiprocessor scheduling with differential evolution. In: Proceedings of congress on evolutionary computation, 2005. p. 2840-7.; Rzadca K, Seredynshi F. Heterogeneous multiprocessor scheduling with differential evolution. In: Proceedings of congress on evolutionary computation, 2005. p. 2840-7. |
| [18] | Feoktistov V, Janaqi S. Generalization of the strategies in differential evolution. In: Proceedings of the 18th international parallel and distributed processing symposium, 2004. p. 165-70.; Feoktistov V, Janaqi S. Generalization of the strategies in differential evolution. In: Proceedings of the 18th international parallel and distributed processing symposium, 2004. p. 165-70. |
| [19] | Paterlini S, Krink T. High performance clustering with differential evolution. In: Proceedings of the IEEE congress on evolutionary computation, vol. 2, 2004. p. 2004-11.; Paterlini S, Krink T. High performance clustering with differential evolution. In: Proceedings of the IEEE congress on evolutionary computation, vol. 2, 2004. p. 2004-11. |
| [20] | Karaboga, D.; Okdem, S., A simple and global optimization algorithm for engineering problems: differential evolution algorithm, Turkish Journal of Electrical Engineering, 12, 1, 53-60 (2004) |
| [21] | Xue F, Sanderson A, Graves R. Pareto-based multi-objective differential evolution. In: Proceedings of the IEEE congress on evolutionary computation, vol. 2, 2003. p. 862-9.; Xue F, Sanderson A, Graves R. Pareto-based multi-objective differential evolution. In: Proceedings of the IEEE congress on evolutionary computation, vol. 2, 2003. p. 862-9. |
| [22] | Omran M, Engelbrecht A, Salman A. Differential evolution methods for unsupervised image classification. In: Proceedings of the IEEE congress on evolutionary computation, vol. 2, 2005. p. 966-73.; Omran M, Engelbrecht A, Salman A. Differential evolution methods for unsupervised image classification. In: Proceedings of the IEEE congress on evolutionary computation, vol. 2, 2005. p. 966-73. |
| [23] | Storn R. Differential evolution design for an iir-filter with requirements for magnitude and group delay. Technical report TR 95-026, International Computer Science Institute, Berkeley, CA; 1995.; Storn R. Differential evolution design for an iir-filter with requirements for magnitude and group delay. Technical report TR 95-026, International Computer Science Institute, Berkeley, CA; 1995. |
| [24] | Babu B, Angira R. Optimization of non-linear functions using evolutionary computation. In: Proceedings of the 12th ISME international conference on mechanical engineering, India, 2001. p. 153-7.; Babu B, Angira R. Optimization of non-linear functions using evolutionary computation. In: Proceedings of the 12th ISME international conference on mechanical engineering, India, 2001. p. 153-7. |
| [25] | Angira R, Babu B. Evolutionary computation for global optimization of non-linear chemical engineering processes. In: Proceedings of International Symposium on Process Systems Engineering and Control, Mumbai, 2003. p. 87-91.; Angira R, Babu B. Evolutionary computation for global optimization of non-linear chemical engineering processes. In: Proceedings of International Symposium on Process Systems Engineering and Control, Mumbai, 2003. p. 87-91. |
| [26] | Abbass H (editor). A memetic pareto evolutionary approach to artificial neural networks. Lecture notes in artificial intelligence, vol. 2256. Berlin, Germany: Springer-Verlag; 2002.; Abbass H (editor). A memetic pareto evolutionary approach to artificial neural networks. Lecture notes in artificial intelligence, vol. 2256. Berlin, Germany: Springer-Verlag; 2002. |
| [27] | Babu B, Jehan M. Differential evolution for multi-objective optimization. In: Proceedings of the IEEE congress on evolutionary computation, vol. 4, 2003. p. 2696-703.; Babu B, Jehan M. Differential evolution for multi-objective optimization. In: Proceedings of the IEEE congress on evolutionary computation, vol. 4, 2003. p. 2696-703. |
| [28] | Price K, Storn R. De web site, 2005. URL \(\langle\) http://www.ICSI.Berkeley.edu/∼storn/code.html \(\rangle \); Price K, Storn R. De web site, 2005. URL \(\langle\) http://www.ICSI.Berkeley.edu/∼storn/code.html \(\rangle \) |
| [29] | Storn R. On the usage of differential evolution for function optimization. In: The North American fuzzy information processing society conference, Berkeley, 1996. p. 519-23.; Storn R. On the usage of differential evolution for function optimization. In: The North American fuzzy information processing society conference, Berkeley, 1996. p. 519-23. |
| [30] | Salman AA, Mehrotra K, Mohan CK. Adaptive linkage crossover. In: Proceedings of ACM symposium on applied computing, 1998. p. 338-42.; Salman AA, Mehrotra K, Mohan CK. Adaptive linkage crossover. In: Proceedings of ACM symposium on applied computing, 1998. p. 338-42. |
| [31] | Salman AA, Mohan CK. Linkage crossover operator for genetic algorithms. PhD thesis, Syracuse University, Syracuse, NY; 1999.; Salman AA, Mohan CK. Linkage crossover operator for genetic algorithms. PhD thesis, Syracuse University, Syracuse, NY; 1999. |
| [32] | Tasgetiren MF, Pan Q-K, Suganthan PN, Liang Y-C. A discrete differential evolution algorithm for the no-wait flowshop scheduling problem with total flowtime criterion. In: Proceedings of the 2007 IEEE symposium on computational intelligence in scheduling, 2007. p. 338-42.; Tasgetiren MF, Pan Q-K, Suganthan PN, Liang Y-C. A discrete differential evolution algorithm for the no-wait flowshop scheduling problem with total flowtime criterion. In: Proceedings of the 2007 IEEE symposium on computational intelligence in scheduling, 2007. p. 338-42. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
