Go 语言
Go 是一种新的语言, 一种并发的带垃圾回收的快速编译的语言 Go 是谷歌 2009 年发布的第二款编程语言 2009 年 7 月份, 谷歌曾发布了 Simple 语言, 它是用来开发 Android 应用的一种 BASIC 语言
Go 是一个开源的编程语言, 它能让构造简单可靠且高效的软件变得容易本文将重点介绍如何用 Go 语言实现遗传算法如果你还没有参加过 GoLang Tour, 我还建议你快速看一下这门语言的介绍
在没介绍正文之前先给大家补充点 go 语言基本知识及实例
Go 语言教程
Go 是一个开源的编程语言, 它能让构造简单可靠且高效的软件变得容易
Go 是从 2007 年末由 Robert Griesemer, Rob Pike, Ken Thompson 主持开发, 后来还加入了 Ian Lance Taylor, Russ Cox 等人, 并最终于 2009 年 11 月开源, 在 2012 年早些时候发布了 Go 1 稳定版本现在 Go 的开发已经是完全开放的, 并且拥有一个活跃的社区
Go 语言特色
简洁快速安全
并行有趣开源
内存管理 v 数组安全编译迅速
Go 语言用途
Go 语言被设计成一门应用于搭载 web 服务器, 存储集群或类似用途的巨型中央服务器的系统编程语言
对于高性能分布式系统领域而言, Go 语言无疑比大多数其它语言有着更高的开发效率它提供了海量并行的支持, 这对于游戏服务端的开发而言是再好不过了
第一个 Go 程序
接下来我们来编写第一个 Go 程序 hello.go(Go 语言源文件的扩展是 .go), 代码如下:
实例
- package main
- import "fmt"
- func main() {
- fmt.Println("Hello, World!")
- }
执行以上代码输出
- $ go run hello.go
- Hello, World!
好了, 正文开始
出于好玩的心态, 我决定学习一下 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
不坏! 由于人口规模只有 520 代, 而且输入的范围被限制在[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 真的是一种很好的语言我鼓励大家在学习一两门语言后再试一试它很快就成为了最流行的语言之一, 有很多原因可以解释为什么我期待着在未来更多地使用它
来源: http://www.phperz.com/article/18/0226/361461.html