알고리즘 - 유전 알고리즘 (Meta Heuristic), 최적해 찾기, 금괴 문제

유전 알고리즘 : Meta Heuristic 계열의 알고리즘

다양한 문제에 대해 경험적으로 솔루션을 제시하는 알고리즘

 

목적

주어진 문제에 대해서 최적의 솔루션을 찾는 것 (즉, 최적해를 찾는 것)

• 유전 알고리즘은 알고리즘 특성상 과정과 결과 설명이 굉장히 어려움. 무작위성이 존재함

 

생물학에서 생물들의 생존 법칙인 적자생존을 기반으로 한 알고리즘

1. 환경에 적합한 개체가 살아남는다.
2. 살아남은 개체는 번식을 한다.
3. 살아남은 개체는 각각 부모가 되어 자손을 생성하는데, 자손은 부와 모의 유전자를 받고
   때때로 돌연변이 유전자를 받아 다음 세대를 살아간다.

→ 위의 세 가지를 반복하면 환경에 적합한 개체들이 살아남고 그 개체들이 좋은 솔루션을 제시한다.

 

 

알고리즘에 쓰이는 용어와 표현

- 개체 : individual

- 단체 : population

- 적합도 함수 : fitness function f (문제마다 다르다. 좋은 해답을 주면 적합도가 높게 정의)

 

 

 

 

individual 선택 방법

1. 토너먼트 선택

 

 

 

2. 절단 선택

 

 

 

3. 적합도 비례 선택

- 함수의 적합도 값을 sampling 될 확률 값으로 변환해서 적합도가 높으면 쉽게 선택함

 

 

4. 정예주의 

- 3단계를 거치지 않고 우수한 individual이 그냥 진출

 

 

유전 연산 방법

1. 교배 (crossover)

DNA염색체가 꼬여 어머니, 아버지 유전 형질을 반반 가지게 되는 것과 비슷하다. 

 

2. 돌연변이

문제에 따라서 돌연변이는 좋은 영향을 주기도 하고 나쁜 영향을 주기도 한다. 

돌연변이가 언제 나타나는지 알 수 없다.

 

 

유전 알고리즘의 pseudo code

T = 0
initialize population 
//적합도 계산
while (적합도 찾지 못함) {
	T += 1
    population에서 선택 (selection)
    유전 연산 (선택된 individuals)
    적합도 계산
 }

 

 

유전 알고리즘 예제 문제 

1. 금괴 담기 

 

10kg을 담을 수 있는 가방이 있다. 다음과 같이 6개의 금괴가 존재할 때, 금괴들이 10kg을 넘지 않으면서 가장 값어치가 높도록 금괴들을 선택하여 가방에 담아야 한다. 

gold 1 : (4kg, $6)

gold 2 : (4kg, $7)

gold 3 : (3kg, $5)

gold 4 : (2kg, $4)

gold 5 : (1kg, $3)

gold 6 : (6kg, $9)

 

개체 (individuals) : size가 6인 배열. 각 index는 금괴번호, 배열의 값은 1(선택) 또는 0(선택X)

적합도 계산 : 개체가 선택한 금괴들의 무게 총합이 10 이하여야 하며, 값어치가 클수록 좋음

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define select_ratio 0.5f
#define population_size 12
#define mutation_ratio 0.05f
#define max_w 10
#define max_unchanged 40

typedef struct {
    int w;  // 금괴의 무게
    int v;  // 금괴의 값어치
} Gold;

typedef struct {
    int sum;    // 선택한 금괴의 무게 합계
    int val;    // 선택한 금괴의 값어치 총합
    int* code;  // 금괴 선택 여부를 나타내는 이진 코드 (0 : 선택하지 않음 / 1 : 선택함)
} Chromosome;   

// 금괴의 무게와 가치를 포함하여 금괴를 생성
void makeGold(Gold** golds) {
    *golds = (Gold*)malloc(6 * sizeof(Gold));
    (*golds)[0].w = 4;
    (*golds)[0].v = 6;
    // 나머지 금괴의 무게와 가치를 초기화해야 함
}

// 초기 염색체(population)를 생성하는 함수
// 각 금괴에 대해 무작위 확률을 사용하여 선택 여부를 결정하며, 선택된 금괴의 무게 및 가치의 합계 계산
void makeChromosomes(Gold* golds, Chromosome* population) {
    int cnt = 0;
    while (cnt < population_size) {
        Chromosome c;
        c.sum = 0;
        c.val = 0;
        c.code = (int*)malloc(6 * sizeof(int));
        for (int i = 0; i < 6; i++) {
            double rand_v = (double)rand() / RAND_MAX;
            if (rand_v > 0.5) {
                c.code[i] = 1;  // 금괴 선택
                c.sum += golds[i].w;
                c.val += golds[i].v;
            } else {
                c.code[i] = 0;  // 금괴 미선택
            }
        }
        if (c.sum <= max_w) {
            population[cnt++] = c;  // 염색체를 염색체 집단(population)에 추가
        } else {
            free(c.code);  // 무게가 최대값을 초과하는 경우 염색체를 버림
        }
    }
}


// 염색체의 값어치를 기준으로 내림차순으로 정렬하기 위한 비교 함수
int compare(const void* a, const void* b) {
    Chromosome* ch1 = (Chromosome*)a;
    Chromosome* ch2 = (Chromosome*)b;
    return ch2->val - ch1->val;
}


// 염색체의 적합도를 평가하고 지금까지 찾은 최적해를 업데이트하는 함수
void test(Chromosome* population, int* best_unchange_cnt, Chromosome* best_chr) {
    qsort(population, population_size, sizeof(Chromosome), compare);    //population 배열을 내림차순으로 정렬하기 위해 qsort 라이브러리 함수 사용
    if (best_chr->val < population[0].val) {
        *best_chr = population[0];  // 최적해를 업데이트
        *best_unchange_cnt = 0;
    } else {
        (*best_unchange_cnt)++;
    }
    // best_chr: 현재까지 찾은 최적해
    // best_unchange_cnt: 최적해가 변경되지 않은 세대 수
}

// 가장 적합한 개체들을 선택하고 나머지 개체를 염색체 집단에서 제거하여 선택된 개체들만 남게하는 함수
void select(Chromosome* population) {
    for (int i = (int)(population_size * select_ratio); i < population_size; i++) {
        free(population[i].code);  // 선택되지 않은 염색체의 메모리 해제
        population[i].code = NULL;
    }
}

// 선택된 염색체들 간에 교배를 수행하는 함수
// 유전 알고리즘 연산 방법 1 교배
void crossover(Chromosome* population) {
    for (int i = (int)(population_size * select_ratio); i < population_size; i++) {
        int p1 = rand() % (int)(population_size * select_ratio);    //무작위로 선택된 인덱스 p1
        int p2 = rand() % (int)(population_size * select_ratio);    
        //population 배열에서 select_ratio 비율에 따라 무작위로 선택된 두 번째 부모 염색체의 인덱스를 결정
        while (p1 == p2) {
            p2 = rand() % (int)(population_size * select_ratio);
        }
        Chromosome* parent1 = &population[p1];
        Chromosome* parent2 = &population[p2];
        Chromosome* child = &population[i];
        child->sum = 0;
        child->val = 0;
        child->code = (int*)malloc(6 * sizeof(int));
        for (int j = 0; j < 6; j++) {
            if (j < 2) {
                child->code[j] = parent1->code[j];
            } else {
                child->code[j] = parent2->code[j];
            }
            child->sum += child->code[j] * parent1->code[j];
            child->val += child->code[j] * parent2->code[j];
        }
    }
    // 선택된 부모로부터 교배하여 새로운 자식 염색체를 생성
}

// 염색체 집단에 무작위 돌연변이를 도입하는 함수
// 유전 알고리즘 연산 방법 2 돌연변이 
void mutation(Chromosome* population) {
    for (int i = 0; i < population_size; i++) {
        double rand_v = (double)rand() / RAND_MAX;
        if (rand_v < mutation_ratio) {
            int idx = rand() % 6;
            population[i].code[idx] = (population[i].code[idx] == 1) ? 0 : 1;
        }
    }
    // 염색체에 무작위 돌연변이를 도입
}

// 염색체 집단이 사용한 메모리를 해제하는 함수
void cleanup(Chromosome* population) {
    for (int i = 0; i < population_size; i++) {
        free(population[i].code);
    }
}

int main() {
    srand((unsigned int)time(NULL));  // 난수 시드 초기화

   Gold* golds;
    makeGold(&golds);  // 금괴 생성

    Chromosome* population = (Chromosome*)malloc(population_size * sizeof(Chromosome));
    makeChromosomes(golds, population);  // 초기 염색체 생성

    int t = 0;  // 세대 카운터
    int best_unchange_cnt = 0;  // 최적해가 변경되지 않은 세대 수 카운터
    Chromosome best_chr = population[0];  // 최적해를 첫 번째 염색체로 초기화

    while (best_unchange_cnt <= max_unchanged) {
        t++;  // 세대 카운터 증가
        test(population, &best_unchange_cnt, &best_chr);  // 적합도 평가 및 최적해 업데이트
        select(population);  // 가장 적합한 개체 선택
        crossover(population);  // 선택된 부모들 간에 교배 수행
        mutation(population);  // 염색체 집단에 무작위 돌연변이 도입
    }

    printf("best sum : %d best value : %d\n", best_chr.sum, best_chr.val);  // 최적해 출력

    cleanup(population);  // 메모리 정리
    free(population);
    free(golds);

    return 0;
}