Введение

Модели естественных вычислений широко применяются в современной науке. Область их применения очень обширна, они используются для решения задач моделирования, искусственного интеллекта, распознавания образов, управления.

Одним из наиболее распространенных методов естественных вычислений являются генетические алгоритмы. Чтобы лучше разобраться, как эти алгоритмы устроены и как работают, было решно воспроизвести один из таких алгоритмов — генетический. Для того, чтобы применять какой-либо метод для решения конкретных задач этот метод необходимо освоить. Поэтому генетический алгоритм, рассмотренный в данной работе, не решает никакой конкретной задачи. Главными являются одновременно процесс и результат работы по созданию программы по моделированию и визуализации работы генетического алгоритма. Важен полученный программистский опыт.
Программа моделирует поведение популяции самых примитивных живых организмов. Эта программа вряд ли будет иметь какое-либо практическое применение, но она наглядно иллюстрирует принцип работы генетических алгоритмов.

Моделирование работы генетического алгоритма, в котором естественный отбор определяется условиями среды

Моделирование – метод научного познания объективного мира через построение и изучение моделей.

Визуализация – один из наиболее удобных для человека способов представления информации. Человеку удобнее воспринимать информацию, если она представлена графически, а не в виде большого массива ничего не значащих чисел, поэтому важной частью работы является графическое представление алгоритма.

Прежде чем использовать какой-либо метод, его нужно изучить и апробировать сначала на относительно простой задаче возможно несколько раз. Для программиста таким изучением является написание конкретных программ.

Для работы выбран язык программирования C++, так как этот язык является мощным, проверенным временем языком программирования. C++ получил широкое распространение среди программистов. Для визуализации использована открытая графическая библиотека OpenGL.

Цель и задачи

Цель работы — написать программу для моделирования работы и визуализации генетического алгоритма, в котором естественный отбор определяется в зависимости от условий среды.
Задачи

1. Провести анализ источников информации.
2. Изучить основные понятия, связанные с генетическими алгоритмами
3. Создать биологический вид примитивных живых организмов.
4. Создать систему взаимодействия организмов друг с другом.
5. Организовать жизненный цикл (рождение новых организмов, продолжительность жизни, размножение и смерть).
6. Создать движущий фактор эволюции.
7. Организовать отношения хищник-жертва.
8. В заключение нужно реализовать сбор статистических данных о популяции.

Создание вида

Программа написана на языке программирования C++ с использованием открытой графической библиотеки OpenGL.
Для представления биологического вида создан класс Bio, который включает в себя координаты, скорость, время жизни и другие параметры примитивного живого организма.

Поля класса Bio

public:
	Code_bio code; //генетический код
	float x,y,dx,dy; //координаты и скорость
	bool life; //жив или мертв
	float w,h; //линейные размеры
	int num; //личный отличительный номер 
	int lifetime; //время жизни
	float range; //радиус обнаружения хищника

В классе Bio предусмотрен конструктор (для создания объектов класса).

Bio(void)
{
	life=1; //оживление
	w=20; //размер по умолчанию
	h=20;
	num=rand()%10000;
	range=200;
	//srand(time(0)); //случайные координаты
	x=rand()%(winW-(int)w);
	y=rand()%(winH-(int)h);
	//srand(time(0));
	dx=rand()%8-4; //случайная скорость
	dy=rand()%8-4;
	lifetime=0;
}

Помимо конструктора необходимо создать функцию set(int a, int b), с помощью которой можно будет вручную задавать координаты создаваемого объекта.

void set(int a,int b){
	x=a;
	y=b;
	life=true;
	dx=rand()%8-4;
	dy=rand()%8-4;
	}

Для имитации случайного движения вводим функцию turn(), которая будет в каждый момент времени поворачивать объект на случайный угол влево или вправо.

inline void turn(float vect, int deg)
{
	if((dx!=0)||(dy!=0))
	{
		float grad;
		if((dx>=0)&&(dy<0))
		{
			dy=-dy;
			grad=atan(dx/dy)*180/pi;
			grad+=deg;
			dx=sin(grad*pi/180)*vect;
			dy=cos(grad*pi/180)*vect;
			dy=-dy;
		}
		if((dx>=0)&&(dy>=0))
		{
			grad=atan(dx/dy)*180/pi;
			grad=90-grad;
			grad+=deg;
			grad=90-grad;
			dx=sin(grad*pi/180)*vect;
			dy=cos(grad*pi/180)*vect;
		}
		if((dx<0)&&(dy<=0))
		{
			dy=-dy;
			dx=-dx;
			grad=atan(dx/dy)*180/pi;
			grad=90-grad;
			grad+=deg;
			grad=90-grad;
			dx=sin(grad*pi/180)*vect;
			dy=cos(grad*pi/180)*vect;
			dy=-dy;
			dx=-dx;
		}
		if((dx<0)&&(dy>=0))
			{
				dx=-dx;
				grad=atan(dx/dy)*180/pi;
				grad+=deg;
				dx=sin(grad*pi/180)*vect;
				dy=cos(grad*pi/180)*vect;
				dx=-dx;
			}
		}
	}

Для обработки столкновения объекта с краями экрана нужны функции collx() и colly().

inline void collx()
	{
		if(x-w/2<0)
		{
			x=winW-w/2;
		}
		if(x+w/2>winW)
		{
			x=w/2;
		}
	}

	inline void colly()
	{
		if(y-h/2<0)
		{
			y=h/2;
			dy=-dy;
		}
		if(y+h/2>winH)
		{
			y=winH-h/2;
			dy=-dy;
		}
	}
};

Теперь нужна только главная функция Draw(), которая будет изменять состояние объекта и отрисовывать его.

void Bio::Draw()
{
	if(life)
	{
		if(dx==0)dx=rand()%30/10+1;
		if(dy==0)dy=rand()%30/10+1;
		//УБЕГАЙ
		float min=range;
		bool ok=0;
		float x2,y2;
		list<Predator>::iterator i=preds.begin();
		for(;i!=preds.end();i++)
		{
			if(sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) )<min)
			{
				min=sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) );
				ok=1;
				x2=i->x;
				y2=i->y;
			}
		}
		if(ok)
		{
			runaway(code.maxspeed,x2,y2);
			turn(code.maxspeed,(rand()%(2*(int)code.maxturn+1)*10)/10-(int)code.maxturn);
		}
		else
		turn((rand()%(int)(code.maxspeed-code.minspeed+1)*10)/10+code.minspeed,
			(rand()%(2*(int)code.maxturn+1)*10)/10-(int)code.maxturn);
			x+=dx;
		collx();
		y+=dy;
		colly();
		//ОТРИСОВКА
		if(1)
		{
		        glBindTexture(GL_TEXTURE_2D,bio_tex[0]);
		        glBegin(GL_QUADS);
			glTexCoord2f(0,1); glVertex2f(x-w/2,y-h/2);
				glTexCoord2f(1,1); glVertex2f(x+w/2,y-h/2);
				glTexCoord2f(1,0); glVertex2f(x+w/2,y+h/2);
				glTexCoord2f(0,0); glVertex2f(x-w/2,y+h/2);
			glEnd();
		}
		//ДЕТИ
		makechild();
		//ПРОД. ЖИЗНИ
		lifetime++;
		if(lifetime>code.maxltime)
			life=0;
		//РОСТ
		w=lifetime/40+20;
		h=lifetime/40+20;
	}
}

На этом создание вида заканчивается. Теперь встает вопрос о хранении всех этих организмов (их ведь будет большое количество). Их количество также будет постоянно изменяться в результате действия жизненного цикла. Для их хранения хорошо подойдет динамический массив list.

list<Bio> bios;

Жизненный цикл

В результате первая задача выполнена. Далее нужно организовать жизненный цикл популяции и взаимодействие организмов друг с другом. Поскольку программа должна моделировать поведение самых примитивных организмов, то и взаимоотношения их будут самыми простыми. При столкновении двух особей, они будут умирать, и в случайных координатах будут появляться их дети (от 1 до 3). Учитывая вычислительные ресурсы обычного компьютера, программа сможет с нормальной скоростью обрабатывать до 200 организмов. Это количество недостаточно для существования стабильной популяции, поэтому чтобы число организмов не становилось слишком большим или слишком маленьким введено условие – если численность популяции меньше 50, рождается больше детей (от 1 до 4), если численность больше 50, размножение будет медленнее.

Для того чтобы генетический алгоритм работал, у каждой особи популяции должен быть свой генетический код. Для этого в программе создана отдельная структура кода. Каждый организм популяции имеет свой экземпляр этой структуры. Также необходима функция скрещивания, которая будет принимать генетические коды родителей и возвращать код ребенка. У этих примитивных существ в коде заложены только минимальная и максимальная скорости, максимальная продолжительность жизни и максимальный угол поворота.

struct Code_bio
{
	int maxltime;
	float minspeed,maxspeed;
	int maxturn;
};

inline Code_bio childcode(Code_bio c1, Code_bio c2)
{
	//СКРЕЩИВАНИЕ
	Code_bio c;
	c.maxltime=(c1.maxltime+c2.maxltime)/2;
	c.minspeed=(c1.minspeed+c2.minspeed)/2;
	c.maxspeed=(c1.maxspeed+c2.maxspeed)/2;
	c.maxturn=(c1.maxturn+c2.maxturn)/2;
	
	//МУТАЦИЯ
	c.maxltime+=c.maxltime/100*((rand()%(maxltime_mut*2+1))-maxltime_mut);
	c.maxspeed+=c.maxspeed/100*((rand()%(maxspeed_mut*2+1))-maxspeed_mut);
	c.minspeed+=c.minspeed/100*((rand()%(minspeed_mut*2+1))-minspeed_mut);
	c.maxturn+=c.maxturn/100*(rand()%(maxturn_mut*2+1)-maxturn_mut);
        return c;
}

В класс Bio теперь нужно добавить функцию размножения. Эта функция будет обнаруживать столкновения организмов, убивать их и создавать потомство.

void Bio::makechild()
{
	list<Bio>::iterator i=bios.begin();
	for(;i!=bios.end();i++)
	{
		if(num!=i->num)
		{
		if((lifetime>200)&&(i->lifetime>200))
		if(sqrt((x-i->x)*(x-i->x))+((y-i->y)*(y-i->y))<w+i->w)
			{
				life=0;
				i->life=0;
				int c;
				if(bios.size()<50)
					c=rand()%4+1;
				else c=rand()%3+1;
				for(int j=0;j<c;j++)
				{
					Bio b;
					b.code=childcode(code,i->code);
					bios.push_back(b);
				}
			}
		}
	}
}

В функцию отрисовки нужно тоже внести изменение: добавить размножение. Отрисовка всех объектов происходит в функции таймера с интервалом 20 мс. В этой же функции программа удаляет все мертвые особи (значение life которых равно false).

list<Bio>::iterator i=bios.begin();
for(;i!=bios.end();i++)
	i->Draw();
bios.remove_if([](Bio b) {return (b.life==0);}); //удаление мертвых

Хищник

Поскольку генетический алгоритм все-таки должен решать какую-то задачу, нужно поставить ему эту задачу. В данном случае задача будет заключаться в нахождении наиболее приспособленного организма. Популяция будет все время совершенствоваться в результате эволюции. Каждое следующее поколение будет лучше приспособлено к условиям окружающей среды. Необходимо создать движущий фактор эволюции, который будет отбирать наиболее приспособленные особи. Этим фактором будет хищник.

Хищников, как и жертв, может быть много. Класс хищника от класса Bio будет отличаться только тем, что хищники не будут уметь размножаться и умирать. Их количество будет всегда фиксированным на протяжении работы программы.

Поля класса Predator

public:
	float x,y,dx,dy,speed;
	bool life;
	float w,h;
	int num;
	int lifetime;
	float range;
	float hungry;

Конструктор по умолчанию и функция set() для ручного создания.

Predator(void)
{
	life=1;
	w=100;
	h=100;
	num=rand()%10000;
	range=250;
	speed=10.2;
	hungry=0;//1*1000/20;
	//srand(time(0));
	x=rand()%(winW-(int)w);
	y=rand()%(winH-(int)h);
	//srand(time(0));
	dx=rand()%8-4;
	dy=rand()%8-4;
	lifetime=0;
}

void set(int a,int b)
{
	x=a;
	y=b;
	life=true;
	dx=rand()%8-4;
	dy=rand()%8-4;
}

В свободное от еды время хищник будет совершать случайное движение. Его функция turn() для изменения направления ничем не отличается от аналогичного метода класса Bio. Для того, чтобы хищник мог догонять жертву, ему нужна функция aim(), которая будет принимать координаты жертвы и скорость, с которой надо ее догонять.

inline void aim(float vect, float x2, float y2)
{
	dx=((x2-x)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) );
	dy=((y2-y)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) );
}

В главной функции Draw(), если хищник голоден, он будет просматривать свое окружение, находить самую близкую жертву и гнаться за ней. Если он не голоден, он будет случайно двигаться по экрану.

inline void Draw()
{
	if(life)
	{
		if(dx==0)dx=rand()%30/10+1;
		if(dy==0)dy=rand()%30/10+1;
		//ПОИСК ЕДЫ
		bool ok=0;
		float x2,y2;
		if(hungry<=0)
		{
			float min=range;
			list<Bio>::iterator i=bios.begin();
			for(;i!=bios.end();i++)
			{
			if(sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) )<w/2+i->w/2-10)
				{
					i->life=0;
					hungry=0.01*1000/20;
				}
				else
				if(sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) )<min)
				{
					min=sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) );
					ok=1;
					x2=i->x;
					y2=i->y;
				}
			}
		}
		if(ok)
			aim(speed,x2,y2);
		else turn(6,(rand()%(2*15+1)*10)/10-15);
		x+=dx;
		collx();
		y+=dy;
		colly();
			
		//ОТРИСОВКА
		if(view)
		{
		glBindTexture(GL_TEXTURE_2D,pred_tex[0]);
		glBegin(GL_QUADS);
			glTexCoord2f(0,1); glVertex2f(x-w/2,y-h/2);
			glTexCoord2f(1,1); glVertex2f(x+w/2,y-h/2);
			glTexCoord2f(1,0); glVertex2f(x+w/2,y+h/2);
			glTexCoord2f(0,0); glVertex2f(x-w/2,y+h/2);
		glEnd();
		}
			
		//ПРОД. ЖИЗНИ
			
		//РОСТ
		//ГОЛОД
		hungry--;
	}
}

Осталось только создать динамический массив хищников.

list<Predator> preds;

Отношения хищник-жертва

Для того чтобы взаимоотношения между хищником и жертвой работали правильно, нужно научить жертву убегать от хищника. Иначе хищник будет просто съедать жертву и никакой эволюции происходить не будет. Для этого надо добавить в класс Bio метод runaway(). Он аналогичен методу преследования хищником жертвы, только направляет объект в противоположную сторону.

inline void runaway(float vect, float x2, float y2)
{
	dx=((x-x2)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) );
	dy=((y-y2)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) );
}

Теперь нужно окончательно модифицировать функцию Draw класса Bio. Помимо простого хаотичного движения надо добавить обнаружение хищника и бегство от него.

if(dx==0)dx=rand()%30/10+1;
	if(dy==0)dy=rand()%30/10+1;
	//УБЕГАЙ
	float min=range;
	bool ok=0;
	float x2,y2;
	list<Predator>::iterator i=preds.begin();
	for(;i!=preds.end();i++)
	{
		if(sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) )<min)
		{
			min=sqrt( (x-i->x)*(x-i->x)+(y-i->y)*(y-i->y) );
			ok=1;
			x2=i->x;
			y2=i->y;
		}
	}
	if(ok)
		runaway(code.maxspeed,x2,y2);
	else
	turn((rand()%(int)(code.maxspeed-code.minspeed+1)*10)/10+code.minspeed,
				(rand()%(2*code.maxturn+1)*10)/10-code.maxturn);

Вероятность поимки хищником быстрой жертвы меньше, чем вероятность поимки медленной. В результате этого быстрые особи будут лучше приспособлены к условиям среды, и постепенно будет наблюдаться увеличение средней скорости популяции.

Принцип действия эволюции

Чтобы эволюция заработала, необходимо было внести еще несколько важных моментов. Когда хищник начинает преследовать жертву, жертва убегает от него в противоположную сторону. Если скорость жертвы будет намного меньше скорости хищника, то эволюция происходить не будет, потому что тогда при незначительных эволюционных изменениях ее скорости хищник все равно догонит и съест жертву. Если же скорость жертвы будет больше скорости хищника, он не сможет догнать ее, разве только если загонит в угол. Остается только один вариант: скорость жертвы должна быть приблизительно равна скорости хищника. Тогда даже при самом небольшом эволюционном изменении скорости жертвы, у нее появится существенное преимущество по сравнению с остальными. У хищника будет меньше шансов догнать такую жертву.

Когда программа создает начальную популяцию, она всем особям задает одинаковые генотипы, в которых указаны одинаковые максимальные и минимальные скорости. Все параметры генотипов потомства рассчитываются, как среднее арифметическое параметров родителей. Например, максимальная скорость ребенка будет средним арифметическим средних скоростей родителей. Если генетический алгоритм запустить именно так, эволюция работать не будет. Все генотипы просто усреднятся и станут одинаковыми. Даже если начальную популяцию создать с разными генотипами, все равно эволюции не будет. Кроме естественного отбора и движущего фактора для эволюции нудна мутация. Все что нужно – это после вычисления среднего арифметического изменять его на плюс/минус 10%. Тогда некоторые особи в результате скрещивания будут рождаться быстрее, а некоторые – медленнее, и эволюция будет работать.

Во время работы программа раз в 10 секунд записывает в четыре файла общие показатели популяции: численность, среднюю, минимальную и максимальную скорости. Используя эти данные можно будет увидеть результат работы генетического алгоритма и сделать вывод об эволюции популяции.

Фрагмент собранных данных:

Численность, Мин. Скорость, Макс. Скорость, Ср. скорость:
45,00 1,01842 9,83393 5,42617
54,00 1,01048 10,214 5,61252
53,00 1,00726 10,4374 5,72231
51,00 0,932109 10,1463 5,53921
48,00 0,93236 10,6849 5,80864
45,00 0,908688 11,0295 5,96907
46,00 0,888795 11,1242 6,0065
51,00 0,894669 11,1927 6,04366
48,00 0,933062 11,679 6,30601
52,00 0,92753 11,9278 6,42764
54,00 0,899226 12,3086 6,6039
51,00 0,875113 12,52 6,69756
43,00 0,902515 12,84 6,87124

На основании этих данных выполняется построение графика:



На графике видно, что в результате эволюции средняя максимальная скорость всех организмов увеличилась в 10 раз. Это действительно колоссальный скачок эволюции организмов. Из этого графика можно также сделать вывод, что средняя минимальная скорость всех организмов не изменилась. Это связано с особенностями движения существ. В то время когда они не убегают от хищника, они просто бегают по экрану в случайных направлениях. При этом их скорость тоже подвержена случайному изменению. Она принимает случайное значение между их минимально возможной скоростью, заложенной в генотипе, и максимально возможной скоростью, так же заложенной в генотипе. Но когда эти организмы убегают от врага, они бегут со своей максимально возможной скоростью. Именно поэтому движущий фактор эволюции, который производит отбор самых приспособленных особей, изменяет только их максимально возможные скорости, что и показывает график.

Результаты и выводы

1. Создан искусственный биологический вид для работы генетического алгоритма.
2. Создана система взаимодействия организмов друг с другом.
3. Организован жизненный цикл (рождение новых организмов, продолжительность жизни, размножение и смерть).
4. В качестве движущего фактора эволюции создан хищник.
5. Организовано взаимодействие хищника и жертвы.
6. Собран пример статистических данных, который наглядно демонстрирует работу алгоритма и доказывает эволюцию созданной популяции.

Заключение

Созданная программа отвечает всем заявленным требованиям. На первый взгляд не выполняет никакой конкретной общественно-полезной задачи, но она наглядно демонстрирует принцип работы генетического алгоритма. Алгоритм, реализованный в этой программе, довольно прост, но, не поняв, как он работает, нельзя создать более сложный генетический алгоритм. Поэтому главная польза программы – опыт для ее автора и пример исследовательской попытки для таких же любознательных начинающих программистов.

В перспективе предполагается рассмотреть на практике параллельные алгоритмические модели генетических алгоритмов.

Литература

1. Ершов Н. М. Естесственные модели параллельных вычислений [Электронный ресурс] URL: naturalmodels.blogspot.ru (дата обращения 10.05.14).
2. Р. Лафоре «Объектно-ориентированное программирование в C++», 4-е издание, 2011г.
3. Б. И. Пахомов «C/C++ и MS Visual C++ 2012».