数理最適化を勉強する話①

「AI・データサイエンスのための図解でわかる数学プログラミング」を読むシリーズ

今回から「数理最適化編」になる

数理最適化
- ①全検索
  - 深さ優先探索(DPS)
  - 動的計画法(Dinamic programming:DP)
- ②ヒューステリック
  - 最近傍法
  - 遺伝アルゴリズム(Genetic Algorithm:GA)

数理最適化
1. ①全検索
  1. 深さ優先探索(DPS)
  2. 動的計画法(Dinamic programming:DP)
2. ②ヒューステリック
  1. 最近傍法
  2. 遺伝アルゴリズム(Genetic Algorithm:GA)

数理最適化

数理最適化とは最適化問題を定式化して、それを解くこと。

定式化は目的関数(最小または最大にする数式)と制約を設定して

解く方法は

全パターンを計算して最適解を見つける
ヒューリスティック

ヒューリスティックは経験的に効率よく最適解にたどり着ける方法で、問題ごとに決まっている「特殊解法」と多くの最適化問題に適応できる「一般解法」の２種類。

①全検索

全てのパターンを検索してその中で目的関数が最小化するものを選択する。

データは多いが時間はかかるが最も最適なものを選択できる。

全パターンを検索するには、数字列を並び替える全てのパターンを計算する、permutations()関数を用いる。

from itertools import permutations
import numpy as np
pattern = np.array([*permutations(range(8))]).T
print(pattern)

これを実行すると、

[[0 0 0 … 7 7 7]
[1 1 1 … 6 6 6]
[2 2 2 … 5 5 5]
…
[5 5 6 … 1 2 2]
[6 7 5 … 2 0 1]
[7 6 7 … 0 1 0]]

で全ての組み合わせを列挙できる。

深さ優先探索(DPS)

permutation関数は次元数が多くなるとメモリ不足になりがちらしい。

そこで“深さ優先探索(DPS)”という方法を使うとメモリ消費が少なくできる。

動的計画法(Dinamic programming:DP)

N個の全ての並び替えで計算を行う場合(つまり全探索)、計算量はN!となる。

しかし実際にはそれぞれの並び替えの中にも共通する部分がある。

並び替えの最終項目から帰納的に計算することで最適化を行う方法を動的計画法という

②ヒューステリック

遺伝アルゴリズム(Genetic Algorithm:GA)

多くの問題の近似解を計算できる”一般解法”

方法としては、

初期世代の個体群を生成
次世代の個体群を生成
2を繰り返す

次世代の個体群を作るには、

交叉
突然変異
選択

の3方法がある

①交叉

親世代の個体群から任意の２世代の一部を入れ替える。

②突然変異

１個体の情報の一部を変化させる。

③選択

最適化に近いものをそのまま次世代に流用する

これを繰り返していくことで、近似解を求めていくやり方。

このコードがちょっと理解に2日くらいかかった。

普段使わないコードが多々出てきたので、python自体の勉強もしないといけないなぁと思ったり。

続きはまた今度。