Теория и практика генетических алгоритмов

Размещено на http://www.allbest.ru/

Содержание

Введение

1. История

2. Описание алгоритма

2.1 Создание начальной популяции

2.2 Размножение (Скрещивание)

2.3 Мутации

2.4 Отбор

3. Применение генетических алгоритмов

4. Пример тривиальной реализации на C++

Литература



Введение

Генетимческий алгоримтм (англ. genetic algorithm) -- это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Генетический алгоритм (ГА) разработан Джоном Голландом (John Holland) в 1975 году в Мичиганском университете. В дальнейшем Д. Голдберг (D. Goldberg) выдвинул ряд гипотез и теорий, помогающих глубже понять природу генетических алгоритмов. К.ДеДжонг (K. DeJong) первым обратил внимание на важность настройки параметров ГА для общей эффективности работы и предложил свой оптимальный вариант подбора параметров, который послужил основой для всех дальнейших исследований. Существенный вклад в эти исследования внесли Дж. Грефенстетт (J. Greffenstett) и Г. Сесверда (G. Syswerda). Генетический алгоритм был получен в процессе обобщения и имитации в искусственных системах таких свойств живой природы, как естественный отбор, приспособляемость к изменяющимся условиям среды, наследование потомками жизненно важных свойств от родителей и т.д. Так как алгоритм в процессе поиска использует некоторую кодировку множества параметров вместо самих параметров, то он может эффективно применяться для решения задач дискретной оптимизации, определённых как на числовых множествах, так и на конечных множествах произвольной природы. Поскольку для работы алгоритма в качестве информации об оптимизируемой функции используются лишь её значения в рассматриваемых точках пространства поиска и не требуется вычислений ни производных, ни каких-либо иных характеристик, то данный алгоритм применим к широкому классу функций, в частности, не имеющих аналитического описания. Использование набора начальных точек позволяет применять для их формирования различные способы, зависящие от специфики решаемой задачи, в том числе возможно задание такого набора непосредственно человеком. Сила генетических алгоритмов в том, что этот метод очень гибок, и, будучи построенным в предположении, что об окружающей среде нам известен лишь минимум информации (как это часто бывает для сложных технических систем), алгоритм успешно справляется с широким кругом проблем, особенно в тех задачах, где не существует общеизвестных алгоритмов решения или высока степень априорной неопределенности.



1. История

«Отцом-основателем» генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого «Адаптация в естественных и искусственных системах» (1975)^[1] является основополагающим трудом в этой области исследований. Ему же принадлежит Генетические алгоритмы.

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

Ежегодно в мире проводится несколько конференций по этой тематике, информацию о которых можно найти в Интернетпо адресам:

Примерами служат задачи размещения, стандартизации, выполнимости и другие. Стандартный генетический алгоритм начинает свою работу с формирования начальной популяции I₀ = {i₁, i₂, …, i_s} -- конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов . Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако формирование "хорошей" начальной популяции (например из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума.

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

Доказательство теоремы схем.

1. Выбрать начальную популяцию I₀ и положить

f* = max { f (i) | i IРазмещено на http://www.allbest.ru/

₀}, k : = 0.

2. Пока не выполнен критерий остановки делать следующее.

2.1. Выбрать родителей i₁, i₂ из популяции I_k.

2.2. Построить i' по i₁, i₂.

2.3. Модифицировать i' .

2.4. Если f* < f (i' ), то f* : = f (i' ).

2.5. Обновить популяцию и положить

k: = k+1

Гипотеза 1.

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

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



2. Описание алгоритма

Схема работы генетического алгоритма

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

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

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» -- crossover и «мутация» -- mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение. генетический алгоритм оптимизационный программирование

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

· нахождение глобального, либо субоптимального решения;

· исчерпание числа поколений, отпущенных на эволюцию;

· исчерпание времени, отпущенного на эволюцию.

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

Таким образом, можно выделить следующие этапы генетического алгоритма:

1. Задать целевую функцию (приспособленности) для особей популяции

2. Создать начальную популяцию

· (Начало цикла)

1. Размножение (скрещивание)

2. Мутирование

3. Вычислить значение целевой функции для всех особей

4. Формирование нового поколения (селекция)

5. Если выполняются условия останова, то (конец цикла), иначе (начало цикла).

2.1 Создание начальной популяции

Перед первым шагом нужно случайным образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей.

2.2 Размножение (Скрещивание)

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

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

Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H0 (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный бич многих генетических алгоритмов -- недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них -- выбор для размножения не самых приспособленных, но вообще всех особей.

2.3 Мутации

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

2.4 Отбор

На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.



3. Применение генетических алгоритмов

Генетические алгоритмы применяются для решения следующих задач:

1. Оптимизация функций

2. Оптимизация запросов в базах данных

3. Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)

4. Настройка и обучение искусственной нейронной сети

5. Задачи компоновки

6. Составление расписаний

7. Игровые стратегии

8. Теория приближений

9. Искусственная жизнь

10. Биоинформатика (фолдинг белков)

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

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

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

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

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

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

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

1. Решение задачи представляется в виде хромосомы. 2. Создается случайный набор хромосом - это изначальное поколение решений. 3. Они обрабатываются специальными операторами репродукции и мутации. 4. Производится оценка решений и их селекция на основе функции пригодности. 5. Выводится новое поколение решений, и цикл повторяется. В результате с каждой эпохой эволюции находятся более совершенные решения.

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

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

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

Возникает вопрос: почему продажи на уровне 999 999 шекелей уже считаются низкими? Очевидно, что это не совсем корректное утверждение. Нечеткая логика оперирует более мягкими понятиями. Например, продажи на уровне 900 тыс. шекелей будут считаться высокими с рангом 0,9 и низкими с рангом 0,1.

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

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

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

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

Перспективы развития научного прогнозирования

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

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

Выбор метода прогнозирования

Любой процесс прогнозирования, как правило, строится в следующей последовательности:

1. Формулировка проблемы. 2. Сбор информации и выбор метода прогнозирования. 3. Применение метода и оценка полученного прогноза. 4. Использование прогноза для принятия решения. 5. Анализ “прогноз-факт”.

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

Выбор конкретного метода прогнозирования зависит от многих моментов. Достаточно ли объективной информации о прогнозируемом явлении (существует ли данный товар или аналоги достаточно долго)? Ожидаются ли качественные изменения изучаемого явления (оснащение автомобиля антигравитационным оборудованием)? Имеются ли зависимости между изучаемыми явлениями и/или внутри массивов данных (объемы продаж, как правило, зависят от объемов вложений в рекламу)? Являются ли данные временным рядом (информация о наличии собственности у заемщиков не является временным рядом)? Имеются ли повторяющиеся события (сезонные колебания)?

Используемые методы

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

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

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

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

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

Из экспертных оценок обычно используют хорошо известный метод “Дельфи”.

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

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

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

В-четвертых, грамотное применение научных методов прогнозирования обычно требует специальных знаний, соответствующего образования, умения пользоваться математическим и статистическим аппаратом, прикладными пакетами анализа и т. д. Какой же точности прогноза удается добиться с помощью используемых на практике методов? Здесь все, как правило, зависит от степени агрегированности показателя. Так, если прогнозировать совокупный общий объем реализации в деньгах - точность прогноза может достигать +-5%. Но если прогнозировать, например, объемы оптовых продаж потребительских товаров по ассортиментным позициям в разрезе регионов - очень высоким результатом считается 40-процентная точность попадания в интервал +-20% в пределах месяца, то есть объем реализации 40% позиций ассортимента угадан с точностью +-20%. Широко известным является факт значительного роста объемов оптовых продаж к концу месяца. Если сравнивать объемы продаж первой и последней недель внутри месяца - разница может достигать нескольких сотен процентов, тогда как разница между двумя месяцами обычно не так велика.

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

Научное прогнозирование и бизнес

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

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

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



4. Пример тривиальной реализации на C++

Поиск в одномерном пространстве, без скрещивания.

# include <iostream>

# include <algorithm>

# include <numeric>

int main()

{

using namespace std;

srand((unsigned)time(NULL));

const int N = 1000;

int a[N];

//заполняем нулями

fill(a, a+N, 0);

for (;;)

{

//мутация в случайную сторону каждого элемента:

for (int i = 0; i < N; ++i)

if (rand()%2 == 1)

a[i] += 1;

else

a[i] -= 1;

//теперь выбираем лучших, отсортировав по возрастанию...

sort(a, a+N);

//... и тогда лучшие окажутся во второй половине массива.

//скопируем лучших в первую половину, куда они оставили потомство, а первые умерли:

copy(a+N/2, a+N, a /*куда*/);

//теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше.

cout << accumulate(a, a+N, 0) / N << endl;

}

}



Литература

1. Александров Д. А. Алгоритм муравьиной колонии для задачи о минимальном покрытии. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т3 (1998), Иркутск, с. 17-20.

2. Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.

3. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер. 2. т6 (1999), № 1, с. 12-32.

4. Горбачевская Л. Е., Кочетов Ю. А. Вероятностная эвристика для двухуровневой задачи размещения. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т1 (1998), Иркутск, с. 249-252.

5. Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

6. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000.

7. Растригин Л.А. Случайный поиск -- специфика, этапы истории и предрассудки. Вопросы кибернетики. Вып. 33 (1978), с. 3-16.

8. Aggarwal C. C., Orlin J. B., Tai R. P. Optimized crossover for maximum independent set. Oper. Res. v45 (1997), pp 225-234.

9. Balas E., Niehaus W. Finding large cliques in arbitrary graphs by bipartite matching. Cliques, coloring, and satisfiability. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. v26 (1996), pp 29-49.

10. Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems. J. Heuristics. v4 (1998), N4, pp 107-122.

11. Boese K. D., Kahng A. B., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett.v16 (1994), N2, pp 101-114.

12. Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. Natural automata and useful simulations. London: Macmillan. 1966. pp 3-42.

Размещено на Allbest.ru

...