0
Обложка: Пишем симулятор естественного отбора на Python

Пишем симулятор естественного отбора на Python

Я начал заниматься этим проектом в 2005 году, в качестве отдушины (как сейчас говорят pet project). Python я тогда не знал, так что параллельно изучал, кстати, без особых успехов, как вы убедитесь.

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

Первый вариант симуляции

Изначально я писал на C++ — из-за перспективы хорошей производительности. Но потом приехал хороший друг и убедил переписать проект на Python. За пару дней я написал часть:

from math import *
seed=123456789
def myrandom(lower=0.0, upper=1.0):
    global seed
    seed = (seed * 13)/11;
    ival = seed % 1000;
    x =  ival*1.0;
    return ( (x * 0.001 * (upper - lower)) + lower)

class neuron:
    def __init__(self, n_sinaps):
        self._weights=[]
        for i in range(n_sinaps+1):
            self._weights.append(myrandom(0.0,0.1))
            ## One weight - adjusting of sigmoid
        self._out=0
        self._inputs=[]
    def calc(self):
        tmpinputs=self._inputs[0:len(self._inputs)]
        tmpinputs.append(1) ## One input always =1 for adjusting of sigmoid
##        print "tmpinputs"+str(tmpinputs)
##        print "self._weights"+str(self._weights)
        s=sum(map(lambda v1,v2:v1*v2,tmpinputs,self._weights))
        self._out=1/(1+exp(-s))
        return self._out
    def __str__(self):
        return str(self._weights)


class layer:
    def __init__(self, n_neurons, n_inputs):
        self._neurons=[]
        for i in range(n_neurons):
            self._neurons.append(neuron(n_inputs))
        self._outs=[]
        self._inputs=[]
    def calc(self):
        self._outs=[] ## 'cos _outs can be not empty after previous step
        for i in self._neurons:
            i._inputs=self._inputs
            self._outs.append(i.calc())
    def __str__(self):
        return str(self._outs)


class nn:
    def __init__(self, n_layers, n_neurons_pl, n_inputs):
        ## n_layers - Количество слоев
        ## n_neurons_pl - Количество нейронов в каждом слое (это массив,
        ##      и последний слой определяет количество выходов)
        ## n_inputs - Количество входов
        self._layers=[]
        self._layers.append(layer(n_neurons_pl[0],n_inputs))
        for i in range(1,n_layers):
            self._layers.append(layer(n_neurons_pl[i],n_neurons_pl[i-1]))
        self._outs=[]
        self._inputs=[]
        self.n_layers=n_layers

    def calc(self):
        self._layers[0]._inputs=self._inputs
        print "Layer 0  Ins: " + str(self._layers[0]._inputs)
        self._layers[0].calc()
        print "Layer 0 Outs: " + str(self._layers[0]._outs)
        for i in range(1,len(self._layers)):
            self._layers[i]._inputs=self._layers[i-1]._outs
            print "Layer " + str(i) + "  Ins: " + str(self._layers[i]._inputs)
            self._layers[i].calc()
            print "Layer " + str(i) + " Outs: " + str(self._layers[i]._outs)
        self._outs=self._layers[len(self._layers)-1]._outs
    def __str__(self):
        s=""
        for i in self._layers:
            for j in i._neurons:
                s += "       Weights (amount="+str(len(j._weights))+"):" + str(j._weights)+"n"
        return str(s)


############################################
#####               Start              #####
############################################

print "Started"

mynn=nn(5,[3,4,5,4,1],5)
mynn._inputs=[1,0,0,0,0]
print "**************************"
print str(mynn)
print "**************************"
print "Net Inputs: " + str(mynn._inputs)
mynn.calc()
print "Net Outs: " + str(mynn._outs)
mynn._inputs=[1,1,0,0,0]
print "Net Inputs: " + str(mynn._inputs)
mynn.calc()
print "Net Outs: " + str(mynn._outs)
mynn._inputs=[1,1,1,0,0]
print "Net Inputs: " + str(mynn._inputs)
mynn.calc()
print "Net Outs: " + str(mynn._outs)

print"Terminated. Закончено."

Забавно вспомнить, что тогда еще utf-8 не захватил весь мир, и чтобы не думать слишком много о кодировке, местами комментарии написаны на ломанном английском:

class neuron:
    def __init__(self, n_sinaps):
    def calc(self):
        ...
class layer:
    def __init__(self, n_neurons, n_inputs):
    def calc(self):
        ...
class nn:
    def __init__(self, n_layers, n_neurons_pl, n_inputs):
    def calc(self):
        ...

Перфикс «n_» означает «количество», то есть целочисленное значение, а «_pl» — это «_per_layer» (анг. «в каждом слое»), то есть тут приходит вектор. Видимо, можно было написать изящнее, с наследованием, но это было не главное.

Проблемы

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

  • Как понять какая минимальная конфигурация сети будет справляться с той или иной задачей?
  • Какими должны быть параметр сигмоиды и смещение сигмоиды?
  • Какую активационную функцию использовать?
  • Как выглядит переобучение?
  • Зачем нормализовывать входы?

Второй вариант симуляции

Мой друг, написал такую версию:

#!/usr/bin/python
# -- mode: pytnon ; encoding: KOI8-R --

import math
import pickle
#####################################################################
# вариант активационной  функции. Логичней вынести из модуля,
# но пока оставил.
#####################################################################
def sigm_af(net):
    return 1/(1+math.exp(-net))

#####################################################################
# neiron
# В общем случае представляет собой список, значения котрого есть значения весов.
# Имеет минимально необходимый набор методов для работы со списком.
# __init__(cnt_sin,fill_iter,active_fn=sigm_af):
# <cnt_sin> - количество весов
# <fill_iter> - интериор или генератор, откуда будут браться значения весов
#               если это интериор, то количество элементов должно равняться
#               количеству свзей, иначе генерируем ошибку
# <active_fn> - активационная функция
# calc(signal):
# <signal> - список попадающих на входж сигналов - на выходе значение
#            количество сигналов должно быть равно количеству связей - 1 .
# ---
#  остальные методы - аналоги методв работы со списком - интериор,
#  доступ по индексу. len - возвращает количество связей
#  Так-же есть один "лишний" нейрон, при удалении связей, если не указан
#  конкретный индекс - удаляется предпоследний нейрон, который "в связи"
#  с предыдущим слоем
#####################################################################
class neiron(object):
    def __init__(self,cnt_sin=0,fill_iter=iter([]),active_fn=sigm_af):
        self.__active_fn_=active_fn
        self.set(cnt_sin,fill_iter)
    def calc(self,signal):
        if len(signal)+1!=len(self):
            raise "Кол-во входных сигналов нейрона должно быть %s"%(len(self.__powers_)-1)
        net=sum(map(lambda s,v:s*v,self.__powers_,signal+[1]))
        return self.__active_fn_(net)
    def set(self,cnt_sin,fill_iter):
        self.__powers_=[]
        for i in range(cnt_sin):
                self.__powers_.append(fill_iter.next())
    def get(self):
        return self.__powers_
    def append(self,item):
        self.__powers_.append(item)
    def insert(self,index,item):
        self.__powers_.insert(index,item)
    def delete(self,index=-2):
        self.__powers_.pop(index)
    def __repr__(self):
        return repr(self.__powers_)
    def __getitem__(self,i):
        return self.__powers_[i]
    def __setitem__(self,i,item):
        self.__powers_[i]=item
    def __len__(self):
        return len(self.__powers_)
    def __str__(self):
        return "Neiron:"+`map(lambda x:str(x),self.get())`
#####################################################################
# Определим "пустой" нейрон, на вход и выход которого равны.
# Мождет использоваться при определении входного слоя.
# Но в принципе ничего не мешает использовать его в любом месте -
# это обычный нейрон
#####################################################################
def fail_act(x):return x
def fail_neiron():
    return neiron(2,iter([1,0]),fail_act)

#####################################################################
# net
# реализация нейронной сети. Представляет собой совокупность нейронов,
# расположенных в слоях.
# методы:
# __init__(layer_list,fill_iter=iter([]),history=True,history_len=1000)
#     layer_list - список слоев из нейронов, (список списков)
#       [ [neriron1,neiron2..->(layer1)] , [<layer2>], [<layer3>], ...]
#       первый слой может пустые нейроны, хотя не совсем обязательно,
#       тогда входные значения придеться дублировать дважды
#     fill_iter - интериатор, заполняющий веса (см.выше), если все
#       веса указаны, то можно опустить
#    history, history_len - для формирования списка истории значений и выходов
# set - инициализация новой сети, вызывается из конструктора, но можно менять в
#       рантайме, все недостающие веса добавляются а ненужные удаляються(конечные)
# addneirons - добавить в нейрон в слой. Добавляет нейрон последним в слой.
# addlayer - добавить в конец слой нейронов
# calc() - получить собстно выход сети. Нам вход подается список входных
#          сигналов. рамер списка должен быть равен количество входов - count_input().
# gethistory - получить всю или часть списка результатов
# остальное думаю ясно по тексту.
#####################################################################
class net(object):
    def __init__(self,layer_list,fill_iter=iter([]),history=True,history_len=1000):
        self.__layerlist_=[]
        self.__layerlist_.append(layer_list[0])
        for layer in layer_list[1:]:
            self.addlayer(layer,fill_iter)
        # для отладки и анализа будем сохранять историю
        self.__history_=history
        self.__history_len_=history_len
        self.__history_list_=[[None,None]]
    ###################################
    # создание и модификация сети
    ###################################
    def addlayer(self,layer,fill_iter=iter([])):
        self.__layerlist_.append(layer)
        self.__check_layer_(layer,fill_iter)
    def deletelayer(self,idx):
        pass
    # количество нейронов в предыдущем слое
    def __get_prev_layer_cnt_(self,layer):
        return len(self.__layerlist_[self.__layerlist_.index(layer)-1])
    def __check_layer_(self,layer,fill_iter):
        prev_cnt=self.__get_prev_layer_cnt_(layer)
        for neiron in layer:
             self.__check_neiron_(neiron,prev_cnt,fill_iter)
    def __check_neiron_(self,neiron,c_power,fill_iter):
        # удалим или добавим необходимые нейроны
        dl=len(neiron)-c_power-1
        if dl>0:
            map(lambda x: neiron.delete(),range(abs(dl)))
        elif dl<0:
            map(lambda x: neiron.append(fill_iter.next()),range(abs(dl)))
    # Тут конечно можно адресовать по двум координатам, но нужно-ли усложнять?
    def addneirons(self,idx,neiron,fill_iter=iter([])):
        if idx!=0:
            prev_cnt=self.__get_prev_layer_cnt_(layer)
        else:
            prev_cnt=1
        self.__check_neiron_(neiron,prev_cnt,fill_iter)
        self.__layerlist_[idx].append(neiron)
        if idx!=len(self.__layerlist_):
            self.__check_layer_(self.__layerlist_[idx+1],fill_iter)
    def delneiron(self,idx):
        self.__layerlist_[idx].pop()
        if idx!=len(self.__layerlist_):
            self.__check_layer_(self.__layerlist_[idx+1],fill_iter)
    def count_input(self):
        return len(self.__layerlist_[0])
    def count_neiron(self,idx=-1):
        return len(self.__layerlist_[idx])
    ##############################
    # вычисление сети
    ##############################
    def calc(self,value):
        if len(value)!=self.count_input():
            raise "Кол-во входных сигналов сети должно быть %s"%(self.count_input())
        # вычисляем вход
        value=map(lambda n,i:n.calc([i]),self.__layerlist_[0],value)
        # по сем слоям и в каждом вычислим значения нейронов.
        # вход на каждый сло - выход предыдущего
        for l in self.__layerlist_[1:]:
            value=map(lambda n:n.calc(value),l)
        return value
    ###################################
    #  Заморозка  сети
    ###################################
    def dump(self,fd):
        pickle.dump(self,fd)
    def dumpto(self,filename):
        fd=open(filename,"w+");self.dump(fd);close(fd)
    # наверное эти функции нужно удалить, т.к. нет еще объекта
    def load(self,fd):
        return pickle.load(self,fd)
    def loadfrom(self,filename):
        fd=open(filename,"r+");
        nn=self.load(fd);
        close(fd);
        return nn
    ###################################
    #  Прочие функции
    ###################################
    def __repr__(self):
        return repr(self.__layerlist_)
    def __getitem__(self,i):
        return self.__layerlist_[i]
    def __setitem__(self,i,item):
        pass
    def __len__(self):
        return len(self.__layerlist_)
    def __add__(self,layer):
        newnet=self.__class__(self.__layerlist_)
        newnet.addlayer(layer)
        return newnet
    def __str__(self):
        hd="-"*35+"n"
        result=hd+"Сеть: id="+str(id(self))
        result+="nКоличество слоев: "+str(len(self.__layerlist_))
        result+="nЗапомнено последних значений: "+str(len(self.__history_list_))
        result+="nПоследнее значение: "+str(self.__history_list_[-1])
        result+="n"+hd
        for nl in range(len(self.__layerlist_)):
            result+="layer: "+str(nl)
            for n in self.__layerlist_[nl]:
                result+="n"+str(n)
            result+="n"+hd
        return  result

#####################################################################
# Такая пока простелька приблуда, которая создает сеть из указанного
# количества нейронов. Первый слой будет входной слой
#####################################################################
def netmaker(list_of_neirons,fill_iter):
    layers=[map(lambda x:fail_neiron(),range(list_of_neirons[0]))]
    for cnt_neiron in list_of_neirons[1:]:
        layers.append(map(lambda x:neiron(),range(cnt_neiron)))
    return  net(layers,fill_iter)

def test_neirons():
    # два простых нейрона
    n1=neiron(3,rndgen())
    n2=neiron(2,iter([0.5,2.4]))
    #просто вход
    inp1=fail_neiron()
    # добавление связи
    n1.append(0.9)
    # непостредственная модификация связи
    n2[0]=0.6
    # вывод
    print n1
    print len(n1)
    # просчитать 1 и 2 нейроны
    print n1.calc([0.2,3.4,0.2]),n2.calc([0.8])
    print inp1.calc([0.5])


def test_net():
    # один слой
    v1  =fail_neiron()
    v2  =fail_neiron()
    l1n1=neiron(3,iter([1,2,3,4,5])); # больше чем нужно
    l1n2=neiron(2,iter([6,7])); # меньше
    n1=net([[v1, v2 ] , [l1n1, l1n2]  ], iter([8,9,10,11,12]))
    print n1
    print "Result:", n1.calc([0.2,0.46])
    print n1
    n2=n1+[neiron(n1.count_neiron()+1,rndgen())]
    print n2
    print n2.calc([0.5,0.46])
    #заморозка
    n2.dump(test_fd)
    del n2;
    print "грохнули "
    test_fd.seek(0);# отъехали к началу
    n2__=pickle.load(test_fd)
    print n2__ ; # яки птица феникс
    print n2__.calc([0.5,0.46]); # "Все оки-доки"
    # и вот такая конструция  тоже легко прокатит
    net3=net([[fail_neiron(),fail_neiron()], [neiron(),neiron(),neiron()] ,[neiron()]],rndgen())
    print "Net3:", net3


def test_netmaker():
    #net1=netmaker([2,3,2],rndgen())
    #print net1
    # или так.
    random.seed(5)
    net2=netmaker([1,5,5,5,1],iter(rndgen()))
    print net2
    print net2.calc([2])
if __name__=="__main__":
    import random
    import StringIO
    test_fd=StringIO.StringIO()
    # создадим простой генератор
    def rndgen():
       while 1:
            yield random.random()
    # короткие тесты
    #test_neirons()
    #test_net()
    test_netmaker()

else:
    pass

Видите, я недоглядел, и Денис улетел в космос. Использованы все возможности языка Python. Итераторы и генераторы, лямбда-функции и мапирование, pickle для сохранения объектов, тесты, наследования и так далее. Класс был изолирован в модуль, так что я мог использовать его дальше и писать приложение, реализующее естественный отбор, чем я и занялся.

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

На сегодня всё. Дальше планирую написать про первую реализацию симуляции естественного отбора, мега-задачу схождения к sin(), проблему с утечкой памяти, съевшей 100500 человеко-часов, и ещё что-нибудь.