Hiroki Hamaguchi

Hiroki Hamaguchi

D1 Student

しっかり学ぶ数理最適化 ヒューリスティック編

概要

本記事は、梅谷俊治先生の『しっかり学ぶ数理最適化 モデルからアルゴリズムまで』(以下、教科書と表記)の内容を基に、私自身がネット上の情報を収集・整理し、特に実装と視覚化に重点を置いて再構成したものです。

また、梅谷先生によるスライド1やスライド2、日本オペレーションズ・リサーチ学会(以下、ORと表記)での記事1や記事2、そしてORの他の方の記事1や記事2なども本記事では参考にさせて頂いています。

梅谷先生からは、BLF法等のHP上に公開されているプログラムの一部使用も含めて許諾を頂いております。深く感謝申し上げます。

目次扱う内容
複雑な関数の最適化局所探索法、多スタート局所探索法、反復局所探索法、可変近傍探索法
巡回セールスマン問題2-opt、bitdp、タブーサーチ、誘導局所探索法
円詰め込み問題焼き鈍し法、山登り法、大洪水法、閾値受理法
長方形詰め込み問題BLF法、探索空間について
MountainCar遺伝的アルゴリズム、局所探索法

導入

本記事では、 発見的解法 (heuristics、ヒューリスティック) について扱います。

ヒューリスティックという単語の定義は、IoT用語辞書によると、

ヒューリスティック……(中略)……とは、ある程度正解に近い解を見つけ出すための経験則や発見方法のことで、「発見法」とも呼ばれます。いつも正解するとは限らないが、おおむね正解するという直感的な思考方法で、たとえば、服装からその人の性格や職業を判断するといったことは、ヒューリステックな方法といえます。理論的に正しい解を求め、コンピュータのプログラムなどに活用される「アルゴリズム」に対置する概念です。

となっています。

教科書における対応範囲は、大まかには4.6, 4.7節に相当します。なお、都合上教科書とは順番を少し変えて各内容を見ていくことにします。また、教科書に載っている内容の全ては、本記事には載っておらず、逆もまた然りです。

前準備

本記事で出てくるコードは、Google Colab上で再現可能となっています。以下にその前準備となるコードを記します。

!pip install gym pyvirtualdisplay > /dev/null 2>&1
!apt-get install -y xvfb python-opengl ffmpeg > /dev/null 2>&1
!apt-get update > /dev/null 2>&1
!apt-get install cmake > /dev/null 2>&1
!pip install gym[atari] > /dev/null 2>&1

import io
import os
import gym
import math
import time
import glob
import base64
import random
import datetime
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
import matplotlib.animation as animation
from typing import List,Tuple
from matplotlib import gridspec
from gym.wrappers import Monitor
from pyvirtualdisplay import Display
from matplotlib.colors import ListedColormap
from IPython import display as ipythondisplay
from IPython.display import HTML,display,YouTubeVideo
%matplotlib inline

複雑な関数の最適化

初めに、ヒューリスティックの最も基本的な戦略である局所探索法についてみていきます。

説明1

簡単に局所探索法に関する説明をします。数理計画用語集によると、局所探索法とは、

「適当な初期解から出発し，解の近傍にそれより良い解があれば置き換える，という操作を繰り返し実行して，解の更新が行われなくなったとき終了する」というアルゴリズム

とされています。非常にシンプルかつ基本的な考え方で、多くの手法がこれに当てはまっています。

用語

  • 初期解 アルゴリズムにおける最初期の解。場合によっては実行不能な場合もありますが、何か一つ解を取ってきているものと思ってもらえれば大丈夫かと思われます。一般には何か別のアルゴリズム(貪欲法など)でそこそこ良い解を適当に取ることも多いです。

  • 近傍 今持っている解に少しの変更を加えることによって得られる解の集合のこと。「近傍が大きい」「近傍が小さい」という表現もありますが、これは「ある解と別の解(近傍内の解)がどれだけ似ているか」ということを言っているとも捉えられます。「良い解どうしは似た構造を持つ」という近傍最適性(proximity optimality principle, POP)が、近傍を考える妥当性になっています。

  • POP 先述の通り、POPは近傍最適性という意味です。例えば、駅から大学までの一番短い経路と、二番目に短い経路では、大部分が同じ経路で、違う部分はわずかなはずです。より抽象的に、数列を最適化する際、「123456」がある程度良い解である場合、それを少し変えた「15234_6」(5を2の位置に挿入した番号)や「153426」(5と2を交換した番号)は妥当な解の一つとなりえます。なお、前者のことを挿入近傍、後者のことを交換近傍とも言います。(以下の図は局所探索法とその拡張—タブー探索法を中心としてという記事から引用しました)

挿入近傍交換近傍.jpeg

  • 実行可能解 制約を満たしている解。線形計画問題などにおいても出てくる用語です。探索空間というのは、この実行可能解全体の集合とも言えます。

手法

局所探索法という分類には、以下の手法などが該当します。

  • 山登り法 (←今扱う手法)
  • 焼きなまし法 (以下の三つは後で登場します)
  • タブーサーチ
  • (遺伝的アルゴリズム) ※注

※注 遺伝的アルゴリズムは、Wikiによると狭義には局所探索法ではないらしいです。ただ、数理計画用語集によると広義には局所探索法らしいです。

実践1

ここでは、局所探索法のイメージを掴みながら、具体例として以下の関数 $f(x)$ を最小化していきます。私が適当に計算して設定した関数です。実行可能領域は、グラフ描画の便宜上、$-3.3 \leq x \leq 3.3$ としました。

(なお、これはあくまで例であるため、複雑な関数の最適化が必ず局所探索法を用いて行われている、という訳ではないことに注意してください。)

def f(x):
    x=np.clip(x,-3.3,3.3)
    # (x-3)(7x-13)(3x-4)(x+3)(2x+5)(x+1) + C
    return (+44*(x**6) + 13*(x**5) - 638*(x**4)
            -88*(x**3) + 2600*(x**2) - 261*x + 6.5653624787847)

まずは特に工夫をせずに、局所探索法を使用して、最適化を試みます。局所探索法の具体的な手順は以下の通りです。

局所探索法 (教科書p.284からの引用)

Step1. 初期解 $ x^{(0)} $ を定める。 $ k=0 $ とする。 Step2. 近傍 $ N(x^{(k)}) $ 内に $ f(x’)<f(x) $ となる改善解 $ x’ $ がなければ終了。 Step3. 改善解 $ x’ \in N(x^{(k)}) $ を1つ選んで、 $ x^{(k+1)}=x’ $ とする。 $ k=k+1 $ としてStep2に戻る。

改善解があればそれを必ず採用するという、極めてシンプルな手法です。Wikiにも擬似コードが掲載されています。なお、この手順のことを山登り法とも言います。

以下に局所探索法を使用したコードを載せます。

def vis(hists: List[List[float]], draw_arrow: bool = False) -> None:
    """ビジュアライズ用関数 見る必要なし

    Args:
        hists (List[List[float]]): 表示する探索履歴のリスト 途中は5個ずつ間引いて表示する
        draw_arrow (bool, optional): 探索履歴同士の遷移を描くかどうか デフォルト値はFalse
    """
    xs = np.linspace(-3.3, 3.3, 100)
    ys = f(xs)
    fig = plt.figure(figsize=(12, 5))
    ax = fig.add_subplot(111)
    ax.plot(ys)
    ax.set_title("f(x) (-3.3 <= x <= 3.3)")
    ax.set_xlabel("x")
    ax.set_ylabel("f(x)")
    ax.set_xticks(np.linspace(0, 100, 5))
    ax.set_xticklabels([-3.3, -1.65, 0, 1.65, 3.3])
    ax.grid()
    for hist in hists:
        for i in range(1, len(hist)-1, 5):
            ax.plot((hist[i]+3.3)/6.6*99,
                    f(hist[i]), 'o', color="gray")
        ax.plot((hist[0]+3.3)/6.6*99,
                f(hist[0]), 'o', color="blue")
        ax.plot((hist[-1]+3.3)/6.6*99,
                f(hist[-1]), 'o', color="red")
    if draw_arrow:
        for i in range(len(hists)-1):
            ax.annotate("", xytext=((hists[i][-1]+3.3)/6.6*100, f(hists[i][-1])),
                        xy=((hists[i+1][0]+3.3)/6.6*100, f(hists[i+1][0])),
                        arrowprops=dict(arrowstyle="->",
                                        color="green"))
    plt.show()

def local_search(x0: int) -> List[float]:
    """局所探索法

    Args:
        x0 (int): 初期解

    Returns:
        List[float]: 探索履歴
    """
    x0 = np.clip(x0, -3.3, 3.3)
    x = x0             # 適当な初期解
    k = 0              # 探索回数
    best_score = f(x)  # 目的関数の値
    hist = [x]         # 解の履歴

    # ここが重要!
    while k < 100:     # 探索回数の上限
        k += 1
        Nx = np.linspace(x-0.05, x+0.05, 10)  # 解xの近傍
        fNx = f(Nx)                           # 近傍の各点における目的関数の値
        if np.any(fNx < best_score):  # 近傍に今より良い解があった場合、それを採用
            new_x = np.random.choice(Nx[np.where(fNx < best_score)[0]])
            best_score = f(new_x)
            x = new_x
            hist.append(new_x)
        else:                         # 近傍に今より良い解がなかった場合、探索を終了
            break

    assert(len(hist) == k)
    print(f"探索回数: {len(hist)}回")
    print(f"得られた最適値: {f(hist[len(hist) - 1])}")
    print("真の最適値: 0")
    return hist

以上で定義した関数を、実行してみます。

hist = local_search(x0=-2)  # -2は適当な初期解
vis([hist])

探索回数: 26回
得られた最適値: 2666.7852665513115
真の最適値: 0

局所探索法.png

青

が初期解、±0.05の範囲を近傍として、その近傍内で最も目的関数の値が小さくなる灰色の点を経由しながら最適化していき、最終的に赤が求まった解、という風になっています。ここで、今考えている問題の目標は、関数 $f(x)$ の最小化であったことを思い出して下さい。つまり、このグラフの一番窪んでいる部分である、$f(x)=0$ に到達することを目指しています。

局所探索法の改良

さて、前節で出力されたグラフを見れば、確かに初期解よりも良い解を得られているものの、今得られている解は局所最適解(locally optimal solution)になってしまっていることが分かります。(局所最適に陥るとも言います。)

局所最適解であるとは、即ち、今の解の近傍にそれより良い解が存在しないということを意味しています。これを解決するには様々な方法が知られていますが、ここでは局所探索法の自然な拡張とも言える、多スタート局所探索法と反復局所探索法、そして可変近傍探索法についてみていきます。

多スタート局所探索法

競技プログラミング(以下、競プロと表記)的な文脈では、よく多点スタートとも呼ばれます。ほぼ名前通りの内容ですが、多くの初期点からスタートして、一番良い局所最適解を最良の解とするだけです。

(競プロ的補足: AHC002というコンテストにおけるtourist(競プロ界のNo.1プレイヤー)の解は多点スタート的解法でした。より厳密には、ある要素を24通り全探索して、その結果からいいものを5個選び(ここが多点スタート)、その各初期点に対して適切な近傍によって山登りし、最後にSA(simulated annealing)をして解を求めていました。このように、多点スタート+何か別の手法とすることも多くあります。)