I'm working on SLAP (storage location assignment problem) using genetic algorithm implemented manually in the C++ programming language. The problem is fairly simple, we do have N products, which we want to allocate to M warehouse location slots (N might and might not be equal to M).
Let's begin with the encoding of the chromosomes. The chromosome length is equal to number of products (i.e. each product is one gene). Each product has one integer value (allele value), representing the location its allocated to.
Let me show you on simple example.
Products Average picking rate Location slots Location number
Prod1 0.4 Location 1, slot 1 (1) // 3rd best
Prod2 0.3 Location 1, slot 2 (2) // 4th best
Prod3 0.2 Location 2, slot 1 (3) // The best
Prod4 0.1 Location 2, slot 2 (4) // 2nd best
We aim for optimal allocation of products (Prod1-4) to location slots (1-4). The better the allocation is, the faster we can process all the products in customer orders. Now let's say the Location 2 is closer to the warehouse entrance/exit, so its more attractive, and the lower the location slot number is, the faster we can pick product out of the location slot. So the optimal allocation should be:
Product Location number
Prod1 3
Prod2 4
Prod3 1
Prod4 2
And expressed as the chromosome:
+---+---+---+---+
| 3 | 4 | 1 | 2 |
+---+---+---+---+
This allocation will lead to the best warehouse performance. Now let me show you my crossover operator (based on TSP crossover https://www.permutationcity.co.uk/projects/mutants/tsp.html):
void crossoverOrdered(std::vector<int32_t>& lhsInd, std::vector<int32_t>& rhsInd)
{
int32_t a, b;
int32_t pos = 0;
int32_t placeholder = -1;
int32_t placeholderCount = 0;
std::vector<int32_t> o1, o1_missing, o1_replacements;
std::vector<int32_t> o2, o2_missing, o2_replacements;
while(true)
{
do
{
a = randomFromInterval(pos, constants::numberDimensions);
b = randomFromInterval(pos, constants::numberDimensions);
}
while(a == b);
if(a > b) std::swap(a, b);
// Insert from first parent
for(int32_t i = pos; i < a; ++i)
{
o1.push_back(lhsInd.at(i));
o2.push_back(rhsInd.at(i));
}
// Insert placeholders
for(int32_t i = a; i < b; ++i)
{
++placeholderCount;
o1.push_back(placeholder);
o2.push_back(placeholder);
}
if(b >= constants::numberDimensions - 1)
{
for(int32_t i = b; i < constants::numberDimensions; ++i)
{
o1.push_back(lhsInd.at(i));
o2.push_back(rhsInd.at(i));
}
break;
}
else
{
pos = b;
}
}
// Find missing elements
for(int32_t i = 0; i < constants::problemMax; ++i)
{
if(std::find(o1.begin(), o1.end(), i) == o1.end()) o1_missing.push_back(i);
if(std::find(o2.begin(), o2.end(), i) == o2.end()) o2_missing.push_back(i);
}
// Filter missing elements and leave only those which are in the second parent (keep the order)
for(int32_t i = 0; i < static_cast<int32_t>(rhsInd.size()); i++)
{
if(std::find(o1_missing.begin(), o1_missing.end(), rhsInd.at(i)) != o1_missing.end()) o1_replacements.push_back(rhsInd.at(i));
}
// Filter missing elements and leave only those which are in the second parent (keep the order)
for(int32_t i = 0; i < static_cast<int32_t>(lhsInd.size()); i++)
{
if(std::find(o2_missing.begin(), o2_missing.end(), lhsInd.at(i)) != o2_missing.end()) o2_replacements.push_back(lhsInd.at(i));
}
// Replace placeholders in offspring 1
for(int32_t i = 0; i < placeholderCount; ++i)
{
auto it = std::find(o1.begin(), o1.end(), placeholder);
*it = o1_replacements.at(i);
}
// Replace placeholders in offspring 2
for(int32_t i = 0; i < placeholderCount; ++i)
{
auto it = std::find(o2.begin(), o2.end(), placeholder);
*it = o2_replacements.at(i);
}
// Assign new offsprings
lhsInd.assign(o1.begin(), o1.end());
rhsInd.assign(o2.begin(), o2.end());
}
My mutation operator(s):
void mutateOrdered(std::vector<int32_t>& ind)
{
int32_t a, b;
do
{
a = randomFromInterval(0, constants::numberDimensions);
b = randomFromInterval(0, constants::numberDimensions);
}
while(a == b);
std::rotate(ind.begin() + a, ind.begin() + b, ind.begin() + b + 1);
}
void mutateInverse(std::vector<int32_t>& ind)
{
int32_t a, b;
do
{
a = randomFromInterval(0, constants::numberDimensions);
b = randomFromInterval(0, constants::numberDimensions);
}
while(a == b);
if(a > b) std::swap(a, b);
std::reverse(ind.begin() + a, ind.begin() + b);
}
I tried to use roulette, truncate, tournament and rank selection alorithms, but each with similar results.
This is my configuration:
populationSize = 20
selectionSize = 5
eliteSize = 1
probabilityCrossover = 0.6
probabilityMutateIndividual = 0.4
probabilityMutateGene = 0.2
My fitness function is fairly simple, since it's real number returned by simulation program which simulates picking of orders on the current allocation we gave it. Unfortunately I cannot provide this program as its confidential. It's just a real number representing how good the current allocation is, the better the allocation is, the lower the number is (i.e. its minimization problem).
The problem
This genetic algorithm can find better solutions than just random allocation, the problem is, it gets "stuck" after lets say few thousand generations and it fails to improve furthermore, even though there are better solutions, and it will go even 20k generations with exact same ellite chromosom (don't improve at all). I tried to increase crossover/mutation probability and population size but none of it worked. Thanks for any help.
