Go語言中如何實現(xiàn)一個遺傳算法

本篇內(nèi)容介紹了“Go語言中如何實現(xiàn)一個遺傳算法”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

話不多說，讓我們開始從代碼說起吧!***個例子與我以前做過的很類似：找到一個二次的最小值。

type GeneticAlgorithmSettings struct {   PopulationSize int   MutationRate int   CrossoverRate int   NumGenerations int   KeepBestAcrossPopulation bool }  type GeneticAlgorithmRunner interface {   GenerateInitialPopulation(populationSize int) []interface{}   PerformCrossover(individual1, individual2 interface{}, mutationRate int) interface{}   PerformMutation(individual interface{}) interface{}   Sort([]interface{}) }

我立馬定義了一組設(shè)置，以便在稍后啟動的算法中用到。

第二部分的GeneticAlgorithmRunner這個看起來有點(diǎn)奇怪。GeneticAlgorithmRunner是一個接口，詢問如何生成初始種群，執(zhí)行corssovers和mutataions，并對答案進(jìn)行排序，以便在Population中保持***的個體，這樣下一代才會更加優(yōu)秀。我認(rèn)為這看起來很奇怪，因為“接口”通常用于面向?qū)ο蟮恼Z言，通常會要求對象實現(xiàn)某些特性和方法。這里沒有什么差別。這一小段代碼實際上是在說，它正在請求一些東西來定義這些方法的細(xì)節(jié)。我是這樣做的:

type QuadraticGA struct {}  func (l QuadraticGA) GenerateInitialPopulation(populationSize int) []interface{}{   initialPopulation := make([]interface{}, 0, populationSize)   for i:= 0; i < populationSize; i++ {     initialPopulation = append(initialPopulation, makeNewEntry())   }   return initialPopulation }  func (l QuadraticGA) PerformCrossover(result1, result2 interface{}, _ int) interface{}{   return (result1.(float64) + result2.(float64)) / 2 }  func (l QuadraticGA) PerformMutation(_ interface{}, _ int) interface{}{   return makeNewEntry() }  func (l QuadraticGA) Sort(population []interface{}){   sort.Slice(population, func(i, j int) bool {     return calculate(population[i].(float64)) > calculate(population[j].(float64))   }) }

更奇怪的是，我從來沒有提到過這些方法的接口。請記住，因為沒有對象，也沒有繼承。QuadraticGA結(jié)構(gòu)體是一個空白對象，隱式地作為GeneticAlgorithmRunner。每個必需的方法都在括號中綁定到該結(jié)構(gòu)體，就像Java中的“@  override”?，F(xiàn)在，結(jié)構(gòu)體和設(shè)置需要傳遞給運(yùn)行該算法的模塊。

settings := ga.GeneticAlgorithmSettings{    PopulationSize: 5,    MutationRate: 10,    CrossoverRate: 100,    NumGenerations: 20,    KeepBestAcrossPopulation: true, }  best, err := ga.Run(QuadraticGA{}, settings)  if err != nil {    println(err) }else{    fmt.Printf("Best: x: %f  y: %f\n", best, calculate(best.(float64))) }

很簡單,對吧?“QuadraticGA  {}”只是簡單地創(chuàng)建了該結(jié)構(gòu)的一個新實例，其余的則由Run()方法完成。該方法返回搜索結(jié)果和發(fā)生的任何錯誤，因為Go不相信try /  catch——另一場戰(zhàn)爭作者采取了嚴(yán)格的設(shè)計立場。

現(xiàn)在來計算每個項的性能，以求二次函數(shù)求出的二次函數(shù)來求出一個新的X值的方法:

func makeNewEntry() float64 {    return highRange * rand.Float64() }  func calculate(x float64) float64 {    return  math.Pow(x, 2) - 6*x + 2 // minimum should be at x=3 }

既然已經(jīng)為二次實現(xiàn)創(chuàng)建了接口，那么GA本身需要完成:

func Run(geneticAlgoRunner GeneticAlgorithmRunner, settings GeneticAlgorithmSettings) (interface{}, error){     population := geneticAlgoRunner.GenerateInitialPopulation(settings.PopulationSize)     geneticAlgoRunner.Sort(population)     bestSoFar := population[len(population) - 1]     for i:= 0; i < settings.NumGenerations; i++ {        newPopulation := make([]interface{}, 0, settings.PopulationSize)        if settings.KeepBestAcrossPopulation {          newPopulation = append(newPopulation, bestSoFar)       }        // perform crossovers with random selection       probabilisticListOfPerformers := createStochasticProbableListOfIndividuals(population)        newPopIndex := 0       if settings.KeepBestAcrossPopulation{          newPopIndex = 1       }       for ; newPopIndex < settings.PopulationSize; newPopIndex++ {          indexSelection1 := rand.Int() % len(probabilisticListOfPerformers)          indexSelection2 := rand.Int() % len(probabilisticListOfPerformers)           // crossover          newIndividual := geneticAlgoRunner.PerformCrossover(             probabilisticListOfPerformers[indexSelection1],             probabilisticListOfPerformers[indexSelection2], settings.CrossoverRate)           // mutate          if rand.Intn(101) < settings.MutationRate {             newIndividual = geneticAlgoRunner.PerformMutation(newIndividual)          }           newPopulation = append(newPopulation, newIndividual)       }        population = newPopulation        // sort by performance       geneticAlgoRunner.Sort(population)        // keep the best so far       bestSoFar = population[len(population) - 1]     }     return bestSoFar, nil }  func createStochasticProbableListOfIndividuals(population []interface{}) []interface{} {     totalCount, populationLength:= 0, len(population)    for j:= 0; j < populationLength; j++ {       totalCount += j    }     probableIndividuals := make([]interface{}, 0, totalCount)    for index, individual := range population {       for i:= 0; i < index; i++{          probableIndividuals = append(probableIndividuals, individual)       }    }     return probableIndividuals }

很像以前，一個新的人口被創(chuàng)造出來，人口的成員將會世代交配，而他們的后代可能攜帶突變。一個人的表現(xiàn)越好，就越有可能交配。隨著時間的推移，算法收斂到***的答案，或者至少是一個相當(dāng)不錯的答案。

那么當(dāng)它運(yùn)行時，它返回了什么呢?

Best: x: 3.072833 y: -6.994695

不壞!由于人口規(guī)模只有5、20代，而且輸入的范圍被限制在[0 100]，這一搜索就釘在了頂點(diǎn)上。

現(xiàn)在，您可能想知道為什么我定義了所有的接口方法來返回“接口{}”。這就像Go和generics一樣。沒有對象，因此沒有對象類型返回，但是沒有描述的大小的數(shù)據(jù)仍然可以在堆棧上傳遞。這本質(zhì)上也是這個返回類型的含義:它傳遞一些已知的和類似的類型的對象。有了這個“泛型”，我就可以將GA移動到它自己的包中，并將相同的代碼移到多個不同類型的數(shù)據(jù)上。

我們有兩個輸入的3D二次方程，而不是一個二維二次方程的單個輸入。接口方法只需要很小的改變:

type Quad3D struct {    x, y float64 } func makeNewQuadEntry(newX, newY float64) Quad3D {    return Quad3D{       x: newX,       y: newY,    } }  func calculate3D(entry Quad3D) float64 {    return math.Pow(entry.x, 2)- 6 * entry.x + math.Pow(entry.y, 2)- 6 * entry.y + 2 }  type Quadratic3dGA struct { }  func (l Quadratic3dGA) GenerateInitialPopulation(populationSize int)[]interface{}{     initialPopulation := make([]interface{}, 0, populationSize)    for i:= 0; i < populationSize; i++ { initialPopulation = append(initialPopulation, makeNewQuadEntry(makeNewEntry(), makeNewEntry())) } return initialPopulation } func (l Quadratic3dGA) PerformCrossover(result1, result2 interface{}, mutationRate int) interface{}{ r1Entry, r2Entry := result1.(Quad3D), result2.(Quad3D) return makeNewQuadEntry((r1Entry.x + r2Entry.x) / 2, (r1Entry.y + r2Entry.y) / 2,) } func (l Quadratic3dGA) PerformMutation(_ interface{}) interface{}{ return makeNewQuadEntry(makeNewEntry(), makeNewEntry()) } func (l Quadratic3dGA) Sort(population []interface{}){ sort.Slice(population, func(i, j int) bool { return calculate3D(population[i].(Quad3D)) > calculate3D(population[j].(Quad3D))    }) }  func quadratic3dMain(){    settings := ga.GeneticAlgorithmSettings{       PopulationSize: 25,       MutationRate: 10,       CrossoverRate: 100,       NumGenerations: 20,       KeepBestAcrossPopulation: true,    }     best, err := ga.Run(Quadratic3dGA{}, settings)    entry := best.(Quad3D)     if err != nil {       println(err)    }else{       fmt.Printf("Best: x: %f  y: %f  z: %f\n", entry.x, entry.y, calculate3D(entry))    } }

而不是到處都是float64s，任何地方都可以通過Quad3D的條目;每一個都有一個X和一個Y值。對于創(chuàng)建的每個條目，都使用contructor  makeNewQuadEntry創(chuàng)建。Run()方法中的代碼都沒有更改。

當(dāng)它運(yùn)行時，我們得到這個輸出:

Best: x: 3.891671 y: 4.554884 z: -12.787259

很接近了!

哦，我忘了說走快了!在Java中執(zhí)行此操作時，即使使用相同的設(shè)置，也會有明顯的等待時間。在一個相對較小的范圍內(nèi)求解二次方程并不是很復(fù)雜，但它對一個人來說是值得注意的。

Go是本地編譯的，比如C。當(dāng)二進(jìn)制執(zhí)行時，它似乎馬上就吐出一個答案。這里有一個簡單的方法來度量每次運(yùn)行的執(zhí)行時間:

func main() {    beforeQuadTime := time.Now()    quadraticMain()    afterQuadTime := time.Since(beforeQuadTime)    fmt.Printf("%d\n", afterQuadTime)     before3dQuadTime := time.Now()    quadratic3dMain()    after3dQuatTime := time.Since(before3dQuadTime)    fmt.Printf("%d\n", after3dQuatTime) }

邊注:我能說我很高興我們是一個開發(fā)者社區(qū)，讓他們從過去的錯誤中走出來，并把綜合的時間模塊和包構(gòu)建成一種語言嗎?Java 8  +擁有它們，Python擁有它們，并擁有它們。這使我開心。

現(xiàn)在的輸出:

Best: x: 3.072833 y: -6.994695 136,876 Best: x: 3.891671 y: 4.554884 z: -12.787259 4,142,778

那“近乎瞬間”的感覺是我想要傳達(dá)的，現(xiàn)在我們有了很難的數(shù)字。136,876看起來很大，但要在納秒內(nèi)報告時間。

重申一遍:納秒。不是幾毫秒，我們都習(xí)慣了在互聯(lián)網(wǎng)時代或者其他像Python和Java這樣的通用語言;納秒。1/1,000,000毫秒。

這意味著我們在不到一毫秒的時間里找到了一個使用遺傳算法來搜索答案的二次方程的答案。這句話，“該死的瞬間”似乎很合適，不是嗎?這包括打印到終端。

那么，要計算更密集的東西呢?在我展示一種尋找好的夢幻足球lineups的方法之前，我在Fanduel上使用。這包括從電子表格中讀取數(shù)據(jù)，制作和過濾lineups，并進(jìn)行更復(fù)雜的交叉和突變。強(qiáng)制尋找***解決方案可能需要超過75,000年(至少使用我當(dāng)時使用的Python)。

我不需要再檢查所有的細(xì)節(jié)，你可以自己去看代碼，但我會在這里顯示輸出:

Best: 121.409960:, $58100 QB: Aaron Rodgers - 23.777778 RB: Latavius Murray - 15.228571 RB: DeMarco Murray - 19.980000 WR: Kelvin Benjamin - 11.800000 WR: Stefon Diggs - 14.312500 WR: Alshon Jeffery - 9.888889 TE: Connor Hamlett - 8.200000 D: Philadelphia Eagles - 10.777778 K: Phil Dawson - 7.444444 16,010,182

“Go語言中如何實現(xiàn)一個遺傳算法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！