<< Предыдущая Список Следующая >>


7. Расстановка наблюдений на двумерном случайном поле с помощью генетического алгоритма

Введение

 

На сегодняшний день задача расстановки наблюдений на двумерном случайном поле с целью наилучшего восстановления по ним всех отсчетов изображения не имеет удовлетворительного решения [1, 2]. Это связано прежде всего с тем, что известные классические подходы к решению оптимизационных задач не приводят к желаемым результатам из-за наличия существенно неравномерной функции сходимости к оптимальному значению. В результате возникает высокая вероятность попадания в локальные оптимумы, а оптимальное решение не достигается. Данная проблема показывает, что для достижения лучших результатов расстановки наблюдений следует использовать алгоритмы поиска способные преодолевать многочисленные локальные оптимумы. К таким алгоритмам относится генетический алгоритм. Восстановление изображений по отдельным отсчетам с помощью фильтра Винера

 

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

При восстановлении отсчетов изображений по известным наблюдениям в качестве критерия качества было выбрано максимальное значение дисперсия ошибок восстановления:

,

где  - восстановленное значение i-ого элемента.

Дисперсия восстановления отдельных отсчетов изображения по множеству неполных наблюдений определяться как

,

где С – MхN – матрица выделения множества неполных наблюдений, Hi – вектор коэффициентов фильтра для восстановления i-ого элемента, P=M{xi,X} – взаимная корреляция элемента xi c вектором X; Rxx=M{XXT} – корреляционная матрица вектора X; - диагональная матрица дисперсий шума наблюдений.

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

 

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

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

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

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

 

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

·        ген – координата пилот-сигнала на матрице представленной в виде вектора;

·        хромосома – вектор генов, определяющий конкретную растановку пилот-сигналов;

·        кроссовер – операция, при которой две хромосомы обмениваются своими частями;

·        мутация  – случайное изменение гена в хромосоме.

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

Шаг работы алгоритма состоит из трех этапов: генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения (current generation), скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения (next generation), и мутация нового поколения. Порождение новых экземпляров хромосом происходит в про­цессе скрещивания (кроссовера) родительских пар. Выбор пары членов популяции в качестве родителей производится случайным образом среди членов данного поколения. При этом вероятность выбора экземпляров в качестве родителей в базовом генетичес­ком алгоритме зависит от их значений функции полезности, т.е. чем лучше значение, тем выше должна быть вероятность выбора.

Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова (например время работы). На каждом поколении ГА реализуется отбор пропорционально приспособленности, кроссовер и мутация. Моделирование алгоритмов расстановки наблюдений изображения

 

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

Для матрицы 55 с 4 наблюдениями генетический алгоритм нашел оптимальное решение, выполнив 5000 итераций. Этот же результат был получен с помощью метода полного перебора, но за 12650 итераций.  Эксперимент был повторен 300 раз, из них в 276 ГА нашел оптимальную расстановку и только в 24 случаях результат был отрицательный. Таким образом, вероятность достижения оптимального решения генетическим алгоритмом составляет 92% при выигрыше по  скорости работы в сравнении с алгоритмом полного перебора в 2,5 раза.

Аналогичным образом были проведены исследования для матриц 6х6, 7х7, 11х11 разного числа наблюдений. Зависимость эффективности ГА от того, во сколько раз меньше итераций было произведено по сравнению с полным перебором, усредненная по множеству всех экспериментов приведена на рис. 1.

 

Рис. 1. Вероятность достижения оптимальной расстановки наблюдений
с помощью генетического алгоритма

 

Таким образом ГА с вероятностью более 90% позволяет найти оптимальное решение, перебирая в 2-3 раза меньше комбинаций, т.е. работая в 2-3 раза быстрее по сравнению с алгоритмом полного перебора. Литература

1.      Адаптивные фильтры: Пер. с англ./Под ред. К. Ф. Н. Коуэна и П.М. Гранта. – М.: Мир, 1988. – 392 с

2.      Васильев К.К. Крашенинников В.Р. Методы фильтрации многомерных случайных полей. – Саратов: Изд-во Сарат. ун-та, 1990. – 128 с.

3.      Введение в Генетические Алгоритмы [Электронный ресурс].- Режим доступа: http://www.gotai.net/documents/doc-ga-003.aspx

 


<< Предыдущая Список Следующая >>