Библиотека генетических алгоритмов - часть 3 - Встроенные операции [продолжение]

ОГЛАВЛЕНИЕ

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

Встроенные операции замены расположены в пространстве имен 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.

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