質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.61%

  • Ruby

    7324questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    392questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

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

受付中

回答 1

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 1,630

shocyu

score 10

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

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

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

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

ソースに関してはもう少しシンプルに書きたいと思っています。なんとなくC言語 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メソッド(2つの親の遺伝情報を交叉、1点交叉)
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 が偶数(0を含む)の遺伝情報は親をそのまま引き継ぐ
      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が偶数(0を含む)でかつラスト(ラストまで交換なし)
      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文終わり

      #突然変異(各個体について、1つの遺伝子を書き換え)
      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=交叉点数の分だけ)

    #突然変異(各個体について、1つの遺伝子を書き換え)
    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クラス定義ここまで
#---------------------------------------------------------------------------------#
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • yuba

    2015/09/24 22:30

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

    キャンセル

  • shocyu

    2015/09/25 15:10

    yubaさん、ご質問ありがとうございます。 重複を許さない場合ですが、こちらはかなり処理が長くなっております。もちろん genesの情報はここでは都市の巡回順です。ここで遺伝情報の重複を許すために(その方が交叉の処理が少なくて済むので)、genesの並びの規則はこのようにしています。10都市の巡回の場合です。 最初の番号(genes[0])は1とする(出発は固定する) genes[1]は [1, 2, 3, 4, 5, 6, 7, 8, 9]のいずれかが入る。この場合すでに都市1は選ばれているので、このような対応になる。 genes[1] : [1, 2, 3, 4, 5, 6, 7, 8, 9] 実際の都市: [2, 3, 4, 5, 6, 7, 8, 9 , 10] もし、genes[1]に3が入った場合(実際の都市は4)genes[2]の選べる値と実際の都市との関係は genes[2] : [1, 2, 3, 4, 5, 6, 7, 8] 実際の都市 : [2, 4, 5, 6, 7, 8, 9, 10] つまり、残った都市の中の何番目か、という情報が各 genes の値となっています。そこで重複はOKとなっています。 重複をこのようにOKとしたのは、重複が不可の場合、遺伝情報の交叉において、それぞれの遺伝情報の並び替えをするため、交叉の効果がなくなるのでは、と判断したからです。重複不可の場合もうまく収束しませんでした。 最初の質問を編集してソースを追加します。

    キャンセル

  • yuba

    2015/09/25 15:19

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

    キャンセル

  • shocyu

    2015/09/25 15:22

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

    キャンセル

回答 1

+2

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

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

順序表現は、交差による致死個体の生成を防げますが、
親の形質を継承しにくいと思います。
以下のページで、実際の例を挙げて、親の形質を継承できない場合を
説明しています。
順序問題へのGAの適用
交叉点の左側の経路は親のものが保存されているが, 右側の経路では壊されており,親の一部しか継承されない.
別の遺伝子表現を採用した方が、収束しやすいのかも知れません。

このままの遺伝子表現とするとした場合ですが、
交叉をは2点交叉くらいにした方が良いかも知れません。
Wikipediaの遺伝的アルゴリズムを見ても、
一般に、3点以上の交叉点をもつ方法を多点交叉あるいは n 点交叉という。しかしながら一部の問題を除き、多点交叉は二点交叉と下記で述べる一様交叉のどちらかよりも良い値が出ることはほとんどなく、あまり使われていない。
とあり、多点交叉は効果が低いのではと思います。
さらに、順序表現なので、交叉点数が増えると、
より親の形質を継承しない子が生成されてしまうのではないでしょうか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/09/25 18:59 編集

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

    キャンセル

  • 2015/09/25 19:33

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

    キャンセル

  • 2015/09/25 19:36

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

    キャンセル

  • 2015/09/25 19:49

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

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Ruby

    7324questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    392questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

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