В статье дается начальное представление о библиотеке GAlib, которая позволяет решать задачи с помощью генетических алгоритмов. Рассматриваются основные возможности и классы библиотеки, также рассматриваются особенности установки и настройки библиотеки. Показан базовый пример работы генетического алгоритма.
Ключевые слова:генетические алгоритмы, библиотека GAlib.
В данной работе рассматривается С++ библиотека компонентов генетических алгоритмов (GAlib) [1]. Далее библиотека или GAlib. Рассматриваемая библиотека содержит множество различных генетических алгоритмов, а также вспомогательных инструментов для решения оптимизационных задач. GAlib разработана Мэтью Волом (Matthew Wall), затем разработка и поддержка переданы Массачусетскому технологическому институту (MIT). С тех пор библиотека стала свободно распространяемой с возможностью использования в коммерческих программных продуктах.
В начале работы с библиотекой следует изучить возможности и структуру всех классов [2]. Если изучить исходный код и документацию библиотеки, можно заметить строгое разделение классов по группам, а также обобщенность, что в дальнейшем позволяет применить библиотеку для различных видов задач. Первое что следует изучить это группу классов, реализующих генетические алгоритмы (рис. 1). Основным абстрактным классом является GAGeneticAlgorithm. В данном классе содержатся все необходимые методы для реализации генетических алгоритмов. Такими методами являются инициализация популяции, установка и извлечение функций кроссинговера и мутации, установка и извлечение функций выборки, и масштабирования и многие другие функции необходимые алгоритмам. Самая простая реализация генетического алгоритма в данной группе компонентов — это класс GASimpleGA. Простая реализация генетического алгоритма наследует все методы основного абстрактного класса GAGeneticAlgorithm. Также данный класс включает методы установки и извлечения параметра перехода новых решений в новое поколение. Согласно документации GAlib класс GASimpleGA реализует генетический алгоритм, где популяция не пересекающаяся, описанный Голдбергом. Следующий класс реализации генетического алгоритма. Класс GASteadyStateGA реализует алгоритм описанный Де Йонгом, согласно документации GAlib. В данном алгоритме применяется пересекающаяся популяция. В классе предусмотрены методы установки количества переходящих решений в новое поколение. В отличие от предыдущего класса, GAIncrementalGA применяет другой способ пересечения популяции, где за каждую генерацию нового поколения пересекаются одно или два решения. Данный алгоритм также описан Де Йонгом. Последний класс GADemeGA содержит мульти популяцию или независимые популяции, т. е. в данном классе реализуется параллельный генетический алгоритм. Все перечисленные классы позволяют решить достаточно большое количество задач. Но если имеющихся классов будет недостаточно для поставленной задачи, архитектура GAlib позволяет реализовать пользовательский генетический алгоритм на основе абстрактного класса GAGeneticAlgorithm или четырех перечисленных.
Рис. 1. Иерархия классов генетических алгоритмов
К следующей группе компонентов относятся классы, реализующие схемы масштабирования (рис. 2). В библиотеке таких схем всего 5, но есть возможность реализации пользовательских схем. Все схемы основываются на одном классе — GAScalingScheme. Данный класс устанавливается в объект популяции. Задача масштабирования — отслеживать оценку приспособленности каждого решения в популяции. GANoScaling — самый простой способ без отслеживания. GALinearScaling — линейный метод масштабирования описанный Голдбергом. GASigmaTruncationScaling — данный метод используется, когда предполагается, что оценочная функция будет отрицательной. GAPowerLawScaling — используется экспоненциальная зависимость. GASharing — данный метод используется, чтобы производить видообразование.
Рис. 2. Иерархия классов масштабирования популяции
Методы выборки служат для генерации пула решений, чтобы производить над ним генетические операторы. В библиотеке существуют 6 методов выборки (рис. 3). Хотя данных набор методов достаточен для решения любых задач, в библиотеке предусмотрено создание пользовательских методов выборки. GARankSelector — ранговый способ выборки производит отбор лучшего решения каждый раз при выполнении данной операции. GARouletteWheelSelector — классический метод выборки, работает по принципу рулетки. Для каждого решения в текущей популяции вычисляется функция приспособленности, на круговой диаграмме отмечается вероятность выборки, в конце производится случайный выбор решений. GATournamentSelector — другой способ выборки, для своей работы производит отбор двух решений с помощью выборки методом рулетки (GARouletteWheelSelector), затем выбирает одно решение с высокой оценкой приспособленности. GADSSelector — детерминированная дискретная выборка использует двухступенчатую процедуру отбора. На первом этапе вычисляется ожидаемое представление каждого решения. Временная популяция наполняется решениями с самой высокой ожидаемой оценкой. Любые оставшиеся позиции заполняются первыми отсортированными оригинальными решениями, затем выбирается самое лучшее решение в списке. На втором этапе производится универсальный случайный выбор из временной популяции. GASRSSelector — метод стохастической выборки остатка. Этапы работы алгоритма такие же, как у предыдущего метода, за исключением того, что любые дробные представления решений используют функцию правдоподобия. GAUniformSelector — стохастическая универсальная выборка.
Рис. 3. Иерархия классов методов выборки
В библиотеке GAlib представлено большое количество классов для кодирования решений. Все классы основываются на абстрактном классе GAGenome. Способы кодирования представлены практически для любых видов задач (рис. 4). Классы GA1DBinaryStringGenome, GA2DBinaryStringGenome, GA3DBinaryStringGenome представляют классическое представление решений в виде бинарной строки, т. е. один элемент решения представляет собой «0» или «1». Каждый из классов реализует одномерную строку, двухмерную строку или трехмерную строку соответственно. Также все 3 класса основываются на заранее подготовленном классе GABinaryString. Классы GA1DArrayGenome, GA2DArrayGenome, GA3DArrayGenome представляют массивы решений, одномерный, двухмерный, трехмерный массивы соответственно. Каждый из этих классов могут содержать произвольный объект. Также все 3 класса основываются на заранее подготовленном классе GAArray. Для упрощения определенных задач на основе класса GA1DArrayGenome созданы GAStringGenome и GARealGenome, которые представляют собой массив символов (строка) и массив вещественных чисел. GATreeGenome — представляет бинарное дерево, в котором кодируется решение. GAListGenome — представляет однонаправленный список. Как видно из перечисленных классов библиотека содержит достаточно большое количество способов кодирования. Поэтому с помощью библиотеки GAlib можно решать задачи, начиная от простейшего поиска экстремума функции до обучения искусственной нейронной сети.
Рис. 4. Иерархия классов методов кодирования решений
Чтобы начать работать с библиотекой GAlib, необходимо выполнить следующие действия [3]. Т. к. библиотека распространяется исключительно в исходных кодах, предварительно необходимо произвести компиляцию. Последняя версия библиотеки располагается на официальном сайте. После загрузки zip-архива, архив необходимо разархивировать в каталог, например в «C:\galib247». Библиотеку можно скомпилировать практически под любую операционную систему, где существуют компиляторы C++. В данной работе, чтобы произвести компиляцию библиотеки, используется среда разработки Visual Studio Express 2013 под управлением Windows 7. В среде разработки создается новый проект с названием «Library», размещение проекта в каталоге «C:\galib247», тип проекта «Visual C++/Win32/Static library». Т. к. библиотека уже отлажена и готова к применению, выбирается тип компиляции «Release». В проект добавляются все файлы исходного кода с расширением «*.C» из каталога «C:\galib247\ga». В настройках проекта в VC++ Directories указывается путь к заголовочным файлам в поле Include Directories. Здесь указывается «C:\galib247». Также в настройках проекта в разделе Code Generation в поле Runtime Library указывается параметр \MT. В настройках проекта в разделе C/C++ — Advanced в поле Calling Convention указывается параметр /Gz. В Language Enable Run-Time Type Information указывается No (/GR-). В Command Line указывается дополнительный параметр /c. В Advanced в поле Compile As указывается /TP. После всех выставленных настроек можно собрать проект. Если все значения в настройках корректно выставлены, то библиотека собирается без ошибок, а итоговый собранный файл Library.lib должен располагаться в каталоге C:\galib247\Library\Release\. Готовый файл библиотеки теперь доступен для решения оптимизационных задач с помощью генетических алгоритмов. Чтобы решать задачи с помощью данной библиотеки, создается новый проект, подключается файл библиотеки Library.lib, подключаются заголовочные файлы GAlib, а затем можно работать с библиотекой GAlib с помощью API.
Простейшая программа на языке С++ выглядит следующим образом:
float Objective(GAGenome&);
int main() {
GA2DBinaryStringGenome genome(width, height, Objective);
GASimpleGA ga(genome);
ga.evolve();
std::cout << ga.statistics() << std::endl;
return 0;
}
Objective представляет целевую функцию, где производится подсчет приспособленности каждого решения. В данном примере используется простейший генетический алгоритм с представлением решения в виде двухмерной бинарной строки. Вызов ga.evolve(); производит активацию алгоритма, после завершения работы можно вывести информацию о найденном решении с помощью вызова ga.statistics(). Работать с библиотекой GAlib достаточно просто, основные задачи пользователя определить целевую функцию, выбрать подходящий алгоритм и задать необходимые параметры. Например, параметры могут быть следующими:
ga.populationSize(popsize);
ga.nGenerations(ngen);
ga.pMutation(pmut);
ga.pCrossover(pcross);
GASigmaTruncationScaling sigmaTruncation;
ga.scaling(sigmaTruncation);
Из примера видно, что для некоторого генетического алгоритма задается способ масштабирования GASigmaTruncationScaling, устанавливается размер популяции popsize, устанавливается количество поколений ngen для алгоритма и устанавливается вероятность мутации pmut и кроссинговера pcross. Здесь показан простой пример работы алгоритма, для детального изучения всех возможностей в документации библиотеки представлен большой набор примеров различной сложности [4].
В заключении стоит отметить, что работать с библиотекой достаточно легко, несмотря на сложную установки и настройку библиотеки GAlib. В библиотеке содержатся практически все необходимые для работы генетические алгоритмы. Но в случае нехватки нужного алгоритма, библиотека позволяет расширить основной набор алгоритмов за счет парадигмы объектно-ориентированного программирования. Т. к. библиотека распространяется в виде исходных кодов, появляется возможность собрать библиотеку и работать с ней на любой операционной системе. Также стоит отметить, что подобная архитектура библиотеки существует только в GAlib, но сама библиотека написана на языке программирования С++, поэтому программист должен уметь работать с таким языком программирования, в противном случае стоит изучить другую библиотеку генетических алгоритмов.
Литература:
1. GAlib: Matthew's Genetic Algorithms Library [электронный ресурс]: информационный портал — режим доступа http://lancet.mit.edu/ga/GAlib.html
2. GAlib: Class Hierarchy [электронный ресурс]: информационный портал — режим доступа http://lancet.mit.edu/galib-2.4/ClassHierarchy.html
3. GAlib: Installation Instructions [электронный ресурс]: информационный портал — режим доступа http://lancet.mit.edu/galib-2.4/Installation.html
4. GAlib: examples [электронный ресурс]: информационный портал — режим доступа http://lancet.mit.edu/galib-2.4/examples/README.html
