Extremal Optimization Applied to the Minimum Order Frequency Assignment Problem

Authors

Keywords:

Frequency assignment problem, Computational intelligence, Evolutionary computation, Extremal optimization, Meta-heuristic algoritms

Abstract

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

Download data is not yet available.

Author Biographies

Pedro Gomez-Meneses, Universidad Católica de la Santísima Concepción, Concepción, Biobío, 4090541, Chile.

Pedro Gomez-Meneses received his B. Sc. degree in Engineering, B. Eng. in Informatic Civil Engineering, PG. Dip. in Industrial Engineering from Universidad de Concepción, Chile. He received his Ph.D. degree in Information Technology from Bond University, Australia. He is currently assistant professor in the Department of Informatic Engineering at the Universidad Católica de la Santísima Concepción (UCSC), Chile. He has been Head of the Informatic Civil Engineering Career and Head of the Department of Informatic Engineering at the UCSC. His research interests are in the area of nature-inspired computation, metaheuristic search methods, combinatorial optimization and machine learning.

Héctor Ayala, Universidad Católica de la Santísima Concepción, Concepción, Biobío, 4090541, Chile.

Héctor Ayala received his B.Sc. degree in Engineering, and Informatic Civil Engineer from the Universidad Católica de la Santísima Concepción, Concepción, Chile. He has experience in database and machine learning. His research interests are machine learning, combinatorial optimization and metaheuristic methods.

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.

Published

2023-01-17

How to Cite

Gomez-Meneses, P., & Ayala, H. (2023). Extremal Optimization Applied to the Minimum Order Frequency Assignment Problem. IEEE Latin America Transactions, 21(3), 466–474. Retrieved from https://latamt.ieeer9.org/index.php/transactions/article/view/7527