@sshmakov7 янв 2018 в 00:38

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

11 мин

32K

Python * Машинное обучение *

+25

Комментарии 34

@0decca 7 янв 2018 в 07:48

Можно вместо Forth использовать PUSH — специально разработанный язык программирования для этой области.
faculty.hampshire.edu/lspector/push3-description.html

Да, область называется en.wikipedia.org/wiki/Genetic_programming
Там много подводных камней на самом деле.

@sshmakov 7 янв 2018 в 09:43

Вот спасибо! Я даже себе не могу объяснить, почему не нашел ваши ссылки раньше.

@0decca 7 янв 2018 в 10:37

Я учил эту область по многотомнику John Koza в начале нулевых или даже в конце 90-х — для трейдинговых систем.
Вот этот человек:
www.genetic-programming.com/johnkoza.html

На самом деле очень интересная тема, позволявшая находить нестандартные решения, которые экспертные группы просто не могли увидеть в силу замыленности взгляда.
Я потом перешел на Grammatical Evolution подход с линейным геномом, до сих пор в разных областях использую — например для поиска оптимальных дескрипторов в обработке изображений, генерации атрибутов для Machine Learning, вообще применения есть.

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

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

Искусственному интеллекту проще обмануть хозяина, чем решать задачу.
:-)

@sshmakov 7 янв 2018 в 14:54

На самом деле очень интересная тема, позволявшая находить нестандартные решения, которые экспертные группы просто не могли увидеть в силу замыленности взгляда.

Мне вообще кажется, что генетические алгоритмы могут сделать всё, их лишь нужно правильно применить.

А вот сложные проблемы надо декомпозировать, здесь бутылочное горлышко и обычная генетика слабо справляется, несмотря на теорему шим.

И я нарвался на это, не смотря на простоту задачи, пришлось делить задачу на две.
В отличие от Матери Природы у нас нет 4-х миллиардов лет и полигона испытаний в виде целой планеты. Поэтому приходится каждый шаг анализировать вручную, а не надеяться, что кривая оптимизации вывезет (при нашей жизни).

С другой стороны, в природе генетика ведь тоже не работает каждый раз с нуля, а базируется на основе уже отработанных решений. Можно придумать генетический алгоритм, вырабатывающий алгоритмы решения типовых элементарных задач, потом, уже на основе найденных решений, возможно после их оптимизации вручную, сделать ГА для решения более сложных задач. И так далее.

Можно также добавить в ГА сравнительный анализ успешных генотипов и защищать от изменений при скрещивании последовательности генов, присутствующие в каждом из них.

@0decca 9 янв 2018 в 21:24

Лучшие результаты в ГА у меня получались когда я включал локальную оптимизацию.
Т.е. ГА ищет структуру со случайными параметрами, а результирующий фитнесс считается после того, как эти параметры оптимизируются отдельно — например стохастическим градиентом (или просто градиентом).
Но это очень затратно.

Имхо современное понимание генетических алгоритмов что-то упускает из виду, а именно декомпозицию задачи на условно-независимые компоненты, которые могут эволюционировать отдельно.
Причем в теории эту декомпозицию можно встроить в сам алгоритм, но вот на практике это работает очень странно и малопредсказуемо.
Я пробовал использовать гиперциклы, разложение фитнесс-функций на аддитивные компоненты, везде чего-то не хватает.
Надеюсь кому-то повезет больше, т.к. имхо потенциал генетики недооценен.

PS
Вот интересная штука на базе генетики, которая считалась копролитом, потом воскресала, потом опять забывалась — несколько раз подряд.
en.wikipedia.org/wiki/Learning_classifier_system

@S_A 7 янв 2018 в 11:21

Тоже баловался подобным (в прошлом году), но на F#.

andrey@debian:~/Development/fsharp$ ./genetic.exe 3 25 0.1 10
 -- The beginning -- 
For 10 iterations target 25.000000 from initial 3.000000 with precision 0.100000
The best is Best with result 25.0 and error 0.000000 is functions sequence: double decrement square 
Length: Some 3
 -- The ending --

Код

let initialPropertyValue = System.Double.Parse(System.Environment.GetCommandLineArgs().[1])
let targetPropertyValue = System.Double.Parse(System.Environment.GetCommandLineArgs().[2])
let targetPrecision = System.Double.Parse(System.Environment.GetCommandLineArgs().[3])
let iterationsNumber = System.Int32.Parse(System.Environment.GetCommandLineArgs().[4])

let actions = 
    [|  
        (fun (x: double) -> x - 1.0); 
        (fun (x: double) -> x); 
        (fun (x: double) -> x + 1.0); 
        (fun (x: double) -> x * 2.0); 
        (fun (x: double) -> -x); 
        (fun (x: double) -> x * x) 
    |]

type Action = double -> double
type Chromosome =  Action []
type Fitness = double
type Individual = Chromosome * Fitness

let populationSize = 5000 // bigger values better when actions number is big
let eliteSize = populationSize / 15 // bigger values makes search faster, but not exact
let populationIterations = populationSize // bigger values are better when functions are complex

let calculateFitness initialValue targetValue chromosome =
    let result = Array.fold (fun accumulator f -> f accumulator) initialValue chromosome
    abs(targetValue - result)

let getFitness = calculateFitness initialPropertyValue targetPropertyValue

let random = System.Random()

let createChromosome (initialActions: Action[]) size : Individual =
    let chromosome = Array.init<Action> size (fun _ ->  initialActions.[random.Next(0, initialActions.Length)] )
    let fitness = getFitness chromosome
    (chromosome, fitness)

let initializePopulation size initialChromosomeLength =
    Array.init<Individual> size (fun _ -> createChromosome actions initialChromosomeLength) 
    |> Array.sortBy (fun (_, fitness) -> fitness)

let getElite (population: Individual []) =
    let size = population.Length - eliteSize
    population.[..size]

let crossover (population: Individual []) =
    let top50percent = population.Length / 2
    let mom = fst population.[random.Next(top50percent)]
    let dad = fst population.[random.Next(top50percent)]
    let index = random.Next(min mom.Length dad.Length)
    let chromosome = Array.append mom.[..index] dad.[index + 1..]
    let fitness = getFitness chromosome
    (chromosome, fitness)

let newGeneration population =
    let elite = getElite population
    let withSize = population.Length - elite.Length
    Array.init<Individual> withSize (fun _ -> crossover population)
    |> Array.append elite
    |> Array.sortBy (fun (_, fitness) -> fitness)

let MatchAction functionIndex =
    match functionIndex with
    | 0 -> "decrement"
    | 1 -> "identity"
    | 2 -> "increment"
    | 3 -> "double"
    | 4 -> "negate"
    | 5 -> "square"
    | _ -> "unknown"
    |> (fun x -> x + " ")

let bestFitnessFor (population: Individual[]) =
    snd population.[0]

let formatBestOf (population: Individual []) =
    let result = fst population.[0] |> Array.fold (fun accumulator f -> f accumulator) initialPropertyValue
    let error = abs result - targetPropertyValue
     
    fst population.[0]
        |> Array.map(fun action -> Array.findIndex (fun f -> f.GetType().FullName = action.GetType().FullName) actions)
        |> Array.fold (fun accumulator value -> accumulator + MatchAction value) "functions sequence: "
        |> sprintf "Best with result %A and error %f is %s" result error

let evolve (population : Individual []) =

    let rec evolve (population : Individual []) n =
        match (n, (snd population.[0])) with
        | (0, _) -> population.[0]
        | (_, 0.0) -> population.[0]
        | _ ->
            let newPopulation = newGeneration population
            evolve newPopulation (n - 1)

    evolve population populationIterations

[<EntryPoint>]
let main args =
    printfn " -- The beginning -- "
    printfn "For %d iterations target %f from initial %f with precision %f" iterationsNumber (float targetPropertyValue) (float initialPropertyValue) (float targetPrecision) 

    seq { 1..iterationsNumber } 
        |> Seq.tryFind (fun chromosomeLength ->
            let population = initializePopulation populationSize chromosomeLength
            let best = evolve population
            let result = bestFitnessFor population
            if targetPrecision > result then formatBestOf population |> printfn "The best is %s"
            targetPrecision > result) 
        |> printfn "Length: %A"

    printfn " -- The ending -- "
    let executionResult = 0
    executionResult

@Sirion 7 янв 2018 в 11:37

Плюсанул чисто за Паркер, потом уже полез читать статью)

Интересный подход. Я думал о чём-то подобном, но было лень. Возможно, с вашими наработками перестанет быть лень. Хотя я думал не в сторону RPN, а в сторону чего-то брейнфакоподобного.

@sshmakov 7 янв 2018 в 14:28

В КДПВ очень просился известный знаток Forth-а магистр Йода в сочетании с мастером Шифу для иллюстрации различных ветвей генетики, но всёобъясняющая фраза Паркер всех победила.

Выбор Forth объясняется просто — когда-то я имел с ним дело, даже писал форт-машину.

@BubaVV 7 янв 2018 в 13:02

Pyevolve вроде такое умеет

@Mobius 7 янв 2018 в 13:24

Существующие библиотеки грамматической эволюции пробовали использовать? Если да, то какие, чем не подошли?

@sshmakov 7 янв 2018 в 14:18

Не пробовал. Мне было нужно самому попробовать сделать свой велосипед и понять, прочувствовать, насколько перспективна идея.

@Mobius 7 янв 2018 в 16:46

Идея перспективная, многое зависит от конкретной задачи.
Здесь информация по теме в дополнение к указнной в комметариях выше.

Литература:
Evolutionary Automatic Programming in an Arbitrary Language O'Neill Michael, Ryan Conor
Foundations in Grammatical Evolution for Dynamic Environments Dempsey Ian, O'Neill Michael, Brabazon Anthony

Здесь про оптимизацию путём расширения грамматики уже найденными решениями.
Это, видимо, как раз последний пункт в вашей статье.
Constituent grammatical evolution Loukas Georgiou, External Examiner: Dr. Michael O’Neill

Некоторое бибилиотеки:
Первая ссылка на данный момент не работает, надеюсь, что временно, так как это как раз библиотека вышеуказанных авторов (Michael O'Neill и Anthony Brabazon).
GEVA: grammatical evolution in Java
Clojure support the the GEVA gramatical evolution library
gramEvol: Grammatical Evolution for R
Grammatical Evolution Ruby Exploratory Toolkit (GERET)
HeuristicLab

По генетике здесь хорошо изложен материал:
Stated Clearly
Bozeman Science
Bioinformatics Algorithms: An Active Learning Approach

Надеюсь кому-то пригодится, так как лучше всё же изучить сначала то, что есть. Возможно этого уже будет достаточно для решения задачи, а если нет, тогда уже улучшать.

@sshmakov 7 янв 2018 в 23:55

Спасибо!

@havock 7 янв 2018 в 16:25

Возьму на себя смелость поделиться с автором своим опытом:
1. В качестве генов возьмите команды какой-нибудь трясины Тьюринга и модифицируйте под свои задачи. Так, например, я брал Brainfuck и писал его интерпретатор, но не для целых, а для float'ов. Один раз даже пришлось модифицировать Brainfuck для непозиционной системы счисления. Не забудьте в этом интерпретаторе сделать проверку синтаксической корректности, в случае с Brainfuck она заключается в закрытости всех скобок и невылете за отведенную память.
2. Напишите «дизассемблер» отдельной особи, который будет множество простых инструкций вашего модифицированного Brainfuck'а (или другой трясины Тьюринга) превращать в высокоуровневые. С учетом специфики трясин Тьюринга и вообще машин Тьюринга такой «дизассемблер» лучше делать с указателями.
3. Интерпретатор и систему оценки результата работы отдельной особи пишите сразу для распределенных систем или GPU (OpenCL, CUDA, OpenMPI и подобных). Причем желательно с возможностью двухуровневого (и выше) параллелизма: сначала на уровне исполнителей, и на уровни выше блоков исполнителей. Так как в реальных приложениях задача ооочень тяжелая. Поэтому же рекомендую использовать для этого pure C.

И помните, метод интересный, но удачность его применения во многом зависит от представления данных. Потому что если между данными и ожидаемым результатом обработки наиболее приспособленной особью будет необходимо большое преобразование данных из сырых в обрабатываемые, то большая часть вашей особи, времени поиска оптимума и ресурсов будут потрачены на построение обработчика «raw data -> processable data», а это вам не нужно. Так как длина возможной «цепочки ДНК» одной особи ограничена памятью и приемлемым временем исполнения.

З.Ы. Ну а вообще 0decca правильно написал, там подводных камней много, и по этой теме можно писать диссертации.

@sshmakov 7 янв 2018 в 23:54

1. Ну, так я так и сделал, взял язык, достаточно простой в реализации и подходящий под задачу. А Forth, точнее, моя его интерпретация, избавляет меня от необходимости проверять скобки.
2. Не уловил, зачем нужен этот дизассемблер? Чтобы использовать созданный генотип в качестве отдельного гена, нужно лишь унифицировать по вызовам метод calc у Gen() и Dnk(). И ранее созданные объекты Dnk() складывать в словарь, из которого их использовать при создании генотипа высшего порядка.
3. Можно, и я думал об этом. Но есть два «но»: (1) в конкретных цифрах я не сравнивал, а на поверхностный взгляд скорость обработки поколений в генетическом алгоритме на входной строке на порядок-два выше обучения нейронной сети на изображениях. То есть ускоряться пока необходимости нет; (2) Еще неизвестно, буду ли я продолжать копать в этом направлении.
Ну и OpenCL можно использовать под Python.

@havock 8 янв 2018 в 02:17

1. Ну, так я так и сделал, взял язык, достаточно простой в реализации и подходящий под задачу. А Forth, точнее, моя его интерпретация, избавляет меня от необходимости проверять скобки.

Проверять скобки не такая уж и большая проблема. А вот выделять для особи целый объект можно только на стадии развлечения, а если задача с большой популяцией, то лучше всего когда особь это просто строка байт. Это экономит и память, и производительность, а кроме того сильно упрощает кроссинговер. К тому же у вас есть необходимость поддержания еще и простого стека, что в целом допустимо и где-то даже удобно, но опять-таки это довольно бессмысленная трата памяти и ресурсов, которые можно использовать эффективнее. Да и в принципе машина Тьюринга или лямбда-исчисление это достаточные формы для реализации любого алгоритма, незачем усложнять и вводить блоки типа умножения и более сложные. Если они нужны для решения задачи эволюция сделает их сама в том виде, в котором эффективнее всего для данной задачи. Более сложные блоки ДНК это в ряде случаев ограничение на гибкость и лишний барьер.

Не уловил, зачем нужен этот дизассемблер? Чтобы использовать созданный генотип в качестве отдельного гена, нужно лишь унифицировать по вызовам метод calc у Gen() и Dnk(). И ранее созданные объекты Dnk() складывать в словарь, из которого их использовать при создании генотипа высшего порядка.

Дизассемблер нужен по ряду причин: (1) эволюция — вещь основанная на случайности, и в структурированном псевдокоде можно найти мусорные фрагменты, которые не выполняют полезной работы; (2) ваш объект содержащий стек и обвязку исполнения Форта это круто, но фактически у вас каждая особь использует весьма сложную инфраструктуру для исполнения, хотя, в общем, нас интересует результат и внутренности только самой приспособленной особи. Таким образом, вынеся высокоуровневый псевдокод и инфраструктуру наружу и применяя их только к одной особи, мы экономим много ресурсов. Насчет ДНК высшего порядка из уже готовых блоков — мне не очень ясно зачем это нужно, так как в среднем это снижает изменчивость и видится мне лишним уровнем абстракции, как будто вы навязываете эволюции функциональный или объектный подход. Если вы хотите сохранять эффективные блоки, то лучше сделать разделение особей по половому признаку, и снизить оценочные требования для пола, который должен сохранять такие эффективные блоки, появление которых в ДНК привело нас в последний локальный экстремум.

Можно, и я думал об этом. Но есть два «но»: (1) в конкретных цифрах я не сравнивал, а на поверхностный взгляд скорость обработки поколений в генетическом алгоритме на входной строке на порядок-два выше обучения нейронной сети на изображениях. То есть ускоряться пока необходимости нет; (2) Еще неизвестно, буду ли я продолжать копать в этом направлении.

Я честно говоря не знаю какие у вас требования к системе, поэтому настаивать на параллелизме в вашем случае не буду, но так как мне приходилось делать подобные штуки для промышленного применения, могу сказать, что на CPU с 64ГБ RAM обработать даже популяцию в 100 особей и довести ее хотя бы до второго экстремума может занимать часы (основные затраты — оценка нового поколения), а в создаваемых системах отклик должен был исчисляться в секундах. По этим причинам в моем случае переход на параллельные вычисления был неизбежен.

Ну и OpenCL можно использовать под Python.

Можно, и не только в Python, но в зависимости от специфики, в случаях нехоббийного написания подобной системы Python не вытянет. Это не претензия к Python'у как таковому, как язык он хорош, но претензия к инфраструктуре исполнения и переизбытку объектов. Инфраструктура и объекты могут подъедать дефицитные ресурсы.

@sshmakov 8 янв 2018 в 10:56

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

"Использование памяти в Python" sleepingonee
Размеры объектов в байтах:

>>> sys.getsizeof(Dnk())
32
>>> sys.getsizeof(Dnk().gen)
76
>>> sys.getsizeof(Gen())
32
>>> sys.getsizeof(Gen().func)
12

Так что не так все страшно. При популяции в сотню объектов займет разве что пару десятков килобайт.

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

Теоретически — да. Практически — а зачем усложнять и замедлять расчет алгоритма аппроксимацией умножения, если операция умножения уже есть и быстро работает? ГА может ее и не использовать, если посчитает, что она не нужна.

Более сложные блоки ДНК это в ряде случаев ограничение на гибкость и лишний барьер.

Это с одной стороны. А с другой сложные блоки позволяют гораздо быстрее выработать готовый алгоритм.

Дизассемблер нужен по ряду причин: (1) эволюция — вещь основанная на случайности, и в структурированном псевдокоде можно найти мусорные фрагменты, которые не выполняют полезной работы;

Про это сказано в конце статьи "— Анализировать и упрощать полученный алгоритм, чтобы в нем оставалось только самое необходимое для получения результата."

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

Все-таки инфраструктура единая, т.к. она описана на уровне класса. Сами экземпляры содержат только данные, и этих данных немного. Кстати, поскольку экземпляры не взаимосвязаны, то ничто не мешает их обрабатывать в параллель.

Насчет ДНК высшего порядка из уже готовых блоков — мне не очень ясно зачем это нужно

Чтобы не повторяться — я на это ответил в другом комментарии.

так как мне приходилось делать подобные штуки для промышленного применения, могу сказать, что на CPU с 64ГБ RAM обработать даже популяцию в 100 особей и довести ее хотя бы до второго экстремума может занимать часы (основные затраты — оценка нового поколения), а в создаваемых системах отклик должен был исчисляться в секундах. По этим причинам в моем случае переход на параллельные вычисления был неизбежен.

Только что померил — обработка 30 особей, 30000 поколений занимает ~2.5 минуты. С накладными расходами (загрузка Python, компиляция, создание начальной популяции) чуть меньше трех минут. Python занял в памяти 6.5 Мбайт. Core i5, 2.5 ГГц, Python 3.6. Возможно, что такой результат получился из-за простого вычисления алгоритма.

И я хочу еще раз подчеркнуть — это НЕ промышленное решение, даже НЕ прототип промышленного решения, НЕ научная работа и даже НЕ учебная. Просто мне показалось, что генетический алгоритм — вещь простая и одновременно эффективная, и захотелось попробовать сделать и увидеть, как это работает и от чего зависит вероятность достижения результата. Эту цель я достиг. Буду ли я дальше развивать идею — не знаю.

@havock 8 янв 2018 в 16:57

ок, я не буду настаивать на промприменении ваших программм, но тем не менее буду держать в голове возможность их вырастания в нечто большее, чем занятие выходного дня )))

Размеры объектов в байтах:
>>> sys.getsizeof(Dnk()) 32
>>> sys.getsizeof(Dnk().gen) 76
>>> sys.getsizeof(Gen()) 32
>>> sys.getsizeof(Gen().func) 12
Так что не так все страшно. При популяции в сотню объектов займет разве что пару десятков килобайт.

Давайте считать не абсолютные размеры памяти, а посмотрим на относительные, давайте покажем отношение длины особи к количеству команд в ней )

Теоретически — да. Практически — а зачем усложнять и замедлять расчет алгоритма аппроксимацией умножения, если операция умножения уже есть и быстро работает? ГА может ее и не использовать, если посчитает, что она не нужна.

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

Это с одной стороны. А с другой сложные блоки позволяют гораздо быстрее выработать готовый алгоритм.

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

Про это сказано в конце статьи "— Анализировать и упрощать полученный алгоритм, чтобы в нем оставалось только самое необходимое для получения результата."

Я это прочитал в вашем списке дальнейших движений, но просто поделился положительным опытом.

Все-таки инфраструктура единая, т.к. она описана на уровне класса. Сами экземпляры содержат только данные, и этих данных немного. Кстати, поскольку экземпляры не взаимосвязаны, то ничто не мешает их обрабатывать в параллель.

Ничто не мешает, вы правы, но на GPU, например, память весьма ограниченная. Впрочем, это уже проблемы больше промприменения, а я их по соглашению обхожу, так что ок.

Чтобы не повторяться — я на это ответил в другом комментарии.

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

В отличие от Матери Природы у нас нет 4-х миллиардов лет и полигона испытаний в виде целой планеты.

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

Можно также добавить в ГА сравнительный анализ успешных генотипов и защищать от изменений при скрещивании последовательности генов, присутствующие в каждом из них.

Тут я уже писал, что такая защита реализована природой в виде полового разделения и увеличения нормы реакции для одного из полов. Возможно есть другие механизмы.

Можно придумать генетический алгоритм, вырабатывающий алгоритмы решения типовых элементарных задач, потом, уже на основе найденных решений, возможно после их оптимизации вручную, сделать ГА для решения более сложных задач. И так далее.

Можно, но нужно ли? Дело в том, что исчисление Чёрча и машина Тьюринга это метаструктуры, которые в принципе могут решить любую задачу решающуюся алгоритмически. И если множество ваших генов полно по Тьюрингу, то вы можете увеличивать уровни абстракции, но смысла в этом, нет никакого ведь новое множество метакоманд может не иметь полноты по Тьюрингу, ну а про гортанный нерв и автомобиль из карбюраторов я уже писал.
Но есть случай, когда такого рода абстракции могут быть полезны: это в случае, когда у вас в ваших генах-командах есть недетерминированная команда и возможно не одна. Тогда возможны специализация особей и их взаимодействие на более высоком уровне абстракции. Но про недетерминированные команды вы не писали.

Только что померил — обработка 30 особей, 30000 поколений занимает ~2.5 минуты.

Тут мы просто снова расходимся в мерах. Если считать поколениями, то — да, все неплохо. Я не считаю поколениями. Я считаю локальными экстремумами. И тот, и другой способ подсчета справедлив, но так как меня интересует результат, а не процесс, я понимаю, что даже 300 000 поколений не гарантируют прибытия в локальный минимум. Возможно, что все эти поколения это бессмысленное блуждание по гиперповерхности. Надо смотреть на ломаную эффективности самой адаптированной особи от поколения к поколению, и если она распределена в горизонтальном интервале с самого начала, то количество поколений неважно — мы никуда не пришли.

@havock 8 янв 2018 в 18:33

небольшое дополнение для снятия неопределенности: в контексте предыдущего сообщения «недетерминированная команда» — это не абсолютно недетерминированная команда, а команда недетерминированная в узком смысле, то есть недетерминированная аргументами функции-особи. Сама команда может быть вполне детерминированной вообще, но она недетерминирована для алгоритма функции-особи, так как получает данные из источника неизвестного функции-особи и данные эти ортогональны ко всем аргументам функции (вместе и по отдельности) при любых алгоритмических искривлениях пространства аргументов.

@sshmakov 8 янв 2018 в 20:10

Давайте считать не абсолютные размеры памяти, а посмотрим на относительные, давайте покажем отношение длины особи к количеству команд в ней )

Получится что-нибудь 80-150 байт на операцию.

Кстати, в ходе опытов выяснилось, что длину генотипа заранее нельзя слишком ограничивать. Когда я устанавливал длину входных значений dataLen=5, то при ограничении операций genCount=20 работающие генотипы могли создаться, а могли и не создаться, как повезет. При genCount=50 они создавались гарантированно. При dataLen=6 можно было работать с genCount=80 и выше. Хотя, как видно из статьи, конечный алгоритм содержал всего 14 операций.

В целом, я не против введения сложных команд, но только тогда, когда вы понимаете, что именно с ними лучше решать данную задачу.

С вашим тезисом про сложные команды в ГА я не готов спорить, это нужно проверять экспериментально. Но я бы хотел использовать ГА как раз в тех ситуациях, когда я не знаю, как задача решается.

Про задачу, не имеющую решения

– Г-голубчики, – сказал Фёдор Симеонович озадаченно, разобравшись в почерках. – Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал, что она н-не имеет р-решения.

– Мы сами знаем, что она не имеет решения, – сказал Хунта, немедленно ощетиниваясь. – Мы хотим знать, как её решать.

– К-как-то ты странно рассуждаешь, К-кристо… К-как же искать решение, к-когда его нет? Б-бессмыслица какая-то…

– Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица – искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен. По-моему, я напрасно начал с тобой беседовать на эту тему.

Можно, но нужно ли? Дело в том, что исчисление Чёрча и машина Тьюринга это метаструктуры, которые в принципе могут решить любую задачу решающуюся алгоритмически. И если множество ваших генов полно по Тьюрингу, то вы можете увеличивать уровни абстракции, но смысла в этом, нет никакого ведь новое множество метакоманд может не иметь полноты по Тьюрингу, ну а про гортанный нерв и автомобиль из карбюраторов я уже писал.

Извините, а откуда следуют неявные утверждения:
1. Что метакоманды должны иметь полноту по Тьюрингу? Если они задачу решают.
2. Что необходимо ограничиваться только теми командами, которые обеспечат полноту по Тьюрингу? И нельзя добавлять другие?
3. Что вместе с метакомандами не могут применяться элементарные операции?
Ведь Природе как-то до Тьюринга все равно…

Я не считаю поколениями. Я считаю локальными экстремумами.

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

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

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

@havock 8 янв 2018 в 22:58

продолжаем обсуждение )))

Получится что-нибудь 80-150 байт на операцию.

Я не считал сам как в вашем случае выходит, но если ваш подсчет верен, то это гигантское число даже для хобби. У вас, кажется, 12 команд (поправьте если ошибся), и если посчитать энтропию одной команды, то она по Шеннону равна 4-ем битам. Я не утвержаю, что одна команда в ДНК должна быть абсолютно равна энтропии, но разница между 4-мя битами и 640-ка битами (80 байт) меня чуть поседеть на заставила )))

С вашим тезисом про сложные команды в ГА я не готов спорить, это нужно проверять экспериментально. Но я бы хотел использовать ГА как раз в тех ситуациях, когда я не знаю, как задача решается.

Экспериментально можно проверить, конечно, но я построю такую модель: Используем ваши 12 команд, из которых положим, что 4 сложные (составные). Положим при мутации появление любой команды равновероятно, тогда появление любой команды 1/12. Предположим, что в идеально приспособленной особи в глобальном экстремуме должна быть последовательность из 3-х простых команд в определенной последовательности. Без учета кроссинговера, при только мутациях: вероятность возникновения этой последовательности примерно (1/12)^3=57E-5. Однако, того же результата можно добиться при использовании одной 1-ой сложной команды плюс 3 простых на коррекцию результата, вероятность возникновения такой последовательности примерно (1/12)^4=48E-6. Таким образом, правильная последовательность возникает с вероятностью примерно (1/12)^3+(1/12)^4=62E-5, а если мы уберем 4 сложные команды, то вероятность вырастает до (1/8)^3=19E-4. Согласитесь, это существенно. Понятно, что модель без учета кроссинговера, последовательного приближения к экстремуму, и с ней можно поспорить, но в целом она выглядит для меня справедливой.
За цитату спасибо, ПНС это хорошо. И тем не менее я допускаю, что могут быть ситуации, когда алгоритм целиком неизвестен, но известны составные команды, которые там точно/высоковероятно присутствуют. У нас так немалая часть физики на теории возмущений построена. Но это, конечно, не общий случай.

Извините, а откуда следуют неявные утверждения:
1. Что метакоманды должны иметь полноту по Тьюрингу? Если они задачу решают.
2. Что необходимо ограничиваться только теми командами, которые обеспечат полноту по Тьюрингу? И нельзя добавлять другие?
3. Что вместе с метакомандами не могут применяться элементарные операции?
Ведь Природе как-то до Тьюринга все равно…

Пункт 1 — мне сложно комментировать, без ухода в длинные лекции, но я постараюсь кратко: если метакоманды неполны по Тьюрингу, то может статься, что эволюционно из них решение подобрать и нельзя, отсюда вывод о решабельности задачи без полноты по Тьюрингу сомнителен, хотя и допустим к частным задачам. Но в любом случае выключая полноту по Тьюрингу мы в лучшем случае исключаем из рассмотрения множество решений, в худшем можем вообще исключить решение задачи.
Пункт 2 — можно добавлять и другие, если они недетерминированы в вышеописанном смысле. Если же добавлять детерминированные составные команды, то само множество команд становится избыточным и приводит к тем проблемам с вероятностями и, следовательно, скоростью эволюции, про которые я уже написал.
Пункт 3 — могут, но это избыточно.
Относительно взаимоотношений природы и Тьюринга: во-первых, компьютер это не совсем природа, и в компьютере Тьюрингу до природы все равно (не самому ему, конечно, но теоремам его, Чёрча, Поста, Шеннона, Гёделя и прочих отцов-основателей); а, во-вторых, может и в природе математике до природы все равно, мы тут точно не решим вопрос о том, что первичней физика или математика, но я уже вижу, что по этому вопросу позиции у нас вероятно противоположные )))

Экстремум в статье был достигнут на поколении 3200.

Ну, в данной задаче — да, но сам способ подходит для решения столь широкого круга задач, что оценивать его по частному результату… некомильфо )))

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

Совсем не соглашусь. Я полагаю для любой задачи со сходимостью стоит строить такую ломаную, чтобы она отражала прогресс.

@sshmakov 9 янв 2018 в 11:43

разница между 4-мя битами и 640-ка битами (80 байт) меня чуть поседеть на заставила )))

В наш просвещенный Век Анчоуса в таких случаях рекомендуется говорить, что ~~неуемное~~ немного большое потребление памяти программой обусловлено заложенными в нее возможностями к расширению.
А с практической точки зрения — когда память станет проблемой, тогда и будем эту проблему решать.

я построю такую модель:

Вот частный случай из статьи
вход = [1,2,3,4,5,6]
выход = [10,20,30,40,50,60]
На этом простом примере видно, что достаточно одной команды умножения на 10 каждого входного значения.

N | Стек                  |Команда
--|-----------------------|--------
1 |                       |push
2 | 1                     |mul 10 
3 | 10                    |pop

А если этой команды нет?
Тогда придется сделать примерно такой набор операций

N | Стек                  |Команда
--|-----------------------|--------
1 |                       |push
2 | 1                     |dup 
3 | 1,1                   |dup
4 | 1,1,1                 |dup
5 | 1,1,1,1               |dup
6 | 1,1,1,1,1             |dup
7 | 1,1,1,1,1,1           |dup
8 | 1,1,1,1,1,1,1         |dup
9 | 1,1,1,1,1,1,1,1       |dup
10| 1,1,1,1,1,1,1,1,1     |dup
11| 1,1,1,1,1,1,1,1,1,1   |add
12| 1,1,1,1,1,1,1,1,2     |add
13| 1,1,1,1,1,1,1,3       |add
14| 1,1,1,1,1,1,4         |add
15| 1,1,1,1,1,5           |add
16| 1,1,1,1,6             |add
17| 1,1,1,7               |add
18| 1,1,8                 |add
19| 1,9                   |add
20| 10                    |pop

То есть если умножением не пользоваться, то минимально (не считая первую и последнюю команды) придется использовать 18 команд. Вероятность появления именно такой последовательности 3,75e-20. С учетом возможных перестановок менее (я точно не считал) 9,8е-15.
При другом значении множителя (a-1)*2 команд. А при нецелочисленном умножении?

Согласитесь, это существенно.

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

Если мы создаем ГА, не имея в виду даже класс задач, который он будет решать, то верно, конечно. Потому что одной из будущих задач может быть — «восстанови-ка себя сам».
На практике же мы примерно представляем, что собираемся решать и «восстанови-ка себя сам» в круг наших задач обычно не входит.

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

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

Ну, в данной задаче — да, но сам способ подходит для решения столь широкого круга задач, что оценивать его по частному результату… некомильфо )))

Как-то ведь оценить надо было… А плохая оценка лучше, чем совсем никакой.

@S_A 9 янв 2018 в 13:11

Немного вклинюсь, если не возражаете.

Полнота по Тьюрингу нужна если нужно вычислять некий интуитивно-вычислимый алгоритм (это про тезис Черча). Подавляющее большинство программ, с котрыми мы имеем дело, несмотря на то что написаны на Тьюринг-полных языках, работают за конечное время (рекурсивны).

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

Генетечиский алгоритм — поиск способа, может и не всегда оптимального, но тем не менее как-то решающего задачу. И так как «нет бесплатных обедов», нет и смысла чистить задачу от производных методов оптимизации.

@havock 9 янв 2018 в 18:00

возражаю )))
Тезис Чёрча штука интересная, но весьма умозрительная. Я даже сказал бы, что я с этим тезисом не согласен. То, что у нас многое хорошо реализуется рекурсивно это любопытно, но ставить знак эквивалентности между вычислимостью и рекурсивностью, мне видится весьма смелым утвержением.

Подавляющее большинство программ, с котрыми мы имеем дело, несмотря на то что написаны на Тьюринг-полных языках, работают за конечное время (рекурсивны).

Вот тут я не понял. Я не уловил, почему "несмотря на то что написаны на Тьюринг-полных языках, работают за конечное время"? Полнота по Тьюрингу разве ограничивает возможность или снижает вероятность остановки программы? Да вроде нет. И вообще, у нас масса программ, которые не останавливаются никогда, если пользователь им не скажет, я бы даже скзал, что таких большинство. Большинство программ запущены и работают пока пользователь их не завершит, если команды завершения не поступило большинство программ будет работать до обесточивания или поломки компьютера. )))

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

Это мне даже сложно комментировать, в свете того, что я уже написал. Чем больше словарь тем лучше сходимость? я вот за представил, как нужна операция инкремента на единицу, в словаре 1 000 000 команд, вероятность мутации на этот инкремент 1e-6, но зато, у нас много запчастей и в итоге инкремент на единицу реализуется через серию возведений в степень, делений, и вычислений суперкорней и логарифмов. Кул, машина с колесам из карбюраторов.
Может у меня плохое чувство юмора и я шутку не понял? )))

@S_A 11 янв 2018 в 12:39

Теперь моя очередь не понимать. Полнота по Тьюрингу гарантирует возможность наличия частично-рекурсивного алгоритма. Я нигде не эквивалентил вычислимость как таковую с только рекурсивным множеством алгоритмов (или его надмножеством с конечным временем выполнения).

Что касается конечного времени. Ожидание ввода, любой поллинг внешних данных — это не алгоритм, а операция. И где-то в недрах while (true) { /* любого веб-сервера */ } есть break; Это означает что где-то на ленте машины Тьюринга все же есть та единица, по которой этот веб-сервер выйдет.

Насчет 1 000 000 команд и прочего — бесплатных обедов нет, я уже писал. Поэтому частные оптимизации выкидывать не имеет смысла.

@havock 11 янв 2018 в 16:33

Полнота по Тьюрингу гарантирует возможность наличия частично-рекурсивного алгоритма.

В принципе, можно сказать, что это утвержение верно, но сформулировано некорректно. Полнота по Тьюрингу не гарантирует наличие алгоритма. Алгоритм либо есть, либо нет. Это вопрос вычислимости. Полнота по Тьюрингу это свойство языка или множества операций, говорящее о том, что на этом языке (с этим множеством) можно составить любой алгоритм.

Я нигде не эквивалентил вычислимость как таковую с только рекурсивным множеством алгоритмов

Вы нет, но вы сослались на тезис Чёрча, а он именно такую эквивалентность и провозглашает. Я с этим не согласен. Это потрынделки вилами на воде. И еще, фраза «рекурсивное множество алгоритмов» поражает своей неопределенностью и заставляет фантазию просто плясать ))). Правильно говорить «множество рекурсивных алгоритмов».

рекурсивным множеством алгоритмов (или его надмножеством с конечным временем выполнения).

А почему вы считаете, что множество рекурсивных алгоритмов это подмножество алгоритмов с конечным временем исполнения? Это бред. Вы никогда не видели бесконечного цикла или бесконечной рекурсии?

Что касается конечного времени. Ожидание ввода, любой поллинг внешних данных — это не алгоритм, а операция. И где-то в недрах while (true) { /* любого веб-сервера */ } есть break; Это означает что где-то на ленте машины Тьюринга все же есть та единица, по которой этот веб-сервер выйдет.

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

Насчет 1 000 000 команд и прочего — бесплатных обедов нет, я уже писал. Поэтому частные оптимизации выкидывать не имеет смысла.

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

@havock 12 янв 2018 в 00:41

Небольшое дополнение, вы в предложении:

Я нигде не эквивалентил вычислимость как таковую с только рекурсивным множеством алгоритмов (или его надмножеством с конечным временем выполнения).

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

@S_A 12 янв 2018 в 05:12

Вы уж извините, но вы что-то не то пишите. Совсем. Я может где-то не до конца формален в формулировках, но вы либо целенаправленно тут воду мутите, либо непонятно что.

Множество рекурсивных алгоритмов (функций) — это не программисткая рекурсия. Дальше нить я теряю. В любом случае посмотрите No Free Lunch-теорему.

@havock 12 янв 2018 в 06:00

Мда. А при чем тут NFL вообще?
Это риторический вопрос. Отвечать на него не обязательно.
Вы либо тролль, либо у вас одновременно две проблемы:
1. Вы не понимаете, что я пишу.
2. Вы не понимаете, что сами пишите.
Поэтому предлагаю завершить обсуждение. )))

@havock 9 янв 2018 в 17:34

давайте, давайте продолжим )))

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

Это началась идеология. Собственно, смысл фразы даже комментировать не хочется, потому что это, на мой взгляд, потребительство в одном из худших его видов. ))) А вот если кустарный образец отличается от промышленного по какой-то характеристике на более чем 2 порядка, тут есть над чем подумать. )))

Вот частный случай из статьи
вход = [1,2,3,4,5,6]
выход = [10,20,30,40,50,60]
На этом простом примере видно, что достаточно одной команды умножения на 10 каждого входного значения.

Эм… Вы, честно говоря, меня сейчас реально в тупик поставили. Я вот правильно понял, что вы мне хотите показать пример поиска алгоритма состоящего из одного гена? То есть, это ситуация, когда у вас весь алгоритм в одной команде. Проводя аналогии с природой, это было бы забавно строить леопарда из леопарда и зайчиков. В принципе надо просто подождать пока зайчики отвалятся, где-то на втором-третьем поколении )))

А если этой команды нет?
Тогда придется сделать примерно такой набор операций

Можно и так, но это проблема вашей стековой машины. В командах 'pop', 'push', 'dup', 'addVal', 'delVal', 'mulVal', 'divVal', 'addMem', 'delMem', 'mulMem', 'divMem', 'const' нет ничего похожего на условия, или циклы, или рекурсию. Поэтому у вас умножение и разворачивается в эту непотребщину. А вот если вы выкините операции умножения-деления, и поставите вместо них «начало цикла-конец цикла», к примеру, или «начало блока рекурсии-конец блока рекурсии», или условный переход, то у вас умножение появится само собой. При некоторых ограничениях, всю арифметику можно сделать из операций инкремент-декремент-рекурсия. Такая структура не будет останавливаться, но будет выполнять все прямые гипероператоры. И реализации всего этого будут очень коротки относительно того, что предлагаете вы. Просто результат придется забирать напрямую из памяти при исполняющейся структуре. Вы вот Тьюринга природой попрекали, а в природе 4-5 нуклеотидов, и из них вырастают и работают леопарды в том числе ))) Можно, конечно, сослаться на сложность правил исполнения, но тем не менее.

Если мы создаем ГА, не имея в виду даже класс задач, который он будет решать, то верно, конечно. Потому что одной из будущих задач может быть — «восстанови-ка себя сам».
На практике же мы примерно представляем, что собираемся решать и «восстанови-ка себя сам» в круг наших задач обычно не входит.

Что такое классы задач? Вы имеете в виду классы сложности или вычислимые-невычислимые? Или другую классификацию? Эволюционный алгоритм для того и придуман чтобы генерировать алгоритмы задач, метод решения которых неизвестен. Процитирую вас же:

А что, если...? Если заставить ГА не оптимизировать параметры, а создавать другой алгоритм, наиболее подходящий для данной задачи. Вот этим я и занимался ради интереса.

А коэффициенты полинома можно и другими более дешевыми методами подбирать, вы и сами об этом написали. И насчет «восстанови-ка себя сам», есть широчайшее множество задач, которые звучат, если не конкретно так, то весьма похоже, например, задача о допустимости запуска данного кода на данной машине. И фактически — да, наивно эта задача решается тем, что машина создает внутри себя такую же машину, затем запускает недоверенный код и оценивает состояние своей копии. И такие задачи на анализ автоматом самого себя при некоторых условиях не редкость, а относительно часто возникающая ситуация, по крайней мере, в моей практике.

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

Это проблема оптимизации конкретно вашей стековой машины, но не самого эволюционного подхода. И не могу не напомнить, что опыт опытом, но у нас тут не физика, а математика ))) Просто производители процессоров сделали финт ушами, и умножение машинного слова производится за условный один такт процессора. Это хорошо, но в общем смысле это костыль для проведения часто используемой операции. Если вы посмотрите как выполняется умножение не машинных слов (например в GMP), то удивитесь как много там интересного ))) Резюмируя по данному пункту: быстрота вашей стековой машины обусловлена частным случаем среды исполнения, но если вы действительно ищете алгоритм, то вам не стоит опираться на оптимизацию конкретной среды исполнения. Не ставьте вашу эволюцию в зависимость от типа процессора.

З.Ы. Я ценю ваш интерес к данной теме, но у меня ощущение, что через несколько сообщений нам придется углубиться с одной стороный в матлогику, с другой в оптимизации операций на конкретных архитектурах. Дабы этого избежать, я порекомендовал бы вам внимательно изучить работы Клини, он хорошо обобщил обсуждаемые тут вопросы, с упором на Чёрча, но эволюционный подход можно реализовывать и по Тьюрингу, и по Чёрчу, так как рассматривают они одно и то же с разных точек зрения.

@sshmakov 9 янв 2018 в 19:21

Эм… Вы, честно говоря, меня сейчас реально в тупик поставили. Я вот правильно понял, что вы мне хотите показать пример поиска алгоритма состоящего из одного гена? То есть, это ситуация, когда у вас весь алгоритм в одной команде.

Кто еще кого в тупик поставил… На этом примере вся статья вообще-то построена.

А вот если вы выкинете операции умножения-деления, и поставите вместо них «начало цикла-конец цикла», к примеру, или «начало блока рекурсии-конец блока рекурсии», или условный переход, то у вас умножение появится само собой.

Я пока не решил, буду ли я развивать ГА в эту сторону. Пока я обдумываю другие идеи.

Просто результат придется забирать напрямую из памяти при исполняющейся структуре.

Стековая машина более перспективна как раз потому, что на ГА возлагается ответственность за выдачу результата, и ГА выдает результат только тогда, когда готов.

Что такое классы задач? Вы имеете в виду классы сложности или вычислимые-невычислимые? Или другую классификацию?

Нет, ничего из этого. Попробую сказать другими словами.
Сначала у нас появляется Задача, которую надо решить, затем мы делаем ГА для решения этой задачи. А не наоборот.

Это проблема оптимизации конкретно вашей стековой машины, но не самого эволюционного подхода.

Разве моей? Ведь это ваши слова "основные затраты — оценка нового поколения" и 0decca "code bloat (неконтролируемый рост кода), сложность с циклами (много зависающих программ, которые сжирают все ресурсы), общая затратность выполнения".

Мое понимание ситуации — не надо пытаться сделать из ГА компьютер, надо дать ему возможность решать, то, что он может решать. Кстати, спасибо вам и 0decca, я теперь знаю, что нужно учесть и так не делать.

И не могу не напомнить, что опыт опытом, но у нас тут не физика, а математика )))

Увы, я не математик и им уже не стану. А опыты ставить интересно.

@havock 9 янв 2018 в 20:15

Кто еще кого в тупик поставил… На этом примере вся статья вообще-то построена.

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

Я пока не решил, буду ли я развивать ГА в эту сторону. Пока я обдумываю другие идеи.

Другие? Поделитесь? В контексте того, что уже сделано я не вижу более важной задачи, чем расширение до тьюринговской полноты. Фактически сейчас у вас не генератор алгоритмов, а генератор формул, и в этом генераторе явно недостает некоторых символов.

Стековая машина более перспективна как раз потому, что на ГА возлагается ответственность за выдачу результата, и ГА выдает результат только тогда, когда готов.

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

Нет, ничего из этого. Попробую сказать другими словами.
Сначала у нас появляется Задача, которую надо решить, затем мы делаем ГА для решения этой задачи. А не наоборот.

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

Разве моей? Ведь это ваши слова «основные затраты — оценка нового поколения» и 0decca «code bloat (неконтролируемый рост кода), сложность с циклами (много зависающих программ, которые сжирают все ресурсы), общая затратность выполнения».

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

Мое понимание ситуации — не надо пытаться сделать из ГА компьютер, надо дать ему возможность решать, то, что он может решать.

Ошибочное понимание. Генетическая генерация кода именно и предполагает, что вы делаете кучу маленьких простых компьютеров и смотрите какой алгоритм лучше исполняется. И в том то и особенность генетической генерации алгоритмов, что при правильном исполнении он может найти алгоритм для любой вычислимой задачи или его приближение в дискретной среде.

Кстати, спасибо вам и 0decca, я теперь знаю, что нужно учесть и так не делать.

Не за что, это было интересное обсуждение.

Увы, я не математик и им уже не стану. А опыты ставить интересно.

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

@sshmakov 9 янв 2018 в 21:11

Поделитесь?

Может быть. Рано еще. Я пока читаю ссылки из этого поста "Добро пожаловать в эру глубокой нейроэволюции" atepeq

Забавно читать это от человека с программированием, машинным обучением и компьютерным зрением в интересах и реализованной стековой машиной.

Не путайте Божий дар с яичницей.

@JediPhilosopher 7 янв 2018 в 17:24

Я когда-то писал статью про использование генетического алгоритма для оптимизации кода. https://habrahabr.ru/post/265195/ У меня там брался кусок из нескольких ассемблерных инструкций (пробовал варианты с байткодом джавы, ассемблером х86 и шейдерным ассемблером), тасовались генетикой и получали оптимизированную формулу. Можно было оптимизировать по длине или по времени выполнения, иногда находило интересные варианты оптимизации математических формул, до которых я сам вручную бы не додумался.
Но на практике оказалось по сути бесполезно, слишком сложно измерить эффект от таких микрооптимизаций.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий