[논문]인공벌 군집 알고리즘을 기반으로 한 복합탐색법

이수항; 김일현; 김용호; 한석영

doi:10.7735/ksmte.2014.23.3.213

인공벌 군집 알고리즘을 기반으로 한 복합탐색법
A Hybrid Search Method Based on the Artificial Bee Colony Algorithm 원문보기

한국생산제조시스템학회지 = Journal of the Korean Society of Manufacturing Technology Engineers, v.23 no.3, 2014년, pp.213 - 217

이수항 (Department of Mechanical Engineering, Hanyang Graduate School) , 김일현 (Department of Mechanical Engineering, Hanyang Graduate School) , 김용호 (Department of Mechanical Engineering, Hanyang Graduate School) , 한석영 (Division of Mechanical Engineering, Hanyang University)

Abstract ▼ AI-Helper

A hybrid search method based on the artificial bee colony algorithm (ABCA) with harmony search (HS) is suggested for finding a global solution in the field of optimization. Three cases of the suggested algorithm were examined for improving the accuracy and convergence rate. The results showed that the case in which the harmony search was implemented with the onlooker phase in ABCA was the best among the three cases. Although the total computation time of the best case is a little bit longer than the original ABCA under the prescribed conditions, the global solution improved and the convergence rate was slightly faster than those of the ABCA. It is concluded that the suggested algorithm improves the accuracy and convergence rate, and it is expected that it can effectively be applied to optimization problems with many design variables and local solutions.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 인공벌 군집 알고리즘에 조화탐색법을 적용하여 기존의 인공벌 군집 알고리즘보다 더 정확하고 빠른 전역해를 구하는 것을 목적으로 한다. 두 가지의 알고리즘을 복합시키는 방법은 여러 가지를 고려할 수 있겠으나 계산시간에 대한 효율적인 해의 탐색을 위해 수치실험을 통해 선택된 세 가지 경우만을 비교하였으며, 네 종류의 벤치마크 함수를 이용하여 제안하는 알고리즘의 정확성과 수렴속도의 향상 정도를 확인하고자 한다.

제안 방법

1 단계: 조화 기억 크기(harmony memory size: HMS)와 변수의 개수(D)를 고려한 조화 기억 행렬(HM)을 생성하고, 조화 기억기여율(harmony memory considering rate: HMCR), 높낮이 조정률(pitch adjusting rate: PAR), 대역폭(bandwidth: BW)값들을 설정한다.
ABCHSA의 세 가지 경우에 대한 정확성 향상 정도를 확인하기 위해 특성이 다른 네 가지의 벤치마크 함수를 이용하여 ABCA와 비교해보았다. 사용된 벤치마크 함수는 Table 1에 나타내었으며, 주어진 함수 f(x)에 대해 최소화 하는 것을 목표로 한다.
HS가 ABCA의 고용벌과 관망벌 단계에 각각 적용되었고, 네가지 벤치마크 함수를 이용하여 정확성과 수렴속도에 대해 기존의 ABCA와 비교하였다. 주어진 계산조건에서는 ABCA가 해를 탐색하는 시간 외에 HS의 탐색시간이 추가되어 총 계산 시간이 대체적으로 더 길어졌음을 확인할 수 있었다.
본 논문에서는 인공벌 군집 알고리즘에 조화탐색법을 적용하여 기존의 인공벌 군집 알고리즘보다 더 정확하고 빠른 전역해를 구하는 것을 목적으로 한다. 두 가지의 알고리즘을 복합시키는 방법은 여러 가지를 고려할 수 있겠으나 계산시간에 대한 효율적인 해의 탐색을 위해 수치실험을 통해 선택된 세 가지 경우만을 비교하였으며, 네 종류의 벤치마크 함수를 이용하여 제안하는 알고리즘의 정확성과 수렴속도의 향상 정도를 확인하고자 한다.
본 논문에서는 ABCA에 HS를 복합시키기 위해 식량원의 위치를 탐색하는 ABCA의 고용벌과 관망벌 단계에 각각 HS를 적용하였다. 즉, 고용벌 단계의 경우 에는 반복횟수를 고용벌의 수와 1인 경우로 나누었으며, 관망벌 단계의 경우는 식량원의 확률값을 HMCRi로 대체하였다.
최근 최적화 문제의 전역해를 찾기 위해 생태계에서 무리를 지어 활동하는 개체들이 가지는 집단지성을 수학적으로 표현하여 해를 찾는 알고리즘들이 많이 제안되었다. 본 논문에서는 음의 조화에 대해 다룬 조화탐색(HS)이 다른 알고리즘들에 비해 빠른 수렴성을 가진다는 점과 다양한 분야에 적용되었다는 점을 참고하여, ABCA에 HS를 복합하여 새로운 탐색 알고리즘을 제안하였다.
본 논문에서는 ABCA에 HS를 복합시키기 위해 식량원의 위치를 탐색하는 ABCA의 고용벌과 관망벌 단계에 각각 HS를 적용하였다. 즉, 고용벌 단계의 경우 에는 반복횟수를 고용벌의 수와 1인 경우로 나누었으며, 관망벌 단계의 경우는 식량원의 확률값을 HMCRi로 대체하였다.

성능/효과

그러나, Figs. 1-4를 통해 네 가지 함수 모두 Case 3의 목적함수가 ABCA에 비해 전역해에 먼저 수렴함을 확인할 수있었다. 따라서, 제안하는 알고리즘이 정확성과 수렴속도 면에서 모두 개선되었음을 알 수 있었다.
계산시간의 경우에는 주어진 조건에서 ABCHSA의 세 가지 경우들이 ABCA에 비해 대체적으로 비슷하거나 더 길어졌음을 확인할 수 있었다. 그러나, Figs.
그러나, ABCA의 관망벌에 HS가 적용된 경우에는 네 가지 벤치마크 함수에 대해 기존의 ABCA보다 목적함수의 값이 더욱 개선되었음을 확인할 수 있었으며, 수렴그래프로부터 목적함수가 전역해에 먼저 수렴함을 확인할 수 있었다. 따라서, 제안하는 알고리즘이 정확성과 수렴속도 면에서 모두 개선되었음을 알 수 있었다.
1-4를 통해 네 가지 함수 모두 Case 3의 목적함수가 ABCA에 비해 전역해에 먼저 수렴함을 확인할 수있었다. 따라서, 제안하는 알고리즘이 정확성과 수렴속도 면에서 모두 개선되었음을 알 수 있었다.
표에서 볼 수 있듯이, Case 1, 2의 경우에는 기존의 ABCA에 비해 대체적으로 목적함수의 평균값이 더 좋지 않았지만, Case 3의 경우에는 다른 방법들보다 목적함수의 값이 개선되어졌음을 확인할 수 있다. 이는 ABCA의 관망벌 단계에서 룰렛휠법에 의해 선택된 식량원을 HS에 의해 높낮이를 조절하고 선택되지 못한 식량원을 다시 새로운 식량원으로 생성함으로써, 임의의 식량원이 아닌 전역해의 확률이 높은 식량원에 대해 HS를 이용하는 것이 해의 탐색 효과를 높인 것으로 확인되었다.
HS가 ABCA의 고용벌과 관망벌 단계에 각각 적용되었고, 네가지 벤치마크 함수를 이용하여 정확성과 수렴속도에 대해 기존의 ABCA와 비교하였다. 주어진 계산조건에서는 ABCA가 해를 탐색하는 시간 외에 HS의 탐색시간이 추가되어 총 계산 시간이 대체적으로 더 길어졌음을 확인할 수 있었다.

질의응답

핵심어	질문	논문에서 추출한 답변
	전역 최적화의 목적은 무엇인가?	전역 최적화(global optimization)의 목적은 제약조건을 만족하는 수많은 국부해(local optimum)들 중에서 최소의 목적함수 (objective function) 값을 주는 변수들의 값을 결정하는 것이다. 최근, 자연의 생태계와 살아있는 생명체의 기본 구조, 원리 및 메커 니즘 등에서 영감을 얻어 실생활에 응용된 자연 모사 기술(natureinspired technology)들이 많이 제안되고 있다.
	최적화 분야에서 응용된 자연 모사 기술에는 무엇이 있는가?	최근, 자연의 생태계와 살아있는 생명체의 기본 구조, 원리 및 메커 니즘 등에서 영감을 얻어 실생활에 응용된 자연 모사 기술(natureinspired technology)들이 많이 제안되고 있다. 최적화 분야에서는 개미, 벌, 물고기, 새, 박쥐 등의 군집의 거동을 모방하여 최적해를 구하는 집단 지능 알고리즘(swarm intelligence algorithm)들이제안되었다[1-4]. 그 중에서도 Karaboga와 Basturk[4]에 의해 제안된 인공벌 군집 알고리즘(artificial bee colony algorithm: ABCA) 은 꿀벌의 먹이(nectar)를 찾는 집단행동을 모방한 알고리즘으로 차분 진화(differential evolution: DE)[5], 입자 군집 최적화(particle swarm optimization: PSO)[2], 진화 알고리즘(evolutionary algorithm: EA)[6]과 비교할 때 전역해를 찾는데 더 효율적임을 확인하였으며, 구조 위상 최적화 문제에도 적용되어 많은 설계변수를 가지는 문제에도 해의 수렴이 뛰어남을 확인하였다[7,8].
	조화탐색법이란 무엇인가?	조화탐색(harmony search: HS)[9]법은 재즈 연주에서 악기들의 음을 조율하는 것에 착안하여 음악에서의 음의 조화는 최적의 변수들이 조화된 벡터와 같다는 것에 기반을 둔 알고리즘이다. 이 탐색 법은 선택된 주요 변수들을 이용하여 국부해에 빠지지 않고, 효율적으로 전역해를 찾을 수 있다.

참고문헌 (13)

Dorigo, M., Stutzle, T., 2004, Ant Colony Optimization, MIT Press, London.
Kennedy, J., Eberhart, R., 1995, Particle Swarm Optimization, Proc. 1995 IEEE Int. Conf. Neural Netw. 4 1942-1948.
Yang, X-S., 2010, A New Metaheuristic Bat-inspired Algorithm, Nat. Inspir. Coop. Strateg. Optim. (NICSO 2010) Stud. Comput. Intell. 284 65-74.
Karaboga, D., Basturk, B., 2008, On the Performance of Artificial Bee Colony (ABC) Algorithm, Appl. Soft Comput. 8:1 687-697.

상세보기
Storn, R., Price, K., 1997, Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, J. Glob. Optim. 11:4 341-359.
Back, T., 1996, Evolutionary Algorithms in Theory and Practice: Evolution, Strategies, Evolution Programming, Genetic Algorithms, Oxford Univ. Press, New York.
Park, J.-Y., Ryu, S.-P., Eom, Y.-S., Yoo, K.-S., Park, J.-Y., Han, S.-Y., 2010, Application of Modified Bee Colony Algorithm for Structural Dynamic Problems, Korea Soc. Mach. Tool Eng. Autumn Conf. 2010 57-58.
Park. J. Y., Han, S. Y., 2013, Topology optimization of nonlinear Structures Using Bee Colony Optimization, Korea Soc. Manuf. Technol. Eng. Spring Conf. 2013 193.
Lee, K. S., Geem, Z. W., 2004, A New Structural Optimization Method Based on the Harmony Search Algorithm, Comput. Struct. 82:9-10 781-798.

상세보기
Geem, Z. W., 2006, Comparison Harmony Search with Other Meta-heuristics in Water Distribution Network Design, Water Distrib. Syst. Anal. Symp. 2006.
Kim, J. H., Geem, Z. W., Kim, E. S., 2001, Parameter Estimation of the Nonlinear Muskingum Model Using Harmony Search, J. Am. Water Resour. Assoc. 37:5 1131-1138.

상세보기
Zarei, O., Fesanghary, M., Farshi, B., Jalili Saffar, R., Razfar, M. R., 2009, Optimization of Multi-pass Face-milling via Harmony Search Algorithm, J. Mater. Process. Technol. 209:5 2386-2392.

상세보기
Goldberg, D. E., 1989, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publ. Co., Boston.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증