Загварчилсан хөргөлт¶
Загварчилсан хөргөлт (SA) нь функцийн глобал оптимумыг ойролцоолдог санамсаргүй алгоритм юм. Үүнийг санамсаргүй алгоритм гэж нэрлэдэг, учир нь хайлтдаа тодорхой хэмжээний санамсаргүй чанарыг ашигладаг тул ижил оролтын хувьд гаралт нь өөр өөр байж болно.
Бодлого¶
Бидэнд $s$ төлвийн энергийг тооцоолдог $E(s)$ функц өгөгдсөн. Бид $E(s)$ хамгийн бага болох $s_{best}$ төлвийг олох даалгавартай. SA нь төлвүүд нь дискрет бөгөөд $E(s)$ олон локал минимумтай байх бодлогод тохиромжтой. Бид Аялагч худалдаачны бодлого (TSP)-ыг жишээ болгон авна.
Аялагч худалдаачны бодлого (TSP)¶
Танд 2 хэмжээст орон зай дахь зангилаануудын багц өгөгдсөн. Зангилаа бүр нь өөрийн $x$ ба $y$ координатаар тодорхойлогдоно. Таны даалгавар бол эдгээр зангилаанд тухайн дарааллаар зочлоход туулах зайг хамгийн бага болгох зангилаануудын эрэмбийг олох явдал юм.
Сэдэл¶
Хөргөлт (annealing) нь металлургийн процесс бөгөөд материалыг халааж, дараа нь хөрөхийг зөвшөөрснөөр доторх атомууд нь дотоод энерги хамгийн бага байх байрлалд дахин зохион байгуулагдах ба энэ нь эргээд материалыг өөр шинж чанартай болгодог. Төлөв нь атомуудын байрлал бөгөөд дотоод энерги нь хамгийн бага болгож буй функц юм. Атомуудын анхны төлвийг дотоод энергийнх нь локал минимум гэж бодож болно. Материалыг атомуудаа дахин зохион байгуулахад хүргэхийн тулд бид глобал минимумд хүрэхийн тулд дотоод энерги нь хамгийн бага болоогүй мужийг гатлахад түүнийг өдөөх хэрэгтэй. Энэ өдөөлтийг материалыг илүү өндөр температурт халаах замаар өгнө.
Загварчилсан хөргөлт нь энэ процессыг шууд утгаараа загварчилдаг. Бид ямар нэг санамсаргүй төлвөөс (материал) эхэлж, өндөр температур тавина (халаана). Одоо алгоритм өндөр температураар өдөөгдсөн тул одоогийн төлвөөс өндөр энергитэй төлвүүдийг хүлээн авахад бэлэн болно. Энэ нь алгоритмыг локал минимумуудад гацахаас сэргийлж, глобал минимум руу хөдлөхөд тусална. Хугацаа өнгөрөх тусам алгоритм хөрч, өндөр энергитэй төлвүүдийг татгалзаж, олсон хамгийн ойрын минимум руу шилжинэ.
E(s) энергийн функц¶
$E(s)$ нь хамгийн бага (эсвэл хамгийн их) болгох шаардлагатай функц юм. Энэ нь төлөв бүрийг бодит тоонд харгалзуулна. TSP-ийн хувьд $E(s)$ нь төлөв дэх зангилаануудын дарааллаар нэг бүтэн тойрог туулах зайг буцаана.
Төлөв¶
Төлвийн орон зай нь $E(s)$ энергийн функцийн тодорхойлогдох муж бөгөөд төлөв гэдэг нь төлвийн орон зайд харьяалагдах дурын элемент юм. TSP-ийн хувьд бүх зангилаанд зочлохын тулд бидний авч болох бүх боломжит зам нь төлвийн орон зай бөгөөд эдгээр замуудын аль нэгийг нь төлөв гэж үзэж болно.
Хөрш төлөв¶
Энэ бол төлвийн орон зай дахь өмнөх төлөвд ойр байх төлөв юм. Энэ нь ихэвчлэн бид энгийн хувиргалт ашиглан анхны төлвөөс хөрш төлвийг олж авч болно гэсэн үг. Аялагч худалдаачны бодлогын хувьд хөрш төлвийг 2 зангилааг санамсаргүйгээр сонгож, одоогийн төлөв дэх байрлалыг нь солих замаар олж авна.
Алгоритм¶
Бид санамсаргүй $s$ төлвөөс эхэлнэ. Алхам бүрд бид одоогийн $s$ төлвийн хөрш $s_{next}$ төлвийг сонгоно. Хэрэв $E(s_{next}) < E(s)$ бол бид $s = s_{next}$ гэж шинэчилнэ. Эс бөгөөс бид $s_{next}$ руу шилжих үү, эсвэл $s$-д үлдэх үү гэдгийг шийддэг $P(E(s),E(s_{next}),T)$ магадлалын хүлээн авах функцийг ашиглана. Энд T нь температур бөгөөд эхэндээ өндөр утгад тавигдаж, алхам бүрд удаанаар хорогдоно. Температур өндөр байх тусам $s_{next}$ руу шилжих магадлал өндөр байна. Үүний зэрэгцээ бид мөн бүх итерацийн туршид хамгийн сайн $s_{best}$ төлвийг хянана. Нийлэлт болох буюу хугацаа дуустал үргэлжлүүлнэ.
Олон локал максимумтай энэ функцийн максимумыг хайж буй загварчилсан хөргөлтийн дүрслэл.
Температур(T) ба хорогдол(u)¶
Системийн температур нь алгоритм өндөр энергитэй төлвийг хүлээн авах хүсэмжийг илэрхийлнэ. Хорогдол нь алгоритмын "хөргөх хурд"-ыг илэрхийлдэг тогтмол юм. Удаан хөргөх хурд (том $u$) илүү сайн үр дүн өгдөг нь мэдэгдэж байгаа.
Магадлалын хүлээн авах функц(PAF)¶
$P(E,E_{next},T) = \begin{cases} \text{True} &\quad\text{if } \mathcal{U}_{[0,1]} \le \exp(-\frac{E_{next}-E}{T}) \\ \text{False} &\quad\text{otherwise}\\ \end{cases}$
Энд $\mathcal{U}_{[0,1]}$ нь $[0,1]$ дээрх тасралтгүй жигд санамсаргүй утга юм. Энэ функц нь одоогийн төлөв, дараагийн төлөв ба температурыг авч, $s_{next}$ руу шилжих үү, эсвэл $s$-д үлдэх үү гэдгийг хайлтад маань хэлдэг булев утга буцаана. $E_{next} < E$-ийн хувьд энэ функц үргэлж True буцаах бөгөөд эс бөгөөс Гиббсийн хэмжүүр-т харгалзах $\exp(-\frac{E_{next}-E}{T})$ магадлалаар шилжилтийг хийсэн хэвээр байж болохыг анхаарна уу.
bool P(double E,double E_next,double T,mt19937 rng){
double prob = exp(-(E_next-E)/T);
if(prob > 1) return true;
else{
bernoulli_distribution d(prob);
return d(rng);
}
}
Кодын загвар¶
class state {
public:
state() {
// Generate the initial state
}
state next() {
state s_next;
// Modify s_next to a random neighboring state
return s_next;
}
double E() {
// Implement the energy function here
};
};
pair<double, state> simAnneal() {
state s = state();
state best = s;
double T = 10000; // Initial temperature
double u = 0.995; // decay rate
double E = s.E();
double E_next;
double E_best = E;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
while (T > 1) {
state next = s.next();
E_next = next.E();
if (P(E, E_next, T, rng)) {
s = next;
if (E_next < E_best) {
best = s;
E_best = E_next;
}
E = E_next;
}
T *= u;
}
return {E_best, best};
}
Хэрхэн ашиглах вэ:¶
state классын функцүүдийг тохирох байдлаар нөхнө. Хэрэв та минимум биш глобал максимум олохыг оролдож байгаа бол $E()$ функц таны хамгийн их болгож буй функцийн сөрөг утгыг буцааж, эцэст нь $-E_{best}$-г хэвлэхийг баталгаажуул. Доорх параметрүүдийг өөрийн хэрэгцээнд тааруулан тохируул.
Параметрүүд¶
- $T$ : Эхний температур. Хайлтыг илүү удаан ажиллуулахыг хүсвэл үүнийг өндөр утгад тохируул.
- $u$ : Хорогдол. Хөргөх хурдыг шийднэ. Удаан хөргөх хурд (u-ийн том утга) нь илүү удаан ажиллах өртгөөр ихэвчлэн илүү сайн үр дүн өгдөг. $u < 1$ байхыг баталгаажуул.
Давталт хэдэн итерац ажиллахыг дараах илэрхийллээр өгнө
$N = \lceil -\log_{u}{T} \rceil$
$T$ ба $u$-г сонгох зөвлөмж : Хэрэв олон локал минимум ба өргөн төлвийн орон зай байвал удаан хөргөх хурдны хувьд $u = 0.999$ тохируул, энэ нь алгоритмд илүү олон боломжийг судлах боломж олгоно. Нөгөө талаас хэрэв төлвийн орон зай нарийн бол $u = 0.99$ хангалттай. Хэрэв та эргэлзэж байвал $u = 0.998$ буюу түүнээс дээш тохируулж найдвартай байлга. Алгоритмын нэг итерацийн time complexity-г тооцоол, үүнийг ашиглан TLE-ээс сэргийлэх $N$-ийн утгыг ойролцоолж, дараа нь доорх томьёог ашиглан $T$-г ол.
$T = u^{-N}$
TSP-д зориулсан жишээ хэрэгжүүлэлт¶
class state {
public:
vector<pair<int, int>> points;
std::mt19937 mt{ static_cast<std::mt19937::result_type>(
std::chrono::steady_clock::now().time_since_epoch().count()
) };
state() {
points = {{0,0},{2,2},{0,2},{2,0},{0,1},{1,2},{2,1},{1,0}} ;
}
state next() {
state s_next;
s_next.points = points;
uniform_int_distribution<> choose(0, points.size()-1);
int a = choose(mt);
int b = choose(mt);
s_next.points[a].swap(s_next.points[b]);
return s_next;
}
double euclidean(pair<int, int> a, pair<int, int> b) {
return hypot(a.first - b.first, a.second - b.second);
}
double E() {
double dist = 0;
int n = points.size();
for (int i = 0;i < n; i++)
dist += euclidean(points[i], points[(i+1)%n]);
return dist;
};
};
int main() {
pair<double, state> res;
res = simAnneal();
double E_best = res.first;
state best = res.second;
cout << "Length of shortest path found : " << E_best << "\n";
cout << "Order of points in shortest path : \n";
for(auto x: best.points) {
cout << x.first << " " << x.second << "\n";
}
}
Алгоритмын нэмэлт өөрчлөлтүүд:¶
- TLE-ээс сэргийлэхийн тулд while давталтад хугацаанд суурилсан гарах нөхцөл нэм
- Дээр хэрэгжүүлсэн хорогдол нь экспоненциал хорогдол юм. Үүнийг та хэрэгцээнийхээ дагуу хорогдлын функцээр үргэлж сольж болно.
- Дээр өгсөн магадлалын хүлээн авах функц нь илтгэгчийн хүртвэр дэх $E_{next} - E$ хүчин зүйлээс болж энерги нь бага төлвүүдийг хүлээн авахыг илүүд үздэг. Та энэ хүчин зүйлийг зүгээр л хасаж PAF-г энергийн зөрүүгээс хамааралгүй болгож болно.
- Энергийн зөрүү $E_{next} - E$-ийн PAF-д үзүүлэх нөлөөг доор үзүүлсэн шиг илтгэгчийн суурийг нэмэгдүүлэх/багасгах замаар нэмэгдүүлж/багасгаж болно:
bool P(double E, double E_next, double T, mt19937 rng) { double e = 2; // set e to any real number greater than 1 double prob = pow(e,-(E_next-E)/T); if (prob > 1) return true; else { bernoulli_distribution d(prob); return d(rng); } }