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

На правах рукописи

Петров Юрий Юрьевич

ООЗ1727Б7

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ПРИМЕНЕНИЯ В ТЕХНИЧЕСКИХ СИО ЕМАХ

Специальность 05 13 18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

1 6 да 2008

Ставрополь, 2008

003172757

Работа выполнена в Северо-Кавказском государственном техническом университете на кафедре «Защита информации»

Научный руководитель: доктор технических наук,

доцент Калмыков Игорь Анатольевич

Официальные оппоненты: доктор технических наук, профессор Галуев Геннадий Аназ ольевич кандидат технических наук, доцент Бережной Виктор Васильевич

Ведущая организация: ЗАО «Орбита», г. Краснодар

Защита состоится 1 июля 2008 юда в 15 00 часов на заседании диссертационного совета Д 212.245 09 при Северо-Кавказском государственном техническом университете по адресу 355028, г Ставрополь, пр Кулакова, 2, ауд 305

С диссертацией можно ознакомиться в библиотеке Северо-Кавказского государственного технического университета по адресу 355028, г Ставрополь, пр Кулакова, 2, с авторефератом - на интернет-сайте www ncstu ru

Автореферат разослан 30 мая 2008 года

Ученый секретарь диссертационного совета —

кандидат физико-математических наук, доцент Мезенцева

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

- нечеткая логика и теория множеств,

- нечеткие экспертные, системы,

- системы приближенных вычислений,

- теория хаоса, фрактальный анализ,

- нелинейные динамические системы,

- гибридные системы (нейронечеткие, генетиконейронные, нечеткогенетические системы),

- нейронные сети,

- эволюционные вычисления

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

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

- проблемно-ориентированное кодирование решений в бинарную строку, называемую хромосомой (особью),

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

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

- возможность интеграции с неэволюционными алгоритмами

При этом, генетический алгоритм, в его базовой конфигурации, предложенной Холландом, обладает недостаточно высокой вероятностью нахождения глобального экстремума, вследствие известной проблемы «застревания» в локальных оптимумах Эта проблема в совокупности с

высокими временными затратами на решение задач ограничивают применимость генетических алгоритмов в технических системах

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

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

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

- использование нестандартных архитектур генетического поиска,

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

- использование нестандартных способов кодирования генотипа

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

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

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

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

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

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

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

Предметом диссертационных исследований являются математические модели генетических алгоритмов и генетических операторов

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

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

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

1 Разработка и анализ матемагической модели процессов сходимости к глобальному экстремуму целевой функции и выхода из локальных экстремумов

2 Разработка способа регуляции вероятностей генетических операторов для увеличения вероятности нахождения глобального экстремума

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

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

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

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

Апробация работы. Основные результаты по теме диссертационного исследования докладывались на VI Международной научно-практической конференции «Информационная безопасность» (Таганрог, 2004), I Международной научно-технической конференции

«Инфотелекоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2004), II Международной научно-технической конференции ('Инфотелекоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2006), VII Международной научно-практической конференции «Информационная безопасность» (Таганрог, 2005), IX региональной научно-технической конференции «Вузовская наука — Северо-Кавказскому региону» (Ставрополь, 2005).

Публикации. По теме диссертации опубликовано 16 печатных трудов, в том числе 5 статей в периодических научных изданиях, 8 публикаций в форме докладов на конференциях, 1 статья опубликована в журнале «Искусственный интеллект», входящем в перечень ВАК Украины, 1 статья опубликована в журнале «Системы управления и информационные

технологии», входящем в перечень, рекомендованных ВАК РФ для публикации докторских диссертационных работ,

Структура и объем работы. Диссертация включает введение, четыре тематических раздела, заключение, список используемых источников и три приложения Основное содержание работы изложено на 283 страницах, включая список литературы из 125 наименований, 17 таблиц и 67 рисунков

Реализация результатов Основные результаты диссертационных исследований внедрены в отделе казначейского исполнения бюджета по Шпаковскому району министерства финансов Ставропольского края (акт о внедрении от 17 04 2008), в учебный процесс кафедры защиты информации СевКавГТУ (акт о внедрении от 22 05 2008)

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

1 Анализ зависимости эффективности генетических алгоритмов от генетических операторов, способов кодирования генотипа и других параметров алгоритма

2 Анализ возможных схем интеграции генетических алгоритмов с другими методами оптимизации

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

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

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

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

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

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

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

- экстремальный шаблон, это шаблон, множеству которого принадлежит генотип экстремума целевой функции,

- глобально-экстремальный шаблон, это шаблон, множеству которого принадлежит генотип глобального экстремума

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

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

(ц

где Ни Я2 - шаблоны, такие что <Т(Н2) = сг(//,) +1 и Н2 С //,, 3(Н) - длина шаблона, сг(//) - порядок шаблона, //'(//) - текущее

значение средней выживаемости по шаблону Я, // - значение

выживаемости популяции в целом в момент времени Ь - длина хромосомы, Рк— вероятность кроссинговера, /^ — вероятность мутации

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

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

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

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

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

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

Вероятность мутации определяется выражением

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

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

(2)

(3)

(4)

Рисунок 1 - Распределение потомков оператора стандартной мутации для 8-ми битной хромосомы. Исходная особь в центре.

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

Критерий равномерности распределения потомков оператора

стандартной мутации — Ру| определяется выражением:

На основании численного анализа формулы (5), для различных Ь, в работе делается вывод о степени расхождении распределения стандартной мутации Ру с равномерным распределением РЕ, а затем об эффективности оператора стандартной мутации для всех значений Рм (рис. 2).

Наибольшая эффективность оператора достигается при Рм = 0,5 .

Действительно, подставив Рм = 0,5 в (5), получаем ||Р£ — Ру |] = 0, а при

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

Рисунок 2 — Эффективность оператора мутации в зависимости от вероятности мутации

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

Рисунок 3 - Популяция «застряла» в локальном экстремуме при оптимизации функции Гриенвонка

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

и производит потомка у е £> £> - область определения целевой функции, 0 = {х = (х1,х2, ,хы)\х, е [а1,Ь1]} , 1 = 1,N Процесс производства

потомка состоит из двух этапов выбор направления мутации и выбор расстояния мутации Выбор направления мутации происходит путем выбора из пространства £> случайного вектора т] За расстояние мутации принимается случайное число р, равномерно распределенное на интервале [0, /(г)], где г(г) - функция максимального расстояния мутации

За функцию максимального расстояния мутации принимается любая скалярная функция одного переменного, непрерывная, возрастающая, принимающая значения на [0, определенная на интервале [0, Ктах\, где Итах - некоторая мера пространства В Значение Нтах рассчитывается следующим образом

Яша*= (б)

Тогда за функцию максимального расстояния мутации можно взять

После того, как направление мутации и расстояние мутации получены, рассчитывается потомок по формуле

у = х + {т]-д), (8)

где вектор £ - центр области определения, вычисляется так

+ (9)

В выражении (8), фенотипх + (г]-д) принадлежит пространству О (рис 4), следовательно, необходимо отобразить его в пространство

Г Г-ч/

Рисунок 4 - Особь у в пространстве и

Пространство I)' определяется параметрами исходной особи

= • )

Для отображения О' в О используется функция /аЬ(у')

У,, если а, <у, <Ь,

Ы/) = \у',+(.Ь.-а,), если у, >Ь1 (10)

у'-(Ь,~а,) если у' <а, С учетом способа кодирования и функции отображения (10)

выражение (8) будет выглядеть так

^ = <п>

Распределение потомков данного оператора вычисляется так £ (Ъг~аг)

Ру =

(12)

Рисунок 5 - Распределение потомков в операторе с равномерным распределением потомков, радиус максимального расстояния мутации равен.5

Из (12) видно, что вероятность каждого потомка оператора мутации зависит только от расстояния между исходной особи х и потомком у и не зависит от Рм■ С учётом равномерности распределения радиуса мутации р

на интервале [о,г(г)]> имеем распределение потомков равномерно внутри

круга, радиусом г{г) ■ На рисунке 5 отображено распределение потомков,

вычисленное по формуле (12), для 8 битной хромосомы. Радиус г(£)~5.

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

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

Выполнение алгоритма происходит следующим образом:

1. Инициализация алгоритма: вычислить значение по формуле (4); вычислить вектор С, по формуле (9).

2. Инициализация начальной популяции: присвоить г = 0; инициализировать М случайных генотипов особей и сформировать из них начальную популяцию Р = л, ..., вычислить значения

приспособленности популяции Ц = {[гх,Цг, /им ), где Ц, = f{g~\s¡)), присвой

/-1 м

3 Начало формирования нового поколения присвоить к= 1, вычислить вероятности кроссинговера и мутации по формулам (2) и (3)

4 Отбор особи в новое поколение выбрать два случайных числа ^ и

из интервала [О, М] таких, что ^ Ф если /и^ > щ , тогда ¿к = , иначе -

5. Кроссинговер выбрать случайное число из интервала [0, 1], если выбранное число больше Р^г) то перети к шагу 8,

6 Отбор второй особи для скрещивания выбрать два случайных числа ^ и из интервала [О, Щ таких, что ^ Е,г, если > , тогда

= ^ , иначе =

7. Скрещивание выбрать случайное число £ из интервала [2,Ь - I], в качестве потомка с равной вероятностью выбрать один из двух вариантов, полученных при замещении битов особи с позиции от 1 до £ -1, либо с

позиции £ до I, соответствующими по индексам битами особи л*, полученный потомок перезаписывается в особь

8. Мутация выбрать случайное число из интервала [0, 1], если выбранное число больше Рм(г), тогда перейти к шагу 9, выбрать N случайных чисел каждое из соответствующего интервала [а|? ¿гД г = ЦУ>

сформировать из них вектор г] = {г]1,Т]2, ,Г)Ы), рассчитать максимальное

расстояние мутации по формуле (7), вычислить потомка по формуле (11),

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

9. Выбор элитарной особи присвоить к = к+ 1, если к = М - 1, тогда в качестве элитарной особи выбрать из популяции Р особь я, с максимальной приспособленностью, для которой и = тах ¡Л И перейти к

шагу 10, иначе перейти к шагу 4

10. Формирование нового поколения Сформировать из полученных особей новую популяцию /*'= {.у^^, вычислить значения

приспособленности популяции // ={ц[, , , где =

присвоить^ =тжм>

1=1,м

11 Счетчик эпох без изменения наилучшей приспособленности если рС > Ц, тогда 2 = 0, иначе г = г + I, новая популяция становится текущей

Р = Р'

12. Условие окончания работы алгоритма если г = V, то в качестве ответа принять элитарную особь Хц = g'l{sм)> "наче перейти к шагу 3

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

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

1 Определить множество тестируемых алгоритмов

2 Определить множество тестовых задач

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

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

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

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

6 Строится таблица тестируемых алгоритмов и их полученных характеристик

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

Четвертая частная задача решена с помощью указанного программного комплекса Были получены сравнительные оценки надежности нахождения глобального экстремума для различных модификаций генетических алгоритмов, в том числе и разработанных в диссертационной работе Оценки некоторых модификаций и предложенных генетических алгоритмов в таблице 1 В качестве тестовых выбран набор сложных многомерных (2, 5 и 10 мерных) функций Де Ионга, Растригина, Гриенвонка Так же в набор тестовых функции включены задача распределения ресурсов и задача одномерной упаковки

Таблица 1 - Сравнительные характеристики надежности нахождения глобального экстремума ряда генетических алгоритмов__

№ Тестируемый алгоритм Вероятность нахождения глобального экстремума Скорость нахождения глобального экстремума, %

1 Генетический алгоритм с двухточечным кроссинговером, регуляцией вероятностей генетических операторов, мутацией с равномерным распределением потомков 0,9074 157

2 Генетический алгоритм с регуляцией вероятностей генетических операторов и мутацией с равномерным распределением потомков 0,8677 163

3 Генетический алгоритм с двухточечным кроссинговером 0,8095 110

4 Генетический алгоритм с двухточечным кроссинговером и точечной мутации 0,801 115

5 Ггнетический алгоритм с унифицированным кроссинговером и точечной мутации 0,7879 152

6 Простой генетический алгоритм 0,773 100

7 Генетический алгоритм с точечной мутацией 0,7628 159

8 Генетический алгоритм с рулеточным отбором 0,7609 60

9 Генетический алгоритм с мутацией «инцест» 0,7444 90

10 Генетический алгоритм с двухточечным кроссинговером и рулеточным отбором 0,7438 67

11 Генетический алгоритм с унифицироеанньш кроссинговером 0,6837 64

12 Генетический алгоритм с унифицированным кроссинговером и рулеточным отбором 0,6714 76

Жирным шрифтом отмечены алгоритмы, предложенные в диссертационной работе

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2 Разработана математическая модель генетического алгоритма, описывающая процессы, происходящие на разпичных этапах генетического поиска

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

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

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

Список публикаций по теме диссертационной работы:

Статьи в периодических научных изданиях, рекомендованных ВАК РФ

1 Петров, Ю10 Математическая модель равновероятного распределения потомков в генетическом алгоритме [Текст] / А Ф Чипига, 10 Ю Петров // Системы управления и информационные технологии - 2005 - №2

Публикации в периодической литературе

2 Петров, Ю Ю Применение генетического алгоритма с регуляцией вероятностей генетических операторов при решении задачи упаковки в контейнеры [Текст] // Сборник научных трудов СевКавГТУ, Серия «Естественнонаучная» — Ставрополь СевКавГТУ, 2006 -№2

3 Петров, Ю Ю Генетический алгоритм с равновероятным распределением потомков [Текст] / А Ф Чипига, Ю Ю Петров II Информационные технологии моделирования и управления Вып 18 - Изд-во «Научная книга», 2004

4 Петров, Ю Ю Генетический алгоритм с регуляцией вероятностей кроссинговера и мутации [Текст] / А Ф Чипига, Ю Ю Петров // Межвузовский сборник научно-практических трудов Вып 2 - Ставрополь ЗАО «Пресса», 2004

5 Петров, Ю Ю Модифицированная математическая модель простого генетического алгоритма [Текст] / АФ Чипига, ЮЮ Петров // Искусственный интеллект -2005 -№4

6 Петров, Ю Ю Анализ основных направлений повышения эффективности генетических алгоритмов [Текст] / А Ф Чипига, Ю Ю Петров, А В Овчаренко//Искусственный интеллект -2007 -№4

7 Петров, Ю 10 Аргумент функции регуляции параметров генетического алгоритма [Текст] / И А Калмыков, А Ф Чипига, Ю Ю Петров II Сборник научных трудов СевКавГТУ, Серия «Естественнонаучная» - Ставрополь СевКавГТУ, 2008 -№4

8 Петров, 10 Ю Повышение вероятности нахождения глобального экстремума регуляцией генетических операторов в генетическом алгоритме [Текст] / И А Калмыков, А Ф Чипига, Ю Ю Петров // Сборник научных трудов СевКавГТУ, Серия «Естественнонаучная» -Ставрополь СевКавГТУ, 2008 -№4 Публикации в сборниках по итогам проведения международных и всероссийских научно-практических конференций

9 Петров, 10 Ю Оценка вероятности выживания шаблона при различных операторах кроссинговера в генетических алгоритмах [Текст] П Материалы IX региональной научно-технической конференции «Вузовская наука - СевероКавказскому региону», Т 1 - Ставрополь, 2005

10 Петров, ЮЮ Регуляция вероятное гей мутации и кроссинговера [Текст] // Инфотелекоммуникационные технологии в науке, производстве и образовании Первая международная научно-техническая конференция - Ставрополь СевКавГГУ, 2004

11 Петров, Ю Ю Вероятности выживания шаблона после выполнения различных операторов мутации в генетических алгоритмах [Текст] // Материалы IX региональной научно-технической конференции «Вузовская наука - СевероКавказскому региону», Т 1 - Ставрополь, 2005

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

алгоритма [Текст] / А Ф Чипига, Ю Ю Петров // Материалы VI Международной научно-практической конференции - Таганрог, 2004

13 Пиров, ЮЮ Локальная оптимизация в операторах мутации генетических алгоритмов [Текст] / А Ф Чпиша, Ю Ю Петров // Иифотелекоммуникациопные технологии в науке, производстве и образовании Первая международная научно-техническая конференция - Ставропочь СевКавГТУ, 2004

14 Петров, ЮЮ Оценка вероятности выживания особей при использовании различных операторов отбора [TeKci] / А Ф Чипига, 10 Ю Петров // Материалы IX региональной научно-технической конференции «Вузовская наука — Северо-Кавказскому региону» Т 1 - Ставрополь, 2005

15 Петров, Ю10 Оценка выбора размера популяции в просто« генетическом алгоритме [Текст] / А Ф Чипига, Ю Ю Петров // Материалы VII Международной научно-практической конференции - Таганрог, 2005

16 Петров, ЮЮ Применение генетического алгоритма с равномерным распределением потомков для решения задачи о назначениях [Текст] / А Ф Чипига, Ю Ю Петров // Инфотелекоммуникационные технологии в науке, производстве и образовании Вторая международная научно-техническая конференция - Ставрополь СевКавГТУ, 2006

Подписано в печать 29 05 2008 г Формат60x84 1/16 Уел печ л.- 1,5 Уч-изд.л -1,0 Бумага офсетная Печать офсетная Заказ №331 Тираж 100 экз ГОУ ВПО «Северо-Кавказский государственный технический университет» 355029, г Ставрополь, пр Кулакова, 2

Издательство Северо-Кавказского государственного технического университета Отпечатано в типографии СевКавГТУ

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МОДИФИКАЦИЙ ГЕНЕТИЧЕСКОГО АЛГОРИТМА И ИХ ПРИМЕНЕНИЕ В

ТЕХНИЧЕСКИХ СИСТЕМАХ.

1.1 Обзор и анализ генетических алгоритмов

1.2. Анализ основных направлений повышения эффективности генетических алгоритмов

1.3 Анализ применимости генетических алгоритмов и их модификаций в технических системах

1.4 Обзор существующих программных комплексов, реализующих оптимизацию с помощью генетических алгоритмов

ВЫВОДЫ К ПЕРВОЙ ГЛАВЕ.

ГЛАВА 2. РАЗРАБОТКА СПОСОБА УВЕЛИЧЕНИЯ ВЕРОЯТНОСТИ НАХОЖДЕНИЯ ГЛОБАЛЬНОГО ЭКСТРЕМУМА ГЕНЕТИЧЕСКИМ АЛГОРИТМОМ.

2.1 Построение и анализ математической модели генетического алгоритма

2.2 Разработка способа регуляции генетических операторов.

ВЫВОДЫ КО ВТОРОЙ ГЛАВЕ.

ГЛАВА 3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА С ПОВЫШЕНОЙ ВЕРОЯТНОСТЬЮ НАХОЖДЕНИЯ ГЛОБАЛЬНОГО ЭКСТРЕМУМА БЕЗ УВЕЛИЧЕНИЯ ВРЕМЕНИ СХОДИМОСТИ.

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

3.2 Генетический алгоритм с регуляцией вероятностей генетических операторов и с равномерным распределением потомков

3.3 Применение разработанного алгоритма в технических системах.ЮЗ

ВЫВОДЫ К ТРЕТЬЕЙ ГЛАВЕ.

ГЛАВА 4.ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ С РЕГУЛЯЦИЕЙ ВЕРОЯТНОСТЕЙ ГЕНЕТИЧЕСКИХ ОПЕРАТОРОВ И МУТАЦИЕЙ С РАВНОМЕРНЫМ

РАСПРЕДЕЛЕНИЕМ ПОТОМКОВ.

4.1 Методика тестирования генетических алгоритмов.

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

ВЫВОДЫ К ЧЕТВЕРТНОЙ ГЛАВЕ.

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

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

- нечёткая логика и теория множеств;

- нечеткие экспертные системы;

- системы приближенных вычислений;

- теория хаоса; фрактальный анализ;

- нелинейные динамические системы;

- гибридные системы (нейронечеткие, генетиконейронные, нечеткогенетические системы);

- нейронные сети;

- эволюционные вычисления.

Из них наиболее перспективным направлением являются эволюционные вычисления, которые подразделяются на эволюционные стратегии [117, 121], эволюционное программирование [88, 90, 91, 92], генетические алгоритмы [102, 103, 104] и генетическое программирование [109, 110]. В свою очередь, из эволюционных вычислений наибольшее распространение получили генетические алгоритмы, способные решать сложные оптимизационные задачи большой размерности.

Основные принципы, положенные в основе генетических алгоритмов, достаточно полно отражены в работах [77, 78, 93, 94, 100, 101, 102]. Среди них можно выделить следующие:

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

- простота схемы алгоритма, упрощающая адаптацию к конкретным особенностям технических систем;

- возможность интеграции с неэволюционными алгоритмами.

При этом, генетический алгоритм, в его базовой конфигурации, предложенной в работе [100], обладает недостаточно высокой вероятностью нахождения глобального экстремума [83, 98, 119], вследствии известной проблемы «застревания» в локальных оптимумах. Эта проблема в совокупности с высокими временными затратами на решение задач ограничивают применимость генетических алгоритмов в технических системах.

Например, задача оптимального распределения электроэнергии в условиях повышенной нагрузки. В случае выхода из строя трансформаторных подстанций, вследствие износа оборудования, повышается нагрузка на другие подстанции. Требуется быстро найти такой способ подключения потребителей электроэнергии к трансформаторным подстанциям, при котором нагрузка на устаревшее оборудование будет минимальной и без отключения потребителей. В случае задержки с решением этой задачи, или если ответ будет не оптимальным, произойдёт авария. Устаревшие трансформаторы будут не выдерживать долго повышенной нагрузки, и последовательно будут выходить из строя. При этом, стандартный генетический алгоритм находит оптимальное решение только в 75% случаях [70], а в остальных случаях решение близко к оптимальному.

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

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

- использование нестандартных архитектур генетического поиска;

- использование нестандартных или модифицированных генетических операторов;

- использование нестандартных способов кодирования генотипа.

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

Параллельные архитектуры являются адаптацией генетического алгоритма для параллельных вычислительных систем [4, 11, 28, 36, 37, 44, 97, 116]. Многофазовые архитектуры это использование различных вариаций генетического алгоритма на различных этапах эволюции и по сути является усложнением базового алгоритма, кратным числу используемых алгоритмов [59]. Многоуровневые [125] и поколенческие архитектуры [37], а так же макроэволюцию [36] целесообразно использовать совместно с параллельной архитектурой на высокопроизводительных параллельных вычислительных системах, в виду многократно возросшей сложности и высоких временных требований таких алгоритмов по сравнению с базовым генетических алгоритмом. Однако эти алгоритмы имеют высокое преимущество перед базовым, в области специфических задач. Интеграция с классическими методами оптимизации сужает круг решаемых задач, из-за дополнительных требований классических методов к поверхности целевой функции, таких как дифференцируемость, непрерывность и т.д. [32]

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

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

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

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

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

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

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

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

1. Разработка и анализ математической модели процессов сходимости к глобальному экстремуму целевой функции и выхода из локальных экстремумов.

2. Разработка способа регуляции вероятностей генетических операторов для увеличения вероятности нахождения глобального экстремума.

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

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

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

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

Работа состоит из четырех глав и приложений.

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

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

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

2. Анализ возможных схем интеграции генетических алгоритмов с другими методами оптимизации.

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

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

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

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

Для решения первой частной задачи введены следующие определения:

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

- экстремальный шаблон, это шаблон, множеству которого принадлежит генотип экстремума целевой функции;

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

На основе теоремы Холланда [100], описывающей динамику численности особей шаблона, с учётов введенных определений, в главе описана математическая модель повышения порядка доминирующего шаблона, с учётом особей, перешедших в рассматриваемый шаблон из других шаблонов, более низкого порядка, число которых значительно при высоких значениях вероятности мутации. Так же в предложенной модели учтен факт ограниченности популяции, чего нет в классической теории. При анализе модели были сделаны выводы об оптимальных значениях вероятностей генетических операторов на различных этапах эволюции. На начальном этапе, когда идет обработка случайного генетического материала, сгенерированного при инициализации, и далее, когда доминирующие шаблоны уже выделены, но имеют низкий порядок, оптимальными являются вероятность кроссинговера, равная 1, и вероятность мутации, равная 0. При достижении локального оптимума, когда доминирующий шаблон имеет высокий порядок, оптимальными являются максимальное значение вероятности мутации (для различных типов оператора лежит в пределах от 0,5 до 1) и вероятность кроссинговера в пределах от 0 до 0,5. Таким образом решена первая частная задача.

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

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

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

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

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

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

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

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

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

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

1. Определить множество тестируемых алгоритмов.

2. Определить множество тестовых задач.

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

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

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

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

6. Строится таблица тестируемых алгоритмов и их полученных характеристик.

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

Четвертая частная задача решена с помощью указанного программного комплекса. Получены сравнительные оценки надёжности нахождения глобального экстремума для различных модификаций генетических алгоритмов, в том числе и разработанных в диссертационной работе. В качестве тестовых выбран набор сложных многомерных (2, 5 и 10 мерных) функций Де Йонга, Растригина, Гриенвонка. Так же в набор тестовых функции включены задача распределения ресурсов и задача одномерной упаковки.

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

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

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

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

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

Практическая значимость работы состоит в следующем:

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

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

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

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

На защиту выносятся следующие основные положения:

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

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

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

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

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

Апробация работы. Основные результаты по теме диссертационного исследования докладывались на VI Международной научно-практической конференции «Информационная безопасность» (Таганрог, 2004), I Международной научно-технической конференции

Инфотелекоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2004), II Международной научно-технической конференции «Инфотелекоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2006), VII Международной научно-практической конференции «Информационная безопасность» (Таганрог, 2005), IX региональной научно-технической конференции «Вузовская наука — СевероКавказскому региону» (Ставрополь, 2005).

Публикации. По теме диссертации опубликовано 16 печатных трудов в том числе 6 статей в периодических научных изданиях; 10 публикаций в форме докладов на конференциях; 2 статьи опубликованы в журнале «Искусственный интеллект», входящем в перечень ВАК Украины; 1 статья опубликована в журнале «Системы управления и информационные технологии», входящем в перечень, рекомендованных ВАК РФ для публикации докторских диссертационных работ;

ВЫВОДЫ К ЧЕТВЕРТОЙ ГЛАВЕ

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. Александров Д.А., Алгоритм муравьиной колонии для задачи о минимальном покрытии//Х1 междунар. Байкальская школа-семинар «Методы оптимизации и их приложения», Труды тЗ, Иркутск, 1998.

2. Баркалов П.С., Буркова И.В., Глаголев А.В., Колпачев В.Н., Задачи распределения ресурсов в управлении проектами, М.: ИПУ РАН, 2002.

3. Барлит А.В., Нужнов Е.В., Решение задачи трехмерной упаковки с помощью параллельного генетического алгоритма//Перспективные информационные технологии и интеллектуальные системы, ТРТУ, 2002.

4. Батищев Д.И., Генетические алгоритмы решения экстремальных задач/Под ред. Львовича Я.Е., Учеб. пособие, Воронеж, 1995.

5. Батищев Д.И., Скидкина Л.Н., Трапезникова Н.В., Глобальная оптимизация с помощью эволюционно генетических алгоритмов//Мужвуз. сборник, Воронеж: ВГТУ, 1994.

6. Батищев Д.И., Гуляева П.А., Исаев C.A., Генетический алгоритм для решения задач невыпуклой оптимизации//Тез.докл. Междунар. конф. «Новые информационные технологии в науке, образовании и бизнесе», Гурзуф, 1997.

7. Бахвалов Л.А., Копелев МЛ., Генетические алгоритмы и планирование финансовой деятельности//Банковские технологии, №1, 1999.

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

9. Букатова И.Л., Обучающиеся, адаптивные и самоорганизующиеся эволюционные вычисления//журнал «ТВП», выпуск 5, 1996.

10. Бюргер Ю.А., Гнатюк В.Й., Литвиненко В.И., Ткачук А.А., Применение распределённого генетического алгоритма при решении задачи об упаковке в контейнеры//Перспективные информационные технологии и интеллектуальные системы, 2003.

11. Васин Е.А., Коваленко Д.С., Костенко В.А., Генетический алгоритм построения системы аксиом для разметки временных рядов//Труды VII Междунар. конф. «Дискретные модели в теории управляющих систем», М.: МАКС Пресс, 2006.

12. Васильев В.И., Ильясов Б.Г., Интеллектуальные системы управления с использованием генетических алгоритмов: Учебное пособие, Уфа: УГАТУ, 1999.

13. Воронкин Р.А., Математическое моделирование поиска глобальных экстремумов для решения задач адаптации на базе генетических алгоритмов: Дис. Канд. тех. наук, Ставрополь, 2004.

14. Вороновский Г.К., и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности, Х.ЮСНОВА, 1997.

15. Гладков В.А., Зинченко Л.А., Курейчик В.В., Курейчик В.М., Лебедев Б.К., Нужнов Е.В., Сорокин С.Н. Методы генетического поиска: Научное издание/Под редакцией В.М. Курейчика, Таганрог: Изд-во ТРТУ, 2002.

16. Гладков В.А., Курейчик В.М., Основные положения теории генетического поиска и её прикладные аспекты: Учебное пособие, Таганрог: из-во ТРТУ, 2001.

17. Гладков В.А., Полупанов А.А., Самоорганизующийся генетический алгоритм эффективный способ достижения оптимума//Тезисы докладов V Всероссийской научно-технической конф. студентов и аспирантов, Таганрог: из-во ТРТУ, 2000.

18. Гончаров Е. Н., Кочетов Ю. А., Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения//Дискретный анализ и исследование операций, Сер. 2. тб, № 1, 1999.

19. Горбачевская JI. Е., Кочетов Ю. А., Вероятностная эвристика для двухуровневой задачи размещения//Х1 междунар. Байкальская школа-семинар «Методы оптимизации и их приложения», Труды, т1, Иркутск, 1998.

20. Гудман Э.В., Вместо предисловия. Эволюционные вычисления и генетические алгоритмы//журнал «ТВП», выпуск 5, 1996.

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

22. Давиденко В.Н., Курейчик В.М., Генетический алгоритм для трассировки двухслойных каналов//Автоматизация проектирования, №1,1999.

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

24. Зуховицкий С.И., Авдеева Л.И., Линейное и выпуклое программирование, М.: Наука, 1967.

25. Ивахненко А.Г., Самообучающиеся системы распознавания и автоматического регулирования, К.: "Наукова думка", 1969

26. Костенко В.А., Возможности генетических алгоритмов для решения задач синтеза архитектур и планирования параллельных вычислений//Труды Третьей Междунар. научн. конф. «Дискретные модели в теории управляющих систем», М.:Диалог МГУ, 1998.

27. Костенко В.А., Трекин А.Г., Генетические алгоритмы решения смешанных задач целочисленной и комбинаторной оптимизации при синтезе архитектур ВС//Искусственный интеллект, №2, Донецк, 2000.

28. Костенко В.А., Трекин А.Г., Влияние способа задания целевой функции на качество работы генетического алгоритма//Искусственный интеллект, №2, Донецк, 2000.

29. Костенко В.А., Принципы построения генетических алгоритмов и их использование для решения задач оптимизации//Труды IV Междунар. конф. «Дискретные модели в теории управляющих систем», 2000.

30. Круглов В.В., Борисов В.В., Искусственные нейронные сети. Теория и практика, М.:Горячая линия Телеком, 2001.

31. Курейчик В.В., Эволюционные, синергетические и гомеостатические методы принятия решений: Монография, Таганрог: Изд-во ТРТУ, 2001.

32. Курейчик В.М., Генетические алгоритмы и их применение, Таганрог: Изд-во ТРТУ, 2002.

33. Курейчик В.М., Генетические алгоритмы, состояние, проблемы. Перспективы//Известия РАН Теории и системы управления, №1, 1999.

34. Курейчик В.М., Генетические алгоритмы. Обзор и состояние//Новости искусственного интеллекта, №3, 1998.

35. Курейчик В.М., Генеические алгоритмы, Таганрог: Изд-во ТРТУ, 1998.

36. Курейчик В.М., Генетические алгоритмы и их применение в САПР, Интеллектуальные САПР//Межведомственный тематический научный сборник, Таганрог, 1995.

37. Кутуков С.Е., Приложение генетических алгоритмов в управлении технологическими режимами нефтепродуктопроводов//Нефтегазовое дело, 2003.

38. Любченко В.Я., Павлюченко Д.А., Генетические алгоритмы оптимизации режимов электроэнергетичсеких систем//Междунар. конф. «Информационные системы и технологии», 2003.

39. Морозов Л.Н., Муравьев В.И., Генетический алгоритм для задачи коммивояжера — анализ применения и обучения решению//Материалы научно-практ. конф. «Актуальные проблемы экономики и современного промышленного менеджмента», Санкт-Петербург, 2004.

40. Мухлаева И.В., Кроссинговер для решения задачи двумерной упаковки и размещения прямоугольных элементов на плоскости/ТПерспективные информационные технологии и интеллектуальные системы, №2, ТРТУ, 2000.

41. Мухлаева И.В., Решение задачи одномерной упаковки в помощью параллельного генетического алгоритма/ЛТерспективные информационные технологии и интеллектуальные системы, №1, ТРТУ, 2000.

42. Норенков И.П., Генетические методы структурного синтеза проектных решений//Информационные технологии, №1, 1998.

43. Норенков И.П., Комбинированные и генетические алгоритмы составления расписаний в задачах проектирования//вестник МГТУ, сер. «Приборостроение», №2, 1995.

44. Нужнов Е.В. Барлит А.В., Трехмерная упаковка на основе эвристических процедур/ЛТерспективные информационные технологии и интеллектуальные системы, №1, 2002.

45. Петров Д.Ф., Генетика с основами селекции, М.: Высшая школа, 1971.

46. Петров Ю.Ю., Вероятности выживания шаблона после выполнения различных операторов мутации в генетических алгоритмах//материалы IX региональной научно-техн. конф.«Вузовская наука — СевероКавказскому региону», т1, Ставрополь, 2005.

47. Петров Ю.Ю., Оценка вероятности выживания шаблона при различных операторах кроссинговера в генетических алгоритмах//материалы IX региональной научно-технической конференции «Вузовская наука Северо-Кавказскому региону», т1, Ставрополь, 2005.

48. Петров Ю.Ю. Регуляция вероятностей мутации и кроссинговера//Инфотелекоммуникационные технологии в науке, производстве и образовании: Первая междунар. научно-техн. конф., Ставрополь: СевКавГТУ, 2004.

49. Петров Ю.Ю., Применение генетического алгоритма с регуляцией вероятностей генетических операторов при решении задачи упаковки в контейнер ы//сборник научн. трудов СевКавГТУ, серия «Естественнонаучная», №2, Ставрополь: СевКавГТУ, 2006.

50. Полупанов А.А., Адаптивная архитектура генетического поиска//Перспективные информационные технологии и интеллектуальные системы, 2003.

51. Полупанов А.А., Повышение эффективности генетического поиска//Тезисы докладов VI Всероссийской конференции студентов и аспирантов, Таганрог: ТРТУ, 2002.

52. Полупанов А.А., Управление процессом генетического поиска в оптимизационных задачах//Тезисы докладов XVII Международной научно-технической конф. «Интеллектуальные САПР», Геленджик, 2002.

53. Прилуцкий М.Х., Картомин А.Г., Потоковые алгоритмы распределения ресурсов в иерархических системах//Электронный журнал «Исследовано в России», http://zhurnal.ape.relarn.ru/articles/2003/039.pdf.

54. Растригин JI.A., Случайный поиск в эволюционных вычислениях, 1968.

55. Растригин JI.A., Случайный поиск — специфика, этапы истории и предрассудки//Вопросы кибернетики, Вып. 33,1978.

56. Скурихин А.Н., Генетические алгоритмы//Новости искусственного интеллекта, №4, 1995.

57. Цыпкин Я.З., Попков Ю.С., Адаптация и обучение в автоматических системах .-Москва:Наука, 1968.

58. Чипига А.Ф., Воронкин Р.А., Вероятностные оценки гипотез для генетического алгоритма с расщеплением признаков при сохранении фиксированной позиции шаблона в процессе мутации/УИскусственный интеллект, №4, 2003.

59. Чипига А.Ф., Петров Ю.Ю., Анализ обучаемости дискретных нейронных сетей с линейными и треугольными функциями активации при помощи генетического алгоритма//материалы VI Международной научно-практической конференции, Таганрог, 2004.

60. Чипига А.Ф., Петров Ю.Ю., Генетический алгоритм с равновероятным распределением потомков//Информационные технологии моделирования и управления, выпуск 18, Изд-во «Научная книга», 2004.

61. Чипига А.Ф., Петров Ю.Ю., Генетический алгоритм с регуляцией вероятностей кроссинговера и мутации//Межвузовский сборник научно-практических трудов, выпуск 2, Ставрополь: ЗАО «Пресса», 2004.

62. Чипига А.Ф., Петров Ю.Ю., Локальная оптимизация в операторах мутации генетических алгоритмов/УИнфотелекоммуникационные технологии в науке, производстве и образовании: Первая международная научно-техническая конференция, Ставрополь: СевКавГТУ, 2004.

63. Чипига А.Ф., Петров Ю.Ю., Математическая модель равновероятного распределения потомков в генетическом алгоритме//Системы управления и информационные технологии, №2, 2005.

64. Чипига А.Ф., Петров Ю.Ю., Модифицированная математическая модель простого генетического алгоритма//Искусственный интеллект, №4, 2005.

65. Чипига А.Ф., Петров Ю.Ю., Оценка вероятности выживания особей при использовании различных операторов отбора//материалы IX региональной научно-технической конференции «Вузовская наука — Северо-Кавказскому региону», т1, Ставрополь, 2005.

66. Чипига А.Ф., Петров Ю.Ю., Оценка выбора размера популяции в простом генетическом алгоритме//материалы VII Международной научно-практической конференции. Таганрог, 2005.

67. Aggarwal С. С., Orlin J. В., Tai R. P. Optimized crossover for maximum independent//set. Oper. Res., v45,1997.

68. Backer, J. E. Adaptive selection methods for genetic algorithms//Proc. of the 1st International Coference on Genetic Algorithm and Their Applications, NJ: Hilisdale, 1985.

69. 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.

70. Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems//J. Heuristics, v4, N4,1998.

71. Blickle Т., Thiele L., A Comparison of Selection Schemes used in Genetic Algorithms, (2nd Edition), 1995.

72. Boese K. D., Kahng А. В., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations.//Oper. Res. Lett., vl6, N2, 1994).77,78,79,80,81,82,8384,85