Библиотека генетических алгоритмов - часть 4 - Пример 2: Сравнение с образцом

Пример 2: Сравнение с образцом

 

Снимок экрана – приложение проверки образца

Этот пример реализует генетический алгоритм, пытающийся угадать последовательность символов. Пример определяет следующую последовательность символов:

const char pattern[] =
"        GGGGGGGGGGGGG               AAA               LLLLLLLLLLL             "
"     GGG::::::::::::G              A:::A              L:::::::::L             "
"   GG:::::::::::::::G             A:::::A             L:::::::::L             "
"  G:::::GGGGGGGG::::G            A:::::::A            LL:::::::LL             "
" G:::::G       GGGGGG           A:::::::::A             L:::::L               "
"G:::::G                        A:::::A:::::A            L:::::L               "
"G:::::G                       A:::::A A:::::A           L:::::L               "
"G:::::G    GGGGGGGGGG        A:::::A   A:::::A          L:::::L               "
"G:::::G    G::::::::G       A:::::A     A:::::A         L:::::L               "
"G:::::G    GGGGG::::G      A:::::AAAAAAAAA:::::A        L:::::L               "
"G:::::G        G::::G     A:::::::::::::::::::::A       L:::::L               "
" G:::::G       G::::G    A:::::AAAAAAAAAAAAA:::::A      L:::::L         LLLLLL"
"  G:::::GGGGGGGG::::G   A:::::A             A:::::A   LL:::::::LLLLLLLLL:::::L"
"   GG:::::::::::::::G  A:::::A               A:::::A  L::::::::::::::::::::::L"
"     GGG::::::GGG:::G A:::::A                 A:::::A L::::::::::::::::::::::L"
"        GGGGGG   GGGGAAAAAAA                   AAAAAAALLLLLLLLLLLLLLLLLLLLLLLL";
const int patternSize=sizeof(pattern)-1;

В нее входят следующие символы: G,A,L,: и пробел.

Генетический алгоритм использует представление хромосомы Chromosome::Representation::GaMVArithmeticChromosome<double> с определенным доменом значений посредством класса Chromosome::Representation::GaMultiValueSet<char>.

GaMultiValueSet<char> valueSet(false);
valueSet.Add("GAL: ","     ",5);

Операция пригодности вычисляет процент совпадающих символов и возвращает это число в качестве значения пригодности хромосомы:

class pFitness : public GaFitnessOperation
{
public:

    virtual float GACALL operator()(const GaChromosome*
        chromosome) const
    {
        const vector<char>& v=
            dynamic_cast<const GaMultiValueChromosome&ltchar>*>
            (chromosome)->GetCode();

        int score=0;
        for(int i=0;i&ltpatternSize;i++)
        {
            if(v[i]==pattern[i])
            score++;
        }

        return (float)score/patternSize*100;
    }

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

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

CCB походит на CCB в предыдущем примере, не считая того , что он использует новую операцию пригодности и другой сравнитель пригодности, потому что его цель – максимизировать пригодность:

pFitness fitnessOperation;
GaChromosomeDomainBlock<char /> configBlock(&valueSet,
    GaCrossoverCatalogue::Instance().GetEntryData(
    "GaMultiValueCrossover"),
    GaMutationCatalogue::Instance().GetEntryData("GaFlipMutation"),
    &fitnessOperation,
    GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMaxFitnessComparator"),
    &chromosomeParams);

Прототипная хромосома:

GaMultiValueChromosome<char> prototype( patternSize, &configBlock );</char>

Этот пример использует генетический алгоритм с неперекрывающимися популяциями, вырабатывающий целую популяцию. Чтобы увеличить разнообразие выработанных хромосом, увеличивается число выбранных хромосом. Такой тип алгоритм требуют популяцию с изменяемым размером. Объект популяции и его конфигурация:

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

GaPopulationConfiguration populationConfig;
populationConfig.SetParameters(populationParams);
populationConfig.SetSortComparator(
    &configBlock.GetFitnessComparator());
populationConfig.Selection().GetParameters().SetSelectionSize(6);

GaPopulation population(&prototype, &populationConfig);

Как сказано, этот пример использует класс Algorithm::SimpleAlgorithms::GaSimpleAlgorithm для генетического алгоритма.

GaSimpleAlgorithmParams algorithmParams(10,2);
GaSimpleAlgorithm algorithm(&population,algorithmParams);

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

В данном примере известно точное условие окончания: когда алгоритм находит хромосому со значением пригодности 100 [100% совпадение]. Правильный критерий остановки Algorithm::StopCriterias::GaFitnessCriteria:

GaFitnessCriteriaParams criteriaParams(100,GFC_EQUALS_TO,
    GSV_BEST_FITNESS);
algorithm.SetStopCriteria(
    GaStopCriteriaCatalogue::Instance().GetEntryData(
    "GaFitnessCriteria"),
    &criteriaParams);

Наблюдатель алгоритма отображает лучшие хромосомы по мере их нахождения:

class pObserver : public GaObserverAdapter
{
public:
    virtual void GACALL NewBestChromosome(const GaChromosome&
        newChromosome,const GaAlgorithm& algorithm)
    {
        const vector<char>& v=
        dynamic_cast<const GaMultiValueChromosome<char>&>
            (newChromosome).GetCode();

        cout<<"Generatiron: "<<
            algorithm.GetAlgorithmStatistics().GetCurrentGeneration()
            <<endl;
        cout<<"Fitness: "<<newChromosome.GetFitness();
        cout<<"\n-------------------------\n";

        for(int i=0;i<v.size();i++)
        {
            if(!(i%78))
                cout<<endl;

            cout<<v[i];
        }
        cout<<"\n-------------------------\n";
    }

    virtual void GACALL EvolutionStateChanged(GaAlgorithmState
        newState,const GaAlgorithm& algorithm)
    {
        if(newState==GAS_CRITERIA_STOPPED)
            cout<<"end.";
    }
};

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

pObserver observer;
algorithm.SubscribeObserver( &observer );
Запуск эволюции:

algorithm.StartSolving(false);