+
Действующая цена700 499 руб.
Товаров:
На сумму:

Электронная библиотека диссертаций

Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО

Расширенный поиск

Применение имитационной нормализации в гибридных алгоритмах

  • Автор:

    Эйрих, Станислав Николаевич

  • Шифр специальности:

    05.13.18

  • Научная степень:

    Кандидатская

  • Год защиты:

    2012

  • Место защиты:

    Тольятти

  • Количество страниц:

    124 с. : ил.

  • Стоимость:

    700 р.

    499 руб.

до окончания действия скидки
00
00
00
00
+
Наш сайт выгодно отличается тем что при покупке, кроме PDF версии Вы в подарок получаете работу преобразованную в WORD - документ и это предоставляет качественно другие возможности при работе с документом
Страницы оглавления работы

Оглавление
Введение
Глава 1. О задачах дискретной оптимизации
1.1. Система линейных алгебраических уравнений
1.2. Транспортная задача. Задача коммивояжера
1.3. Минимизация недетерминированных конечных автоматов
Заключение
Глава 2. О методах решения
2.1. Обоснование выбора алгоритмов
2.2. Алгоритм имитационной нормализации
2.3. Генетический алгоритм
2.4. Метод ветвей и границ
Глава 3. Комбинированный алгоритм с настройкой на решение конкретной задачи дискретной оптимизации
3.1. Настройка генетического алгоритма на предметные области
3.2. Настройка алгоритма имитационной нормализации на предметные области
3.3. Преобразование метода ветвей и границ в незавершённый
3.4. Применение имитационной нормализации в гибридных
алгоритмах
Заключение
Глава 4. Сравнительные характеристики гибридных алгоритмов
4.1. Обзор методов и анализ сравнения алгоритмов
4.2. Результаты исследования гибридных алгоритмов
4.2. Результаты сравнения эффективности гибридных алгоритмов
Заключение
Приложение
Литература

Введение
Задачи оптимизации - одна из востребованных проблем современной вычислительной и прикладной математики. Решение подобных проблем требуется во многих задачах из различных отраслей науки и техники. Ещё Леонард Эйлер (1707-1783), один из величайших математиков, говорил: «В мире не происходит ничего, в чём бы не был виден смысл какого-нибудь максимума или минимума» [47]. При этом особый интерес представляет нахождение так называемых глобальных экстремумов (оптимумов) функции - т.е. таких оптиму-мов, которые являются наилучшими на всей рассматриваемой области определения целевой функции, а не только в сравнении с близлежащими точками из некоторой своей окрестности. При этом многие задачи, возникающие в различных сферах человеческой деятельности, могут быть сведены к задаче поиска глобального оптимума. Неудивительно, что в настоящее время оптимизация, особенно глобальная оптимизация, - актуальное и интенсивно развивающееся направление вычислительной математики.
Большинство задач дискретной оптимизации являются труднорешаемыми [15], т.е. на сегодняшний день нет алгоритмов, решающих такие задачи за время, ограниченное некоторым полиномом относительно размера входных данных; и, возможно, таких алгоритмов не

существует вообще. Трудными также считаются задачи, для которых полиномиальная разрешимость доказана - однако (пока) неизвестны полиномиальные алгоритмы небольших степеней.
Для огромного количества практических задач, возникающих в самых разных сферах практической деятельности, в качестве моделей выступают оптимизационные задачи. Основной проблемой решения оптимизационных задач является размерность. Для эффективного решения задач реальных размерностей применение точных алгоритмов на практике невозможно - т.к. вычисление целевой функции на каждом шаге итерации требует слишком больших затрат вычислительных ресурсов (машинного времени и, возможно, памяти).
Для задач дискретной оптимизации характерны такие отличительные признаки, как факториальный (а иногда - более чем факториальный) рост вычислительной сложности и допустимость приближённого решения. Представителями указанного класса задач являются КР-полные задачи оптимизации. В 1984 году А.А.Гагановым было показано, что даже для полиномиальной целевой функции Дх) задача глобальной оптимизации является КР-трудной [63] - что фактически равносильно признанию того, что для её решения требуются не менее чем экспоненциальные (в зависимости от размерности п) трудозатраты. Например, полученная недавно теорема Кирфотта-Крейновича,

• если л/ > 0 (реіиение ухудшилось), то принять с вероятностью

р = е Т в качестве текущего решения новый вариант решения X, к п. 5,
5. Вызвать функции изменения текущей температуры и шага мутации.
6. Если не выполнен критерий останова, то перейти к п.З.
2.3. Генетический алгоритм
Схема алгоритма [87]:
популяция
і Отбов Ц

{ Скрещивание

Переход к новому поколению Ч
I №утацмя
Результат
Рисунок
Опишем каждый шаг, показанный на рисунке 8 подробнее:
1. Сгенерировать начальную популяцию Х°.
2. Вычислить приспособленность каждой особи и популяции в целом. Посчитать вероятность выбора особей.
3. С определённой вероятностью выбрать две особи и применить операцию скрещивания.

Рекомендуемые диссертации данного раздела

Время генерации: 0.130, запросов: 967