Go語(yǔ)言實(shí)現(xiàn)遺傳算法的實(shí)例代碼

在沒(méi)介紹正文之前先給大家補(bǔ)充點(diǎn)go語(yǔ)言基本知識(shí)及實(shí)例。

Go 語(yǔ)言教程

Go 是一個(gè)開(kāi)源的編程語(yǔ)言，它能讓構(gòu)造簡(jiǎn)單、可靠且高效的軟件變得容易。

Go是從2007年末由Robert Griesemer, Rob Pike, Ken Thompson主持開(kāi)發(fā)，后來(lái)還加入了Ian Lance Taylor, Russ Cox等人，并最終于2009年11月開(kāi)源，在2012年早些時(shí)候發(fā)布了Go 1穩(wěn)定版本?，F(xiàn)在Go的開(kāi)發(fā)已經(jīng)是完全開(kāi)放的，并且擁有一個(gè)活躍的社區(qū)。

Go 語(yǔ)言特色

簡(jiǎn)潔、快速、安全
并行、有趣、開(kāi)源
內(nèi)存管理、v數(shù)組安全、編譯迅速

Go 語(yǔ)言用途

Go 語(yǔ)言被設(shè)計(jì)成一門(mén)應(yīng)用于搭載 Web 服務(wù)器，存儲(chǔ)集群或類(lèi)似用途的巨型中央服務(wù)器的系統(tǒng)編程語(yǔ)言。

對(duì)于高性能分布式系統(tǒng)領(lǐng)域而言，Go 語(yǔ)言無(wú)疑比大多數(shù)其它語(yǔ)言有著更高的開(kāi)發(fā)效率。它提供了海量并行的支持，這對(duì)于游戲服務(wù)端的開(kāi)發(fā)而言是再好不過(guò)了。

第一個(gè) Go 程序

接下來(lái)我們來(lái)編寫(xiě)第一個(gè) Go 程序 hello.go（Go 語(yǔ)言源文件的擴(kuò)展是 .go），代碼如下：

實(shí)例

package main
import "fmt"
func main() {
  fmt.Println("Hello, World!")
}

執(zhí)行以上代碼輸出

$ go run hello.go 
Hello, World!

好了，正文開(kāi)始。

出于好玩的心態(tài)，我決定學(xué)習(xí)一下Go語(yǔ)言。我認(rèn)為學(xué)習(xí)新語(yǔ)言最好的方法就是深入學(xué)習(xí)，并且盡可能多犯錯(cuò)誤。這樣做雖然可能會(huì)很慢，但是可以確保在后面的過(guò)程中再也不會(huì)出現(xiàn)編譯的錯(cuò)誤。

Go語(yǔ)言與我習(xí)慣的其他語(yǔ)言不同。Go更喜歡自己?jiǎn)为?dú)實(shí)現(xiàn)，而其他像Java這類(lèi)語(yǔ)言更喜歡繼承。其實(shí)在Go語(yǔ)言里面根本沒(méi)有繼承這種概念，因?yàn)樗鼔焊蜎](méi)有對(duì)象這一說(shuō)法。比如說(shuō)C語(yǔ)言，它有結(jié)構(gòu)體，但是沒(méi)有類(lèi)。但是這樣它還是可以有像“構(gòu)造者”這樣的常見(jiàn)思想和設(shè)計(jì)模式（一種在這種情況下有序地產(chǎn)生結(jié)構(gòu)體的方式）。

Go語(yǔ)言堅(jiān)決擁護(hù)組合（composition），同時(shí)也很反對(duì)繼承的做法，在網(wǎng)絡(luò)上引起了強(qiáng)烈的討論，同時(shí)也讓人們重新思考了語(yǔ)言該往哪個(gè)方向發(fā)展。所以，從這個(gè)角度來(lái)看，Go語(yǔ)言與其它語(yǔ)言的差別可能也沒(méi)有那么大。

本文將重點(diǎn)介紹如何用Go語(yǔ)言實(shí)現(xiàn)遺傳算法。如果你還沒(méi)有參加過(guò)GoLang Tour，我還建議你快速看一下這門(mén)語(yǔ)言的介紹。

話不多說(shuō)，讓我們開(kāi)始從代碼說(shuō)起吧！第一個(gè)例子與我以前做過(guò)的很類(lèi)似：找到一個(gè)二次的最小值。

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è)置，以便在稍后啟動(dòng)的算法中用到。

第二部分的GeneticAlgorithmRunner這個(gè)看起來(lái)有點(diǎn)奇怪。GeneticAlgorithmRunner是一個(gè)接口，詢(xún)問(wèn)如何生成初始種群，執(zhí)行corssovers和mutataions，并對(duì)答案進(jìn)行排序，以便在Population中保持最好的個(gè)體，這樣下一代才會(huì)更加優(yōu)秀。我認(rèn)為這看起來(lái)很奇怪，因?yàn)椤敖涌凇蓖ǔＳ糜诿嫦驅(qū)ο蟮恼Z(yǔ)言，通常會(huì)要求對(duì)象實(shí)現(xiàn)某些特性和方法。這里沒(méi)有什么差別。這一小段代碼實(shí)際上是在說(shuō)，它正在請(qǐng)求一些東西來(lái)定義這些方法的細(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))
 })
}

更奇怪的是，我從來(lái)沒(méi)有提到過(guò)這些方法的接口。請(qǐng)記住，因?yàn)闆](méi)有對(duì)象，也沒(méi)有繼承。QuadraticGA結(jié)構(gòu)體是一個(gè)空白對(duì)象，隱式地作為GeneticAlgorithmRunner。每個(gè)必需的方法都在括號(hào)中綁定到該結(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)))
}

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

現(xiàn)在來(lái)計(jì)算每個(gè)項(xiàng)的性能，以求二次函數(shù)求出的二次函數(shù)來(lái)求出一個(gè)新的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)為二次實(shí)現(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
}

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

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

Best: x: 3.072833 y: -6.994695

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

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

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

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，任何地方都可以通過(guò)Quad3D的條目;每一個(gè)都有一個(gè)X和一個(gè)Y值。對(duì)于創(chuàng)建的每個(gè)條目，都使用contructor makeNewQuadEntry創(chuàng)建。Run()方法中的代碼都沒(méi)有更改。

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

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

很接近了!

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

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

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

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

現(xiàn)在的輸出:

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

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

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

這意味著我們?cè)诓坏揭缓撩氲臅r(shí)間里找到了一個(gè)使用遺傳算法來(lái)搜索答案的二次方程的答案。這句話，“該死的瞬間”似乎很合適，不是嗎?這包括打印到終端。

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

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

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

哦,是的!現(xiàn)在看來(lái)這是一個(gè)很好的陣容!它只需要16毫秒就能找到。

現(xiàn)在，這個(gè)遺傳算法可以改進(jìn)了。與C一樣，當(dāng)將對(duì)象傳遞給方法時(shí)，將在堆棧上復(fù)制對(duì)象(讀取數(shù)據(jù))。隨著對(duì)象大小的增長(zhǎng)，最好不要反復(fù)復(fù)制它們，而是要在堆中創(chuàng)建它們，并在周?chē)鷤鬟f指針。目前，我將把它作為未來(lái)的工作。

Go也被用coroutines和信道的原生支持編寫(xiě)，利用多個(gè)內(nèi)核來(lái)解決一個(gè)問(wèn)題，比過(guò)去簡(jiǎn)單多了，相比于單核時(shí)代的其他語(yǔ)言來(lái)說(shuō)，這是一個(gè)巨大的優(yōu)勢(shì)。我想要增強(qiáng)這個(gè)算法來(lái)使用這些工具，但這也必須留給以后的工作。

我很享受學(xué)習(xí)的過(guò)程。對(duì)于我來(lái)說(shuō)，用組合而不是繼承來(lái)考慮工程解決方案是很困難的，因?yàn)槲乙呀?jīng)習(xí)慣了8年以上的時(shí)間，也是我學(xué)會(huì)編程的方式。但是每種語(yǔ)言和方式都有各自的優(yōu)點(diǎn)和缺點(diǎn);每一種語(yǔ)言在我的工具中都是不同的工具。對(duì)于任何擔(dān)心嘗試的人，不要。有一個(gè)駝峰(更像是一個(gè)減速帶)，但你很快就會(huì)克服它，走上成功之路。

還有一些我喜歡的東西，我喜歡其他語(yǔ)言，主要是一組基本的函數(shù)方法來(lái)操作數(shù)據(jù)。我需要一個(gè)lambda函數(shù)和方法來(lái)映射、減少和篩選數(shù)據(jù)的數(shù)組或部分。設(shè)計(jì)人員反對(duì)功能實(shí)現(xiàn)的理由是，代碼應(yīng)該總是簡(jiǎn)單、易于閱讀和編寫(xiě)，并且這與for循環(huán)是可實(shí)現(xiàn)的。我認(rèn)為，映射、過(guò)濾和減少通常更容易讀和寫(xiě)，但這是一場(chǎng)已經(jīng)在肆虐的戰(zhàn)爭(zhēng)中的爭(zhēng)論。

盡管我與一些開(kāi)發(fā)人員的觀點(diǎn)存在分歧，以及我必須考慮解決問(wèn)題的不同方式，但Go真的是一種很好的語(yǔ)言。我鼓勵(lì)大家在學(xué)習(xí)一兩門(mén)語(yǔ)言后再試一試。它很快就成為了最流行的語(yǔ)言之一，有很多原因可以解釋為什么。我期待著在未來(lái)更多地使用它。

總結(jié)

以上所述是小編給大家介紹的Go語(yǔ)言實(shí)現(xiàn)遺傳算法的實(shí)例代碼，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)億速云網(wǎng)站的支持！