🎓10주차: 진화적 알고리즘 (유전 알고리즘)

"생물의 진화 원리(변이, 선택, 교배)를 코드로 구현해서, 컴퓨터가 스스로 '좋은 해답'을 찾아가게 만드는 알고리즘"이에요.
이것은 최적화 문제, 생성 디자인, 인공생명 시뮬레이션 등에서 자연의 진화를 모방하는 핵심 원리입니다.

항목	내용
이름	Genetic Algorithm (GA)
의미	생물학적 진화(유전, 돌연변이, 자연선택)를 모방한 최적화 알고리즘
핵심 아이디어	여러 개체가 경쟁하고, 우수한 개체끼리 교배(crossover)하고 변이(mutation)를 거쳐 세대를 거듭하며 진화
결과 패턴	세대가 지날수록 목표에 가까워지는 개체 집단의 '적응'
관련 개념	자연선택(natural selection), 적합도(fitness), 교배(crossover), 돌연변이(mutation)

---

📖 유전 알고리즘의 기본 원리

1️⃣ 초기 집단(Population) 생성

→ 무작위로 여러 개체(individual)를 만듦
(예: 목표 문장을 찾는 경우, 랜덤한 문자열을 여러 개 생성)

2️⃣ 적합도(Fitness) 평가

→ 각 개체가 "목표에 얼마나 가까운지" 점수를 매김
(예: 목표 문장과 몇 글자가 일치하는지)

3️⃣ 선택(Selection)

→ 적합도가 높은 개체를 더 많이 선택함
→ 자연선택(survival of the fittest)을 모방

4️⃣ 교배(Crossover)

→ 선택된 두 부모의 유전자를 섞어 자식을 만듦
(예: 부모 A의 앞부분 + 부모 B의 뒷부분)

5️⃣ 돌연변이(Mutation)

→ 일정 확률로 자식의 유전자 일부를 랜덤하게 바꿈
→ 다양성을 유지하고 지역 최적해(local optimum)를 탈출

6️⃣ 다음 세대로 대체

→ 새로운 집단으로 교체하고 2️⃣로 돌아감
→ 목표에 도달하거나 일정 세대수까지 반복

---

🔗 자연 현상과의 연결

🧬 생물 진화	갈라파고스 핀치새가 부리 모양을 환경에 맞게 진화
🌱 식물 적응	선인장이 건조한 환경에 적응한 형태로 진화
🦋 곤충의 의태	나뭇잎처럼 보이도록 진화한 나방
🐆 포식자-피식자	치타의 속도와 가젤의 민첩성이 서로 경쟁하며 진화

---

📊 다른 주제와의 연결

주제	관계
랜덤(Randomness)	돌연변이와 초기 집단 생성의 기반
시스템(Systems)	개체들의 집단적 상호작용으로 복잡성 생성
형태 & 구조(Form & Structure)	진화를 통해 형태가 최적화됨
데이터(Data)	유전자를 데이터로 표현하고 조작

---

💻 예제 코드

🔹 예제 1: 기본 유전 알고리즘 (문자열 진화)

let population = [];
let target = "BamgasiJM";
let mutationRate = 0.01;
let popSize = 200;

function setup() {
  createCanvas(600, 250);
  // 초기 집단 생성
  for (let i = 0; i < popSize; i++) {
    population.push(new DNA(target.length));
  }
}

function draw() {
  background(15);

  // 적합도 계산
  for (let dna of population) {
    dna.calcFitness(target);
  }

  // 다음 세대 생성
  let matingPool = [];
  for (let dna of population) {
    let n = floor(dna.fitness * 100);
    for (let i = 0; i < n; i++) {
      matingPool.push(dna);
    }
  }

  // 교배 및 돌연변이
  for (let i = 0; i < population.length; i++) {
    let parentA = random(matingPool);
    let parentB = random(matingPool);
    let child = parentA.crossover(parentB);
    child.mutate(mutationRate);
    population[i] = child;
  }

  // 최고 개체 표시
  let best = population[0];
  for (let dna of population) {
    if (dna.fitness > best.fitness) {
      best = dna;
    }
  }

  fill(210, 180, 0);
  textSize(32);
  textAlign(CENTER);
  text("Target: " + target, width / 2, 70);
  fill(30, 200, 190);
  textSize(32);
  textAlign(CENTER);
  text("Best: " + best.genes, width / 2, 120);
  fill(200);
  textSize(18);
  textAlign(CENTER);
  text("Generation: " + frameCount, width / 2, 180);
  text("Fitness: " + nf(best.fitness, 0, 4), width / 2, 210);

  // 목표 달성 시 정지
  if (best.genes === target) {
    noLoop();
    console.log("Completed! Number of Generations: " + frameCount);
  }
}

class DNA {
  constructor(len) {
    this.genes = "";
    this.fitness = 0;
    for (let i = 0; i < len; i++) {
      this.genes += this.randomChar();
    }
  }

  randomChar() {
    let c = floor(random(32, 128));
    return String.fromCharCode(c);
  }

  calcFitness(target) {
    let score = 0;
    for (let i = 0; i < this.genes.length; i++) {
      if (this.genes[i] === target[i]) {
        score++;
      }
    }
    this.fitness = score / target.length;
  }

  crossover(partner) {
    let child = new DNA(this.genes.length);
    let midpoint = floor(random(this.genes.length));
    child.genes =
      this.genes.substring(0, midpoint) + partner.genes.substring(midpoint);
    return child;
  }

  mutate(rate) {
    let genes = "";
    for (let i = 0; i < this.genes.length; i++) {
      if (random(1) < rate) {
        genes += this.randomChar();
      } else {
        genes += this.genes[i];
      }
    }
    this.genes = genes;
  }
}

---

🔹 예제 2: 타겟을 향한 로켓 진화

let population = [];
let popSize = 50;
let target;
let lifespan = 300;
let lifeCounter = 0;
let generation = 1;

function setup() {
  createCanvas(600, 600);
  target = createVector(width / 2, 50);
  
  for (let i = 0; i < popSize; i++) {
    population.push(new Rocket());
  }
}

function draw() {
  background(0);
  
  // 목표 지점
  fill(255, 0, 0);
  circle(target.x, target.y, 20);
  
  // 로켓 업데이트
  for (let rocket of population) {
    rocket.update();
    rocket.show();
  }
  
  lifeCounter++;
  
  // 세대 교체
  if (lifeCounter >= lifespan) {
    lifeCounter = 0;
    evaluate();
    selection();
    generation++;
  }
  
  // 정보 표시
  fill(255);
  textAlign(LEFT);
  text("Generation: " + generation, 10, 20);
  text("Lifespan: " + lifeCounter + "/" + lifespan, 10, 40);
}

function evaluate() {
  let maxFit = 0;
  for (let rocket of population) {
    rocket.calcFitness(target);
    if (rocket.fitness > maxFit) {
      maxFit = rocket.fitness;
    }
  }
  
  // 정규화
  for (let rocket of population) {
    rocket.fitness /= maxFit;
  }
}

function selection() {
  let matingPool = [];
  
  for (let rocket of population) {
    let n = floor(rocket.fitness * 100);
    for (let i = 0; i < n; i++) {
      matingPool.push(rocket);
    }
  }
  
  let newPopulation = [];
  for (let i = 0; i < popSize; i++) {
    let parentA = random(matingPool);
    let parentB = random(matingPool);
    let child = parentA.crossover(parentB);
    child.mutate();
    newPopulation.push(child);
  }
  
  population = newPopulation;
  lifeCounter = 0;
}

class Rocket {
  constructor(dna) {
    this.pos = createVector(width / 2, height - 50);
    this.vel = createVector();
    this.acc = createVector();
    this.completed = false;
    this.crashed = false;
    this.fitness = 0;
    
    if (dna) {
      this.dna = dna;
    } else {
      this.dna = [];
      for (let i = 0; i < lifespan; i++) {
        this.dna.push(p5.Vector.random2D().setMag(0.1));
      }
    }
  }
  
  update() {
    if (!this.completed && !this.crashed) {
      this.applyForce(this.dna[lifeCounter]);
      this.vel.add(this.acc);
      this.pos.add(this.vel);
      this.acc.mult(0);
      
      // 충돌 감지
      if (this.pos.x < 0 || this.pos.x > width || 
          this.pos.y < 0 || this.pos.y > height) {
        this.crashed = true;
      }
      
      // 목표 도달
      if (dist(this.pos.x, this.pos.y, target.x, target.y) < 20) {
        this.completed = true;
      }
    }
  }
  
  applyForce(force) {
    this.acc.add(force);
  }
  
  show() {
    push();
    translate(this.pos.x, this.pos.y);
    rotate(this.vel.heading());
    
    if (this.completed) {
      fill(0, 255, 0);
    } else if (this.crashed) {
      fill(255, 0, 0);
    } else {
      fill(255);
    }
    
    rectMode(CENTER);
    rect(0, 0, 20, 5);
    pop();
  }
  
  calcFitness(target) {
    let d = dist(this.pos.x, this.pos.y, target.x, target.y);
    this.fitness = map(d, 0, width, width, 0);
    
    if (this.completed) {
      this.fitness *= 10;
    }
    if (this.crashed) {
      this.fitness /= 10;
    }
  }
  
  crossover(partner) {
    let newDNA = [];
    let midpoint = floor(random(this.dna.length));
    
    for (let i = 0; i < this.dna.length; i++) {
      if (i < midpoint) {
        newDNA.push(this.dna[i]);
      } else {
        newDNA.push(partner.dna[i]);
      }
    }
    
    return new Rocket(newDNA);
  }
  
  mutate() {
    let mutationRate = 0.01;
    for (let i = 0; i < this.dna.length; i++) {
      if (random(1) < mutationRate) {
        this.dna[i] = p5.Vector.random2D().setMag(0.1);
      }
    }
  }
}

---

🔹 예제 3: 원 회피 로켓 진화

let population = [];
let popSize = 50;
let target;
let obstacles = [];
let lifespan = 300;
let lifeCounter = 0;
let generation = 1;

function setup() {
  createCanvas(600, 600);
  target = createVector(width / 2, 50);
  
  // 장애물 생성
  obstacles.push(createVector(width / 2, height / 2));
  obstacles.push(createVector(width / 2 - 100, height / 2 + 100));
  obstacles.push(createVector(width / 2 + 100, height / 2 + 100));
  
  for (let i = 0; i < popSize; i++) {
    population.push(new Rocket());
  }
}

function draw() {
  background(0);
  
  // 목표 지점
  fill(0, 255, 0);
  circle(target.x, target.y, 20);
  
  // 장애물
  fill(255, 0, 0);
  for (let obs of obstacles) {
    circle(obs.x, obs.y, 40);
  }
  
  // 로켓 업데이트
  for (let rocket of population) {
    // 장애물 충돌 체크
    for (let obs of obstacles) {
      if (dist(rocket.pos.x, rocket.pos.y, obs.x, obs.y) < 25) {
        rocket.crashed = true;
      }
    }
    
    rocket.update();
    rocket.show();
  }
  
  lifeCounter++;
  
  if (lifeCounter >= lifespan) {
    lifeCounter = 0;
    evaluate();
    selection();
    generation++;
  }
  
  fill(255);
  textAlign(LEFT);
  text("Generation: " + generation, 10, 20);
  text("Lifespan: " + lifeCounter + "/" + lifespan, 10, 40);
}

function evaluate() {
  let maxFit = 0;
  for (let rocket of population) {
    rocket.calcFitness(target);
    if (rocket.fitness > maxFit) {
      maxFit = rocket.fitness;
    }
  }
  
  for (let rocket of population) {
    rocket.fitness /= maxFit;
  }
}

function selection() {
  let matingPool = [];
  
  for (let rocket of population) {
    let n = floor(rocket.fitness * 100);
    for (let i = 0; i < n; i++) {
      matingPool.push(rocket);
    }
  }
  
  let newPopulation = [];
  for (let i = 0; i < popSize; i++) {
    let parentA = random(matingPool);
    let parentB = random(matingPool);
    let child = parentA.crossover(parentB);
    child.mutate();
    newPopulation.push(child);
  }
  
  population = newPopulation;
  lifeCounter = 0;
}

class Rocket {
  constructor(dna) {
    this.pos = createVector(width / 2, height - 50);
    this.vel = createVector();
    this.acc = createVector();
    this.completed = false;
    this.crashed = false;
    this.fitness = 0;
    
    if (dna) {
      this.dna = dna;
    } else {
      this.dna = [];
      for (let i = 0; i < lifespan; i++) {
        this.dna.push(p5.Vector.random2D().setMag(0.1));
      }
    }
  }
  
  update() {
    if (!this.completed && !this.crashed) {
      this.applyForce(this.dna[lifeCounter]);
      this.vel.add(this.acc);
      this.pos.add(this.vel);
      this.acc.mult(0);
      
      if (this.pos.x < 0 || this.pos.x > width || 
          this.pos.y < 0 || this.pos.y > height) {
        this.crashed = true;
      }
      
      if (dist(this.pos.x, this.pos.y, target.x, target.y) < 20) {
        this.completed = true;
      }
    }
  }
  
  applyForce(force) {
    this.acc.add(force);
  }
  
  show() {
    push();
    translate(this.pos.x, this.pos.y);
    rotate(this.vel.heading());
    
    if (this.completed) {
      fill(0, 255, 0);
    } else if (this.crashed) {
      fill(255, 0, 0, 50);
    } else {
      fill(255, 150);
    }
    
    rectMode(CENTER);
    rect(0, 0, 20, 5);
    pop();
  }
  
  calcFitness(target) {
    let d = dist(this.pos.x, this.pos.y, target.x, target.y);
    this.fitness = map(d, 0, width, width, 0);
    
    if (this.completed) {
      this.fitness *= 10;
    }
    if (this.crashed) {
      this.fitness /= 10;
    }
  }
  
  crossover(partner) {
    let newDNA = [];
    let midpoint = floor(random(this.dna.length));
    
    for (let i = 0; i < this.dna.length; i++) {
      if (i < midpoint) {
        newDNA.push(this.dna[i]);
      } else {
        newDNA.push(partner.dna[i]);
      }
    }
    
    return new Rocket(newDNA);
  }
  
  mutate() {
    let mutationRate = 0.01;
    for (let i = 0; i < this.dna.length; i++) {
      if (random(1) < mutationRate) {
        this.dna[i] = p5.Vector.random2D().setMag(0.1);
      }
    }
  }
}

---

🔹 예제 4: 형태 진화 (색상 + 크기 최적화)

let population = [];
let popSize = 100;
let targetColor;
let targetSize = 50;
let generation = 1;

function setup() {
  createCanvas(600, 600);
  targetColor = color(255, 100, 150); // 목표 색상
  
  for (let i = 0; i < popSize; i++) {
    population.push(new Circle());
  }
}

function draw() {
  background(0);
  
  // 목표 표시
  fill(targetColor);
  circle(width / 2, 100, targetSize);
  fill(255);
  textAlign(CENTER);
  text("Target", width / 2, 150);
  
  // 현재 세대 표시
  for (let i = 0; i < population.length; i++) {
    let x = (i % 10) * 60 + 30;
    let y = floor(i / 10) * 60 + 200;
    population[i].show(x, y);
  }
  
  // 정보
  fill(255);
  textAlign(LEFT);
  text("Generation: " + generation, 10, 20);
  
  // 한 프레임마다 진화
  if (frameCount % 60 === 0) {
    evolve();
    generation++;
  }
}

function evolve() {
  // 적합도 계산
  for (let circle of population) {
    circle.calcFitness(targetColor, targetSize);
  }
  
  // 정규화
  let maxFit = 0;
  for (let circle of population) {
    if (circle.fitness > maxFit) {
      maxFit = circle.fitness;
    }
  }
  for (let circle of population) {
    circle.fitness /= maxFit;
  }
  
  // 선택
  let matingPool = [];
  for (let circle of population) {
    let n = floor(circle.fitness * 100);
    for (let i = 0; i < n; i++) {
      matingPool.push(circle);
    }
  }
  
  // 교배 및 돌연변이
  let newPopulation = [];
  for (let i = 0; i < popSize; i++) {
    let parentA = random(matingPool);
    let parentB = random(matingPool);
    let child = parentA.crossover(parentB);
    child.mutate();
    newPopulation.push(child);
  }
  
  population = newPopulation;
}

class Circle {
  constructor(r, g, b, size) {
    if (r === undefined) {
      this.r = random(255);
      this.g = random(255);
      this.b = random(255);
      this.size = random(10, 80);
    } else {
      this.r = r;
      this.g = g;
      this.b = b;
      this.size = size;
    }
    this.fitness = 0;
  }
  
  show(x, y) {
    fill(this.r, this.g, this.b);
    circle(x, y, this.size);
  }
  
  calcFitness(targetCol, targetSize) {
    let dr = abs(this.r - red(targetCol));
    let dg = abs(this.g - green(targetCol));
    let db = abs(this.b - blue(targetCol));
    let colorDist = (dr + dg + db) / 3;
    
    let sizeDist = abs(this.size - targetSize);
    
    let totalDist = colorDist + sizeDist;
    this.fitness = map(totalDist, 0, 255 + 80, 255 + 80, 0);
  }
  
  crossover(partner) {
    let childR = random(1) < 0.5 ? this.r : partner.r;
    let childG = random(1) < 0.5 ? this.g : partner.g;
    let childB = random(1) < 0.5 ? this.b : partner.b;
    let childSize = random(1) < 0.5 ? this.size : partner.size;
    
    return new Circle(childR, childG, childB, childSize);
  }
  
  mutate() {
    let mutationRate = 0.05;
    
    if (random(1) < mutationRate) {
      this.r += random(-20, 20);
      this.r = constrain(this.r, 0, 255);
    }
    if (random(1) < mutationRate) {
      this.g += random(-20, 20);
      this.g = constrain(this.g, 0, 255);
    }
    if (random(1) < mutationRate) {
      this.b += random(-20, 20);
      this.b = constrain(this.b, 0, 255);
    }
    if (random(1) < mutationRate) {
      this.size += random(-5, 5);
      this.size = constrain(this.size, 10, 80);
    }
  }
}

---

🔑 핵심 개념 정리

유전 알고리즘의 4대 요소

1. 집단(Population): 여러 개체를 동시에 평가
2. 적합도(Fitness): 목표에 대한 평가 기준
3. 선택(Selection): 우수한 개체를 선호
4. 변이(Variation): 교배와 돌연변이로 다양성 유지

장점

• 복잡한 최적화 문제를 해결 가능
• 지역 최적해에 갇히지 않음 (돌연변이 덕분)
• 병렬 탐색으로 효율적

활용 분야

• 게임 AI (캐릭터 행동 학습)
• 건축/디자인 최적화
• 경로 탐색
• 스케줄링
• 생성 아트

---

🎨 실험 아이디어

• 돌연변이율을 조정하면 어떻게 되는지 관찰해보세요
• 적합도 함수를 다르게 설계하면 어떤 형태가 나올까요?
• 여러 목표를 동시에 만족하는 개체를 진화시켜보세요
• 교배 방식(1점 교배, 2점 교배, 균등 교배)을 바꿔보세요