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

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

ГЕНЕРАЛОВ Константин Александрович

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И ПРОГРАММНЫЕ СРЕДСТВА РЕАЛИЗАЦИИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ НА ОСНОВЕ ТЕОРИИ НУМЕРАЦИИ

Специальности: 05.13.17 - «Теоретические основы информатики»; 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

2 6 НОЯ 2009

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

ПЕНЗА 2009

003484335

Работа выполнена на кафедре «Математическое обеспечение и применение ЭВМ» в ГОУ ВПО «Пензенский государственный университет».

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

Шашков Борис Дмитриевич.

Научный консультант - кандидат технических наук, доцент

Кольчугина Елена Анатольевна.

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

Горбаченко Владимир Иванович;

кандидат технических наук, доцент Пащенко Дмитрий Владимирович.

Ведущая организация - ОАО «НПП "Рубин"» (г. Пенза).

Защита состоится « » ре/саЯря 2009 г., в ТУ часов, на заседании диссертационного совета Д 212.186.01 в ГОУ ВПО «Пензенский государственный университет» по адресу: 440026, г. Пенза, ул. Красная, 40, корпус 1.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Пензенский государственный университет». Автореферат размещен на сайте www.pnzgu.ru

Автореферат разослан « 19 » 2009 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор ' Гурии Е. И.

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

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

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

В последнее время интерес к использованию ГА возрастает. Об этом свидетельствует растущий объём публикаций. Исследованиям в области ГА посвящены работы Д. Гольдберга, Д. Холланда, Д. Коза, Д. И. Батищева, В. М. Курейчика, В. В. Курейчика и других авторов. Большинство работ посвящены следующим вопросам:

- сходимость ГА;

- частные варианты реализации ГА для конкретных задач;

- параллельные реализации ГА;

- особенности представления хромосом и генов.

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

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

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

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

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

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

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

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

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

3. Разработка обобщённой алгебраической модели генетических алгоритмов.

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

5. Создание инструментального ПО для реализации языка программирования.

6. Экспериментальное подтверждение эффективности предложенного инструментария с помощью методик количественной и качественной оценки ПО.

Методы исследования основаны на теории множеств, теории нумераций, теории графов, теории эволюционных вычислений и генетических алгоритмов, теории чисел, метрических характеристиках М. Холстеда.

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

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

чальной популяции; стратегии распараллеливания генетических алгоритмов. Классификация позволила обобщить:

- способы представления хромосом в виде графовых структур;

- операции над хромосомами как операции над графовыми структурами.

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

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

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

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

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

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

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

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

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

Реализация результатов работы. Результаты диссертационных исследований использовались в НИР «Разработка комплекса моделей и их трансформаций для проектирования распределённых информационно-управляющих систем промышленной автоматики» (№ 2.1.2/4257), проводимой в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы». Результаты работы внедрены в ООО НПФ «КРУГ».

Апробация работы. Результаты исследований докладывались на следующих конференциях: VII Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2006 г.); VII Международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2007 г.); Международной конференции «Проблемы автоматизации и управления в технических системах» (Пенза, 2008 г.); I Всероссийской научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2008 г.); VIII Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2008 г.), а также на Международном симпозиуме «Надёжность и качество» (Пенза, 2009 г.).

Публикации. По теме диссертации опубликовано 12 печатных работ, из них 2 - в журналах, рекомендованных ВАК РФ, 1 - в межвузовском сборнике научных трудов.

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, пяти приложений и списка литературы. Работа содержит 178 страниц текста, 44 рисунка, 10 таблиц.

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

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

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

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

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

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

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

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

Хромосома представлена в виде графа Н, вершинами которого являются гены. Ген - это элемент множества О, такой, что g ей, g¡= . Вершина g определяется следующими атрибу-

тами: значением х(, способом кодирования с, , местоположением в хромосоме

Структура графа Я описывается матрицей смежности М = { {т1 },"=1 }"=) размером п х п, где п - количество элементов хромосомы; т1 ^ определяет наличие

дуги из /-й вершины в у'-ю. Свойства элементов графа II определяет упорядоченное множество вершин &

На рисунке I представлен пример хромосомы.

Местоположение гена Значение гена Тип кодирования гена

( 4 \

12

< 2 У

с N

Г

X

ч с

г \ 2 1 3

АРСН 10010

1 ^ { 4 J

Рисунок 1 - Пример хромосомы

Для преобразования < М,С > во внутреннее представление используются методы теории нумерации. Каждому графу поставим в соответствие натуральное число (или номер). Номер будет образовываться путём свёртки:

Т = >У(Я),

где Г - номер графа; м> - операция свёртки; Н =< Л/, О >.

Операция восстановления мт является обратной по отношению к операции свёртки:

Я = ит(Г).

Операции свёртки и восстановления графа основаны на методах нумерации пары чисел.

Преобразование и» происходит следующим образом: Т = и'(Л/, О) = н'з (IV! (М), и'2 (О) = (и, V), где II описывает структуру внутреннего представления; V - элементы внутреннего представления; Г - унифицированное внутреннее представление хромосомы; - функция преобразования структуры хромосомы; >1>2 - функция преобразования упорядоченного множества элементов (генов); н'з - функция преобразования пары <и,У >.

Нумерация пары чисел в общем случае определяется как пит = 5(х|,л:2), где х\,х2)пит е Лг; 5 - функция нумерации. Обратное преобразование определяется формулами х, = г(пит),х2 = 1{пит), где г и / являются функциями получения значений пары чисел по их номеру.

При кодировании хромосомы на функцию нумерации 5 накладываются ограничения:

V х,у 3 (дг,у)) =< х,у >; V г 3 х,у:(г) =<х,у>.

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

Номер последовательности натуральных чисел вычисляется на основе нумерации пары чисел и определяется по формулам:

•*2(*1>*2) = 5(*1»*2)>

, Х2, ) = Ф2 , Х2), х3),

Л*,

хп-2)'хп-0'хп)-

Вычисление последовательности натуральных чисел по номеру основано на применении выражений х\ = г(пит) и хг = 1(пит) и определяется следующим образом:

х„ = 1{пит), х„-\ =1(г(пит)),

х2=1(г(...г(пит)...)), *, =г(г(..у(им/и)...)).

Преобразование матрицы М (функция м^) описывается следующим алгоритмом:

1) задать номер строки матрицы / = 1;

2) для 1-й строки матрицы М вычислить номер: пит1 =л(М,);

3) перейти на следующую строку матрицы: / = / +1;

4) если / меньше или равно количеству строк матрицы М -перейти на шаг 2;

5) для последовательности вычисленных номеров строк матрицы М вычислить номер V = з(пит)\

6) выход.

Преобразование генов G:={g^,g2,.•.,g„} (где л - количество генов) описывается алгоритмом (функция

1) запомнить текущий ген: V = g^;

2) задать текущий индекс гена: / = 2;

3) вычислить номер: V - ;

4) перейти к следующему гену: / = / +1;

4) если / < п, то - на шаг 3;

5) выход.

Представление хромосомы как графа позволяет сформулировать классическую алгебраическую модель ГА А:

А = (Р,ор(Р)),

где Р - множество хромосом (во внешнем представлении в виде графа, Н е РУ, ор - операции над хромосомами (ор = {т?,сг\$1}; тГ' -оператор мутации; сг'~ оператор скрещивания; я/- оператор селекции).

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

В = (Т*,ор(Т*)),

где Т*- множество хромосом (во внутреннем представлении в виде натуральных чисел, ТеТ*); ор = (т/ - оператор нумераци-

онной мутации; сг - оператор нумерационного скрещивания); 5/ -оператор селекции, аналогичный модели А.

Оператор нумерационного скрещивания определяется как

сг{Тх,Тг,Г) = Т2,

где Г],Г2 - унифицированное представление хромосом в виде натурального числа; /' - тип операции скрещивания, определяющий арифметическую операцию над исходными хромосомами для получения новой хромосомы.

Оператор нумерационной мутации определяется как

тп{(ТиГ) = Т2,

где 7\ - унифицированное представление хромосом в виде натурального числа; /" - тип операции мутации, определяющий арифметическую операцию по изменению исходной хромосомы.

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

Замкнутый интервал определяется как / = [а,Ь] = {Т е N | а й Т й Ь). Пусть даны две популяции Рх ={Г11,Г21,...,ГП1> и Р2 Популяцию предложено охарактеризовать интервалом: I = [а,Ь], а = шт(?), ¿ = тах(Р). Длина интервала / = [а,Ь] есть значение 1еп(/)=|6-а|.

Интервальные операции умножения, деления, сложения, вычитания над указанными интервалами определены как:

Л +12 =[в| +°г>ъ\ +Ъ2] = [аг,Ьг] = 1ъ\

/, -12 = [а1-а2,Ь]-Ь2) = [а3,Ь3]=: 13\

/, /2 = [ш ¡п {а, 6,, , а26,, а2Ь2 },шах{йг1й1,а1Ь2, а^ ,а262}] =

= [а3,г>3] = /3;

Результатом операций над интервалами является интервал /3 = [а3,63], описывающий популяцию /*3.

Результат теоретико-множественной операции пересечения интервалов, описывающих популяции, может быть вычислен как /3 =/, п/2 =[тах{а,,а2},тт{6],62}]. Объединение интервалов определено как 73 = и/2 =[шт{а1)а2},шах{Ь1,Ь2}].

Предложены способы вычисления новых популяций на основе интервальных вычислений: операция «больше или равно» между интервалом и константой /) < р, где /] - интервал; р - константа; операция усечения интервала р{<1\< рг, здесь р\,рг - константы; /; - интервал; операция «меньше или равно» между интервалами /[ й /2; операции разбиения интервалов (разбиение интервала на подынтервалы равной длины; разбиение интервала на подынтервалы, содержащие равное количество элементов; разбиение интервала на подынтервалы по критерию, например по признаку чётность/нечётность).

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

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

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

Оператор Описание

repeat... until Цикл с постусловием

while Цикл с предусловием

if... else Условный оператор

crossover Скрещивание (кроссовер)

mutation Мутация

selection Селекция

bestflt Получить лучшую хромосому в популяции

print Вывести информацию (на экран или на график)

pmut Структура, описывающая параметры оператора мутации

pcross Структура, описывающая параметры оператора скрещивания

pselect Структура, описывающая параметры оператора селекции

+ Сложение

- ' Вычитание

/ Деление

* Умножение

parallel Параллельное выполнение закодированного генетического алгоритма

pop Описание популяции

unified Тип данных — целое число, необходимый для представления хромосом в унифицированном виде

Проведён эксперимент, заключающийся в решении задачи поиска экстремума функции средствами различных языков программирования (С++, Pascal, Lisp, язык программирования генетических алгоритмов). Для полученного программного кода были вычислены характеристики, введённые М. Холстедом: длина программы, объём программы, уровень программы, уровень языка программирования, ожидаемое время реализации алгоритма, интеллектуальное содержание алгоритма, работа (как характеристика проделанной человеком умственной работы).

В качестве исследуемой функции была взята тестовая функция Ро-зенброка (vV = 12):

fCx)= Ъ(1Щхм-х?)2 +(х, -I)2).

1=1

Функция достигает минимума /(*) = О при х, = 1,/ = 1,..., 12. Задача поиска экстремума была решена на рассматриваемых языках программирования. Результаты эксперимента представлены в таблице 2. Таблица 2 - Результаты эксперимента

Название характеристики С++ Равса! Ывр Код на С++ с использованием библиотеки функций ГА Программа на языке программирования ГА

Длина программы, количество операторов и операндов 352 300 320 263 239

Объём программы, бит 2297 2218 1992 896 783

Уровень программы 0,01 0,011 0,013 0,028 0,036

Уровень языка программирования 0,23 0,233 0,313 0,67 0,86

Ожидаемое время реализации алгоритма, с 12490 10650 8193 3066 2114

Интеллектуальное содержание алгоритма 22 21 26 24,7 25,6

Количество переданных ошибок 0,766 0,722 0,664 0,3 0,261

Работа, количество действий, необходимых для реализации программы 261700 255300 141400 31540 18910

Анализ полученных данных позволил сделать следующие основные выводы:

- уменьшается время реализации ГА при использовании языка программирования генетических алгоритмов;

- вероятность появления ошибок в реализации ГА уменьшается при использовании языка программирования ГА.

В четвёртой главе были продемонстрированы возможности нового языка программирования ГА на примере следующих задач: задача

об «умном муравье»; аппроксимация функции; задача разбиения графа; определение паросочетаний графа; задача о коммивояжёре.

Решение указанных задач предложенными инструментальными средствами эффективнее использования стандартных инструментальных средств по следующим критериям:

- превосходство по характеристикам Холстеда;

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

Результаты работы внедрены в ООО НПФ «КРУГ».

В заключении сформулированы основные результаты диссертационной работы.

В приложениях представлены обзор ГА, экспериментальные данные, акт внедрения.

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

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

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

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

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

- упрощаются процедура преобразования существующих структур данных и генерация новых;

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

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

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

- длина программы меньше на 5...15 %;

- выигрыш по времени программирования от 30 %;

- количество переданных ошибок меньше на 35 %;

- уровень программы выше как минимум на 30 %.

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

- превосходство по характеристикам Холстеда;

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

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

Публикации в журналах, рекомендованных ВАК РФ

1. Генералов, К. А. Анализ эффективности использования генетических алгоритмов в задачах при использовании различных языков программирования / К. А. Генералов // Вопросы современной науки и практики. Университет им. В. И. Вернандского. Том 2. Серия Технические науки. - 2008. - № 12 (2). - С. 148-155.

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

ритмов/ К. А. Генералов // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2008. - № 3. - С. 25-32.

Публикации в других изданиях

3. Генералов, К. А. Создание начальной популяции генетических алгоритмов на основе плотности распределения / К. А- Генералов // Вычислительные системы и технологии обработки информации : меж-вуз. сб. науч. тр. - Вып. 6. - Пенза : Информационно-издательский центр ПензГУ, 2006. - С. 5-11.

4. Генералов, К. А. Динамическая настройка параметров генетических алгоритмов, основанная на предварительном анализе / К. А. Генералов // Научно-техническое творчество молодёжи - путь к обществу, основанному на знаниях: сб. науч. докл. [Московский государственный строительный университет]. - М.: МГСУ, 2006. - С. 253-255.

5. Генералов, К, А. Язык генетического программирования / К. А. Генералов // Новые информационные технологии и системы : тр. VII Меж-дунар. науч.-техн. конф. Часть 2. - Пенза : Информационно-издательский центр ПензГУ, 2006. - С. 98-104.

6. Генералов, К. А. Использование параллельных вычислений в генетических алгоритмах / К. А. Генералов // Высокопроизводительные параллейные вычисления на кластерных системах: материалы седьмой Междунар. конф. - Нижний Новгород : Изд-во Нижегор. ун-та, 2007.-С. 90-96.

7. Генералов, К. А. Разработка нового языка программирования / К. А. Генералов // Проблемы автоматизации и управления в технических системах : тр. Междунар. науч.-техн. конф. / под ред. д.т.н., проф. М. А. Щербакова. - Пенза : Информационно-издательский центр ПензГУ, 2008. - С. 245-247.

8. Генералов, К. А. Методы увеличения эффективности использования генетических алгоритмов / К. А. Генералов // Перспективы развития информационных технологий : сб. материалов I Всерос. науч,-практ. конф./ под общ. ред. С. С. Чернова. - Новосибирск : ЦРНС -Издательство СИБПРИНТ, 2008,- С. 81-85.

9. Генералов, К. А. Преобразование элементов данных генетических алгоритмов к унифицированному виду / К. А. Генералов // Новые информационные технологии и системы: тр. VIII Междунар. науч.-техн. конф. Часть 2. - Пенза : Информационно-издательский центр ПензГУ, 2008. - С. 91-99!

10. Генералов, К. А. Методы решения задач глобальной оптимизации / К. А. Генералов // Новые информационные технологии и системы : тр. VIII Междунар. науч.-техн. конф. Часть 2. - Пенза : Информационно-издательский центр ПензГУ, 2008. -С. 99-104.

11. Генералов, К. А. Интервальные вычисления как инструмент манипулирования популяциями в параллельных генетических алгоритмах / К. А. Генералов // Высокопроизводительные параллельные вычисления на кластерных системах : тр. восьмой Междунар. конф. -Казань : Изд-во КГТУ, 2008. - С. 222-225.

12. Генералов, К. А. Применение теории нумерации в генетических алгоритмах / К. А. Генералов // Надёжность и качество : тр. Междунар. симп. - Пенза: Изд-во Пенз. гос. ун-та, 2009 - С. 195-196.

Научное издание

Генералов Константин Александрович

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И ПРОГРАММНЫЕ СРЕДСТВА РЕАЛИЗАЦИИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ НА ОСНОВЕ ТЕОРИИ НУМЕРАЦИИ

Специальности: 05.13.17 - «Теоретические основы информатики»; 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

Редактор Т. В. Веденеева Технический редактор Н. А. Вьялкова

Корректор Н. А. Сидельникова Компьютерная версткаМ Б. Жучковой

Сдано в производство 09.11.2009. Формат 60x84 VI6. Уч.-изд. л. 1,11. Заказ № 563. Тираж 100.

Издательство ПГУ. 440026, Пенза, Красная, 40.

Введение.

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

1.1 Формулировка задачи поиска экстремума.

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

1.3 Принцип работы простого генетического алгоритма.

1.4 Отличия генетических алгоритмов от других методов.

1.5 Анализ вариантов реализации генетических алгоритмов.

1.5.1 Варианты представление генов и хромосом.

1.5.2 Разработка классификации генетических алгоритмов.

1.6 Анализ основных направлений исследований в области генетических алгоритмов.

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

1.8 Исследование методов, средства и технологии реализации генетических алгоритмов.

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

Выводы по первой главе.

2 Обобщённая алгебраическая модель генетических алгоритмов.

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

2.2 Нумерация пар чисел.

2.3 Разработка алгоритма преобразования хромосом к унифицированному виду.

2.4 Пример преобразования хромосом к унифицированному виду.

2.5 Разработка обобщённой алгебраической модели генетического алгоритма.

2.6 Интервальные вычисления над популяциями.

2.7 Общая модель решения задачи.

Выводы по второй главе.

3 Лингвистические средства разработки генетических алгоритмов.

3.1 Концепция языка программирования генетических алгоритмов.

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

3.3 Структура среды реализации генетических алгоритмов.

3.4 Характеристики Холстеда как инструмент оценки эффективности реализации программ.

3.5 Экспериментальное определение характеристик Холстеда.

3.5.1 Постановка решаемой задачи.

3.5.2 Решение задачи на различных языках программирования.

3.6 Анализ результатов эксперимента.

Выводы по третьей главе.

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

4.1 Актуальность использования генетических алгоритмов в задачах оптимизации.

4.2 Решение задачи об "умном муравье".

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

4.4 Решение задачи разбиения графа.

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

4.6 Определение паросочетаний графа.

Выводы по четвёртой главе.

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

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

В последнее время интерес к использованию ГА возрастает. Об этом свидетельствует растущий объём публикаций. Исследованиям в области ГА посвящены работы Д. Гольдберга, Д. Холланда, Д. Коза, Д. И. Батищева, В. М. Курейчика, В. В. Курейчика и других авторов. Большинство работ посвящены следующим вопросам:

- сходимость ГА;

- частные варианты реализации ГА для конкретных задач;

- параллельные реализации ГА;

- особенности представления хромосом и генов.

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

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

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

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

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

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

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

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

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

3. Разработка обобщённой алгебраической модели генетических алгоритмов.

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

5. Создание инструментального ПО для реализации языка программирования.

6. Экспериментальное подтверждение эффективности предложенного инструментария с помощью методик количественной и качественной оценки ПО.

Методы исследования основаны на теории множеств, теории нумераций, теории графов, теории эволюционных вычислений и генетических алгоритмов, теории чисел, метрических характеристиках М. Холсте да.

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

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

- способы представления хромосом в виде графовых структур;

- операции над хромосомами как операции над графовыми структурами.

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

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

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

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

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

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

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

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

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

Реализация работы. Результаты диссертационной работы использовались в научной исследовательской работе "Разработка комплекса моделей и их трансформаций для проектирования распределённых информационно-управляющих систем промышленной автоматики" (№ 2.1.2/4257), проводимой в рамках аналитической ведомственной целевой программы "Развитие научного потенциала высшей школы" Результаты работы внедрены в ООО НПФ "КРУГ".

Публикации. По теме диссертации опубликовано 12 печатных работ, из них 2 в журналах, рекомендованном ВАК РФ, 1 в межвузовском сборнике научных трудов.

Апробация работы. Результаты исследований докладывались на следующих конференциях:

- VII международной научно-технической конференции "Новые информационные технологии и системы" (Пенза, 2006 г);

- VII международной конференции "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород 2007 г.);

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

- I Всероссийской научно-практической конференции "Перспективы развития информационных технологий" (г. Новосибирск, 2008 г.)

- VIII международной научно-технической конференции "Новые информационные технологии и системы" (Пенза, 2008 г);

- Международный симпозиум "Надёжность и качество" (Пенза, 2009 г.).

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, пяти приложений и списка литературы. Работа содержит 178 страниц текста, 44 рисунка, 10 таблиц.

2. Результаты работы внедрены в ООО НПФ "КРУГ". Аппроксимация функции с помощью предложенной обобщённой алгебраической модели генетических алгоритмов использовалась при аппроксимации трендов. Акт внедрения представлен в приложении Д.

Заключение

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

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

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

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

- упрощаются процедура преобразования существующих структур данных и генерация новых;

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

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

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

-длина программы меньше на 5.25 %;

- выигрыш по времени программирования от 30 %;

- количество переданных ошибок меньше на 35 %;

- уровень программы выше как минимум на 30 %.

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

- превосходство по характеристикам Холстеда;

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

1. Батищев, Д.И. Генетические алгоритмы. Решение экстремальных задач/ Д.И. Батищев Нижегородский государственный университет имени Н.И. Лобачевского, 1995 г.

2. Гладков, Л.А. Генетические алгоритмы / Л.А. Гладков, В.В Курейчик,

3. B.М. Курейчик 2-е изд., испр и доп.-М.: ФИЗМАТЛИТ, 2006. -320 с.

4. Поляк, Б.Т. Введение в оптимизацию/ Б.Т. Поляк М.: Наука, 1983.

5. Сухарев, А.Г. Глобальный экстремум и методы его отыскания / А.Г. Сухарев М.: Изд. МГУ, 1981.

6. Васильев, Ф.П. Численные методы решения экстремальных задач/ Ф.П. Васильев -М.: Наука, 1980.

7. Жиглявский, А.А. Методы поиска глобального экстремума/ Жиглявский, А.А., Жилинскас А.Г. М.: Наука, 1991.

8. Herrera, F. Tackling real-coded genetic algorithms: operators and tools for the behaviour analysis/F. Herrera, M. Lozano, J.L. Verdegay // Artificial Intelligence Review, Vol. 12, No. 4, 1998. P. 265-319.

9. Комарцова, Л.Г. Нейрокомпьютеры: Учеб. пособие для вузов. / Л.Г. Комарцова, А.В. Максимов М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. -320 с.

10. Дюк, В.А. Data Mining: учебный курс./ В.А. Дюк, А.П. Самойленко -СПб.: Питер, 2001.

11. D'haeseleer, P. "Context preserving crossover in genetic programming."/ P.D'haeseleer.// In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, volume 2 pages 256-261.

12. Branke, J. Global Selection Methods for SIMD Computers."/ J. Branke, H.

13. C. Andersen, H. Schmeck // Forschungsbericht Xo. 333, Institute AIFB, University of Karlsruhe, Germany.

14. Allenson, R. Genetic Algorithms with Gender for Multi-function Optimisation"/R Allenson//. EPC SS92-01, September 1992.

15. Drechsler, R. A Genetic algorithm for minimization of fixed polarity reed-muller expression"/ R. Drechsler, B. Becker, N. Gockel. // International Conference on Artificial Neural Networks and Genetic Algorithms, pages 392395, Ales, April 1995.

16. Culberson, J. Genetic Invariance: a new Paradigm for genetic algorithm design"/ J. Culberson // DEPARTMENT OF COMPUTING SCIENCE University of Alberta, Edmonton, Alberta, Canada, Technical Report 1992 TR 92-02

17. Dorigo, M. Parallel genetic algorithms: Introduction and overview of current research./ M. Dorigo, M. V. Maniezzo. In J. Stender, editor// Parallel Genetic Algorithms, pages 5-42. IOS Press, 1993.

18. Herrera, F. Fuzzy Connectives Based Crossover Operators to Model Genetic Algorithms Population Diversity / F. Herrera, M. Lozano, J.L.Verdegay // Department of Computer Science and Artificial Intelligence, Technical Report, February 1995.

19. Lienig, J. A Parallel Genetic Algorithm for Performance-Driven VLSI Routing/ J. Lienig // Tanner Research,Inc.,2650 EastFoothi lBlvd. Pasadena,CA 9107.

20. Corno, F. A Parallel Genetic Algorithm for Automatic Generation33. of Test Sequences for Digital Circuits / Fulvio CORNO, Paolo PRINETTO, Maurizio REBAUDENGO, Matteo SONZA REORDA, // Dip. Automatica e Informatica Politecnico di Torino - Torino, Italy.

21. Belding, T.C. The Distributed Genetic Algorithm Revisited// Division of Computer Seine and Engineerin University of Michigan.

22. Dick, R.P. MOGAC: A Multiobjective Genetic Algorithm for Hardware-Software Co-Synthesis of Distributed Embedded Systems/ Robert P. Dick, Niraj K. Jha // Princeton University, Princeton

23. Crompton, W. A Parallel Genetic Algorithm for Frequency Assignment Problems/ W.Crompton, S.Hurley, N.MStephens // Department of Computing Mathematics University of Wales Colege of Cardi, 1994.

24. Goldberg, D.E. SamirW.Mahfoud, Paralel Recombinative Simulated Annealing: A Genetic Algorithm/ David E.Goldberg // Ilinois Genetic Algorithms Laboratory (IliGAL) Department of General Enginering University of Ilinois at Urbana-Champaign.

25. D. Abramson, J. Abela ,A Parallel Genetic Algorithm for Solving the School Timetabling Problem// High Performance Computation Project Division of Information Technology, 15 Australian Computer Science Conference, Hobart, Feb 1992.

26. Levine, D. Users Guide to the PGAPack Paralel Genetic AlgorithmLibrary/ David Levine // Mathematics and Computer Science Division, January 1996

27. Turton B.C.H.,A HARDWARE ARCHITECTURE FOR A PARALLEL GENETIC ALGORITHM FOR IMAGE REGISTRATION/ B.C.H. Turton, T. Arslan, D.H. Horrocks

28. Doval, D. Automatic Clustering of Software Systems using a Genetic Algorithm/ D. Doval, S. Mancoridis, B. S. Mitchell // Dept. of Mathematics and Computer Science Drexel University, Philadelphia.

29. Whitley, D. An Exexutable Model of a Simple Genetic Algorithm/ Darell Whitley // Computer Science Department, Colorado State University

30. Курейчик, B.M. Генетические алгоритмы / B.M. Курейчик // Перспективные информационные технологии и интеллектуальные системы. -2000.-№1.

31. Родзин, С.И. Формы реализации и границы применения эволюционных алгоритмов/ С.И. Родзин // Перспективные информационные технологии и интеллектуальные системы. 2002. — №1.

32. Паклин, Н.Б. Интеллектуальные модели на основе гибридного генетического алгоритма с градиентным обучением лидера / Н.Б. Паклин, М.А. Сенилов, В.А. Тененев // Искусственный интеллект. — Донецк: Наука i ocBiTa. 2004. - № 4. С. 159-168.

33. Макконелл, Дж. Основы современных алгоритмов/ Дж. Макконелл 2-е дополненное издание Москва: Техносфера, 2004. - 368 с.

34. Курейчик, В.М. Эволюционная адаптация в обучении нейронных сетей/ В.М. Курейчик, Б.К. Лебедев, В.И. Божич. // Перспективные информационные технологии и интеллектуальные системы. — №2, 2000, с 22— 25.

35. Гладков, JI.A. Генетический алгоритм планаризации на основе матрицы цепей / JI.A. Гладков // Перспективные информационные технологии и интеллектуальные системы. 2000. - №2. — С. 105-113.

36. Лебедев, В.Б. Планирование СБИС методом генетического поиска / В.Б. Лебедев // Перспективные информационные технологии и интеллектуальные системы. — 2000. №2 - С. 97-104.

37. Курейчик, В.М. Генетические алгоритмы в комбинаторно-логических задачах искусственного интеллекта / В.М. Курейчик, В.В. Курейчик. // Перспективные информационные технологии и интеллектуальные системы. -2000.-№2, -С. 92-95.

38. Иванов, В.В. Генетические эвристики для определения планарности графа / В.В. Иванов, Н.В. Курейчик. // Перспективные информационные технологии и интеллектуальные системы. 2000. - №3. — С. 94-95.

39. Курейчик, В.М. Алгоритмы эволюционного проектирования электронных устройств в статическом режиме/ В.М. Курейчик, Л.А. Зинченко. // Перспективные информационные технологии и интеллектуальные системы. 2000. - №3. - С. 63-68.

40. Курейчик, В.В. Применение гомеостатических, синергетических и эволюционных подходов для принятия решений в интеллектуальных системах/ В.В. Курейчик. // Перспективные информационные технологии и интеллектуальные системы. 2000. - №4. - С. 125-127.

41. Рябец, М.Н. О нормировочных коэффициентах в многокритериальных задачах на базе генетических алгоритмов/ М.Н. Рябец. // Перспективные информационные технологии и интеллектуальные системы. №4, 2000, с 2829.

42. Ковалев, А.В. Генетический алгоритм размещения разногабаритных блоков СБИС/ А.В. Ковалев, Б.Г. Конаплев. // Перспективныеинформационные технологии и интеллектуальные системы. 2002. - №5. -С. 71-87.

43. Божич, В.И. Разработка генетического алгоритма обучения нейронных сетей/ В.И. Божич, О.Б. Лебедев, Ю.Л. Шницер. // Перспективные информационные технологии и интеллектуальные системы. 2002. - №5. -С. 21-24.

44. Курейчик, В.В. Эволюционные методы принятия решений с синергетическими и гомеостатическими принципами управления/ В.В. Курейчик. // Перспективные информационные технологии и интеллектуальные системы. 2002. - №5. - С. 6-10.

45. Курейчик, В.М. Эволюционное моделирование с использованием численно-аналитических моделей / В.М. Курейчик, Л.А. Зинченко. // Перспективные информационные технологии и интеллектуальные системы. -2002.-№6. -С. 30-39.

46. Курейчик, В.М. Исследование динамических операторов в эволюционном моделировании/ В.М. Курейчик, Л.А Зинченко, И.В. Хабарова. // Перспективные информационные технологии и интеллектуальные системы. 2002. - №7 - С. 65—70.

47. Курейчик, В.В. Принятие решений на основе моделирования эволюций / В.В. Курейчик. // Перспективные информационные технологии и интеллектуальные системы. 2002. - №7. С. 61-65.

48. Харламов, И.А. Генетический алгоритм компоновки с переменной структурой/ И.А. Харламов. // Перспективные информационные технологии и интеллектуальные системы. 2002. - №8. - С. 65-71.

49. Смирнова, О.В. Метод локального поиска для разбиения схем ЭВМ / О.В. Смирнова. // Перспективные информационные технологии и интеллектуальные системы. №10, 2003, с 35-36.

50. Родзин, С.И. Эволюционные стратегии: концепция и результаты/ С.И. Родзин // Перспективные информационные технологии и интеллектуальные системы. -2003. №10, 2003, с 4-12.

51. Божич, В.И. Методы генетического поиска для решений представимых мультихромосомами / В.И. Божич, В.Б. Лебедев. // Перспективные информационные технологии и интеллектуальные системы. — 2003— №11. -С. 38-44.

52. Лебедев, Б.К. Формирование гомологических структур хромосом при кодировании списков/ Б.К. Лебедев. // Перспективные информационные технологии и интеллектуальные системы. — 2003. №11. — С. 24-32.

53. Малюков, С.П. Проектирование магнитных головок с помощью генетических алгоритмов / С.П. Малюков, С.А. Обжелянский. // Перспективные информационные технологии и интеллектуальные системы. — 2003.-№11,-С. 56-60.

54. Черун, С.В. Эволюционное проектирование логических схем / С.В. Черун. // Перспективные информационные технологии и интеллектуальные системы. 2003. - №12.- С. 30-34.

55. Курейчик, В.В. Построение моделей эволюций для решения задач на графах / В.В. Курейчик, Л.А. Стасенко. // Перспективные информационные технологии и интеллектуальные системы. 2003. -№12.- С. 14-21.

56. Стасенко, Л.А. Основные принципы генетического поиска для решения задач на графах / Л.А. Стасенко. // Перспективные информационные технологии и интеллектуальные системы. 2003. №13. - С. 15-18.

57. Кодачигов, В.И. Применение генетического подхода к оценке эффективности приведения разряженных матриц к ленточной форме / В.И. Кодачигов, Н.В. Братащенко // Перспективные информационные технологии и интеллектуальные системы. 2003. - №14 - С. 16-21.

58. Холстед, М. X. Начала науки о программах / М.Х. Холстед, пер. с англ. В.М. Юфы. — М.: финансы и статистика, 1981 128 с.

59. Andersson, M. Object-Oriented Design Quality Metrics / Magnus Andersson Patrik Vestergren // Uppsala Master's Theses in Computer Science 276, Information Technology Computing Science Department Uppsala University, Sweden, 2004-06-07.

60. Victor, R. A VALIDATION OF OBJECT-ORIENTED DESIGN METRICS AS QUALITY INDICATORS/ R.Victor, L. Briand, Walcelio L. Melo, // Technical Report, Univ. of Maryland, Dep. of Computer Science, College Park, MD, 20742 USA. April 1995.

61. Линьков, В. M. Нумерационные методы в проектировании систем управления данными: Монография./ В.М. Линьков Изд-во Пензенского государственного технического университета, 1994.-156с.

62. Ахо, А.Теория синтаксического анализа, перевода и компиляции/ А. Ахо, Д.Ульман -М.: Мир, 1978.

63. Грис, Д. Конструирование компиляторов для вычислительных машин / Д. Грис -М.: Мир, 1976.

64. Рейуорд-Смит, В. Теория формальных языков. Вводный курс. / Рейуорд-Смит В. М.: Радио и связь, 1988

65. Фридман, А. Теория и проектирование переключательных схем / Фридман А., Менон П. М.: Мир, 1978.

66. Кук, Д. Компьютерная математика / Кук Д., Бейз Г. М.: Наука, 1990.

67. Кузнецов, О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский М.: Энергоатомиздат, 1988.

68. Вавилов, Е.Н. Синтез схем электронных цифровых машин / Вавилов Е.Н., Портной Т.П. М.: Наука, 1970.

69. Фомичев B.C. Арифметические и логические основы вычислительной техники: Конспект лекций./ЛЭТИ. Л., 1973-1975. Вып.1. 1973; Вып.2. 1974; Вып.З. 1975; Вып.4. 1975.

70. Неупокоева, Н.В. Об одной архитектуре генетического поиска/ Н.В. Неупокоева // Перспективные информационные технологии и интеллектуальные системы. 2003. - №15. - С. 32-35.

71. Потарусов, Р.В. Модифицированные генетические операторы для задачи упаковки блоков / Р.В. Потарусов // Перспективные информационные технологии и интеллектуальные системы. 2006. - №4. - С. 42-47.

72. Неупокоева, Н.В. Разработки и применение интегрированных квантовых и генетических алгоритмов размещения / Н.В. Неупокоева // Перспективные информационные технологии и интеллектуальные системы. —2005,- №3.-С. 4-11.

73. Герасимов, И.В. Дискретная математика: переключательные функции: Учебное пособие./ Герасимов И.В., Крайников А.В., Фомичев B.C. ТЭТУ. СПб., 1997.

74. Ахо, А. Компиляторы. Принципы, технологии, инструменты./ А. Ахо, Р. Сети, Д. Ульман М.: Вильяме, 2001. - 768с.

75. Генералов, К.А. Специализированный язык программирования как наиболее эффективное средство использования генетических алгоритмов/ К.А. Генералов // Известия высших учебных заведений. Поволжский регион. Технические науки. 2008. - №3 - С. 25 -32.

76. Генералов, К.А. . Язык генетического программирования / К. А. Генералов // Новые информационные технологии и системы : тр. VII

77. Междунар. науч.-техн. конф. Часть 2. Пенза : Информационно-издательский центр ПензГУ, 2006. - С. 98-104.

78. Генералов, К.А Методы решения задач глобальной оптимизации / К. А. Генералов // Новые информационные технологии и системы : тр. VIII Междунар. науч.-техн. конф. Часть 2. Пенза : Информационно-издательский центр ПензГУ, 2008. - С. 99-104.

79. Генералов, К.А. Применение теории нумерации в генетических алгоритмах// Надёжность и качество. Труды международного симпозиума. Пенза: Издательство Пенз. ГУ,- 2009.- С.195-196.

80. Бнркгоф, Г. Современная прикладная алгебра/ Г.Биркгоф, Т. Барти, пер. с англ. Ю.И. Манина- М: Мир 1976 400с.

81. Фогель, JI. Искусственный интеллект и эволюционное моделирование/ Л. Фогель ,А. Оуэне,М. Уолш // М. Мир 1969. — 231 с.93. . Поликарпова, Н. И. Автоматное программирование/ Н. И. Поликарпова, А. А. Шалыто //. 2008. — 167 с.

82. Angeline P.J., Pollack J. Evolutionary Module Acquisition / Proceedings of the Second Annual Conference on Evolutionary Programming. 1993.