GENETIC ALGORITHM OF RADIO TELESCOPE GROUP OPERATION PLANNING
Генетический алгоритм планирования работы группы радиотелескопов
7
УДК 004.8.023:520.274
А. Е. РОГОВ
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПЛАНИРОВАНИЯ РАБОТЫ ГРУППЫ РАДИОТЕЛЕСКОПОВ
Предложен метод планирования работы группы радиотелескопов при проведении эксперимента с использованием радиоинтерферометри и со сверхдлинными базами, позволяющий представить задачу планирования как задачу дискретной оптимизации. Показана NP-полнота указанной задачи и предложен эволюционный метод ее решения.
Ключевые слова: генетический алгоритм, планирование эксперимента, радиоинтерферометрия со сверхдлинными базами.
Введение. В настоящее время радиоинтерферометрия со сверхдлинными базами (РСДБ) является одним из наиболее востребованных методов радиоастрономии. Во время проведения эксперимента РСДБ радиотелескопы по заранее составленной программе одновременно наблюдают один и тот же космический объект. Время наблюдения может составлять всего несколько минут, при этом общее количество наблюдаемых во время эксперимента объектов — несколько десятков. Как правило, общее время наблюдения непосредственно космических объектов в 2—3 раза меньше общего времени проведения эксперимента, поскольку используемые в эксперименте радиотелескопы обладают сравнительно низкой скоростью углового перемещения. В некоторых случаях для перемещения зеркала радиотелескопа от одного космического объекта к другому может потребоваться несколько минут. Снизить трудоемкость разработки программы эксперимента и увеличить количество осматриваемых объектов без увеличения продолжительности эксперимента можно путем рационального планирования экспериментов РСДБ.
Постановка задачи. Задача планирования эксперимента РСДБ может быть сформулирована следующим образом.
Необходимо найти последовательность выполнения заданий З=[Зi1,Зi2, …, Зik] ( i =1, n ), такую что:
k
∑ ci τi → max , k0 если объект за горизонтом и tвjk–t
0;
aV > 0 .
Максимальную скорость V радиотелескопа во время перехода в соотношении (4) можно
определить в виде
( ) ( )V12 =Vj (t′) ±
ϕ j (t′) − ϕi (t )
a+
V j (t′) −Vi (t) 2
2
.
(5)
Одно из значений V1 или V2 в (5) выбирается из условий
ϕ
j
(t
′) −
V
ϕi
(
t
)
>
0;
V
−Vi a
(t)
>
0;
V
−V j a
(t
′)
>
0
.
Если скорость V выше перебросочной (максимальной) скорости радиотелескопа по со-
ответствующей координате Vmax, то в (4) вместо V следует подставить Vmax. Как правило, диапазон рабочих углов радиотелескопа допускает сопровождение косми-
ческого объекта по азимуту несколькими разными способами, при этом Ai1 (t ) = Ai (t ) ;
Ai2,i3 (t ) = Ai (t ) ± 360°; Ai4,i5 (t ) = Ai (t ) ± 720° и т.д. Поэтому целесообразно при расчете
∆tA (t ) из всех допустимых значений выбирать наименьшее, т.е.
∆tA (t ) = min (∆tA1 (t ), ∆tA2 (t ),..., ∆tAS (t )) . Допустимым считается значение, удовлетворяю-
щее условию
Amin ≤ Aik (t ) ≤ Amax ; t∈[ti0 ,tik ],
где Amin и Amax — минимальное и максимальное рабочее значение азимута некоторого радиотелескопа соответственно; ti0 — время начала наведения радиотелескопа на i-й объект; tik — время окончания наведения радиотелескопа на i-й объект.
Таким образом, зависимость времени перехода радиотелескопов от одного объекта к другому определяется движением небесной сферы и собственным движением космических объектов, вследствие чего с течением времени угловое расстояние между объектами в системе координат, связанной с подвесом каждого из радиотелескопов, изменяется. Кроме того,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
10 А. Е. Рогов
проведенные исследования показали, что для большинства пар космических объектов время перехода dij (t) от объекта к объекту существенно зависит от времени t и имеет большой разброс значений. Пример зависимости продолжительности перехода t от времени суток представлен на рис. 2.
t, с
84
74 64
54
44
34 0:00
4:00
8:00 12:00 16:00 20:00 ч:мин
Рис. 2
Генетический алгоритм для решения задачи. Генетические алгоритмы [4] являются
одним из высокоэффективных методов поиска оптимальных решений для различных задач
науки и техники.
Начало
От других методов оптимизации генетические алгоритмы отличаются тем, что:
Формирование исходной популяции
— оперируют в основном не параметрами задачи, а закодированным множеством параметров, переход к реальным параметрам осуществляется только при подсчете целевой функции;
— осуществляют поиск не путем оптимизации одного реше-
ния, а путем использования нескольких альтернативных вариантов
на заданном множестве решений;
Репродукция
— для оценки качества решений используют целевую функ-
цию, а не ее различные приращения;
Мутация
— применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.
Для описания генетических алгоритмов, как правило, исполь-
Рекомбинация
зуются генетические операторы, которые по аналогии с алгоритми-
ческими операторами являются конструкциями, представляющими
Расчет окончен?
Нет
один шаг из последовательности работы генетического алгоритма. Основными генетическими операторами являются операторы репродукции, мутации и рекомбинации. Обобщенный генетический
Да алгоритм, в терминах генетических операторов, представлен на
Конец
рис. 3.
Рис. 3
Алгоритм решения задачи планирования эксперимента РСДБ сводится к следующему. Оператор репродукции представляет со-
бой комбинацию операторов селекции и кроссинговера (скрещивания). Первый выбирает
подходящие пары родителей для воспроизводства новых решений, а второй из выбранной
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Генетический алгоритм планирования работы группы радиотелескопов
11
пары решений-родителей воспроизводит решение-потомка. Выбрана следующая реализация оператора селекции: первое решение-родитель выбирается из списка, а второе — случайным образом, т.е. каждое решение в популяции используется для воспроизводства как минимум один раз. Выбор одного и того же родителя для репродукции исключен.
Правило реализации оператора кроссинговера определяется правилом кодирования хромосом. Для решения задачи оптимального планирования работы радиотелескопа выбран простейший способ кодирования — хромосома, т.е. список номеров объектов в порядке их отслеживания радиотелескопами. Однако из-за наличия ограничений на возможные комбинации генов (ни один объект в решении не должен повторяться дважды) использование простейших генетических операторов приводит к появлению большого количества нереальных решений. Поэтому выбран модифицированный упорядоченный оператор кроссинговера (рис. 4), с помощью которого относительно просто можно получить только допустимые решения.
Рис. 4
При использовании упорядоченного оператора кроссинговера у первого родителя случайным образом выбираются две разрезающие точки, отстоящие друг от друга на половину длины хромосомы, после чего средний сегмент первого родителя, расположенный между разрезающими точками, передается потомку со случайным сдвигом влево или вправо. Остальные позиции берутся у второго родителя в упорядоченном виде слева направо, исключая элементы первого родителя. Сдвиг выбранной части хромосомы первого родителя обеспечивает эффективное изменение времени соответствующих переходов между объектами, что в силу нестационарности может значительно изменить их длину в ту или иную сторону. При классической постановке задачи выполнение сдвига не приводит к повышению эффективности работы алгоритма.
Оператор мутации реализован следующим образом: в решении случайным образом выбирается последовательность вершин и перемещается на случайное число позиций влево или вправо. Полученное таким образом новое решение добавляется к популяции. Всего мутации подвергаются 10 % случайно выбранных решений в популяции.
Оператор рекомбинации в данном алгоритме является модифицированным оператором редукции. Его действие заключается в устранении повторяющихся решений из популяции, а затем — в сокращении популяции до исходных пределов. При этом все лучшие решения сохраняются.
Критерием окончания расчета служит достижение нужного количества поколений. Обычно размер популяции и количество поколений до окончания счета зависят от размерности задачи. В данном случае размер популяции был выбран равным 8N, где N — количество заявок, а количество поколений — 10N.
Значение целевой функции рассчитывается по формуле:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
12 А. Е. Рогов
∑ ∑⎛
⎜
k
ci
⎞ ⎟
⎛ ⎜
k
d(i−1)i
(
ti−1
)
⎞ ⎟
f
=
m
⎜ ⎜
i=1
k
⎝⎜⎜
⎟ ⎟
+
n
⎜⎜1−
⎟⎠⎟ ⎝⎜⎜
i=1
tk
+ dk0 (tk
)
⎟ ⎟
,
m
=
n
=
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 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
7
УДК 004.8.023:520.274
А. Е. РОГОВ
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПЛАНИРОВАНИЯ РАБОТЫ ГРУППЫ РАДИОТЕЛЕСКОПОВ
Предложен метод планирования работы группы радиотелескопов при проведении эксперимента с использованием радиоинтерферометри и со сверхдлинными базами, позволяющий представить задачу планирования как задачу дискретной оптимизации. Показана NP-полнота указанной задачи и предложен эволюционный метод ее решения.
Ключевые слова: генетический алгоритм, планирование эксперимента, радиоинтерферометрия со сверхдлинными базами.
Введение. В настоящее время радиоинтерферометрия со сверхдлинными базами (РСДБ) является одним из наиболее востребованных методов радиоастрономии. Во время проведения эксперимента РСДБ радиотелескопы по заранее составленной программе одновременно наблюдают один и тот же космический объект. Время наблюдения может составлять всего несколько минут, при этом общее количество наблюдаемых во время эксперимента объектов — несколько десятков. Как правило, общее время наблюдения непосредственно космических объектов в 2—3 раза меньше общего времени проведения эксперимента, поскольку используемые в эксперименте радиотелескопы обладают сравнительно низкой скоростью углового перемещения. В некоторых случаях для перемещения зеркала радиотелескопа от одного космического объекта к другому может потребоваться несколько минут. Снизить трудоемкость разработки программы эксперимента и увеличить количество осматриваемых объектов без увеличения продолжительности эксперимента можно путем рационального планирования экспериментов РСДБ.
Постановка задачи. Задача планирования эксперимента РСДБ может быть сформулирована следующим образом.
Необходимо найти последовательность выполнения заданий З=[Зi1,Зi2, …, Зik] ( i =1, n ), такую что:
k
∑ ci τi → max , k0 если объект за горизонтом и tвjk–t
0;
aV > 0 .
Максимальную скорость V радиотелескопа во время перехода в соотношении (4) можно
определить в виде
( ) ( )V12 =Vj (t′) ±
ϕ j (t′) − ϕi (t )
a+
V j (t′) −Vi (t) 2
2
.
(5)
Одно из значений V1 или V2 в (5) выбирается из условий
ϕ
j
(t
′) −
V
ϕi
(
t
)
>
0;
V
−Vi a
(t)
>
0;
V
−V j a
(t
′)
>
0
.
Если скорость V выше перебросочной (максимальной) скорости радиотелескопа по со-
ответствующей координате Vmax, то в (4) вместо V следует подставить Vmax. Как правило, диапазон рабочих углов радиотелескопа допускает сопровождение косми-
ческого объекта по азимуту несколькими разными способами, при этом Ai1 (t ) = Ai (t ) ;
Ai2,i3 (t ) = Ai (t ) ± 360°; Ai4,i5 (t ) = Ai (t ) ± 720° и т.д. Поэтому целесообразно при расчете
∆tA (t ) из всех допустимых значений выбирать наименьшее, т.е.
∆tA (t ) = min (∆tA1 (t ), ∆tA2 (t ),..., ∆tAS (t )) . Допустимым считается значение, удовлетворяю-
щее условию
Amin ≤ Aik (t ) ≤ Amax ; t∈[ti0 ,tik ],
где Amin и Amax — минимальное и максимальное рабочее значение азимута некоторого радиотелескопа соответственно; ti0 — время начала наведения радиотелескопа на i-й объект; tik — время окончания наведения радиотелескопа на i-й объект.
Таким образом, зависимость времени перехода радиотелескопов от одного объекта к другому определяется движением небесной сферы и собственным движением космических объектов, вследствие чего с течением времени угловое расстояние между объектами в системе координат, связанной с подвесом каждого из радиотелескопов, изменяется. Кроме того,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
10 А. Е. Рогов
проведенные исследования показали, что для большинства пар космических объектов время перехода dij (t) от объекта к объекту существенно зависит от времени t и имеет большой разброс значений. Пример зависимости продолжительности перехода t от времени суток представлен на рис. 2.
t, с
84
74 64
54
44
34 0:00
4:00
8:00 12:00 16:00 20:00 ч:мин
Рис. 2
Генетический алгоритм для решения задачи. Генетические алгоритмы [4] являются
одним из высокоэффективных методов поиска оптимальных решений для различных задач
науки и техники.
Начало
От других методов оптимизации генетические алгоритмы отличаются тем, что:
Формирование исходной популяции
— оперируют в основном не параметрами задачи, а закодированным множеством параметров, переход к реальным параметрам осуществляется только при подсчете целевой функции;
— осуществляют поиск не путем оптимизации одного реше-
ния, а путем использования нескольких альтернативных вариантов
на заданном множестве решений;
Репродукция
— для оценки качества решений используют целевую функ-
цию, а не ее различные приращения;
Мутация
— применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.
Для описания генетических алгоритмов, как правило, исполь-
Рекомбинация
зуются генетические операторы, которые по аналогии с алгоритми-
ческими операторами являются конструкциями, представляющими
Расчет окончен?
Нет
один шаг из последовательности работы генетического алгоритма. Основными генетическими операторами являются операторы репродукции, мутации и рекомбинации. Обобщенный генетический
Да алгоритм, в терминах генетических операторов, представлен на
Конец
рис. 3.
Рис. 3
Алгоритм решения задачи планирования эксперимента РСДБ сводится к следующему. Оператор репродукции представляет со-
бой комбинацию операторов селекции и кроссинговера (скрещивания). Первый выбирает
подходящие пары родителей для воспроизводства новых решений, а второй из выбранной
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
Генетический алгоритм планирования работы группы радиотелескопов
11
пары решений-родителей воспроизводит решение-потомка. Выбрана следующая реализация оператора селекции: первое решение-родитель выбирается из списка, а второе — случайным образом, т.е. каждое решение в популяции используется для воспроизводства как минимум один раз. Выбор одного и того же родителя для репродукции исключен.
Правило реализации оператора кроссинговера определяется правилом кодирования хромосом. Для решения задачи оптимального планирования работы радиотелескопа выбран простейший способ кодирования — хромосома, т.е. список номеров объектов в порядке их отслеживания радиотелескопами. Однако из-за наличия ограничений на возможные комбинации генов (ни один объект в решении не должен повторяться дважды) использование простейших генетических операторов приводит к появлению большого количества нереальных решений. Поэтому выбран модифицированный упорядоченный оператор кроссинговера (рис. 4), с помощью которого относительно просто можно получить только допустимые решения.
Рис. 4
При использовании упорядоченного оператора кроссинговера у первого родителя случайным образом выбираются две разрезающие точки, отстоящие друг от друга на половину длины хромосомы, после чего средний сегмент первого родителя, расположенный между разрезающими точками, передается потомку со случайным сдвигом влево или вправо. Остальные позиции берутся у второго родителя в упорядоченном виде слева направо, исключая элементы первого родителя. Сдвиг выбранной части хромосомы первого родителя обеспечивает эффективное изменение времени соответствующих переходов между объектами, что в силу нестационарности может значительно изменить их длину в ту или иную сторону. При классической постановке задачи выполнение сдвига не приводит к повышению эффективности работы алгоритма.
Оператор мутации реализован следующим образом: в решении случайным образом выбирается последовательность вершин и перемещается на случайное число позиций влево или вправо. Полученное таким образом новое решение добавляется к популяции. Всего мутации подвергаются 10 % случайно выбранных решений в популяции.
Оператор рекомбинации в данном алгоритме является модифицированным оператором редукции. Его действие заключается в устранении повторяющихся решений из популяции, а затем — в сокращении популяции до исходных пределов. При этом все лучшие решения сохраняются.
Критерием окончания расчета служит достижение нужного количества поколений. Обычно размер популяции и количество поколений до окончания счета зависят от размерности задачи. В данном случае размер популяции был выбран равным 8N, где N — количество заявок, а количество поколений — 10N.
Значение целевой функции рассчитывается по формуле:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12
12 А. Е. Рогов
∑ ∑⎛
⎜
k
ci
⎞ ⎟
⎛ ⎜
k
d(i−1)i
(
ti−1
)
⎞ ⎟
f
=
m
⎜ ⎜
i=1
k
⎝⎜⎜
⎟ ⎟
+
n
⎜⎜1−
⎟⎠⎟ ⎝⎜⎜
i=1
tk
+ dk0 (tk
)
⎟ ⎟
,
m
=
n
=
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 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2010. Т. 53, № 12