Описание алгоритмов программы

5.1 Генетические алгоритмы

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

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

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

Всю большую популярность приобретают генетические алгоритмы на основе кодирования не бинарной строкой, а простой переменной с плавающей точкой, т.н. Real-Coded Genetic Algorithm. Для них разработаны специальные операторы, которые, вероятно, более разумны и математически обоснованы, чем стандартные бинарные операторы.

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

5.2 Бинарное кодирование

Генетический алгоритм бинарного кодирования использует бинарное представление информации, т.е. параметры особи представлены в бинарной строке как совокупность ‘1’ и ‘0’[3]. Для кодирования признака, принимающего действительные значения в некотором диапазоне, в битовую строку, используется специальный прием. Интервал допустимых значений признака разбивают на участки с требуемой точностью. Для преобразования целочисленного значения гена из множества в вещественное число из интервала пользуются формулой:

, (10)

где N – количество разрядов для кодирования битовой строки.

Чаще всего используются значения N = 8; 16; 32. При увеличении N пространство поиска расширяется и становится огромным. В иностранных источниках часто приводится такой пример. Пусть для 100 переменных, изменяющихся в интервале [-500; 500], требуется найти минимум с точностью до шестого знака после запятой. В этом случае при использовании ГА с двоичным кодированием длина строки составит 3000 элементов, а пространство поиска - около 10 в степени 1000.

Для решения таких задач в непрерывных пространствах возник новый тип ГА - генетический алгоритм с вещественным кодированием (англ.: Real-coded Genetic Algorithm, RGA) [2,3,4]. Основная идея RGA заключается в том, чтобы напрямую представлять гены в виде вещественных чисел, т.е. генотип объекта становится идентичным его фенотипу. Вектор хромосомы состоит из вектора вещественных чисел, и точность найденного решения будет определяться не количеством разрядов для кодирования битовой строки, а будет ограничена возможностями ЭВМ, на которой реализуется вещественный ГА.

5.3 Реальное кодирование

Применение вещественного кодирования может повысить точность найденных решений и повысить скорость нахождения глобального минимума или максимума. Скорость повышается из-за отсутствия процессов кодирования и декодирования хромосом на каждом шаге алгоритма. Для RGA стандартные операторы скрещивания и мутации не подходят, т.к. алгоритм работает только с вещественными числами. По этой причине были разработаны и исследованы специальные операторы. Наиболее полный их обзор приведен в [4]. Этот обзор предлагает сравнение 17 различных модификаций генетических алгоритмов реального кодирования. Тестирование выявила лучший алгоритм по версии Herrera, который использует BLX-alpha(=0.3) (рис 4.) кроссовер и мутацию Non-uniform Mutation (b=5).

Рисунок 4 - BLX-оператор скрещивания

Пусть - хромосома и - мутируемый ген. - результат мутации.

BLX-alpha crossover: Генерируемый потомок где случайно заданное число из интервала , где , , .

Non-uniform Mutation: Этот оператор применяется для поколения t, где - максимальное число поколений, тогда

(11)

где может быть случайным числом 1 или 0.

(12)

где - случайно заданное число из диапазона [0,1] и b – параметр, заданный пользователем, который определяет уровень зависимости от номера текущего поколения.

Это функция возвращает значение из диапазона [0,y], так что вероятность возврата нуля увеличивается с ходом работы алгоритма. Число интервала генераций gmax должно быть меньше реального числа итераций. Это свойство позволяет производить поиск во всем пространстве в начале работы ГА и уточнять решений при его локализации.

5.4 Структура хромосомы

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

Ниже, на рис. 5 можно наблюдать вид простого степенного полинома, где A0..A2 – коэффициенты мономов полинома, а P1.0..P2.1 степени при переменных соответствующих мономов.

Рисунок 5 - Структура степенного монома

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

Кроме того, на рис. 6 даны примерные значения параметров (коэффициентов, степеней) мономов.

Рисунок 6 - Структура хромосомы

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

Рисунок 7 - Полином хромосомы

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

5.5 Тип используемого генетического алгоритма

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

Используемый генетический алгоритм был любезно предоставлен Лощиловым И.Г. в виде библиотеки DLL на условиях использования в учебных целях. В таблице 1 представлены основные параметры генетического алгоритма.

Таблица 1 - Параметры генетического алгоритма

Функции пригодности	=Ошибка преобразования
Цель алгоритма	Минимизация ошибки преобразования
Критерий останова алгоритма	Команда пользователя
Тип кодирования информации	Реальное (RCGA)
Число популяций
Размер популяций	Фиксирован, 100 особей

Окончание таблицы 1 - Параметры генетического алгоритма

Оператор скрещивания	Есть
Число родителей
Число потомков
Оператор мутаций	Нет
Дополнительные операции	Нет

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

Средства взаимодействия с программой Microwave Office

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

Таким образом, внешний разработчик может, например, программно задать параметры моделируемой схемы и параметры моделирования. Кроме того, он может запустить процесс моделирования и получить его результаты. Однако, программно нельзя выполнить любое действие доступное пользователю. Причиной является ограниченность этих механизмов внешнего управления. Управление внутренними источниками выполняется за счет применения так называемой COM-технологии. В данном случае, суть заключается в том, что программист может работать с классами (их интерфейсами) среды моделирования как с собственным.

Т.е. может свободно оперировать элемента среды моделирования. Ограничения заключаются в том, что не для всех элементов управления, доступных пользователю написаны COM объекты для внешнего использования. С каждой новой версией программы набор этих инструментов (COM-объектов) расширяется, однако, например, лишь в последних версиях Microwave Office появилась такая возможность как поворот элемента на 90 градусов. Раньше эта функция COM объекта просто отсутствовала, и при необходимости требовалось удалить соответствующий элемент на схему, создав на его месте новый, но с новым параметром – ‘под углом 90 градусов’. До настоящего времени многие малоиспользуемые функции просто недоступны, это может остановить процесс разработки ПО, когда некоторое действие просто невозможно осуществить программно.

Приведенная на рис. 8 схема позволяет представить в целом структуру и взаимодействие внешних классов среды моделирования MWO. Предположительно, внутренняя структура программы MWO использует COM технологию умеренно, иначе, разработчики могли бы предоставить пользователю внутренние COM-классы. Вероятно, они просто «обертывают» некоторые внутренние классы для сокращения функциональных возможностей и предотвращениях ошибок. Кроме того, встроенный эмулятор языка Visual Basic позволяет, позволяющий пользователям работать с COM-объектами без использования внешней среды разработки (например, Microsoft Visual Studio). Для среднего пользователя системы этого более чем достаточно.

Рисунок 8 - Структура внешних COM классов MWO

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

Таблица 2 Примеры использования среды MWO

1.Открытие программы Microwave Office
Используется:	CoCreateInstance(CLSID_Application, NULL, CLSCTX_LOCAL_SERVER, IID_IMWOffice, (void **) &m_pApplication);
Где:	m_pApplication – экземпляр класса IMWOffice, описывающий интерфейс MWO.
2. Получение интерфейса активного проекта
Используется:	m_pApplication->get_Project(&m_spProject);
Где:	m_spProject – указатель на интерфейс IProject, описывающий класс проекта.

Продолжение таблицы 2 Примеры использования среды MWO

3.Получение списка схем проекта
Используется:	m_spProject->get_Schematics(&m_spSchematics);
Где:	m_spProject – активный проект, m_spSchematics – список схем
4.Получение списка графиков проекта
Используется:	m_spProject->get_Graphs(&m_spGraphs)
Где:	m_spProject – активный проект, m_spSchematics – список графиков
5.Получение определенной схемы
Используется:	m_spSchematics->get_Item(index,&Scheme);
Где:	m_spSchematics – список схем, index – номер схемы, Scheme – полученная схема
6.Получение определенного графика
Используется:	m_spGraphs->get_Item(index,&Graph);
Где:	m_spGraphs – список графиков, index – номер графика, Graph – полученный график
7.Получить список элементов заданной схемы
Используется:	m_spSchematic->get_Elements(&elements);
Где:	m_spSchematic – активная схема, elements – список элементов
8.Получить определенный элемент
Используется:	elements->get_Item(index,&element);
Где:	elements – список элементов, index – номер элемента, element – полученный элемент
9.Получить список параметров элемента
Используется:	element->get_Parameters(&parameters);
Где:	element – актуальный элемет, parameters – список параметров элемента
10.Получить заданный параметр схемы
Используется:	parameters->get_Item(index,&parameter);
Где:	parameters – список параметров элемента, index – запрашиваемого элемента, parameter – результирующий параметр
111.Проверить задана ли оптимизация для данного элемента

Продолжение таблицы 2 - Примеры использования среды MWO

Используется:	parameter->get_Optimize(&isOpt);
Где:	parameter - данный параметр элемента, isOpt – логическая переменная
12.Для заданного графика получить список измерений
Используется:	m_spGraph->get_Measurements(&measurements);
Где:	m_spGraph – актуальный график измерений, measurements – лист измерений
13.Получить заданное измерение для графика
Используется:	measurements->get_Item(index,&meas);

Окончание таблицы 2 Примеры использования среды MWO

Где:	measurements – лист измерений, index – номер интересующего измерения, meas – значения полученного измерения
14.Получить значение нижнего предела варьируемого параметра элемента
Используется:	Parameter->get_LowerConstraint(&MinValue);
Где:	Parameter – параметр элемента, MinValue – значение нижнего предела
15.Задать значение параметра элемента
Используется:	Parameter->put_ValueAsDouble(Value);
Где:	Parameter – параметр элемента, Value – задаваемое значение
16.Получить список частот
Используется:	m_spSchematic->get_Frequencies(&freqs)
Где:	m_spSchematic – атуальная схема, freqs – список частот моделирования для данной схемы
17.Получить значение полученного измерения
Используется:	m_spMeasurement->get_YValues(1, &psa);
Где:	m_spMeasurement – заданное измерений, psa – массив результатов измерения (размер = количество частот)
18.Произвести моделирование всех схем
Используется:	m_spProject->Simulate()

Список можно продолжать и дальше, однако, и так ясно, что нет никаких сложностей в использовании внутренних средств MWO. Каждому объекту, будь то схема, график, элемент, параметр, ставится в соответствие COM-объект, который позволяет легко с собой работать.

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

Информацию о структуре и иерархии COM-классов для последней версии программы Microwave Office можно найти на официальном сайте компании Applied Wave Research www.appwave.com.

Дата добавления: 2015-07-08