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

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

Q-обучение - это алгоритм обучения с подкреплением без использования моделей. Цель Q-Learning - изучить политику, которая сообщает агенту, какие действия следует предпринять при каких обстоятельствах. Для него не требуется модель среды, и он может решать проблемы со стохастическими переходами и вознаграждениями, не требуя адаптации.

Сначала импортирую необходимые модули. Я буду использовать библиотеку networkx для определения Graph

Давайте определим и визуализируем график

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

Математически,

Значения Q можно рассчитать с помощью уравнения:

Q (s, a) ‹= (1-α) Q (s, a) + α (R (s, a) + γmaxQ (s’, a ’)), где

  • Q (s, a) - это значение Q действия a из состояния s в s ’
  • α - скорость обучения
  • R (s, a) - это награда за выполнение действия a из состояния s в s ’
  • γ - коэффициент дисконтирования
  • maxQ (s ’, a’) - максимальное значение Q среди всех возможных действий a ’в следующем состоянии s’

Я хочу найти кратчайший путь от 0 до 10. Мне нужно привлечь прогулки к ребрам с участием 10, поэтому я даю эти действия высокой награде. В библиотеке networkx G [узел] предоставляет все узлы, которые образуют ребро с узлом.

Здесь я инициализирую матрицу вознаграждения и Q:

Я установил для всех наград 0, кроме действий, поступающих в узел 10. Эти действия идут от 8 до 10 или от 9 до 10. Как и награды, Q-значения инициализируются в матрице. Чтобы исключить невозможные действия, их Q-значения установлены на -100. Например, на графике невозможно перейти непосредственно от 2 к 10, поэтому его значение Q установлено как -100. Возможные действия инициализируются как 0. Давайте посмотрим на матрицы R и Q:

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

После нам понадобится функция для обновления Q-значения предпринятого действия.

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

Давайте проверим окончательные значения Q

Теперь мы можем найти кратчайший путь от 0 до 10, выбрав максимальное значение Q из матрицы Q при принятии решения о действии:

использованная литература

Https://en.wikipedia.org/wiki/Graph_theory
https://everything.explained.today/Q-learning/
http://firsttimeprogrammer.blogspot.com/ 2016/09 / get-ai-smarter-with-q-learning.htm l