Последовательная версия генетического алгоритма с турнирной схемой отбора

ga.cpp

#include <iostream>
#include <cmath>

using namespace std;

double frand() // вещественное случайное число в диапазоне [0,1)
{
	return double(rand())/RAND_MAX;
}

struct genom // структура для представления двоичного генома
{
	double* data; // геном
	int len; // длина генома
	genom() { data = 0; } 
	~genom() { if( data ) delete[] data; }
};

double eval(genom& x) // целевая функция 
{
	double sum = 0;
	for( int i=0; i<x.len; i++ )
		sum += fabs(x.data[i]);
	return sum/x.len;
}

void create(genom& A, int l) // создание новой особи со случайным геномом
{
	A.data = new double[l];
	A.len = l;
	for( int i=0; i<l; i++ )
		A.data[i] = 200*frand()-100; // случайный выбор гена 
}

void copy(genom& A, genom& B) // копирование генома одного индивида (для отбора)
{
	for( int i=0; i<A.len; i++ )
		B.data[i] = A.data[i];
}

void select(genom& A, genom& B) // отбор (турнирная схема) - поединок между двумя индивидами
{
	const double pwin = 0.75; // вероятность выживания лучшего в паре
	double fa = eval(A);
	double fb = eval(B);
	double p = frand();
	if( fa<fb && p<pwin || fa>fb && p>pwin )
		copy(A,B); // победил A
	else
		copy(B,A); // победил B
}

void crossover(genom& A, genom& B) // скрещивание двух индивидов (одноточечное)
{
	int n = A.len;
	int k = rand()%(n-1); // точка скрещивания
	for( int i=k+1; i<n; i++ )
		swap(A.data[i],B.data[i]);
}

void crossover2(genom& A, genom& B) // скрещивание двух индивидов (двухточечное)
{
	int n = A.len;
	int k = rand()%(n-2); // 1-ая точка скрещивания
	int l = k+1+rand()%(n-k-1); // 2-ая точка скрещивания 
	for( int i=k+1; i<=l; i++ )
		swap(A.data[i],B.data[i]);
}

void crossover3(genom& A, genom& B) // скрещивание двух индивидов (равномерное)
{
	const double pswap = 0.25;
	int n = A.len;
	for( int i=0; i<n; i++ )
		if( frand()<pswap ) 
		    swap(A.data[i],B.data[i]);
}

void mutate(genom& A) // мутация особи
{
    const double pmutate = 0.1; // вероятность мутации одного гена 
    double dx = 0.1; // степень мутации 
	for( int i=0; i<A.len; i++ )
		if( frand()<pmutate )
			A.data[i] += dx*(2*frand()-1); // мутация гена
}

void shuffle(genom* P, int size) // перемешивание популяции 
{
	for( int i=0; i<size; i++ )
		swap(P[i].data,P[rand()%size].data);
}

int main()
{
	const double pselect = 0.5; // вероятность выполнения поединка
	const double pcross = 0.5; // вероятность выполнения скрещивания
	int size = 4096; // размер популяции
	int len = 100; // длина генома (размер задачи)
	genom* P = new genom[size]; // создаем популяцию
	for( int i=0; i<size; i++ ) 
		create(P[i],len); 
	const int tmax = 600; // число итераций алгоритма
	double* best = new double[tmax]; // лучшие значения целевой функции на каждом шаге алгоритма
	double* average = new double[tmax]; // средние по популяции значения целевой функции 
	for( int t=0; t<tmax; t++ ) // основной цикл алгоритма
	{
		// отбор
		shuffle(P,size); 
		for( int i=0; i<size/2; i++ )
			if( frand()<pselect )
				select(P[2*i],P[2*i+1]);
		// скрещивание
		shuffle(P,size);
		for( int i=0; i<size/2; i++ )
			if( frand()<pcross )
				crossover2(P[2*i],P[2*i+1]);
		// мутация
		for( int i=0; i<size; i++ )
			mutate(P[i]);
		// сбор статистики - среднее и лучшее по популяции значения целевой функции
		average[t] = 0;
		best[t] = eval(P[0]);
		for( int i=0; i<size; i++ )
		{
			double f = eval(P[i]);
			average[t] += f;
			if( f<best[t] )
				best[t] = f;
		}
		average[t] /= size;
	}
	// печать статистики
	for( t=0; t<tmax; t+=10 )
		cout << t << " " << average[t] << " " << best[t] << endl;
	// освобождение динамической памяти
	delete[] best; 
	delete[] average;
	delete[] P; 
	return 0;
}