Go語言如何實現遺傳算法
出于好玩的心態，我決定學習一下Go語言。我認為學習新語言***的方法就是深入學習，并且盡可能多犯錯誤。這樣做雖然可能會很慢，但是可以確保在后面的過程中再也不會出現編譯的錯誤。
Go語言與我習慣的其他語言不同。Go更喜歡自己單獨實現，而其他像Java這類語言更喜歡繼承。其實在Go語言里面根本沒有繼承這種概念，因為它壓根就沒有對象這一說法。比如說C語言，它有結構體，但是沒有類。但是這樣它還是可以有像“構造者”這樣的常見思想和設計模式(一種在這種情況下有序地產生結構體的方式)。
Go語言堅決擁護組合(composition)，同時也很反對繼承的做法，在網絡上引起了強烈的討論，同時也讓人們重新思考了語言該往哪個方向發展。所以，從這個角度來看，Go語言與其它語言的差別可能也沒有那么大。
本文將重點介紹如何用Go語言實現遺傳算法。如果你還沒有參加過GoLang Tour，我還建議你快速看一下這門語言的介紹。
話不多說，讓我們開始從代碼說起吧!***個例子與我以前做過的很類似：找到一個二次的最小值。
- 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{})
- }
我立馬定義了一組設置，以便在稍后啟動的算法中用到。
第二部分的GeneticAlgorithmRunner這個看起來有點奇怪。GeneticAlgorithmRunner是一個接口，詢問如何生成初始種群，執行corssovers和mutataions，并對答案進行排序，以便在Population中保持***的個體，這樣下一代才會更加優秀。我認為這看起來很奇怪，因為“接口”通常用于面向對象的語言，通常會要求對象實現某些特性和方法。這里沒有什么差別。這一小段代碼實際上是在說，它正在請求一些東西來定義這些方法的細節。我是這樣做的:
- 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結構體是一個空白對象，隱式地作為GeneticAlgorithmRunner。每個必需的方法都在括號中綁定到該結構體，就像Java中的“@ override”。現在，結構體和設置需要傳遞給運行該算法的模塊。
- 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 {}”只是簡單地創建了該結構的一個新實例，其余的則由Run()方法完成。該方法返回搜索結果和發生的任何錯誤，因為Go不相信try / catch——另一場戰爭作者采取了嚴格的設計立場。
現在來計算每個項的性能，以求二次函數求出的二次函數來求出一個新的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
- }
既然已經為二次實現創建了接口，那么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
- }
很像以前，一個新的人口被創造出來，人口的成員將會世代交配，而他們的后代可能攜帶突變。一個人的表現越好，就越有可能交配。隨著時間的推移，算法收斂到***的答案，或者至少是一個相當不錯的答案。
那么當它運行時，它返回了什么呢?
- Best: x: 3.072833 y: -6.994695
不壞!由于人口規模只有5、20代，而且輸入的范圍被限制在[0 100]，這一搜索就釘在了頂點上。
現在，您可能想知道為什么我定義了所有的接口方法來返回“接口{}”。這就像Go和generics一樣。沒有對象，因此沒有對象類型返回，但是沒有描述的大小的數據仍然可以在堆棧上傳遞。這本質上也是這個返回類型的含義:它傳遞一些已知的和類似的類型的對象。有了這個“泛型”，我就可以將GA移動到它自己的包中，并將相同的代碼移到多個不同類型的數據上。
我們有兩個輸入的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值。對于創建的每個條目，都使用contructor makeNewQuadEntry創建。Run()方法中的代碼都沒有更改。
當它運行時，我們得到這個輸出:
- Best: x: 3.891671 y: 4.554884 z: -12.787259
很接近了!
哦，我忘了說走快了!在Java中執行此操作時，即使使用相同的設置，也會有明顯的等待時間。在一個相對較小的范圍內求解二次方程并不是很復雜，但它對一個人來說是值得注意的。
Go是本地編譯的，比如C。當二進制執行時，它似乎馬上就吐出一個答案。這里有一個簡單的方法來度量每次運行的執行時間:
- 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)
- }
邊注:我能說我很高興我們是一個開發者社區，讓他們從過去的錯誤中走出來，并把綜合的時間模塊和包構建成一種語言嗎?Java 8 +擁有它們，Python擁有它們，并擁有它們。這使我開心。
現在的輸出:
- Best: x: 3.072833 y: -6.994695
- 136,876
- Best: x: 3.891671 y: 4.554884 z: -12.787259
- 4,142,778
那“近乎瞬間”的感覺是我想要傳達的，現在我們有了很難的數字。136,876看起來很大，但要在納秒內報告時間。
重申一遍:納秒。不是幾毫秒，我們都習慣了在互聯網時代或者其他像Python和Java這樣的通用語言;納秒。1/1,000,000毫秒。
這意味著我們在不到一毫秒的時間里找到了一個使用遺傳算法來搜索答案的二次方程的答案。這句話，“該死的瞬間”似乎很合適，不是嗎?這包括打印到終端。
那么，要計算更密集的東西呢?在我展示一種尋找好的夢幻足球lineups的方法之前，我在Fanduel上使用。這包括從電子表格中讀取數據，制作和過濾lineups，并進行更復雜的交叉和突變。強制尋找***解決方案可能需要超過75,000年(至少使用我當時使用的Python)。
我不需要再檢查所有的細節，你可以自己去看代碼，但我會在這里顯示輸出:
- 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
哦,是的!現在看來這是一個很好的陣容!它只需要16毫秒就能找到。
現在，這個遺傳算法可以改進了。與C一樣，當將對象傳遞給方法時，將在堆棧上復制對象(讀取數據)。隨著對象大小的增長，***不要反復復制它們，而是要在堆中創建它們，并在周圍傳遞指針。目前，我將把它作為未來的工作。
Go也被用coroutines和信道的原生支持編寫，利用多個內核來解決一個問題，比過去簡單多了，相比于單核時代的其他語言來說，這是一個巨大的優勢。我想要增強這個算法來使用這些工具，但這也必須留給以后的工作。
我很享受學習的過程。對于我來說，用組合而不是繼承來考慮工程解決方案是很困難的，因為我已經習慣了8年以上的時間，也是我學會編程的方式。但是每種語言和方式都有各自的優點和缺點;每一種語言在我的工具中都是不同的工具。對于任何擔心嘗試的人，不要。有一個駝峰(更像是一個減速帶)，但你很快就會克服它，走上成功之路。
還有一些我喜歡的東西，我喜歡其他語言，主要是一組基本的函數方法來操作數據。我需要一個lambda函數和方法來映射、減少和篩選數據的數組或部分。設計人員反對功能實現的理由是，代碼應該總是簡單、易于閱讀和編寫，并且這與for循環是可實現的。我認為，映射、過濾和減少通常更容易讀和寫，但這是一場已經在肆虐的戰爭中的爭論。
盡管我與一些開發人員的觀點存在分歧，以及我必須考慮解決問題的不同方式，但Go真的是一種很好的語言。我鼓勵大家在學習一兩門語言后再試一試。它很快就成為了***的語言之一，有很多原因可以解釋為什么。我期待著在未來更多地使用它。
