2018-03-12 19:16:20

go-遗传算法-简单实现

ga(genetic algorithm)遗传算法
x+10*sin(5*x)+7*cos(4*x) 在[0,9]的最大值
代码
core

package core

import (
    "math"
    "math/rand"
    "time"
)

// Ga 遗传算法
type Ga struct {
    // 染色体长度
    Length int
    // 种群数量
    Count int
    // 种群
    Population []int
    //retain 适应度
    retain float64
    // 幸运者
    random float64
    // 变异几率
    mutation float64
}

func init() {
    rand.Seed(time.Now().UnixNano()) //利用当前时间的UNIX时间戳初始化rand包
}

// NewGa 初始化
func NewGa(length, count int, retain, random, mutation float64) Ga {
    ga := Ga{
        Length:   length,
        Count:    count,
        retain:   retain,
        random:   random,
        mutation: mutation,
    }
    ga.Population = make([]int, count)
    for i := 0; i < count; i++ {
        tmp := 0
        // 随机生成染色体
        for j := 0; j < length; j++ {
            tmp |= (1 << uint(j)) * rand.Intn(2)
        }
        ga.Population[i] = tmp
    }
    return ga
}

// Evolve 进化
func (ga *Ga) Evolve() {
    // 选择
    ga.Selection()
    // 繁衍
    ga.Crossover()
    // 变异
    ga.Mutation()
}

// Selection 选择
func (ga *Ga) Selection() {
    // 计算适应度
    fit := ga.Fitness()
    // 排序适应度
    for i := 0; i < ga.Count-1; i++ {
        for j := i + 1; j < ga.Count; j++ {
            if fit[i] <= fit[j] {
                fit[i], fit[j] = fit[j], fit[i]
                // 种群与适应度统一
                ga.Population[i], ga.Population[j] = ga.Population[j], ga.Population[i]
            }
        }
    }
    // 选择适应度强的染色体
    flag := int(float64(len(fit)) * ga.retain)
    parents := ga.Population[:flag]
    for _, v := range ga.Population[flag:] {
        if rand.Float64() < ga.random {
            parents = append(parents, v)
        }
    }
    ga.Population = parents
}

// Fitness 计算适应度
func (ga Ga) Fitness() []float64 {
    t := 1 << uint(ga.Length)
    f := make([]float64, 0, ga.Count)
    for idx := 0; idx < ga.Count; idx++ {
        gf := float64(ga.Population[idx]) * 9.0 / float64(t)
        // 计算函数值
        f = append(f, gf+10*math.Sin(5*gf)+7*math.Cos(4*gf))
    }
    return f
}

// Crossover 繁衍
func (ga *Ga) Crossover() {
    pLen := len(ga.Population)
    // 需要的子代数量
    targetCount := ga.Count - pLen
    // 子代种群
    children := make([]int, 0, targetCount)
    for targetCount > 0 {
        male := rand.Intn(pLen)
        female := rand.Intn(pLen)
        if male != female {
            targetCount--
            // 随机交叉点
            crossPos := rand.Intn(ga.Length)
            // 生成掩码
            mask := 0
            for i := 0; i < crossPos; i++ {
                mask |= (1 << uint(i))
            }
            male = ga.Population[male]
            female = ga.Population[female]
            // 孩子获得父亲在交叉点之前的基因,和目前交叉点之后的基因
            child := ((male & mask) | (female &^ mask)) & (1<<uint(ga.Length) - 1)
            children = append(children, child)
        }
    }
    // 经过繁殖后的新种群
    ga.Population = append(ga.Population, children...)
}

// Mutation 变异
func (ga Ga) Mutation() {
    for idx := 0; idx < ga.Count; idx++ {
        if rand.Float64() < ga.mutation {
            r := rand.Intn(ga.Length)
            ga.Population[idx] ^= 1 << (uint(r))
        }
    }
}

// Resutl 结果
func (ga *Ga) Resutl() float64 {
    // 计算适应度
    fit := ga.Fitness()
    // 排序适应度
    for i := 0; i < ga.Count-1; i++ {
        for j := i + 1; j < ga.Count; j++ {
            if fit[i] <= fit[j] {
                fit[i], fit[j] = fit[j], fit[i]
                // 种群与适应度统一
                ga.Population[i], ga.Population[j] = ga.Population[j], ga.Population[i]
            }
        }
    }
    t := 1 << uint(ga.Length)
    return float64(ga.Population[0]) * 9.0 / float64(t)
}

main

package main

import (
    "fmt"
    "ga/core"
)

func main() {
    ga := core.NewGa(17, 600, 0.2, 0.5, 0.01)
    for i := 0; i < 400; i++ {
        ga.Evolve()
    }
    fmt.Println(ga.Resutl())
}

本文链接:https://www.paishouba.com/post/ga-simple.html

-- EOF --

Comments