Развитие деревьев выражений

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

Сущность генетического программирования

Перед тем как начать писать код, который делает код лучше, если его переписать, давайте начнем с определения того, что такое генетическое программирование. Генетическое программирование – это техника, которая использует идеи и операции из теории эволюции для создания новых программ на основе существующих. Генетический алгоритм (GA) представляет собой более общую версию генетического программирования. Вы создаете пул программ, или популяцию, которая меняется через итеративный подход. На каждом этапе процесса вы оцениваете и/или меняете членов популяции, основываясь на различных правилах и условиях. Если программа в популяции (называемая хромосомой) соответствует каким-то приемлемым критериям, процесс останавливается и эта хромосома выбирается в качестве ответа.

Совет

Есть огромное количество информации о генетическом программировании. Мы рекомендуем начать с веб-сайта Джона Коза: www.genetic-programming.com. Коза считается пионером в мире генетического программирования. Проблема из раздела 6.4 основана на одном из первых «набегов» Коза в генетическое программирование. Он использовал Lisp, а мы используем выражения в .NET.

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

Рисунок 6-6: Входные и выходные данные функции. Имейте в виду, что вы не знаете, что представляет собой функция.

Глядя на данные на рисунке 6-6, вы можете понять, что основная функция является такой:

f(x) = x ^ 3

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

Популяция

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

f(x) = x ^ 2
f(x) = x + 3
f(x) = (x ^ 3) + 1
f(x) = 3 * x

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

Выбор

Теперь, когда у вас есть популяция хромосом, вам нужно найти те, которые подходят. Чтобы определить, что такое "подходят", нужно создать функцию соответствия, которая дает очки данной хромосоме. Определение функции соответствия полностью зависит от вас, но хорошим показателем является то, насколько хорошо хромосома решает данную проблему. В данном случае мы будем использовать среднеквадратическую ошибку (СКО, mean-squared error, MSE), чтобы определить, подходит ли функция. Чем меньше ошибка, тем лучше функция соответствует заданному набору данных.

Примечание

Более подробную информацию о СКО (MSE) смотрите на http://mng.bz/x12Q и http://en.wikipedia.org/wiki/Mean_squared_error.

Рисунок 6-7 демонстрирует среднее СКО для каждой из четырех функций в популяции и индикатор, который показывает, какие функции были выбраны для следующей операции.

Рисунок 6-7: Выбор функций в генетическом программировании. Вы хотите выбрать хороших кандидатов, но вы не всегда будете выбирать самых лучших.

Вы можете удивиться, почему не был выбран третий вариант, потому что это явно лучший выбор. В генетическом программировании существуют различные методы, чтобы выбрать "лучшую" хромосому (например, турнир и рулетка), но все методы имеют встроенную степень случайности. Поэтому при случайном выборе вы можете не получить то, что кажется лучшим выбором. Однако эта случайность сохраняет генофонд (так сказать) динамическим. Как вы увидите в следующем разделе, из некоторых «не-таких-хороших» хромосом можно сделать что-то хорошее.

Кроссовер

После выбора хромосом вы будете определять (по рандомному шансу), будете ли вы выполнять кроссовер для хромосом. Это означает, что вы возьмете часть (или части) одной хромосомы и обменяете их на часть (или части) другой. Рисунок 6-8 показывает, что произойдет, когда вы поменяете постоянные узлы между выбранными функциями.

Рисунок 6-8: Выполнение кроссовера для двух функций. Обратите внимание, как изменилась первая функция и насколько «лучше» она стала.

Иногда кроссовер может привести к более эффективным решениям, а иногда может сделать хуже. Как вы видите на рисунке 6-8, первая функция теперь идеально сочетается с набором данных, с которым вы начали. Но вы еще не закончили: есть еще одна операция, которая может смешать новый материал.

Мутация

После кроссовера вы сможете выполнить мутацию данной хромосомы. Обычно вероятность мутации в GA является низкой, но таким образом можно оставить популяцию динамической. Мутация может быть хорошей или плохой вещью для хромосомы – вы никогда этого не знаете. Рисунок 6-9 показывает, как выглядит четвертая функция, после того как произошел кроссовер, и постоянное значение поменялось на совершенно новую операцию.

Рисунок 6-9: Результаты мутации функции. Константа была заменена полностью новым поддеревом.

Это "лучше" или "хуже"? Мы оставим этот расчет для заинтересованного читателя. Дело в том, что теперь у вас есть новый генетический материал в популяции, который может (или не может) что-то улучшить.

Итерация

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

  • Вы найти хромосому, которая превышает некое пороговое значение (например, СКО составляет меньше 0.5 процентов).
  • Вы превысили максимальное число итераций, указанных в начале запуска.

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

Теперь, когда вы знаете, как работают GA , давайте посмотрим, как вы можете сделать это в .NET при помощи деревьев выражений.

Применение GA к выражениям

Одно дело видеть, как работают GA, на рисунках. Но заставить их работать и видеть результаты – это весело. В данном разделе вы увидите, как выбрать выражения, чтобы они нашли функцию, соответствующую данному набору данных. Чтобы сделать это, вы получите фрагменты кода для программы, которую мы написали (ExpressionEvolver), она включена в онлайн код. Кодовая база является очень обширной, поэтому мы сосредоточимся на аспектах, которые имеют дело с операторами GA и .NET выражениями. Давайте начнем с того, как можно создать случайные выражения в .NET.

Создание рандомных выражений

Первая часть кода, которую вы увидите – это класс (RandomExpressionGenerator), который управляет созданием выражений. Это необходимо при создании начальной популяции или когда происходит мутация. В этом примере вы будете придерживаться основных математических операций, определенных в перечислении Operators:

private enum Operators
{
	Add,
	Subtract,
	Multiply,
	Divide,
	Power
}

Вы также должны быть в состоянии создать постоянные значения, и это обрабатывается в методе GetConstant():

private ConstantExpression GetConstant()
{
	var value = this.Random.NextDouble() * this.ConstantLimit;
	var constant = value * (this.Random.NextBoolean() ? -1d : 1d);
	return Expression.Constant(constant);
}

Значение свойства ConstantLimit передается конструктору – так лучше всего ограничить размер постоянных значений, созданных во время запуска GA.

Создание случайных выражений немного запутанное. Это делается при помощи метода GetRandomOperation(), как показано в следующем листинге.

Листинг 6-6: Создание рандомной операции
private void GetRandomOperation(Operators @operator)
{
	var isLeftConstant = this.Random.NextDouble() <
		this.InjectConstantProbabilityValue;
	var isRightConstant = this.Random.NextDouble() <
		this.InjectConstantProbabilityValue;
	var isLeftBody = true;
	var isRightBody = true;
	if(!isLeftConstant && !isRightConstant)
	{
		isLeftBody = this.Random.NextDouble() < 0.5;
		isRightBody = !isLeftBody;
	}
	else if(isLeftConstant && isRightConstant)
	{
		isLeftConstant = this.Random.NextDouble() <
	this.InjectConstantProbabilityValue;
		isRightConstant = !isLeftConstant;
	}
	else if(@operator == Operators.Divide &&
		!isLeftConstant && !isRightConstant)
	{
		isLeftConstant = this.Random.NextBoolean();
		isRightConstant = !isLeftConstant;
	}
	this.Body = RandomExpressionGenerator.GetExpressionFunction(
		@operator)(
		isLeftConstant ? this.GetConstant() :
	(isLeftBody ? this.Body : this.Parameter),
		isRightConstant ? this.GetConstant() :
	(isRightBody ? this.Body : this.Parameter));
}

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

private static Func<Expression, Expression, Expression>
	GetExpressionFunction(Operators @operator)
{
	Func<Expression, Expression, Expression> selectedOperation = null;
	switch(@operator)
	{
		case Operators.Add:
			selectedOperation = Expression.Add;
			break;
		case Operators.Subtract:
			selectedOperation = Expression.Subtract;
			break;
		case Operators.Multiply:
			selectedOperation = Expression.Multiply;
			break;
		case Operators.Divide:
			selectedOperation = Expression.Divide;
			break;
		case Operators.Power:
			selectedOperation = Expression.Power;
			break;
		default:
			throw new NotSupportedException(
			string.Format(CultureInfo.CurrentCulture,
			"Unexpected operator type: {0}", @operator));
	}
	return selectedOperation;
}

Чтобы создать случайное выражение, вызывается метод GetRandomOperation() в цикле for, который выстраивает свойство Body до нужного размера для дерева выражений:

private void GenerateBody(int maximumOperationCount)
{
	for(var i = 0; i < maximumOperationCount; i++)
	{
		this.GetRandomOperation(
		(Operators)this.Random.Next((int)Operators.Power + 1));
	}
}

Вот как вы будете использовать RandomExpressionGenerator для создания случайного выражения:

var parameter = Expression.Parameter(typeof(double), "a");
var body = new RandomExpressionGenerator(10,
	0.5, 100d, parameter, new SecureRandom()).Body.Compress();

Теперь вы знаете, как генерировать случайные выражения в. NET. Давайте перейдем к функции кроссовера в GA и посмотрим, как использовать класс ExpressionVisitor для обработки этого.

Обработка кроссовера при помощи выражений

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

public Expression Transform(Expression source,
	ReadOnlyCollection<ParameterExpression> sourceParameters,
	Expression find, Expression replacement)
{
	this.Find = find;
	if(sourceParameters != null)
	{
		this.Replacement = new ParameterReplacementVisitor()
		.Transform(sourceParameters, replacement);
	}
	else
	{
		this.Replacement = replacement;
	}
	return this.Visit(source);
}

Вы должны иметь в виду, что когда вы меняете компоненты между выражениями, вы не можете поменять параметры. Если вы переместите узел ParameterExpression из одного выражения в другое, вы получите исключение, если попытаетесь использовать это новое выражение. Вот почему используется класс ParameterReplacementVisitor. Это вложенный класс от ReplacementVisitor, и он меняет параметры в целевом узле заданными исходными параметрами.

ReplacementVisitor переписывает VisitBinary(), VisitConstant() и VisitParameter(), каждый из которых вызывает ReplaceNode(), который определяет, будет ли происходить замена:

private Expression ReplaceNode(Expression node)
{
	if(node == this.Find)
	{
		return this.Replacement;
	}
	else
	{
		return node;
	}
}

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

Генерация набора данных

Когда вы выделяете выражения, вам необходим набор данных, который GA может использовать в качестве своей цели. Но никто не любит создавать набор данных вручную. Лучше разобрать (отпарсить) выражение в строку следующим образом:

"a => a + 3 * Math.Pow(a, 2.5)"

Как только у вас есть лямбда-выражение, вы можете скомпилировать его и давать ему случайные входные значения, схватывая результаты в процессе. Тогда у вас будет набор данных, который вы могли бы дать GA. К сожалению, нет никакой функциональности по парсингу в System.Linq.Expressions, но парсер уже существует с компилятором C#!

В ExpressionEvolver есть проект под названием ExpressionBaker. Он содержит класс с именем Baker (примечание, Baker – пекарь), который принимает строку и "выпекает" ее, так что создается выражение. Это делается в методе Bake():

public Expression<TDelegate> Bake()
{
	var name = string.Format(CultureInfo.CurrentCulture,
		BakerConstants.Name, Guid.NewGuid().ToString("N"));
	var cscFileName = name + ".cs";
	File.WriteAllText(cscFileName,
		string.Format(CultureInfo.CurrentCulture,
		BakerConstants.Program, name, this.GetDelegateType(),
		this.Expression));
	this.CreateAssembly(name, cscFileName);
	return Assembly.LoadFrom(name + ".dll").GetType(name)
		.GetField("func").GetValue(null) as Expression<TDelegate>;
}

Этот метод принимает заданное выражение (сохраненное в свойстве Expression) и помещает его в файл .cs, который содержит код, выглядящий следующим образом:

public const string Program =
	@"using System;using System.Linq.Expressions;
	public static class {0}{{
	public static readonly Expression<{1}> func = {2};}}";

Как только файл будет сохранен на диск, CreateAssembly() создаст новую DLL через C# компилятор:

private void CreateAssembly(string name, string cscFileName)
{
	var startInformation = new ProcessStartInfo("csc");
	startInformation.CreateNoWindow = true;
	startInformation.Arguments = string.Format(
		CultureInfo.CurrentCulture,
		BakerConstants.CscArguments, name, cscFileName);
	startInformation.RedirectStandardOutput = true;
	startInformation.UseShellExecute = false;
	var csc = Process.Start(startInformation);
	csc.WaitForExit();
}

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

Примечание

Правда, хотя класс Baker обеспечивает функциональность, необходимую для компиляции выражения во время выполнения, он неуклюж и «попахивает» хакерством. В главе 10 вы увидите, как Project Roslyn делает компилятор легко доступным во время выполнения. Вы можете вернуться к этому разделу и переписать класс Baker, используя API компилятора Project Roslyn, как только вы закончите с главой 10.

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

Запуск кода

Теперь все на месте. Мутация выражений, разбор выражений и так далее. Пришло время запустить приложение. Рисунок 6-10 показывает, как приложение выглядит, когда оно запущено. Вы можете увидеть две строки: одна является целью, а вторая – это самое лучшее по развитию выражение в текущей генерации.

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

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

Сокращение выражений

Один артефакт использования древовидной структуры в GA – это «раздутие» (bloat). «Раздутие» возникает тогда, когда деревья начинают бесконтрольно расти во время процесса развития. Это то, что мы видели в ExpressionEvolver. Например, из начального набора данных, который был создан из этого выражения

a => (2 * Math.Pow(a, 4)) - (11 * Math.Pow(a, 3)) -
	(6 * Math.Pow(a, 2)) + (64 * a) + 32

был получен следующий приемлемый результат:

a => (((((-1 * a) - a) * ((-1 * a) - a)) *
	(((-1 * a) - a) - a)) +
	(((((-1 * a) - a) * (-1 * a)) *
	(-1 * a)) * (-1 * a)))

Хотя графики схожи, выражения не выглядят одинаково, пока вы сделаете некоторое символьное сокращение результата:

a => (2 * Math.Pow(a, 4)) - (12 * Math.Pow(a, 3))

Наличие более маленького выражения может помочь снизить потребление памяти, которое мы видели во время выполнения ExpressionEvolver.

В классе Expression есть метод Reduce(), но он не имеет ничего общего с математической символьной редукцией. Было бы неплохо, если бы существовала библиотека, чтобы делать такую редукцию для .NET выражений. Наиболее близкой, которую мы нашли, является WolframAlpha (http://alpha.wolfram.com), и ее мы использовали для сокращения предыдущего результата. Но хотя API доступен, нахождение результата потребует вызова веб сервиса. Это не так уж плохо, но мы должны быть осторожны, чтобы не сократить каждое выражение после каждой генерации. Наличие движка «в процессе» было бы лучшим вариантом.

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

или RSS канал: Что новенького на smarly.net