Фитнес-функция для Лабиринта Решения Генетического Алгоритма
Я работаю над Лабиринтом, используя подход 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 поколений или около того бродят по лабиринту в течение долгого времени, прежде чем пробраться к выходу, и иногда они не получают все путь их, потому что они провели слишком много времени, возвращаясь и вперед.
То, что у меня сейчас, в порядке... но не отлично. Я хотел бы получить несколько советов по улучшению моей фитнес-функции. Я также буду экспериментировать с различными процессами кроссовера и выбора позже. Заранее спасибо!