**假设有N个任务，需要负载均衡器分配给M个服务器节点去处理。每个任务的任务长度、每台服务器节点(下面简称“节点”)的处理速度已知，请给出一种任务分配方式，使得所有任务的总处理时间最短。**
```go
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)
}
```
有疑问加站长微信联系（非本文作者））
