Программная реализация 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‎ - классика