Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Пример решения задачи коммивояжера





Задача коммивояжера является классической оптимизационной задачей. Суть ее заключается в следующем. Дано множество из n городов и матрица расстояний между ними или стоимостей переезда (в зависимости от интерпретации). Цель коммивояжера – объехать все эти города по кратчайшему пути или с наименьшими затратами на поездку. Причем в каж­дом городе он должен побывать один раз и свой путь закончить в том же городе, откуда начал.

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

0 4 6 2 9

4 0 3 2 9

6 3 0 5 9

2 2 5 0 8

9 9 9 8 0

Для решения задачи применим следующий генетический алгоритм. Ре­шение представим в виде перестановки чисел от 1 до 5,отображающей последовательность посещения городов. Значение целевой функции бу­дет равно стоимости всей поездки, вычисленной в соответствии с вышеприведенной матрицей. Сразу заметим, что одним из оптимальных реше­ний задачи является последовательность 514235 стоимостью 25.

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

В качестве оператора скрещивания выберем процеду­ру, похожую на двухточечный оператор скрещивания. Поясним его работу на примере. Пусть есть две родительские перестановки (12345) и (34521). Случайно и равновероятно выбираются две точки разрыва. Для примера возьмем ситуацию, когда первая точка разрыва находится между первым и вторым элементами перестановки, а вторая точка – между четвертым и пя­тым: (1|234|5), (3|452|1). На первом этапе перестановки обмениваются фрагментами, заключенными между точками разрыва: (* | 4 52 | *), (* | 234 | *). На втором этапе вместо звездочек вставляются соответствую­щие числа из исходной родительской перестановки, начиная со второго числа выделенного фрагмента и пропуская уже имеющиеся в новой перестановке числа. В данном случае в первой перестановке (1|234|5) таким начальным числом является 3, за ним идет 4, которое есть в новой перестановке, и мы его пропускаем, также пропускаем число 5, переходим на начало перестановки и выбираем число 1. В итоге вместо (* | 452 | *)получаем (34521) , аналогич­но из (3|452|1) и (* | 234 | *) получаем (52341).



Оператор мутации будет представлять собой случайную перестановку двух чисел в хромосоме, также выбранных случайно по равномерному за­кону. Вероятность мутации 0,01. Размер популяции выберем равным 4.

Исходная популяция представлена в таблице 9.1.

Пусть для скрещивания были выбраны следующие пары: (1, 3) и (2, 4). В результате были получены потомки, представленные в таблице 9.2.

 

Таблица 9.1

№ строки Код Значение целевой функции Вероятность участия в процессе размножения
32/122
32/122
29/122
29/122

 

Таблица 9.2

№ строки Родители Потомки Значение целевой функции для потомков
1|234|5 5|431|2
5|431|2 1|23|54 мутация 13254
2|143|5 4|312|5
4|312|5 2|143|5

Пусть для потомка (12354) сработал оператор мутации, и обменялись местами числа 2 и 3. В данном случае строка (12354) изменилась и приняла значение (13254). Популяция первого поколения после отсечения худших особей в результате работы оператора редукции приняла вид, представ­ленный в таблице 9.3.

Таблица 9.3

№ строки Код Значение целевой функции Вероятность участия в процессе размножения
1(1) 28/115
2(2) 28/115
3(н) 29/115
4(н) 28/115

Пусть для получения второго поколения были выбраны следующие пары строк: (1,4) и (2, 3). И в результате были получены потомки, показан­ные в таблице 9.4.

Таблица 9.4

№ строки Родители Потомки Значение целевой функции для потомков
|123|45 |214|35
|214|35 |123|45
|21|435 |13|452
|13|254 |21|354

Популяция второго поколения после отсечения худших особей приня­ла вид, показанный в таблице 9.5.

Таблица 9.5

№ строки Код Значение целевой функции Вероятность участия в процессе размножения
1(1) 28/115
2(2) 28/115
3(3) 29/115
4(н) 28/115

Таким образом, после двух итераций значение целевой функции для лучшего решения изменилось с 29 на 28, среднее значение изменилось с 30,5 до 28,75,а общее качество с 122 до 115. Таким образом, имеем незначи­тельное, но улучшение популяции.

Лекция. Нейросетевые системы

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

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

Задачи, решаемые с использованием нейросетей

Нейронные сети используют для решения следующих типов задач.

Распознавание образов

Задача состоит в отнесении входного набора данных, представляющих распознаваемый объект, к одному из заранее известных классов. К числу таких задач относятся распознавание рукописных и печатных символов при оптическом вводе в ЭВМ, распознавание типов клеток крови, распознавание речи и другие.

Кластеризация данных

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

3. Ассоциативная (контекстно – адресуемая ) память

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

Аппроксимация функций

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

Прогнозирование

Имеется набор значений y, представляющих поведение системы в моменты времени . Требуется по предыдущему поведению системы предсказать ее поведение y(tn+1) в момент времени tn+1. Эта задача решается при управлении складскими запасами и в системах принятия решений.

Оптимизация

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







Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2022 zdamsam.ru Размещенные материалы защищены законодательством РФ.