벌 알고리즘

Bees algorithm
인공벌 군집 알고리즘과 혼동해서는 안 된다.

컴퓨터 과학과 운영 연구에서 벌 알고리즘은 2005년 팸, 간바르자데 등이 개발한 인구 기반 검색 알고리즘이다.[1] 꿀벌 군락지의 먹이 포획 행동을 모방한다. 기본 버전에서 알고리즘은 글로벌 검색과 결합된 일종의 인접 검색을 수행하며 조합 최적화와 연속 최적화에 모두 사용할 수 있다. 벌 알고리즘을 적용하기 위한 유일한 조건은 용액 사이의 거리 측도가 정의되는 것이다. 벌 알고리즘의 효과와 구체적인 능력은 여러 연구에서 입증되었다.[2][3][4][5]

은유

꿀벌의 군락은 먼 거리(14km 이상)[6]와 여러 방향으로 동시에 뻗어 여러 식재료(꽃밭)에서 과즙이나 꽃가루를 수확할 수 있다. 군락의 극히 일부분이 끊임없이 환경을 뒤져 새로운 꽃밭을 찾는다. 이 정찰벌들은 벌집을 둘러싸고 있는 지역에서 무작위로 움직이며, 마주치는 식량원의 수익성(순에너지 산출량)을 평가한다.[6] 그들이 벌집으로 돌아왔을 때, 스카우트들은 수확한 음식을 맡긴다. 수익성이 높은 식재료를 발견한 사람들은 벌집의 "춤 바닥"이라고 불리는 곳에 가서, 그 춤으로 알려진 의식을 행한다.[7] 스카우트 벌은 왜글춤을 통해 발견 장소를 한가한 구경꾼들에게 전달하고, 그들은 화단의 착취에 동참한다. 춤의 길이는 스카우트의 식재료 등급에 비례하기 때문에, 더 많은 식량담당개미들이 최고의 등급의 꽃밭을 수확하기 위해 모집된다. 춤을 추고 난 후, 스카우트는 더 많은 음식을 모으기 위해 발견한 음식 공급원으로 돌아온다. 이들이 수익성이 있다는 평가를 받는 한, 풍부한 식량원은 스카우트들이 벌집으로 돌아갈 때 광고에 나올 것이다. 모집된 포획자는 춤도 출 수 있어 보상이 높은 꽃밭에 대한 모집 인원을 늘릴 수 있다. 이러한 자기분석적 과정 덕분에, 벌 군락지는 가장 수익성이 높은 꽃밭에 포획 작업의 초점을 빠르게 전환할 수 있다.[6]

알고리즘.

벌 알고리즘은[2][8] 꿀벌의 포획 전략을 모방하여 최적화 문제에 대한 최선의 해결책을 찾는다. 각 후보 해법은 식재료(꽃)로 생각되며, n개 요원(벌)의 모집단(색)을 사용해 해법 공간을 탐색한다. 인공벌은 꽃(용액 위의 땅)을 방문할 때마다 그 수익성(피트니스)을 평가한다.

벌 알고리즘은 주어진 횟수 T 동안 또는 허용 가능한 적합성의 해결책이 발견될 때까지 반복되는 초기화 절차와 주 검색 사이클로 구성된다. 각 검색 주기는 모집, 지역 검색, 이웃 축소, 사이트 포기, 글로벌 검색의 다섯 가지 절차로 구성된다. 

i=1, …,ns i 스카우트[i]=에 대한 표준 벌 알고리즘[2] 1의 유사 코드initialize_scout()i ii flower_patch[i]=stop_condition=까지 initialize_flower_patch(scout[i]) 2 do.TRUE i 모집()i =1,...,na 1꽃_패치[i]=local_search(flower_patch[i]) 2꽃_patch[i]=사이트_폐기(꽃_패치[i]) 3꽃_패치[i]=i = nb,...,ns 1꽃_패치[i]=의 인접_수축(flower_patch[i])iii.Global_search(flower_patch[i])}

초기화 절차에서 ns 스카우트 벌은 검색 공간에 무작위로 배치되며, 그들이 착륙한 해결책의 적합성을 평가한다. 각 솔루션에 대해 이웃 지역(화훼 패치라고 함)이 구분된다.

채용 절차에서는 nbns 적자 솔루션(최우수 사이트)을 방문한 스카우트들이 와글댄스를 선보인다. 즉, 그들은 가장 유망한 해결책의 이웃을 더 찾아낼 식량담당자를 모집한다. 최고의 ne≤nb 솔루션(엘리트 사이트)을 찾은 스카우트들은 nre 포워더를 각각 모집하고, 나머지 nb-ne 스카우트들은 nrbnre 포워더를 각각 모집한다. 따라서 모집된 포획기의 수는 식재료의 수익성에 따라 달라진다.

현지 검색 절차에서 모집된 포획기는 스카우트가 방문한 해결책(현지 착취)을 둘러싸는 꽃밭 안에 랜덤하게 흩어져 있다. 꽃밭에 있는 식량담당자 중 한 명이라도 스카우트가 방문한 해법보다 더 높은 체력단련을 위한 해법에 착륙한다면, 그 식량담당자는 새로운 스카우트가 된다. 어떤 위조지폐도 더 높은 건강의 해결책을 찾지 못하면, 꽃밭의 크기는 축소된다(근접 수축 절차). 보통, 꽃밭은 처음에는 넓은 면적에 걸쳐 정의되며, 그 크기는 이웃의 축소 절차에 의해 점차적으로 축소된다. 결과적으로, 지역 탐구의 범위는 지역 피트니스에 가장 가까운 지역에 점진적으로 집중된다. 사전 설정된 검색 주기 횟수에 대해 지정된 꽃밭에 피트니스 개선을 기록하지 않으면 현지 최대 피트니스 발견, 패치를 폐기(사이트 포기)한 후 무작위로 새로운 스카우트가 생성된다.

생물학적 벌 군락에서와 마찬가지로 소수의 스카우트들이 새로운 피트니스 지역(글로벌 검색)을 찾아 솔루션 공간을 계속 탐색하고 있다.[6] 글로벌 검색 절차는 임의로 생성된 솔루션을 사용하여 마지막 ns-nb 플라워 패치를 다시 초기화한다.

한 번의 검색 사이클이 끝나면 스카우트 인구는 다시 ns 스카우트: 현지 검색 절차에 의해 생산된 nr 스카우트와 글로벌 검색 절차에 의해 생성된 ns-nb 스카우트로 구성된다. 총 인공벌 군집 크기는 n=ne•nre+(nb-ne)•nrb+ns(엘리트 사이트 포바이저 + 남은 베스트 사이트 포바이저 + 스카우트) 벌이다.

변형

기본벌 알고리즘 외에도 여러 가지 개량형 또는 복합형 버전의 BA가 있는데, 각각은 기본 BA의 몇 가지 단점에 초점을 맞추고 있다.[8] 이러한 변형에는 퍼지 또는 강화된 BA([9]EBA), 그룹화된 BA([5]GBA), 하이브리드 변형 BA(MBA)[10] 등이 포함된다. 그룹화된 BA(GBA)에 대한 의사 코드는 다음과 같다. 

함수 GBA %% 문제 매개변수 maxIteration = ..; %의 반복 횟수(예: 1000-5000) maxParameter = ..; %의 입력 변수 min = [..]; 각 입력 매개 변수 max = [..]의 최소값을 나타내는 크기 maxParameter의 배열 %; 각 입력 매개 변수 %%의 최대값을 나타내는 크기 maxParameter의 배열 %. 그룹화된 벌 알고리즘(GBA) 매개 변수 R_ngh = ..; 첫 번째 그룹에서 벌에 대한 동네의 패치 반지름 비율(예: 0.001 - 1) n = ..; %의 정찰벌 수(예: 4-30) n그룹 = ..; % number of groups, excluding the random group  %% GBA's automatic parameter settings k = 3 * n / ((nGroups+1)^3 - 1); % GBA's parameter to set the number of scout bees in each group groups = zeros(1,nGroups); % An array to keep the number of scout bees for each group recruited_bees = zeros(1,nGroups); % An array to keep the number of recruited bees for each group a = (((max - min) ./ 2) - R_ngh) ./ (nGroups^2 - 1); % GBA's parameter for setting neighborhood radiuses b = R_ngh - a; % GBA's parameter for setting neighborhood radiuses for i=1:nGroups % For each group  groups(i) = floor(k*i^2); % determine the number of scout bees in each group  if groups(i) == 0  groups(i) = 1; % there has to be at least one scout bee per each group  end  recruited_bees = (nGroups+1-i)^2; % set the number of recruited bees for each group  ngh(i) = a * i*i + b; % set the radius patch for each group end group_random = n - sum(groups); % assign the remainder bees (if any) to random search group_random = max(group_random,0); % make sure it is not a negative 번호 %는 모집단 행렬 모집단 = 0(n,maxParameters+1); 모든 입력 변수와 i=1:n 모집단에 대한 적합성을 포함한 n벌 모집단 비율(i,1:maxParameters)= generate_runtom_solution(maxParameters,min, maxParameters+), maxParameters 변수의 % 랜덤 초기화1) = evalulate_fitness(인구(i,:); 각 솔루션의 % 피트니스 평가 및 모집단 매트릭스 마지막 지수인 sortruptation_population = sortrow(인구);%는 자신의 피트니스에 기반하여 모집단을 정렬함 i=1:maxIteration % GBA의 주 루프 비인덱스 = 0; % 추적es (i.e, patches)  for g=1:nGroups % for each group of scout bees   for j = 1 : groups(g) % exploit each patch within each group  beeIndex = beeIndex + 1; % increase the counter per each patch  for i = 1 : recruited_bees(g) % for each recruited bees of the group  solution = bee_waggle_dance(sorted_population(beeIndex,1:maxParameters),ngh(g)); % seaRch 선택한 patch/solution에ngh은 반경 내에서 이웃)evaluate_fitness(해결책).%최근에 발견된 해결책의 합리성을 평가한다 만약 건강한<>sorted_population(beeIndex,maxParameters+1)%최소화 문제:더 나은 location/patch/solution은 발견된 recuiter 벌 sorted_population(beeIndex,1:maxParam.eters+1) = [solution(1 : maxParameters),fit]; % copy new solution and its fitness to the sorted population matrix  end   end  end  end  for i= 1 : group_random % For the remaining random bees  beeIndex = beeIndex + 1;  solution(beeIndex,1:maxParameters)= generate_random_solution(maxParameters,min, max); % generate a new random solution at the index beeIndex 솔루션(beeIndex,maxParameters+1)= evalu_fitness(솔루션), % corrected_population(beeIndex,::) = [솔루션(1 : maxParameters), fit], % 새 랜덤 솔루션과 그 적합성을 정렬된 모집단 매트릭스에 복사(sortrows(s(s(solated_populated_copulation); %)에 따라 모집단을 분류)solution_sofar=sorted_population(1,:);    disp('Best:');disp(Best_solution_sofar); % Display the best solution of current iteration end % end of GBA's main loop  end % end of main function %% Function Bee Waggle Dance function new_solution=bee_waggle_dance(solution, ngh, maxParameters)  new_solution(1:maxParameters) = (solution-ngh)+(2*ngh.*rand(1, maxParameter); 끝

참고 항목

참조

  1. ^ Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S, Zaidi M. 벌알고리즘. 기술 노트, 영국 카디프 대학교 제조 엔지니어링 센터, 2005.
  2. ^ a b c Pham, D.T., Castellani, M. (2009) Bees 알고리즘 – 지속적인 최적화 문제 해결을 위한 Foraging 거동 모델링. Proc. ImechE, Part C, 223(12), 2919-2938.
  3. ^ Pham, D.T. 및 Castellani, M.(2013), 자연 기반 인구 기반 연속 최적화 알고리즘의 벤치마킹 및 비교, 소프트 컴퓨팅, 1-33.
  4. ^ Pham, D.T.와 Castellani, M.(2015), 기능 최적화를 위한 도구로서의 벌 알고리즘 비교 연구, Cogent Engineering 2(1), 1091540.
  5. ^ a b c 나스린푸어, H. R., 마사 바바니, A, 테쉬네랩, M, (2017), 그룹화된 벌 알고리즘: A 그룹버전 2017, 컴퓨터 2017, 6(1), 5; (doi:10.3390/컴퓨터 6010005)
  6. ^ a b c d 테레시코 5세, 룬가로프 A, (2005) 꿀벌 포징 다이내믹스의 집단적 의사결정. 컴퓨팅 및 정보 시스템 저널 9(3), 1-7.
  7. ^ 본 프리슈, K. (1967) 벌의 춤 언어와 오리엔테이션. 매사추세츠주 캠브리지 하버드대 프레스
  8. ^ a b Pham D.T, Ghanbarzade A, Koc E, Rahim S, Zaidi M, 벌 알고리즘, 복잡한 최적화를 위한 새로운 도구, 지능형 생산 기계 및 시스템에 대한 Proc 2차 가상 콘센트(IPROMS 2006), 옥스퍼드: 2006년 454-459페이지.
  9. ^ Pham D. T, Haj Darwish A, (2008) A. Fuzzy Selection of Local Search Sites in the Bees Algorithm. 지역 검색 사이트 선택 혁신적 생산 기계 및 시스템 절차(IPROMS 2008)
  10. ^ Pham Q. T, Pham D. T, Castellani M, A 수정된 Bees 알고리즘 및 매개변수 조정을 위한 통계 기반 방법. 기계공학협회(ImechE), 파트 1: 시스템 및 제어 Eng, 2011 (doi:10.1177/0959651811422759)

외부 링크