Differential Evolution on Bin Packing
Two numerical examples: standard random-key encoding, then a discrete configuration-difference adaptation.
Problem Instance
Bin capacity C = 10. Six items:
| Item | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Weight | 4 | 8 | 1 | 4 | 2 | 7 |
Fitness for this example:
The number of bins is the main objective. The small slack penalty breaks ties, like a smoother fitness surface.
Method 1: Random-Key DE
Target vector and decoding
The current target individual is:
| Item | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
Target key x_i | 0.62 | 0.15 | 0.87 | 0.31 | 0.44 | 0.73 |
Sort by ascending key:
First Fit decoding:
Target uses 3 bins. Slack vector is [0, 1, 3].
DE mutation
Use DE/rand/1/bin with mutation factor F = 0.60.
| Vector | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
x_r1 base | 0.20 | 0.80 | 0.35 | 0.65 | 0.10 | 0.55 |
x_r2 | 0.90 | 0.30 | 0.75 | 0.25 | 0.60 | 0.40 |
x_r3 | 0.40 | 0.70 | 0.10 | 0.50 | 0.20 | 0.95 |
x_r2 - x_r3 | 0.50 | -0.40 | 0.65 | -0.25 | 0.40 | -0.55 |
0.60 * diff | 0.30 | -0.24 | 0.39 | -0.15 | 0.24 | -0.33 |
Donor v | 0.50 | 0.56 | 0.74 | 0.50 | 0.34 | 0.22 |
Binomial crossover
Use crossover rate CR = 0.70. If random number <= CR, take donor key; otherwise keep target key. Force item D from donor as j_rand.
| Item | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Random number | 0.81 | 0.14 | 0.66 | 0.91* | 0.38 | 0.52 |
| Take from | target | donor | donor | donor* | donor | donor |
Trial u | 0.62 | 0.56 | 0.74 | 0.50 | 0.34 | 0.22 |
The star means D is forced by j_rand, even though 0.91 is greater than CR.
Decode the trial
Sort by ascending trial key:
First Fit decoding:
Trial uses 3 bins. Slack vector is [0, 2, 2].
Selection: trial vs target
| Candidate | Bin loads | Bins | Slack | Slack penalty | Fitness |
|---|---|---|---|---|---|
Target x_i | 10, 9, 7 | 3 | 0, 1, 3 | 4.67 | 3.0467 |
Trial u | 10, 8, 8 | 3 | 0, 2, 2 | 2.67 | 3.0267 |
Trial is accepted because it uses the same number of bins and has a better tie-breaker fitness.
Method 2: Configuration-Difference / Similarity DE
Represent a configuration by co-location features
A feature means "item X and item Y are in the same bin." This is useful for bin packing because good packings often preserve good item pairings.
Base configuration R1
Features: BE, AD, AC, DC
Configuration R2
Features: BC, AD, AE, DE
Configuration R3
Features: FE, FC, EC, AD
Define the discrete difference
Instead of arithmetic R2 - R3, use features present in R2 but not in R3:
Let F = 2/3. Apply two of the three difference features to the base R1. Suppose we choose:
Apply feature BC to the base
Base has B with E, and C with A,D. To enforce BC, move C into B's bin.
But B8 + E2 + C1 = 11, which violates capacity. Repair by ejecting E temporarily:
Apply feature AE and repair
Now enforce AE by placing E2 with A4. Bin 2 has load 8, so adding E gives load 10 and stays feasible.
This donor configuration is valid and uses 3 bins.
What this means conceptually
This discrete version mimics DE:
| Continuous DE | Configuration-difference DE |
|---|---|
x_r2 - x_r3 | Features/moves present in R2 but not R3 |
F * difference | Apply only a fraction of those features/moves |
x_r1 + ... | Start from base R1 and inject those selected features |
| Bounds/clipping | Repair capacity violations and unplaced items |
| Greedy replacement | Accept donor/trial only if it beats the target fitness |
Which Answer Should You Use In The Exam?
If the question asks what you actually did in HW#5: use the random-key explanation.
If the question asks how to adapt DE more natively to bin packing: use the configuration-difference answer, but explicitly say you must define difference over moves/features and repair infeasible bins.