IA crescente - algoritmos genéticos: uma introdução

(imagem gerada)

Existem muitas maneiras de criar uma rede neural artificial ou mesmo "inteligência artificial". Mas todos esses métodos são desencorajadores, da parte da complexidade que eu não entendo completamente, em parte do fato de que tudo se resume a fórmulas matemáticas.

Não há nada de errado com essas abordagens, pois elas ajudam a resolver as tarefas atribuídas a elas. Mas parece que eu realmente quero escrever uma bicicleta.

, ?

, , .
.

, , , 1 0 . 1 0 . , , .

+- . , ? , — ? " "?

Axon guidance.

, .

:

Eph-

: , , ;
: CRMP- (CRMP1, CRMP2, CRMP3, CRMP4, CRMP5)

, , . . .

. . - , ?

( )

( 3 — )

, , , , , - .

, , — . — - , .

. , .

.

« » , . , , , , .

. , , « » . : . . , ? « » . ? ? ? ? , . , , . , , ? ? ? , ? , «» , . .

?

1950- , , ( «GA»), , , Adaptation in Natural and Artificial Systems GA. , « ».

, . , . , . Java, .

« » : , , ( ). , , , , , , .

. , : . , — .

«to be or not to be that is the question» ( «to be or not to be: that is the question»). 39 . , , — 1 27. — 1 27 * 27. , , : $$$(1/27)^{39}$

1 66,555,937,033,867,822,607,895,549,241,096,482,953,017,615,834,735,226,163.

— , 9 719 096 182 010 563 073 122 (253 593 605 017 ). ( 13 750 000 000 .)

, , , , ( ) "to be or not to be that is the question". .

, , , , , . , .

, . , , :

. , . , , .

().

, -, . , , , : , , , . - . , .

(). , . « ». , , . , , , . « » . , , . , , , , . , «» ( , ) « ». — , «to be or not to be».

—

, , . , ( ). . cat :
hug
rid
won

, , , . , . , , , , "c" , "a" , "a" . , , , ( ).

, — .

, , . .

( () ())

( () ())

. , , . , ANSI genes.
— — . , +- , .

—

— ,

.

1.

, , , . fitness, fit.

(Fitness function). , . , . , , .

, . cat car:

2. ( )

, .

. , : " ? ".

, . ( ) , , . , 500 1000. , . , . 500 , 501 ?

, « » ( «»). , , , :

:

, B . , C . . "to be or not to be":

A: to be or not to go
B: to be or not to pi
C: xxxxxxxxxxxxxxxxbe

B , C . .

, . . .

—

. 5 . :

1. (Crossover)

. , , .

A: FORK
B: PLAY

. , ( 50/50) — A B, :

. :

:

, . . , -. .

2.

— . , . . . , , . . .

. FORY , 1%, , FORY 1% . 96% . , :

, , "" .

:

SETUP:

1: , N . .

LOOP:

2: , .

3: . N :

4. 2.

. , .

Python. , JavaScript.

JS , . Node.js. , , . :)

DNA:

// DNA.js
const random = require('./random');

class DNA {
    constructor(length, dna = null) {
        // Main
        this.length = length;
        this.genes = dna ? dna.genes : this.getRandomGenes(this.length);

        // Additional
        this.fitness = 0;
    }

    getRandomGenes(length) {
        return  new Array(length)
            .fill(0)
                .map(() => random.getRandomInt(32, 128));
    }

    //       ,    
    updateLength(length) {
        if (length <= this.genes) {
            throw 'Error';
        }

        this.genes = [...this.genes, this.getRandomGenes(length - this.genes.length)];
    }
}

module.exports = DNA;

DNA , , .

getRandomInt 32 128 . ANSI .

// random.js
function getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);

    return Math.floor(Math.random() * (max - min)) + min; // 
}

module.exports = {
    random: Math.random,
    getRandomInt
}

DNA.js genes. .

. , , .

initPopulation() {
        this.population = new Array(this.n)
            .fill(0)
            .map(() => new this.dna(this.target.length));

        this.population.forEach((dna) => dna.fitness = this.evaluateFitness(dna));
    }

n, . . , .

evaluateFitness(dna) {
        return (dna.genes.reduce((acc, current, index) => {
            if (current === this.target.codePointAt(index)) {
                return acc + 1;
            }

            return acc;
        }, 0) / this.target.length);
    }

, . this.target . , .

getMatingPool() {
        let matingPool = [];

        this.population.forEach((dna) => {
            const n = parseInt(dna.fitness * 100);

            matingPool = [...matingPool, ...(new Array(n).fill(dna))];
        });

        return matingPool;
    }

, . , . , .

findRandomParent(matingPool) {
        return matingPool[random.getRandomInt(0, matingPool.length)];
    }

crossover(dna1, dna2) {
        const child = new this.dna(this.target.length);

        const midpoint = random.getRandomInt(0, dna1.genes.length);

        for (let i = 0; i < dna1.genes.length; i++) {
            if (i > midpoint) {
                child.genes[i] = dna1.genes[i];
            }
            else {
                child.genes[i] = dna2.genes[i];
            }
        }

        return child;
    }

, , .

:

mutation(dna) {
        const mutatedDNA = new this.dna(this.target.length, dna);

        //     
        for (let i = 0; i < dna.genes.length; i++) {
            if (random.random() < this.mutationRate) {
                //    
                mutatedDNA.genes[i] = random.getRandomInt(32, 128);
            }
        }

        return mutatedDNA;
    }

, .

:

// Population.js
const random = require('./random');

class Population {
    constructor(target, dna, n = 100, mutationRate = 0.01, adaptive = false, adaptiveThreshold = 0.6, cutLength = 5) {
        this.endTarget = target; // String
        this.adaptive = adaptive;
        this.adaptiveThreshold = adaptiveThreshold;
        this.cutLength = cutLength;
        this.target = this.adaptive ? target.substr(0, this.cutLength) : target; // String
        this.dna = dna;
        this.n = n;
        this.mutationRate = mutationRate;
        this.population = []
        this.populationInfo = {
            generationCount: 0
        };

        this.initPopulation();
    }

    initPopulation() {
        this.population = new Array(this.n)
            .fill(0)
            .map(() => new this.dna(this.target.length));

        this.population.forEach((dna) => dna.fitness = this.evaluateFitness(dna));
    }

    //       ,    
    updateDNA(target) {
        this.target = target;

        this.population.forEach((dna) => {
            dna.updateLength(target.length);
        });
    }

    getPopulationInfo() {
        let statsFitness1 = 0;

        return {
            generationCount: this.populationInfo.generationCount,
            averageFitness: this.population
                .reduce((acc, current) => {
                    if (this.target === String.fromCharCode.apply(this, current.genes)) {
                        statsFitness1 += 1;
                    }

                    return acc + current.fitness
                }, 0) / this.population.length,
            statsFitness1
        }
    }

    getMatingPool() {
        let matingPool = [];

        this.population.forEach((dna) => {
            const n = parseInt(dna.fitness * 100);

            matingPool = [...matingPool, ...(new Array(n).fill(dna))];
        });

        return matingPool;
    }

    evaluateFitness(dna) {
        return (dna.genes.reduce((acc, current, index) => {
            if (current === this.target.codePointAt(index)) {
                return acc + 1;
            }

            return acc;
        }, 0) / this.target.length);
    }

    findRandomParent(matingPool) {
        return matingPool[random.getRandomInt(0, matingPool.length)];
    }

    nextGeneration() {
        let matingPool = this.getMatingPool();

        this.population.forEach((_, index) => {
            const parentA = this.findRandomParent(matingPool);
            let parentB = null;

            while (!parentB || (parentB === parentA)) {
                parentB = this.findRandomParent(matingPool);
            }

            let child = this.crossover(parentA, parentB);

            child = this.mutation(child);
            child.fitness = this.evaluateFitness(child)

            this.population[index] = child;
        });

        this.populationInfo.generationCount += 1;

        //       ,    
        if (this.adaptive && this.target !== this.endTarget) {
            if (this.getPopulationInfo().averageFitness >= this.adaptiveThreshold) {
                this.updateDNA(this.endTarget.substr(0, this.target.length + this.cutLength));
            }
        }
    }

    crossover(dna1, dna2) {
        const child = new this.dna(this.target.length);

        // Picking a random “midpoint” in the genes array
        const midpoint = random.getRandomInt(0, dna1.genes.length);

        for (let i = 0; i < dna1.genes.length; i++) {
            // Before midpoint copy genes from one parent, after midpoint copy genes from the other parent
            if (i > midpoint) {
                child.genes[i] = dna1.genes[i];
            }
            else {
                child.genes[i] = dna2.genes[i];
            }
        }

        return child;
    }

    mutation(dna) {
        const mutatedDNA = new this.dna(this.target.length, dna);

        // Looking at each gene in the array
        for (let i = 0; i < dna.genes.length; i++) {
            if (random.random() < this.mutationRate) {
                // Mutation, a new random character
                mutatedDNA.genes[i] = random.getRandomInt(32, 128);
            }
        }

        return mutatedDNA;
    }
}

module.exports = Population;

, . , . Node.js WebGL , , -, — .

blessed-contrib .

, . , .

// Log.js
const blessed = require('blessed');
const contrib = require('blessed-contrib');

class Log {
    constructor(rows, cols) {
        this.lines = [];
        this.screen = blessed.screen();

        this.grid = new contrib.grid({
            rows,
            cols,
            screen: this.screen
        });

        this.screen.on('resize', () => {
            this.lines.forEach((line) => {
                line.emit('attach');
            })
        });

        this.screen.key(['escape', 'q', 'C-c'], function(ch, key) {
            return process.exit(0);
        });
    }

    addLine(x, label, row, col) {
        const line = this.grid.set(row, col, 1, 1, contrib.line, {
            label,
            style: {
                line: "yellow",
                text: "green",
                baseline: "black"
            },
            xLabelPadding: 3,
            xPadding: 5
        });

        this.screen.append(line);

        line.setData([{
            x: x,
            y: x.map(v => v * 100)
        }]);

        return this.lines.push(line) - 1;
    }

    updateLineData(index, x) {
        this.lines[index]
            .setData([{
                x,
                y: x
            }]
        );
    }

    render() {
        this.screen.render();
    }
}

module.exports = Log;

, , 100% .

getPopulationInfo() {
        let statsFitness1 = 0;

        return {
            generationCount: this.populationInfo.generationCount,
            averageFitness: this.population
                .reduce((acc, current) => {
                    if (this.target === String.fromCharCode.apply(this, current.genes)) {
                        statsFitness1 += 1;
                    }

                    return acc + current.fitness
                }, 0) / this.population.length,
            statsFitness1
        }
    }

, .

// index.js
const DNA = require('./DNA');
const Population = require('./Population');
const Log = require('./Log');
const contrib = require('blessed-contrib');

//     
const log = new Log(2, 2);
const statsFitnessAverageIndex = log.addLine([], 'Fitness', 0, 0);
const statsFitness1Index = log.addLine([], 'Fitness 1', 0, 1);
const screenLog = log.grid.set(1, 1, 1, 1, contrib.log, {
    label: 'logs'
});

const TARGET = 'Hello Habr!';
const GENERATIONS = 1000;
const POPULATION_NUMBER = 150;
const MUTATION_RATE = 0.01;

const population = new Population(TARGET, DNA, POPULATION_NUMBER, MUTATION_RATE);

//   
const statsFitnessAverage = [];
const statsFitness1 = [];

, .

// index.js
...

function main() {
    population.nextGeneration();

    const stats = population.getPopulationInfo();
    statsFitnessAverage.push(stats.averageFitness);
    statsFitness1.push(stats.statsFitness1);
}

. , .

function update() {
    log.updateLineData(statsFitnessAverageIndex, statsFitnessAverage);
    log.updateLineData(statsFitness1Index, statsFitness1);
}

function sync() {
    for (let i = 0; i < GENERATIONS; i++) {
        main();
    }

    update();

    log.render();
}

sync();

screenLog.log(`${population.endTarget} : ${population.target}`)

sync . , :

function async() {
    setInterval(() => {
        main();
        update();
        log.render();
    }, 10)
}

:

, .

, 90% , 100% .
Fintess 1, 100% . 20 75 .

. Hello Habr! . To be or not to be:

, 1000 . , .

:

, 0.1% 1%?

, 80% 31-33%. .

. , , .

, ? , .

. .

, . 3 : adaptive — , adaptiveThreshold — , cutLength — .

:

const TARGET = 'To be or not to be To be or not to be';
const GENERATIONS = 1000;
const POPULATION_NUMBER = 150;
const MUTATION_RATE = 0.01;

const population = new Population(TARGET, DNA, POPULATION_NUMBER, MUTATION_RATE, true, 0.5, 7);

, . 1000 , . , ?

. . . . , , 100% .

, , .

:

( , . )

:

:

( — )

.

Consideraremos essas soluções no próximo artigo. Também entrei no meu campo de visão, ao que parece, como a linguagem https://processing.org/ e a estrutura HYPE na qual muitas coisas interessantes são criadas. Vou tentar brincar com eles.