ruby で遺伝的アルゴリズムを使って巡回セールスマン問題を解くプログラムを作成しました、思ったように値が収束しません。

Question

言語はrubyを使って巡回セールスマン問題を解くプログラムを作成しました。遺伝的アルゴリズムを用い、遺伝情報などアルゴリズムで用いる固有の変数や配列をクラスを用いてひとまとめにしてあります。

アルゴリズムとしては基本的なスタイルは踏襲し、また遺伝情報の交叉もテストにて正しく交叉されていることは確認できました（交叉の点数は４点交叉です）。また適合度の高い順にソートも出来ています。次の世代にはその中から上位５０％を残し、ルーレット式で次世代の遺伝情報を選択しています。

一通り作成し、実際に動作させてみました。個体数２５６、世代数３０世代にわたって回し、結果を出力させました。３０世代までだいたい距離４５から４０の間を行ったり来たりしており、参考書に書かれているようにきれいに収束する様子が見られません。（解答は 35.626）

選択の方法に問題があるのかと思っています。また突然変異の確率も調整が必要かもしれません。

ソースに関してはもう少しシンプルに書きたいと思っています。なんとなくＣ言語 like なソースになっています。500行は長すぎな気がしています。

ソースを添付しますので、ご回答をよろしくお願いいたします。ソースは最初に作成した genetic クラスのみ添付します。

#------------------------------------------------------------------------------------#
#Geneticsクラス（genesの生成と、交叉）
class Genetics

#インスタンス変数 genes, value, evaluation は参照と変更可能
attr_accessor :genes
attr_accessor :value
attr_accessor :evaluation
attr_accessor :reciprocal

#コンストラクタ（インスタンス変数 @genes, @value, @evaluation, @reciprocal生成)
def initialize(number_of_genes, max_value, overwrap)
  @genes = Array.new(number_of_genes, 0)    #genes配列（遺伝情報を格納する配列）
  @value = Array.new(number_of_genes, 0.0)    #value配列（遺伝情報に基づく値（表現型の情報））
  @evaluation = 1.0    #value配列に基づき、各個体の評価関数の値（適合度）を格納
  @reciprocal = 0.0    #評価関数の値（evaluation)の逆数を格納（評価関数が少ないほど良い場合に用いる）

  #重複を認める場合、ランダムに遺伝情報を生成
  if overwrap == 0
    for i in 0..(number_of_genes-1) do
      @genes[i] = Random.rand(max_value * 10) % max_value
    end
  #重複を認めない場合、遺伝情報の分だけ値をシャッフルして生成
  else
    for i in 0..(number_of_genes-1) do
      @genes[i] = i
    end

    @genes.shuffle!
  end

end

#crossメソッド(２つの親の遺伝情報を交叉、１点交叉）
def cross(other, child1, child2, number_of_genes, max_value, overwrap, cross)

  index = 0
  division = number_of_genes / (cross+1)

  #重複を認める場合
  if overwrap == 0
    stack = 0

    #cross（交叉点数により交叉する、しないの区別）
    for i in 0..(cross) do

      #i が偶数（０を含む）の遺伝情報は親をそのまま引き継ぐ
      if (i != cross)  && ( ( i / 2 ) == 0 )
        for j in (division * i)..( (division * (i+1)) -1 ) do
          child1.genes[j] = self.genes[j]
          child2.genes[j] = other.genes[j]
        end

      #i が奇数の場合は遺伝情報を交換
      elsif (i != cross) && ( ( i / 2 ) != 0)
        for j in (division * i)..( (division * (i+1)) -1 ) do
          child1.genes[j]= other.genes[j]
          child2.genes[j] = self.genes[j]
        end

      #iが偶数（０を含む）でかつラスト（ラストまで交換なし）
      elsif (i == cross)  && ( ( i / 2 ) == 0)
        for j in (division * i)..( number_of_genes -1 ) do
          child1.genes[j] = self.genes[j]
          child2.genes[j] = other.genes[j]
        end

      #i が奇数でかつラスト（ラストまで交換）
      elsif (i == cross) && ( ( i / 2 ) != 0)
        for j in (division * i)..(number_of_genes-1) do
          child1.genes[j]= other.genes[j]
          child2.genes[j] = self.genes[j]
        end

      end    #if文終わり

      #突然変異（各個体について、１つの遺伝子を書き換え）
      index = Random.rand(number_of_genes * 10) % number_of_genes
      child1.genes[index] = Random.rand(max_value)
      child2.genes[index] = Random.rand(max_value)
      #puts "index = " + index.to_s
    end

  #重複を認めない場合
  else
    stack = 0

    one_to_two = 0
    two_to_one = 0

    #親から子へそのままコピー
    for i in 0..(number_of_genes-1) do
      child1.genes[i] = self.genes[i]
      child2.genes[i] = other.genes[i]
    end

    for i in 0..cross do

      #交差点が偶数で crossの値が（ラスト）でない場合はそのまま
      if (i != cross) && ( (i / 2) == 0 )
        next

      #交差点が奇数で crossの値が（ラスト）でない場合は遺伝情報を交換
      elsif ( i != cross) && ( (i / 2) != 0 )
        for j in (division * i)..( (division * (i+1)) -1 ) do
          one_to_two = child1.genes[j]
          two_to_one = child2.genes[j]

          if child1.genes[j] == child2.genes[j]
            child1.genes[j] = two_to_one
            child2.genes[j] = one_to_two
          else
            #2つの個体の遺伝情報が異なる場合、各個体間で入れ替え（重複を避けるため）
            for k in 0..(number_of_genes-1) do
              if child1.genes[k] == two_to_one && (k != j)
                child1.genes[k] = child1.genes[j]
                child1.genes[j] = two_to_one
                break
              end
            end

            for k in 0..(number_of_genes-1) do
              if child2.genes[k] == one_to_two && (k != j)
                child2.genes[k] = child2.genes[j]
                child2.genes[j] = one_to_two
                break
              end
            end

          end    #if文終了（遺伝情報が同じかどうかの判定）
        end    #for文終了（遺伝情報の交換）

      #交差点が偶数で cross（ラスト）の場合はループ終了
      elsif (i == cross) && ( (i / 2) == 0 )
        break

      #交差点が奇数で cross（ラスト）の場合は最後（number_of_genes -1)まで遺伝情報を交換
      elsif (i == cross) && ( (i / 2) != 0 )
        for j in (division * i)..( number_of_genes -1 ) do
          one_to_two = child1.genes[j]
          two_to_one = child2.genes[j]

          if child1.genes[j] == child2.genes[j]
            child1.genes[j] = two_to_one
            child2.genes[j] = one_to_two
          else
            #2つの個体の遺伝情報が異なる場合、各個体間で入れ替え（重複を避けるため）
            for k in 0..(number_of_genes-1) do
              if child1.genes[k] == two_to_one && (k != j)
                child1.genes[k] = child1.genes[j]
                child1.genes[j] = two_to_one
                break
              end
            end

            for k in 0..(number_of_genes-1) do
              if child2.genes[k] == one_to_two && (k != j)
                child2.genes[k] = child2.genes[j]
                child2.genes[j] = one_to_two
                break
              end
            end

          end    #if文終了（遺伝情報が同じかどうか判定）
        end    #for文終了 (遺伝情報の交換）

      end    #if文終了 (crossが偶数か奇数か)
    end    #for文終了（cross＝交叉点数の分だけ）

    #突然変異（各個体について、１つの遺伝子を書き換え）
    index = Random.rand(number_of_genes * 10) % number_of_genes
    stack = child1.genes[index]
    child1.genes[index] = Random.rand(max_value)

    for j in 0..(number_of_genes-1) do
      if child1.genes[j] == stack && (j != index)
        child1.genes[j] = stack
        break
      end
    end

    index = Random.rand(number_of_genes * 10) % number_of_genes
    stack = child2.genes[index]
    child2.genes[index] = Random.rand(max_value)

    for j in 0..(number_of_genes-1) do
      if child2.genes[j] == stack && (j != index)
        child2.genes[j] = stack
        break
      end
    end

    stack = 0
    index = 0

  end    #overwrapによる場合分け終了
end    #crossメソッド終了

end
#Geneticクラス定義ここまで
#---------------------------------------------------------------------------------#

Comments

[yuba]

genesという配列に入っているのは、都市の巡回順でしょうか？
当然、重複や欠落はないはずですよね。
で、他の遺伝子と交叉するとその結果は重複や欠落がないことが保証できなくなると思いますが、実際crossメソッドでは重複を許さない場合にどうするかの記述がないようです。どのようにしているのですか？

[shigemi_sano]

yubaさん、ご質問ありがとうございます。

重複を許さない場合ですが、こちらはかなり処理が長くなっております。もちろん genesの情報はここでは都市の巡回順です。ここで遺伝情報の重複を許すために（その方が交叉の処理が少なくて済むので）、genesの並びの規則はこのようにしています。１０都市の巡回の場合です。

最初の番号(genes[0])は１とする（出発は固定する）
genes[1]は [1, 2, 3, 4, 5, 6, 7, 8, 9]のいずれかが入る。この場合すでに都市１は選ばれているので、このような対応になる。

genes[1] : [1, 2, 3, 4, 5, 6, 7, 8, 9]
実際の都市: [2, 3, 4, 5, 6, 7, 8, 9 , 10]

もし、genes[1]に3が入った場合（実際の都市は４）genes[2]の選べる値と実際の都市との関係は
genes[2] : [1, 2, 3, 4, 5, 6, 7, 8]
実際の都市 : [2, 4, 5, 6, 7, 8, 9, 10]
つまり、残った都市の中の何番目か、という情報が各 genes の値となっています。そこで重複はＯＫとなっています。

重複をこのようにＯＫとしたのは、重複が不可の場合、遺伝情報の交叉において、それぞれの遺伝情報の並び替えをするため、交叉の効果がなくなるのでは、と判断したからです。重複不可の場合もうまく収束しませんでした。
最初の質問を編集してソースを追加します。

[yuba]

帰ってからまた考えますが、タグにアルゴリズムがあると目に止まりやすいかと思います。

[shigemi_sano]

yubaさん、さっそくの返信ありがとうございます。タグにアルゴリズムを追加しました。アドバイスありがとうございました。

Answer 1

あまり、これが原因だとは断定しにくい質問ですね。

遺伝的アルゴリズムで巡回セールスマン問題を解く場合、
代表的な遺伝子表現として、パス表現、隣接表現、順序表現があるようですね。

順序表現は、交差による致死個体の生成を防げますが、
親の形質を継承しにくいと思います。
以下のページで、実際の例を挙げて、親の形質を継承できない場合を
説明しています。
順序問題へのGAの適用

交叉点の左側の経路は親のものが保存されているが， 右側の経路では壊されており，親の一部しか継承されない．

別の遺伝子表現を採用した方が、収束しやすいのかも知れません。

このままの遺伝子表現とするとした場合ですが、
交叉をは2点交叉くらいにした方が良いかも知れません。
Wikipediaの遺伝的アルゴリズムを見ても、

一般に、3点以上の交叉点をもつ方法を多点交叉あるいは n 点交叉という。しかしながら一部の問題を除き、多点交叉は二点交叉と下記で述べる一様交叉のどちらかよりも良い値が出ることはほとんどなく、あまり使われていない。

とあり、多点交叉は効果が低いのではと思います。
さらに、順序表現なので、交叉点数が増えると、
より親の形質を継承しない子が生成されてしまうのではないでしょうか？

Comments

[eripong]

コードを見ると、4点交叉ではなく1点交叉ですか？

[shigemi_sano]

eripong さん、回答ありがとうございます。そして貴重な資料のリンクを貼ってくださり感謝します。まずは遺伝子表現を検討して、もっとも親の性質を受け継ぐことの出来る表現と、それに伴う交叉点数を検証してみたいと思います。アルゴリズムの奥の深さを実感できました。

[shigemi_sano]

eripongさん、もう一点ご質問のあった件ですが、実行した際には交叉点数は４点でやってみました。最初は１点交叉にしたのですが、そこで収束しなかったので調整してみました。crossメソッドの最後の引数である crossによって交叉点数を可変出来るようにしてあります。

[eripong]

「順序問題へのGAの適用」を見ると書いてありますが、
遺伝子表現を変えた場合、交叉の方法も変わります。
そのため、交叉点数の調整というより、交叉方法の選択になると思います。

交叉点数の変更については、了解です。