Библиотека генетических алгоритмов - часть 3

Written on .

ОГЛАВЛЕНИЕ

Данная статья является продолжением второй части из серии статей о библиотеке генетических алгоритмов.

• Скачать исходный код библиотеки - 279 Кб
• Скачать исходный код демонстрационных приложений - 85.81 Кб
• Скачать демонстрационные приложения - 138.83 Кб
• Скачать документацию библиотеки - 1.03 Мб
• Последние версии библиотеки

Первую часть данной серии статей вы можете найти здесь, а вторую - здесь.

Библиотека генетических алгоритмов

Представления хромосом

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

Хромосомы, поддерживающие случайный переворот или инвертирование значений в своем коде, должны реализовывать интерфейс GaMutableCode. Этот интерфейс определяет два метода: Invert и Flip. Метод Invert должен выбирать определенное число значений кода хромосомы и инвертировать их. Метод Flip должен менять случайно определенное число значений кода хромосомы.

Схема - интерфейс GaMutableCode

Интерфейс GaSwapableCode должен реализовываться хромосомами, умеющими переставлять блок значений кода хромосомы. Этот интерфейс определяет метод Swap.

Схема - интерфейс GaSwapableCode

Интерфейс GaSizableCode должен реализовываться хромосомами, умеющими менять число значений в своем коде. Метод Insert должен вставлять определенное число случайных значений в заданное место в коде хромосомы. Метод Remove должен удалять блок значений в заданном месте из кода хромосомы.

Схема - Интерфейс GaSizableCode

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

Схема - Интерфейс GaMultiValueCode

Класс GaCodeValuesBuffer управляет буферами для хранения значений из кодов хромосом. Буфер может использоваться для хранения значений из нескольких хромосом, следовательно, он подходит для объединения хромосом в операциях кроссовера.

Схема - Класс GaCodeValuesBuffer

Интерфейс GaArithmeticalCode должен реализовываться хромосомами, поддерживающими арифметические операции над значениями в своем коде. Этот интерфейс определяет операторы для основных арифметических операций [+, -, *, /] и метод для нахождения срединной точки.

Схема - Интерфейс GaArithmeticalCode

Интерфейс GaCodeValue должен реализовываться классами, обертывающими типы данных значений в коде хромосомы. Этот интерфейс определяет метод FormBuffer, извлекающий единственное значение [в заданном месте] из предоставленного буфера. Метод Initialize при реализации должен случайно инициализировать обернутые данные.

Схема - Интерфейс GaCodeValue

В большинстве ситуаций значения в коде хромосомы имеют ограничения [домен]. Эти ограничения в библиотеке реализованы через наборы значений. Класс GaDomainChromosome использует CCB, хранящий указатель на набор значений, определяющий ограничения значений в коде хромосомы.

Схема – Классы GaDomainChromosome и GaChromosomeDomainBlock

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

Схема – Класс GaValueSet

Метод GenerateRandom случайно выбирает одно значение из набора значений и возвращает его. Метод Inverse возвращает соответствующее значение из группы инвертированных значений. Метод Belongs возвращает true, если заданное значение принадлежит набору значений. ClosestValue возвращает ближайшее значение к заданному значению, принадлежащему набору значений.

Каждый набор значений имеет группу значений [называемых оригиналы] и соответствующую группу противоположных значений [называемых инвертированные значения]. Член _viceVersa определяет обработку инвертированных значений. Если он установлен в true, инвертированные значения рассматриваются как действительные члены набора значений, а значит, инвертированные значения могут использоваться со всеми определенными операциями набора значений так же, как оригинальные значения.

Шаблонный класс GaSingleValueSet является набором значений только с одним оригинальным значением и одним инвертированным значением. Этот набор значений полезен для значений кода хромосомы, имеющих два возможных состояния.

Схема - Класс GaSingleValueSet

Шаблонный класс GaMultiValueSet является набором значений с несколькими значениями. Каждому значению в группе оригиналов соответствует ровно одно инвертированное значение. Дубликаты оригинальных значений запрещены. Инвертированные значения могут дублироваться, только если _viceVersa установлен в false.

Схема – Класс GaMultiValueSet

Шаблонный класс GaIntervalValueSet является набором значений, содержащим продолжающиеся значения в заданном интервале. Границы интервала определены шаблонным классом GaValueIntervalBounds. У типа значений в наборе должны быть определены операторы +, -, >, >=, < и <=. Пользователь должен предоставить генератор случайных значений, реализующий интерфейс GaRandom.

Схема - Класс GaIntervalValueSet

Шаблонный класс GaUnboundValueSet должен использоваться, когда у значений кода хромосомы нет дополнительных ограничений. У типов сохраненных значений должен быть определен унарный оператор -. Пользователь должен предоставить генератор случайных значений, реализующий интерфейс GaRandom. Диапазон значений, генерируемый этим набором значений, определяется исключительно представленным случайным генератором.

Схема - Класс GaUnboundValueSet

GaCombinedValueSet объединяет два и более наборов значений в один набор.

Схема - Класс GaCombinedValueSet

Шаблонный класс GaSingleValueChromosome используется для хромосом, представляющих решение с единственным значением. Это может быть единственное вещественное или целое число или значение любого другого типа. Этот класс реализует только интерфейс GaMutableCode. Поскольку SingleValueChromosome наследует класс GaDomainChromosome, доменом значения управляет набор значений.

Шаблонный класс GaSVAChromosome подходит для хромосом, поддерживающих арифметические операции, потому что он реализует GaArithmeticalCode. У типа данных значений хромосомы должны быть определены операторы +, -, *, / и оператор / с целочисленным операндом с правой стороны. Это позволяет использовать хромосому во встроенных арифметических операциях кроссовера.

Схема - Класс GaSingleValueChromosome

Шаблонный класс GaMultiValueValueChromosome используется для хромосом, требующих несколько значений для представления решения. Этот класс реализует интерфейсы GaMutableCode, GaSwapableCode, GaSizableCode и GaMultiValueCode. Класс GaChromosomeValue применяется для вставки кода в код хромосомы и извлечения значения.

Шаблонный класс GaMVAChromosome расширяет GaMultiValueValueChromosome подобно тому, как GaSVAChromosome расширяет GaSingleValueValueChromosome.

Схема - Класс GaMultiValueChromosome

Шаблонный класс GaBinaryChromosome реализует хромосомы, представляющие решение с помощью двоичного кодирования. Этот класс имеет набор методов, кодирующих встроенные типы в двоичный поток и раскодирующих поток в оригинальные значения. GaBinaryChromosome использует класс GaBinaryChromosomeParams для параметров хромосом. Этот класс определяет состояние набора вероятностей при создании хромосомы.

Класс GaBit применяется для вставки битов в код хромосомы или для их извлечения.

Схема - Класс GaBinaryChromosome

Эти классы расположены в пространствах имен Chromosome::Representation.


Встроенные сравнители пригодности

Встроенные сравнители пригодности расположены в пространстве имен Chromosome::FitnessComparators.

 

Схема – Встроенные сравнители пригодности

Есть два сравнителя пригодности:
•    GaMaxFitnessComparator – применяется для генетических алгоритмов, максимизирующих значение пригодности,
•    GaMinFitnessComparator - применяется для генетических алгоритмов, минимизирующих значение пригодности.

Встроенные операции кроссовера

Встроенные операции кроссовера расположены в пространстве имен Chromosome::Crossover.

 

Схема - Встроенные операции кроссовера

Класс GaMutiValueCrossover реализует операцию кроссовера, создающую потомка путем выбора N точек пересечения, и затем поочередно копирующую значения из родителей, меняя исходного родителя при каждом достижении выбранной точки пересечения. Эта операция требует хромосом, реализующих интерфейс GaMultiValueCode.

 

Схема – Результаты операции GaMutiValueCrossover

Класс GaMidpointCrossover реализует операцию кроссовера, создающую потомка путем вызова метода Midpoint выбранных родителей. Эта операция требует хромосом, реализующих интерфейс GaArithmeticalCode.

 

Схема - Результаты операции GaMidpointCrossover [хромосома с множеством значений, тип значений - int]

GaAddCrossover вызывает operator+ родительской хромосомы, а GaSubCrossover вызывает operator-.

 

Схема - Результаты операции GaAddCrossover [хромосома с множеством значений, тип значений - int]

 

Схема - Результаты операции GaSubCrossover [хромосома с множеством значений, тип значений - int]

Встроенные операции мутации

Встроенные операции мутации расположены в пространстве имен Chromosome::Mutation.

 

Схема - Встроенные операции мутации

Класс GaSwapMutation реализует операцию мутации, выбирающую два блока значений в коде хромосомы и меняющую их местами в коде [максимальное число переставляемых значений определяется размером мутации, заданным в параметрах хромосомы].

 

Схема - Результаты операции GaSwapMutation

Класс GaInvertMutation реализует операцию мутации, выбирающую N значений [максимальное число значений определяется размером мутации, заданным в параметрах хромосомы] и инвертирующую их значения с помощью метода Invert набора значений, определенного хромосомой. Эта операция требует хромосом, реализующих интерфейс GaMutableCode.

 

Схема - Результаты операции GaInvertMutation

Класс GaFlipMutation реализует операцию мутации, выбирающую N значений [максимальное число значений определяется размером мутации, заданным в параметрах хромосомы] и случайно устанавливает их значения с помощью метода GenerateRandom набора значений, определенного хромосомой. Эта операция требует хромосом, реализующих интерфейс GaMutableCode.

 

Схема - Результаты операции GaFlipMutation

Встроенные операции селекции

Встроенные операции селекции расположены в пространстве имен Population::SelectionOperations.

 

Схема – Операции селекции GaSelectBest и GaSelectWorst

Класс GaSelectBest реализует операцию селекции, выбирающую N [определено размером селекции в параметрах операции] хромосом, являющимся лучшими в популяции. Если популяция несортированная, операция выбирает только хромосомы, входящие в сортированную группу лучших хромосом популяции.

Схема – Операции GaSelectRouletteWheel и GaSelectTournament

Класс GaSelectRouletteWheel реализует операцию селекции, выбирающую хромосомы исходя из их значения пригодности. Значения пригодности хромосом используются для вычисления их вероятности селекции. Если генетический алгоритм максимизирует пригодность, большая пригодность означает большую вероятность селекции. Если генетический алгоритм минимизирует пригодность, меньшая пригодность означает большую вероятность селекции. Операция требует сортированную популяцию. Если популяция имеет определенную операцию масштабирования, селекция использует масштабированные значения пригодности; в противном случае используются необработанные значения пригодности. Эта операция селекции может выбрать отдельного родителя более одного раза, что может создать проблемы для некоторых операций замены. Во избежание этого GaSelectRouletteWheel использует класс GaSelectDuplicatesParams для своих параметров, чтобы контролировать дубликаты в наборе результатов селекции.

GaSelectTournament использует метод, подобный GaSelectRouletteWheel. Он выполняет N [определено параметрами операции] селекций "колеса рулетки" для единственного места в наборе результатов селекции. Лучшая хромосома из выбранных помещается в набор результатов. Этот процесс повторяется, чтобы выбрать всех родителей. Операция использует класс GaSelectTournamentParam для своих параметров.

 

Схема - Операции GaSelectRandom и GaSelectRandomBest

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

GaSelectRandomBest работает так же, как GaSelectRandom, но выбирает больше родителей, чем определено параметрами; затем она обрезает набор результатов до желаемого размера селекции, оставляя только лучших родителей в наборе. Эта операция использует класс GaRandomBestParams, определяющий число родителей, выбираемых перед обрезкой.

Встроенные операции спаривания

Встроенные операции спаривания расположены в пространстве имен Population::CouplingOperations.

 

Схема – Встроенные операции спаривания

Операция GaSimpleCoupling принимает первые два родителя из набора результатов селекции и затем вырабатывает две хромосомы потомства посредством операций кроссовера, и каждый родитель привязывается к потомку, затем она принимает следующих двух родителей, и так далее... Если все родители были использованы, но надо выработать больше потомков, операция заново запускается с начала набора результатов селекции, пока не выработается достаточно потомков. Это спаривание использует класс GaCouplingParams для своих параметров.

 

Схема - Операция GaSimpleCoupling

 

Схема – Встроенные операции спаривания

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

 

Схема - Операция GaCrossCoupling

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

 

Схема - Операция GaInverseCoupling

Операция GaRandomCoupling последовательно берет первых родителей из результатов селекции, а вторые родители выбираются случайно. Если все родители были использованы как первые родители, но надо выработать больше потомков, операция заново запускается с начала, пока не выработается достаточно потомков.

 

Схема - Операция GaRandomCoupling

Операция GaBestAlwaysCoupling всегда берет хромосому с лучшим значением пригодности в наборе результатов селекции в качестве первого родителя, а вторые родители берутся последовательно. Если все родители были использованы, но надо выработать больше потомков, операция заново запускается с начала, пока не выработается достаточно потомков.

 

Схема - Операция GaBestAlwaysCoupling

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


Встроенные операции замены

Встроенные операции замены расположены в пространстве имен Population::ReplacementOperations.

 

Схема - Операции GaReplaceWorst и GaReplacBest

Операция GaReplaceWorst заменяет худшие хромосомы в популяции на хромосомы потомства из предоставленного набора результатов спаривания. Если популяция не отсортирована, операция заменяет только хромосомы, отсортированные в худшей сортированной группе популяции. Эта операция использует класс GaReplacementParams для своих параметров.

Операция GaReplaceBest работает так же, как GaReplaceWorst, но заменяет лучшие хромосомы в популяции.

 

Схема - Операции GaReplaceParents и GaReplaceRandom

Операция GaReplaceParents заменяет родителей хромосом потомства в предоставленном наборе результатов спаривания. Как сказано, операция спаривания хранит информацию о родителе хромосомы в наборе результатов спаривания. Если используется эта операция, операция селекции не должна выбирать одну и ту же хромосому более одного раза, и операция спаривания не должна привязывать одного родителя к нескольким потомкам.

Операция GaReplaceRandom случайно выбирает заменяемые хромосомы.

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

Встроенные операции масштабирования

Встроенные операции масштабирования расположены в пространстве имен Population::ScalingOperations.

 

Схема - Операции GaWindowScaling и GaNormalizationScaling

Операция GaWindowScaling вычисляет масштабированную пригодность путем вычитания пригодности худшей хромосомы из пригодности масштабируемой хромосомы [scaled_fitness = chromosome_fitness - worst_chromosome_fitness].

Операция GaNoramlizationScaling вычисляет масштабированную пригодность исходя из ранга хромосомы [scaled_fitness = population_size - chromosome_rank]. Она требует сортированной популяции.
Эти операции не требуют параметров.

 

Схема - Операции GaLinearScaling и GaExponentialScaling

Операция GaLinearScaling масштабирует значения пригодности путем линейного преобразования: scaled_fitness = a * fitness + b [a и b - коэффициенты масштабирования]. “a” и “b” высчитываются следующим образом:

if( min_f > ( factor * avg_f - max_f ) / factor - 1 )
{
    a = avg_f / ( avg_f - min_f  );
    b = -1 * min_f * avg_f / ( avg_f - min_f );
}
else
{
    a = ( factor - 1 ) * avg_f / ( max_f - avg_f );
    b = avg_f * ( max_f - factor * avg_f ) / ( max_f - avg_f );
}

•    min_f – значение пригодности худшей хромосомы в популяции
•    max_f - значение пригодности лучшей хромосомы в популяции
•    avg_f – среднее значение пригодности всех хромосом в популяции
•    factor - масштабный коэффициент [применяется для умножения средней пригодности, определяющей масштабированное значение пригодности лучшей хромосомы в популяции]

Эта операция не может работать с отрицательными значениями пригодности.

Операция GaExponentialScaling вычисляет масштабированную пригодность путем возведения значения пригодности хромосомы в заданную степень [заданную параметрами популяции].

Обе операции используют класс GaScaleFactorParams для своих параметров.

Встроенные операции условия остановки

Встроенные операции условия остановки расположены в пространстве имен Population::StopCriterias.

 

Схема – Классы GaGenerationCriteria и GaGenerationCriteriaParams

GaGenerationCriteria применяется для остановки генетического алгоритма, когда он достигает нужного числа генераций. Он использует класс GaGenerationCriteriaParams в качестве параметров.

 

Схема – Классы GaFitnessCriteria и GaFitnessCriteriaParams

GaFitnessCriteria решает, когда алгоритм должен остановиться, исходя из статистических данных алгоритма о значении пригодности [необработанном или масштабированном, таком как пригодность лучшей хромосомы, средняя пригодность или пригодность худшей хромосомы]. Перечисление GaFitnessCriteriaComparison определяет типы сравнений, используемых для сравнения нужного значения пригодности с заданной предельной величиной. GaFitnessCriteria использует класс GaFitnessCriteriaParams в качестве своих параметров.

 

Схема – Классы GaFitnessProgressCriteria и GaFitnessProgressCriteriaParams

GaFitnessProgressCriteria решает, когда алгоритм должен остановиться, исходя из прогресса статистических данных алгоритма о значениях пригодности. Это условие измеряет и отслеживает прогресс нужного значения во время генераций алгоритма. Если алгоритм не осуществляет нужный прогресс за одну генерацию после определенного числа генераций, условие приказывает алгоритму остановиться. Класс GaFitnessProgressCriteriaParams является параметром для этого условия. Класс параметров также хранит историю прогресса алгоритма.

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

Встроенные генетические алгоритмы расположены в пространстве имен Population::SimpleAlgorithms.

 

Схема - Встроенные генетические алгоритмы

Класс GaSimplemAlgorithm реализует генетический алгоритм с неперекрывающимися популяциями. Пользователь должен задать объект популяции [не инициализированный] при создании генетического алгоритма. Алгоритм реализует элитизм, и число сохраненных хромосом определяется параметрами алгоритма [класс GaSimpleAlgorithmParams]. Алгоритм работает следующим образом:
1.    создать копию заданного объекта популяции
2.    инициализировать предоставленный объект популяции
3.    выбрать родителей и выработать хромосомы потомства
4.    скопировать лучшую хромосому из текущей популяции [элитизм]
5.    вставить хромосомы потомства в лучшую популяцию
6.    проверить условие остановки [завершение при достижении]
7.    сменить объекты популяции и вернуться к шагу 3.

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

Алгоритм работает следующим образом:
1.    инициализировать предоставленный объект популяции
2.    выбрать родителей и выработать хромосомы потомства
3.    заменить старые хромосомы на потомство
4.    проверить условие остановки [завершение при достижении]
5.    сменить объект популяции и вернуться к шагу 2.

Заключительную часть данной серии вы найдете здесь.

форум разработчиков