Интегрированная среда для исследования генетических алгоритмов dsk-gen
Донецкий национальный технический
университет
Факультет компьютерных информационных
технологий и автоматизации
Поляков С.В., группа КСД-99а
Руководитель проф. Скобцов Ю.А.
E-mail : polyakov@ukr.net
Polyakov S.V.
Integrated environment for
research of genetic algorithms of dsk-gen. Genetic algorithms base on the natural
evolution principle and make directed search in a given space. As a result of
inefficient use of some genetic operators (mutation and crossover) destruction
of evolutionary process can be brought in. Special software DSK-GEN was
realized for the research purpose of the various effective structures of
genetic algorithms. The description of its modules and test results is
included. Direction of its
further development is determined.
Введение
Использование эволюционных алгоритмов
позволяет решать различные задачи оптимизации:
навигационные и оптимизации управления подвижными объектами; оптимизации
нечетких баз знаний; оптимизации простых
функций; оптимального распределения объектов. Генетические алгоритмы (ГА) также
широко используются в процессах принятия решений, в финансовых и экономических
моделях. ГА не гарантируют нахождение оптимального решения, но позволяют находить
субоптимальное решение.
Перспективной и интенсивно
развивающейся является двунаправленная интеграция ГА и нечеткой логики (НЛ)
(гибридные системы) [1]. Это позволяет использовать в НЛ преимущества обоих
методов. Хорошо известно, что НЛ позволяет принимать решения в условиях
неопределенности. Например, НЛ обеспечивает базис для представления различных
форм знаний в неопределенных средах, позволяет моделировать взаимодействие
переменных информационной системы. ГА дают возможность обучения, глобального и
локального поиска. Объединению этих двух методов посвящено большое количество
работ [2]. Такое объединение используется для оптимизации нечетких систем, для
нейронных нечетких сетей, нечеткого информационного поиска и обработки баз
данных, в нечетком распознавании образов и обработки изображений, в нечетких
контроллерах (проектировании, обучении, настройке).
1. Описание DSK-GEN
Интегрированная среда DSK-GEN
предназначена для исследования различных вариантов генетических алгоритмов.
Функционально ее можно разделить на следующие блоки: модель объекта,
операционный базис, анализ результатов.
Решение задачи оптимизации с помощью описанного пакета может
производиться как автоматически так и в пошаговом
режиме с возможностью коррекции процесса.
Использование генетических алгоритмов
позволяет формировать стратегии управления рассматриваемым объектом и на их
основе получать оптимальные решения с точки зрения заданного критерия. В случае использования генетических алгоритмов эволюция популяции
(совокупности стратегий) заключается в построении различных вариантов диаграмм
(стратегий) с конечным числом состояний, моделирующих процесс принятия решений
и отображаемых бинарными строками, в полях каждой из которых кодируются номера
состояний и выполняемые действия, причем переход от одной диаграммы к другой
осуществляется за счет использования введенных операционного базиса и критерия
качества. Эволюция популяции в конечном счете
должна привести к оптимальной стратегии, удовлетворяющей цели управления.
Модель объекта задается:
·
кодировкой
исходной информационной системы;
·
оценкой
стратегий в популяции - при этом каждой задаче соответствует своя оценочная
функция, в соответствии с которой формируются значения показателя качества
каждой из стратегий. Моделирование поведения объекта в соответствии с заданной
стратегией является неотъемлемой частью решения задачи и осуществляется в
соответствии с установленной кодировкой.
Связующим звеном между блоком модели
и блоком операционного базиса является задание следующих параметров: длина
стратегии (числа состояний), количество стратегий в популяции, критерии
качества и времени моделирования при оценке каждой стратегии. Для работы
алгоритма также необходимо задать вариант схемы алгоритма, количество поколений
(число шагов процесса оптимизации).
Операционный базис представляет собой
набор генетических операторов, применяемых для решения той или иной задачи.
Операционный базис не зависит от выбранной задачи. Задавая различные типы
генетических операторов, схемы их применения, а также вероятности их
выполнения, можно сформировать генетический алгоритм, в соответствии с которым
будет осуществляться процесс оптимизации.
Анализ результатов предполагает
возможность анализа информации о результатах работы в виде графиков или
текстовых файлов. В среде также имеется возможность контролировать текущее
состояние информационной системы (кодировку стратегий и эффективность их
выполнения).
Для работы системы необходимо выбрать
исходные файлы модели и параметров. Решение задачи оптимизации может
производиться как автоматически, так и в пошаговом режиме с возможностью
коррекции процесса.
2. Результаты тестирования
Для того,
чтобы провести анализ того или иного генетического алгоритма или группы
алгоритмов, необходимо ответить на несколько вопросов:
·
как
будет выполнена селекция;
·
при
заданной селекции и скрещивании, каков будет прогресс популяции;
·
каким
образом можно объединить в одном алгоритме селекцию, мутацию и скрещивание.
Важными параметрами генетических
алгоритмов являются: размер популяции n, вероятность
мутации Pm, вероятность скрещивания Pc. Небольшой размер популяции приводит
к быстрой сходимости алгоритма, с другой стороны, слишком большой размер
популяции требует больших объемов вычислений.
Для оценки алгоритмов использовались
функции on-line и off-line,
определенные в [4]:
On-line(T)=1/Tna t=1Ta i=1n f(dt,i);
Off-line(T)=1/Ta t=1Ta i=1n f(dt*);
где f(dt,i) – одно значение функции в одной популяции,
f(dt*) –
лучшее значение в популяции.
Другими словами, on-line
показывает среднее значение по всем функциям, а off-line
– среднее значение по всем лучшим значениям популяций.
Помимо этого использовалась третья
оценка, которая представляет собой лучшие значения популяции.
Тестирование проводились с
усреднением результатов по 100 запускам, число поколений (число шагов) каждого
запуска –100. Основные результаты следующие:
Тест 1. Результаты тестирования
программы DSK-GEN подтвердили результаты, в которых сравнивались различные схемы
селекции и пришли к выводу, что эффективность методов селекции примерно
одинаковая.
Тест 2. Элитизм
является эффективным дополнением селекции.
Тест 3. Однородное скрещивание лучше,
чем одноточечное и двухточечное и сравнимо с адаптивным однобитовым
локальным скрещиванием, которое все же может дать несколько лучшие
результаты, однако значительного улучшения не дает (результаты эксперимента
совпадают с экспериментами [6]).
Тест 4. Алгоритм различных типов
скрещивания с мутацией лучше алгоритма только с мутацией, особенно по
характеристике on-line, которая считается наиболее
показательной.
Тест 5. Использование алгоритмов
только с оператором скрещивания приводит к быстрой сходимости далеко от
оптимума, но находит подтверждение тот факт, что однородное скрещивание
эффективнее одноточечного. Однако первые два варианта существенно хуже варианта
с использованием только оператора мутации, который, в свою очередь, уступает
вариантам алгоритма с использованием двух операторов - скрещивания и мутации.
Тест 6. Варианты схем генетического
алгоритма (алгоритм с выполнением одноточечного скрещивания с последующей
мутацией скрещенных стратегий; алгоритм с выполнением одноточечного скрещивания
и мутацией остальных стратегий). Результаты эксперимента говорят о том, что
схема 1 несколько лучше схемы 2 при одинаковых вероятностях скрещивания и
мутации. Улучшения со схемой 1 возможны при увеличении интенсивности
скрещивания и мутации.
Заключение
На основании полученных результатов
можно сделать вывод о том, что существует зависимость эффективности ГА от типа,
схемы и вероятности использования генетических операторов. Адаптация или
самоадаптация генетических алгоритмов позволяет повысить эффективность ГА.
Литература
1. Ф. Уоссермен “Нейрокомпьютерная техника: Теория и практика”
Перевод на русский язык, Ю. А. Зуев,
В. А. Точенов,
1992. c. 193
2. А. Н. Скурихин ”Генетические алгоритмы ” статья с. 26
3. Курс лекций по предмету "Основы
проектирования систем с искусственным интеллектом" (http://re-tech.narod.ru/inf/ai/lectures.htm)