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