C++练习项目：演化模拟之Weasel程序的实现

介绍

该程序实现了道金斯（Dawkins）在《The Blind Watchmaker》一书中提到的演化过程，这个过程展示了自然选择的过程。程序中使用了莎士比亚（Shakespere）的短语“ METHINKS IT IS LIKE A WEASEL”。

实现

#include <string>
#include <random>
#include <array>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <sstream>

class Weasel
{
    std::string target;
    std::uniform_int_distribution<> chardist;
    std::uniform_int_distribution<> ratedist;
    std::mt19937 mt;
    std::string const allowed_chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";

public:
    Weasel(std::string_view t) : target(t), chardist(0, 26), ratedist(0, 100)
    {
        std::random_device rd;
        auto seed_data = std::array<int, std::mt19937::state_size>{};
        std::generate(std::begin(seed_data), std::end(seed_data), std::ref(rd));
        std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
        mt.seed(seq);
    }

    void run(int const copies)
    {
        auto parent = make_random();
        int step = 1;
        std::cout << std::left << std::setw(5) << std::setfill(' ')
                  << step << parent << std::endl;

        do
        {
            std::vector<std::string> children;
            std::generate_n(std::back_inserter(children), copies,
                            [parent, this]() {
                                return mutate(parent, 5);
                            });
            parent = *std::max_element(
                std::begin(children), std::end(children),
                [this](std::string_view c1, std::string_view c2) {
                    return fitness(c1) < fitness(c2);
                });
            std::cout << std::left << std::setw(5) << std::setfill(' ')
                      << step << parent << std::endl;
            ++step;
        } while (parent != target);
    }

private:
    Weasel() = delete;

    double fitness(std::string_view candidate) const
    {
        int score = 0;
        for (size_t i = 0; i < candidate.size(); ++i)
        {
            if (candidate[i] == target[i])
            {
                ++score;
            }
        }
        return score;
    }

    std::string mutate(std::string_view parent, double const rate)
    {
        std::stringstream sstr;
        for (auto const c : parent)
        {
            auto nc = ratedist(mt) > rate ? c : allowed_chars[chardist(mt)];
            sstr << nc;
        }
        return sstr.str();
    }

    std::string make_random()
    {
        std::stringstream sstr;
        for (size_t i = 0; i < target.size(); ++i)
        {
            sstr << allowed_chars[chardist(mt)];
        }
        return sstr.str();
    }
};

int main()
{
    Weasel w("METHINKS IT IS LIKE A WEASEL");
    w.run(100);

    return 0;
}

效果

从一个随机字符串出发，每次复制的时候随机出错，不断淘汰，最终就可以得到我们想要的字符串。

    MEQBJU KAGPAVVIGK ECK MJSGUI
1    MEQBJU KAGPAVVIGK ECK MESGUT
2    MEQBJU KAGPAVVIGI ECK MESGUX
3    MEQBJU KAGPAVVIGIKECK MESGUX
4    METBJU KAGPAVVIGIKECK MESGUN
5    METBJU KADPAVVTLIKECW MESGUN
6    METIJUGKAKPAVVTLIKECW MESGUN
...
14   METBDUIKAIP IVTLIKECW MEASUL
15   METBDUIKAIP IVTLIKEPA MEASUL
16   METBDUIK IP IVTLIKEPA MEASUL
17   METBDUIK IP IVTLIKEPA MEASUL
18   METBDNIZ IP IVTLIKEPA MEASUL
19   METBDNIZ IP IVTLIKEPA MEASUL
...
44   METHINKS IT ISGLIKE A WEASEL
45   METHINKS IT ISGLIKE A WEASEL
46   METHINKS IT ISGLIKE A WEASEL
47   METHINKS IT ISGLIKE A WEASEL
48   METHINKS IT IS LIKE A WEASEL