遗传算法(2)

遗传算法核心表示

/**
 * 交叉遗传的概率Pc
 * 遗传变异的概率Pm
 * 种群规模M
 * 终止进化代数G
 * 当产生出一个个体的适应度超过给定Tf,则终止进化
 */
 步骤1
 初始化产生 Pc Pm M G Tf参数并随机生成第一代种群population,简称P1
 初始化P = P1
 do {
 	计算P中每一个个体的适应度F(i)
 	初始化空种群newP
 	do {
 		根据适应度比例选择算法选择出2个个体
 		if (rnd1 < Pc) {
 			进行交叉操作
 		}
 		if (rnd2 < Pm) { 进行变异操作 } 将两个操作后的个体放进newP中,即产生的新个体进入新的种群 } until (M个个体被创建) P = newP } until(任何染色体满足适应度或者繁殖代数>G)

在这里我们看到了,这个随机选择以及产生后代的方式需要斟酌,如果设定的不好,那么很有可能这个种族最后就灭绝了,算个说话也就是我们没有得到我们的解。
大自然这里还有一个规律叫做:物竞天择 适者生存
在我们这里也需要对算法进行优化:
择优 为了防止进化过程中产生的最优解被交叉和变异所破坏,可以将每一代中的最优解原封不动的复制到下一代中。

具体实例

  • 理解实例
  • 求 f(x1, x2) = x1^3 + x2^2 + (x1 * (x1 – x2))的最大值,其中x1属于{-5, -3, 1, 3, 5}, x2属于{0, 2, 4}
    当然这个题目解法很多,穷举方法也非常的迅速。这个例子为了更加透彻的理解遗传算法。
    步骤1 编码
    我们此处定义隐射关系为
    [
    [0] = -5,
    [1] = -3,
    [2] = 0,
    [3] = 1,
    [4] = 2,
    [5] = 3,
    [6] = 4,
    [7] = 5
    ]
    8可以用4位二进制表示,而x1和x2则用8位二进制即可完成验证比如{0110|0110}则表示[x1 = 3, x2 = 4]
    步骤2 生成种群,注意生成种群的数量以及作用域关系,写一段js代码来进行测试

    步骤3 随机选择父代进行通过交叉和变异生成子代(选出适应度较高的进行)

    代码示意,因为没有变异以及编码是否可以有更好的办法,所以只为显示整体过程

    console.log("遗传算法");
    var everyone = [];
    var number = 200;
    function in_array(search, array){
        for(var i in array){
            if(array[i]==search){
                return true;
            }
        }
        return false;
    }
    var genChromosome = function(scope) {
        var timestamp = new Date().getTime();
        var index = Math.ceil(Math.random() * timestamp) % scope.length;
        var chromosome = scope[index].toString(2);
        while (chromosome.length < 4) {
            chromosome = "0" + chromosome;
        }
        return chromosome;
    }
    
    // 计算每个的适应度
    var calFitness = function(omo) {
        var codes = [-5, -3, 0, 1, 2, 3, 4, 5];
        var arr1 = [-5, -3, 1, 3, 5];
        var arr2 = [0, 2, 4];
        var x1 = codes[parseInt(omo.substr(0, 4), 2)];
        var x2 = codes[parseInt(omo.substr(4, 4), 2)];
        if (x1 != undefined && x2 != undefined && in_array(x1, arr1) && in_array(x2, arr2)) {
            return x1 * x1 * x1 + x2 * x2 + (x1 * (x1 - x2));
        }
        return -9999;
    }
    
    function sortNumber(a,b) 
    { 
        return a - b 
    } 
    
    $('#genUnit').click(function() {
        $('#geti').html('');
        var scope1 = [0, 1, 3, 5, 7];
        var scope2 = [2, 4, 6];
        // 生成50组个体
        everyone = [];
        for (var i = 0; i < number; i++) {
            var new_omo = genChromosome(scope1) + genChromosome(scope2);
            everyone.push (new_omo);
        }
        for (var i = 0; i < everyone.length; i++) {
            $('#geti').append(everyone[i] + " ");
            if ((i + 1) % 10 == 0) {
                $('#geti').append("
    "); } } }); // 交叉函数 var cross = function(omo1, omo2) { // 针对这个,四位是一个染色体特征控制 var ret = ""; var timestamp = new Date().getTime(); var rnd = Math.ceil(Math.random() * timestamp) % 4; if (rnd <= 1) { // 互换前四位 for (var i = 0; i < 4; i++) { var tmp = omo1[i]; omo1[i] = omo2[i]; omo2[i] = tmp; } } else if (rnd <= 3) { // 互换后四位 for (var i = 4; i < 8; i++) { var tmp = omo1[i]; omo1[i] = omo2[i]; omo2[i] = tmp; } } var rnd_next = Math.ceil(Math.random() * timestamp) % 2; if (rnd_next == 0) { ret = omo1; } else { ret = omo2; } return ret; } // 变异函数 var variation = function(omo1, omo2) { // 变异某一位,然后做交叉运算 // 这里暂时不需要,所以直接进行选择 var timestamp = new Date().getTime(); var rnd_next = Math.ceil(Math.random() * timestamp) % 2; if (rnd_next == 0) { ret = omo1; } else { ret = omo2; } return ret; } // 判断结束 var finish = function() { // 这里直接看第五十代 } $('#genNextUnit').click(function() { if (everyone.length == 0) { return } // 至少5代且满足best适应值占75%或最多50代 var g_num = 0; while (g_num < 50) { // 假设淘汰20%,最优的保留,剩下随机 var fitness_score = []; for (var i = 0; i < everyone.length; i++) { fitness_score.push(parseInt(calFitness(everyone[i]))); } fitness_score.sort(sortNumber); var over = Math.ceil(fitness_score.length * 0.2) for (var i = 0; i < over; i++) { fitness_score.shift(); } var best = fitness_score[fitness_score.length - 1]; // 生成子代 var new_generation = []; while (new_generation.length < number) { var curr_unit; // 选择 var timestamp = new Date().getTime(); var choose_fitness1 = everyone[Math.ceil(Math.random() * timestamp) % everyone.length]; var choose_fitness2 = everyone[Math.ceil(Math.random() * timestamp) % everyone.length]; if (calFitness(choose_fitness1) == best && calFitness(choose_fitness2) == best) { // 进行交叉 curr_unit = cross(choose_fitness1, choose_fitness2) if (Math.ceil(Math.random() * timestamp) % 100 < 2) { // 进行变异 curr_unit = variation(choose_fitness1, choose_fitness2) } } else if (Math.ceil(Math.random() * timestamp) % 100 > 50) { // 进行交叉 curr_unit = cross(choose_fitness1, choose_fitness2) // 进行变异 if (Math.ceil(Math.random() * timestamp) % 100 < 2) { // 进行变异 curr_unit = variation(choose_fitness1, choose_fitness2) } } if (curr_unit != undefined) { if (calFitness(curr_unit) > -9999) { new_generation.push(curr_unit); } } } everyone = new_generation; g_num = g_num + 1; } var fitness_score = []; for (var i = 0; i < everyone.length; i++) { fitness_score.push(parseInt(calFitness(everyone[i]))); } console.log(everyone[0]); fitness_score.sort(sortNumber); var best_number = fitness_score[fitness_score.length - 1]; $('#zidai').html(best_number); // 01110010 });

    欢迎留言

    avatar
      Subscribe  
    Notify of