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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

 

Государственное образовательное учреждение

высшего профессионального образования

“Московский государственный технический университет им. Н.Э. Баумана”

(МГТУ им. Н.Э.Баумана)

 

Факультет «Робототехника и комплексная автоматизация» (РК)

Кафедра «Системы автоматизированного проектирования» (РК-6)

 

 

 

Расчетно-пояснительная записка к курсовому проекту на тему

“Разработка программного комплекса для синтеза

популяционных алгоритмов”

 

 

 

 

 

 

                                                         Выполнил: студент группы РК6-112 Ковтун О.В.

Руководитель :  д. ф.м. н., проф. каф. САПР Карпенко А.П.

 

 

 

Москва 2014

Содержание

Введение…………………………………………………………………………...3

1. Общие сведения о П-алгоритмах.……………………………………………..4

2. Постановка задачи на разработку программной системы…………………5

3. Методы решения поставленной  задачи………………………………………6

4. Программная реализация……………………………………………………7

5. Тестирование разработки………………………………………………………8

Вывод………………………………………………………………………..……12

Список литературы………………………………………………………………13

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

В данной работе рассматривается общая концепция популяционных алгоритмов (П-алгоритмов) и приводятся основные понятия, относящиеся к П-алгоритмам.

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

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

 

 

 

 

 

 

 

 

 

 

 

1. Общие сведения  о П-алгоритмах

Популяционные алгоритмы (population algorithms) составляют класс алгоритмов поисковой оптимизации. Они предполагают одновременную обработку нескольких вариантов решения задачи оптимизации и представляют собой альтернативу классическим «траекторным» поисковым алгоритмам, в которых в области поиска эволюционирует только один кандидат на решение этой задачи [1].

Рассмотрим постановку задачи П-алгоритма. В качестве основной рассматриваем детерминированную задачу безусловной оптимизации [1]

,                                   (1)

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

,

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

Рассматриваем также аналогичную задачу условной оптимизации

,                                   (2)

где

 -

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

 

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

1. Инициализация популяции. В области поиска тем или иным образом создаем некоторое число начальных приближений к искомому решению задачи – инициализируем популяцию особей.

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

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

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

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

1) Программа должна решать задачу  условной оптимизации.

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

3) Необходимо предусмотреть удобный пользовательский интерфейс.

4) Необходимо осуществить тестирование  созданного алгоритма на стандартных  примерах.

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

6) Необходимо осуществить статистику  данных, полученных при моделировании  алгоритмов.

3. Методы решения поставленной  задачи

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

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

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

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

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

4. Программная  реализация

Задача создания программного комплекса для синтеза П-алгоритмов может быть решена путем программной реализации. При этом необходимо учесть необходимость графического интерфейса. Программная реализация может быть осуществлена на многих известных языках программирования: С, С++, С#, Delphi, Python, Java, PHP и т.д. Главное требование – компилируемость выбранного языка программирования в графической среде. На сегодняшний день существует множество удобных графических сред, например Microsoft Visio Studio, QT Creator, .Net Framework и т.д. Выбор графической среды зависит от удобства ее использования.

Для реализации программного комплекса необходимо использование объектно-ориентированного программирования. Это обусловлено необходимостью создания классов особи и популяции и многократного применения к объектам классов методов скрещивания и мутации. На основе данных фактов для программной реализации был выбран объектно-ориентированный язык С++, так как данный язык не требует времени на изучение, позволяет реализовать все функции данного программного комплекса, его структурированность оставляет возможность модификации программы [2].

В качестве графической среды была выбрана среда Microsoft Visio Studio. Данная среда удобна в использовании, наиболее известная из графических сред, не требует времени на изучение, позволяет создавать отдельный исполнимый файл программы в качестве приложения.

Опишем основные классы и методы, используемые в программной реализации.

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

1) Метод  void TestChromosomes( ) реализует фитнес-функцию для поставленной задачи.

2) Метод TSpecies Cross( ) реализует оператор кроссинговера.

3) Метод TSpecies Mutation( ) реализует оператор мутации.

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

1) MaxSize - максимальное число осбоей, которое может содержать популяция.

2) CrossPossibility - вероятность скрещивания. Задается пользователем с помощью стандартного ввода.

3) MutationPossibility вероятность мутации. Задается пользователем с помощью стандартного ввода.

5. Тестирование  разработки

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

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

Рисунок 1. Работа программы на первом тестовом примере

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

В качестве второго тестового примера пользователю предлагается минимизировать функцию Швефеля . Данная функция примечательна тем, что она имеет много локальных минимумов и максимумов, но глобальный минимум у нее только один. Если все n переменных  изменяются в интервале (-500; 500), то глобальный минимум будет в точке, когда все переменные   будут равны 420.9687. При этом значение целевой функции будет равно -n · 418.9829.

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

Рисунок 2. Работы программы на втором тестовом примере

 

 Пользователь может переключаться между двумя формами «Решение» и «Сходимость».  Первая форма представляет пользователю аналитическое решение, а вторая форма – графическое решение. Графическое решение представлено на рисунке 3.

Рисунок 3. Графическое решение второго тестового примера

 

 

 

 

 

 

 

Вывод

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

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

 

 

 

 

 

 

 

 

 

 

 

Список литературы

1. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учебное пособие. – М.: Издательство МГТУ им. Н. Э. Баумана, 2014, с. 14-116.

2. Грэхем И. Объектно-ориентированные методы. Принципы и практика. — М.: «Вильямс», 2004, с.100-499.