Creative Coding 독학 제309일 2025년01월30일(목)

2025년 1월 30일

오늘은 Genetic Algorithm 기반 Travelling Salesman Problem 전체 코드를 살펴보고 플레이 해 보는 날~^^*

노란 햇살이 가만히 다가오는 아늑한 소리에 몸을 푸시기 바래요~^^* 코드 정리해서 돌아올게요~^^* 쓩우웅~^^*

하나. 어제까지 우리가 함께 공부하며 만들어 본 함수들을 모두 한 곳에 모아 보겠습니다~^^* YEAH~^^*

const cities = [];
const totalCities = 10;

const popSize = 500;
const fitness = [];

let population = [];
let recordDistance = Infinity;
let bestEver;

function setup() {
  createCanvas(400, 400);
  const order = [];
  
  for (let i = 0; i < totalCities; i++) {
    const v = createVector(random(width), random(height));
    cities[i] = v;
    order[i] = i;
  }
  for (let i = 0; i < popSize; i++) {
    population[i] = shuffle(order);
  }
}

function draw() {
  background(0);

  calculateFitness();
  normalizeFitness();
  nextGeneration();

  stroke(255);
  strokeWeight(4);
  noFill();
  beginShape();
  for (let i = 0; i < bestEver.length; i++) {
    const n = bestEver[i];
    vertex(cities[n].x, cities[n].y);
    ellipse(cities[n].x, cities[n].y, 16, 16);
  }
  endShape();
}

function calculateFitness() {
  for (let i = 0; i < population.length; i++) {
    const d = calcDistance(cities, population[i]);
    if (d < recordDistance) {
      recordDistance = d;
      bestEver = population[i];
    }
    fitness[i] = 1 / (d + 1);
  }
}

function calcDistance(points, order) {
  let sum = 0;
  
  for (let i = 0; i < order.length - 1; i++) {
    const cityAIndex = order[i];
    const cityA = points[cityAIndex];
    const cityBIndex = order[i + 1];
    const cityB = points[cityBIndex];
    const d = dist(cityA.x, cityA.y, cityB.x, cityB.y);
    sum += d;
  }
  return sum;
}

function normalizeFitness() {
  let sum = 0;
  
  for (let i = 0; i < fitness.length; i++) {
    sum += fitness[i];
  }
  for (let i = 0; i < fitness.length; i++) {
    fitness[i] = fitness[i] / sum;
  }
}

function nextGeneration() {
  const newPopulation = [];
  
  for (var i = 0; i < population.length; i++) {
    const orderA = pickOne(population, fitness);
    const orderB = pickOne(population, fitness);
    const order = crossOver(orderA, orderB);
    mutate(order);
    newPopulation[i] = order;
  }
  population = newPopulation;
}

function pickOne(list, prob) {
  let index = 0;
  let r = random(1);

  while (r > 0) {
    r = r - prob[index];
    index++;
  }
  index--;
  return list[index].slice();
}

function crossOver(orderA, orderB) {
  const start = floor(random(orderA.length));
  const end = floor(random(start + 1, orderA.length));
  const neworder = orderA.slice(start, end);

  for (let i = 0; i < orderB.length; i++) {
    const city = orderB[i];
    if (!neworder.includes(city)) {
      neworder.push(city);
    }
  }
  return neworder;
}

function mutate(order) {
    const indexA = floor(random(order.length));
    const indexB = floor(random(order.length));
    swap(order, indexA, indexB); 
}

function swap(a, i, j) {
  const temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

자, 그럼, Genetic Algorithm을 기반으로 하는 Travelling Salesman Problem 외판원 문제 프로그램을 작동시켜 볼까요~^^*

둘. 이번에는 fitness 값의 변별력을 좀더 키워보겠습니다. 함수 pow()를 사용하여 거리값을 8승증폭시켜 사용해 볼게요~^^* 거리값이 크면 fitness 값이 엄청엄청 작아질 것 같아요~^^*

function calculateFitness() {
   .
   .
   .
    fitness[i] = 1 / (pow(d, 8) + 1);
  }
}

fitness 값의 변별력이 높아진 버전을 작동시켜 볼까요~^^*

셋. 지금까지는 돌연변이를 생성할 때 배열의 구성요소 두 개를 무작위로 뽑아서 서로 맞바꾸었는데요. (1) 이번에는 돌연변이 생성 확률을 조정할 수 있도록 개선해 보겠습니다. (2) 배열의 서로 이웃하는 구성요소를 맞바꾸어 보겠습니다.

const mutateR = 0.01;

function nextGeneration() {
  const newPopulation = [];
  for (var i = 0; i < population.length; i++) {
    const orderA = pickOne(population, fitness);
    const orderB = pickOne(population, fitness);
    const order = crossOver(orderA, orderB);
    mutate(order, mutateR);
    newPopulation[i] = order;
  }
  population = newPopulation;

}

function mutate(order, mutationRate) {
  for (let i = 0; i < totalCities; i++) {
    if (random(1) < mutationRate) {

      const indexA = floor(random(order.length));
      const indexB = (indexA + 1) % totalCities;
      //indexA는 무작위로 뽑구요~^^*
      //indexB에는 indexA 바로 다음 구성요소를 저장하겠습니다.
      // % 나머지값 연산자를 사용하여, 
      // indexA가 배열의 맨 마지막 구성요소일 경우, 
      // indexB에는 배열의 첫번째 구성요소를 저장하겠습니다. 
      // 예를 들어, 총 도시 갯수가 3일 때, 
      // 만약 우리가 마지막 구성요소 order[2]를 indexA로 뽑았다면,
      // indexB에는 3을 3으로 나누었을 때의 나머지 값 0을 저장하겠습니다. 
      // order[2]와 order[0], 
      // 즉, 맨 마지막 구성요소와 첫번째 구성요소를 맞바꾸게 되겠네요. 
      // % 나머지값 연산자를 사용하면, 
      // indexA가 마지막 구성요소가 아닐 경우, 
      // indexB는 indexA의 바로 다음 구성요소가 저장됩니다. 
      // 예를 들어 order[1]을 indexA로 뽑는다면, 
      // (1 + 1) % 3 = 2 % 3 = 2 
      // 2를 3으로 나누면, 몫은 0이고 나머지는 2이니까요~^^*  
  
      swap(order, indexA, indexB);
    }
  }
}

개선된 mutation 함수를 테스트 해 볼까요~^^* 우리~^^*

네~^^* 오늘 저와 함께 전체 코드를 살펴보고 fitness 적합성 변별력 향상과 mutate 함수 개선 작업을 해 주셔서 감사합니다~^^*

와우…신기한 것 같아요. Genetic Algorithm으로 Travelling Salesman Problem도 해결할 수 있다는 것이요~~^^*

이 과정을 위해서 우리가 동영상 강의 2개 분량을 소화해 내었어요~~^^*