Библиотека генетических алгоритмов - часть 4 - Пример 3: Задача коммивояжера
ОГЛАВЛЕНИЕ
Пример 3: Задача коммивояжера
Снимок экрана – приложение TSP
Хромосома является массивом городов [указателей на объекты класса TspCity] в порядке их посещения. Ее реализует класс TspChromosome. Класс наследует GaMultiValueChromosome, чтобы реализовать пользовательскую инициализацию хромосомы путем переопределения метода MakeFromPrototype. Этот метод копирует города в код хромосом и затем меняет их местами. Этот класс также переопределяет метод MakeCopy и определяет копирующий конструктор.
class TspChromosome : public GaMultiValueChromosome<const TspCity*>
{
public:
TspChromosome(GaChromosomeDomainBlock<const TspCity*>* configBlock) :
GaMultiValueChromosome(configBlock) { }
TspChromosome(const TspChromosome& chromosome,
bool setupOnly) :
GaMultiValueChromosome<const TspCity*>(chromosome, setupOnly) { }
virtual GaChromosomePtr GACALL MakeCopy(bool setupOnly) const
{ return new TspChromosome( *this, setupOnly ); }
virtual GaChromosomePtr GACALL MakeNewFromPrototype() const;
int GACALL GetCityPosition(const TspCity* city) const;
};
Использование простой одноточечной или многоточечной операции кроссовера генерирует много неверных решений, что ухудшает производительность и результаты алгоритма. Во избежание генерации неверных решений алгоритм использует пользовательскую операцию кроссовера. Операция берет случайный город из одного родителя и копирует его в хромосому потомка. Затем она ищет города, соединенные с выбранным городом [в обоих родителях] и берет ближайший город [и копирует его в хромосому потомка], если он еще не взят. Он берется, если операция выбирает другой присоединенный город. Если взяты все присоединенные города, операция случайно выбирает не взятый город. Далее кроссовер использует этот город для такого же продления пути. Процесс повторяется, чтобы выбрать все города. Класс TspCrossover реализует эту операцию кроссовера:
class TspCrossover : 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; }
private:
inline void SelectNextCity(const TspCity* previousCity,
const TspCity** currentBestNextCity,
const TspCity* nextCity) const;
};
Алгоритм использует встроенную операцию GaSwapMutation. Значение пригодности равняется длине пути. Класс TspFitnessOperation реализует операцию пригодности:
class TspFitness : 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; }
};
Параметры хромосом:
1. вероятность мутации: 3%
2. размер мутации: 2
3. исключительно улучшающие мутации: нет
4. вероятность кроссовера: 80%
5. число точек кроссовера: 1 [игнорируется]
CCB:
1. TspCrossover
2. TspSwapMutation
3. TspFitnessOperation
4. TspMinFitnessComparator
5. Набор значений не определен
Параметры популяции:
1. размер популяции: 100
2. популяция с изменяемым размером: нет [используется инкрементный алгоритм, не требующий популяции с изменяемым размером]
3. популяция отсортирована: да
4. масштабированная пригодность используется для сортировки: нет
5. отслеживание лучших хромосом: 0 [популяция уже отсортирована]
6. отслеживание худших хромосом: 0 [популяция уже отсортирована]
Конфигурация популяции:
1. Селекция GaSelectRandomBest, выбирающая 8 хромосом
2. GaSimpleCoupling, вырабатывающая 8 хромосом потомства
3. GaRandomReplaces, заменяющая 8 хромосом в каждой генерации, с размером элитизма в 10 хромосом
4. Нет операции масштабирования
Алгоритм использует GaFitnessProgressCriteria, потому что не известно точное условие окончания. Условие остановит алгоритм, если не сможет улучшить значение пригодности больше чем на 1 за 50000 генераций. Генетический алгоритм инкрементный.
Класс TSP является контейнером для объекта алгоритма. Класс TspCity представляет и хранит информацию о городе [например, его координаты и название]. Он имеет метод GetDistance, вычисляющий расстояния между городами. TspCities управляет коллекцией городов, введенной пользователем.