Алгоритмы решения задач выбора. 
Алгоритм отжига

Министерство образования и науки Российской Федерации Уральский Государственный Экономический Университет Институт менеджмента и информационных технологий Математическое обеспечение и администрирование информационных систем Кафедра статистики, эконометрики и информатики.

Курсовая работа.

Дисциплина: Алгоритмы и структуры данных Тема: «Алгоритмы решения задач выбора.

Алгоритм отжига" .

Исполнитель Аспидов Сергей Сергеевич Группа ЭМА-14−1.

Руководитель Ассистент Кислицын Е.В.

Екатеринбург 2015.

• Введение
• Глава 1.

  Введение

  в оптимизацию

• 1.1 Что такое оптимизация
• 1.2 Оптимизация как целевая функция
• Глава 2. Алгоритм отжига
• 2.1 Что такое алгоритм отжига
• 2.2 Метод градиентного спуска
• 2.3 Используемые переменные и описание алгоритма
• 3. Практическое задание
• 3.1 Введение в задачу коммивояжера
• 3.2 Представление задачи через граф
• 3.3 Сведение задачи к переменным и решение
• 3.4 Выходные данные
• 3.5 Листинг программы
• 3.5 Тестирование программы
• Заключение
• Список использованных источников

Термин интеллект (intelligence) происходит от латинского intellectus — что означает ум, рассудок, разум; мыслительные способности человека. Соответственно искусственный интеллект (artificialintelligence) — ИИ (AI) обычно означает свойство автоматических систем брать на себя отдельные функции интеллекта человека, например, выбирать и принимать оптимальные решения на основе ранее полученного опыта и рационального анализа внешних воздействий.

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

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

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

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

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

Актуальность темы: Задачи на поиск оптимального решения, используются повсеместно и помогают получить больше полезности при меньших затратах.

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

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

Задачи:.

1) Изучение теории о оптимизации;

2) Изучение алгоритма отжига;

3) Постановка задачи, практическая реализация решения.

Объект и предмет исследования:.

Объектом исследования данной работы является выяснение как с помощью математического и программного аппарата можно проанализировать экономические проблемы.

Предметом исследования являются виды экономических задач, решаемых с помощью графического метода линейного программирования.

Глава 1.

Введение

в оптимизацию.

1.1 Что такое оптимизация.

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

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

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

Так что же делает оптимизация? Оптимизация — находит хорошее решение, не всегда самое лучшее, но точно хорошее. Давайте узнаем определение слова оптимальное.

Оптимальное (от лат. optimus - наилучшее) решение - решение, которое по тем или иным признакам предпочтительнее других..

Следовательно, оптимизация — это способ нахождения оптимального решения.

1.2 Оптимизация как целевая функция.

Теперь давайте попробуем измерить насколько хорошее наше решение, в задаче про ранец давайте предметам присвоим их приоритет. Пусть у ножика будет 100 а у ноутбука 1. Мы уже имеем четкую цель и наша задача сведется к тому что мы найдем предметы с наибольшими значениями приоритета и возьмем их n-ное количество чтобы заполнить ими сумку. (Вес нас в данный момент не интересует) А теперь мы понимаем что мы ищем максимум некоторой целевой функции! А теперь опять все сведем к одному определению.

Оптимизация (математика) — нахождение экстремума (минимума или максимума) целевой функции в некоторой области..

Мы теперь поняли, что такое оптимизация, но появился главный вопрос КАК это представить?!.

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

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

Глава 2. Алгоритм отжига .

2.1 Что такое алгоритм отжига.

Давайте разберемся что такое алгоритм отжига и откуда у него растут ноги. Забегу в перёд и скажу что стохастических (умеющий угадывать) или вероятностных методов. Причем здесь вероятность и как она помогает чуть позже.

" Все гениальное, просто".

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

У каждого металла есть кристаллическая, она описывает положение атомов вещества. Совокупность всех позиций атомов веществ — Состояние системы, каждому состоянию соответствует определённый уровень энергии. Цель отжига — привести систему в состояние с наименьшей энергией. Чем ниже уровень энергии, тем лучше кристаллическая решетка. (меньше дефектов, прочнее метал).

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

Как видите, в рамках данного процесса происходит минимизация энергии. Меняем энергию на нашу целевую функцию, и Победа! Или нет? Давайте задумаемся, а чем же так хорош столь мудрёный процесс? Почему бы нам, например, всегда не переходить в состояния с меньшей энергией?

2.2 Метод градиентного спуска.

Примерно так работает имеющий широкое распространение метод градиентного спуска. (Рисунок 1).

Рисунок 1 Лыжник на целевой функции.

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

(Глобальный минимум функции).

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

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

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

2.3 Используемые переменные и описание алгоритма .

Теперь перейдём к математике.

Введём обозначения:

· S — множество всех состояний (решений) нашей задачи. Например, для задачи о вагоне это будет множество всевозможных наборов грузов.

· S_i — состояние на i-м шаге алгоритма. S_iS.

· t_i — температура на i-м шаге.

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

1. Функцию энергии — то что мы оптимизируем. E: S > R.

2. Функцию изменения температуры с течением времени. T: N > R.

3. Функцию, порождающую новое состояние. F: S>S.

А теперь по пунктам, подробно.

· каждому решению по какому-то правилу ставит в соответствие число. (Зависит от задачи).

· ставят номеру итерации i в соответствие с температурой.

· Функция определяет, как долго будет работать наш алгоритм (На семам деле у функции более важное значение).

· Если будет линейной функцией, то время работы будет относительно большим. В случае же со степенной функцией, все быстрей, но больше шансов попасть в локальный минимум.

· Функция на основе предыдущего состояния порождает новое состояние, в которое система может перейти. Обозначать будем его.

Теперь мы можем написать алгоритм отжига на алгоритмическом языке или через блок схему (Рисунок 2).

Ввод Ввод Пока Если то Если то вероятность перехода Понижаем температуру Возвращаем последние состояние.

Рисунок 2 Блок схема Алгоритм отжига.

Подставив в нашу формулу разность между и получим вероятность перехода. Представим единичный отрезок, разобьём его на две части, относительно нашей вероятности, число в левой части? Совершаем переход. В правой? ничего не делаем. (Рисунок3).

Рисунок 3 Вероятность перехода.

3. Практическое задание.

3.1 Введение в задачу коммивояжера.

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

Задача коммивояжера является одной из знаменитых задач теории комбинаторики. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются всё новые методы.

Постановка задачи следующая:

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3. n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

3.2 Представление задачи через граф.

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

Чтобы привести задачу к научному виду, введём некоторые термины. Итак, города перенумерованы числами jТ= (1,2,3,., n). Тур коммивояжера может быть описан циклической перестановкой t = (j₁, j₂,., j_n,), причём все j₁. j_n — разные номера; повторяющийся в начале и в конце j₁, показывает, что перестановка зациклена. Расстояния между парами вершин образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал.

Можно представить, чтоC состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребропроведено, если и не проведено, если. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу, то есть найдем гамильтонов цикл.

Используя графы задачу можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра . Найти гамильтонов цикл минимальной длины.

3.3 Сведение задачи к переменным и решение.

Увы наша задача использовать алгоритм отжига так что сведем задачу к нему.

· C — множество всех городов.

· |C| - общее количество городов.

· С_i-Каждый город представленный как пара координат.

· S — Все возможные маршруты проходящие через один город или множество упорядоченных последовательностей элементов С, в которой всякое C_i встречается ровно один раз и да длинна этой последовательности равна общему количеству городов - |C|.

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

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

Для тех кто забыл, Евклидово — расстояние между двумя точками, по координатам.

А теперь надо думать, как получать новое состояние? Почему просто не менять местами два произвольных города в маршруте, вроде все красиво, и правда это изменение будет непредсказуемо влиять на, но метод будет работать долго, и не факт что успешно.

Намного лучше выбирать два произвольных города и инвертировать путь между ними. Например был маршрут (1,2,3,4,5,6,7) случайно выбрали 4 и 6 город, получаем на выходе (1,2,3,6,5,4,7).

Так как алгоритм имеет вероятностную природу, случай может распорядиться так, что «отжиг» возьмёт, да и застрянет в локальном минимуме. Поэтому стоит сделать несколько запусков и обратить внимание к какому минимальному значению сходятся результаты и откорректировать минимальное значение для оптимального решения.

Рисунок 5 Пример высокого минимального значения температуры.

Рисунок 6 Пример правильного подобранного минимального значения температуры.

3.4 Выходные данные .

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

Применение задачи коммивояжёра. Задача коммивояжёра применяется для решения широкого круга экономических задач. В любом предприятии для получения прибыли требуется логистика ресурсов. Нахождение оптимального пути, при котором затраты минимизируются, а прибыль максимизируется. Значит, алгоритма данной задачи может применяться на различных предприятиях в разных сферах деятельности. Например, в туристическом агентстве, строительной фирме, автомобильных компаниях, фирме, выпускающей механические игрушки и компьютерные игры и т. д.

Рассмотрим примеры, где может применяться данный алгоритм.

Пример:

Рисунок 4. Самый короткий маршрут.

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

На (Рисунке 4) указан самый короткий маршрут между 15 городами, это один из 43 589 145 600 всевозможных вариантов.

3.5 Листинг программы.

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

Конченым решением было графическое представление пути между точками, без вывода расстояния между ними (которое можно было получить суммой всех метрик между точками.) У моей версии MatLab была проблема сборки в консольное приложение из-за того что под Windows 8.1 64bitвстроенный компилятор консольных приложений не работает правильно без SDK Windows 7 которое установить на мою систему не получалось. Я пытался использовать средства виртуализации и пробовал разные сборки Windows 7 64 bit. В них присутствовала другая проблема с компиляций приложения.

Города задаются заранее двухмерным массивом с помощью функции cities =rand (2,100) *10, там содержаться координаты по осям xи y.

St Temperature, end Temperature начальная и конечная температура отжига.

function [state] = Simulated (cities, st Temperature, end Temperature).

[n, z] = size (cities); %размер вектора городов.

state = randperm (n) '; %начальное состояние, как случайная перестановку городов.

current Energy = Calculate Energy (state, cities); %энергия для первого состояния.

T = st Temperature;

for k = 1: 100 000.

state Candidate = Generate State Candidate (state); %Состояние кандитат.

candidate Energy = Calculate Energy (stateCandidate, cities); % энергия состояния кандита.

if (candidate Energy.

current Energy = candidate Energy; % переход в текущее состояние.

state = state Candidate;

else.

p = Get Transition Probability (candidate Energy — current Energy, T); % или вычисление вероятности перехода.

if (Make Transit (p)) % проверка перехода.

Current Energy = candidate Energy;

state = state Candidate;

end.

end;

T = Dec Temp (st Temperature, k); % уменьшаем температуру.

if (T <= end Temperature) % условие выхода.

break;

end;

end.

end.

function [distance] = Metric (A, B) % Евклидова метрика.

distance = (A — B). ^2;

distance = sqrt (distance);

distance = sum (distance);

end.

function [a] = MakeTransit (probability) % Переход состояния.

value = rand (1);

if (value <= probability).

a = 1;

else.

a = 0;

end.

end.

function [P] = Get Transition Probability (E, T) % Расчёт вероятности перехода.

P = exp (-E/T);

end.

function [seq] = Generate State Candidate (seq) % Состояние координат.

n = size (seq, 1);

i = randi (n, 1);

j = randi (n, 1);

if (i> j).

seq (j: i) = flipud (seq (j: i));

else.

seq (i: j) = flipud (seq (i: j));

endend.

function [T] = DecTemp (stTemperature, k) % Уменьшение температуры.

T = stTemperature * 0.1/k;

end.

function [E] = Calculate Energy (sequence, cities) % Расчёт энергии.

n = size (sequence);

E = 0;

fori = 1: n-1.

E = E + Metric (cities (sequence (i):), cities (sequence (i+1):));

end.

E = E + Metric (cities (sequence (end):), cities (sequence (1):)); end.

3.5 Тестирование программы.

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

Список тестов и результаты приведены в таблице № 1 В следствии иногда большого количества координат, и не комфортном импортом данных, координаты городов не приводиться.

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

Таблица № 1.

Заключение.

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

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

Во второй главе курсовой мною был приведен алгоритм работы имитации отжига, работы с целевой функцией.

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

В этой части курсовой работы мною была поставлена задача; описаны входные, выходные данные и используемые временные переменные;

разработан алгоритм, реализована программа на MatLab с приведением листинга программы и ее тестирование.

На этом этапе большинство задач связанных с заданием были решены и частично цель достигнута.

Значит, все задачи частично выполнены, цель достигнута, тема раскрыта.

Список использованных источников.

1. Introduction in optimization. Simulation of annealing URL: http://sysmagazine.com/posts/209 610/.

2. Задача о составлении маршрута коммивояжера. Метод ветвей и границ URL: http://knowledge. /mathematics/d-3c0b65635a2ad78b4c53b89421206d37.

3. Решение задачи коммивояжера URL: http://otherreferats. /mathematics/177 241₀.

4. Алгоритм имитации отжига.

5. URL: http://www.math. nsc.ru/AP/benchmarks/UFLP/uflp_sa.

6. Алгоритм имитации отжига.

7. URL: http://www.machinelearning.ru/wiki/index. php? title=Алгоритм_имитации_отжига.

8. Как я изобретал метод имитации отжига URL: http://habrahabr.ru/post/210 942/.

9. Задача коммивояжёра | Метод имитации отжига URL: http://mech. math. msu. su/~shvetz/54/inf/perl-problems/chCommisVoyageur. xhtml.