Фитнес-функция для Лабиринта Решения Генетического Алгоритма - PullRequest
Новая
       42

Фитнес-функция для Лабиринта Решения Генетического Алгоритма

0 голосов
/ 20 мая 2018

Я работаю над Лабиринтом, используя подход GA.Каждый геном имеет направления, закодированные как символы («N», «S», «E», «W»), и каждый геном в поколении оценивается на пригодность и скрещивание с использованием взвешенной рулетки.

До сих пор задание идет хорошо, но я заметил причуду с моей функцией фитнеса, которая (я думаю) дает мне более длинные / менее оптимальные решения.

Поскольку я стремлюсь решитьуниверсальный лабиринт без решения перед этим, я настроил свою фитнес-функцию следующим образом: (пожалуйста, игнорируйте жестко запрограммированные начальную и конечную позиции, они будут сделаны общими позже ...) 

private static double calculateMazeScore(Genome genome) {

    int start_row = 1;
    int start_col = 0;
    int end_row = 12;
    int end_col = 8;

    MazePosition pos = new MazePosition(start_row, start_col);

    int penalty = 0;
    for (char gene : genome.geneString().toCharArray()) {
        int n, e, s, w;
        n = pos.getNeighborValueNeg1IfEdge(Direction.N);
        e = pos.getNeighborValueNeg1IfEdge(Direction.E);
        s = pos.getNeighborValueNeg1IfEdge(Direction.S);
        w = pos.getNeighborValueNeg1IfEdge(Direction.W);

//    System.out.printf("pos:[%d,%d] val:%d next:%s n:%d  s:%d  e:%d  w:%d \n", 
//                        pos.getRowIdx(), pos.getColumnIdx(), pos.getValue(), gene, n, s, e, w);

        if (gene == 'N') {
            if (n == 0 || n == 2 || n == 3) {
                pos = pos.getNeighbor(Direction.N);
                penalty -= 1.5;
            } else {
                penalty++;
            }
        } else if (gene == 'E') {
            if (e == 0 || e == 2 || e == 3) {
                pos = pos.getNeighbor(Direction.E);
                penalty -= 1.5;
            } else {
                penalty++;
            }
        } else if (gene == 'S') {
            if (s == 0 || s == 2 || s == 3) {
                pos = pos.getNeighbor(Direction.S);
                penalty -= 1.5;
            } else {
                penalty++;
            }
        } else if (gene == 'W') {
            if (w == 0 || w == 2 || w == 3) {
                pos = pos.getNeighbor(Direction.W);
                penalty -= 1.5;
            }
        }
    }

    double x1 = pos.getRowIdx();
    double y1 = pos.getColumnIdx();

    double distFromStart = Math.sqrt(Math.pow(start_row - x1, 2) + Math.pow(start_col - y1, 2));
    double distFromGoal = Math.sqrt(Math.pow(end_row - x1, 2) + Math.pow(end_col - y1, 2));

    double mazeScore = distFromStart - distFromGoal - penalty;
    if (mazeScore <= 0)
        mazeScore = 0;

    return mazeScore;
}

Поскольку я оцениваюСтрока генома через лабиринт, я увеличиваю счетчик штрафов, когда геном "врезается" в стену, и уменьшаю счетчик, когда это не так.После того, как геном сделан, я делаю расчет расстояния, чтобы найти расстояние от начала и до конца.Окончательная пригодность - dist_from_start - dist_from_end - штрафы.

Это на самом деле работает довольно хорошо, геномы действительно подходят к концу, не врезаясь в слишком много стен ... но я думаю, что я стимулировал слишком много бродить по лабиринту.Я получаю много "WEWEWEWENSNSNSNSNS", искусственно увеличивая баллы ... Наиболее подходящие из последних 10 поколений или около того долго бродят по лабиринту, прежде чем пробираются к выходу, и иногда они не получают всеКстати, потому что они проводили слишком много времени, ходя взад и вперед.

То, что у меня есть сейчас, в порядке ... но не замечательно.Я хотел бы получить несколько советов по улучшению физической формы.Я также буду экспериментировать с различными процессами кроссовера и выбора позже.Заранее спасибо!

...