Skip to content

Instantly share code, notes, and snippets.

@adrianseeley

adrianseeley/pso.js

Last active June 5, 2021 12:03
Show Gist options
  • Save adrianseeley/9155206 to your computer and use it in GitHub Desktop.
Save adrianseeley/9155206 to your computer and use it in GitHub Desktop.
Download ZIP
JavaScript Normalized Particle Swarm Optimization Implementation - Search for an N-dimensional vector of components between -1 and +1 that optimizes a given function to a fitness of 0.
Raw
pso.js
// based on http://msdn.microsoft.com/en-us/magazine/hh335067.aspx
// usage example at bottom
function pso (number_of_dimensions, function_to_optimize, number_of_particles, number_of_iterations, fitness_threshold, inertia_weight, cognitive_weight, social_weight) {
var particles = [];
var swarm_best_position = [];
var swarm_best_fitness = null;
for (var p = 0; p < number_of_particles; p++) {
particles.push({
particle_position: [],
particle_velocity: [],
particle_fitness: null,
particle_best_position: [],
particle_best_fitness: null,
});
for (var d = 0; d < number_of_dimensions; d++) {
particles[p].particle_position.push((Math.random() * 2) - 1);
particles[p].particle_best_position.push(particles[p].particle_position[d]);
particles[p].particle_velocity.push((Math.random() * 2) - 1);
}
particles[p].particle_fitness = function_to_optimize(particles[p].particle_position);
if (swarm_best_fitness == null || particles[p].particle_fitness < swarm_best_fitness) {
swarm_best_fitness = particles[p].particle_fitness;
swarm_best_position = [];
for (var copy = 0; copy < particles[p].particle_position.length; copy++) swarm_best_position.push(particles[p].particle_position[copy]);
}
}
for (var i = 0; i < number_of_iterations && swarm_best_fitness > fitness_threshold; i++) {
for (var p = 0; p < particles.length; p++) {
for (var component = 0; component < particles[p].particle_velocity.length; component++) {
particles[p].particle_velocity[component] =
Math.max(-1, Math.min(1,
(inertia_weight * particles[p].particle_velocity[component]) +
(cognitive_weight * Math.random() * (particles[p].particle_best_position[component] - particles[p].particle_position[component])) +
(social_weight * Math.random() * (swarm_best_position[component] - particles[p].particle_position[component]))));
particles[p].particle_position[component] = Math.max(-1, Math.min(1, particles[p].particle_position[component] + particles[p].particle_velocity[component]));
}
particles[p].particle_fitness = function_to_optimize(particles[p].particle_position);
if (particles[p].particle_fitness < particles[p].particle_best_fitness) {
particles[p].particle_best_fitness = particles[p].particle_fitness;
particles[p].particle_best_position = [];
for (var copy = 0; copy < particles[p].particle_position.length; copy++) particles[p].particle_best_position.push(particles[p].particle_position[copy]);
}
if (particles[p].particle_fitness < swarm_best_fitness) {
swarm_best_fitness = particles[p].particle_fitness;
swarm_best_position = [];
for (var copy = 0; copy < particles[p].particle_position.length; copy++) swarm_best_position.push(particles[p].particle_position[copy]);
}
}
}
return {number_of_iterations: i, swarm_best_position: swarm_best_position, swarm_best_fitness: swarm_best_fitness};
};
// usage example
var result = pso(2, function (position) { return (position[0] * position[0]) + (position[1] * position[1]); }, 10, 10000, 0, 0.729, 1.49445, 1.49445);
console.log(result); // {number_of_iterations: 2867, swarm_best_position: [ 0, 0 ], swarm_best_fitness: 0}
Raw
pso.js.html
<html>
<meta charset="utf-8">
<body>
<canvas id="canvas"></canvas>
<script type="text/javascript">
var canvas = document.getElementById('canvas');
canvas.width = window.innerWidth * 0.95;
canvas.height = window.innerHeight * 0.95;
var ctx = canvas.getContext('2d');
ctx.Clear = function () {
ctx.clearRect(0, 0, canvas.width, canvas.height);
};
ctx.Dot = function (cx, cy, r, color) {
ctx.beginPath();
ctx.arc(cx, cy, r, 0, 2 * Math.PI, false);
ctx.fillStyle = color;
ctx.fill();
};
ctx.nDot = function (ncx, ncy, nr, color) {
ctx.Dot(ncx * canvas.width, canvas.height - (ncy * canvas.height), nr * canvas.height, color);
};
ctx.Circle = function (cx, cy, r, color, thickness) {
ctx.beginPath();
ctx.strokeStyle = color;
ctx.lineWidth = thickness;
ctx.arc(cx, cy, r, 0, 2 * Math.PI, false);
ctx.stroke();
};
ctx.nCircle = function (ncx, ncy, nr, color, thickness) {
ctx.Circle(ncx * canvas.width, canvas.height - (ncy * canvas.height), nr * canvas.height, color, thickness);
};
ctx.Line = function (x1, y1, x2, y2, width, color) {
ctx.beginPath();
ctx.moveTo(x1, y1);
ctx.lineTo(x2, y2);
ctx.lineWidth = width;
ctx.strokeStyle = color;
ctx.stroke();
};
ctx.nLine = function (nx1, ny1, nx2, ny2, width, color) {
ctx.Line(nx1 * canvas.width, canvas.height - (ny1 * canvas.height), nx2 * canvas.width, canvas.height - (ny2 * canvas.height), width, color);
};
ctx.Path = function (p, width, color) {
ctx.beginPath();
ctx.lineWidth = width;
ctx.strokeStyle = color;
ctx.moveTo(p[0].x, p[0].y);
for (var i = 1; i < p.length; i++) {
ctx.lineTo(p[i].x, p[i].y);
}
ctx.stroke();
};
ctx.nPath = function (np, width, color) {
ctx.beginPath();
ctx.moveTo(np[0].nx * canvas.width, np[0].ny * canvas.height);
for (var i = 1; i < np.length; i++) {
ctx.lineTo(np[i].nx * canvas.width, canvas.height - (np[i].ny * canvas.height));
}
ctx.lineWidth = width;
ctx.strokeStyle = color;
ctx.stroke();
};
ctx.Text = function (string, x, y, color) {
ctx.beginPath();
ctx.font = '20px monospace';
ctx.fillStyle = color;
ctx.fillText(string, x, y);
};
ctx.nText = function (string, nx, ny, color) {
ctx.Text(string, nx * canvas.width, canvas.height - (ny * canvas.height), color);
};
function draw_particle_graph (particles, swarm_best_fitness, swarm_best_position, iteration) {
var fitness_max = 0;
for (var p = 0; p < particles.length; p++) {
if (particles[p].particle_fitness > fitness_max) {
fitness_max = particles[p].particle_fitness;
}
}
ctx.Clear();
// outer circle
ctx.nCircle(0.5, 0.5, 0.45, 'black', 1);
// inner circles
for (var c = 0; c < 3; c++) ctx.nCircle(0.5, 0.5, ((0.45 / 4) * c) + (0.45 / 4), 'grey', 0.3);
// postive line
ctx.nLine(0.5, 0.5, 0.5, 0.95, 1, 'black');
// zero line
ctx.nLine(0.5, 0.5, 0.5, 0.05, 0.3, 'grey');
// origin 0
ctx.nText('0', 0.5, 0.5, 'black');
//dimensional 0
ctx.nText('0', 0.5, 0.055, 'grey');
// fitness max marker
ctx.nText('+' + fitness_max, 0.5, 0.96, 'black');
// fitness best market
ctx.nText('Best(+' + swarm_best_fitness + ')', 0.65, 0.9, 'black');
ctx.nText('Iter(' + iteration + ')', 0.2, 0.9, 'black');
// -1 dimensional marker
ctx.nText('-1↑', 0.2, 0.5, 'grey');
ctx.nText(' 0↓', 0.2, 0.45, 'grey');
// +1 dimensional marker
ctx.nText('+1↑', 0.77, 0.5, 'grey');
ctx.nText(' 0↓', 0.77, 0.45, 'grey');
var x_scale_fix = canvas.height / canvas.width;
for (var p = 0; p < particles.length; p++) {
var normalized_radial_magnitude = (particles[p].particle_fitness / fitness_max) * 0.45;
var last_pcx = null;
var last_pcy = null;
for (var component = 0; component < particles[p].particle_position.length; component++) {
var pcx = 0.5 + (Math.sin((1 - particles[p].particle_position[component]) * Math.PI) * normalized_radial_magnitude * x_scale_fix);
var pcy = 0.5 + (Math.cos((1 - particles[p].particle_position[component]) * Math.PI) * normalized_radial_magnitude);
var color = 'hsl(' + (360 - Math.floor((p / particles.length) * 360)) + ', 50%, 50%)';
ctx.nDot(pcx, pcy, 0.004, color);
if (component > 0) {
ctx.nLine(last_pcx, last_pcy, pcx, pcy, 1, color);
}
last_pcx = pcx;
last_pcy = pcy;
}
}
console.log(canvas.toDataURL().length)
};
function pso (speed_limit, number_of_dimensions, function_to_optimize, number_of_particles, number_of_iterations, fitness_threshold, inertia_weight, cognitive_weight, social_weight, fps, cb) {
var particles = [];
var swarm_best_position = [];
var swarm_best_fitness = null;
for (var p = 0; p < number_of_particles; p++) {
particles.push({
particle_position: [],
particle_velocity: [],
particle_fitness: null,
particle_best_position: [],
particle_best_fitness: null,
});
for (var d = 0; d < number_of_dimensions; d++) {
particles[p].particle_position.push((Math.random() * 2) - 1);
particles[p].particle_best_position.push(particles[p].particle_position[d]);
particles[p].particle_velocity.push((Math.random() * 2) - 1);
}
particles[p].particle_fitness = function_to_optimize(particles[p].particle_position);
if (swarm_best_fitness == null || particles[p].particle_fitness < swarm_best_fitness) {
swarm_best_fitness = particles[p].particle_fitness;
swarm_best_position = [];
for (var copy = 0; copy < particles[p].particle_position.length; copy++) swarm_best_position.push(particles[p].particle_position[copy]);
}
}
var i = 0;
function iter () {
if (i < number_of_iterations && swarm_best_fitness > fitness_threshold) {
draw_particle_graph(particles, swarm_best_fitness, swarm_best_position, i);
// you must be incredibly careful to update all velocities,
// then after ALL velocities have been updated can positions
// then be updated, otherwise you get a trailing effect
for (var p = 0; p < particles.length; p++) {
for (var component = 0; component < particles[p].particle_velocity.length; component++) {
particles[p].particle_velocity[component] =
Math.max(-1 / speed_limit, Math.min(1 / speed_limit,
(inertia_weight * particles[p].particle_velocity[component]) +
(cognitive_weight * (Math.random() * 0.01) * (particles[p].particle_best_position[component] - particles[p].particle_position[component])) +
(social_weight * (Math.random() * 0.01) * (swarm_best_position[component] - particles[p].particle_position[component]))));
}
}
for (var p = 0; p < particles.length; p++) {
for (var component = 0; component < particles[p].particle_velocity.length; component++) {
particles[p].particle_position[component] = Math.max(-1, Math.min(1, particles[p].particle_position[component] + particles[p].particle_velocity[component]));
}
particles[p].particle_fitness = function_to_optimize(particles[p].particle_position);
if (particles[p].particle_fitness < particles[p].particle_best_fitness) {
particles[p].particle_best_fitness = particles[p].particle_fitness;
particles[p].particle_best_position = [];
for (var copy = 0; copy < particles[p].particle_position.length; copy++) particles[p].particle_best_position.push(particles[p].particle_position[copy]);
}
if (particles[p].particle_fitness < swarm_best_fitness) {
swarm_best_fitness = particles[p].particle_fitness;
swarm_best_position = [];
for (var copy = 0; copy < particles[p].particle_position.length; copy++) swarm_best_position.push(particles[p].particle_position[copy]);
}
}
i++;
return setTimeout(iter, 1000 / fps);
} else {
return cb({number_of_iterations: i, swarm_best_position: swarm_best_position, swarm_best_fitness: swarm_best_fitness});
}
};
iter();
};
var result = pso(10, 10, function (position) {
var total = 0;
for (var p = 0; p < position.length; p++) total += Math.pow(position[p], 2);
return total;
}, 1000, 100000, 0, 0.729, 1.49445, 1.49445, 10000, function (result) {console.log(result);});
</script>
<body>
<html>
@ddrscott
Copy link

Copied to Code Pen: http://codepen.io/anon/pen/vLkzd

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment