Genetic Programming - Pathfinding not enougth couples

Question

I do genetic programming. I have 5 parcours, the first on the left is the easiest parcour.

The first parcour can be solved by place one belt in the middle pointing downwards to solve the problem. If placed in the middle downwards, the puzzle is solved because the iron-ore flows downwards to the robotic arm. The robotic arm grabs the iron-ore and place it into the wooden-box.

To solve the second parcour 3 belts have to be set.

This is the Brain of the Thinker to mutate:

const int MAX_IDEAS=40000;
enum IdeaType {
    MOVE_LEFT, MOVE_RIGHT, MOVE_UP, MOVE_DOWN, INC_MEM1_PTR, DEC_MEM1_PTR,
    SET_MEM1_ZERO, INC_MEM1_BY_1, DEC_MEM1_BY_1, INC_MEM1_BY_10, 
    DEC_MEM1_BY_10, FLIP_MEM1_MEM2, GT_JMP, LT_JMP, EQ_JMP, NEQ_JMP, 
    LOOKUP_MEM1, STORE_MEM1, PLACE_BELT, GET_OBJECTIVE, ROTATE, FINISH,
    FOLLOW_DIRECTION,

    // the end
    _COUNT
};
class Thinker {

private:
    unsigned char memory[255];
    unsigned char mem_pointer1, mem_pointer2;
    unsigned char posX, posY;
public:
    IdeaType ideas[MAX_IDEAS];
    unsigned int execute(Playground *p, unsigned int maxExecs,
            Objective *obj);
    void randomize(int globalSeed);
    Thinker* mutate(Thinker* spouse, int globalSeed);
    void showIdeas();
};

This is the implementation of the steps to do:

unsigned int Thinker::execute(Playground *p, unsigned int maxExecs,
        Objective *obj) {
    mem_pointer1 = 0;
    mem_pointer2 = 0;
    posX = 0;
    posY = 0;
    unsigned int steps = 0;
    for (int ideaNr = 0; ideaNr < MAX_IDEAS; ++ideaNr) {
        steps++;

        if (ideaNr < 0)
            ideaNr = 0;
        if (ideaNr > MAX_IDEAS)
            ideaNr = MAX_IDEAS - 1;
        IdeaType i = ideas[ideaNr];
        switch (i) {
        case LOOKUP_MEM1:
            memory[mem_pointer1] = p->getCell(posX, posY)->getBuilding();
            break;
        case STORE_MEM1:
            memory[mem_pointer1] = mem_pointer1;
            break;
        case GT_JMP:
            if (mem_pointer1 > mem_pointer2) {
                ideaNr += (mem_pointer1 - mem_pointer2);
            }
            break;
        case LT_JMP:
            if (mem_pointer1 < mem_pointer2) {
                ideaNr += (mem_pointer2 - mem_pointer1);
            }
            break;
        case EQ_JMP:
            if (mem_pointer1 == mem_pointer2) {
                ideaNr += mem_pointer1;
            }
            break;
        case NEQ_JMP:
            if (mem_pointer1 != mem_pointer2) {
                ideaNr += mem_pointer1;
            }
            break;
        case INC_MEM1_PTR:
            mem_pointer1++;
            break;
        case DEC_MEM1_PTR:
            mem_pointer1--;
            break;
        case SET_MEM1_ZERO:
            memory[mem_pointer1] = 0;
            break;
        case INC_MEM1_BY_1:
            memory[mem_pointer1] += 1;
            break;
        case DEC_MEM1_BY_1:
            memory[mem_pointer1] -= 1;
            break;
        case INC_MEM1_BY_10:
            memory[mem_pointer1] += 10;
            break;
        case DEC_MEM1_BY_10:
            memory[mem_pointer1] -= 10;
            break;
        case FLIP_MEM1_MEM2:
            unsigned char l;
            l = mem_pointer1;
            mem_pointer1 = mem_pointer2;
            mem_pointer2 = l;
            break;
        case PLACE_BELT:
            if (p->getCell(posX, posY) == 0) {
                return steps;
            }
            if (p->getCell(posX, posY)->isBuildingLocked()) {
                return steps;
            }
            p->setCell(posX, posY, YELLOW_BELT, NOTHING, DOWN);
            break;
        case FINISH:
            return steps;
        case MOVE_UP:
            if (posY == 0) {
                return steps;
            }
            posY--;
            break;
        case MOVE_LEFT:
            if (posX == 0) {
                return steps;
            }
            posX--;
            break;
        case MOVE_RIGHT:
            if (p->getCell(posX + 1, 0) == 0) {
                return steps;
            }
            posX++;
            break;
        case FOLLOW_DIRECTION:
            if (p->getCell(posX, posY) == 0) {
                return steps;
            }
            Cell* c;
            c = p->getCell(posX, posY);
            if(c->getBuilding()==YELLOW_BELT) {
                switch (c->getDirection()) {
                    case DOWN:
                        if(p->below(p->getCell(posX, posY))==0) {
                            return steps;
                        }
                        posY++;
                        break;
                    case UP:
                        if(posY==0) {
                            return steps;
                        }
                        posY--;
                        break;
                    case LEFT:
                        if(posX==0) {
                            return steps;
                        }
                        posX--;
                        break;
                    case RIGHT:
                        if(p->right(p->getCell(posX, posY))==0) {
                            return steps;
                        }
                        posX++;
                        break;
                    default:
                        break;
                }
            }
            break;
        case MOVE_DOWN:
            if (p->getCell(0, posY + 1) == 0) {
                return steps;
            }
            posY++;
            break;
        case GET_OBJECTIVE:
            if (obj->row == posY && obj->cell == posX) {
                memory[mem_pointer1] = obj->prospection;
            } else {
                memory[mem_pointer1] = 255;
            }
            break;
        case ROTATE:
            if (p->getCell(posX, posY) == 0) {
                return steps;
            }
            if (p->getCell(posX, posY)->isBuildingLocked()) {
                return steps;
            }
            p->getCell(posX, posY)->rotate();
            break;
        default:
            cout << endl << "PROBLEM!!!!; VALUE OUT OF RANGE: " << (int) i
                    << endl;
            return steps;
            break;
        }
        if (steps > maxExecs) {
            cout << "Max ideas reached!" << endl;
            break;
        }
    }
    return steps;
}

Before mutation I initialize by this random method:

void Thinker::randomize(int globalSeed) {
    srand(globalSeed);
    for (int ideaNr = 0; ideaNr < MAX_IDEAS; ++ideaNr) {
        int r = rand() % _COUNT;
        ideas[ideaNr] = static_cast<IdeaType>(r);
    }
}

To mutate two thinker I use this method:

Thinker* Thinker::mutate(Thinker *spouse, int globalSeed) {
    Thinker *tt = new Thinker();
    srand(globalSeed);
    int from = rand() % MAX_IDEAS - 1;
    int count = rand() % (MAX_IDEAS - from);
    if (count == 0) {
        count = 1;
    }
    int halfMaxIdeas = count / 2 + from;
    for (int i = from; i < from + count; i++) {
        if (i < halfMaxIdeas) {
            tt->ideas[i] = ideas[i];
        } else {
            tt->ideas[i] = spouse->ideas[i];
        }
    }
    return tt;
}

The rest is like this: There must be always 20,000 thinker. They do all try to solve the puzzle. Those winners are mutated.

Current results:

1. From the first 20,000 candidates there where only 138 who could solve the maze successfully.
2. I do mutate all the 138 candidates up to 20,000 mutations of those candidates. Then I let them solve the second puzzle.
3. From the second puzzle there where only 2 winners.

Only 2 winners is a bad result because they can be mutated but they are much too inbreeded for further healthy candidates.

What do I need a review for?

• Documentation style
• Range check
• Missing important IdeaTypes
• Check if the mutation algorithm do a valid mutation.
• Maybe optimizations

Answer 1

I don't know anything about Factorio which your question also seems to be about, so I can't say anything about "missing important IdeaTypes", for instance.

1. Since MAX_IDEAS is a compile-time constant, you might as well mark it as such by constexpr instead.

2. Perhaps only nitpicking, but it seems clear that any type is... a type. So I think Idea is a better type name than IdeaType. I mean, it's std::vector<T> and not std::vector_type<T> for comparison.

3. For Thinker: avoid C-style arrays. If you really do know 255 characters are sufficient, consider using e.g., std::array instead. You'll be able to enforce range checking much more easily, to name just one benefit. If you chose 255 just because it feels large enough, then use a dynamic data structure like a string or a vector.

4. I don't see the reason ideas has to be a public array. Just rather make it a constant static array which is "suitably global", as per your needs.

5. When you want to minimize the risk of leaking memory or doing something unintended, don't use pointers. You don't seem to need any dynamic memory management (for e.g., polymorphism), so just don't. It's much easier to reason about non-pointer types and references.

6. In particular, mutate does not need to return a dynamically allocated object. Just return by value, modern C++ does guarantee copy elision and you don't take any hit by doing so. Also, the caller don't have to worry about managing the object lifetime (which you possibly might have neglected to do in your full code).

7. The variable name i is quite surprising. Your instinct tells you it's probably a loop variable, but it's actually of type IdeaType. So I'd rename this to e.g., idea.

8. The switch-case is quite a beast to parse and to understand. Here's a few pointers (no pun intended) for how you can make it more readable: note that FLIP_MEM1_MEM2 is std::(iter_)swap; rely on standard implementations. All of SET_MEM1_ZERO, ..., DEC_MEM1_BY_10 increment a location by a constant. So we could use an (unordered) map to store these values, where the key is IdeaTypes. So if you are in one of these cases, reach into the map and increment by the corresponding value.

9. Further, for the latter parts (dealing with movement it seems), you could consider delegating this work to helper functions to aid readability.

10. Another example of a pointer you likely don't need is Cell* c. You don't show what this type is, but make const Cell& c = p.getCell(posX, posY); if you can, and just make is Cell& c if you can't. I'm also assuming here you pass by (constant) reference, and not by pointer (don't do that, unless you really know you want to).

11. I think the default branch of your switch case shouldn't just print "PROBLEM!!!!", but rather fail hard. So you probably want to use an assert as this case (I assume) means the internal program logic is broken, i.e., we should never get here no matter what.

12. Try to think about what constructors Thinker should have. Should it be the case that you pass it a Playground, maxExecs, and an Objective and it initializes suitably? Or should you be able to give the constructor a seed so that the candidate solution is built randomly? Think about the semantics here, the constructor helps you make your code more efficient and more readable; it also self-documents what a Thinker is.

13. For randomize, read about how to use randomness more appropriately with the use of <random>. These facilities exist because of shortcomings of just using rand() and such. So you could do (untested!) something like:

void Thinker::randomize(int globalSeed) {
    std::random_device rnd_device;
    std::mt19937 engine {rnd_device()};
    std::uniform_int_distribution<int> dist{0, MAX_IDEAS};
    // It's so nice that ideas is an std::array so that we can use begin() and end()
    std::generate(ideas.begin(), ideas.end(), [&]() { return static_cast<IdeaType>(dist(engine)); });
    // Otherwise, we'd have to something more error prone like std::generate(ideas, ideas + 255, ...)

14. You can apply the same ideas for mutate. In short, don't return a pointer & use the modern random facilities. This also gives you the added benefit of more control in an easy way: what if you don't want a uniform distribution? You want to weight it in some exotic way? Much easier with <random> than doing it by hand!

15. In general, it would help if you explained how the relevant concepts relate to the expected components of a genetic algorithm. For example, it seems that Thinker is a chromosome (i.e., a candidate solution), but it would be nice to see your fitness function as well, and so on. This helps in communicating ideas and in the (self-)documentation of your code.

16. If you don't have a fitness function, your search essentially only progresses by mutation likely making it very inefficient as it explores the search space in random manner without any guidance.

Answer 2

Interpreting the problem as a path on a graph:

The problem can be interpreted as trying to find a path (from S to T) in a graph.

E.g.

Genetic Algorithm improvements

There are several techniques to mitigate your problems:

• Divide the problem into two smaller ones, You could first find the path on the graph and then given a valid path, you can find the action that builds that path.
• Blending Roulette Wheel Selection & Rank Selection, basically it's a better way to select the population that tries to balance exploitation and exploration.
• Add a heuristic to the fitness function, you could use the L1 distance from the current end of the path and the target square. This way you simulate the A* algorithm.
• Elitism, basically you keep untouched the best 5~10% of the population. This is meant to avoid regression.

Optimal Solution (No genetic algorithm)

This might be kind of offtopic, but if you don't need to use a Genetic Algorithm you can use Dynamic Programming to find the optimal solution.

If we set a constant weight on all the edges we can use Dijkstra's algorithm to find the solution that requires the least amount of belts. Here a quite clear C++ implementation.

Once you have the optimal solution, it shouldn't be hard to build the sequence of actions that build that path.

If the problem became really big, you could use Ant System, which could be viewed as a hybrid between a pathfinding algorithm and a genetic algorithm.

Answer 3

Your problem is difficult in trying for a genetic algorithm to create a long program for which the only outputs are a single binary ('problem is solved', 'problem is not solved') and that you are trying to find a single algorithm that solves all five problems, as seen by you promoting those that solve the first problem to the gene pool of the second.

You might want to add a scoring function, e.g., how close the ore got to box with a huge bonus for getting to the box. You can then kill a reasonable number (say half) for each new level.

You may find that this is not really a solvable problem, especially since your mutations are random op code swaps. You could experiment with swapping a random subsequence of the program instead.

Otherwise, you are putting two frogs in a blender and hoping that 'Puree' creates one bigger frog.