Ростелеком ТВ 

Как сделать sdr всеволновый приемник. Делаем первые шаги с RTL-SDR. Радиопереговоры самолетов и диспетчеров

Выдавал благородную пустоту. Однако недостаточный уровень *вырезано цензурой* отодвинул дату публикации, и вот только сейчас после позорного нудливого попрошайничества с моей стороны эта статья получила возможность показать себя миру. За этот промежуток времени успели выйти в свет как минимум три (столько мне на глаза попалось) статьи на подобную тему, и, вполне вероятно, что-то из написанного ниже вы прочитаете не впервые. Таким людям я предлагаю не хмурить носики от очередной попытки неопытного юнца научно-популярно объяснить ГА, а проходить к следующему экспонату ко второй части, где описывается создание на основе ГА бота для программистской игры Robocode. Это, по последним сведениям разведки, еще не встречалось на хабре.

Часть первая. Жизнь и творчество генетического алгоритма.

Начнем издалека. Есть некоторый набор задач, которые требуют решения. Наша цель - найти действия, которые смогут преобразовать Дано (начальные условия задач) в Ответ (целевое состояние).

Если ситуация простая, и решение такой задачи можно явно посчитать из условий при помощи этих ваших матанов, то и славно, тут и без наших премудростей все хорошо, нас наебали, все расходимся. Например, при решении квадратного уравнения ответ (значения x1, x2) получаются из начального условия (коэффициентов a, b, c) путем применения формулы, которую мы все учили в школе. А что делать в более печальном случае, когда нужной формулы в учебнике нету? Можно попробовать с помощью мозгового штурма решить одну из задач. Аналитически. Численными методами. Силой отчаянного перебора функций. Через некоторое время послышатся мечтательное студенческое «хоть бы оно само решилось». Ага, тут-то мы и вылезаем из-за занавесок. Итак, цель - написать программу, которая бы находила функцию (программу), получающую на вход исходные данные и возвращающую годные циферки. Сила метапрограммирования, в бой!

Хм, как же мы будем добиваться такой цели? Принесем у костра жертву богам рекурсии: напишем программу, которая напишет программу, которая бы находила функцию (программу)... Нет, во второй раз такое не прокатит. Лучше мы возьмем пример у природы, кинув наш взор на такие явления, как механизм эволюции, естественный отбор. Всё как в жизни: наши программы будут жить, спариваться, давать потомство и погибать под гнетом более приспособившихся особей, передавая свои лучшие качества потомкам. Звучит безумно, но стоит приглядеться.

Бог нашего мира программ - это наша задача. Программы должны верить в нее, спариваться ради нее, ставить в нее честь свечки в церкви и жить с единственной целью - найти смысл жизни решение этой задачи. Наиболее приспособившийся к среде (приблизившийся к решению задачи) становится альфа-самцом, выживает и дает крепкое потомство. Лузер, который просидел всю жизнь за онлайн играми не познал успеха в решении задачи, имеет совсем маленькие шансы дать потомство. Генофонд будет очищаться от вклада этих прыщавых товарищей, а всё общество программ будет идти к светлому будущему решенной задачи. Что же, в общих чертах уже понятно, теперь нужно разобраться с нюансами: во-первых, как вы себе представление спаривание программ? во-вторых, откуда мы возьмем первое поколение программ? в-третьих, по какому признаку мы будем определять приспособленность особей и как она будет влиять на скрещивание? в-четвертых, стоит определиться с условиями окончания работы алгоритма, когда всю эту оргию останавливать.

Искусство спаривания программ

Думаю, многие из нас иногда испытывают жгучее желание применить к программам насильственное действие сексуального характера. Тут мы вынуждены заранее предупредить, что у нас такие межвидовые девиации не поощряются. У нас всё как завещала католическая церковь: программа с программой, только после брака… и партнеров не меняют, даже если тот томный парень купил тебе коктейль в баре. Хотя нет, вру, многоженство гаремного типа процветает. Да, и еще, несмотря на применение ниже таких слов как «отец» или «сын», программы у нас гермафродиты. Ну и инцест тоже… Тьфу, и я еще о церкви говорил *facepalm*. Ладно, об этом позже.

Вопрос скрещивания программ не так уж прост. Случайный обмен функциями, строками или переменными приведет к жирному потоку страшных слов в ваш адрес от компилятора/интерпретатора, а никак не новую программу. То есть необходимо найти способ скрестить программы корректно . Умные дяди нашли выход. А умные мальчики и девочки, изучавшие строения компиляторов, тоже уже догадались. Да-да, это синтаксическое дерево .

Сразу же умерю пыл: у нас борода еще не очень густая, поэтому будем использовать самые простые типы программ. Желающие могут отправиться в долину несметного богатства программирования, а нас тут всё просто - программа состоит из выражений, в свою очередь состоящих из простых функций с некоторой арностью, переменных и констант. Каждое выражение считает по одному из возвращаемых программой значений.

Например: некоторая особь-программа square из двух выражений, пытающаяся (не особо удачно) решить квадратное уравнение:
function square(a, b, c){ x1 = min(sin(b)*(a+1), 0); x2 = 3 + exp(log(b*a)); return {x1, x2}; }
С представлением определились, теперь надо разобраться с хранением. Так как вокруг этих самых программ еще предстоит множество плясок, в том числе передача их из одной часть системы в другую (которые, вообще говоря, в моем случае вообще были написаны на разных языках), то хранение нашей особи в виде дерева не очень-то удобное. Для представления более удобным способом (идеально - набор строк над некоторым конечным алфавитом) нашу особь-программу-набор_деревьев придется научиться кодировать/раскодировать.

Вроде как дерево, а вроде и нет
Итак, надо представить дерево в виде строки. Тут нас выручит сила karva-деревьев. Для начала стоит определиться с набором функций, переменных и констант, которые могут попасться в дереве. Переменные и константы соответствуют листьям дерева и будут называться терминалами, функции - остальным (внутренним) узлам дерева, именуются нетерминалами. Так же стоит обратить внимание на то, что функции могут иметь разное количество аргументов, посему такие знания («арность», - тихо пробежало слово по губам знатоков) нам очень даже понадобятся. В итоге получается таблица кодировки, например, такая:

Здесь n, +, *, if - функции; 2 - константа; a и b - переменные. В реальных задачах таблица поувесистей, с таким набором и квадратное уравнение не решить. Также надо иметь ввиду тот факт, что во избежании деления на нуль и других сценариев апокалипсиса все функции должны быть определены на всём множестве вещественных чисел (ну, или какое вы там множество используете в задаче). А то придется сидеть на карауле, отлавливать логарифмы от нуля и потом разбираться, что с этим делать. Мы люди не гордые, мы пойдем легким путем, исключая подобные варианты.

Так вот, с помощью такой таблицы гонять функции из дерева в строку и обратно не проблема. Например, пришла нам такая строка на расшифровку:

По таблице идентифицируем каждый элемент, вспоминаем также и про арность:

Теперь при помощи арности расставляем ссылки на аргументы функций:

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

Теперь если его потянуть вверх за первый элемент, то у нас в руке будет болтаться дерево выражения:

Значение функции можно вычислить рекурсивным обходом по дереву, она у нас оказывается такой:

У меня глаза от папы такие
Возвращаемся к самому горячему - к скрещиванию. Операции скрещивания программ мы ставим следующие условия: во-первых, две скрещивающиеся особи дают два потомка (т.е. размер популяции постоянный); во-вторых, в результате скрещивания потомки должны в определенной мере обладать характеристиками обеих родителей (т.е. яблоко не должно укатываться уж очень далеко от яблони). Мы теперь узнали, как программа будет представляться - это набор строк или деревьев. Соответственно, и скрещивать их можно как строки или как деревья.

Скрещивание деревьев представляет собой обмен случайно выбранными ветками. Скрещивание строк можно реализовать несколькими способами: одноточечная рекомбинация (кусочное склеивание), двуточечная рекомбинация, поэлементный обмен и др. Их можно описать длинными сложноподчиненными предложениями с деепричастными оборотами, но и одного взгляда на схемку достаточно, чтобы смекнуть, что к чему:

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

Эй, эта девушка со мной!

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

Особи делятся на поколения. Новое поколение состоит из детей особей предыдущего поколения. Получается, есть текущее поколение сыновей и дочерей, поколение отцов и матерей, бабушек и дедушек, прабабушек и так далее до нулевого поколения - прародителей всего гордого народа. Каждая особь нового поколения после рождения пытается решить задачу, ее действия оценивает некоторая божественная функция пригодности, и в зависимости от ее оценок деятельности юнца особь получает некоторые шансы на воспроизведение потомства, то есть попадания в класс лучших представителей поколения, выбранных для продолжения рода. Наш мир суров и жесток, и по всем канонам антиутопий (или согласно идеям фюрера, как хотите) ни к чему не пригодные родители-пенсионеры после выполнения своей миссии рождения потомства отправляются в путешествие на газенвагене, освобождая жилплощадь паре своих чад. Дети идут по стопам родителей, и так из поколения в поколение.

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

Функция приспособленности выдает каждой особи поколения некоторое число, показывающее ее полезность, приспособленность. Это значение будет влиять на процедуру отбора (селекции): чем больше у особи это значение, тем больше у нее вероятность найти пару для скрещивания (и даже не одну). На практике, после вычисления приспособленности для всех особей поколения мы нормируем эти значения (чтобы сумма приспособленностей особей равнялась 1) и для каждого из мест для поцелуев бросается жребий (случайное число от 0 до 1), определяющий счастливчика. Альфа-самец может получить себе несколько мест, неудачник ничего не получит и так и останется в одиночестве с потертым календариком 1994 года с Памеллой. Такой способ селекции называется «отбором методом рулетки», и схематично это выглядит как-то так:

Существуют и другие способы селекции, но все они придерживаются общего правила: чем больше у особи приспособленность, тем больше она должна участвовать в скрещивании. Также в процесс можно включить опцию элитизма, когда лучший представитель поколения получает за заслуги перед Отечеством премию в виде дополнительных лет жизни: он переходит в следующее поколение без изменений, хотя и может параллельно наделать детей. Это позволяет нам не потерять очень удачное решение, которое может разрушиться в процессе скрещивания.

Тут же упомянем и мутацию. Это операция случайным образом с некоторой маленькой вероятностью меняет фрагмент особи, что позволяет разнообразить генофонд. Полезная вещь, вдруг такая мутация лактозу расщепить поможет! А если нет, и еще одна рука лишняя - то уж помучайся с ней до конца дней своих, потомство дать все равно шансов маловато.

Сотворения мира и Апокалипсис

Как переходить от поколения к поколению выяснили, теперь вопрос следующий - «а что стало первопричиной, с чего все началось?». В отличие от этого вашего мира, у нас для объяснения таких вещей не надо придумывать уловки типа «большого взрыва» или «7 дней». Тут ответ предельно ясен - всё началось с нулевого поколения, которое было сотворено случайным образом. Да-да, просто генерируем рандомом строки/деревья. Единственное требование - корректность особи, а насколько она ущербна - никого не волнует, отбор сделает свое дело.

Существует же наш мир настолько долго, насколько нам надо. Мы или задаем планку удовлетворяющей нас приспособленности, и при появлении достаточно крутой особи останавливаем процесс, или проверяем, насколько особи поколения сильно различаются друг от друга. Логично, что если всё поколение состоит из однояйцевых близняшек, то дальнейшее спаривание возбуждает не даст ничего нового генофонду, а на одну мутацию надеяться наивно. Также можно установить ограничение по времени.

Эй, ты! Харошш парить мозг! Что в итоге-то?

Сделаем паузу в этом увлекательном словоблудии и оглянемся назад (ну т.е. наверх). Если подводить итоги, то генетический алгоритм выглядит так:

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

Часть вторая. Роль генетического алгоритма в образе бота Robocode.

Что-то первая часть затянулась, мы все утомились, поэтому не будем повторяться. Также опустим некоторые особенности реализации.
Узнать что такое Robocode можно тут: habrahabr.ru/blogs/programmers_games/59784 (картинки утеряны правда). Если коротко - эта программистская игра, изначально созданная для изучения особенностей языка Java, которая позволяет участникам создавать своих ботов-роботов и устраивать между ними бои. Каждый участник пишет код на Java, который управляет небольшим танком, и сражается с другими такими же танками.

Перед нами стоит следующая задача: разработка при помощи генетического алгоритма автоматизированную системы управления ботом-танком. Робот должен создаваться и модифицироваться автоматически, т.е. в ходе своей эволюции «подстраиваться» под конкретного и заранее выбранного соперника в боях 1 на 1.

Как представить решение задачи в виде особи

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

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

Так как функция управления должна возвращать 4 значения (энергия выстрела, угол поворота башни, угол поворота корпуса, перемещение танка), то, как объяснялось в прошлой части, она будет состоять из четырех выражений, т.е. из четырех строк/деревьев.

Для составления таблицы кодирования необходимо определиться с набором базовых функций, переменных и констант.

Функции:
+(x, y) = x + y
++(x, y, z) = x + y + z
n(x) = -x
*(x, y) = x * y
**(x, y) = x * y * z
min(x, y) = x > y? y: x
s(x) = 1/(1+exp(-x))
if(x, y, z, w) = x > y? z: w

Переменные:
x, y - координаты танка соперника относительно нашего танка;
dr - расстояние, которое осталось «доехать» нашему танку;
tr - угол, на который осталось повернуться нашему танку;
w - расстояние от нашего танка до края поля;
dh - угол между направлением на танк соперника и пушкой нашего танка;
GH - угол поворота пушки нашего танка;
h - направление движения танка соперника;
d - расстояние между нашим танком и танком соперника;
e - энергия танка соперника;
E - энергия нашего танка.

Ну и константы: 0.5, 0, 1, 2, 10

Функция приспособленности

Опишем, как была выбрана функция приспособленности. Результаты боя «Robocode» формирует на основе множества нюансов. Это не только количество побед, но и всевозможные очки за активность, за выживаемость, за попадание в соперника и т.д. В итоге «Robocode» ранжирует роботов по параметру «total scores», который учитывает все вышеописанные тонкости. Его мы и будем использовать при подсчете приспособленности особи: итоговая приспособленность будет равняться доле в процентах очков нашего танка от суммы очков обеих танков, и принимает значение от 0 до 100. Соответственно, если значение приспособленности больше 50, то наш робот набрал больше очков, чем соперник, следовательно, сильнее его. Заметим, что согласно такой системе подсчета, первое место далеко не всегда занимает тот, кто победил в большинстве раундов боя. Ну тут мы разводим руками с фразой про мотороллер: создатели определили критерии, мы им следуем.

Вообще говоря, вычисление приспособленности особи включает в себя проведение серии боев! Т.е. такой, казалось бы, незначительный пункт, как просчет приспособленности, состоит из таких плясок с бубном:
1) Наша система сохраняет закодированные хромосомы особи в файл chromosome.dat;
2) Для каждой особи запускается среда «Robocode», которая организовывает поединок. На вход ей мы подаем файл формата.battle, описывающий условия боя - список сражающихся танков, размеры поля, количество раундов и прочее;
3) Для битвы Robocode загружает танки, наш робот-оболочка считывает файл chromosome.dat с закодированным поведением, интерпретирует его в набор действий и ведет согласно им бой;
4) Среда Robocode по окончании поединка записывает результат битвы в файл results.txt и на этом завершает свою работу;
5) Наша система подбирает этот файл, парсит и выделяет из него значения total score нашего танка и соперника. Путем нехитрой арифметики получаем значение приспособленности.

Как наши их, да?

Подведем итоги нашего конструкторского бюро. Наша система состоит из двух частей (программ). Первая из них на основе генетического алгоритма собирает особь и сохраняет ее в виде набора строк, а вторая (код робота) интерпретирует ее (перерабатывая в дерево выражения) и осуществляет управление танком (вычисляя рекурсивным обходом значение деревьев выражений при заданных переменных, то есть текущем состоянии боя). Первая программа написана на языке СИ, вторая - на языке Java.

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

В качестве результата продемонстрируем итоги создания соперника роботам Walls и Crazy:




В первом случае мы остановили процесс после достижения одной из особей приспособленности рубежа 70, во втором нам было достаточно, что средняя приспособленности особей поколения превышает 50.

После созерцания промыть глаза спиртом

Если кто не боится плакать кровавыми слезами в конвульсиях от созерцания быдлокодинга (особенно волосы начнут шевелиться от кода робота - у нас с java взаимная ненависть), то прикрепляю

Эволюционный процесс представляется как способность «лучших» хромосом оказывать большее влияние на состав новой популяции на основе длительного выживания из более многочисленного потомства. Основные этапы эволюционного поиска следующие:

1. Конструируется начальная популяция. Вводится точка отсчета поколений t = 0. Вычисляется приспособленность каждой хромосомы в популяции, а затем средняя приспособленность всей популяции.

2. Устанавливается t= t+1. Производится выбор двух родителей (хромосом) для реализации оператора кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей.

3. Формируется генотип потомков. Для этого с заданной вероятностью производится оператор кроссинговера над генотипами выбранных хромосом. Далее с вероятностью 0,5 выбирается один из потомков P i (t) и сохраняется как член новой популяции. После этого к P i (t) последовательно применяется оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохраняется как P k (t).

4. Определяется количество хромосом для исключения их из популяции, чтобы ее размер оставался постоянным. Текущая популяция обновляется заменой отобранных хромосом на потомков P k (t).

5. Производится определение приспособленности (целевой функции) и пересчет средней приспособленности всей полученной популяции.

6. Если t = t заданному, то переход к 7, если нет, то переход к 2.

7. Конец работы.

Данный алгоритм известен как упрощенный «репродуктивный план Д. Холланда». Заметим, что в практических задачах вместо понятия «приспособленность» используют понятие «целевая функция».

Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда. Его механизм несложен. Предварительно ПГА случайно генерирует популяцию последовательностей – хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем производится копирование последовательности хромосом и перестановка их частей. Далее ПГА реализует множество простых операций к начальной популяции и генерирует новые решения.

ПГА состоит из трех операторов:

    репродукция;

    кроссинговер;

Репродукция – процесс, в котором хромосомы копируются пропорционально значению их ЦФ. Копирование хромосом с «лучшим» значением ЦФ имеет большую вероятность для попадания в следующую генерацию. Рассматривая эволюцию Ч. Дарвина, можно отметить, что оператор репродукции (ОР) является искусственной версией натуральной селекции - «выживание сильнейших». Он представляется в алгоритмической форме различными способами. Самый простой – создать модель «колеса рулетки», в которой каждая хромосома имеет поле, пропорциональное значению ЦФ.

Рассмотрим пример Д. Гольдберга: необходимо найти значение максимума функции f(x)=x 2 на целочисленном интервале . Традиционными методами можно изменять значения переменной x, пока не получим максимальное значение f(x).

Для объяснения и реализации ПГА построим следующую таблицу:

Номер хромосом

Хромосома (двоичный код)

Десятичный код

Значение ЦФ

Значение ЦФ, в процентах

В столбце 2 табл. расположены 4 хромосомы (представленные в двоичном коде), сгенерированные случайным образом. Значение ЦФ для каждой хромосомы (столбец 4) определяется как квадрат значения десятичного кода двоичного числа, которое приведено для хромосом во втором столбце таблицы. Тогда суммарное значение ЦФ всех хромосом равно 890. Для селекции хромосом используется оператор репродукции на основе колеса рулетки. На рисунке поля колеса рулетки соответствуют значению ЦФ каждой хромосомы в процентах. В одной генерации колесо рулетки вращается, и после останова ее указатель определяет хромосому, выбранную для реализации следующего оператора. Очевидно, не всегда хромосома с большим значением ЦФ в результате ОР будет выбрана для дальнейших преобразований.

Колесо рулетки для примера

На основе реализации ОР выбираются хромосомы для применения ОК. Оператор кроссинговера, как правило, выполниться в 3 шага, одним из ОК описанным выше. Точка разрыва kвыбирается случайно между 1 и числом равным длине хромосомы минус единица, то есть в интервале (1, L-1). Длина хромосомы L – это число значащих цифр в ее коде. В рассматриваемом примере таблицы длина каждой хромосомы равна пяти (L=5). На основе ОК создаются две новые хромосомы, путем обмена их частей между позициями (k+1) и L соответственно.

Например, рассмотрим хромосомы 1 и 2 из начальной популяции. Пусть k=1. Тогда получим:

P 1 0 | 1 1 0 0 До применения оператора кроссинговера

P 2 1 | 0 0 0 0,

-----------------

P 1 0 0 0 0 0 После применения оператора кроссинговера

P 2 1 1 1 0 0.

Работа ПГА начинается с репродукции. Хромосомы для следующей генерации выбираются путем вращения колеса рулетки. В примере колесо рулетки вращается 4 раза. Это число соответствуют мощности начальной популяции.

Величину отношения
называют вероятностью выбора копий (хромосом) при реализации оператора репродукции и обозначают:

где f i (x)значение ЦФ i-й хромосомы в популяции, sum f(x)суммарное значение ЦФ всех хромосом в популяции. Величину
также называют нормализованной вероятностью выбора. Ожидаемое число копий

i-й хромосомы после реализации ОР определяются по формуле:

где
число анализируемых хромосом, причемN G включается вN.

Ожидаемое число копий хромосомы P i , переходящее в следующее поколение, также иногда определяют на основе выражения:

.

где
среднее значение ЦФ по всей популяции.

Тогда для рассматриваемого примера, ожидаемое число копий для первой хромосомы из таблицы равно 0,164=0,64 копий, для второй0,294=1,16 копий, для третьей0,054 = 0,2 и наконец для четвертой0,54=2. Используя модель «бросание монеты» можно определить число полученных копий. Например, (см. столбец 7 таблицы) хромосомы P 1 и P 2 получают 1 копию, хромосома P 4 – 2 копии, и хромосома 3 не получает копий. Сравнивая этот результат с ожидаемым числом копий, получаем то, что «лучшие» хромосомы дают большее число копий, «средние» остаются и «плохие» удаляются после реализации оператора репродукции.

Начальная популяция

Значение f i (x)/sum

Ожидаемое число копий

Число полученных копий

Суммарное значение ЦФ (sumf(x))

Среднее значение ЦФ

Max значение ЦФ

Для рассматриваемого примера построим таблицу. В столбце 2 приведен вид 4 хромосом после выполнения оператора репродукции. В столбце 3 приведены списки пар хромосом, которые выбраны случайным образом для реализации оператора кроссинговера. В столбце 4 указан номер позиции для точки разреза хромосом. В столбце 5 приведен вид 4 хромосом после выполнения оператора кроссинговера. В столбце 6 приведены значения десятичного кода двоичного числа каждой хромосомы столбца 5. В столбце 7 приведено значение f(x) для каждой из 4 хромосом новой популяции. В строке 5 приведено суммарное значение ЦФ хромосом новой популяции, в строке 6 –среднее значение их ЦФ, а в строке 7- максимальное значение ЦФ хромосомы из новой популяции.

Популяция после оператора репродукции

выбранные

случайно

Новая популяция

Применяя к популяции полученной после реализации оператора репродукции (столбец 2 табл.) оператор кроссинговера, получим новую популяцию хромосом (5 столбец таблицы). В принципе оператор кроссинговера можно применять любое число раз. После проведения одной генерации ПГА улучшились все показатели: среднее и максимальное значение ЦФ.

Далее, согласно схеме выполнения ПГА, реализуется оператор мутации. Существует большое количество видов операторов мутации. Заметим, что эти операторы соответствуют перестановкам элементов внутри заданного множества. Очевидно, что при небольшой длине хромосомы L (порядка 1020) можно выполнить полный перебор за приемлемое время и найти наилучшие решения. При увеличении L до 50200 и выше, полный перебор произвести затруднительно, и необходимы другие механизмы поиска. Здесь как раз и приходит на помощь направленно-случайный поиск, который реализуется на основе ПГА.

Отметим, что глобальный максимум можно было найти еще на этапе реализации кроссинговера. Для этого необходимо было увеличить пространство поиска. Например, если в столбце 5 табл. выбрать хромосомы P 2 и P 4 и между ними выполнить оператор кроссинговера (точка ОК выбрана случайно и равна 3), то получим:

P 2: 1 0 1 | 1 1 (ЦФ-23)

P 4: 1 1 1 | 0 0 (ЦФ-28)

P 2 : 1 0 1 0 0 (ЦФ-20)

P 4 : 1 1 1 1 1 (ЦФ-31).

Решение P 4 , полученное в результате применения ОК случайным образом, является наилучшим результатом (глобальным оптимумом).

Как отмечалось выше, в генетических алгоритмах можно выделять два основных механизма воспроизводства хромосом:

    потомки являются точными копиями родителей (неполовое воспроизводство без мутации);

    потомки имеют «большие» отличия от родителей.

В генетических алгоритмах в основном используют комбинации этих механизмов. Отметим, что в инженерных задачах начальная популяция может выбираться любым образом, например, моделированием «бросания монеты» (орел = 1, решка = 0). Тогда оператор репродукции выполняется через моделирование движения колеса рулетки. Оператор кроссинговера в задачах вычислительного характера обычно выполняется через двоичное декодирование двух положений монеты. Часто применяют другие типы ОК и другие технологии его выполнения. Вероятность ОК допускается равной Рr(ОК) = 1.0 и меньше, вероятность ОМ допускается равной Рr(ОМ) = 0.01 и больше. В общем случае вероятность применения оператора мутации зависит от знаний о решаемой задаче.

Приведем другой стандартный тип генетического алгоритма, описанный Л.Девисом:

    Инициализация популяции хромосом.

    Оценка значения каждой хромосомы в популяции.

    Создание новых хромосом посредством скрещивания текущих хромосом; применение операторов мутации и рекомбинации.

    Устранение хромосом из популяции, чтобы освободить место для новых хромосом.

    Оценка значений новых хромосом и вставка их в популяцию.

    Если время, заданное на реализацию алгоритма, закончено, то останов и возврат к наилучшей хромосоме, если нет, то переход к 3.

    Конец работы алгоритма.

Сравнивая описание ПГА Д. Гольдберга, Д. Холланда и Л. Девиса, видно, что в них реализована одна основная идея моделирования эволюции с некоторыми модификациями. Однако заметим, что эти изменения могут существенно влиять на окончательное качество решения.

Приведем пример модифицированного ПГА:

1. Создание начальной популяции решений.

2. Моделирование популяции (определение ЦФ для каждой хромосомы).

3. Пока не проведено необходимое число генераций или не закончилось время, заданное на реализацию алгоритма или не найдено оптимальное значение ЦФ (если оно известно):

а) выбор элементов для репродукции;

Применение:

б) оператора кроссинговера для создания потомков;

в) оператора мутации;

г) оператора инверсии;

д) оператора транспозиции;

е) оператора транслокации;

ж) оператора сегрегации;

з) оператора удаления вершин;

и) оператора вставки вершин;

к) рекомбинация родителей и потомков для создания новой генерации;

л) оператора редукции.

4. Реализация новой генерации.

Новые модификации ГА могут строиться путем объединения, например, пунктов «б – л» или их частичного устранения, или их перестановок, а также на основе применения адаптационных принципов управления эволюционным поиском.

Введение в аксиоматическую теорию генетических алгоритмов

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

Пусть каждому исходному понятию и отношению аксиоматической теории ГА поставлен в соответствие некоторый конкретный математический объект. Совокупность таких объектов называется полем интерпретации . Всякому утверждению U теории ГА ставится в соответствие некоторое высказывание U* об элементах поля интерпретации, которое может быть истинным или ложным. Тогда можно сказать, что утверждение U теории ГА соответственно истинно или ложно в данной интерпретации. Поле интерпретации и его свойства сами обычно являются объектом рассмотрения другой теории ПГА, которая в частности может быть аксиоматической. Этот метод позволяет доказывать суждения типа: если теория ГА непротиворечива, то непротиворечива и теория ПГА.

Пусть теория ГА проинтерпретирована в теории ПГА таким образом, что все аксиомы A i теории ГА интерпретируются истинными суждениями A i * теории ПГА. Тогда всякая теорема теории ГА, то есть всякое утверждение А, логически выведенное из аксиом A i в ГА, интерпретируется в ПГА некоторым утверждением A * , выводимым в ПГА из интерпретаций A i * аксиом A i и, следовательно, истинным.

Метод интерпретаций позволяет также решать вопрос о независимости систем аксиом: для доказательства того, что аксиома А теории ГА не зависит от остальных аксиом этой теории, то есть не выводима из них, и, следовательно, необходима для получения всего объема данной теории, достаточно построить такую интерпретацию ГА, в которой аксиома А была бы ложна, а все остальные аксиомы этой теории истинны. Уточнением понятия аксиоматической теории является понятие формальной системы . Это позволяет представлять математические теории как точные математические объекты и строить общую теорию или метатеорию таких теорий. Всякая формальная система строится как точно очерченный класс выражений – формул, в котором некоторым точным образом выделяется подкласс формул, называемых теоремами данной формальной системе. При этом формулы формальной системы непосредственно не несут в себе содержательного смысла. Их можно строить из произвольных знаков и символов. Общая схема построения произвольной формальной системы ГА такова:

    Язык системы ГА: аппарат алгебры логики; теория множеств; теория графов, теория алгоритмов, основные положения биологии и теории систем.

    1. Алфавит – перечень элементарных символов системы: двоичный, десятичный, буквенный, Фибоначчи и др.

      Правила образования (синтаксис), по которым из элементарных символов строятся формулы теории ГА:

    построение моделей эволюций;

    конструирования популяций;

    построения ЦФ;

    разработки генетических операторов;

    репродукции популяций;

    рекомбинации популяций;

    редукции;

    адаптации.

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

    Аксиомы системы ГА. Выделяется некоторое множество конечных формул, которые называются аксиомами системы. В ГА существует большое число наборов аксиом. Например, базовый набор аксиом следующий:

    Популяция конструируется случайным образом.

    Выполнение оператора репродукции производится на основе «колеса рулетки».

    Обязательное использование операторов кроссинговера и мутации.

    Размер популяции после каждой генерации остается постоянным.

    Размер популяции меняется.

    Число копий (решений), переходящих в следующую генерацию меняется.

    Целевая функция определяется на основе принципа «Выживание сильнейших».

    Правила вывода ГА. Фиксируется конечная совокупность предикатов П 1 , П 2 ,…, П k на множестве всех формул системы. Пусть П (x 1 ,…,x ni +1) – какой-либо из этих предикатов (n i 0) если, для данных формулF 1 ,…,F ni +1 утверждение П (F 1 ,…,F ni +1) истинно, то говорят, что формулаF ni +1 непосредственно следует из формулF 1 ,…,F ni +1 по правилу П i .

Заданием 1,2,3 исчерпывается задание формальной системы ГА как точного математического объекта. При этом степень точности определяется уровнем точности задания алфавита, правил образования и правил вывода. Выводом системы ГА называется всякая конечная последовательность формул, в которой каждая формула либо является аксиомой системы ГА, либо непосредственно следует из каких-либо предшествующих ей (этой последовательности) формул по одному из правил вывода П i системы.

Всякую конкретную математическую теорию ГА можно перевести на язык подходящей формальной системы таким образом, что каждое ложное или истинное предложение теории ГА выражается некоторой формулой системы. Метод интерпретаций позволяет устанавливать факт относительной непротиворечивости, то есть доказывать суждения типа: «если теория ГА непротиворечива, то непротиворечива и теория ПГА». В общем случае, проблема непротиворечивости не решена и является одной из основных в математике.

Предлагается ряд основных стратегий взаимодействия методов эволюционного и локального поиска:

    «поиск – эволюция»;

    «эволюция – поиск»;

    «поиск – эволюция - поиск»;

    «эволюция – поиск - эволюция».

Заметим, что иерархически можно строить стратегии такого типа любого уровня сложности. Например, «эволюция – поиск – эволюция - поиск – эволюция - поиск» и т.д. Отметим, что такое построение зависит от наличия вычислительных ресурсов и времени, заданного на получения окончательного решения.

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

Во втором случае конструируется популяция и реализуется одна из схем эволюции. Лучшее решение анализируется и улучшается (если это возможно) одним из алгоритмов поиска. Далее процесс выполняется, как в первом случае. В остальных случаях процесс поиска результатов выполняется аналогично.

Выводы

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

Существует четыре основных отличия ГА от оптимизационных методов:

    прямое преобразование кодов;

    поиск из популяции, а не из единственной точки;

    поиск через элементы (слепой поиск);

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

Использование ГА при решении инженерных задач позволяет уменьшить объем и время вычислений и упростить моделирование функций, сократить число ошибок моделирования.

Генетические алгоритмы (ГА) предназначены для решения задач оптимизации. В основе генетического алгоритма лежит метод случайного поиска. Основным недостатком случайного поиска является то, что нам неизвестно, сколько понадобится времени для решения задачи. Для того, чтобы избежать таких расходов времени при решении задачи, применяются методы, проявившиеся в биологии. При этом используются методы открытые при изучении эволюции и происхождения видов. Как известно, в процессе эволюции выживают наиболее приспособленные особи. Это приводит к тому, что приспособленность популяции возрастает, позволяя ей лучше выживать в изменяющихся условиях.

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

Впервые подобный алгоритм был предложен в 1975 году Дж. Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов.

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

В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.

Основные генетические операторы

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

  1. из популяции выбираются две особи, которые будут родителями;
  2. определяется (обычно случайным образом) точка разрыва;
  3. потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора :

Хромосома_1: 0000000000

Хромосома_2: 1111111111

Допустим, разрыв происходит после 3-го бита хромосомы, тогда

Хромосома_1: 0000000000 >> 000 1111111 Результирующая_хромосома_1

Хромосома_2: 1111111111 >> 111 0000000 Результирующая_хромосома_2

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

000 1111111 >> 1111111 000

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

Схема функционирования генетического алгоритма

Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.

  1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B 0 = {A 1 ,A 2 ,…,A k)
  2. Вычислить приспособленность (пригодность ) каждой особи F Ai = fit(A i) , i=1…k и популяции в целом F t = fit(B t) (также иногда называемую термином фиттнес ). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
  3. Выбрать особь A c из популяции. A c = Get(B t)
  4. С определенной вероятностью (вероятностью кроссовера P c) выбрать вторую особь из популяции А c1 = Get(B t) и произвести оператор кроссовера A c = Crossing(A c ,A c1).
  5. С определенной вероятностью (вероятностью мутации P m) выполнить оператор мутации. A c = mutation(A c).
  6. С определенной вероятностью (вероятностью инверсии P i) выполнить оператор инверсии A c = inversion(A c).
  7. Поместить полученную хромосому в новую популяцию insert(B t+1 ,A c).
  8. Выполнить операции, начиная с пункта 3, k раз.
  9. Увеличить номер текущей эпохи t=t+1.
  10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Рассмотрим подробнее отдельные этапы алгоритма.

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

P Get(Ai) ~ Fit(A i)/Fit(B t).

Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор . Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма , которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

Другой важный момент – определение критериев останова.

В качестве критериев останова алгоритма могут использоваться такие:

  • сформировано заданное число поколений;
  • популяция достигла заданного качества;
  • достигнут определенный уровень сходимости.

Пример

Найти максимум функции f(x)=x2 в диапазоне 0

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

Установим размер популяции, равный четырем строкам.

Таблица 11.1 – Начальная популяция и оценка пригодности

Начальная популяция

Относительная пригодность, %

Так как функция пригодности второй строки - лучшая, отбираем две копии второй строки и оставляем первую и четвертую строки в родительском пуле. Отбор партнеров производим случайным образом: партнером первой строки служит вторая, партнером четвертой - тоже вторая. Положение точек скрещивания также случайно и выбирается следующим образом: для пары из первой и второй строк точка скрещивания - после четвертого бита; для пары из второй четвертой строк - после второго бита.

Таблица 11.2– Родительский пул и скрещивание

Родительский пул

Парная строка

До скрещивания

После скрещивания

Второе поколение без мутации приведено ниже.

Таблица 11.3 – Второе поколение

Начальная популяция

Относительная пригодность, %

Видно, что третья строка является лучшей во втором поколении и значении x=27 достаточно близко к отыскиваемому максимуму. Очевидно, что через несколько шагов оптимальное решение будет найден даже без использования оператора мутации.

Применение генетических алгоритмов

Генетический алгоритм для решения любой проблемы должен содержать, как правило, следующие компоненты:

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

Генетические алгоритмы широко используются для того, чтобы быстро решать сложнейшие оптимизационные задачи в бизнесе и финансах. Но этим сфера их применения не ограничивается. Многочисленные варианты генетических алгоритмов употребляются при исследовании разнообразных научных и технических проблем: создание реактивных двигателей, повышение эффективности обслуживания самолетов авианосцами и др. Генетические алгоритмы используются также для создания вычислительных структур, применяются при проектировании нейронных сетей и при управлении роботами. Кроме этого, они приносят неоценимую помощь при моделировании процессов развития в биологических, социальных и других системах.

Примеры программного обеспечения

На рынке программного обеспечения имеется несколько продуктов, использующих генетические алгоритмы: Evoler, GeneHunter, Genetic Training Option for BrainMaker, Auto2Fit, Omega, Genitor, Xpert Rule Gen Asy, PC/Beagle, EM, Escapate, GAGA, Gausd, Genesis, OOGA, EnGENer, Game, GA Workbench, Pegasus и др.

Уверен, для многих из вас, как и для меня совсем недавно, происходящее в радиоэфире было настоящей магией. Мы включаем телевизор или радио, поднимаем трубку сотового телефона, определяем свое положение на карте по спутникам GPS или ГЛОНАСС - и все это работает автоматически. Благодаря RTL-SDR у нас появился доступный способ заглянуть внутрь всего этого волшебства.

Как уже говорилось, RTL-SDR - это целое семейство дешевых ТВ-тюнеров, способных выполнять функцию SDR-приемника. У этих игрушек разные названия и бренды, но объединяет их одно - все они построены на чипсете RTL2832. Это микросхема, содержащая два 8-битных АЦП с частотой дискретизации до 3,2 МГц (однако выше 2,8 МГц могут быть потери данных), и интерфейс USB для связи с компьютером. Эта микросхема на входе принимает I- и Q-потоки, которые должны быть получены другой микросхемой.

R820T и E4000 - это две наиболее удобные для SDR микросхемы, реализующие радиочастотную часть SDR: усилитель антенны, перестраиваемый фильтр и квадратурный демодулятор с синтезатором частоты. На рисунке - блок-схема E4000.

Разница между ними следующая: E4000 работает в диапазоне ~52–2200 МГц и имеет немного большую чувствительность на частотах менее 160 МГц. Из-за того что производитель E4000 обанкротился и микросхема снята с производства, остающиеся тюнеры покупать все труднее, и цены на них растут.

R820T работает в диапазоне 24–1766 МГц, однако диапазон перестройки внутренних фильтров сильно затрудняет работу R820T выше 1200 МГц (что делает невозможным, например, прием GPS). На данный момент тюнеры на этой микросхеме легко купить, и стоят они около 10–11 долларов.

Также продаются тюнеры на микросхемах FC0012/FC0013/FC2580 - у них очень серьезные ограничения по частотам работы, и лучше их не покупать. Узнать, на какой микросхеме сделан тюнер, можно в описании товара или спросив у продавца. Если информации по используемым чипам нет - лучше купить в другом месте.

Покупка

В розничных магазинах их не найти, поэтому нам поможет aliexpress.com . Пишем в поиске R820T или E4000, сортируем по количеству заказов, внимательно читаем описание (там должно быть явно написано, что тюнер использует микросхемы RTL2832 + E4000 или RTL2832 + R820T), и можно заказывать. Присылают обычно почтой России, в течение 3–6 недель.

В комплекте с тюнером будет и крошечная антенна - ее, конечно, лучше заменить. Хорошие результаты можно получить, используя обычную комнатную телевизионную антенну МВ-ДМВ «рога». В описании товара также нужно обратить внимание на разъем антенны - и либо искать тюнер с обычным телевизионным разъемом, либо расчехлять паяльник и делать переходник / перепаивать разъем. При пайке очень легко убить устройство статическим электричеством, так что заземляйтесь.


На многих тюнерах рядом с коннектором антенны отсутствуют защитные диоды (в данном случае U7) - их можно либо впаять самому (один к земле, один от земли - я, например, впаял 1N4148), либо оставить как есть, и антенну голыми руками не трогать и всячески беречь от статического электричества.

Софт и API для работы с RTL2832

rtl_sdr

Rtl_sdr – драйвер, обеспечивающий «нецелевое» использование данных с TV-тюнеров на базе rtl2832. В Windows вам придется заменить драйвер тюнера по умолчанию на WinUSB с помощью программы Zadig.

Rtlsdr.dll требуют все SDR-программы, и зачастую эта DLL уже идет в поставке софта, использующего RTL2832.

Rtl_sdr также можно использовать и через консольную утилиту, чтобы протестировать тюнер или слить кусок эфира в файл:

Rtl_sdr -f 1575520000 -g 34 -s 2048000 out.dat

При дальнейшей обработке нужно помнить, что в файле байты I- и Q-потоков идут поочередно.

SDRSharp


Что послушать в радиоэфире?

Радиопереговоры в безлицензионных диапазонах

Гражданские рации, не требующие регистрации в России, работают на частотах 433 и 446 МГц. Впрочем, в Москве русскую речь там услышать сложно. Их сразу и без проблем слышно в SDRSharp, модуляция NFM.

Поскольку каналов много, очень полезен плагин для SDRSharp AutoTuner Plugin - он автоматически включает частоту, на которой ведется передача, и таким образом можно слушать сразу все каналы раций.

Чтобы слушать рации на частоте 27 МГц, нужен тюнер с микросхемой R820T или внешний конвертер в случае E4000 (например, описанный ранее Ham It Up v1.2). Оптимальная антенна для 27 МГц уже требуется более серьезная, длиной ~2,59 или ~1,23 м.

Радиопереговоры полиции

Полиция в Москве и во многих других регионах России перешла на использование цифровых радиостанций, работающих в стандарте APCO-25 (P25). В P25 данные передаются в цифровом виде со сжатием и кодами коррекции ошибок - это позволяет увеличить дальность устойчивой связи и больше каналов впихнуть в ту же полосу радиочастот. Также существует опциональная возможность шифрования переговоров, однако обычная полиция работает без шифрования.

Для приема P25-раций можно использовать декодер DSD . DSD ожидает аудиоданные на входе. Перенаправить аудио с SDRSharp в DSD можно с помощью Virtual Audio Cable. DSD весьма критичен к настройкам SDRSharp - я рекомендую устанавливать AF Gain около 20–40%, возможно отключать галочку Filter Audio. Если все идет по плану - в окне DSD побегут декодированные пакеты, а в наушниках будут слышны переговоры. Эта схема также работает с упомянутым плагином AutoTuner в SDRSharp.

Найти частоты предлагаю читателям самостоятельно, так как эта информация не является открытой.

Радиопереговоры самолетов и диспетчеров

По историческим причинам для радиосвязи в авиации используется амплитудная модуляция. Обычно передачи с самолетов лучше слышно, чем от диспетчеров или погодных информаторов на земле. Диапазон частот - 117–130 МГц.

Прием сигналов с автоматических передатчиков самолетов ADS-B

ADS-B используется для того, чтобы и диспетчер, и пилот видели воздушную обстановку. Каждый самолет регулярно передает параметры полета на частоте 1090 МГц: название рейса, высота, скорость, азимут, текущие координаты (передаются не всегда).

Эти данные можем принять и мы, чтобы лично наблюдать за полетами. Два популярных декодера ADS-B для RTL2832 - ADSB# и RTL1090. Я использовал ADSB#. Перед запуском желательно настроиться на 1090 МГц в SDRSharp, посмотреть, есть ли сигнал и какая ошибка частоты из-за неточности кварцевого генератора. Эту ошибку необходимо скомпенсировать в настройках Front-end’а: Frequency correction (ppm). Нужно помнить, что величина этой ошибки может изменяться вместе с температурой приемника. Найденную коррекцию нужно указать и в окне ADSB### (предварительно закрыв SDRSharp).

Оптимальная антенна-монополь для 1090 МГц получается длиной всего 6,9 см. Так как сигнал очень слабый, тут очень желательно иметь дипольную антенну, установленную вертикально с такой же длиной элементов.

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

После запуска adsbSCOPE необходимо открыть пункт меню Other -> Network -> Network setup, нажать внизу на кнопку adsb#, убедиться, что указан адрес сервера 127.0.0.1. Затем на карте необходимо найти твое местоположение и выполнить команду Navigation -> Set Receiver Location. Затем запустить подключение к ADSB#: Other -> Network -> RAW-data client active.

Если все сделано правильно, то в течение нескольких минут ты сможешь увидеть информацию о самолетах (если, конечно, они пролетают рядом с тобой). В моем случае с антенной-монополем можно было принимать сигналы от самолетов на расстоянии примерно 25 км. Результат можно улучшить, взяв более качественную антенну (диполь и сложнее), добавив дополнительный усилитель на входе (желательно на GaAs), используя тюнер на основе R820T (на этой частоте он имеет более высокую чувствительность по сравнению с E4000).


Прием длинно- и коротковолновых аналоговых и цифровых радиостанций

До прихода интернета КВ-радиостанции были одним из способов узнавать новости с другого конца земного шара - короткие волны, отражаясь от ионосферы, могут приниматься далеко за горизонтом. Большое количество КВ-радиостанций существует и поныне, их можно искать в диапазоне ~8–15 МГц. Ночью в Москве мне удавалось услышать радиостанции из Франции, Италии, Германии, Болгарии, Великобритании и Китая.

Дальнейшее развитие - цифровые DRM-радиостанции: на коротких волнах передается сжатый звук с коррекцией ошибок + дополнительная информация. Слушать их можно с помощью декодера . Диапазон частот для поиска - от 0 до 15 МГц. Нужно помнить, что для таких низких частот может понадобиться большая антенна.

Помимо этого, можно услышать передачи радиолюбителей - на частотах 1810–2000 кГц, 3500–3800 кГц, 7000–7200 кГц, 144–146 МГц, 430–440 МГц и других.

Радиостанция «судного дня» - UVB-76

UVB-76 расположена в западной части России, передает на частоте 4,625 МГц с начала 80-х годов и имеет не до конца ясное военное назначение. В эфире время от времени передаются кодовые сообщения голосом. Мне удалось принять ее на RTL2832 с конвертором и 25-метровую антенну, спущенную с балкона.

GPS

Одна из самых необычных возможностей - прием навигационных сигналов со спутников GPS на TV-тюнер. Для этого понадобится активная GPS-антенна (с усилителем). Подключать антенну к тюнеру нужно через конденсатор, а до конденсатора (со стороны активной антенны) - батарейка на 3 В для питания усилителя в антенне.

Далее можно либо обрабатывать слитый дамп эфира matlab-скриптом - это может быть интересно в целях изучения принципов работы GPS, - либо использовать GNSS-SDR , который реализует декодирование сигналов GPS в реальном времени.

Принять аналогичным способом сигнал с ГЛОНАСС-спутников было бы затруднительно - там разные спутники передают на разных частотах, и все частоты в полосу RTL2832 не помещаются.

Другие применения и границы возможного

RTL2832 можно использовать для отладки радиопередатчиков, подслушивания за радионянями и аналоговыми радиотелефонами, для разбора протоколов связи в игрушках на радиоуправлении, радиозвонках, пультов от машин, погодных станций, систем удаленного сбора информации с датчиков, электросчетчиков. С конвертором можно считывать код с простейших 125 кГц RFID меток. Сигналы можно записывать днями, анализировать и затем повторить в эфир на передающем оборудовании. При необходимости тюнер можно подключить к Android-устройству, Raspberry Pi или другому компактному компьютеру для организации автономного сбора данных из радиоэфира.

Можно принимать фотографии с погодных спутников и слушать передачи с МКС - но тут уже потребуются специальные антенны, усилители. Фотографии декодируются программойWXtoImg .

Есть возможность захватывать зашифрованные данные, передаваемые GSM-телефонами (проект airprobe), в случае если в сети отключен frequency-hopping.

Возможности SDR на основе RTL2832 все-таки не безграничны: до Wi-Fi и Bluetooth он не достает по частоте, и, даже если сделать конвертер, из-за того, что полоса захватываемых частот не может быть шире ~2,8 МГц, невозможно будет принимать даже один канал Wi-Fi. Bluetooth 1600 раз в секунду меняет рабочую частоту в диапазоне 2400–2483МГц, и за ним будет не угнаться. По этой же причине невозможен полноценный прием аналогового телевидения (там нужна принимаемая полоса 8 МГц, с 2,8 МГц можно получить только черно-белую картинку без звука). Для таких применений нужны более серьезные SDR-приемники: HackRF, bladeRF, USRP1 и другие.

Тем не менее возможность исследовать как аналоговый, так и цифровой радиоэфир, прикоснуться к спутникам и самолетам теперь есть у каждого!

Программно-зависимые приёмники SDR на самом деле достаточно несложны и малогабаритны. Размером от спичечного коробка до пачки сигарет. Но как говорится, мал золотник, да дорог. При всей своей простоте, с компьютером и соответствующей программой, подобный приёмник превращается в достаточно серьёзное приёмное устройство. Вполне может использоваться как по прямому назначению, так и служить в качестве анализатора спектра. На сегодняшний день наиболее популярны приёмники разработанные YU1LM и различные варианты приёмникаSoftRock 40. Как правило, для упрощения конструкции, в качестве задающего генератора используется кварцевый генератор. С таким расчётом, чтобы центральная частота находилась в середине интересующего участка диапазона. Хотя ничего не мешает использовать и синтезатор частоты.

Рис.1 - Внешний вид простого SDR приемника


Для работы с такими приемниками создано несколько программ (например, Rocky, SDRadio, KGKSDR), которые обеспечивают перестройку по частоте путем изменения низкой промежуточной частоты (т.н. перестраиваемая ПЧ).


Рис.2 - Экранная форма программы для работы с SDR приемником


Блок-схема очень простого аналогового приемника для SDR на диапазон 40 м SoftRock40, который разработалиTony Parks, KB9YIG, и Bill Tracey, KD5TFD, приведена ниже. Он состоит из диапазонного полосового фильтра, квадратурного детектора Tayloe , малошумящего предварительного НЧ усилителя, кварцевого генератора на частоту 28,224 МГц, формирователя прямоугольных импульсов и делителя частоты на D-триггерах. Квадратурный детектор на быстродействующих ключах, предложенный D.Tayloe, N7VE, обладает большой перегрузочной способностью, низкими потерями, а также очень хорошими фильтрующими свойствами, т.к. этот детектор фактически включает в себя фильтр на коммутируемых конденсаторах. Частота кварцевого генератора в 4 раза превышает частоту принимаемого сигнала. С помощью D-триггеров частота кварцевого генератора делится на 4, а сигналы, подаваемые на квадратурный детектор, сдвинуты по фазе на 90о. Используя кварцевый генератор на частоту 28,224 МГц, можно принимать сигналы в диапазоне 40 м, находящиеся как выше, так и ниже частоты 7056 кГц.


Рис.3 - Структурная схема SDR приемника


Если частота дискретизации звуковой карты составляет 48 кГц, то на вход звуковой карты можно подавать сигналы частотой до 24 кГц. Следовательно, с упомянутым приемником перекрывается полоса частот от (7056 – 24) до (7056 + 24) кГц, т.е. 7032 - 7080 кГц. Прием в этой полосе ведется с использованием фазового метода подавления нерабочей полосы. Сигналы I и Q, сдвинутые по фазе на 90о, позволяют программному обеспечению отличать, как следует обрабатывать сигналы боковых полос в зависимости от того, выше или ниже частоты опорного кварцевого генератора (7056 кГц) ведется прием. При переходе частоты через ноль автоматически программно переключается боковая полоса, и, соответственно, получается удвоенная полоса приема. При частоте дискретизации звуковой карты 96 кГц диапазон перестройки SDR-приемника увеличивается до +/- 48 кГц. В зависимости от выбранной частоты дискретизации (48 или 96 кГц) желательно, чтобы частотная характеристика малошумящего предварительного НЧ усилителя имела завал на частотах выше 25 или 50 кГц соответственно. Любые сигналы, частоты которых расположены выше частоты дискретизации, будут интерферировать с полезными сигналами, вызывая появление побочных сигналов в потоке данных. Применив в опорном генераторе синтезатор частоты, формирующий сетку частот через 48 кГц или 96 кГц, на основе программы Rocky и аппаратной части SoftRock40 можно изготовить всеволновый всережимный SDR-приемник. Такой приемник имеет панорамный спектральный дисплей, DSP-фильтры с различной полосой пропускания и коэффициентом прямоугольности вплоть до 1,05 (!), традиционные для современных трансиверов и приемников функции подавления помех и снижения шума, автоматический notch-фильтр и т.д. Как правило, SDR-приемник обеспечивает демодуляцию практически всех распространенных видов излучения - CW, LSB, USB, AM, FM, а с помощью дополнительного программного обеспечения и цифровых видов - как радиолюбительских, так и коммерческих (например, DRM - цифрового радиовещания). Итак, какие же практические преимущества предлагает в настоящее время SDR по сравнению со стандартным радиолюбительским приёмником или трансивером? Первое и основное ключевое преимущество заключается в том, что программная часть SDR позволяет “увидеть” радиосигналы - не только тот, который принимается на определенной частоте, но и сигналы, которые присутствуют в определенном участке любительского диапазона. Это стало возможным благодаря очень высокой чувствительности и разрешающей способности панорамного спектрального дисплея. Steve Ireland, VK6VZ - “фанат” диапазона 160 м - построил SDR приемник на свой любимый диапазон. Тестируя Rocky и SoftRock на слабых телеграфных DX сигналах в диапазоне 160 м, VK6VZ отмечает, что, по сравнению с трансивером Yaesu FT-1000MP, из каждого четвертого сигнала, который он видит на экране компьютера, на слух, при перестройке FT-1000MP по диапазону, можно было заметить только один из них. А вот панорамный спектральный дисплей Rocky позволяет увидеть сигналы всех любительских передатчиков в полосе частот около 48 кГц, и кликом мышки настроиться на прием любого из них. Кстати, имея более 200 подтвержденных стран на диапазоне 160 м, VK6VZ считает, что стран было бы гораздо больше, если бы он в предыдущие годы использовал SDR-приемник. Спектральный дисплей в программе можно растянуть на всю ширину экрана монитора. Располагая самый интересный для радиолюбителя участок спектра перед глазами, можно действительно сказать: “Вижу, что диапазон представляет сегодня”. Кроме того, для работы спектрального дисплея используется полифазное быстрое преобразование Фурье, что позволяет отчетливо различать даже очень слабые сигналы на экране компьютера, которые при стандартном преобразовании просто сливаются. VK6VZ нашел, что слабые CW сигналы (S2 - S3) в диапазоне 160 м отчетливо отображаются даже летом, когда уровень шума на этом диапазоне очень велик. Кроме панорамного спектрального дисплея, который имеет очень высокое разрешение по частоте, в SDR-программах часто встроен дисплей с высоким разрешением по времени (“водопад”). Этот дисплей позволяет видеть даже телеграфные посылки, передаваемые со скоростью до 40 слов в минуту. Кроме того, с помощью “водопада” можно оценить спектральную чистоту принимаемых сигналов, в частности, увидеть выбросы на фронтах телеграфных посылок. Еще одно ключевое преимущество SDR заключается в том, что благодаря компьютерной обработке сигнала, когда селективность обеспечивается цифровыми методами, а не кварцевыми и электромеханическими фильтрами, у оператора появляется возможность непрерывной коррекции требуемой селективности. Например, в программе Rocky простым кликом мышки на “бегунке” управления шириной полосы пропускания фильтра и перетаскиванием бегунка можно плавно изменять ширину полосы пропускания выбранного фильтра (для телеграфного фильтра - от 600 до 20 Гц). Это означает, что можно действительно оптимизировать полосу пропускания для принимаемого сигнала с точки зрения получения наилучшего отношения сигнал/шум. Кроме того, фильтрация и подавление шума в SDR значительно лучше, чем в любом аналоговом трансивере, даже оборудованном дополнительными устройствами DSP. Говоря о SDR, также нельзя не отметить программную реализацию автоматической регулировки усиления, которая, в отличие от классической (аппаратной), обеспечивает оптимальный динамический диапазон выходного сигнала. Кроме того, в SDR автоматическая регулировка усиления имеет не только привычные состояния “быстрая”, “медленная” и “выключена”, но и позволяет регулировать такие параметры как время атаки, задержки включения и восстановления, порога срабатывания и т.д. Как правило, радиолюбители достаточно скептически относятся к S-метрам промышленных трансиверов, не говоря уже о самодельных конструкциях. И это вполне заслуженно, ведь традиционно S-метр зависим от напряжения системы АРУ. Да и калибровка в различных моделях трансиверов оставляет желать лучшего.


Рис.4 - S-meter


В SDR приёмнике, а точнее в программе, измерения никак не связаны с АРУ. Панорама замеряет уровни доDSP фильтра основной селекции, S-метр после. До этой части нет никаких регулируемых каскадов, способных изменить уровни сигналов. Достаточно откалибровать программу одним известным напряжением на антенном входе, например 50 мКв, хотя это значение не принципиально. Математика в дальнейшем безошибочно будет определять уровни сигналов на входе приёмника, начиная от уровня собственных шумов приёмной части, до максимально возможных. Это значит, что и S-метру и панорамному анализатору SDR радио вполне можно доверять не только при работе в эфире, но и использовать как измерительный прибор или анализатор спектра. Один американский радиолюбитель метко высказался по этому поводу, SDR - это измерительный комплекс с возможностями радио. Попробуйте собрать SDR приёмник, думаю он вас не разочарует и будет настоящим помощником в шэке.