3

我用遗传算法写了一个快速实验。它只需要一个正方形网格并尝试改变它们的颜色以使它们全部变黄。它惨遭失败,我似乎无法弄清楚为什么。我已经包含了一个指向 JSFiddle 的链接,该链接演示了工作代码,以及完整的代码副本。

http://jsfiddle.net/mankyd/X6x9L/

<!DOCTYPE html>
<html lang="en">
    <head>
    </head>
    <body>
        <div class="container">
            <h1>The randomly flashing squares <i>should</i> be turning yellow</h1>
            <div class="row">
                <canvas id="input_canvas" width="100" height="100"></canvas>
                <canvas id="output_canvas" width="100" height="100"></canvas>
            </div>
            <div class="row">
                <span id="generation"></span>
                <span id="best_fitness"></span>
                <span id="avg_fitness"></span>
            </div>
        </div>
    </body>
</html>

请注意,下面的 javascript 在一些地方依赖于 jquery。

// A bit of code that draws several squares in a canvas
// and then attempts to use a genetic algorithm to slowly
// make those squares all yellow.

// Knobs that can be tweaked
var mutation_rate = 0.1; // how often should we mutate something
var crossover_rate = 0.6; // how often should we crossover two parents
var fitness_influence = 1; // affects the fitness's influence over mutation
var elitism = 1; // how many of the parent's generation to carry over
var num_offspring = 20; // how many spawn's per generation
var use_rank_selection = true; // false == roulette_selection

// Global variables for easy tracking
var children = []; // current generation
var best_spawn = null; // keeps track of our best so far
var best_fitness = null; // keeps track of our best so far
var generation = 0; // global generation counter
var clear_color = 'rgb(0,0,0)';

// used for output
var $gen_span = $('#generation');
var $best_fit = $('#best_fitness');
var $avg_fit = $('#avg_fitness');
var $input_canvas = $('#input_canvas');
var input_ctx = $input_canvas[0].getContext('2d');
var $output_canvas = $('#output_canvas');
var output_ctx = $output_canvas[0].getContext('2d');

// A spawn represents a genome - a collection of colored
// squares.
var Spawn = function(nodes) {
    var _fitness = null; // a cache of our fitness
    this.nodes = nodes; // the squares that make up our image

    this.fitness = function() {
        // fitness is simply a function of how close to yellow we are.
        // This is defined through euclidian distance. Smaller fitnesses
        // are better.

        if (_fitness === null) {
            _fitness = 0;
            for (var i = 0; i < nodes.length; i++) {
                _fitness += Math.pow(-nodes[i].color[0], 2) + 
                            Math.pow(255 - nodes[i].color[1], 2) +
                            Math.pow(255 - nodes[i].color[2], 2);
            }
            _fitness /= 255*255*3*nodes.length; // divide by the worst possible distance
        }

        return _fitness;
    };

    this.mutate = function() {
        // reset our cached fitness to unknown
        _fitness = null;

        var health = this.fitness() * fitness_influence;
        var width = $output_canvas[0].width;
        var height = $output_canvas[0].height;

        for (var i = 0; i < nodes.length; i++) {
            // Sometimes (most times) we don't mutate
            if (Math.random() > mutation_rate) {
                continue;
            }

            // Mutate the colors. 
            for (var j = 0; j < 3; j++) {
                // colors can move by up to 32 in either direction
                nodes[i].color[j] += 64 * (.5 - Math.random()) * health;
                // make sure that our colors stay between 0 and 255
                nodes[i].color[j] = Math.max(0, Math.min(255, nodes[i].color[j]));
            }
        }
    };

    this.draw = function(ctx) {
        // This draw function is a little overly generic in that it supports
        // arbitrary polygons.
        ctx.save();
        ctx.fillStyle = clear_color;
        ctx.fillRect(0, 0, ctx.canvas.width, ctx.canvas.height);
        for (var i = 0; i < nodes.length; i++) {
            ctx.fillStyle = 'rgba(' + Math.floor(nodes[i].color[0]) + ',' + Math.floor(nodes[i].color[1]) + ',' + Math.floor(nodes[i].color[2]) + ',' + nodes[i].color[3] + ')';
            ctx.beginPath();
            ctx.moveTo(nodes[i].points[0][0], nodes[i].points[0][1]);
            for (var j = 1; j < nodes[i].points.length; j++) {
                ctx.lineTo(nodes[i].points[j][0], nodes[i].points[j][1]);
            }
            ctx.fill();
            ctx.closePath();
        }
        ctx.restore();
    };
};

Spawn.from_parents = function(parents) {
    // Given two parents, mix them together to get another spawn
    var nodes = [];
    for (var i = 0; i < parents[0].nodes.length; i++) {
        if (Math.random() > 0.5) {
            nodes.push($.extend({}, parents[0].nodes[i]));
        }
        else {
            nodes.push($.extend({}, parents[1].nodes[i]));
        }
    }
    var s = new Spawn(nodes);
    s.mutate();

    return s;
};

Spawn.random = function(width, height) {
    // Return a complete random spawn.
    var nodes = [];
    for (var i = 0; i < width * height; i += 10) {
        var n = {
            color: [Math.random() * 256, Math.random() * 256, Math.random() * 256, 1],
            points: [
                [i % width, Math.floor(i / width) * 10],
                [(i % width) + 10, Math.floor(i / width) * 10],
                [(i % width) + 10, Math.floor(i / width + 1) * 10],
                [i % width, Math.floor(i / width + 1) * 10],
                ]
        };
        nodes.push(n);
    }
    return new Spawn(nodes);
};

var select_parents = function(gene_pool) {
    if (use_rank_selection) {
        return rank_selection(gene_pool);
    }
    return roulette_selection(gene_pool);
};

var roulette_selection = function(gene_pool) {
    var mother = null;
    var father = null;
    gene_pool = gene_pool.slice(0);
    var sum_fitness = 0;
    var i = 0;
    for (i = 0; i < gene_pool.length; i++) {
        sum_fitness += gene_pool[i].fitness();
    }
    var choose = Math.floor(Math.random() * sum_fitness);
    for (i = 0; i < gene_pool.length; i++) {
        if (choose <= gene_pool[i].fitness()) {
            mother = gene_pool[i];
            break;
        }
        choose -= gene_pool[i].fitness();
    }
    // now remove the mother and repeat for the father
    sum_fitness -= mother.fitness();
    gene_pool.splice(i, 1);
    choose = Math.floor(Math.random() * sum_fitness);
    for (i = 0; i < gene_pool.length; i++) {
        if (choose <= gene_pool[i].fitness()) {
            father = gene_pool[i];
            break;
        }
        choose -= gene_pool[i].fitness();
    }
    return [mother, father];
};

var rank_selection = function(gene_pool) {
    gene_pool = gene_pool.slice(0);
    gene_pool.sort(function(a, b) {
        return b.fitness() - a.fitness();
    });

    var choose_one = function() {
        var sum_fitness = (gene_pool.length + 1) * (gene_pool.length / 2);
        var choose = Math.floor(Math.random() * sum_fitness);
        for (var i = 0; i < gene_pool.length; i++) {
            // figure out the sume of the records up to this point. if we exceed
            // our chosen spot, we've found our spawn.
            if ((i + 1) * (i / 2) >= choose) {
                return gene_pool.splice(i, 1)[0];
            }
        }

        return gene_pool.pop(); // last element, if for some reason we get here
    };

    var mother = choose_one();
    var father = choose_one();
    return [mother, father];
};

var start = function() {
    // Initialize our first generation
    var width = $output_canvas[0].width;
    var height = $output_canvas[0].height;

    generation = 0;
    children = [];
    for (var j = 0; j < num_offspring; j++) {
        children.push(Spawn.random(width, height));
    }

    // sort by fitness so that our best comes first
    children.sort(function(a, b) {
        return a.fitness() - b.fitness();
    });
    best_spawn = children[0];
    best_fitness = best_spawn.fitness();
    best_spawn.draw(output_ctx);
};

var generate = function(spawn_pool) {
    // generate a new set of offspring
    var offspring = [];
    for (var i = 0; i < num_offspring; i++) {
        var parents = select_parents(spawn_pool);
        // odds of crossover decrease as we get closer
        if (Math.random() * best_fitness < crossover_rate) {
            var s = Spawn.from_parents(parents);
        }
        else {
            // quick hack to copy our mother, with possible mutation
            var s = Spawn.from_parents([parents[0], parents[0]]);
        }
        offspring.push(s);
    }
    // select a number of best from the parent pool (elitism)
    for (var i = 0; i < elitism; i++) {
        offspring.push(spawn_pool[i]);
    }

    // sort our offspring by fitness (this includes the parents from elitism). Fittest first.
    offspring.sort(function(a, b) {
        return a.fitness() - b.fitness();
    });
    // pick off the number that we want
    offspring = offspring.slice(0, num_offspring);
    best_spawn = offspring[0];
    best_fitness = best_spawn.fitness();
    best_spawn.draw(output_ctx);
    generation++;

    return offspring;
};


var average_fitness = function(generation) {
    debugger;
    var a = 0;
    for (var i = 0; i < generation.length; i++) {
        a += generation[i].fitness();
    }
    return a / generation.length;
};

//Draw yellow and then initialize our first generation
input_ctx.fillStyle = 'yellow';
input_ctx.fillRect(0, 0, input_ctx.canvas.width, input_ctx.canvas.height);
start();

// Our loop function. Use setTimeout to prevent things from freezing
var gen = function() {
    children = generate(children);
    $gen_span.text('Generation: ' + generation);
    $best_fit.text('Best Fitness: ' + best_fitness);
    $avg_fit.text('Avg. Fitness: ' + average_fitness(children));
    if (generation % 100 === 0) {
        console.log('Generation', generation);
        console.log('Fitness', best_fitness);
    }
    setTimeout(gen, 1);
};
gen();​

我已经对代码进行了注释,以尝试使解析变得容易。基本思想很简单:

  1. 从当前一代中选择 1 个或 2 个父母
  2. 把那一两个父母混在一起
  3. 稍微改变结果并将其添加到下一代
  4. 选择最好的少数父母(示例中的 1 个)并将它们添加到下一代
  5. 对 N 个结果进行排序和分割,并将它们用于下一代(可能是父母和后代的混合体)
  6. 冲洗并重复

输出永远不会接近黄色。它很快陷入一种看起来很糟糕的稳定状态。我哪里出错了?

4

1 回答 1

1

解决了。它在“from_parents”方法中:

    if (Math.random() > 0.5) {
        nodes.push($.extend({}, parents[0].nodes[i]));
    }
    else {
        nodes.push($.extend({}, parents[1].nodes[i]));
    }

$.extend()正在做一个浅拷贝。显而易见的解决方案是要么将true其作为导致深层复制的第一个参数。然而,这在性能方面是非常缓慢的。更好的解决方案是$.extend()从该代码块中完全删除,而是将其移至方法,仅当节点实际上要更改时mutate()我才调用该方法。$.extend()换句话说,它变成了写时复制。

另外,我在适应度函数中输入的颜色是错误的:P

于 2012-12-15T14:11:03.153 回答