22. Особенности и причины появления «мягких» вычислений. Основные направления «мягких» вычислений.

Причины:

• любые ситуации, требующие принятия решений, содержат большое количество неопределенностей;

• человек часто оперирует качественными понятиями;

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

• человеческое мышление способно образовывать нечеткую информацию;

• традиционный математический аппарат для описания знаний человека использовать часто невозможно.

«Мягкие» вычисления – ветвь ИИ, в которой создаются математические алгоритмы, направленные на решение задач, имеющих свойство размытости и неточности.

«Традиционный» ИИ характеризуется:

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

• моделирование рассуждений на основе логического вывода (дедукция, индукция, аргументирование, рассуждения по аналогии и т.д.);

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

«Мягкие» вычисления характеризуются:

• основная идея: создание интеллектуальных вычислительных моделей, которые:

  • ориентированы на обработку неточной, неопределенной, частично истинной информации;

  • базируются на определенных аналогиях из реального мира;

• представление знаний является не чисто символьным, а символьно-числовым или числовым.

37. Эволюционное моделирование. Назначение и принципы построения генетических алгоритмов.

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

Основа эволюционного моделирования – принципы развития природы:

1. наследственность и улучшение в поколениях полезных свойств;

2. изменчивость;

3. естественный отбор.

Алгоритмические основы эволюционного моделирования:

1. генетические алгоритмы;

2. генетическое программирование;

3. эволюционные стратегии;

4. эволюционное программирование.

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

Основателем генетических алгоритмов считается Джон Холланд (англ. John Holland), книга которого «Адаптация в естественных и искусственных системах» (1992) (англ. Adaptation in Natural and Artificial Systems) является основополагающим трудом в этой области исследований.

Основные понятия ГА:

Хромосома – вектор (последовательность) из 0 и 1. Каждая позиция (бит) называется геном.

Индивидуум (генетический код) – набор хромосом (вариант решения задачи).

Кроссовер – операция, при которой 2 хромосомы обмениваются своими частями.

Мутация – случайное изменение одной или нескольких позиций в хромосоме.

О писание алгоритма

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

1. нахождение глобального, либо субоптимального решения;

2. исчерпание числа поколений, отпущенных на эволюцию;

3. исчерпание времени, отпущенного на эволюцию.

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

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

Отбор. На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.

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

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

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

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

• они не требуют никакой информации о поверхности ответа;

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

• они стойки к попаданию в локальные оптимумы;

• они хорошо работают при решении крупномасштабных проблем оптимизации;

• могут быть использованы для широкого класса задач;

• просты и прозрачны в реализации;

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

Недостатки генетических алгоритмов:

• в случае когда необходимо найти точный глобальный оптимум;

• время исполнения функции оценки велико;

• необходимо найти все решения задачи, а не одно из них;

• конфигурация является не простой (кодирование решения).

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

Генетические алгоритмы применяются для решения следующих задач:

• оптимизация функций;

• оптимизация запросов в базах данных;

• разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний);

• настройка и обучение искусственной нейронной сети;

• задачи компоновки;

• составление расписаний;

• игровые стратегии;

• теория приближений;

• искусственная жизнь;

• биоинформатика (свертывание белков).