검색 알고리즘 번역(한국어 원본)Meta-Heuristic algorithm이 최근에 Optimization problem를 해결하는데 많이 사용되고 있다. Optimization problem는 설계할 system이 복잡해지면서 급속히 발전하고 있는 computer를 사용해 해결하고 있다. 하지만, 전통적인 방법은 computer를 사용하더라도 연산 시간이 많이 걸리고, local Optimum에 빠지는 등의 문제가 있다. Meta-Heuristic algorithm은 memory 공간과 자연을 모방한 operator를 사용해 해결하고 있다. 대표적인 algorithm으로 Genetic algorithm(GA)[1], Ant Colony Optimization(ACO)[2], Particle Swarm Optimization( PSO)[3], Harmony Search algorithm(HS)[4]과 같은 다양한 Meta-Heuristic algorithm이 개발되어 좋은 성능을 보여주고 있다. 적용 분야도 설계나 비용의 Optimization뿐 만 아니라 SVM이나 MLP, HMM, GMM과 같은 machine learning과 같이 다양한 분야로 확대되고 있다.
machine learning과 같은 분야에 적용하기 위해서는 빠르고 정확성이 높아야 한다. Meta-Heuristic algorithm은 제한된 시간 내에 optimum value 또는 가까운 값을 찾아준다[5]. 따라서 건물설계, 운용 등에 적용된 Optimization Algorithm 들은 가장 좋은 optimum value 하나를 찾아주면 된다. 하지만 machine learning은 테스트 샘플을 이용해 통해 얻은 parameter가 성능에 직접 영향을 미치게 된다. 또한 데이터가 update되거나 자료가 수정되었을 때마다 새로 학습을 하기 때문에 지속적으로 optimum value 또는 가장 가까운 값을 제시해야 하며, 학습시간이 빠를수록 다양한 일을 처리 할 수 있으므로 빠르게 찾을 수 있어야 한다.
Meta-Heuristic Algorithm 이 빠르고 정확하게 찾기 위해서는 가능성 높은 값들로 memory가 구성될 수 있도록 관리되어야 한다. 대부분의 Algorithm 은 더 best value을 찾게 되면 memory(유전자Algorithm 의 유전자 풀이나 HS의 Harmony Memory(HM) 같은)에 저장해 검색에 활용한다. memory에 있는 값들은 local Optimum나 빠질 수 있기 때문에 벗어나기 위해 사용하는 random number를 같이 사용한다. 두 가지 값 중에서 random number는 신뢰성이 낮기 때문에 memory 값에 많은 비중을 두고 있다. 하지만 Initial memory도 random number로 생성하기 때문에 Initial 구성이 좋게 구성되어 있다고 보장을 못한다. 따라서 Initial memory의 구성에 따라 local Optimum에 빠지거나 수렴 속도가 느려지는 등의 문제가 발생해 전체 성능이 낮아진다[6][7].
본 논문에서는 인간 인내심의 한계를 모방해 만든 memory를 수정하는 방법을 제안했다. optimum value을 모르기 때문에 memory 수정 시점이나 기준을 판단하기 어렵다. 이처럼 판단하기 힘든 경우 인간은 계속 시도를 하다가 인내심의 한계를 느끼게 되면 참고 했던 자료를 수정해 효율적으로 작업을 한다. 이를 모방해 계속해서 optimum value이 생성되지 않으면 인간의 인내심처럼 최대 시도 횟수를 설정해 초과하면 memory를 수정한다[6][7]. memory 수정에는 수정하기 전까지 찾은 optimum value 중 가장 좋은 value을 조정해 사용한다.
Meta-Heuristic Algorithm 은 최근 좋은 성능을 보이는 HS에 적용했다. Meta-Heuristic Algorithm 의 memory에 해당되는 HM은 optimum value과 fitness가 분리되어 저장되므로 수정이 쉽다. harmony memory 내에 있는 나쁜 value보다 좋은 값을 찾았을 때 만 update되고 개별적으로 선택되기 때문에 building block problem가 없어 항상 best value으로 유지 할 수 있다[8].
논문의 구성은 첫 번째로, 제안한 Algorithm 과 기본이 되는 harmony search Algorithm 을 설명했다. 실험에서는 이산 값을 이용해 찾는 방정식 2개와 연속적인 값으로 찾는 방정식 1개를 사용해 parameter와 memory 수정에 따른 정확성 변화를 살펴보고, 제안하는 Algorithm 이 harmony search Algorithm 의 성능을 향상시키는 방법임을 검증했다. 마지막에 결론에서 전체 실험 결과 요약과 적용분야 소개로 마무리 했다. |
검색 알고리즘 번역(영어 번역본)Recently, meta-heuristic algorithm is widely used to solve optimization problems. Rapidly evolving computers are used to solve optimization problems as the systems to be designed become more complicated. However, traditional method still require large computation time even when computers are used and may become trapped in local optimum. Meta-heuristic algorithm uses operator imitating memory space and nature to solve problems. Diverse meta-heuristic algorithms such as Genetic algorithm (GA) [1], Ant Colony Optimization (ACO) [2], Particle Swarm Optimization (PSO) [3], and Harmony Search algorithm (HS) [4] are developed and show high performance. Fields in which these algorithms are applicable include not only optimization of design and cost, but also are expanding to diverse fields such as SVM or machine learning such as MLP, HMM, and GMM.
An algorithm must be fast and accurate in order to be applied in fields such as machine learning. Meta-heuristic algorithm finds optimum or approximate value within a limited time [5]. Therefore, optimization algorithms applied in building design or operation only need to find the best, single optimum value. However, in machine learning, parameters obtained through test sample have a direct influence on the performance. Also, the algorithm must continuously provide optimum or approximate value because it learns from update or modification of data. It must also be able to quickly provide the value since it can process more tasks when learning time is shortened.
For Meta-heuristic algorithm to quickly and accurately find solutions, memory must be maintained so that it is composed of values with high possibility. When most algorithms come across a better value, they store the value in the memory (such as genetic pool in genetic algorithm and harmony memory in HS) and utilize it for searching. Because values in the memory may become trapped in local optimum, random number is used alongside these values to escape from local optimum. Of the two types of values, values in the memory are weighted heavier since random number has low reliability. However, there is no guarantee that initial configuration is well-established because initial memory is also generated from random numbers. Depending on the initial memory configuration, problems such as local optimum traps or slow convergence speed may arise to decrease the overall performance [6][7].
In this study, we present a memory modification method that imitates human endurance limits. In finding the solution, it is difficult to determine the criteria and timing for memory modification since the optimum value is unknown. In such a case, human continues the effort until one reaches the limits of endurance, at which one modifies the data to perform the task more efficiently. Simulating this behavior, the presented algorithm continues looking for optimum value until the maximum number of attempts similar to human endurance is reached, after which it modifies the memory [6][7]. Before the memory modification, the best optimum value up to that point is adjusted and used.
Meta-heuristic algorithm was applied to HS, which has recently shown high performance. HM, which corresponds to memory in meta-heuristic algorithm, separately stores optimum value and fitness, which allows easy modification. HM is only updated when a value better than the one in the memory is found, and best value can be maintained since there is no building block problem [8].
In this paper, we will first explain the presented algorithm and the harmony search algorithm, which is the basis for the presented algorithm. Next, two equations with discrete values and one equation with continuous values were used to observe change in accuracy after modification of parameters and memory, and confirmed that the presented algorithm improves the performance of harmony search algorithm. Finally, summary of the overall experiment and discussion of applicable areas were presented in the conclusion. |
