Simulated Annealing

INTRO

 

동아리에서 진행하는 방학 프로젝트에서 다들 휴리스틱을 고르는 분위기여서

저 또한 Simulated Annealing을 적용할 수 있는 문제로 잘 알려진 TSP를 고르게 되었습니다. 

언젠가 봐야지하고 6개월쯤 미뤄뒀던 Simulated Annealing을 이제야...

(Optimization By Simulated Annealing에도 TSP가 언급되어있네요)

 

방학 프로젝트의 결과물은 아래 링크에 있습니다.

보고서를 급하게 쓰기도 했고 제가 잘 아는 것도 아니라 오류가 꽤 있을거라 생각됩니다. 너그럽게 봐주세요...

https://github.com/kim1109123/Euclidean_TSP

GitHub - kim1109123/Euclidean_TSP

---

Concept

 

Simulated Annealing은 최적화 문제에서 Global Optimum을 찾는 확률론적 알고리즘입니다. 

[동전 뒤집기 2]와 같이 결정론적인 알고리즘을 다항시간에 돌리기 어려운 경우  SA와 같은 휴리스틱을 사용할 여지가 있습니다.

SA의 기본적인 흐름은 다음과 같습니다.

 

1. 초기 상태 세팅

2. 인접 상태 중 하나를 골라 이것을 선택했을 때 이득이 될 확률을 계산

3. 구간 [0, 1]에서 난수를 골라 난수 < [2]의 확률이라면 전이

4. [2], [3]을 적당히 반복

 

[3]은 이득이 아닌 경우에도 확률적으로 전이할 수 있도록 구간 [0, 1]의 난수를 생성하고 이와 비교해 상태전이를 결정합니다.

[3]과 같이 처리하는 이유는 [2]의 확률이 1 이상일 때에만 전이한다면 경사하강법처럼 Local Optimum에 빠질 여지가 있기 때문입니다. 

 

---

인접 상태

 

최종적으로 수렴해야하기 때문에 인접상태는 현재상태와 최대한 가까운 것이 좋습니다.

TSP를 생각하면 생각해볼 인접 상태의 정의가 3가지정도 있습니다.

 

1. 방문 순서에서 랜덤한 두 정점을 swap

2. 방문 순서에서 인접한 두 정점을 swap

3. 방문 순서에서 구간 flip

 

어떤 것이 가장 인접할지 생각해보겠습니다.

[1]은 변화하는 간선이 4개, [2]는 3개, [3]는 2개입니다. 

따라서 [3]이 가장 인접한 상태라고 생각할 수 있을 듯 합니다. 

 

실제로 테스트 해봤을 때에도 [3]의 정확도와 속도가 월등했습니다. 

 

* n = 100정도에서는 변화를 볼 새도 없이 빨리 끝나버려서 100ms 단위로 업데이트했습니다. 

 

---

다음 상태가 이득일 확률

 

\( P(e1, e2) = e^{(e2 - e1) / (K \times T) } \)

 

e1 = 현재 상태의 평가함수 값, e2 = 다음 상태의 평가함수 값이라고 정의했을 때 위의 식을 통해 확률을 계산합니다.

K는 볼츠만 상수, T는 온도를 의미합니다. 위 식은 볼츠만 맥스웰 분포에 근거합니다. 

 

[Concept]의 설명처럼 \( e1 \leq e2 \)인 경우 P(e1, e2)는 항상 1이상이기 때문에 전이하고 

\( e1 > e2 \)인 경우(\( P(e1, e2) \in [0, 1) \)인 경우) 확률적으로 전이합니다. 

 

double e1 = f(now);
double e2 = f(nxt);
double P = exp((e2 - e1) / (K * T));
if(rnd.nxtDouble(0, 1) <= P) now = nxt;

 

---

평가 함수

 

평가함수의 값이 클수록 좋은 상태로 정의하는 것이 보편적입니다. 

 

예를 들어 TSP에서는 경로의 길이가 짧을 수록 좋기 때문에 \(f(now) =  -1 \times \) 경로의 길이, 

3 sat에서는 참인 절의 개수로 정의할 수 있습니다. 

 

---

볼츠만 상수, 시작온도, 온도 감률

 

\( P(e1, e2) = e^{(e2 - e1) / (K \times T) } \)

 

P의 값에 \( (e2 - e1) / (K \times T) \)이 큰 영향을 주기 때문에 지역 최소에 빠지지 않도록 

랜덤하게 이득이 아닌 경우도 전이할 수 있는 상수를 잘 찾아야합니다. 

그에 맞게 (e2 - e1)의 기댓값과 K, T의 비율을 적절히 조절하면됩니다. 

 

---

TSP 코드

 

TypeScript로 작성했습니다.

Simulated Annealing 코드는 function* simulated_annealing 부분에 있습니다.

 

export { };

const IT = 1000000;
const BASE = 20;
const R = 5;

function nodeDraw(n: number, mp: { x: number, y: number }[]) {
    const cvs = document.getElementById("asdf")! as HTMLCanvasElement;
    const ctx = cvs.getContext('2d')!;
    const __nodeDraw = (p: number, q: number) => {
        ctx.beginPath();
        ctx.arc(p * R + BASE, q * R + BASE, 10, 0, Math.PI * 2, false);
        ctx.stroke();
        ctx.fillStyle = 'blue'; ctx.fill();
    };
    for (let i = 0; i < n; i++) __nodeDraw(mp[i].x, mp[i].y);
}

function edgeDraw(mp: { x: number, y: number }[], edges: Array<[number, number]>) {
    const cvs = document.getElementById("asdf")! as HTMLCanvasElement;
    const ctx = cvs.getContext('2d')!;
    const __edgeDraw = (edge: [number, number]) => {
        const currentMps = [mp[edge[0]], mp[edge[1]]];
        ctx.beginPath();
        ctx.moveTo(BASE + currentMps[0].x * R, BASE + currentMps[0].y * R);
        ctx.lineTo(BASE + currentMps[1].x * R, BASE + currentMps[1].y * R);
        ctx.strokeStyle = 'black';
        ctx.lineWidth = 4;
        ctx.stroke();
    };
    for (const edge of edges) __edgeDraw(edge);
}

function getCanvas() {
    const cvs = document.getElementById("asdf")! as HTMLCanvasElement;
    const ctx = cvs.getContext('2d')!;
    ctx.clearRect(0, 0, cvs.width, cvs.height);
}

function render
    (
        n: number,
        mp: { x: number, y: number }[],
        edge: Array<[number, number]>
    ) {
    getCanvas();
    edgeDraw(mp, edge);
    nodeDraw(n, mp);
}

function frame
    (
        gen: Generator<Array<[number, number]>, void, unknown>,
        n: number,
        mp: { x: number, y: number }[]
    ) {
    const edge = gen.next();
    if (edge.value)
        render(n, mp, edge.value);
    setTimeout(() => {
        frame(gen, n, mp);
    }, 100);
}

function* simulated_annealing(n: number, mp: { x: number, y: number }[]) {
    let T = n / 2;
    const K = 1;
    const D = 0.9999;
    let e1 = 0;
    let e2 = 0;
    const perm: number[] = [];
    mp.sort((a: { x: number, y: number }, b: { x: number, y: number }) => a.x - b.x);
    for (let i = 0; i < n; i++) perm[i] = i;
    const getidx = (idx: number) => { return (idx + n) % n; };
    const dist = (p: number, q: number) => {
        p = getidx(p); q = getidx(q);
        const a = mp[perm[p]].x - mp[perm[q]].x;
        const b = mp[perm[p]].y - mp[perm[q]].y;
        return Math.sqrt(a * a + b * b);
    };
    for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) T = Math.max(T, dist(i, j));
    const Swap = (p: number, q: number) => {
        p = getidx(p); q = getidx(q);
        if (p > q) {
            const tmp = p;
            p = q;
            q = tmp;
        }
        for (let i = 0; p + i < q - i; i++) {
            const tmp = perm[p + i];
            perm[p + i] = perm[q - i];
            perm[q - i] = tmp;
        }
    };
    let edge: [number, number][] = [];
    const cost = () => {
        let ret = 0;
        for (let i = 0; i < n; i++) ret += dist(i - 1, i);
        return ret;
    };
    e1 = cost();
    for (let tc = 0; tc < IT; tc++) {
        for (let i = 0; i < 1000; i++) {
            const p: number = Math.floor(Math.random() * n);
            const q: number = Math.floor(Math.random() * n);
            e1 = cost();
            Swap(p, q);
            e2 = cost();
            const newE: [number, number][] = [];
            for (let i = 0; i < n; i++) {
                newE.push([perm[getidx(i - 1)], perm[i]]);
            }
            const x: number = Math.exp((e1 - e2) / (K * T));
            if (e2 < e1 || x >= Math.random()) edge = newE;
            else Swap(p, q);
            T *= D;
        }
        yield edge;
    }
}

{
    const t = document.getElementById("submit");
    if (t) {
        t.onclick = () => {
            const nodeCount = document.getElementById("nodeInput") as HTMLInputElement | null;
            const edgeData = document.getElementById("edgeInput") as HTMLInputElement | null;
            if (nodeCount && edgeData) {
                const n = parseInt(nodeCount.value.trim());
                const xyz = edgeData.value.trim().split(/\s/).map(qwer => parseInt(qwer));
                if (n * 2 == xyz.length) {
                    const asdf: { x: number, y: number }[] = [];
                    for (let i = 0; i < n; i++) {
                        asdf[i] = {
                            x: xyz[i * 2],
                            y: xyz[i * 2 + 1]
                        };
                    }
                    frame(simulated_annealing(n, asdf), n, asdf);
                } 
            } 
        };
    }
    console.log("1");
}