Press "Enter" to skip to content

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

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

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

 

package main
import (
	"fmt"
	"math/rand"
	"sort"
)
const (

	TaskNum = 100

	NodeNum = 10

	TaskLengthMin = 10

	TaskLengthMax = 100

	NodeSpeedMin = 10

	NodeSpeedMax = 100

	IteratorNum = 10000

	ChromosomeNum = 20

	CopyPercent = 0.2

	CrossoverNum = ChromosomeNum * (1 - CopyPercent)
)

var tasks []int

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
}

func maxn(selectionProbability []float64, n int) (indexs []int) {

	m := make(map[float64]int)
	for k, v := range selectionProbability {
		m[v] = k
	}

	var keys []float64
	for k := range m {
		keys = append(keys, k)
	}
	sort.Float64s(keys)

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

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注