The knapsack problem deals with a set of items we want to put in a bag, each with associated weights and values. Crucially, the bag has a weight capacity that the selected items can’t exceed. The solution therefore is the subset of items that can fit in the bag with the optimum ‘profit’. A few variations of the problem exist (and even more approaches to solving them) but this post is about applying the genetic algorithm metaheuristic to 0-1 knapsack:…
To get started with the project I first confirmed the Arduino could reliably control the LEDs. I’d successfully powered the LEDs before, but only with another controller and it looked broken because the LEDs had so many glitches. So I soldered all my RGB LEDs into one strip and uploaded a simple FastLED demo onto the Arduino:
First time powering the strip - careful with the order (LEDs before Arduino) to avoid damaging the Arduino…
Week Five: “Choosing a supervised learning algorithm” decision tree (forum link) Arduino circuit photo and code (below) Paper questionnaire (handed in) Reflection: I found making a decision tree of common supervised machine learning algorithms not entirely straight-forward. The no free lunch theorem (Wikipedia link) states that algorithms can never be optimal for all problems. And the number of exceptions in the decision tree I made point to the same conclusion.…
The video below demonstrates my media processing project which uses networked cameras and different layers of analysis and feedback to gradually distort webcam streams. It was inspired by artist Quayola’s ‘paintings’ (link here).
In the software is a ‘view’ C++ class that updates images to 1) detect the closest visual keypoint to the cursor and 2) compute motion using optical flow. That data is then passed to GLSL graphics card shaders together with the livestream and two more parameters; ‘glitch’ and ‘expression,’ normalised from 0 to 1.…
The first problem I wanted to focus on in my nature-inspired metaheuristics project was circle packing in a circle, which aims to fit N unit circles within a larger circle as tightly as possible. It seems that just 25 cases for N have solutions known that don’t leave any circles loose (moveable without overlap). From what I found N = 91 is the largest. [?]
Above: Set of optimal circle packings with loose circles coloured pink (source)…
I plan to design and build a digital light for living spaces. The object’s exterior casing will feature addressable LEDs that effectively form a low-resolution screen, able to stimulate human observers with changing patterns. Responsivity, enabled by connecting an input to the system, will provide functionality too; it could sit on a bedside table as an alarm clock which illuminates in an increasingly annoying way until you wave your hand over a sensor to turn it off.…
The Travelling Salesman Problem (TSP) is an optimisation problem in algorithmic research based on a simple scenario:
A salesman must travel between N cities Cities are linked to other cities with a cost (e.g. journey distance or duration) The salesman does not care about order, just that they visit all cities To solve TSP, our aim is to search for the lowest cost path connecting every node (city) in the graph (map).…
Week Four: Q&A question on learn.gold (forum link) Online quiz on learn.gold Wekinator Assignment 4 on learn.gold (and here) Reflection: An interesting question asks what classes k-nearest neighbors algorithm as ‘machine learning’. It can be argued that it is so simple in comparison to neural networks and other machine learning algorithms that it just doesn’t fit. There is no training involved which is another way it stands out compared to most other solutions.…
Week Two: Online quiz on learn.gold Wekinator Assignment 2 group work on learn.gold openFrameworks app that responds to Wekinator classifier on learn.gold Code for the app demonstrated below: link Reflection: The third task this week; to create a piece of code that responds to a classifier, was surprising in several ways. With it being an early experiment, I made a simple program to demonstrate classification: clicking the mouse sends two features (current X and Y position within the 2-dimensional input space) to Wekinator.…