移動ロボットの経路生成シミュレーションのソースコードです。初期の経路(ユーザが任意で指定)を読み込み，遺伝的アルゴリズムを適用することで消費エネルギーを抑えた経路を生成します。生成する経路がマップのセルを何回通過するか指定可能です(現状は2回通過までしか対応していません)。
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <time.h>
#include "create/create.h"
extern int coordinate[31][31];
extern int start_x,start_y;
typedef struct{
int score;
std::vector<char> route;
int pass_miss;
}path;
typedef struct{
char move;
int times;
}m_selection;
bool comparisonFunc(const path &a,const path &b);
bool comparisonMselection(const m_selection &a,const m_selection &b);
int main(){
int len[1024];
int path_num = 0;
int parents_num = 0;
int generation = 1000;
std::cout << "You can choose generation number: ";
std::cin >> generation;
std::cout << std::endl;
int generation_n = generation;
int extension = 0;
int extension2 = 0;
int iteration = 1;
int ite = 1;
std::cout << "Decide how many times you want to pass through the cell : ";
std::cin >> iteration;
std::cout << std::endl;
double frequency = 1.0;
std::cout << "How many mutations are there ? (Usually once.) :";
std::cin >> frequency;
std::cout << std::endl;
double frequency_tmp = frequency;
double same_move;
std::cout << "If it is the same as previous or next action, what is the frequency?(specify with a decimal point) :";
std::cin >> same_move;
std::cout << std::endl;
double same_moveBoth;
std::cout << "If it is the same as previous and next action, what is the frequency?(specify with a decimal point) :";
std::cin >> same_moveBoth;
std::cout << std::endl;
double moveFirstf;
std::cout << "If the first action is f, what is the frequency?(specify with a decimal point) :";
std::cin >> moveFirstf;
std::cout << std::endl;
double same_moveFirstf;
std::cout << "If the first action is f, and the next action is also f, what is the frequency?(specify with a decimal point) :";
std::cin >> same_moveFirstf;
std::cout << std::endl;
/*int leave = 3;
std::cout << "Decide how much of the mutation you want to keep : ";
std::cin >> leave;
std::cout << std::endl;*/
srand((unsigned)time(NULL));
const char *file = "sample";
FILE *fp = NULL;
char a[4096];
int n = 0;
int tmp_n = 0;
fp = fopen(file,"r");
if(fp==NULL){
std::cout << file << " file not open" << std::endl;
return 0;
}
while(fscanf(fp,"%c",&(a[n])) != EOF){
while(a[n] != '\n'){
n++;
fscanf(fp,"%c",&(a[n]));
}
len[path_num]=n-tmp_n;
path_num++;
n++;
tmp_n = n;
}
parents_num = path_num / 2;
fclose(fp);
std::vector<path> parents(path_num);
std::vector<path> child(path_num);
std::vector<path> child_tmp(path_num);
path child_tmp2;
for(int i=0;i<path_num;i++){
parents[i].route.resize(len[i]);
}
int sum = 0;
for(int i=0;i<path_num;i++){
for(int j=0;j<len[i];j++) parents[i].route[j] = a[sum+j];
sum = len[i] + sum + 1;
}
for(int i=0;i<path_num;i++){
for(int j=0;j<len[i];j++) std::cout << parents[i].route[j];
start_pos s = map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
parents[i].score = scoreCalc(parents[i].route.data(),len[i]);
parents[i].pass_miss = checkPassmiss_ite(ite);
std::cout << " :this score is " << parents[i].score << " and, ";
std::cout << "pass miss : " << parents[i].pass_miss << std::endl;
}
std::cout << std::endl;
//ga start.
while(generation > 0){
sort(parents.begin(),parents.end(),comparisonFunc);
//excelent g inherited
for(int i=0;i<parents_num;i++){
child[i].route.resize(parents[i].route.size());
child[i] = parents[i];
}
for(int i= parents_num;i<path_num;i++){
child[i].route.resize(parents[i-parents_num].route.size());
child[i] = parents[i-parents_num];
child_tmp[i].route.resize(child[i].route.size());
child_tmp[i] = child[i];
}
for(int i= parents_num;i<path_num;i++){
int child_psms = child[i].pass_miss;
for(unsigned int j=0;j<child[i].route.size();j++){
if(j==0){
if(child[i].route[j]=='f'){
frequency = moveFirstf;
if(child[i].route[j]==child[i].route[j+1]) frequency = same_moveFirstf;
}
if(child[i].route[j]!='f' && child[i].route[j]==child[i].route[j+1]) frequency = same_move;
}
if(j>0 && child[i].route.size()-1>j){
if(child[i].route[j]==child[i].route[j-1] || child[i].route[j]==child[i].route[j+1]) frequency = same_move;
if(child[i].route[j]==child[i].route[j-1] && child[i].route[j]==child[i].route[j+1]) frequency = same_moveBoth;
}
if(j==child[i].route.size()-1 && child[i].route[j]==child[i].route[j-1]) frequency = same_move;
if(rand() % int(child[i].route.size()/frequency) == 0){
int random = rand() % 3;
char tmp_move = child[i].route[j];
if(tmp_move == 'f'){
if(random == 0) child[i].route[j] = 'b';
else if(random == 1) child[i].route[j] = 'r';
else if(random == 2) child[i].route[j] = 'l';
}else if(tmp_move == 'b'){
if(random == 0) child[i].route[j] = 'f';
else if(random == 1) child[i].route[j] = 'r';
else if(random == 2) child[i].route[j] = 'l';
}else if(tmp_move == 'r'){
if(random == 0) child[i].route[j] = 'f';
else if(random == 1) child[i].route[j] = 'b';
else if(random == 2) child[i].route[j] = 'l';
}else{
if(random == 0) child[i].route[j] = 'f';
else if(random == 1) child[i].route[j] = 'b';
else if(random == 2) child[i].route[j] = 'r';
}
std::vector<char> route_mid;
route_mid.resize(j+1);
for(unsigned int m=0;m<j+1;m++) route_mid[m] = child[i].route[m];
start_pos s = map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
move_count mutant = moveEmu(route_mid.data(),j+1);
if(mutant.conflict_n > 0) child[i].route[j] = tmp_move;
else{
s=map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
move_count mutan = moveEmu(child[i].route.data(),child[i].route.size());
child[i].pass_miss = checkPassmiss_ite(ite);
if(child[i].pass_miss>child_psms || mutan.conflict_n>0){
s=map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
position area = moveFinish(child[i].route.data(),j+1);
std::vector<m_selection> neigh(4);
for(unsigned int m=j+1;m<child[i].route.size();m++){
neigh[0].times=coordinate[start_x+area.x][start_y+area.y-1];
neigh[0].move='f';
neigh[1].times=coordinate[start_x+area.x+1][start_y+area.y];
neigh[1].move='r';
neigh[2].times=coordinate[start_x+area.x-1][start_y+area.y];
neigh[2].move='l';
neigh[3].times=coordinate[start_x+area.x][start_y+area.y+1];
neigh[3].move='b';
sort(neigh.begin(),neigh.end(),comparisonMselection);
int min_n=1;
int min = neigh[0].times;
for(int u=1;u<4;u++){
if(min==neigh[u].times) min_n++;
}
char sel_m[min_n];
for(int u=0;u<min_n;u++) sel_m[u]=neigh[u].move;
char selected_m;
if(min_n==1) selected_m = neigh[0].move;
else if(min_n==2){
int ran = rand()%2;
selected_m = sel_m[ran];
}else if(min_n==3){
int ran = rand()%3;
selected_m = sel_m[ran];
}else if(min_n==4){
int ran = rand()%4;
selected_m = sel_m[ran];
}
child[i].route[m]=selected_m;
s=map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
area = moveFinish(child[i].route.data(),m+1);
}
}
}
}
frequency = frequency_tmp;
start_pos s=map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
child[i].score = scoreCalc(child[i].route.data(),child[i].route.size());
child_psms = checkPassmiss_ite(ite);
}
if(child_tmp[i].route != child[i].route){
start_pos s = map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
child[i].score = scoreCalc(child[i].route.data(),child[i].route.size());
child[i].pass_miss = checkPassmiss_ite(ite);
if(child[i].pass_miss>child_tmp[i].pass_miss){
//child_tmp2.route.resize(child[i].route.size());
//child_tmp2 = child[i];
child[i] = child_tmp[i];
//if(rand()%leave == 0) child[i] = child_tmp2;
}
}
}
for(int i=0;i<path_num;i++){
parents[i].route.resize(child[i].route.size());
parents[i] = child[i];
}
generation -= 1;
if(generation==0 && parents[0].pass_miss!=0){
generation += generation_n;
if(ite == 1){
extension += 1;
std::cout << "now,extension: " << extension << std::endl;
}else{
extension2 += 1;
std::cout << "now,extension2: " << extension2 << std::endl;
}
}else if(generation==0 && parents[0].pass_miss==0){
for(int i=0;i<path_num;i++){
for(unsigned int j=0;j<parents[i].route.size();j++) std::cout << parents[i].route[j];
std::cout << std::endl;
start_pos s = map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
int cut = moveNum(parents[i].route.data(),parents[i].route.size(),ite);
parents[i].route.resize(cut+1);
s = map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
parents[i].score = scoreCalc(parents[i].route.data(),parents[i].route.size());
parents[i].pass_miss = checkPassmiss_ite(ite);
for(unsigned int j=0;j<parents[i].route.size();j++) std::cout << parents[i].route[j];
std::cout << ":length : " << parents[i].route.size() << std::endl;
std::cout << "-----------------------------------" << std::endl;
}
if(iteration>1){
std::cout << "path expand!" << std::endl;
ite = iteration;
iteration = 1;
unsigned int size_tmp[path_num];
for(int i=0;i<path_num;i++){
unsigned int size = parents[i].route.size();
parents[i].route.resize(size*ite);
unsigned int tir =1;
for(unsigned int j=size;j<parents[i].route.size();j++){
if(tir>size) tir = 1;
if(parents[i].route[j-(2*tir-1)]=='f') parents[i].route[j]='b';
else if(parents[i].route[j-(2*tir-1)]=='b') parents[i].route[j]='f';
else if(parents[i].route[j-(2*tir-1)]=='r') parents[i].route[j]='l';
else if(parents[i].route[j-(2*tir-1)]=='l') parents[i].route[j]='r';
tir += 1;
}
size_tmp[i]=size;
}
//std::cout << "hey!" << std::endl;
for(int i=0;i<path_num;i++){
if(parents[i].route[size_tmp[i]-1]=='f'){
parents[i].route.insert(parents[i].route.begin()+size_tmp[i],'b');
parents[i].route.insert(parents[i].route.begin()+size_tmp[i]+1,'f');
}else if(parents[i].route[size_tmp[i]-1]=='r'){
parents[i].route.insert(parents[i].route.begin()+size_tmp[i],'l');
parents[i].route.insert(parents[i].route.begin()+size_tmp[i]+1,'r');
}else if(parents[i].route[size_tmp[i]-1]=='l'){
parents[i].route.insert(parents[i].route.begin()+size_tmp[i],'r');
parents[i].route.insert(parents[i].route.begin()+size_tmp[i]+1,'l');
}else if(parents[i].route[size_tmp[i]-1]=='b'){
parents[i].route.insert(parents[i].route.begin()+size_tmp[i],'f');
parents[i].route.insert(parents[i].route.begin()+size_tmp[i]+1,'b');
}
}
for(int i=0;i<path_num;i++){
start_pos s;
s=map();
coordinate[s.x][s.y]=1;
start_x = s.x;
start_y = s.y;
parents[i].score = scoreCalc(parents[i].route.data(),parents[i].route.size());
parents[i].pass_miss = checkPassmiss_ite(ite);
}
for(int i=0;i<path_num;i++){
for(unsigned int j=0;j<parents[i].route.size();j++) std::cout << parents[i].route[j];
std::cout << ": socre is " << parents[i].score;
std::cout << ". pass miss is " << parents[i].pass_miss << std::endl;
}
generation += generation_n;
}
}
}
std::cout << "parents's final score is " << parents[0].score << ". and this pass miss is " << parents[0].pass_miss << "." << std::endl;
std::cout << "The number of extensions is " << extension << "." << std::endl;
std::cout << "And this route is ";
for(unsigned int i=0;i<parents[0].route.size();i++){
std::cout << parents[0].route[i];
}
std::cout << ": character num : " << parents[0].route.size();
std::cout << std::endl;
return 0;
}
bool comparisonFunc(const path &a,const path &b){
return a.score < b.score;
}
bool comparisonMselection(const m_selection &a,const m_selection &b){
return a.times < b.times;
}
29行目～68行目 [染色体に関する変数宣言と突然変異の確率などの初期設定]
77～101行目 [初期染色体の読み込み]
brbbbb
flrb
flllllll
lrlrb103行目～129行目 [親染色体(初期染色体)の設定]
132行目～383行目 [遺伝的アルゴリズム] ここ(132行目のwhile文)から遺伝的アルゴリズムの処理に入ります。この処理は変数generationの数だけ繰り返します。
135行目～147行目 [親染色体のソートと次世代の親染色体の生成，子染色体の生成]