Библиотека генетических алгоритмов - часть 4 - Пример 4: Расписание занятий

Пример 4: Расписание занятий

 

Снимок экрана – приложение расписания занятий

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

Класс Schedule определяет представление хромосомы. Он наследует GaMultiValueChromosome.

class Schedule : public GaMultiValueChromosome<list<CourseClass*> >
{
    friend class ScheduleCrossover;
    friend class ScheduleMutation;
    friend class ScheduleFitness;
    friend class ScheduleObserver;

private:
    CourseClassHashMap _classes;

    CourseClassHashMap _backupClasses;

    // Флаги удовлетворения требований занятий
    mutable vector<bool> _criteria;

public:
    Schedule(GaChromosomeDomainBlock<list<CourseClass*> >* configBlock);

    Schedule(const Schedule& c, bool setupOnly);

    virtual ~Schedule() { }

    virtual GaChromosomePtr GACALL MakeCopy(bool setupOnly) const
        { return new Schedule( *this, setupOnly ); }

    virtual GaChromosomePtr GACALL MakeNewFromPrototype() const;

    virtual void GACALL PreapareForMutation();

    virtual void GACALL AcceptMutation();

    virtual void GACALL RejectMutation();

    // Возвращает ссылку на таблицу занятий
    inline const hash_map<courseclass*, />& GetClasses() const
        { return _classes; }

    // Возвращает массив флагов удовлетворения требований занятий
    inline const vector<bool>& GetCriteria() const
        { return _criteria; }

    // Возвращает ссылку на массив интервалов времени
    inline const vector<list<CourseClass*>>& GetSlots() const
        { return _values; }
};

Затем определяются операции кроссовера, мутации и пригодности:

class ScheduleCrossover : public GaCrossoverOperation
{
public:
    virtual GaChromosomePtr GACALL operator ()(
        const GaChromosome* parent1,
        const GaChromosome* parent2) const;

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

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

};

class ScheduleMutation : public GaMutationOperation
{
public:

    virtual void GACALL operator ()(
        GaChromosome* chromosome) const;

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

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

};

class ScheduleFitness : public GaFitnessOperation
{
public:

    virtual float GACALL operator ()(
        const GaChromosome* chromosome) const;

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

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

Дополнительную информацию о представлении хромосом и упомянутых операциях смотрите в этой статье.
Класс ScheduleTest является контейнером для объектов генетического алгоритма.

ScheduleTest::ScheduleTest()
{
  // инициализировать внутренние структуры библиотеки генетических алгоритмов
  GaInitialize();

  // создать параметры хромосомы
  // вероятность кроссовера: 80%
  // точки кроссовера: 2
  // нет "исключительно улучшающих мутаций"
  // вероятность мутации: 3%
  // число перемещенных занятий за мутацию: 2
  _chromosomeParams = new GaChromosomeParams(
    0.03F, 2, false, 0.8F, 2 );

  // создать CCB со следующими настройками:
  // нет набора значений
  // с генетическими операциями ScheduleCrossover, ScheduleMutation и
  // ScheduleFitness
  // установить сравнитель пригодности для максимизации значения пригодности
  // использовать ранее определенные параметры хромосомы
  _ccb = new GaChromosomeDomainBlock<list<courseclass* /> >(
    NULL, &_crossoverOperation, &_mutationOperation,
    &_fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMaxFitnessComparator" ),
    _chromosomeParams );

  // создать прототип хромосомы
  _prototype = new Schedule( _ccb );

  // создать параметры популяции
  // число хромосом в популяции: 100
  // популяция всегда имеет фиксированное число хромосом
  // популяция не отсортирована
  // используются непреобразованные(немасштабированные) значения пригодности
  // для сортировки и отслеживания хромосом
  // популяция отслеживает 5 лучших и 5 худших хромосомы
  GaPopulationParameters populationParams(
    100, false, true, false, 2, 0 );

  // создать параметры для операции селекции
  // селекция будет выбирать 16 хромосом,
  // но лишь 8 лучших из них будут сохраняться в набор результатов селекции
  // в наборе результатов не будет дубликатов хромосом
  GaSelectRandomBestParams selParam( 10, false, 16 );

  // создать параметры для операции замены
  // заменить 8 хромосом,
  // но оставить 5 лучших хромосом в популяции
  GaReplaceElitismParams repParam( 10, 2 );

  // создать параметры для операции спаривания
  // операция спаривания будет вырабатывать 8 новых хромосом
  // из выбранных родителей
  GaCouplingParams coupParam( 10 );

  // создать конфигурацию популяции
  // использовать определенные параметры популяции
  // использовать для сортировки такой же сравнитель, как и используемый хромосомами сравнитель
  // использовать операцию селекции, случайно выбирающую хромосомы
  // использовать операцию замены, случайно выбирающую подлежащие замене
  // хромосомы из популяции,
  // но оставляющую лучшие хромосомы
  // использовать простое спаривание
  // отключить масштабирование
  _populationConfig = new GaPopulationConfiguration( populationParams,
    &_ccb->GetFitnessComparator(),
    GaSelectionCatalogue::Instance().GetEntryData(
    "GaSelectRandom" ), &selParam,
    GaReplacementCatalogue::Instance().GetEntryData(
    "GaReplaceRandom" ), &repParam,
    GaCouplingCatalogue::Instance().GetEntryData(
    "GaSimpleCoupling" ), &coupParam,
    NULL, NULL );

  // создать популяцию
  // с ранее определенным прототипом хромосом
  // и конфигурацией популяции
  _population = new GaPopulation( _prototype, _populationConfig );

  // создать параметры для генетических алгоритмов
  // алгоритм будет использовать два рабочих процесса
  GaMultithreadingAlgorithmParams algorithmParams( 2 );
  // создать инкрементный алгоритм с ранее определенной популяцией
  // и параметрами
  _algorithm = new GaIncrementalAlgorithm(
    _population, algorithmParams );

  // создать параметры для условия остановки на основе значения пригодности
  // остановиться, когда лучшая хромосома достигнет значения пригодности 1
  GaFitnessCriteriaParams criteriaParams(
    1, GFC_EQUALS_TO, GSV_BEST_FITNESS );

  // установить условие остановки алгоритма (основанное на значении пригодности)
  // и его параметры
  _algorithm->SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaFitnessCriteria" ), &criteriaParams );

  // подписать наблюдателя
  _algorithm->SubscribeObserver( &_observer );
}

Переносимость, компиляция и подключение библиотеки генетических алгоритмов

Библиотека генетических алгоритмов поддерживает следующие компиляторы и платформы:

	Microsoft C++	Intel C++	GCC G++	Borland C++	Sun Studio C++
Windows	12	12	~	6	~
Linux	~	34	34	~	~
Mac OS X	~	34	34	~	~
*BSD	~	~	345	~	~
Solaris	~	~	5	~	8
- Компилятор поддерживается. ~ - Компилятор не поддерживается. 1 - Доступно в виде проекта Visual Studio. 2 - Компилируется в виде статической или динамической библиотеки (DLL). 3 - Доступен сборочный файл. 4 - Компилируется только как статическая библиотека. 5 - команда gmake используется для компоновки библиотеки. 6 - компилятор надо настроить на использование библиотеки STLport. 7 - команда dmake используется для компоновки библиотеки.

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