유전 알고리즘을 만들고 있는데 3가지 부분을 만드는게 어려워서 질문을 올리게 되었습니다.

돌연변이와 교차 알고리즘 그리고 새 유전자 명시하는 코드 입니다.

#include <iostream>

#include <string.h>

#include <fstream>

#include <time.h>

#include <algorithm>

using namespace std;

const int NOI=50; // 물건의 개수=유전자의 길이

const int MW=40000; // 배낭의 최대 저장 무게

const int NOG=64; // 유전자의 개수

int GbestValue=0; // 최대 적합도(최대 가치)

int GbestWeight=0;  // 최고 무게

struct itemType{  //화물정보를 위한 구조체

int weight; // 화물의 무게

int value; // 화물의 가치

};

struct geneType{ // 유전자 구조체

char dna[NOI+1]; // 유전자 문자열 -> "0010010100100011101010110101...."

int wSum; // 위 유전자 상태에서의 무게합

int valueSum; // 그 때의 총가치

};

itemType items[NOI]; // 화물정보를 저장한 배열

geneType gene[2][NOG]; // 유전자 배열- 0: 이전 세대, 1: 이후 세대

bool cmp(const geneType &a, const geneType &b) // sort 함수를 위한 비교함수

{

return (a.valueSum > b.valueSum); // > : 내림차순, < : 오름차순

}

void read_data(){ // 파일로 부터 화물 정보를 읽어 items 배열에 저장

ifstream in("knapsack50.txt");

if (in.is_open()) {

for(int i=0;i<NOI;i++){

in >> items[i].weight >> items[i].value;

}

}

else {

cout << "파일을 찾을 수 없습니다!" << endl;

exit(-1);

}

in.close();

}

void w_sum(int g, int num){ // 이전(g=0), 이후(g=1) 세대 유전자들의 num번째 유전자 상태에 따른

    // 무게 합과 가치 합을 구해 저장하는 함수

int wsum=0;

int vsum=0;

for(int i=0;i<NOI;i++){

if(gene[g][num].dna[i] == '1'){

// 화물이 들어가는 경우(유전자열 문자가 '1'인 경우)에만 합을 구함

wsum = wsum + items[i].weight;

vsum = vsum + items[i].value;

}

}

gene[g][num].wSum = wsum;

gene[g][num].valueSum = vsum;

}

void init_gene(){ // 초기 64개의 유전자를 랜덤으로 생성하는 함수

int i=0;

while(i<NOG){

for(int j=0; j<NOI; j++){

if(rand()%2 == 1){ // 홀수이면 1, 짝수이면 0으로 세팅

gene[0][i].dna[j]='1';

}

else{

gene[0][i].dna[j]='0';

}

}

gene[0][i].dna[NOI] = '\0'; // 문자열 마지막은 항상 NULL로 막아야 함

w_sum(0, i); // 랜덤으로 생성된 유전자열의 무게합을 확인하기 위해 합을 구함

if(gene[0][i].wSum <= MW){

// 무게가 초과되지 않아야만 유효한 유전자. 그렇지 않으면 다시 생성

i++;

}

}

sort(gene[0], gene[0]+NOG, cmp); // 내림차순 정렬

GbestValue=gene[0][0].valueSum;

// 총가치를 기준으로 내림차순 정렬이므로 맨 앞의 유전자가 베스트 유전자

}

void copyGene(int des, int src){ // src 번째 이전 유전자를 dec 번째 새 유전자로 복사

// 이전 세대의 유전자들 중 가장 우수한 것을 그대로 넘기기 위함.(elitism)

strcpy(gene[1][des].dna, gene[0][src].dna);

gene[1][des].valueSum = gene[0][src].valueSum;

gene[1][des].wSum = gene[0][src].wSum;

}

// g 세대의 k, m번째 유전자 2개를 돌연변이시킴

void mutate(int g, int k, int m){

int place; // 교차위치 임시변수

//////////////////////////////////////////////////////////////////////

// 이 곳에 돌연변이 함수를 직접 작성해 봄

// k번째, m번째 유전자의 1곳, 또는 2곳 정도만 일정 확률로 돌연변이시킴

// 무작위 위치의 문자가 0이면 1, 1이면 0으로 치환

// 확률은 10% 이하로 낮게 잡는 것이 좋음. 돌연변이가 너무 많으면

// 널뛰기처럼 들쭉 날쭉해져서 무작위 탐색처럼 되고 최적해에 빨리 수렴하지 못함

//////////////////////////////////////////////////////////////////////

}

void crossover1p(int i, int j, int k, int m){

// 이전 i번째 j번째 유전자를 교차하여 k, m번째 새 유전자로 집어넣음

// 랜덤 위치의 단순 교차

char tempa[NOI+1];

char tempb[NOI+1];

while(1){

////////////////////////////////////////

/// 여기에 교차 알고리즘 작성해 보기 ///

////////////////////////////////////////

strcpy(gene[1][k].dna, tempa); // 생성된 첫번째 교차 유전자열을 복사

strcpy(gene[1][m].dna, tempb); // 생성된 두번째 교차 유전자열을 복사

mutate(1, k, m); // 돌연변이 시행

w_sum(1, k); // 무게 초과를 확인하기 위해 무게합 구함

w_sum(1, m);

if(gene[1][k].wSum <= MW && gene[1][m].wSum <= MW){

break; // 무게 조건이 둘 다 맞아야만 유효한 생성으로 함수 종료

}

}

}

void copyAllBack(){ // 이후 세대의 유전자들을 모두 이전 세대 변수로 복사

// 그래야만 동일한 방법으로 이전 세대 유전자로 다시 이후 세대 유전자를 반복하면서 생성

for(int i=0;i<NOG;i++){

strcpy(gene[0][i].dna, gene[1][i].dna);

gene[0][i].valueSum=gene[1][i].valueSum;

gene[0][i].wSum=gene[1][i].wSum;

}

}

void select_and_crossover(){

// 선택기법에 따라 선택한 이전 세대 유전자로 이후 세대 유전자 생성

// 엘리티즘을 반드시 사용하도록 함.

// 엘리티즘을 사용하지 않으면 널뛰기처럼 값이 들쭉 날쭉해져서 최적해로의 수렴이 어려움

copyGene(0, 0); // 엘리티즘용

copyGene(63, 0); // 엘리티즘용.

crossover1p(0,1,1,2);

crossover1p(0,3,3,4);

crossover1p(0,5,5,6);

crossover1p(0,7,7,8);

crossover1p(0,9,9,10);

////////////////////////////////////////////////////////

// 이 곳에 선택법에 따른 이전 유전자 2개 선택과

// 그 2개로 인해 생성되는 새 유전자를 명시하는 코드 작성

// 위의 예처럼 단순하게 다 나열해도 되고

// 반복문을 잘 활용하면 더 깔끔하게 작성할 수 있음

////////////////////////////////////////////////////////

sort(gene[1], gene[1]+NOG, cmp); // 새로 생성된 유전자들을 가치순으로 정렬

}

int main(){

double avg; // 모든 유전자들의 가치 평균값 저장

int sum; // 평균을 위한 합계

    ofstream out("result.txt");

srand (int(time(NULL))); // 랜던 함수 시드 설정

read_data(); // 화물 데이터 읽어들임

init_gene(); // 랜덤으로 초기 유전자 세트  생성

sum=0;

for(int i=0;i<NOG;i++){ // 초기 랜덤 유전자들의 평균 가치를 출력하기 위한 합계 산출

sum = sum + gene[0][i].valueSum;

}

// 초기 랜던 유전자들의 최고 가치, 그때의 무게합, 평균 가치를 출력

cout << gene[0][0].valueSum << ", " << gene[0][0].wSum << ", " << sum/NOG << endl;  

out << gene[0][0].valueSum << ", " << gene[0][0].wSum << ", " << sum/NOG << endl;  

for(int i=0;i<2000;i++){ // 진화를 2,000세대만 진행시켜서 동료들과 결과 비교

select_and_crossover(); // 선택법에 따른 선택과 교차를 시행하여 새로운 유전자 세트를 생성

copyAllBack(); // 반복을 위해 새 유전자 세트를 이전 유전자 세트로 복사

sum=0;

for(int i=0;i<NOG;i++){

sum = sum + gene[0][i].valueSum;

}// 새로 생성된 유전자들의 평균 가치를 출력하기 위한 합계 산출

// 세대별 변화를 보고 싶을 경우 아래 문의 주석 헤제

// cout << gene1[0].valueSum << ", " << gene1[0].wSum << ", " << sum/NOG << endl;  

// out << gene1[0].valueSum << ", " << gene1[0].wSum << ", " << sum/NOG << endl;

}

//최종 결과를 출력하는 부분

cout << gene[0][0].valueSum << ", " << gene[0][0].wSum << ", " << sum/NOG << endl;  

out << gene[0][0].valueSum << ", " << gene[0][0].wSum << ", " << sum/NOG << endl;  

out.close();

return 0;

}