Genetic algorithm encoding technique to be used in this scenario

Question

The problem is to find the optimum quantity that incurs minimum total cost in a number of warehouses using genetic algorithm.

Let's say there are n warehouses. Associated with each warehouse are a few factors:

• LCost_i: loading cost for warehouse i
• HCost_i: holding cost for warehouse i
• TCost_i: transportation cost for warehouse i
• OCost_i: ordering cost for warehouse i

Each warehouse has quantity Q_i associated with it that must satisfy these 4 criteria:

• loading constraint: Q_i * LCost_i >= A_i for warehouse i
• holding constraint: Q_i * HCost_i >= B_i for warehouse i
• Transportation constraint: Q_i * TCost_i >= C_i for warehouse i
• Ordering constraint: Q_i * OCost_i >= D_i for warehouse i

where A, B, C and D are constants for each of the warehouses.

Another important criterion is that each Q_i must satisfy:

• D_i >= Q_i

where D_i is the demand in warehouse i.

And the equation of total cost is:

Total cost = sum(Q_i * (LCost_i + HCost_i + TCost_i) + OCost_i / Q_i)

How do I encode a chromosome for this problem? What I am thinking is that combining one of the four constraints that gives a minimum allowable value for Q_i and the last constraint, I can get a range for Q_i. Then I can randomly generate values in that range for the initial population. But how do I perform crossover, and mutation in the above scenario? How do I encode the chromosomes?

Answer 1

Generally, in constrained problems you have basically three possible approaches (regarding evolutionary algorithms):

1. Incorporate constraint violation into fitness

You can design your fitness as a sum of the actual objective and penalties for violation of constraints. The extreme case is a "death penalty", i.e. any individual which violates any constraint in any way receives the worst possible fitness.

This approach is usually very easy to implement but, however, has a big drawback: it often penalizes solutions that have good building blocks but violate the constraints too much.

2. Correction operators, resistant encoding

If it is possible for your problem, you can implement "correction operators" - operators that take a solution that violate constraints and transform it into another one that does not violate the constraints, preserving as much structure from the original solution as possible. Similar thing is to use such an encoding that guarantees that the solution will always be feasible, i.e. you have such a decoding algorithm that always produces valid solution.

If it is possible, this is probably the best approach you can take. However, it is often quite hard to implement, or not possible without major changes in the solutions which can then significantly slow the search down, or even make it useless.

3. Multi-objective approach

Use some multi-objective (MO) algorithm, e.g. NSGA-II, and turn your measure(s) of constraint violation into objectives and optimize all the objectives at once. The MO algorithms usually provide a pareto-front of solutions - a set of solutions that are on the front of the objective-violation tradeoff space.

Answer 2

Using Differential Evolution you can keep the same representation and avoid the double conversion (integer -> binary, binary -> integer).

The mutation operation is:

V(g+1, i) = X(g, r1) + F ⋅ (X(g, r2) − X(g, r3))

where:

• i, r1, r2, r3 are references to vectors in the population and none is equal to the other
• F is a random constant in the [0, 1.5] range

V (the mutant vector) is recombined with elements of a target vector (X(g, i)) to build a trial vector u(g+1, i). The selection process chooses the better candidate from the trial vector and the target vector (see the references below for further details).

The interesting aspects of this approach are:

• you haven't to redesign the code. You need a different mutation / recombination operator and (perhaps) you have to cast some reals to integers, but it's simple and fast;
• for constraint management you can adopt the techniques described in zegkljan's answer;
• DE has been shown to be effective on a large range of optimization problems and it seems to be suitable for your problem.

---

References:

• Explain the Differential Evolution method and an old Dr.Dobb's article (by Kenneth Price and Rainer Storn) as introduction;
• Storn's page for more details and many code examples.