クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Optunaでヒューリスティックコンテストを解く

この記事は競プロ Advent Calendar 2021 14日目の記事です。

こんにちは、クルトンです!

この記事ではヒューリスティックコンテストにOptunaを活用する方法について解説しています。

Optunaとは

Optunaは公式サイトで以下のように説明されています。

Optuna はハイパーパラメータの最適化を自動化するためのソフトウェアフレームワークです。ハイパーパラメータの値に関する試行錯誤を自動的に行いながら、優れた性能を発揮するハイパーパラメータの値を自動的に発見します。現在は Python で利用できます。

Optuna は次の試行で試すべきハイパーパラメータの値を決めるために、完了している試行の履歴を用いています。そこまでで完了している試行の履歴に基づき、有望そうな領域を推定し、その領域の値を実際に試すということを繰り返します。そして、新たに得られた結果に基づき、更に有望そうな領域を推定します。具体的には、Tree-structured Parzen Estimator というベイズ最適化アルゴリズムの一種を用いています。

ハイパーパラメータ自動最適化ツール「Optuna」公開

「良い感じのハイパーパラメーターを見つけてくれるPythonのライブラリ」という理解で大丈夫です。

具体的な使い方

簡単な使用例を見てみましょう。

Optunaでf(x)=(x-2)^2を最小化するxを調べてみます。

import optuna

# 最小化する目的関数
def objective(trial):
    # パラメータ
    x = trial.suggest_uniform('x', -10, 10)
    score = (x - 2) ** 2
    # 最小化したい値を戻り値にする
    return score

# Studyを作成
study = optuna.create_study()

# 目的関数をStudyに渡す
study.optimize(objective, n_trials=100)

# 実験で得られた最良のパラメーター
print(study.best_params)

# 実験で得られた最良の目的関数の値
print(study.best_value)


何をしているのかはコメントに書いてある通りなんですが、一応流れを書いておくと

  1. 最小化(または最大化)したいスコアを返り値とする目的関数を定義する
  2. optuna.studyインスタンスを作成する
  3. optuna.study.optimizeに目的関数を渡す

これだけです!めっちゃ簡単ですね!


ちなみに上のコードの実行結果は以下のようになりました。

{'x': 2.005349708575524}
2.861938184303352e-05

この結果を見ると、xの値がf(x)を最小化するx=2に十分近く、実験が上手くいっていることが分かります。

ヒューリスティックコンテストでOptunaを使う

ヒューリスティックコンテストではハイパラ調整を行う場面が数多くあります。

例えば、焼きなまし法の温度調整などです。焼きなまし法では初期温度と終点温度の2変数を使用するため、これらをハイパーパラメータとして調整することになります。

パラメーターが1つだけであれば人力でも時間を掛ければ調整できるかも知れませんが、3つ4つと増えてくると、人力でのパラメーター調整が困難*1になってきます。

そこでこのようなハイパーパラメーターの調整をOptunaにやらせよう、というのがこの記事の内容になります。

Python以外でもOptunaを使いたい!

ここまで、Optuna自体の説明とどのようにヒューリスティックコンにOptunaを活用するのかを説明してきました。

しかし、OptunaはPythonのライブラリであるため、ほかの言語で書いたコードのハイパラ調整に用いるのが難しいという問題点があります。

そのため、ここではC++で書かれたヒューリスティックコンテスト(AHC005)のコードを例に、Optunaの使い方を説明していこうと思います。(コードの使用を許可してくださったMtSakaさん、ありがとうございます)

ここでは2つのパラメーターa, bを調整してスコアの変化を調べます。(なんのパラメーターなのかという説明は本質ではないので省略します)

C++側のコード

int main(int argc, char* argv[]){
  if (argc >= 4) {
    double a, b;
    string text_path;
    a = stod(argv[1]);
    b = stod(argv[2]);
    text_path = argv[3];
    textfile_input(text_path);
    init();
    calc_dist();
    solve(a, b);
    initialize();
    int score = round(1e4+1e7*(double)n/best_cost);
    cout << score << endl;
  }
}

全体を載せると長くなりすぎるのでmain関数だけを載せました。

重要なのは

  • ハイパラと使用するテストケースのパス*2を受け取る
  • スコアを返す

という二点だけです。

textfile_inputはテストケースのパスを渡すと入力を受け取るような関数になっています。

これをコンパイルしておけばC++側での準備は完了です。

Python側のコード

import optuna
import subprocess
from multiprocessing import Pool
import os
import optuna
from random import sample
from tqdm import tqdm

using_testcase_num = 200
total_testcase_num = 10000
n_trials = 400

def f(args):
    i, a, b = args
    cmd = './a.out {} {} in/{:04}.txt'.format(a, b, i)
    res = subprocess.run([cmd], universal_newlines=True, shell=True, stdout=subprocess.PIPE)
    return float(res.stdout)
    
def wrapper(args):
    mean = 0
    using_tastcases = sample(list(range(total_testcase_num)), using_testcase_num)
    with Pool() as pool:
        mean = sum(pool.map(f, [[i] + args for i in using_tastcases]))
    mean /= using_testcase_num
    return mean

def objective(trial):
    a  = trial.suggest_loguniform('a', 1e-8, 1e8)
    b  = trial.suggest_loguniform('b', 1e-8, 1e8)
    score = wrapper([a, b])
    print('a: %1.3f, b: %1.3f, score: %f' % (a, b, score))
    return score

# 探索
study = optuna.create_study(direction='maximize')
study.optimize(objective, n_trials=n_trials)
print('best_score:{:.2f}'.format(study.best_value))
print('a:{}, b:{}'.format(study.best_params["a"], study.best_params["b"]))

# logの書き込み
f = open('log.txt', 'a')
f.write('best_score:{:.2f}, a:{}, b:{}, using_testcase_num:{}, total_testcase_num:{}, n_trials:{}\n'.format(study.best_value, study.best_params["a"], study.best_params["b"], using_testcase_num, total_testcase_num, n_trials))
f.close()

# 探索過程の可視化
fig = optuna.visualization.plot_optimization_history(study)
fig.show()


この部分は真紅色に染まるぷーんさんのコードを参考にさせて頂きました。ありがとうございます。

結構長いコードなので、いくつかに区切って解説していきます。

ライブラリのインポート
import optuna
import subprocess
from multiprocessing import Pool
import os
import optuna
from random import sample
from tqdm import tqdm

ライブラリをインポートしているだけですね。

各種変数
using_testcase_num = 200
total_testcase_num = 10000
n_trials = 400

いくつかの変数を定義しています。

今回のコードでは

  • optunaが1回の探索に用いるテストケース数
  • 用意している総テストケース数
  • optunaの探索回数

を定義しています。

目的関数
def f(args):
    i, a, b = args
    cmd = './a.out {} {} in/{:04}.txt'.format(a, b, i)
    res = subprocess.run([cmd], universal_newlines=True, shell=True, stdout=subprocess.PIPE)
    return float(res.stdout)
    
def wrapper(args):
    mean = 0
    using_tastcases = sample(list(range(total_testcase_num)), using_testcase_num)
    with Pool() as pool:
        mean = sum(pool.map(f, [[i] + args for i in using_tastcases]))
    mean /= using_testcase_num
    return mean

def objective(trial):
    a  = trial.suggest_loguniform('a', 1e-8, 1e8)
    b  = trial.suggest_loguniform('b', 1e-8, 1e8)
    score = wrapper([a, b])
    print('a: %1.3f, b: %1.3f, score: %f' % (a, b, score))
    return score

実行を並列化をしているのでコードが複雑になっていますが、一つずつ見ていけば大して難しくありません。

まずf(args)ですが、この関数ではテストケースの番目を表すiと最適化させたい2つのパラメーターa,bを受け取り、パラメーターa,bでテストケースiを実行した際のスコアを返しています。このときに、subprocess.runで先程コンパイルした./a.outを実行しています。

次にwrapper(args)では、2つのパラメーターa,bを受け取り、用意しているすべてのテストケースから1回の探索に用いる分のテストケースを抽出し、パラメーターa,bでそれらを実行した際のスコアの平均を返しています。

最後に目的関数ですが、これは単純にwrapper(args)の返り値をそのまま返しています。

探索
study = optuna.create_study(direction='maximize')
study.optimize(objective, n_trials=n_trials)
print('best_score:{:.2f}'.format(study.best_value))
print('a:{}, b:{}'.format(study.best_params["a"], study.best_params["b"]))

パラメーターを探索しています。今回はスコアが高ければ高いほど良いという問題設定だったので、optuna.create_studyの引数に direction='maximize' を渡すことで目的関数の返り値を最大化させています。

logの書き込み
f = open('log.txt', 'a')
f.write('best_score:{:.2f}, a:{}, b:{}, using_testcase_num:{}, total_testcase_num:{}, n_trials:{}\n'.format(study.best_value, study.best_params["a"], study.best_params["b"], using_testcase_num, total_testcase_num, n_trials))
f.close()

探索結果をテキストファイルに書き込ませています。

探索過程の可視化
fig = optuna.visualization.plot_optimization_history(study)
fig.show()

探索過程をグラフとして表示させています。


以上がコードの説明になります。

実験結果

実際に

  • using_testcase_num:100
  • total_testcase_num:10000
  • n_trials:400

で実験してみたところ

以下のような結果になりました。

f:id:kuruton456:20211214001205p:plain

縦軸が目的変数、横軸が最適化の探索回数になってます。オレンジの折れ線が最良の目的変数の値となっており、何回目のトライアルでベストパラメータが出たのかが分かるようになっています。


上のグラフから

  • 100回探索した時点でスコアがかなり収束していること
  • パラメーターによってスコアが大きく変動すること

などが分かります。

スコアを最大化するように調整したパラメーターで実際に提出してみたところ、21707556点でした。

また一方で、スコアを最小化するように調整した*3パラメーターで提出したところ、4235639点になりました(上記のスコアの約5分の1)。

このことから、実験は上手くいっており、Optunaを使ってパラメーターを調整することで大きくスコアが改善できるということが確認できました。

おまけ

ここまで書いておいてなんですが、実は今回の実験では元々のコードのスコアを超える事ができませんでした…

f:id:kuruton456:20211213234829p:plain
Optunaで調整したパラメーターでのスコア
f:id:kuruton456:20211213235630p:plain
MtSakaさんのパラメーターでのスコア

探索回数(n_trials)を1000~2000回まで増やして回すことも考えたんですが、そこまで探索に時間をかけるのは「Optunaで手軽にハイパラを調整する」という本来の目的から外れているように思えたので、残念ですがここで断念しました。

しかも話を聞くと、MtSakaさんは3回の探索でこのスコアを出したらしいです…(は?)


MtSakaさんがOptunaより強いということが分かったところで、この記事を終わらせて頂こうと思います!それではまた!

*1:人力でハイパラを調整しようとするとグリッドサーチやランダムサーチなどを行うことになりますが、Optunaではこれをベイズ最適化アルゴリズムで行うのでより効率的に探索してくれます

*2:このコードでは事前にテストケースを作っておいて、同じ階層のinフォルダに0000.txt~9999.txtとして置いてあります

*3:普通にdirection='maximize'を付け忘れて実験してただけとは言えない…