Программная реализация Q-learning+
Архив Проекта | |
Пожалуйста, не редактируйте эту страницу! |
- Эта статья — часть материалов: проекта RNAFoldingAI
На основе постановки задачи в терминах Q-learning, необходимо реализовать модификацию алгоритма Q-learning, учитывающею реальные условия задач. Данную модификацию мы назовем Q-learning+.
Вопросы, которые нужно осветить
- Множество действий
- Множество состояний
- Вознаграждение (подкрепление) и Целевое состояние
- Обобщение Q - матрицы
Открытое множество действий
Действием агента будем считать все возможные повороты элементов цепи. Действие определяется двумя числами: (1) выбранной позицией - нуклеотид который поворачивается и (2) идентификатором поворота - определяет 9 углов поворота с последующим пересчетом позиций атомов нуклеотида.
Первым отличием является необходимость реализации открытого множества действий, а не конечного набора. Более того изначально данное множество пусто. Оно реализуется списком объектов «ДействиеВращения».
public class RotateAction : Action
{
public int Position;
public int FragID;
public RotateAction(int argPosition, int argFragID)
{
Position = argPosition;
FragID = argFragID;
}
}
public class RNAAgent : Agent
{
public new List<RotateAction> Actions = new List<RotateAction>();
}
«Действия» различают: обдуманное (техногенное) или случайное (естественное), причем по умолчанию действие случайное. Таким образом, пока нету списка возможных обдуманных действий агент может не влиять на среду. Сама же среда в это время будет осуществлять естественные действия.
public class Action
{
/// <summary>
/// Тип действия Technogenic - обдуманное, Natural - случайное
/// </summary>
public ActionType Type = ActionType.Natural;
}
При наблюдении, среда возвращает успешные действия, те которые случайно понижают энергию цепи РНК. На основе них агент заполняет список обдуманных действий.
public class RNAAgent : Agent
{
public void Observe(Sensor argSensor)
{
if (argSensor == null) return;
Sensor = argSensor as RNASensor;
if (Sensor.oAction != null)
{
bool IsFounded = false;
for (int i = 0; i < Actions.Count; i++)
{
if (Actions[i] == Sensor.oAction)
{
IsFounded = true;
break;
}
}
if (IsFounded == false)
{
Actions.Add((RotateAction)Sensor.oAction.Clone());
}
}
}
}
Открытое множество состояний
Аналогично действиям множество состояний нужно реализовать как открытое множество состояний, а не конечный жестко заданный набор. Поэтому состояние определяется списком целых чисел, обозначающих некоторую последовательность.
public class State
{
public List<int> TimeActionList = new List<int>();
}
В нашем случае, это последовательность позиций, поворот в которых понизил энергию РНК-цепи. Среда, осуществляя ход времени запоминает текущее состояние, а также некоторые другие характеристики. А при наблюдении агентом, подает эти значения на сенсор.
public class RNAWorld : World
{
/// Выполнить действия среды на один этап
protected override float NextTime(Effector argEffector)
{
...
if (CurrentScore < LowScore)
{
IsLowPose = true;
LowPose = CurrentPose.Clone();
LowScore = CurrentScore;
CurrentState.TimeActionList.Add(oRotate.CurrentPosition);
}
...
}
// Обновляет состояние сенсора
public override Sensor GetSensor()
{
if (IsLowPose)
{
RNASensor locSensor = new RNASensor();
locSensor.Reward = CurrentReward;
locSensor.oAction = CurrentAction;
locSensor.oState = CurrentState;
locSensor.LowPose = CurrentPose.Clone();
locSensor.LowScore = CurrentScore;
return locSensor;
}
return null;
}
}
Вознаграждение и Целевое состояние
Вознаграждение от среды в нашем эксперименте - это значение оценки энергии РНК-цепи LowScore.
Агент же это вознаграждение от среды, которое определяется абсолютным значением оценки энергии цепи, будет преобразовывать к относительному виду. Для этого он будет считать вознаграждением за действие разность между предыдущей и текущей оценкой энергии. То есть для него вознаграждением будет, то на сколько его действия позволили улучшить последнее состояние с минимальной энергией.
Например, рассмотрим фрагмент поиска:
Position: 2 FragID: 1280 Change: х.ххх LowScore: 8.539 Position: 4 FragID: 2093 Change: 0.076 LowScore: 8.463 Position: 2 FragID: 1187 Change: 1.328 LowScore: 7.135 Position: 4 FragID: 2550 Change: 0.290 LowScore: 6.845
Первый поворот 2 нуклеотида (Position) в положение 1280 (FragID) дает оценку энергии 8.539 (LowScore). Далее в среде выполняются некоторые действия, которые не приводят к никакому вознаграждению, так как не уменьшают энергию относительно 8.539. Но вот какое то из действий, а именно поворот 4 нуклеотида в положение 2093, дает вознаграждение от среды 8.463. Агент же преобразовывает это значение как разность 8.539 - 8.463 = 0.076. Таким образом, истинным вознаграждением (скажем так, которое агент ощущает) является столбец Change.
Обобщение Q - матрицы
Классический вид Q - матрицы следующий:
- Q[s',a'] = Q[s',a'] + LF * ( r + DF * MAX(Q,s) - Q[s',a'] ), где
- s' - Предыдущие состояние
- a' - Предыдущие действие
- s - Текущие состояние
- r - Вознаграждение за предыдущие действие, полученное сейчас
- LF - величина от [0..1], фактор обучения. Чем он выше, тем сильнее агент доверяет новой информации.
- DF - величина от [0..1], фактор дисконтирования. Чем он меньше, тем меньше агент задумывается о выгоде от будущих своих действий.
Некоторая необычность состоит в том, что обновляется не текущие состояние-действие на основе предыдущих, а наоборот, предыдущие состояние-действие, на основе текущих.
Для упрощения анализа примем LF = 1; DF = 1, тогда получим
- Q[s',a'] = r + MAX(Q,s)
В условиях, когда нет опыта что делать в текущем состоянии MAX(Q,s) возвратит 0, т.к. состояние-действие ранее не оценивало ситуацию. Если же такая оценка уже проводилось, то будет возвращено вознаграждение за наилучшее из имеющихся действий (а не за текущие). Таким образом, предыдущие состояние-действие равно сумме текущего вознаграждения и вознаграждение лучшего из имеющихся действий в текущем состоянии.
Обновление Q - матрицы
Из-за открытых множеств действий и состояний, матрица Q реализована так же как открытый список, к которому определяет доступ по ключу. Ключ же формируется как строка, однозначно характеризующая определенное состояние и осуществленное действие. Например, ключ может иметь вид: "4;1;-1;244;". Что означает в состоянии - успешное действие в позиции 4, успешное действие в позиции 1, осуществлено действие для позиции 1 с поворотом 244. При этом если определенного состояния еще нету, то оно заносится в список.
public class QLearning
{
/// Матрица предпочтения действия в определенном состоянии
public Dictionary<string, float> Q = new Dictionary<string, float>();
/// Обновить матрицу предпочтения действий
public void UpdateQ(RNAAgent argAgent)
{
SJ.AICore.Action a = argAgent.Sensor.oAction;
double r = argAgent.Sensor.Reward;
State s = argAgent.Sensor.oState;
if (!Q.ContainsKey(new Key(s, a).ToString()))
{
Q.Add(new Key(s, a).ToString(), 0.0f);
}
float locQ = Q[new Key(s, a).ToString()];
Q[new Key(s, a).ToString()] = Convert.ToSingle(locQ + LF *
(r + DF * GetMax(s, argAgent) - locQ));
}
/// Дать оценку выбраному действию
private float GetMax(State argState, RNAAgent argAgent)
{
float max = 0;
for (int i = 0; i < argAgent.Actions.Count; i++)
{
string key = new Key(argState, argAgent.Actions[i]).ToString();
if (Q.ContainsKey(key))
{
if (Q[key] > max)
{
max = Q[key];
}
}
}
return max;
}
}
Определение наилучшего действия
Наилучшее действие ищется в матрице Q - как действие с наибольшей оценкой. В нашем случае эта оценка представляет собой величину на сколько удалось уменьшить энергию по сравнению с предыдущим шагом. При этом поиск ведется учитывая все состояния определенного шага. То есть проверяются значения по ключу. Ключ формируется как текущие состояние плюс к нему добавляется один шаг (планируемый), и проверяется все множество возможных действий в этих состояниях. Таким образом, определяется наилучшее следующее действие в аналогичных условиях. Если оказалось что действие не удачно (не привело к понижению энергии), то определение не сможет предложить другого действия - и алгоритм установит вид действия в естественный, чтобы не влиять на среду. При этом среда будет осуществлять случайный поиск.
public class QLearning
{
/// <summary>
/// Какое действие нужно сделать в текущих условиях
/// </summary>
/// <param name="argAgent">Агент для которого нужно сделать действие</param>
/// <returns>Выбраное действие</returns>
public RotateAction WhatAction(RNAAgent argAgent)
{
State locState = argAgent.Sensor.oState.Clone();
RotateAction locAction = new RotateAction();
float max = 0;
int maxAction = -1;
int index = locState.TimeActionList.Count;
locState.TimeActionList.Add(0);
//TODO переделать Q матрицу - в таблицу базы данных и применять select-запрос
for (int j = 1; j < 4+1; j++)
{
locState.TimeActionList[index] = j;
for (int i = 0; i < argAgent.Actions.Count; i++)
{
string key = new Key(locState, argAgent.Actions[i]).ToString();
if (Q.ContainsKey(key))
{
if (Q[key] > max)
{
max = Q[key];
maxAction = i;
}
}
}
}
if (maxAction != -1)
{
locAction = argAgent.Actions[maxAction];
if (argAgent.ActionOldValue == locAction ||
argAgent.ActionOldValue == new RotateAction())
{
locAction.Type = ActionType.Technogenic;
}
else
{
locAction.Type = ActionType.Natural;
}
}
return locAction;
}
}
См. также
- Q-learning - классика