golang 实现的一个遗传算法的例子

假设有N个任务，需要负载均衡器分配给M个服务器节点去处理。每个任务的任务长度、每台服务器节点(下面简称“节点”)的处理速度已知，请给出一种任务分配方式，使得所有任务的总处理时间最短。

package main

import (
    "fmt"
    "math/rand"
    "sort"
)

const (
    // TaskNum 任务数为100
    TaskNum = 100
    // NodeNum 计算节点数为10
    NodeNum = 10
    // TaskLengthMin 任务长度最小值10
    TaskLengthMin = 10
    // TaskLengthMax 任务长度最大值100
    TaskLengthMax = 100
    // NodeSpeedMin 节点计算能力最小值10
    NodeSpeedMin = 10
    // NodeSpeedMax 节点计算能力最大值100
    NodeSpeedMax = 100
    // IteratorNum 迭代次数100
    IteratorNum = 10000
    // ChromosomeNum 染色体个数10
    ChromosomeNum = 20
    // CopyPercent 复制比例0.2
    CopyPercent = 0.2
    // CrossoverNum 由染色体的数量和复制比例确定，保证每一代的染色体数量都是相同的
    CrossoverNum = ChromosomeNum * (1 - CopyPercent)
)

//tasks[i]表示第i个任务的长度
var tasks []int

//nodes[i]表示第i个节点的处理速度
var nodes []int

// 给指定长度的切片的值赋随机值
func randomIntSlice(length, min, max int) []int {
    m := make([]int, length)
    for i := 0; i < length; i++ {
        m[i] = rand.Intn(max-min) + min
    }
    return m
}

// 生成新一代的染色体
func createGeneration(chromosomeMatrix [][]int, selectionProbability []float64) [][]int {
    newChromosomeMatrix := make([][]int, ChromosomeNum)
    // 第一代
    if chromosomeMatrix == nil {
        for i := 0; i < ChromosomeNum; i++ {
            newChromosomeMatrix[i] = make([]int, TaskNum)
            for j := 0; j < TaskNum; j++ {
                newChromosomeMatrix[i][j] = rand.Intn(NodeNum)
            }
        }
        return newChromosomeMatrix
    }
    // 交叉
    newChromosomeMatrix = crossover(chromosomeMatrix, selectionProbability)
    // 变异
    newChromosomeMatrix = mutation(newChromosomeMatrix)
    // 复制
    newChromosomeMatrix = copy(newChromosomeMatrix, chromosomeMatrix, selectionProbability)
    return newChromosomeMatrix
}

// 交叉
func crossover(chromosomeMatrix [][]int, selectionProbability []float64) (newChromosomeMatrix [][]int) {
    for i := 0; i < CrossoverNum; i++ {
        //父亲染色体
        chromosomeBa := chromosomeMatrix[rws(selectionProbability)]
        //母亲染色体
        chromosomeMa := chromosomeMatrix[rws(selectionProbability)]
        //随机一个交叉位置
        index := rand.Intn(TaskNum)
        //儿子染色体
        var chromosomeSon []int
        chromosomeSon = append(chromosomeSon, chromosomeBa[:index]...)
        chromosomeSon = append(chromosomeSon, chromosomeMa[index:]...)
        newChromosomeMatrix = append(newChromosomeMatrix, chromosomeSon)
    }
    return
}

// 变异
func mutation(chromosomeMatrix [][]int) [][]int {
    //随机找一个染色体
    index := rand.Intn(CrossoverNum)
    //随机找一个任务
    taskIndex := rand.Intn(TaskNum)
    //随机找一个节点
    nodeIndex := rand.Intn(NodeNum)
    chromosomeMatrix[index][taskIndex] = nodeIndex
    return chromosomeMatrix
}

// 复制
func copy(chromosomeMatrix [][]int, oldChromosomeMatrix [][]int, selectionProbability []float64) [][]int {
    indexs := maxn(selectionProbability, ChromosomeNum-CrossoverNum)
    for _, i := range indexs {
        chromosomeMatrix = append(chromosomeMatrix, oldChromosomeMatrix[i])
    }
    return chromosomeMatrix
}

// 找到适应度大的的n个染色体的索引
func maxn(selectionProbability []float64, n int) (indexs []int) {
    //将一维切片，转化成map,key为selectionProbability的值,value为selectionProbability的索引
    m := make(map[float64]int)
    for k, v := range selectionProbability {
        m[v] = k
    }

    //将m的key保存到切片
    var keys []float64
    for k := range m {
        keys = append(keys, k)
    }

    sort.Float64s(keys)

    //获取前n个keys对应m的值
    for i := 0; i < n; i++ {
        indexs = append(indexs, m[keys[len(keys)-i-1]])
    }
    return
}

// 轮盘赌博算法，返回染色体索引
func rws(selectionProbability []float64) (index int) {
    sum := 0.0
    r := rand.Float64()
    for index < len(selectionProbability) {
        sum += selectionProbability[index]
        if sum >= r {
            break
        }
        index++
    }
    return
}

// 计算每一代的最佳时间
func calCalTime(chromosomeMatrix [][]int) float64 {
    min := 0.0
    for i := 0; i < len(chromosomeMatrix); i++ {
        sum := 0.0
        for j := 0; j < len(chromosomeMatrix[0]); j++ {
            nodeIndex := chromosomeMatrix[i][j]
            sum += float64(tasks[j]) / float64(nodes[nodeIndex])
        }
        if min == 0.0 || sum < min {
            min = sum
        }
    }
    return min
}

// 计算适应度函数
func calAdaptability(chromosomeMatrix [][]int) (selectionProbability []float64) {
    var adaptability []float64
    for i := 0; i < len(chromosomeMatrix); i++ {
        sum := 0.0
        for j := 0; j < len(chromosomeMatrix[0]); j++ {
            nodeIndex := chromosomeMatrix[i][j]
            sum += float64(tasks[j]) / float64(nodes[nodeIndex])
        }
        adaptability = append(adaptability, 1.0/sum)
    }

    // 计算基数
    total := 0.0
    for _, v := range adaptability {
        total += v
    }

    //计算选择概率
    for _, v := range adaptability {
        selectionProbability = append(selectionProbability, v/total)
    }
    return selectionProbability
}

// 开始迭代
func goSearch(iteratorNum, chromosomeNum int) {
    chromosomeMatrix := createGeneration(nil, nil)
    fmt.Printf("第0代所需时间:%f \n", calCalTime(chromosomeMatrix))

    for i := 0; i < iteratorNum; i++ {
        selectionProbability := calAdaptability(chromosomeMatrix)
        chromosomeMatrix = createGeneration(chromosomeMatrix, selectionProbability)
        fmt.Printf("第%d代所需时间:%f \n", i+1, calCalTime(chromosomeMatrix))
    }

}

func main() {
    tasks = randomIntSlice(TaskNum, TaskLengthMin, TaskLengthMax)
    nodes = randomIntSlice(NodeNum, NodeSpeedMin, NodeSpeedMax)

    goSearch(IteratorNum, ChromosomeNum)
}