<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Terry Clark on Medium]]></title>
        <description><![CDATA[Stories by Terry Clark on Medium]]></description>
        <link>https://medium.com/@iamterryclark?source=rss-22b3a2c5decf------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*WQBoKGLA-bJX1AFE.</url>
            <title>Stories by Terry Clark on Medium</title>
            <link>https://medium.com/@iamterryclark?source=rss-22b3a2c5decf------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 14:30:53 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@iamterryclark/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Natural Computing Mini Project]]></title>
            <link>https://medium.com/@iamterryclark/natural-computing-mini-project-873be3b46ab9?source=rss-22b3a2c5decf------2</link>
            <guid isPermaLink="false">https://medium.com/p/873be3b46ab9</guid>
            <category><![CDATA[docker]]></category>
            <dc:creator><![CDATA[Terry Clark]]></dc:creator>
            <pubDate>Tue, 19 Dec 2017 10:20:50 GMT</pubDate>
            <atom:updated>2017-12-19T10:30:59.451Z</atom:updated>
            <content:encoded><![CDATA[<h4>Swarmotion</h4><h4>What is it?</h4><p>This project will compare two Swarm Intelligent (SI) algorithms to test performance over a continuously changing search space.</p><p>Swarmotion is a sonificiation and comparison of two SI algorithms, namely <strong>Dispersive Fly Optimisation</strong> and a variation of the inertia weighted <strong>Particle Swarm Optimisation</strong>.</p><h4><strong>What are the components?</strong></h4><p>Using openFrameworks and C++ I’ll create an interactive program making of the underlying processes of both algorithms heard through sonifiying the distance from the best in the swarms. I want to be able to hear the difference in the way they find the solution.</p><p>Its search space is the motion detection using a thresholded frame differencing. I took inspiration from an application Ifound called <a href="http://cs-chan.com/doc/MVA2013_2.pdf">SwATrack</a>, which is a swarm intelligent motion tracker as I was intrigued by the high accuracy of PSO and how it was able to quickly track jerky/abrupt motion on video.</p><p>It’s solution would be that the swarm is attracted to the area of highest velocity.</p><h4>Where can I see the code?</h4><p>I’ll stick the code on github here:</p><p><a href="https://github.com/iamterryclark/Swarmotion">https://github.com/iamterryclark/Swarmotion</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=873be3b46ab9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Search Algorithm Series: PSO]]></title>
            <link>https://medium.com/@iamterryclark/swarm-intelli-eb5e46eda0c3?source=rss-22b3a2c5decf------2</link>
            <guid isPermaLink="false">https://medium.com/p/eb5e46eda0c3</guid>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[swarm-intelligence]]></category>
            <category><![CDATA[swarm]]></category>
            <category><![CDATA[particle-swarm]]></category>
            <category><![CDATA[nature]]></category>
            <dc:creator><![CDATA[Terry Clark]]></dc:creator>
            <pubDate>Mon, 18 Dec 2017 18:15:56 GMT</pubDate>
            <atom:updated>2017-12-20T14:44:19.277Z</atom:updated>
            <content:encoded><![CDATA[<h4>Particle Swarm Optimisation</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/837/1*xb84rQPsgS6WVT-k1p6Gpg.png" /><figcaption>PSO</figcaption></figure><h4>Introduction</h4><p>PSO is a branch of meta-heuristic search optimisation. This means that the algorithm makes fewer assumptions about the search space, based on lots of smaller processes.</p><p>This algorithm uses a combination of individual and environmental factors to find the overall best solution. It does this by keeping a working memory of its personal best results along with the global best. The personal bests act like anchor points where the swarm will flow and collapse between where the global best will be, as suggested, the overall best solution.</p><p>Proposed back in 1995 there have been many variations which make adjustments to the topology of the particles along with how the velocity is calculated. For example, using <strong>inertia weights</strong>, a scalar to reduce the overall impact of the velocity, preventing the phenomenon of <strong>particle explosion!</strong> This is when the particles are moving too quickly to that the global best doesn’t locate the solution.</p><p>Another variation takes advantage of the communication between the particles. <strong>Ring Topology, </strong>connects<strong> </strong>the last in the particle array with the first. <strong>Fully Connected Topology, </strong>connects all particles to every other particle. And finally the <strong>Adaptive Topology</strong>, which connects <strong>a number</strong> of neighbours and itself of its personal best. All of these variations share the current particle’s personal best result along with the stored global best. This reminds me somewhat of how SDS performs when disseminating information to their fellow miners.</p><p>A known issue with vanilla PSO is that once the particle collapse towards the global best the velocity will become closer to 0 meaning that for continuous spaces this algorithm as it is, wouldn’t perform very well and will become static once a optimal point was found in the search space.</p><p>To get around this I have modified the algorithm slightly by adding a behaviour much like DFO where a disturbance threshold will effectively send out probes in check for more areas of the search space which could be optimal. This stops the particles from getting trapped into local optima.</p><h3>Algo Recipe</h3><p>For this experiment I will use a similar example as my other blogs as to find the brightest pixel within a continuous search space (video).</p><h4>1. Randomly Initialise</h4><p>Of course we will begin with a randomly initialised population of particles to capture a range of the search space.</p><h4><strong>2. Evaluate fitness and personal best positions.</strong></h4><p>We assume this is a minimisation problem and therefore we aim to get a 0 fitness once we find the solution. We also evaluate the personal best fitnesses in order to make the later comparisons.</p><h4><strong>3. Compare</strong></h4><p>Although it does not help oneself to compare against others in life. In the case of PSO we will need to see if the current fitness is better than the personal best. If it is the current position should then be stored if not the personal best will stay where it is.</p><p>Also we will nee to check if the personal best is better than the global best then the global position should also update to the personal best position;</p><h4>4. Next comes the all important update method</h4><p>The update I am using comes from the inertia weighted variation as described above.2</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/860/1*GkNVx1vZ-XUqKi1qPpnylg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/312/1*I2tscR40oAJDNN2XAJ0y1A.png" /></figure><p><strong><em>The coded version:<br></em></strong>// Recommended values<br><em>X = 0.72984; <br>c1 = X * (4.1/2);<br>c2 = X * (4.1/2);</em></p><p><em>p.vel = X * p.vel + </em><strong><em>c1</em></strong><em> * R(0, 1) * (pBest — pos) +</em><strong><em> c2</em></strong><em> * R(0,1) * (gBest — pos)</em></p><p>Then update the position with <em>pos += vel</em></p><p><strong>c1</strong> and <strong>c2</strong> are usually a combination resulting to a max of 4, this has been based on observations made overtime with the algorithm. <strong>c1</strong> gives more importance to the personal best result, this is where the particles will have more pull towards the blue dots in the video below. Whilst the <strong>c2 </strong>gives importance to the global best or social influence, where the particles will gravitate towards the best in the swarm.</p><p>PSO overall felt very familiar to DFO in the way that it can either use the elitist approach following the best in the swarm or a best neighbour approach utilising the more social approach. Also here I added a disturbance threshold much like DFO in order to create a working PSO algorithm for the continuous search space ( a moving light across the screen). This is due to the <strong>diversity</strong> of the algorithm where because there is a lack of stochastic process the swarm become stuck in a local optima.</p><p>I found that when reducing the c1 &amp; c2 values together equally the particles would hover around an area and then when the disturbance kicked in the particle would send out a prob check to see if this was a personal best and then the full swarm would gravitate towards that point.</p><p>My example of this is below:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FN3l2KZyYgI0%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DN3l2KZyYgI0&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FN3l2KZyYgI0%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/50f623b67dfaaac59f419fa97bb6f56f/href">https://medium.com/media/50f623b67dfaaac59f419fa97bb6f56f/href</a></iframe><h4><strong>Natural Camp Activities:</strong></h4><p><em>What is the best thing(s) you have learnt in the course?</em></p><ul><li>I learned to read academic papers and find interest in hard to grasps topics (This has always been a life fail of mine so far that I wanted to achieve…), deciphered the notion for swarm intelligence algorithms and feel more confident with thinking conceptually about the code.</li><li>A majority of problems can be broken down into smaller sections to then combine later to find a solution (also a life moto…)</li><li>I felt that this course was unexpected in the content covered and maybe I was a little unprepared for the uphill struggle I experience. Given that I felt that by the end of this course I was more confident overall with understanding the basics of swarm intelligence.</li></ul><h4>References:</h4><ul><li>Particle Swarm Optimization Based Source Seeking — Rui Zou, Vijay Kalivarapu, Eliot Winer, James Oliver, Sourabh Bhattacharya</li><li><a href="https://www.youtube.com/watch?v=yF1rS_7rl6E">https://www.youtube.com/watch?v=yF1rS_7rl6E</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eb5e46eda0c3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Natural Camp Classwork — GA Example Problem]]></title>
            <link>https://medium.com/@iamterryclark/natural-camp-classwork-ga-example-problem-79c88aefb20d?source=rss-22b3a2c5decf------2</link>
            <guid isPermaLink="false">https://medium.com/p/79c88aefb20d</guid>
            <dc:creator><![CDATA[Terry Clark]]></dc:creator>
            <pubDate>Sat, 09 Dec 2017 14:10:46 GMT</pubDate>
            <atom:updated>2017-12-09T14:10:46.706Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>Example GA Scenario</strong></h3><p><em>Assume that your GA has chromosomes in the following structure:</em></p><ul><li><em>ch = (x0, x1, x2, x3, x4, x5, x6, x7)</em></li><li>x0–7<strong> </strong>can be any digit between zero to nine.</li></ul><p><em>The fitness of each chromosome is calculated using the following formula:</em></p><ul><li><em>f(ch) = (x0 + x1) − (x2 + x3) + (x4 + x5 ) − (x6 + x7)</em></li></ul><p><em>This problem is a maximisation problem.</em></p><p><em>In this scenario we initially have a population of four chromosomes as shown below:</em></p><ul><li><em>ch1 = (6, 5, 4, 1, 3, 5, 3, 2)</em></li><li><em>ch2 = (8, 7, 1, 2, 6, 6, 0, 1)</em></li><li><em>ch3 = (2, 3, 9, 2, 1, 2, 8, 5)</em></li><li><em>ch4 = (4, 1, 8, 5, 2, 0, 9, 4)</em></li></ul><h3><strong>Part I:</strong></h3><p><em>Calculate the fitness of each individual (and show your workings even if you initially think I might be mean to ask this, you’ll gradually change your mind!).</em></p><ul><li><em>fitness(ch1) = (6+ 5) — (4+ 1) + (3 + 5) — (3+ 2) = 9</em></li><li><em>fitness(ch2) = (8+7) — (1+2) + (6+6) — (0+1) = 23</em></li><li><em>fitness(ch3) = (2+3) — (9+2) + (1+2) — (8+5) = -16</em></li><li><em>fitness(ch4) = (4 + 1) — (8+ 5) + (2+0) — (9+4) = -19</em></li></ul><p><em>Then arrange the chromosomes by putting the fittest one first and the least fit at the end.</em></p><ul><li><em>1st — ch2 | 23</em></li><li><em>2nd — ch1 | 9</em></li><li><em>3rd — ch3 | -16</em></li><li><em>4rd — ch4 | -19</em></li></ul><h3><strong>Part II:</strong></h3><p><em>Now apply the following crossover to the chromosomes:</em></p><p><em>1Use one-point crossover (at the middle) to cross the best two chromosomes. [This would lead in creating the first two children]</em></p><ul><li><em>ch1 = (6, 5, 4, 1, </em><strong><em>|</em></strong><em> </em><strong><em>3, 5, 3, 2</em></strong><em>) child1 = (6, 5, 4, 1, </em><strong><em>6, 6, 0, 1</em></strong><em>)</em></li><li><em>ch2 = (8, 7, 1, 2, </em><strong><em>| 6, 6, 0, 1</em></strong><em>) child2 = (8, 7, 1, 2, </em><strong><em>3, 5, 3,</em></strong><em> </em><strong><em>2</em></strong><em>)</em></li></ul><p><em>2Use two-point crossover (after x1 and after x5) to cross the 2nd and 3rd best individual. [This would results in creating two extra children]</em></p><ul><li><em>ch1 = (6, 5 </em><strong><em>|</em></strong><em> </em><strong><em>4, 1, 3, 5</em></strong><em> </em><strong><em>|</em></strong><em> 3, 2) child3 = (6, 5, </em><strong><em>9, 2, 1, 2</em></strong><em>, 3, 2)</em></li><li><em>ch3 = (2, 3 </em><strong><em>|</em></strong><em> </em><strong><em>9, 2, 1, 2</em></strong><em> </em><strong><em>|</em></strong><em> 8, 5) child4 = (2 ,3, </em><strong><em>4, 1, 3, 5</em></strong><em>, 8, 5)</em></li></ul><p><em>Use uniform crossover (the way you’d like to) to cross the 1st and 3rd best chromosomes. [Now you should have two more children; six in total]</em></p><ul><li><em>ch2 = (8 </em><strong><em>| 7 |</em></strong><em> 1</em><strong><em> | 2 | </em></strong><em>6 </em><strong><em>| 6 |</em></strong><em> 0 </em><strong><em>| 1 |</em></strong><em> ) child5 = (8, </em><strong><em>3</em></strong><em>, 1, </em><strong><em>2</em></strong><em>, 6, </em><strong><em>2</em></strong><em>, 0, </em><strong><em>5</em></strong><em>)</em></li><li><em>ch3 = (2 </em><strong><em>| 3 | </em></strong><em>9 </em><strong><em>| 2 |</em></strong><em> 1 </em><strong><em>| 2 |</em></strong><em> 8 </em><strong><em>| 5 |</em></strong><em> ) child6 = (2,</em><strong><em> 7</em></strong><em>, 9, </em><strong><em>2</em></strong><em>, 1, </em><strong><em>6,</em></strong><em> 8, </em><strong><em>1</em></strong><em>)</em></li></ul><h3><strong>Part III:</strong></h3><p><em>Following the crossover operations conducted above, the population size is six (for a moment ignore that classically, population size doesn’t change in GA). Now calculate the fitness of each of the newly generated offspring (again showing your workings), and state if there are any improvement compared to the initial population.</em></p><ul><li><em>child1 = (6+5) — (4+1) + (6+6) — (0+1) =1</em></li><li><em>child2 = (8+7) — (1+2) + (3+5) — (3+2) =1</em></li><li><em>child3 = (6+5) — (9+2) + (1+2) — (3+ 2) = -2</em></li><li><em>child4 = (2+3) — (4+ 1) + (3+5) — (8+5) = -5</em></li><li><em>child5 = (8+ 3) — (1+ 2) + (6+2) — (0+5) = 11</em></li><li><em>child6 = (2+ 7) — (9+ 2) + (1+6) — (8+1) = -4</em></li></ul><p>Overall the standard deviation from the mean fitness is much narrower, however the next generation of chromosomes where not able to achieve a higher fitness than the parents. The search continues…</p><h3><strong>Part IV:</strong></h3><p><em>Acknowledging that the value of each gene is in the range of [0,9], suggest a chromosome that would return the optimal solution (i.e. with the maximum fitness)</em></p><ul><li>chmax = (9, 9, 0, 0, 9, 9, 0, 0) = 36</li></ul><h3><strong>Part V:</strong></h3><p><em>Looking at the initial population and based on the answer to part IV, is it possible to reach the optimal state without the mutation operator? State why?</em></p><p>It wouldn’t be possible to get a child which is equal to chmax without the mutation operator, as there needs to be both a 9 and a 0 in the same combination above in each set of input chromosomes. For example:</p><p>· <em>ch1 = (</em><strong><em>9</em></strong><em>, 5, 4, 1, 3, 5, </em><strong><em>0,</em></strong><em> 2)</em></p><p>· <em>ch2 = (8, </em><strong><em>9</em></strong><em>, 1, 2, 6, </em><strong><em>9</em></strong><em>, 0, 1)</em></p><p>· <em>ch3 = (2, 3, </em><strong><em>0</em></strong><em>, 2, </em><strong><em>9</em></strong><em>, 2, 8, </em><strong><em>0)</em></strong></p><p>· <em>ch4 = (4, 1, 8, </em><strong><em>0</em></strong><em>, 2, 0, 9, 4)</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=79c88aefb20d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Search Algorithm Series: GA]]></title>
            <link>https://medium.com/@iamterryclark/search-algorithm-series-3bdf7d5eb777?source=rss-22b3a2c5decf------2</link>
            <guid isPermaLink="false">https://medium.com/p/3bdf7d5eb777</guid>
            <category><![CDATA[swarm-intelligence]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[genetic-algorithm]]></category>
            <category><![CDATA[science]]></category>
            <category><![CDATA[algorit]]></category>
            <dc:creator><![CDATA[Terry Clark]]></dc:creator>
            <pubDate>Sun, 26 Nov 2017 12:12:51 GMT</pubDate>
            <atom:updated>2017-12-18T19:04:03.853Z</atom:updated>
            <content:encoded><![CDATA[<h4>Genetic Algorithm</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/434/1*UU1uzhbglTTHOmMQQ3evZA.gif" /></figure><p>GA are a concept thought of back in the 1960’s and fit the model of evolution in a way that it naturally selects out of a population to solve a particular problem. To give this some more context it can be thought of as a process to dynamically change parameters in an infinite amount of interactions in order to find the target solution or find interesting solutions through the process of mutation and crossover, discussed later in this blog post.</p><p>For this example we focus on the following problem to test our GA implementation:</p><blockquote>Each one of you is given 10 cards, numbered 1–10. You’re asked to divide the cards in two groups where the sum of the numbers on the cards in the first group is as close to <strong>36 </strong>and the product of the numbers in the second group is as close as possible to<strong> 360</strong>.</blockquote><p>GA is split into 5 processes of which each of these can differ in the implementation meaning that you can have complete control in the way the individual GA processes work and how much randomness is introduced into it. The aim of this blog post will be to in some way define these processes with some C++ code and that I tried to implement this in.</p><p>I say it like this as GA can be defined in many ways depending on the type of problem you are trying to solve. This is just one of many variations you can implement and ill try to highlight options along the way.</p><p>Below is a general overview of the components needed to implement GA</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*Aju7XS6Z0vbWLupi3P4iww.png" /></figure><h4>Initialise Population</h4><p>Here we need to create something called a chromosome which will hold all the number of cards aka genes as we need to split the cards into two groups we will need to then assign these at random, so 0 and 1. This means that our search space will have 2¹⁰ (1024) possible combinations to test in order to find the correct solution, 2 possible groups to choose from in 10 cards.</p><p>From these randomly selected cards we will need to find the sum of one group and the product of the other to get our target values of <strong>36</strong> and <strong>360 </strong>as per our instructions for this particular problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*mq-1GLJMG6Wkj-R4ZK0rjg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/678/1*QAZ13auIIHk34wVEs3XKAw.jpeg" /></figure><h4>Evaluate Files</h4><p>Next is to calculate the fitness of the chromosomes or another words how close are they are getting the correct combination of 0&#39;s and 1’s to the above problem.</p><p>Here I go through all the genes for every chromosome in the population and calculate both groups total values. We then take the absolute value of this in order to get rid of the negative results. A point to note is that in this problem we have two sub-fitnesses to calculate, one for the group 0 target and one for the and group 1 target.</p><p>I also found out that in class that due to group 1 having a larger target value this could create a bias in the chromosome and thus scaling this down to be a similar size ( i.e target 2 * 0.1 = 36 ) so the other target this will help to not emphasise this group over the other. unless of course you have reason to.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fIrKyNBatx-EJaEEV1DPiQ.png" /></figure><p>A note here is that the fitness can be calculate in a number of ways. I have used quite a simple method of just adding the differences together which should produce a 0 fitness (minimal value) which is what we are aiming for overall.</p><h4>Selection</h4><p>A simple way to achieve the selection would be to take the top 50 fittest chromosomes or a split of the top n chromosomes and then the rest from the worst. However, it is ideal here to gather a mixed population of the best and the worst chromosomes as taking all of the best will not necessarily lead to quickly finding the correct solution.</p><p>However for this process, I chose to use the roulette style selection in order to get the best parents from the population in terms of probability. To do this a random float is picked between 0 and 1 which we then compare to an array of probabilities created by incrementally summing all the different fitness values of each agent.</p><p>Again this is an area which can be entirely defined by the programmer any selection process, which would benefit the fitness and finding the solution, should be used here.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*YcgtuBNpu9S9gKf-gWsLiQ.jpeg" /><figcaption>Roulette Wheel</figcaption></figure><p>The chromosome with the largest probability (fitness / overall fitness) will more likely be selected meaning that the majority of the ‘fittest’ chromosome will be then selected as the parents.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/714/1*A6ZAx9L6AQt0xqrqeV7O7w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/978/1*CUqTS8dSq6BOeIR7WL53Uw.png" /></figure><h4><strong>Crossover / Mutation</strong></h4><p>The best parents then go on to make a child. The idea here is to have from which a crossover followed by a mutation process will create the children ready to later become the next parents.</p><p>Crossover essentially splits the genes in two halves where the genes on one side is then taken from one parent and other side taken from the other parent.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*wZALyFlRwePosZg-UJebNg.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/948/1*L5IJHCKbKvqeOCxIwS62jw.png" /></figure><p>Mutation is simpler, here I decided to mutate the genes if, for every gene, the random value was below the certain mutation rate which could limit the amount of times it mutates so it isn’t too dis-similar from the parent.</p><p>Option 2 could be to randomly swap indices around whilst another option could be to generate a random value for an index and then only mutating this value.</p><p>This could be a benefit to control the amount of times a mutation happens however, this is another area which can be amended to fit your particular problem.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/1*MjwILKJcsmtd00rWguwsmA.png" /></figure><p>From here we replace the children with the current population and the cycle is complete. Now all that is left is to check how many iterations there are before a solution, of target 36 for 0’s and 360 for 1’s, is found. Through these experiments I found that with a larger population it was quicker to find the target solution, which feel rather obvious as there are many more combinations at the start of the process.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3bdf7d5eb777" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Search Algorithm Series: SDS]]></title>
            <link>https://medium.com/@iamterryclark/search-algorithm-series-560c155aca6b?source=rss-22b3a2c5decf------2</link>
            <guid isPermaLink="false">https://medium.com/p/560c155aca6b</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[search]]></category>
            <category><![CDATA[optimisation]]></category>
            <category><![CDATA[swarm-intelligence]]></category>
            <category><![CDATA[optimization]]></category>
            <dc:creator><![CDATA[Terry Clark]]></dc:creator>
            <pubDate>Sat, 28 Oct 2017 13:14:51 GMT</pubDate>
            <atom:updated>2017-12-18T18:33:19.904Z</atom:updated>
            <content:encoded><![CDATA[<h4><strong>Stochastic Diffusion Search</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vVAcekqQ5XVVEtQDkpwCOw.jpeg" /></figure><p>We now take a look at <strong>Stochastic Diffusion Search</strong> (SDS), another branch of Swarm Intelligence thought of back in 1989 which focuses on insect like behaviour, in particular how worker find the best location to build a nest.</p><p>We saw that in last weeks blog on <a href="https://medium.com/@iamterryclark/dispersive-flies-optimisation-natural-computing-week-2-52176738da14">DFO</a> that the collective intelligence of a swarm is a powerful and fast way to explore a particular search space. Imagine an ant looking for an ideal nest, bee’s swarming over the most ideal flower bed or even miners looking for gold.</p><p>What would be the best way for them to communicate to the others where these ideal spots are? By telling them of course! Let’s follow an example based on the latter of the above three analogies.</p><ul><li><strong>Random initialise miners on hills</strong></li><li><strong>Evaluate if miner has found gold (is active or not)</strong></li><li><strong>Diffuse information to other miners</strong></li><li><strong>Passive miners select active miners to find out the hill they were on</strong></li><li><strong>If agent is still passive then they will select a new random</strong></li></ul><p>Full C++ OpenFrameworks Implementation can be found on <a href="https://github.com/iamterryclark/ofxSDS">GitHub</a>. However, lets go through the code anyway. SDS find a solution by applying a set of rules to the agents or miners, in this case, within the search space.</p><p>1. Randomly assigning the miners to a spot in the search space.This forms the basis of a lot of swarm intelligence and Genetic algorithm starting points. I allows for any noise in the data to be treated fairly and not disrupt the algorithms process. Ideally, a <strong>uniform random generator </strong>should be used in order to disregard the bias that comes from all computer’s random number generator.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9d9y8di-MCOZo7b3i3TvEg.png" /><figcaption>Initialise miners with random position</figcaption></figure><p>2. Check if there is any gold in that random location and activate (or be happy, that they have found the gold). Those who do not find gold will be unhappy, this process is know as the <strong>“Test Phase”</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/696/1*7N0kDMXTdvoYN4w-IKEX5A.png" /><figcaption>Run “Test Phase” to test if miner found gold</figcaption></figure><p>3. At the end of the day they find themselves in the pub where they share information amongst themselves about their success. The happy miners get on with their business and are content to go back to the same hill the next morning to check for more. The unhappy miners will ask another random miner if they found anything on their hill. This is know as the <strong>“Diffusion Phase” </strong>and is fundamental to all swarm intelligence in how it disseminates information between the whole swarm along with the stochastic approaches that are needed for complex search spaces.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/792/1*KluGy0JxASAur28USkYK-A.png" /><figcaption>Unhappy miners speak to a random miner in the pub</figcaption></figure><p>4. If that random miner is happy that they found gold they will share which hill they were on that morning but not the exact location so that the unhappy miner could then have more chance at finding the gold.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yb6TBJIBXMRcvw5RG5nd5g.png" /><figcaption>Unhappy miner who finds a happy miner will go back to the same hill but different location</figcaption></figure><p>5. If the random miner picked is not happy the current miner will pick an completely random hill and location, checking for gold in that spot.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Vop5z23eeSEJfkGH4t9B0A.png" /><figcaption>if miner doesn’t find happy miner then pick another random hill and location</figcaption></figure><p>6. If the agent was already happy they found gold then go back to the same hill but different location to see if they can find more gold.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yWaBPM4qR6jovG_Gqjq4zw.png" /></figure><h4>Experimentation</h4><p>Here I implemented my own basic version of the program which our lecturer provided in our natural computing module. As you can see here the areas with most “gold” attract the “miners” the most, if the space is full of gold with no gaps they will get stuck there and not leave. For discrete search spaces with multiple areas of interest this may be a problem that this particular implementation could not resolve. However for continuous search space where the ideal areas of interest come in and out of focus this could be useful and I believe SDS would be great in finding this also due to its grid like system which is needed to explore the search space. This make the search space smaller and easier to search.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F3Nq6v1ENlwI%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D3Nq6v1ENlwI&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F3Nq6v1ENlwI%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/c4e2ab37780224afef7247797b87e774/href">https://medium.com/media/c4e2ab37780224afef7247797b87e774/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=560c155aca6b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Search Algorithm Series: DFO]]></title>
            <link>https://medium.com/@iamterryclark/dispersive-flies-optimisation-natural-computing-week-2-52176738da14?source=rss-22b3a2c5decf------2</link>
            <guid isPermaLink="false">https://medium.com/p/52176738da14</guid>
            <category><![CDATA[swarm-intelligence]]></category>
            <category><![CDATA[optimisation]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[search]]></category>
            <dc:creator><![CDATA[Terry Clark]]></dc:creator>
            <pubDate>Thu, 12 Oct 2017 23:20:50 GMT</pubDate>
            <atom:updated>2017-12-18T18:32:09.607Z</atom:updated>
            <content:encoded><![CDATA[<p>This series will focus on the mechanics of Swarm Intelligence (SI) whilst giving some refection to the natural computing course material and showing some experiments I have managed to complete along the way.</p><p>Swarms use it’s collective intelligence to effect the direction of search . This is achieved through passing information between each agent or by following a best in the swarm. Their searching behaviours are modelled on the social behaviours of insects/animals, which lend themselves to being applied to complex problems.</p><p>One of these behaviours are <strong>exploration</strong>,<strong> </strong>which uses stochastic movements around a given search space <em>i.e. video, image or audio file</em>, to find the best result in the whole space, this helps from the swarm falling into local optima, described later in the fitness function section. And <strong>exploitation</strong>, to search a localised area within the full search space, fine tuning the parameters. The aim is to achieve a fine balance of the two as to get the overall best solution in the search space.</p><h3>Dispersive Flies Optimisation (DFO)</h3><h4>Introduction</h4><p>‘Flies’ are randomly scattered across a search space i.e an image or an audio waveform, however could have any number of dimensions (images are 2d and audio is 1d). The flies are dispersed across this space with the aim to find local and global optima from a defined fitness function i.e <strong>“What’s the brightest pixel in this image?”</strong> or <strong>“What’s the loudest point in this waveform?”.</strong></p><h4>What is a fitness function?</h4><p>Fitness functions are mathematical equations for example a <strong>“sphere” </strong>function which is plotting <strong>y=x²</strong> . This sums up n-dimensional positions that the individual fly has and powers the positions by two. We can then take the absolute or square rooted value of that result to give us the fitness of each fly within the given dimension. More functions can be found here <a href="https://www.sfu.ca/~ssurjano/optimization.html">https://www.sfu.ca/~ssurjano/optimization.html</a>. The link shows visualisations of how each function behaves within a 3D coordinate space so it is possible to see how a fly with an XYZ position coordinate could navigate this function.</p><p>The main requirement of a fitness function is determine what type of problem you are trying to solve either minimisation or maximisation. This can be found out via the link above if you are using the test optimisation functions provided there. However, when applied to your own problem I found it best to use a minimisation technique. For examples, taking away a large value from the fitness in order to reach a low number or 0.</p><p>Below I have depicted the process which will be used for each iteration in the search algorithm. I will now try to explain how DFO works by using the example to find the brightest pixel in an image or video.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/486/1*z-lxADT3-yGVqzvPLsEaqg.png" /></figure><p>DFO begins by setting the fitness of all the flies to the difference between the brightest pixel value, which will be 255, by the current pixel value where it is positioned. We then set the fly with the best fitness in the swarm to be the best overall fly.</p><p>We then check all flies in the swarm and use it’s neighbours directly to the left and right it to work out, “who has the best fitness score?”. That fly then becomes the “best neighbour”. Now for the interesting part, this comes from the randomness within the equation. By check a random value against a “disturbance threshold”<strong> </strong>the flies then reposition themselves randomly all over the entire search space. Otherwise they will use the formula below to work out its next position based on the neighbours and moving their position towards the best best fly in the swam.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/818/1*Atpr4XmHaANJACrtmzMJRw.png" /><figcaption>Completed for all flies in the swarm</figcaption></figure><p>We can discover solutions based on my complex data by figuring out our fitness function in order to make the output as close to 0 as possible we do this as this program is this is minimisation problem. Whether it is a maximisation or minimisation problem it is important to understand what the solution could actually look like by using an example image and manually in your head thinking of what you are trying to find out.</p><h4>Experimentation</h4><p>I managed to put my webcam through the search algorithm and as you can see by the video below it is performing extremely well. Because the search space is also quite large there are some bugs where the swarm get attached to the middle of my head and not the bright light behind me.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F26WgxuMsO1Q%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D26WgxuMsO1Q&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F26WgxuMsO1Q%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/7ae763647d1b02a27ad0146b038023f6/href">https://medium.com/media/7ae763647d1b02a27ad0146b038023f6/href</a></iframe><h4>Experimentation 2 — DFO with Motion Tracking (frame differencing)</h4><p>Using a similar process along with motion capture techniques I was able to use a thresholded image with the DFO algorithm to get a better result this will develop into my mini project for the natural course also described in another blog post of mine.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FtIAz69lh5XA%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DtIAz69lh5XA&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FtIAz69lh5XA%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/519f20489b3bef0bc0c72a137b242851/href">https://medium.com/media/519f20489b3bef0bc0c72a137b242851/href</a></iframe><p>I found that the flies still find it difficult to track the white areas perfectly. This would be due to the noise in the background and also that the flies are still searching a very large search space. The thresholded image was also using a gaussian blur to reduce this noise and another way I can think of would be to downsample the image resolution so that the search space was smaller.</p><h4>Natural Camp Questions</h4><p><em>Write a fitness function (the Utils class, a method called “bright”) for finding the brightness part of the an image.</em></p><ul><li>void fitnessFunction(float currentBrightness){<br> return 255-currentBrightness;<br> //This should equal 0 if you have found the brightest spot or 255 if on a dark spot<br>}</li><li>The best neighbour is then picked from this fitness and the one with the best (least) fitness value will be the best neighbour used within the DFO update algorithm</li></ul><p><em>Could you have two optima? If so how would you address the issue?</em></p><ul><li>DFO is only capable in locating one optima at a time as there is only one fitness function in this case which is searching for brightness. If you have a separate swarm tracking the most red, green and blue pixels (3 swarms) this could allow for tracking of multiple optima at once.</li></ul><p><em>Is it possible to trace a moving object? How about tracing gradually fading and emerging objects?</em></p><ul><li>As shown above in my experiments DFO is ok at tracking moving optima, however if there is a lot of noise in the background, a large search space and high disturbance threshold this causes issues for the algorithm as it will track for sometime then decide to track something else instead.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=52176738da14" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[“No Free Lunch” Theorem (NFL)]]></title>
            <link>https://medium.com/@iamterryclark/no-free-lunch-theorem-nfl-10e69f1842f6?source=rss-22b3a2c5decf------2</link>
            <guid isPermaLink="false">https://medium.com/p/10e69f1842f6</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[swarm-intelligence]]></category>
            <dc:creator><![CDATA[Terry Clark]]></dc:creator>
            <pubDate>Fri, 06 Oct 2017 10:35:28 GMT</pubDate>
            <atom:updated>2017-12-18T12:54:45.250Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>A brief look at Machine Learning</strong></h3><p>The popularity of machine learning has been on the increase since the mid 80’s becoming more accessible via the advancements of more frameworks, libraries and programming languages. It is therefore interesting to see the exponential growth of online interest since around 2015 as shown by the graph below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/938/1*N0qSV4SomzckpAHiVT0_1g.png" /><figcaption>Keyword searched on Google.com “Machine Learning”</figcaption></figure><p>To help us understand machine learning in a basic sense the diagram below depicts the flow of information whereby a large dataset/input is required for the algorithm of choice to perform statistical, stochastic and probabilistic methods to extract meaning or future predictions. The data itself is made up of “features” which we can think of as a structure for the algorithm to make sense of. The model or learning algorithm is essentially a “black box” meaning that it is currently impossible or extremely difficult to understand in terms of the inner workings. The training examples are used to test the model and this is a simple set of data. Once the user is satisfied with the output that the algorithm gives it is then better placed to accept the large dataset and give us the “honey from the hive”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/710/1*u6j32-dNG5YB70Zt38NfUw.png" /></figure><h3><strong>The “No Free Lunch Theorem”</strong></h3><p>The “No Free Lunch” (NFL) theorem was introduced to try and better understand the complex nature of the machine learning model, exploring “the connection between effective optimisation algorithms” (Wolpert &amp; Macready, 1996). Put simply, which of these methods are best placed to solve a particular real-world problem. The theorem itself is comprised of two approaches, one which focusses on the performance limits of the algorithm tested over a number of problems / datasets and the other focuses on one data set and a number of algorithms to see which gave the best results.</p><h3>Findings</h3><p>Overall, their findings proved that the initial question posed on the algorithms was inappropriate, this includes datasets collected over a certain timeframe or taken from a snapshot in time. They discovered that “the average performance of any pair of algorithms across all possible problems is exactly identical” (Wolpert &amp; Macready, 1996). Meaning that it’s impossible to choose which algorithm is the best to solve all problems as reality is just not that simple, there are a number of factors which could affect the real world problems trying to be solved and thus it’s a case of trial and error to see which algorithm best fits the data being analysed and the problem you want to solve.</p><h3><strong>Course Reflection</strong></h3><p>Throughout the Natural Computing module I took at Goldsmiths University I found this finding to be true with the problems we were asked to solve. In particular using Genetic Algorithm, described in another blog post of mine. Here the processes were quite flexible in their approach to a problem. I could also see a good way to mix certain processes from one algorithm into another to create hybrid swarm intelligence algorithms which would produce better and faster accuracy in its results.</p><h3>References</h3><p><a href="https://en.wikipedia.org/wiki/No_free_lunch_theorem">https://en.wikipedia.org/wiki/No_free_lunch_theorem</a><br><a href="http://www.no-free-lunch.org/WoMa96a.pdf">http://www.no-free-lunch.org/WoMa96a.pdf</a><br>Wolpert, D. H. &amp; Macready, W. G., 1996. <em>No Free Lunch Theorems for Search, </em>NM: The Santa Fe Institute.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=10e69f1842f6" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>