Факторы, создающие сложность для ГА

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

Обманчивость ( deception ) — это характеристика функции, построенной так, что локальный максимум достигается при всех битах, равных 0, глобальный — при всех 1. При добавлении единицы в подстроку приспособленность особи будет падать (за исключением случая, когда все остальные биты подстроки уже равны 1). При замене 1 на 0 она будет расти. Поэтому популяция сойдется к решению, при котором большинство подстрок будут состоять из всех нулей, и лишь некоторые из всех единиц. Однако это не будет глобальным максимумом. Из этого решения попасть в глобальный максимум, т. е. заменить все нули единицами, для ГА будет невозможно.

Многоэкстремальность: это проблема для любого метода поиска, т. к. создается множество ложных аттракторов. Пример — функция Растригина Минимум достигается при всех x_i = 0. Количество аргументов функции можно варьировать, тем самым повышая или понижая сложность задачи поиска минимума.

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

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

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

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

Генетические оптимизаторы бывают встроены в специализированные программы, хотя чаще встречаются в виде компонентов или библиотек классов, дополнений к различным пакетам или самостоятельных исследовательских инструментов. Примером библиотеки классов с учетом компонентного использования может служить OptEvolve, генетический оптимизатор на C ++ фирмы Scientific Consultant Services: этот многоцелевой генетический оптимизатор использует несколько алгоритмов, включая дифференциальную эволюцию, и продается в виде портативного кода на C ++, пригодного для UNIX / LINUX, DOS и Windows.

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

Детерминированные технологии - это методики, которые на основе каких-либо моделей, алгоритмов, математических теорем позволяют по известным данным оценить значения неизвестных характеристик и параметров. Простейший пример аналитической технологии - теорема Пифагора, которая позволяет по длинам сторон прямоугольника определить длину его диагонали по известной формуле с² = а² + b².

последние 30-40 лет идет активное развитие аналитических систем нового типа. В их основе - технологии искусственного интеллекта, имитирующие природные процессы, такие как деятельность нейронов мозга, процесс естественного отбора, роевой интеллект пчел или муравьев. Искусственный (компьютерный) интеллект – это вычислительная система, способная самообучаться и принимать независимые решения.

Особенности мозга:

1) Способность к обучению на примерах.

2) Способность к обобщению (Мы не просто запомнили все примеры виденных деревьев, мы создали в мозгу некоторый идеальный образ абстрактного дерева. Сравнивая с ним любой объект мы сможем сказать, похож он на дерево или нет).

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

4) Ассоциативность нашей памяти. Это способность находить нужную информацию по ее малой части.

5) Поразительная надежность нашего мозга. При травмах или к старости некоторые структуры мозга теряют до 40% нервных клеток. При этом многие остаются в здравом уме и твердой памяти.

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

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

Рассмотрим строение биологического нейрона. Каждый нейрон имеет отростки нервных волокон двух типов - дендриты, по которым принимаются импульсы, и единственный аксон, по которому нейрон может передавать импульс. Аксон контактирует с дендритами других нейронов через специальные образования - синапсы, которые влияют на силу импульса. Нервная клетка может находиться в двух состояниях: обычном и возбуждённом. В возбуждённом состоянии клетка генерирует электрический импульс величиной около 100 мВ и длительностью 1 мс, который проходит по аксону до синапсов. Синапс при приходе импульса выделяет вещество, способствующее проникновению положительных зарядов внутрь соседней клетки. Синапсы имеют разную способность концентрировать это вещество, некоторые даже препятствуют его выделению - они называются тормозящими. Если суммарный заряд, попавший в клетку, превосходит некоторый порог, клетка возбуждается и генерирует импульс, который распространяется по аксону и доходит до синапсов, что способствует возбуждению следующих клеток. После возбуждения клетки наступает период релаксации. Некоторое время она не способна генерировать новые импульсы. Благодаря этому клетки работают по тактам, наподобие дискретных автоматов, а сеть в целом передаёт направленную волну импульсов.

Скорость распространения нервного импульса составляет приблизительно 100 м/с, что в миллион раз меньше скорости распространения электрического сигнала в медной проволоке. Тем не менее, сложные задачи распознавания человек решает за десятые доли секунды. Это означает, что нейровычисления требуют N= сотни последовательных тактов и выполняются с большой степенью параллелизма. Кора головного мозга человека содержит порядка 10¹¹ нейронов, и каждый нейрон связан с 10³ –10⁴ других нейронов. Это обеспечивает высокую взаимозаменяемость нервных клеток и надежность нервной системы в целом. Отказ даже существенной доли нейронов не нарушает нормального хода распространения нервного импульса.

Приближенно математическая модель описанного процесса следующая:

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

На рисунке изображена модель нейрона с тремя входами (дендритами), причем синапсы этих дендритов имеют веса w₁, w₂, w₃. Пусть к синапсам поступают импульсы силы x₁, x₂, x₃ соответственно, тогда после прохождения синапсов и дендритов к нейрону поступают импульсы w₁x₁, w₂x₂, w₃x₃. Нейрон преобразует полученный суммарный импульс x=w₁x₁+ w₂x₂+ w₃x₃ в соответствии с некоторой передаточной функцией f(x). Сила выходного импульса равна y=f(x)=f(w₁x₁+ w₂x₂+ w₃x₃).
Таким образом, нейрон полностью описывается своими весами w_k(t) и передаточной функцией f(x). Получив набор чисел (вектор x_k) в качестве входов, нейрон выдает некоторое число y на выходе. Рассмотренная модель МакКаллока-Питтса эквивалентна линейному пороговому классификатору.

Выражение u_i=w_i0+w_i1x₁+w_i2x₂. определяет плоскость в трехмерном пространстве, которая разбивает пространство входных сигналов < x₁, x₂ > на две области: в одной из них (заштрихованной) значения u_i >0, и, следовательно, функция активации принимает значение 1; в другой - u_i <0, и y_i =0. Таким образом, наглядно видно, что персептрон является простейшим линейным классификатором.

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

ИНС нашли применение в следующих областях.

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

Аппроксимация. ИНС дают возможность с любой требуемой точностью аппроксимировать нелинейную непрерывную функцию f(x). Применительно к проблематике автоматизированного проектирования — это задача построения формальной математической модели объекта.

Прогнозирование. Нейронные сети с обратными связями (рекуррентные нейронные сети) способны предсказывать будущее состояние моделируемого объекта/процесса по его состоянию на предыдущих шагах модельного времени и текущему воздействию Х. Основные достоинства ИНС состоят в следующем:

- способность к адаптации (обучению и самообучению);

- параллельность обработки информации;

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

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

Формулировка задачи для нейронной сети. Дано: растровое черно-белое изображение буквы размером 30x30 пикселов. Надо построить нейронную сеть с 900 входами и 33 выходами, которые помечены буквами. Сигнал на входе представляет из себя вектор, состоящий из нулей и единиц, описывающих растровую букву. Если на вход нейронной сети подано изображение буквы "А", то максимальное значение выходного сигнала должно быть на выходе "А". Аналогично нейронная сеть работает для всех 33 букв.

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

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