Browse Month

January 2019

Evolving Robots to Cut Stocks: A Coding #10YearChallenge

Ten years ago, I was in high school. I had some experience with coding, mostly through computer science lessons in school; I did Computer Science HL for the IB diploma programme, which had a sizable Java component. As part of the IB programme, students need to write an extended essay, which is basically a research paper.

I worked on Application of Evolutionary Algorithms to Solve the One-Dimensional Cutting Stock Problem. There are two terms to unpack here. First, “evolutionary programming” is a biologically inspired heuristic for solving optimisation problems. The idea is that we first randomly generate a pool solutions that are feasible. We then create ‘related’ solutions by permuting the existing solutions in some way, assess their quality using a function and then replace the old population by selecting randomly from the old and new, with bias towards better solutions. In this way, the theory is that the population of solutions increases in fitness/quality over time.

Second, the “cutting stock problem” is an operations research problem in manufacturing, where raw materials are supplied in finite sizes (e.g. rolls of paper) and one needs to cut them to fixed specifications. The assumption here is that it’s not possible to glue together parts that don’t correspond to any request to fulfill one – any pieces that are too small are lost (this is called ‘trim loss’).

In hindsight this seems decently ambitious for a high-school project. I did well, and got an A (which is the highest grade for these), though I remember how long it took me to write a (in hindsight absolutely terrible) working implementation.

Implementation

The project was implemented in Java, which the IB programme focuses on in its Computer Science course.

Looking back at how my code was structured, it was rather unsurprisingly amateurish and messy. There were just four source files for the entire project, including one 700-liner. That said, there was some semblance of organisation, at least in the sense of abstraction and factoring out logical units into functions. The main loop body of the runOneIteration() method I had was just four statements that ran the major steps of the evolutionary algorithm – clone the current generation, perform mutation, evaluate the new generation’s fitness, select the next generation.

My Java knowledge was poor at the time. Some of this was not knowing about the possibility of using external libraries – I had my own implementation of deep copying objects. Some of this wasn’t even external libraries; I had implementations of median-of-three quicksort and the Fisher-Yates shuffle, which seems unnecessary (these are Collections.sort() and shuffle() respectively).

I seem to have had near zero knowledge of the Collections APIs. I also used a lot of primitives and arrays of primitives, which made things hard to read. This could be argued as having better performance (by avoiding function calls, boxing when performing math and so on), but there wasn’t such a discussion in the paper or comments anywhere, so I’d chalk it up to lack of knowledge.

For an example, we can look at the implementation of a deep-copying routine I wrote back then.

If I was to review this code, there were quite a few things I’d highlight:

  • I’m not sure Java serialization and deserialization is the best way to do this. The general serialize/deserialize approach makes sense, but there are more user-friendly and performant serialization libraries out there. I’d probably use Jackson now.
  • There are no tests! Amazingly I didn’t have any automated tests for my implementation at all. (Contrast with MCMAS, where one of the first things I did when working on that codebase was introducing an automated test framework.)
  • Swallowing exceptions and returning a potentially null object seems like an error-prone pattern. I’d prefer to have clients check for errors by catching (possibly unchecked) exceptions, rather than checking if the reference is null.
  • The ObjectOutputStream can be leaked if writeObject() or flush() throws. We should use something like try with resources (though at the time that didn’t exist – in that case we would put close() in a finally block).
  • The class is a utility class, but it has a public constructor (default in Java). It’s silly, but someone could instantiate instances of this class, which shouldn’t be allowed.
  • Using Object directly for the return type can be troublesome, especially since we know the object that’s being returned has the same type as the input.
  • The reason we have to assign null to obj on line 3 is because it may not be assigned when referenced on line 21. If we wanted to keep this contract (don’t throw, and return null on failures) we can avoid this by returning in.readObject() directly in 13 and null directly in the catch blocks, which is probably more readable.
  • This is not a fair criticism in 2008 (as the feature in question was introduced in Java 7), but nowadays if we want to handle different types of exceptions in the same way we should use the multi-catch syntax to be concise.

Algorithms

The cutting stock problem is difficult (it’s in FNP, and the decision version of “is there a better solution than some number of stocks” is NP-hard), hence heuristic-based algorithms like this seem reasonable. The mutations I used then were swaps, which probably makes sense for this problem as it preserves feasibility (the orders can’t be changed).

The algorithm was probably a bit too greedy in terms of how much it prioritised already-good solutions. I’m not sure if I had heard of the words simulated annealing then, but I interestingly seem to have suggested something like it when discussing possible future work! Those words weren’t mentioned anywhere in the essay and the paragraph in question has no references, so it might well have been a thought from first principles.

The approach of selecting stocks with high wastage to swap pieces from is initially effective in reducing trim loss; yet, this also caused the algorithm to converge at local optima frequently. Conversely, selecting stocks with low wastage to swap pieces from seems to encourage the algorithm to search for the global optimum, though this may require significant amounts of time. A conditional approach, more biased towards swapping stocks with more wastage at the beginning than at the end might prove effective.

Documentation

The obvious difference was that this was written in Word while nowadays I’d almost certainly use Latex for a document like this. Some of the formulas were awkwardly typeset, and rather frustratingly there wasn’t a consistent theme to the diagrams (I see Arial, Calibri, Times New Roman and LM Roman!)

There were some fair points that I made then; for example, the algorithm is flexible with resource constraints, in that terminating at any point will spit out a feasible solution, and much of the gain is obtained early on.

Conclusion

More generally, it’s good to see that things have changed, and that there has been real and significant improvement. I’m often frustrated about my learning and development as an engineer, and in the moment it’s often hard to see any improvement. Yet, viewed over a larger time-scale, across the Imperial degree (shout-out to Software Engineering Design), multiple internships and a battery of research papers and patentable work, things have improved quite a fair bit, which is somewhat gratifying.

Boundary of Lines and Gradients

In The 7 Habits of Highly Effective People, Stephen Covey introduces the notion that things we encounter in life may be classified as irrelevant or relevant to us (whether they are in our circle of concern), and then of the things that are relevant, whether they are things we can influence (hence circle of influence).

This idea is introduced in the context of arguing that highly effective people are proactive. The book claims that there’s a risk that one spends too much time focusing on things within one’s circle of concern, but external to one’s circle of influence. By definition, these can’t be meaningfully changed by one’s actions, so one logically should not focus on these; yet, there is a tendency for one to index too heavily on these, perhaps because they are worrying to look at.

I remember some concern over my work visa application process when I was still studying at Imperial; at the time, the UK Migration Advisory Committee was actively reviewing the Tier 2 scheme with a specific focus on post-study work. Obviously, that was within my circle of concern, but was out of my circle of influence. I was quite concerned about it then, and spent a good amount of time researching how Tier 2 visas looked like and what changes might have occurred.

I also took positive action to hedge these risks (which was within my circle of influence). This included investigating opportunities elsewhere, restricting my internships to places that were willing and able to sponsor Tier 2 visas, and trying to be “so good they can’t ignore you”. Looking back, I think the hedging was valuable; poring over visa rules was less so.

So far, so good. However, there is some difficulty in applying this idea. Two challenges I’ve thought about recently are accurately identifying the boundaries of one’s circle of influence, as well as figuring out when one should exercise one’s ability to influence things in one’s circle of influence.

In terms of identifying boundaries, one may incorrectly identify things as within one’s circle of influence, owing to overconfidence or excessive optimism – a classical example being what other people, especially other people we don’t know choose to do. The inverse would be identifying things as outside from fear; I’ve done this before in terms of some aspects of how I’d been investing my free time (in particular, a commitment to over-studying).

Errors in both directions may also stem from ignorance; for example, one may (correctly) think that the spot GBPUSD exchange rate is mostly not in one’s circle of influence, and then extend that to say that the number of pounds one must pay for a known upcoming dollar expense is out of one’s circle of influence (wrong; forward contracts and other hedging methods exist).

Some authors make further distinction between things one can influence and things one can control, which usually implies personal ability to decide the outcome (for example, one can control one’s own decisions, but can probably only influence another person’s behaviour). I find this a fairly useful distinction to make.

We then move to figuring out if things within our circle of influence are actionable. They can be, but aren’t always. For example, I’ve thought about how to insulate my portfolio from the storms of Brexit and the recent market turbulence. On one hand, my asset allocation is clearly within my circle of influence. I can sell everything and go to cash (or, if one’s worried about the pound, to the US dollar or yen). I’d say it’s even stronger than that – it’s something I can directly control in that I know I am able to execute the relevant transactions if I want to.

Yet, I don’t necessarily know how changes in my asset allocation will affect the returns I will get and the risk I’ll be taking on. I can make some estimates based on past distributions, but those will suppose that at least to some extent past performance is indicative of future returns; there might be ‘black swans’ which can mess with this and by definition are not foreseeable (and thus outside of my circle of influence). In a sense, I know I can change things, but I don’t know as well what impacts my changes will actually have; there is also a cost to implementing changes (both in terms of tax and dealing fees). Making repeated portfolio changes that individually make sense if one thinks one can significantly influence returns or risk could turn out being very costly.

A variant of this is that we may loses sight of actions we should probably take that contribute towards progress on a goal in our circle of concern, even if we (correctly) identify it as mostly outside our circle of influence. This might include the broader state of the economy, environment or public health – it’s probably reasonable to think of these as not things we can directly influence, but that shouldn’t be a reason to ignore them altogether. These behaviours should be accounted for by related things within our circle of influence, possibly at a finer resolution (e.g. “I will continue to work, earn, invest and spend” because I am concerned about my own personal economy and living standards), but they might not necessarily be.

I agree that we should focus our energies on things that we can influence; that said, we need to be careful to identify these correctly (or for things that are large, identify what we can influence), and also to be aware that being able to influence something doesn’t mean we should.