[알고리즘] Genetic Algorithms (유전 알고리즘)

Genetic Algorithm(GA)

자연 선택과 진화를 모방하여 최적화 문제를 해결하는 메타휴리스틱 알고리즘입니다. 생물학적 진화의 개념인 선택(Selection), 교차(Crossover), 돌연변이(Mutation)를 기반으로 작동하며, 다음과 같은 단계를 통해 최적의 해를 찾아갑니다:

초기화(Initialization)

초기 염색체 집합(해 집합)을 무작위로 생성합니다.

적합도 평가(Fitness Evaluation)

각 염색체(해)의 적합도를 계산합니다.

선택(Selection)

적합도가 높은 염색체를 부모로 선택합니다.

교차(Crossover)

부모 염색체를 결합하여 새로운 자손 염색체를 생성합니다.

돌연변이(Mutation)

자손 염색체에 일부 변화를 가하여 다양성을 유지합니다.

종료 조건 확인(Termination)

종료 조건(예: 세대 수, 적합도 임계값 등)이 충족되면 알고리즘을 종료합니다. 그렇지 않으면 2단계로 돌아갑니다.

---

GA는 최적화 문제, 탐색 문제 등 다양한 분야에서 활용되며, 복잡한 문제에 대해 전역 최적해를 찾는 데 유용합니다.

 

Kotlin을 활용한 Genetic Algorithm 샘플 코드

아래는 Kotlin으로 간단한 유전 알고리즘을 구현한 예제입니다.

import kotlin.random.Random

// 개체 모델 정의
data class Individual(val genes: IntArray, var fitness: Double = 0.0)

// 초기 개체군 생성
fun initializePopulation(populationSize: Int, geneLength: Int): List<Individual> {
    return List(populationSize) {
        Individual(genes = IntArray(geneLength) { Random.nextInt(0, 2) })
    }
}

// 적합도 평가 함수 (예: 유전자의 합을 적합도로 사용)
fun evaluateFitness(individual: Individual) {
    individual.fitness = individual.genes.sum().toDouble()
}

// 부모 선택 (룰렛 휠 방식)
fun selectParents(population: List<Individual>): Pair<Individual, Individual> {
    val totalFitness = population.sumOf { it.fitness }
    fun selectOne(): Individual {
        val rand = Random.nextDouble(totalFitness)
        var cumulative = 0.0
        for (individual in population) {
            cumulative += individual.fitness
            if (cumulative >= rand) return individual
        }
        return population.last()
    }
    return Pair(selectOne(), selectOne())
}

// 교차 연산
fun crossover(parent1: Individual, parent2: Individual): Individual {
    val crossoverPoint = Random.nextInt(parent1.genes.size)
    val childGenes = parent1.genes.copyOf().apply {
        for (i in crossoverPoint until size) this[i] = parent2.genes[i]
    }
    return Individual(childGenes)
}

// 돌연변이 연산
fun mutate(individual: Individual, mutationRate: Double = 0.01) {
    for (i in individual.genes.indices) {
        if (Random.nextDouble() < mutationRate) {
            individual.genes[i] = 1 - individual.genes[i] // 0 -> 1 또는 1 -> 0
        }
    }
}

// 유전 알고리즘 실행
fun runGeneticAlgorithm(
    populationSize: Int,
    geneLength: Int,
    generations: Int,
    mutationRate: Double
) {
    var population = initializePopulation(populationSize, geneLength)

    repeat(generations) { generation ->
        // 적합도 평가
        population.forEach { evaluateFitness(it) }

        // 새로운 세대 생성
        val newPopulation = mutableListOf<Individual>()
        while (newPopulation.size < populationSize) {
            val (parent1, parent2) = selectParents(population)
            val child = crossover(parent1, parent2)
            mutate(child, mutationRate)
            newPopulation.add(child)
        }

        population = newPopulation

        // 현재 세대의 최고 적합도 출력
        val bestIndividual = population.maxByOrNull { it.fitness }!!
        println("Generation $generation: Best Fitness = ${bestIndividual.fitness}")
    }
}

fun main() {
    runGeneticAlgorithm(
        populationSize = 100,
        geneLength = 10,
        generations = 50,
        mutationRate = 0.01
    )
}

 

코드 설명

초기화

initializePopulation 함수에서 무작위로 초기 개체군을 생성합니다.

적합도 평가

evaluateFitness 함수에서 각 개체의 유전자 합을 적합도로 계산합니다.

부모 선택

selectParents 함수에서 룰렛 휠 방식을 사용해 부모를 선택합니다.

교차

crossover 함수에서 교차점을 기준으로 자손을 생성합니다.

돌연변이

mutate 함수에서 일정 확률로 유전자를 변형시킵니다.

실행 결과 예시

Generation 0: Best Fitness = 8.0
Generation 1: Best Fitness = 9.0
...
Generation 49: Best Fitness = 10.0

 

위 코드는 단순화된 문제에 대해 작동하며, 실제 문제에 맞게 적합도 함수와 파라미터를 조정할 수 있습니다