一个遗传算法的 js 实现

昨天看了一点遗传算法的相关资料

所以打算利用自己理解的遗传算法写一个 js 版本的 demo

P.S. 为了写代码方便 && 强迫症，本次可能会用到一些还没成为标准的 JS 语法，例如尾逗号，如果有想自己测试的请使用最新版本 Chrome 浏览器测试

本 demo 的目的：在一个 100 * 100 的方格中生成一堆尽量靠方格中心，颜色尽量接近 #66CCFF88 的 方格。。

本次 demo 的代码托管在 CodePen 上：BJQRKB

首先用 JS 生成一个 100*100 的方格区域。然后调整一下 CSS 让他看上去好看一点。

html:

<main></main><br/>
<button id="new">重新生成</button><br/>
<button id="next">下一代</button><br/>
<button id="continue">开始/停止自动进化</button><br/>
<input id="speed" value="10">( 自动进化速度，单位 次/秒 )
<div>迭代次数：<span id="iteration">0</span>次</div>

CSS:

main{
 display: inline-grid;
 background: #0002;
 grid-template: repeat(100, 3px) / repeat(100, 3px);
 grid-gap: 1px;
 border: 1px solid #0002;
}
main div{
 background: #FFF;
}

JS:

// 配置信息
let speed = 1000 / document.querySelector("#speed").value;
document.querySelector("#speed").oninput = () => { speed = 1000 / document.querySelector("#speed").value; };

// 定义常量
const PAPAPA = 0.8 // 交配概率
const MUTANT = 0.01 // 突变概率
const PRIMARY = 50 * 50 // 种群起始值
const AIM = {
    R: parseInt("66", 16),
    G: parseInt("CC", 16),
    B: parseInt("FF", 16),
    A: parseInt("88", 16),
    X: parseFloat("45.5", 10),
    Y: parseFloat("45.5", 10),
}

// 变量保存位置
let p = {};
p.iteration = 0; // 迭代次数
p.squares = []; // 当代方块的所有参数信息
p.children = []; // 子代方块的所有参数信息
p.render = new Array(100); // 即将进行渲染的方块信息

// 生成 100 * 100 的方格
let main = document.querySelector("main");
for (let i = 100 * 100; i-- > 0;) { // 使用趋向运算符（大雾
    let div = document.createElement("div");
    main.append(div);
}

这样准备工作就做好了。

然后开始编写渲染方法，目的是把生成的对象转化为每个格子的真实的RGBA值，并渲染到图像中

每个对象有以下几个属性

R: 红色值。 [0, 255] ， 与 parseInt(66, 16) 方差越小越好 // 即 102

G: 绿色值。 [0, 255] ， 与 parseInt(CC, 16) 方差越小越好 // 即 204

B: 蓝色值。 [0, 255] ， 与 parseInt(FF, 16) 方差越小越好 // 即 255

A: 透明度。 [0, 255] ， 与 parseInt(88, 16) 方差越小越好 // 即 136

X: 横坐标。[0, 99], 与 44.5 方差越小越好

Y: 纵坐标。[0, 99], 与 44.5 方差越小越好

// render 渲染函数
let render = () => {
    p.render = new Array(100); // 清空数据
    p.render.fill(null);
    p.squares.forEach(square => {
        // 把所有当前代的方块数据按照位置存储在 p.render 参数中，由于可能会产生一个方块位子里有好多格子的情况，因此用数组存储并用一个简单的 mixin 方法混合颜色
        if (!p.render[square.X]) {
            p.render[square.X] = new Array(100);
            p.render[square.X].fill(null);
        }
        p.render[square.X][square.Y] = p.render[square.X][square.Y] || [];
        p.render[square.X][square.Y].push({
            R: square.R,
            G: square.G,
            B: square.B,
            A: square.A,
        });
    });
    let squares = document.querySelectorAll("main div");
    let draw = (X, Y, RGBA) => {
        X = +X;
        Y = +Y;
        let number = 100 * Y + X;
        let square = squares[number];
        square.style.background = `rgba(${RGBA.R},${RGBA.G},${RGBA.B},${RGBA.A})`;
    }
    for (let X in p.render) {
        p.render[X] = p.render[X] || new Array(100);
        for (let Y in p.render[X]) {
            p.render[X][Y] = p.render[X][Y] || [];
            if (p.render[X][Y].length === 0) draw(X, Y, { R: 255, G: 255, B: 255, A: 255 });
            else {
                let RGBA = { R: 0, G: 0, B: 0, A: 0 };
                p.render[X][Y].forEach(one => {
                    RGBA.R += one.R;
                    RGBA.G += one.G;
                    RGBA.B += one.B;
                    RGBA.A += one.A;
                });
                let length = p.render[X][Y].length;
                RGBA.R /= length;
                RGBA.G /= length;
                RGBA.B /= length;
                RGBA.A /= length;
                draw(X, Y, RGBA);
            }
        }
    }
    document.querySelector("#iteration").innerHTML = p.iteration;
}

然后是生成第一代方块的 JS， 很简单，生成 50 * 50 个对象，并随机按照给定范围赋予属性值

// 第一代
let generate = () => {
    p.iteration = 0;
    let random = (max) => {
        return Math.round(Math.random() * max);
    };
    p.squares = [];
    for (let i = PRIMARY; i-- > 0;) {
        p.squares.push({
            R: random(255),
            G: random(255),
            B: random(255),
            A: random(255),
            X: random(99),
            Y: random(99),
        });
    }
};
document.querySelector("#new").onclick = () => {
    generate();
    render();
};

写完以后试一下，似乎没有什么问题，生成了一堆方块

现在开始实现遗传算法的具体细节

// 产生下一代
let next = () => {
    let random = (max) => {
        return Math.round(Math.random() * max);
    };
    let papapa = (f, m) => {
        // papapa 的细节, 接受两个亲代的信息并返回子代数组
        let children = [];
        let times = 1;

        // 由于评估函数会筛掉一部分不符合标准的样本，因此如果总样本数量过少则当前亲代会多交配几次以产生足够多的子代维持算法继续下去。
        times = Math.ceil(PRIMARY / (p.children.length + p.squares.length));
        while (times--) {
            let c1 = {};
            let c2 = {};
            let cutPoint = random(5);
            let cutArray = ["R", "G", "B", "A", "X", "Y"];
            for (let i = 0; i < 6; i++) {
                let key = cutArray[i];
                if (i < cutPoint) {
                    c1[key] = f[key];
                    c2[key] = m[key];
                } else {
                    c1[key] = m[key];
                    c2[key] = f[key];
                }
            }
            children.push(c1);
            children.push(c2);
        }
        return children;

    }

    while (p.squares.length >= 2) {
        // 随机取出两个个体
        let length = p.squares.length;
        let i = random(length - 1);
        let j = random(length - 2);
        let f = p.squares.splice(i, 1)[0];
        let m = p.squares.splice(j, 1)[0];

        if (Math.random() < PAPAPA) p.children.splice(p.children.length, 0, ...papapa(f, m));
        else p.children.splice(p.children.length, 0, f, m);
    }
    p.children.splice(p.children.length, 0, ...p.squares);

    let mutant = (unit) => {
        // 突变细节 
        let newUnit = {};
        let m = (key, max) => {
            newUnit[key] = Math.random() < MUTANT ? random(max) : unit[key];
        }
        m("R", 255);
        m("G", 255);
        m("B", 255);
        m("A", 255);
        m("X", 99);
        m("Y", 99);
        return newUnit;
    };

    let suit = (unit) => {
        // 适应度评估
        let v = (key, max) => {
            return Math.sqrt(Math.pow(AIM[key] - unit[key], 2)) / Math.max(max, max - AIM[key]);
        };
        let vR = v("R", 255);
        let vG = v("G", 255);
        let vB = v("B", 255);
        let vA = v("A", 255);
        let vX = v("X", 99);
        let vY = v("Y", 99);

        let calc = (a, b, max) => {
            return Math.sqrt(Math.pow(a - b, 2)) / max;
        }
        let vColor = ((vR + vG + vB) / 3 + calc(AIM.R + AIM.G + AIM.B, unit.R + unit.G + unit.B, 255 * 3)) / 2;
        let vAxis = ((vX + vY) / 2 + calc(AIM.X + AIM.Y, unit.X + unit.Y, 99 * 2)) / 2;

        v = (vColor + vAxis) / 2;
        return Math.random() > v;
    }

    // 子代变为亲代
    p.iteration += 1;
    p.children = p.children.map(mutant);
    p.squares = p.children.filter(suit);
    p.children = [];
};

最后绑定上两个事件

document.querySelector("#next").onclick = () => {
    next();
    render();
};
document.querySelector("#continue").onclick = (() => {
    let started;
    return () => {
        if (started) {
            clearTimeout(started);
            started = null;
        } else {
            let f = () => {
                next();
                render();
                started = setTimeout(f, speed);
            }
            f();
        }
    };
})();

测试一下效果

经过 500 次迭代之后生成的图像变成了

似乎我在坐标的适应度评估方法还是有点问题

以后再改吧(:з)∠)

大概就是这样

本代码在 codepen.io 上有： BJQRKB

======= update ======

稍微改了一下评估函数

let colorRange = Math.cbrt(Math.pow(Math.max(255, 255 - AIM.R), 3) + Math.pow(Math.max(255, 255 - AIM.G), 3) + Math.pow(Math.max(255, 255 - AIM.B), 3));
let axisRange = Math.sqrt(Math.pow(Math.max(255, 255 - AIM.X), 2) + Math.pow(Math.max(255, 255 - AIM.Y), 2));
let suit = (unit) => {
    // 适应度评估
    let v = (key, max) => {
        return Math.sqrt(Math.pow(AIM[key] - unit[key], 2));
    };
    let vR = v("R");
    let vG = v("G");
    let vB = v("B");
    let vA = v("A");
    let vX = v("X");
    let vY = v("Y");

    let vColor = Math.cbrt(Math.pow(vR, 3) + Math.pow(vG, 3) + Math.pow(vB, 3));
    vColor /= colorRange;

    let vAxis = Math.sqrt(Math.pow(vX, 2) + Math.pow(vY, 2));
    vAxis /= axisRange;

    v = (vColor + vAxis) / 2;

    return Math.random() > v;
}

同样进行 500 次迭代

这次出来的结果比上次稍微好了那么一丢丢，依附于两个坐标轴的现象比上次稍微好了一点。。。