Suppose I have an assignment problem where I need to assign riders to seats. I need to enforce the constraint that at most, one rider is assigned to any given seat and every rider is assigned one seat.
Linear programming offers a means to articulate these constraints; however, do to a non-linear objective function, a heuristic algorithm, such as Genetic Algorithms, is potentially suitable optimization model choice.
If 25 seats are available, I need a mechanism to sample these seats without replacement when genes are initialized. Further, I need mutations and crossovers to observe this constraint.
gene_space = [
{"low": 1, "high": 25, "step": 25},
]
My questions are:
- Does PyGAD support this set sampling without replacement functionality?
- If not, is there an algorithm available that can adapt randomly sampled integers and enforce this constraint?
In regards to 2, a partial solution might include using a cumulative distribution function given randomly sampled integers with replacement and in some way use the CDF to retrieve samples without replacement from the seats available. (Such an approach might be inefficient, which could potentially thwart some of the perks of using PyGAD.)
You can set
allow_duplicate_genes=False
to prevent duplicate genes. This way, the value given to one gene will not be used by another gene.