Методы поиска решений комбинаторных задач
Ввиду практической сложности решения в точной форме многих важных комбинаторных задач (симплекс-метода, метода ветвей и границ, теории графов и др.) и поскольку требуется получить некоторое решение, представляющее практический интерес, начали появляться алгоритмы, которые пропорциональны (соразмерны) решениям (т.е. удовлетворяют ограничениям) и приводят к оптимальному значению целевой функции в допустимое время.
Такие алгоритмы называют эвристиками. Имеется несколько причин, благоприятствующих распространению этих алгоритмов:
1. Когда не существует точного метода решения задачи или когда для этого требуется много вычислительного времени или памяти машины.
2. Когда нет необходимости получения оптимального решения.
3. Когда используются нечеткие числовые данные. Преимуществом эвристик является их большая гибкость, которая позволяет без труда управлять нелинейными функциями. Эвристики являются более легкими для понимания по сравнению со сложными математическими методами, использующими точные средства.
Напротив, один из недостатков эвристик заключается в том, что в общем случае невозможно узнать, как близко от оптимального х* найденное решение хлучшее. Если решается задача максимизации, то нам известно, что хлучшееЈx*. Без сомнения, существует метод для реализации взвешиваний (размежевания), состоящий в уменьшении задачи (удаляя, например, некоторые из ограничений или осуществляя “релаксацию Лагранжа” таким образом, чтобы ее легко было решить). Если оптимум уменьшенной задачи есть х’ и известно, что xлучшееЈx*Јx’, то значение х’ приближается к хлучшее и гарантирует, что эвристика дает хорошую аппроксимацию. Существуют различные типы эвристик, соответствующие способам достижения решения.
|
|
Конструктивные методы. Эти методы позволяют постепенное приближение к решению путем добавления к нему отдельных компонент до того момента, пока не получится выполнимое решение. Наиболее распространенный из этих алгоритмов – алгоритм ‘’greedy”, который строит шаг за шагом решения, отыскивая максимум выгоды на каждом шаге. Рассмотрим задачу о рюкзаке. Это задача о рациональной загрузке рюкзака, который имеет ограничение по объему. Каждый помещенный в рюкзак предмет имеет определенную значимость. Задача состоит в определении загрузки рюкзака такими предметами, которые приносят наибольшую суммарную пользу. Для решения этой задачи в соответствии с гриди (“greedy”) алгоритмом осуществляется движение между еще не отобранными элементами, и выбираются те из них, которые несут наибольшее значение на единицу объема, повторяя процесс до тех пор, пока не достигается больше продуктов.
|
|
Методы декомпозиции. Суть этих методов заключается в разделении задачи на подзадачи меньшего размера, считая выход одной задачи в качестве входа другой, таким образом, чтобы получить результат при решении всех задач. Пример применения этого метода к задаче смешанного линейного программирования состоит в определении некоторой формы (возможно с помощью другой эвристики) решения для входных переменных, и затем в решении полученной задачи линейного программирования путем замены этих переменных их значениями. В случае задачи о рюкзаке на первом шаге можно идентифицировать некоторым способом предметы, которые априори неинтересны (например, значение, меньшее единицы объема), и затем точно решать полученную задачу меньшего размера.
Манипулирование с моделью. Эти эвристики изменяют структуру модели с целью сделать ее более простой и получения ее решения в качестве результата исходной задачи. Она может состоять в уменьшении пространства решений (сделать линейные функции вместо нелинейных; сгруппировать переменные с целью уменьшения их количества; наложить новые ограничения на поведение, ожидая получить оптимальное решение и т.д.) или увеличении этого пространства (исключить ограничения в задаче).
|
|
Методы локального улучшения. Эти методы касаются получения выполненного решения на основе одного из решений (возможно полученных другими эвристиками) и посредством альтернативы его, базируясь на других выполненных решениях, но лучшей стоимости. В эту последнюю группу входят эвристики, которые позволяют реализовать переход от одного выполненного решения к другому. В связи с этим определяют окрестность N(s) решения s, т.е. множество решений подобных s. Слово “подобных” здесь понимается в том смысле, что можно получить одно s’ОN(s) исходя из решения s с помощью одной элементарной операции над s (удалить или добавить элемент, поменять элементы местами и т.д.).
Пусть в задаче о рюкзаке из пяти элементов имеем следующее решение: s={1,0,0,1,1}, где xi=1 означает, что выбран элемент i. Можно рассматривать в качестве окрестности s все те решения, в которых заменяется один из выбранных элементов другим. Таким образом, в N(s) могло бы входить решение s’={0,0,1,1,1}, где удаляется первая единица и помещается третья.
Эти методы называются также эвристическимистратегиями. Они не предполагают наличия процедуры и основываются на поиске решения среди элементов окрестности N(s), имеющего лучшее значение, которое улучшается до тех пор, пока не получается лучшее решение.
|
|
Одно из главных неудобств этих методов состоит в существовании локальных оптимумов, если имеется s’ОN(s), c(s), c(s’) (предполагается, что целью является минимизация и что c(s) представляет стоимость решения s (рис. 1.4)). Если в процессе поиска мы попали вначале в локальный оптимум, то эвристика будет продолжать поиск оптимального решения, а затем покинет эту ложную точку.
Рис. 1.4. Пример функции с локальным оптимумом: N(xi)={xi-1,xi+1}
Другая проблема эвристических стратегий состоит в создании независимых начальных решений. Очевидно, что начальная точка имеет большее влияние на возможность покинуть или нет локальный оптимум. Например, на рис. 1.4, если отправиться от точки xi-2, то можно избежать риска.
Эвристический поиск. Алгоритм А*. В интеллектуальных информационных системах (ИИС) знания обычно накапливаются фрагментарно и нельзя заранее определить цепочку логических выводов, в которых они используются. Поэтому методом проб и ошибок выбирается некоторая цепочка выводов, ведущая к цели, и в случае неуспеха осуществляется перебор с возвратами для поиска других цепочек выводов. Такой метод позволяет найти выход в самых различных ситуациях и свидетельствует о гибкости ИИС. Предложенный метод состоит из следующих шагов:
1. Выбрать некоторое действие из множества возможных действий.
2. Выполнить выбранное действие, тем самым изменив текущую ситуацию.
3. Оценить ситуацию.
4. Отбросить бесполезные ситуации.
5. Если достигнута цель (конечная ситуация), то конец, иначе выбрать новую исходную ситуацию и начать сначала.
Поскольку эффективность простого поиска низка, то возникает необходимость выбора пути, по которому следует начать поиск в первую очередь. При эвристическом поиске, например алгоритме А*, принимаются оценочные функции для оценки стоимости перехода от заданной ситуации к целевой.
Рассмотрим более детально алгоритм А*. Всякой ситуации S, полученной из исходной ситуации в результате выполнения некоторой цепочки действий, придается численная оценка
f(S) = g(S)+h(S),
где g(S) – реальная текущая стоимость ситуации S, h(S) – эвристическая функция, которая оценивает стоимость наилучшей последовательности действий, ведущей от состояния S к цели (решению). Следовательно, f (S) – мера стоимости решений, “подчиненных” ситуации S, т.е. решений, включающих то же подмножество исходных действий, что и S. Пусть с(S1,S2,a) – стоимость перехода из S1 в S2 с помощью действия a. Тогда g(S) равна сумме стоимостей действий, которые нужно выполнить, чтобы перейти от исходной к текущей ситуации.
Описание этого алгоритма удобно рассмотреть на примере игры в восемь (инвариант игры в пятнадцать). На поле 3х3 размещены восемь пронумерованных шашек. Цель игры: от заданного начального состояния перейти к целевому:
(За одно действие в пустую клетку можно поставить фишку, расположенную по соседству по вертикали или горизонтали.)
В этой игре имеется четыре действия – оператора преобразования состояния, соответствующие одному из передвижений фишки на пустой квадрат (слева, справа, сверху, снизу). Вместо передвижения фишки (какой-то) будем перемещать пустой квадрат.
С помощью указанных операторов и оценочной функции будем осуществлять поиск оптимального решения в пространстве состояний. Пусть f(n) – стоимость оптимального пути к цели от первой вершины (начального состояния) через n вершин дерева поиска:
f(n)=g(n)+h(n),
где g(n) – стоимость оптимального пути от первой до n-й вершины, h(n) – стоимость оптимального пути от n-й вершины до цели.
Будем считать, что стоимость перемещения одной фишки равна 1 (единица), т.е. оптимальным считается решение с минимальным числом ходов.
В процессе поиска в общем случае нельзя знать f(n), поэтому рассмотрим априорное значение f’(n). В момент прохождения n-й вершины g(n) известно и поэтому можно написать: f’(n)=g(n)+h’(n). Если представить пространство состояний в виде дерева, то g(n) – это глубина от первой до n-й вершины. В качестве h’(n), например, выберем число фишек, расположенных не на своих местах.
На рис. 1.5 показан результат поиска. Справа от каждой ситуации приводится пара значений g(n) и h(n).
десь важно, что h’(n)Јh(n), а истинно, если априорное значение стоимости от n-й вершины до цели меньше или равно истинной стоимости оптимального пути к цели, то это гарантирует, что обязательно будет найден оптимальный путь. Поскольку h’(n) – число фишек, находящихся не на своих местах, и h’(n) Јh(n), то мы не достигнем цели, пока число перемещений меньше числа фишек, находящихся не на своих местах. Если выбрать h’(n)=0, то мы имеем горизонтальный поиск, при котором раскрываются близлежащие вершины (число таких вершин быстро возрастает), и оптимальный путь при этом в конце концов находится. Если h’1(n)<h’2(n)Ј h(n), то можно доказать, что число вершин, раскрытых при поиске с использованием функции f1(n)=g(n)+h’1(n) меньше, чем при использовании функции f’2(n)=g(n)+h’2(n). А именно, h(n) можно рассматривать как объем эвристических знаний, предсказывающих стоимость пути от цели до цели. Следовательно, поиск тем оптимальнее, чем больше имеется эвристических знаний: h2(n)>h1(n).
Было предложено несколько вариантов этого алгоритма. В качестве f(S) использовалась f (S)=(1-a)g(S)+ ah(S), где a – константа, aО[0,1].
Таким образом, указывается определенный баланс между известной g(S) и эвристической составляющей h(S). Алгоритму А* соответствует a=1/2. При a=1 имеем градиентный метод, а при a = 0 – метод полного перебора.
Коэффициент a не обязательно должен быть постоянным в течение всего поиска: можно уменьшать его значение по мере нашего продвижения вперед, когда эвристическая оценка теряет свою значимость; для некоторой конкретной задачи наилучшие значения a могут быть приняты апостериорно для имитации числа получаемых ситуаций. Наконец, поиск может идти в двух направлениях: вперед от исходной ситуации, а также от целевой ситуации через инверсию возможных действий; поиск останавливается при появлении одинаковой ситуации в обоих графах.
Нейронные сети
Впервые нейронные сети появились в 40-е гг. С целью моделирования работы человеческого мозга исследователи создали аппаратные (а позже программные) средства, имитирующие функции биологического нейрона и его соединений. В 1943г. Маккалок и Питс предложили модель нейронной сети, которую они использовали для распознавания изображений. Возрождение интереса к нейронным сетям обязано, главным образом, разработке методов обучения многослойных сетей. Стремительное развитие исследований в этой области позволяет использовать полученные результаты для разработки интеллектуальных систем поддержки принятия решений.
Нейроны и связи между ними
Основные компоненты искусственных нейронных сетей моделируют структуру мозга. Мозг состоит из нейронов, которые являются малыми единицами обработки информации. Нейроны получают вход либо из внешнего окружения, либо от других нейронов. Нейроны соединены в большую и сложную сеть. Сеть состоит из дендритов, которые передают сообщения через различные пути в сети. Дендриты можно себе представить как дороги или скоростные пути, связывающие различные города (нейроны).
Связь этой сети с некоторым нейроном называется синапсом или синоптической связью. Синапс можно рассматривать как точку соединения, в которой принимаются сигналы дендритами. Нейроны имеют много таких точек соединения в сети. Нейрон может иметь до 10000 синапсов. Уникальной способностью нейрона является прием, обработка и передача электрохимических сигналов по нервным путям. Принятые синапсом входные сигналы суммируются, причем одни входы стремятся возбудить нейрон, другие – воспрепятствовать его возбуждению. Когда суммарное возбуждение в теле нейрона превышает некоторый порог, нейрон возбуждается, посылая сигнал другим нейронам.
Искусственный нейрон имитирует в первом приближении свойства биологического нейрона. В нейрон поступает некоторое множество входных сигналов из внешней среды или из других нейронов. Множество этих входных сигналов, обозначаемое вектором х1,...xn, соответствует сигналам, приходящим в синапсы биологического нейрона. Каждый входной сигнал xi умножается на соответствующий вес wi и поступает на суммирующий блок. Вес wi соответствует “силе” одной биологической синаптической связи. Множество весов обозначается вектором W. Суммирующий блок, соответствующий телу биологического элемента, складывает взвешенные входы и создает выход, который будем обозначать NET (рис. 1.6). С использованием векторных обозначений NET=XW.
Рис. 1.6. Искусственный нейрон
Нейроны соединяются в сеть путями, в которых выход одного нейрона служит в качестве входа другого нейрона. Эти пути, как правило, являются однонаправленными. Однако не запрещается использовать двунаправленную связь между двумя нейронами (рис. 1.7).
Рис. 1.7. Двунаправленная связь нейронов
Одним из наиболее важных элементов при проектировании нейронных сетей является “сила” связи между двумя нейронами, обозначаемая весом этой связи wij. При двунаправленной связи между нейронами i и j, как
правило, wij№wji. Область знаний формируется и хранится как множество значений этих весов и система обучается новым знаниям путем установления весов связей.
Рассмотрим более подробно входы и выходы нейронов. Нейрон i получает импульсы от n других нейронов, с которыми он соединен в сети. Поскольку нейрон i получает много входных импульсов, то его чистый вход равен:
NETi = S wjiOUTj
где j – все нейроны, соединенные с нейроном i.
В некоторых сетях абсолютное значение весов ограничены интервалом от 0 до 1. Эта нормализация позволяет избежать больших значений на входе нейрона.
Дата добавления: 2019-07-15; просмотров: 175; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!