최적화 알고리즘 참고사항 (26) 조화 검색 알고리즘
(다음 설명은 학술 용어가 아니며 모든 사람이 즐겁게 읽을 수 있도록 하기 위한 것입니다.)
하모니 검색 알고리즘은 음악의 하모니에서 영감을 받아 제안되었습니다( 2001년에 발표된) 비교적 오래된 알고리즘으로 간주됩니다. 요즘 조화 검색 알고리즘의 성능은 매우 평균적이지만 다른 알고리즘의 성능을 향상시키기 위해 다른 알고리즘과 통합할 수 있는 도메인 검색을 위한 구체적인 구현 방법을 제안합니다.
조화를 단독으로 보는 것은 큰 의미가 없습니다. 조화의 한 차원은 그룹 내에서 해당 차원의 모든 값을 기반으로 필드 범위를 결정하고 필드를 수행합니다. 찾다.
원래 알고리즘은 음악에서 영감을 얻었기 때문에 그것이 해결하는 목표 문제도 이산 문제입니다.
하모니 검색 알고리즘에서 개인을 하모니 메모리(HM)라고 하며, 그룹 내 하모니 메모리 개수는 N, D는 각 하모니 메모리의 음표(차원) 수입니다. 각 차원의 값 범위는 입니다.
원래 알고리즘의 각 차원의 값 범위 L은 정렬된 이산 값의 집합, 즉 지정된 변수 값 중 하나가 하모니 메모리 값으로 선택됩니다.
각 하모니 메모리는 반복할 때마다 해당 필드의 값으로만 변경할 수 있습니다.
하모니 알고리즘에는 두 가지 작업이 있습니다: 1. 필드로 이동, 2. 필드로의 돌연변이
확률은 HMCR(Harmony Memory 고려 비율)과 피치 조정 비율입니다. (파).
그 중 HMCR 값은 약 0.95, PAR 값은 약 0.10 정도이다.
이 알고리즘의 단계와 값은 유전 알고리즘을 참조하며, 둘 다 이산적인 문제를 다루도록 설계되었음을 알 수 있습니다.
예시는 다음과 같습니다.
하모니 메모리 개수는 3개, 차원은 2입니다. 1차원의 값 범위는 {A,B,C,D, E,F ,G}, 두 번째 차원의 값은 {3,4,5,6}입니다.
1세대에서 세 개인의 가치는 다음과 같다
2세대를 계산할 때 각 개인의 각 차원은 동네의 가치까지만 갈 수 있다 그 차원의.
개인 1_2가 얻을 수 있는 가치는 (A,3) (A,4) (B,3) (B,4)입니다.
개인 2_2가 얻을 수 있는 가치는 다음과 같습니다. (F ,4)(F,5)(F,6)(G,4)(G,5)(G,6)
3_2 개인이 얻을 수 있는 값은 (C,3) (C,4)(C,5)(D,3)(D,4)(D,5)(E,3)(E,4)(E,5),
이는 그림에는 세 사람이 접근할 수 있는 동네가 표시되어 있습니다.
돌연변이 연산도 매우 간단합니다. 이 연산은 유전자 알고리즘의 돌연변이 연산의 벤치마크입니다.
이웃 작업으로 변경할 때 차원은 현재 기존 값으로 변경되지 않습니다.
예를 들어 개인 1_1이 첫 번째 차원을 변경하는 경우 모집단의 첫 번째 차원 값이 {A, D, G}이므로 이 차원은 {B, C, E, F만 사용할 수 있습니다. }.
아래 그림에서 색칠된 블록은 돌연변이 연산으로 도달할 수 없는 위치를 벗어났고, 빈 위치는 돌연변이 연산으로 도달할 수 있는 위치입니다. (빈 자리가 없으면 어쩌지? 확률은 아주 작다. 결국 개별 위치는 해 공간 위치보다 훨씬 적다. 이런 일이 발생하면 위치를 변경하거나 무작위화하지 않아도 괜찮을 것이다)
반복 후 새 위치가 더 좋을 경우 하모니 메모리는 유지되고 가장 나쁜 하모니 메모리는 제거됩니다.
마지막으로 기사에서는 찾은 솔루션이 최적 솔루션인지 판단하는 판단 기능을 제공합니다.
그 중 Hr=HMCR, Hi는 반복 횟수에 따라 증가합니다. 이 차원에서 더 나은 가치가 발견됩니다. 이 공식의 기능은 주로 알고리즘 프로그램을 종료할 시기를 결정하는 것입니다. 그러나 최대 반복 횟수를 사용하여 알고리즘 프로그램을 종료하기 전에는 거의 쓸모가 없는 것 같습니다.
알고리즘 프로세스도 매우 간단합니다.
하모니 검색의 원래 알고리즘은 음악의 조화 개념을 기반으로 하며 모든 알고리즘도 이산적입니다. 유전 알고리즘은 이산 솔루션 공간 문제를 처리하는 데 사용됩니다. 그렇다면 연속적인 수치 문제를 처리할 수 있도록 조화 검색 알고리즘을 수정하는 방법은 무엇입니까?
가장 중요한 점은 '이웃'을 어떻게 처리하느냐 하는 점이다. 연속해 공간에서는 점의 영역을 정의하기 어렵고, 각 차원의 값의 개수도 무한하다. .
조화 검색 알고리즘의 이웃을 정의하는 데는 여러 가지 아이디어가 있습니다.
1. 모든 개인을 개인의 이웃으로 정의합니다. 즉, 매번 그룹에서 무작위로 하나를 선택합니다. 개인 - 이 차원은 선택한 개인으로 이동합니다.
그 중 D, E, F는 각각 AB, AC, BC의 중간점입니다. A, B, C의 세 가지 조화 기억의 이웃은 의 세 지점에 의해 결정됩니다. DEF와 솔루션 공간의 경계입니다. 이 이웃은 아이디어 2보다 작으며 겹치는 부분이 없습니다.
특정 차원의 두 도메인 값이 동일할 경우 위(2차원) 이웃(표면)이 이웃(선)으로 퇴화되어 차원이 빠르게 수렴될 수 있습니다. 이 값이므로 이때 중복된 값을 무시하고 이웃을 다시 확장(표면이 됨)해야 합니다.
연속 알고리즘에서는 HCMR 조건이 충족되면 지정된 값을 제거할 수 없으므로 알고리즘은 PAR 조건이 충족되면 위의 색상 블록을 기반으로 주변의 값을 무작위로 선택합니다. , 단순화를 위해 해당 차원의 임의 고조파 메모리로 직접 이동합니다.
이후의 실험은 연속함수의 최대값을 구하는 것이기 때문에 위에서 언급한 연속알고리즘에서 세 가지 아이디어를 선택하겠습니다.
피트니스 기능.
실험 1: 아이디어 1
이미지에서 볼 수 있듯이 아이디어 1의 전략은 유전자 알고리즘과 매우 유사하며 이동 경로는 십자가와 유사합니다. 결국에는 올바른 해 근처로 수렴됩니다. 초기 탐색은 주로 이웃 이동에 의존하는 반면, 후기 탐색은 돌연변이에 의존합니다.
결과에서도 알 수 있듯이 유전 알고리즘은 그다지 안정적이지 않습니다. 인접한 조화 메모리로 날아가는 전략이므로 범위가 상대적으로 큽니다. , 정확성은 전적으로 돌연변이에 달려 있습니다.
실험 2: 아이디어 2
인구의 검색 경로가 실험 1처럼 직선 교차 경로가 아니며 수렴 속도도 이미지를 통해 알 수 있습니다. 훨씬 느리지만 여전히 올바른 솔루션에 가깝게 수렴할 수 있습니다.
두 번째 아이디어의 결과가 훨씬 더 좋고 안정적이라는 것을 결과에서 알 수 있습니다(잘못, 행운, 이전 실험에서 나쁜 결과가 발생하여 재현할 수 없음). 이 아이디어의 동네 검색 영역은 더 커지고, 개인 간의 동네에는 중첩이 있기 때문에 나쁜 위치로 수렴할 수도 있지만 확률도 적습니다.
실험 3: 아이디어 3
이미지가 점차 뱀으로 변해갑니다! 초기 이미지는 첫 번째 아이디어와 비슷하고, 이후 이미지는 유전자 알고리즘과 조금 유사하다. 동네의 면적이 점차 긴 띠로 줄어드는 것일 수도 있지만, 결국 '욕심쟁이 뱀'이 되는 것이다. 아직도 음식을 먹습니다.
결과를 보면 아이디어 3의 안정성이 그다지 좋지 않다는 것을 알 수 있습니다. 모든 개인이 한 지점으로 수렴하면 아이디어 1의 교체 작업이 시작됩니다. , 값은 동일하며 더 나은 위치를 찾기가 어렵고 좋지 않은 결과가 발생합니다. 여기에서 임의성 범위를 늘려 로컬 최적 상태에서 벗어날 수도 있습니다.
하모니 검색 알고리즘은 하모니 음악 이론에 대한 지식을 바탕으로 제안된 알고리즘입니다. 음표는 이산값이므로 알고리즘도 유전 알고리즘을 벤치마킹하므로 이산 문제에 대해서도 원래의 알고리즘을 제안한다. 연속성 문제를 해결하려면 이웃 개념을 확장하고 수정해야 하며 최종 효과는 유전 알고리즘과 크게 다르지 않습니다.
현재 관점에서 볼 때 조화 탐색 알고리즘의 효과는 실제로 평균 수준이며 이에 대한 표적화된 연구는 많지 않습니다. 이 알고리즘은 주로 해법 공간을 횡단하는 방법을 제안합니다. 유전자 알고리즘. 따라서 많은 논문에서 조화탐색 알고리즘과 기타 알고리즘을 활용한 개선 사례를 볼 수 있다.
유전자 알고리즘에 비해 조화 탐색 알고리즘의 이웃 개념은 유전자 알고리즘의 유전자를 선에서 표면으로 확장합니다. 이는 SVM과 컨볼루셔널 신경망의 관계와 다소 유사하지만, 유전자 알고리즘과 조화 검색 알고리즘의 차이는 그리 크지 않고 검색 방법만 다릅니다.
참고 자료
Geem Z W , Kim J H , Loganathan G V . 새로운 경험적 최적화 알고리즘: 하모니 검색[J], 2001, 2(2):60-68. 코드: 4udl
Omran M, Mahdavi M. 글로벌 최고의 조화 검색[J], Applied Mathematics and Computation, 2008, 198(2):643-656 추출 코드: pk3s
다음 지표는 순전히 개인적인 것이며 참조용입니다.
목차
이전 최적화 알고리즘 참고 사항(25개) Moth to Flame 알고리즘
다음 기사 최적화 알고리즘 참고 사항(27개) 하루살이 알고리즘