고성능 컴퓨팅에 대한 요구를 충족시키기 위해 24시간 내내 개발되는 다양한 전략과 도구로 인해 알고리즘 세계는 아름답습니다. 실제로 알고리즘이 자연 법칙에서 영감을 얻으면 흥미로운 결과가 관찰됩니다. 진화 알고리즘은 이러한 종류의 알고리즘에 속합니다. 이러한 알고리즘은 인간 게놈의 특정 행동과 진화적 특성을 모방하도록 설계되었습니다. 더욱이 이러한 알고리즘 설계는 인간에게만 국한되는 것이 아니라 특정 동물의 자연스러운 행동에서도 영감을 받을 수 있습니다. 이러한 방법론을 제작하는 기본 목표는 지금까지 기존 방법으로는 해결할 수 없었던 문제에 대해 현실적이고 관련성이 높으면서도 저렴한 솔루션을 제공하는 것입니다.
따라서 이러한 진화 알고리즘을 기반으로 다양한 최적화 기술이 진화하여 메타 휴리스틱스의 영역이 열렸습니다. 메타휴리스틱 두 개의 그리스어 단어, 즉, 메타 의미 한 레벨 위 그리고 휴리스킨 의미 찾다 . PSO(Particle Swarm Optimization) 및 ACO(Ant Colony Optimization)와 같은 알고리즘은 떼 지능 및 메타 휴리스틱스의 예입니다. 떼 지능의 목표는 개미, 흰개미, 벌, 말벌과 같은 사회적 곤충과 새 떼나 물고기 떼와 같은 기타 동물 사회의 집단적 행동에서 영감을 얻어 지능형 다중 에이전트 시스템을 설계하는 것입니다.
배경:
Ant Colony Optimization 기술은 순전히 다음에서 영감을 받았습니다. 채집 개미 군체의 행동은 1990년대 Marco Dorigo에 의해 처음 소개되었습니다. 개미는 개별 종으로서보다는 공동체의 생존과 유지를 선호하는 진사회성 곤충입니다. 그들은 소리, 촉각, 페로몬을 통해 서로 소통합니다. 페로몬 개미는 같은 종의 구성원에게 사회적 반응을 유발하는 유기 화학 화합물입니다. 이는 분비하는 개인의 신체 외부에서 호르몬처럼 작용하여 수용하는 개인의 행동에 영향을 미칠 수 있는 화학 물질입니다. 대부분의 개미는 땅에 살기 때문에 토양 표면을 사용하여 다른 개미가 따라갈(냄새를 맡을) 수 있는 페로몬 흔적을 남깁니다.
개미는 공동체 둥지에 살고 있으며 ACO의 기본 원리는 가능한 최단 경로에서 먹이를 찾기 위해 둥지에서 개미의 움직임을 관찰하는 것입니다. 처음에 개미는 둥지 주변에서 먹이를 찾기 위해 무작위로 움직이기 시작합니다. 이 무작위 검색은 둥지에서 먹이 공급원까지 여러 경로를 열어줍니다. 이제 개미는 음식의 질과 양에 따라 음식의 일부를 필요한 페로몬 농도와 함께 돌아오는 경로로 운반합니다. 이러한 페로몬 실험에 따라 다음 개미가 특정 경로를 선택할 확률이 식량 공급원에 대한 안내 요소가 될 것입니다. 분명히 이 확률은 농도와 페로몬의 증발 속도에 기초합니다. 또한 페로몬의 증발 속도도 결정적인 요소이기 때문에 각 경로의 길이를 쉽게 설명할 수 있음을 관찰할 수 있습니다.
위 그림에서는 단순화를 위해 먹이 공급원과 개미집 사이에 가능한 두 가지 경로만 고려했습니다. 단계는 다음과 같이 분석할 수 있습니다.
- 1단계: 모든 개미가 둥지에 있습니다. 환경에는 페로몬 함량이 없습니다. (알고리즘 설계의 경우 확률을 방해하지 않고 잔류 페로몬 양을 고려할 수 있습니다.) 2단계: 개미는 각 경로를 따라 동일한(개당 0.5) 확률로 검색을 시작합니다. 분명히 곡선 경로는 더 길기 때문에 개미가 먹이 공급원에 도달하는 데 걸리는 시간이 다른 경로보다 더 깁니다. 3단계: 개미는 더 짧은 경로를 통해 먹이원에 더 일찍 도달합니다. 이제 그들은 분명히 비슷한 선택 딜레마에 직면해 있지만 이번에는 이미 이용 가능한 더 짧은 경로를 따라 페로몬 흔적이 있기 때문에 선택 확률이 더 높습니다. 4단계: 더 짧은 경로를 통해 더 많은 개미가 돌아오고 이후 페로몬 농도도 증가합니다. 더욱이 증발로 인해 더 긴 경로의 페로몬 농도가 감소하여 다음 단계에서 이 경로를 선택할 확률이 감소합니다. 따라서 전체 식민지는 점점 더 높은 확률로 더 짧은 경로를 사용합니다. 따라서 경로 최적화가 달성됩니다.
알고리즘 설계:
위의 개미 행동과 관련하여 이제 알고리즘 설계를 개발할 수 있습니다. 단순화를 위해 단일 먹이원과 단일 개미 군체를 두 가지 가능한 이동 경로로 간주했습니다. 전체 시나리오는 개미 서식지와 먹이 공급원이 정점(또는 노드) 역할을 하는 가중치 그래프를 통해 실현될 수 있습니다. 경로는 가장자리 역할을 하고 페로몬 값은 가장자리와 관련된 가중치입니다.
그래프를 보자 G = (V, E) 여기서 V, E는 그래프의 모서리와 꼭지점입니다. 우리가 고려한 정점은 다음과 같습니다. 안에에스 (소스 정점 - 개미 군집) 및 안에디 (목적지 정점 – 식량 공급원), 두 가장자리는 그리고1 그리고 그리고2 길이가 있는 엘1 그리고 엘2 각각 할당됩니다. 이제 관련 페로몬 값(강도를 나타냄)은 다음과 같이 가정할 수 있습니다. 아르 자형1 그리고 아르 자형2 정점 E의 경우1그리고 E2각기. 따라서 각 개미에 대해 경로 선택의 시작 확률(E 사이1그리고 E2)는 다음과 같이 표현될 수 있다:
분명히 R이라면1>R2, E를 선택할 확률1더 높고 그 반대도 마찬가지입니다. 이제 이 최단 경로로 돌아오는 동안 E라고 말하세요.나, 해당 경로에 대한 페로몬 값이 업데이트됩니다. 업데이트는 경로의 길이와 페로몬의 증발 속도를 기반으로 수행됩니다. 따라서 업데이트는 다음과 같이 단계적으로 실현될 수 있습니다.
- 경로 길이에 따라 –
위 업데이트에서는 i = 1, 2이고 'K'가 모델의 매개변수로 사용됩니다. 또한 업데이트는 경로 길이에 따라 달라집니다. 경로가 짧을수록 페로몬이 더 많이 추가됩니다. 페로몬의 증발속도에 따라 -
매개변수 'v'는 페로몬 증발을 조절하는 간격(0, 1]에 속하며, i = 1, 2입니다.
각 반복에서 모든 개미는 소스 정점 V에 배치됩니다.에스(개미 식민지). 그 후 개미는 V에서 이동합니다.에스V에게디(먹이 공급원) 1단계를 수행합니다. 다음으로 모든 개미는 2단계를 기반으로 선택한 경로를 강화하고 돌아오는 여행을 수행합니다.
유사 코드:
Procedure AntColonyOptimization: Initialize necessary parameters and pheromone trials; while not termination do : Generate ant population; Calculate fitness values associated with each ant; Find best solution through selection methods; Update pheromone trial; end while end procedure>
위 의사코드의 페로몬 업데이트와 적합도 계산은 위에서 언급한 단계별 구현을 통해 확인할 수 있습니다.
따라서 ACO 최적화 기술의 도입이 확립되었습니다. ACO의 적용은 유명한 문제와 같은 다양한 문제로 확장될 수 있습니다. TSP(여행하는 세일즈맨 문제) .
참고자료:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf