Библиотека генетических алгоритмов - часть 1 - Хромосомы
ОГЛАВЛЕНИЕ
Хромосомы
Хромосомы являются основными объектами в генетическом алгоритме. Хромосомы определены классом GaChromosome в этой библиотеке.
Схема – Класс GaChromosome
GaChromosome – интерфейс для фактических реализаций хромосом. Этот класс [интерфейс] определяет методы Crossover, Mutation, CalculateFitness и CompareFitness, представляющие вышеописанные генетические операции [мутация, кроссовер, операция пригодности и сравнитель пригодности].
Метод MakeCopy является виртуальным копирующим конструктором. Новые классы должны переопределить этот метод, и он должен возвращать новый экземпляр объекта хромосомы. Этот метод может копировать всю хромосому [набор заданных значений и закодированное решение], или он может копировать лишь набор заданных значений хромосомы [оставляя кодировку пустой]. Метод MakeFromPrototype создает новый объект хромосомы с таким же набором заданных значений, что и у текущего объекта, но случайно инициализирует кодировку решений.
Каждая хромосома имеет определенные параметры [такие как вероятность кроссовера и мутации]; эти параметры представлены классом GaChromosomeParams.
Схема - Класс GaChromosomeParams
GaChromosomeParams определяет вероятность мутации и кроссовера, размер мутации и число точек кроссовера, а также флаг "только улучшающая мутация". Конструктор по умолчанию инициализирует следующие параметры хромосомы по умолчанию:
• вероятность мутации: 3%
• размер мутации: 1 [изменяется только одно значение кодированного решения]
• разрешены только улучшающие мутации: да
• вероятность кроссовера: 80%
• число точек кроссовера: 1
Все классы параметров в библиотеке наследуют класс GaParameters.
Схема – Класс GaParameters
Этот класс [интерфейс] определяет метод Clone, являющийся виртуальным копирующим конструктором, и он должен возвращать указатель на новый объект параметров, являющийся копией текущего объекта.
Класс GaChromosomes является интерфейсом и не реализует никаких поведений. Однако несколько базовых свойств свойственно всем типам хромосом [хранение параметров хромосомы и значения пригодности]; эти свойства реализует класс GaDefaulChromosome. Кроме параметров, хромосомы могут иметь другие данные конфигурации [блок конфигурации хромосомы или CCB], и обычно эти данные одинаковы у всех хромосом в популяции. Хранение данных конфигурации хромосомы определяется классом GaChromosomeParamBlock.
Схема – Классы GaDefaultChromosome и GaChromosomeParamsBlock
Методы Crossover и Mutation класса GaDefaultChromosome выполняют эти генетические операции только с вероятностью, определенной параметрами хромосомы. Если надо выполнить операции, эти методы вызывают PerformCrossover и PerformMutation. Новые хромосомы, наследующие класс GaDefaultChromosome, должны переопределить PerformCrossover и PerformMutation, а не методы Crossover и Mutation.
Также этот класс вводит каркас для исключительно улучшающих мутаций. Перед выполнением операции мутации вызывается метод PrepareForMutation. Этот метод делает резервную копию старой хромосомы, после чего выполняется мутация. Затем сравниваются старая пригодность хромосомы [до мутации] и новая пригодность. Если мутация имеет улучшенную пригодность, она принимается, и вызывается метод AcceptMutation; в противном случае вызывается метод RejectMutation. Если не установлен флаг "только улучшающая мутация", мутации сразу принимаются без вызова упомянутых методов.
Операции кроссовера, мутации и пригодности могут быть реализованы путем наследования уже определенного класса, реализующего конкретные типы хромосом. Затем пользователь может переопределить методы PerformCrossover [или Crossover],PerformMutation [или Mutation] и CalculateFitness и реализовать конкретные операции для целевой задачи.
Библиотека генетических алгоритмов предоставляет другой способ добиться этого. Упомянутые генетические операции могут быть определены и реализованы в отдельных классах. Ссылки на объекты этих классов [называемые функторами] могут храниться в CCB. Это позволяет пользователю менять генетические операции во время выполнения [что невозможно при использовании ранее описанного метода].
Схема – Класс GaDynamicOperationChromosome и интерфейсы для генетических операций
GaDynamicOperationChromosome переопределяет методы PerformCrossover, PerformMutation, CalculateFitness и CompareFitnesses и направляет вызовы к функторам генетических операций, хранящимся в CCB.
CCB, представленный классом GaChromosomeOperationsBlock, хранит эти функторы.
GaCrossoverOperation – интерфейс для операции кроссовера. Определенные пользователем классы должны переопределять operator():
virtual GaChromosomePtr operator ()(
const GaChromosome* parent1,
const GaChromosome* parent2) const;
Параметры являются указателями на родителей, используемых операцией кроссовера. Оператор должен вернуть интеллектуальный указатель на созданную хромосому потомства.
GaMutationOperation – интерфейс для операции мутации. Определенные пользователем классы должны переопределять operator():
virtual void operator ()(GaChromosome* chromosome) const;
Этот оператор принимает [в качестве параметра] указатель на хромосому, над которой должна быть выполнена эта операция.
GaFitnessOperation – интерфейс для операции пригодности. Определенные пользователем классы должны переопределять operator():
virtual float operator ()(const GaChromosome* chromosome) const;
Этот оператор принимает [в качестве параметра] указатель на хромосому, над которой должна быть выполнена эта операция, и возвращает вычисленное значение пригодности хромосомы.
Последняя операция – сравнитель пригодности. Интерфейс для сравнителей пригодности определен классом GaFitnessComparator. Определенные пользователем классы должны переопределять operator():
virtual int operator ()
float fitness1,
float fitness2) const;
Этот оператор принимает два значения пригодности в качестве параметров и возвращает целое число:
1. -1, если первое значение пригодности меньше второго
2. 0, если эти два значения равны
3. 1, если первое значение пригодности больше второго
Все классы, реализующие генетические операции в библиотеке, наследуют класс GaOperation.
Схема – класс GaOperation
MakeParameters создает объект параметров, необходимый операции, и возвращает указатель на объект. Если операция не требует параметров, метод возвращает указатель NULL. Метод CheckParameters проверяет правильность предоставленных параметров и возвращает true в случае их правильности или false при их неправильности. Все генетические операции должны реализовывать эти два метода.
Библиотека генетических алгоритмов рассчитана на использование объектов генетических операций без внутреннего состояния [функторов]. Исходя из такого устройства, все встроенные операции лишены внутреннего состояния, но библиотека способна обрабатывать определенные пользователем операции, объекты которых обладают внутренним состоянием.