遺伝的アルゴリズムとは
生きものの進化をまねて、答えを探す方法です。1970年代にジョン・ホランドが形にしました。くり返すのは4つだけです。
① 評価 全員を同じ条件でためして、点数（適応度）をつける。ここでは15秒で進んだ距離。
② 選択 点数の高いものが親になる。
③ 交叉 2匹の親の遺伝子をまぜて子を作る。
④ 突然変異 子の遺伝子を少しだけ、でたらめに変える。
だれも「こう歩け」とは教えていません。でたらめな体から始めても、残るものと消えるものがあるだけで、世代をかさねると歩き方が「見つかって」いきます。
この生きものの遺伝子
体は関節（丸）と筋肉（帯）でできています。遺伝子に書いてあるのは:
・関節の数（3〜8）と、生まれたときの位置
・足の裏のすべりにくさ（摩擦係数 0.2〜1.2。暗い丸ほどすべりにくく、爪のように地面をつかむ力も強い）
・筋肉がどの関節をつなぐか、縮んだ長さと伸びた長さ、強さ（太さで表示）
・体のリズム（1周の秒数）と、筋肉ごとに1周のどこで縮むか
筋肉は時計に合わせて縮んだり伸びたりするだけで、まわりを見てはいません。それでも、すべりにくい足で地面をつかみ、すべりやすい足を前に出すと、体が前へ進みます。ミミズやシャクトリムシも、体の毛や吸盤で「すべりにくさ」を切りかえて進みます。
関節や筋肉の数が変わる突然変異もあります。関節と筋肉の数の組み合わせを種と呼んで色を分けています（多い8種まで。ほかは灰色）。
環境がちがうと、ちがう体に
同じシードで環境だけを変えて、何十世代か進めてみてください。上り坂では、すべり落ちないよう、すべりにくい足が増えます。氷の上では、地面をけっても力が伝わりにくいかわりに、すべりだすと止まりにくいので、スケートのようにすべって進むものが出てきます。月面では跳ねて長く飛ぶ動きが得になります。水の中には地面がないので、筋肉の棒で水をかく、まったく別の泳ぎ方になります。
進化のとちゅうで環境を変えると、それまでの1位が急に進めなくなり、また何世代かかけて適応していくようすが見えます（グラフの黄色の線）。
本物の進化とのちがい
目的がない: 本物の進化には「15秒で遠くへ」のような決められた点数はありません。その場所で生きのびて、子を多く残したものの性質が、結果として広がります。
偶然: 本物では、強くても運が悪くて子を残せないことがあります。集団が小さいほど偶然の影響が大きくなります（遺伝的浮動）。このアプリの「トーナメント」は、くじ引きで対戦相手が決まるので、少し偶然が入ります。
遺伝子の量: ヒトの DNA は約30億文字。この生きものの遺伝子は数十個の数字です。また、ここでは体の形が遺伝子にそのまま書いてありますが、本物の体は遺伝子が細胞の増え方を調節して、発生の中で作られます。
歴史
1975年、ホランドが本『Adaptation in Natural and Artificial Systems』で遺伝的アルゴリズムをまとめました。1994年、カール・シムズは、ブロックと関節でできた仮想の生きものを3次元の物理の中で進化させ、泳ぐ・歩く・跳ぶものが生まれる映像（Evolving Virtual Creatures）を発表しました。
ゲームでは、1998年の『アストロノーカ』で、畑をあらす生きもの「バブー」が、わなをくぐりぬけたものから子を残して、だんだん手ごわくなりました。このアプリの関節と筋肉の体と、種の色分けの見せ方は、carykh さん（Cary Huang）の進化シミュレーターを参考にしています。
このアプリのしくみと簡単にしたところ
物理: 関節は 2kg の点、筋肉は減衰のあるばね（強さ 150〜600N/m）。縮む時間帯は「縮んだ長さ」、それ以外は「伸びた長さ」に近づこうとします。地面に当たった関節は、下向きの勢いを止めた分に摩擦係数をかけた分だけ、横の勢いも止まります（クーロン摩擦）。それに加えて、すべりにくい足ほど、爪やひづめが土にくいこむように地面をつかみます（いちばん強い足で 200N。押しつける力に関係なく効く）。重力は地球 9.8m/s²、月 1.62m/s²。1/120 秒ずつ計算します。
水の中: 体は水と同じ重さとしました（魚のうきぶくろのように、浮きも沈みもしない）。筋肉を太さ 6cm の棒とみなし、棒に垂直に動くと速さの2乗に比例する抵抗（抵抗係数 1.0）、棒に沿って動くと小さな抵抗を受けます。
簡単にしたところ: 2次元（前後と上下だけ）なので、体の部品は1枚の平面の上にあり、おたがいにすり抜けられません。関節は直径 11cm の玉、筋肉は太さ 6cm の棒として、ぶつかると押し戻し、はね返らずに止まり、こすれると摩擦（0.4）がはたらきます。平面の上では交差した筋肉はほどけないので、筋肉が交差しない体だけが生まれるようにしています（突然変異で交差する形になったら、やり直し）。強い筋肉で押しつけたときは、玉や棒が少しめりこむことがあります。筋肉はばねで、本物の筋肉のように「縮む力しか出せない」性質はありません（伸ばす力も出す）。関節に質量があり、筋肉には質量がありません。水の流れそのものは計算していません。氷の上は、摩擦係数と地面をつかむ力を 0.1 倍にしただけです。
点数: 15秒後の重心の位置（スタートからの前向きの距離、坂では坂に沿った距離）。うしろへ進むとマイナスです。計算がこわれるほど速く動いたものは 0 点にしています。
おもな出どころ
- J. H. Holland（1975）『Adaptation in Natural and Artificial Systems』: 遺伝的アルゴリズム
- K. Sims（1994）「Evolving Virtual Creatures」SIGGRAPH 94: 仮想の生きものの進化
- carykh（Cary Huang）さんの進化シミュレーター: 関節と筋肉の体、種の色分けの見せ方
- 『アストロノーカ』（1998年、PlayStation 用のゲーム）: バブーの進化
- 重力: 地球 9.8 m/s²、月 1.62 m/s²
- 筋肉の強さ・摩擦係数・地面をつかむ力・水の抵抗は、動きが見やすくなるように決めたモデルの値で、本物の生きものを測った値ではありません
使っているもの: 文字に Dela Gothic One・Zen Kaku Gothic New・IBM Plex Mono（SIL Open Font License）。
What is a genetic algorithm?
It is a way of searching for answers by imitating how living things evolve. John Holland shaped the idea in the 1970s. Only four steps are repeated.
① Evaluation Test everyone under the same conditions and give each a score (fitness). Here, the distance traveled in 15 seconds.
② Selection Those with higher scores become parents.
③ Crossover Mix the genes of two parents to make a child.
④ Mutation Change the child’s genes a little, at random.
Nobody teaches them “walk like this”. Even starting from random bodies, some survive and some disappear, and over the generations ways of moving get “discovered”.
The genes of these creatures
The body is made of joints (circles) and muscles (bands). The genes record:
• the number of joints (3–8) and where they start
• how grippy each foot is (friction 0.2–1.2; darker circles grip better and also grab the ground like claws)
• which joints each muscle connects, its contracted and extended lengths, and its strength (shown by thickness)
• the body rhythm (seconds per cycle) and when in each cycle each muscle contracts
The muscles only contract and relax in time with a clock; they don’t sense their surroundings. Even so, gripping the ground with grippy feet and sliding slippery feet forward moves the body ahead. Earthworms and inchworms also move by switching which parts grip, using bristles or suckers.
Some mutations change the number of joints or muscles. Each combination of joint and muscle counts is called a species and gets its own color (up to the 8 most common; the rest are gray).
Different environments, different bodies
Keep the same seed, change only the environment, and run a few dozen generations. On the uphill slope, grippy feet become more common so the creatures don’t slide back down. On ice, pushing against the ground doesn’t transfer much force, but once sliding they are hard to stop, so creatures appear that glide forward like skaters. On the Moon, bouncing and flying far pays off. Underwater there is no ground, so a completely different way of swimming appears, paddling the water with muscle rods.
If you change the environment partway through, the previous champion suddenly can’t get anywhere, and you can watch the population adapt again over several generations (the yellow line on the graph).
How this differs from real evolution
No goal: real evolution has no set score like “get far in 15 seconds”. The traits of whatever survived in that place and left more offspring simply spread as a result.
Chance: in reality, even a strong individual may be unlucky and leave no offspring. The smaller the population, the bigger the effect of chance (genetic drift). This app’s “Tournament” picks opponents by lottery, so it adds a bit of chance.
Amount of genes: human DNA has about 3 billion letters. These creatures’ genes are a few dozen numbers. Also, here the body’s shape is written directly in the genes, while real bodies are built during development, as genes control how cells grow.
History
In 1975, Holland described genetic algorithms in his book Adaptation in Natural and Artificial Systems. In 1994, Karl Sims evolved virtual creatures made of blocks and joints in 3D physics and showed a famous video (Evolving Virtual Creatures) in which swimming, walking and jumping creatures appear.
In the 1998 Japanese video game Astronōka, creatures called “Baboo” that raid your farm got tougher over time, because the ones that got past your traps had the offspring. This app’s joint-and-muscle bodies and its way of coloring species are based on the evolution simulator by carykh (Cary Huang).
How this app works, and what is simplified
Physics: joints are 2 kg points and muscles are damped springs (strength 150–600 N/m). During its contraction time a muscle pulls toward its “contracted length”, and otherwise toward its “extended length”. A joint that hits the ground loses sideways speed in proportion to the downward speed it lost, times its friction (Coulomb friction). On top of that, grippier feet grab the ground the way claws or hooves dig into soil (up to 200 N for the grippiest foot, regardless of how hard it presses). Gravity is 9.8 m/s² on Earth and 1.62 m/s² on the Moon. The calculation runs in steps of 1/120 s.
Underwater: the body weighs the same as water (like a fish with a swim bladder, it neither floats nor sinks). Muscles are treated as rods 6 cm thick; moving across a rod meets drag proportional to speed squared (drag coefficient 1.0), and moving along it meets only a little drag.
What is simplified: it is 2D (forward/back and up/down only), so all body parts lie in one plane and cannot pass through each other. Joints are balls 11 cm across and muscles are rods 6 cm thick; when they hit, they are pushed apart and stop without bouncing, with friction (0.4) when they rub. In a plane, crossed muscles could never untangle, so only bodies with no crossing muscles are born (if a mutation makes one cross, it is redone). When strong muscles push hard, balls and rods may sink into each other a little. Muscles are springs, so unlike real muscles they can push as well as pull. Joints have mass but muscles don’t. The flow of the water itself is not calculated. Ice is simply friction and grip ×0.1.
Score: the position of the center of mass after 15 seconds (forward distance from the start; along the slope on the hill). Going backward gives a negative score. Anything moving so fast that the calculation breaks gets 0.
Main sources
- J. H. Holland (1975), Adaptation in Natural and Artificial Systems: genetic algorithms
- K. Sims (1994), “Evolving Virtual Creatures”, SIGGRAPH 94: evolving virtual creatures
- The evolution simulator by carykh (Cary Huang): joint-and-muscle bodies and the way species are colored
- Astronōka (1998, a PlayStation game, Japan): the evolution of the Baboo
- Gravity: Earth 9.8 m/s², Moon 1.62 m/s²
- Muscle strength, friction, grip and water drag are model values chosen to make the motion easy to see, not measurements of real animals
Fonts: Dela Gothic One, Zen Kaku Gothic New and IBM Plex Mono (SIL Open Font License).