Практическая реализация перспективных схем генетического поиска в инструментальной среде "GenSeacrh"

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

ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ ПЕРСПЕКТИВНЫХ СХЕМ ГЕНЕТИЧЕСКОГО ПОИСКА В ИНСТРУМЕНТАЛЬНОЙ СРЕДЕ «GENSEARCH»

Голубин А.В., к.т.н.

Московский Государственный Технический

Университет им. Н.Э. Баумана,

e-mail: golubinal@yandex.ru

ВВЕДЕНИЕ

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

· жесткая привязка, разработанного ПО к задаче на этапах кодирования и декодирования ее решений в виде генов и хромосом;

· программная реализация ГА производится практически с нуля;

· закрытость разработанных программ, как для доработки, так и для интеграции с другими программами;

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

· малое количество реализованных ГО;

Исходя из вышеописанного представляется перспективным разработка инструментальной среды (ИС), удовлетворяющей следующим требованиям:

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

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

· наличие блока подбора и адаптации параметров ГА и ГО под решаемую задачу;

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

· наличие блока анализа исходных данных, сохранения, обработки и анализа результатов с расчетом основных статистических данных;

· возможность встраивания ИС в различные системы, как блок оптимизации;

· простота разработка ИС.

инструментальный среда алгоритм поиск генетический

СТРУКТУРА ИНСТРУМЕНТАЛЬНОЙ СРЕДЫ

Структура ИС «GenSeacrh» изображена на рис.1.

Рис. 1. Структура ИС «GenSearch»

Среда состоит из 4 основных блоков:

1. блока определения и корректировки параметров ГА;

2. блок запуска ГО;

3. блока подстройки ЭС;

4. блока сбора статистики и анализа результатов.

Блок определения и корректировки параметров ГА (БОП) предназначен для определения параметров ГА на основе исходных данных и корректировки параметров ГА в целом и отдельных ГО во время работы ГА. Как показано [2] в эффективность работы ГА напрямую зависит от его параметров. В состав данного блока входят:

1. блок анализа исходных данных;

2. блок реализующий конструктор ГА;

3. экспертная система;

4. внешний блок подбора параметров.

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

Блок, реализующий конструктор ГА предназначен для автоматического определения параметров ГА с помощью конструктора ГА [2]. Его задача состоит в подборе 7 основных параметров для выбранной функции. Принцип действия конструктора следующий:

· пользователь выбирает параметры генетического алгоритма, которые конструктор будет искать и накладывает необходимые ограничения на эти параметры. Количество параметров определяет количество генов хромосом конструктора;

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

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

· следующие этапы соответствуют этапам работы обычного генетического алгоритма.

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

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

Obj ГА

{

PROP Размерность функции

{QUE Количество переменных в функции?

LEG малое((1,1),(5,0))

LEG среднее((3,0),(6,1),(9,1),(10,0))

LEG большое((8,0),(10,1),(25,1),(30,0))

LEG очень большое((25,0), (30,1), (200,1)) }

//список других свойств объекта

}

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

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

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

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

Функция пригодности в ИС может быть определена одним из 3 способов:

· выбрана из библиотеки тестовых функций;

· описана с помощью блока задания функции (БЗФ);

· с помощью внешней процедуры.

В ИС реализовано 14 тестовых непрерывных многопараметрических функций (Роджерса, Жилинскаса, Диксона, Многоэкстремальная, Химмельблау, N переменных, Растригина n=2, Растригина n=10, Растригина n=25, Розенброка, Флетчера и Пауэлла, Вуда, Пауэлла, Павиани), две NP-полных комбинаторных задачи (задача коммивояжера и задача плоского размещения), практическая задача, относящаяся к классу NP-полных (управления запасами при оптимизации ленточного раскроя [6]). Для каждой непрерывной функции имеется возможность просмотра математической формулы, ограничений на переменные, значение экстремума. Блок позволяет задавать любую непрерывную функцию через интерфейс ИС без подключения внешних процедур.

Блок подстройки ЭС (БПЭС) предназначен для корректировки базы правил ЭС во время генетического поиска.

Блок сбора статистики и анализа результатов содержит следующие элементы:

1. блок сохранения результатов;

2. блок расчета параметров популяции;

3. блок анализа результатов;

4. блок графического представления результатов;

5. блок проведения исследований.

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

Блок расчета параметров популяции производит расчет параметров, описанных в [5] и используемых ЭС для выбора ГО.

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

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

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

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

ПОРЯДОК РАБОТЫ СРЕДЫ

Перед началом работы ГА, необходимо первоначально решить несколько задач:

· Какое кодирование хромосом выбрать?

· Как задать функцию пригодности?

· Какое подобрать условие завершения?

· Как отбирать хромосомы на скрещивание, как определять отбракованные геномы?

· Могут ли индивиды из текущего поколения переходить в следующее и будут ли они при этом мутировать?

· Как будут создаваться новые хромосомы?

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

Порядок действий для специалистов прикладной области:

1. провести задание ФП путем:

· выбора из списка реализованных ФП;

· через интерфейс с помощью указания пользовательской непрерывной функции;

· с помощью подключения внешней библиотеки расчета ФП;

2. произвести задание параметров ГА:

· путем установки раннее полученных параметров ГА под решаемую задачу;

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

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

После установки параметров, ИС произведет тестовый запуск ГА со случайно созданной хромосомой и сообщит пользователю примерное время решения.

Отметим, что данное время решения приблизительно и может изменяться в связи с изменением параметров ГА экспертной системой, в том числе критерия останова.

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

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

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

1. Курейчик В.В., Нужнов Е.В. Об интегрированной инструментальной среде поддержки генетических алгоритмов // Новости искусственного интеллекта, 2003. - №5.- С.13-19.

2. Голубин А.В. Определение параметров генетического алгоритма для оптимизации многопараметрических функций // Прогрессивные технологии, конструкции и системы в приборы- и машиностроении: Сборник статей. -М.: МГТУ им. Н.Э. Баумана, 2001. -С.65-67.

3. Бендат Дж., Пирсол А. Измерение и анализ случайных процессов. - М: Мир, 1974.

4. Борель Э., Дельтейл Р., Юрон Р. Вероятности, ошибки / Пер. с франц. -М.: Статистика, 1972.

5. Голубин А.В., Тарасов В.Б. Нечеткие генетические алгоритмы // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'05) и «Интеллектуальные САПР» (CAD-2005). -М.:ФизМатЛит, 2005. -Т.1. -С.39-45.

6. Голубин А.В. Инструментальная среда исследования генетических алгоритмов «GenSearch» // Программные продукты и системы, 2005. - №3. -С.37-42.

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