GOM-Based Compatible Substitutions Optimization for Variable-Length Representation Gray-Box Problems

Effective recombination operators utilizing interdependence of genes ensure that specific arrangements or combinations of genes are preserved, allowing offspring to inherit beneficial traits from both parents without disrupting important gene interactions. However, such operators are easiest to implement for fixed-length genetic representations such as vectors of genes. In this work, we show that for some problems with variable-length representations, it is possible to design an algorithm that employs the GOM (Gene-pool Optimal Mixing) operator without the need to learn dependencies between specific genes. Instead, our approach - Compatible Substitutions Optimization (CoSO) - leverages expert-driven models of compatible substitutions that take advantage of the characteristics of the representation. Our experiments indicate that the proposed method performs better than standard evolutionary algorithms on a problem of evolving tall 3D structures, while also providing significant potential for further enhancements.