Мы собираемся сделать что-то, что изначально казалось мне трудным. По формуле найдем формулу для ее неопределенного интеграла. В этом предыдущем посте я показал, что мы можем найти определенный интеграл от функции, используя случайный процесс, известный как Siumulation Монте-Карло. Поскольку мы можем найти значение определенного интеграла в любых точках, которые мы хотим, мы можем использовать другой метод, чтобы превратить эти данные в формулу. Техника, которую мы будем использовать, известна как генетический алгоритм.
Решение
Давайте начнем с просмотра интерактивной демонстрации и анализа того, как для меня сработала пара конкретных случаев. Нажмите здесь для демонстрации
Что такое генетический алгоритм?
Генетический алгоритм — это способ поиска довольно хорошего решения проблемы путем случайного угадывания решений и последующего объединения тех, которые добиваются наилучших результатов. Генетический алгоритм состоит из нескольких различных концепций.
- Генофонд — популяция программ.
- Хромосома — индивидуальная программа. В предыдущей статье я подробно изучил, как я их определяю и анализирую. Прочитайте это здесь .
- Мутация — процесс, посредством которого программа случайно изменяется.
- Разведение — Используемый процесс, который объединяет две или более программ в надежде создать новую хромосому, которая лучше подходит, чем любая из родительских хромосом.
- Пригодность — тест, выполненный на каждой хромосоме, чтобы определить, насколько хорошо это решение проблемы.
- Поколение — единая итерация селекции хромосом и фитнес-тестирования.
Представьте, что вы разводите собак, чтобы быть самыми агрессивными. У вас будет питомник (генофонд), заполненный множеством отдельных собак (хромосом). Самые агрессивные (определенные некоторыми критериями пригодности) вы размножаетесь вместе. Иногда один из щенков может родиться ЧРЕЗВЫЧАЙНО агрессивным … или пассивным из-за какой-то мутации. Как только вы достигнете желаемого уровня агрессии, все готово. Мы собираемся сделать то же самое.
Соединение концепций с нашей задачей
Мы начнем с популяции совершенно случайно сгенерированных математических формул. Мы ищем формулы, которые наиболее точно соответствуют интегралу другой функции, которая предусмотрена в нашем фитнес-тесте. Важно отметить, что формула, по которой мы тестируем фитнес, остается неизменной. В нашем случае формула, которую мы интегрируем, написана на Javascript. Затем мы будем использовать методы Монте-Карло, чтобы найти определенный интеграл в серии случайных точек, определенных нашим полным алгоритмом. Хромосомы, которые ближе всего подходят к правильным ответам, будут разведены вместе.
В какой-то момент процесса хромосомы очень часто начинают выглядеть очень похожими. По этой причине мы также реализуем мутации.
Как выглядит этот процесс?
Best score: 0.5309003809188878 Generation #0 Best score: 0.5309003809188878 Generation #1 Best score: 0.5309003809188878 Generation #2 Best score: 0.5309003809188878 Generation #3 Best score: 0.5309003809188878 Generation #4 Best score: 0.5309003809188878 Generation #5 Best score: 0.5309003809188878 Generation #6 Best score: 0.5309003809188878 Generation #7 Best score: 0.3806625060392219 Generation #8 Best score: 0.3806625060392219 Generation #9 Best score: 0.37563382661080047 Generation #10 Best score: 0.37563382661080047 Generation #11 Best score: 0.011973503793781733 Generation #12
Это я нашел неопределенный интеграл для греха (х). Это сходилось удивительно быстро. Первое поколение, его показатель пригодности был на уровне примерно .53, а первое поколение — ниже .13, программа остановилась. Оказывается, в первый раз, когда он опустился ниже, чем .13, он фактически получил .119. Цифры ничего не значат за исключением того, что они пошли вниз. Это все относительно.
Найденное решение (-672) — (cos (x))
Фактический ответ -cos (x) + c … Так что вы можете понять, что это совершенно верно. Константа -672 несущественна и может быть удалена. Всего за двенадцать поколений!
Алгоритмическая большая картина
Ниже приведен основной цикл программы. Он состоит из следующих частей по порядку:
- Произвольно генерируйте вопросы и соответствующие правильные ответы, которые будут использоваться для фитнес-теста.
- Начните повторять каждое поколение хромосом. В каждом поколении …
- Создайте столько случайных хромосом, сколько у нас есть места в генофонде.
- Проверьте пригодность каждого и сортируйте их от лучшего к худшему.
- Разведите каждую хромосому сразу после нее в порядке качества.
- Повторяйте до тех пор, пока хромосома не достигнет нашей целевой пригодности или пока мы не повторим максимальное количество поколений.
var main = function(data){
var gene_pool = [];
var winning_scores = null;
var questions = generate_questions(data.points_to_test_each_generation);
var correct_answers = generate_correct_answers(questions,
function(x){
return eval(data.javascript_formula_text);
});
for(var i=0; i<data.generation_count; i++){
var gene_pool = generate_random_chromosomes(gene_pool, data.genes_per_generation);
var gene_scoreboard = test_fitness(gene_pool, questions, correct_answers);
winning_scores = gene_scoreboard;//.slice(0, data.winners_per_generation);
postMessage("Best score: " + String(gene_scoreboard[0].score));
if(i > 5 && gene_scoreboard[0].score <= data.target_fitness){
postMessage(
{
'type':'great_find',
'value': gene_scoreboard.slice(0, data.winners_per_generation)
});
break;
}
var winning_genes = winning_scores.slice(0,data.genes_per_generation-30)
.map(
function(elem){
return elem.gene;
});
gene_pool = breed_with_next_best(
winning_genes,
data.mutation_chance,
data.max_constant,
data.winners_per_generation,
data.genes_per_generation);
}
postMessage({'type': 'final_result', 'value': winning_scores});
};
Стратегия разведения
Однажды я видел документальный фильм о том, как размножаются олени, газели или что-то еще. Давайте просто притворимся, что это был олень, так как я не могу найти реальную ссылку на эту детскую память. Самцы образуют ряд свободных колец вокруг альфа-самца, а самка оленя пытается добраться до самого внутреннего кольца, которое они могут. Конечно, все время олени также борются за то, чтобы подняться до пресловутого альфа-самца.
Я делаю что-то подобное здесь.
У меня есть массив, заполненный хромосомами, которые отсортированы по их показателям пригодности, сначала лучшим. Затем я делю каждую хромосому на следующую по качеству (следующую в массиве).
Фитнес-функция
Для фитнеса я нахожу интеграл маленьких сегментов кривой шириной в одну единицу. Я делаю это так, чтобы, когда я использую методы Монте-Карло, чтобы найти область под кривой, я могу сохранить плотность своих случайных точек, по крайней мере, несколько согласованной.
Я создаю 70 случайных точек х и нахожу интеграл в области х, х + 1. Я храню каждый из 70 вопросов в массиве и задаю каждую хромосому в каждой итерации, чтобы дать мне интеграл для каждого из 70 значений x.
Сначала я пытался придумать отдельный набор вопросов для каждого поколения, но обнаружил, что это делает процесс более нестабильным.
var test_fitness = function(chromosomes, fitness_questions, correct_answers){
var gene_pool = chromosomes;
var gene_scoreboard = [];
for(var gene_index=0; gene_index<gene_pool.length; gene_index++){
var gene = gene_pool[gene_index];
var chromosome = new Chromosome(gene);
var gene_answers = generate_gene_answers(fitness_questions, chromosome.evaluate);
var fitness_score = std_dev(correct_answers, gene_answers)/Math.sqrt(correct_answers.length-1);
if(!isNaN(fitness_score)){
gene_scoreboard.push({'gene':gene, 'score':fitness_score});
}
}
gene_scoreboard.sort(function(left, right){
if(isNaN(left.score)){
return 1;
}
if(isNaN(right.score)){
return -1;
}
return left.score < right.score
? -1
: left.score > right.score
? 1
: 0;
});
return gene_scoreboard;
};
Here we use the standard error as a fitness function. Initially I happened upon using the distance formula, but then I found it changing as I added more test points. To account for this I began dividing by the number of test points but then realized it was super close to just using the standard error and thought I’d just do that instead.
Here’s my standard deviation implementation:
var std_dev = function(left_answers, right_answers){
var squared_differences = [];
for(var i=0; i < left_answers.length; i++){
var left = left_answers[i];
var right = right_answers[i];
var squared_difference = Math.pow(left-right,2);
squared_differences.push(squared_difference);
}
var sum = squared_differences.reduce(function(a, b) { return a + b; }, 0);
return Math.sqrt(sum);
};
Solutions as Chromosomes
I talked in my previous post on Genetic Algorithms on everything that goes into encoding mathical formulae as chromosomes. You can refer to it here.
Here is how I generate random chromosomes:
var randomize = function(max_length, max_constant){
var chromosome_components = [];
var chromosome_definition = [
'*','/','+','-','n','x','q','s','c','t','^','l'
];
var random_length = Math.floor(Math.random() * max_length);
for(var i = 0; i<random_length; i++){
var chromosome_sequence = Math.floor(Math.random() * chromosome_definition.length);
var random_sequence = chromosome_definition[chromosome_sequence];
if(random_sequence == 'n'){
random_sequence += String(Math.floor(Math.random() * 2*max_constant)-max_constant);
}
chromosome_components.push(random_sequence);
}
return chromosome_components.join('');
};
Each character in the chromosome definition list represents one of the possible operators in the chromosome grammar I’ve created.
Breeding Solutions
When breeding the solutions I use a method that chooses a random mid-point on the two chromosomes being bred and swaps the segments divided by the midpoint. It thus creates two “children” chromosomes.
var breed_with_next_best = function(genes, mutation_chance, max_constant, winners_to_keep, max_population){
var previous_winners = genes.slice(0, winners_to_keep);
var babies = previous_winners;
var second_to_last_gene_index = genes.length-2;
for(var gene_index=0; gene_index <= second_to_last_gene_index; gene_index++){
var better_gene = genes[gene_index];
var worse_gene = genes[gene_index + 1];
var baby_genes = breed_by_gene_swap(better_gene, worse_gene);
babies.push(baby_genes[0]);
babies.push(baby_genes[1]);
}
var chromosome_factory = new Chromosome('');
return babies.slice(0, max_population).map(function(elem){
var mutated_chromosome = chromosome_factory.mutate(elem, mutation_chance, max_constant);
return mutated_chromosome;
});
};
Mutating Solutions
After breeding occurs I run all of the chromosomes through a mutation process that affects X% of the chromosomes. If a chromsome is selected for mutation there are one of four strategies that may be applied to it.
Once the program decides whether or not a mutation will occur, it decides how many mutations to apply with a maximum of 15. The number 15 is a limit I picked arbitrarily. Here’s the code that handles the mutation logic.
var token_map = {
'*': {'type':'two_term_operator', 'value':'*'},
'/': {'type':'two_term_operator', 'value':'/'},
'+': {'type':'two_term_operator', 'value':'+'},
'-': {'type':'two_term_operator', 'value':'-'},
'^': {'type':'two_term_operator', 'value':'^'},
'n': {'type': 'constant', 'value':null},
'x': {'type': 'input_constant', 'value':'x'},
'q': {'type': 'one_term_operator', 'value':'q'},
'l': {'type': 'one_term_operator', 'value':'l'},
's': {'type': 'one_term_operator', 'value':'s'},
'c': {'type': 'one_term_operator', 'value':'c'},
't': {'type': 'one_term_operator', 'value':'t'},
};
var get_values = function(dictionary){
var values = Object.keys(dictionary).map(function(key){
return dictionary[key];
});
return values;
};
var stringify = function(tokens){
var text = '';
for(var token_index in tokens){
var token = tokens[token_index];
if(token.type === 'constant'){
if(isNaN(token.value)){
text = 'n' + text;
}else{
text = 'n' + String(token.value) + text;
}
} else {
text = String(token.value) + text;
}
}
return text;
};
var get_mutation_choice = function(max_constant){
var mutation_choices = get_values(token_map);
var mutation_chosen = mutation_choices[Math.floor(Math.random() * (mutation_choices.length))];
if(mutation_chosen.type === 'constant'){
mutation_chosen.value = Math.floor(Math.random() * 2*max_constant)-max_constant;
}
return mutation_chosen;
};
var mutate = function(chromosome, chance, max_constant){
var do_mutation = (chance >= Math.random());
if(do_mutation){
var tokens = lex_this(chromosome);
var mutations_to_insert = Math.floor(Math.random()*15 + 1);
var mutation_decider = Math.random();
if( mutation_decider < .25){
for(var mutation_index=0; mutation_index<mutations_to_insert; mutation_index++){
var mutation_chosen = get_mutation_choice(max_constant);
var index_to_mutate = Math.floor(Math.random() * (tokens.length));
tokens[index_to_mutate] = mutation_chosen;
}
} else if(mutation_decider < .5) {
for(var mutation_index=0; mutation_index<mutations_to_insert; mutation_index++){
var mutation_chosen = get_mutation_choice(max_constant);
tokens.push(mutation_chosen);
}
} else if(mutation_decider < .75) {
for(var mutation_index=0; mutation_index<mutations_to_insert; mutation_index++){
var mutation_chosen = get_mutation_choice(max_constant);
tokens.unshift(mutation_chosen);
}
} else {
for(var mutation_index=0; mutation_index<mutations_to_insert; mutation_index++){
if(tokens.length > 1){
var index_to_mutate = Math.floor(Math.random() * (tokens.length));
tokens.splice(index_to_mutate, 1);
}
}
}
var new_chromosome = stringify(tokens);
return new_chromosome;
} else{
return chromosome.slice(0,50);
}
};
The Demo
Well if you’ve made it this far and you haven’t checked out the demo yet you can play with it here: Click here for the demo
Open Challenges
Given more complex formulae the algorithm tends to prematurely converge on local optima. There are techniques to handle this such as using hamming distance to dictate mutations to be more or less likely and thus keep genetic diversity high.
Beyond that, I had to use Web Workers so that the page would be responsive while processing the algorithm. With a little more work, I bet one could run a couple of simulations in parallel at a minimal extra overhead cost and cross breed the highest quality chromosomes from each simulation.
Currently my breeding implementation is fairly simplistic. There are several different techniques which exist that might make this process work better. The technique I’m using is somewhat of an “elitist” solution which can cause rapid convergence because it focuses on breeding the best with the best. It can however also lead to converging prematurely into local optima like I’m experiencing. It might be smart to do some sort of randomized elitism. Perhaps just let the fitness score influence the randomness of the mate pairings.
Any questions or thoughts make sure to hit me up on one of the contact options in the upper left of this page.
Thank you for reading!
(Note: This article and the opinions expressed are solely my own and do not represent those of my employer.)