このエントリはU-TOKYO AP Advent Calendar 2017の12日目の記事です．

はじめに

趣味のクラシックギターと絡めて，譜読み＝楽譜を読むことについてゆるふわな記事を書きました．
なんとなく対象を広めに意識しているためどの人にとっても冗長な記事になっているという事態が生じていますがご了承ください．というかすごく長くなっちゃいました．かいつまんで読んでください．

ざっくりギターの説明をしてから遺伝的アルゴリズムの説明に入って実験結果をお見せします．
なお，説明は厳密さを欠く部分があったり，一般には用いられていない単語を用いている部分がある可能性があります．ご了承ください．

##ギターの仕組み
一般的なクラシックギターは皆さんが想像するようなギターと機構的には変わりません．

6つの弦が張られ，指板にはフレットというものがおかれており，その部分を左手指で押さえた上で右手で弦を弾くと，押さえられたフレットに対応する高さの音が出ます．
イメージを掴んでもらうには，以下の2つの動画を見てもらうと早いと思います．
1つめは簡単に音を出している動画で，2つめはクラシックギターの実際の演奏の動画です．多くの人が聴いたことのある曲だと思います．

1つめを見てもらうと分かると思うのですが，同じ高さの音を出すにもいくつかの方法があって，例えばミ(E3)の音を出すのに使う弦とフレットにも4弦2フレット，5弦7フレット，6弦12フレットの3通りがあります(フレット数が大きいほど穴に近い)．

##モチベ
上記の仕組みのおかげで様々な和音を弾きやすくなっているのですが，同時に「同じ音を弾くにも選択肢が多くてどれで弾けば良いか決まらない」という問題が生じます．

これは音の高さと鍵の位置が一対一に対応しているピアノとは対照的で，楽譜を見て直ちに指の配置が決まるわけではないところが，楽譜を読む上での一つのボトルネックのようなものになっているのです．

ではどのようにこの指使いの問題を解決するかというと，

弦ごとの音色の違い
フレーズにおける運指(指使い)のコンパクトさ
が代表的なものとして考えられます．

1.は最初の動画で感じ取ってください(動画中盤の高いミの3音で顕著)．今回の記事中ではこの1.には触れないこととします．
2.について考えます．ここでもうひとつの動画を見てみてください．

これは全音階を2通りの指遣いで弾いたものです．左手の動きがあまり多くなくコンパクトなものと，左手が頻繁に動いて弾きづらいものとがある，ということが容易に分かると思います．すなわち，運指のコンパクトさをある程度最適化して楽譜を読まねばならないということになります．五線譜を読み慣れていない人にとって，音の高さを把握するのに加えてこのことを考えることは結構大変なので，じゃあプログラミング？とかいうすごそうなものにやらせちゃえ！というのが本記事のモチベーションです．

##はじめての遺伝的アルゴリズム
では，上記の運指最適化問題をどのように解決すれば良いか，ということを考えます．
例えばドレミファソラシドという8音のスケールを弾くことを考えてみると，8音それぞれに対応する(弦，フレット)の組は大体3,4種類あります．ということは組み合わせの個数的には少なくとも3^8=６５６１通りということになります．~~...あれ？思ったより少ない~~遺伝的アルゴリズムを試すのが目的なので目をつぶります．さらに和音が入ってくると，例えば4つの音で構成される和音が8つ連続するとすると単純には(3^4)^8= 1,853,020,188,851,841=1.8*10^15通りとなり，これはさすがに全探索するにはきつい数です．

###遺伝的アルゴリズム(GA)
そこで！出てくるのが遺伝的アルゴリズムです．
遺伝的アルゴリズム(Genetic Algorithms,以下GA)は生物の進化を模倣したアルゴリズムです．遺伝的アルゴリズムを参考にしました．
~~まあぶっちゃけ明らかにムリな運指を枝刈りしながら探索すればhogeって感じもするんですが,まあ実装が簡単なので良しとします~~

まずGAの†理念†について述べます.
GAを簡単に理解できる動画があります．

これは人が立ち上がるアルゴリズムをGAで学習させている様子です.

そこで，GAでは手元にいろんな動き方をする人間をわんさか用意します．人間の動き方，ここでは関節の動かし方がその個体の"遺伝子"ともいうべきものになります．
次にその中で出来るだけ頭の高さの平均値が高い"エリート"を選りすぐります．
そして優秀な遺伝子を持つエリートたちを"交配"させる，つまり，2人のエリートのあるタイミングでの関節の動かし方を入れ替えたりします．これが遺伝子の組み換え，「交叉」に当たります．

ただしこれだけだと，交配により生まれたエリートたちがすべて同じ動かし方になっていつまでも進化しない状況に陥ったりします．このとき，遺伝子はすべての個体において同じなので，入れ替えても遺伝子は変わりません．つまりもうその集団からは立ち上がることのできる革命的な存在は生まれることはありません．

そのような局所最適解に陥ることを防ぐために，GAでは"突然変異"というものを取り入れています．これは名前の通り，(交配とは無関係に)個体をランダムに選び，その遺伝子の一部分をある確率でランダムに変化させるものです．

このように，遺伝子を持つ個体たちを交配させたり突然変異を起こさせたりして，エリートの頭の平均の高さを高くしていくと結果的に最後に直立している人間が生まれるということです．めでたしめでたし．

今まではすべて立ち上がりの文脈で述べていましたが，クラシックギターの運指最適化も同じ感じです．
ギタリストをたくさん集めて，それぞれランダムに楽譜をプレイしてもらい，その中で優秀者を選び，その個体の遺伝子=弾き方を交配したり突然変異させることで，最終的には最適なプレイングをするギタリストが養成されるという次第です．クール．

###GAの定式化と擬似コード
GAの雰囲気を理解して頂いたところで，今までに出てきた言葉も使いながらもう一度GAを定式化しておきます．
GAにおいて，最適なパラメータ$g=\left\{ c_i \right\}_{i=1}^n \in C^n$を決めるとします．ここで$C$は問題により決まる有限集合とします．このとき$g$の最適性を関数$opt(g)$ではかるとします．すなわち，optを最小化するパラメータが最適な個体に相当します．そこで以下の擬似コードのような遺伝的アルゴリズムで最適解を求めます．

$K,G,e,p_i,p_g$を決める．
$K$体の個体を用意し，個体$k$に遺伝子パラメータ$g_{k}=\left\{c_{ki}\right\}\in C^n$を一様ランダムに割り当てる．この個体群を世代と呼ぶ．世代数を0とする．
世代数$\leq G$の間繰り返す:
　　各個体の適応度を$opt(g_{k})$とする．
　　$E=$現世代の適応度上位$e$個の個体の集合
　　$P=E$の$j$番目と$j+1$番目の個体に交叉を施して得られた個体の集合($j=1,2,\ldots,e-1$)
　　$C=$現世代からの$N-|E|-|P|$個のランダムサンプル
　　次世代の個体の集合$=E\cup P\cup C$
　　次世代の各個体$k$に対して独立に，確率$p_i$で次の突然変異を起こす:
　　　　遺伝子の各インデックス$i$に対して独立に，確率$p_g$で$c_{ki}$を別のランダムな値に変える
　　世代数を1増やす
適応度が最大の個体を返す

という感じになります．このアルゴリズムは解析的な最適解への収束への保証はありませんが，上記のヒューリスティックな反復により問題によっては精度の良い解を短い反復で得られます．

以上！
…想像以上に数式が出てこねえ(当たり前)．ゆるふわ記事だからいっか．

##実際にやってみた
Goで上記のアルゴリズムに従ってコーディングしました．Goを書いたことも読んだこともなかったのでググりながら書いたため汚い．Goを使おうと思った理由は知り合いのエンジニアがGoとPythonを使ってて売り込まれたからというだけです．
ちょくちょくGoの説明も入れていきます．
最後にgithubへのリンクも貼ってあるので解説必要ない方や実装に興味ない方は読み飛ばしてください．

###運指のデータ構造
まずギターのポジションの情報をプログラムで扱える形にします．
ギターの音域は標準的な調弦ではE2からB#5(20フレット有だとC6)なので，低い方から0,1,...と番号をつけます．
例えばE3(ミ)の音は12に対応します．
posという配列のi番目の要素に、音iを弾いたときのポジションの配列を格納します．
ただし，音iを弾くポジションが複数ある場合どの弦で弾くかは今は区別しません．
E3は4弦2フレット，5弦7フレット，6弦12フレットで弾けるので，pos[12] = [2,7,12]というふうにします．
Goでは二次元配列は次のように初期化します．

var pos = [][]int{{0},{1},{2},{3},{4},{0,5},{1,6},{2,7},{3,8},{4,9},{0,5,10},{1,6,11},{2,7,12},{3,8,13},{4,9,14},{0,5,10},{1,6,11},{2,7,12},{3,8,13},{0,4,9,14},{1,5,10},{2,6,11},{3,7,12},{4,8,13},{0,5,9,14},{1,6,10,15},{2,7,11,16},{3,8,12,17},{4,9,13},{5,10,14},{6,11,15},{7,12,16},{8,13,17},{9,14,18},{10,15},{11,16},{12,17},{13,18},{14},{15},{16},{17},{18},{19},{20}}

目的とする旋律は音の番号で持ちます．各要素が和音を表します(本記事では便宜上「和音」と言った場合単音を指すこともあります．)

var input_melody = [][]int{{34},{26,22,17},{26,22,17},{33},{26,22,17},{31,26,22,17},{33,27,24,5},{17},{19},{21},{22},{24},{26},{27},{29},{31},{33},{34}}

さらに，和音に対して候補となるポジションを返す関数chordToPosを定めておきます．
Goには名前付き戻り値という概念があって，戻り値の宣言を関数の宣言に含めることができます．このとき戻り値の変数にはデフォルト値がセットされるっぽい？
また名前付き戻り値を使った時にはreturnのあとに何も書かなくてもその戻り値がreturnされます(naked returnという)．

func chordToPos(chord []int) (candidatePositions [][]int) {
  for i := 0; i < len(chord); i++ {
    candidatePositions = append(candidatePositions,pos[chord[i]])
  }
  return
}

###遺伝子情報の設計
さて，遺伝的アルゴリズムを用いるために，運指を何らかの関数$opt$で評価できる形の遺伝子情報に落としこむ必要があります．
Genomという構造体を作りましょう．Goでは型は変数名のあとに書きます．また，後のためにtypeをつけて新たな型を定義する形をとります(構造体の宣言には必ずしもtypeは必要ない)．C++でいうtypedefと似たような働きです．

type Genom struct {
  gene [][]int
  fitness float64
}

geneがGenom(個体)の持つ遺伝子列，fitnessがその遺伝子列に対して定義される適応度です．
なお，本記事では$opt$の最小化をはかるというスタンスでいくので，その意味的には反適応度という名前をつけるべきですが，ここでは面倒なのでfitnessで統一します．
geneはintの二次元配列の形をとっていますが，geneの各要素(intの配列)が旋律の中の各和音に対応していて，和音の構成音の情報が格納されています．input_melodyと同じ持ち方です．
例えば単音で C3 D3 E3 (ドレミ)と弾く場合は

[[8] [10] [12]]

となり，F G Em Amという王道？コード進行は

[[1 8 13 17 20 25] [3 7 10 15 19 27] [0 7 12 15 19 24] [5 12 17 20 24]]

となります．

さらに，Genom構造体のメソッドとして，これらのメンバを参照したり変更したりする関数を定めます．evaluate関数は後で定めます．
(Goではtypeで構造体の新たな型を定義することでメソッドを定義する，という形をとれます．)

func (g Genom) getFitness() float64 {
  return g.fitness
}

func (g Genom) getGene() [][]int {
  return g.gene
}

func (g *Genom) setFitness(fitness float64) {
  g.fitness = fitness
}

func (g *Genom) setGene(gene [][]int) {
  g.gene = gene
  g.evaluate()
}

また，あとでGenomの集合をFitnessに従ってソートしたりシャッフルしたりするので，次のように定義してしまいます．
ソートについてはGolang の sort パッケージ - Qiitaを参考にしました．
シャッフルにはFisher-Yates shuffleアルゴリズム - Wikipediaを用いました．

type GenomList []Genom

func (gl GenomList) min() float64 {
  var k float64  = 1e7
  for i:=0;i<len(gl);i++{
    if k > gl[i].getFitness(){
      k = gl[i].getFitness()
    }
  }
  return k
}

// for sorting BEGIN
func (gl GenomList) Len() int {
  return len(gl)
}

func (gl GenomList) Swap(i, j int) {
  gl[i], gl[j] = gl[j], gl[i]
}

func (gl GenomList) Less(i, j int) bool {
  return gl[i].fitness < gl[j].fitness
}
// for sorting END

func (gl GenomList) shuffle() {
  n := len(gl)
  for i := n-1; i>=0; i-- {
    j := rand.Intn(i+1)
    gl[i], gl[j] = gl[j], gl[i]
  }
}

###optの設計
遺伝子の持ち方を決めたので，次に関数$opt$を定めましょう．
遺伝的アルゴリズムは遺伝子の持ち方と適応度を計算する$opt$さえ設計してしまえば前述の擬似コードに従って実行することができるので，実装が非常に簡単です．

和音と和音の間の距離を，和音の各構成音同士の指板上での横方向の距離と定めます．こうすることで横方向の移動を最小化できます．
$opt$としては，隣接する和音間の距離と，1つおきの和音の距離を足しあげたものとします．2つ離れた和音も含めることで，全体として自然な運指になることを期待します．いくつ和音を含めるかは，いくつか試してみて最も実際の運指っぽいものが生成されるものとして2に決めました．離れたものは重みを小さくするなども考えられますが割愛．
$opt$が定められたので，コードに落としていきます．
まずポジション(フレット数)から横方向の位置を返す関数を定義します．ギターの画像を見れば分かるように，ギターのフレットの間隔は穴に近づくにつれて短くなっているので，これを考慮します．ギターは平均律の楽器なので以下のようになります(650は有効な弦の長さ，開放:position=0に相当)．

func positionToX(position int) float64 {
  return 650*(1-1/(math.Pow(2,float64(position)/12)))
}

次にこれを使ってGenomの遺伝子列を$opt$で評価する関数evaluateを定義します．愚直な実装．
以降，Genomを作ってgeneを代入したタイミングでevaluate関数を呼ぶようにします．

func (g *Genom)evaluate() {

  gene := g.getGene()
  var sum float64 = 0
  for d := 1; d < 3 ; d++ {

    for i := 0; i < len(gene)-d; i++ {

      g1 := gene[i]
      g2 := gene[i+d]

      for j := 0; j < len(g1); j++ {
        for k := 0; k < len(g2); k++ {
          if g1[j]*g2[k] != 0{
            sum += math.Abs(positionToX(g1[j])-positionToX(g2[k]))
          }
        }
      }
    }
  }
  g.setFitness(sum)
}

###遺伝的アルゴリズムの設計
最後に遺伝的アルゴリズムの部分を実装していきます．
・GenomListの初期値を定めるcreateGenom(とそのための関数たち)
・GenomListからエリートを選び出すselectGenom
・２つのGenomの交叉を行うcrossover
・現在のGenomListとエリートGenomList，さらにエリートGenomListに交叉を施したGenomたちを統合して次世代のGenomListを作るnextGLCreate
・突然変異を行うmutation

####createGenom
ひとつ目から．最初のGenomListは和音のポジションをランダムに決める必要があるので，これを実装します．
chordToPosで返される和音のポジションの候補の配列を引数にとります．

func randomChooseChordPos(candidatePositions [][]int) (positions []int) {

  var ind int = 0
  for i := 0; i < len(candidatePositions); i++ {
    ind = rand.Intn(len(candidatePositions[i]))
    positions = append(positions,candidatePositions[i][ind])
  }
  return
}

これを実装したらランダムに初期化をするcreateGenomが実装できますね．

func createGenom(melody [][]int) (genom Genom) {

  var positions [][]int
  for i := 0; i<len(melody); i++ {
    var pos []int = randomChooseChordPos(chordToPos(melody[i]))
    positions = append(positions,pos)
  }
  genom.setGene(positions)
  return
}

####selectGenom
次にselectGenomを実装します．これは単純にソートして上位を取り出すだけです．
appendは配列に要素を追加するメソッドでしたが，配列に配列を追加することもできます．その場合は追加する配列名に...をつけます．結構これでコンパイルエラー吐かれた．

func selectGenom(gl GenomList, eliteNum int) (gl_Elite GenomList) {

  gl_Elite = append(gl_Elite,gl...)
  sort.Sort(gl_Elite)
  return gl_Elite[:eliteNum]
}

####crossover
交叉は(やっていることに対して)コードが少し煩雑になります．今回は二点交叉を実装しました．cross_1とcross_2はランダムに選ばれた交叉を行う範囲です．
2つの配列の部分配列を入れ替える方法が他に良い方法がわからずこんな実装になりました．

func crossover(genom1, genom2 Genom) (gl_Ret GenomList) {

  cross_1 := rand.Intn(GENOM_LENGTH)
  cross_2 := rand.Intn(GENOM_LENGTH-cross_1)+cross_1
  gene_1 := genom1.getGene()
  gene_2 := genom2.getGene()

  var progeny_1 [][]int
  var progeny_2 [][]int
  progeny_1 = append(progeny_1, gene_1[:cross_1]...)
  progeny_2 = append(progeny_2, gene_2[:cross_1]...)
  progeny_1 = append(progeny_1,gene_2[cross_1:cross_2]...)
  progeny_2 = append(progeny_2,gene_1[cross_1:cross_2]...)
  progeny_1 = append(progeny_1,gene_1[cross_2:]...)
  progeny_2 = append(progeny_2,gene_2[cross_2:]...)

  progenom1 := Genom{progeny_1,0}
  progenom2 := Genom{progeny_2,0}
  progenom1.evaluate()
  progenom2.evaluate()
  gl_Ret = append(gl_Ret,progenom1)
  gl_Ret = append(gl_Ret,progenom2)
  return gl_Ret 
}

####nextGLCreate
nextGLCreateを実装します．単純な配列の結合．

func nextGLCreate(gl, gl_Elite, gl_Progeny GenomList) (gl_Next GenomList) {

  gl_Next = append(gl_Next, gl...)
  gl_Next.shuffle()
  gl_Next = gl_Next[:len(gl_Next)-len(gl_Elite)-len(gl_Progeny)]
  gl_Next = append(gl_Next, gl_Elite...)
  gl_Next = append(gl_Next, gl_Progeny...)
  return gl_Next
}

####mutation
最後にmutationを実装すれば準備は万端です．

func mutation(gl GenomList, indivMutateRate float64, geneMutateRate float64) (gl_Ret GenomList) {

  for i := 0; i < len(gl); i++ {
    genom := gl[i]
    if indivMutateRate > float64(rand.Intn(100))/100 {
      var newGenom [][]int
      for j := 0; j < len(genom.getGene()); j++ {
        if geneMutateRate > float64(rand.Intn(100))/100{
          p := randomChooseChordPos(chordToPos(input_melody[j]))
          newGenom = append(newGenom, p)
        } else {
          p := genom.getGene()[j]
          newGenom = append(newGenom, p)
        }
      }
      genom.setGene(newGenom)
    }
    gl_Ret = append(gl_Ret,genom)
  }
  return gl_Ret
}

上記をまとめたコードをgithubにおいておきました．

##実験と考察
さて，以上のコードを用いて最適なポジションを探索してみました．
対象のフレーズですが，僕のお気に入りの曲:椿姫の主題による幻想曲(作曲:J.アルカス)の一部分を使ってみました．
この曲は以下からどうぞ．

5:58からの3秒間のフレーズを使いました．なおベースの音はドロップDチューニングで6弦開放でしか弾けないので無視しました．

まず最適な運指は次のようになりました:

[[10] [7 7 7] [7 7 7] [9] [7 7 7] [7 7 7 7] [9 8 0 0] [7] [0] [11] [12] [0] [11] [12] [14] [12] [14] [15]]

実際の運指は次のようです:

[[10] [7 7 7] [7 7 7] [9] [7 7 7] [7 7 7 7] [9 8 9 0] [7] [9] [6] [7] [9] [7] [8] [10] [7] [9] [10]

最初の6和音は実際の運指と一致しています．その次の[9 8 0 0]は実は実際には演奏不可能です．というのも現在の実装では弦の番号を考慮していないので，1つの弦で2つの音を弾く状況が発生してしまいます．そこで改善点として，evaluateの中で，和音の中に同じ弦で弾く音がある場合は十分大きな値を返す必要があります．また，このフレーズでは顕在化していませんがひとつの和音の中での音同士の距離もevaluateに加えないと物理的に押さえられないケースが最適値として返されるおそれがあります(和音間の距離の最小化である程度抑制は効いているが)．

そのあとの単音のスケールですが，これも実際と異なります．2箇所[0]がありますが，これは弦を押さえずに弾くことに対応します．これは簡単に弾けるので，実はevaluateでは開放弦の場合はsumに値を加えていません．そうするとこのようなスケールの場所では開放で弾けるものは開放で弾こうとします．実際にはこれも開放で弾かないほうが右手的にも左手的にも音色的にも良いことが多く(ハイフレットでは特に)，それを考慮した$opt$を設計しないと実際の運指とは一致しません．

あと，ギターのフレット幅がハイフレットの方が小さいので，割とハイフレットで弾こうとするのも特徴として見られますね(後半)．

また，遺伝的アルゴリズムといっても交配や突然変異の方法には様々なバリエーションがあって，今回実装したものがこの問題に適していたかはわかりません．
エリートの数を多めにしていたので，最終的には同じ遺伝子をもつエリートが上位を占めるようになります．

プログラムを実行すると分かるのですが(実行環境にもよるかもしれないが)突然変異の確率を両方0.3にすると200~1000世代くらいで変化がなくなったと思いきや直後に最適値っぽいもの(上記の解)が求まります．実はこれは最適値ではないのですが，突然変異の確率をいじるなどすると最適値が求まったりして，さながら機械学習のパラメータチューニングのようです(適当)．

##おわりに
長かった．
ここまで読んでいただきありがとうございました．前からこれっぽいことをやってみたかったので一区切り．改善の余地はとてもあるのでぼちぼちやりたいけれど，運指を決めるのはあくまで自分の耳と頭でやるのが丸い，という感じです．初見力をつけよう(特大BU-MERAN)．
無事にYoutuberデビューできて一安心です(動画をどう共有するかで一番頭を悩ませた末の苦肉の策)．