Методы поиска решений комбинаторных задач

 

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

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

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; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!