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

Мы погружаемся в ту же проблему, используя генетический алгоритм (эвристика поиска, вдохновленная теорией эволюции путем естественного отбора) с помощью pyamaze для построения лабиринта и графического интерфейса. для задачи. Используемый язык программирования — Python версии 3.10.5.

Генетический алгоритм решает эту проблему с помощью следующих шагов:

  • Создание случайной популяции хромосом
  • Оценка наиболее приспособленных с использованием фитнес-функции
  • Выбор родительских хромосом и получение дочерних хромосом с помощью кроссинговера
  • Мутация в популяции
  • Повторяйте пункты 2–4, пока не будет найдено решение.

Планирование пути

Наиболее важным аспектом решения лабиринта является планирование пути. Для целей этого проекта мы в основном использовали два разных типа путей, оба реализованы как в квадратных [n*n], так и в прямоугольных [m*n] лабиринтах. Путь в основном определяется хромосомами в популяции, поэтому мы должны сначала обсудить хромосому. Существует два метода планирования пути: Сначала столбец и Сначала ряд.

Хромосома: Хромосома представлена ​​списком (объект списка в python), содержащим разные гены. В каждой хромосоме индекс списка представляет столбец, а значение элемента в каждом индексе представляет строку. Каждый ген представляет собой веху на пути.

Сначала столбец.Для столбца сначала путь перемещается сначала по столбцам, а если столбцы одинаковы, то он переходит по строкам.

Таким образом, хромосома [1 1 3 6 9 9 9 9 10 5 7 7 7 12 15] может быть представлена ​​как X, а промежуточные этапы представлены как O.

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

Таким образом, хромосома [1 1 3 6 9 9 9 9 10 5 7 7 7 12 15] может быть представлена ​​как X, а промежуточные этапы представлены как O.

Функции генетического алгоритма

Теперь сосредоточимся на том, как на самом деле работает программа. Лабиринт создается с помощью модуля pyamaze. Агент (или персонаж), который перемещается по сетке, следуя пути из генетического алгоритма, также создается с помощью pyamaze.

from pyamaze import maze,COLOR,agent

# Creating/Loading the maze and agent with starting point(1,1)
m=maze(row, column)

m.CreateMaze(row, column, theme=COLOR.dark, loopPercent=100)

a=agent(m, x=1, y=1, footprints = True)

# After creating the path through GA
m.tracePath({a:path})  
m.run()

Для получения дополнительной информации о pyamaze обратитесь к этому блогу автора модуля.

Создание случайной популяции хромосом:

Эта функция генерирует случайную популяцию для лабиринта, используя встроенный случайный модуль Python. Каждая хромосома имеет длину n-2 (столбец-2). Это сделано потому, что лабиринт начинается в позиции (1,1) и заканчивается в (m, n) для сетки размером m*n. Но, как мы увидим позже, имеет место случайная мутация. Чтобы предотвратить любые проблемы с созданным путем, мы добавим эти значения с помощью отдельной функции (chromosomemaker), когда это необходимо.

Фактические значения списка (хромосома) находятся в диапазоне от 0 до m-1. Функция возвращает полную популяцию хромосом, реализованную в виде списка списков.

def generate_population(rows, columns, popsize):
    for _ in range (0, pop_size):
        sublist =[]
        sublist= [random.randrange(0,rows) for _ in range(columns - 2)]
        population.append(sublist)
    
    return population

Создание направления хромосом:

Эта функция работает аналогично вышеупомянутой функции, но генерирует число для определения направления пути. Где 0 → первый столбец и 1 → первый ряд.

def generate_direction():

    direction = [random.randrange(2) for _ in range (pop_size)]
    return direction

Завершение хромосомы:

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

def chromosomemaker(chromosome):
    # chromosome --> each chromosome in population to be completed
    chromo = []
    chromo.append(0)

    for gene in chromosome:
        chromo.append(gene)

    chromo.append(Grid_rows-1)
    return chromo

Оценщик пути:

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

Аргументами функции являются население, направление и лабиринт карты (созданный модулем pyamaze).

#for checking infeasible steps
        for k in range (0,step-1):
            row,col = path[k]
            if mapmaze[path[k]]['E']==0 and path[k+1]==(row,col+1):
                infeas+=0.25
            elif mapmaze[path[k]]['W']==0 and path[k+1]==(row,col-1):
                infeas+=0.25
            elif mapmaze[path[k]]['N']==0 and path[k+1]==(row-1,col):
                infeas+=0.25
            elif mapmaze[path[k]]['S']==0 and path[k+1]==(row+1,col):
                infeas+=0.25
        inf.append(infeas)

Функции pathvar1 и pathvar2 используются для создания пути для каждой хромосомы. pathvar1 создает путь для данной хромосомы с первым столбцом (0), тогда как pathvar2 создает путь с первой строкой (1).

Функция пригодности и функции сортировки:

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

Нормализация здесь означает масштабирование значений от 0 до 1. Принимая во внимание, что вес невозможных шагов = 5, вес поворотов и шагов = 2. В приведенном ниже кодовом блоке maxinf = максимальное количество недопустимых шагов в популяции, а mininf = минимальное невозможное шагов (принимается за 0, что означает решение).

Сортировка в алгоритме происходит в зависимости от значения пригодности и в порядке убывания. [Наиболее подходящий (например, 500) → Наименее подходящий (например, 0)]

def fitnessfn(inf, turns, steps):
     maxinf, maxturns, maxsteps = max(inf), max(turns), max(steps)
     mininf, minturns, minsteps = 0, min(turns), min(steps)
     for j in range (0,pop_size):
        finf = 1 - ((inf[j] - mininf) / (maxinf - mininf))
        fturn = 1 - ((turns[j] - minturns) / (maxturns - minturns))
        flength = 1 - ((steps[j] - minsteps) / (maxsteps - minsteps))

        fitval = 5 * 100 * finf * ((2 * fturn + 2 * flength) / (2 + 2))
        fitness.append(fitval)
    return fitness

    #Sort function can be used as follows
    sortt=[(fitness[i],population[i]) for i in range (0,pop_size)]
    sortt.sort(reverse=True)
    #then unpack the sortt into seperate list for fitness and population and
    #return it.

Функция кроссовера:

Кроссовер включает в себя выбор части родителя 1 и объединение его с родителем 2. Например, для создания двух новых хромосом, как показано ниже.

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

Мутация и поиск решения:

Мутация — это размещение случайного значения в случайном индексе каждой хромосомы. Это добавляет элемент мутации, который существует и в природе. Частота мутаций для нашего алгоритма составляет 50%.

Решение определяется путем поиска хромосомы с нулевыми невозможными шагами, этот метод отдает приоритет поиску решения, а не поиску наиболее оптимального.

     
def mutation(population):
    index, val = 0,0
    for i in range (0,pop_size,2):
        index = random.randint(0,Grid_columns-3)
        val = random.randint(0,Grid_rows-1)
        population[i].insert(index,val)
    return population


def solution(inf):
    for i in range(0,pop_size):
        if (inf[i]==0.00) :
            return i
    return 0

Решение

Сравнение в случайных сетках:

На приведенных ниже диаграммах показано, как меняется вероятность успеха алгоритма для случайных лабиринтов. Данные для этих сеток были собраны за 100 итераций. Среднее поколение, в котором было найдено решение, следует той же тенденции, что и показатель успеха.

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

Сравнение случайных и одинаковых сеток:

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

Тренды в фитнесе:

Графики были построены с использованием пакета matplotlib Python.

Код:

Полный код можно найти на GitHub по следующей ссылке. Код

https://gist.github.com/AbiamAsifKhalid/c3b76957f5e5738403ceab4e331d5eee