Multiobjective evolutionary algorithm for frequency assignment problem in satellite communications

详细信息    查看全文

• 作者：Jiahai Wang (1)
  Yiqiao Cai (2)
  
  1. Department of Computer Science ; Sun Yat-sen University ; Guangzhou ; 510006 ; People鈥檚 Republic of China
  2. College of Computer Science and Technology ; Huaqiao University ; Xiamen ; 361021 ; People鈥檚 Republic of China
  
• 关键词：Frequency assignment problem ; Multiobjective optimization ; Differential evolution ; Decomposition ; Subproblem ; dependent heuristic assignment
• 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：19
• 期：5
• 页码：1229-1253
• 全文大小：2,855 KB
• 参考文献：1. Aardal KI, van Hoesel SPM, Koster AMCA, Mannino C, Sassano A (2007) Models and solution techniques for frequency assignment problems. Ann Oper Res 153(1):79鈥?29
  2. Alcal谩-Fdez J, S谩nchez L, Garc铆a S (2008) KEEL: a software tool to assess evolutionary algorithms to data mining problems. Soft Comput 13(3):307鈥?18
  3. Bechikh, S, Said, LB, Gh茅dira, K (2011) Searching for knee regions of the Pareto front using mobile reference points. Soft Comput 15: pp. 1807-1823 CrossRef
  4. Castro-Gutierrez J, Landa-Silva D, P茅rez JM (2011) Nature of real world multi-objective vehicle routing with evolutionary algorithms. In: Proceedings of IEEE International Conference on SMC, pp 257鈥?64
  5. Czyzzak, P, Jaszkiewicz, A (1998) Pareto simulated annealing: a metaheuristic technique for multiple-objective combinatorial optimization. J Multi-Criteria Decis Anal 7: pp. 34-47 CrossRef
  6. Das, S, Suganthan, PN (2011) Differential evolution: a survey of the state-of-the-art. IEEE Trans Evolut Comput 15: pp. 4-31 CrossRef
  7. Deb K, Jain H (2014) An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part I: solving problems with box constraints. In: Proceedings of IEEE Transactions on Evolutionary Computation, 2014 (in press)
  8. Deb, K, Pratap, A, Agarwal, S, Meyarivan, T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evolut Comput 6: pp. 182-197 CrossRef
  9. Derrac, J, Garc铆a, S, Molina, D, Herrera, F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evolut Comput 1: pp. 3-18 CrossRef
  10. Funabiki, N, Nishikawa, S (1997) A gradual neural-network approach for frequency assignment in satellite communication systems. IEEE Trans Neural Netw 8: pp. 1359-1370 CrossRef
  11. Garcia-Najera, A, Bullinaria, J (2011) An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows. Comput Oper Res 38: pp. 287-300 CrossRef
  12. Hopfield, JJ, Tank, DW (1985) Neural computation of decisions in optimization problems. Biol Cybern 52: pp. 141-152
  13. Ishibuchi H, Hitotsuyanagi Y, Tsukamoto N, Nojima Y (2008) Use of heuristic local search for single-objective optimization in multiobjective memetic algorithms. In: Proceedings of parallel problem solving from nature-PPSN X, pp 743鈥?52
  14. Ishibuchi, H, Yoshida, T, Murata, T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7: pp. 204-223 CrossRef
  15. Jaszkiewicz, A (2003) Do multiple objective metaheuristics deliver on their promises? A computational experiment on the set covering problem. IEEE Trans Evolut Comput 7: pp. 133-143 CrossRef
  16. Ke, L, Zhang, Q, Battiti, R (2013) MOEA/D-ACO: a multiobjective evolutionary algorithm using decomposition and ant colony. IEEE Trans Cybern 43: pp. 1845-1859 CrossRef
  17. Konstantinidis, A, Yang, K (2011) Multi-objective energy-efficient dense deployment in wireless sensor networks using a hybrid problem-specific MOEA/D. Appl Soft Comput 11: pp. 4117-4134 CrossRef
  18. Konstantinidis, A, Yang, K (2011) Multi-objective k-connected deployment and power assignment in WSNs using a problem-specific constrained evolutionary algorithm based on decomposition. Comput Commun 34: pp. 83-98 CrossRef
  19. Kurokawa, T, Kozuka, S (1993) A proposal of neural networks for the optimum frequency assignment problem. Trans IEICE J76鈥揃鈥揑I: pp. 811-819
  20. Lacomme, P, Prins, C, Sevaux, M (2006) A genetic algorithm for a biobjective capacitated arc routing problem. Comput Oper Res 33: pp. 3473-3493 CrossRef
  21. Li H, Landa-silva D, Gandibleux X (2010) Evolutionary multi-objective optimization algorithms with probabilistic representation based on pheromone trails. In: Proceedings of the IEEE congress on evolutionary computation, pp 2307鈥?314
  22. Li, H, Zhang, Q (2009) Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Trans Evolut Comput 12: pp. 284-302 CrossRef
  23. Li, H, Landa-Silva, D (2011) An adaptive evolutionary multi-objective approach based on simulated annealing. Evolut Comput 19: pp. 561-595 CrossRef
  24. Liu W, Shi H, Wang L (2007) Minimizing interference in satellite communications using chaotic neural networks. In: Proceeding of the third international conference on natural computation, pp 441鈥?44
  25. Luna, F, Est茅banez, C (2011) Optimization algorithms for large-scale real-world instances of the frequency assignment problem. Soft Comput 15: pp. 975-990 CrossRef
  26. Maximiano MS, Vega-Rodr铆guez MA et al (2009) Multiobjective frequency assignment problem using the MO-VNS and MO-SVNS algorithms. In: Proceedings of the world congress on nature and biologically inspired computing, pp 221鈥?26
  27. Maximiano MS, Vega-Rodr铆guez MA et al (2009) Parameter analysis for differential evolution with Pareto tournaments in a multiobjective frequency assignment problem. In: Proceedings of the 10th international conference on intelligent data engineering and automated learning, pp 799鈥?06
  28. Maximiano, MS, Vega-Rodr铆guez, MA (2013) A new multiobjective artificial bee colony algorithm to solve a real-world frequency assignment problem. Neural Comput Appl 22: pp. 1447-1459 CrossRef
  29. Mei, Y, Tang, K, Yao, X (2011) Decomposition-based memetic algorithm for multi-objective capacitated arc routing problem. IEEE Trans Evolut Comput 15: pp. 151-165 CrossRef
  30. Mizuike, T, Ito, Y (1989) Optimization of frequency assignment. IEEE Trans Commun 37: pp. 1031-1041 CrossRef
  31. Mizuike, T, Ito, Y (1986) Optimum frequency assignment for reduction of cochannel interference. Trans IEICE J69鈥揃: pp. 921-932
  32. Pelton, JN, Oslund, RJ, Marshall, P (2004) Communications satellites: global change agents. Lawrence Erlbaum, Mahwah
  33. Peng W, Zhang Q, Li H (2009) Comparison between MOEA/D and NSGA-II on the multi-objective travelling salesman problem. In: Proceedings of studies in computational intelligence, multi-objective memetic algorithms, vol 171, pp 309鈥?24
  34. Peng W, Zhang Q (2012) Network topology planning using MOEA/D with objective-guided operators. In: Proceedings of parallel problem solving from nature-PPSN II, pp 62鈥?1
  35. Praditwong, K, Harman, M, Yao, X (2011) Software module clustering as a multi-objective search problem. IEEE Trans Softw Eng 37: pp. 264-282 CrossRef
  36. Qu, B-Y, Li, H, Zhao, S-Z, Suganthan, PN, Zhang, Q (2011) Multiobjective evolutionary algorithms: a survey of the state-of-the-art. Swarm Evolut Comput 1: pp. 32-49 CrossRef
  37. Saha, S, Sur-Kolay, S, Dasgupta, P, Bandyopadhyay, S (2009) MAkE: multiobjective algorithm for k-way equipartitioning of a point set. Appl Soft Comput 9: pp. 711-724 CrossRef
  38. Salcedo-Sanz, S, Santiago-Mozos, R, B-Calz鈥檕n, C (2004) A hybrid Hopfield network-simulated annealing approach for frequency assignment in satellite communications systems. IEEE Trans Syst Man Cybern-B Cybern 34: pp. 1108-1116 CrossRef
  39. Salcedo-Sanz, S, B-Calz鈥檕n, C (2005) A hybrid neural-genetic algorithm for the frequency assignment problem in satellite communications. Appl Intell 22: pp. 207-217 CrossRef
  40. Salman, AA, Ahmad, I, Omran, MGH, Mohammad, MG (2010) Frequency assignment problem in satellite communications using differential evolution. Comput Oper Res 37: pp. 2152-2163 CrossRef
  41. Shim, VA, Tan, KC, Cheong, CY (2012) A hybrid estimation of distribution algorithm with decomposition for solving the multiobjective multiple traveling salesman problem. IEEE Trans Syst Man Cybern Part C Rev Appl 42: pp. 682-691 CrossRef
  42. Storn, RM, Price, KV (1997) Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11: pp. 341-359 CrossRef
  43. Talbi, E-G, Basseur, M, Nebro, AJ, Alba, E (2012) Multi-objective optimization using metaheuristics: non-standard algorithms. Int Trans Oper Res 19: pp. 283-305 CrossRef
  44. Tan, KC, Chew, YH, Lee, LH (2006) A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Comput Optim Appl 34: pp. 115-151 CrossRef
  45. Wang J, Cai Y, Yin J (2011) Multi-start stochastic competitive Hopfield neural network for frequency assignment problem in satellite communications. Expert Syst Appl 38(1):131鈥?45
  46. Wang, L, Liu, W, Shi, H (2008) Noisy chaotic neural networks with variable thresholds for the frequency assignment problem in satellite communications. IEEE Trans Syst Man Cybern Part C Rev Appl 38: pp. 209-217 CrossRef
  47. Wang Z, Tang K, Yao X (2010) Multi-objective approaches to optimal testing resource allocation in modular software systems. IEEE Trans Reliab 59(3):563鈥?75
  48. Whalen DJ (2008) Communication satellites: making the global village possible. Available at: http://www.hq.nasa.gov/office/pao/History/satcomhistory.html
  49. Zhang Q, Liu W, Li H (2009) The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. In: Proceedings of IEEE congress on evolutionary computation, pp 1鈥?
  50. Zhang, Q, Li, H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evolut Comput 11: pp. 712-731 CrossRef
  51. Zitzler E, Laumanns M, Thiele L (2002) SPEA2: improving the strength Pareto evolutionary algorithm. In: Proceedings of evolution methods for design, optimization and control applications to industrial problems, pp 95鈥?00
  52. Zitzler, E, Thiele, L (1999) Multi-objective evolutionary algorithms: a comparative study and the strength Pareto approach. IEEE Trans Evolut Comput 3: pp. 257-271 CrossRef
  
• 刊物类别：Engineering
• 刊物主题：Numerical and Computational Methods in Engineering
  Theory of Computation
  Computing Methodologies
  Mathematical Logic and Foundations
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1433-7479

文摘

Satellite communications technology leads to an important improvement in our life and world. The frequency assignment problem (FAP) is a fundamental problem in satellite communication system for providing high-quality transmissions. The whole goal of the FAP in satellite communication system is to minimize co-channel interference between two satellite systems by rearranging frequency assignment. Recently, many metaheuristics, including neural networks and evolutionary algorithms, are proposed for this NP-complete problem. All such algorithms formulate the FAP as a single-objective problem, although it obviously has two objectives and thus essentially is a multiobjective optimization problem. This study explicitly formulates FAP as a multiobjective optimization problem and presents a multiobjective evolutionary algorithm based on decomposition (MOEA/D) with a problem-specific subproblem-dependent heuristic assignment (SHA), called MOEA/D-SHA, for the multiobjective FAP. Simulation results show that the MOEA/D-SHA outperforms significantly general-purpose MOEA/D, and an off-the-shelf multiobjective algorithm, i.e., NSGA-II. The advantages of the MOEA/D-SHA over the state-of-the-art single-objective approaches are also shown.