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

УДК 519.676

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

ШТУЦА ИЛЬЯ МИХАЙЛОВИЧ

МОДЕЛИ И АЛГОРИТМЫ ПРИНЯТИЯ РЕШЕНИЙ НА ОСНОВЕ ГЕНЕТИЧЕСКОГО ПОИСКА

0034488bU

Специальность 05.13.01 - Системный анализ, управление и обработка информации

(в науке и технике)

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

МОСКВА 2008

и опт®»

003448850

Работа выполнена в Московском Государственном Техническом Университете им. Н.Э. Баумана.

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

Научный консультант:

Официальные оппоненты: доктор технических наук, профессор

А.И. Нистюк

кандидат технических наук, доцент P.M. Гафаров

Ведущая организация: ОАО «Научно-исследовательский

институт управляющих машин и систем», г. Пермь

Защита диссертации состоится "06" ноября 2008 года в /2 часов на заседании диссертационного совета Д 212.065.06 в ГОУ ВПО ИжГТУ по адресу 426069, г. Ижевск, ул. Студенческая, 7.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО ИжГТУ.

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

Автореферат разослан "«У " сентября 2008 г.

доктор технических наук, профессор В.Н. Голубкин

кандидат технических наук, доцент A.M. Андреев

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

/ ¿г к.т.н., доцент L^f В.Н. Ся¡стерев

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

Актуальность темы

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

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

Особенный интерес исследователей привлек один из недетерминированных методов численной оптимизации, а именно «генетический алгоритм» (словосочетание «генетический алгоритм» является устойчивым, хотя за ним скрывается множество различных алгоритмов, иногда значительно отличающихся друг от друга) - в основе которого лежит механизм подобный закону естественного отбора (Holland, 1975)

Долгое время программные продукты, использующие генетический алгоритм, разрабатывались только в США и были запрещены к экспорту за пределы этого государства. В отечественной практике 70-х годов в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идеи бионического поведения особей Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Наличие признаков эволюционного алгоритма наблюдается и в Методе Группового Учета Аргументов (МГУА) украинского кибернетика А.Г. Ивахненко.

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

Цели и основные задачи работы

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

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

1. Анализ существующих модификаций ГА, идей и принципов лежащих в их реализации;

2. Построение обобщающей модели, позволяющей математически формализовать ГА, выдвигать гипотезы по его свойствам и

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

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

4. Выполнение численных экспериментов по исследованию свойств, влияния настраиваемых параметров и временной сложности ГА, анализ результатов;

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

Объектом исследования является генетический алгоритм численной оптимизации.

Предметом исследования является обобщающая модель, характеристики и применимость алгоритма, влияние настраиваемых параметров, временная сложность.

Методика исследований. При решении поставленных задач в работе использованы теории численных методов оптимизации, графов, матриц, вероятностей и математической статистики. Были разработаны алгоритмы, инструментарий и методика проведения численных экспериментов для исследования свойств ГА. Эксперименты выполнены на тестовых функциях, рекомендованных в литературе, посвященной методам численного анализа и генетическим алгоритмам; по данным для задачи коммивояжера (TSP) из библиотеки Университета Heidelberg (Германия); реальным экспериментальным данным, собранным в отечественной промышленности. Для оценки качества работы предложенных методов было проведено сравнение ГА с традиционными методами экстраполирования (регрессионный анализ на основе метода наименьших квадратов).

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

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

2. Предложены методы повышения эффективности ГА, связанные с нелинейным уменьшением максимального значения приращения оператора мутации и алгоритмами кластеризации;

3. Экспериментально получены оценки временной сложности ГА;

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

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

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

Практическая ценность и реализация результатов:

1. Разработаны высокоэффективные алгоритмы, реализующие операторы ГА;

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

3. Разработан программный пакет для решения оптимизационных научных и прикладных задач;

4. Реализована инженерная методика решения прикладных оптимизационных задач (на примере производства труб из сплава Э110 на ОАО «ЧМЗ» для нуяад атомной промышлённости РФ).

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

Результаты полученные в диссертационной работе использованы в действующем производстве ОАО «ЧМЗ» (г.Глазов), что подтверждено Актом 981-04/2415 от 25 04.07 г., а также в работе Центра технологического прогнозирования при ГТУ МИСиС для выполнения научных разработок и учебного курса студентов и аспирантов, что подтверждено «Актом внедрения» от 02 09 2008 г.

На защиту выносится:

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

2. Алгоритмы, реализующие операторы ГА, и программный пакет для решения научных и прикладных задач на их основе;

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

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

Апробация работы. Содержание отдельных разделов и диссертации в целом было доложено на: Межвузовской научной конференции «Информатика и системы управления в XXI веке» 2003 т. (Москва); Межвузовской научно-технической конференции аспирантов и студентов «Современные информационные технологии» 2004 г. (Москва);

Международной конференции «Теоретические аспекты использования сорбционных и хроматографических процессов в металлургии и химической технологии» 2006 г. (Екатеринбург); VIII Международной научно-технической конференции «Информационно-вычислительные технологии и их приложения» 2008 г. (Пенза); научных семинарах ИжГТУ 2007-2008 гг. (Ижевск).

Публикации. Основные результаты работы опубликованы в 6 печатных работах, из них 3 опубликованы в изданиях, рекомендуемых ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложений. Общий объем диссертации 203 страницы, включая рисунки, список литературы и приложения. Библиография содержит 110 наименований, из них 30 иностранных (на английском языке).

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

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

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

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

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

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

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

По источникам из литературы построена классификация известных модификаций генетических алгоритмов - классифицированы стратегии отбора, скрещивания, мутации, замещения, типа хромосом и прочих модификаций ГА. Среди стратегий отбора выделены пропорциональный отбор (рулетка, Goldberg, 1989), турнирный отбор (Brindle, 1981; Goldberg, Deb, 1991), элитизм (De Jong, 1975), концепция островов (метод миграции, Levine, 1994), панмиксия, селективный отбор (Goldberg, 1989), инбридинг и оутбридинг. Среди стратегий скрещивания выделены кроссовер одноточечный, двухточечный, многоточечный, равномерный, а также дифференциальное скрещивание. В стратегиях мутации различают случайную одноэлементную, абсолютную, комбинаторную мутации. В стратегиях замещения можно выявить неявное, N-наихудщих (селективное, Goldberg, 1989), обратно пропорциональное. По типу хромосом (кодированию варианта решения) различают битовые строки, вектора целых чисел, вектора вещественных чисел, комбинаторные строки (с дополнительными ограничениями). Среди модификаций ГА известны метод прерывистого равновесия, операторы переупорядочивания (инверсии, Goldber, Bridges, Bisley). В ходе диссертационной работы были предложены еще ряд модификаций ГА - нелинейное уменьшение максимального значения приращения оператора мутации, операторы скрещивания и мутации для решения задачи коммивояжера, штрафные функции для решения задач условной оптимизации, многокритериальная оптимизация на основе ГА. В инструментарий исследования также включен алгоритм финальной кластеризации найденных решений.

Известна теорема схем (scheme theorem, Holland):

m(H, t +1) & m(H, О X X (1 - Pcj~) x (1 - Pm)'(H), (1)

где

т{Н,0 - кол-во особей в популяции,

составляющих схему Н в поколении и С!(Н) - средняя приспособленность особей схемы Н; ()ср - средняя приспособленность всех особей популяции; Рс - вероятность кроссовера; Рт - вероятность мутации; <т(Н) - определенная длина схемы Н

(расстояние между крайними определенными генами); о(Н) - порядок схемы Н (количество определенных генов); / - длина схемы.

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

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

В Приложение 1 вынесено рассмотрение существующих пакетов оптимизации, в основе работы которых лежат генетические алгоритмы.

Анализ позволяет выделить следующие основополагающие принципы

ГА:

■ одновременная работа с множеством решений (популяцией);

■ соответствие итерационной схеме алгоритма - отбор, скрещивание, мутация, замещение;

■ оператор отбора - наиболее приспособленные особи должны выбираться чаще;

■ оператор скрещивания - оператор работает с несколькими особями, на основе которых создает дочерние, несущие признаки родителей, '

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

■ оператор замещения - наименее приспособленные особи должны чаще замещаться более приспособленными.

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

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

В Главе 2 «Теоретическое исследование ГА» разработка обобщающей модели проведена с учетом ряда допущений, а именно: постоянство популяции; в отборе, скрещивании и замещении участвуют две особи; не рассматриваются стратегии отбора с элитизмом и миграцией.

Для дальнейшей разработки обобщающей модели ГА введем случайную величину w, распределенную по равномерному закону в интервале от 0 (включительно) до 1 (невключительно).

Пусть ставится задача максимизации (минимизации) целевой функции: Q(x) -> max (min). (2)

В случае решения однокритериальной задачи V^.ßW^ßWeR1; (3)

оператор отбора S (selection) выполняет отображение на основе значения целевой функции Q:

S,:R,-»R,> (4)

S(6(x))eR'.

Цель оператора отбора в поиске на каждом шаге (поколении) t алгоритма индексов двух родительских особей исходя из неравенств

1,,-1

и

^ I J J < ^(х,,);

<-i *-i i.i

•• I <£s(xkJ).

Лв1

Свойства:

»i.

(5)

ß(x)max,Vi,7 ß(x„)£ß(x„) =>S(x,,)<.S(x.(); ß(x) -> min, Vi, у ß(x„) < ß(x,,)=> S(xJ к S(x„).

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

S(Q(x»

S(Q(x»

S(Q(x))

S(Q(x»

А) Б) В)

Рисунок 1. Виды функции отбора S

а) £"((2(х)) = 0 - данный вид функции соответствует поведению классического пропорционального отбора (рис.1, а);

б) Х"(2(х))<0 - особи со средней приспособленностью имеют практически равную вероятность к отбору по сравнению с более приспособленными. Такой вид отбора будет замедлять эволюционное улучшение средней приспособленности популяции в пользу более полного исследования пространства поиска и может быть рекомендован для оптимизации сложных, с множеством локальных экстремумов, целевых функций (рис. 1, б);

в) 5"(бОО)>0 - особи со средней приспособленностью имеют значительно более низкую вероятность к отбору по сравнению с более приспособленными. Такой вид отбора будет ускорять эволюционное улучшение средней приспособленности популяции в пользу менее полного исследования пространства поиска и может быть рекомендован для оптимизации простых целевых функций (рис 1, в);

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

Таблица 1

Оператор отбора

'СтрЩЩотбдрЩ1

Пропорциональная 5(х) = <2(х) S(x) = тах(б(х)) + тю(2(х)) ~б(х)

Квадратично-пропорциональная 5(х) = б2(х) 5(х) = тах(0(х))2 + тт(2(х))2 - @(х)2

Селективная адЛ0'^6 ие(х)<б

Панмиксия 5(х)=1

Турнирный ¿■(х) = 1

Инбридинг Я,(х.) =-1- 2 ' ртш*,)) (х,) = тах(б(х))+тт(е(х)) - 0(х,) А(х,) =-^-

Оутбридинг $,(*,)=е(х,) $,(*>>=/*е(*,).е(1У)) 51(х,) = тах(2(х))+тт(е(х))-е(х,) 5!(ху) = р(е(х,),е(ху))

Ранговый

Аналогично оператору отбора (5) можно определить оператор замещения:

Г,., ■ Z ^t ,,) < £ Д(х,,);

*.i »-i

Свойства:

Vfc,fR(xt,)>0;/?(xt,)6K';

g(x)->min,V/,y 2(х(,)<2(х;,)=>Я(х(,)<Л(х;,).

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

Для построения обобщающей модели ГА введем матричную запись оператора скрещивания:

C,(x,/,xv) = x>i/ (Т) + х,.(Е-Т);

ra, 0 0

0 a 0 0

0 0 a 0

,0 0 0

U

Таблица 2

Оператор скрещивания

Стратегу я

Схемы родительских и

Матричная фзййс^

-(t'i ' 'iSfi'rfj' '-¿¡Л

g 1>5|

Ч J л

о R

т=

о.

О)

CD

О О О

о о.

■ St

х I

m <и

4 5

и с

1 □ С

1 1 L

т=

0,1* j

1.' = J,i<k,

',' = J,t>k2

0,i = j, i, <= i <= ij

S5 Se

ie

T =

0,i* j

1, i = 7,/mod2 = 0 0,i = y,imod2?t0

§ i ^

в as

as <u

a. 2

: с

т=

«1/

[о."4 j

,a,j = h,i = j,w<ll2 [0,» = 1/2

В общем случае, действие оператора мутации можно характеризовать векторной функцией 0(и>,*„,/):

М(1,,) = х(, + 0(и'>х,1,/).

Свойства:

(8)

0(и>, х,,, I) = 0 - нежадный оператор;

, /) * 0 - жадный оператор.

Исходя из оценки сокращения эффективного пространства поиска в процессе эволюции в Главе сделано предложение о перерасчете максимального значения приращения оператора мутации по формуле:

й. - с!« / 2=—77=;

1 0

(9)

В Главе 2 исследовано решение задач условной оптимизации с использованием функции штрафа (целевая функция Р представлена разностью исходной функции приспособленности ^ и функции штрафа Р) Р'(1о)

Р Я!. -,£„) = О .....£„)-Р (£,,£2-»>£„)-

Описываемый подход предполагает сведение системы ограничений С^(х),/ = й (11)

к одному обобщенному ограничению Сг'ОО с помощью преобразования

а'(х) = тах{С/Дх)} = тах|тах{0,(х),()}}, ] = 1 ,т;

адх)< 0 У/' = Гт=>О'(х) = 0; (12)

Зу=Гм: 0/х)>0 =>а'(х)> 0.

На базе обобщенного ограничения предлагается использовать следующие штрафные функции ГО, еслиа'(х) = 0

(А*а (х), еслиС/(х)>0,

л«- °-есл.ис:'(х)=°. (М)

(х/, еслиС/ (х)>0, |0,есл„а-(х) = 0 {(к-0° *Сг (х)", если С/(х)>0, где к,а,р - константы, I - номер поколения.

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

12

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

Пусть

и - количество критериев оптимизации,

И- размер популяции (множества одновременно рассматриваемых решений),

(2\ • значение целевой функции решения (особи)} по критерию ¡,

тогда для каждой особи ] можно получить вероятность ее выбора по критерию \ в случае его максимизации (пропорциональный отбор):

= (16)

Её!

1

В случае минимизации по критерию \ вероятность отбора определяется соотношением:

р!=^ (17)

Вероятность отбора особи по всем критериям одновременно равна произведению вероятностей отбора по каждому из критериев (вероятность одновременного наступления независимых событий)

р'-ПР! (18)

1=1

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

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

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

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

Проведен выбор программного средства для реализации инструментария реализации ГА - Visual Basic for Application на базе Microsoft Excel. Выбор определился исходя из распространенности пакета среди потенциальных пользователей, значительного объема накопленных для анализа данных в формате Excel, возможности интеграции с СУБД (Oracle, SQL Server, DB2, Access) на основе протокола ODBC.

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

Для реализации функции отбора (вычисления индексов исходя из приведенного неравенства) введем одномерный массив R, вычисляемый

I

по формуле Я, = £ S(xkl). ¡•¡.и

Вычисление следует проводить по итерационной процедуре.

R, =S(xu),

(19)

В этом случае задача построения массива R имеет вычислительную сложность O(N) = N.

Тогда задача поиска особей для скрещивания сводится к.

JJ " ' (20)

Свойства :

VM S(x^) ;> Q;S(xkl)e R' Vi : R,_, iR,.

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

0(N)=log,(tf+l). (21)

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

7>aW+61og2(W+l) + tf. (22)

В случае использования жадных алгоритмов зависимость получается другой:

T,*>aN + b\og1(.N + l) + cl\ (23)

где а,Ь,с - весовые коэффициенты.

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

В Главе 4 «Проведение численного эксперимента» разработана и описана технология проведения численного эксперимента, которая применялась для исследования свойств ГА. Для исследования ГА был составлен альбом тестовых функций с учетом факторов, представляющих сложность при решении задач оптимизации, мультимодапьность (multi-modality), обманчивость (deception), изоляция (isolation), шум (collateral noises). Основой для синтеза тестов стали функции, описанные в литературе (Растригина, Griewank) По результатам численных экспериментов сделан ряд выводов, основные из которых:

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

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

1) задача быстрой локализации одного оптимального значения,

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

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

■ ГА обладают уникальным свойством продолжать оптимизацию после переопределения ЦФ без останова вычислительного процесса - это свойство может быт£> применено в системах реального времени;

■ алгоритм имеет низкую вычислительную сложность, что позволяет его применять для оптимизации одновременно нескольких десятков и даже сотен изменяемых параметров;

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

В Главе 4 рассмотрен классический пример NP-полной комбинаторной задачи - задачи коммивояжера. Для решения данной задачи разработаны специальные алгоритмы операторов скрещивания и мутации, которые удовлетворяют ограничениям, накладываемым на представление хромосом (гамильтонов цикл). Оператор мутации представляет собой следующим алгоритм - хромосома разрезается в двух местах - средняя часть в дочерней хромосоме переписывается в обратном порядке. Данное преобразование удаляем из маршрута два ребра, заменяя их новыми. В тексте работы приводится доказательство теоремы о том, что такое преобразование является минимальным позволяющим из одного гамильтонова цикла получить другой. Экспериментальные данные для решения задачи коммивояжера взяты из электронной библиотеки TSPLIB. Глобально-оптимальные маршруты в данной библиотеке получены путем вычислений в кластере высокопроизводительных ЭВМ в Университете Хедельберг (Heidelberg, Германия).

В случае решения задачи коммивояжера размерности 29 (общее количество вариантов полного перебора составляет 1,52е+29) ГА нашел решение, полностью совпадающее с глобальным в 30% случаев в среднем за 18 секунд на современном персональном компьютере. Во всех остальных случаях ГА предложил решения, незначительно уступающие глобальному оптимуму Дальнейшее исследование вычислительной сложности ГА (вычисления прекращались при достижении порогового значения среднеквадратичного отклонения, те. стабилизации популяции) показало, что стабилизация популяции происходит за время 0(LA2) с коэффициентом детерминации 0.98.

В Главе 5 «Технологическое прогнозирование производства труб из сплава Э110» описано применение разработанного инструментария для решения задачи прогнозирования показателей качества в зависимости от технологических параметров производства твэльного проката из цирконий-ниобиевых сплавов на ОАО «Чепецкий механический завод» (г. Глазов).

Исследовались статистические данные, собранные экспериментально при производстве твэльного проката. Объем выборки составляет 96 партий по 100 труб в каждой, исходными данными являлись: подача трубных заготовок в очаг деформации М (3 стадии), мм; количество двойных ходов клети N (3 стадии), 1/мин; угол поворота трубных заготовок перед очагом деформации W (3 стадии), град; сопротивление металла пластическому деформированию S (3 стадии), МПа. Итого: 12 показателей (4*3), массив данных 1152 (12*96). Показателями качества являлись' уровень брака (геометрические показатели, микронесплошности); механические свойства (временное сопротивление разрыву, предел текучести); эксплуатационные характеристики (коэф. ориентации гидридов). Всего 23 показателя. Из них для прогнозирования по согласованию выбраны 3: минимальное для партии труб временное сопротивления металла в испытаниях образцов на растяжение в поперечном направлении при температуре 20°С, МПа); максимальный для партии труб предел текучести металла в испытаниях образцов на растяжение в поперечном направлении при температуре

380°С, МПа); минимальный для партии труб коэффициент ориентации гидридов.

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

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

Этап 1. Перевод абсолютных значений факторов в относительные в интервале [1 ;2];

Этап 2. Дополнение факторов их сочетаниями в различных формах (относительной, статистической, взвешенно-суммируемой, разностной);

Этап 3 На основе корреляционной матрицы определение факторов прямого значимого влияния и отсев закоррелированных с ними факторов, проявивших косвенное (опосредованное) воздействие;

Этап 4. Прогнозирование с использованием регрессионного анализа на основе метода наименьших квадратов. Аппроксимирующая функция -полином второй степени Для п=6 - 22 весовых коэффициентов;

Этап 5. Прогнозирование с использованием генетического алгоритма. Аппроксимирующая функция - дробно-рациональная функция, в которой числитель и знаменатель являются полиномами второй степени. Для п=6 -44 весовых коэффициентов;

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

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

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

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

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

описанием существующих модификаций, что позволяет строить ГА на

основе сочетаний различных стратегий из классификатора;

2. Построена обобщающая модель генетического алгоритма позволяющая математически формализовать ГА;

3. Предложен метод повышения эффективности ГА, связанный с нелинейным уменьшением максимального значения приращения оператора мутации и алгоритмом кластеризации;

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

5. Предложен алгоритм решения задач многокритериальной оптимизации на основе ГА и принципа справедливого компромисса;

6. Разработан пакет программ для решения оптимизационных научных и прикладных задач на основе ГА и методика проведения численных экспериментов;

7. Определено влияние настраиваемых параметров метода, позволяющее выделить оптимальные сочетания для решения различных классов задач;

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

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

СПИСОК ОСНОВНЫХ РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ

ДИССЕРТАЦИИ

1. Штуца И.М. Подход к оптимизации (генетические алгоритмы)

// Информатика и системы управления в XXI веке. Труды молодых ученых, аспирантов и студентов. - М„ 2003. - №1. - С 369-375

2. Штуца И.М. Применение генетических алгоритмов к решению задачи вычислительно сложных задач хроматографии цветных и редких металлов // Теоретические аспекты использования сорбционных и хроматографических процессов в металлургии и химической технологии. Сборник тезисов докладов международной конференции.

- Екатеринбург, 2006. - С.56-57.

3. Бринза В.В., Сафонов В.Н., Штуца И.М. Технологическое прогнозирование как средство, выявления дополнительных конкурентных преимуществ производства // Металлург. Научно-технический и производственный журнал. - М., 2007. - №2. - С.31-36.

4. Андреев А.М., Штуца И.М. Нелинейный оператор мутации генетического алгоритма // Вестник ИжГТУ. - Ижевск: Изд-во ИжГТУ, 2008,-№4.-С. 18-22.

5. Андреев А.М., Штуца И.М. Исследование вычислительной (временной) сложности генетического алгоритма на примере задачи коммивояжера // Вестник ИжГТУ. - Ижевск: Изд-во ИжГТУ, 2008. - №4.

- С. 22-26

Андреев A.M., Штуца И.М. Подход к многокритериальной оптимизации на основе генетического алгоритма // Информационно-вычислительные технологии и их приложения. Сборник тезисов докладов международной научно-технической конференции. - Пенза, 2008. - С. 10-13.

Подписано в печать 23.09.08. Формат 60x84/16. Бумага офсетная. Усл.печл 1,0 Тираж 100 экз.'Заказ 284 Отпечатано в типографии Издательства ИжГТУ г. Ижевск, ул. Студенческая, 7

СПИСОК ТЕРМИНОВ И СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

Постановка задачи.9

ГЛАВА 1. Анализ генетических алгоритмов в контексте методов функциональной оптимизации.10

1.1. Методы функциональной оптимизации.10

1.1.1. Детерминированные методы.10

1.1.2. Вероятностные методы.12

1.2. Введение в генетические алгоритмы.12

1.2.1. История появления и развития ГА.12

1.2.2. Описание генетического алгоритма.16

1.2.3. Классификация ГА.18

1.2.4. Символьная модель ГА.25

1.2.5. Работа классического ГА.28

1.2.6. Теорема схем (шим).30

1.3. Применимость ГА.34

1.4. Анализ идеи и принципов операторов ГА.35

1.5. Выводы.37

ГЛАВА 2. Теоретическое исследование ГА.39

2.1. Обобщенная модель ГА.39

2.2. Модели операторов ГА.39

2.2.1. Операторы отбора и замещения.•.39

2.2.2. Оператор скрещивания.42

2.2.3. Оператор мутации.44

2.3. Предложение по модификации оператора мутации.45

2.4. Условная оптимизация на основе ГА.48

2.5. Многокритериальная оптимизация на основе ГА.50

2.6. Выводы.57

ГЛАВА 3. Разработка инструментария для исследования свойств ГА.59

3.1. Разработка функциональной схемы.59

3.2. Выбор программного средства.61

3.3. Разработка структур данных и оценка емкостной сложности алгоритма. 63

3.4. Разработка методов задания целевой функции.67

3.5. Разработка алгоритма оптимизации, оценка вычислительной сложности .69

3.6. Разработка алгоритма кластеризации.72

3.7. Оценка быстродействия.74

3.8. Системы поддержки принятия решений и ГА.77

3.9. Выводы.81

ГЛАВА 4. Проведение численного эксперимента.82

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

4.2. Планирование эксперимента.84

4.3. Исследование направлений оптимизации.86

4.3.1. Оценка поиска на максимум ЦФ.86

4.3.2. Оценка поиска на минимум ЦФ.89

4.3.3. Оценка приведения ЦФ к заданному значению.92

4.4. Оценка целочисленной оптимизации.94

4.5. Исследование условной оптимизации.95

4.6. Исследование настраиваемых параметров ГА.97

4.6.1. Исследование различных стратегий отбора.97

4.6.2. Оценка влияния вероятности скрещивания.100

4.6.3. Оценка влияния вероятности мутации.103

4.7. Исследование эволюционирования при смене ЦФ.106

4.8. Исследование оптимизации разрывных функций.108

4.9. Исследование работы ГА с модифицированным оператором мутации. 110

4.10. Многокритериальная оптимизация.113

4.11. Решение задачи коммивояжера.115

4.11.1. Постановка задачи.115

4.11.2. Кодирование хромосом.116

4.11.3. Разработка TSP-генетических операторов.116

4.11.4. Результаты решения задач большой размерности.120

4.11.5. Экспериментальная оценка вычислительной сложности алгоритма .128

4.12. Выводы.132

ГЛАВА 5. Технологическое прогнозирование производства труб из сплава Э110 .134

5.1. Актуальность задачи.134

5.2. Пассивный эксперимент.135

5.3. Сравнительный анализ регрессионного анализа на основе метода наименьших квадратов и ГА.136

5.4. Производство труб из сплава Э110 в России.138

5.5. Исходные данные и прогнозные модели.141

5.6. Анализ результатов.143

5.7. Выводы.152

ВЫВОДЫ.153

Выводы по диссертации.153

Основные результаты.155

Направления дальнейшей работы.157

СПИСОК ИСТОЧНИКОВ.158

ПРИЛОЖЕНИЯ.168

ПРИЛОЖЕНИЕ 1. Существующие пакеты оптимизации на основе ГА.168

Evolver (Palisade Corp.).168

GeneHunter (WARD Systems Group).173

ПРИЛОЖЕНИЕ 2. Тестовые функции для исследования оптимизации на основе ГА.176

ПРИЛОЖЕНИЕ 3. Данные для решения задачи коммивояжера.183

ПРИЛОЖЕНИЕ 4. Руководство пользователя.184

ПРИЛОЖЕНИЕ 5. Исходные данные по решению задачи технологического прогнозирования производства труб из сплава Э110.200

ПРИЛОЖЕНИЕ 6. Акт № 981-04/2415 от 25.04.2007. Использование результатов диссертации на ОАО ЧМЗ.203

ПРИЛОЖЕНИЕ 7. Акт внедрения результатов диссертации в МИСиС.204

СПИСОК ТЕРМИНОВ И СОКРАЩЕНИЙ

Аллель — значение гена, вариант свойства

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

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

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

Особь — вариант решения поставленной задачи (точка в пространстве поиска), в контексте ГА представляется хромосомой (хромосомами) с закодированным множеством параметров задачи

Отбор — оператор ГА, который выделяет наиболее приспособленных особей из популяции для выполнения операторов скрещивания и мутации, а наименее приспособленных — для удаления из популяции

Поколение - стадия развития популяции, которая характеризуется степенью обновления ее членов

Популяция — конечное множество особей

Фенотип — декодированная структура генотипа особи, т.е. множество параметров задачи (решение, точка в пространстве поиска) Хромосома — упорядоченная последовательность генов Эволюция - процесс, который в ходе отбора позволяет улучшать приспособленность популяции в целом от поколения к поколению

ВВЕДЕНИЕ

Актуальность проблемы

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

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

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

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

Результаты применения недетерминированных алгоритмов в решении некоторых задач оказываются лучше, чем детерминированных. Но в области недетерминированных алгоритмов остается большой круг нерешенных проблем — отсутствует строгая терминология, недоработаны модели, классификации, не существует строгих доказательств сходимости, оценок вычислительной сложности. Это неудивительно, т.к. в самой фразе «недетерминированный алгоритм» заложено противоречие - если обратиться к классической теории вычислительной техники, утверждающей что «алгоритм -это точный набор инструкций, описывающих последовательность действий некоторого исполнителя для достижения определенного результата». Основными признаками алгоритма являются: детерминированность — определённость, в каждый момент времени следующий шаг работы исполнителя однозначно определяется состоянием системы; понятность — алгоритм должен включать только те команды, которые исполнителю доступны и входят в его систему команд; конечность — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.

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

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

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

Постановка задачи

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

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

Анализ существующих модификаций ГА, идей и принципов лежащих в их реализации;

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

Разработка инструментария и методики проведения численных экспериментов по исследованию свойств ГА;

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

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

Основные результаты

В процессе исследований, выполненных в рамках диссертационной работы, получены следующие основные результаты: выполнена классификация генетических алгоритмов с подробным описанием существующих модификаций, что позволяет строить ГА на основе сочетаний различных стратегий из классификатора; проанализированы идеи и принципы операторов ГА на основе которых построена обобщающая модель генетического алгоритма позволяющая математически формализовать ГА; на основе геометрических интерпретации действия операторов скрещивания и мутации, позволяющих более глубоко понять принципы функционирования генетического алгоритма, выявлена аналогия между генетическим алгоритмом и методом ветвей и границ, позволяющая прогнозировать основные характеристики ГА; предложен метод повышения эффективности ГА, связанный с нелинейным уменьшением максимального значения приращения оператора мутации и алгоритмом кластеризации; предложен подход к решению задач условной оптимизации с использованием штрафных функций; предложен подход к решению задачи многокритериальной оптимизации на основе ГА и принципа справедливого компромисса; разработан пакет для решения оптимизационных научных и прикладных задач на основе ГА; определено влияние настраиваемых параметров метода, позволяющее выделить оптимальные сочетания для решения различных классов задач ; проведено решение NP-полной задачи большой размерности (на примере задачи коммивояжера), подтвердившей возможность нахождения глобального оптимума и получена экспериментальная оценка вычислительной сложности генетического алгоритма, которая оказалась квадратичной; выполнено технологическое (в зависимости от изменения многочисленных технологических факторов) прогнозирование эксплуатационных свойств труб из сплава Э110 произведенных на предприятии отечественной промышленности на основе сравнительного анализа аппроксимации на основе метода наименьших квадратов и ГА. Достоверность прогноза подтверждена улучшением и стабилизацией свойств (предела прочности, предела текучести, относительного удлинения, коэффициента ориентации гидридов, коэффициента анизотропии) циркониевых труб, выпущенных в течение 4 кв. 2006 — 1 кв. 2007 г.г.

Направления дальнейшей работы

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

Очень важной работой является продолжение работы по созданию строгой математической модели ГА, позволяющей доказать сходимость алгоритма. К сожалению, на текущий момент такой модели создать не удалось, хотя существует ряд работ математической направленности посвященной этой теме. [84]

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

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

1. Базы данных. Интеллектуальная обработка информации/ В.В. Корнеев, А.Ф. Гареев, B.C. Васюткин, В.В. Райх. М.: Нолидж, 2001. - 496 с.

2. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. — Воронеж: Воронеж, 1995. — 64 с.

3. Батищев ДИ. Методы оптимального проектирования.—М.: Радио и связь, 1984.-248 с.

4. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. — Воронеж: Воронеж, 1997. — 416 с.

5. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. — М.: БИНОМ, 2002. 632 с.

6. Брандт 3. Статистические методы анализа наблюдений — М.: Мир, 1975. — 312 с.

7. Букатова И.Л. Эволюционное моделирование и его приложения .- М.: Наука, 1979,- 231 с.

8. Васильев Ф.П. Методы оптимизации. — М.: Факториал Пресс, 2002. — 824с.

9. Гарнаев Ю.А. Самоучитель YBA. Технология создания приложений. — М.: BHV, 1999.-512 с.

10. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности/ Г.К. Вороновскин, К.В. Махотило, С.Н. Петрашев, С.А. Сергеев. — Харьков: Основа, 1997. — 112 с.

11. Гладков А.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. — М.: Физматлит, 2006. 320 с.

12. Грешплов А.А. Математические методы принятие решений. — М.:МГТУ им. Н.Э. Баумана, 2006. — 584 с.

13. Дасгупта В. Искусственные имунпые системы и их применение. — М.: Физматлит, 2006. 344 с.

14. Джопс Т. Программирование искусственного интеллекта в приложениях. М.: ДМК Пресс, 2004. - 312 с.15