Библиотека генетических алгоритмов - часть 4 - Пример 4: Расписание занятий
ОГЛАВЛЕНИЕ
Страница 4 из 5
Пример 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 |
|
|
~ |
|
~ |
||||||||||||||||||
|
Linux |
~ |
|
|
~ |
~ |
||||||||||||||||||
|
Mac OS X |
~ |
|
|
~ |
~ |
||||||||||||||||||
|
*BSD |
~ |
~ |
|
~ |
~ |
||||||||||||||||||
|
Solaris |
~ |
~ |
|
~ |
|
||||||||||||||||||
|
|||||||||||||||||||||||
12Библиотека содержит набор директив препроцессора, управляющих процессом компиляции в соответствии с обнаруженным компилятором и целевой операционной системой.