2,3回動かしてうまくいっただけなのでもしかしたらバグがあるかもしれない。
まあ、今回はそれなりに満足いけたものを作れた気がする。
あと、今忙しくて全然書くことまとめれてないから今度暇なときにこの記事修正する。
未来の自分へ
お前は次に「こんなの使わねえよww」と言う。
・・・ハッ!?
以下2015/11/30追記
いやー、やっとひと段落しました。いや、してないんですけどね。とりあえずはゆっくり記事書けるぐらいの時間は確保できたと。
それじゃあ、今回作ったタブーサーチの紹介でもしますか。
タブーサーチとは(デデン!
探索アルゴリズムの手法の一つだそうです。詳しいことはあまり知りません(^p^)
DMMのLord of Walkureというゲームでですね、討伐戦団というコンテンツがありまして。
主人公とワルキューレ(味方)×10人がボスを倒す、という内容です。
この討伐っていうのがすごく難しくて、ワルキューレの隊列の組み方で勝率に影響が出るんですよね。
例えば、A、B、C、D、Eというワルキューレがいたとして、隊列を[ABCDE]にして戦うと勝率が30%だったとします。
これを[BACDE]としただけで勝率が50%まで跳ね上がる、なんてことがあるんですよ。
ボスとは無限に戦えるわけじゃないからできるだけ勝率を高くしたい・・・。
そんなわけでシミュレータを作りました。(今回はシミュレータの方のプログラムは載せません^^;理由は後述)
Lord of Walkureは課金をしなかった場合、最大で50枚ほどのワルキューレを仲間にすることができます。その中から一番効率よくボスを倒せる10人を選ぶわけです。数式で表すと50P10です。
とりあえず4P4でシミュレーションしてみることにしました。べ、別にデータ入力が面倒だったわけじゃないんだからね(^p^)
計算結果は4秒。まあ、こんなもんかな。次に10P10で計算。
・・・計算が終わらないだと?
そうなんです。計算が終わらなかったんです。ブレークポイントを作って確認してみると計算自体はしているようでした。不思議に思いながら何も考えずに10P10を計算してみると
3628800!
300万回も計算する必要があったわけです。4P4を計算すると24になったので、一秒に6回計算できるわけです。300万回の計算には50万秒必要なわけで、50万秒はおよそ8000分で、8000分はおよそ140時間で、140時間はおよそ5日という計算になります。
本当は50P10の計算をしたいんです。
しかし、この値を計算すると37.27604302[P]となります。[P]って知ってますか?10の15乗のことらしいですよ。
僕もよくわからないんですけど、多分私が生きている間に計算を終えることが不可能なんじゃないかなと思います。
あほらしくなりましたね(^p^)
しかし、ここであきらめるほど私はヤワじゃない!
ここからようやくタブーサーチの話に入るわけです。
全件探索するから遅いんです。効率よく探索すれば早いはず!
ということで探索アルゴリズムを使うことに。
個人的には遺伝アルゴリズムなんかに興味があったのですが、「タブー探索勉強中!」といっている友人がいたのでタブー探索を使うことにしました。
アルゴリズムの内容に関してはwikipediaで調べたものを基本的に使っています。
私の日本語力がないからかもしれませんが、一部よくわからないところがあったのでそこは自分で補完しました。
以下、探索の流れ
1.初期解の生成
2.解の近傍生成
3.優良解の判定
4.現在解の更新判定
5.タブー判定
6.2.~5.を現在解が収束するか、任意の計算回数になるまでループ
とりあえずテスト。
任意の個数の数値をn個組み合わせて総和が最大になるものを探索します。
評価関数は素直に総和を返すようにします。
ちょっと何言ってるかわからないと思うので実際に見せます。
総和が一番大きくなる組み合わせになっていそうですね。
ただ、今回は並び方も考慮したいので、並び順も評価関数に組み込みたいですね。
場所によって重みをつけることにしましょう。後ろにあるほうがより重くなるということです。
7,8,9,10,11と出力してくれればうれしいです。
されたっぽいですね。
じゃあテスト終わり。
いよいよ討伐シミュレータに組み込みます。
まずは4P4をどれだけ高速化できるか・・・!
(正確には4個のデータの組み合わせです。)
計算結果・・・8秒
(#^p^)
(#^p^)(#^p^)
普通に計算した時より遅いし。
キレソウ(#^p^)
というわけでシミュレータ機能せず・・・。
タブー探索の収束条件とかもうちょっといじれそう。
ほかにも最適化できそうなところがちらほら・・・。
これを直せば早くなるんでしょうか?
教えて偉い人。
とりあえず動作はしているのでタブー探索のソースをあげます。
最適化できそうなところがあったら教えてください。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#pragma once | |
#include"stdafx.h" | |
//タブーサーチクラス | |
template<class T_n> | |
class TabuSearchClass | |
{ | |
private: | |
//現在の解 | |
vector<T_n> current; | |
//最適解 | |
vector<T_n> optimal; | |
//最適解のサイズ | |
size_t optimal_size; | |
//タブーリスト | |
vector<pair<T_n, T_n>> tabu_list; | |
//タブーリストのサイズ | |
size_t tabu_list_size; | |
//探索回数 | |
size_t search_num; | |
//最大評価値 | |
double max_evaluate; | |
//現在の評価値 | |
double current_evaluate; | |
//乱数用 | |
mt19937 mt; | |
//最適解と最大評価値の初期化 | |
void Initialize() | |
{ | |
optimal = vector<T_n>(this->current.begin(), current.begin() + optimal_size); | |
max_evaluate = current_evaluate = 0.; | |
} | |
//近傍の選択 | |
vector<vector<T_n>> ChoiceNeighbor(const vector<T_n> ¤t) | |
{ | |
size_t current_size = current.size(); | |
//size_t data_size = GetDataSize(); | |
vector<vector<T_n>> neighbor(current_size, vector<T_n>(current)); | |
for (size_t i = 0; i < current_size; i++) | |
{ | |
swap(neighbor[i][0], neighbor[i][i]); | |
} | |
return vector<vector<T_n>>(neighbor.begin() + 1, neighbor.end()); | |
} | |
//優良解の探索 | |
//predにはvector<T_n>の型を引数にした評価関数を渡す | |
template<class _Pre> | |
void ChoiceExellence(_Pre pred) | |
{ | |
vector<vector<T_n>> neighbor = ChoiceNeighbor(this->current); | |
size_t solve_size = GetSolveSize(); | |
size_t neighbor_size = neighbor.size(); | |
double max = 0.; | |
double evaluate; | |
vector<pair<double, int>> better; | |
for (size_t i = 0; i < neighbor_size; i++) | |
{ | |
evaluate = pred(vector<T_n>(neighbor[i].begin(), neighbor[i].begin() + solve_size)); | |
/*if (evaluate>=max) | |
{ | |
max = evaluate; | |
better = i; | |
}*/ | |
better.push_back(make_pair(evaluate, i)); | |
} | |
sort(better.begin(), better.end(), std::greater<pair<double, int>>()); | |
this->current_evaluate = better[0].first; | |
for (auto &i : better) | |
{ | |
if (CheckTransition(neighbor[i.second], make_pair(this->current[0], neighbor[i.second][0]))) | |
break; | |
} | |
//this->current_evaluate = max; | |
//CheckTransition(neighbor[better], make_pair(neighbor[better][0], neighbor[better][better])); | |
//return neighbor[better]; | |
} | |
//遷移がタブーリストに含まれているか判定 | |
//含まれていたらtrue | |
bool CheckTabu(const pair<T_n, T_n> &transition) | |
{ | |
for (auto &i : tabu_list) | |
{ | |
if (i == transition || i == make_pair(transition.second, transition.first)) | |
{ | |
return true; | |
} | |
} | |
return false; | |
} | |
//現在の解を遷移するか判定 | |
//遷移したらtrue | |
bool CheckTransition(const vector<T_n> &neighbor, const pair<T_n, T_n> &transition) | |
{ | |
size_t solve_size = this->GetSolveSize(); | |
if (current_evaluate > max_evaluate) | |
{ | |
this->optimal = vector<T_n>(neighbor.begin(), neighbor.begin() + solve_size); | |
this->current = neighbor; | |
max_evaluate = current_evaluate; | |
if (CheckTabu(transition)) | |
{ | |
tabu_list.erase(find(tabu_list.begin(), tabu_list.end(), transition)); | |
tabu_list.push_back(transition); | |
} | |
else | |
{ | |
tabu_list.push_back(transition); | |
if (CheckTabuListSizeOver()) | |
{ | |
tabu_list.erase(tabu_list.begin()); | |
} | |
} | |
return true; | |
} | |
else | |
{ | |
if (!CheckTabu(transition)) | |
{ | |
this->current = neighbor; | |
tabu_list.push_back(transition); | |
if (CheckTabuListSizeOver()) | |
{ | |
tabu_list.erase(tabu_list.begin()); | |
} | |
return true; | |
} | |
else | |
return false; | |
} | |
return false; | |
} | |
//タブーリストのサイズが指定のサイズをオーバーしたか判定 | |
//オーバーしたらtrue | |
bool CheckTabuListSizeOver() | |
{ | |
return tabu_list.size() > tabu_list_size; | |
} | |
//重複回数をカウント、指定回数以上重複でtrueを返す | |
class CheckConvergence | |
{ | |
private: | |
vector<T_n> data; | |
int count; | |
int num; | |
public: | |
//コンストラクタはコメント表示されない? | |
CheckConvergence(){} | |
//dataに初期解、numに何回解が変わらなかったら収束するかを設定 | |
CheckConvergence(const vector<T_n> &data, const int &num) | |
{ | |
this->data = data; | |
this->count = 0; | |
this->num = num; | |
} | |
~CheckConvergence(){} | |
//countがnumを超えたらtrue(収束) | |
bool operator()(const vector<T_n> &data) | |
{ | |
if (this->data == data) | |
{ | |
count++; | |
} | |
else | |
{ | |
this->data = data; | |
count = 0; | |
} | |
return count > num; | |
} | |
}; | |
public: | |
//デフォルト値 | |
//最適解のvectorのサイズ | |
static const size_t default_optimal_size = 10; | |
//探索回数 | |
static const size_t default_search_num = 100; | |
//タブーリストのサイズ | |
static const size_t default_list_size = 7; | |
//コンストラクタ | |
TabuSearchClass() | |
{ | |
SetMt(); | |
} | |
//最適解を見つけたいvectorをvに渡す | |
TabuSearchClass(const vector<T_n> &v) | |
{ | |
SetMt(); | |
SetData(v); | |
SetOptimalSize(default_optimal_size); | |
SetSeachNum(default_search_num); | |
this->SetTabuListSize(default_list_size); | |
} | |
//最適解を見つけたいvectorをvに渡す | |
//最適解のvectorのサイズをoptimal_sizeに渡す | |
TabuSearchClass(const vector<T_n> &v, const size_t &optimal_size) | |
{ | |
SetMt(); | |
SetData(v); | |
SetOptimalSize(optimal_size); | |
SetSeachNum(100); | |
this->SetTabuListSize(7); | |
} | |
//最適解を見つけたいvectorをvに渡す | |
//最適解のvectorのサイズをoptimal_sizeに渡す | |
//探索回数をsearch_numに渡す | |
TabuSearchClass(const vector<T_n> &v, const size_t &optimal_size, const size_t &search_num) | |
{ | |
SetMt(); | |
SetData(v); | |
SetOptimalSize(optimal_size); | |
SetSeachNum(search_num); | |
this->SetTabuListSize(7); | |
} | |
//最適解を見つけたいvectorをvに渡す | |
//最適解のvectorのサイズをoptimal_sizeに渡す | |
//探索回数をsearch_numに渡す | |
//タブーリストのサイズをlist_sizeに渡す | |
TabuSearchClass | |
( | |
const vector<T_n> &v, const size_t &optimal_size, const size_t &search_num, | |
const size_t &list_size | |
) | |
{ | |
SetMt(); | |
SetData(v); | |
SetOptimalSize(optimal_size); | |
SetSeachNum(search_num); | |
this->SetTabuListSize(list_size); | |
} | |
~TabuSearchClass(){} | |
////最適解を見つけたいvectorをvに渡す | |
void SetData(const vector<T_n> &v) | |
{ | |
this->current = v; | |
} | |
//最適解のvectorのサイズをoptimal_sizeに渡す | |
void SetOptimalSize(const size_t &size) | |
{ | |
this->optimal_size = size; | |
} | |
//メルセンヌツイスタの初期化 | |
void SetMt() | |
{ | |
random_device rnd; | |
mt.seed(rnd()); | |
} | |
//データのサイズを返す | |
size_t GetDataSize()const | |
{ | |
return this->current.size(); | |
} | |
//最適解のサイズを返す | |
size_t GetSolveSize()const | |
{ | |
return this->optimal.size(); | |
} | |
//タブーリストのサイズをsizeに設定する | |
void SetTabuListSize(const size_t &size) | |
{ | |
this->tabu_list_size = size; | |
} | |
//タブーサーチをする | |
//predにはvector<T_n>の型を引数にした評価関数を渡す | |
template<class _Pre> | |
vector<T_n> TabuSearch(_Pre pred) | |
{ | |
const size_t convergence_num = 5; | |
CheckConvergence obj(this->current, convergence_num); | |
Initialize(); | |
for (int i = 0; !obj(this->current) && i < search_num; i++) | |
{ | |
ChoiceExellence(pred); | |
//CheckTransition(); | |
} | |
return optimal; | |
} | |
//探索回数をnumに設定 | |
void SetSeachNum(const size_t &num) | |
{ | |
this->search_num = num; | |
} | |
//最大評価値を返す | |
double GetMaxEvaluate()const | |
{ | |
return max_evaluate; | |
} | |
}; |
あと、だれかもっと効率のいいアルゴリズム教えてください。ってかワルキューレのシミュレータ作ってください。
長すぎるんだよ!3行でまとめろよ!
Lord of Walkureの討伐戦団最適化したい
タブー探索使ってみた
でも遅いから違う方法これから探す(^p^)