Suchergebnisse

Whitley, D., & Chicano F. (2012). Quasi-elementary Landscapes and Superpositions of Elementary Landscapes. (Hamadi, Y., & Schoenauer M., Ed.).Learning and Intelligent Optimization - 6th International Conference, LION 6, Paris, France, January 16-20, 2012, Revised Selected Papers. 277–291. ; There exist local search landscapes where the evaluation function is an eigenfunction of the graph Laplacian that corresponds to the neighborhood structure of the search space. Problems that display this structure are called "Elementary Landscapes" and they have a number of special mathematical properties. The term "Quasi-elementary landscapes" is introduced to describe landscapes that are "almost" elementary; in quasi-elementary landscapes there exists some efficiently computed "correction" that captures those parts of the neighborhood structure that deviate from the normal structure found in elementary landscapes. The "shift" operator, as well as the "3-opt" operator for the Traveling Salesman Problem landscapes induce quasi-elementary landscapes. A local search neighborhood for the Maximal Clique problem is also quasi-elementary. Finally, we show that landscapes which are a superposition of elementary landscapes can be quasi-elementary in structure. ; Universidad de Málaga. Campus de Excelencia Internacional Andalucía Tech. Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number FA9550-11-1-0088. Spanish Ministry of Science and Innovation and FEDER under contract TIN2008-06491-C04-01 (the M∗ project). Andalusian Government under contract P07-TIC-03044 (DIRICOM project).

Evolutionary Computation Journal 19(4):597-637 ; A small number of combinatorial optimization problems have search spaces that correspond to elementary landscapes, where the objective function f is an eigenfunction of the Laplacian that describes the neighborhood structure of the search space. Many problems are not elementary; however, the objective function of a combinatorial optimization problem can always be expressed as a superposition of multiple elementary landscapes if the underlying neighborhood used is symmetric. This paper presents theoretical results that provide the foundation for algebraic methods that can be used to decompose the objective function of an arbitrary combinatorial optimization problem into a sum of subfunctions, where each subfunction is an elementary landscape. Many steps of this process can be automated, and indeed a software tool could be developed that assists the researcher in finding a landscape decomposition. This methodology is then used to show that the subset sum problem is a superposition of two elementary landscapes, and to show that the quadratic assignment problem is a superposition of three elementary landscapes. ; Spanish Ministry of Science and Innovation and FEDER under contract TIN2008-06491-C04-01 (the M∗ project). Andalusian Government under contract P07-TIC- 03044 (DIRICOM project). Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number FA9550-08-1-0422.

Chicano, F., Whitley D., & Alba E. (2012). Exact computation of the expectation curves for uniform crossover. (Soule, T., & Moore J. H., Ed.).Genetic and Evolutionary Computation Conference, GECCO'12, Philadelphia, PA, USA, July 7-11, 2012. 1301–1308. ; Uniform crossover is a popular operator used in genetic algorithms to combine two tentative solutions of a problem represented as binary strings. We use the Walsh decomposition of pseudo-Boolean functions and properties of Krawtchouk matrices to exactly compute the expected value for the fitness of a child generated by uniform crossover from two parent solutions. We prove that this expectation is a polynomial in , the probability of selecting the best-parent bit. We provide efficient algorithms to compute this polynomial for ONEMAX and MAX-kSAT problems, but the results also hold for domains such as NK-Landscapes. ; Universidad de Málaga. Campus de Excelencia Internacional Andalucía Tech. Spanish Ministry of Science and Innovation and FEDER under contract TIN2011-28194 (the roadME project). Andalusian Government under contract P07-TIC-03044 (DIRICOM project).

Theoretical Computer Science 412(43),2011, pp.6002-6019 ; 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 paper we study a general version of the FAP that can include adjacent frequency constraints. Using concepts from landscapes' theory, we prove that this general FAP can be expressed as a sum of two elementary landscapes. Further analysis also shows that some subclasses of the problem correspond to a single elementary landscape. This allows us to compute the kind of neighborhood information that is normally associated with elementary landscapes. We also provide a closed form formula for computing the autocorrelation coefficient for the general FAP, which can be useful as an a priori indicator of the performance of a local search method. ; This work has been partially funded by the Spanish Ministry of Science and Spanish Ministry of Science and Innovation and FEDER under contract TIN2008-06491-C04-01 (the M∗ project). Andalusian Government under contract P07-TIC-03044 (DIRICOM project). Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number FA9550-08-1-0422.