AI yang Bertumbuh - Algoritma Genetika: Suatu Pengantar

(gambar yang dihasilkan)

Ada banyak cara untuk membuat jaringan saraf tiruan atau bahkan "kecerdasan buatan". Tetapi semua metode ini mengecewakan, dari bagian kompleksitas yang saya tidak sepenuhnya mengerti, sebagian dari kenyataan bahwa semuanya datang ke rumus matematika.

Tidak ada yang salah dengan pendekatan semacam itu, mereka membantu menyelesaikan tugas yang diberikan kepadanya. Tapi sepertinya saya benar-benar ingin menulis sepeda.

, ?

, , .
.

, , , 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% .

, , .

:

( , . )

:

:

( — )

.

Kami akan mempertimbangkan solusi tersebut di artikel selanjutnya. Saya juga masuk ke bidang visi saya, sepertinya, seperti bahasa https://processing.org/ dan kerangka kerja HYPE tempat banyak hal menarik dibuat. Saya akan mencoba bermain dengan mereka.