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)
}