research-article

Elementary landscapes of frequency assignment problems

Authors:

L. Darrell Whitley,

Francisco Chicano,

Enrique Alba,

Francisco LunaAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 1409 - 1416

https://doi.org/10.1145/1830483.1830743

Published: 07 July 2010 Publication History

Get Access

Abstract

We analyze various forms of the Frequency Assignment Problem using the theory of elementary landscapes. We show that three variants of the Frequency Assignment Problem are either directly an Elementary Landscape, or are a superposition of two Elementary Landscapes. We also examine the computability of neighborhood averages for partial neighborhoods.

References

[1]

J. W. Barnes, B. Dimova, and S. P. Dokov. The theory of elementary landscapes. Applied Mathematics Letters, 16(3):337--343, April 2003.

Crossref

Google Scholar

[2]

B. Codenotti and L. Margara. Local properties of some NP-complete problems. TR 92-021, International Computer Science Institute, Berkeley, CA, 1992.

Google Scholar

[3]

B. Colletti and J. W. Barnes. Linearity in the traveling salesman problem. Applied Mathematics Letters, 13(3):27--32, April 2000.

Crossref

Google Scholar

[4]

B. Dimova, J. Wesley Barnes, and E. Popova. Arbitrary elementary landscapes & AR(1) processes. Appl. Math., Lett., 18(3):287--292, 2005.

Google Scholar

[5]

L. K. Grover. Local search and the local structure of NP-complete problems. Operations Research Letters, 12:235--243, 1992.

Digital Library

Google Scholar

[6]

F. Luna, C. Blum, E. Alba, A. J. Nebro, ACO vs EAs for solving a real-world frequency assignment problem in GSM networks, in: Genetic and Evolutionary Computation Conference (GECCO 2007), 2007, pp. 94--101.

Digital Library

Google Scholar

[7]

A. Solomon, J. W. Barnes, S. P. Dokov, and R. Acevedo. Weakly symmetric graphs, elementary landscapes, and the TSP. Appl. Math. Lett., 16(3):401--407, 2003.

Crossref

Google Scholar

[8]

P. F. Stadler. Toward a theory of landscapes. In R. Lopéz-Peña et al., editors, Complex Systems and Binary Networks, pages 77--163. Springer Verlag, 1995.

Google Scholar

[9]

P F. Stadler. Landscapes and their correlation functions. Journal of Mathematical Chemistry, 20:1--45, 1996.

Crossref

Google Scholar

[10]

A. Sutton, D. Whitley and A. Howe. A Polynomial Time Computation of the Exact Correlation Structure of k-Satisfiability Landscapes. In Genetic and Evolutionary Computation Conference, pages 365--372. ACM. July 2009.

Digital Library

Google Scholar

[11]

L. D. Whitley and A. M. Sutton. Partial neighborhoods of elementary landscapes. In Genetic and Evolutionary Computation Conference, pages 381--388. ACM, July 2009.

Digital Library

Google Scholar

[12]

L. D. Whitley, D. Hains and A. Howe. Tunneling Between Optima: Partition Crossover for the Traveling Salesman Problem. In Genetic and Evolutionary Computation Conference, pages 915--922. ACM, July 2009.

Digital Library

Google Scholar

Cited By

View all

Klemm KStadler P(2013)Rugged and Elementary LandscapesTheory and Principled Methods for the Design of Metaheuristics10.1007/978-3-642-33206-7_3(41-61)Online publication date: 12-Nov-2013
https://doi.org/10.1007/978-3-642-33206-7_3
Whitley DChicano F(2012)Quasi-elementary Landscapes and Superpositions of Elementary LandscapesRevised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 721910.5555/2961491.2961512(277-291)Online publication date: 16-Jan-2012
https://dl.acm.org/doi/10.5555/2961491.2961512
Alba ELuque GNesmachnow S(2012)Parallel metaheuristics: recent advances and new trendsInternational Transactions in Operational Research10.1111/j.1475-3995.2012.00862.x20:1(1-48)Online publication date: 13-Aug-2012
https://doi.org/10.1111/j.1475-3995.2012.00862.x
Show More Cited By

Index Terms

Elementary landscapes of frequency assignment problems
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Elementary landscape decomposition of the frequency assignment problem

The Frequency Assignment Problem (FAP) is an important problem that arises in the design of radio networks, when a channel has to be assigned to each transceiver of the network. This problem is a generalization of the graph coloring problem. In this ...
Fitness landscapes and graphs: multimodularity, ruggedness and neutrality
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

The performances of evolutionary algorithms (genetics algorithms, genetic programming, etc.) or local search algotihms (Simulated annealing, tabu search, etc.) depends on the properties of seach space structure. One concept to analyse the search space ...
Elementary landscape decomposition of the test suite minimization problem
SSBSE'11: Proceedings of the Third international conference on Search based software engineering

Landscape theory provides a formal framework in which combinatorial optimization problems can be theoretically characterized as a sum of a special kind of landscape called elementary landscape. The decomposition of the objective function of a problem ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
128
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Klemm KStadler P(2013)Rugged and Elementary LandscapesTheory and Principled Methods for the Design of Metaheuristics10.1007/978-3-642-33206-7_3(41-61)Online publication date: 12-Nov-2013
https://doi.org/10.1007/978-3-642-33206-7_3
Whitley DChicano F(2012)Quasi-elementary Landscapes and Superpositions of Elementary LandscapesRevised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 721910.5555/2961491.2961512(277-291)Online publication date: 16-Jan-2012
https://dl.acm.org/doi/10.5555/2961491.2961512
Alba ELuque GNesmachnow S(2012)Parallel metaheuristics: recent advances and new trendsInternational Transactions in Operational Research10.1111/j.1475-3995.2012.00862.x20:1(1-48)Online publication date: 13-Aug-2012
https://doi.org/10.1111/j.1475-3995.2012.00862.x
Whitley DChicano F(2012)Quasi-elementary Landscapes and Superpositions of Elementary LandscapesLearning and Intelligent Optimization10.1007/978-3-642-34413-8_20(277-291)Online publication date: 2012
https://doi.org/10.1007/978-3-642-34413-8_20
Chicano FWhitley LAlba ELuna F(2011)Elementary landscape decomposition of the frequency assignment problemTheoretical Computer Science10.1016/j.tcs.2011.02.011412:43(6002-6019)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1016/j.tcs.2011.02.011

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Elementary landscape decomposition of the frequency assignment problem

Fitness landscapes and graphs: multimodularity, ruggedness and neutrality

Elementary landscape decomposition of the test suite minimization problem