Що таке граматична еволюція + легка реалізація

Зовсім недавно я написав статті, в якій без пояснень показав те, на що здатний метод граматичної еволюції. Я повністю згоден, що так робити не можна, але, як хотілося показати результати цікавого методу. Я думав «що буде краще: перевести першоджерело або дати своє власне пояснення». Лінь взяла верх.

Якщо комусь цікаві еволюційні методи і завдання символьної регресії(і не тільки), то прошу до прочитання.

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

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

Вікіпедія дає цілком адекватне визначення:
БНФ — формальна система опису синтаксису, в якій одні синтаксичні категорії послідовно визначаються через інші категорії. БНФ використовується для опису контекстно-вільних формальних граматик.
БНФ має термінальні й термінальні символи. Термінали — константи. Ми їх підставили і все тут, а от з нетерминальными символами все набагато цікавіше: їх можна підставляти один в одного за правилами.

Розглянемо приклад. У нас є наступна формальна система опису синтаксису контекстно-вільної граматики:

<sntnce> :: = <sntnce> | <noun><verb> | <прислівник><verb>
<noun> ::= Peter \, | \, ball
<verb> ::= ran \,|\, fell
<прислівник> ::= quickly
У нашому прикладі множина нетермінальних символів

N =\{<sntnce>,<noun>,<verb>,<adverb>\}.
А безліч термінальних символів представлено так

T= \{Peter, \, ball, \, quickly, \, ran, \, fell \}
Множина S буде містити один елемент.

S = \{<sntnce>\}
Цей елемент буде вхідною точкою для побудови і роботи з правилами.

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

Стежимо за ланцюжками

1) <sntnce> => <прислівник><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. Все досить примітивно.

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

Тепер трохи про оператори ГА і всякі фітнес функції.

Фітнес-функція — функціонал, який ми повинні оптимізувати. Він варіюється від завдання до завдання. Якщо стоїть питання мінімізації функціоналу, то для селекції потрібні батьки, які мають як можна меншою фітнес-функцією.

Кросовер — класна штука. У генетичному програмуванні, до речі, цей оператор є чи не єдиним для отримання потомства з кращими якостями. Суть полягає в тому, що ми беремо двох батьків (а точніше їх генотип). Ділимо його навпіл. І міняємо місцями. Зараз покажу.

Є два списки:

first \, parent = [1,2,3,4,-5,-6,-7,-8,]
Second \, parent = [-1,-2,-3,-4,5,6,7,8]
Result:
Child \, 1 = [1,2,3,4,5,6,7,8]
Child \, 2 = [-1,-2,-3,-4,-5,-6,-7,-8]
Це був приклад точкового кросовера. Є інші варіації на цю тему, але про них не будемо.

Мутація — процес випадково заміни того чи іншого гена.

was = [1,2,3,4]
be = [1,-5,3,4]
Часто вживаний метод відбору в нове покоління — елітарний. Ми просто беремо n кращих особин зі списку діти+ батьки. А потім доповнюємо популяцію випадковим чином до потрібної кількості.

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

Граматична еволюція

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

Детальніше про хромосомі.

Нехай маємо таку граматику

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

<val> ::= x | 3 | 2

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

Далі у нас є така хромосома

chromo = [2,1,6,4,5,1]
Спочатку символьне представлення функції містить один нетерминальный символ: 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>.

Якщо проробляти ці нехитрі маніпуляції далі, то вийде така ланцюжок

&amp;lt;val&amp;gt;&amp;lt;op&amp;gt;&amp;lt;e&amp;gt; (6\%3 = 0) -&amp;gt; x &amp;lt;op&amp;gt;&amp;lt;e&amp;gt;
x &amp;lt;op&amp;gt; &amp;lt;e&amp;gt; (4 \% 4 = 0) -&amp;gt; x + &amp;lt;e&amp;gt;
<img src=«tex.s2cms.ru/svg/%20x%20%2B%20%3Ce%3E%20(5%20%5C%25%202%20%3D%201)%20-%3E%20x%20%2B%20%3Cval%3E» alt=x + <e> (5 \% 2 = 1) -> x + <val>"/>
<img src=«tex.s2cms.ru/svg/%20x%20%2B%20%3Cval%3E%20(1%20%5C%25%203%20%3D%201)%20-%3E%20x%20%2B%203» alt=x + <val> (1 \% 3 = 1) -> x + 3"/>
H = x + 3.
Далі використаємо цю функцію, щоб порахувати функціонал і визначити наскільки нам підходить індивідуум з даними фенотипном(так функція зветься) і генотипом(хромосомою).

Це все. Так, є кілька варіантів заміни: в глибину(розглянутий), в ширину, так звана \pi— підстановка. Але це вже матеріал на окрему статтю.

А тепер приклад.

Є інтервал часу t \in [-5,5]. Є функція y(x) = 1+x+x^2+x^3. Потрібно знайти функцію, яка давала б мінімальну квадратичну помилку — функціонал даної задачі.

Подивимося на код

модуль main
import GE
import time

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

interval = [-5,5]
values =[foo(elem) for elem in range(interval[0],interval[1])]

if __name__ == "__main__" :

time_begin = time.time()
result = GE.GA(
dim=15,
lengthPopulation=50,
count=150
)[0]

print(result)
print()
print("time = {0}".format(time.time() - time_begin))

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

Довжина хромосоми(dim) = 15;

Довжина популяції = 50;

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

Модуль parser
import math
import random
re import

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

def parse(chromo):
length = len(chromo)
j=0
H = "<expr>"
grammar = {
"<expr>":[
"<expr><op><expr>",
"<val>"
],
"<op>":["+", "-", ".*", "/"],

"<val>": [ "x" , "1"]
}

s = r"<+[expr|op|val]+>"
pattern = re.compile(s)

while(j<length):
elem = pattern.findall(H)
if elem == [] and j<length : break
elem = elem[0]
c = len(grammar[elem])
i = chromo[j] " %c
newE = grammar[elem][i]
H = H. replace(elem,newE,1)
j += 1

while True:
elems = pattern.findall(H)
if elems != [] :
for i in range(0,len(elems)):
elem = elems[i]
if elem=="<expr>" :
elem = "<val>"
c = len(grammar[elem])
randd = rand©
n = grammar[elem][randd]
elem = elems[i]
H = H. replace(elem,n,1)
else:
break

return H

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

модуль GE
import random
import math
from parser import parse

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

class Individ:
def __init__(self, genotype=None):
self.genotype = genotype
self.phenotype = self.getPhenotype()
self.fitness = self.getMistake()

def __str__(self):
return "Chromosome : {0}\nPhenotype = {2}\nFitness = {1}\n".format(self.genotype, self.fitness, self.phenotype)

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

def getMistake(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:
val = f(i)
f_vals.append(val)
except:
return 10000
try:
return sum(list(map(lambda elems: (elems[0] - elems[1]) ** 2, list(zip(vals, f_vals)))))
except:
return 10000


def GA(dim, lengthPopulation, count):
population = [inst for inst in getPopulation(lengthPopulation, dim)]
while count > 0:
if count % 50 == 0:
print("count = {0}".format(count))
print(population[0])
childrnChromos = getChildrenChromose(population)
mutation(childrnChromos, rand(0.3 * lengthPopulation))
children = [child for child in getChildren(childrnChromos)]
population = getNewPopulation(population, children)
count -= 1
return population

def getGenotype(gen_length=0):
return [rand(200) for i in range(gen_length)]

def getPopulation(length, chromo_len):
for i in range(0, length):
yield Individ(genotype=getGenotype(chromo_len))

def getChildrenChromose(parents):
children_chromo = []
buf = parents[:]
random.shuffle(buf)
length = int(len(buf) / 2)
for i in range(length):
children_chromo += crossover(parents[i], parents[i + 1])
return children_chromo

def getChildren(childrnChromos):
l = len(childrnChromos)
for i in range(l):
yield Individ(childrnChromos[i])

def crossover(p1, p2):
l = len(p1.genotype)
d = rand(l - 1)
return [p1.genotype[:d] + p2.genotype[d:], p2.genotype[:d] + p1.genotype[d:]]

def mutation(chldrnChromo, howMuch):
l = len(chldrnChromo[0])
for j in range(0, howMuch):
chromo = chldrnChromo[j]
chromo[rand(l - 1)] = rand(200)
chldrnChromo[j] = chromo
return chldrnChromo

def getNewPopulation(population, children):
l_need = len(population)
buf = (population + children)[:]
buf.sort(key=lambda elem: elem.fitness)
count = rand(0.2 * len(buf))
result = buf[:count]
another = buf[count:]
i = count
while i < l_need:
r = rand(l_need - count)
while another[r] in result:
r = rand(l_need - count)
result.append(another[r])
i += 1
return result

Звичайна реалізація генетичного алгоритму.

Функція GA є вхідною точкою в цикл еволюції.

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

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

В результаті, за час роботи алгоритму

time= 1.2367351 ms
отримую функцію

x+x/1*x+x*x*1*x+1/1&quot;/
що дуже сильно нагадує

1+ x +x^2 +x^3
Як ви можете бачити, граматика дуже важлива.

Сподіваюся, тепер стало ясно що за метод такий граматична еволюція і як його використовувати для вирішення завдань. Цікавий той факт, що символьна регресія застосовується не тільки для функцій. Ми можемо створювати інструкції для роботів, а також будувати структуру нейронної мережі та настроїти в ній параметри. Нам стає не потрібен метод зворотного поширення помилки, для навчання мережі. Разом з ним можна відмовитися від функцій активацій (обов'язкової) першої похідної. А також ми більше не потребуємо навчальної вибірки. Це цікавий підхід, який вимагає роздумів і досліджень. Але можу сказати, що він працює.

Ще раз даю посилання на джерело. Якщо хто хоче глибше зрозуміти метод.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.