Автономное планирование пути, классическая задача программирования, реализуемая с помощью различных алгоритмов и методов. Он имеет множество практических применений в промышленности, доставке посылок, наблюдении и даже может спасать человеческие жизни в случае стихийных бедствий.
Мы погружаемся в ту же проблему, используя генетический алгоритм (эвристика поиска, вдохновленная теорией эволюции путем естественного отбора) с помощью 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