遺伝的アルゴリズムとは

ざっくりと説明すると，

初期値として，N個の個体を無作為に生成する
評価関数を用いて，上位のM個の個体を選ぶ（エリート主義）
一定の確率に従い，交差や突然変異を行い，N個まで増やす
一定回数2~3を繰り返す

今回は交差，突然変異を次のように実装している．
選択の仕方や，交差の仕方などはいくつかの種類があります．

交差

個体A, Bの要素に対して，乱数Rを0~要素数-1の間で発生させ，

A[Begin to R-1] + B[R to End]

上記のよう繋ぎ合わせることで，新たな個体を生成．

突然変異

個体Xのある要素に対して，STEP数（正の整数）を同等の確率で可算または減算する．

X[R] += STEP
or
X[R] -= STEP

例

Githubに置いている例を紹介．

タスク

５冊の本の中から，読みたい本２冊を１０人に上げてもらう．
それぞれの本は，２冊づつしかない．
全体の満足度を最大化するためには，どのように分配すればよいか？

それぞれが上げた本の組

prefs = [('Alicia',
              ("The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).",
               'Something Wicked This Way Comes')),
             ('Caesar',
              ('Do Androids Dream of Electric Sheep?',
               "I Was Told There'd Be Cake")),
             ('June',
              ('Pride and Prejudice and Zombies',
               'Do Androids Dream of Electric Sheep?')),
             ('Gaston',
              ('Do Androids Dream of Electric Sheep?',
               "I Was Told There'd Be Cake")),
             ('Edgar',
              ('Pride and Prejudice and Zombies',
               "The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).")),
             ('Claire',
              ('Something Wicked This Way Comes',
               "I Was Told There'd Be Cake")),
             ('Lana',
              ("I Was Told There'd Be Cake",
               'Pride and Prejudice and Zombies')),
             ('Kevin',
              ("The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).",
               'Something Wicked This Way Comes')),
             ('Aaron',
              ("The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).",
               'Something Wicked This Way Comes')),
             ('Nina',
              ('Something Wicked This Way Comes',
               'Pride and Prejudice and Zombies'))]

出力例

$ python src/example.py
(8, [7, 5, 0, 0, 0, 1, 2, 1, 1, 0])
(8, [7, 5, 0, 0, 0, 1, 2, 1, 1, 0])
(8, [7, 5, 0, 0, 0, 1, 2, 1, 1, 0])
(8, [7, 1, 0, 2, 0, 4, 3, 0, 1, 0])
(8, [6, 5, 0, 0, 0, 1, 3, 2, 1, 0])
(7, [7, 1, 0, 0, 0, 1, 2, 1, 1, 0])
(7, [6, 1, 0, 0, 0, 1, 2, 1, 1, 0])
(6, [7, 1, 0, 0, 0, 4, 3, 1, 1, 0])
(6, [6, 1, 0, 0, 0, 4, 3, 1, 1, 0])
(2, [7, 1, 1, 0, 0, 4, 3, 1, 1, 0])
(2, [6, 1, 1, 0, 0, 4, 3, 1, 1, 0])
…
Alicia  Something Wicked This Way Comes
Caesar  Do Androids Dream of Electric Sheep?
June    Pride and Prejudice and Zombies
Gaston  Do Androids Dream of Electric Sheep?
Edgar   Pride and Prejudice and Zombies
Claire  I Was Told There'd Be Cake
Lana    I Was Told There'd Be Cake
Kevin   The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).
Aaron   The Hitchhiker's Guide to the Galaxy (Hitchhiker's Guide to the Galaxy).
Nina    Something Wicked This Way Comes