Что такое грамматическая эволюция + легкая реализация

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

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

Форма Бакуса-Наура

Сначала нужно сказать про то, что такое контекстно-независимая грамматика в форме Бакуса-Наура(сокращенно БНФ). Про формальные языки и грамматики на Хабре уже есть довольно интересная статья. Очень рекомендую к прочтению. Но наша цель заключается в том, чтобы понять, что такое БНФ и научиться этой формой пользоваться.

Википедия дает вполне адекватное определение:

БНФ — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик.

БНФ имеет терминальные и нетерминальные символы. Терминалы — константы. Мы их подставили и все тут, а вот с нетерминальными символами все гораздо интересней: их можно подставлять друг в друга по правилами.

Рассмотрим пример. У нас есть следующая формальная система описания синтаксиса контекстно-свободной грамматики:





В нашем примере множество нетерминальных символов


А множество терминальных символов представлено так


Множество S будет содержать один элемент.


Этот элемент будет входной точкой для постройки и работы с правилами.

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

Следим за цепочками

1) <sntnce> => <adverb><verb> => quickly <verb> => quickly ran

2) <sntnce> => <noun><verb> => Peter <verb> => Peter fell

Возникает вопрос: на каком основании происходят данные подстановки? На этот вопрос я отвечу чуть позже.

Генетический алгоритм

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

Итак, ГА использует поведение природы. На самом деле ничего нового придумано не было. Этот алгоритм работает уже миллионы лет. Спасибо ему. Ведь если б не он, то нас бы не было.

ГА состоит из нескольких этапов.

(1) Создание начальной популяции (создаем хромосому для каждой особи)

(2) Высчитывание у каждого индивидуума фитнес-функции(именно она показывает кто приспособлен в данной популяции лучше всего)

(3) Отбор лучший представителей для образования дальнейшего потомства

(4) Кроссовер

(5) Мутация

(6) После (4) получаем детей, часть которых проходит через (5). На выходе получаем потомство

(7) Отбор отцов и детей в новое поколение

(8) возврат к шагу (2), если значения, которые выдают дети нас не устраивает

Хромосома — закодированное представление нужной нам информации. В первоисточниках используется бинарное представление. Т.е. если нам нужно найти 4 параметра(каждый из них в интервале от 0 до 15), то на каждый параметр понадобится 4 бита(ноль или единица). А сама хромосома будет длиной 16. Все довольно примитивно.

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

Теперь немного про операторы в ГА и всякие фитнес функции.

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

Кроссовер — классная штука. В генетическом программировании, кстати, этот оператор является чуть ли не единственным для получения потомства с лучшими качествами. Суть заключается в том, что мы берем двух родителей (а точнее их генотип). Делим его пополам. И меняем местами. Сейчас покажу.

Есть два списка:






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

Мутация — процесс в случайно замене того или иного гена.



Часто употребимый метод отбора в новое поколение — элитарный. Мы просто берем n лучших особей из списка дети+ родители. А потом дополняем популяцию случайным образом до нужного количества.

Важно: размер хромосомы может быть как фиксированным, так и произвольным. Тоже самое касается и размера популяции.

Грамматическая эволюция

А вот теперь о самом главном. Что ж это за метод такой и с чем его едят.
Сама суть заключается в том, что у вас есть задача, которую надо решить. Вы строите грамматику в форме Бакуса-Наура. Создаете исходную популяцию, в которой у каждого индивидуума будет своя хромосома, описывающая какие правила когда, куда, подставлять. Важность заключается в том, что благодаря этим правилам вы получаете функцию, которую можете использовать для вычислений. Значение этой функции с подставленными в нее заранее заданными(или нет) параметрами может выступать в качестве функционала(фитнес-функции). Чем лучше функционал, тем лучше функция, а следовательно и индивидуум со своей хромосомой.

Подробней о хромосоме.

Пусть имеем следующую грамматику

<e> ::= <e><op><e> | <val>

<val> ::= x | 3 | 2

<op> ::= + | — | * | /

Дальше у нас есть такая хромосома


Изначально символьное представление функции содержит один нетерминальный символ: H = <e>(как правило).

Берем первый элемент из chromo: 2. Считаем сколько правил в преобразования в <e>: 2. Делим 2 % 2 (по модулю!!) = 0. Значит вместо <e> подставляем <e><op><e>. Таким образом Н = <e><op><e>. Двойку из chromo выкидываем. Она больше не нужна.

На очереди единица. и снова смотрим на <e>. 1 % 2(число правил подстановки) = 1. Значит вместо <e> подставляем <val>. Получаем H = <val><op><e>.

Если проделывать эти нехитрые манипуляции дальше, то получится такая цепочка






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

Это все. Да, есть несколько вариантов подстановки: в глубину(рассмотренный), в ширину, так называемая — подстановка. Но это уже материал на отдельную статью.

А теперь пример.

Есть интервал времени . Есть функция . Нужно найти функцию, которая давала бы минимальную квадратичную ошибку — функционал данной задачи.

Посмотрим на код

модуль main

# -*- coding: utf-8 -*-

import GE

def foo(x):
  return 1+x+x**2+x**3

interval = [-5, 5]
values =[foo(e) for e in range(interval[0], interval[1])]
if __name__ == "__main__":
  result = GE.GA(
    chromo_len=12,
    pop_len=100,
    count=20
  )[0]

  print(result)

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

Длина хромосомы = 15;

Длина популяции = 100;

Число итераций(эволюций) = 20;

Модуль parser

# -*- coding: utf-8 -*-

import random
import re

def rand(num):
    return int(random.random()*num)

def parse(chromo):
  l = len(chromo)
  j = 0
  h = "<expr>"
  grammar = {
    "<expr>": ["<expr><op><expr>", "<val>"],
    "<op>": ["+", "-", "*", "/"],
    "<val>": ["x", "1"]
  }
  s = r"<+["+('|'.join(list(map(lambda x: x[1:-1], grammar.keys()))))+"]+>"
  pattern = re.compile(s)

  while j < l:
    elems = pattern.findall(h)
    if not elems:
      break
    el = elems[0]
    h = h.replace(el, grammar[el][(chromo[j] % int(len(grammar[el])))], 1)
    j += 1

  while True:
    elems = pattern.findall(h)
    if elems:
      for elem in elems:
        el = elem
        if elem == "<expr>":
          el = "<val>"
        h = h.replace(elem, grammar[el][rand(len(grammar[el]))], 1)
    else:
      break
  return h

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


модуль GE

# -*- coding: utf-8 -*-

import random
import math
from parser import parse

def rand(num):
  return int(random.random() * num)

class Individ:
  def __init__(self, genotype):
    self.genotype = genotype
    self.phenotype = self.get_phenotype()
    self.fitness = self.get_mistake()

  def __eq__(self, other):
    return self.fitness == other.fitness

  def __ne__(self, other):
     return not self.__eq__(other)

  def __lt__(self, other):
    return self.fitness < other.fitness

  def __ge__(self, other):
    return not self.__lt__(other)

  def __str__(self):
    return "chromosome : {0}\nphenotype = {2}\nfitness = {1}\n".format(self.genotype, self.fitness, self.phenotype)

  def get_phenotype(self):
    return parse(self.genotype)

  def get_mistake(self):
    import main
    intr = main.interval
    vals = main.values
    f = eval("lambda x: {0}".format(self.phenotype))
    f_vals = []
    for i in range(intr[0], intr[1]):
      try:
        f_vals.append(f(i))
      except:
        return 10000
    return sum(list(map(lambda e: (e[0] - e[1]) ** 2, list(zip(vals, f_vals)))))

def GA(chromo_len, pop_len, count):
  population = get_population(pop_len, chromo_len)
  while count > 0:
    childrn_chromos = get_children_chromose(population)
    mutation(childrn_chromos, 0.8)
    children = get_children(childrn_chromos)
    population = get_new_population(population, children)
    count -= 1
  return population

def get_genotype(gen_length):
  return [rand(200) for _ in range(gen_length)]

def get_population(length, chromo_len):
  return [Individ(get_genotype(chromo_len)) for _ in range(length)]

def get_children_chromose(parents):
  
  def tournament():
    return [min([parents[rand(len(parents)-1)] for _1 in range(7)]) for _2 in range(2)]

  children_chromo = []
  for _3 in range(int(len(parents)/2)):
    children_chromo += crossover(tournament())
  return children_chromo

def get_children(childrn_chromos):
  return [Individ(childrn_chromos[i]) for i in range(len(childrn_chromos))]

def crossover(pair):
  p1 = pair[0]
  p2 = pair[1]
  d = random.randint(1, len(p1.genotype) - 2)
  return [p1.genotype[:d] + p2.genotype[d:], p2.genotype[:d] + p1.genotype[d:]]

def mutation(chldrn_chromo, p):
  for j in range(len(chldrn_chromo)):
    if p > random.random():
      i = random.randint(1, len(chldrn_chromo[j]) - 1)
      chldrn_chromo[j][i] = rand(200)
  return chldrn_chromo

def get_new_population(population, children):
  l = len(population)
  buf = population+children
  buf.sort()
  c = math.trunc(0.2*l)
  new_population = buf[:c]
  tmp = buf[c:]
  ll = len(tmp)
  new_population += [tmp[random.randint(1, ll - 1)] for _ in range(c, l)]
  return new_population

Обычная реализация генетического алгоритма.

Функция GA является входной точкой в цикл эволюций.

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

Каждый индивидуум имеет три поля: генотип, фенотип, значение фитнес-функции.

В итоге

получаю функцию



что идентично



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

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

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