Name
Title | ||
|---|---|---|
Quadratization of gray coded representations, long path problems and needle functions |
Abstract | ||
|---|---|---|
ABSTRACTIn Evolutionary Computation, it is informative to ask what happens when well known benchmarks and bit representations are transformed into quadratic pseudo-Boolean optimization problems. Such transforms are commonly used in quantum computing in order to reduce nonlinearity to k-bounded interactions. First we show that Gray code representations are transformed into linear encodings with quadratic constraints. Next we look at Long Path problems which are constructed so that bit flip local search requires exponential time to converge to a global or local optimum. We show that Long Path problems are similar to reflected Gray codes in both construction and complexity. Finally, a basic form of the "Needle in a haystack" problem is transformed into a problem that can be optimally solved in linear time. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3449639.3459325 | Genetic and Evolutionary Computation Conference |
Keywords | DocType | Citations |
Quadratization, Pseudo-Boolean Functions, Representations, Gray Codes | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| L. Darrell Whitley | 1 | 6631 | 968.30 |
| J. Francisco Chicano | 2 | 132 | 9.27 |
| Hernán E. Aguirre | 3 | 3 | 1.04 |