The problem of planning of cellular networks. Showing multi-criteria approach to its solution. Discusses genetic algo-rithms used to solve such problems
cellular network planning, metaheuristics, genetic algorithms, optimization
I.Введение
На сегодняшний день большое число задач оптимизации сложных систем из различных областей науки и техники не могут быть решены с помощью аналитического моделирования. Во многих проблемах реальной жизни, рассматриваемые цели конфликтуют друг с другом, и оптимизация решения по одной цели может привести к неприемлемым результатам в отношении других целей. Разумным решением такой проблемы является исследование множества решений, каждое из которых удовлетворяет цели на приемлемом уровне, без доминирования какого-либо из решений.
II. Планирование телекоммуникационных сетей
При планировании сотовой телекоммуникационной сети инженеру планирования необходимо рассматривать три критерия [2]:
- критерий функциональной надежности сети (Р);
- критерий стоимости сети (К);
- критерий пропускной способности (С).
Таким образом, задача состоит в построении недорогой высокоэффективной и отказоустойчивой сети. Иногда можно найти оптимальное решение, удовлетворяющее всем критериям. Однако чаще всего критерии несогласованны друг с другом и изменения в одном критерии ведут к изменениям в других. В таком случае в качестве решения будет выбран компромисс между заданными критериями. При этом инженеру планирования необходимо рассматривать наилучшие возможные варианты построения телекоммуникационной сети. Существует множество способов определить набор «наилучших вариантов», но наиболее известным является множество Парето на пространстве возможных решений [1].
Рассмотрим два варианта построения сети, Mи N. Говорят, что М доминирует N по Парето, если М не хуже N по всем критериям и хотя бы по одному критерию превосходит N. В таком случае в качестве решения задачи выбирается М, так как оно не ступает Nпо всем критериям, а в некоторых случаях превосходит. Если рассмотреть два критерия (стоимость и надежность), то область решений, доминируемых по Парето решением М можно представить следующим образом (рис. 1):
1. Luke Sean. Essentials of metaheuristics. - Vol. 3. -Raleigh : Lulu, 2009. - 251r.
2. Skovpin, M. S. Planirovanie i optimizatsiya setey sotovoy svyazi [Tekst] / M. S. Skovpin, M. L. Lapshina. Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta. - 2013. - T. 9. -№ 6-3. - S. 81-84.
3. Brockhoff, D. Analyzing hypervolume indicator based algorithms [Tekst] / D. Brockhoff, F. Tobias, N. Frank. Parallel Problem Solving from Nature-PPSN X. - 2008- P. 651-660.
4. Srinivas, N. Multiobjective optimization using nondominated sorting in genetic algorithms [Tekst] / N. Srinivas , K. Deb. Evolutionary Computation. - 1994. - P. 221-248.
5. Zitzler, E. SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization [Tekst] / E. Zitzler, M. Laumanns, L. Thiele. Evolutionary Methods for Design, Optimization, and Control. - 2002. - P. 19-26.
