Текущая ветка обсуждений получилась довольно интересной :-) Спасибо вам за замечания.
Однако, изначально, при написании данной статьи у меня была несколько иная цель — проиллюстрировать на простом примере концепцию ГП, предоставить людям работающий прототип, и поделиться собственными наблюдениями.
Здесь есть небольшая сводка математических моделей, в рамках которых были проанализированы некоторые аспекты ГП.
Относительно пространства поиска, в общем случае, можно заметить что оно бесконечномерное, а также, боюсь, что вопрос о его топологии связан с проблемой разрешимости — со всеми вытекающими отсюда последствиями.
Да, ещё очень удобным является тип данных CODE, который, по сути, предоставляет всю функциональность необходимую для ГП.
Также, как мне кажется, наиболее удобно и эффективно оперировать синтаксическими конструкциями, которые соответствуют чистым функциональным программам. Исходя из их лаконичности, а соответственно — небольшой сложности синтаксического дерева, это положительно сказывается на скорости нахождения решения, а также значительно помогает при последующем анализе и упрощении решения.
Например:
map(sin, list(1, 10))
То же самое, в императивном стиле:
for(int i = 1; i < 11; i++) {
arr[i] = sin(i);
}
return arr;
В некоторм роде вы говорите правильные вещи, но ваш стиль комментирования довольно предвзятый (я имею ввиду выражения «притягивать за уши», «костыли», «мега-теория» и т.п.)
Тем более, вы тоже оперируете далеко не академически точными понятиями и терминами.
Как человек с образованием в данной области (квантовая механика и стат. термодинамика), хочу обратить внимание на то, что вы заблуждаетесь относительно того, что "… физический смысл имеют только некоторые точки пространства состояний, причем заранее неясно, какие..." — физический смысл имеют все точки фазового пространства, и он чётко определяется в терминах классической термодинамики.
Второе замечание, — задачи о которых вы упоминаете довольно легко поддаются сферическо-вакуумному формализму. Поэтому, если вы попытаетесь методами чистой стат. физики, например, рассчитать теплоемкость реального кристалла (какого-нибудь германия), или рассчитать температуру фазового равновесия (даже простой воды), то вы потерпите эпический крах — получите результаты, которые могут на порядки отличатся от реальных измерений (почему? да, как минимум, потому что невозможно аналитически рассчитать интеграл взаимодействия в системе, которая содержит больше одного электрона). А для практических расчётов, всё так же, используются всяческие приближения и эмпирические модели.
И да, признаюсь, я тоже не в восторге от обилия биологических терминов в литературе по генетическим алгоритмам, но, во-первых, вы могли заметить что я без надобности не злоупотребляю таковыми. А во-вторых, хоть данные алгоритмы ещё на стадии эмпирических исследований, но это совсем не отменяет того факта, что они позволяют получать хорошие решения.
Последняя аналогия — классическая термодинамика, как область естествознания, полностью построена на эмпирике. Хочу привести цитату А. Эйнштейна* по этому поводу: «Теория производит тем большее впечатление, чем проще ее предпосылки, чем разнообразнее предметы, которые она связывает, и чем шире область её применения. Отсюда глубокое впечатление, которое произвела на меня классическая термодинамика. Это единственная физическая теория общего содержания, относительно которой я убежден, что в рамках применимости ее основных понятий она никогда не будет опровергнута (к особому сведению принципиальных скептиков)» — не замечаете ли аналогии?
* (Цит. по: Кириллин Б. Л., Сычев В. В., Шейндлин А. Е. Техническая термодинамика, 3-е изд. М., 1979, с. 502.)
Конечно, если в базовом наборе есть функция sin — ничто не мешает, в результате мутации поместить в корень синтаксического дерева функцию sin.
Хотя, как вы понимаете, по очень маленькому и монотонному промежутку данных — невозможно однозначно определить функцию. Поэтому, на промежутке по х от -0.5 до 0.5, с одинаковой вероятностью можно получить как линейную, так и синусоидальную зависимость.
В общем, правильный результат отыскивается довольно быстро если в наборе базовых функций содержатся функции, комбинация которых позволяет построить искомую зависимость, и если искомая формула имеет не очень сложную структуру (к сожалению, пока что, не могу привести конкретных цифр, а только собственные наблюдения).
Вот пример с асимптотической функцией:
Ищем функцию: f(x) = 2/x
Исходные данные
# allowed functions are: ADD SUB MUL DIV SQRT POW LN SIN COS
# set which functions to use:
ADD MUL SUB DIV POW SQRT
# looking for:
f(x) - ?
# define training set:
f(-1) = -2
f(-0.9) = -2.222222222
f(-0.8) = -2.5
f(-0.7) = -2.857142857
f(-0.6) = -3.333333333
f(-0.5) = -4
f(-0.4) = -5
f(-0.3) = -6.666666667
f(-0.2) = -10
f(-0.1) = -20
f(0.1) = 20
f(0.2) = 10
f(0.3) = 6.666666667
f(0.4) = 5
f(0.5) = 4
f(0.6) = 3.333333333
f(0.7) = 2.857142857
f(0.8) = 2.5
f(0.9) = 2.222222222
f(1) = 2
threshold = 5
И уже на 10-й итерации получаем ответ: f(x) = (((-40.187091057457245) / x) * (-0.04967024882881388))
лог эксперимента
Start time is: Fri Dec 21 16:30:21 EET 2012
f(x) = (x + x)
1 1110.6141849372693
f(x) = (x * 5.227087163426092)
2 1032.0300015165594
f(x) = (x * 5.188903230694518)
3 1032.0222453656522
f(x) = ((x + x) * 2.599190101196649)
4 1032.0220755614089
5 1032.0220755614089
f(x) = (((x + x) * (-0.12522500922214785)) * (-20.749626688467036))
6 1032.022006105762
7 1032.022006105762
f(x) = (x * 5.19507279952461)
8 1032.0219777015882
f(x) = (x * sqrt(abs(((-33.321388309286405) / x))))
9 873.1171859876806
f(x) = (((-40.187091057457245) / x) * (-0.04967024882881388))
10 0.004707596212974934
Best function is:
f(x) = (((-40.187091057457245) / x) * (-0.04967024882881388))
End time is: Fri Dec 21 16:30:25 EET 2012
Конечно, можно попытаться втиснуть задачу в рамки конкретного метода аппроксимации, но я акцентирую внимание на автоматическом конструировании модели.
При таком подходе, множество функций можно легко расширить до неаналитических, использовать шаблоны, работать с любым количеством переменных, использовать трансцендентные функции ( habrahabr.ru/post/163195/#comment_5611389 ), можно даже реализовать рекурсивные отношения.
Такой подход позволяет спокойно работать с данными, которые тяжело представить в виде функциональной зависимости. Всё тот же пример — демка 1
Я искал нейронную сеть, которая позволит максимизировать эффективность не отдельно взятого агента, а коллективную эффективность группы агентов в незнакомой среде.
Поэтому на каждом шаге генетического алгоритма, для каждой нейронной сети — я проверял насколько эффективно будет действовать группа агентов, каждый из которых управляется этой нейронной сетью (фактически подсчитывал суммарное количество «еды», собранной агентами).
Генетическое программирование эффективно использовать в задачах, которые трудно формализировать. Если же задачу формализировать достаточно просто, то можно использовать алгоритм специально разработанный для данной предметной области, но в то же время — приемлемые результаты можно получить и с помощью генетического программирования. Именно это я и продемонстрировал в топике.
С этого-то я и начинал топик: «вместо того, чтобы самостоятельно выбирать алгоритм, разработаем программу, которая способна автоматически генерировать алгоритмы для решения задач».
Конечно, любой частный алгоритм, разработанный для конкретной задачи или модели — будет лучше общего подхода.
Но я фокусировался именно на общем подходе, и рассмотрел символьную регрессию, как пример, в свете оного, дабы показать что таким образом тоже можно получать адекватные решения
Относительно сходимости — её нельзя рассматривать отдельно от типа эволюционный стратегии (проще говоря — параметров генетического алгоритма)
для того чтоб контролировать размер популяции в памяти
размер дерева влияет на скорость вычисления соответствующей формулы
эмпирически установил, что ограничения на 6-7 уровневую глубину дерева, и правильно подобранного множества базисных функций — должно быть достаточно для конструирования приемлемого решения
также, я заметил что в данной задаче, небольшие мутации, в применении к огромным деревьям, не привносят качественно лучшие решения
Опишите, пожалуйста, как с помощью ДПФ можно получить формулу f(x, y, z) = x^2 + 3*x + 2*y + z + 5 из описанного в топике эксперимента?
И совсем непонятно, каким образом ДПФ поможет, например, для автоматического конструирования нейронной сети?
Спасибо
Удаётся реконструировать формулу, даже в случае небольшого количества точек, равномерно распределённых по монотонному участку искомой функции.
Например:
Пусть искомая функция будет f(x) = x^3 — 70*(x^2)
Входные данные — будут точки с монотонного интервала [-100… -40]
файл с входными данными
# allowed functions are: ADD SUB MUL DIV SQRT POW LN SIN COS
# set which functions to use:
ADD MUL SUB POW DIV
# looking for:
f(x) - ?
# define training set:
f(-100) = -1700000
f(-90) = -1296000
f(-80) = -960000
f(-70) = -686000
f(-60) = -468000
f(-50) = -300000
f(-40) = -176000
Да, можно подойти к этому вопросу и таким образом: определить какие наборы функций или шаблонов функций эффективнее применять как в одном, так и в другом случае. В моём случае эффективным оказалось то решение, которое я описал (в сочетании с этапом оптимизации коэффициентов дерева).
Ваши наблюдения верны: найденные решения могут быть правильными или очень хорошими, но из-за способа построения могут выглядеть довольно громоздко, или содержать мёртвые участки кода. Но вот с Вашими с выводами я не соглашаюсь.
Можно конструировать «простые программы», но во многих случаях это лишь затруднит поиск хорошего решения.
Пример, когда мёртвые участки кода полезны:
представте что мы ищем формулу (1 + (x — 5)^2).
Она может получится в результате мутации дерева с мёртвым участком: (1 + (x — x)^2) -> (1 + (x — 5)^2)
(небольшое уточнение к графику: в точке x = 0 — асимптота, но так как точка 0 не входила в обучающую выборку, то при построении графика, я её случайно «проскочил»)
Спасибо Вам за идею. Решил проверить — получить формулу для синуса, не имея функции sin.
Для этого создал следующую обучающую выборку (где f(x) — значения синуса x):
sin_as_cos.txt
# allowed functions are: ADD SUB MUL DIV SQRT POW LN SIN COS
# set which functions to use:
ADD SUB MUL DIV SQRT POW COS
# looking for:
f(x) - ?
# define training set:
f(-5) = 0.958924275
f(-4.6) = 0.993691004
f(-4.2) = 0.871575772
f(-3.8) = 0.611857891
f(-3.4) = 0.255541102
f(-3) = -0.141120008
f(-2.6) = -0.515501372
f(-2.2) = -0.808496404
f(-1.8) = -0.973847631
f(-1.4) = -0.98544973
f(-1) = -0.841470985
f(-0.6) = -0.564642473
f(-0.2) = -0.198669331
f(0.2) = 0.198669331
f(0.6) = 0.564642473
f(1) = 0.841470985
f(1.4) = 0.98544973
f(1.8) = 0.973847631
f(2.2) = 0.808496404
f(2.6) = 0.515501372
f(3) = 0.141120008
f(3.4) = -0.255541102
f(3.8) = -0.611857891
f(4.2) = -0.871575772
f(4.6) = -0.993691004
threshold = 0.5
Провёл эксперимент несколько раз. Ниже приведены полученные результаты:
f(x) = cos((((x — 0.20866701892617723) + 0.20909776128069524) + (-1.5658757184422276)))
После упрощения: f(x) = cos(x — 1.56544498)
а это почти cos(x — pi/2)
f(x) = cos(((-1.5518824117603933) — ((x * (-22.779793630567173)) * ((0.9905590241810334 ^ x) / 22.778425607844536))))
Опять получили немного запутанную формулу. Хотя, легко заметить, что (0.9905590241810334 ^ x) это почти (1 ^ x) — а значит никак на результирующую формулу влияет. Затем, можно сократить числитель и знаменатель — 22.779793630567173
Таким образом, приходим к формуле: f(x) = cos(-1.5518824117603933 + x)
а это почти cos(x — pi/2)
Да, с несколькими экстремумами ситуация выглядит немного сложнее.
Но хочу обратить внимание на то, что мы оперируем функциями и комбинациями функций. Таким образом, мы можем получить синтаксическое дерево, которое соответствует функции с несколькими экстремумами (а затем оптимизировать коэффициенты в соответствии с тренировочными данными)
Да, это, большей мерой, результат достигнутый экспериментальным путём.
Один интересный момент, который можно заметить — два синтаксически подобных дерева — могут очень сильно различаться семантически. Хотя, может, это даже лучше, в плане покрытия пространства поиска решений
Однако, изначально, при написании данной статьи у меня была несколько иная цель — проиллюстрировать на простом примере концепцию ГП, предоставить людям работающий прототип, и поделиться собственными наблюдениями.
Здесь есть небольшая сводка математических моделей, в рамках которых были проанализированы некоторые аспекты ГП.
Относительно пространства поиска, в общем случае, можно заметить что оно бесконечномерное, а также, боюсь, что вопрос о его топологии связан с проблемой разрешимости — со всеми вытекающими отсюда последствиями.
Также, как мне кажется, наиболее удобно и эффективно оперировать синтаксическими конструкциями, которые соответствуют чистым функциональным программам. Исходя из их лаконичности, а соответственно — небольшой сложности синтаксического дерева, это положительно сказывается на скорости нахождения решения, а также значительно помогает при последующем анализе и упрощении решения.
Например:
То же самое, в императивном стиле:
Тем более, вы тоже оперируете далеко не академически точными понятиями и терминами.
Как человек с образованием в данной области (квантовая механика и стат. термодинамика), хочу обратить внимание на то, что вы заблуждаетесь относительно того, что "… физический смысл имеют только некоторые точки пространства состояний, причем заранее неясно, какие..." — физический смысл имеют все точки фазового пространства, и он чётко определяется в терминах классической термодинамики.
Второе замечание, — задачи о которых вы упоминаете довольно легко поддаются сферическо-вакуумному формализму. Поэтому, если вы попытаетесь методами чистой стат. физики, например, рассчитать теплоемкость реального кристалла (какого-нибудь германия), или рассчитать температуру фазового равновесия (даже простой воды), то вы потерпите эпический крах — получите результаты, которые могут на порядки отличатся от реальных измерений (почему? да, как минимум, потому что невозможно аналитически рассчитать интеграл взаимодействия в системе, которая содержит больше одного электрона). А для практических расчётов, всё так же, используются всяческие приближения и эмпирические модели.
И да, признаюсь, я тоже не в восторге от обилия биологических терминов в литературе по генетическим алгоритмам, но, во-первых, вы могли заметить что я без надобности не злоупотребляю таковыми. А во-вторых, хоть данные алгоритмы ещё на стадии эмпирических исследований, но это совсем не отменяет того факта, что они позволяют получать хорошие решения.
Последняя аналогия — классическая термодинамика, как область естествознания, полностью построена на эмпирике. Хочу привести цитату А. Эйнштейна* по этому поводу: «Теория производит тем большее впечатление, чем проще ее предпосылки, чем разнообразнее предметы, которые она связывает, и чем шире область её применения. Отсюда глубокое впечатление, которое произвела на меня классическая термодинамика. Это единственная физическая теория общего содержания, относительно которой я убежден, что в рамках применимости ее основных понятий она никогда не будет опровергнута (к особому сведению принципиальных скептиков)» — не замечаете ли аналогии?
* (Цит. по: Кириллин Б. Л., Сычев В. В., Шейндлин А. Е. Техническая термодинамика, 3-е изд. М., 1979, с. 502.)
Хотя, как вы понимаете, по очень маленькому и монотонному промежутку данных — невозможно однозначно определить функцию. Поэтому, на промежутке по х от -0.5 до 0.5, с одинаковой вероятностью можно получить как линейную, так и синусоидальную зависимость.
Относительно тригонометрических функций, я приводил экмпреримент в данном комментарии: habrahabr.ru/post/163195/#comment_5611389
В общем, правильный результат отыскивается довольно быстро если в наборе базовых функций содержатся функции, комбинация которых позволяет построить искомую зависимость, и если искомая формула имеет не очень сложную структуру (к сожалению, пока что, не могу привести конкретных цифр, а только собственные наблюдения).
Вот пример с асимптотической функцией:
Ищем функцию:
f(x) = 2/x
И уже на 10-й итерации получаем ответ:
f(x) = (((-40.187091057457245) / x) * (-0.04967024882881388))
При таком подходе, множество функций можно легко расширить до неаналитических, использовать шаблоны, работать с любым количеством переменных, использовать трансцендентные функции ( habrahabr.ru/post/163195/#comment_5611389 ), можно даже реализовать рекурсивные отношения.
Такой подход позволяет спокойно работать с данными, которые тяжело представить в виде функциональной зависимости. Всё тот же пример — демка 1
Я искал нейронную сеть, которая позволит максимизировать эффективность не отдельно взятого агента, а коллективную эффективность группы агентов в незнакомой среде.
Поэтому на каждом шаге генетического алгоритма, для каждой нейронной сети — я проверял насколько эффективно будет действовать группа агентов, каждый из которых управляется этой нейронной сетью (фактически подсчитывал суммарное количество «еды», собранной агентами).
Генетическое программирование эффективно использовать в задачах, которые трудно формализировать. Если же задачу формализировать достаточно просто, то можно использовать алгоритм специально разработанный для данной предметной области, но в то же время — приемлемые результаты можно получить и с помощью генетического программирования. Именно это я и продемонстрировал в топике.
Конечно, любой частный алгоритм, разработанный для конкретной задачи или модели — будет лучше общего подхода.
Но я фокусировался именно на общем подходе, и рассмотрел символьную регрессию, как пример, в свете оного, дабы показать что таким образом тоже можно получать адекватные решения
Относительно сходимости — её нельзя рассматривать отдельно от типа эволюционный стратегии (проще говоря — параметров генетического алгоритма)
демка 1
демка 2
При чём, я специально не строил априорных предположений о наилучшей структуре нейронной сети
И совсем непонятно, каким образом ДПФ поможет, например, для автоматического конструирования нейронной сети?
Спасибо
В результате получаем формулу:
f(x) = ((x * (((-13.242522576569776) + (x — (-49.47522269762757))) * x)) — ((x * (-11.740960627643991)) * (x * (-9.048031523291307))))
После преобразований:
f(x) = x^3 — 69 * x^2
Например:
Пусть искомая функция будет f(x) = x^3 — 70*(x^2)
Входные данные — будут точки с монотонного интервала [-100… -40]
Можно конструировать «простые программы», но во многих случаях это лишь затруднит поиск хорошего решения.
Пример, когда мёртвые участки кода полезны:
представте что мы ищем формулу (1 + (x — 5)^2).
Она может получится в результате мутации дерева с мёртвым участком:
(1 + (x — x)^2) -> (1 + (x — 5)^2)
Для этого создал следующую обучающую выборку (где f(x) — значения синуса x):
Провёл эксперимент несколько раз. Ниже приведены полученные результаты:
После упрощения:
f(x) = cos(x — 1.56544498)
а это почти cos(x — pi/2)
После упрощения:
f(x) = cos(-1.07016828426169 * x — 4.75171966) = cos(1.07016828426169 * x + 4.75171966)
а это почти cos(x + 3*pi/2)
Опять получили немного запутанную формулу. Хотя, легко заметить, что (0.9905590241810334 ^ x) это почти (1 ^ x) — а значит никак на результирующую формулу влияет. Затем, можно сократить числитель и знаменатель — 22.779793630567173
Таким образом, приходим к формуле:
f(x) = cos(-1.5518824117603933 + x)
а это почти cos(x — pi/2)
f(x) = ((-22.66355680142012) / ((15.948637956747325 / (((-2.6050273232187884) / x) — (x * (-0.2602149380973864)))) — (17.992754706738232 / x)))
Но хочу обратить внимание на то, что мы оперируем функциями и комбинациями функций. Таким образом, мы можем получить синтаксическое дерево, которое соответствует функции с несколькими экстремумами (а затем оптимизировать коэффициенты в соответствии с тренировочными данными)
И опять же, для ускорения работы — я рассматривал только небольшой интервал значений x: от -10 до +11
Один интересный момент, который можно заметить — два синтаксически подобных дерева — могут очень сильно различаться семантически. Хотя, может, это даже лучше, в плане покрытия пространства поиска решений