Gray-Box Optimization using the Parameter-less Population Pyramid

Unlike black-box optimization problems, gray-box optimization problems have known, limited, non-linear relationships between variables. Though more restrictive, gray-box problems include many real-world applications in network security, computational biology, VLSI design, and statistical physics. Leveraging these restrictions, the Hamming-Ball Hill Climber (HBHC) can efficiently find high quality local optima. We show how 1) a simple memetic algorithm in conjunction with HBHC can find global optima for some gray-box problems and 2) a gray-box version of the Parameter-less Population Pyramid (P3), utilizing both the HBHC and the known information about variable relationships, outperforms all of the examined algorithms. While HBHC's inclusion into P3 adds a parameter, we show experimentally it can be fixed to 1 without adversely effecting search. We provide experimental evidence on NKq-Landscapes and Ising Spin Glasses that Gray-Box P3 is effective at finding the global optima even for problems with thousands of variables. This capability is complemented by its efficiency, with running time and memory usage decreased by up to a linear factor from Black-Box P3. On NKq this results in a 375x speedup for problems with at least 1,000 variables.