Harmony Search 알고리즘의 수렴성 개선에 관한 연구

이상경(SangKyung Lee),고광은(Kwang-Enu Ko),심귀보(Kwee-Bo Sim) 한국지능시스템학회 2011 한국지능시스템학회논문지 Vol.21 No.3

복잡해진 최적화문제를 전통적인 방법보다 효율적으로 해결하기위해 유전알고리즘이나 개미군집화, 하모니서치알고리즘과 같은 다양한 메타휴리스틱이 개발되었다. 그 중에서 하모니 서치알고리즘이 다른 메타휴리스틱알고리즘보다 좋은 결과를 보이고 있다. 하모니 서치 알고리즘은 음악을 작곡할 때 아름다운 소리를 내는 하모니를 찾는 과정을 모방했다. 성능은 하모니 메모리에서 선택하는 비율인 HMCR값과 하모니 메모리에서 선택된 값의 조정 비율을 결정하는 PAR값에 따라 달라지는 것으로 알려져 있다. 다르게 말하면 두 변수의 기반이 되는 하모니 메모리의 사용방법의 문제로 볼 수 있다. 본 논문은 설정한 기간 동안 더 좋은 최적해를 찾지 못할 경우 하모니 메모리의 일부를 좋은 하모니로 구성되게 수정하는 방법을 제안했다. 테스트 함수를 이용한 검증 실험결과에서 하모니 메모리를 수정할 경우 정확도 변화가 적어 신뢰성 있는 정확도를 보였으며, Iteration이 짧더라도 최적값에 근접한 값을 찾았다. In order to solve a complex optimization problem more efficiently than traditional approaches, various meta-heuristic algorithms such as genetic algorithm, ant-colony algorithm, and harmony search algorithm have been extensively researched. Compared with other meta-heuristic algorithm, harmony search algorithm shows a better result to resolve the complex optimization issues. Harmony search algorithm is inspired by the improvision process of musician for most suitable harmony. In general, the performance of harmony search algorithm is determined by the value of harmony memory considering rate, and pitch adjust rate. In this paper, modified harmony search algorithm is proposed in order to derive best harmony. If the optimal solution of a specific problem can not be found for a certain period of time, a part of original harmony memory is updated as the selected suitable harmonies. Experimental results using test function demonstrate that the updated harmony memory can induce the approximation of reliable optimal solution in the short iteration, because of a few change of fitness.

하모니 서치를 이용한 노노그램 퍼즐풀이

이건희(Geon Hee Lee),김종우(Zong Woo Geem) 한국지능시스템학회 2021 한국지능시스템학회논문지 Vol.31 No.5

노노그램이란 주어진 숫자만큼 칸을 칠하면서 전체적인 모양을 완성하는 퍼즐로 방대한 경우의 수를 가진 NP-Hard 문제이다. 이러한 노노그램을 풀기 위해 유전 알고리즘을 적용하거나 입자군집최적화나 깊이우선탐색법 등이 쓰이기도 하였다. 그러나 아직까지 하모니서치 알고리즘을 적용한 연구는 없었기에 본 논문에서 노노그램을 하모니서치 알고리즘을 사용해 풀어보고 그 결과를 진화연산기법인 유전 알고리즘과 비교해보고자 한다. 결과적으로 10×10 이상의 비교적 큰 보드에서는 유전 알고리즘이, 그보다 작은 보드에서는 하모니서치 알고리즘이 더 우수한 결과를 보였기에 조건에 따라 하모니서치 알고리즘이 경쟁력을 가질 수 있음을 확인하였고, 추후의 연구에서는 새로운 연산자를 도입하여 성능 개선을 하고자 한다. Nonogram is an NP-Hard problem having a vast number of combinations, which completes the overall shape while painting certain spaces based on given numbers. In order to solve these Nonograms, genetic algorithm as well as particle swarm optimization and depth-first-search have been applied. However, since there was no attempt of using the harmony search algorithm, we would like to solve the Nonogram using the algorithm and compare the results with another evolutionary computation technique, genetic algorithm. Results showed that genetic algorithm solved better for relatively large boards of 10×10 or more while harmony search solved better for smaller boards. Further studies are expected to improve the performance of harmony search in the future by introducing new problem-specific operators.

Harmony Search 알고리즘의 수렴성 개선에 관한 연구

이상경(SangKyung Lee),고광은(Kwang-Eun Ko),심귀보(Kwee-Bo Sim) 한국지능시스템학회 2011 한국지능시스템학회 학술발표 논문집 Vol.21 No.1

하모니 서치 알고리즘은 음악을 작곡할 때 아름다운 소리를 내는 하모니를 찾는 과정을 모방한 알고리즘이다. 유전자알고리즘이나 개미 군집화 알고리즘과 같은 자연을 모방한 알고리즘에 비해 NP-hard와 지역 최적 해에 수렴하는 문제 등 다양한 최적화 문제에서 우수한 성능을 나타내고 있다. 성능은 하모니 메모리 선택 하는 HMCR값과 하모니 메모리에서 선택된 값의 변경 유무를 결정하는 PAR값에 따라 달라지는 것으로 알려져 있다. 이를 다르게 말하면 두 변수의 기반이 되는 하모니 메모리의 조합의 문제로 볼 수 있다. 따라서 본 논문은 HMCR값과 PAR 값의 변경 보다는 일정 기간 동안 최적 해를 찾지 못할 경우 하모니 메모리의 일부를 재설정하는 방법을 제안했다. 테스트 함수를 이용해 검증 실험결과에서 하모니메모리 값의 초기 설정에 따라 큰 성능 변화를 보였으며, 하모니 메모리를 수정할 경우 성능 개선됨을 확인했다.

하모니 서치 알고리즘의 피치 조정 연산자 개선 연구

이건희,김종우 한국지능시스템학회 2022 한국지능시스템학회논문지 Vol.32 No.4

본 논문에서는 하모니 서치 알고리즘의 성능, 즉 전역 최적해로의 수렴성을 높이기 위한 연구의 일환으로서, 하모니 서치 알고리즘의 주요 3연산자(무작위 선택, 하모니 메모리 고려,피치 조정) 중의 하나인 피치 조정의 방식을 수정해보았다. 5개의 테스트 함수를 통해 시뮬레이션 해 본 결과, 기존 피치 조정 방식의 하모니 서치 알고리즘보다 4개의 테스트 함수에서 확실히 더 좋은 결과를 보였으며, 나머지 1개의 테스트 함수에서는 두 방식간의 차이가거의 없었다

국문 등재지 기반 하모니 서치 알고리즘의 이론과 응용사례 리뷰

김종우(Zong Woo Geem) 한국지능시스템학회 2022 한국지능시스템학회논문지 Vol.32 No.3

세계적으로 연구의 영향력이 있는 과학기술논문들을 모아 SCI (Science Citation Index) 데이터베이스에서 관리한다. 비슷하게 국내에서도 KCI (Korea Citation Index)를 만들어 논문을 관리하고 있다. 본 연구에서는 그동안 KCI에 등재된 하모니 서치 관련 국문 논문에 대한 광범위한 리뷰를 하였다. 하모니 서치는 음악에서 영감을 받은 지능형 최적화 알고리즘으로 그동안 다양한 문제에 적용되었는데 본 리뷰에서는 이론분야 (알고리즘 구조개선, 알고리즘간의 융합)나 응용분야 (토목공학, 전기/전자/통신공학, 컴퓨터학, 기타공학 및 의사결정분야)의 주요한 60여편의 논문을 선정하여 요약정리 하였다. 이를 통해 그동안 알고리즘이 국내에 적용된 분야를 확인 할 수 있었고 또 추후 나아가야할 연구의 방향을 제시하였다. Science Citation Index (SCI) database manages world influential research papers in science and technology. Similarly, Korea Citation Index (KCI) manages domestic influential research papers. This paper reviewes major harmony search (HS) papers written in Korean that are indexed in KCI. It gives an extensive summary of HS, music-inspired intelligent optimization algorithm, in the fields of theory (algorithm structure enhancement and hybridization with other algorithms) and applications (civil engineering, electrical/electronic/commucation engineering, computer science, and other technology & decision-making) which may enable readers to view the past, present, and future of the algorithm.

터널 굴착면 전방의 이상지반 예측을 위한 전기비저항 기반 하모니서치 (HS) 역해석 알고리즘

박진호,이강현,신상훈,이성원,이인모,Park, Jin-Ho,Lee, Kang-Hyun,Shin, Sang-Hoon,Lee, Seong-Won,Lee, In-Mo 한국터널지하공간학회 2014 한국터널지하공간학회논문집 Vol.16 No.2

본 연구의 목적은 전기비저항을 사용한 터널 굴착면 전방의 이상지반 탐사 시 이상지반의 위치와 두께 및 전기적 특성을 예측하기 위한 하모니서치(Harmony Search, HS) 알고리즘의 적용과 역해석 정확성의 검증이다. 가우스법칙(Gauss' laws)과 옴의 법칙(Ohm's laws)으로부터 이상지반 존재 시 암반의 전기저항과 이상지반 특성 변수를 연관 짓는 관계식을 유도하고, 전기저항을 사용하여 이상지반 특성 변수를 예측하도록 HS 알고리즘 기반의 역해석 프로그램을 개발하였다. 지반의 전기비저항을 측정하기 위한 저항 측정 시스템을 제작하였으며, 제안된 HS 알고리즘을 검증하기 위해 실내실험으로 모사한 이상지반의 전기저항을 측정하여 역해석을 수행하였다. 그 결과, 이상지반의 위치와 두께에 대한 예측은 5% 이하의 낮은 오차율을 나타내어 이상지반의 특성을 높은 정확도로 예측함을 보였다. The objective of this study is the application of the harmony search (HS) algorithm and verification of the accuracy of inverse analysis to predict the location, thickness and electrical properties of anomalous zone ahead of tunnel face when utilizing the electrical resistivity survey using electrical resistivity of the ground. The relationship correlating the characteristic values of the anomalous zone with the electrical resistance values was derived using Gauss' laws and Ohm's laws. Inverse analysis program was developed to predict anomalous zone by using electrical resistivity based on HS algorithm. Electrical resistance measuring system is devised to obtain the electrical resistivity of the ground, and laboratory tests were performed on anomalies to verify the proposed HS algorithm. The test results show that the characteristics of the anomalies are predicted reasonably well resulting in less than 5% error when predicting the location and thickness of the anomaly.

변수값 범위의 축소를 고려한 하모니 서치 알고리즘

이건희,김종우 한국지능시스템학회 2022 한국지능시스템학회논문지 Vol.32 No.2

In this paper, to improve the search efficiency of Harmony Search algorithm, the ranges of variable values are reduced over iteration. Results show that certain reduction strategy performes better than traditional Harmony Search algorithm with fixed value ranges 본 논문에서는 확률적으로 해 공간을 탐색하는 하모니서치 알고리즘의 탐색 효율 향상을 위해서, 알고리즘 파라미터값을 조절하던 기존 연구들과는 달리, 결정 변수들의 값범위를 특정조건을 만족하거나 시간의 흐름에 따라 축소 시켜가면서 해 공간의 크기를 줄여 확률적으로최적해에 도달할 확률을 높여보고자 하였다. 그 결과 너무 급격하게 작은 범위까지 축소시킬 경우, 전역 최적 해를 찾지 못할 확률이 더 높아진다는 사실을 확인 할 수 있었으며, 비교적 큰 범위로만 축소시킨 경우에는 조건에 따라 기존의 고정된 변수 범위 방식보다 좋은 결과를 보임으로써, 알고리즘 성능 개선에 대한 가능성을 볼 수 있었다.

EM 알고리즘 및 메타휴리스틱을 통한 다이나믹 환경에서의 베이지안 네트워크 학습 전파 프레임웍

추상현(Sanghyun Choo),이현수(Hyunsoo Lee) 한국지능시스템학회 2016 한국지능시스템학회논문지 Vol.26 No.5

기 구축되어있는 베이지안 네트워크에서 다이나믹한 환경 변화가 발생 할 때, 관련된 베이지안 네트워크의 파라미터는 새롭게 형성된 데이터의 패턴에 적응하여 새로운 파라미터로 변경되어야 한다. 이때, 새로운 파라미터는 베이지안 네트워크의 인과관계를 고려하여 변경되어야 한다. 본 논문에서는 Expectation Maximization(EM)알고리즘과 Meta-Heuristics 기법 중 하나인 Harmony Search(HS)알고리즘을 이용한 다이나믹한 파라미터 업데이트 프레임웍을 제안한다. 일반적으로, EM 알고리즘은 숨겨진 파라미터를 추정하는데 유효한 알고리즘이지만 지역 최적값에 수렴한다는 단점을 가지고 있다. 이 문제를 해결하기 위해서 본 논문은 Maximum Likelihood Estimator(MLE)의 파라미터가 글로벌 최적값을 지향하도록 하기 위하여 메타휴리스틱 방법론의 하나인 HS를 적용한다. 제안된 방법은 EM 알고리즘의 단점을 보완하고 글로벌 최적값에 수렴하는 MLE의 파라미터를 추정하여 다이나믹하게 변화하는 환경에서도 사용 가능한 베이지안 네트워크의 학습 및 전파프레임웍을 제시한다. When dynamics changes occurred in an existing Bayesian Network (BN), the related parameters embedding on the BN have to be updated to new parameters adapting to changed patterns. In this case, these parameters have to be updated with the consideration of the causalities in the BN. This research suggests a framework for updating parameters dynamically using Expectation Maximization (EM) algorithm and Harmony Search (HS) algorithm among several Meta-Heuristics techniques. While EM is an effective algorithm for estimating hidden parameters, it has a limitation that the generated solution converges a local optimum in usual. In order to overcome the limitation, this paper applies HS for tracking the global optimum values of Maximum Likelihood Estimators (MLE) of parameters. The proposed method suggests a learning and propagation framework of BN with dynamic changes for overcoming disadvantages of EM algorithm and converging a global optimum avlue of MLE of parameters.

하모니서치 알고리즘 기반 인접 다중 경유지 최적 경로 탐색 기법

탁예지(Yeji Tak),박승민(Seungmin Park) 한국컴퓨터정보학회 2023 한국컴퓨터정보학회 학술발표논문집 Vol.31 No.2

하모니 서치와 시뮬레이티드 어넬링을 사용한 트러스의 단면 및 형상 최적설계

김봉익,Kim, Bong Ik 한국강구조학회 2015 韓國鋼構造學會 論文集 Vol.27 No.2

트러스구조는 대형구조물의 설계 및 시공에 편리하며, 부재의 경량화에 따른 비용의 절검 효과를 얻을 수 있는 구조물로 최근 다양한 형태의 구조물건설에 많이 사용되고 있다. 본 연구에서는 응력, 좌굴 그리고 구조물의 고유진동수 제약조건을 고려한 트러스 구조물의 단면과 형상에 대해 최적설계를 하였다. 최적설계에서 최적화기법으로 HA-SA방법을 제시하였으며, HA-SA방법은 HA 초기메모리에서 최상의 설계를 SA의 초기 설계로 하여 최적화 하는 방법이다. 예제에 사용된 트러스 구조물은 고유진동수 제약조건으로 10-bar, 72-bar, 52-bar 트러스와 응력 및 좌굴응력 제약조건으로 18-bar, 47-bar 트러스를 사용하였다. 그리고 52-bar, 18-bar, 47-bar의 경우는 트러스의 형상을 최적설계 하였다. 예제로부터 다양한 설계 제약조건하에서 여러 연구결과와 HA, SA, GA, HA-SA방법에 의한 결과를 서로 비교하여 HA-SA방법의 적용성을 입증하였다. In this paper, we present an optimization of truss structures subjected to stress, buckling, and natural frequency constraints. The main objective of the present study is to propose an efficient HA-SA algorithm for solving the truss optimization subject to multiple constraints. The procedure of hybrid HA-SA is a search method which a design values in harmony memory of harmony search are used as an initial value designs in simulated annealing search method. The efficient optimization of HA-SA is illustrated through several optimization examples. The examples of truss structures are used 10-Bar truss, 52-Bar truss (Dome), and 72-Bar truss for natural frequency constraints, and used 18-Bar truss and 47-Bar (Tower) truss for stress and buckling constraints. The optimum results are compared to those of different techniques. The numerical results are demonstrated the advantages of the HA-SA algorithm in truss optimization with multiple constraints.