Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
236 lines (214 sloc) 6.24 KB
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<meta name=”viewport” content=”width=960">
<title>genetic-algorithm</title>
<style>
body{
margin: 0;
padding: 0;
}
</style>
</head>
<body>
<canvas id="canvas" width="960" height="540" style="background: black"></canvas>
<script>
const canvas = document.querySelector("canvas");
const context = canvas.getContext("2d");
const generationSize = 180;
const genomeSize = 360;
const radius = canvas.width / (generationSize * 2);
let generation = 0;
let currentAge = [];
let newAge = [];
const INDIVIDUAL_MUTATION = 0.05;
const GENOME_MUTATION = 0.05;
let goal = [];
// 生物個体を表すクラスです
class Biont {
constructor(genome) {
this.genome = genome;
}
/**
* 適応度を取得します
* @param goal
*/
getEvaluation(goal) {
let score = 0;
for (let i = 0; i < this.genome.length; i++) {
if (goal[i] === this.genome[i]) {
score++;
}
}
return score / this.genome.length;
}
/**
* genomeの要素を足し合わせ、合計の数値を返します
*/
getColor() {
return this.genome.reduce((total, current) => {
return total + current;
}, 0);
}
/**
* 遺伝子配列を更新します
* @param genome
*/
setGenome(genome) {
this.genome = genome;
}
}
/**
* 適応度の高い遺伝子を持つ個体をvalue体だけ選別します
* @param age
* @param value
*/
function getElite(age, value) {
const elite = age.sort((a, b) => {
return b.getEvaluation(goal) - a.getEvaluation(goal);
});
return elite.slice(0, value);
}
/**
* 引数bios1, bios2の遺伝子配列を交叉させた子を返します
* @param bios1
* @param bios2
*/
function getCrossedProgeny(bios1, bios2) {
// bios1とbios2の遺伝子配列のcrossOne番目からcrossTwo番目を交換します
const crossOne = Math.round(Math.random() * genomeSize);
const crossTwo =
crossOne + Math.round(Math.random() * (genomeSize - crossOne));
const one = bios1.genome;
const two = bios2.genome;
const progenyOne = [
...one.slice(0, crossOne),
...two.slice(crossOne, crossTwo),
...one.slice(crossTwo, genomeSize)
];
const progenyTwo = [
...two.slice(0, crossOne),
...one.slice(crossOne, crossTwo),
...two.slice(crossTwo, genomeSize)
];
return [new Biont(progenyOne), new Biont(progenyTwo)];
}
/**
* 次世代を作ります
* @param age
* @param elite
* @param progeny
*/
function getNextGeneration(age, elite, progeny) {
const sortedAge = age.sort((a, b) => {
return a.getEvaluation(goal) - b.getEvaluation(goal);
});
sortedAge.splice(0, elite.length + progeny.length);
sortedAge.push(...elite, ...progeny);
return sortedAge;
}
/**
* 遺伝子に変異を加えます。
* @param age
* @param individualMutationRate:個体が変異する確率です
* @param genomeMutationRateRate:個々の遺伝子の変異確率です
*/
function mutate(age, individualMutationRate, genomeMutationRateRate) {
const boids = [];
age.forEach(biont => {
// 確率的に変異させる個体を選別します
if (individualMutationRate > Math.random()) {
const mutatedGenome = [];
biont.genome.forEach(genome => {
// 確率的に変異させる遺伝子を選別します
if (genomeMutationRateRate > Math.random()) {
mutatedGenome.push(Math.round(Math.random()));
} else {
mutatedGenome.push(genome);
}
});
biont.setGenome(mutatedGenome);
boids.push(biont);
} else {
boids.push(biont);
}
});
return boids;
}
/**
* 適応度の基準の配列を作ります
*/
function createGoal() {
// goalは[1, 1, 1, ...... , 1]となります
goal = Array(360).fill(1);
context.beginPath();
context.fillStyle = `hsl(${genomeSize},50%,50%)`;
context.rect(0, 0, canvas.width, 10);
context.fill();
}
/**
* 個体の遺伝子配列をランダムに作成します
*/
function createGenome() {
const initialGenome = [];
const c = Math.floor(Math.random() * genomeSize);
for (let i = 0; i < c; i++) {
initialGenome.push(1);
}
for (let j = 0; j < genomeSize - c; j++) {
initialGenome.push(0);
}
return new Biont(initialGenome);
}
/**
* 初期設定を行う関数です
*/
function setup() {
for (let i = 0; i < generationSize; i++) {
currentAge[i] = createGenome();
}
generation = 0;
createGoal();
}
setup();
/**
* timestampミリ秒ごとに処理を実行します
*/
function loop() {
if (generation < 66) {
// selection
const elite = getElite(currentAge, 2);
// eliteの子供を作成
const progeny = [];
for (let i = 0; i < elite.length - 1; i++) {
progeny.push(...getCrossedProgeny(elite[i], elite[i + 1]));
}
// elite, progeny, 現在の世代から適応度の高い順に選別
newAge = getNextGeneration(currentAge, elite, progeny);
// 適度に変異を入れる
newAge = mutate(newAge, INDIVIDUAL_MUTATION, GENOME_MUTATION);
// 描画
newAge.forEach((age, index) => {
context.beginPath();
context.fillStyle = `hsl(${age.getColor()},50%,50%)`;
context.arc(
radius / 2 + index * 2 * radius,
canvas.height - (radius + radius * 3 * generation),
radius,
0,
2 * Math.PI
);
context.fill();
});
generation++;
// 次世代を現世代に
currentAge = newAge;
newAge = [];
}
window.requestAnimationFrame(loop);
}
loop()
</script>
</body>
</html>
You can’t perform that action at this time.