Генетические алгоритмы в задачах классификации искусственных нейронных сетей
ОГЛАВЛЕНИЕ
Генетический алгоритм применяется для решения множества задач оптимизации, не подходящих для стандартных алгоритмов оптимизации, в том числе задач, в которых целевая функция с разрывами, недифференцируемая, стохастическая или сильно нелинейная. В данной статье показано применение GA в обучении искусственных нейронных сетей для целей классификации. Его преимущество заключается в том, что он ищет лучшее решение во всем пространстве в ущерб скорости, по сравнению с численными методами.
• Скачать демо - 99.6 Кб
• Скачать исходники - 25.2 Кб
Введение
Природа предоставляет присущие ей методы для решения задач оптимизации, называемые генетическими алгоритмами. Живые организмы эволюционируют, адаптируются к меняющимся условиям, спариваются и производят индивидуумов, еще более приспособленных, чем их предки. Приспособленность индивидуума обозначает его живучесть или более высокую пригодность для конкретной цели. Генетический алгоритм (GA) является методом решения задач оптимизации на базе естественного отбора – процесса, управляющего биологической эволюцией. Генетический алгоритм многократно изменяет популяцию отдельных решений. На каждом шаге генетический алгоритм случайно отбирает индивидуумов из текущей популяции в качестве родителей и использует их для производства потомков для следующего поколения. Сквозь последовательные поколения популяция 'эволюционирует' в сторону оптимального решения. Генетический алгоритм применяется для решения множества задач оптимизации, не подходящих для стандартных алгоритмов оптимизации, в том числе задач, в которых целевая функция с разрывами, недифференцируемая, стохастическая или сильно нелинейная. В данной статье показано применение GA в обучении искусственных нейронных сетей для целей классификации. Его преимущество заключается в том, что он ищет лучшее решение во всем пространстве в ущерб скорости, по сравнению с численными методами. Последние часто сходятся к локальным минимумам. GA и численные методы имеют свои плюсы и минусы и могут использоваться взаимозаменяемо для конкретных задач.
Подготовка
Требуется знание генетических алгоритмов. Для изучения темы посмотрите сайты: генетические алгоритмы, генетическое программирование, генетические алгоритмы на разговорном английском. Необходимо понимание процессов кроссовера, мутации и селекции для грамотного использования кода. Консольный интерфейс для нейронной сети и описание структуры файла находится в предыдущей статье: Искусственные нейронные сети с обратным распространением на C++.
Использование кода
Строка помощи консольного приложения позволяет использовать следующие параметры:
argv[1] t-train, r-run
argv[2] network conf file
argv[3] cls1 files [0.9]
argv[4] cls2 files [0.1]
argv[5] epochs num
argv[6] [population size 50]
argv[7] [crossover chance 2]
argv[8] [mutation chance 1000]
argv[9] [validation class]
argv[10] [test class]
argv[12] [validation TH 0.5]
argv[12] [validation type [mse]]
argv[13] [normalization]: [0-no], 1-minmax, 2-zscore,
3-softmax, 4-energy
argv[14] [error tolerance cls] +- 0.05 default
argv[1] r-run
argv[2] network conf file
argv[3] cls files
argv[4] [validation TH 0.5]
argv[5] [normalization]: [0-no], 1-minmax, 2-zscore, 3-softmax, 4-energy
ann1dn.exe t net.nn cls1 cls2 3000 [50]
[crossover rate] [mutation rate]
[tst.txt][val.txt][TH [0.5]][vtype [mse]]
[normalization [0]] [err [0.05]]
ann1dn.exe r net.nn testcls [TH [0.5]] [normalization [0]]
Единственным отличием от проекта искусственная нейронная сеть с обратным распространением на C++ является добавление специфичных параметров GA: 6, 7 и 8. В остальном все такое же. Они обозначают начальный размер популяции, вероятность кроссовера и вероятность мутации. Стандартные значения - 50, 2 и 1000. Частоты кроссовера и мутации означают, что есть шанс 1 из 2 для кроссовера генов для каждой хромосомы двух родителей, и вероятность мутации равна 1 из 1000 для мутации определенных битов гена в ходе процесса спаривания. Итак, можно начать обучение прямо сейчас:
>ann1dg.exe t iris.nn setosa.txt virgi.txt 200
В приложенном файле run.bat находится следующая строка команды для выполнения:
>ann1dg.exe t iris.nn setosa.txt virgi.txt 200 50 2 100 void void 0.5 0 2
Она использует размер популяции 50 организмов, с вероятностью кроссовера, равной 2, и вероятностью мутации, равной 100. Следующие параметры означают случайный отбор контрольной и тестовой выборок из обучающей выборки с использованием среднеквадратичной ошибки в качестве показателя перекрестной проверки и нормализацию Zscore входных данных. Нормализация необходима, если диапазон данных сильно отличается от предпочтительного диапазона; от -1.0 до 1.0 подходит для классификации нейронной сети.
Ниже представлен типичный процесс GA для классификации данных IRIS до setosa и versi от видов virgi:
loading data...
cls1: 100 cls2: 50 files loaded. size: 4 samples
validaton size: 25 12
validaton size: 26 13
normalizing zscore...
training...
epoch: 1 0.454 0.450 pop age:0 mean[0.00] fit:0.00
bOrg: 0.715 0.546 fit 9.68 age 0
epoch: 2 0.642 0.631 pop age:1 mean[1.00] fit:238.01
bOrg: 0.715 0.546 fit 9.68 age 1
epoch: 3 0.630 0.617 pop age:2 mean[1.64] fit:334.49
bOrg: 0.665 0.341 fit 11.63 age 0
epoch: 4 0.638 0.617 pop age:3 mean[2.18] fit:288.08
bOrg: 0.665 0.341 fit 11.63 age 1
epoch: 5 0.607 0.577 pop age:4 mean[2.48] fit:395.51
bOrg: 0.665 0.341 fit 11.63 age 2
epoch: 6 0.636 0.602 pop age:5 mean[2.90] fit:456.78
bOrg: 0.685 0.341 fit 11.80 age 0
epoch: 7 0.638 0.583 pop age:6 mean[3.34] fit:390.31
bOrg: 0.677 0.452 fit 12.09 age 0
epoch: 8 0.651 0.562 pop age:7 mean[3.52] fit:425.81
bOrg: 0.764 0.513 fit 12.71 age 0
epoch: 9 0.649 0.535 pop age:8 mean[3.45] fit:415.64
bOrg: 0.826 0.455 fit 17.96 age 0
epoch: 10 0.608 0.445 pop age:9 mean[3.02] fit:408.99
bOrg: 0.826 0.455 fit 17.96 age 1 vld: 9.71 (epoch 10) se:68.00 sp:100.00 ac:78.38
epoch: 11 0.650 0.445 pop age:10 mean[2.98] fit:463.34
bOrg: 0.826 0.455 fit 17.96 age 2 vld: 9.71 (epoch 10) se:68.00 sp:100.00 ac:78.38
epoch: 12 0.615 0.405 pop age:11 mean[3.24] fit:467.19
bOrg: 0.826 0.455 fit 17.96 age 3 vld: 9.71 (epoch 10) se:68.00 sp:100.00 ac:78.38
epoch: 13 0.666 0.454 pop age:12 mean[2.98] fit:532.92
bOrg: 0.826 0.455 fit 17.96 age 4 vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
epoch: 14 0.662 0.401 pop age:13 mean[3.19] fit:627.14
bOrg: 0.826 0.455 fit 17.96 age 5 vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
epoch: 15 0.667 0.390 pop age:14 mean[3.35] fit:517.49
bOrg: 0.711 0.216 fit 22.49 age 0 vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
epoch: 16 0.662 0.372 pop age:15 mean[3.08] fit:508.93
bOrg: 0.711 0.216 fit 22.49 age 1 vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
epoch: 17 0.638 0.339 pop age:16 mean[2.65] fit:732.92
bOrg: 0.711 0.216 fit 22.49 age 2 vld: 15.42 (epoch 13) se:88.00 sp:100.00 ac:91.89
epoch: 18 0.676 0.366 pop age:17 mean[3.27] fit:793.93
bOrg: 0.711 0.216 fit 22.49 age 3 vld: 33.02 (epoch 18) se:100.00 sp:100.00 ac:100.00
epoch: 19 0.648 0.333 pop age:18 mean[3.35] fit:741.40
bOrg: 0.711 0.216 fit 22.49 age 4 vld: 33.02 (epoch 18) se:100.00 sp:100.00 ac:100.00
...
...
epoch: 187 0.747 0.213 pop age:186 mean[1.85] fit:2343.14
bOrg: 0.778 0.243 fit 42.80 age 0 vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
epoch: 188 0.747 0.213 pop age:187 mean[2.23] fit:1630.09
bOrg: 0.778 0.243 fit 42.80 age 1 vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
epoch: 189 0.747 0.213 pop age:188 mean[2.17] fit:2050.81
bOrg: 0.778 0.243 fit 42.80 age 2 vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
epoch: 190 0.748 0.214 pop age:189 mean[2.36] fit:1899.64
bOrg: 0.778 0.243 fit 42.81 age 0 vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
epoch: 191 0.751 0.217 pop age:190 mean[2.41] fit:1692.95
bOrg: 0.778 0.243 fit 42.81 age 1 vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
epoch: 192 0.752 0.223 pop age:191 mean[2.00] fit:1869.26
bOrg: 0.778 0.243 fit 42.81 age 0 vld: 65.97 (epoch 183) se:100.00 sp:100.00 ac:100.00
epoch: 193 0.755 0.221 pop age:192 mean[2.00] fit:1965.02
bOrg: 0.778 0.243 fit 42.82 age 0 vld: 81.72 (epoch 193) se:100.00 sp:100.00 ac:100.00
epoch: 194 0.762 0.227 pop age:193 mean[2.42] fit:2118.48
bOrg: 0.778 0.243 fit 42.82 age 1 vld: 81.72 (epoch 193) se:100.00 sp:100.00 ac:100.00
epoch: 195 0.766 0.232 pop age:194 mean[2.63] fit:2538.75
bOrg: 0.778 0.243 fit 42.82 age 2 vld: 81.72 (epoch 193) se:100.00 sp:100.00 ac:100.00
epoch: 196 0.778 0.244 pop age:195 mean[2.66] fit:2140.18
bOrg: 0.778 0.243 fit 42.82 age 3 vld: 81.77 (epoch 196) se:100.00 sp:100.00 ac:100.00
epoch: 197 0.778 0.243 pop age:196 mean[2.86] fit:2140.25
bOrg: 0.778 0.243 fit 42.82 age 4 vld: 81.77 (epoch 196) se:100.00 sp:100.00 ac:100.00
epoch: 198 0.778 0.243 pop age:197 mean[2.76] fit:2311.59
bOrg: 0.778 0.243 fit 42.82 age 0 vld: 81.81 (epoch 198) se:100.00 sp:100.00 ac:100.00
epoch: 199 0.778 0.243 pop age:198 mean[2.52] fit:2226.04
bOrg: 0.778 0.243 fit 42.82 age 1 vld: 81.81 (epoch 198) se:100.00 sp:100.00 ac:100.00
epoch: 200 0.777 0.242 pop age:199 mean[2.49] fit:1583.92
bOrg: 0.778 0.243 fit 42.82 age 2 vld: 81.81 (epoch 198) se:100.00 sp:100.00 ac:100.00
training time: 00:00:00:781
classification results: maxacur.nn
train set: 49 25
sensitivity: 97.96
specificity: 96.00
+predictive: 97.96
-predictive: 96.00
accuracy: 97.30
validation set: 25 12
sensitivity: 100.00
specificity: 100.00
+predictive: 100.00
-predictive: 100.00
accuracy: 100.00
test set: 26 13
sensitivity: 88.46
specificity: 100.00
+predictive: 100.00
-predictive: 81.25
accuracy: 92.31
Вывод одиночной эпохи означает для примера последней эпохи 200: средний результат 0.777 популяции на обучающей выборке для позитивного класса, 0.242 – для негативного класса, возраст популяции – 199, средний возраст организмов – 2.49, средняя приспособленность – 1583.92 (обратная от MSE), bOrg – наиболее приспособленный организм с средним результатом 0.788 на обучающей выборке для позитивного класса, 0.243 – для негативного, с возрастом 2, и своими результатами классификации на контрольной выборке.
Для сравнения было выполнено несколько итераций обучения GA, со случайными частями обучающих данных IRIS, и была взята лучшая конфигурация частоты классификации. То же самое было повторено для нейронной сети с алгоритмом обучения с обратным распространением из статьи: Искусственные нейронные сети с обратным распространением на C++. Ниже представлены веса и частоты классификации сети. Видно, что GA достиг очень близких результатов по производительности в сравнении с алгоритмом обратного распространения:
Результаты GA:
4
4 3 2 1
0
1
-44.000000 0.115305
-22.000000 0.257352
-10.000000 0.057181
-1.000000 0.136029
-1.018195
1.106349
-0.252558
-3.816144
0.060086
2.665148
0.106655
-0.719681
1.192948
-2.096924
-0.999024
0.572130
-1.355700
0.017045
1.615307
-2.008180
-8154.750000
-0.141530
7.478271
-1.202083
0.817744
1.999939
-2.613441
-0.727891
-1.999817
14.607610
train set: 49 25
sensitivity: 100.00
specificity: 100.00
+predictive: 100.00
-predictive: 100.00
accuracy: 100.00
validation set: 25 12
sensitivity: 100.00
specificity: 100.00
+predictive: 100.00
-predictive: 100.00
accuracy: 100.00
test set: 26 13
sensitivity: 96.15
specificity: 100.00
+predictive: 100.00
-predictive: 92.86
accuracy: 97.44
Результаты алгоритма обратного распространения:
4
4 3 2 1
0
1
-43.000000 0.109332
-23.000000 0.251434
-11.000000 0.055665
-1.000000 0.133365
7.644542
1.920880
0.046209
-4.151631
-2.031714
-8.133764
1.372707
-1.903027
2.587456
2.505832
1.232619
-0.139417
0.577583
1.139807
1.212673
-1.549961
-4.962042
4.220874
-1.322594
1.052067
2.433295
-2.301689
0.902922
0.755153
-4.881694
2.221259
train set: 49 25
sensitivity: 97.96
specificity: 100.00
+predictive: 100.00
-predictive: 96.15
accuracy: 98.65
validation set: 25 12
sensitivity: 100.00
specificity: 100.00
+predictive: 100.00
-predictive: 100.00
accuracy: 100.00
test set: 26 13
sensitivity: 100.00
specificity: 100.00
+predictive: 100.00
-predictive: 100.00
accuracy: 100.00
Генетический алгоритм
Специфичные классы GA в проекте следующие:
• Gene
• Chromosome
• Organism
• Population
Они будут описаны в таком порядке.
Обычно для процессов классификации с участием чисел с плавающей точкой отдельный ген представляется этим числом, и оператор мутации прибавляет случайное значение к этому числу. Но в реальных процессах ген состоит из последовательности отдельных битов: 1 или 0. И мутация инвертирует случайный бит в гене. Инвертирование бита нельзя применять к числам с плавающей точкой, так как можно получить NaN или огромное число, приближающееся к пределам числа с плавающей точкой, и для классификаций нейронной сети типичный диапазон весов составляет от -1.0 до 1.0. Чтобы использовать целочисленное представление гена, но со значением с плавающей точкой, в качестве отдельного гена используется 32- битное целое число, значение с плавающей точкой которого получается путем деления старшего знакового слова на младшее знаковое слово. Необходимо только избегать нулевых слов, так как этот сценарий может привести к делению на нуль или нулевым коэффициентам в нейронной сети, что при селекции и мутации может привести к организмам с большинством нулевых генов без настоящей информации.
Класс Gene представлен ниже, и его конструктор использует случайную инициализацию гена или устраивает копию из другого гена.
Gene::Gene()
{
//если MAX_RAND=0x7fff, умножить на 2*rand()
unsigned short lo = 0xFFFF & (2 * rand());
while (!lo)
lo = 0xFFFF & (2 * rand());
unsigned short hi = 0xFFFF & (2 * rand());
while (!hi)
hi = 0xFFFF & (2 * rand());
m_gene = lo | hi << 16;
}
Gene::Gene(unsigned int gene): m_gene(gene)
{
}
class Gene
{
friend class Population;
friend class Chromosome;
public:
Gene(); //случайный ген
Gene(unsigned int gene); //копировать ген
inline float gene() const;
private:
Gene(const Gene& gene);
const Gene& operator=(const Gene& gene);
unsigned int m_gene; //32-битное число только младшее/старшее ненулевые значения
};
inline float Gene::gene() const
{
short lo = 0xFFFF & m_gene;
short hi = 0xFFFF & (m_gene >> 16);
return (float)hi / (float)lo;
}
friend используется как защищенный интерфейс protected, что не обязательно в той библиотеке.
Следующая дилемма была в том, как грамотно составить структуру организма, состоящего из хромосом из генов, то есть нейронной сети, состоящей из весов с плавающей точкой, чтобы спаривание двух родительских конфигураций нейронной сети давало улучшенного потомка для конкретной задачи классификации. Случайная перестановка весов из разных слоев не работает. Эта проблема была решена путем обозначения каждого отдельного нейрона в сети как хромосомы, состоящей из генов, представляющих входные соединения с нейроном, являющиеся весами с плавающей точкой. Таким образом, соответствующие хромосомы, то есть нейроны, используются в ходе процесса кроссовера. То есть первая хромосома (нейрон) в отобранном родителе (нейронной сети) обменивается своими весами с первой хромосомой второго отобранного родителя (нейронной сети), вторая хромосома – с соответствующей второй хромосомой из того родителя, и так далее. Таким образом, кроссовер разумен в том смысле, что нет обмена весов из нейронов последнего слоя с нейронами из первого слоя.
Целая нейронная сеть действует как организм, представленный классом Organism, а отдельные нейроны представлены как объект Chromosome с несколькими генами, представляющими несколько входных весовых соединений с этим нейроном. Следовательно, нейронная сеть состоит из 3 слоев из 10 5 1 нейрона, соответственно представленных организмом, состоящим из 5 + 1 = 6 хромосом с 5 * (10 + 1) + 1 * (5 + 1) = 55 + 6 = 61 суммарными генами. 1 добавленное является смещенным соединением. Хромосомы из первого слоя состоят из 11 генов, а хромосома последнего слоя имеет 6 генов. Хромосомы из первого слоя первого родителя обмениваются своими генами с аналогичными хромосомами первого слоя из второго родителя.
Класс Chromosome показан ниже:
Chromosome::Chromosome(int genes_number)
{
for (int g = 0; g < genes_number; g++)
m_genes.push_back(new Gene());
}
Chromosome::Chromosome(vector<Gene *> *genes)
{
for (int g = 0; g < (int)genes->size(); g++)
m_genes.push_back(new Gene(genes->at(g)->m_gene));
}
Chromosome::~Chromosome()
{
for (int g = 0; g < get_genes_number(); g++)
delete m_genes[g];
}
class Chromosome
{
friend class Population;
friend class Organism;
public:
Chromosome(int genes_number); //конструктор случайных генов
Chromosome(vector<Gene *> *pgenes); //конструктор копий генов
~Chromosome();
inline int get_genes_number() const;
inline const Gene *get_gene(int g) const;
private:
Chromosome(const Chromosome& chrom);
const Chromosome& operator=(const Chromosome& chrom);
vector<Gene *> m_genes;
};
inline int Chromosome::get_genes_number() const
{
return (int) m_genes.size();
}
inline const Gene *Chromosome::get_gene(int g) const
{
if (g > get_genes_number() - 1 || g < 0)
return 0;
return m_genes[g];
}
Он содержит вектор генов, и можно создать случайные гены или скопировать их из другой хромосомы.
Объект Organism походит на живой организм с множеством хромосом, состоящих из разного числа генов. Организм имеет возраст, число прожитых им популяций, и приспособленность для решения задачи классификации, как правило, обратн(ое/ая) от среднеквадратичной ошибки (MSE) на обучающей, контрольной или тестовой выборках. Можно создать его с использованием конкретной конфигурации нейронной сети, количества слоев с количеством нейронов на каждый слой, или скопировать существующий организм, скопировав его значения генов.
Organism::Organism(int layers_number, const int *neurons_per_layer):
m_chromosomes_number(0), m_genes_number(0), m_age(0), m_fitness(-1.0f)
{
for (int i = 0; i < USERDATA_SIZE; i++)
user_data[i] = 0.0f;
//например: 10 5 1 5хромосом из 10+1 генов, 1 хромосома из 5+1 генов
for (int l = 0; l < layers_number - 1; l++) { //цикл по слоям
for (int c = 0; c < neurons_per_layer[l+1]; c++) {
//инициализировать количеством генов+1 [в том числе 1 смещенный нейрон!]
Chromosome *pchr = new Chromosome(neurons_per_layer[l] + 1);
m_chromosomes.push_back(pchr);
for (int g = 0; g < neurons_per_layer[l] + 1; g++) {
m_genes_number++;
CHROM_GENE_INDEX pnt;
pnt.c = m_chromosomes_number;
pnt.g = g;
m_gene_index.push_back(pnt);
}
m_chromosomes_number++;
}
}
}
Organism::Organism(const Organism& org) : m_chromosomes_number(org.m_chromosomes_number),
m_genes_number(org.m_genes_number),
m_age(0), m_fitness(-1.0f)
{
for (int i = 0; i < USERDATA_SIZE; i++)
user_data[i] = org.user_data[i];
//скопировать индексы хромосомы/гена
for (int i = 0; i < m_genes_number; i++)
m_gene_index.push_back(org.m_gene_index[i]);
//скопировать гены из шаблона
for (int c = 0; c < m_chromosomes_number; c++)
m_chromosomes.push_back(new Chromosome(&org.m_chromosomes[c]->m_genes));
}
typedef struct _chrom_gene_index {
int c; //индекс хромосомы
int g; //индекс гена
} CHROM_GENE_INDEX, *PCHROM_GENE_INDEX;
#define USERDATA_SIZE 2
class Organism
{
friend class Population;
public:
//создать организм с определенной конфигурацией
Organism(int layers_number, const int *neurons_per_layer);
Organism(const Organism& org); //конструктор копий
~Organism();
inline int get_chromosomes_number() const;
inline const Chromosome *get_chromosome(int c) const;
inline CHROM_GENE_INDEX get_gene_index(int i) const;
inline float fitness() const;
inline void fitness(float fitness);
inline int age() const;
inline void age(int age);
//результаты на обучающей выборке
float user_data[USERDATA_SIZE];
private:
const Organism& operator=(const Organism& org);
//массив хромосомы
vector<Chromosome *> m_chromosomes;
//индекс отдельного гена m_gene_index.size() = m_genes_number
vector<CHROM_GENE_INDEX> m_gene_index;
int m_chromosomes_number; //суммарное число хромосом
int m_genes_number; //суммарное число генов
float m_fitness; //приспособленность организма
int m_age; //возраст организма
};
m_gene_index является массивом структур CHROM_GENE_INDEX. Он позволяет случайно выбрать отдельный ген из хромосом для процесса мутации. Он содержит только координаты отдельного гена в конкретной хромосоме.
Класс Population является вместилищем организмов.
#define PSZVAR 30+1 //вариация размера популяции 30% от m_meansize
////////////////Популяция////////////////////////////////////////////////////
class Population
{
enum CROSOVER_TYPE {ONEPOINT, TWOPOINT, UNIFORM, ARITHMETIC};
public:
Population(int mean_size, int layers_number, const int *neurons_per_layer);
~Population();
void populate(); //удалить непригодных, спарить родителей, произвести братьев
inline int crossover_rate() const;
inline void crossover_rate(int c_rate);
inline int mutation_rate() const;
inline void mutation_rate(int m_rate);
inline int population_size() const;
inline Organism *get_organism(int i);
inline const Organism *get_organism(int i) const;
inline int get_age() const;
inline float get_fitness() const;
inline float get_fittest_meanage() const;
private:
Population(const Population& pop);
const Population& operator=(const Population& pop);
vector<Organism *> m_organisms;
//частота кроссовера 1 шанс из m_crossover_rate для хромосомы
int m_crossover_rate;
//частота мутации 1 шанс из m_mutation_rate максимум=0x7FFF
int m_mutation_rate;
int m_mean_size; //жестко запрограммированный размер начальных наиболее //приспособленных родителей
int m_age; //возраст популяции
float m_fittest_meanage; //средний возраст наиболее приспособленных организмов
float m_fitness; //суммарная приспособленность текущей популяции
int m_parents_limit; //размер текущей популяции организмов родителей
int m_offsprings_limit; // размер текущей популяции организмов потомков
int m_fittest_limit; //размер наиболее приспособленных из
//[m_parents_limit + m_offsprings_limit]
//получить случайных наиболее приспособленных
const Organism *run_roulette_wheel(float population_fitness) const;
//спарить родителей - 2 организма
Organism *mate_parents(const Organism *X, const Organism *Y) const;
};
Population::Population(int mean_size, int layers_number,
const int *neurons_per_layer): m_mean_size(mean_size),
m_age(0), m_fittest_meanage(0.0f), m_fitness(0.0f),
m_crossover_rate(2), m_mutation_rate(1000)
{
srand((unsigned int)time(0));
//максимальный размер родителей/потомков
//средний размер +/- N% родителей
float a = float(short(0xFFFF & (2 * rand())) % PSZVAR) / 100.0f;
m_parents_limit = m_mean_size + int(a * (float)m_mean_size);
// потомки
float b = float(short(0xFFFF & (2 * rand())) % PSZVAR) / 100.0f;
m_offsprings_limit = m_mean_size + int(b * (float)m_mean_size);
// размер наиболее приспособленных
float f = float(short(0xFFFF & (2 * rand())) % PSZVAR) / 100.0f;
m_fittest_limit = m_mean_size + int(f * (float)m_mean_size);
//инициализировать популяцию, в том числе организмы родителей/потомков
for (int i = 0; i < (m_parents_limit + m_offsprings_limit); i++) {
Organism *porg = new Organism(layers_number, neurons_per_layer);
m_organisms.push_back(porg);
}
}
Она инициализируется таким образом:
//загрузить сеть ANN(искусственная нейронная сеть)/////////////////////////////
ann = new ANNetwork(argv[2]);
if (ann->status() < 0) {
wprintf(L"failed to load network: %s", argv[2]);
exit(1);
}
//...
//инициализировать код GA/////////////////////////////////
int *cnf = new int[ann->get_layers_number()];
for (int i = 0; i < ann->get_layers_number(); i++)
cnf[i] = ann->get_layer(i)->get_neurons_number();
//индивидуумы parents_number конфигурации ANN
gpop = new Population(parents_number, ann->get_layers_number(), cnf);
gpop->crossover_rate(crossover_rate);
gpop->mutation_rate(mutation_rate);
delete[] cnf;
При конструировании будет создана начальная популяция родителей и потомков со случайными генами, и будет определен предел наиболее приспособленных организмов, переходящих в следующую популяцию, остальные погибают. Для размера популяции 50 будет создано 50+-15 родителей и потомков. Предел размера наиболее приспособленной популяции установлен в 50+-15. Например, 60 родителей и 48 потомков, всего 60 + 48 = 108 организмов. Если предел наиболее приспособленных установлен в 55, то после оценки приспособленности каждого организма на обучающих данных, менее приспособленные 108 - 55 = 53 организма будут удалены из популяции. И наиболее приспособленные 55 доживут до следующего поколения. Процесс повторяется, производя новых потомков, оценивая приспособленность на обучающих данных и удаляя неприспособленных индивидуумов.
void Population::populate()
//удалить неприспособленных, спарить популяцию
{
m_age++;
//процесс селекции
random_shuffle(m_organisms.begin(), m_organisms.end());
while (population_size() > m_fittest_limit) {
//пока число организмов превышает предел наиболее приспособленных
int ind = 0;
Organism *unfit = m_organisms[ind];
for (int i = 1; i < population_size(); i++) {
if (m_organisms[i]->m_fitness <= unfit->m_fitness) {
ind = i;
unfit = m_organisms[i];
}
}
delete unfit;
m_organisms.erase(m_organisms.begin() + ind);
}
m_parents_limit = m_fittest_limit; //потомки становятся родителями
m_fittest_meanage = 0.0f;
m_fitness = 0.0f;
//увеличить возраст наиболее приспособленных индивидуумов
for (int i = 0; i < population_size(); i++) {
m_organisms[i]->m_age++;
m_fitness += m_organisms[i]->m_fitness;
m_fittest_meanage += m_organisms[i]->m_age;
}
m_fittest_meanage /= (float)population_size();
//спарить наиболее приспособленных индивидуумов
vector<Organism *> siblings;
float b = float(short(0xFFFF & (2 * rand())) % PSZVAR) / 100.0f;
//размер потомков
m_offsprings_limit = m_mean_size + int(b * (float)m_mean_size);
float f = float(short(0xFFFF & (2 * rand())) % PSZVAR) / 100.0f;
//предел размера наиболее приспособленных
m_fittest_limit = m_mean_size + int(f * (float)m_mean_size);
for (int s = 0; s < m_offsprings_limit; s++) {
//селекция по колесу рулетки
const Organism *X = run_roulette_wheel(m_fitness);
const Organism *Y = run_roulette_wheel(m_fitness);
while (X == Y)
Y = m_organisms[rand()%population_size()];
//до 5 потомков
int cnum = rand() % 5;
cnum++;
for (int i = 0; i < cnum; i++) {
siblings.push_back(mate_parents(X, Y));
s++;
if (!(s < m_offsprings_limit))
break;
}
}
//ввести братьев в популяцию
for (int s = 0; s < (int)siblings.size(); s++)
m_organisms.push_back(siblings[s]);
}
Для селекции используется метод колеса рулетки.
inline const Organism *Population::run_roulette_wheel(float population_fitness) const
//получить случайного наиболее приспособленного
{
float psum = 0.0f;
float ind = float(rand() % 100); //0...99
for (int i = 0; i < population_size(); i++) {
//prcnt колеса рулетки
psum += 100.0f * (m_organisms[i]->m_fitness / population_fitness);
if (psum > ind)
return m_organisms[i];
}
return m_organisms[population_size()-1];
}
Спаривание, за которым следует мутация, определено следующей функцией:
//mate_parents 2 организма: 1,2 точечный, однотипный, арифметический кроссовер
inline Organism *Population::mate_parents(const Organism *X,
const Organism *Y) const
{
Organism *child = new Organism(*X);
int type = rand() % 2;//4;
//выбрать тип кроссовера
switch (type) {
case ONEPOINT:
for (int c = 0; c < child->m_chromosomes_number; c++) {
if (m_crossover_rate > 1 && rand() % m_crossover_rate) continue;
int gnum = child->m_chromosomes[c]->get_genes_number();
if (gnum == 1) continue;
//поменять местами в случайной точке
int p = (rand() % (gnum - 1)) + 1;
for (int g = 0; g < p; g++)
child->m_chromosomes[c]->m_genes[g]->m_gene =
Y->m_chromosomes[c]->m_genes[g]->m_gene;
//или swap(child->...->m_genes[g],
// Y->...->m_genes[g]) адреса класса Gene
}
break;
case TWOPOINT:
for (int c = 0; c < child->m_chromosomes_number; c++) {
if (m_crossover_rate > 1 && rand() % m_crossover_rate) continue;
int gnum = child->m_chromosomes[c]->get_genes_number();
if (gnum <= 2) continue;
//поменять местами в 2 случайных точках только для 3 генов хромосом
int p1 = (rand() % (gnum - 1)) + 1;
int p2 = (rand() % (gnum - 1)) + 1;
while (p1 == p2)
p2 = (rand() % (gnum - 1)) + 1;
if (p1 > p2) swap(p1, p2);
for (int g = 0; g < p1; g++)
child->m_chromosomes[c]->m_genes[g]->m_gene =
Y->m_chromosomes[c]->m_genes[g]->m_gene;
for (int g = p2; g < gnum; g++)
child->m_chromosomes[c]->m_genes[g]->m_gene =
Y->m_chromosomes[c]->m_genes[g]->m_gene;
}
break;
//плохие кроссоверы
case UNIFORM:
for (int c = 0; c < child->m_chromosomes_number; c++) {
if (rand() % m_crossover_rate) continue;
for (int g = 0; g < child->m_chromosomes[c]->get_genes_number(); g++) {
unsigned int res = 0;
unsigned int gX = child->m_chromosomes[c]->m_genes[g]->m_gene;
unsigned int gY = Y->m_chromosomes[c]->m_genes[g]->m_gene;
for (int i = 0; i < 32; i++) { //32 бита на каждый ген
if (rand() % 2)
res |= (1 << i) & gY;
else
res |= (1 << i) & gX;
}
if ((0xFFFF&res) && (res >> 16))
child->m_chromosomes[c]->m_genes[g]->m_gene = res;
else
child->m_chromosomes[c]->m_genes[g]->m_gene = gY;
}
}
break;
case ARITHMETIC:
for (int c = 0; c < child->m_chromosomes_number; c++) {
if (m_crossover_rate > 1 && rand() % m_crossover_rate) continue;
for (int g = 0; g < child->m_chromosomes[c]->get_genes_number(); g++) {
unsigned int gX = child->m_chromosomes[c]->m_genes[g]->m_gene;
unsigned int gY = Y->m_chromosomes[c]->m_genes[g]->m_gene;
if ((0xFFFF&(gX&gY)) && ((gX&gY) >> 16))
child->m_chromosomes[c]->m_genes[g]->m_gene = gX & gY;
else
child->m_chromosomes[c]->m_genes[g]->m_gene = gY;
}
}
break;
}
//видоизменить потомков
if (rand() % m_mutation_rate == 0) {
CHROM_GENE_INDEX *pnt;
unsigned int gene, mask;
//получить случайное число хромосом (генов) для видоизменения
int N = rand() % (child->m_chromosomes_number);
for (int n = 0; n < N + 1; n++) {
//получить случайный CHROM_GENE_INDEX в массиве индексов хромосом/генов
pnt = &child->m_gene_index[rand()%child->m_genes_number];
gene = child->m_chromosomes[pnt->c]->m_genes[pnt->g]->m_gene;
mask = 1 << (rand() % 32);
if ((0xFFFF&(gene ^ mask)) && ((gene ^ mask) >> 16))
//ненулевые старшая/младшая части в гене
child->m_chromosomes[pnt->c]->m_genes[pnt->g]->m_gene = gene ^ mask;
//(dw &= ~маска; разумная операция)
}
}
return child;
}
Используются только 1 и 2 точечные кроссоверы, так как остальные склонны давать плохие результаты на задачах классификации, но можно поэкспериментировать: раскомментировать 4 и использовать его вместо 2:
int type = rand() % 4;