18

私は Haskell プログラミングの世界に不慣れで、巡回セールスマン問題の適切な解決策を見つけるための単純な遺伝的アルゴリズムに歯を食いしばっています。私はソリューションを整数の順列として表現しているので、このタイプのシノニムがあります

type Genome = [Int]

アルゴリズム自体は、解を操作する一連の関数です。

mutation :: Genome -> Genome
selectParents :: [Genome] -> [Genome] -> [Genome]
crossover :: Genome -> Genome -> (Genome, Genome)
selectSurvivors :: [Genome] -> [Genome] -> [Genome]

私のコードが私の質問にどの程度関連しているかわかりませんので、詳細が必要かどうか尋ねてください。言及する価値があるかもしれないことの 1 つは、上記の型シグネチャが実際には単純化されていることです。実際、私は State モナドを使用して を持ち歩いているStdGenため、これらすべての関数は実際にステートフルな計算を返します。

これでやりたいことがいくつかありますが、頭を悩ませることはできません。ソリューションにさまざまな表現を選択できるようにしたいのですが、これは型クラスを使用するのに自然な場所であると思われるためGenome、型クラスと[Int]this の特定のインスタンスになりますGenome。

今、私は実装を実験できるようになりたいと思っています。また、他のプロジェクトでコードを使用できるようにしたいと考えています。このような型クラスを使用すると、新しいアルゴリズムを作成するたびに の別のインスタンスを作成する必要がありますがGenome、これはライブラリを作成する良い方法ですか?

おまけの質問の 1 つですが、私を悩ませているのは、関数の型シノニムのようなものを作成して、関数を引数として受け取る関数を作成する場合に、型全体ではなくシノニムを作成できるようにする方法はありますか?関数の署名、つまり次のようなものが機能するようにします。

type someFunc = [Int] -> [Int] -> Int
someOtherFunc :: someFunc -> [Int] -> Int

そうです、うまくいけば、それが問題の十分に明快な説明です。私は本当に明白な答えを見逃したように感じますが、それは私に飛びつきませんでした. 乾杯

4

2 に答える 2

8

残念ながら、理想的なソリューションは通常、問題のドメインによって異なります。 このブログ投稿では、型クラスのアプローチとビット単位のアプローチについて説明しています。個人的には、柔軟性が必要な場合はハイブリッド アプローチが最適だと思います。適切なビット単位のマッピングがある場合は、それを定義できます。実装はそこから派生します。そうでない場合は、クロスオーバーを実装して手動で変更できます。

jaの方法は実際にはうまくいきません。ゲノム関数のいくつかはランダムな入力を必要とするでしょう。これは、このスレッドのような乱数ジェネレーターを使用してステート モナドで実行することで取得できます。

class Genome a where
    fitness :: a -> Int
    breed :: (RandomGen g, MonadState g m) => a -> a -> m a
    mutate :: (RandomGen g, MonadState g m) => a -> m a

次に、実装に関係なく、一連のゲノムを操作する共通の関数を用意します。

selectParents :: (Genome a, RandomGen g, MonadState g m) => [a] -> m [a]
selectSurvivors :: (Genome a, RandomGen g, MonadState g m) => [a] -> m [a]

適切なビット マッピングがある場合は、BitArray に固定関数を定義するだけで済みます (それぞれがフィットネス関数をパラメーターとして取得する必要があることに注意してください)。

breed :: (RandomGen g, MonadState g m) => BitArray -> BitArray -> m BitArray
mutate :: (RandomGen g, MonadState g m) => BitArray -> m BitArray
selectParents :: (RandomGen g, MonadState g m) => (BitArray -> Int) -> [BitArray] -> m [BitArray]
selectSurvivors :: (RandomGen g, MonadState g m) => (BitArray -> Int) -> [BitArray] -> m [BitArray]
于 2011-02-19T09:12:13.457 に答える
2

はい、型クラスを使用してゲノムを表すことは良い方法です。このようなもの：

クラスゲノム
   突然変異 :: a -> a
   selectParents :: [a] -> [a] -> [a]
   交差 :: a -> a -> (a, a)
   selectSurvivors :: [a] -> [a] -> [a]
インスタンスゲノム [a] ここで
   突然変異 l = l
   selectParents l1 l2 = l1
   交差 g1 g2 = (g1,g2)
   selectSurvivors l1 l2 = l1
データツリー a = リーフ a | ブランチ [ツリー a]   
インスタンス ゲノム (ツリー a) どこで
   突然変異 t = t
   selectParents l1 l2 = l1
   交差 g1 g2 = (g1,g2)
   selectSurvivors l1 l2 = l1

各アルゴリズムの新しいデータ型のインスタンス化に関しては、ライブラリにいくつかのインスタンスを含めることができますが、新しいインスタンス化に問題はありません - それがポイントです!

于 2011-02-16T17:16:04.433 に答える