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

mqyang56 · · 322 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
**假设有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) } ```

入群交流(和以上内容无关):Go中文网 QQ 交流群:798786647 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

322 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传