1. はじめに

本記事では、プリキュアの名前でしりとりをしたときに登場する最大の人数を遺伝的アルゴリズムで求めていきます。

既に総当りで解を求めた記事が執筆されています。答えは11人のようです。
Q. プリキュア名でしりとりをしたとき、最大で何人登場するか？

2. 対象のプリキュア

「プリキュアの定義」なんて諸説あるテーマには触れたくありませんが・・・

今回は、2023/09/07発売の「プリキュアオールスターズまるごと大図鑑 2023」に登場するプリキュア78人＋「ふたりはプリキュア Splash☆Star」のキュアブライト&キュアウィンディ。

以上80人のプリキュアを対象とします。

先程の総当たりの記事とは対象のプリキュアが異なっていますが（本記事ではキュアエコーは対象外ですが、キュアマジェスティは対象とする）、総当たりで求めた解にキュアエコーは含まれていないため、キュアエコーの有無は最適解に関係ありません。

そのため、総当たりで求めた解と同じ解を遺伝的アルゴリズムで求める or キュアマジェスティを含んだ新たな解を求めることができれば、うまく遺伝的アルゴリズムが機能していると言えそうです。

3. 今回のしりとりのルール

ほとんどのプリキュアは名前が「キュア」から始まるため、普通にしりとりをしようとすると全く繋がりません。

それだと面白くないので、今回は「キュア」から始まるプリキュアは、頭から「キュア」を取り除いた名前でしりとりを行います。

また、名前の最初もしくは最後の文字が濁音、半濁音、半音の場合は清音に変換し、最後の文字が長音の場合は長音の1つ前の文字を最後の文字とします。

例1.「キュアブラック」
最初の文字「フ」（濁音を清音に変換する）
最後の文字「ク」
例2.「キュアフェリーチェ」
最初の文字「フ」
最後の文字「エ」（半音を清音に変換する）
例3.「キュアスター」
最初の文字「ス」
最後の文字「タ」（長音の1つ前の文字を最後の文字とする）

4. 遺伝的アルゴリズムで解く

遺伝的アルゴリズムについては、こちらのスライドが分かりやすいです。
遺伝的アルゴリズム（Genetic Algorithm）を始めよう！

4-1. 個体の定義

個体の遺伝子をプリキュア名とします。そのため個体の染色体はプリキュア名の配列として定義します。
遺伝子のプリキュア名が多く繋がっている（長いしりとりが成立している）染色体を持つ個体ほど、優秀な個体とみなします。

4-2. 遺伝的アルゴリズムの設定

遺伝的アルゴリズムのモデルはMGGモデルを用いました。
遺伝的アルゴリズムにおける世代交代モデルの提案と評価

パラメータ名	値
集団を構成する個体数	10000
交叉回数	100
家族を構成する子の数	200（交叉回数 * 2）
家族を構成する個体数	202（子の数 + 親の数2）
交叉手法	2点交叉
個体の突然変異確率	1%

個体数、交叉回数については、小さい値（個体数=100, 交叉回数=1など）だと解を探すのに時間がかかることが多かったため、適当に個体数=10000, 交叉回数=100としています。

MGGにおける個体数，交叉回数，交叉手法の検討

突然変異の手法は、染色体（プリキュアの配列）からランダムに遺伝子（プリキュア名）を選び、選んだプリキュアとは異なるプリキュアに遺伝子を変化させました。

4-3. 評価関数

遺伝子のプリキュア名が多く繋がっている（長いしりとりが成立している）染色体を持つ個体ほど、優秀な個体であるとするためには、しりとりの成立具合を数値化する必要があります。

数値化に用いる評価関数は、下記のサイトに掲載されていた手法を参考に、
評価関数 = (最長接続数 × 100) + (全ての接続のうち、繋がっている割合 × 100) + 1としました。
9-7. vcoptでポケモンしりとりできるかな

int connect_cnt = 0;
int max_connect_cnt = 0;
int sum_connect_cnt = 0;
vector<bool> is_used(PrecureNum, false);

for(int i = 1; i < pre_array.size(); ++i) {
    Precure prev_pre = pre_array[i - 1];
    Precure crnt_pre = pre_array[i];
    is_used[prev_pre] = true;

    // 言葉が繋がっている かつ 未使用のプリキュア名
    if(prev_pre.isConnect(crnt_pre) && (is_used[crnt_pre] == false)) {
        ++connect_cnt;
    } 
    else {
        if(connect_cnt >= max_connect_cnt) {
            max_connect_cnt = connect_cnt;
        }

        sum_connect_cnt += connect_cnt;
        connect_cnt = 0;
        is_used.clear();
    }
}

// 最も多く単語が繋がってる回数 * 100 + (単語が繋がってる割合 * 100) + 1
int eval = (max_connect_cnt * 100)
           + (100.f * sum_connect_cnt / (pre_array.size() - 1))
           + 1;

+1している理由は、個体の評価値を必ず1以上で生成するためです。
評価対象の個体郡の全ての個体の評価値が0である場合に、うまくルーレット選択を実装する方法が分からなかったため、評価値は1以上で生成するようにしています。

int eval_sum = 0;    // 全ての個体の評価値の合計
for(int i = 0; i < group.size(); ++i) {
    eval_sum += group[i].eval;
}

int select_idx;
int rand_eval = getRandom(1, eval_sum);    // [1, eval_sum]の乱数を生成
int eval_sum_temp = 0;
// ルーレット選択
for(int i = 0; i < group.size(); ++i) {
    eval_sum_temp += group[i].eval;
    if(eval_sum_temp >= rand_eval) {
        select_idx = i;
        break;
    }
}

5. 実装

5-1. PrecureNameクラスの作成

個体の遺伝子となるプリキュア名を表すクラス：PrecureNameクラスを作成します。

プリキュア名が繋がってしりとりになっているかを判別するために、プリキュア名の最初と最後の文字の情報を持たせました。

enum KATAKANA {
    A,I,U,E,O,
    KA,KI,KU,KE,KO,
    SA,SI,SU,SE,SO,
    TA,TI,TU,TE,TO,
    NA,NI,NU,NE,NO,
    HA,HI,HU,HE,HO,
    MA,MI,MU,ME,MO,
    YA,YU,YO,
    RA,RI,RU,RE,RO,
    WA,NN,
    NUM,
};

struct PrecureName {
    PrecureName(string const &name, KATAKANA first_kana, KATAKANA last_kana)
    : m_name(name), m_first_kana(first_kana), m_last_kana(last_kana) { }

    bool isConnect(PrecureName const &pre) const {
        return this->m_last_kana == pre.m_first_kana;
    }

    string m_name;
    KATAKANA m_first_kana;
    KATAKANA m_last_kana;
};

5-2. DataBase_PrecureNameクラスの作成

個体の遺伝子をPrecureNameのオブジェクトとし、染色体をPrecureNameオブジェクトの配列としても良いですが、メモリの節約のために外部にPrecureNameオブジェクトの配列を作成し、その配列への添字を個体の遺伝子とします。

PrecureNameの情報が必要になった時は、遺伝子である配列の添字を通して、外部のPrecureNameオブジェクトの配列から情報を取得します。

外部のPrecureNameオブジェクトの配列をDataBase_PrecureNameクラス、個体の遺伝子に持たせる配列への添字をDataBase_PrecureName::Accessorクラスとしました。

struct DataBase_PrecureName {
    struct Accessor {
        Accessor(size_t accessor = 0)
        : m_accessor(accessor) { }

        PrecureName const& getPrecureName() const {
            return DataBase_PrecureName::c_database_prename[this->m_accessor];
        }

        operator size_t() const {
            return this->m_accessor;
        }

        size_t m_accessor;
    };

    static DataBase_PrecureName::Accessor rand() {
        return getRandom(0, c_database_prename.size() - 1);
    }

    static size_t size() {
        return DataBase_PrecureName::c_database_prename.size();
    }

    static vector<PrecureName> c_database_prename;
};

vector<PrecureName> DataBase_PrecureName::c_database_prename = {
    PrecureName("キュアブラック",     KATAKANA::HU, KATAKANA::KU),
    PrecureName("キュアホワイト",     KATAKANA::HO, KATAKANA::TO),
    PrecureName("シャイニールミナス", KATAKANA::SI, KATAKANA::SU),
    PrecureName("キュアブルーム",     KATAKANA::HU, KATAKANA::MU), 
    PrecureName("キュアイーグレット", KATAKANA::I,  KATAKANA::TO), 
    PrecureName("キュアブライト",     KATAKANA::HU, KATAKANA::TO), 
    PrecureName("キュアウィンディ",   KATAKANA::U,  KATAKANA::I),
    PrecureName("キュアドリーム",     KATAKANA::TO, KATAKANA::MU), 
    PrecureName("キュアルージュ",     KATAKANA::RU, KATAKANA::YU), 
    PrecureName("キュアレモネード",   KATAKANA::RE, KATAKANA::TO), 
    PrecureName("キュアミント",       KATAKANA::MI, KATAKANA::TO), 
    PrecureName("キュアアクア",       KATAKANA::A,  KATAKANA::A), 
    PrecureName("ミルキィローズ",     KATAKANA::MI, KATAKANA::SU),
    PrecureName("キュアピーチ",       KATAKANA::HI, KATAKANA::TI), 
    PrecureName("キュアベリー",       KATAKANA::HE, KATAKANA::RI), 
    PrecureName("キュアパイン",       KATAKANA::HA, KATAKANA::NN), 
    PrecureName("キュアパッション",   KATAKANA::HA, KATAKANA::NN),
    PrecureName("キュアブロッサム",   KATAKANA::HU, KATAKANA::MU), 
    PrecureName("キュアマリン",       KATAKANA::MA, KATAKANA::NN), 
    PrecureName("キュアサンシャイン", KATAKANA::SA, KATAKANA::NN), 
    PrecureName("キュアムーンライト", KATAKANA::MU, KATAKANA::TO),
    PrecureName("キュアメロディ",     KATAKANA::ME, KATAKANA::I), 
    PrecureName("キュアリズム",       KATAKANA::RI, KATAKANA::MU), 
    PrecureName("キュアビート",       KATAKANA::HI, KATAKANA::TO), 
    PrecureName("キュアミューズ",     KATAKANA::MI, KATAKANA::SU),
    PrecureName("キュアハッピー",     KATAKANA::HA, KATAKANA::HI), 
    PrecureName("キュアサニー",       KATAKANA::SA, KATAKANA::NI), 
    PrecureName("キュアピース",       KATAKANA::HI, KATAKANA::SU), 
    PrecureName("キュアマーチ",       KATAKANA::MA, KATAKANA::TI), 
    PrecureName("キュアビューティ",   KATAKANA::HI, KATAKANA::I),
    PrecureName("キュアハート",       KATAKANA::HA, KATAKANA::TO), 
    PrecureName("キュアダイヤモンド", KATAKANA::TA, KATAKANA::TO), 
    PrecureName("キュアロゼッタ",     KATAKANA::RO, KATAKANA::TA), 
    PrecureName("キュアソード",       KATAKANA::SO, KATAKANA::TO), 
    PrecureName("キュアエース",       KATAKANA::E,  KATAKANA::SU),
    PrecureName("キュアラブリー",     KATAKANA::RA, KATAKANA::RI), 
    PrecureName("キュアプリンセス",   KATAKANA::HU, KATAKANA::SU), 
    PrecureName("キュアハニー",       KATAKANA::HA, KATAKANA::NI), 
    PrecureName("キュアフォーチュン", KATAKANA::HU, KATAKANA::NN),
    PrecureName("キュアフローラ",     KATAKANA::HU, KATAKANA::RA), 
    PrecureName("キュアマーメイド",   KATAKANA::MA, KATAKANA::TO), 
    PrecureName("キュアトゥインクル", KATAKANA::TO, KATAKANA::RU), 
    PrecureName("キュアスカーレット", KATAKANA::SU, KATAKANA::TO),
    PrecureName("キュアミラクル",     KATAKANA::MI, KATAKANA::RU), 
    PrecureName("キュアマジカル",     KATAKANA::MA, KATAKANA::RU), 
    PrecureName("キュアフェリーチェ", KATAKANA::HU, KATAKANA::E),
    PrecureName("キュアホイップ",     KATAKANA::HO, KATAKANA::HU), 
    PrecureName("キュアカスタード",   KATAKANA::KA, KATAKANA::TO), 
    PrecureName("キュアジェラート",   KATAKANA::SI, KATAKANA::TO), 
    PrecureName("キュアマカロン",     KATAKANA::MA, KATAKANA::NN), 
    PrecureName("キュアショコラ",     KATAKANA::SI, KATAKANA::RA), 
    PrecureName("キュアパルフェ",     KATAKANA::HA, KATAKANA::E),
    PrecureName("キュアエール",       KATAKANA::E,  KATAKANA::RU), 
    PrecureName("キュアアンジュ",     KATAKANA::A,  KATAKANA::YU), 
    PrecureName("キュアエトワール",   KATAKANA::E,  KATAKANA::RU), 
    PrecureName("キュアマシェリ",     KATAKANA::MA, KATAKANA::RI), 
    PrecureName("キュアアムール",     KATAKANA::A,  KATAKANA::RU),
    PrecureName("キュアスター",       KATAKANA::SU, KATAKANA::TA), 
    PrecureName("キュアミルキー",     KATAKANA::MI, KATAKANA::KI), 
    PrecureName("キュアソレイユ",     KATAKANA::SO, KATAKANA::YU), 
    PrecureName("キュアセレーネ",     KATAKANA::SE, KATAKANA::NE), 
    PrecureName("キュアコスモ",       KATAKANA::KO, KATAKANA::MO),
    PrecureName("キュアグレース",     KATAKANA::KU, KATAKANA::SU), 
    PrecureName("キュアフォンテーヌ", KATAKANA::HU, KATAKANA::NU), 
    PrecureName("キュアスパークル",   KATAKANA::SU, KATAKANA::RU), 
    PrecureName("キュアアース",       KATAKANA::A,  KATAKANA::SU),
    PrecureName("キュアサマー",       KATAKANA::SA, KATAKANA::MA), 
    PrecureName("キュアコーラル",     KATAKANA::KO, KATAKANA::RU), 
    PrecureName("キュアパパイア",     KATAKANA::HA, KATAKANA::A), 
    PrecureName("キュアフラミンゴ",   KATAKANA::HU, KATAKANA::KO), 
    PrecureName("キュアラメール",     KATAKANA::RA, KATAKANA::RU),
    PrecureName("キュアプレシャス",   KATAKANA::HU, KATAKANA::SU), 
    PrecureName("キュアスパイシー",   KATAKANA::SU, KATAKANA::SI), 
    PrecureName("キュアヤムヤム",     KATAKANA::YA, KATAKANA::MU), 
    PrecureName("キュアフィナーレ",   KATAKANA::HU, KATAKANA::RE),
    PrecureName("キュアスカイ",       KATAKANA::SU, KATAKANA::I), 
    PrecureName("キュアプリズム",     KATAKANA::HU, KATAKANA::MU),
    PrecureName("キュアウィング",     KATAKANA::U,  KATAKANA::KU), 
    PrecureName("キュアバタフライ",   KATAKANA::HA, KATAKANA::I), 
    PrecureName("キュアマジェスティ", KATAKANA::MA, KATAKANA::I),
};

5-3. GA::Configの作成

遺伝的アルゴリズムの設定をGA::Configにまとめます。

namespace GA {
    namespace Config {
        int const group_size = 10000;
        int const crossover_cnt = 100;
        int const child_size = crossover_cnt * 2;
        int const family_size = child_size + 2;
        int const mutate_percent = 1;
    }
}

5-4. GA::Individualクラスの作成

個体を表すクラス：Individualクラスを作成します。
m_connect_cnt、m_connect_first_idx、m_connect_last_idxは結果を出力するときに使用する変数です。

m_connect_cnt=個体の染色体のうち、最も長くしりとりが繋がっている長さ
m_connect_first_idx=最も長く繋がっているしりとり部分の開始位置
m_connect_last_idx=最も長く繋がっているしりとり部分の終了位置

namespace GA {
    struct Individual {
        Individual()
        : m_pre_array(DataBase_PrecureName::size()), m_eval(0), m_connect_cnt(0), 
          m_connect_first_idx(0), m_connect_last_idx(0) {
            vector<bool> is_used(DataBase_PrecureName::size(), false);
            // すべてのプリキュアが重複せずに登場するように初期化する
            for(auto &ref_pre : this->m_pre_array) {
                DataBase_PrecureName::Accessor rand_pre;
                do {
                    rand_pre = DataBase_PrecureName::rand();
                } while(is_used[rand_pre]);
                is_used[rand_pre] = true;
                ref_pre = rand_pre;
            }
    
            this->evaluate();
        }
    
        static size_t randPrecureArrayIndex() {
            return getRandom(0, DataBase_PrecureName::size() - 1);
        }
    
        void evaluate() {
            int connect_cnt = 0;
            int max_connect_cnt = 0;
            int sum_connect_cnt = 0;
            size_t first_idx, last_idx;
            vector<bool> is_used(DataBase_PrecureName::size(), false);
    
            first_idx = 0;
            for(size_t i = 1; i < this->m_pre_array.size(); ++i) {
                DataBase_PrecureName::Accessor const &prev_pre = this->m_pre_array[i - 1];
                DataBase_PrecureName::Accessor const &crnt_pre = this->m_pre_array[i];
                is_used[prev_pre] = true;
    
                if(prev_pre.getPrecureName().isConnect(crnt_pre.getPrecureName()) && (is_used[crnt_pre] == false)) {
                    ++connect_cnt;
                } else {
                    last_idx = i - 1;
                    if(connect_cnt >= max_connect_cnt) {
                        max_connect_cnt = connect_cnt;
                        // 最も多く単語が繋がっている部分列を出力させる
                        this->m_connect_first_idx = first_idx;
                        this->m_connect_last_idx = last_idx;
                    }
    
                    first_idx = i;
                    sum_connect_cnt += connect_cnt;
                    connect_cnt = 0;
                    is_used.clear();
                }
            }
    
            this->m_connect_cnt = max_connect_cnt;
            // 最も多く単語が繋がってる回数 * 100 + (単語が繋がってる割合 * 100)
            this->m_eval = (max_connect_cnt * 100)
                         + (100.f * sum_connect_cnt / (this->m_pre_array.size() - 1))
                         + 1;
        }
    
        void mutate() {
            // どこか1つをランダムなプリキュアに変化させる
            int rand_per = getRandom(1, 100);
            if(rand_per <= GAConfig::mutate_percent) {
                size_t rand_idx = randPrecureArrayIndex();
                DataBase_PrecureName::Accessor rand_pre;
                do {
                    rand_pre = DataBase_PrecureName::rand();
                } while(rand_pre == this->m_pre_array[rand_idx]);
                this->m_pre_array[rand_idx] = rand_pre;
            }
        }
    
        vector<DataBase_PrecureName::Accessor> m_pre_array;
        int m_eval;
        int m_connect_cnt;
        size_t m_connect_first_idx, m_connect_last_idx;
    };
}

5-5. GAの関数の作成

namespace GA {
    // 集団からランダムに親を2体選ぶ
    void selectParent(vector<GA::Individual> &group, vector<GA::Individual*> *p_set_parent) {
        int parent_idx1 = getRandom(0, group.size() - 1);
        int parent_idx2;
        do {
            parent_idx2 = getRandom(0, group.size() - 1);
        } while(parent_idx1 == parent_idx2);

        (*p_set_parent)[0] = &group[parent_idx1];
        (*p_set_parent)[1] = &group[parent_idx2];
    }

    // 親から子を生成する
    void crossover(vector<GA::Individual*> &parent, vector<GA::Individual> *p_set_child) {
        size_t pre_array_size = parent[0]->m_pre_array.size();
        vector<vector<bool>> is_used(pre_array_size, vector<bool>(pre_array_size, false));

        for(size_t i = 0; i < GA::Config::crossover_cnt; ++i) {
            // 同じ遺伝子を持つ子が複数体生まれないように全て異なる交叉点で交叉させる
            size_t first_idx, last_idx;
            do {
                first_idx = Individual::randPrecureArrayIndex();
                last_idx = Individual::randPrecureArrayIndex();
                if(first_idx > last_idx) {
                    swap(first_idx, last_idx);
                }
            } while(is_used[first_idx][last_idx]);
            is_used[first_idx][last_idx] = true;

            Individual *p_set_child1 = &((*p_set_child)[i * 2]);
            Individual *p_set_child2 = &((*p_set_child)[(i * 2) + 1]);

            for(size_t k = 0; k < pre_array_size; ++k) {
                if((first_idx <= k) && (k <= last_idx)) {
                    p_set_child1->m_pre_array[k] = parent[1]->m_pre_array[k];
                    p_set_child2->m_pre_array[k] = parent[0]->m_pre_array[k];
                } 
                else {
                    p_set_child1->m_pre_array[k] = parent[0]->m_pre_array[k];
                    p_set_child2->m_pre_array[k] = parent[1]->m_pre_array[k];
                }
            }

            p_set_child1->mutate();
            p_set_child2->mutate();
        }
    }

    // 親と子を家族に登録する
    void createFamily(vector<GA::Individual*> *p_set_family, vector<GA::Individual*> &parent, vector<GA::Individual> &child) {
        (*p_set_family)[0] = parent[0];
        (*p_set_family)[1] = parent[1];
        for(size_t i = 0; i < child.size(); ++i) {
            (*p_set_family)[2 + i] = &child[i];
        }
    }

    // 家族の中から次の世代に残す個体を2体選ぶ
    void selectNextIndividualFromFamily(vector<GA::Individual*> &family, vector<GA::Individual*> *p_set_next_indv) {
        using size_t = vector<GA::Individual*>::size_type;
        for(size_t i = 0; i < family.size(); ++i) {
            family[i]->evaluate();
        }

        int max_eval = 0;
        size_t max_eval_indv_idx = 0;
        for(size_t i = 0; i < family.size(); ++i) {
            if(family[i]->m_eval > max_eval) {
                max_eval = family[i]->m_eval;
                max_eval_indv_idx = i;
            }
        }

        size_t elite_select_idx = max_eval_indv_idx;

        int eval_sum = 0;
        for(size_t i = 0; i < family.size(); ++i) {
            if(i == elite_select_idx) {
                continue;
            }

            eval_sum += family[i]->m_eval;
        }

        size_t roulette_select_idx;
        int rand_eval = getRandom(1, eval_sum);
        int eval_sum_temp = 0;
        for(size_t i = 0; i < family.size(); ++i) {
            if(i == elite_select_idx) {
                continue;
            }

            eval_sum_temp += family[i]->m_eval;
            if(eval_sum_temp >= rand_eval) {
                roulette_select_idx = i;
                break;
            }
        }

        if(elite_select_idx > roulette_select_idx) {
            swap(elite_select_idx, roulette_select_idx);
        }

        (*p_set_next_indv)[0] = family[elite_select_idx];
        (*p_set_next_indv)[1] = family[roulette_select_idx];
    }
}

5-6. メイン関数の作成

遺伝的アルゴリズムを実行し、集団の中でしりとりが繋がっている回数の最大値が更新されたタイミングで結果を出力します。

int main(void) {
    // GA用変数
    vector<GA::Individual> group(GA::Config::group_size);
    vector<GA::Individual*> parent(2);
    vector<GA::Individual> child(GA::Config::child_size);
    vector<GA::Individual*> family(GA::Config::family_size);
    vector<GA::Individual*> next_indv(2);

    // 結果出力用変数
    // しりとりが繋がっている長さがこの値に達した個体が現れたら結果を出力する
    int output_connect_cnt = 2;
    int gen_cnt = 1;
    int sum_connect_cnt, max_connect_cnt, ave_connect_cnt;
    clock_t ga_start_clock = clock(), ga_crnt_clock, erapsed_sec;

    // GA初期設定出力
    cerr << endl << "[GA_Config]" << endl;
    cerr << "Group_Size = " << GA::Config::group_size << endl;
    cerr << "Family_Size = " << GA::Config::family_size << endl << endl;

    while(1) {
        // 結果出力用 s
        ga_crnt_clock = clock();
        erapsed_sec = (0.5f + (ga_crnt_clock - ga_start_clock)) / CLOCKS_PER_SEC;

        // 集団の個体の中で、しりとりが最も長く繋がっている回数と回数の平均値を求める
        sum_connect_cnt = 0;
        max_connect_cnt = 0;
        for(auto const &indv : group) {
            sum_connect_cnt += indv.m_connect_cnt;
            max_connect_cnt = max(max_connect_cnt, indv.m_connect_cnt);
        }
        ave_connect_cnt = 1.f * sum_connect_cnt / group.size();

        cout << fixed << setprecision(3)
             << "Gen "  << gen_cnt
             << " Max " << max_connect_cnt
             << " Ave " << ave_connect_cnt
             << " Sec " << erapsed_sec
             << endl;

        // 集団の中でしりとりが繋がっている回数の最大値が更新されたら結果を出力する
        if(max_connect_cnt >= output_connect_cnt) {
            clock_t end_clock = clock();

            cerr << "[Connect = " << max_connect_cnt 
                 << ", Gen = " << gen_cnt 
                 << ", Sec = " << erapsed_sec 
                 << "]" << endl;

            for(auto const &indv : group) {
                if(indv.m_connect_cnt == max_connect_cnt) {
                    for(size_t i = indv.m_connect_first_idx; i <= indv.m_connect_last_idx; ++i) {
                        DataBase_PrecureName::Accessor const &pre = indv.m_pre_array[i];
                        cerr << pre.getPrecureName().m_name << " ";
                    }
                    cerr << endl;
                }
            }
            output_connect_cnt = max_connect_cnt + 1;
        }
        // 結果出力用 e

        GA::selectParent(group, &parent);
        GA::crossover(parent, &child);
        GA::createFamily(&family, parent, child);
        GA::selectNextIndividualFromFamily(family, &next_indv);

        // 次の世代に残す個体を集団に戻す
        *(parent[0]) = *(next_indv[0]);
        *(parent[1]) = *(next_indv[1]);

        ++gen_cnt;
    }

    return 0;
}

6. 結果

何回か動かしてみたところ、しりとりが繋がっている長さ = 10、つまり11人が繋がった下記の結果を得ることが出来ました。

キュアホイップ キュアフェリーチェ キュアエース キュアスパイシー シャイニールミナス キュアスカイ キュアイーグレット キュアドリーム キュアムーンライト キュアトゥインクル キュアルージュ 

キュアパパイア キュアアクア キュアアース キュアスパイシー シャイニールミナス キュアスカイ キュアイーグレット キュアドリーム キュアムーンライト キュアトゥインクル キュアルージュ 

キュアホイップ キュアブラック キュアグレース キュアスパイシー シャイニールミナス キュアスター キュアダイヤモンド キュアドリーム キュアムーンライト キュアトゥインクル キュアルージュ

今回の試行では、キュアマジェスティを含んだ新たな解は発見することが出来ませんでしたが、総当たりの解と同じ結果を得ることが出来たので、遺伝的アルゴリズムはうまく機能していると言えそうです。

いずれの結果もキュアルージュで終わっているのは、ルから始まるプリキュアがキュアルージュしかおらず、ユから始まるプリキュアがいないためです。

ここからさらにしりとりを繋げるためには、例えばユから始まるプリキュアが登場すれば、キュアルージュ→キュアユ〇→・・・と繋がっていきますね。

また、3つの結果を見ると、1人目のプリキュアからキュアスパイシーに至るまでに登場するプリキュアが異なるため、スで始まりハで終わるプリキュアが登場すれば、キュアホイップ→キュアフェリーチェ→キュアエース→キュアス〇〇ハ→キュアパパイア→キュアアクア→キュアアース→キュアスパイシー→・・・は確定で繋がります。

7. 番外編

スで始まりハで終わるプリキュアとして、「キュアスリッパ」というオリジナルプリキュアを登場させた時、本当に繋がるのかを検証しました。

結果、キュアスリッパの後にキュアパパイアキュアアクアキュアアースが繋がり、15人のプリキュアが登場するしりとりを求めることが出来ました。

キュアホイップ キュアフェリーチェ キュアエース キュアスリッパ キュアパパイア キュアアクア キュアアース キュアスパイシー シャイニールミナス キュアスカイ キュアイーグレット キュアドリーム キュアムーンライト キュアトゥインクル キュアルージュ 

キュアホイップ キュアフェリーチェ キュアエース キュアスパイシー シャイニールミナス キュアスリッパ キュアパパイア キュアアクア キュアアース キュアスター キュアダイヤモンド キュアドリーム キュアムーンライト キュアトゥインクル キュアルージュ

8. 参考文献

Q. プリキュア名でしりとりをしたとき、最大で何人登場するか？
遺伝的アルゴリズムにおける世代交代モデルの提案と評価
 MGGにおける個体数，交叉回数，交叉手法の検討
 9-7. vcoptでポケモンしりとりできるかな