|
Первым делом посмотрим на заголовок класса:
#include <stdlib.h>
#include <time.h>
#define MAXPOP 25
struct gene {
int alleles[4];
int fitness;
float likelihood;
// Test for equality.
operator==(gene gn) {
for (int i=0;i<4;i++) {
if (gn.alleles[i] != alleles[i]) return false;
}
return true;
}
};
class CDiophantine {
public:
CDiophantine(int, int, int, int, int);
int Solve();
// Returns a given gene.
gene GetGene(int i) { return population[i];}
protected:
int ca,cb,cc,cd;
int result;
gene population[MAXPOP];
int Fitness(gene &);
void GenerateLikelihoods();
float MultInv();inverse.
int CreateFitnesses();
void CreateNewPopulation();
int GetIndex(float val);
gene Breed(int p1, int p2);
};
Существуют две структуры: gene и класс CDiophantine. gene используется для слежения за различными наборами решений. Создаваямая популяция - популяция ген. Эта генетическая структура отслеживает свои коэффециенты выживаемости и вероятность оказаться родителем. Также есть небольшая функция проверки на равенство, просто чтобы сделать кое-какой другой код покороче. Теперь по функциям:
Fitness function
вычисляет воэффициент выживаемости ( приспособленности - fitness) каждого гена. В нашем случае это - модуль разности между желаемым результатом и полученным значением. Этот класс использует две функции: первая вычисляет все коэффициенты, а вторая - поменьше (желательно сделать ее inline) вычисляет коэффициент для какого-то одного гена.
int CDiophantine::Fitness(gene &gn) {
int total = ca * gn.alleles[0] + cb * gn.alleles[1]
+ cc * gn.alleles[2] + cd * gn.alleles[3];
return gn.fitness = abs(total - result);
}
int CDiophantine::CreateFitnesses() {
float avgfit = 0;
int fitness = 0;
for(int i=0;i<MAXPOP;i++) {
fitness = Fitness(population[i]);
avgfit += fitness;
if (fitness == 0) {
return i;
}
}
return 0;
}
Заметим, что если fitness = 0, то найдено решение - возврат. После вычисления приспособленности (fitness) нам нужно вычислить вероятность выбора этого гена в качестве родительского.
Likelihood functions
Как и было объяснено, вероятность вычисляется как сумма обращенных коэффициентов, деленная на величину, обратную к коэффициенту данному значению. Вероятности кумулятивны (складываются), что делает очень легким вычисления с родителями. Например:
|
Хромосома |
Вероятность |
|
1 |
(1/84)/0.135266 = 8.80% |
|
2 |
(1/24)/0.135266 = 30.8% |
|
3 |
(1/26)/0.135266 = 28.4% |
|
4 |
(1/133)/0.135266 = 5.56% |
|
5 |
(1/28)/0.135266 = 26.4% |
В программе, при одинаковых начальных значениях, вероятности сложатся: представьте их в виде кусков пирога. Первый ген - от 0 до 8.80%, следующий идет до 39.6% (так как он начинает 8.8). Таблица вероятностей будет выглядеть приблизительно так:
|
Хромосома |
Вероятность (smi = 0.135266) |
|
1 |
(1/84)/smi = 8.80% |
|
2 |
(1/24)/smi = 39.6% (30.6+8.8) |
|
3 |
(1/26)/smi = 68% (28.4+39.6) |
|
4 |
(1/133)/smi = 73.56% (5.56+68) |
|
5 |
(1/28)/smi = 99.96%
(26.4+73.56) |
Последнее значение всегда будет 100. Имея в нашем арсенале теорию, посмотрим на код. Он очень прост: преобразование к float необходимо для того, чтобы избедать целочисленного деления. Есть две функции: одна вычисляет smi, а другая генерирует вероятности оказаться родителем.
float CDiophantine::MultInv() {
float sum = 0;
for(int i=0;i<MAXPOP;i++) {
sum += 1/((float)population[i].fitness);
}
return sum;
}
void CDiophantine::GenerateLikelihoods() {
float multinv = MultInv();
float last = 0;
for(int i=0;i<MAXPOP;i++) {
population[i].likelihood = last
= last + ((1/((float)population[i].fitness) / multinv) * 100);
}
}
Итак, у нас есть и коэффициенты выживаемости (fitness) и необходимые вероятности (likelihood). Можно переходить к размножению (breeding).
Breeding Functions
Функции размножения состоят из трех: получить индекс гена, отвечающего случайному числу от 1 до 100, непосредственно вычислить кросс-овер двух генов и главной функции генерации нового поколения. Рассмотрим все эти функции одновременно и то, как они друг друга вызывают. Вот главная функция размножения:
void CDiophantine::CreateNewPopulation() {
gene temppop[MAXPOP];
for(int i=0;i<MAXPOP;i++) {
int parent1 = 0, parent2 = 0, iterations = 0;
while(parent1 == parent2 || population[parent1]
== population[parent2]) {
parent1 = GetIndex((float)(rand() % 101));
parent2 = GetIndex((float)(rand() % 101));
if (++iterations > (MAXPOP * MAXPOP)) break;
}
temppop[i] = Breed(parent1, parent2); // Create a child.
}
for(i=0;i<MAXPOP;i++) population[i] = temppop[i];
}
Итак, первым делом мы создаем случайную популяцию генов. Затем делаем цикл по всем генам. Выбирая гены, мы не хотим, чтобы они оказались одинаковы (ни к чему скрещиваться с самим собой :), и вообще - нам не нужны одинаковые гены (operator = в gene). При выборе родителя, генерирем случайное число, а затем вызываем GetIndex. GetIndex использует идею кумулятивности вероятностей (likelihoods), она просто делает итерации по всем генам, пока не найден ген, содержащий число:
int CDiophantine::GetIndex(float val) {
float last = 0;
for(int i=0;i<MAXPOP;i++) {
if (last <= val && val <= population[i].likelihood) return i;
else last = population[i].likelihood;
}
return 4;
}
Возвращаясь к функции CreateNewPopulation(): если число итераций превосходит MAXPOP2,
она выберет любых родителей. После того, как родители выбраны, они скрещиваются: их индексы передаются вверх на функцию размножения (Breed). Breed function возвращает ген, который помещается во временную популяцию. Вот код:
gene CDiophantine::Breed(int p1, int p2) {
int crossover = rand() % 3+1;
int first = rand() % 100;
gene child = population[p1];
int initial = 0, final = 3;
if (first < 50) initial = crossover;
else final = crossover+1;
for(int i=initial;i<final;i++) {
child.alleles[i] = population[p2].alleles[i];
if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1);
}
return child;
}
В конце концов мы определим точку кросс-овера. Заметим, что мы нехотим, чтобы кросс-овер состоял из копирования только одного родителя. Сгенерируем случайное число, которое определит наш кросс-овер. Остальное понятно и очевидно. Добавлена маленькая мутация, влияющая на скрещивание. 5% - вероятность появления нового числа.
И, наконец...
Теперь уже можно взглянуть на функцию Solve(). Она всего лишь итеративно вызывает вышеописанные функции. Заметим, что мы присутствует проверка: удалось ли функции получить результат, используя начальную популяцию. Это маловероятно, однако лучше проверить.
int CDiophantine::Solve() {
int fitness = -1;
// Generate initial population.
srand((unsigned)time(NULL));
for(int i=0;i<MAXPOP;i++) {
for (int j=0;j<4;j++) {
population[i].alleles[j] = rand() % (result + 1);
}
}
if (fitness = CreateFitnesses()) {
return fitness;
}
int iterations = 0;
while (fitness != 0 || iterations < 50) {
GenerateLikelihoods();
CreateNewPopulation();
if (fitness = CreateFitnesses()) {
return fitness;
}
iterations++;
}
return -1;
}
Описание завершено. Пример использования был дан в предыдущем описании, а сам класс можно скачать тут.
|
