बढ़ते एआई - आनुवंशिक एल्गोरिथम: एक परिचय

(उत्पन्न छवि)

एक कृत्रिम तंत्रिका नेटवर्क या यहां तक ​​कि "कृत्रिम बुद्धिमत्ता" बनाने के कई तरीके हैं। लेकिन ये सभी तरीके हतोत्साहित कर रहे हैं, जटिलता के उस भाग से जिसे मैं पूरी तरह से नहीं समझता, आंशिक रूप से इस तथ्य से कि सबकुछ गणितीय फॉर्मूलों पर आ जाता है।

ऐसे दृष्टिकोणों में कुछ भी गलत नहीं है, वे उन्हें सौंपे गए कार्यों को हल करने में मदद करते हैं। लेकिन ऐसा लगता है कि मैं वास्तव में एक बाइक लिखना चाहता हूं।

, ?

, , .
.

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

, , .

:

( , . )

:

:

( — )

.

हम अगले लेख में ऐसे समाधानों पर विचार करेंगे। मैं अपनी दृष्टि के क्षेत्र में भी आया, ऐसा लगता है, जैसे भाषा https://processing.org/ और HYPE फ्रेमवर्क जिस पर कई दिलचस्प चीजें बनाई जाती हैं। मैं उनके साथ खेलने की कोशिश करूंगा।