Gene.cpp

#include <algorithm>
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <iterator>
#include <random>
#include <fstream>
#include <bitset>

using uint32 = std::uint32_t;
using int32 = std::int32_t;

namespace MyUtil {
    namespace Private {
        std::random_device rd;
        std::mt19937 mt(rd());
    }  // namespace Private

    [[nodiscard]] bool RandomBool(double p_ = 0.5) noexcept {
        std::bernoulli_distribution getBool(p_);
        return getBool(Private::mt);
    }

    [[nodiscard]] uint32 RandomUint32(const uint32 min_, const uint32 max_) noexcept {
        std::uniform_int_distribution<uint32> getNum(min_, max_);
        return getNum(Private::mt);
    }

    /// <summary>
    /// 重さの最大値
    /// これを超える重さになる場合、価値を0にする
    /// </summary>
    constexpr uint32 weightMax = 744;

    /// <summary>
    /// 世代数
    /// </summary>
    constexpr uint32 generation = 1000;

    /// <summary>
    /// グラフの数
    /// </summary>
    constexpr uint32 graph = 50;

    /// <summary>
    /// 遺伝子座の数（一人につき30個）
    /// </summary>
    constexpr uint32 locus = 30;

    /// <summary>
    /// 選べる親の数
    /// </summary>
    constexpr uint32 parentsChoose = 100;

    /// <summary>
    ///	エリート戦略で残す親の数
    /// </summary>
    constexpr uint32 parentsClone = 2;

    /// <summary>
    ///	評価値の最大値を格納するための定数
    /// </summary>
    constexpr uint32 maxEvaluationValue = std::max<uint32>(parentsClone, 1);

    /// <summary>
    ///	突然変異する割合
    /// </summary>
    constexpr double mutationRate = 0.01;

    std::array<std::array<uint32, 2>, 30> valueList;
}  // namespace MyUtil

/// <summary>
/// 遺伝子のクラス
/// 評価値、重さ、遺伝子座を持っている
/// </summary>
class Gene {
private:
    /// <summary>
    /// 遺伝子座
    /// </summary>
    std::bitset<MyUtil::locus> m_serects;

    /// <summary>
    /// 評価値
    /// </summary>
    uint32 m_value;

    /// <summary>
    /// 重さ
    /// </summary>
    uint32 m_weight;

public:
    /// <summary>
    /// コンストラクタ
    /// </summary>
    Gene() noexcept : m_value(0), m_weight(0) {
        for (uint32 i{}; i < MyUtil::locus; ++i) {
            m_serects.set(i, MyUtil::RandomBool());
        }

        Calculate();
    }

    /// <summary>
    /// Copulateメソッドで呼び出される
    /// </summary>
    Gene(const std::bitset<MyUtil::locus>& locus_) noexcept : m_value(0), m_weight(0) {
        for (uint32 i{}; i < MyUtil::locus; ++i) {
            if (MyUtil::RandomBool(MyUtil::mutationRate)) {
                m_serects.set(i, !locus_.test(i));
                continue;
            }

            m_serects.set(i, locus_.test(i));
        }

        Calculate();
    }

    /// <summary>
    /// 遺伝子座の評価値と重さの合計値の計算
    /// </summary>
    void Calculate() {
        m_value = 0, m_weight = 0;

        for (uint32 i{}; i < MyUtil::locus; ++i) {
            if (!m_serects.test(i)) {
                continue;
            }
            m_value += MyUtil::valueList[i][0];
            m_weight += MyUtil::valueList[i][1];
        }

        /// <summary>
        /// m_weightがweightMaxを超えた場合、
        /// 評価値を0にする
        /// </summary>
        if (m_weight > MyUtil::weightMax) {
            m_value = 0;
        }
    }

    [[nodiscard]] uint32 GetValue() const noexcept {
        return m_value;
    }

    [[nodiscard]] bool IsUseLocus(const uint32 i_) const noexcept {
        return m_serects.test(i_);
    }

    bool operator<(const Gene& right_) const {
        return m_value < right_.GetValue();
    }

    bool operator==(const Gene& right_) const {
        return ((m_value == right_.m_value) && (m_weight == right_.m_weight) && (m_serects == right_.m_serects));
    }
};

class People {
private:
    /// <summary>
    /// 親たち
    /// </summary>
    std::vector<Gene> m_parents;

    /// <summary>
    /// 子供たち
    /// </summary>
    std::vector<Gene> m_children;

    /// <summary>
    /// 優秀な親たち
    /// </summary>
    std::vector<Gene> m_excellentParents;

    /// <summary>
    /// 親世代の遺伝子の合計評価値を計算する
    /// </summary>
    /// <returns>合計評価値</returns>
    uint32 SumValue() {
        uint32 sum{};

        for (const auto& human : m_parents) {
            sum += human.GetValue();
        }

        return sum;
    }

    /// <summary>
    /// 親世代から親を一人選ぶ
    /// </summary>
    /// <returns>親</returns>
    Gene SerectParent() {
        int32 randomNum{static_cast<int32>(MyUtil::RandomUint32(0, SumValue()))};
        for (const auto& human : m_parents) {
            randomNum -= human.GetValue();
            if (0 < randomNum) {
                continue;
            }

            return human;
        }

        return m_parents.back();
    }

public:
    People() noexcept : m_parents(MyUtil::parentsChoose, Gene()), m_children(MyUtil::parentsChoose, Gene()), m_excellentParents(MyUtil::parentsClone) {
        for (uint32 i{}; i < MyUtil::parentsClone; ++i) {
            auto& itr = *std::max_element(m_children.begin(), m_children.end());
            m_excellentParents[i] = itr;
            m_children.erase(std::remove(m_children.begin(), m_children.end(), itr), m_children.end());
        }
    }

    People& Copulate() {
        /// <summary>
        /// 優秀な親世代の人たちを数人子供達にクローンする
        /// </summary>
        m_children.assign(m_excellentParents.begin(), m_excellentParents.end());

        for (uint32 i{MyUtil::parentsClone}; i < MyUtil::parentsChoose; i += 2) {
            std::bitset<MyUtil::locus> child_1, child_2;
            Gene father{SerectParent()};
            Gene mother{SerectParent()};

            uint32 separate{MyUtil::RandomUint32(0, MyUtil::locus - 1)};

            for (uint32 j{}; j < separate; ++j) {
                child_1.set(j, father.IsUseLocus(j));
                child_2.set(j, mother.IsUseLocus(j));
            }
            for (uint32 j{separate}; j < MyUtil::locus; ++j) {
                child_1.set(j, mother.IsUseLocus(j));
                child_1.set(j, father.IsUseLocus(j));
            }

            m_children.emplace_back(child_1);
            m_children.emplace_back(child_2);
        }
        return *this;
    }

    /// <summary>
    /// 子世代を親世代にする
    /// </summary>
    People& ChangeGeneration() {
        m_parents = m_children;

        for (uint32 i{}; i < MyUtil::parentsClone; ++i) {
            auto& itr = *std::max_element(m_children.begin(), m_children.end());
            m_excellentParents[i] = itr;
            m_children.erase(std::remove(m_children.begin(), m_children.end(), itr), m_children.end());
        }

        return *this;
    }

    void OutputMaxValue(const uint32 count_, const uint32 numGra_, std::vector<std::vector<uint32>>& yData_) {
        /// <summary>
        /// 評価値の最大値を出力する
        /// </summary>
        std::cout << count_ + 1 << "回目:" << m_excellentParents.front().GetValue() << "\t";

        yData_[count_][numGra_] = m_excellentParents.front().GetValue();
    }

    void Answer() {
        std::cout << "\n" << std::endl;
        std::cout << "親世代の遺伝子座は、" << std::endl;
        for (auto& parent : m_parents) {
            std::cout << parent.GetValue() << " ";
        }
        std::cout << "です。" << std::endl;
        std::cout << std::endl;
    }
};

/// <summary>
/// データを挿入する
/// </summary>
void DataInit() {
    for (uint32 y{}; y < MyUtil::locus; ++y) {
        for (uint32 x{}; x < 2; ++x) {
            std::cin >> MyUtil::valueList[y][x];
        }
    }
}

/// <summary>
/// 各世代の評価値の平均を作成する
/// </summary>
void CreateAverageData(const std::vector<std::vector<uint32>>& data_, std::vector<double>& averages_) {
    /// <summary>
    /// 各世代の合計値
    /// </summary>
    double sum{};
    for (int y = 0; y < MyUtil::generation; ++y) {
        sum = 0;
        for (int x = 0; x < MyUtil::graph; ++x) {
            sum += data_[y][x];
        }
        /// <summary>
        /// 評価値の平均をとる
        /// </summary>
        sum /= MyUtil::graph;

        /// <summary>
        /// 評価値の平均をaverages_に格納する
        /// </summary>
        averages_.emplace_back(sum);

        std::cout << y + 1 << "世代：" << averages_[y] << "\t";
    }
    std::cout << std::endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);

    DataInit();

    /// <summary>
    /// gnuplotに書き出すための作業
    /// </summary>
    std::ofstream fout("gene1.dat");

    std::vector<std::vector<uint32>> yData(MyUtil::generation, std::vector<uint32>(MyUtil::graph));

    /// <summary>
    /// 各世代毎の平均を格納する
    /// </summary>
    std::vector<double> yAve;

    for (uint32 gra{}; gra < MyUtil::graph; ++gra) {
        People people;

        for (uint32 count{}; count < MyUtil::generation; ++count) {
            people.Copulate().ChangeGeneration().OutputMaxValue(count, gra, yData);
        }

        people.Answer();
    }

    CreateAverageData(yData, yAve);

    std::cout << "平均の最大値は : " << *std::max_element(yAve.begin(), yAve.end()) << std::endl;

    /// <summary>
    /// gene.datに各世代の平均値を出力する
    /// </summary>
    for (int i = 0; i < MyUtil::generation; ++i) {
        fout << i + 1 << " " << yAve[i] << std::endl;
    }
}