We consider the problem of finding the edges of a hidden weighted graph and their weights by using a certain type of queries as few times as possible, with focusing on two types of queries with additive property. For a set of vertices, the additive query asks the sum of weights of the edges with both ends in the set. For a pair of disjoint sets of vertices, the cross-additive query asks the sum of weights of the edges crossing between the two sets. These queries were motivated by DNA sequencing, population genetics, and artificial intelligence, and have been paid considerable attention to in computational learning. In this paper, we achieve an ultimate goal of recent years for graph finding with the two types of queries, by constructing the first polynomial time algorithms with optimal query complexity for the general class of graphs with n vertices and at most m edges in which the weights of edges are arbitrary real numbers. The algorithms are randomized and their query complexities are O(\fracm \log n\log m). These bounds improve the best known by a factor of \log m, and settle the open problem posed in some papers including [Choi and Kim, Optimal query complexity bounds for finding graphs, STOC 2008]. To build key components for graph finding, we consider the coin weighing problem with a spring scale. The problem itself has been paid much attention to in a long history of combinatorial search. We construct the first polynomial time algorithm with optimal query complexity for the general case in which the weight differences between counterfeit and authentic coins are arbitrary real numbers. We also construct the first polynomial time optimal query algorithm for finding the Fourier coefficients of a certain class of pseudo-Boolean functions.

For a real-valued functionfdefined on {0,1}n, the linkage graph offis a hypergraph that represents the interactions among the input variables with respect tof. In this paper, lower and upper bounds for the number of function evaluations required to discover the linkage graph are rigorously analyzed in the black box scenario. First, a lower bound for discovering linkage graph is presented. To the best of our knowledge, this is the first result on the lower bound for linkage discovery. The investigation on the lower bound is based on Yao's minimax principle. For the upper bounds, a simple randomized algorithm for linkage discovery is analyzed. Based on the Kruskal-Katona theorem, we present an upper bound for discovering the linkage graph. As a corollary, we rigorously prove thatO(n2logn) function evaluations are enough for bounded functions when the number of hyperedges isO(n), which was suggested but not proven in previous works. To see the typical behavior of the algorithm for linkage discovery, three random models of fitness functions are considered. Using probabilistic methods, we prove that the number of function evaluations on the random models is generally smaller than the bound for the arbitrary case. Finally, from the relation between the linkage graph and the Walsh coefficients, it is shown that, for bounded functions, the proposed bounds are eventually the bounds for finding the Walsh coefficients.

We consider the problem of finding an unknown graph by using two types of queries with an additive property. Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask sum of weights for the weighted graphs. These types of queries were partially motivated in DNA shotgun sequencing and linkage discovery problem of artificial intelligence.

Normalization transforms one parent genotype to be consistent with the other before crossover. In this paper, we explain how normalization alleviates the difficulties caused by nonsynonymously redundant encodings in genetic algorithms. We define the encodings with maximally nonsynonymous property and prove that the encodings induce uncorrelated search spaces. Extensive experiments for a number of problems show that normalization transforms the uncorrelated search spaces to correlated ones and leads to significant improvement in performance.

Keystroke authentication is a biometric method utilizing the typing characteristics of users. In this paper, we propose an evolutionary method for stable keystroke authentication. In the method, typing characteristics of users are represented by n-dimensional vectors and an ellipsoidal hypothesis space, which distinguishes a collection of the timing vectors of a user from those of the others, is evolved by a genetic algorithm. A filtering scheme and an adaptation mechanism are also presented to improve the stability and effectiveness of the proposed method. Empirical results show that the error rates of our method for authentication are reasonably small.

The properties of symmetric fitness functions are investigated. We show that the search spaces obtained from symmetric functions have the zero-correlation structures between fitness and distance. It is also proven that symmetric functions induce a class of the hardest problems in terms of the epistasis variance and its variants. These analyses suggest that the existing quantitative measures cannot discriminate among symmetric functions, which reveals critical limitations of the measures. To take a closer look at the symmetric functions, additional analyses are performed from other viewpoints including additive separability and boundedness. It is shown that additive separability in a symmetric function is closely related to the symmetry of its subfunctions. This elucidates why most of the well-known symmetric fitness functions are additively inseparable. The properties of two-bounded symmetric functions are investigated and they are utilized in designing an efficient algorithm to check additive separability for the two-bounded functions. Throughout this paper, we heavily use the generalized Walsh transform over multary alphabets. Our results have an independent interest as a nontrivial application of the generalized Walsh analysis.

The properties of symmetric fitness functions are investigated. We show that a well-known encoding scheme inducing symmetric functions has the non-synonymous property and the search spaces obtained from symmetric functions have the zero-correlation structures. The Walsh analysis reveals the properties of symmetric functions related to additive separability, problem difficulty measures and so on. Our results support the claim of other researchers that the search spaces with symmetry induce relatively difficult problems. The results also present some limitations of existing problem difficulty measures for symmetric fitness functions.

Function approximation or regression is the problem of finding a function that best explains the relationship between independent variables and a dependent variable from the observed data. Genetic programming has been considered a promising approach for the problem since it is possible to optimize both the functional form and the coefficients. Genetic programming has been considered a promising approach for function approximation since it is possible to optimize both the functional form and the coefficients. However, it is not easy to find an optimal set of coefficients by using only non-adjustable constant nodes in genetic programming. To overcome the problem, there have been some studies on genetic programming using adjustable parameters in linear or nonlinear models. Although the nonlinear parametric model has a merit over the linear parametric model, there have been few studies on it. In this paper, we propose a nonlinear parametric genetic programming which uses a nonlinear gradient method to estimate parameters. The most notable feature in the proposed genetic programming is that we design a parameter attachment algorithm using as few redundant parameters as possible. It showed a significant performance improvement over the traditional genetic programming approaches on real-world application problems.

This paper proposes a hybrid genetic algorithm for multiple sequence alignment. The algorithm evolves guide sequences and aligns input sequences based on the guide sequences. It also embeds a local search heuristic to search the problem space effectively. In the experiments for various data sets, the proposed algorithm showed the performance comparable to existing algorithms.

An analysis for the phase transition in a random NK landscape model is given. For the fixed ratio model, NK(n,k,z), Gao and Culberson [17] showed that a random instance generated by NK(n,2,z) with z > z0 = 27-7/√54 is asymptotically insoluble. Based on empirical results, they conjectured that the phase transition occurs around the value z = z0. We prove that an instance generated by NK(n,2,z) with z < z0 is soluble with positive probability by providing a variant of the unit clause algorithm. Using branching process arguments, we also reprove that an instance generated by NK(n,2,z) with z > z0 is asymptotically insoluble. The results show the phase transition around z = z0 for NK(n,2,z). In the course of the analysis, we introduce a generalized random 2-SAT formula, which is of self interest, and show its phase transition phenomenon.

Jung-Hwan Kim School of Computer Science and Engineering Seoul National University Shilim-dong, Kwanak-gu, Seoul, 151-742 Korea [email protected] Sung-Soon Choi School of Computer Science and Engineering Seoul National University Shilim-dong, Kwanak-gu, Seoul, 151-742 Korea [email protected] Byung-Ro Moon School of Computer Science and Engineering Seoul National University Shilim-dong, Kwanak-gu, Seoul, 151-742 Korea [email protected]

In this paper, we propose a neuro-genetic stock prediction system based on financial correlation between companies. A number of input variables are produced from the relatively highly correlated companies. The genetic algorithm selects a set of informative input features among them for a recurrent neural network. It showed notable improvement over not only the buy-and-hold strategy but also the recurrent neural network using only the input variables from the target company.

A hybrid genetic algorithm (GA) is proposed for the optimal sorting network problem. Based on a graph-theoretical viewpoint, we devised a solution repair heuristic which incorporates a strong local optimization. We also propose a new encoding scheme which combines the characteristics of Lamarckian and Baldwinian GAs. Using a single-CPU PC, we obtained results comparable to previous results obtained with supercomputers.

We consider the problem space of a sorting network as a graph. Based on this viewpoint, we devised local optimization heuristics for sorting networks and combined them with a genetic algorithm framework. Using a single-CPU PC, we obtained results comparable with previous results obtained using supercomputers.