Нажмите на живой пример того, что я буду освещать
Что такое генетические алгоритмы? (Рассмотрение)
Хромосома : исполняемый код.
Функция пригодности : количественно определяет качество исполняемого кода.
Мутации : вносит случайные новые изменения в код. Иногда это ужасно, иногда блестяще.
Разведение : помогает алгоритму итеративно улучшить хромосому в направлении более правильного решения.
Поколение : заданная итерация N хромосом. Борьба за выживание происходит в каждом поколении.
Весь смысл генетического алгоритма состоит в том, чтобы разработать набор хромосом, проверяющих их на соответствие определенной функции пригодности в надежде найти хромосому с достаточно хорошим решением.
Проблема, которую я решаю
Я хочу написать алгоритм, который может интегрировать данную математическую функцию. Не определенный интеграл. Я уже написал статью о том, как этого добиться с помощью симуляции Монте-Карло. Нет, я имею в виду, что мой алгоритм придумал новую функцию, которая является хорошим приближенным неопределенным интегралом для представленного уравнения. Если вы знакомы с неопределенными интегралами и всеми особыми случаями и методами, вы поймете, насколько это сложно.
Как я планирую заняться этим с помощью генетических алгоритмов? Ключ лежит в фитнес-функции. Я планирую использовать определенный интегральный калькулятор Монте-Карло из моего предыдущего поста, чтобы оценивать хромосомы, которые развиваются. Пользуясь этим, я надеюсь, что в конечном итоге хромосома случится либо в большом приближении, либо в точном правильном решении.
Я никогда не пробовал это раньше, и я также не смог найти статьи о других, пытающихся это сделать. Так что либо это интересный, хотя бы несколько новаторский подход, либо … это ужасная УЖАСНАЯ идея. ?
Сосредоточение внимания на хромосомах
Эта работа была намного больше работы, чем я планировал. Кажется, стоит рассмотреть только одну часть в этой статье, а остальную часть — в следующей. Это означает, что эта статья будет посвящена лексизированию и синтаксическому анализу хромосомы для построения так называемого абстрактного синтаксического дерева, которое можно использовать для оценки хромосомы при заданных значениях «x».
Давным-давно я выучил интересную технику кодирования математической формулы в хромосомы. Это в основном требует, чтобы вы выписали формулу слева направо в виде строки, используя отдельные буквы для различных математических операторов. Я добавил небольшой твик, чтобы позволить мне вставлять произвольные числа в хромосомы. Вот несколько простых примеров и их математический перевод:
- «N0» -> 0
- «+ N1n2.1» -> 1 + 2,1
- ”+ N4qn5n11” -> 4 + (5 кв. (11))
Для последнего примера это может помочь узнать, что означают буквы. Вы, возможно, догадались, что любое число, которому предшествует «n», является константой. + и * представляют сложение и умножение соответственно. Так что же такое «д»? «Q» представляет квадратный корень числа.
Вот полный набор определений:
q = sqrt(x)
+ = addition
- = subtraction
/ = division
* = multiplication
s = sin(x)
c = cos(x)
t = tan(x)
^ = pow(x,y)
n[0-9]+ = [0-9]+
x = input value
Что за х? Вот как я планирую сделать формулу, сгенерированную алгоритмом, функцией общего пользования. Например:
- «^ X2» -> x ^ 2
- «+ N2q + ^ n1xn2» -> 2 + sqrt (x ^ 2 + 1)
Поэтому, когда я оцениваю первую хромосому в 2, я должен получить 4. Оценка второй в 2 должна получить 4,236. Вы можете перейти к живому примеру здесь: Нажмите здесь, чтобы открыть пример
Как оценить хромосомы
Существуют разные способы анализа таких хромосом. Мой способ — читать их справа налево. Давайте начнем с простого примера:
*+-n1n2n3n4
шаги:
- Я вижу константу со значением 4. Я запишу это на блокноте:
1. Блокнот: 4 - Есть константа 3. Записать это 1. Блокнот: 4,3
- Там константа 2.
1. Скретч-площадка: 4,3,2 - Наконец, последняя константа, номер 1.
1. Скретч-панель: 4,3,2,1 - Я добираюсь до моего первого оператора. Это вычитание, и оно занимает два срока. Левый термин и правый термин. Я беру первые два термина, которые я нашел (константы 4 и 3), и делаю математику. 3-4 это -1.
1. Блокнот: 2,1, -1 - Следующий оператор, которого я ударил — это сложение. Я беру следующие два условия и добавляю их, чтобы получить 1 + 2 = 3
1. Блокнот: -1,3 - Наконец я остался с последним оператором. Я умножаю -1 и 3 и получаю -3 в качестве ответа.
Я не буду лгать: это не самый простой и простой расчет. При создании моего парсера я несколько раз сталкивался с проблемами, связанными с собственным недоразумением.
Имея это в виду, давайте начнем наше обсуждение того, что связано с анализом и выполнением простого куска кода.
Шаги к разбору
- Лексинг — это то, где мы определяем, как сгруппировать наши символы строки в «слова». Например, в приведенном выше примере «n1» на самом деле просто представляет число 1. После выделения текста текст «n1» превратится в небольшой объект, который будет иметь некоторые метаданные, которые представляют собой значение и значение.
- Парсинг — это то место, где мы берем вывод из нашего лексического анализа и формируем его в исполняемое дерево.
- Оценка — здесь у нас есть дерево, и мы можем рекурсивно вызвать какую-то функцию оценки в корневом узле, чтобы получить результат.
лексический
При лексизме мы проходим нашу входную строку символ за символом и просто группируем связанные биты, если это помогает нам делать нашу работу. В этом случае я просто хотел бы классифицировать разницу между операторами, константами и входными константами. Я также хотел бы сгруппировать все символы констант в один токен, чтобы облегчить жизнь, когда я доберусь до стадии разбора.
Вот весь мой лексер:
var lex_this = function(chromosome){
var tokens = [];
chromosome = chromosome.split('').slice(0);
var buffer = '';
for(var index=chromosome.length-1; index >= 0; index--){
var character = chromosome[index];
console.log(character);
switch(character){
case '*':
tokens.push({'type':'operator', 'value':'*'});
break;
case '/':
tokens.push({'type':'operator', 'value':'/'});
break;
case '+':
tokens.push({'type':'operator', 'value':'+'});
break;
case '-':
tokens.push({'type':'operator', 'value':'-'});
break;
case 'n':
tokens.push({'type': 'constant', 'value':parseFloat(buffer)});
buffer = '';
break;
case 'x':
tokens.push({'type': 'input_constant'});
break;
case 'q':
tokens.push({'type': 'operator', 'value':'q'});
break;
case 's':
tokens.push({'type': 'operator', 'value':'s'});
break;
case 'c':
tokens.push({'type': 'operator', 'value':'c'});
break;
case 't':
tokens.push({'type': 'operator', 'value':'t'});
break;
case '^':
tokens.push({'type': 'operator', 'value':'^'});
break;
default:
var constant_pattern=/[0-9\.]/
if(constant_pattern.test(character)){
buffer = character + buffer;
console.log('Buffer is now: ' + buffer);
} else {
throw 'Unexpected value of ' + character;
}
break;
}
}
return tokens;
};
Вы можете заметить, что я повторяю это в обратном порядке. Это было легче для меня лично. Если вы хотите попробовать это с противоположной стороны, это полностью верно.
Ключом к этому является то, что вы идете от персонажа к персонажу и выводите все, что вам легко на текущем уровне абстракции. В более сложных задачах вы можете даже ввести еще одну фазу типа лексера перед тем, как перейти к своему анализатору только потому, что вам проще перебирать свой список токенов.
анализ
Теперь, когда для каждой концепции есть токен (оператор, константа, входная константа), будет проще создать дерево из этой информации.
Все в моем списке определений должно быть оцениваемым узлом в моем дереве. Даже константы. Преобразовав все в узел, я могу установить непротиворечивый интерфейс для их оценки и использовать полиморфизм для обработки конкретных деталей для каждого из них.
Вот полный код парсера:
var parse_these = function(tokens){
tokens = tokens.slice(0);
var nodes_to_assemble = [];
for(var index in tokens){
var token = tokens[index];
switch(token.type){
case 'operator':
switch(token.value){
case '+':
var right_term = nodes_to_assemble.shift();
var left_term = nodes_to_assemble.shift();
var operator_node = new AdditionOperatorNode(left_term, right_term);
nodes_to_assemble.push(operator_node);
break;
case '-':
var right_term = nodes_to_assemble.shift();
var left_term = nodes_to_assemble.shift();
var operator_node = new SubtractionOperatorNode(left_term, right_term);
nodes_to_assemble.push(operator_node);
break;
case '*':
var right_term = nodes_to_assemble.shift();
var left_term = nodes_to_assemble.shift();
var operator_node = new MultiplicationOperatorNode(left_term, right_term);
nodes_to_assemble.push(operator_node);
break;
case '/':
var right_term = nodes_to_assemble.shift();
var left_term = nodes_to_assemble.shift();
var operator_node = new DivisionOperatorNode(left_term, right_term);
nodes_to_assemble.push(operator_node);
break;
case '^':
var right_term = nodes_to_assemble.shift();
var left_term = nodes_to_assemble.shift();
var operator_node = new PowerOperatorNode(left_term, right_term);
nodes_to_assemble.push(operator_node);
break;
case 'q':
var term = nodes_to_assemble.shift();
var operator_node = new SquareRootOperatorNode(term);
nodes_to_assemble.push(operator_node);
break;
case 's':
var term = nodes_to_assemble.shift();
var operator_node = new SineOperatorNode(term);
nodes_to_assemble.push(operator_node);
break;
case 'c':
var term = nodes_to_assemble.shift();
var operator_node = new CosineOperatorNode(term);
nodes_to_assemble.push(operator_node);
break;
case 't':
var term = nodes_to_assemble.shift();
var operator_node = new TangentOperatorNode(term);
nodes_to_assemble.push(operator_node);
break;
}
break;
case 'constant':
var constant = new ConstantTermNode(token.value);
nodes_to_assemble.push(constant);
break;
case 'input_constant':
var input_constant = new InputConstantTermNode();
nodes_to_assemble.push(input_constant);
break;
default:
throw 'Unexpected token type ' + token.type;
break;
}
}
if(nodes_to_assemble.length > 1){
throw 'Invalid AST. Ambiguous root node';
}
return nodes_to_assemble[0];
};
Опять же, я просто работаю один за другим, но на этот раз над моими жетонами вместо символов из строки. Обратите внимание, что я использую тип узла в цикле, чтобы сгруппировать операторы, константы и входные константы вместе. Я мог бы добавить немного больше информации об операторах, чтобы позволить мне повторно использовать код среди двух моих операторов термина. Также обратите внимание, как я просто нахожу термины, бросаю их в очередь, а затем использую их для создания новых терминов по ходу дела? Это тот же процесс, что и в 7 шагах, описанных выше, но вместо «блокнота» у меня есть список «node_to_assemble». Javascript поставляется с поддерживаемыми очередями. Я могу нажать на массив, а затем использовать функцию сдвига, чтобы получить первый элемент в массиве и удалить из него. Это делает так, что когда я сталкиваюсь с оператором, который хочет два термина, я просто вызываю shift () дважды и использую результаты для создания нового узла.После создания нового узла я просто помещаю его обратно в очередь. Оттуда наш новый узел будет обрабатываться так же, как и константы, и втягиваться в какой-то другой узел для оценки.
Здесь также есть несколько особых случаев. Что произойдет, если мы столкнемся с токеном, который говорит нам создать узел с двумя терминами операторов, но когда мы сдвигаемся, в списке только один узел (или, что еще хуже, ни один)? Я еще не добавил специальную обработку для этого, но это означало бы, что наша хромосома была неправильно отформатирована. Поскольку мы будем случайным образом генерировать хромосомы, мы захотим сделать наше дерево устойчивым к ошибкам, но я сохраню это на потом.
Другой особый случай — когда в нашем списке node_to_assemble больше не осталось токенов и остался только один узел. Это на самом деле то, что мы хотим. Это значит, что мы полностью закончили и наше дерево создано. Мы возвращаем этот последний узел в качестве корневого узла нашего дерева и называем его днем.
Оценка
Вот быстрый пример нескольких разных узлов, которые я создал. Посмотрите, что похоже, а что отличается.
var SquareRootOperatorNode = function(node){
return {
'evaluate': function(input_constant){
return Math.sqrt(node.evaluate(input_constant));
}
}
};
var SineOperatorNode = function(node){
return {
'evaluate': function(input_constant){
return Math.sin(node.evaluate(input_constant));
}
}
};
var CosineOperatorNode = function(node){
return {
'evaluate': function(input_constant){
return Math.cos(node.evaluate(input_constant));
}
}
};
var TangentOperatorNode = function(node){
return {
'evaluate': function(input_constant){
return Math.tan(node.evaluate(input_constant));
}
}
};
var ConstantTermNode = function(constant_value){
return {
'evaluate': function(input_constant){
return constant_value;
}
};
};
var InputConstantTermNode = function(){
return {
'evaluate': function(input_constant){
return input_constant;
}
}
};
Так. Сходства? Каждый узел имеет функцию «оценки», которая принимает один параметр, называемый «входной константой». Почему это? Ну, так как мы не будем знать, что является входной константой, до времени выполнения И мы не будем знать, нуждается ли лист нашего дерева в предоставленной ему входной константе, проще просто передать входную константу всем. Представьте, что у нас есть SquareRootOperatorNode. Если бы мы сделали так, чтобы константы вызывались по-другому, нам нужно было бы проверить, ЕСЛИ данный узел был константой, и тогда оператору потребовалась бы специальная обработка для него. Таким образом, оператор может просто передать «input_constant» и не знать, действительно ли используется значение.
Примечание: все высказанные здесь мнения принадлежат мне, а не моему работодателю.