Последнее время вокруг все больше разговоров об искусственном интеллекте, то там то тут звучат модные термины "нейросети" и "генетические алгоритмы". В прошлых проектах (НейроКачели, НейроБашня и N3uralV1s10n) мы уже создавали простейшие нейронные сети, разобрались с тем что это такое в первом приближении и как они работают. Похоже пришло время сделать тоже самое с генетическими алгоритмами.
Генетический алгоритм - это прежде всего алгоритм эволюционный. Его основная фишка взята из живой природы. При поиске оптимального решения задачи мы порождаем варианты, отбираем из них лучшие, "скрещиваем" между собой, получая решения с общими для "родителей" удачными свойствами.
Для того чтобы пощупать всю эту магию в действии мы применим ее к решению классической задачи робототехники - движению робота по черной линии, а точнее - к подбору параметров ПИД-регулятора для того, чтобы робот смог двигаться по линии быстрее и точнее.
Замечание: данный проект не несет в себе ни оттенка соревновательной составляющей. Наша основная цель не в том, чтобы "вывести" быстрого гонца по линии, мы хотим получить опыт использования алгоритмов генетического типа с целью дальнейшего их использования в близкой нам по духу хоббийной робототехнике.
Начнем с конструкции робота. Это традиционная двухмоторная тележка на базе LEGO Mindstorms NXT, в передней части установлено 4 датчика освещенности, два из которых (внутренних, подключенных к портам 2 и 3) используются ПИД-регулятором робота для движения по линии, а два внешних(подключенных соответственно к портам 1 и 4) - для контроля срыва с линии в процессе обучения. Инструкцию в формате LEGO Digital Designer можно скачать по ссылке.
Для реализации поиска лучших для данной трассы коэффициентов ПИД-регулятора с применением генетического алгоритма нам потребуется создавать в памяти экземпляры ПИД-регулятора и автоматизированно тестировать их на реальном роботе, оценивая результат на соответствие заданному условию - более длинный пройденный путь в единицу времени, соответственно выше скорость движения по линии, при этом срывы с трассы недопустимы.
Алгоритм в общем виде выглядит следующим образом:
Для создания первой популяции виртуальных роботов давайте, для начала, опишем пользовательскую структуру данных, которая будет использоваться в качестве шаблона для создания особей в популяции.
struct person
{
// у каждой особи должно быть имя, хотя бы codename
string name;
// номер поколения, в котором родилась данная особь
int generation;
// энергичность (быстрота) особи
int speed;
// скорость реакции
float reaction;
// мудрость (память) особи
float memory;
// интуиция (проницательность)
float intuition;
// степень доминантности особи
float dominance;
// пройденный особью путь за отведенный на тестирование промежуток времени
int path;
};
Теперь создадим первую популяцию на основе этого шаблона, в ней у нас будет 6 особей:
person robot[6];
Генерируем случайным образом свойства особей первой популяции:
for (int i=0;i<6;i++){
robot[i].name = "GeneLINEr_"+NumToStr(Random(1000));
robot[i].generation=1;
// энергичность (быстрота) особи 0..100
robot[i].speed = Random(70)+30;
// скорость реакции 0..3
robot[i].reaction = Random(3000)/1000;
// мудрость (память) особи 0..0,1
robot[i].memory = Random(100)/1000;
// интуиция (проницательность) 0..3
robot[i].intuition = Random(3000)/1000;
// степень доминантности особи не понятна до тестирования
robot[i].dominance = 0;
// пройденный особью жизненный путь = 0
robot[i].path = 0;
}
Далее начинается самое интересное. Начинаем условно бесконечный цикл смены поколений. В каждом поколении нам нужно испытать особей данного поколения и выявить из них самых быстрых и точных, не слетающих с трассы.
В роботе реализована функция ПИД-регулятора движения по линии, принимающий на вход параметры Kp, Ki, Kd, скорость робота, выполняющая 5 секундное движение по линии и возвращающая длину пройденного пути, сглаженного до криволинейной траектории.
long pid(float Pk,float Ik,float Dk,int speed){
long B=0;
long C=0;
long path=0;
long MC=MotorRotationCount(OUT_C);
long MB=MotorRotationCount(OUT_B);
long e = 0;
int porog=28;
float ERRo=0;
float ERR=0;
float u=0;
float z1=0;
float z2=0;
long tmp=CurrentTick();
int p;
int i;
int d;
while(CurrentTick()-tmp<=5000){
MC=MotorRotationCount(OUT_C);
MB=MotorRotationCount(OUT_B);
ERR=Sensor(IN_3)-Sensor(IN_2);
p=Pk*ERR;
d=Dk*(ERR-ERRo);
i=Ik*e;
if(i>10)i=10;
if(i<-10)i= -10;
u=p+i+d;
z1=speed-u;
z2=speed+u;
if(speed-u>100)z1=100;
if(speed-u<-100)z1=-100;
if(speed+u>100)z2=100;
if(speed+u<-100)z2=-100;
OnFwd(OUT_B,z1);
OnFwd(OUT_C,z2);
if(Sensor(IN_1)<=porog){
PlayTone(TONE_C5, MS_500);
RotateMotorEx(OUT_BC, 35, 100, 100, true, true);
go_to_line();
break;
}
if(Sensor(IN_4)<=porog){
PlayTone(TONE_C5, MS_500);
RotateMotorEx(OUT_BC, 35, 100, -100, true, true);
go_to_line();
break;
}
ERRo=ERR;
e+=ERR;
B=MotorRotationCount(OUT_B)-MB;
C=MotorRotationCount(OUT_C)-MC;
if(B>0 && C>0){
if(B<C){
path+=B;
}
else{
path+=C;
}
}
}
Off(OUT_BC);
return path;
}
void go_to_line(){
float P=1.0;
float D=1.0;
float ERRo=0;
float ERR=0;
float u=0;
while(abs(Sensor(IN_2)-Sensor(IN_3))>5){
int ERR=Sensor(IN_3)-Sensor(IN_2);
int u=P*ERR+D*(ERR-ERRo);
int z1=-u;
int z2=+u;
if(z1>100) z1=100;
if(z1<-100) z1=-100;
if(z2>100) z2=100;
if(z2<-100) z2=-100;
OnFwd(OUT_B,z1);
OnFwd(OUT_C,z2);
}
}
В случае, если в процессе 5-секундного испытания особи один из внешних датчиков видит линию, считается что робот сошел с трассы. При этом функция возвращает его на линию и особь выбывает из тестирования с результатом, который успела набрать до срыва, как правило рейтинг данной особи будет низким.
for (int i=5;i>=0;i--){
robot[i].path = pid(robot[i].reaction,
robot[i].memory,robot[i].intuition,robot[i].speed);
PlayTone(TONE_A4, MS_500);
}
После испытания всех особей текущего поколения ранжируем их в порядке убывания пройденного за время тестирования пути. Так как время на тест для каждой особи фиксировано - 5 секунд, соответственно у особей убывает и скорость. Будем использовать пузырьковую сортировку и "временную особь", для перестановки пар при ранжировании.
person robot_tmp;
for (int i=0;i<5;i++){
for (int j=0;j<(5-i);j++){
if(robot[j].path < robot[j+1].path){
robot_tmp = robot[j];
robot[j]=robot[j+1];
robot[j+1]= robot_tmp;
}
}
}
Чем выше у особи рейтинг, тем выше и доминантность данной особи, соответственно тем большую часть свойст данной особи унаследуют ее потомки (выше = ближе к 1):
for (int i=0;i<6;i++){
robot[i].dominance=i+1;
}
Две особи, самые слабые в популяции (5 и 6 в ранжированном списке) умирают, остальные дают потомство, порождая 6 особей новой популяции, наследующих черты родительских особей. В скрещивании участвуют доминантные признаки особей, давая соотношение унаследованных признаков. Унаследованный признак новорожденного кроме этого подвергается колебанию в 20%, для ускорения эволюции.
person newborn(person male, person female){
person newburn;
male.dominance = 1 - (male.dominance/(male.dominance+female.dominance));
female.dominance = 1 - male.dominance;
newburn.name = "GeneLINEr_"+NumToStr(Random(1000));
newburn.generation=male.generation+1;
if(male.speed>female.speed){
newburn.speed = male.speed;
}
else{
newburn.speed=female.speed;
}
newburn.reaction = male.reaction * male.dominance + female.reaction * female.dominance;
newburn.reaction =newburn.reaction *((Random(40)+80)/100.0);
newburn.memory = male.memory * male.dominance + female.memory * female.dominance;
newburn.memory =newburn.memory *((Random(40)+80)/100.0);
newburn.intuition = male.intuition * male.dominance + female.intuition * female.dominance;
newburn.intuition = newburn.intuition *((Random(40)+80)/100.0);
newburn.path = 0;
newburn.dominance = 0;
if(newburn.speed>max_speed){
max_speed=newburn.speed;
}
return newburn;
}
// новая популяция из 6 особей
person robot_next_generation[6];
robot_next_generation[0] = newborn(0,1);
robot_next_generation[1] = newborn(0,2);
robot_next_generation[2] = newborn(0,3);
robot_next_generation[3] = newborn(1,2);
robot_next_generation[4] = newborn(1,3);
robot_next_generation[5] = newborn(2,3);
Теперь в дело вступает природа и у одной, случайной особи происходит мутация - ее один, случайный, признак изменяется. Мутация чаще всего приводит к появлению неконкурентоспособных или вообще нежизнеспособных особей, однако очень полезна в ситуации, когда вектор развития эволюции пошел изначально не в том направлении. В результате мутации может появиться особь со свойством, выигрышно выделяющим ее на фоне остальных. Такая особь сразу же окажется на вершине рейтинга и даст начало новой династии.
// Мутация
void mutants(){
int property=Random(3);
int mutant=Random(5);;
if(mutant<4){
switch(property){
case 0:
robot_next_generation[mutant].speed = max_speed+5;
break;
case 1:
robot_next_generation[mutant].reaction =robot_next_generation[mutant].reaction *((Random(40)+80)/100.0);
break;
case 2:
robot_next_generation[mutant].memory =robot_next_generation[mutant].memory *((Random(40)+80)/100.0);
break;
case 3:
robot_next_generation[mutant].intuition = robot_next_generation[mutant].intuition *((Random(40)+80)/100.0);
break;
default:
break;
}
}
else{
switch(property) {
case 0:
robot_next_generation[mutant].speed = max_speed+5;
break;
case 1:
robot_next_generation[mutant].reaction = Random(3000)/1000;
break;
case 2:
robot_next_generation[mutant].memory = Random(100)/1000;
break;
case 3:
robot_next_generation[mutant].intuition = Random(3000)/1000;
break;
default:
break;
}
}
}
Теперь производим смену популяций. Дети сменяют родителей:
for(int i=0;i<6;i++){
robot[i]=robot_next_generation[i];
}
Теперь снова пришла пора испытать новое поколение, более приспособленное к решению поставленной задачи, оценить возросшую скорость,, выявить сильнейших и так до тех пор, пока результат не будет нас устраивать.
На этапе ранжирования можно сохранять информацию о свойствах особей в каждой популяции в файл.
byte fh;
int msg_len;
string logstr;
for(int i=0;i<6;i++){
logstr = robot[i].name;
logstr = logstr + ";" + NumToStr(robot[i].generation);
logstr = logstr + ";" + NumToStr(robot[i].reaction) +";"+NumToStr(robot[i].memory)+";"+NumToStr(robot[i].intuition);
logstr = logstr + ";" + NumToStr(robot[i].path)+";"+NumToStr(robot[i].speed);
msg_len = StrLen(logstr);
WriteLnString(fh, logstr, msg_len);
}
По данным, накопленным в файле в процессе работы программы, можно представить ход эволюции в виде наглядного графика (ось X - номер поколения, ось Y - средняя скорость особи):
Генетический алгоритм - это прежде всего алгоритм эволюционный. Его основная фишка взята из живой природы. При поиске оптимального решения задачи мы порождаем варианты, отбираем из них лучшие, "скрещиваем" между собой, получая решения с общими для "родителей" удачными свойствами.
Для того чтобы пощупать всю эту магию в действии мы применим ее к решению классической задачи робототехники - движению робота по черной линии, а точнее - к подбору параметров ПИД-регулятора для того, чтобы робот смог двигаться по линии быстрее и точнее.
Замечание: данный проект не несет в себе ни оттенка соревновательной составляющей. Наша основная цель не в том, чтобы "вывести" быстрого гонца по линии, мы хотим получить опыт использования алгоритмов генетического типа с целью дальнейшего их использования в близкой нам по духу хоббийной робототехнике.
Начнем с конструкции робота. Это традиционная двухмоторная тележка на базе LEGO Mindstorms NXT, в передней части установлено 4 датчика освещенности, два из которых (внутренних, подключенных к портам 2 и 3) используются ПИД-регулятором робота для движения по линии, а два внешних(подключенных соответственно к портам 1 и 4) - для контроля срыва с линии в процессе обучения. Инструкцию в формате LEGO Digital Designer можно скачать по ссылке.
Для реализации поиска лучших для данной трассы коэффициентов ПИД-регулятора с применением генетического алгоритма нам потребуется создавать в памяти экземпляры ПИД-регулятора и автоматизированно тестировать их на реальном роботе, оценивая результат на соответствие заданному условию - более длинный пройденный путь в единицу времени, соответственно выше скорость движения по линии, при этом срывы с трассы недопустимы.
Алгоритм в общем виде выглядит следующим образом:
struct person
{
// у каждой особи должно быть имя, хотя бы codename
string name;
// номер поколения, в котором родилась данная особь
int generation;
// энергичность (быстрота) особи
int speed;
// скорость реакции
float reaction;
// мудрость (память) особи
float memory;
// интуиция (проницательность)
float intuition;
// степень доминантности особи
float dominance;
// пройденный особью путь за отведенный на тестирование промежуток времени
int path;
};
Теперь создадим первую популяцию на основе этого шаблона, в ней у нас будет 6 особей:
person robot[6];
Генерируем случайным образом свойства особей первой популяции:
for (int i=0;i<6;i++){
robot[i].name = "GeneLINEr_"+NumToStr(Random(1000));
robot[i].generation=1;
// энергичность (быстрота) особи 0..100
robot[i].speed = Random(70)+30;
// скорость реакции 0..3
robot[i].reaction = Random(3000)/1000;
// мудрость (память) особи 0..0,1
robot[i].memory = Random(100)/1000;
// интуиция (проницательность) 0..3
robot[i].intuition = Random(3000)/1000;
// степень доминантности особи не понятна до тестирования
robot[i].dominance = 0;
// пройденный особью жизненный путь = 0
robot[i].path = 0;
}
Далее начинается самое интересное. Начинаем условно бесконечный цикл смены поколений. В каждом поколении нам нужно испытать особей данного поколения и выявить из них самых быстрых и точных, не слетающих с трассы.
В роботе реализована функция ПИД-регулятора движения по линии, принимающий на вход параметры Kp, Ki, Kd, скорость робота, выполняющая 5 секундное движение по линии и возвращающая длину пройденного пути, сглаженного до криволинейной траектории.
long pid(float Pk,float Ik,float Dk,int speed){
long B=0;
long C=0;
long path=0;
long MC=MotorRotationCount(OUT_C);
long MB=MotorRotationCount(OUT_B);
long e = 0;
int porog=28;
float ERRo=0;
float ERR=0;
float u=0;
float z1=0;
float z2=0;
long tmp=CurrentTick();
int p;
int i;
int d;
while(CurrentTick()-tmp<=5000){
MC=MotorRotationCount(OUT_C);
MB=MotorRotationCount(OUT_B);
ERR=Sensor(IN_3)-Sensor(IN_2);
p=Pk*ERR;
d=Dk*(ERR-ERRo);
i=Ik*e;
if(i>10)i=10;
if(i<-10)i= -10;
u=p+i+d;
z1=speed-u;
z2=speed+u;
if(speed-u>100)z1=100;
if(speed-u<-100)z1=-100;
if(speed+u>100)z2=100;
if(speed+u<-100)z2=-100;
OnFwd(OUT_B,z1);
OnFwd(OUT_C,z2);
if(Sensor(IN_1)<=porog){
PlayTone(TONE_C5, MS_500);
RotateMotorEx(OUT_BC, 35, 100, 100, true, true);
go_to_line();
break;
}
if(Sensor(IN_4)<=porog){
PlayTone(TONE_C5, MS_500);
RotateMotorEx(OUT_BC, 35, 100, -100, true, true);
go_to_line();
break;
}
ERRo=ERR;
e+=ERR;
B=MotorRotationCount(OUT_B)-MB;
C=MotorRotationCount(OUT_C)-MC;
if(B>0 && C>0){
if(B<C){
path+=B;
}
else{
path+=C;
}
}
}
Off(OUT_BC);
return path;
}
void go_to_line(){
float P=1.0;
float D=1.0;
float ERRo=0;
float ERR=0;
float u=0;
while(abs(Sensor(IN_2)-Sensor(IN_3))>5){
int ERR=Sensor(IN_3)-Sensor(IN_2);
int u=P*ERR+D*(ERR-ERRo);
int z1=-u;
int z2=+u;
if(z1>100) z1=100;
if(z1<-100) z1=-100;
if(z2>100) z2=100;
if(z2<-100) z2=-100;
OnFwd(OUT_B,z1);
OnFwd(OUT_C,z2);
}
}
В случае, если в процессе 5-секундного испытания особи один из внешних датчиков видит линию, считается что робот сошел с трассы. При этом функция возвращает его на линию и особь выбывает из тестирования с результатом, который успела набрать до срыва, как правило рейтинг данной особи будет низким.
for (int i=5;i>=0;i--){
robot[i].path = pid(robot[i].reaction,
robot[i].memory,robot[i].intuition,robot[i].speed);
PlayTone(TONE_A4, MS_500);
}
После испытания всех особей текущего поколения ранжируем их в порядке убывания пройденного за время тестирования пути. Так как время на тест для каждой особи фиксировано - 5 секунд, соответственно у особей убывает и скорость. Будем использовать пузырьковую сортировку и "временную особь", для перестановки пар при ранжировании.
person robot_tmp;
for (int i=0;i<5;i++){
for (int j=0;j<(5-i);j++){
if(robot[j].path < robot[j+1].path){
robot_tmp = robot[j];
robot[j]=robot[j+1];
robot[j+1]= robot_tmp;
}
}
}
Чем выше у особи рейтинг, тем выше и доминантность данной особи, соответственно тем большую часть свойст данной особи унаследуют ее потомки (выше = ближе к 1):
for (int i=0;i<6;i++){
robot[i].dominance=i+1;
}
Две особи, самые слабые в популяции (5 и 6 в ранжированном списке) умирают, остальные дают потомство, порождая 6 особей новой популяции, наследующих черты родительских особей. В скрещивании участвуют доминантные признаки особей, давая соотношение унаследованных признаков. Унаследованный признак новорожденного кроме этого подвергается колебанию в 20%, для ускорения эволюции.
person newborn(person male, person female){
person newburn;
male.dominance = 1 - (male.dominance/(male.dominance+female.dominance));
female.dominance = 1 - male.dominance;
newburn.name = "GeneLINEr_"+NumToStr(Random(1000));
newburn.generation=male.generation+1;
if(male.speed>female.speed){
newburn.speed = male.speed;
}
else{
newburn.speed=female.speed;
}
newburn.reaction = male.reaction * male.dominance + female.reaction * female.dominance;
newburn.reaction =newburn.reaction *((Random(40)+80)/100.0);
newburn.memory = male.memory * male.dominance + female.memory * female.dominance;
newburn.memory =newburn.memory *((Random(40)+80)/100.0);
newburn.intuition = male.intuition * male.dominance + female.intuition * female.dominance;
newburn.intuition = newburn.intuition *((Random(40)+80)/100.0);
newburn.path = 0;
newburn.dominance = 0;
if(newburn.speed>max_speed){
max_speed=newburn.speed;
}
return newburn;
}
// новая популяция из 6 особей
person robot_next_generation[6];
robot_next_generation[1] = newborn(0,2);
robot_next_generation[2] = newborn(0,3);
robot_next_generation[3] = newborn(1,2);
robot_next_generation[4] = newborn(1,3);
robot_next_generation[5] = newborn(2,3);
Теперь в дело вступает природа и у одной, случайной особи происходит мутация - ее один, случайный, признак изменяется. Мутация чаще всего приводит к появлению неконкурентоспособных или вообще нежизнеспособных особей, однако очень полезна в ситуации, когда вектор развития эволюции пошел изначально не в том направлении. В результате мутации может появиться особь со свойством, выигрышно выделяющим ее на фоне остальных. Такая особь сразу же окажется на вершине рейтинга и даст начало новой династии.
// Мутация
void mutants(){
int property=Random(3);
int mutant=Random(5);;
if(mutant<4){
switch(property){
case 0:
robot_next_generation[mutant].speed = max_speed+5;
break;
case 1:
robot_next_generation[mutant].reaction =robot_next_generation[mutant].reaction *((Random(40)+80)/100.0);
break;
case 2:
robot_next_generation[mutant].memory =robot_next_generation[mutant].memory *((Random(40)+80)/100.0);
break;
case 3:
robot_next_generation[mutant].intuition = robot_next_generation[mutant].intuition *((Random(40)+80)/100.0);
break;
default:
break;
}
}
else{
switch(property) {
case 0:
robot_next_generation[mutant].speed = max_speed+5;
break;
case 1:
robot_next_generation[mutant].reaction = Random(3000)/1000;
break;
case 2:
robot_next_generation[mutant].memory = Random(100)/1000;
break;
case 3:
robot_next_generation[mutant].intuition = Random(3000)/1000;
break;
default:
break;
}
}
}
Теперь производим смену популяций. Дети сменяют родителей:
for(int i=0;i<6;i++){
robot[i]=robot_next_generation[i];
}
Теперь снова пришла пора испытать новое поколение, более приспособленное к решению поставленной задачи, оценить возросшую скорость,, выявить сильнейших и так до тех пор, пока результат не будет нас устраивать.
byte fh;
int msg_len;
string logstr;
for(int i=0;i<6;i++){
logstr = robot[i].name;
logstr = logstr + ";" + NumToStr(robot[i].generation);
logstr = logstr + ";" + NumToStr(robot[i].reaction) +";"+NumToStr(robot[i].memory)+";"+NumToStr(robot[i].intuition);
logstr = logstr + ";" + NumToStr(robot[i].path)+";"+NumToStr(robot[i].speed);
msg_len = StrLen(logstr);
WriteLnString(fh, logstr, msg_len);
}
По данным, накопленным в файле в процессе работы программы, можно представить ход эволюции в виде наглядного графика (ось X - номер поколения, ось Y - средняя скорость особи):
