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

    Паркер: А чем Вы занимаетесь в выходные?

    В типичной реализации генетический алгоритм оперирует параметрами какой-то сложной функции (диофантовые уравнения в статье "Генетический алгоритм. Просто о сложном" mrk-andreev) или алгоритма ("Эволюция гоночных автомобилей на JavaScript" ilya42). Количество параметров неизменно, операции над ними тоже изменить невозможно, как генетика не старается, потому что они заданы нами.

    Хьюстон, у нас проблема


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

    Часто, а в последнее время и модно, вместо детерминированного алгоритма использовать нейронную сеть. Тут у нас тоже открывается широчайший выбор (FNN, CNN, RNN, LTSM, ...), но проблема остается той же — выбрать нужно правильно. Согласно Википедии "Выбирать тип сети следует, исходя из постановки задачи и имеющихся данных для обучения".

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


    Генотип из операций


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

    Так вот, идея в том, что «геном» будет элементарная операция, а «генотипом» — алгоритм, составленный из этих операций. Например, генотип, составленный из математических операций и реализующий функцию $f(x)=e^{(\frac{3x + 20}{0.34}) ^ 2}$:

    x3 | +20 | /0.34 | ^2 | e^x

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

    Скрещивание фактически не меняется, новый генотип получает кусочки от каждого родителя.

    Мутацией может быть замена одного из генов на какой-либо другой, то есть происходит замена одной операции в алгоритме и/или изменение параметров этой операции.

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


    Кстати, у машинок критерий был один, но работал он только в пределах текущей трассы. Лучшая для одной трассы машинка вряд ли оказалась бы лучшей на другой.

    А если подумать?


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

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

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

    Просто do it!


    Получился такой объект, реализующий один ген.

    Объект Gen
    class Gen():
        func = 0
        param = ()
        def __init__(self):
            super().__init__()
            self.func = random.randint(0,7)
            self.param = round(random.random()*2-1,2)
    
        def calc(self, value, mem):
            if self.func == 0: # push
                mem.append(value + self.param)
                return (None, 1)
            elif self.func == 1: # pop
                return (mem.pop() + self.param, 0)
            elif self.func == 2: # dup
                mem.append(mem[-1] + self.param)
                return (None, 0)
            elif self.func == 3: # add
                mem.append(mem.pop() + value + self.param)
                return (None, 1)
            elif self.func == 4: # del
                mem.append(mem.pop() - (value + self.param))
                return (None, 1)
            elif self.func == 5: # mul
                mem.append(mem.pop() * (value + self.param))
                return (None, 1)
            elif self.func == 6: # div
                mem.append(mem.pop() / (value + self.param))
                return (None, 1)
            return (self.params, 0)
    
        def funcName(self, func):
            if self.func >= 0 and self.func <= 7:
                return [
                    'push',
                    'pop',
                    'dup',
                    'add',
                    'del',
                    'mul',
                    'div',
                    'const'][func]
            return str(func)
        
        def __str__(self):
            return "%s:%s" % (self.funcName(self.func), str(self.param))
    

    Это был первый вариант, в принципе рабочий, но с ним быстро выявилась проблема — для арифметических операций требовалось передавать значение, а для операций на стеке pop и dup — нет. Мне не хотелось различать вызываемые операции в вызывающем коде и определять, сколько нужно параметров передавать каждой из них, поэтому переделал — вместо одного значения value передавал массив входных значений, и пусть сама операция делает с ним что хочет.

    Объект Gen v.2
    class Gen():
        func = 0
        param = ()
        def __init__(self):
            super().__init__()
            self.func = random.randint(0,7)
            self.param = round(random.random()*2-1,2)
    
        def calc(self, values, mem):
            if self.func == 0: # pop
                return mem.pop() + self.param
            elif self.func == 1: # push
                mem.append(values.pop() + self.param)
                return None
            elif self.func == 2: # dup
                mem.append(mem[-1] + self.param)
                return None
            elif self.func == 3: # add
                mem.append(mem.pop() + values.pop() + self.param)
                return None
            elif self.func == 4: # del
                mem.append(mem.pop() - (values.pop() + self.param))
                return None
            elif self.func == 5: # mul
                mem.append(mem.pop() * (values.pop() + self.param))
                return None
            elif self.func == 6: # div
                mem.append(mem.pop() / (values.pop() + self.param))
                return None
            return self.param
    
        def funcName(self, func):
            if self.func >= 0 and self.func <= 7:
                return [
                    'pop',
                    'push',
                    'dup',
                    'add',
                    'del',
                    'mul',
                    'div',
                    'const'][func]
            return str(func)
        
        def __str__(self):
            return "%s:%s" % (self.funcName(self.func), str(self.param))
    

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

    Ниже последняя версия.

    Объект Gen v.8
    class Gen():
        func = 0
        param = ()
        def __init__(self, func=None):
            super().__init__()
            if func is None:
                funcMap = [0,1,2,3,4,5,6,7,8,9,10,11]
                i = random.randint(0,len(funcMap)-1)
                func = funcMap[i]
            self.func = func
            self.param = round((random.random()-0.5)*10,2)
    
        def calc(self, values, mem):
            def getVal():
                v = values[0]
                values[0:1]=[]
                return v
            if self.func == 0: # pop
                return mem.pop()
            elif self.func == 1: # push
                mem.append(getVal())
                return None
            elif self.func == 2: # dup
                mem.append(mem[-1] + self.param)
                return None
            elif self.func == 3: # addVal
                mem.append(getVal() + self.param)
                return None
            elif self.func == 4: # delVal
                mem.append(getVal() + self.param)
                return None
            elif self.func == 5: # mulVal
                mem.append(getVal() * self.param)
                return None
            elif self.func == 6: # divVal
                mem.append(getVal() / self.param)
                return None
            elif self.func == 7: # addMem
                mem.append(self.param + mem.pop())
                return None
            elif self.func == 8: # delMem
                mem.append(self.param - mem.pop())
                return None
            elif self.func == 9: # mulMem
                mem.append(self.param * mem.pop())
                return None
            elif self.func == 10: # divMem
                mem.append(self.param / mem.pop())
                return None
            mem.append(self.param)
            return None
    
        def funcName(self, func):
            funcNames = (
                'pop',
                'push',
                'dup',
                'addVal',
                'delVal',
                'mulVal',
                'divVal',
                'addMem',
                'delMem',
                'mulMem',
                'divMem',
                'const')
            if self.func >= 0 and self.func < len(funcNames):
                return funcNames[func]
            return str(func)
        
        def __str__(self):
            return "%s:%s" % (self.funcName(self.func), str(round(self.param,4)))
    

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

    Объект Dnk
    class Dnk:
        gen = []
        level = 0
        def __init__(self, genlen=10):
            super().__init__()
            self.gen = [ Gen(1), Gen(1) ] + [ Gen() for i in range(genlen-2) ]
            
        def copy(self, src):
            self.gen = src.gen
    
        def __mul__(self, other):
            divider = 2
            def sel():
                v = random.random()*(self.level + other.level)
                return v <=self.level
            mode = random.randint(0,3)
            minLen = min(len(self.gen), len(other.gen))
            maxLen = max(len(self.gen), len(other.gen))
            n = Dnk()
            if mode == 0:
                n.gen = [ self.gen[i] if sel() else other.gen[i] for i in range(minLen) ]
            elif mode == 1:
                n.gen = [ Gen() for i in range(minLen) ]
                for g in n.gen:
                    g.param += round((random.random()-0.5)/divider,3)
            elif mode == 2:
                n.gen = [ self.gen[i-1] if i % 2 == 1 else other.gen[i] for i in range(minLen) ]
                for g in n.gen:
                    g.param += round((random.random()-0.5)/divider,3)
            else:
                v = random.randint(0,1)
                n.gen = [ self.gen[i] if i % 2 == v else other.gen[-1-i] for i in range(minLen) ]
                for g in n.gen:
                    g.param += round((random.random()-0.5)/divider,3)
            n.gen = n.gen + [ Gen() for i in range(minLen,maxLen) ]
            return n
    
        def calc(self, values):
            res = []
            mem = []
            varr = values.copy()
            i = 0
            for g in self.gen:
                try:
                    r = g.calc(varr, mem)
                    i = i + 1
                except:
                    self.gen = self.gen[0:i]
                    #raise
                    break;
                if not r is None:
                    res.append(r)
            return res
    
        def __str__(self):
            return  '(' + ', '.join([ str(g) for g in self.gen ]) + '):'+str(round(self.level,2))
    

    Для обоих классов переопределен метод __str__, чтобы выводить их содержимое в консоль.

    Функция просчета алгоритма чуть подробнее:

        def calc(self, values):
            res = []
            mem = []
            varr = values.copy()
            i = 0
            for g in self.gen:
                try:
                    r = g.calc(varr, mem)
                    i = i + 1
                except:
                    self.gen = self.gen[0:i]
                    #raise
                    break;
                if not r is None:
                    res.append(r)
            return res
    

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

    Итак, есть генотип, есть словарь генов, есть функция скрещивания двух генотипов. Можно проверить:

    >>> a = Dnk()
    >>> b = Dnk()
    >>> c = a * b
    >>> print(a)
    (push:4.061, push:1.79, dup:-4.32, mulMem:3.6, push:-3.752, addVal:2.4, delVal:-1.863, delMem:4.06, delVal:-3.692, addMem:0.48):0
    >>> print(b)
    (push:0.356, push:-4.8, pop:2.865, delVal:1.53, addMem:-2.853, mulVal:-1.6, const:-2.451, delVal:-2.53, divVal:4.424, delMem:-0.6):0
    >>> print(c)
    (push:4.061, divVal:4.424, dup:-4.32, const:-2.451, push:-3.752, addMem:-2.853, delVal:-1.863, pop:2.865, delVal:-3.692, push:0.356):0
    >>> 

    Теперь нужны функции размножения (отбор и скрещивание лучших) и мутации.
    Функции скрещивания и размножения генотипов до необходимого количества я написал в трех вариантах. Но худшая половина погибает в любом случае.

    # Скрещивание любой с любым из первой половины
    def mixIts(its, needCount):
        half = needCount // 2
        its[half:needCount] = []
        nIts = []
        l = min(len(its), half)
        ll = l // 2
        for ii in range(half,needCount):
            i0 = random.randint(0,l-1)
            i1 = random.randint(0,l-1)
            d0 = its[i0]
            d1 = its[i1]
            nd = d0 * d1
            mutate(nd)
            its.append(nd)
    
    # Скрещивание родителя из первой четверти с родителем из второй четверти
    def mixIts2(its, needCount):
        half = needCount // 2
        its[half:needCount] = []
        nIts = []
        l = min(len(its), half)
        ll = l // 2
        for ii in range(half,needCount):
            i0 = random.randint(0,ll-1)
            i1 = random.randint(ll,l-1)
            d0 = its[i0]
            d1 = its[i1]
            nd = d0 * d1
            mutate(nd)
            its.append(nd)
        
    # Скрещивание родителя из первой восьмой части с родителем из второй восьмой
    def mixIts3(its, needCount):
        half = needCount // 2
        its[half:needCount] = []
        nIts = []
        l = min(len(its), half)
        ll = l // 4
        for ii in range(half,needCount):
            i0 = random.randint(0,ll-1)
            i1 = random.randint(ll,ll*2-1)
            d0 = its[i0]
            d1 = its[i1]
            nd = d0 * d1
            mutate(nd)
            its.append(nd)
    

    Функция мутации применяется к новому генотипу

    def mutate(it):
        # Три пары генов меняем местами
        listMix = [
            (random.randint(0,len(it.gen)-1), random.randint(0,len(it.gen)-1))
            for i in range(3) ]
        for i in listMix:
            it.gen[i[0]], it.gen[i[1]] = (it.gen[i[1]], it.gen[i[0]])
        # Три гена совсем новых,случайных
        for i in [ random.randint(0,len(it.gen)-1) for i in range(3) ]:
            it.gen[i] = Gen()
        # У одного гена меняем параметр случайным образом
        for i in [ random.randint(0,len(it.gen)-1) for i in range(1) ]:
            it.gen[i].param = it.gen[i].param + (random.random()-0.5)*2
    

    Как можно применить такой генетический алгоритм?
    Например:
    — выявлять закономерность среди входных данных, регрессионный анализ
    — выработать алгоритм, восстанавливающий выпадения в сигнале и убирающий помехи — полезно для речевой связи
    — разделять сигналы, пришедшие от разных источников по одному каналу — полезно для голосового управления, создания псевдостерео

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

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

    # Длина массива входных и выходных данных
    dataLen = 6
    # Размер популяции
    itCount = 100
    # Начальная длина генотипа
    genLen = 80
    # Максимальное количество поколений
    epochCount = 100
    
    srcData = [ i+1 for i in range(dataLen) ]
    
    def getIts(dest = 0):
        its = [ Dnk(genLen) for i in range(itCount) ]
        res = []
        for epoch in range(epochCount):
            nIts = []
            maxAchiev = 0
            for it in its:
                try:
                    res = it.calc(srcData)
                    achiev = len(res)
                    if achiev == 0:
                        it = None
                        continue
                    maxAchiev = max(maxAchiev, achiev)
                    it.level = achiev
                    nIts.append(it)
                except:
                    # print('Died',it[0],sys.exc_info()[1])
                    it = None
            its = nIts
            l = len(its)
            if l<2:
                print("Low it's count:",l)
                break;
            # отсортируем так, чтобы лучшие оказались первыми
            its.sort(key = lambda it: -it.level)
            if maxAchiev >= dataLen:
                break;
            mixIts(its, itCount)
        for it in its[:]:
            if it.level<dest:
                its.remove(it)
        return its
    

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

    def diffData(resData, srcData):
        # Если длина результата не верна, то не имеет смысла считать результат
        if len(resData) != len(srcData):
            return None
        d = 0
        for i in range(len(resData)):
            d = d + abs((len(resData)*30 - i) * (resData[i] - srcData[i]))
        return d
    

    Ну и последний штрих — собственно ГА на отобранных генотипах.

    # Размер популяции
    bestCount = 30
    # Максимальное количество поколений
    globCount = 30000
    # Ищем генотип, на котором отклонение будет меньше этой цифры
    seekValue = 8000
    
    its = []
    while len(its)<bestCount:
        its = its + getIts(len(destData))
        print('Its len', len(its))
    # Показать, с какого результата начинаем
    printIts(its[0:1], srcData)
    its[bestCount:len(its)]=[]
    for glob in range(globCount):
        minD = None
        for it in its[:]:
            resData = it.calc(srcData)
            d = diffData(resData, destData)
            # Если результат совсем плохой, то отбраковываем этот генотип.
            if d is None:
                its.remove(it)
                continue
            # Из значения отклонения получаем значение приспособленности генотипа
            it.level = 100000 - d
            minD = d if minD is None else min(d, minD)
        its.sort(key = lambda it: -it.level)
        if glob % 100 == 0 or glob == globCount - 1:
            # Вывести текущий прогресс, выводим на каждый 100-й раз
            print('glob', glob, ':', round(minD,3) if minD else 'None', len(its)) #, resData)
        if minD < seekValue:
            print('Break')
            break
        mixIts2(its, bestCount)
    
    # Вывести лучшие три результата
    printIts(its[0:3], srcData)
    


    Результат
    ...
    glob 2900 : 7067.129 18
    glob 3000 : 4789.967 15
    glob 3100 : 6791.239 17
    glob 3200 : 6809.478 15
    Break
    16
    0 (const:24.7735, addMem:1.7929, dup:39.1318, dup:-15.2363, mulVal:24.952, mulVal:4.7857, pop:14.4176, pop:19.8343, dup:-19.4728, pop:2.6658, dup:-14.8237, pop:6.7005, pop:1.3567, pop:-2.7399):97009.88 => [9.571, 24.952, 30.989, 35.638, 50.462, 65.698]
    1 (const:24.7735, dup:-4.8988, dup:39.1318, dup:-4.3082, mulVal:24.952, mulVal:6.1096, pop:14.4176, pop:19.8343, dup:-19.4728, pop:2.6658, dup:-14.8237, pop:6.7005, pop:1.3567, pop:-2.7128):96761.03 => [12.219, 24.952, 35.226, 39.875, 54.698, 59.007]
    2 (const:24.7735, addMem:1.7929, dup:39.1318, dup:-15.2363, mulVal:24.952, delVal:3.4959, pop:14.4176, pop:19.8343, dup:-19.4728, pop:2.6658, dup:-14.8237, pop:6.7005, pop:1.3567, pop:-2.7399):96276.27 => [5.496, 24.952, 30.989, 35.638, 50.462, 65.698]
    >>> 

    Или, проще говоря, лучший результат ГА с целью destData = [10, 20, 30, 40, 50, 60] получился [9.571, 24.952, 30.989, 35.638, 50.462, 65.698]. Этого результата добивается генотип с алгоритмом (const:24.7735, addMem:1.7929, dup:39.1318, dup:-15.2363, mulVal:24.952, mulVal:4.7857, pop:14.4176, pop:19.8343, dup:-19.4728, pop:2.6658, dup:-14.8237, pop:6.7005, pop:1.3567, pop:-2.7399).

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

    Что дальше?


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

    Подробнее
    Реклама

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

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

      Да, область называется en.wikipedia.org/wiki/Genetic_programming
      Там много подводных камней на самом деле.
        0
        Вот спасибо! Я даже себе не могу объяснить, почему не нашел ваши ссылки раньше.
          +4
          Я учил эту область по многотомнику John Koza в начале нулевых или даже в конце 90-х — для трейдинговых систем.
          Вот этот человек:
          www.genetic-programming.com/johnkoza.html

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

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

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

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

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

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

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

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

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

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

              PS
              Вот интересная штука на базе генетики, которая считалась копролитом, потом воскресала, потом опять забывалась — несколько раз подряд.
              en.wikipedia.org/wiki/Learning_classifier_system
        +1
        Тоже баловался подобным (в прошлом году), но на 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
        
        


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

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

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

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

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

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

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

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

                    "Использование памяти в 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. Возможно, что такой результат получился из-за простого вычисления алгоритма.

                    И я хочу еще раз подчеркнуть — это НЕ промышленное решение, даже НЕ прототип промышленного решения, НЕ научная работа и даже НЕ учебная. Просто мне показалось, что генетический алгоритм — вещь простая и одновременно эффективная, и захотелось попробовать сделать и увидеть, как это работает и от чего зависит вероятность достижения результата. Эту цель я достиг. Буду ли я дальше развивать идею — не знаю.
                      +1
                      ок, я не буду настаивать на промприменении ваших программм, но тем не менее буду держать в голове возможность их вырастания в нечто большее, чем занятие выходного дня )))
                      Размеры объектов в байтах:
                      >>> 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 поколений не гарантируют прибытия в локальный минимум. Возможно, что все эти поколения это бессмысленное блуждание по гиперповерхности. Надо смотреть на ломаную эффективности самой адаптированной особи от поколения к поколению, и если она распределена в горизонтальном интервале с самого начала, то количество поколений неважно — мы никуда не пришли.
                        0
                        небольшое дополнение для снятия неопределенности: в контексте предыдущего сообщения «недетерминированная команда» — это не абсолютно недетерминированная команда, а команда недетерминированная в узком смысле, то есть недетерминированная аргументами функции-особи. Сама команда может быть вполне детерминированной вообще, но она недетерминирована для алгоритма функции-особи, так как получает данные из источника неизвестного функции-особи и данные эти ортогональны ко всем аргументам функции (вместе и по отдельности) при любых алгоритмических искривлениях пространства аргументов.
                          0
                          Давайте считать не абсолютные размеры памяти, а посмотрим на относительные, давайте покажем отношение длины особи к количеству команд в ней )

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

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

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

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

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

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

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


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

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

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

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

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

                          Это да, но не для этой задачи, поскольку она искусственная, и имеет практически бесконечное число равновероятных и почти одинаковых по сложности решений.
                            0
                            продолжаем обсуждение )))
                            Получится что-нибудь 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.
                            Ну, в данной задаче — да, но сам способ подходит для решения столь широкого круга задач, что оценивать его по частному результату… некомильфо )))
                            Это да, но не для этой задачи, поскольку она искусственная, и имеет практически бесконечное число равновероятных и почти одинаковых по сложности решений.
                            Совсем не соглашусь. Я полагаю для любой задачи со сходимостью стоит строить такую ломаную, чтобы она отражала прогресс.
                              0
                              разница между 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 команд. А при нецелочисленном умножении?
                              Согласитесь, это существенно.

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

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

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

                              Как-то ведь оценить надо было… А плохая оценка лучше, чем совсем никакой.
                                +1
                                Немного вклинюсь, если не возражаете.

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

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

                                Генетечиский алгоритм — поиск способа, может и не всегда оптимального, но тем не менее как-то решающего задачу. И так как «нет бесплатных обедов», нет и смысла чистить задачу от производных методов оптимизации.
                                  0
                                  возражаю )))
                                  Тезис Чёрча штука интересная, но весьма умозрительная. Я даже сказал бы, что я с этим тезисом не согласен. То, что у нас многое хорошо реализуется рекурсивно это любопытно, но ставить знак эквивалентности между вычислимостью и рекурсивностью, мне видится весьма смелым утвержением.
                                  Подавляющее большинство программ, с котрыми мы имеем дело, несмотря на то что написаны на Тьюринг-полных языках, работают за конечное время (рекурсивны).
                                  Вот тут я не понял. Я не уловил, почему "несмотря на то что написаны на Тьюринг-полных языках, работают за конечное время"? Полнота по Тьюрингу разве ограничивает возможность или снижает вероятность остановки программы? Да вроде нет. И вообще, у нас масса программ, которые не останавливаются никогда, если пользователь им не скажет, я бы даже скзал, что таких большинство. Большинство программ запущены и работают пока пользователь их не завершит, если команды завершения не поступило большинство программ будет работать до обесточивания или поломки компьютера. )))
                                  Минимальные операции тоже не обязательны практически по той же причине. Функции равны, алгоритмы эквивалентны, а вот чем больше словарь — тем лучше сходимость и менее вероятно застревание в локальном оптимуме (но тут инфа не сотка конечно, это навскидку).
                                  Это мне даже сложно комментировать, в свете того, что я уже написал. Чем больше словарь тем лучше сходимость? я вот за представил, как нужна операция инкремента на единицу, в словаре 1 000 000 команд, вероятность мутации на этот инкремент 1e-6, но зато, у нас много запчастей и в итоге инкремент на единицу реализуется через серию возведений в степень, делений, и вычислений суперкорней и логарифмов. Кул, машина с колесам из карбюраторов.
                                  Может у меня плохое чувство юмора и я шутку не понял? )))
                                    0
                                    Теперь моя очередь не понимать. Полнота по Тьюрингу гарантирует возможность наличия частично-рекурсивного алгоритма. Я нигде не эквивалентил вычислимость как таковую с только рекурсивным множеством алгоритмов (или его надмножеством с конечным временем выполнения).

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

                                    Насчет 1 000 000 команд и прочего — бесплатных обедов нет, я уже писал. Поэтому частные оптимизации выкидывать не имеет смысла.
                                      0
                                      Полнота по Тьюрингу гарантирует возможность наличия частично-рекурсивного алгоритма.
                                      В принципе, можно сказать, что это утвержение верно, но сформулировано некорректно. Полнота по Тьюрингу не гарантирует наличие алгоритма. Алгоритм либо есть, либо нет. Это вопрос вычислимости. Полнота по Тьюрингу это свойство языка или множества операций, говорящее о том, что на этом языке (с этим множеством) можно составить любой алгоритм.
                                      Я нигде не эквивалентил вычислимость как таковую с только рекурсивным множеством алгоритмов
                                      Вы нет, но вы сослались на тезис Чёрча, а он именно такую эквивалентность и провозглашает. Я с этим не согласен. Это потрынделки вилами на воде. И еще, фраза «рекурсивное множество алгоритмов» поражает своей неопределенностью и заставляет фантазию просто плясать ))). Правильно говорить «множество рекурсивных алгоритмов».
                                      рекурсивным множеством алгоритмов (или его надмножеством с конечным временем выполнения).
                                      А почему вы считаете, что множество рекурсивных алгоритмов это подмножество алгоритмов с конечным временем исполнения? Это бред. Вы никогда не видели бесконечного цикла или бесконечной рекурсии?
                                      Что касается конечного времени. Ожидание ввода, любой поллинг внешних данных — это не алгоритм, а операция. И где-то в недрах while (true) { /* любого веб-сервера */ } есть break; Это означает что где-то на ленте машины Тьюринга все же есть та единица, по которой этот веб-сервер выйдет.
                                      Вы можете, хоть половину бесконечной ленты Тьюринга утыкать командой «стоп», это не значит, что машина остановится. Не путайте ленту и машину.
                                      Насчет 1 000 000 команд и прочего — бесплатных обедов нет, я уже писал. Поэтому частные оптимизации выкидывать не имеет смысла.
                                      Частные оптимизации делать не имеет смысла, по уже написанным мной и некоторым другим причинам. Да, в некоторых случаях, они могут сэкономить время, но это зависит от среды исполнения. Да, в некоторых случаях, они могут сэкономить память, но это зависит от того действительно ли решаемый алгоритм можно декомпозировать на множество команд содержащее данную сложную команду. Но в общем случае, если мы эволюционно ищем алгоритм любая избыточная команда видится мне вредной. И пока это мнение вы не пошатнули даже на планковскую длину )
                                        0
                                        Небольшое дополнение, вы в предложении:
                                        Я нигде не эквивалентил вычислимость как таковую с только рекурсивным множеством алгоритмов (или его надмножеством с конечным временем выполнения).
                                        подменили понятие рекурсивности множеством рекурсивных алгоритмов, это тоже некорректно. Поэтому мой ответ выше базируется на контекстном понимании вашей довольно вольной терминологии.
                                          0
                                          Вы уж извините, но вы что-то не то пишите. Совсем. Я может где-то не до конца формален в формулировках, но вы либо целенаправленно тут воду мутите, либо непонятно что.

                                          Множество рекурсивных алгоритмов (функций) — это не программисткая рекурсия. Дальше нить я теряю. В любом случае посмотрите No Free Lunch-теорему.
                                            –1
                                            Мда. А при чем тут NFL вообще?
                                            Это риторический вопрос. Отвечать на него не обязательно.
                                            Вы либо тролль, либо у вас одновременно две проблемы:
                                            1. Вы не понимаете, что я пишу.
                                            2. Вы не понимаете, что сами пишите.
                                            Поэтому предлагаю завершить обсуждение. )))
                                  0
                                  давайте, давайте продолжим )))
                                  В наш просвещенный Век Анчоуса в таких случаях рекомендуется говорить, что неуемное немного большое потребление памяти программой обусловлено заложенными в нее возможностями к расширению.
                                  А с практической точки зрения — когда память станет проблемой, тогда и будем эту проблему решать.
                                  Это началась идеология. Собственно, смысл фразы даже комментировать не хочется, потому что это, на мой взгляд, потребительство в одном из худших его видов. ))) А вот если кустарный образец отличается от промышленного по какой-то характеристике на более чем 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), то удивитесь как много там интересного ))) Резюмируя по данному пункту: быстрота вашей стековой машины обусловлена частным случаем среды исполнения, но если вы действительно ищете алгоритм, то вам не стоит опираться на оптимизацию конкретной среды исполнения. Не ставьте вашу эволюцию в зависимость от типа процессора.

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

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

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

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

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

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

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

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

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

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

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

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

                                    Увы, я не математик и им уже не стану. А опыты ставить интересно.
                                      0
                                      Кто еще кого в тупик поставил… На этом примере вся статья вообще-то построена.
                                      Как пример для демонстрации концепции эволюционного подхода это нормально, но как пример в подтверждение необходимости сложных инструкций он довольно странен.
                                      Я пока не решил, буду ли я развивать ГА в эту сторону. Пока я обдумываю другие идеи.
                                      Другие? Поделитесь? В контексте того, что уже сделано я не вижу более важной задачи, чем расширение до тьюринговской полноты. Фактически сейчас у вас не генератор алгоритмов, а генератор формул, и в этом генераторе явно недостает некоторых символов.
                                      Стековая машина более перспективна как раз потому, что на ГА возлагается ответственность за выдачу результата, и ГА выдает результат только тогда, когда готов.
                                      А я и не предлагал вам делать машину на трех командах, я просто отметил, что это возможно. Ничто не мешает к трем командам добавить команду «стоп» и другие. И мне кажется, что вы залипли на стековой машине по неясным мне причинам. Вообще, на мой взгляд, стековая машина не лучшее решение для генерации алгоритмов, как я и писал в первом сообщении.
                                      Нет, ничего из этого. Попробую сказать другими словами.
                                      Сначала у нас появляется Задача, которую надо решить, затем мы делаем ГА для решения этой задачи. А не наоборот.
                                      Вот как раз в этом случае наоборот. Эволюционный подход не решает задачу семантически. Он просто генерирует алгоритмы. Любые возможные при достаточном времени. И в некотором смысле для ряда невычислимых задач его можно оптимизировать, но это отдельный вопрос за рамками нашего обсуждения.
                                      Разве моей? Ведь это ваши слова «основные затраты — оценка нового поколения» и 0decca «code bloat (неконтролируемый рост кода), сложность с циклами (много зависающих программ, которые сжирают все ресурсы), общая затратность выполнения».
                                      Да, это мои слова, но это было к тому, что лучше параллелить оценку. Хотя в идеале, если бы я делал оценку не на архитектуре общего назначения, а на тех же ASIC'ах, то выиграл бы много. Но основные операции внутри особи остались бы все теми же атомарными, я просто ускорил бы исполнение отдельной особи за счет реализации интерпретатора (или стековой машины) прямо в железе.
                                      Мое понимание ситуации — не надо пытаться сделать из ГА компьютер, надо дать ему возможность решать, то, что он может решать.
                                      Ошибочное понимание. Генетическая генерация кода именно и предполагает, что вы делаете кучу маленьких простых компьютеров и смотрите какой алгоритм лучше исполняется. И в том то и особенность генетической генерации алгоритмов, что при правильном исполнении он может найти алгоритм для любой вычислимой задачи или его приближение в дискретной среде.
                                      Кстати, спасибо вам и 0decca, я теперь знаю, что нужно учесть и так не делать.

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

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

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

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

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

                    Самое читаемое