Go言語で遺伝的アルゴリズムを実装する方法

ただの楽しみのために、Go 言語を学ぶことにしました。新しい言語を学ぶ最良の方法は、深く学び、できるだけ多くの間違いをすることだと思います。これは遅くなるかもしれませんが、プロセスの後半でコンパイルエラーが発生しないことが保証されます。

Go は私が慣れている他の言語とは異なります。 Go は個別の実装を好みますが、Java などの他の言語は継承を好みます。実際、Go 言語にはオブジェクトの概念がまったくないため、継承などの概念は存在しません。たとえば、C 言語には構造体はありますが、クラスはありません。しかし、それでも「コンストラクター」(この場合、構造を整然と生成する方法) などの共通のアイデアや設計パターンは許可されます。

Go 言語は、合成をしっかりとサポートし、継承に反対しており、インターネット上で白熱した議論を巻き起こし、言語が発展すべき方向性を再考するきっかけとなりました。なので、この観点から見ると、Go と他の言語の違いはそれほど大きくないかもしれません。

この記事では、Go 言語で遺伝的アルゴリズムを実装する方法に焦点を当てます。 GoLang ツアーにまだ参加していない場合は、言語の紹介も簡単に見ることをお勧めします。

さっそく、コードを見てみましょう。最初の例は、私が以前にやったことと非常に似ています。2 次最小値を見つけることです。

型 GeneticAlgorithmSettings 構造体 {
  人口規模int  
  変異率int  
  クロスオーバーレートint  
  世代数int  
  KeepBestAcrossPopulation ブール値
} 
 
型 GeneticAlgorithmRunner インターフェース {
  初期人口を生成する(populationSize int ) []インターフェース{}
  クロスオーバーを実行します(individual1、individual2 インターフェース{}、mutationRate int ) インターフェース{}
  PerformMutation(個別のインターフェース{}) インターフェース{}
  ソート([]インターフェース{})
 }

後でアルゴリズムを起動するときに使用する一連の設定をすぐに定義します。

2 番目の部分である GeneticAlgorithmRunner は少し奇妙に見えます。 GeneticAlgorithmRunner は、初期の集団を生成する方法を尋ね、交差と突然変異を実行し、回答を並べ替えて、次の世代がより優れたものになるように、集団内の最良の個体を維持するインターフェースです。「インターフェース」は通常、オブジェクト指向言語で使用され、通常はオブジェクトが特定の特性とメソッドを実装することを必要とするため、これは奇妙に思えます。ここに違いはありません。この短いコードスニペットが実際に言っているのは、これらのメソッドの詳細を定義する何かを要求しているということです。私がそれをやった方法は次のとおりです:

型 QuadraticGA 構造体 {} 
 
 func (l QuadraticGA) GenerateInitialPopulation(populationSize int ) []interface{}{
  初期人口:= make([]インターフェース{}, 0, 人口サイズ)
 i:= 0; i < populationSize; i++ {
    初期人口 = 追加(初期人口、新しいエントリの作成())
  }
 initialPopulationを返す
} 
 
 func (l QuadraticGA) PerformCrossover(result1, result2 interface{}, _ int ) interface{}{
 （結果1.(float64) + 結果2.(float64)）/ 2を返す
} 
 
 func (l QuadraticGA) PerformMutation(_ interface{}, _ int ) interface{}{
 makeNewEntry()を返す
} 
 
 func (l QuadraticGA) Sort(population []interface{}){
  sort.Slice(population, func(i, j int ) bool {
計算(population[i].(float64))を返す> 計算(population[j].(float64))
  })
 }

さらに奇妙なのは、これらのメソッドのインターフェースについては一度も言及していないことです。オブジェクトが存在しないため、継承は存在しないことに注意してください。 QuadraticGA 構造は、暗黙的に GeneticAlgorithmRunner として機能する空のオブジェクトです。必要な各メソッドは、Java の「@ override」と同様に、括弧で囲まれた構造体にバインドされます。ここで、構造と設定をアルゴリズムを実行するモジュールに渡す必要があります。

設定:= ga.GeneticAlgorithmSettings{
   人口規模: 5,
   変異率: 10,
   クロスオーバー率: 100,
   世代数: 20,
   KeepBestAcrossPopulation: true 、
 } 
 
ベスト、エラー:= ga.Run(QuadraticGA{}, 設定) 
 
 err != nil の場合 {
   println(エラー)
 }それ以外{
   fmt.Printf( "ベスト: x: %f y: %f\n" , best, calculate(best.(float64)))
 }

とても簡単ですよね? 「QuadraticGA{}」は単に構造体の新しいインスタンスを作成し、Run() メソッドが残りの処理を実行します。このメソッドは検索結果と発生したエラーを返します。これは、Go が try/catch を信じていないためです。これは、war の作者が採用したもう 1 つの厳格な設計スタンスです。

ここで、各項のパフォーマンスを計算し、2次関数によって得られた2次関数を使用してXの新しい値を見つけましょう。

関数makeNewEntry() float64 {
 highRange * rand.Float64()を返す
} 
 
関数calculate(x float64) float64 {
 return math.Pow(x, 2) - 6*x + 2 // 最小値はx=3 のとき
}

セカンダリ実装のインターフェースが作成されたので、GA 自体を完成させる必要があります。

 func Run(geneticAlgoRunner GeneticAlgorithmRunner、設定 GeneticAlgorithmSettings) (interface{}、error){ 
 
   人口:= geneticAlgoRunner.GenerateInitialPopulation(settings.PopulationSize) 
 
   遺伝的アルゴリズムランナー.Sort(人口) 
 
   bestSoFar := 人口[len(人口) - 1] 
 
 i := 0; i < settings.NumGenerations; i++ { 
 
      新しい人口:= make([]インターフェース{}, 0, 設定.人口サイズ) 
 
      設定.KeepBestAcrossPopulation {
         newPopulation = append(newPopulation, bestSoFar)
      } 
 
      //ランダム選択によるクロスオーバーを実行する
      確率的出演者リスト:= 確率的個人リストを作成します(人口) 
 
      新しいポップインデックス:= 0
      設定.KeepBestAcrossPopulation{
         新しいポップインデックス = 1
      }
 ; newPopIndex < settings.PopulationSize; newPopIndex++ {
         indexSelection1 := rand.Int () % len(probabilisticListOfPerformers)
         indexSelection2 := rand.Int () % len(probabilisticListOfPerformers) 
 
         // クロスオーバー
         新しい個体:= 遺伝的アルゴリズムランナー.クロスオーバーを実行します(
            確率的リストOfPerformers[インデックス選択1],
            probabilisticListOfPerformers[indexSelection2]、settings.CrossoverRate) 
 
         // 変異
         rand.Intn(101) < settings.MutationRate {の場合
            新しい個体 = 遺伝的アルゴランナー.PerformMutation(新しい個体)
         } 
 
         新しい人口 = 追加(新しい人口、新しい個人)
      } 
 
      人口 = 新しい人口
 
      //パフォーマンス順に並べ替え
      遺伝的アルゴリズムランナー.Sort(人口) 
 
      // これまでのベストを維持
      bestSoFar = 人口[len(人口) - 1] 
 
   } 
 
 bestSoFar, nil を返す
} 
 
 func createStochasticProbableListOfIndividuals(人口 []interface{}) []interface{} { 
 
   totalCount、populationLength:= 0、len(人口)
 j:= 0の場合; j < populationLength; j++ {
      合計数 += j
   } 
 
   可能性のある個体:= make([]interface{}, 0, totalCount)
のために インデックス、個体 := 範囲 人口 {
 i := 0; i <インデックス; i++{
         可能性のある個体 = append(可能性のある個体、個体)
      }
   } 
 
可能性のある個人を返す
}

以前と同様に、新しい集団が作られ、その集団のメンバーは世代を超えて交配し、その子孫は突然変異を持つ可能性があります。個体のパフォーマンスが優れているほど、交尾する可能性が高くなります。時間が経つにつれて、アルゴリズムは最良の答え、または少なくともかなり良い答えに収束します。

では、実行すると何が返されるのでしょうか?

ベスト: x: 3.072833 y: -6.994695

悪くないですね！集団のサイズはわずか 5,20 世代であり、入力は [0 100] の範囲に制限されているため、この検索はトップを正確に特定します。

さて、すべてのインターフェースメソッドを「interface{}」を返すように定義した理由が疑問に思われるかもしれません。それは Go とジェネリックのようなものです。オブジェクトが存在しないため、オブジェクトタイプは返されませんが、サイズが指定されていないデータはスタックに渡すことができます。基本的に、この戻り値の型も意味します。つまり、既知の類似した型のオブジェクトを渡します。この「汎用性」により、GA を独自のパッケージに移動し、複数の異なるタイプのデータに対して同じコードを使用できるようになりました。

2D 二次方程式への単一の入力の代わりに、2 つの入力を持つ 3D 二次方程式があります。インターフェースメソッドにはわずかな変更のみが必要です。

 Quad3D構造体型{
   x, y float64
 }
 func makeNewQuadEntry(newX, newY float64) Quad3D {
 Quad3Dを返す{
      x: 新しいX、
      y: 新しいY、
   }
 } 
 
 function calculate3D(エントリ Quad3D) float64 {
戻り値math.Pow(entry.x, 2)- 6 * entry.x + math.Pow(entry.y, 2)- 6 * entry.y + 2
 } 
 
型Quadratic3dGA構造体{
 } 
 
 func (l Quadratic3dGA) GenerateInitialPopulation(populationSize int )[]interface{}{ 
 
   初期人口:= make([]インターフェース{}, 0, 人口サイズ)
 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))
   })
 } 
 
関数quadratic3dMain(){
   設定:= ga.GeneticAlgorithmSettings{
      人口規模: 25,
      変異率: 10,
      クロスオーバー率: 100,
      世代数: 20,
      KeepBestAcrossPopulation: true 、
   } 
 
   ベスト、エラー:= ga.Run(Quadratic3dGA{}, 設定)
   エントリ := ベスト。(Quad3D) 
 
   err != nil の場合 {
      println(エラー)
   }それ以外{
      fmt.Printf( "最適: x: %f y: %f z: %f\n" , entry.x, entry.y, calculate3D(entry))
   }
 }

どこでも float64 の代わりに、どこにでも Quad3D のエントリを渡すことができます。それぞれのエントリには X 値と Y 値があります。作成されたエントリごとに、コンストラクター makeNewQuadEntry が使用されます。 Run() メソッド内のコードは変更されていません。

実行すると、次の出力が得られます。

ベスト: x: 3.891671 y: 4.554884 z: -12.787259

とても近いです！

ああ、速く走ることを忘れていました。Java でこれを実行すると、同じ設定でも、かなりの待ち時間が発生します。比較的小規模な二次方程式を解くことはそれほど複雑ではありませんが、人間が理解するには注目に値することです。

Go は C と同様にネイティブにコンパイルされます。バイナリが実行されると、すぐに答えが吐き出されるようです。各実行の実行時間を測定する簡単な方法は次のとおりです。

関数main() {
   beforeQuadTime :=時間.Now()
   二次メイン()
   afterQuadTime :=時間.Since(beforeQuadTime)
   fmt.Printf( "%d\n" , afterQuadTime) 
 
   before3dQuadTime :=時間.Now()
   二次3dメイン()
   after3dQuadTime :=時間.Since(before3dQuadTime)
   fmt.Printf( "%d\n" 、 after3dQuatTime)
 }

補足: 私たちが過去の失敗から立ち直り、包括的な時間モジュールとパッケージを言語に組み込む開発者コミュニティであることを嬉しく思います。Java 8+ にはそれらがあり、Python にもそれらがあり、にもあります。これは私を幸せにします。

出力は次のようになります:

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

その「ほぼ瞬時」な感覚こそ私が伝えたかったことであり、今では確かな数字が存在します。 136,876 は大きいように思えるかもしれませんが、時間はナノ秒単位で報告されます。

繰り返しますが、ナノ秒です。インターネット時代や、Python や Java などの他の一般的な言語で私たちが慣れ親しんでいるミリ秒ではなく、ナノ秒です。 1/1,000,000ミリ秒。

これは、遺伝的アルゴリズムを使用して 1 ミリ秒未満で二次方程式の答えを検索し、その答えを見つけたことを意味します。「地獄の瞬間」というフレーズは、まさに適切なように思えます。これには、端末への印刷も含まれます。

では、もっと計算量の多いものはどうでしょうか? 優れたファンタジーフットボールのラインナップを見つける方法を紹介する前に、を使用します。これには、スプレッドシートからのデータの読み取り、ラインナップの作成とフィルタリング、より複雑なクロスオーバーと突然変異の実行が含まれます。 *** ソリューションを力ずくで探すと、おそらく 75,000 年以上かかるでしょう (少なくとも当時私が使用していた Python を使用した場合)。

すべての詳細をもう一度説明する必要はありません。コードを自分で確認することもできますが、ここでは出力を示します。

最高: 121.409960:、$58100
 QB: アーロン・ロジャース - 23.777778
 RB: ラタビウス・マレー - 15.228571
 RB: デマルコ・マレー - 19.980000
 WR: ケルビン・ベンジャミン - 11.800000
 WR: ステフォン・ディグス - 14.312500
 WR: アルション・ジェフリー - 9.888889
 TE: コナー・ハムレット - 8.200000
 D: フィラデルフィア・イーグルス - 10.777778
 K: フィル・ドーソン - 7.444444
 16,010,182

ああ、そうだ！これは良いラインナップのようだ！見つけるのにたった 16 ミリ秒しかかからない。

現在、この遺伝的アルゴリズムは改善することができます。 C と同様に、オブジェクトがメソッドに渡されると、オブジェクトはスタックにコピーされます (データが読み取られます)。オブジェクトのサイズが大きくなるにつれて、オブジェクトを何度もコピーするのではなく、ヒープ内に作成してポインターを渡します。今のところ、将来の課題として残しておきます。

Go はコルーチンとチャネルのネイティブサポートも備えて記述されているため、複数のコアを活用して問題を解決することが以前よりもはるかに簡単になり、シングルコア時代の他の言語に比べて大きな利点となっています。これらのツールを使用するためのアルゴリズムを強化したいのですが、これは将来の作業に残す必要があります。

私は学習のプロセスを本当に楽しんでいます。私にとって、継承ではなく構成の観点からエンジニアリングソリューションを考えるのは難しいことです。なぜなら、それが私が 8 年以上慣れ親しんできたことであり、プログラミングを学んだ方法だからです。しかし、それぞれの言語とアプローチには独自の長所と短所があり、それぞれの言語は私のツールキット内の異なるツールです。試すのが不安な人は、やめてください。障害（スピードバンプのようなもの）はありますが、すぐに乗り越えて成功への道を歩むことになるでしょう。

他の言語で気に入っている点がいくつかありますが、主に、データを操作するための関数型メソッドの基本的なセットです。配列またはデータの一部をマップ、削減、フィルタリングするためのラムダ関数とメソッドが必要です。関数型の実装に反対する設計者の主張は、コードは常にシンプルで読みやすく書きやすいものでなければならないということであり、これは for ループで実現できます。一般的に、map、filter、reduce の方が読み書きが簡単だと思いますが、これはすでに激しい議論が繰り広げられているところです。

一部の開発者との意見の相違や、問題解決について考える方法の違いにもかかわらず、Go は本当に素晴らしい言語です。皆さんも、1つか2つの言語を学んだら、ぜひ試してみることをお勧めします。急速に最も人気のある言語の 1 つになりましたが、それには多くの理由があります。今後も利用させていただくことを楽しみにしております。

<<: AI時代のクラウドベースのインテリジェントコンピューティング

>>: AIとデータセンターの相互依存