[Перевод] Эволюционные вычисления: учим табуретку ходить27.10.2017 11:49

Этот туториал посвящён эволюционным вычислениям, тому, как они работают и как реализовать их в своих проектах и играх. После прочтения статьи вы сможете овладеть мощью эволюции для поиска решений задач, решить которые вы не можете. В качестве примера в этом туториале будет показано, как эволюционные вычисления можно использовать для обучения простого существа ходьбе. Если вы хотите ощутить мощь эволюционных вычислений в браузере, оцените Genetic Algorithm Walkers.

Часть 1. Теория

Введение

Как программист, вы наверно знакомы с концепцией алгоритма. Если у вас есть задача, то вы пишете чёткий набор инструкций для её решения. Но что происходит, когда задача слишком сложна, или вы не понимаете, как её решить? Есть очень чёткая стратегия оптимальной игры в судоку, но не для распознавания лиц. Как закодировать решение задачи, если вы совершенно не представляете, как её решать?

В этом случае обычно применяется искусственный интеллект. Одна из простейших техник, которые можно использовать для решения такого класса задач — эволюционные вычисления. Если вкратце, то они основаны на идее применения дарвиновской эволюции к компьютерной программе. Цель эволюции — улучшение качества плохого решения случайными мутациями, пока задача не будет решена с необходимой точностью. В этом туториале мы рассмотрим, как можно применять эволюционные вычисления для обучения оптимальной стратегии ходьбы. Более сложную реализацию можно посмотреть в видео ниже (статья: Flexible Muscle-Based Locomotion for Bipedal Creatures).

Естественный искусственный отбор

Есть вероятность, что вы слышали дарвиновской концепции выживания наиболее приспособленных. Основная идея проста: выживание — сложная задача, и выжившие существа имеют более высокий шанс на размножение. Среда естественным образом отбирает существ, которые наиболее к ней приспособлены, убивая тех, кто не справится с этой задачей. Это часто демонстрируется на слишком упрощённом (и вводящем в заблуждение) примере жирафов: более длинная шея помогала жирафам добираться до верхних ветвей. Со временем отбирались жирафы со всё более и более длинными шеями. Никогда не было непосредственной силы, «удлиняющей» шею жирафа: сама среда постепенно отбирала особей с более длинными шеями.

Такой же механизм можно применить и к компьютерным программам. Если у нас есть приблизительное решение задачи, то мы можем случайным образом изменять его и проверять, улучшило ли это его результаты. Если мы продолжим повторять этот процесс, то в результате всегда будем получать лучшее (или такое же) решение. Естественный отбор не зависит от поставленной задачи, по своей сути он управляется случайными мутациями.

Фенотип и генотип

Чтобы понять, как вычисления можно объединить с эволюцией, нам для начала нужно разобраться с ролью эвoлюции в биологии. В природе каждое существо имеет тело и набор поведений. Они известны как его фенотип, то есть то, как выглядит и ведёт себя существо. Волосы, глаза, цвет кожи — все они являются частью вашего фенотипа. Внешний вид существа в основном определяется набором инструкций, записанных внутри его клеток. Это называется генотипом и относится к информации, передаваемой в основном через ДНК. Фенотип — это то, как выглядит дом после строительства, генотип — исходный чертёж, управлявший его созданием. Первая причина, по которой мы разделяем фенотип и генотип, очень проста — среда играет огромную роль в конечном внешнем виде существа. Один и тот же дом, построенный с разным бюджетом, может быть очень разным.

В большинстве случаев именно среда определят успех генотипа. С точки зрения биологии успехом является достаточно долгое выживание. Успешные существа имеют бОльшие шансы на размножение, передачу своего генотипа своим потомкам. Информация о создании тела и поведений каждого существа хранится в его ДНК. При размножении существа его ДНК копируется и передаётся потомку. В процессе репликации возникают случайные мутации, вносящие изменения в ДНК. Эти изменения потенциально могут привести к изменениям в фенотипе.

Эволюционное программирование

Эволюционные вычисления — это довольно широкий и расплывчатый «зонтичный» термин, объединяющий в себе множество различных, хотя и похожих техник. Если конкретнее, мы сосредоточимся на эволюционном программировании: повторяемый алгоритм будет постоянным, но его параметры открыты для оптимизации. С биологической точки зрения мы используем естественный отбор только для мозга существа, но не для его тела.

Эволюционное программирование заключается в простой имитации механизма естественного отбора:

Initialisation (инициализация). Эволюция должна стартовать с начального решения. Выбор хорошей стартовой точки важен, потому что он может привести к совершенно различным результатам.
Duplication (дубликация). Создаётся множество копий текущего решения.
Mutation (мутация). Каждая копия случайным образом мутирует. Величина мутации критична, потому что она управляет скоростью выполнения эволюционного процесса.
Evaluation (оценка). Изменяется оценка гена, зависящая от показателей, продемонстрированных сгенерированным существом. Во многих случаях для него требуется этап интенсивной симуляции.
Selection (отбор). После оценки существ лучшим из них разрешается репликация, позволяющая стать основой следующего поколения.
Output (вывод). Эволюция — итеративный процесс, на любом этапе её можно остановить, чтобы получить улучшенную (или ту же самую) версию предыдущего поколения.

Локальные максимумы

Цель эволюции — максимизация приспособленности генома, лучшего соответствия определённой среде. Несмотря на глубокую связь с биологией, её можно рассматривать как чистую задачу оптимизации. У нас есть функция приспособленности и нам нужно найти точку её максимума. Проблема в том, что мы не знаем, как выглядит функция и можем только делать догадки, выбирая (симулируя) точки вокруг текущего решения.

На этом графике видно, как различные мутации (на оси X) приводят к разным оценкам приспособленности (ось Y). Эволюция занимается выборкой случайных точек в локальной окрестности $x$ , пытаясь увеличить приспособленность. Если учесть размер окрестности, то для достижения максимума потребуется множество поколений. И на этом этапе всё становится сложным. Если окрестность слишком мала, эволюция может застрять в локальных максимумах. Это решения, которые оптимальны локально, но не глобально. Очень часто локальные максимумы обнаруживаются посередине впадин приспособленности. Когда такое происходит, эволюция может и не найти поблизости более хорошее решение, после чего застрять. Часто говорят, что тараканы застряли в эволюционных локальных максимумах (Can An Animal Stop Evolving?): они невероятно успешны в своём образе жизни, и любые долговременные улучшения требуют слишком высокой кратковременной расплаты снижением их приспособленности.

Заключение

В этой части мы познакомились с концепцией эволюции и её ролью в искусственном интеллекте и машинном обучении.

В следующей части мы начнём создавать реализацию эволюционных вычислений. Первый необходимый этап — создание тела существа, которое сможет эволюционировать.

Часть 2. Фенотип.

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

Тело

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

Объектом нашего эксперимента будет очень простое двуногое существо. У него есть две ноги, L и R, которые прикреплены к телу шарнирами. Благодаря двум пружинам они могут поворачиваться. Когда пружины растягиваются и сжимаются, они втягивают и вытягивают ноги, вынуждая их поворачиваться. Существо не знает, как непосредственно поворачивать своими ногами, но может управлять длиной пружин, передавая им значение в интервале от -1 (сжатые) до +1 (растянутые).

Примечание: Перемещение сложных тел — серьёзная задача. Для финального проекта я заменил в Unity SpringJoint2D на DistanceJoint2D, потому что они более предсказуемы. Но я всё равно буду продолжать называть их пружинами. Для более сложного рэгдолла, показанного в анимации, части тела будут поворачиваться непосредственно из кода.

Мозг

Ходьба — это не только вопрос нахождения подходящих значений углов для L и R. Это длительная задача, требующая равно непрерывных движений ног. Если мы хотим ходить, то нам нужно предоставить существу компактный и значимый способ перемещения ног. Список возможных способов здесь бесконечен. Ради упрощения расслабление и сжатие пружин будут управляться двумя синусоидами.

Эволюционный процесс будет приспосабливать синусоиды L и R таким образом, чтобы существо могло ходить. Пример показан на анимации выше: зелёная и красная синусоида управляют соответственно ногами L и R.

Пружины — это сущности, управляемые существом, они будут целью наших эволюционных вычислений. Каждая синусоида имеет период $p$ в интервале от $m$ до $M$ и смещена по оси X на $o$ . Это значит, что цель эволюции — найти два множества для этих четырёх параметров, которые в результате дают наилучшую стратегию ходьбы.

Контроллер

В уже имеющейся системе у нас есть несколько сущностей: ноги, пружины и синусоиды. Чтобы упростить способ решения проблемы, давайте создадим класс LegController, позволяющий управлять сжатием пружин с помощью значений от -1 до +1:

Мы выполняем поворот ноги, меняя длину пружины в FixedUpdate. Это заставляет соединение подтягивать или выталкивать ногу, пока она не достигнет нужной точки назначения.

public class LegController : MonoBehaviour
{
	public DistanceJoint2D spring;

	private float contracted;
	private float relaxed;

	[Range(-1, +1)]
	public float position = +1;

	void Start () {
		float distance = spring.distance;
		relaxed = distance * 1.5f;
		contracted = distance / 2f;
	}

	void FixedUpdate ()
	{
		spring.distance = linearInterpolation(-1, +1, contracted, relaxed, position);
	}

	public static float linearInterpolation(float x0, float x1, float y0, float y1, float x)
	{
		float d = x1 - x0;
		if (d == 0)
			return (y0 + y1) / 2;
		return y0 + (x - x0) * (y1 - y0) / d;
	}
}

Два контроллера ног постоянно обновляются классом Creature:

public class Creature
{
	public LegController left;
	public LegController right;

	public void Update ()
	{
		left.position =  // ...
		right.position = // ...
	}
}

В следующей части туториала мы увидим, как эволюционирует класс Creature, чтобы включить в себя и геном существа.

Оценка приспособленности

Эволюция требует оценивать приспособленность существа. Этот этап, хотя и кажется довольно тривиальным, на самом деле невероятно сложен. Причина заключается в том, что оценка, которую мы присваиваем каждому существу в конце симуляции, должна правильно отображать именно то, чему мы хотим научиться. Если это нам не удастся, то мы неизбежно получим плохие результаты, а эволюция застрянет в локальных максимумах.

Моей первой попыткой была оценка приспособленности существа в зависимости от пройденного из начальной точки расстояния:

private Vector3 initialPosition;
public void Start ()
{
	initialPosition = transform.position;
}

public float GetScore ()
{
	return position.x - initialPosition.x;
}

Это привело к стратегии ходьбы, требующей наименьших усилий — волочение себя по полу:

Меня не устроило такое решение, потому что оно не ухватывало один из важнейших аспектов ходьбы: сохранение баланса. Во второй попытке я добавил очень серьёзный бонус всем существам, которым удавалось оставаться на ногах:

public float GetScore ()
{
	// Оценка ходьбы
	float walkingScore = position.x - initialPosition.x;

	// Оценка равновесия
	bool headUp =
		head.transform.eulerAngles.z < 0+30   ||
		head.transform.eulerAngles.z > 360-30;
	bool headDown =
		head.transform.eulerAngles.z > 180-45 &&
		head.transform.eulerAngles.z < 180+45;

	return
		walkingScore
		* (headUp   ? 2f   : 1f)	// Удвоить оценку, если UP
		* (headDown ? 0.5f : 1f)	// Оценка в два раза меньше, если DOWN
		;
}

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

Чтобы компенсировать это, я попытался придать стимул к тому, чтобы сохранение равновесия оценивалось независимо от ходьбы.

return
	walkingScore
	* (headDown ? 0.5f : 1f)
	+ (headUp ? 2f : 0f)
	;

Во всех моих попытках существа приходили к неуклюжему, но очень функциональному решению:

Заключение

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

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

Часть 3. Генотип.

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

Геном

Как сказано выше, каждая нога управляется синусоидой $s$ , задаваемой четырьмя параметрами: $m$ , $M$ , $p$ и $o$ , то есть:

$s=\frac{M-m}{2}\left ( 1+sin\left ( \left ( t+o \right )\frac{2\pi }{p} \right ) \right )+m$

Это просто обычная синусоида с периодом $p$ в интервале от $m$ до $M$ и смещённая по оси X на $o$ .

Задача обучения хождению теперь стала задачей поиска точки в пространстве с 8 измерениями (по 4 на каждую ногу). Давайте начнём создавать геном для одной ноги. Он будет храниться в структуре под названием GenomeLeg. Она оборачивает четыре необходимых параметра и предоставляет возможность оценивать представляемую ею синусоиду:

[System.Serializable]
public struct GenomeLeg
{
	public float m;
	public float M;
	public float o;
	public float p;

	public float EvaluateAt (float time)
	{
		return (M - m) / 2 * (1 + Mathf.Sin((time+o) * Mathf.PI * 2 / p)) + m;
	}
}

Теперь нам нужно обернуть две GenomeLeg в единую структуру, которая будет хранить весь геном:

[System.Serializable]
public struct Genome
{
	public GenomeLeg left;
	public GenomeLeg right;
}

На этом этапе у нас имеется полная структура, определяющая стратегию ходьбы существа. Это позволяет нам завершить класс Creature, который мы оставили в предыдущей части:

public class Creature
{
	public Genome genome;

	public LegController left;
	public LegController right;

	public void Update ()
	{
		left.position =  genome.left.EvaluateAt(Time.time);
		right.position = genome.right.EvaluateAt(Time.time);
	}
}

Клонирование

В самой основе эволюции лежит концепция передачи и мутации генома. Чтобы эволюция работала, нам нужно создать копии генома и применить к ним случайные мутации. Давайте начнём с добавления метода Clone к структуре GenomeLeg:

public GenomeLeg Clone ()
{
	GenomeLeg leg = new GenomeLeg();
	leg.m = m;
	leg.M = M;
	leg.o = o;
	leg.p = p;
	return leg;
}

А также к структуре Genome:

public Genome Clone ()
{
	Genome genome = new Genome();
	genome.left = left.Clone();
	genome.right = right.Clone();
	return genome;
}

Стоит заметить, что поскольку они являются мелкими структурами (shallow structs), то метод Clone не требуется. Структуры обрабатываются как примитивные типы: при передаче или назначении они всегда копируются.

Мутация

Самая интересная часть этого туториала — это, очевидно, мутации. Давайте начнём с простого: подвергнем мутации структуру Genome. Мы случайным образом выбираем ногу и применяем к ней мутацию:

public void Mutate ()
{
	if (	Random.Range(0f,1f) > 0.5f	)
		left.Mutate();
	else
		right.Mutate();
}

Теперь нам нужно взять геном ноги и применить случайную мутацию, которая потенциально может улучшить её приспособленность. Сделать это можно бесконечным количеством способов. Выбранный мной для туториала просто выбирает случайный параметр и изменяет его на небольшую величину:

public void Mutate ()
{
	switch (	Random.Range(0,3+1)	)
	{
		case 0:
			m += Random.Range(-0.1f, 0.1f);
			m = Mathf.Clamp(m, -1f, +1f);
			break;
		case 1:
			M += Random.Range(-0.1f, 0.1f);
			M = Mathf.Clamp(M, -1f, +1f);
			break;
		case 2:
			p +=Random.Range(-0.25f, 0.25f);
			p = Mathf.Clamp(p, 0.1f, 2f);
			break;
		case 3:
			o += Random.Range(-0.25f, 0.25f);
			o = Mathf.Clamp(o, -2f, 2f);
			break;
	}
}

Метод Mutate содержит множество магических чисел — констант, появившихся из ниоткуда. Хотя логично будет ограничить значения наших параметров, задавая объёмы мутации, но здесь это довольно неэффективно. Более разумным способом будет тонкая настройка параметров согласно тому, насколько мы близко к решению. Когда мы близки к цели, то нужно замедлиться, чтобы не перепрыгнуть нужное решение и не упустить его. Этот аспект, часто называемый адаптивной скоростью обучения, является важным этапом оптимизации, который в туториале рассматриваться не будет.

Стоит также заметить, что изменение значений на небольшие величины может также помешать нахождению более хорошего решения. Лучше выбрать подход, при котором случайным образом полностью заменяется один из параметров.

Заключение

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

В следующей части мы завершим посвящённый эволюции туториал, показав последний необходимый фрагмент: сам цикл эволюции.

Часть 4. Цикл.

Наше приключение по овладению мощью эволюции подходит к концу. В предыдущих трёх частях туториала мы создали двуногое тело и мутирующий геном, определяющий его поведение. Нам осталось только реализовать сами эволюционные вычисления, чтобы найти успешную стратегию ходьбы.

Цикл эволюции

Эволюция — итеративный процесс. Мы используем корутину, чтобы обеспечить продолжение такого цикла. Если вкратце, то мы начнём с определённого генома и создадим несколько мутировавших копий. Для каждой копии мы создадим экземпляр существа и протестируем его работу в симуляции. Затем мы возьмём геном наиболее успешного существа и повторим итерацию.

public int generations = 100;
public float simulationTime = 15f;

public IEnumerator Simulation ()
{
	for (int i = 0; i < generations; i ++)
	{
		CreateCreatures();
		StartSimulation();

		yield return new WaitForSeconds(simulationTime);

		StopSimulation();
		EvaluateScore();

		DestroyCreatures();

		yield return new WaitForSeconds(1);
	}
}

Симуляция

Для проверки успешности ходьбы существа нам нужно создать его тело и дать ему достаточно времени для движения. Чтобы упростить работу, давайте представим, что в игровой сцене есть достаточно длинный пол. Мы будем создавать экземпляры существ поверх него, на значительном расстоянии, чтобы они не влияли друг от друга. Представленный ниже код выполняет именно эту задачу, расставляя существ (хранящихся в префабах) на определённом расстоянии distance.

public int variations = 100;
private Genome bestGenome;

public Vector3 distance = new Vector3(50, 0, 0);
public GameObject prefab;
private List creatures = new List();

public void CreateCreatures ()
{
	for (int i = 0; i < variations; i ++)
	{
		// Выполняем мутирование генома
		Genome genome = bestGenome.Clone().Mutate();

		// Создаём экземпляр существа
		Vector3 position = Vector3.zero + distance * i;
		Creature creature = Instantiate(prefab, position, Quaternion.identity);

		creature.genome = genome;
		creatures.Add(creature);
	}
}

Функция CreateCreatures отслеживает всех созданных существ, чтобы ими можно было проще манипулировать. Чтобы улучшить управление, мы отключим в префабе существа скрипт Creature. Благодаря этому существо не будет двигаться. Тогда мы сможем запускать и останавливать симуляцию с помощью следующих функций.

public void StartSimulation ()
{
	foreach (Creature creature in creatures)
		creature.enabled = true;
}

public void StopSimulation ()
{
	foreach (Creature creature in creatures)
		creature.enabled = false;
}

public void DestroyCreatures ()
{
	foreach (Creature creature in creatures)
		Destroy(creature.gameObject);

	creatures.Clear();
}

Оценка приспособленности

Эволюция заключается в оценке приспособленности. После завершения симуляции мы обходим в цикле всех существ и получаем их конечную оценку. Мы отслеживаем наилучшее существо, чтобы можно было выполнить его мутацию в следующей итерации.

private float bestScore = 0;

public void EvaluateScore ()
{
	foreach (Creature creature in creatures)
	{
		float score = creature.GetScore();
		if (score > bestScore)
		{
			bestScore = score;
			bestGenome = creature.genome.Clone();
		}
	}
}

Улучшения

Внимательный читатель мог заметить, что описанная в этой статье техника зависит от нескольких параметров. А именно: generations, simulationTime и variations. Они представляют собой, соответственно, количество симулируемых поколений, длительность каждой симуляции и количество вариаций, создаваемых в каждом поколении. Однако ещё более внимательный читатель мог также заметить, что используемая стратегия отравлена подразумеваемыми предположениями. Они являются результатом слишком упрощённых выбранных характеристик конструкции, которые теперь становятся жёсткими ограничениями. Поэтому результаты программы, работающей один час, и программы, работающей месяц, будут различаться. В этом разделе я попытаюсь решить проблемы с некоторыми из этих ограничений, создав более разумные альтернативы, которые вы сможете реализовать самостоятельно.

Лучшие K геномов. Геномы, начинающие следующее поколение, являются лучшими из всех поколений. Это означает, что если текущее поколение не может улучшить приспособленность, то следующее поколение начнётся с того же генома. Очевидная ловушка здесь в том, что мы можем застрять в цикле, в котором один и тот же геном симулируется снова и снова, без каких-либо разумных улучшений. Возможным решением было бы всегда брать лучший геном из текущего прогона. Недостаток такого подхода в том, что приспособленность может снизиться, если ни одна из мутаций не принесёт улучшений. Более разумным подходом стал бы выбор лучших k геномов из каждого поколения, и использование их в качестве основы следующей итерации. Можно добавить немутировавший лучший геном предыдущего поколения, чтобы приспособленность не ухудшилась, однако имелась возможность и для поиска лучших решений.
Адаптивная скорость обучения. При каждой мутации генома мы изменяем только один параметр ноги и на определённую величину. Только мутации двигают нас по пространству параметров, в котором лежит наше решение. Скорость, с которой мы движемся, очень важна: если мы сдвинемся слишком далеко, то можем перепрыгнуть решение, но если двигаться слишком медленно, то мы можем не выбраться из локальных максимумов. Количество выполненных мутаций (скорость обучения) генома должна быть связана со скоростью, с которой улучшается оценка. В анимации ниже показано, насколько значительным может быть влияние различных стратегий на скорость схождения.

Раннее завершение. Легко увидеть, что некоторые симуляции заведут нас в тупик. Каждый раз, когда существо переворачивается на спину, то оно никак не сможет вернуться на ноги. Хороший алгоритм должен распознавать их и прерывать такие симуляции для экономии ресурсов.
Изменение функции приспособленности. Если то, чему вы хотите научиться, достаточно сложно, то возможно стоит делать это поэтапно. Это можно реализовать, постепенно меняя функцию приспособленности. Так мы сможем сосредоточить усилия по обучению на простой задаче.
Несколько проверок. Когда дело доходит до симуляции физики, то есть вероятность, что вы никогда не получите одного результата дважды. Есть хороший способ — создать несколько экземпляров существа с одним геномом в одних и тех же условиях, а потом усреднить их оценки, чтобы получить более надёжную оценку.

Заключение

В этом туториале мы познакомились с эволюционными вычислениями и разобрались с их работой. Эта тема невероятно широка, так что воспринимайте эту статью как общее введение.

Полный пакет Unity этого проекта можно скачать здесь.