A genetic hill climbing method for function optimization using a neighborhood based on interactions among parameters

Most conventional genetic algorithms (GAs) for function optimization always search all parameters simultaneously. As the result, the search space size increases exponentially with the number of parameters. Therefore, the search efficiency of these GAs deteriorates in high-dimensional function optimization because they requires a huge population size and enormous computation time. Generally, in order to find the optima, if a parameter has no interaction with the others, it can be searched independently and, if it has interactions with others, it must be searched with the ones which have interactions with it. We believe that, in many cases, all parameters do not need to be searched simultaneously because many evaluation functions in real-world applications have partially epistasis. We propose a new genetic hill climbing method. The proposed method, first, estimates all interactions among parameters and, then, incrementally improves a search point, using a neighborhood that is a subspace spaned by a parameter and the parameters having interactions with it, named epistasis neighborhood. The sampling method in an epistasis neighborhood is UNDX+MGG, which is a real-coded GA showing good performance on epistatic multimodal functions. We confirm that the proposed method shows better performance than conventional GAs on high-dimensional partially-epistatic functions by applying them to some benchmark problems.