2. Описание программы Mendel
Программа Mendel предназначена для решения задач оптимизации. Реализует в себе диплоидную версию генетического алгоритма и позволяет работать с произвольными пользовательскими задачами оптимизации. Целевая функция оптимизационной задачи и ее параметры описывается во внешней dll-библиотеке задачи оптимизации.
В общем случае для решения задачи с помощью программы Mendel требуется:
1) Создать задачу оптимизации с помощью мастера Новая задача, указав dll-библиотеку задачи.
2) Задать параметры генетического алгоритма (число особей в популяции, критерии останова работы алгоритма, параметры процедур скрещивания, мутации, отбора и т.д.)
3) Запустить работу генетического алгоритма.
Информацию о результатах поиска можно сохранить в виде отчета
Рассмотрим работу с программой Mendel на следующих примерах:
Пример 1. Найти минимум функции
.
Ниже приведен график тестовой функции для случая двухмерного поискового пространства (рис. 1). Даже этот упрощенный вариант позволяет оценить сложность поставленной задачи минимизации.
Рис. 1. – График функции
Для решения задачи необходимо проделать следующие шаги:
1) Выбрать команду Новая задача пункта меню Задача в главном окне программы и указать путь к библиотеке, хранящей параметры и целевую функцию решаемой задачи (рис. 2).
Рис. 2 – Выбор библиотеки задачи оптимизации
2) Далее зададим количество особей в популяции и способ их формирования (например, случайным образом) (рис. 3).
Рис. 3 – Задание параметров популяции
3) Следующее окно программы (рис. 4) позволяет управлять работой алгоритма и содержит в себе главное меню, панель инструментов, панель Поиск, переключатель показа/скрытия панели Поиск, панель Статистика, переключатель показа/скрытия панели Статистика, строку состояния.
Рис. 4
Главное меню содержит следующие пункты:
1) Меню Задача позволяет создавать и управлять файлами задач и шаблонов задач, содержит следующие команды:
Новая задача – запуск мастера создания новой задачи;
Новая задача по шаблону – открывает шаблон задачи и запускает мастер Новая задача с параметрами из шаблона;
Открыть задачу – открывает задачу или ее резервную копию;
Последние задачи – позволяет открыть задачу из списка последних задач;
Сохранить задачу - сохраняет текущую задачу;
Сохранить задачу как – сохраняет задачу под новым именем;
Сохранить как шаблон – сохраняет текущую задачу как шаблон в виде файла с расширением .m4p.
2) Меню Правка позволяет управлять отдельными особями в популяции
Добавить особи (Удалить особи) – позволяет редактировать число особей в популяции;
Пересчитать популяцию – пересчет приспособленности всех особей популяции.
3) Меню Работа позволяет управлять процессом поиска решения задачи и экспортировать результаты работы
Запустить – запуск алгоритма;
Остановить – останавливает работу алгоритма;
Отчет – создает отчет о процессе поиска и лучшем решении задачи в виде файла с расширением .rep;
Выполнить – запускает определенное пользователем приложение;
4) Меню Параметры позволяет произвести общую и точную настройку параметров программы
Генетический алгоритм – открывает окно с параметрами алгоритма;
Условие окончания – позволяет выбрать критерий останова алгоритма;
Меню пользователя – позволяет произвести настройку меню пользователя;
Настройка – позволяет задать настройки пользователя.
Панель Поиск содержит закладки:
Целевая функция – отображает график изменения величины целевой функции для всех особей в зависимости от порядкового номера эпохи;
Область поиска – отображает положение особей популяции текущей эпохи.
Панель Статистика содержит закладки:
Задача – отображает сведения о задаче, статистические данные о процессе поиска решения и характеристики популяции;
Решение – отображает текущее решение задачи;
ГА – отображает статистические данные о работе генетического алгоритма.
Для рассматриваемого нами примера, после запуска алгоритма при следующих параметрах: число особей - 200, останов после достижения 1000 эпохи, были получены следующие результаты (рис. 6).
Рис. 6 – Результат работы генетического алгоритма
Пример 2.
Рассмотрим пример создания библиотеки
dll
для решения пользовательской задачи
нахождения минимума функции
.
Напомним, что DLL (Dynamic Link Library) - это один или несколько логически законченных фрагментов кода, сохраненных в файле с расширением .dll. Этот код может быть запущен на выполнение в процессе функционирования какой-либо другой программы, как в случае с программой Mendel (такие приложения называются вызывающими по отношению к библиотеке), но сама dll-библиотека не является исполняемым файлом.
Общая структура такой библиотеки реализованной с помощью среды Delphi выглядит следующим образом:
library test;
var
Epoche: longint;
RecalcNow: boolean;
procedure InitTask(var TaskName: PChar; var MinimizationTask: boolean;
var TaskDim: integer; var pMin,pMax,pMap,pEp,pRcN: pointer);
begin
TaskName := название задачи;
MinimizationTask := тип задачи минимизации;
TaskDim := размерность задачи;
pMin := указатель на массив нижних пределов области поиска;
pMax := указатель на массив верхних пределов области поиска;
pMap := указатель на массив, описывающий карту хромосомы;
pEp := Addr(Epoche);
RecalcNow := false;
pRcN := Addr(RecalcNow);
end;
function FitnessFunction(parameters: pointer; var condition: boolean): double;
begin
condition := выполнение условия при параметрах parameters;
result := целевая функция от параметров parameters;
end;
function GetKnownParameters(index: integer; parameters: pointer): boolean;
begin
parameters := вектор координат известного решения номер index;
result := было ли присвоено известное значение parameters;
end;
EXPORTS
FitnessFunction,
InitTask,
GetKnownParameters;
BEGIN
END.
В данной лабораторной работе будет рассмотрен способ создания dll-библиотеки с помощью среды Lazarus.
В самом начале работы необходимо запустить среду Lazarus и выполнить команду Создать меню Файл. В открывшемся окне (рис. 7) необходимо выбрать Library, после чего переходим к редактору исходного кода библиотеки.
Рис. 7 – Создание библиотеки
В редакторе исходного кода запишем:
library primer2;
type
m = double;
const
min: m=-500;
max: m=500;
map: m=16;
var
Epoche: longint;
RecalcNow: boolean;
procedure InitTask(var TaskName: PChar; var MinimizationTask: boolean;
var TaskDim: integer; var pMin,pMax,pMap,pEp,pRcN: pointer);
begin
TaskName := 'primer2';
MinimizationTask := true; {true-задача на поиск минимума, false - если поиск максимума}
TaskDim := 1;{размерность задачи}
pMin := addr(min);{указатель на массив нижних пределов области поиска}
pMax := addr(max);{указатель на массив верхних пределов области поиска}
pMap := addr(map);{указатель на массив, описывающий карту хромосомы}
pEp := Addr(Epoche);
RecalcNow := false; {нужно ли пересчитать популяцию}
pRcN := Addr(RecalcNow);
end;
function FitnessFunction(parameters: pointer; var condition: boolean): double;
var
p:^m;
begin
p:= parameters;
condition := true;{выполнение условия при параметрах parameters}
result := p^*p^-4*p^+3;{целевая функция от параметров parameters}
end;
function GetKnownParameters(index: integer; parameters: pointer): boolean;
var
i:integer;
p:^m;
begin
p:=parameters;{вектор координат известного решения номер index}
result:=false;
if index<=70 then
begin
p^:=i;
result:=true;
end;
end;
EXPORTS
FitnessFunction,
InitTask,
GetKnownParameters;
BEGIN
END.
Далее сохраняем проект, и используем созданную нами библиотеку для работы с программой Mendel, как это описано в примере 1.
Задания на лабораторную работу
1. В интерактивном режиме изучить работу с программой Mendel.
2. Изучить ход создания пользовательских библиотек для работы с программой Mendel.
3. Найти минимум функции
.
4. Аппроксимировать функцию по следующим данным
|
x |
-5 |
-2.5 |
-1 |
1 |
2.5 |
3.5 |
4.5 |
|
y |
14 |
0.25 |
-2 |
2 |
10.25 |
18.25 |
28.25 |
Требования к отчету
Отчет к лабораторной работе должен содержать титульный лист, цель работы, задания на лабораторную работу, исходные данные, результаты вычислений, выводы по работе, ответы на контрольные вопросы.