Epistasis measures how strongly variables depend on one another in an optimization problem. Changing one variable can alter the values, feasibility, or constraints of others. section 18.1.10
The degree of interaction becomes clearer through common optimization models:
- The 0-1 knapsack problem has mostly independent genes, although enforcing the weight constraint creates a loose indirect dependency. section 18.1.10
- The traveling salesperson problem has stronger dependency because assigning a vertex to one gene prevents other genes from using the same value. section 18.1.10
- A house-design problem can couple area, room count, and flooring materials: changing the size changes the required amount of wood. section 18.1.10
Choosing an optimization method
High epistasis means that many variables are tightly coupled, so changing one forces changes in others. Simulated annealing may then outperform a genetic algorithm; low-epistasis problems such as vertex cover are favorable for genetic algorithms. Testing both methods on smaller instances helps resolve the choice using actual data. section 18.5
