Генетический алгоритм решения лабиринта с использованием Python (с визуализацией)

Генетический алгоритм (ГА) – это алгоритм оптимизации, основанный на процессах естественного отбора и генетики. Он используется для поиска наилучшего решения проблемы путем моделирования процесса биологической эволюции.

Начиная с набора возможных решений, ГА использует операторы выбора, кроссовера и мутации для создания нового кандидата. решения. Оператор отбора выбирает из популяции наиболее подходящих особей, которые станут родителями следующего поколения. Комбинируя генетический материал двух родителей, оператор кроссинговера генерирует новые решения. Чтобы исследовать новые области пространства поиска, оператор мутации случайным образом изменяет некоторые гены в решении.

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

Многие задачи оптимизации, такие как инженерное проектирование, планирование и финансовое моделирование, используют ГА. Это особенно полезно, когда пространство поиска большое и сложное, а традиционные методы оптимизации неэффективны.

Мы разработаем генетический алгоритм на Python для решения проблемы лабиринта. Это один из примеров вывода кода, который мы будем разрабатывать:

Студийный проект - Kapwing
Gif made on Kapwingwww.kapwing.com

Наша задача — найти путь от начальной до конечной точки в лабиринте. Мы будем представлять лабиринт в виде двумерного массива, используя pyamaze, где 1 представляет собой путь, а 0 — стену.

В генетическом алгоритме рассматриваются пять фаз:

Исходное население
Фитнес-функция
Выбор
кроссовер
Мутация

Давайте погрузимся в код для решения лабиринта с использованием GA.

Первым шагом является создание лабиринта и агента. Лабиринт создается с помощью библиотеки pyamaze. Агент создается с использованием той же библиотеки и используется для навигации по лабиринту.

import random
from pyamaze import maze, agent

# Create the maze and agent
m = maze(rows, columns)
m.CreateMaze(loopPercent=100)
a = agent(m, filled=True, footprints=True, shape="arrow")
mazeMap = m.maze_map

Исходное население:

Мы начнем с инициализации совокупности потенциальных решений. Каждое потенциальное решение будет представлено в виде массива целых чисел, где каждое целое число представляет собой столбец в лабиринте. Первым целым числом всегда будет 1, что представляет собой начальную точку, а последним целым числом всегда будет количество столбцов, представляющее конечную точку.

Приведенная ниже функция генерирует начальную популяцию размера poolSize:

def initialPopulation(populationSize , rows, columns):
    for i in range(populationSize):
        pop = []
        pop.append(1)
        for j in range(1, columns - 1):
            pop.append(random.randint(1, rows + 1))
        pop.append(columns)
        population.append(pop)

Функция фитнеса:

Функция фитнеса определяет, насколько физически подготовлен человек (способность человека конкурировать с другими людьми). Это дает каждому человеку ценность пригодности. Вероятность того, что особь будет выбрана для воспроизводства, основана на ее ценности пригодности.

и) Количество витков:

Первая метрика, используемая для оценки пригодности человека, — это количество поворотов, необходимых для достижения конца лабиринта. Количество поворотов определяется как количество раз, когда человек меняет направление при движении от начальной точки к конечной точке лабиринта.

Чтобы вычислить количество поворотов, функция перебирает каждого индивидуума в популяции и для каждого индивидуума она перебирает столбцы лабиринта и проверяет, отличается ли текущее положение индивидуума от его предыдущего положения. Если позиции разные, это означает, что человек повернулся, и счетчик поворотов увеличивается.

Затем количество ходов добавляется в список под названием "noOfTurns", в котором хранится количество ходов для всех особей в популяции. Наконец, переменная поворотов сбрасывается на 0, чтобы подготовиться к оценке следующего индивидуума в популяции.

noOfTurns = []
def fitness():
    # Number of turns
    for i in population:
        turns = 0
        for j in range(columns-2):
            if i[j + 1] != i[j]:
                turns += 1
        noOfTurns.append(turns+1)
        turns = 0

ii) Поиск пути:

Список путь содержит путь для каждого человека в популяции. Путь представлен в виде списка кортежей (x, y), представляющих координаты каждой точки пути. Первый кортеж — это (1, 1), который является начальной точкой лабиринта, а последний кортеж — это (строки, столбцы), который конечная точка лабиринта.

Чтобы сгенерировать путь для каждого человека, код перебирает каждую хромосому у человека и определяет направление движения на основе разницы между значениями соседних хромосом. Если разность положительная, то движение идет вниз или вправо, а если разность отрицательна, то движение идет вверх или влево.

Для каждой хромосомы код генерирует последовательность кортежей (x, y) в зависимости от направления движения. Если направление вниз или вправо, то последовательность генерируется путем итерации от текущего значения хромосомы к следующему значению хромосомы. Если направление вверх или влево, то последовательность генерируется путем итерации от текущего значения хромосомы к следующему значению хромосомы в обратном порядке.

Затем сгенерированные кортежи (x, y) добавляются во временный список p. После обработки всех хромосом конечная точка лабиринта добавляется в список p. чтобы завершить путь.

Наконец, список p добавляется к списку path, который содержит путь для текущего человека. Процесс повторяется для всех особей популяции.

path = []
def fitness():
for i in population:
        p = []
        for j in range(0, rows - 1):
            if (i[j + 1] - i[j]) >= 0: # down or right
                for k in range(i[j], i[j+1]+1):
                    if k <= rows or k <= columns: # check if value is within range
                        p.append((k, j+1))
            if (i[j + 1] - i[j]) < 0: # up or left
                for k in range(i[j], i[j+1]-1, -1):
                    if k <= rows or k <= columns: # check if value is within range
                        p.append((k, j+1))
        p.append((rows, columns))
        path.append(p)

iii) Поиск препятствий:

Этот код использует путь, сгенерированный для каждого человека в популяции, чтобы определить количество встреченных препятствий. Он делает это, перебирая каждую координату пути и проверяя, есть ли между ними препятствие (обозначенное 0 на карте лабиринта (которая содержит значения всех 4 направлений для всех кортежей)) и следующая координата в пути. При обнаружении препятствия счетчик наблюдений увеличивается. После проверки всех координат на пути счетчик наблюдений добавляется к списку препятствий, а затем сбрасывается на 0 для следующего человека.

Обратите внимание, что код проверяет, находится ли следующая координата пути в той же строке или столбце, что и текущая координата, перед проверкой препятствий в соответствующем направлении. Это гарантирует, что код проверяет наличие препятствий только вдоль горизонтальных или вертикальных путей и не учитывает диагональные препятствия.

obstacles = []
def fitness():
obs = 0
    for i in path:
        for j in range(len(i) - 1):
            if i[j+1][0]-i[j][0] >= 0 and i[j+1][1] == i[j][1]:
                if mazeMap[(i[j])]["S"] == 0:
                    obs += 1
            if i[j+1][0]-i[j][0] < 0 and i[j+1][1] == i[j][1]:
                if mazeMap[(i[j])]["N"] == 0:
                    obs += 1
            if i[j+1][1]-i[j][1] >= 0 and i[j+1][0] == i[j][0]:
                if mazeMap[(i[j])]["E"] == 0:
                    obs += 1
            if i[j+1][1]-i[j][1] < 0 and i[j+1][0] == i[j][0]:
                if mazeMap[(i[j])]["W"] == 0:
                    obs += 1
        obstacles.append(obs)
        obs = 0

iv) Количество шагов:

Этот код перебирает каждый элемент i в списке path и добавляет длину этого элемента (который сам является списком) в список noOfSteps. . По сути, это подсчет количества шагов, предпринятых для достижения цели для каждого пути.

noOfSteps = []
def fitness():
for i in path:
        noOfSteps.append(len(i))

v) Значение пригодности с использованием формул:

Это последняя часть фитнес-функции. Этот код вычисляет значение пригодности для каждого человека в популяции. Оценка пригодности используется для определения того, насколько хорошо человек выполняет данную задачу, в данном случае нахождение пути через лабиринт.

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

Чтобы рассчитать значение приспособленности, сначала из генеральной совокупности определяются минимальное и максимальное значения каждого фактора. Затем для каждого человека рассчитываются нормализованные значения каждого фактора в диапазоне от 0 до 1. Затем нормализованные значения умножаются на их соответствующие веса и объединяются для получения окончательной оценки пригодности.

Окончательная оценка физической подготовки рассчитывается следующим образом:

minimumObstacles = min(obstacles)
    maximumObstacles = max(obstacles)
    minimumTurns = min(noOfTurns)
    maximumTurns = max(noOfTurns)
    minimumSteps = min(noOfSteps)
    maximumSteps = max(noOfSteps)
    weightOfObstacle = 3
    weightOfPath = 2
    weightOfTurn = 2

    for i in range(populationSize):
        finalObstacles = (1 - ((obstacles[i] - minimumObstacles) / (maximumObstacles - minimumObstacles)))
        FinalObstacles.append(finalObstacles)
        finalTurns = (1 - ((noOfTurns[i] - minimumTurns) / (maximumTurns - minimumTurns)))
        FinalTurns.append(finalTurns)
        finalSteps = (1 - ((noOfSteps[i] - minimumSteps) / (maximumSteps - minimumSteps)))
        FinalSteps.append(finalSteps)
        finalFitness = ((100 * weightOfObstacle * FinalObstacles[i]) * ( ((weightOfPath * FinalSteps[i]) + (weightOfTurn * FinalTurns[i])) / (weightOfPath + weightOfTurn)))
        FinalFitness.append(finalFitness)

Выбор:

Идея фазы отбора состоит в том, чтобы выбрать наиболее приспособленных особей и позволить им передать свои гены следующему поколению.

Две пары людей (родители) выбираются на основе их показателей физической подготовки. Особи с высокой приспособленностью имеют больше шансов быть отобранными для размножения.

Кроссовер:

Кроссовер — это наиболее важная фаза генетического алгоритма. Для каждой пары родителей, подлежащих скрещиванию, внутри генов случайным образом выбирается точка кроссовера.

Например, предположим, что точка кроссовера равна 3, как показано ниже.

Потомство создается путем обмена генами родителей между собой до тех пор, пока не будет достигнута точка кроссовера.

Новое потомство добавляется к популяции.

Эта функция реализует операцию кроссовера для генетического алгоритма. Операция кроссовера используется для создания нового потомства от двух родительских решений в популяции. Функция сначала перебирает популяцию парами особей, выбирает случайную точку пересечения между 0 и количеством столбцов в лабиринте, а затем создает двух дочерних элементов, комбинируя генетический код двух родителей. Генетический код в данном случае представляет собой путь координат от начальной точки к конечной. Точка пересечения определяет, где пути двух родителей разделяются и объединяются для создания путей дочерних элементов. Наконец, функция заменяет два родительских решения двумя дочерними в популяции.

def crossover():
    for i in range(0, populationSize - 1, 2):
        crossoverPoint = random.randint(0, columns - 1)
        parent1 = deepcopy(population[i])
        parent2 = deepcopy(population[i + 1])
        child1 = []
        child2 = []
        # Combine the genetic code of the parents to create the children
        for j in range(len(parent1)):
            if j < crossoverPoint:
                child1.append(parent1[j])
                child2.append(parent2[j])
            else:
                child1.append(parent2[j])
                child2.append(parent1[j])
        # Replace the parents with the children in the population
        population[i] = child1
        population[i + 1] = child2

Мутация:

У определенных новых потомков некоторые из их генов могут быть подвергнуты мутации с низкой случайной вероятностью. Это означает, что некоторые биты в битовой строке могут быть инвертированы.

Функция Мутация выполняет случайную мутацию каждого человека в популяции. В частности, он случайным образом выбирает позицию в генетическом коде индивидуума (представленном в виде списка целых чисел) между вторым и предпоследним элементами и заменяет значение в этой позиции случайно сгенерированным целым числом между 1 и количество рядов в лабиринте. Это вводит случайные вариации в популяцию, чтобы помочь предотвратить преждевременную сходимость к субоптимальным решениям.

Мутация происходит для поддержания разнообразия в популяции и предотвращения преждевременной конвергенции.

def mutation():
    for i in population:
        i[random.randint(1, columns - 2)] = random.randint(1, rows)

Алгоритм пузырьковой сортировки:

Эта функция сортирует популяцию на основе пригодности каждого человека в порядке убывания, используя простой алгоритм пузырьковой сортировки. Сначала он сравнивает приспособленность каждой пары особей и меняет их местами, если особь с более высокой приспособленностью идет первой, пока не будет отсортирована вся популяция. Затем он печатает отсортированное население вместе с соответствующими показателями пригодности. Этот этап сортировки важен, потому что он помогает выбрать наиболее приспособленных особей для следующего поколения и отбросить более слабых.

# Bubble sorting in descending order
def sorting():
    for i in range(populationSize - 1):
        for j in range(i+1, populationSize):
            if FinalFitness[j] > FinalFitness[i]:
                FinalFitness[i], FinalFitness[j] = FinalFitness[j], FinalFitness[i]
                population[i], population[j] = population[j], population[i]
    for i in range(populationSize):
        print(f"{population[i]}          {FinalFitness[i]}")

Решение:

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

Если найдено допустимое решение, он сохраняет путь в списке sol, а затем перебирает путь для обновления словаря с именем словарь. Этот словарь представляет сопоставление каждой ячейки со следующей ячейкой пути, т. е. ключи словаря представляют координаты ячеек пути, а значения словаря представляют координаты следующей ячейки пути.

Наконец, он возвращает 1, если решение найдено, иначе возвращает 0, указывающий на то, что в текущем поколении популяции решения не существует.

def solution():
    sol = []
    for i in range(populationSize):
        if FinalFitness[i] > 0 and obstacles[i] == 0:
            sol = path[i]
            for j in range(len(sol) - 1):
                dictionary.update({sol[j+1]:sol[j]}) # This loop updates a dictionary named dictionary where the keys represent the coordinates of the cells that form the path, and the values represent the coordinates of the cells that should be visited next in order to follow the path.
            return 1
    return 0

Основная функция:

Этот код является основным кодом драйвера для генетического алгоритма решения лабиринта. Во-первых, он генерирует начальную популяцию из populationSize особей, используя функцию initialPopulation(). Затем он входит в цикл, который выполняется до тех пор, пока не будет найдено решение. В каждой итерации цикла он вычисляет пригодность каждого человека, используя функцию fitness().

Затем он проверяет, было ли найдено решение, используя функцию solution(). Если решение найдено, он выводит сообщение с указанием номера итерации и использует функцию tracePath() из модуля лабиринта для визуализации пути решения в лабиринте. Наконец, он завершает программу с помощью оператора break.

Если решение еще не найдено, оно приступает к генетическим операциям для создания следующего поколения особей. Сначала он сортирует население по приспособленности, используя функцию sorting(). Затем он выполняет пересечение популяции, используя функцию crossover(). Наконец, он выполняет мутацию в популяции, используя функцию mutation().

Затем цикл продолжается со следующей итерацией, и процесс повторяется до тех пор, пока не будет найдено решение.

initialPopulation(populationSize,rows,columns)
i = 0
while True:
    i+=1
    fitness()
    if solution():
        print(f"Solution found in iteration number = {i}")
        m.tracePath({a:dictionary},delay=500)
        m.run()
        break
    sorting()
    crossover()
    mutation()

Псевдокод:

START
Generate the initial population
Compute fitness
REPEAT
    Selection
    Crossover
    Mutation
    Compute fitness
UNTIL population has converged
STOP

Полный код на Python:

Для реализации этого алгоритма на Python мы будем использовать модуль pyamaze.

# Registratioin Number : 2021-MC-77
# Name : Muhammad Faisal
# Section : B
# Home Work : CEP - 1
# Date : 5th March 2023
# Submitted To : Sir Doctor Muhammad Ahsan Naeem

import random
from copy import deepcopy
from pyamaze import maze, agent

rows = 7
columns = 7
population = []
populationSize = 400
FinalObstacles = []
FinalTurns = []
FinalSteps = []
FinalFitness = []
dictionary = {}

# Create the maze and agent
m = maze(rows, columns)
m.CreateMaze(loopPercent=100)
a = agent(m, filled=True, footprints=True, shape="arrow")
mazeMap = m.maze_map

def initialPopulation(populationSize , rows, columns):
    for i in range(populationSize):
        pop = []
        pop.append(1)
        for j in range(1, columns - 1):
            pop.append(random.randint(1, rows + 1))
        pop.append(columns)
        population.append(pop)
       
noOfTurns = []
path = []
obstacles = []
noOfSteps = []
def fitness():
    # Number of turns
    for i in population:
        turns = 0
        for j in range(columns-2):
            if i[j + 1] != i[j]:
                turns += 1
        noOfTurns.append(turns+1)
        turns = 0

    # Finding Path
    for i in population:
        p = []
        for j in range(0, rows - 1):
            if (i[j + 1] - i[j]) >= 0: # down or right
                for k in range(i[j], i[j+1]+1):
                    if k <= rows or k <= columns: # check if value is within range
                        p.append((k, j+1))
            if (i[j + 1] - i[j]) < 0: # up or left
                for k in range(i[j], i[j+1]-1, -1):
                    if k <= rows or k <= columns: # check if value is within range
                        p.append((k, j+1))
        p.append((rows, columns))
        path.append(p)

   # Obstacles
    obs = 0
    for i in path:
        for j in range(len(i) - 1):
            if i[j+1][0]-i[j][0] >= 0 and i[j+1][1] == i[j][1]:
                if mazeMap[(i[j])]["S"] == 0:
                    obs += 1
            if i[j+1][0]-i[j][0] < 0 and i[j+1][1] == i[j][1]:
                if mazeMap[(i[j])]["N"] == 0:
                    obs += 1
            if i[j+1][1]-i[j][1] >= 0 and i[j+1][0] == i[j][0]:
                if mazeMap[(i[j])]["E"] == 0:
                    obs += 1
            if i[j+1][1]-i[j][1] < 0 and i[j+1][0] == i[j][0]:
                if mazeMap[(i[j])]["W"] == 0:
                    obs += 1
        obstacles.append(obs)
        obs = 0

    # Number of steps
    for i in path:
        noOfSteps.append(len(i))

    # Fitness Value
    minimumObstacles = min(obstacles)
    maximumObstacles = max(obstacles)
    minimumTurns = min(noOfTurns)
    maximumTurns = max(noOfTurns)
    minimumSteps = min(noOfSteps)
    maximumSteps = max(noOfSteps)
    weightOfObstacle = 3
    weightOfPath = 2
    weightOfTurn = 2

    for i in range(populationSize):
        finalObstacles = (1 - ((obstacles[i] - minimumObstacles) / (maximumObstacles - minimumObstacles)))
        FinalObstacles.append(finalObstacles)
        finalTurns = (1 - ((noOfTurns[i] - minimumTurns) / (maximumTurns - minimumTurns)))
        FinalTurns.append(finalTurns)
        finalSteps = (1 - ((noOfSteps[i] - minimumSteps) / (maximumSteps - minimumSteps)))
        FinalSteps.append(finalSteps)
        finalFitness = ((100 * weightOfObstacle * FinalObstacles[i]) * ( ((weightOfPath * FinalSteps[i]) + (weightOfTurn * FinalTurns[i])) / (weightOfPath + weightOfTurn)))
        FinalFitness.append(finalFitness)

def crossover():
    for i in range(0, populationSize - 1, 2):
        crossoverPoint = random.randint(0, columns - 1)
        parent1 = deepcopy(population[i])
        parent2 = deepcopy(population[i + 1])
        child1 = []
        child2 = []
        # Combine the genetic code of the parents to create the children
        for j in range(len(parent1)):
            if j < crossoverPoint:
                child1.append(parent1[j])
                child2.append(parent2[j])
            else:
                child1.append(parent2[j])
                child2.append(parent1[j])
        # Replace the parents with the children in the population
        population[i] = child1
        population[i + 1] = child2

def mutation():
    for i in population:
        i[random.randint(1, columns - 2)] = random.randint(1, rows)

# Bubble sorting in descending order
def sorting():
    for i in range(populationSize - 1):
        for j in range(i+1, populationSize):
            if FinalFitness[j] > FinalFitness[i]:
                FinalFitness[i], FinalFitness[j] = FinalFitness[j], FinalFitness[i]
                population[i], population[j] = population[j], population[i]
    for i in range(populationSize):
        print(f"{population[i]}          {FinalFitness[i]}")

def solution():
    sol = []
    for i in range(populationSize):
        if FinalFitness[i] > 0 and obstacles[i] == 0:
            sol = path[i]
            for j in range(len(sol) - 1):
                dictionary.update({sol[j+1]:sol[j]}) # This loop updates a dictionary named dictionary where the keys represent the coordinates of the cells that form the path, and the values represent the coordinates of the cells that should be visited next in order to follow the path.
            return 1
    return 0

# Main Function
initialPopulation(populationSize,rows,columns)
i = 0
while True:
    i+=1
    fitness()
    if solution():
        print(f"Solution found in iteration number = {i}")
        m.tracePath({a:dictionary},delay=500)
        m.run()
        break
    sorting()
    crossover()
    mutation()