304 lines
8.2 KiB
HTML
304 lines
8.2 KiB
HTML
<!DOCTYPE html>
|
|
<html lang="en" dir="ltr">
|
|
<head>
|
|
<title>Genetic Algorithm - Experiments - srifqi</title>
|
|
<meta charset="utf-8">
|
|
<meta name="author" content="srifqi">
|
|
<meta name="description" content="An example of genetic algorithm in action">
|
|
<meta name="viewport" content="width=device-width,height=device-height,initial-scale=1">
|
|
<style>
|
|
noscript, .noscript {
|
|
background: #fff9c4;
|
|
border: 4px solid #fff176;
|
|
border-radius: 4px;
|
|
display: block;
|
|
padding: 4px;
|
|
margin: 8px;
|
|
}
|
|
|
|
noscript, .noscript, noscript *, .noscript * {
|
|
font: 12px sans-serif !important;
|
|
}
|
|
|
|
body {
|
|
font: 16px sans-serif;
|
|
overflow-x: hidden;
|
|
overflow-y: scroll;
|
|
text-align: center;
|
|
}
|
|
|
|
#form {
|
|
display: none;
|
|
text-align: left;
|
|
}
|
|
|
|
#form label {
|
|
display: block;
|
|
margin: 4px auto;
|
|
width: 350px;
|
|
}
|
|
|
|
#form br {
|
|
display: block;
|
|
height: 4px;
|
|
}
|
|
|
|
#form input {
|
|
background: white;
|
|
border: 1px solid #e0e0e0;
|
|
float: right;
|
|
height: 16px;
|
|
width: 200px;
|
|
}
|
|
|
|
pre {
|
|
font: 12px monospace;
|
|
line-height: 150%;
|
|
}
|
|
|
|
#canvas {
|
|
height: 200px;
|
|
width: 500px;
|
|
}
|
|
|
|
.p {
|
|
text-decoration: underline;
|
|
}
|
|
|
|
.p, .q {
|
|
background: lightgreen;
|
|
color: green;
|
|
}
|
|
|
|
.d {
|
|
background: pink;
|
|
color: red;
|
|
}
|
|
</style>
|
|
</head>
|
|
<body>
|
|
<h1 id="title">Hello, World!</h1>
|
|
<p>An example of genetic algorithm in action</p>
|
|
<noscript class="noscript">
|
|
For full functionality of this site, it is necessary to enable JavaScript.
|
|
Here are the <a href="https://www.enable-javascript.com/" target="_blank">
|
|
instructions how to enable JavaScript in your web browser</a>.
|
|
</noscript>
|
|
<p>
|
|
<button id="btnResume">Resume</button>
|
|
<button id="btnRestart" disabled="disabled">Restart</button>
|
|
<button id="btnEdit" disabled="disabled">Edit environment</button>
|
|
</p>
|
|
<p id="form">
|
|
<label>Population size: <input type="number" id="pSize" min="4" value="25"></label><br>
|
|
<label>Generation limit: <input type="number" id="genLim" min="1" value="500"></label><br>
|
|
<label>Target: <input type="text" id="trgtText"></label><br>
|
|
<label>Building blocks: <input type="text" id="bBlocks"></label>
|
|
</p>
|
|
<pre id="con"></pre>
|
|
<canvas id="canvas" width=500 height=200></canvas>
|
|
<script>
|
|
var POPULATION_SIZE = 25;
|
|
var POPULATION = new Array(POPULATION_SIZE);
|
|
var POPULATION_HISTORY = [];
|
|
var POPULATION_HISTORY_SAMPLE = 25;
|
|
var BLOCKS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 ,.!?";
|
|
var TARGET = "Hello, World!";
|
|
|
|
let GENERATION_NUM = 0;
|
|
var GENERATION_LIMIT = 500;
|
|
|
|
const a = canvas.getContext("2d");
|
|
const GRAPH_WIDTH = 500;
|
|
const GRAPH_SIZE = 100;
|
|
const g_max = new Array(GRAPH_SIZE);
|
|
|
|
const randomString = (length) => {
|
|
let res = new Array(length);
|
|
for (let i = 0; i < length; i ++)
|
|
res[i] = randomInt(BLOCKS.length);
|
|
return res;
|
|
};
|
|
|
|
const randomInt = (max) => Math.round(Math.random() * max - 0.5);
|
|
|
|
const toChromosome = (text) => text.split("").map(x => BLOCKS.indexOf(x));
|
|
const toText = (chromosome) => chromosome.map(x => BLOCKS[x]).join("");
|
|
|
|
let sqrtPopu = Math.floor(Math.sqrt(POPULATION_SIZE));
|
|
function updateGUI() {
|
|
con.innerHTML = "generation #" + GENERATION_NUM + "\n";
|
|
for (let i = 0; i < POPULATION_SIZE; i ++)
|
|
con.innerHTML += toText(POPULATION[i]) +
|
|
(i % sqrtPopu == sqrtPopu - 1 ? "\n" : " ");
|
|
title.innerText = toText(POPULATION[0]);
|
|
a.clearRect(0, 0, 500, 200);
|
|
let graph_max = Math.max(...g_max);
|
|
let graph_min = Math.min(...g_max);
|
|
a.strokeStyle = "blue";
|
|
a.beginPath();
|
|
a.moveTo(0, 200 - (g_max[0] - graph_min) / (graph_max - graph_min) * 200);
|
|
for (let i = 1; i < GRAPH_SIZE; i ++)
|
|
a.lineTo(i / GRAPH_SIZE * GRAPH_WIDTH, 200 - (g_max[i] - graph_min) / (graph_max - graph_min) * 200);
|
|
a.stroke();
|
|
a.fillText(graph_max, 0, 20);
|
|
a.fillText(graph_min, 0, 190);
|
|
}
|
|
|
|
function updateGUILast() {
|
|
updateGUI();
|
|
if (GENERATION_NUM % POPULATION_HISTORY_SAMPLE != 0)
|
|
POPULATION_HISTORY.push([GENERATION_NUM, POPULATION.slice(0)]);
|
|
let con_buf = "";
|
|
for (let k = POPULATION_HISTORY.length - 1; k >= 0; k --) {
|
|
con_buf += "generation #" + POPULATION_HISTORY[k][0] + "<br>";
|
|
for (let i = 0; i < POPULATION_SIZE; i ++) {
|
|
let person = toText(POPULATION_HISTORY[k][1][i]);
|
|
if (person == TARGET)
|
|
con_buf += "<span class=\"p\">" + person + "</span>";
|
|
else
|
|
for (let c = 0; c < TARGET.length; c ++)
|
|
con_buf += "<span class=\"" +
|
|
(person[c] == TARGET[c] ? "q" : "d") +
|
|
"\">" + person[c] + "</span>";
|
|
con_buf += (i % sqrtPopu == sqrtPopu - 1 ? "<br>" : " ");
|
|
}
|
|
con_buf += "<br>";
|
|
}
|
|
con.innerHTML = con_buf;
|
|
}
|
|
|
|
function init() {
|
|
GENERATION_NUM = 0;
|
|
TARGET_C = toChromosome(TARGET);
|
|
for (let i = 0; i < POPULATION_SIZE; i ++)
|
|
POPULATION[i] = randomString(TARGET.length);
|
|
POPULATION.sort((a, b) => fitness(b) - fitness(a));
|
|
for (let i = 0; i < GRAPH_SIZE; i ++)
|
|
g_max[i] = fitness(POPULATION[0]);
|
|
POPULATION_HISTORY.length = 0;
|
|
POPULATION_HISTORY.push([GENERATION_NUM, POPULATION.slice(0)]);
|
|
updateGUI();
|
|
}
|
|
|
|
function mutate(chromosome) {
|
|
if (Math.random() > 0.75)
|
|
return chromosome;
|
|
let pos = randomInt(chromosome.length);
|
|
let amount = randomInt(BLOCKS.length);
|
|
chromosome[pos] = (chromosome[pos] + amount) % BLOCKS.length;
|
|
return chromosome;
|
|
}
|
|
|
|
function crossover(parentA, parentB) {
|
|
let pos = randomInt(parentA.length);
|
|
let childA = parentA.slice(0, pos).concat(parentB.slice(pos, parentB.length));
|
|
let childB = parentB.slice(0, pos).concat(parentA.slice(pos, parentA.length));
|
|
return Math.random() < 0.5 ? childA : childB;
|
|
}
|
|
|
|
let TARGET_C;
|
|
function fitness(chromosome) {
|
|
let error = 0;
|
|
for (let i = 0; i < chromosome.length; i ++)
|
|
error -= Math.pow(chromosome[i] - TARGET_C[i], 2);
|
|
return error;
|
|
}
|
|
|
|
function generate() {
|
|
let newP = new Array(POPULATION_SIZE);
|
|
const POPULATION_SIZE_HALF = Math.floor(POPULATION_SIZE / 2);
|
|
const POPULATION_SIZE_QUARTER = Math.floor(POPULATION_SIZE / 4);
|
|
for (let i = 0; i < POPULATION_SIZE; i ++) {
|
|
let parentA = POPULATION[Math.floor(i / POPULATION_SIZE_QUARTER)];
|
|
let parentB = POPULATION[i % POPULATION_SIZE_QUARTER];
|
|
// console.log(i, Math.floor(i / POPULATION_SIZE_QUARTER), i % POPULATION_SIZE_QUARTER);
|
|
newP[i] = crossover(parentA, parentB);
|
|
}
|
|
for (let i = 0; i < POPULATION_SIZE; i ++)
|
|
POPULATION[i] = mutate(newP[i]);
|
|
POPULATION.sort((a, b) => fitness(b) - fitness(a));
|
|
g_max.shift();
|
|
g_max.push(fitness(POPULATION[0]));
|
|
GENERATION_NUM ++;
|
|
if (GENERATION_NUM % POPULATION_HISTORY_SAMPLE == 0)
|
|
POPULATION_HISTORY.push([GENERATION_NUM, POPULATION.slice(0)]);
|
|
updateGUI();
|
|
}
|
|
|
|
function runner() {
|
|
if (title.innerText == TARGET || GENERATION_NUM >= GENERATION_LIMIT) {
|
|
clearInterval(timer);
|
|
timer = undefined;
|
|
btnResume.innerText = "Pause";
|
|
btnResume.disabled = "disabled";
|
|
btnRestart.disabled = "";
|
|
btnEdit.disabled = "";
|
|
updateGUILast();
|
|
if (title.innerText != TARGET && GENERATION_NUM >= GENERATION_LIMIT)
|
|
title.innerHTML += "<br><small>(aborted; too long)</small>";
|
|
} else {
|
|
generate();
|
|
}
|
|
}
|
|
|
|
let timer;
|
|
function restart() {
|
|
init();
|
|
timer = setInterval(runner, 10);
|
|
btnResume.innerText = "Pause";
|
|
btnResume.disabled = "";
|
|
btnRestart.disabled = "disabled";
|
|
btnEdit.disabled = "disabled";
|
|
}
|
|
restart();
|
|
pSize.value = pSize.placeholder = POPULATION_SIZE;
|
|
genLim.value = genLim.placeholder = GENERATION_LIMIT;
|
|
trgtText.value = trgtText.placeholder = TARGET;
|
|
bBlocks.value = bBlocks.placeholder = BLOCKS;
|
|
|
|
pSize.oninput = pSize.onchange = () => POPULATION_SIZE = pSize.value;
|
|
genLim.oninput = genLim.onchange = () => GENERATION_LIMIT = genLim.value;
|
|
trgtText.oninput = trgtText.onchange = () => TARGET = trgtText.value;
|
|
bBlocks.oninput = bBlocks.onchange = () => BLOCKS = bBlocks.value;
|
|
|
|
btnResume.addEventListener("click", () => {
|
|
if (timer == undefined) {
|
|
timer = setInterval(runner, 10);
|
|
btnResume.innerText = "Pause";
|
|
btnRestart.disabled = "disabled";
|
|
btnEdit.disabled = "disabled";
|
|
} else {
|
|
clearInterval(timer);
|
|
timer = undefined;
|
|
btnResume.innerText = "Resume";
|
|
btnRestart.disabled = "";
|
|
btnEdit.disabled = "";
|
|
}
|
|
});
|
|
|
|
btnRestart.addEventListener("click", () => {
|
|
if (timer == undefined) {
|
|
if (POPULATION_SIZE < 4) {
|
|
alert("Population size should not be less than 4.");
|
|
return;
|
|
}
|
|
if (GENERATION_LIMIT < 1) {
|
|
alert("Generation limit should not be less than 1.");
|
|
return;
|
|
}
|
|
form.style.display = "";
|
|
restart();
|
|
}
|
|
});
|
|
|
|
btnEdit.addEventListener("click", () => {
|
|
btnResume.disabled = "disabled";
|
|
btnRestart.disabled = "";
|
|
btnEdit.disabled = "disabled";
|
|
form.style.display = "block";
|
|
});
|
|
</script>
|
|
</body>
|
|
</html>
|