Автор работы: Пользователь скрыл имя, 24 Сентября 2009 в 18:16, Не определен
Данная работы состоит в изучении теоретического аспекта использования генетических алгоритмов, а так же в практической реализации задачи с использованием генетического алгоритма
}
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;
}
Описание завершено.
2.
Листинг программы
#include <stdlib.h>
#include <time.h>
#include <iostream.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); // Constructor with coefficients for a,b,c,d.
int Solve(); // Solve the equation.
// Returns a given gene.
gene GetGene(int i) { return population[i];}
protected:
int ca,cb,cc,cd; // The coefficients.
int result;
gene population[MAXPOP];
int Fitness(gene &); // Fitness function.
void GenerateLikelihoods(); // Generate likelihoods.
float MultInv(); // Creates the multiplicative inverse.
int CreateFitnesses();
void CreateNewPopulation();
int GetIndex(float val);
gene Breed(int p1, int p2);
};
CDiophantine::CDiophantine(int
a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res)
{}
int CDiophantine::Solve() {
int
fitness = -1;
// Generate initial population.
srand((unsigned)time(
for(int i=0;i<MAXPOP;i++) { // Fill the population with numbers between
for (int j=0;j<4;j++) { // 0 and the result.
population[
}
}
if (fitness = CreateFitnesses()) {
return fitness;
}
int iterations = 0; // Keep record of the iterations.
while (fitness != 0 || iterations < 50) {// Repeat until solution found, or over 50 iterations.
GenerateLikelihood
CreateNewPopulatio
if (fitness = CreateFitnesses()) {
return fitness;
}
iterations++;
}
return -1;
}
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;
}
float CDiophantine::MultInv() {
float
sum = 0;
for(int i=0;i<MAXPOP;i++) {
sum += 1/((float)population[i].
}
return sum;
}
void CDiophantine::
float
multinv = MultInv();
float last = 0;
for(int i=0;i<MAXPOP;i++) {
population[i].likelihood
= last = last + ((1/((float)population[i].
}
}
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;
}
gene CDiophantine::Breed(int p1, int p2) {
int crossover = rand() % 3+1; // Create the crossover point (not first).
int
first = rand() % 100; // Which parent comes first?
gene
child = population[p1]; // Child is all first parent initially.
int initial = 0, final = 3; // The crossover boundaries.
if (first < 50) initial = crossover; // If first parent first. start from crossover.
else
final = crossover+1; // Else end at crossover.
for(int i=initial;i<final;i++) { // Crossover!
child.alleles[i] = population[p2].alleles[i];
if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1);
}
return child; // Return the kid...
}
void CDiophantine::
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 > 25) break;
}
temppop[i] = Breed(parent1, parent2); // Create a child.
}
for(i=0;i<MAXPOP;i++) population[i] = temppop[i];
}
void main() {
CDiophantine
dp(1,2,3,4,30);
int ans;
ans = dp.Solve();
if (ans == -1) {
cout << "No solution found." << endl;
} else {
gene gn = dp.GetGene(ans);
cout << "The solution set to a+2b+3c+4d=30 is: ";
cout << "a = " << gn.alleles[0] << "." << endl;
cout << "b = " << gn.alleles[1] << "." << endl;
cout << "c = " << gn.alleles[2] << "." << endl;
cout << "d = " << gn.alleles[3] << "." << endl;
}
}
Заключение
Мы с вами проделали большой путь, открывая для себя генетические алгоритмы, их, казалось бы, тривиальную и одновременно с этим гениальную идею, взятую из природы. По окончанию работы можно сделать выводы о том, что: во-первых, генетические алгоритмы являются универсальным методом оптимизации многопараметрических функций, что позволяет решать широкий спектр задач; во-вторых, они имеют множество модификаций и сильно зависят от параметров. Зачастую небольшое изменение одного из них может привести к неожиданному улучшению результата. Но следует помнить, что применение ГА полезно лишь в тех случаях, когда для данной задачи нет подходящего специального алгоритма решения.
Несмотря
на небольшое количество задач в
данной научно-исследовательской работе,
которое мы с вами рассмотрели: решение
Диофантова уравнения и задачу коммивояжера,
мы полностью подтверждаем гипотезу. Задачи
оптимизации успешно решаются при помощи
генетических алгоритмов.
Список
используемой литературы
Информация о работе Генетические алгоритмы и их практическое применение