MAX-MIN Ant System 개략적 설명

기본적 특징

1. AS(Ant System)에 기반한다.
2. Iteration에서 가장 좋은 해를 찾은 개미 또는 best-so-far에 해당하는 개미만 pheromone trail이 가능하다.
3. Pheromone trail 값의 범위를 제한한다.(Max-Min) 이때 pheromone evaporation rate는 작은 값을 갖는다.
4. Pheromone trail의 초기값은 upper pheromone trail limit으로 초기화 된다.
5. 몇 번의 연이은 iteration 동안 해의 개선이 이루어지지 않거나 system이 stagnation에 빠진 경우 pheromone trail을 ^[각주:1]로 재초기화 한다.

절차

1. 모든 개미가 해를 구성
2. Evaporation 적용(AS와 동일)
3. Pheromone deposit
1. Iteration best 또는 best-so-far만 pheromone deposit (번갈아가는 전략 사용)
2. 시간이 지남에 따라 (best-so-far의 update 기회) 증가
4. Pheromone trail을 통해 stagnation이 관측 되거나 몇 번의 iteration이 지나도 개선이 없으면 pheromone 재초기화
5. termination condition이 될 때까지 반복

수식

1. 
2. 
1. ^[각주:2]

References

Ant Colony Optimization, Marco Dorigo & Thomas Stützle, The MIT Press, 2004.

---

1. arc에 놓여진 pheromone trail의 최대량 [본문으로]
2. avg is the average number of different choices available to an ant at each step while constructing a solution (for a justification of these values see Stutzle & Hoos (2000)) [본문으로]