AI en crecimiento - Algoritmos genéticos: una introducción

(imagen generada)

Hay muchas formas de crear una red neuronal artificial o incluso "inteligencia artificial". Pero todos estos métodos son desalentadores, por la parte de la complejidad que no entiendo completamente, en parte por el hecho de que todo se reduce a fórmulas matemáticas.

Estos enfoques no tienen nada de malo; ayudan a resolver las tareas que se les asignan. Pero parece que realmente quiero escribir una 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 tales soluciones en el próximo artículo. Parece que también entré en mi campo de visión, como el lenguaje https://processing.org/ y el marco HYPE en el que se crean muchas cosas interesantes. Intentaré jugar con ellos.