0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Proper GA implementation should find options close to optimal in dozens, not thousands of iterations in such simple case. Why don't you look at other implementations, for instance, described here - stackoverflow.com/questions/2179823/genetic-algorithms and compare outcomes? $\endgroup$ – Stepan Novikov Oct 29 '20 at 9:35
  • $\begingroup$ Well the example presented is really a minimal experiment possible, which can be optimized in just a few iterations. The problems of course occurs for hundreds of articles/slots. Sorry if I didn't make it clear. Although my friend already suggested me to remove a few individuals each iteration, and generate completely new ones, which sounds like a good advise to me and I will give it a chance. $\endgroup$ – kocica Oct 29 '20 at 10:28
  • $\begingroup$ I see. I would recommend even not including chromosomes from a previous iteration into a new one at all - in my experience its speedup it a bit. Also using of Gray code will speed up things - en.wikipedia.org/wiki/Gray_code#Genetic_algorithms $\endgroup$ – Stepan Novikov Oct 29 '20 at 10:56
  • $\begingroup$ In our genetic search stuff, we not only mix chromosomes for best of breed but we always prune duplicates (new and old) and then supplement the generation with random models to allow unexplored portions of the space to potentially influence future generations. $\endgroup$ – David Hoelzer May 22 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.