Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

2013 학사 논문

No description
by

yang taemin

on 30 September 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 2013 학사 논문

Background photo by t.shigesa
Part 3.
⇒ 동전들을 이용하여 거스름 돈 41 센트를 만드는데,
25센트, 10센트, 4센트 자리 동전이 주어졌다고 가정한다.

⇒ 그래서 Greedy heuristic algorithm으로 풀어보면 25센트, 10센트, 4센트를
선택하면 남은 2센트는 거슬러 주지 못하게 된다.





⇒ 그러므로 해답은 25센트 1개와 4센트 동전 4개를 선택하는 것이다
Part 1.
Part 2.
End .
20071164 양태민
20103251 배상호
조합최적화
(combinatorial optimization)
문제에대한 알고리즘의 비교 연구
< 목 차 >
1. 용어설명

(a) 조합최적해 (Combinatorial Optimization) 란?
(b) Big-O 표기법
(c) Grobal Optimum vs Local Optimum
(d) Exact Method vs Heuristic Method
2. Exact Method

(a) Summary of BNB (Branch And Bound) Algorithm
(b) Oprimality Test
(c) Representable Branch rule 1), 2)
(d) BNB’s simple example
3. Heuristic Method

(a) Definition
(b) Greedy Heuristic’s definition
(c) Greedy Heuristic’s example
4. Metaheuristic Method (GA / TS / SA)
(a) Definition
< 목 차 >
5. Genetic Algorithm

(a) Background & Definition
(b) GA’s step
- Crossover & Mutation & Selection
- Genetic Algorithm’s example 1), 2)
6. Tabu Search

(a) Background & Definition
(b) TS’s step
- Tabu Search’s example
- Tabu Search Applications
7. Simulated Annealing

(a) Background & Definition / Survey of annealing algorithm
(b) SA’s step
- Simulated Annealing’s example 1), 2)
8. 미래 연구 방향 (Future Research)

(a) Metaheuristic’s Advantage & defect
(b) Hybrid Metaheuristic ( TS+SA / TS+GA / GA+SA )
(c) TS + DM(DataMining)
(d) BNB
1. 용어설명
(a). 조합최적화 (Combinatorial Optimization)
- 응용수학과 전산학에서 조합최적화는 최적화 문제의 일종으로서, 운용 과학,
알고리즘 이론, 계산 복잡도 이론과 관련되어 있고,
인공지능, 소프트웨어 공학과 영역이 겹친다. 조합최적화에서는
일반적으로 어렵다고 보는 문제를 풀려고 하는데,
어려운 문제들은 보통 문제 공간이 크기 때문에
조합최적화 알고리즘은 문제 공간을 좁히거나 탐색 효율을 높이는 데 중점을 둔다.
(b). Big – O 표기법
- O(logN) : 처리 데이터의 양이 증가할 수록 실행시간이 약간씩 증가한다.
하지만 logN의 그래프가 그렇듯이 증가 폭이 급격히 증가하진 않는다.
일반적으로 좋은 효율의 알고리즘이 여기에 해당한다.
- O(N^3) : 데이터에 양에 대해 세제곱 만큼 시간이 증가하기에
좋은 알고리즘이 아니다. For문이 세번 중첩되면 이꼴이 난다
.

- O(2^N) : 2의 N제곱이 되는 알고리즘은 거의 최악의 알고리즘 중 하나이다.
f2
f1
- Global Optimum은 시스템 차원에서 전략을 탐색하여 전체의 구성을 주도하여
최적의 답을 찾는 것이라면, Local Optimum은 한 부분의 최적화를 통해서
전체로 확장시켜 그 최적의 답을 찾는다.
* Local vs. Global optimum(Continuous Case)
f3
local optimum -> Heuristic Alg.
Global optimum :
Max{ f1, f2, f3}
-> Exact Alg.

* Local vs. Global optimum(Discrete Case)
* Local optimum(Greedy heuristic alg.)
* Global optimum(BNB alg. Exact Method)
(d) Exact Method vs Heuristic Method
2. Exact Method
(a) Summary of BNB (Branch And Bound) Algorithm
Initialization Step : Set Zu=∽(minimization case)
Branch Step : Use some branch rule to select one of the remaining
subsets and partition it into two or more
new subsets of solutions.
Bound Step : For each new subset, obtain a lower bound Zl on the
value of objective funtion for the
feasible solutions in the subset.
Fathoming Step : For each new subset,
exclude it from further consideration
by the following fathoming tests :

Test 1. Fathom the subsets with Zl >= Zu
Test 2. Fathom the subsets with no feasible solutions.
Test 3. Fathom the new feasible solution with Zl < Zu
(reset Zu = Zl and apply Test 1.)
(d) BNB’s simple example (Assignment Prob.)
3. Heuristic Method
(a) Definition
- Heuristic은 경험에 기반하여 문제를 해결하거나 학습하거나 발견해 내는 방법을 말한다.
컴퓨터과학 또는 공학에서는 한정된 시간 내에 수행하기 위해 최적의 해
대신 현실적으로 만족할 수 있는 해를 구하는 방법이다.
컴퓨터과학 또는 공학에서 Heuristic Algorithm을 이용하여
실제로 많은 시나리오가 존재할 수 있는 문제의 용인할 수 있는해(Solution)을
찾아내고 있다. 하지만 그 해의 최적임을 밝히는 형식을 갖춘 증명은 하지 않는다.
증명을 통해서 얻어진 최적의 해는 아니지만
최적의 해에 근사한 해일 것이다. Heuristic은 전형적으로 최적의 해를 찾는
알려진 방법이 없을 때 사용된다.
- Planning and Scheduling
- Transportation and Routing
→ Traveling Salesman
- Telecommunication
- Logic and Artificial Intelligence
- Design
→ Transport Network Design
- Graph Optimization
- Production and Inventory and Investment
- Technology
- Location and Allocation
- General Combinatorial
- Parallel Computing
- Optimization on Structures
- Specialized Techniques and General Zero-One Solvers
- Tabu Search Applications
- Greedy Heuristic Algorithm 이라고 하며, 흔히들 탐욕 알고리즘 이라고 한다.
탐욕 알고리즘의 정의는.
현재의 최선의 선택이 전체의 최선의 선택이다 라는 가정하에 만들어진 알고리즘.
즉, 문제를 푸는 과정에서 최적의 해를 구하기 위해 매 선택의 순간 마다 가장 좋은 것을
택하는 알고리즘이다. 그러므로 모든 경우의 수에 대한 테이터를 철저히 검색하지 않기 때문에
많은 경우 최적의 해를 찾지 못한다.
(b) Greedy Heuristic’s definition
End.
- Genetic Algorithm’s simple example 2)
- Genetic Algorithm’s simple example 1)
◦ 유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서
존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로,
최적화 문제를 해결하는 기법의 하나이다.
생물의 진화를 모방한 진화 연산의 대표적인 기법으로,
실제 진화의 과정에서 많은 부븐을 차용하였다.

즉, 자연계에서 생물의 진화(Evolution)의 메커니즘을 공학적으로 모델링 하여
문제를 해결하는 방법이다.

Genetic Algorithm의 대표적인 방법으로는 변이(Mutation), 교배(Crossover)
연산 등이 존재한다.
또한, 세대 · 인구 등의 용어도 문제 풀이 과정에서 사용된다.
(a) Background & Definition
5. Genetic Algorithm
- 그러나, 10년 아니면 20년 후쯤에
엄청난 사양의 컴퓨터가 나와 모든 문제를 BNB로 해결할수 있다면,
Metaheuristic에 대한 연구 보다는
Heuritstic → Metaheuristic 으로 연구가 발전 된 것처럼 BNB에 대한 연구가
진행 될 것이다.
- 지금까지 Heuristic 과 Metaheuristic 이 활발하게 연구 중인것은
BNB가 최적해를 풀어내는데, 많은 시간과 많은 양의 반복수 등등이 제한이 되어
복잡한 많은 문제를 해결하는 데에는 현존하는 컴퓨터능력으로는 불가능한 부분이
있기 때문이다.
(d) BNB
- Simulated Annealing은 이름 글대로 금속학에서의 냉각과정에서 유래되었는데,
금속 결정의 원활한 형성을 위해 가열과 냉각을 적절히 조절해야 하는 기술을
최적화 이론에 적용한 것이다.
- 이 알고리즘은 1983년 크릭페트릭(Krikpatrick) 등에 의해 처음으로 제안되었다.
- 고온 물질의 분자가 식어가면서 (annealing) 점차 안정화되어 가는 과정을
묘사(Simulation)하여 광역적 최적화(Global optimization)를 수행하는
알고리즘이다.
(a) Background & Definition
7. Simulated Annealing
- Tabu Search는 인간의 기억과정을 이용하였고 인공지능분야에서 선택된 개념에
기초를 둔 기법
- Tabu Search는 복잡한 해 영역에서 좋은 해를 얻기 위해 탐색을 유도하는
일반적인 휴리스틱 과정이다.
- 1960년대 후반과 1970년대 초반에 그 기원을 두고
Fred W.Glover에 의해 1986년에 만들어 졌으며, 1989년에 공식화가 되었다.
(a) Background & Definition
6. Tabu Search
- 선택의 방법은 일반적으로 적응도가 높은 염색체를 살리는 방향으로 이루어진다.
따라서 자동적으로 적응도가 낮은 염색체들은 도태된다. 간단한 방법으로는 적응도에 비례하는
확률로 개체를 살아남게 하는 방법이 있다.
(이러면 자동으로 적응도가 높은 애들이 살아남게 된다.)
◦ Selection
- 변이(Mutation)는 교차 후 발생하는데 매우 낮은 확률로 유전자가 달라지는 것이다.
(0은 1로, 1은 0으로 변형 되는 방법이 있다.)
따라서, 초기의 모집단이 답과 매우 떨어져 있는 구성이더라도 변이를 통해 최적해에
근사될 수 있는 것이다.
◦ Mutation
교배(Crossover)의 방법은
⇒ 단순 교차, 다점 교차, 균등 교차, 싸이클 교차, 순서 교차, PMX, 산술적 교차, 휴리스틱,
간선 재결합 등이 있다.
◦ Crossover’s method
부모 개체를 선별하는 방법은 여러가지가 있지만, 일반적으로 랜덤한 방식을 사용한다.
부모 개체로 부터 태어나는 자식은 부모 개체의 유전형을 절반씩 나눠 갖는다.
예를 들어, 부모 개체가 (0011), (1100) 이라면, 그 자식 개체는 (0000) 혹은 (1111)이 될 것이다.
◦ Crossover
- Crossover & Mutation & Selection
X
Example 2)
If only the shown boxes are available → 0/1 Knapsack Prob.
◦ 수식으로 보여진 예제
◦ 생활에서의 예제
Example 1) “ 거스름돈 문제 “
⇒ 동전들을 이용하여 거스름 돈 41 센트를 만든다. 이 때 사용되는 동전의 개수를
최소로 하여야한다. 25센트, 10센트, 5센트, 1센트 자리 동전이 주어졌다고 가정한다.

⇒ 위 문제를 ‘Greedy Heuristic Algorithm’ 으로 풀어보면 거술러 주어야 하는 값을 넘지
않으면서 가장 큰 동전을 무조건 선택하는 것이다. 그러므로 가장 큰 25센트를 먼저 선택하면
16센트가 남고 여기서 10센트를 선택한다. 그러면 6센트가 남고 5센트를 선택하면 1센트가 남게
되어 값이 맞아 떨어지므로 해가 구해졌다.
(c) Greedy Heuristic’s example
(a). 조합최적화 (Combinatorial Optimization)

- 응용수학과 전산학에서 조합최적화는 최적화 문제의 일종으로서, 운용 과학, 알고리즘 이론, 계산 복잡도 이론과 관련되어 있고, 인공지능, 소프트웨어 공학과 영역이 겹친다. 조합최적화에서는 일반적으로 어렵다고 보는 문제를 풀려고 하는데, 어려운 문제들은 보통 문제 공간이 크기 때문에 조합최적화 알고리즘은 문제 공간을 좁히거나 탐색 효율을 높이는 데 중점을 둔다.
조합 최적화 알고리즘은 보통 NP-Exact method를 다루는데, 일반적으로 쉽게 풀수 없다고 보고 있다. 그 이유는 n개의 문제에 대해서 평균적으로 O(2^n)번 시행해야 되기 때문에 많은 양의 문제 즉, 예를 들어 1000개의 문제를 해결하기 위해서는 평균 100만번의 시행횟수가 생기기 때문에 현존 하는 컴퓨터로는 해결하기가 어려운 부분이 있다. 그러나 복잡도 이론의 여러 근사에 따른 몇몇 특수한 경우에는 효율적으로 풀 수 있다.
Simulated Annealing 으로 경로를 탐색하면서 나온 과정들
Simulated Annealing 으로 구한
최적의 경로
Simulated Annealing 으로 경로를 탐색하면서 나온 과정들
Simulated Annealing 으로 구한
최적의 경로
⊙ Linda (1987)
- the application of the annealing algorithm to the construction
of exact optimal designs.
⊙ Lundy and Mees (1986)
- Prove that the algorithm converages with probability close to 1.
⊙ Lundy (1985)
- Applications of the annealing algorithm to combinatorial
problems in statistics.
ex ) evolutionary tree problem
⊙ Cerny (1985)
- Develop an efficient simulated annealing algorithm to the TSP
⊙ Bonomi and Lutton (1984)
- N-city TSP
⊙ Krikpatrick, Gelatt & Vecchi (1982, 1983)
- The annealing idea was first applied to combinatorial problems.
⊙ Metropolis (1953)
- Metropolis algorithm (Finding the thermal equilibrium)
- Survey of Annealing Algorithm
◦ Metaheuristic 기법에는 Genetic Algorithm / TABU search / Simulated Annealing
이 있다. 이들 기법들은 각기 다른 특성이 있지만 공통점으로 개념과 이론이 단순하고 해공간의
탐색성능이 우수하여 공학, 자연과학, 경영학, 사회과학 등의 최적화 분야 또는 의사결정분야에
응용이 가능하다. 이들 기법은 각기 독립적으로 여러 분야에 적용될 수 있을 뿐만 아니라 각 기법의
단점을 상호보완하면서, 서로 장점들을 결합하여 함께 적용될 수 있다.
◦ Metaheuristic은 조합 문제와 같이 컴퓨팅 비용이 많이 드는 문제가 있는 일반적인 문제들을
사용자에게서 주어진 규칙들을 조합하여 해결하는 확률 기반의 heuristic 방법이다.
Heuristic은 해결하고자 하는 문제마다 각기 그 특성에 맞추어 개발해야하는 어려움을 가지고 있다.
이러한 어려움을 극복하기 위하여 특정문제가 갖는 정보에 크게 구속되지 않고 다양한 문제에 적용
가능한 상위 수준의 Metaheuristic을 사용해야한다.
Metaheuristic을 사용하는 대부분은 조합 최적화 문제를 대상으로 하고 있지만 부울 방정식을
푸는 것과 같은 Metaheuristic의 형식으로 고쳐 쓸 수 있는 문제들도 해결할 수 있다.
(a) Definition
4. Metaheuristic Method (GA / TS / SA)
- Heuristic은 경험에 기반하여 문제를 해결하거나 학습하거나 발견해 내는 방법을 말한다.
컴퓨터과학 또는 공학에서는 한정된 시간 내에 수행하기 위해 최적의 해
대신 현실적으로 만족할 수 있는 해를 구하는 방법이다.
컴퓨터과학 또는 공학에서 Heuristic Algorithm을 이용하여 실제로 많은 시나리오가 존재할 수 있는
문제의 용인할 수 있는해(Solution)을
찾아내고 있다. 하지만 그 해의 최적임을 밝히는 형식을 갖춘 증명은 하지 않는다.
증명을 통해서 얻어진 최적의 해는 아니지만
최적의 해에 근사한 해일 것이다. Heuristic은 전형적으로 최적의 해를 찾는 알려진 방법이 없을 때
사용된다.
(a) Definition
3. Heuristic Method
CGH
( Computer-Generated Hologram )
Simulated Annealing
Tabu Search
Random initial pattern
- Tabu Search 과 Simulated Annealing을
이용한 컴퓨터 형성 홀로그램의 성능 향상
* TS+SA
(b) Hybrid Metaheuristic ( TS+SA / TS+GA / GA+SA )
초기 임으로 정해진 경로
각각의 경로의 cost
N = 20
Example 2)
- Simulated Annealing’s Example 2)
q2 = 1010110
P2 = 1100110
P1 = 1010101
한 개의 교배점(Crossover Site)을 기준으로 두 부모의 해를 번갈아 받아 온다.


Example )
부모 p1,p2 의 염색체가 각각 다음과 같고 교배점이 3일 때, 두 부모의 자식 q1은 다음과 같다.
◦ 단순 교차(Simple Crossover)
- Crossover’s method

1. 41 – 25 = 16

2. 16 – (4 * 4) = 0
1. 41 – 25 = 16
2. 16 – 10 = 6
3. 6 – 4 = 2
⇒ 동전들을 이용하여 거스름 돈 41 센트를 만드는데,
25센트, 10센트, 4센트 자리 동전이 주어졌다고 가정한다.

⇒ 그래서 Greedy heuristic algorithm으로 풀어보면 25센트, 10센트, 4센트를 선택하면
남은 2센트는 거슬러 주지 못하게 된다.





⇒ 그러므로 해답은 25센트 1개와 4센트 동전 4개를 선택하는 것이다
◦ Greedy heuristic algorithm이 실패하는 경우
- 후보 해결방법들의 모집단을 갖고 탐색해 나간다. (한 개의 해결방법이 아닌 )
- 해결방법의 모집단을 사용함으로써 Local Opt.에 빠지는 위험을 방지할 수 있다.
- 현실 세계에 존재하는 문제 중 대상으로 하는 문제를 유전자형으로 바꾸는 과정이 간단하지 않다.
* Genetic Algorithm
- 탐색 공간이 큰 Traveling Salesman Problem등의 경로 최적화에 효과적
- 확률을 이용하여 국소 최적해를 피할 수 있으나 일반적으로 계산시간이 많이 걸린다.
* Simulated Annealing
- 최적화 과정에서 사용되는 메모리는 과거로부터 얻은 값을 저장함으로써
재탐색을 하지 않으므로 탐색의 효율을 높일 수 있다.
- 국소 최적해(Local Opt.)에 빠질 위험이 적으면서 전역 탐색이 가능하다.
* Tabu Search
(a) Metaheuristic’s Advantage & defect
8. 미래 연구 방향 (Future Research)
* 교배점은 랜덤하게 결정된다.
q2 = 1010101
P2 = 1100110
P1 = 1011101
단순 교차와 비슷하나 여러 개의 교배점을 가진다.


Example )
부모 p1,p2 의 염색체가 각각 다음과 같고 교배점이 3,5일 때, 두 부모의 자식 q1은 다음과 같다.
◦ 다점 교차(Multipoint Crossover)
각각의 경로의 cost
초기 임으로 정해진 경로
N = 7
6
5
4
3
2
1
0
Example 1)
- Simulated Annealing’s Example
If termination criterion is satisfied,
then stop with the best so far.
If the best neighbor is better than the current best, then it is replaced.
Select the best neighbor
(Which is not tabu list or satisfies the aspiration)
Update the tabu list
Generate neighbor of current solution by a neighborhood structure.
- Tabu Search’s simple step
NO
NO
YES
NO
YES
YES
If(rand()<exp[-∆/T])
END
If(∆ > 0)
T = aT
C++
S = S′
C = ∆ + C
If(∆ < 0)
∆ = cost(s′) – cost(s)
S′ = rand(S)
S = rand(S)
T = 100
a = 0.999
C = 1
START
(b) SA’s step
X2= X3 = 1 ⇒ 11
Z = 34
X3= X4 = 1 ⇒ 7
Z = 20
X1= X2 = 1 ⇒ 12
Z = 38
X1= X4 = 1 ⇒ 8
Z = 34
X4 = 1 ⇒ 3
Z = 8
X2 = 1 ⇒ 7
Z = 22
X1= X2 = X4 = 1 ⇒ 15
Z = 46
X2 = X4 = 1 ⇒ 10
Z = 30
X2 = X3 = X4 = 1 ⇒ 14
Z = 42
(0110)2
(0011)2
(1100)2
(1001)2
(0001)2
(0100)2
(1101)2
Subtract
Add
Add + Sub
(0111)2
(0101)2
- Tabu Search’s example
* 여기서 첫번째로 Tabu list에 올라간 (0111)2 이 위 식에
최적합(조건식에도 맞고, 해도 그중 가장 크다)이기에 여기서
Tabu Search는 종료 되게 된다.
Update the tabu list
X2= X3 = 1 ⇒ 11
Z = 34
X1= X2 = 1 ⇒ 12
Z = 38
X3= X4 = 1 ⇒ 7
Z = 20
X1= X4 = 1 ⇒ 8
Z = 34
X4 = 1 ⇒ 3
Z = 8
X2 = 1 ⇒ 7
Z = 22
X1= X2 = X4 = 1 ⇒ 15
Z = 46
X2 = X4 = 1 ⇒ 10
Z = 30
X2 = X3 = X4 = 1 ⇒ 14
Z = 42
(0110)2
(0011)2
(1100)2
(1001)2
(0001)2
(0100)2
(1101)2
Subtract
Add
Add + Sub
(0111)2
(0101)2
(d) BNB’s simple example (Assignment Prob.)
YES
NO

종결 조건
적합도 평가
돌연변이 (Mutation)
교배 (Crossover)
선택, 재생 (Selection)
적합도 평가
초기 집단 생성
시 작
(b) GA’s step
3/12
5/12
2/12
1/12
1/12
4/12
6
5
4
3
1
1/12
1/12
1/12
2/12
3/12
6
5
4
3
2
1
0
* Example )
- 예를 들어, TSP를 TS로 해결할 경우에는 각 지나간 node 들은 list에 저장하여 한 번 지나간
경로에 대해서는 탐색을 하지 않는다.
- DataMining 이란 간단히 말해서 많은 데이터 가운데 숨겨져 있는 유용한 상관관계를 발견하여,
미래에 실행 가능한 정보를 추출해 내고 의사 결정에 이용하는 과정을 말한다.
(c) TS + DM(DataMining)
f(x) 에 적용
Feasible
Solution
&
Global Opt.
Mutation
16
31
25
27
(10000)2
(11111)2
(11001)2
(11011)2
Selection
(10000)2
(11011)2
(11001)2
(11011)2
16
27
25
12
Selection
Crossover
(10011)2
(11000)2
(11000)2
(01101)2
Feasible
solution
(10011)2
(11000)2
(11000)2
(01101)2
(10000)2
(11011)2
(11001)2
(01100)2
x
0.31
0.06
0.49
0.14
361/1170
64/1170
576/1170
169/1170
361
64
576
169
19
8
24
13
(10011)2
(01000)2
(11000)2
(01101)2
Feasible
solution
(11100)2
(00100)2
(11111)2
(11011)2
(11100)2
(00100)2
(11101)2
(11011)2
(11100)2
(00100)2
(11101)2
(11011)2
(11100)2
(00101)2
(11100)2
(11011)2
(11100)2
(00101)2
(11100)2
(11011)2
f(x) 에 적용
Feasible
Solution
&
Global Opt.
Mutation
28
4
31
27
Selection
Crossover
Feasible
solution
x
0.06
0.14
0.41
0.39
3/49
7/49
20/49
19/49
3
7
20
19
9
5
28
27
(01001)2
(00101)2
(11100)2
(11011)2
(b) Greedy Heuristic’s definition
- Greedy Heuristic Algorithm 이라고 하며,
흔히들 탐욕 알고리즘 이라고 한다.
탐욕 알고리즘의 정의는. 현재의 최선의 선택이 전체의 최선의 선택이다
라는 가정하에 만들어진 알고리즘.
즉, 문제를 푸는 과정에서 최적의 해를 구하기 위해 매 선택의 순간 마다
가장 좋은 것을 택하는 알고리즘이다.
그러므로 모든 경우의 수에 대한 테이터를 철저히 검색하지 않기 때문에
많은 경우 최적의 해를 찾지 못한다.
(c) Greedy Heuristic’s example
Example 1) “ 거스름돈 문제 “
⇒ 동전들을 이용하여 거스름 돈 41 센트를 만든다. 이 때 사용되는 동전의 개수를
최소로 하여야한다. 25센트, 10센트, 5센트, 1센트 자리 동전이 주어졌다고 가정한다.

⇒ 위 문제를 ‘Greedy Heuristic Algorithm’ 으로 풀어보면 거술러 주어야 하는 값을 넘지
않으면서 가장 큰 동전을 무조건 선택하는 것이다. 그러므로 가장 큰 25센트를 먼저 선택하면
16센트가 남고 여기서 10센트를 선택한다. 그러면 6센트가 남고 5센트를 선택하면 1센트가 남게
되어 값이 맞아 떨어지므로 해가 구해졌다.
* 생활에서의 예제
* Greedy heuristic algorithm이 실패하는 경우
* 수식으로 보여진 예제
Example 2)
If only the shown boxes are available → 0/1 Knapsack Prob.
X
4. Metaheuristic Method (GA / TS / SA)
(a) Definition
- Metaheuristic은 조합 문제와 같이 컴퓨팅 비용이 많이 드는 문제가 있는 일반적인 문제들을
사용자에게서 주어진 규칙들을 조합하여 해결하는 확률 기반의 heuristic 방법이다.
Heuristic은 해결하고자 하는 문제마다 각기 그 특성에 맞추어 개발해야하는 어려움을 가지고 있다.
이러한 어려움을 극복하기 위하여 특정문제가 갖는 정보에 크게 구속되지 않고 다양한 문제에 적용
가능한 상위 수준의 Metaheuristic을 사용해야한다.
Metaheuristic을 사용하는 대부분은 조합 최적화 문제를 대상으로 하고 있지만 부울 방정식을
푸는 것과 같은 Metaheuristic의 형식으로 고쳐 쓸 수 있는 문제들도 해결할 수 있다.
- Metaheuristic 기법에는 Genetic Algorithm / TABU search / Simulated Annealing
이 있다. 이들 기법들은 각기 다른 특성이 있지만 공통점으로 개념과 이론이 단순하고 해공간의
탐색성능이 우수하여 공학, 자연과학, 경영학, 사회과학 등의 최적화 분야 또는 의사결정분야에
응용이 가능하다. 이들 기법은 각기 독립적으로 여러 분야에 적용될 수 있을 뿐만 아니라 각 기법의
단점을 상호보완하면서, 서로 장점들을 결합하여 함께 적용될 수 있다.
5. Genetic Algorithm
(a) Background & Definition
- 유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서
존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로,
최적화 문제를 해결하는 기법의 하나이다.
생물의 진화를 모방한 진화 연산의 대표적인 기법으로,
실제 진화의 과정에서 많은 부븐을 차용하였다.

즉, 자연계에서 생물의 진화(Evolution)의 메커니즘을 공학적으로 모델링 하여
문제를 해결하는 방법이다.

Genetic Algorithm의 대표적인 방법으로는 변이(Mutation), 교배(Crossover)
연산 등이 존재한다.
또한, 세대 · 인구 등의 용어도 문제 풀이 과정에서 사용된다.
(b) GA’s step
- Crossover & Mutation & Selection

- 부모 개체를 선별하는 방법은 여러가지가 있지만, 일반적으로 랜덤한 방식을 사용한다.

부모 개체로 부터 태어나는 자식은 부모 개체의 유전형을 절반씩 나눠 갖는다.

예를 들어, 부모 개체가 (0011), (1100) 이라면, 그 자식 개체는 (0000) 혹은 (1111)이 될 것이다.
교배(Crossover)의 방법은
⇒ 단순 교차, 다점 교차, 균등 교차, 싸이클 교차, 순서 교차, PMX, 산술적 교차, 휴리스틱,
간선 재결합 등이 있다.

* Crossover
* Crossover’s method
- Crossover’s method
한 개의 교배점(Crossover Site)을 기준으로 두 부모의 해를 번갈아 받아 온다.


Example )
부모 p1,p2 의 염색체가 각각 다음과 같고 교배점이 3일 때, 두 부모의 자식 q1은 다음과 같다.
* 단순 교차(Simple Crossover)
- Crossover’s method
단순 교차와 비슷하나 여러 개의 교배점을 가진다.


Example )
부모 p1,p2 의 염색체가 각각 다음과 같고 교배점이 3,5일 때, 두 부모의 자식 q1은 다음과 같다.
* 다점 교차(Multipoint Crossover)
* 교배점은 랜덤하게 결정된다.
- 변이(Mutation)는 교차 후 발생하는데

매우 낮은 확률로 유전자가 달라지는 것이다.

(0은 1로, 1은 0으로 변형 되는 방법이 있다.)
따라서, 초기의 모집단이 답과 매우 떨어져 있는 구성이더라도 변이를 통해 최적해에
근사될 수 있는 것이다.
- 선택의 방법은 일반적으로

적응도가 높은 염색체를 살리는 방향으로 이루어진다.


따라서 자동적으로 적응도가 낮은 염색체들은 도태된다. 간단한 방법으로는 적응도에 비례하는
확률로 개체를 살아남게 하는 방법이 있다.
(이러면 자동으로 적응도가 높은 애들이 살아남게 된다.)

* Mutation
* Selection
- Genetic Algorithm’s simple example 1)
- Genetic Algorithm’s simple example 1)
- Genetic Algorithm’s simple example 2)
- Genetic Algorithm’s simple example 2)
6. Tabu Search
(a) Background & Definition
- 1960년대 후반과 1970년대 초반에 그 기원을 두고
Fred W.Glover에 의해 1986년에 만들어 졌으며, 1989년에 공식화가 되었다.
- Tabu Search는 인간의 기억과정을 이용하였고 인공지능분야에서 선택된 개념에
기초를 둔 기법
- Tabu Search는 복잡한 해 영역에서 좋은 해를 얻기 위해 탐색을 유도하는
일반적인 휴리스틱 과정이다.
- Tabu Search’s simple step
- Tabu Search’s example
- Tabu Search’s example
* 여기서 첫번째로 Tabu list에 올라간 (0111)2 이 위 식에
최적합(조건식에도 맞고, 해도 그중 가장 크다)이기에 여기서
Tabu Search는 종료 되게 된다.
- Tabu Search Applications
- Planning and Scheduling
- Transportation and Routing

→ Traveling Salesman
- Telecommunication
- Logic and Artificial Intelligence
- Design

→ Transport Network Design
- Graph Optimization
- Production and Inventory and Investment
- Technology
- Location and Allocation
- General Combinatorial
- Parallel Computing
- Optimization on Structures
- Specialized Techniques and General Zero-One Solvers
7. Simulated Annealing
- Simulated Annealing은 이름 글대로 금속학에서의 냉각과정에서 유래되었는데,
금속 결정의 원활한 형성을 위해 가열과 냉각을 적절히 조절해야 하는 기술을
최적화 이론에 적용한 것이다.
- 이 알고리즘은 1983년 크릭페트릭(Krikpatrick) 등에 의해 처음으로 제안되었다.
- 고온 물질의 분자가 식어가면서 (annealing) 점차 안정화되어 가는 과정을
묘사(Simulation)하여 광역적 최적화(Global optimization)를 수행하는
알고리즘이다.
(a) Background & Definition
- Survey of Annealing Algorithm
⊙ Linda (1987)
- the application of the annealing algorithm to the construction
of exact optimal designs.
⊙ Lundy and Mees (1986)
- Prove that the algorithm converages with probability close to 1.
⊙ Lundy (1985)
- Applications of the annealing algorithm to combinatorial problems in statistics.
ex ) evolutionary tree problem
⊙ Cerny (1985)
- Develop an efficient simulated annealing algorithm to the TSP
⊙ Bonomi and Lutton (1984)
- N-city TSP
⊙ Krikpatrick, Gelatt & Vecchi (1982, 1983)
- The annealing idea was first applied to combinatorial problems.
⊙ Metropolis (1953)
- Metropolis algorithm (Finding the thermal equilibrium)
(b) SA's Step
- Simulated Annealing’s Example 1)
각각의 경로의 cost
N = 7
Example 1)
초기 임으로 정해진 경로
- Simulated Annealing’s Example 1)
Simulated Annealing 으로 구현한
최적의 경로
N = 7
Example 1)
Simulated Annealing 으로
경로를 탐색하면서 나온 과정들
- Simulated Annealing’s Example 2)
각각의 경로의 cost
N = 20
Example 2)
초기 임으로 정해진 경로
- Simulated Annealing’s Example 2)
Simulated Annealing 으로 구현한
최적의 경로
N = 20
Example 2)
Simulated Annealing 으로
경로를 탐색하면서 나온 과정들
8. 미래 연구 방향 (Future Research)
(a) Metaheuristic’s Advantage & defect
- 후보 해결방법들의 모집단을 갖고 탐색해 나간다. (한 개의 해결방법이 아닌 )
- 해결방법의 모집단을 사용함으로써 Local Opt.에 빠지는 위험을 방지할 수 있다.
- 현실 세계에 존재하는 문제 중 대상으로 하는 문제를 유전자형으로 바꾸는 과정이 간단하지 않다.
* Genetic Algorithm
- 탐색 공간이 큰 Traveling Salesman Problem등의 경로 최적화에 효과적
- 확률을 이용하여 국소 최적해를 피할 수 있으나 일반적으로 계산시간이 많이 걸린다.
* Simulated Annealing
- 최적화 과정에서 사용되는 메모리는 과거로부터 얻은 값을 저장함으로써
재탐색을 하지 않으므로 탐색의 효율을 높일 수 있다.
- 국소 최적해(Local Opt.)에 빠질 위험이 적으면서 전역 탐색이 가능하다.
* Tabu Search
(b) Hybrid Metaheuristic
( TS+SA / TS+GA / GA+SA )
- Tabu Search 과 Simulated Annealing을 한 컴퓨터 형성 홀로그램의 성능 향상
* TS+SA
(c) TS + DM(DataMining)
* Example )
- 예를 들어, TSP를 TS로 해결할 경우에는 각 지나간 node 들은 list에 저장하여 한 번 지나간
경로에 대해서는 탐색을 하지 않는다.
- DataMining 이란 간단히 말해서 많은 데이터 가운데 숨겨져 있는 유용한 상관관계를 발견하여,
미래에 실행 가능한 정보를 추출해 내고 의사 결정에 이용하는 과정을 말한다.
(d) BNB
- 그러나, 10년 아니면 20년 후쯤에
엄청난 사양의 컴퓨터가 나와 모든 문제를 BNB로 해결할수 있다면,
Metaheuristic에 대한 연구 보다는
Heuritstic → Metaheuristic 으로 연구가 발전 된 것처럼
BNB에 대한 연구가 진행 될 것이다.
- 지금까지 Heuristic 과 Metaheuristic 이 활발하게 연구 중인것은
BNB가 최적해를 풀어내는데, 많은 시간과 많은 양의 반복수 등등이 제한이 되어
복잡한 많은 문제를 해결하는 데에는 현존하는 컴퓨터능력으로는 불가능한 부분이
있기 때문이다.
1. 용어설명
(c) Global Optimum vs Local Optimum
* Global optimum(BNB alg. Exact Method)
* Local optimum(Greedy heuristic alg.)
* Local vs. Global optimum(Discrete Case)
Full transcript