前回はNEATの概念をご紹介し、populationを用意する段階まで進みました。

今回は用意したpopulationを種に分ける操作を行います。

種に分ける(②)

次のコードを用意します。

compatibility_threshold            = 3.0
initial_connection                 = 'full'
compatibility_disjoint_coefficient = 1.0

class Species(object):
    def __init__(self, key, generation):
        self.key = key
        self.created = generation
        self.last_improved = generation
        self.representative = None
        self.members = {}
        self.fitness = None
        self.adjusted_fitness = None
        self.fitness_history = []

    def update(self, representative, members):
        self.representative = representative
        self.members = members

    def get_fitnesses(self):
        return [m.fitness for m in self.members.values()]

class DefaultSpeciesSet(object):

    def __init__(self):
        self.indexer = count(1)
        self.species = {}
        self.genome_to_species = {}

    @staticmethod
    def distance(me, other):

        node_distance = 0.0
        if me.nodes or other.nodes:
            disjoint_nodes = 0
            for k2 in other.nodes:
                if k2 not in me.nodes:
                    disjoint_nodes += 1

            for k1, n1 in me.nodes.items():
                n2 = other.nodes.get(k1)
                if n2 is None:
                    disjoint_nodes += 1
                else:
                    node_distance += n1.distance(n2)

            max_nodes = max(len(me.nodes), len(other.nodes))
            node_distance = (node_distance +
                             (compatibility_disjoint_coefficient *
                              disjoint_nodes)) / max_nodes

        connection_distance = 0.0
        if me.connections or other.connections:
            disjoint_connections = 0
            for k2 in other.connections:
                if k2 not in me.connections:
                    disjoint_connections += 1

            for k1, c1 in me.connections.items():
                c2 = other.connections.get(k1)
                if c2 is None:
                    disjoint_connections += 1
                else:
                    connection_distance += c1.distance(c2)

            max_conn = max(len(me.connections), len(other.connections))
            connection_distance = (connection_distance +
                                   (compatibility_disjoint_coefficient *
                                    disjoint_connections)) / max_conn

        distance = node_distance + connection_distance
        return distance

    def speciate(self, population, generation):

        unspeciated = set(population)
        new_representatives = {}
        new_members = {}
        for sid, s in self.species.items():
            candidates = []
            for gid in unspeciated:
                g = population[gid]
                d = self.distance(s.representative, g)
                candidates.append((d, g))

            ignored_rdist, new_rep = min(candidates, key=lambda x: x[0])
            new_rid = new_rep.key
            new_representatives[sid] = new_rid
            new_members[sid] = [new_rid]
            unspeciated.remove(new_rid)

        while unspeciated:
            gid = unspeciated.pop()
            g = population[gid]

            candidates = []
            for sid, rid in new_representatives.items():
                rep = population[rid]
                d = self.distance(rep, g)
                if d < compatibility_threshold:
                    candidates.append((d, sid))

            if candidates:
                ignored_sdist, sid = min(candidates, key=lambda x: x[0])
                new_members[sid].append(gid)
            else:
                sid = next(self.indexer)
                new_representatives[sid] = gid
                new_members[sid] = [gid]

        self.genome_to_species = {}
        for sid, rid in new_representatives.items():
            s = self.species.get(sid)
            if s is None:
                s = Species(sid, generation)
                self.species[sid] = s

            members = new_members[sid]
            for gid in members:
                self.genome_to_species[gid] = sid

            member_dict = dict((gid, population[gid]) for gid in members)
            s.update(population[rid], member_dict)

    def get_species_id(self, individual_id):
        return self.genome_to_species[individual_id]

これで種の管理をするSpeciesクラスと種に分けるメソッドspeciateを含むDefaultSpeciesSetを定義することができました。

そして次のコードで種に分ける操作をします。

species = DefaultSpeciesSet()
generation = 0
species.speciate(population, generation)
print(species.species)
print(species.genome_to_species)

print(species.species[1].representative)
print(species.species[1].representative.key)

print(species.species)をみると、辞書型が表示されており、そのkeyが一つしかないことから、一種類の種ができたことがわかります。また、print(species.genome_to_species)より、150体あるpopulationのどのネットワークも1という種に分類されている様子がわかります。

さらに、print(species.species[1].representative)より種の代表(representative)がpopulationのKey=1のネットワークであることもわかります。

representativeは各世代の中のそれぞれの種に一つあり、その種を代表するネットワークとして種を分ける際に基準のネットワークとなります。

ここで、種を分ける方法について説明します。

speciate
種に分ける際は、ネットワーク同士の距離(distance)がある水準より大きいか小さいかを計算します。

例として次の簡易的な二つのネットワークのdistanceを測ります。

左がrepresentativeで右が比較する対象となるotherです。それぞれNodesとConnectionsがあり、weightやBiasも値が与えられています。

コードに従って説明すると、distanceはnode_distanceとconnection_distanceの和で表すことができます。

node_distance

まず、Inputを除くNodesの差を見ます、この例ではどちらも0Nodesしかなく、違いはありません。

disjoint_nodes=0

次に共通のNodesに関してそのBiasの差を計算します。

node_distance=(Bias(rep)-Bias(other))×compatibility_weight_coefficient
=(2-1)×0.5=0.5

また、max_nodesを計算します。

max_nodesはrepresentative、またはotherのうちより多い方のNodes数です。今回はどちらも1なので、

max_nodes=1

となります(BiasはNodesとして含めません)。

最終的に求めるnode_distanceは

node_distance=(node_distance+compatibility_disjoint_coefficient×disjoint_nodes)/max_nodes

より、
node_distance=(0.5+1.0×0)/1=0.5

connection_distance

まず、Connectionsの差を見ます、この例ではrepresentativeが2本あり、otherは1本なので、違いは+1として考えます。

disjoint_connections=1

次に共通のConnectionsに関してそのweightの差を計算します。

connection_distance=(weight(rep)-weight(other))×compatibility_weight_coefficient
=(2-1)×0.5=0.5

また、max_connを計算します。

max_connはrepresentative、またはotherのうちより多い方のConnections数です。今回はrepresentativeの2本を採用して、

max_nodes=2

となります。

最終的に求めるconnection_distanceは

connection_distance=(connection_distance+compatibility_disjoint_coefficient×disjoint_connections)/max_conn

より、
connection_distance=(0.5+1.0×1)/2=0.75

つまりdistanceは
distance=node_distance+connection_distance=0.5+0.75=1.25

となります。このような計算を行った上でdistanceがcompatibility_threshold(今回は3.0)を超えれば新たな種が生まれます。

generation=0のときは、populationの最初のネットワーク(Key=1)をrepresentativeとして他のネットワークとの距離(distance)を測ります。generation=1以降は一つ前のrepresentativeと最も近いネットワークをその世代のrepresentativeとし、そのネットワークをそれ以外のネットワークと比べてdistanceを測ります。

次回はネットワークの成績を計算します。