Генетические алгоритмы в задачах классификации искусственных нейронных сетей - Генетический алгоритм
ОГЛАВЛЕНИЕ
Генетический алгоритм
Специфичные классы 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;