Введение к работе
Актуальность работы. Большая часть задач науки и техники относится к обширному классу, проблем поиска оптимальных решений, т.е. к оптимизационным задачам. Среди них существуют задачи, в которых использование традиционных методов поиска решения неэффективно или практически невозможно (например задачи, поиск решений в которых связан с перебором). Для поиска наилучшего решения, как правило, осуществляются направленный, случайный и комбинаторный переборы. В этой связи разрабатывается большое число методов решений этих задач.
Одним из эффективных механизмов решения задач оптимизации является механизм генетических алгоритмов (ГА). Первый ГА был описан Д. Гольдбергом на основе работ Д. Холланда. Основу ГА составляет направленный поиск, принцип работы которого базируется на идеях эволюции живой природы.
В последнее время интерес к использованию ГА возрастает. Об этом свидетельствует растущий объём публикаций. Исследованиям в области ГА посвящены работы Д. Гольдберга, Д. Холланда, Д. Коза, Д. И. Батищева, В. М. Курейчика, В. В. Курейчика и других авторов. Большинство работ посвящены следующим вопросам:
сходимость ГА;
частные варианты реализации ГА для конкретных задач;
параллельные реализации ГА;
особенности представления хромосом и генов.
ГА обладают концептуальной простотой и простотой реализации. Основу ГА составляют три основные операции (скрещивание, мутация, селекция), которые применяются к множеству хромосом.
На сегодняшний день отсутствуют развитые специализированные инструментальные программные средства, позволяющие описывать задачи и процесс их решения в терминах ГА. Причиной этого является многообразие вариантов представления структур данных ГА и операций над ними. Это усложняет процесс реализации ГА, несмотря на то, что алгоритмы этого класса обладают одинаковой общей структурой.
Таким образом, актуальными являются исследования, связанные с повышением эффективности использования ГА, разработкой математического обеспечения и программных средств для реализации ГА.
Объектом исследований являются программные средства автоматизации использования генетических алгоритмов.
Предметом исследований являются языковые средства реализации генетических алгоритмов, включающие в себя синтаксис, семантику языка, представление и кодирование структур данных и алгоритмы их обработки.
Цель работы: создание математического и программного обеспечения, предназначенного для автоматизации разработки прикладных программ, реализующих генетические алгоритмы на основе внутреннего представления хромосом средствами теории нумерации.
Задачи исследования. Для достижения поставленной цели решаются следующие задачи:
Анализ вариантов реализации генетических алгоритмов, структур данных, вариантов их обработки и разработка классификации генетических алгоритмов.
Разработка внутреннего унифицированного представления структур данных генетических алгоритмов.
Разработка обобщённой алгебраической модели генетических алгоритмов.
Разработка проблемно-ориентированного языка программирования генетических алгоритмов с использованием новых способов представления структур данных генетических алгоритмов и операций над ними.
Создание инструментального ПО для реализации языка программирования.
Экспериментальное подтверждение эффективности предложенного инструментария с помощью методик количественной и качественной оценки ПО.
Методы исследования основаны на теории множеств, теории нумераций, теории графов, теории эволюционных вычислений и генетических алгоритмов, теории чисел, метрических характеристиках М. Холстеда.
Научная новизна работы состоит в следующем:
1. Предложена классификация генетических алгоритмов, отличающаяся тем, что в её основу положены следующие признаки: способы представления структур данных (хромосом); методы реализации основных операций генетических алгоритмов; стратегии создания на-
чальной популяции; стратегии распараллеливания генетических алгоритмов. Классификация позволила обобщить:
способы представления хромосом в виде графовых структур;
операции над хромосомами как операции над графовыми структурами.
Предложен способ кодирования графов натуральными числами, отличающийся возможностью представления разнотипных структур данных генетических алгоритмов в унифицированном виде. Способ позволяет упростить манипулирование разнотипными структурами данных генетических алгоритмов и работать с ними по единообразной схеме.
Предложен способ манипулирования структурами данных в параллельных генетических алгоритмах, на основе интервальных вычислений. Представление популяций как интервалов позволяет применять интервальные вычисления и задавать правила обмена хромосомами между популяциями, расположенными на отдельных вычислительных узлах.
Предложены синтаксис и семантика проблемно-ориентированного языка программирования генетических алгоритмов. Язык учитывает особенности реализации генетических алгоритмов, а также отличается способом кодирования структур данных в виде номеров и возможностью параллельного выполнения генетических алгоритмов. Применение языка программирования позволяет снизить время разработки программ и вероятность ошибок в коде при реализации генетических алгоритмов.
Практическая ценность. Разработан язык программирования для реализации генетических алгоритмов. Предложенный язык программирования позволяет описать задачу и процесс решения в терминах генетических алгоритмов, повысить эффективность реализации генетических алгоритмов.
На защиту выносятся:
Способ преобразования структур данных генетических алгоритмов, позволяющий получить унифицированное представление структур данных.
Операторы модификации структур данных генетических алгоритмов, позволяющие работать с унифицированным представлением разнотипных структур по единообразной схеме.
Набор операций над популяциями генетических алгоритмов на основе интервальных вычислений, позволяющий задать правила управления популяциями в параллельных генетических алгоритмах.
Синтаксис и семантика языка программирования генетических алгоритмов, позволяющего описать задачу и процесс её решения в терминах теории генетических алгоритмов.
Реализация результатов работы. Результаты диссертационных исследований использовались в НИР «Разработка комплекса моделей и их трансформаций для проектирования распределённых информационно-управляющих систем промышленной автоматики» (№ 2.1.2/4257), проводимой в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы». Результаты работы внедрены в ООО НПФ «КРУГ».
Апробация работы. Результаты исследований докладывались на следующих конференциях: VII Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2006 г.); VII Международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2007 г.); Международной конференции «Проблемы автоматизации и управления в технических системах» (Пенза, 2008 г.); I Всероссийской научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2008 г.); VIII Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2008 г.), а также на Международном симпозиуме «Надёжность и качество» (Пенза, 2009 г.).
Публикации. По теме диссертации опубликовано 12 печатных работ, из них 2 - в журналах, рекомендованных ВАК РФ, 1 - в межвузовском сборнике научных трудов.
Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, пяти приложений и списка литературы. Работа содержит 178 страниц текста, 44 рисунка, 10 таблиц.
