tag:blogger.com,1999:blog-69280440250997486542024-03-05T13:29:51.783+02:00Tech-EffigyConcepts made SimpleTech-Effigyhttp://www.blogger.com/profile/00705129860720175840noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-6928044025099748654.post-81375003414183043712020-04-02T13:58:00.048+02:002021-01-24T22:11:12.240+02:00Particle Swarm Optimization - Demystified<br /><h2 style="text-align: left;">Introduction</h2><div>Particle Swarm Optimization(PSO) is a swarm intelligence based meta-heuristic, used for finding optimal solutions in large search-spaces; such as the infamous Genetic Algorithm. PSO outperforms most optimization algorithms in terms of speed and convergence in the continuous-space domain of numbers (Real Numbers); making it better suited for applications such as training neural networks and solving equations.<br /> <br /> PSO has a higher resilience toward idling in local-optimum positions. The founders of PSO (James Kennedy and Russell Eberhart) originally intended to digitally simulate the flocking behavior of birds - later realizing its practical uses in optimization.
<div><br /></div><div><br /></div><div><h2 style="text-align: left;">Mechanics</h2>Particles are placed randomly into the search space and evaluated on performance via the Evaluation Function. Particle positions are updated according to the best position the particle has recorded, and toward the best position recorded by the swarm as a whole - known respectively as Local-Best-Position and Global-Best-Position. <br /><br /><br /><div>
<h2>
The Algorithm Flow</h2><div><br /></div>
<div>
<br /></div>
<div>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBV1RShq51z5Wv7oZdD5Pf60TQl-rwzqt0xy1_Sr0i9pQ-Xce7IbbNPJ4da9-t0p2x1ZzDNDPn3ImtproD-0JGEDq7vaHjHtxSXiRfZaruveQJ36lVZMJOzT0ggKn8cB9UATM2Se6reic/s1600/flow.png"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjBV1RShq51z5Wv7oZdD5Pf60TQl-rwzqt0xy1_Sr0i9pQ-Xce7IbbNPJ4da9-t0p2x1ZzDNDPn3ImtproD-0JGEDq7vaHjHtxSXiRfZaruveQJ36lVZMJOzT0ggKn8cB9UATM2Se6reic/s1600/flow.png" /></a></div>
<div>
<br />
<h3>Prerequisite Vocabulary</h3>A particles position-vector represents the parameters of the Evaluation Function being optimized. The velocity-vector represents the change of position on each update. The search-space represents the minimum and maximum bounds of the parameters.</div><div><br /><h3>
Initialize Particle Population</h3>
A population of particles known as the Swarm are created and distributed randomly within the search-space, population size ranges from 20 to 150 particles depending on the search-space size and runtime resources required for the evaluation function to execute. The Swarm serves as a container and controller for keeping track of best position found and managing the updates and data-structures of the algorithm. </div><div><br /></div><div>
<h3>
Evaluate Particles</h3>
The Evaluation Function, also known as the Objective Function is the function who's parameters we wish to optimize. Particle positions represent the parameters of the function, and the return value is what we wish to maximize/minimize.</div><div><br /><h3>
Update Particles Position</h3>
Particles update their velocity toward the Global-Best-Position and Particles-Best-Position by random jumping factors; in turn aiding in the exploration of the search-space, and idling in local optimum positions. Here's the equation:</div>
<div>
<br /></div>
<div>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhDMclfzOrlMWmuRKDuPVt4qD7YBgmzcosHAzDwKgCuoTn3yzTgZHrYBX4C5sBbWqHfGL56YBODrFOdfMGow9k9RXDokw0-Y16NL5-9TxYvz_I-oBAM76uvZoTPOrJTJJy6o_QeftLqUmQ/s1600/updateformula.png"><img border="0" height="228" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhDMclfzOrlMWmuRKDuPVt4qD7YBgmzcosHAzDwKgCuoTn3yzTgZHrYBX4C5sBbWqHfGL56YBODrFOdfMGow9k9RXDokw0-Y16NL5-9TxYvz_I-oBAM76uvZoTPOrJTJJy6o_QeftLqUmQ/s640/updateformula.png" width="640" /></a></div>
<div>
<br />
<b>w</b> - Velocity decay constant<br />
<b>Pvel</b> - The Particle Velocity vector<br />
<b>R1, R2</b> - Random numbers 0 to 1<br />
<b>C1, C2</b> - Maximum Jump(interpolation) Constants<br />
<b>Pbest</b> - Particle-Best-Position recorded<br />
<b>Ppos</b> - Particles current position<br />
<b>Sbest</b> - Global-Best-Position recorded</div>
<div>
<br />
<b>(Pbest - Ppos)</b> Distance and direction toward the Particles-Best-Position recorded. C1 determines the maximum jump constant; where a value of 2 would indicate twice the vector length. R1 is a random number from 0 to 1 - determining how far it will jump along the vector length. <i>C1 defaults to 1.5 to 2 for search space exploration reasons.</i></div>
<div>
<br />
<b>(Sbest - Ppos)</b> Distance and direction toward the Global-Best-Position, C2 determines the maximum jump constant, C2 is the same as C1 in most cases. R2 is a random number from 0 to 1 - determining how far it will jump along the vector length. <i>R2 is not the same as R1.</i></div>
<div>
<br />
<b>w*Pvel</b> keep particles heading in a direction, improving resilience to local optimums. w is the inertia factor; that dictates how easily particles are influenced by position updates. <i>w is usually a number in the range of 0 to 1, where 1 is no decay; the default is 0.72.</i></div>
<div>
<br /></div>
<div>
<div style="text-align: left;"><i><b>PSO Equation for coders</b></i></div></div><div><i>
P.vel[i] = w*P.vel[i] + rand()*c1*(P.best[i] - P.pos[i]) + rand()*c2*(S.best[i] - P.pos[i])<br />
P.pos[i] = P.pos[i] + P.vel[i]</i></div>
<div>
<br />
<h3>
Done - When to stop</h3>
When the Global-Best-Position reaches a satisfactory Fitness Score - or when the rate of change becomes permissible.</div>
<div>
<br /></div><div><br /></div>
</div>
</div>
<h2>
Quick Code!</h2>
<!--HTML generated using hilite.me--><br />
<div style="background: rgb(255, 255, 255); border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="background: rgb(255, 255, 255); line-height: 125%; margin: 0px;"><span style="color: blue;">class</span> Particle {
constructor(searchSpaceSize, searchSpaceMaximum) {
<span style="color: green;">// position and velocity vectors sized according to search space</span>
<span style="color: blue;">this</span>.position = Array(50).fill(searchSpaceSize);
<span style="color: blue;">this</span>.velocity = Array(50).fill(searchSpaceSize);
<span style="color: green;">// Search Space bounds</span>
<span style="color: blue;">this</span>.searchSpaceMaximum = searchSpaceMaximum;
<span style="color: green;">//memory of the best positition found so far</span>
<span style="color: blue;">this</span>.bestPosition = Array(50).fill(0);
<span style="color: green;">//score/fitness value</span>
<span style="color: blue;">this</span>.score = 0;
}
<span style="color: green;">// can be an array of bounds for each element</span>
placeRandomlyInSearchSpace() {
<span style="color: blue;">for</span> (<span style="color: blue;">let</span> i = 0; i < <span style="color: blue;">this</span>.position.length; i++) {
<span style="color: blue;">this</span>.position[i] = Math.random() * <span style="color: blue;">this</span>.searchSpaceMaximum;
}
}
updatePosition(swarmBestPosition) {
<span style="color: green;">// Decay and distance constants</span>
<span style="color: blue;">const</span> w = 0.72;
<span style="color: blue;">const</span> C1 = 2;
<span style="color: blue;">const</span> C2 = 2;
<span style="color: green;">// for the random numbers</span>
<span style="color: blue;">let</span> R1 = 0;
<span style="color: blue;">let</span> R2 = 0;
<span style="color: blue;">for</span> (<span style="color: blue;">let</span> i = 0; i < <span style="color: blue;">this</span>.position.length; i++) {
<span style="color: green;">//Generate Random Numbers</span>
R1 = Math.random();
R2 = Math.random();
<span style="color: green;">// Update Velocity</span>
<span style="color: blue;">this</span>.velocity[i] =
w * <span style="color: blue;">this</span>.velocity[i] +
R1 * C1 * (<span style="color: blue;">this</span>.bestPosition[i] - <span style="color: blue;">this</span>.position[i]) +
R2 * C2 * (swarmBestPosition[i] - <span style="color: blue;">this</span>.position[i]);
<span style="color: green;">// Update Position</span>
<span style="color: blue;">this</span>.position[i] = <span style="color: blue;">this</span>.position + <span style="color: blue;">this</span>.velocity[i];
}
}
evaluatePosition(evaluationFunction) {
<span style="color: green;">// Evaluate the current position and get score</span>
<span style="color: blue;">this</span>.score = evaluationFunction(<span style="color: blue;">this</span>.position);
<span style="color: green;">// Check if it's the best position found so far by particle</span>
<span style="color: blue;">if</span> (<span style="color: blue;">this</span>.score > <span style="color: blue;">this</span>.bestScore) {
<span style="color: blue;">this</span>.bestScore = <span style="color: blue;">this</span>.score;
<span style="color: blue;">this</span>.bestPosition = [...<span style="color: blue;">this</span>.position];
}
<span style="color: blue;">return</span> <span style="color: blue;">this</span>.score;
}
}
<span style="color: blue;">class</span> Swarm {
constructor(
evalFunc,
numberOfParticles,
searchSpaceSize,
searchSpaceMaximum
) {
<span style="color: green;">// Evaluation Function as a callback</span>
<span style="color: blue;">this</span>.evaluationFunction = evalFunc;
<span style="color: blue;">this</span>.particles = Array(numberOfParticles);
<span style="color: green;">// Best position found in history of object</span>
<span style="color: blue;">this</span>.bestPosition = [];
<span style="color: blue;">this</span>.bestScore = 0;
<span style="color: green;">// Some params defining the search space</span>
<span style="color: blue;">this</span>.searchSpaceSize = searchSpaceSize;
<span style="color: blue;">this</span>.searchSpaceMaximum = searchSpaceMaximum;
}
<span style="color: green;">// Creates Particles and passes search space info to particles</span>
initializeParticles() {
<span style="color: blue;">for</span> (<span style="color: blue;">let</span> i = 0; i < <span style="color: blue;">this</span>.particles.length; i++) {
<span style="color: blue;">this</span>.particles[i] = <span style="color: blue;">new</span> Particle(
<span style="color: blue;">this</span>.searchSpaceSize,
<span style="color: blue;">this</span>.searchSpaceMaximum
);
<span style="color: blue;">this</span>.particles[i].placeRandomlyInSearchSpace(50);
}
}
run() {
<span style="color: blue;">this</span>.initializeParticles();
<span style="color: blue;">let</span> running = <span style="color: blue;">true</span>;
<span style="color: blue;">while</span> (running) {
<span style="color: blue;">for</span> (<span style="color: blue;">let</span> i = 0; i < <span style="color: blue;">this</span>.particles.length; i++) {
<span style="color: blue;">this</span>.particles[i].updatePosition(<span style="color: blue;">this</span>.bestPosition);
score = <span style="color: blue;">this</span>.particles[i].evaluatePosition(<span style="color: blue;">this</span>.evaluationFunction);
<span style="color: green;">// Check if Particle Score better than ever found</span>
<span style="color: green;">// If so save</span>
<span style="color: blue;">if</span> (<span style="color: blue;">this</span>.particles[i].score > <span style="color: blue;">this</span>.bestScore) {
<span style="color: blue;">this</span>.bestPosition = <span style="color: blue;">this</span>.particles[i].position;
<span style="color: blue;">this</span>.bestScore = <span style="color: blue;">this</span>.particles[i].score;
}
}
}
}
}
</pre>
</div>
</div>Tech-Effigyhttp://www.blogger.com/profile/00705129860720175840noreply@blogger.com0tag:blogger.com,1999:blog-6928044025099748654.post-33601168180306258462015-02-17T14:53:00.000+02:002020-04-02T14:18:06.617+02:00The Genetic Algorithm - Explained<h2>
Paradigm of Evolution</h2>
Every organism contains an array of traits - called DNA, when 2 parents mate they produce a child containing a mixture of their DNA. Depending on how well those traits work together to help the child survive so that he may reproduce, will determine if those traits will pass into future generation. Rarely a random trait enters a child's DNA that was not inherited from the parents, we call this mutation. If the mutation is beneficial, the organism will survive long enough to carry the mutation over to future generations. So the cycle continues, after many generations we continue to optimize the population by "mixing and matching", "trial and error" of DNA.<br>
<br>
<h2>
Introduction</h2>
Genetic Algorithms are used to find optimal solution by method of evolution-inspired search and optimization; Generally used in problems where linear/brute-force searches are not viable in terms of time, such as – Travelling Salesman Problem, Timetable Scheduling, Finding Neural Network Weights, Sudoku, Trees(data-structure) etc.. The first requirement is an encoding scheme suitable for representing individuals, second requirement being a evaluation function for representing the fitness of an individual.<br>
<br>
<a href="http://techeffigytutorials.blogspot.com/2015/02/the-genetic-algorithm-explained.html#more"></a>Tech-Effigyhttp://www.blogger.com/profile/00705129860720175840noreply@blogger.com16tag:blogger.com,1999:blog-6928044025099748654.post-7988537590690870502015-01-08T23:36:00.001+02:002020-04-02T14:19:40.283+02:00Neural Network Illustrated – Step by Step<div class="separator" style="clear: both; text-align: left;">
<b>I<span style="font-size: x-small;">1</span> </b>and <b>I<span style="font-size: x-small;">2</span> </b>are the inputs scaled to [-1,1] or [0, 1], depending on the activation function used</div>
<b>f()</b>=Activation Function=Tanh(), Sigmoid() or any differential-able function<br>
<b>W</b>=Current neurons input weights, initialized randomly between [-1, 1].<br>
<b>Wb</b>=Bias Weight, connected to nothing, used as a threshold, initialized same as W<br>
<b>N</b>=The output of the current neuron.<br>
<div class="separator" style="clear: both; text-align: center;">
<br></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6IsjKQWRZnLnWREc3VtJVikDM5FQ-BIvLMXFjRJtGfJupod4ejjfg93ew8R5KHflDeQxSOYfYeii9xtexkx5wTiOcpQzu30BtXTrr9fFWZ8WXJI05Hh377aYB3j7eExy4rN535I5ZKdM/s1600/NN-01.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6IsjKQWRZnLnWREc3VtJVikDM5FQ-BIvLMXFjRJtGfJupod4ejjfg93ew8R5KHflDeQxSOYfYeii9xtexkx5wTiOcpQzu30BtXTrr9fFWZ8WXJI05Hh377aYB3j7eExy4rN535I5ZKdM/s1600/NN-01.jpg"></a></div>
<br>
<a href="http://techeffigytutorials.blogspot.com/2015/01/neural-network-illustrated-step-by-step.html#more"></a>Tech-Effigyhttp://www.blogger.com/profile/00705129860720175840noreply@blogger.com10tag:blogger.com,1999:blog-6928044025099748654.post-61328705368158731342015-01-08T23:28:00.000+02:002020-04-02T14:20:37.296+02:00Markov Chains - ExplainedMarkov Chains is a probabilistic process, that relies on the current state to predict the next state. For Markov chains to be effective the current state has to be dependent on the previous state in some way; For instance, from experience we know that if it looks cloudy outside, the next state we expect is rain. We can also say that when the rain starts to subside into cloudiness, the next state will most likely be sunny. Not every process has the Markov Property, such as the Lottery, this weeks winning numbers have no dependence to the previous weeks winning numbers.<br>
<br>
<a href="http://techeffigytutorials.blogspot.com/2015/01/markov-chains-explained.html#more"></a>Tech-Effigyhttp://www.blogger.com/profile/00705129860720175840noreply@blogger.com18tag:blogger.com,1999:blog-6928044025099748654.post-47511325233797764152015-01-08T23:20:00.001+02:002020-04-02T14:21:04.259+02:00Bloom Filters - ExplainedThe Bloom filter is a space efficient, probabilistic data structure, designed to test the membership of elements to a set. The trade-off for being a space efficient data structure is it may return false positives, but always returns definite negatives: Meaning Bloom filters can accurately test an element for non-membership to a set, but can only with probability test an element for membership. Bloom filters find application in circumstances where testing for non-membership saves resources such as calls to a web server, checking a proxy cache. Google uses Bloom filters in the Chrome browser as a preliminary check for malicious URL's.<br>
<br>
<a href="http://techeffigytutorials.blogspot.com/2015/01/bloom-filters-explained.html#more"></a>Tech-Effigyhttp://www.blogger.com/profile/00705129860720175840noreply@blogger.com7