HAPPY NEW YEAR 0x7E6

遺伝的アルゴリズムで…

遺伝的アルゴリズムで… pic.twitter.com/zf2QxTaVWx
— とりてん (@s51517765) 2021年12月31日

遺伝的アルゴリズム(Genetic algorithm)とはプログラミングにおいて、「自然界の遺伝と変異」を応用して最適解を求めるアルゴリズムです。
主な流れは
・初期個体を生成
・優良個体を選抜
・一定の変異をさせながら複製
を繰り返し理想に近い状態を探索します。

一般には解析的に最適解が見つけにくい（見つけられない）問題に対して、ランダムな変異と良い傾向を組み合わせてなるべく良い解を求めることに使われます。
アルゴリズムにはいくつかのパターンがあるようですが、その中でここでは上記のタイプを選択しました。
今回の問題に対してわかりやすく、収束が早そうという理由からです。
この他のオプションとしては個体同士の「交叉」があります。

解説

まず初期個体としてランダムな文字列を生成します。
ここではpoolという配列にTARGETの長さの文字列をN個ランダムに生成します。
ここで使う文字はALFABETO = list(string.ascii_letters+string.digits+"x"+" ")で定義し、大文字のアルファベットと数字とスペースと小文字のxです。
（xは16進数を表すのに使いたいため）

def init():   # 初期個体を生成
    global pool
    for i in range(N):
        tmp = ""
        for j in range(LENGTH):
            tmp += str(random.choice(ALFABETO))
        pool.append(tmp)
    # print(pool)
    return 0

ここでは目指すべき形が一つに定まっています。
TARGET = "HAPPY NEW YEAR 0x7E6"

これに対して「個体」の適応度を以下のように算出します。

def getFitness(pool):  # 適応度
    value = 0
    for i in range(LENGTH):
        if pool[i] == TARGET[i]:
            value += 1
    #print("value", value)
    return value

これによりこの世代の最優良個体を選抜し、文字ごとに一定の割合で変異させます。

def mutate(str):  # 突然変異、文字ごとに変異させる
    tmp = ""
    for i in str:
        if random.random() < MUTATION_RATE:
            tmp += random.choice(ALFABETO)
        else:
            tmp += i
    return tmp

変異させた中から優良個体を選択し、ここまでの流れを繰り返します。

パラメータとしては世代あたりの個体数Nを大きくすると進化が早くなります。
変異率MUTATION_RATEは高くしすぎても今回のケースでは必ずしも良くはなりませんでした。
使える文字は小文字のアルファベットもすべて加えるなど増やせば遅くなります。
これらのパラメータを調整し、だいたい2000世代ぐらいまでで収束するように調整しました。
ただし、ランダム要素があるので早いときは400ぐらいで終わる場合もあります。