금일 세미나에서 메타휴리스틱 병렬화 연구를 소개하였다. 메타휴리스틱
병렬화 연구의 분류체계와 특징을 살펴보았고, 사례연구로 GPU 기반 simulated annealing 병렬화 연구를 소개하였다.



메타휴리스틱이란
최적화 문제 (해 탐색 또는 학습)를 제한된 시간과 자원으로
효율적으로 풀기 위한 알고리즘이다. 메타휴리스틱은 전통적인 최적화 기법으로 다루기 힘든 NP-hard 문제에 근사해를 제공할 수 있고, 다양한 문제에 범용적으로
적용할 수 있어 널리 활용된다.



하지만
대규모 데이터셋과 탐색영역이 주어질 경우 메타휴리스틱만의 성능을 보장할 수 없다. 대부분의 메타휴리스틱
알고리즘은 순차적으로 탐색하는 전략(strategies)과 가이드라인(guideline)을
제시한다. 이와 같은 내재적인 알고리즘 특성을 개선하지 못하면 고성능 컴퓨터를 사용해도 근본적인 해결이
불가능하다.



이와
같은 연산처리의 능력 한계를 뛰어넘기 위해서 최근 병렬화 연구가 활발하게 이루어지고 있다. 그 배경에는
병렬연산 처리능력이 강화된 GPU, APU와 spark, hadoop
등의 분산처리 프레임워크가 보급된 영향이 크다. 하지만,
병렬 및 분산 컴퓨팅을 기반으로 성능을 개선하기 위해서는 메타휴리스틱 알고리즘도 변경되어야 한다. 메타휴리스틱은
크게 trajectory와 population 기반의 알고리즘으로
분류되는데, 각 체계 마다 서로 다른 병렬 방법을 취할 수 있다. 병렬화
방법을 정하는데 있어서 정해야 하는 고려사항은 다음과 같다. 1) 매 탐색 시 주어진 임무(task)를 독립적인 부분임무(subtask)로 나눌 수 있는지, 2) 부분집합 합 문제(subset sum problem)에 해당하는지, 3) 병렬처리 효과를 반감시키는 특성(예시. 잦은 동기화 또는 과도한 중복 탐색)은 없는지, 4) 병렬처리가 탐험(exploration)과 활용(exploitation) 능력을 개선시키는지, 마지막으로 5) 병렬처리를 통해 알고리즘의 속도(speed)와 해의질(quality of solutions)이 얼만큼 개선되었는지 확인해야 한다.



알고리즘
병렬화 연구라는 조금은 낯선 주제에 다루었음에도 잘 경청해준 연구원들께 감사인사를 드린다.

​

메타휴리스틱은 closed form으로 해결되지 않는 복잡한 최적화
문제에 대해 합리적 시간내에 local optimal solution을 제공해준다. 메타 휴리스틱은 크게 두개의 방법 Trajectory-based
metaheuristics, Population-based metaheuristics로 나뉘게 된다.
두 방법의 큰 차이는 solution을 search하는 point를 한 개를 둘지 population을 구성할 지로 나뉘게
된다. trajectory-based에서 병렬적으로 모델을 구성하는 방법은 parallel moves model, parallel multi-start model, move acceleration
model로 구분된다. population-based는
master-slave model distributed model, cellular model로 구분된다. 새로 접하는 주제임에도 불구하고 그리고 방대한 내용이 발표에 담겨있음에도 불구하고 발표자료의 구성이 훌륭해서
이해가 수월했다. 각 방법들에 대한 간단한 활용 예시도 잘 담겨 있어서 좋았다. case study에서 trajectory의 한 알고리즘만이 담겨
있어서 population에서 많이 활용된다는 cellular
model에 대한 실험결과는 따로 확인해 보고 싶었다. 머신러닝의 알고리즘도 complexity가 높은 모델들은 방대한 데이터를 사용해서 모델의
parameter를 찾는데 시간이 많이 사용되는 경우가 많다. 또한 search space가 넓어서 효율적인 search로 효과적인 local optimal 값을 찾는 것이 중요하다. 따라서 오늘 설명된
병렬처리 방법들을 사용해서 실험할 때 효율적으로 performance를 낼 수 있는지 고민해 본다면
좋을 것 같다고 생각되었다.

오늘 상민이형께서 “Parallel metaheuristics for
large data sets”에 대해 발표해주셨다. Heuristic이란 최적화 문제에서
시간적인 제약이나 풀지 못하는 문제를 풀기 위한 알고리즘이다. Heuristic은 특별한 케이스가 아니라면
최적해를 보장해 주지 않는다. 하지만 제약안에서의 local
optimal을 구해준다. 따라서, Heuristic은
시간 또는 자원제약이 있는 상황에서 충분히 좋은 의사결정을 하기 위한 기법이다. 요즘 Graphics Processing Unit, Accelerated Processing Unit, Distributed
Computing Framework, Cloud Computing들이 발전되면서 병렬처리에 대한 관심이 증가하고 있다. Distributed Computing같은 경우 Hadoop, Spark를
예로 들수 있다. 이로인해, Heuristic에도 병렬처리가
적용이 되어 빠른 시간 내에 local optima에 빠지지 않고 최적해를 찾아가게 해주는 연구가 활발히
진행 되고 있다. 하지만, 이것도 최적해를 보장해 주지는
않는다. Parallel approach Heuristic에는 크게 두가지가 있다. 첫번째는 Trajectory-based metaheuristics가
있고 두번째는 Population-based metaheuristic이 있다. Trajectory-based metaheuristics에는 대표적으로
Hill climbing, Tabu search, Iterative local search 등이 있고 Population-based metaheuristics에는 대표적으로
Genetic algorithms, Genetic programming, Ant colony optimization, Adaptive
memory programming 등이 있다. 오늘 발표에서 상민이형께서 두가지 모두 자세하게
설명을 해주셨지만 둘 중에 Population-based metaheuristic에 관심이 많이 생겼다. Genetic algorithm으로 병렬화 한 것을 예로 들어보면
search space에서 찾아가는 처음 점을 여러 개를 둬서 각자 독립적으로 최적해를 찾아가는 것이다. 여기서 드는 의문은 처음에 search space에서 처음 점을
어떻게 두면 독립적이고 각자의 길을 잘 찾아 갈까? 가 의문이 들었다.
전반적으로 Parallel metaheuristic에 관심이 생겼고 굉장히 재미 있고 유익한
세미나였다.

최근에 센서데이터, 이미지등의 활용도가 높아 짐에 따라 대부분의 데이터의
크기가 상당히 많이 커졌다. GPU등의 하드웨어로 연산속도가 향상이 되었음에도 불구하고 큰 데이터에서는
그래도 많은 시간이 소요되는것이 사실이다. 오늘 세미나를 통해 SA,
GA등의 metaheuristic 방법론을 어떻게 병렬화 시킬수 있는지에 대한 흐름을 배울
수 있었다. 개인적으로는 높은 사양의 하드웨어로 충분히 처리가 가능하지 않을까라는 생각을 인해 병렬처리에
대해 크게 필요성을 못 느꼈다. 물론 테라바이트이상의 큰 데이터를 다룰 기회가 많치 않아서 일 수 도
있겠다. 그러나 최근 강화학습을 하면서 구축된 모델의 학습 유무를 파악하기 위해서는 최소 1~2일은 있어야 했던 사례를 비춰봤을때, 병렬화가 어느정도는 필요하다는
것을 최근에야 몸소 깨달았다. 실제 병렬처리를 깊숙히 다루는 부분은 데이터마이닝을 전공하는 사람이 다뤄야
될 부분이 아니라고 생각하지만 적어도 병렬처리에 대해서도 대략적인 방법과 개념정도는 알고있으면 추후 알고리즘 구현, 적용에서 충분히 도움이 될 수 있겠구나 라는 것을 배울 수 있는 세미나 였다.

휴리스틱은 “시간 또는 자원의 제약이 있는 상황” 에서 충분히 좋은 의사결정을 하기 위한 함수 혹은 알고리즘으로 정의 돼있다.
컴퓨터 성능이 고도화 되어가며 메타휴리스틱은 최적의 해를 찾기 위해 제한된 시간 내에 적절한 해를 구하려 한다. AI 시대의 방대한 데이터와 탐색해야 할 영역이 기하급수적으로 넓어졌을 때 메타휴리스틱 기법의 성능은 보장될
수 없다고 한다. 이에 컴퓨터 성능을 끌어올리려는 GPU, APU 등의
기술이 개발되어 지고 있다.



발표자는 Trajectory와
Population 기반의 병렬연산 처리가 다른 알고리즘을 설명해 주었다.



위의 두 가지를 설명해 줄 때 의사결정나무를 실례로 들어 탐색하지 못 한 부분을 잡아낼 수 있는 점 그리고 문제
영역을 만드는데 각각의 모델이 독립적으로 좋은 것이 있으면 서로 공유하는 점을 이해하기 쉽게 설명해 주었다. 특히 Case study에서 담금질 기법으로 ‘해의 질’ 을 높일 수 있는 설명과 GPU 구조에 대해 배울 수 있어 보람된
시간이었다.

오늘 세미나에서는 Metaheuristic 방법론을 분산처리하는 방법에
대한 설명을 들을 수 있었다. Metaheuristic은 풀기 어려운 최적화 문제를 합리적인 시간에
해결할 수 있게 도와주는 방법론이다. 대부분의 문제에서 최적의 해를 찾는 것이 보장되지는 않지만 적당히
좋은 해를 찾아주기 때문에 다양한 최적화 문제 해결에 응용되고 있다. Metaheuristic은 현재의
해를 평가하고 이를 개선시킬 수 있는 후보군들을 산출한 후에 후보군을 평가하고 다시 다른 후보군을 찾는 절차를 반복하면서 해를 찾는다. 따라서 주어진 시간 안에 최대한 많은 후보군들을 추출해서 평가하는 것이 성능향상에 중요하다. 그래서 분산처리가 필요한 것이다. 요즘에는 GPU를 이용한 분산처리가 활발하게 연구되고 있다. 후보군에 대한
추출과 평가는 계산 로드가 크지 않은 작업들이기 때문에 코어가 여러 개 있는 GPU의 각 코어에 이를
할당해서 처리하게 적합하다. 이러한 방식으로 분산처리를 하게 되면 더 빠르게 좋은 해를 찾을 수 있는
장점이 있다. 이러한 분산처리 기법은 인공지능이 실시간으로 의사결정을 하는 과정에서 좀 더 빠른 의사결정을
할 수 있게 도와줄 수 있는 유용한 기술이라 생각이된다. 최근 딥러닝을 통해서 인공지능의 인식능력이
비약적으로 상승되었는데 최종적인 의사결정 문제까지 빠르게 해결될 수 있다면 둘을 결합해서 다양한 문제 해결에 사용될 수 있을 것 같다.

컴퓨터 사이언스 전공을 한 저에게는 꽤 흥미로운 세션이었습니다. Graph 문제나
동적 게획법에 대한 프로그래밍 문제는 알고리즘시험에서 당골로 나오는 문제인데 이런 기법들이 meta
heuristic한 방법에 사용되는 점에 인사이트가 있었으며 Apache Spark이나 GPU의 발전으로 병렬처리에 대한 수요는 급증하리라 더 매력적인 연구분야인 것 같습니다. 하지만 reasonable함의 정의를 통해 현실과 타협함으로써 나오는 tradeoff는 적용분야가 제한적이지 않을까 생각이 듭니다.
sequential한 처리를 어떻게 parrellel하게 디자인하는가가 제일 중요한 문제같구요. Tranjectory basd는 신경망의 Gradient descending과
유사해보였고 Population basd는 유전자알고리즘으로 이해했으며, 처음 individuals을 어떻게 샘플링하는지에 대한 고민도 exploration 관점에서 중요할 것 같습니다. 그리고 가장 요즘
성능이 잘나왔다고 한 Cellular model에서 crossover과 mutation이 일어나는 부분은 exploitation 에 대한
걸 낮추고 exploration을 좀 더 하기 위해 성능이 잘 나오는 것을 잠시 off하는 개념으로 이해했는데 맞는지 모르겠습니다. 마지막으로 SA같은 경우는 asynchrouns와 synchronous로 나뉘는데요. synchronous와 asynchoronus의 장점을 같이 취할수
있지 않을까라고도 생각해보았습니다. 결국 비동기처리를 하지만 어느 정도는 synchrounous하게 처리도 가능하리라 생각이 들었습니다. 재미있는
주제 잘 들었습니다.

금일 세미나는 Parallel metaheuristics for large
data sets 라는 주제로 진행 되었다. Exhaustive Algorithm 은 Full-space Search 기법으로 Optimal solution 을
보장한다는 장점이 있으나 많은 문제에서 시간 또는 자원의 제약으로 인하여 활용하기 어려운 문제점이 있다. 반면에 Heuristic Algorithm 은 시간 또는 자원의 제약 속에서 최선의
Solution 을 선택하는 방법이다. 오늘 논의된
Metaheuristic 도 reasonable time 내에 suboptimal solution 을 제공한다. 변수나 case 가 많은 large data sets 는 Sequential algorithm 의 효율이 문제가 되는데 이를 해결 하기 위한 방법으로 parallel metaheuristics 가 있다. Parallel
approach 는 짧은 시간 내에 solution 의 질을 늘릴 수 있다는 장점이 있다. trajectory-based metaheuristics 의 parallel
model 은 parallel moves, parallel multi-start, move
acceleration model 이 있으며, 각각
independent 한 영역을 동시에 처리하여 효율성을 높이는 방법들이다.
Population-based metaheuristics 의 parallel model 은 master-slave. Distribute, cellular model 이 있으며, 임의의 영역을 parallel 하게 생성 후 각각의 영역에서 계산된
해를 가지고 Master 에서 다시 구별하거나 주변 Process 에 migration 을 함으로서 최선을 해를 찾아가는 방법들이다. 실제로
많은 영역에서 모집단의 크기는 아주 큰 반면에 분석해야 할 시간은 아주 짧은 경우가 많은데, 이런 경우에
대한 처리방법에 대하여 여러가지 방법들을 예로 들면서 쉽게 잘 설명해 준 좋은 세미나 였다.

금일 세미나는 Parallel metaheuristics for Large
Data Sets라는 주제로 진행되었다. Heuristic Algorithm이란 이미 정립된
공식에 의해서가 아니라, 정보가 완전하지 않은 상황에서 trial
and error을 거쳐 최적 해를 구하는 방식이다. Meta-heuristic Algorithm은 최적 해를 구하는 알고리즘
중 기준이 되는 알고리즘이다. 세미나는 Meta-heuristic 알고리즘을 parallel 방식으로 접근한 방법론에 대해 소개하는 자리였다.
Parallel의 접근 방식은 알고리즘의 총 수행 시간을 줄일 수 있고 최적 해를 개선하는 점에서도 장점이 있다. 이는 총 두 가지 방식으로 구분 할 수 있는데, 첫번째 Trajectory-based metaheuristic 방식은 하나의 초기 해가 주어지고, 초기 해를 통해 최적 해 영역이 주어지면 그 영역에 따라서 또 다른 최적 해 영역으로 탐색이 진행된다. 두 번째 방식은 population-based metaheuristic 방식으로
여러 개의 초기 해를 바탕으로 선택되는 해, 제거되는 해를 선정하는 방식으로 탐색한다. 데이터를 분석하는 데에 있어서 어떤 데이터를 sampling하여
어떤 방식으로 알고리즘에 적용할 것인가는 중요한 연구이다. K-means clustering이나 Active Learning의 분야에서도 효율적인 알고리즘 구축을 위해 병렬적으로 샘플링을 처리하게 되면 어떨까라는
생각이 들었다. 단순히 존재하는 알고리즘을 데이터에 적용하는 것을 넘어서서 데이터마이닝 알고리즘을 변형하고
적용시키는 측면에 대해 생각해 볼 수 있는 유익한 기회였다.

금주 참석한 세미나에서는 ‘Parallel metaheuristics for
large data sets’라는 주제로 Heuristics, Metaheuristics알고리즘의 introduction과 이런 고차원 알고리즘들이 sequential하여
발생하는 처리 속도의 한계를 개선하기 위해 제안된 Parallel approach에 대해 소개해주셨다. 먼저 Heuristics 알고리즘은 제한된 시간 내에 fairly good solution값을 얻는 것이 목표이다. 실제로
현실에서 다루어지는 최적화 문제 중 상당수는 문제 상황에 대해 fomulation을 정의할 수 있지만, NP-Hard문제이기 때문에 Local optmal를 보장해주는
반복적 알고리즘인 Heuristics방법론을 많이 사용한다.
Metaheuristics는 Heuristics알고리즘을 설계하는 전략적인 가이드라인을
제공해주며, 다양한 문제에 적용 가능한 Heuristics의
상위의 개념으로 탐색 의사결정에 대한 evaluation까지 하게 된다. Metaheuristics는 크게 두경우로 나눌 수 있는데 이는
Trajectory-based metaheuristics와 Population-based
metaheurstics으로 전자의 경우 각각의 instance가 인접 영역 내에서 탐색하여 optimal solution을 갱시하며 최종적인 local optimal
solution을 구하며, 후자의 경우 탐색하고자 하는
search instance중 비교하고 일부를 갱신해가며 local optimal solution을
구하게 된다. 하지만 앞서 언급했듯이 Metaheuristics알고리즘은
대부분 sequential하고, large data sets이기
때문에 처리속도에 한계가 있으며 이를 개선하기위해 두 경우의 Parallel approach를 제시하였고, 단시간 global optimal에 근사한 solution을 구할 수 있게 되었다. 세미나를 통해 평소에 헷갈렸던 Heuristics 개념에 대해 정리해볼 수 있어 유익하였고 최근 크롤링 실습을 하면서 처리시간이 오래 걸려
아쉬움이 있었는데 Parallel approach를 접목시켜 봐야겠다고 생각했다.

오늘 세미나는 'Parallel Metaheuristics for Large
Datasets'라는 주제로, 메타휴리스틱 기법들에 대한 개괄적인 설명과 함께 시간효율성과
해의 퀄리티 향상을 위한 메타휴리스틱 기법의 병렬화에 대해 포괄적으로 이해를 돕는 자리였다. 휴리스틱
기법이란 보통 풀고자하는 문제에 대한 해의 퀄리티를 조금 희생하는 대신, 제한된 시간 안에 만족스러운
해를 찾는 기법들을 의미하며 메타휴리스틱은 이러한 기법들을 포괄적으로 아우르는 말이다. 시간이 무한정
주어진다면 당연지사 최적해를 보장하는 알고리즘을 사용하는 것이 합당하지만, 대개 우리가 다루는 많은
현실 문제들은 시간에 대한 제약이 존재하기 때문에 그 문제를 풀어내는 알고리즘을 선택 시 메타휴리스틱 기법들이 종종 사용되곤 한다. 경험적으로 메타휴리스틱 기법들은 제한된 시간 안에 양질의 해를 도출하는 데 좋은 성능을 보인다고 알려져 있는데, 몇몇 알고리즘들은 계산 절차를 병렬화했을 때 그 시간을 더욱 단축시킬 수 있을 뿐만 아니라 해의 품질 개선도
가능하다. 오늘 다루어진 병렬 메타휴리스틱 알고리즘 중에서는
Cellular Genetic Algorithm이 가장 신선하였고, 추후 흥미를 갖고 공부해보면
좋을 것 같다. 아울러 trajectory-based와 population-based로 다양한 메타휴리스틱 기법들을 나누어 정리해 봄으로써 기존에 알고 있던 기법들이
한 눈에 정리되었다. 최적화와 알고리즘 중심의 오늘 세미나는 기존 연구실에서 진행되던 세미나들과는 사뭇
다른 성격이지만, 우리가 공부하는 많은 기계학습 방법론들의 기저에는 언제나 최적화가 핵심이 되는만큼
많은 연구원들의 생각의 너비와 깊이가 신장될 수 있는 기회였다고 생각한다. 실제로 한동안 사용되지 않던
메타휴리스틱 기법들이 최근 들어 다시 변수선택과 모델선택에 우수한 성능을 보이면서 많은 관심을 받고 있기 때문에 주목할만한 충분한 가치가 있다고
판단된다.

금일 세미나는 Parallel Metaheuristics for Large
Datasets를 주제로 진행되었다. Heuristics는 주로 풀고자 하는 문제에서 정확한
해를 찾을 수 없거나, 찾을 수 있더라도 매우 많은 시간이 걸리는 경우에 사용하는 방법으로 '최적'은 아니지만 '최적에
최대한 근사한' 해를 reasonable한 시간 내에 풀기위한
방법이다. 메타휴리스틱이란 탐색 프로세스의 방향을 제시해주기 위한 전략이라고 생각할 수 있다. 메타휴리스틱은 주로 순차적으로 진행이 되는 특성을 가지고 있기 때문에 데이터의 크기가 클 때 비효율적인 면을
보인다. 이러한 문제를 해결하기 위해 병렬처리를 통한 1) 알고리즘의
시간 단축 2) 효율적인 해의 탐색을 통한 솔루션의 퀄리티를 향상시키기 위한 연구들이 진행되고 있다. 다양한 종류의 메타휴리스틱 알고리즘을 Trajectory-Based
& Population-Based으로 구분지었는데, 기존에 알고 있거나 들어봤던
알고리즘들에 대한 대략적인 특징을 다시 한번 정리할 수 있어 유익한 시간이었다.

오늘 세미나는 parallel metaheuristics for large
datasets라는 주제로, 최적화 기법 중 하나인 메타휴리스틱 알고리즘들의 병렬화와 관련된
내용을 소개하는 방식으로 진행되었다. 일반적으로 최적화 문제를 푸는 데 있어 가장 먼저 고려되는 방법론은
전역 최적해를 얻기 위한 전역 탐색 기법이다. 하지만 복잡한 최적화 문제의 경우, 전역 탐색 기법을 이용하여 최적 해를 찾는 것이 비효율적이거나 불가능한 경우가 많다. 휴리스틱 기법은 이와 같이 시간 또는 자원제약이 있는 상황에서 충분히 좋은 해를 효율적으로 얻기 위한 기법이며, 메타휴리스틱은 이러한 휴리스틱 기법들을 보다 포괄적(휴리스틱의 휴리스틱)으로 지칭하는 표현이다. 충분한 시간 또는 충분한 컴퓨팅 파워가 주어진다면 전역 탐색 기법을 적용하지
않을 이유가 없겠지만, 현실에서는 항상 시간 또는 자원에 대한 제약이 존재하기 때문에 메타휴리스틱을
이용하여 적당한 시간 내에 적당한 퀄리티의 해를 찾아내는 것 역시 많은 분야에서 사용되어 왔다. 최근
컴퓨팅 파워의 비약적인 발전, 특히 병렬 컴퓨팅을 지원하는 하드웨어/소프트웨어가
발달함에 따라 메타휴리스틱 알고리즘을 병렬화하여 성능을 높이고자 하는 시도 역시 연구되고 있다. 세미나에서는
메타휴리스틱 병렬화의 taxonomy를 간단히 설명하고, 이를
통해 얻을 수 있는 이점을 소개하였다. 메타휴리스틱의 병렬화는 단순히 계산 속도에서의 이점만을 가져오는
것이 아니라, 더 좋은 해를 얻을 수 있는 가능성도 제공한다고 한다.
메타휴리스틱에 대해 관심은 있었으나 접할 기회가 많지 않았는데, 메타휴리스틱에 대한 간략한
설명에 더해 병렬화 및 적용 사례로 구성된 이번 세미나를 통해 많은 것들을 정리하고 배울 수 있었다.

오늘 세미나에서는 최적화 방법론 중 하나인 metaheuristic을
소개하고 metaheuristic 알고리즘을 병렬화하는 방법론에 대해 다루었다. Metaheuristic은 어려운 최적화 문제의 근사 최적해를 찾기 위한 최적화 방법론 중 하나로, 주로 시간과 자원이 한정된 상황에서 충분히 좋은 의사결정을 내리기 위해 사용된다. 많은 분야에서 나타나는 현실 문제들은 full-space search 알고리즘을
통해서 전역 최적해를 찾는 것이 사실상 불가능하기 때문에 현실 문제 해결을 위해서 metaheuristic을
사용하는 경우가 많다. 최근에는 GPU나 APU와 같은 하드웨어, 분산 컴퓨팅이나 클라우트 컴퓨팅과 같은 소프트웨어
측면에서 병렬 컴퓨팅이 발전함에 따라 metaheuristic 알고리즘들을 병렬화하여 성능을 높이기
위한 연구들이 진행되고 있다. 세미나에서는 metaheuristic을 trajectory-based와 population-based로 나누어
설명하고, population-based 알고리즘을 병렬화하는 방법론들에 대해 소개했다. 기계학습이나 통계를 비롯한 많은 현실 문제들이 최적화를 포함하고 있기 때문에 최적화 분야의 한 방법론과 그와
관련된 최신 트렌드에 대한 지식을 얻을 수 있는 의미 있는 세미나였다.

오늘 세미나에서는 상민이형이 metaheuristic 알고리즘을 병렬화
하는 기법에 대해 다뤘다. Metaheuristic은 다양한 최적화 문제를 제한된 시간내에 근사해를
구하기 위해 사용하는 기법으로 다양한 분야에서 활용된다. 최근에
GPU나 CPU가 병렬처리를 통해 성능을 향상시키는 방향으로 발전하고 있기 때문에 metaheuristic 알고리즘도 병렬처리를 통해 성능을 향상시키고자 하려는 시도가 이뤄지고 있다. 오늘 세미나에서는 metaheuristic 알고리즘을 population-based / trajectory-based 기법으로 나누어 이들 두 기법을 어떻게 병렬화
시킬 수 있는지 알아보았다. 최근에는 딥러닝이나 강화학습 등을 비롯한 다양한 알고리즘이 병렬화를 통해
성능을 향상시키는것이 하나의 트렌드로 자리잡은것 같다.

금주 세미나는 휴리스틱의 기본 개념부터 메타휴리스틱 병렬화까지 메타휴리스틱 연구에 대한 전체적인 리뷰였다. 휴리스틱이란 최적해 찾기 문제를 제한된 자원으로 효율적으로 풀기 위한 알고리즘이다. 확장된 개념으로 메타휴리스틱은 휴리스틱을 위한 휴리스틱 알고리즘이다. 최근
빅데이터 시대를 맞아 방대한 데이터가 수집되고 있고, 최적해 찾기 문제에서 탐색해야 할 공간을 증가
시켰다. 탐색공간이 넓고 복잡해 졌기 때문에 기존 대비 많은 시간을 요구한다. 이러한 문제를 해결하기 위해 GPU, 하둡 등 병렬 연산처리 기반
메타휴리스틱 연구가 주목 받고 있다. 병렬 연산처리 기반 메타휴리스틱은 기본적으로 순차적 알고리즘인
메타휴리스틱을 병렬화 시켜 해를 탐색하게 하는 방법으로, 큰 해공간을 몇 개의 작은 공간으로 분할해서
탐색하는 것과 같다. 순차적 알고리즘이 적용되는 gradient
descent 기반 parameter optimization 문제 및 active learning 문제 등의 machine learning 연구에
효과적으로 사용 될 것으로 생각된다. 관련 연구들의 동향을 살펴보면 좋을 것 같다.

오늘 전체 세미나는 Parallel Metaheuristics for
Large Datasets 라는 주제로 상민이형이 진행하였다. 메타휴리스틱이란 주어진 해공간에
최적해를 찾기 위한 효율적 탐색 알고리즘이다. 하지만 요즘과 같이 생성되는 데이터 변수와 관측치 양이
매우 클 때, 최적해를 찾기 위한 탐색영역이 매우 크기 때문에 성능을 보장하기 어려운 점이 있다. 이를 극복하기 위해 병렬처리 연구가 활발하게 이루어지고 있다. 먼저
휴리스틱과 메타휴리스틱의 차이점과 구성요소를 소개해 주어 전체적인 밑그림을 그리고 발표를 들을 수 있었다. 메타휴리스틱
접근은 크게 Trajectory와 Population 기반
이 두 가지로 나눌 수 있고 다양한 기법들이 존재한다. 주로 모델 성능 향상에 목적을 두어 연구하는
것뿐만 아니라 효율적인 탐색기법이 왜 필요하고, 곧 성능 향상으로 이어진다는 것을 알 수 있는 세미나였다.

이번 세미나에서는 ‘Parallel metaheuristics for
large data sets’라는 주제를 다루었다. 연구실 내 대부분의 연구원들에게 다소
생소한 주제였지만 발표 자료의 흐름이 잘 짜여 있어 편하게 들을 수 있었다. Heuristic은 시간
또는 자원의 제약이 있는 상황에서 충분히 좋은 의사결정을 하기 위한 기법이다. Metaheuristics이란 Heuristics를 잘 하기 위한 전략으로 Heuristics를
위한 Heuristic이라고 볼 수 있다. 글로벌 optimality를 보장하지는 못하지만 합리적인 시간 안에
suboptimal 해를 찾으므로 현실적인 방법론이다. 대부분의 Metaheuristics 기법들은 순서가 있는 특성을 가지고 있다. 따라서
이를 parallel하게 접근하여 많은 양의 데이터를 다룰 때 계산의 효율성을 높이고자 하는 시도들이
있어왔다. 가장 간단하게는 k가 1부터 n까지 변하는 for문이
있을 수 있는데 이를 1부터 m까지, m부터 n까지로 쪼개어 동시에 계산한다는 접근이다. 이렇게 함으로써 전체 연산이 완료되기까지 걸리는 시간도 단축할 수 있고 얻어진 해의 질도 올릴 수 있다. Metaheuristics 방법론은 크게 Population-based
metaheuristics, Trajectory-based metaheuristics로 나눌 수 있다. 세미나에서는 각 방법론에 대한 병렬 처리 모델을 간략하게 소개하고, 마지막으로 Trajectory-based metaheuristics 중 하나인 simulated
annealing을 병렬 처리한 논문을 소개하여 지금까지 설명했던 큰 컨셉에 대한 이해를 도왔다. 본인의
연구 분야가 아닌 쪽은 따로 혼자 공부하기가 어려운데 이번 세미나를 통해서 metaheuristics에
대한 개괄적인 내용을 알 수 있었기 때문에 의미 있는 시간이었다.