Обработка сигналов в системах телекоммуникаций (стр. 5 )

При таком подходе только наилучшему в глобальном смысле муравью (т.е. муравью, который нашел наиболее оптимальное расположение базовых станций с начала эксперимента) позволено откладывать феромон. Этот выбор вместе с использованием правила перехода преднамеренно делает поиск более направленным.

В общем виде муравьиный алгоритм представлен на рисунке 1.

В момент, когда все муравьи сгенерировали тур, лучший муравей откладывает (в конце итерации ) свой феромон, определяя таким образом «привилегированный тур» для поиска в следующей итерации алгоритма . Фактически, в течение итерации  муравьи будут видеть ребра, принадлежащие наилучшему туру, как более привлекательные и будут выбирать их с высокой вероятностью.

 

Рис. 1 – Муравьиный алгоритм

 

В заключение можно сказать, что муравьиные алгоритмы являются новым интересным подходом для параллельной стохастической оптимизации задачи оптимального размещения базовых станций.

Литература

1.     . Задача синтеза топологической структуры беспроводной сети // Труды IX Международной конференции «Цифровая обработка сигналов и ее применение», Москва, 2007. – С. 168-171.

2.     . Применение генетических алгоритмов для решения задачи оптимального размещения базовых станций // Труды X Международной конференции «Цифровая обработка сигналов и ее применение», Москва, 2008. – С. 312-314.

3.     . О преимуществе генетического подхода в задаче синтеза беспроводных сетей передачи информации // Труды IX Международной конференции «Кибернетика и высокие технологии XXI века», Воронеж, 2008. – С. 488-492.

4.     TSPLIB: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp

5.     Dorigo M., Gambardella L. M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation. - 1997. – Vol 1, № 1. - P. 53-66.

 

«NATURAL COMPUTING» AS APPROACH TO SOLVING HARD PROBLEMS IN TELECOMMUNICATIONS

Ermolaev S.

PSUTI

In suggested below article the task of designing broadband wireless access, namely, base stations accommodation optimization, is considered. Existing classical techniques of solving this problem (branch and bound method, cutting planes and their combination) do not give good results. In this context, to solve this task on base genetic algorithm is suggested in given paper. Results of simulations are proving effectiveness of this direction.

Also this paper introduces ant colony algorithms, a distributed algorithm that is applied to the base stations accommodation optimization. In ant algorithms, a set of cooperating agents called ants cooperate to find good solutions to problem. Ants cooperate using an indirect form of communication mediated by pheromone they deposit on the edges of the graph while building solutions.

The natural metaphor on which ant algorithms are based is that of ant colonies. Real ants are capable of finding the shortest path from a food source to their nest without using visual cues by exploiting pheromone information. While walking, ants deposit pheromone on the ground, and follow, in probability, pheromone previously deposited by other ants.

The main novel idea introduced by ant algorithms, which will be discussed in the remainder of the paper, is the synergistic use of cooperation among many relatively simple agents which communicate by distributed memory implemented as pheromone deposited on edges of a graph.

In fact, ant algorithm works as follows:  ants are initially positioned on  places-candidates chosen according to some initialization rule (e.g., randomly). Each ant builds a tour (i.e., a feasible solution to the task of base stations accommodation optimization) by repeatedly applying a stochastic the state transition rule. While constructing its tour, an ant also modifies the amount of pheromone on the visited edges by applying the local updating rule. Once all ants have terminated their tour, the amount of pheromone on edges is modified again (by applying the global updating rule).

Once all the ants have generated a tour, the best ant deposits (at the end of iteration ) its pheromone, defining in this way a “preferred tour” for search in the following algorithm iteration . In fact, during iteration  ants will see edges belonging to the best tour as highly desirable and will choose them with high probability.

In conclusion, this paper has shown that ant algorithm is an interesting novel approach to parallel stochastic optimization to the task of base stations accommodation optimization.

¾¾¾¾¾¨¾¾¾¾¾