Оценка эффективности генетического алгоритма

Рассмотрим простейший случай традиционного варианта генетического алгоритма, предполагая:

- цепочки символов в хромосомах бинарны,

- длина цепочек равна N=const,

- отбор пропорционально вероятностный,

- рекомбинации отсутствуют, есть только точечные мутации (случайные равновероятностные замены символов),

- численность популяций постоянна и равна n=const.

Будем считать, что приспособленность особей определяются хемминговой мерой близости, то есть имеется одна оптимальная особь Sm, а приспособленности других особей экспоненциально уменьшаются с ростом расстояния по Хеммингу между рассматриваемой S и оптимальной хромосомой Sm.

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

Разумно выбрать такую интенсивность мутаций, чтобы за одно поколение в среднем менялся один символ в хромосоме. То есть вероятность замены каждого символа Pm в процессе мутаций должна быть порядка N^-1.

Тогда, если пренебречь нейтральным отбором, то число поколений, требуемых для нахождения оптимума, составляет T~ (Pm)^-1~N (1)

Условие пренебрежения нетрального отбора может быть записано в следующем виде: T<Tn~n (2)

Это условие предполагаем выполненным на пределе, то есть полагаем, что Т~n.

Общее число особей, участвующих в эволюции, составляет: n_общ=nT

Комбинируя формулы 1 и 2, имеем: n_общ~n². Хотя оценки 1-3 являются грубыми, они важны с инженерной точки зрения – используя эти оценки, разработчик конкретного алгоритма может оценить ту вычислительную мощность, которая ему потребуется.

Компьютерное зрение: основные понятия.

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

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

Поэтому компьютерное зрение называют ключевой областью искусственного интеллекта.

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

Задачи, относящиеся к компьютерному зрению, являются сложными по следующим причинам:

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

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

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

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

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

Учет всех особенностей невозможен без априорных знаний или эвристик.

- в области компьютерного зрения требуется быстро обрабатывать большие объемы данных. Имеются задачи, требующие решения в реальном времени.

Обзор систем компьютерного зрения.

1. Visions

Создана А. Хэнсоном и Э. Райзманом в Массачусетском университете в начале 70-х годов прошлого века. Эта система технического зрения, основанная на знаниях, представляла собой среду для универсальной обработки и логических выводов.

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

2. ACRONYM.

Системы была разработана Р. Бруксом в Стэнфордском университет в середине 70-х годов 20 века. Система предвосхитила важную роль в 3D-моделировании. Возможности системы были продемонстрированы при интерпретации изображений аэропортов, полученных с самолетов, а также в робототехнических системах.

3. SIGMA.

Назначение системы – интерпретация аэроснимков. Система использовала принцип классной доски. В ней предусматривались средства взаимодействия с оператором.

Все эти системы представляли универсальную среду, в которую встраивались контекстно-зависимые модули.

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

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

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

В общем, представление структур меняется от уровня к уровню.

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

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

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

В-четвертых, нет необходимости, чтобы системы работали исключительно в направлении снизу-вверх (управление со стороны данных, то есть от сигналов к символам). Возможность возврата к предыдущим шагам обработки часто обеспечивает разрешение неоднозначности.

Активизация моделей и генерация гипотез происходит в нисходящем направлении.

Выделение граничных элементов.

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

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

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

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

Следующие наблюдения подтверждают это:

1. Нейроны, обнаруживающие границы, изобилуют на первых этапах зрительного пути.

2. Прерывистые движения глаза сканируют контуры при восприятии объекта.

3. Человек способен идентифицировать объект на основе простого рисунка в виде контурных линий.

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

- направлением,

- позицией,

- силой.

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

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

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

Элементы границы первоначально обнаруживаются при помощи градиентных (граничных) операторов.

Восстановление границ.

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

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

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

Одна из возможностей состоит в использовании кода Фримана со значениями, лежащими в диапазоне от 0 до 7. При этом используется некоторое соглашение о направлении границы и о положении объекта. Кроме этого, применяется специальная метка, обозначающая отсутствие границы.

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

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

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

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

Функция совместимости q_i^k(лямбда) определяет, насколько необходимо уменьшить или увеличить текущую вероятность (относительную силу метки лямбда) для пикселя i в процессе восстановления границы.

Возможная формула может быть такой:

Формула у Костика 1

Здесь k- номер шага итерации, величины r_ij и q_i^k(лямбда) характеризуются знаком, массив весов d_ij учитывает пространственное положение пикселей i и j; внутреннее суммирование выполняется по всем меткам пикселя j, характеризуемых вероятностями Р_j(лямбда’) относительной силы.

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

Обновление значений вероятностей выполняется на основе формулы:

Формула у Костика 2.

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

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

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

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

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

От граничных элементов к граничным сегментам.

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

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

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

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

Преобразование Хафа.

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

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

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

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

y=mx+b, где

m и b – параметры восстанавливаемой прямой линии

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

Трудности возникают при построении вертикальных линий, когда m→бесконечность. Имеются два решения этой проблемы:

1. Использование двух или более частных пространств параметров, то есть -1<=m<=1 и -1<=1/m<=1.

2. Использование для прямой линии другой системы параметров, например, в полярных координатах.

Уравнение прямой линии в полярных координатах имеет вид:

Ро=x*cos фи + y*sin фи

Ро – расстояние от прямой до начала координат.

Фи- угол наклона перпендикуляра, опущенного на прямую из начала координат,

X, y – координаты точки, лежащей на прямой.

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

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

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

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

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

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

Рассмотрим пример обнаружения кругов на изображении. Будем опять анализировать два пространства – пространство изображений и пространство параметров, которое в данном случае трехмерное.

Уравнение окружности в пространстве изображений имеет вид:

(x1-xс)²+(y1-yc)²=r²

В этом случае точкe x1, y1 в пространстве изображений соответствует коническая поверхность в пространстве параметров. Каждая из точек конической поверхности представляет набор параметров, которые определяют круг с центром в соответствующей точке пространства изображений и наоборот, если рассматривается некоторый круг в пространстве изображений, то он соответствует точке с координатами(xc1, yc1, r1) в пространстве параметров.

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

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

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

ЕЯ-интерфейс доступа к базам данных.

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

Рассмотрим построение ЕЯ-интерфейса базы данных на основе рационального подхода, в ходе которого выполняется анализ и интерпретация входных ЕЯ-запросов средствами традиционных грамматик.

Основная задача такого интерфейса – преобразование ЕЯ-запросов в запрос на внутреннем языке базы данных, например SQL. Применение ЕЯ-интерфейса для доступа к базам данным характеризуется следующими достоинствами:

1. Пользователю не требуется изучать сложные искусственные языки доступа к базе данных.

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

3. Возможность обработки запросов с учетом дискурса.

Существующие ЕЯ-интерфейсы баз данных используют различные подходы:

- метод сопоставления с образцом,

- синтаксические грамматики,

- семантические грамматики,

- некоторый внутренний язык.

Интерфейсы, основанные на методе сопоставления с образцом, являются наиболее простыми. Рассмотрим их особенности.

Пусть есть таблица реляционной базы данных, содержащая сведения о странах:

Страна	Столица	Язык
Франция	Париж	Французский
Германия	Берлин	Немецкий
Италия	Рим	Итальянский
…	…	…

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

1. Образец: … «столица&»…?S

Действие: вывести значение поля «Столица» для строки таблицы, удовлетворяющей условию Страна=S.

2. Образец: …”столица& ”…”стран&”;

Действие: вывести значения полей «Страна» и «Столица» для каждой строки таблицы.

В соответствии с первым правилом, если в запросе пользователя после слова «столица&» будет следовать название страны, то необходимо найти строку таблицы, для которой значение поля «Страна» сопоставимо со значением переменной образца S и сообщить пользователю соответствующее значение поля «Столица».

Второе правило активизируется, если в запросе пользователя после слова «Столиц&» следует слово «Стран&», например «список столиц всех стран». В этом пользователю сообщается весь список стран и их столиц.

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

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

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

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

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

Затем логический запрос преобразуется в выражение языка запросов базы данных и обрабатывается СУБД. На рисунке изображена возможная структурная схема ЕЯ-интерфейса доступа к базе данных с промежуточным логическим представлением запроса.

Рисунок 1.

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

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

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

Например, смысл слов «столица», «граничат», «страна» может представляться с помощью следующих предикатов на языке Prolog:

Столица (Столица, Страна)

граничат (Страна1, Страна2)

Является страной (Страна)

Семантический интерпретатор конструирует логический запрос из логических выражений лексикона. Например, вопрос «Назовите столицы стран, которые граничат с Германией» преобразуется в логический запрос, конструируемый из предикатов лексикона.

Ответ([Столица, Страна]):- является_страной(Страна), граничат(Страна, ‘Германия’), столица (Столица, Страна).

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

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

В случае реляционных баз данных устанавливается простая связь между каждым предикатом и оператором SELECT языка запросов SQL.

Пусть база данных содержит две таблицы: страны (см. выше) и таблица «граничат».

Страна1	Страна2
Франция	Германия
Франция	Швейцария
Германия	Франция
…	…

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

Ответ([Столица, Страна]):- явл_страной(Страна), граничат (Страна, ‘Германия’), столица (Столица, Страна).

Сведения об отображениях предикатов в отношениях базы данных позволяют сформировать следующие фрагменты SQL-запросов:

1. Для предиката «является_страной»

SELECT страна FROM Табл_стран

2. Для предиката «граничат»

SELECT страна1, страна2 FROM табл_граничат

3. SELECT столица, страна FROM табл_стран

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

SELECT Табл_страны.столица, Табл_страны.страна FROM Табл_страны, Табл_граничат where Табл_страны.страна=Табл_граничат.страна1 AND Табл_граничат. Страна2=’Германия’.

Данный запрос поступает на вход СУБД, которая обеспечивает поиск необходимого ответа и передает его на вход генератора ЕЯ-ответов.

Рассмотренный ЕЯ-интерфейс базы данных с промежуточным логическим представлением запросов характеризуется следующими достоинствами:

1. Благодаря выделению лингвистического интерфейса в самостоятельный модуль настройка интерфейса на конкретную СУБД требует адаптации только генератора запросов базы данных.

2. Выделение проблемно-ориентированных знаний позволяет достаточно просто адаптировать интерфейс к различным предметным областям.

3. Использование внутреннего логического представления запросов позволяет организовать взаимодействие с модулями логического вывода и тем самым использовать в ходе вывода сведения из базы данных.