죽림고수에 유전 알고리즘 및 인공 신경망 적용하기
Algorithm
2024-10-20
유전 알고리즘과 인공 신경망이 어떤 구조를 가지고 있는지 알아보고, 게임 죽림고수를 플레이 하면서 이해합니다.
이전 포스트인 죽림고수 만들기와 연결됩니다!
Contents
유전 알고리즘이란?
유전 알고리즘은 자연 선택과 유전학을 바탕으로 한 탐색 알고리즘으로 최적의 개체를 찾는 데 사용됩니다. 유전 알고리즘은 (초기 개체 생성) → (적합도 평가) → (종료 조건 검사) → (선택) → (연산)의 사이클을 반복하며 종료 조건에 더 가까운 개체를 생성합니다. 이러한 과정을 진화로 표현할 수 있으며, 개체를 점진적으로 개선합니다.
유전 알고리즘의 단계
초기 개체 생성
우선 무작위로 초기 개체를 생성합니다. 이 개체들은 진화 과정에서 유전자에 해당합니다.
적합도 평가
현재 세대의 개체를 보통 적합도 함수를 사용하여 평가합니다.
종료 조건 검사
현재 세대의 개체가 종료 조건을 만족하는지 확인합니다. 이를 만족하는 경우 알고리즘을 종료하고, 만족하지 않는 경우 선택 단계로 이동합니다.
선택
다음 세대 개체를 만들기 위해 적합도 평가가 우수한 개체들을 선택합니다.
연산 (교차, 돌연변이)
선택된 개체들을 교차 연산하여 다음 세대의 개체를 만듭니다. (부모가 자식을 낳는 과정과 유사합니다.)
다음 개체들의 일부 유전자는 무작위로 변경될 수 있습니다. 이는 새로운 개체 (해결 방안)을 탐색하는 데 중요한 역할을 합니다.
유전 알고리즘 구조도
인공 신경망이란?
인공 신경망이란 데이터를 입력받아 학습하고, 이를 바탕으로 예측이나 분류를 수행하는 알고리즘이며, 인간의 뇌에서 정보를 처리하는 방식에서 영감을 받아 만들었습니다.
인공 신경망의 구성 요소
노드 (Neuron)
인공신경망의 기본 단위로 각 노드는 입력을 받아 처리하고, 출력값을 생성합니다. 노드는 생물학적 신경세포와 유사하게 작동합니다.
층 (Layer)
- 입력층 (Input Layer): 외부 데이터 (인풋 값)를 받아들이는 층으로 입력값의 수는 이 층의 노드 수에 따라 결정됩니다.
- 은닉층 (Hidden Layer): 입력층과 출력층 사이에 위치한 층으로, 데이터의 복잡한 패턴을 학습하는 역할을 합니다. 여러 개의 은닉층을 사용할 수 있으며, 이는 신경망의 깊이를 결정합니다.
- 출력층 (Output Layer): 신경망의 최종 결과를 출력하는 층으로 예측하려는 결과의 수에 따라 노드 수가 결정됩니다.
인공 신경망 구조
인공 신경망 예제
아래 코드는 인공신경망을 통해 XOR 문제를 해결하는 예제입니다. Trainer 인스턴스를 생성하고, XOR 문제의 데이터셋으로 훈련합니다. 데이터셋은 각 입력에 대한 출력을 제공합니다.
import "./style.css";
import { Architect, Trainer } from "synaptic";
const myNetwork = new Architect.Perceptron(2, 3, 1);
const trainer = new Trainer(myNetwork);
trainer.train([
{ input: [0, 0], output: [0] },
{ input: [0, 1], output: [1] },
{ input: [1, 0], output: [1] },
{ input: [1, 1], output: [0] },
]);
document.querySelector("#app").innerHTML = `
<div>
<div class="card">
<button id="predict" type="button">Predict XOR(1, 0)</button>
<p id="prediction-result"></p>
</div>
</div>
`;
document.querySelector("#predict").addEventListener("click", () => {
const result = myNetwork.activate([1, 0]);
document.querySelector(
"#prediction-result"
).innerText = `Prediction for XOR(1, 0): ${result}`;
});아래는 이에 따른 실행 결과입니다. (1, 0)의 경우 정답이 1이며 근접하게 나오는 것을 확인할 수 있습니다.
1차: Prediction for XOR(1, 0): 0.9150900470368268
2차: Prediction for XOR(1, 0): 0.9106759543031171
3차: Prediction for XOR(1, 0): 0.9295060753265536
synaptic 예제 페이지에서 더 자세한 내용을 확인하실 수 있습니다.
죽림고수에 유전 알고리즘과 인공신경망 적용하기
아래는 죽림고수에 적용할 인공 신경망입니다. Input Layer에는 캐릭터의 위치 (x, y), 화살의 위치(x, y), 화살의 속도 (vx, vy)로 이루어져 8개의 Hidden Layer를 거쳐 움직임에 해당하는 Output Layer가 출력됩니다.
죽림고수에 적용할 인공 신경망 구조
죽림고수 로직 이해하기
- 방향키를 사용하여 캐릭터를 움직입니다.
- 캐릭터를 움직이면서 날아오는 화살을 피합니다.
- 계속 화살을 피하면서 최대한 오래 생존합니다.
알고리즘 계획하기
- 10마리의 캐릭터로 이루어진 집단을 만듭니다.
- 캐릭터의 위치, 화살의 위치, 화살의 벡터 값을 인공 신경망을 통해 학습합니다.
- 화살과 충돌하면 유전자를 교배풀에 저장합니다.
- 적응도가 높은 신경망 (Network)를 선택하여 자식 캐릭터를 생성합니다.
- 위 과정을 계속 반복합니다.
인공 신경망 적용하기
위 사진과 같은 구조를 synaptic을 통해 적용합니다.
const setupNeuralNetwork = () => {
const inputLayer = new Layer(6);
const hiddenLayer = new Layer(8);
const outputLayer = new Layer(4);
inputLayer.project(hiddenLayer);
hiddenLayer.project(outputLayer);
const network = new Network({
input: inputLayer,
hidden: [hiddenLayer],
output: outputLayer,
});
return network;
};그리고 고양이 캐릭터 클래스를 만들어 input을 주입합니다.
class Cat {
constructor(x, y, index) {
this.x = x;
this.y = y;
this.index = index;
this.brain = setupNeuralNetwork();
this.alive = true;
this.survive;
}
think(arrows, p) {
let closestArrow = null;
let minDistance = Infinity;
for (const arrow of arrows) {
const dist = p.dist(this.x, this.y, arrow.x, arrow.y);
if (dist < minDistance) {
minDistance = dist;
closestArrow = arrow;
}
}
const K = 5000;
if (closestArrow) {
console.log("Closest Arrow:", closestArrow);
const inputs = [
this.x * K,
this.y * K,
closestArrow.x * K,
closestArrow.y * K,
closestArrow.vx * K,
closestArrow.vy * K,
];
console.log("Inputs:", inputs);
const output = this.brain.activate(inputs);
console.log("Output:", output);
console.log(
`${this.index}번: Output: Up: ${output[0]}, Down: ${output[1]}, Left: ${output[2]}, Right: ${output[3]}, x: ${this.x}, y: ${this.y}`
);
const Dy = output[0] - output[1];
const Dx = output[2] - output[3];
if (Dy > 0 && this.y < p.height) {
this.y += Dy * 10;
} else if (Dy < 0 && this.y + catImage.height * catScalar > 0) {
this.y += Dy * 10;
}
if (Dx > 0 && this.x + catImage.weight * catScalar < p.width) {
this.x += Dx * 10;
} else if (Dx < 0 && this.x > 0) {
this.x += Dx * 10;
}
const centerX = p.width / 2;
const centerY = p.height / 2;
const radius = Math.min(p.width, p.height) / 2 - 10;
const distanceFromCenter = Math.sqrt(
(this.x - centerX) ** 2 + (this.y - centerY) ** 2
);
if (distanceFromCenter > radius) {
const angle = Math.atan2(this.y - centerY, this.x - centerX);
this.x = centerX + radius * Math.cos(angle);
this.y = centerY + radius * Math.sin(angle);
}
}
}
}캐릭터의 위치 (x, y), 화살의 위치(x, y), 화살의 속도 (vx, vy)로 이루어진 input이 인공 신경망을 거쳐 output이 출력됩니다. output은 0에서 1사이에 값들을 가진 배열이며, 배열의 각 값은 하, 상, 좌, 우로 움직여야 한다라고 판단하는 정도입니다.
유전 알고리즘 적용하기
위에서 적용한 인공 신경망을 지닌 고양이들 중 우수 개체들을 선별하여 다음 세대로 brain (인공 신경망)을 상속합니다.
const crossover = (brain1, brain2) => {
const newBrain = setupNeuralNetwork();
newBrain.layers.hidden.forEach((layer, i) => {
layer.list.forEach((neuron, j) => {
Object.values(neuron.connections.projected).forEach((connection, k) => {
const parentConnection =
Math.random() > 0.5
? Object.values(
brain1.layers.hidden[i].list[j].connections.projected
)[k]
: Object.values(
brain2.layers.hidden[i].list[j].connections.projected
)[k];
connection.weight = parentConnection.weight;
});
});
});
return newBrain;
};crossover()는 상위 2개 개체 (고양이 캐릭터) 중 랜덤하게 하나를 골라 상속하는 함수입니다.
const mutate = (network) => {
network.layers.hidden.forEach((layer) => {
layer.list.forEach((neuron) => {
Object.values(neuron.connections.projected).forEach((connection) => {
if (Math.random() < 0.1) {
connection.weight += Math.random() * 0.2 - 0.1;
}
});
});
});
};그리고 mutate()를 통해 돌연변이를 생성해줍니다. 돌연변이는 weight 값에 영향을 줍니다.
const generateCats = (brain1, brain2) => {
generation++;
cats = [];
for (let i = 0; i < 10; i++) {
let newBrain;
if (brain1 && brain2) {
newBrain = crossover(brain1, brain2);
mutate(newBrain);
} else {
newBrain = setupNeuralNetwork();
}
const newCat = new Cat(281, 281, i);
newCat.brain = newBrain;
cats.push(newCat);
}
};다음으로 위 함수들을 기반으로 10마리 모두 죽었을 때 새로운 집단을 생성합니다.
전체 코드
import p5 from "p5";
import catImageSrc from "./assets/cat.webp";
import backgroundImage from "./assets/background.webp";
import { Layer, Network } from "synaptic";
let catImage;
let catScalar = 0.05;
let cats = [];
let arrows = [];
let arrowSpeed = 2;
let arrowSpawnInterval = (Math.random() * 0.5 + 0.5) * 1000;
setInterval(() => {
arrowSpawnInterval = (Math.random() * 0.5 + 0.5) * 1000;
}, 500);
let lastMultipleArrowTime = 0;
let generation = 1;
let startTime = Date.now();
let brains = [];
let records = [];
/** 현재 시간 */
const getElapsedTime = () => {
const currentTime = Date.now();
const elapsedTime = (currentTime - startTime) / 1000;
return elapsedTime.toFixed(2);
};
/** 고양이 클래스 */
class Cat {
constructor(x, y, index) {
this.x = x;
this.y = y;
this.index = index;
this.brain = setupNeuralNetwork();
this.alive = true;
this.survive;
}
/** 고양이 움직임 판단 */
think(arrows, p) {
let closestArrow = null;
let minDistance = Infinity;
for (const arrow of arrows) {
const dist = p.dist(this.x, this.y, arrow.x, arrow.y);
if (dist < minDistance) {
minDistance = dist;
closestArrow = arrow;
}
}
const K = 5000;
if (closestArrow) {
console.log("Closest Arrow:", closestArrow);
const inputs = [
this.x * K,
this.y * K,
closestArrow.x * K,
closestArrow.y * K,
closestArrow.vx * K,
closestArrow.vy * K,
];
console.log("Inputs:", inputs);
const output = this.brain.activate(inputs);
console.log("Output:", output);
console.log(
`${this.index}번: Output: Up: ${output[0]}, Down: ${output[1]}, Left: ${output[2]}, Right: ${output[3]}, x: ${this.x}, y: ${this.y}`
);
const Dy = output[0] - output[1];
const Dx = output[2] - output[3];
if (Dy > 0 && this.y < p.height) {
this.y += Dy * 10;
} else if (Dy < 0 && this.y + catImage.height * catScalar > 0) {
this.y += Dy * 10;
}
if (Dx > 0 && this.x + catImage.weight * catScalar < p.width) {
this.x += Dx * 10;
} else if (Dx < 0 && this.x > 0) {
this.x += Dx * 10;
}
const centerX = p.width / 2;
const centerY = p.height / 2;
const radius = Math.min(p.width, p.height) / 2 - 10;
const distanceFromCenter = Math.sqrt(
(this.x - centerX) ** 2 + (this.y - centerY) ** 2
);
if (distanceFromCenter > radius) {
const angle = Math.atan2(this.y - centerY, this.x - centerX);
this.x = centerX + radius * Math.cos(angle);
this.y = centerY + radius * Math.sin(angle);
}
}
}
}
/** 고양이 인공 신경망 구조 */
const setupNeuralNetwork = () => {
const inputLayer = new Layer(6);
const hiddenLayer = new Layer(8);
const outputLayer = new Layer(4);
inputLayer.project(hiddenLayer);
hiddenLayer.project(outputLayer);
const network = new Network({
input: inputLayer,
hidden: [hiddenLayer],
output: outputLayer,
});
return network;
};
/** 돌연변이 생성 */
const mutate = (network) => {
network.layers.hidden.forEach((layer) => {
layer.list.forEach((neuron) => {
Object.values(neuron.connections.projected).forEach((connection) => {
if (Math.random() < 0.1) {
connection.weight += Math.random() * 0.2 - 0.1;
}
});
});
});
};
/** 상위 2개 brain을 랜덤으로 결정한 후 다음 세대에 상속 */
const crossover = (brain1, brain2) => {
const newBrain = setupNeuralNetwork();
newBrain.layers.hidden.forEach((layer, i) => {
layer.list.forEach((neuron, j) => {
Object.values(neuron.connections.projected).forEach((connection, k) => {
const parentConnection =
Math.random() > 0.5
? Object.values(
brain1.layers.hidden[i].list[j].connections.projected
)[k]
: Object.values(
brain2.layers.hidden[i].list[j].connections.projected
)[k];
connection.weight = parentConnection.weight;
});
});
});
return newBrain;
};
/** 새 세대 고양이 생성 */
const generateCats = (brain1, brain2) => {
generation++;
cats = [];
for (let i = 0; i < 10; i++) {
let newBrain;
if (brain1 && brain2) {
newBrain = crossover(brain1, brain2);
mutate(newBrain);
} else {
newBrain = setupNeuralNetwork();
}
const newCat = new Cat(281, 281, i);
newCat.brain = newBrain;
cats.push(newCat);
}
};
/** 현재 남은 개체 수 */
const updateRemainingCats = () => {
const remainingCats = cats.filter((cat) => cat.alive).length;
const remainingCatsElement = document.getElementById("remain");
remainingCatsElement.innerText = `남은 개체 수: ${remainingCats}`;
};
/** p5.js 함수 */
const sketch = (p) => {
/** 고양이 캐릭터 로딩 */
p.preload = () => {
catImage = p.loadImage(catImageSrc);
};
/** 초기 설정 (1번만 실행됨) */
p.setup = () => {
const canvas = p.createCanvas(562, 562);
canvas.parent("canvas");
const backgroundImg = document.getElementById("background");
backgroundImg.src = backgroundImage;
const generationElement = document.getElementById("generation");
generationElement.innerText = `${generation}세대`;
setInterval(spawnArrow, arrowSpawnInterval);
generateCats();
updateSeconds();
updateRemainingCats();
};
/** 반복 실행 설정 (반복됨) */
p.draw = () => {
p.background(32, 34, 57);
/** 생존 중인 고양이에 대한 함수 */
cats.forEach((cat) => {
if (cat.alive) {
cat.think(arrows, p);
arrows.forEach((arrow) => {
if (checkCollision(cat, arrow, p)) {
cat.alive = false;
cat.survive = getElapsedTime();
}
});
p.image(
catImage,
cat.x,
cat.y,
catImage.width * catScalar,
catImage.height * catScalar
);
}
});
/** 화살 모양 함수 */
arrows.forEach((arrow) => {
arrow.x += arrow.vx * arrowSpeed;
arrow.y += arrow.vy * arrowSpeed;
if (
arrow.x < 0 ||
arrow.x > p.width ||
arrow.y < 0 ||
arrow.y > p.height
) {
arrows.splice(arrows.indexOf(arrow), 1);
}
p.stroke(255, 255, 255);
p.strokeWeight(4);
p.line(
arrow.x,
arrow.y,
arrow.x - arrow.vx * 10,
arrow.y - arrow.vy * 10
);
});
updateRemainingCats();
/** 모든 개체가 죽은 경우 */
if (cats.every((cat) => !cat.alive)) {
arrows = [];
cats.sort((a, b) => b.survive - a.survive);
const generationElement = document.getElementById("generation");
generationElement.innerText = `${generation}세대`;
brains[generation - 1] = [cats[0].brain, cats[1].brain];
records[generation - 1] = cats[0].survive;
console.log(cats[0].brain, cats[1].brain);
console.log(brains);
console.log(records);
generateCats(cats[0].brain, cats[1].brain);
startTime = Date.now();
}
/** 화살 생성 간격 조절 */
if (getElapsedTime() - startTime > 10000) {
arrowSpawnInterval = Math.max(500, arrowSpawnInterval - 100);
startTime = getElapsedTime();
}
/** 동시에 많은 화살 생성 간격 */
if (getElapsedTime() / 1000 - lastMultipleArrowTime >= 10) {
spawnMultipleArrows(((getElapsedTime() / 1000) * 3) / 5 + 10);
lastMultipleArrowTime = getElapsedTime() / 1000;
}
};
/** 화살 생성 */
function spawnArrow() {
const edge = Math.floor(Math.random() * 4);
let arrow = { x: 0, y: 0, vx: 0, vy: 0 };
const angleOffset = (Math.random() * Math.PI) / 6;
switch (edge) {
case 0:
arrow.x = Math.random() * p.width;
arrow.y = 0;
const angle0 =
Math.PI / 2 + (Math.random() < 0.5 ? -angleOffset : angleOffset);
arrow.vx = Math.cos(angle0) * arrowSpeed;
arrow.vy = Math.sin(angle0) * arrowSpeed;
break;
case 1:
arrow.x = p.width;
arrow.y = Math.random() * p.height;
const angle1 =
Math.PI + (Math.random() < 0.5 ? -angleOffset : angleOffset);
arrow.vx = Math.cos(angle1) * arrowSpeed;
arrow.vy = Math.sin(angle1) * arrowSpeed;
break;
case 2:
arrow.x = Math.random() * p.width;
arrow.y = p.height;
const angle2 =
-Math.PI / 2 + (Math.random() < 0.5 ? -angleOffset : angleOffset);
arrow.vx = Math.cos(angle2) * arrowSpeed;
arrow.vy = Math.sin(angle2) * arrowSpeed;
break;
case 3:
arrow.x = 0;
arrow.y = Math.random() * p.height;
const angle3 = Math.random() < 0.5 ? angleOffset : -angleOffset;
arrow.vx = Math.cos(angle3) * arrowSpeed;
arrow.vy = Math.sin(angle3) * arrowSpeed;
break;
}
arrows.push(arrow);
}
/** 동시 화살 생성 */
function spawnMultipleArrows(count) {
for (let i = 0; i < count; i++) {
spawnArrow();
}
}
/** UI 시간 업데이트 */
function updateSeconds() {
const secondsOutput = document.getElementById("seconds");
if (secondsOutput) {
secondsOutput.innerText = `${getElapsedTime()}초`;
}
requestAnimationFrame(updateSeconds);
}
/** 고양이 위치 및 화살 인식 오류 제거 */
function checkCollision(cat, arrow, p) {
const catLeft = cat.x;
const catRight = cat.x + catImage.width * catScalar;
const catTop = cat.y;
const catBottom = cat.y + catImage.height * catScalar;
const arrowLeft = arrow.x - arrow.vx * 10;
const arrowRight = arrow.x;
const arrowTop = arrow.y - arrow.vy * 10;
const arrowBottom = arrow.y;
return !(
catLeft > arrowRight ||
catRight < arrowLeft ||
catTop > arrowBottom ||
catBottom < arrowTop
);
}
};
new p5(sketch);결과
기록
212세대 까지의 기록: data.js
실험 중 건드리지 않는 착한 디미고 친구들
바로 변질됨
실험은 배포된 페이지에서, 더 자세한 코드는 Github에서 확인하실 수 있습니다.
긴 글 읽어주셔서 감사합니다.