个人中心
gpt4 book ai didi

genetic-algorithm - 为什么我的遗传算法很糟糕(为什么不收敛)？

转载 作者：行者123 更新时间：2023-12-01 13:41:27 24 4
gpt4 key购买 nike

我用遗传算法编写了一个快速实验。它只需要一个正方形网格，并尝试改变它们的颜色，使它们都变成黄色。它悲惨地失败了，我似乎无法弄清楚为什么。我提供了一个指向演示工作代码的 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 个 parent
  2. 将一两个 parent 混合在一起
  3. 对结果稍作变异，加入到下一代
  4. 选出最好的几个父本(例子中的1个)加入下一代
  5. 对 N 个结果进行排序和分割，并将它们用于下一代(可能是 parent 和后代的混合体)
  6. 冲洗并重复

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

最佳答案

解决了。它在“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

关于genetic-algorithm - 为什么我的遗传算法很糟糕(为什么不收敛)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13887018/

24 4 0
文章推荐： Java数据库: bind multiple instances of a class to one instance of another class
文章推荐： java - Play Framework 无法创建 Intellij 项目
文章推荐： java - ubuntu 上的开普勒 glassfish
文章推荐： reactjs - 是否可以在其构造函数签名中安全地解构 ES6 React Component 类？
行者123
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com