Extremal Optimization Applied to the Minimum Order Frequency Assignment Problem
Keywords:
Frequency assignment problem, Computational intelligence, Evolutionary computation, Extremal optimization, Meta-heuristic algoritmsAbstract
Extremal Optimization (EO) is a metaheuristic used to solve complex combinatorial optimization problems. However, the behavior of this algorithm has not been studied for various interesting problems. Such as, it is the case of the Minimum Order Frequency Assignment Problem (MO-FAP). Specifically, this problem seeks to minimize the number of frequencies assigned to a group of transceiver, without violating any of the problem’s constraints. In particular, the aim of this study was to use EO to solve the MO-FAP. Furthermore, it was found that EO was able to find the best reported value for most instances of the dataset used for experimentation. Additionally, it was possible to identify how the EO Tau hyperparameter reported better results for much higher values than those reported in the literature. Finally, the difficulty of defining and configuring a fitness function for each element of the solution was evidenced. Therefore, this can affect the effectiveness of the algorithm according to the particular characteristics of the dataset to be solved. Consequently, this opens an opportunity to develop improvements in the form of defining the contribution of each element of the solution to the objective function.
Downloads
References
S. Boettcher and A. G. Percus, “Extremal Optimization: Methods derived from Co-Evolution,” apr 1999.
P. Bak and K. Sneppen, “Punctuated equilibrium and criticality in a simple model of evolution,” Physical Review Letters, vol. 71, pp. 4083–4086, dec 1993.
S. Boettcher and A. G. Percus, “Extremal Optimization for Graph Partitioning,” Physical Review E, vol. 64, p. 26114, 2001.
S. Boettcher and A. G. Percus, “Extremal Optimization: an Evolutionary Local-Search Algorithm,” CoRR, vol. cs.NE/0209, 2002.
S. Boettcher and A. G. Percus, “Extremal optimization at the phase transition of the three-coloring problem,” Phys. Rev. E, vol. 69, p. 66703, 6 2004.
F. L. D. Sousa, V. Vlassov, and F. M. Ramos, “Heat Pipe Design Through Generalized Extremal Optimization,” Heat Transfer Engineering, vol. 25, no. 7, pp. 35–45, 2004.
J. Duch and A. Arenas, “Community detection in complex networks using Extremal Optimization,” Physical Review E, vol. 72, p. 27104,
M. E. Menaï and M. Batouche, “An effective heuristic algorithm for the maximum satisfiability problem,” Applied Intelligence, vol. 24, no. 3, pp. 227–239, 2006.
Y.-W. Chen, Y.-Z. Lu, and P. Chen, “Optimization with extremal dynamics for the traveling salesman problem,” Physica A: Statistical
Mechanics and its Applications, vol. 385, no. 1, pp. 115–123, 2007.
Y.-W. Chen, Y.-Z. Lu, and G.-K. Yang, “Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization
for production scheduling,” The International Journal of Advanced Manufacturing Technology, vol. 36, no. 9, pp. 959–968, 2008.
J. Ding, Y. Lu, and J. Chu, “Extremal optimization for unit commitment problem for power systems,” in 2012 IEEE Power and Energy Society General Meeting, pp. 1–8, 2012.
E. Sidiropoulos, “Spatial resource allocation via extremal optimization enhanced by cell-based local search,” International Journal of Modeling, Simulation, and Scientific Computing, vol. 6, p. 1550020, 2 2015. doi: 10.1142/S1793962315500208.
F. Redoloza and L. Li, “A novel method for well placement design in groundwater management: Extremal optimization,” Advances in Water Resources, vol. 132, 2019.
S. Boettcher, “Ground state properties of the diluted sherrington-kirkpatrick spin glass,” Physical Review Letters, vol. 124, p. 177202,
T. Insights, “Iot connected devices by vertical 2030 | statista.” Web Page, 2020.
Statista, “Internet users in the world 2025 | statista.” Web Page, 2021.
K. I. Aardal, S. P. M. van Hoesel, A. M. C. A. Koster, C. Mannino, and A. Sassano, “Models and solution techniques for frequency assignment problems,” Annals of Operations Research, vol. 153, pp. 79–129, 9 2007.
J. Wang and Y. Cai, “Multiobjective evolutionary algorithm for frequency assignment problem in satellite communications,” Soft Comput., vol. 19, p. 1229–1253, may 2015.
A. Stojanova, D. Bikov, G. Kobeaga, M. Kocaleva, T. Koca, T. Ashley, and T. Balabanov, “Self-organized networks,” Proceedings of the 131st European study group with industry, pp. 18–25, 2017.
W. Hale, “Frequency assignment: Theory and applications,” Proceedings of the IEEE, vol. 68, no. 12, pp. 1497–1514, 1980.
R. Borndörfer, A. Eisenblätter, M. Grötschel, and A. Martin, “Frequency assignment in cellular phone networks,” Annals of Operations Research, vol. 76, pp. 73 – 93, 1998.
A. M. C. A. Koster, Frequency Assignment - Models and Algorithms. PhD thesis, Maastricht University, 1999.
G. Colombo, “A Genetic Algorithm for Frequency Assignment with Problem Decomposition,” Int. J. Mob. Netw. Des. Innov., vol. 1, no. 2, pp. 102–112, 2006.
Lu Liwei and Fan Rongshuang, “Simulated annealing algorithm in solving frequency assignment problem,” in 2010 3rd International
Conference on Advanced Computer Theory and Engineering(ICACTE), vol. 1, pp. 1–361, IEEE, 8 2010.
D. J. Castelino, S. Hurley, and N. M. Stephens, “A tabu search algorithm for frequency assignment,” Annals of Operations Research, vol. 63, no. 2, pp. 301–319, 1996.
K. Alrajhi, J. Thompson, and W. Padungwech, “Tabu Search Hybridized with Multiple Neighborhood Structures for the Frequency Assignment Problem,” in Hybrid Metaheuristics (M. J. Blesa, C. Blum, A. Cangelosi, V. Cutello, A. DI NUOVO, M. Pavone, and E.-G. Talbi, eds.), (Cham), pp. 157–170, Springer International Publishing, 2016.
A. Eisenblatter, H. Geerdes, and I. Siomina, “Integrated Access Point Placement and Channel Assignment for Wireless LANs in an Indoor Office Environment,” in 2007 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, pp. 1–10, 2007.
B. Koo, H. B. Yilmaz, C. Chae, H. Park, J. Ham, and S. Park, “Heuristics for frequency assignment problem with realistic interference
constraints,” in 2016 IEEE International Conference on Communications (ICC), pp. 1–6, 5 2016.
Z. I. Berlin, “CALMA Frequency Assignment Problems,” 2010.
Y.-Z. Lu, Y.-W. Chen, M. Chen, P. Chen, and G.-Q. Zeng, Extremal Optimization: Fundamental, Algorithms and Applications. CRC Press
and Chemical Industrial Press, 10 2016.
A. Kapsalis, P. Chardaire, V. J. Rayward-Smith, and G. D. Smith, “The radio link frequency assignment problem: A case study using
genetic algorithms,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 993, pp. 117–131, 10 1995.
S. Boettcher and A. G. Percus, “Extremal optimization: an evolutionary local-search algorithm,” in Computational Modeling and Problem Solving in the Networked World, pp. 61–77, Springer, 2003.
S. Boettcher and A. G. Percus, “Optimization with extremal dynamics,” Physical Review Letters, vol. 86, pp. 5211–5214, 6 2001.
