Помощь в учёбе, очень быстро...
Работаем вместе до победы

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

Диссертация: Адаптация оптимальных решений нестационарных комбинаторных задач с помощью популяционно-генетических методов
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

В 2008 году программная система, составляющая прикладную часть диссертационной работы, прошла апробацию в ФГУ «ОКБМ им. И.И.Африкантова» при решении задачи оптимальной загрузки станка ANCA RX7 для изготовления и заточки режущего инструмента. А также в «ФНПЦ НИИИС им Ю.Е.Седакова» при решении задачи определения оптимальной последовательности выполнения проверок технологических операций при… Читать ещё >

Содержание

  • 1. ПОСТАНОВКА ЗАДАЧИ НЕСТАЦИОНАРНОЙ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ
    • 1. 1. Нестационарные задачи комбинаторного типа
    • 1. 2. Трудности решения задач комбинаторного типа
    • 1. 3. Обзор методов оптимизации нестационарных задач
    • 1. 4. Критерии оценки эффективности алгоритмов для решения задач в динамических средах
  • 2. ГАПЛОИДНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ
    • 2. 1. Переход от задачи дискретной оптимизации к задаче поиска, генетический поиск
    • 2. 2. Основные определения и структура генетического алгоритма
    • 2. 3. Операторы генетического алгоритма
    • 2. 4. Применение популяционно-генетического алгоритма к решению нестационарных задач дискретной оптимизации
    • 2. 5. Применение генетического алгоритма к решению задачи коммивояжера большой размерности
    • 2. 6. Гаплоидный генетический алгоритм с гипермутацией
    • 2. 7. Генетический алгоритм с использованием базы опыта для формирования начальной популяции
  • 3. ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ ПОВЕДЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
    • 3. 1. Шаблоны сходства генотипов
    • 3. 2. Основные теоретические результаты
    • 3. 3. Время сходимости и время захвата
    • 3. 4. Применение цепей Маркова для исследования генетического дрейфа в генетических алгоритмах
  • 4. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ С ДИПЛОИДНЫМ ПРЕДСТАВЛЕНИЕМ ГЕНОТИПА ДЛЯ РЕШЕНИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ
    • 4. 1. Диплоидная хромосома. Понятие доминирования
    • 4. 2. Операторы кроссовера и мутации для диплоидного представления
    • 4. 3. Диплоидные алгоритмы с доминированием и без
    • 4. 4. Диплоидный алгоритм для задач на перестановках
    • 4. 5. Метод, основанный на структурном представлении генотипа
  • 5. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ
    • 5. 1. Методы адаптации нестационарных функций
    • 5. 2. Описание программного комплекса
    • 5. 3. Сравнение различных подходов к адаптации решений на основе популяционно-генетических методов
    • 5. 4. Сравнение популяционно-генетического алгоритма с классическими алгоритмами на задаче о ранце

    5.5 Использование популяционно-генетического алгоритма в задаче определения оптимальной последовательности выполнения операций технологического контроля при производстве изделий микроэлектроники с микронными топологическими нормами.

    5.6 Использование популяционно-генетического алгоритма в задаче загрузки уникального оборудования.

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

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

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

Пионерами построения адаптивных систем в нашей стране являются И. Л. Букатова, Л. А. Расстригин, Я. З. Цыпкин. Они предлагали алгоритмы, способные работать при отсутствии достаточной априорной информации об объекте оптимизации (управления). Важной особенностью такого подхода является возможность адаптации и самоадаптации алгоритма в процессе поиска при накапливании информации об объекте в процессе поиска.

Введение

в алгоритмы аналогов биологических и социальных процессов привело к созданию новых методов: эволюционного моделирования (Л.Фогель, А. Оуенс, М. Уолш, И.Л.Букатова), эволюционных стратегий (I.Rechenberg, H.P.Schwefel), социальных эвристик (М.Л.Цетлин), эволюционной адаптации коллективом вероятностных автоматов (Ю.И.Неймарк, Л.А.Расстригин), генетических алгоритмов (J.H. Holland, D.E. Goldberg, Е. Goodman, К. A. De Jong, Z. Michalewicz, Д. И. Батищев, В. В. Емельянов, Л. А. Зинченко, В.М.Курейчик).

Сейчас одним из широко известных подходов являются эволюционные алгоритмы. Термин «эволюционные алгоритмы» был введен Михалевичем (Michalewicz) для обозначения всех алгоритмов, в основе которых лежат принципы популяционной генетики. Наиболее известными и развиваемыми сейчас представителями эволюционных алгоритмов являются эволюционное программирование [57], генетические алгоритмы [95], эволюционные стратегии [117,121] и генетическое программирование [99].

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

• отказ от использования истории и перезапуск алгоритма с нуля может быть очень затратным по времени;

• изменение условий задачи может быть не обнаружено совсем или в течение достаточно долгого периода времени;

• если изменения достаточно малы, то и решения могут отличаться незначительно;

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

Эволюционные алгоритмы уже достаточно хорошо зарекомендовали себя как в оптимизации сложных стационарных задач [1, 2, 11, 32, 67, 73, 77, 83, 88, 95, 98 и др.], так и для принятия решения или предсказания в условиях недостаточной информации [15,35,36,46,74,79,89,91,112,114,125,129,136]. Широкое использование эволюционных алгоритмов для решения задач оптимизации обусловлено их адаптивными свойствами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При помощи моделирования генетического алгоритма на цепях Маркова, исследован процесс сходимости к одному значению аллели при отсутствии селективного преимущества аллелей.

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

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

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

Для тестирования и сравнения предложенных алгоритмов разработана программная система, имеющая диалоговый интерфейс.

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

Материалы диссертационной работы были внедрены в учебный процесс факультета вычислительной математики и кибернетики ННГУ в 2007/2008 учебном году при преподавании курса «Генетические алгоритмы» (лектор Е.А. Неймарк), нашли свое отражение в учебном пособии «Применение генетических алгоритмов к решению задач дискретной оптимизации» [11], изданному в рамках Инновационной образовательной программы ННГУ.

В 2008 году программная система, составляющая прикладную часть диссертационной работы, прошла апробацию в ФГУ «ОКБМ им. И.И.Африкантова» при решении задачи оптимальной загрузки станка ANCA RX7 для изготовления и заточки режущего инструмента. А также в «ФНПЦ НИИИС им Ю.Е.Седакова» при решении задачи определения оптимальной последовательности выполнения проверок технологических операций при производстве изделий микроэлектроники с микронными топологическими нормами.

Результаты работы докладывались и обсуждались на Всероссийской научно-практической конференции «Компьютерная геометрия и графика»

Н.Новгород, 1998 г.), VI-ом Интернациональном Конгрессе по математическому моделированию (Н.Новгород, 2004г). На научном семинаре Института Динамики Систем и Теории Управления СО РАН (Иркутск). На Десятой национальной конференции по искусственному интеллекту с международным участием КИИ-2006 (Обнинск), на Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2006, ИСТ-2007)» (Н.Новгород), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (Н.Новгород).

Исследования по теме диссертационной работе проводились в рамках бюджетной темы «Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации». Структура и объем работы

Работа состоит из пяти глав, введения, заключения, списка литературы и приложений. Общий объем работы составляет 136 страниц.

Список литературы

составляет 150 наименований. Публикации по теме диссертации

По теме диссертации опубликовано 14 работ (в том числе 7 статей, 3 из которых опубликованы в сборниках, рекомендованных ВАК, и одно учебное пособие). Основные результаты диссертации опубликованы в следующих работах: [6,7,9,13,36,38,39]. Краткое содержание работы

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

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

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

разделить на несколько классов:

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

Поскольку методы сравнения эффективности алгоритмов оптимизации стационарных функций не подходят для сравнения эффективности алгоритмов оптимизации нестационарных функций, то в § 1.4 приводятся специальные меры эффективности, используемые для задач этого класса.

В главе 2 даются основные понятия генетического алгоритма на примере генетического алгоритма с гаплоидным представлением генотипа.

В § 2.1 показывается каким образом осуществляется переход от исходной задачи оптимизации к генетическому поиску.

В § 2.2 даны основные определения и понятия генетического алгоритма. В § 2.3 приводятся его основные операторы: формирование начальной популяции, кроссовер, мутация, селекция.

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

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

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

Поскольку эволюционный алгоритм в стандартной реализации, не дает хороших результатов, в основном из-за свойства преждевременной сходимости, поэтому для решения нестационарной задачи было рассмотрено несколько подходов на основе эволюционного алгоритма: алгоритм с явным использованием памяти (§ 2.7), алгоритм с гипермутацией (§ 2.6), гибридные алгоритмы (§ 2.4.2, § 2.4.4).

В § 2.6 описан метод с гипермутацией, этот метод основан на повышении вероятности мутации в популяции при обнаружении изменения состояния внешней среды.

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

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

В § 3.1 вводится понятие схемы (Schema). Схема — это шаблон, представленный строкой длины L, состоящей из символов {0,1,*}, который описывает сходство генотипов в определенных позициях. Понятие шаблона является основным в теоретическом исследовании поведения генетических алгоритмов. Вводится понятия средней приспособленности шаблона и средней наблюдаемой приспособленности.

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

В следующих параграфах § 3.3, § 3.4 приводятся исследования сходимости генетического алгоритма по одному признаку. Рассматривается процесс изменения пропорции аллелей в одном локусе популяции при переходе в следующее поколение. Выводятся рекуррентные соотношения для изменения пропорции аллелейформулы, отражающие время сходимости и захвата признаком популяции.

В главе 4 приводятся основные понятия, операторы и алгоритмы для диплоидного представления генотипа.

В § 4.1 вводится понятия диплоидной хромосомы и понятия доминирования, при помощи которого диплоидный генотип преобразуется в фенотип особи.

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

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

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

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

В § 5.1 описываются методы, применяемые в ходе вычислительного эксперимента: структурный алгоритм, диплоидный алгоритм, гаплоидный алгоритм с гипермутацией и две модификации гаплоидного генетического алгоритма для задачи о ранце.

В § 5.2 приводится описание программного комплекса, использовавшегося для тестирования и решения практических задач.

В § 5.3 приведены условия тестов, и результаты сравнения различных подходов к адаптации нестационарных функций на тестовых нестационарных задачах о ранце и задачах коммивояжера.

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

В § 5.5 приводится постановка задачи определения оптимальной последовательности выполнения операций технологического контроля при производстве изделий микроэлектроники с микронными топологическими нормами и результаты поиска оптимального решения этой задачи.

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

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

Для нестационарных комбинаторных задач разработаны модификации генетических алгоритмов.

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

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

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

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

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

6 Заключение

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

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

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

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

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

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

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

Разработана и исследована многоуровневая модель хромосомы для решения задачи коммивояжера большой размерности, обладающая адаптивной структурой, позволяющая понизить размерность решаемой задачи. Популяци-онно-генетический алгоритм, использующий ярусную модель хромосомы, был проверен на известных тестовых примерах Oliver’s -30, Eilon’s-50 и Eilon’s-75. С его помощью удалось построить разбиение на регионы и найти решения, которые совпадают с лучшими известными решениями, для каждой задачи.

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

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

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

Показать весь текст

Список литературы

  1. , Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие./ Д.И. Батищев- под ред. Львовича Я.Е.- Воронеж, 1995.64 с.
  2. , Д.И. Методы оптимального проектирования./ Д. И. Батищев М.: Радио и связь, 1984 — 248 с.
  3. , Д.И. Вычислительная сложность экстремальных задач переборного типа: Учебное пособие./ Батищев Д. И., Коган Д.И. Н. Новгород, ННГУ, 1994, 111 с.
  4. , Д.И. Декомпозиционный подход к нахождению минимального Га-мильтонова цикла./ Д. И Батищев, Е. А. Неймарк // Оптимизация и моделирование в автоматизированных системах. Межвузовский сборник научных трудов. Воронеж: ВГТУ, 1998, С. 12−19.
  5. , Д.И. Диплоидное представление в оптимизации нестационарной функции. / Д. И Батищев, Е. А. Неймарк //Труды НГТУ системы обработки информации и управления, 2005 Том 54. Выпуск 12 — С. 17−22.
  6. Ю.Батищев, Д. И. Оптимизация нестационарных задач комбинаторного типа с помощью генетических алгоритмов. / Д. И. Батищев, Е. А. Неймарк,
  7. Н.В.Старостин // Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25−28 сентября 2006 г., Обнинск): Труды конференции. В 3-т. Т.З. М.: Физматлит, 2006 — С. 976−983.
  8. П.Батищев, Д. И. Применение генетических алгоритмов к решению задач дискретной оптимизации: Учебное пособие. / Д. И. Батищев, Е. А. Неймарк, Н. В. Старостин Н. Новгород, изд-во ННГУ им. Н. И. Лобачевского, 2006 -136 с.
  9. З.Булгаков, И. В. Решение задачи коммивояжера с использованием генетических алгоритмов/ И. В. Булгаков, Е. А. Неймарк //Вестник ННГУ. Вып.2(19), 1998 С.186−192.
  10. , И.Л. Эвоинформатика: теория и практика эволюционного моделирования./ И. Л. Букатова, Ю. И. Михасев, A.M. Шаров М.:Наука- 1991 — 206 с.
  11. , И.Л. Эволюционное моделирование и его приложения./ И.Л. Бука-това М: Наука, 1979 — 232 с.
  12. Буш, Р. Стохастические модели обучаемости./ Р. Буш, Ф. Мостеллер — Перев. с англ.- М.: Физматгиз 1962 .- 481 с.
  13. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г. К. Вороновский, К. В. Махотило, С. Н. Петрашев, С. А. Сергеев.— X.: ОСНОВА, 1997.— 112 с.
  14. , С.Н. Системная память живого./ С. Н. Гринченко Москва: ИПИРАН, Мир.- 2004.
  15. , М. Вычислительные машины и трудно решаемые задачи ./ М. Гери, Д. Джонсон Пер. С англ.- М: Мир — 1982 — 416 с.
  16. , Ч. Сочинения: в 3 т./ Ч. Дарвин — Перев. с англ.- Изд-во АН СССР, Москва-Зт, 1939.
  17. , Р. Эгоистичный ген./ Р. Докинз- Пер. С англ. Пер. с англ. Н. О. Фоминой М: Мир, 1993 — 316 с.
  18. , Н.П. Избранные труды. В 4х томах. Т.1.: Проблемы гена и эволюции./ Н. П. Дубинин М: Наука — 2000 — 546 с.
  19. , Н. П. Некоторые проблемы современной генетики: РАН. Ин-т общей генетики им. Н. И. Вавилова./ Н. П. Дубинин М.: Наука — 1994 — 223 с.
  20. , Г. Н. Жадные алгоритмы для задачи о ранце: поведение в среднем / Г. Н. Дюбин, А. А. Корбут // Сибирский журнал индустриальной математики- 1999- Т. 2, № 2 (4). С. 68−93.
  21. , В.В. Теория и практика эволюционного моделирования./ В. В. Емельянов, В. М. Курейчик, В. В. Курейчик М.:ФИЗМАИЛИТ- 2003 -432 с.
  22. , А.Г. Самообучающиеся системы распознавания и автоматического управления./А.Г. Ивахненко Киев.: Техника -1969 .- 392 с.
  23. , А.А. Дискретное программирование./ А. А. Корбут, Ю.Ю. Финкель-штейн М: Наука, 1969 — 368 с.
  24. , Н. Теория графов. Алгоритмический подход. / Н. Кристофидес-
  25. Пер. с анг. М.: Мир, 1978. — 432 с.
  26. , В.М. Эволюционные методы решения оптимизационных задач: Монография./В.М.Курейчик -Таганрог: изд-во ТРТУ 1999 -95с.
  27. , И.И. Задача коммивояжера. Вопросы и теория./И.И.Меламед, О. И. Сергеев, И. Х. Сигал //АиТ 1989 — № 9, С.3−33 — № 10-С.З-29- № 11-С.З-26.
  28. , Б.М. Теория случайных процессов в примерах и задачах./ Б. М. Миллер, А.Р. Панков-М.:ФИЗМАИЛИТ, 2002 -302с.
  29. , В.И. Автоматная оптимизация с эволюционной адаптацией. / В. И. Мухин, Ю. И. Неймарк, Е. И. Ронин //Проблемы случайного поиска. -Рига, вып.2, 2005 С. 83−98.
  30. , Е.А. Оптимизация нестационарной функции с использованием генетического алгоритма / Е. А. Неймарк // Вестник ВГАВТ. Вып.14. Межвузовская серия Моделирование и оптимизация сложных систем. Н. Новгород: Изд-во ФГОУ ВПО ВГАВТ, 2005 С.85−90.
  31. , Е.А. Использование структурного генетического алгоритма для оптимизации нестационарной функции. / Е. А. Неймарк //Тезисы докладов международной научно-технической конференции ИСТ-2006 Н. Новгород, изд-во НГТУ, 2006 С. 176−177.
  32. , Е.А. Примемнение генетического алгоритма для решения нестационарной задачи коммивояжера. / Неймарк Е. А. // Системы обработки информации и управления: труды НГТУ.-Н.Новгород:НГТУ Т.65.Вып. 14, 2007 — С.152−155
  33. , Е.А. Решение нестационарной задачи о ранце при помощи генетического алгоритма. / Е. А. Неймарк //Вестник ННГУ. Вып.3(32), 2006 -С. 133 137
  34. , Ю.И. Динамические системы и управляемые процессы./ Ю. И. Неймарк М.: Наука, 1978 — 336 с.
  35. , Ю.И. Новые технологии применения метода наименьших квадратов. ./ Ю. И. Неймарк, Л. Г. Теклина -Н.Новгород :Изд-во ННГУ, 2003 196 с.
  36. , X. Комбинаторная оптимизация: Алгоритмы и сложность./
  37. Х.Пападимитриу, К. Стайглиц М.: Мир, 1985 — 510 с.
  38. , А.И. Алгоритм поиска глобального экстремума при проектировании инженерных конструкций./ А. И. Половинкин // АиТ № 1, 1975 С.88−103.
  39. Популяционно-генетический подход к решению задач покрытия множества./ Д. И. Батищев, В. Е. Костюков, Н. В. Старостин, А. И. Смирнов Н. Новгород, ННГУ, 2004−152 с.
  40. , JI.A. Адаптация сложных систем./ JI.A. Растригин Рига: Зинатне, 1981 — 376 с.
  41. , JI.A. Адаптивные компьютерные системы./ JI.A. Растригин М: Знание, 1987−60 с.
  42. , JI.A. Адаптация случайного поиска./ JI.A. Растригин, К. К. Рипа, Г. С. Тарасенко Рига: Зинатне, 1978 — 239 с.
  43. , Э. Комбинаторные алгоритмы. Теория и практика./ Э. Рейнгольд, Ю. Нивергельт, Н. Део Пер. с англ. Е. П. Липатова под ред. В. Б. Алексеева, — М.: Мир, 1980 — 476 с.
  44. , Ф.Н. Математическое моделирование экологических процессов. / Ф. Н. Семевский, С. М. Семенов Л: Гидрометеоиздат -1982 — 280 с
  45. , М.А. О подходе к доказательству сходимости эволюционных методов./ М. А. Семенов, Д. А. Теркел // Перспективы развития вычислительных систем. Рига: РПИ, 1985 С.92−102.
  46. , И.Х. Алгоритм приближенного решения задачи коммивояжера большой размерности и его вычислительная реализация. / И. Х. Сигал //ЖВМ и МФ, т.27, № 8, 1987 с.1145−1153.
  47. , И.Х. Введение в прикладное дискретное программирование./ И. Х. Сигал, А. П. Иванова, М. Физматлит, 2007 304с.
  48. , И.Х. Декомпозиционный подход к решению задачи коммивояжера большой размерности и некоторые его приложения / И. Х. Сигал // Изв. АН СССР. Техническая кибернетика, № 6, 1990 С.143−155.
  49. , И.Х. Задача коммивояжера большой размерности. / И. Х. Сигал -М: ВЦ АН СССР, 1968 -32с.
  50. , И.Х. Задача о рюкзаке: теория и вычислительные алгоритмы. Учебное пособие. / И. Х. Сигал М.: МИИТ, 1999 — 270 с.
  51. , В.Ф. Феномен науки: Кибернетический подход к эволюции./ В. Ф. Турчин -Изд. 2-е М.: ЭТС. 2000 — 368 с.
  52. , В. Введение в теорию вероятностей и ее приложения. Т.1. / В. Феллер М.: Мир- 1984 — 528 с.
  53. , В. Введение в теорию вероятностей и ее приложения. Т.2. / В. Феллер М.: Мир- 1984 — 752 с.
  54. , JI. Искусственный интеллект и эволюционное моделирование./ Л. Фогель, А. Оуэне, М. Уолш — Пер. с англ. М.:Мир, 1969 -230 с.
  55. Ху, Т. Ч. Комбинаторные алгоритмы / Т. Ч. Ху, М. Т. Шинг Пер. с англ. -Нижний Новгород: Изд-во Нижегородского госуниверситета им. Н. И. Лобачевского, 2004 — 330 с.
  56. , М.Л. Исследования по теории автоматов и моделированию биологических систем./ М. Л. Цетлин М.: Наука, 1969 — 316с.
  57. Цыпкин, Я.3. Адаптация и обучение в автоматических системах./ Я.З. Цып-кин М.: Наука. Гл. ред. физ.-мат. лит., 1968 — 400 с.
  58. , Я.З. Адаптивные алгоритмы оптимизации при априорной неопределенности./Я.З. Цыпкин //АиТ 1979- № 6- С.94−108.
  59. , С.С. Проблемы общей биологии и генетики. / С.С. Четвериков-Новосибирск, 1983 273 с.бб.Шмальгаузен, И. И. Кибернетические вопросы биологии. / Шмальгаузен И. И. Новосибирск: Наука — 1968 — 223 с.
  60. Эволюционные вычисления и генетические алгоритмы. /Составители Гудман Э. Д., Коваленко А. П. //Обозрение прикладной и промышленной математики. -М: Изд-во ТВП- Выпуск 5, 1996 С. 1−11.
  61. Adrews, М. Diversity does not necessarily imply adaptability./ M. Adrews, A. Tuson //GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems- J. Branke, editor, 2003- P. 24−28.
  62. Bendtsen, C. N. Dynamic Memory Model for Non-Stationary Optimization. / Bendtsen, C. N. and Krink, T. // Proceedings of the Fourth Congress on Evolutionary Computation (CEC-2002), Vol. 1, 2002 P. 145−150.
  63. Bertoni, M. Implicit parallelism in Genetic Algorithms./ M. Bertoni, M. Dorigo // In Artificial Intelligence (61) 2, 1993 P.307−314.
  64. Blackwell, Т. M. Swarms in dynamic environments. Lecture Notes in Computer
  65. Science (LNCS) No. 2723. / Т. M. Blackwell //Proceedings of the Genetic and Evolutionary Computation Conference 2003 (GECCO 2003), Chicago, IL, USA, 2003-P. 1−12.
  66. Branke, J. Memory enhanced evolutionary algorithms for changing optimization problems./ J. Branke // In Congress on Evolutionary Computation CEC99, Vol.3, IEEE, 1999 P. 1875−1882.
  67. Branke, J. Evolutionary approaches to dynamic environments updated survey./ J. Branke // In GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, 2001 — P.27−30.
  68. Branke, J. Evolutionary Optimization in Dynamic Environments./ J. Branke Klu-wer Academic Publishers, 2003 — 317 p.
  69. Branke, J. Multi-Population Approach to Dynamic Optimization Problems./ J. Branke, T. Kausler, C. Schmidt, and H. Schmeck A //In Adaptive Computing in Design and Manufacturing, Springer, 2000.
  70. Cobb, H. An Investigation into the Use of Hypermutation as an adaptive Operator in Genetic Algorithm Having Continuous, Time-Dependent Nonstationary Environments. / H. Cobb //Naval Research Laboratory Memorandum Report 6760, 1990.
  71. Cobb, H. G. Genetic Algorithms for Tracking Changing Environments./ H. G. Cobb, J. F. Grefenstette // Proceedings of the 5th International Conference on Genetic Algorithms Forrest, editor, 1993 — P.523−530.
  72. Collingwood E. Useful Diversity via Multiploidy ./ E. Collingwood, D. Corne, P. Ross // in Proceedings of International Conference on Evolutionary Computing, 1996-P. 810−813.
  73. Dasgupta, D. Optimisation in Time-Varying environments using Structured Genetic Algorithms/ D. Dasgupta // Technical Report No IKBS-17−93, Dec. 1993.
  74. Dasgupta, D. Nonstationary function optimization using the Structured Genetic Algorithm./ D. Dasgupta, D. R. McGregor // In Proceedings of Parallel Problem Solving From Nature (PPSN-2), Brussels, 28−30 September, 1992 P.145−154.
  75. Dasgupta, D. SGA: A Structured Genetic Algorithm./ D. Dasgupta, D. R. McGregor //Technical report no. IKBS-8−92, University of Strathclyde, 1992.
  76. Davis, L. Genetic Algorithms and Simulated Annealing, Morgan Kaufmann, 1987 216 p.
  77. Davis, L. Handbook of Genetic Algorithms/ L. Davis van Nostrand Reinhold, New York — 1991.
  78. Eggermont, J. Non-stationary function optimization using evolutionary algorithms with a case-based memory/ J. Eggermont, T. Lenaerts // Technical Report TR2001, 2001.
  79. Ghosh, A. Function optimization in nonstationary environment using steady state genetic algorithms with aging of individuals./ A. Ghosh, S. Tstutsui, and H.Tanaka. // In IEEE Intl. Conf. on Evolutionary Computation—, 1998 P.666−671.
  80. Goldberg, D.E. Genetic algorithms in search, optimization, and machine learn-ing./Goldberg D.E. Addison-Wesley, 1989
  81. Gordon, V. A note on the performance of genetic algorithms on zero-one knapsack problems./V.Gordon, A. BOhm, D. Whitley// Proceedings of the 1994 ACM symposium on Applied computing, 1994 P. 194−195.
  82. Grefenstette, J. J. Genetic Algorithms for changing environments./ J. J. Grefenstette // In Proceedings of Parallel Problem Solving From Nature (PPSN-2), Brussels, 28−30 September, 199 P. 137−144.
  83. Grefenstette, J. J. An Approach to Anytime Learning. Proceedings of the Ninth / J. J. Grefenstette, C. L. Ramsey //International Conference on Machine Learning, San Mateo, С A: Morgan Kaufmann, 1992 P. 189−195.
  84. Handbook of Evolutionary Computation/ Editors: Back Т., Fogel D.B., Michale-wicz Z.- Oxford University Press, NewYork, 1997.
  85. Haupt, R. Practical Genetic Algorithms/ R. Haupt, S. Haupt John Wiley & Sons, 1998−261 p.
  86. Holland, J.H., Adaptation in Natural and Artificial Systems/ J.H. Holland Ann Arbor: University of Michigan Press, 1975.
  87. Holland, J.H. Genetic algorithms and classifier systems: Foundations and future directions. / J.H. Holland// 2nd International Conference on Genetic Algorithms, 1987-P. 82−89.
  88. Hollstien, R. B. Artificial genetic adaptation in computer control systems./ R. B. Hollstien // Dissertation Abstracts International, 32(3):1510B (University Mi-crolmsNo. 7123, 773), 1971.
  89. De Jong, K. A. An analysis of the behavior of a class of genetic adaptive systems. / De Jong, К. A. //PhD Dissertation, Univ. of Michigan, 1975.
  90. Koza, John R. Genetic Programming: on the programming of computers by means of natural selection. // John R. Koza, -MIT Press. 1992.
  91. Larranaga, P./ Tackling the Traveling Salesman Problem with Evolutionary Algorithms: Representations and Operators / P. Larranaga, C.M.H.Kuijpers, R.H. Murga // Technical Report, 1998
  92. Louis, S. J. Solving similar problems using genetic algorithms and case-based memory. / S. J. Louis, J Johnson // In Proceedings of the Seventh International Conference on Genetic Algorithms, Morgan Kauffman, San Mateo. P.283−290.
  93. Lewis, J. A comparison of dominance mechanisms and simple mutation on non-stationary problems./ J. Lewis, E. Hart, G.Ritchie. // In 5PPSN: Parallel Problem Solving from Nature, Vol. 1498. LNCS, Springer, 1998 P. 139−148.
  94. Lin, S. An effective heuristic algorithm for the traveling salesman problem. / S. Lin, B.W. Kernighan //Oper.Res, Vol.21,#2, 1973 P.498−516.
  95. Lopez de Mantaras, R. Case-Based Reasoning: An overview. / R. Lopez de Mantaras, E. Plaza //AI Communications Journal 10(1), 1997 P. 21−29.
  96. Morrison, R. Performance measurement in dynamic environments./ R. Morrison // In J. Branke, editor, GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, 2003 P.5−8.
  97. Michalewicz, Z. Genetic algorithms + data structures = evolution programs./ Z. Michalewicz Springer Verlag, New York, 3rd edition, 1996.
  98. Mitchell, M. An Introduction to Genetic Algorithms / Mitchell M. MIT Press, 1996.
  99. Neumark, E.A. The application of GA for the decomposition of the TSP./ E.A. Neumark, A.M. Perelubsky //VI International Congress of Mathematical modeling. N. Novgorod, 2004 P.370.
  100. Ng, K. P. A new diploid scheme and dominance change mechanism for non-stationary function optimization. / K. P. Ng, K. C. Wong // Proc. 6th Int’l Conference on Genetic Algorithms, Morgan Kaufmann Publishers 1995, P. 159−166.
  101. Ohkura, K. Structured string representation and adaptive genetic search. / K. Ohkura, K. Ueda //In Proceedings of the Japan-USA Symposium on Flexible Automation, Vol.2., 1996 P. 1477−1480.
  102. Oliver, I. A study of permutation crossover operators on the traveling salesman problems. / I. Oliver, D. Smith, J.R. Holland //Proc. of the Second International Conf. on Genetic Algorithms. 1987 P.224−230.
  103. Ramsey, C. Case-based initialization of genetic algorithms./ C. Ramsey, J. Grefenstette // In Proc. Fifth International Conference on Genetic Algorithms. 1993 -P.84—91.
  104. Ramsey, C. L. Case-based anytime learning. // C. L. Ramsey, J. J. Grefenstette //In Case-Based Reasoning: Papers from the 1994 Workshop, (D. W. Aha, Ed.). Technical Report WS-94−07, AAAI Press: Menlo Park, CA, Aug., 1994.
  105. Rechenberg I. Evolution Strategy./ I. Rechenberg // Computational intelligence imitating life. IEEE Press. 1994.
  106. Rudolph, G. Convergence Analysis of Canonical Genetic Algorithms./ G. Rudolph // IEEE Trans, on Neural Networks, special issue on Evolutionary Computation, Vol. 5, no. 1, 1994- P.96−101.
  107. Ryan, C. Diploidy without dominance. / C. Ryan //In J. T. Alander, editor, Third Nordic Workshop on Genetic Algorithms, 1997 P.63−70.
  108. Ryan, C. The Degree of Oneness. / C. Ryan // 1st Online Workshop on Soft Computing, Nagoya, Japan, 1996 P. 100−105.
  109. Schwefel H.-P. Evolution and Optimum Seeking. / H.-P. Schwefel John-Wiley, New York, 1995
  110. Smith, R. E. Diploidy and Dominance in Artificial Genetic Search / R. E. Smith, D. E. Goldberg // Complex Systems, Vol.6, 1992 P. 251—285.
  111. Suzuki, J. A Markov Chain Analysis on Simple Genetic Algorithms./ J. Suzuki // IEEE Trans, on Systems, Man, and Cybernetics, April, 1995 P.655−659.
  112. Suzuki J. A Further Result on the Markov Chain Model of GAs and Their Application to SA-like Strategy./ J. Suzuki // IEEE Trans, on Systems, Man, and Cybernetics. Feb. 1998 P.95−102.
  113. Trojanowski, K. Evolutionary algorithms for non-stationary environments./
  114. K.Trojanowski, Z.Michalewicz.// In Proc. of 8th Workshop: Intelligent Information systems. ICS PAS Press, 1999 P.229−240.
  115. Vavak, F. Leaning the Local search range for genetic optimization in nonsta-tionary environments/ F. Vavak, K.A. Jukes, T.C.Fogarty //In IEEE Intl. Conf. on Evolutionary Computation ICEC'97 IEEE Publishing, 1997 P. 355−360.
  116. Van Hemert, J. A futurist approach to dynamic environments./ J. Van Hemert, C. Van Hoyweghen, E. Lukshandl, and K.Verbeeck.// In GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, 2001 P.35−38.
  117. Whitley, D. A Genetic Algorithm Tutorial. / D. Whitley //Statistics and Computing- Vol. 4, 1994 P. 64−85.
  118. Whitley, D. An Overview of Evolutionary Algorithms / D. Whitley //Journal of Information and Software Technology, Vol. 43, 2001 P. 817−831.
  119. Weicker, K. Performance Measures for Dynamic Environments./ K. Weicker // In: Parallel Problem Solving from Nature PPSN VII, Lecture Notes in Computer Science 2349. Springer-Verlag, 2002 — P. 64−73.
Заполнить форму текущей работой

Пора сдавать?