Генетический алгоритм планирования работы группы радиотелескопов

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004.8. 023:520. 274
А. Е. Рогов
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПЛАНИРОВАНИЯ РАБОТЫ ГРУППЫ РАДИОТЕЛЕСКОПОВ
Предложен метод планирования работы группы радиотелескопов при проведении эксперимента с использованием радиоинтерферометри и со сверхдлинными базами, позволяющий представить задачу планирования как задачу дискретной оптимизации. Показана КР-полнота указанной задачи и предложен эволюционный метод ее решения.
Ключевые слова: генетический алгоритм, планирование эксперимента, радиоинтерферометрия со сверхдлинными базами.
Введение. В настоящее время радиоинтерферометрия со сверхдлинными базами (РСДБ) является одним из наиболее востребованных методов радиоастрономии. Во время проведения эксперимента РСДБ радиотелескопы по заранее составленной программе одновременно наблюдают один и тот же космический объект. Время наблюдения может составлять всего несколько минут, при этом общее количество наблюдаемых во время эксперимента объектов — несколько десятков. Как правило, общее время наблюдения непосредственно космических объектов в 2−3 раза меньше общего времени проведения эксперимента, поскольку используемые в эксперименте радиотелескопы обладают сравнительно низкой скоростью углового перемещения. В некоторых случаях для перемещения зеркала радиотелескопа от одного космического объекта к другому может потребоваться несколько минут. Снизить трудоемкость разработки программы эксперимента и увеличить количество осматриваемых объектов без увеличения продолжительности эксперимента можно путем рационального планирования экспериментов РСДБ.
Постановка задачи. Задача планирования эксперимента РСДБ может быть сформулирована следующим образом.
Необходимо найти последовательность выполнения заданий З=[Зг1Д2, …, З/к] (/ = 1, п), такую что:
к
2 с/ т/ ^ тах, к& lt-п, 1=1 к
2 ?(/ -1)/ -1Н ^ /=1
где Т — плановое время работы сети РСДБ- З{З1, З2, …, Зп} - набор заданий, подлежащих выполнению- [т] - продолжительность выполнения /-го задания- [с,] - приоритет (степень важности) задания, с/е {0,1}, ^?^?(?^?(г^+ъ — время выполнения последовательности заданий-
(1)
(2)
?ц (г)
о
?10 (г)
ё.
01 (г) 0
ё20 (г) ?21 (г)
?02 (г) ?12(1) 0
?п0(г) ?п1(г) ?п2(г)
?0п (г) ?1п (г) ?2п (г)
0
— время перехода радиотелескопов, участвующих в эксперименте, от одного космического объекта к другому- ?0() — время перехода радиотелескопов, участвующих в эксперименте,
из некоторых начальных положений (положение парковки) к первому наблюдаемому космическому объекту- di0(t) — время парковки радиотелескопов после окончания эксперимента при условии
tk+dko (tk-i)& lt-T. (3)
В простейшем случае, когда все заявки обладают одинаковым приоритетом, задача сводится к попытке выполнить в определенный интервал времени максимальное количество заявок. Оптимизация процесса при этом достигается за счет сокращения суммарного времени перенацеливания радиотелескопов, таким образом повышается степень полезного использования уникальных и дорогостоящих инструментов наблюдения.
По критерию (1) данная задача является вариантом задачи «оранце & quot- [1, 2], а по критерию (2) — нестационарной задачей «коммивояжера& quot- [3]. Обе задачи относятся к классу NP-полных задач.
Как правило, во время эксперимента некоторые объекты необходимо наблюдать неоднократно. В этом случае в список под разными номерами следует несколько раз вставить наблюдение одного и того же космического объекта. При этом в dj (t) следует запретить непосредственный переход между объектами с этими номерами, установив на соответствующих позициях значение «бесконечность& quot-.
Кроме того, эксперимент РСДБ может продолжаться несколько суток с перерывами на техническое обслуживание и отдых для персонала по 8−12 часов в сутки. В этом случае T=T1luT2iu … ^& gt-Tm. Соответственно по окончании очередного рабочего интервала T выполняется парковка всех радиотелескопов, а в начале следующего Ti+1 интервала наблюдений переход осуществляется не из положения предыдущего космического объекта, а из положения парковки. Это относительно легко учесть путем соответствующей модификации условия (3).
При необходимости обеспечить наблюдение какого-то космического объекта ровно один раз в сутки в течение всего периода наблюдений, следует использовать динамический приоритет Ci=Ci (t). Первая в сутки заявка на наблюдение указанного объекта будет иметь высокий приоритет, остальные — низкий. Возможны и более сложные случаи назначения динамического приоритета, например, когда необходимо провести наблюдение объекта два раза в сутки, один раз утром, другой — вечером. В этом случае приоритет у одной заявки должен быть высоким в начале суток, а затем убывать с течением времени, например, линейно, а у другой, наоборот, линейно возрастать от какого-либо исходного низкого значения.
Определение минимального времени перехода от объекта к объекту с учетом ограничений. Для двухосного азимутально-угломестного подвеса радиотелескопов, участвующих в эксперименте, время перехода от объекта к объекту можно определить следующим образом:
dj (t) = max (Ыа (t), AtM (t), j -1,…, AtAl (t), Athl (t), j -1),
где l — количество радиотелескопов, участвующих в эксперименте- AtAk, Athk — время перехода от i-го объекта к j-му соответственно по азимуту и углу места k-го радиотелескопа- fjk — время ближайшего восхода j-го объекта в точке расположения k-го радиотелескопа (выбирается так, чтобы tBjk-t& gt-0 если объект за горизонтом и tBjk-t& lt-0 — если над горизонтом).
Введем следующие обозначения: фг (^ - конечный угол наведения некоторого радиотелескопа на i-й космический объект- V (t) — конечная скорость движения некоторого радиотелескопа при наведении на i-й объект- ф j (t'-) — начальный угол наведения на j-й объект- Vj (t'-) — начальная скорость наведения на j-й объект.
На рис. 1 отражено время перехода от i-го объекта к j-му с учетом времени разгона Atр
и торможения At, j:
А* (*) =
фу (*'-) -Ф/ (О (V — V (*))2 V — V (*'-))2
V 2aV
где, а — максимальное ускорение радиотелескопа.
Ф
2aV
(4)

наведение на
У) Рис. 1
Знак ускорения и скорости определяется из условий
Фу (*'-)-ф/ (*).
V
¦& gt-0- aV& gt-0.
Максимальную скорость V радиотелескопа во время перехода в соотношении (4) можно определить в виде
2 = VJ (*'-)^(фу (Г)-фг ())а +
((*'-) — V (*))
(5)
Одно из значений VI или ^ в (5) выбирается из условий
фу (* '-)-Ф» (*) & gt- 0- V — у (*) & gt- 0- V (*'-) & gt- 0.
V, а '- а
Если скорость V выше перебросочной (максимальной) скорости радиотелескопа по соответствующей координатетах, то в (4) вместо V следует подставитьах.
Как правило, диапазон рабочих углов радиотелескопа допускает сопровождение космического объекта по азимуту несколькими разными способами, при этом Лц (*) = Л{ (*) —
А2г3 (*) = ЛI (*)± 360°- Л/4/5 (*) = Л1 (*)± 720° и т. д. Поэтому целесообразно при расчете А*Л (*) из всех допустимых значений выбирать наименьшее, т. е. А*Л (*) = тт (А*Л1 (*), А*л2 (*),…, АЛ (*)). Допустимым считается значение, удовлетворяющее условию
Лтт ^ Л/к (*) ^ Лтах- * е [*/0, */к ],
где Лтщ и Лтах — минимальное и максимальное рабочее значение азимута некоторого радиотелескопа соответственно- */0 — время начала наведения радиотелескопа на /-й объект- ик — время окончания наведения радиотелескопа на /-й объект.
Таким образом, зависимость времени перехода радиотелескопов от одного объекта к другому определяется движением небесной сферы и собственным движением космических объектов, вследствие чего с течением времени угловое расстояние между объектами в системе координат, связанной с подвесом каждого из радиотелескопов, изменяется. Кроме того,
проведенные исследования показали, что для большинства пар космических объектов время перехода (V) от объекта к объекту существенно зависит от времени V и имеет большой разброс значений. Пример зависимости продолжительности перехода V от времени суток представлен на рис. 2.
V, с
84 74 64 54 44 34
0: 00
4: 00
8: 00
12: 00
Рис. 2
16: 00
20: 00
ч: мин
Генетический алгоритм для решения задачи. Генетические алгоритмы [4] являются одним из высокоэффективных методов поиска оптимальных решений для различных задач науки и техники.
От других методов оптимизации генетические алгоритмы отличаются тем, что:
— оперируют в основном не параметрами задачи, а закодированным множеством параметров, переход к реальным параметрам осуществляется только при подсчете целевой функции-
— осуществляют поиск не путем оптимизации одного решения, а путем использования нескольких альтернативных вариантов на заданном множестве решений-
— для оценки качества решений используют целевую функцию, а не ее различные приращения-
— применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.
Для описания генетических алгоритмов, как правило, используются генетические операторы, которые по аналогии с алгоритмическими операторами являются конструкциями, представляющими один шаг из последовательности работы генетического алгоритма. Основными генетическими операторами являются операторы репродукции, мутации и рекомбинации. Обобщенный генетический алгоритм, в терминах генетических операторов, представлен на рис. 3.
Алгоритм решения задачи планирования эксперимента РСДБ сводится к следующему. Оператор репродукции представляет собой комбинацию операторов селекции и кроссинговера (скрещивания). Первый выбирает подходящие пары родителей для воспроизводства новых решений, а второй из выбранной
Рис. 3
пары решений-родителей воспроизводит решение-потомка. Выбрана следующая реализация оператора селекции: первое решение-родитель выбирается из списка, а второе — случайным образом, т. е. каждое решение в популяции используется для воспроизводства как минимум один раз. Выбор одного и того же родителя для репродукции исключен.
Правило реализации оператора кроссинговера определяется правилом кодирования хромосом. Для решения задачи оптимального планирования работы радиотелескопа выбран простейший способ кодирования — хромосома, т. е. список номеров объектов в порядке их отслеживания радиотелескопами. Однако из-за наличия ограничений на возможные комбинации генов (ни один объект в решении не должен повторяться дважды) использование простейших генетических операторов приводит к появлению большого количества нереальных решений. Поэтому выбран модифицированный упорядоченный оператор кроссинговера (рис. 4), с помощью которого относительно просто можно получить только допустимые решения.
1 родитель
12 8 1 10 9 21 19 20 22 23 11 7 6 5 3 2 24 15 18 16 14 17 25 13
потомок /VV^/yV/^ i& quot-7-/-/
10 21 25 19 17 20 23 11 7 6 5 3 2 24 15 18 16 14 8 13 22 9 1 12

23 10 21 25 24 2 19 3 14 17 11 20 8 13 22 15 9 1 18 5 12 б 16 7
II родитель
Рис. 4
При использовании упорядоченного оператора кроссинговера у первого родителя случайным образом выбираются две разрезающие точки, отстоящие друг от друга на половину длины хромосомы, после чего средний сегмент первого родителя, расположенный между разрезающими точками, передается потомку со случайным сдвигом влево или вправо. Остальные позиции берутся у второго родителя в упорядоченном виде слева направо, исключая элементы первого родителя. Сдвиг выбранной части хромосомы первого родителя обеспечивает эффективное изменение времени соответствующих переходов между объектами, что в силу нестационарности может значительно изменить их длину в ту или иную сторону. При классической постановке задачи выполнение сдвига не приводит к повышению эффективности работы алгоритма.
Оператор мутации реализован следующим образом: в решении случайным образом выбирается последовательность вершин и перемещается на случайное число позиций влево или вправо. Полученное таким образом новое решение добавляется к популяции. Всего мутации подвергаются 10% случайно выбранных решений в популяции.
Оператор рекомбинации в данном алгоритме является модифицированным оператором редукции. Его действие заключается в устранении повторяющихся решений из популяции, а затем — в сокращении популяции до исходных пределов. При этом все лучшие решения сохраняются.
Критерием окончания расчета служит достижение нужного количества поколений. Обычно размер популяции и количество поколений до окончания счета зависят от размерности задачи. В данном случае размер популяции был выбран равным 8N, где N — количество заявок, а количество поколений — 10N.
Значение целевой функции рассчитывается по формуле:
f = m
Z С
i=1 + п
к
V
(к Z d (i-Di C^i-i)
1-
i=1
h + dk о (tk)
да = и = 1.
Для проверки эффективности этого алгоритма была разработана программа, написанная на языке Pascal, в среде Delphi 7.0. Программа выполнялась на ПЭВМ, оснащенной процессором AMD Athlon 2500+ с 1 Гб оперативной памяти под управлением ОС Windows XP. Результаты ее работы показывают, что планирование суточного эксперимента при пятнадцатиминутном времени наблюдения объекта может быть осуществлено за «45 мин. Таким образом, можно сделать вывод, что использование разработанного генетического алгоритма для решения задачи планирования эксперимента РСДБ является достаточно эффективным.
список литературы
1. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.
2. Канцедал С. А. Дискретная математика. М.: Форум-Интра-М, 2007.
3. Рогов А. Е. Генетический алгоритм оперативного планирования работы космического радиотелескопа // Естественные и технические науки. 2008. № 2. С. 406−413.
4. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.
Алексей Евгеньевич Рогов
Сведения об авторе канд. техн. наук- Российский научно-исследовательский институт космического приборостроения, Москва- начальник сектора- E-mail: niikp@list. ru
Рекомендована институтом
Поступила в редакцию 15. 03. 10 г.

ПоказатьСвернуть
Заполнить форму текущей работой