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

ОГЛАВЛЕНИЕ

Данная статья является завершающей частью из серии статей о библиотеке генетических алгоритмов и в ней мы приведем примеры использования библиотеки

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

По следующим ссылкам вы сможете найти предыдущие части данной серии:

- часть первая
- часть вторая
- часть третья

Примеры

Пользователь должен выполнить следующие шаги для построения генетического алгоритма с помощью данной библиотеки:
1.    Выбрать представление хромосом
2.    Определить операцию пригодности
3.    Выбрать операции кроссовера и мутации и сравнитель пригодности
4.    Выбрать операции селекции, спаривания, замены и масштабирования
5.    Выбрать тип алгоритма и условие остановки

Пример 1: Нахождение минимума f(x, y) = 5*x*sin(x) + 1.1*y*sin(y); x, y на интервале (0, 10)

Важно: перед использованием библиотеки генетических алгоритмов надо вызвать GaInitialize. Перед выходом из приложения надо вызвать GaFinalize.

Проще всего выбрать представление хромосомы с множеством значений, поддерживающее арифметические операции [класс Chromosome::Representation::GaMVArithmeticChromosome<double>].
После выбора представления хромосомы пользователь должен определить операцию пригодности.

class fFitness : public GaFitnessOperation
{
public:

    virtual float GACALL operator() (const GaChromosome*
        chromosome) const
    {
        const vector<double>& vals=
            dynamic_cast<const GaMVArithmeticChromosome<double>*>
            (chromosome)->GetCode();

        return 5*vals[0]*sin(vals[0])+1.1*vals[1]*sin(vals[1]);
    }

    virtual GaParameters* GACALL MakeParameters() const { return NULL; }

    virtual bool GACALL CheckParameters(const GaParameters&
        parameters) const { return true; }
};

Класс fFitness наследует класс GaFitnessOperation и переопределяет operator(), вычисляющий значение пригодности хромосомы путем оценки фактической математической функции.

На следующем шаге строится блок конфигурации хромосомы (CCB), содержащий:
1.    указатель на параметры хромосом
2.    указатель на функторы генетических операций [операции кроссовера, мутации, пригодности и сравнитель пригодности]
3.    указатель на набор значений, определяющий домен переменных x и y

Класс Chromosome::Representation::GaValueInterval<T> используется в качестве набора значений хромосомы, потому что домен переменных x и y является непрерывным интервалом (0, 10). GaIntervalValueSet требует 4 границы [нижняя и верхняя границы – для задания интервала оригинальных значений, и нижняя и верхняя границы – для задания интервала инвертированных значений] и генератор случайных значений.

GaValueIntervalBound<double /> valueInt(0,10);
GaValueIntervalBound<double /> invValueInt(0,10);
GaValueInterval<double /> valueSet(valueInt,invValueInt,
    GaGlobalRandomDoubleGenerator,false);

CCB должен быть:

fFitness fitnessOperation;
GaChromosomeDomainBlock<double> configBlock(&valueSet,
    GaCrossoverCatalogue::Instance().GetEntryData(
    "GaMultiValueCrossover"),
    GaMutationCatalogue::Instance().GetEntryData("GaFlipMutation"),
    &fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMinFitnessComparator"),
    &chromosomeParams);

Определяется CCB для использования операций GaMultiValuesCrossover и GaFlipMutation. Задается GaMinFitnessComparator, поскольку задача алгоритма – найти минимум функции.
Когда CCB определен, пользователь может построить прототипную хромосому:

GaMVArithmeticChromosome<double> prototype(2,&configBlock);

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

GaPopulationParameters populationParams(30,false,true,false,0,0);

Объект популяции использует стандартную конфигурацию, не считая того, что он меняет сравнитель сортировки:
1.    операции селекции: GaSelectRouletteWheel
2.    число выбираемых хромосом: 2
3.    операция спаривания: GaInverseCoupling
4.    вырабатывается потомков: 2
5.    операция замены: GaReplaceWorst
6.    заменяется хромосом: 2
7.    операция масштабирования: нет
8.    сравнитель сортировки: GaMaxFitnessComparator [стандартный] изменен на GaMinFitnessComparator

Теперь все готово для создания объекта популяции:

GaPopulationConfiguration populationConfig;
populationConfig.SetParameters(populationParams);
populationConfig.SetSortComparator(
    &configBlock.GetFitnessComparator());

GaPopulation population( &prototype, &populationConfig );

Этот пример использует инкрементный генетический алгоритм [класс GaIncrementalAlgorithm]. Создание объекта алгоритма:

GaMultithreadingAlgorithmParams algorithmParams(1);
GaIncrementalAlgorithm algorithm(&population,algorithmParams);

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

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

GaGenerationCriteriaParams criteriaParams(100000);

algorithm.SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaGenerationCriteria"),&criteriaParams);

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

Чтобы отслеживать процесс эволюции, пользователь должен задать объект наблюдателя для генетического алгоритма.

class fObserver : public GaObserverAdapter
{
    virtual void GACALL NewBestChromosome(const GaChromosome&
        newChromosome,const GaAlgorithm& algorithm)
    {
        const vector<double>& vals=
            dynamic_cast<const GaMVArithmeticChromosome<double>&>
            (newChromosome).GetCode();
        cout << "New chromosome found:\n";
        cout << "Fitness: " << newChromosome.GetFitness() << endl;
        cout << "x: " << vals[0] << " y: " << vals[1] << endl;
    }

    virtual void GACALL EvolutionStateChanged(GaAlgorithmState
        newState,const GaAlgorithm& algorithm)
    {
        if(newState==GAS_RUNNING)
            cout << "start\n";
        else if(newState==GAS_CRITERIA_STOPPED)
            cout << "end";
    }
};

Регистрация наблюдателя:

fObserver observer;
algorithm.SubscribeObserver(&observer);

Запуск алгоритма:

algorithm.StartSolving(false);

Параметр StartSolving определяет, должен ли алгоритм продолжить ранее приостановленный процесс эволюции [true] или же запустить совершенно новый процесс [false].