Mostrar el registro sencillo del ítem

dc.contributor.authorSutton, Andrew M.
dc.contributor.authorChicano, Francisco 
dc.contributor.authorWhitley, L. Darrell
dc.date.accessioned2014-10-03T07:38:24Z
dc.date.available2014-10-03T07:38:24Z
dc.date.issued2014-10-03
dc.identifier.otherdoi:10.1162/EVCO_a_00098
dc.identifier.urihttp://hdl.handle.net/10630/8167
dc.descriptionEvolutionary Computation, 21(4): 561-590, 2013es_ES
dc.description.abstractThe frequency distribution of a fitness function over regions of its domain is an important quantity for understanding the behavior of algorithms that employ randomized sampling to search the function. In general, exactly characterizing this distribution is at least as hard as the search problem, since the solutions typically live in the tails of the distribution. However, in some cases it is possible to efficiently retrieve a collection of quantities (called moments) that describe the distribution. In this paper, we consider functions of bounded epistasis that are defined over length-n strings from a finite alphabet of cardinality q. Many problems in combinatorial optimization can be specified as search problems over functions of this type. Employing Fourier analysis of functions over finite groups, we derive an efficient method for computing the exact moments of the frequency distribution of fitness functions over Hamming regions of the q-ary hypercube. We then use this approach to derive equations that describe the expected fitness of the offspring of any point undergoing uniform mutation. The results we present provide insight into the statistical structure of the fitness function for a number of combinatorial problems. For the graph coloring problem, we apply our results to efficiently compute the average number of constraint violations that lie within a certain number of steps of any coloring. We derive an expression for the mutation rate that maximizes the expected fitness of an offspring at each fitness level. We also apply the results to the slightly more complex frequency assignment problem, a relevant application in the domain of the telecommunications industry. As with the graph coloring problem, we provide formulas for the average value of the fitness function in Hamming regions around a solution and the expectation-optimal mutation rate.es_ES
dc.description.sponsorshipSpanish 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 Re- search, Air Force Materiel Command, USAF, under grant number FA9550-08-1-0422.es_ES
dc.language.isoenges_ES
dc.rightsinfo:eu-repo/semantics/openAccesses_ES
dc.subjectOptimización combinatoriaes_ES
dc.subjectComputación evolutivaes_ES
dc.subject.otherLandscape theoryes_ES
dc.subject.otherFourier analysises_ES
dc.subject.otherCombinatorial optimizationes_ES
dc.subject.otherEvolutionary algorithmses_ES
dc.subject.otherLocal searches_ES
dc.titleFitness function distributions over generalized search neighborhoods in the q-ary hypercubees_ES
dc.typeinfo:eu-repo/semantics/preprintes_ES
dc.centroE.T.S.I. Informáticaes_ES


Ficheros en el ítem

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem