初めての焼きなまし法やってみた

TL;DR

pythonのsimannealパッケージを使うと一瞬で実装できるます．
作ってくれた人ありがとうます．

背景

ラボメンに，遺伝子パーツの選択の相談をされた．
30種くらいの遺伝子パーツの中から，10個くらい良さげなペアを選んでほしいとのこと．
各々の遺伝子パーツは，入力分子とそれに応答する素子で構成される．応答素子は対応する入力分子以外にも応答する可能性があるため，この応答交差性を最小限にするようなパーツの組み合わせを選択したいという問題になる．
選択基準としては，遺伝子パーツ間の距離が定義されていて，選択したものの間の距離の最小値を最大にするというタスクになりそう．
ここcs.stackexchange.com
に同じような相談があったのでそれを参考にした．
DPでできるかなとも思ったが，よくわからなかったDPの更新式がめんどくさそうのでとりあえずDPはやめた．（できた人はおしえてください．）（1つメンバーを変えると，それ以外のメンバーの間の距離も変わってしまうため，DPには向かないタスクと思われた．）
全探索したらどうなるのか軽く概算したところ10^8 ~ 10^9くらいの計算量になるっぽい．
とりあえず近似解で良いかなと思い，焼きなまし法を選択することにした．

やったこと

pythonのsinannealパッケージがどうやら便利とのことなのでそれで実装した．確かにすごい便利．
バージョンとか書くべきなんだろうけど，とりあえずsimanneal-0.5.0使いました．
Annealerクラスを継承して，energyとmoveを書いてやればおしまい．
一部詳細を省いているが，以下のような感じになった．超便利．
やはり，subsetの組み合わせを計算しなければいけないので，結構時間が掛かる．
何回かtrialを重ねて最も良いsubsetを選択するような形でなんとか行けた．

from simanneal import Annealer
import random
from scipy.spatial import distance

class FindSubsetProblem(Annealer):
    def __init__(self, data, state):
        super(FindSubsetProblem, self).__init__(state)
        self.state = state
        self.data = data
        self.state_data = hogehoge # dataからstateに属するsubsetの選択. 

    def pair_energy(self, g1, g2):
        return # subsetを選択したときの, g1-g2距離の定義.
    
    def energy(self):
        min_dist = float("inf")
        for i in range(len(self.state)):
            for j in range(len(self.state)):
                if i > j:
                    d = self.pair_energy(self.state[i], self.state[j])
                    if d < min_dist:
                        min_dist = d
        return min_dist

    def move(self):
        E_pre = self.energy()
        rm_i = random.randint(0, len(self.state)-1)
        add_gene = random.choice(list(set(self.data.index) - set(self.state)))
        self.state[rm_i] = add_gene
        self.state_data = hogehoge # initでも書いているが, ここで改めて記述しないと更新されない仕様になっている. 
        E_post = self.energy()
        return E_pre - E_post

if __name__ == "__main__":
    import argparse
    parser = argparse.ArgumentParser()
    parser.add_argument('--input', '-i')    # 必須の引数を追加
    parser.add_argument('--n_members', '-n', default = 13, type = int)    # 必須の引数を追加
    parser.add_argument('--steps', type = int)    # 必須の引数を追加
    parser.add_argument('--random_seed', default = 42, type = int)    # 必須の引数を追加
    args = parser.parse_args()

    random.seed(args.random_seed)

    fsp = FindSubsetProblem(df, init_state)
    fsp.steps = args.steps
    fsp.copy_strategy = "slice"
    state, e = fsp.anneal()
    print("Selected members", state)
    f = FindSubsetProblem(df, state)
    print("Minimum distance", f.energy())

結語

pythonのsimannealパッケージ，神．