Проблема заключается в следующем:
Имеется работающий генетический алгоритм, требуется дополнить его, чтобы он выполнял:
1)метод наискорейшего спуска
2) Переход по первому улучшению, т. е. к примеру в процессе работы алгоритма было выбрано некоторое колличество особей:
0100000000
0010000000
1000000000
0001000000
Путём инвертирования сначало первой особи находим первое более лучшшее решение и сразу начинаем просмотр окркстности из новой точки. Можно переходить только в допустимые точки.
Помогите пожалуйста.
меню:
Код:
#include <iostream.h>
#include "GA.h"
void main() {
GA dp(5,6,7,40);
int ans;
ans = dp.Solve();
if (ans == -1) {
cout << "Решений не найдено." << endl;
} else {
gene gn = dp.GetGene(ans);
cout << "Решение уравнения 5*x1+6*x2+7*x3=40:\n";
cout << "x1 = " << gn.alleles[0] << "." << endl;
cout << "x2 = " << gn.alleles[1] << "." << endl;
cout << "x3 = " << gn.alleles[2] << "." << endl;
}
}
Сам GA.h
Код:
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <string.h>
using std::string;
#define MAXPOP 10
struct gene {
int alleles[3];
int fitness;
float likelihood;
operator==(gene gn) {
for (int i=0;i<3;i++) {
if (gn.alleles[i] != alleles[i]) return false;
}
return true;
}
};
class GA {
public:
GA(int, int, int, int); // Конструктор для коэффициентов x1,x2,x3.
int Solve(); // Решаем уравнение.
// Возвращение этого гена.
gene GetGene(int i) { return population[i];}
protected:
int ca,cb,cc; // Коэффициенты
int result;
gene population[MAXPOP]; // Популяция
int Fitness(gene &); // Функция приспосабливаемости
void GenerateLikelihoods(); // Вычисляет вероятность выбора гена в качестве родительского
float MultInv();
int CreateFitnesses();
void CreateNewPopulation();
int GetIndex(float val);
int BinToDec(string bin);
string DecToBin(int val);
gene Breed(int p1, int p2);
};
GA::GA(int a, int b, int c, int res) : ca(a), cb(b), cc(c), result(res) {}
int GA::Solve() { //итеративно вызывает вышеописанные функции
int fitness = -1;
// Создание начальной популяции.
srand((unsigned)time(NULL));
for(int i=0;i<MAXPOP;i++) { // Заполняем популяцию числами от 0 до результата
for (int j=0;j<3;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;
}
int GA::Fitness(gene &gn) { //вычисляет коэффициент выживаемости ( приспособленности - fitness) каждого гена.
int total = ca * gn.alleles[0] + cb * gn.alleles[1] + cc * gn.alleles[2];
return gn.fitness = abs(total - result);
}
int GA::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 GA::MultInv() {
float sum = 0;
for(int i=0;i<MAXPOP;i++) {
sum += 1/((float)population[i].fitness);
}
return sum;
}
void GA::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);
}
}
int GA::GetIndex(float val) { //GetIndex использует идею кумулятивности вероятностей (likelihoods), она просто делает итерации по всем генам, пока не найден ген, содержащий число
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 GA::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; // Возврвщает ребенка
}
void GA::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 > 25) break;
}
temppop[i] = Breed(parent1, parent2);
}
for(i=0;i<MAXPOP;i++) population[i] = temppop[i];
}
int GA::BinToDec(string bin)//переводит из двоичных в десятичную
{
int val = 0;
int value_to_add = 1;
for (int i = bin.length(); i > 0; i--)
{
if (bin.at(i-1) == '1')
val += value_to_add;
value_to_add *= 2;
}
return val;
}
string GA::DecToBin(int val)//переводит из десятичной в двоичную
{
string bin,Temp;
while (val != 0)
{
Temp += ((val%2)+0x30);
val /= 2;
}
for (int i=0;i<Temp.size();i++)
bin += Temp[Temp.size()-(i+1)];
return bin;
}
