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.
public class DeepCopy {
public static Object copy(Object a) {
Object obj = null;
try {
ByteArrayOutputStream bos = new ByteArrayOutputStream();
ObjectOutputStream out = new ObjectOutputStream(bos);
out.writeObject(a);
out.flush();
out.close();
ObjectInputStream in = new ObjectInputStream(
new ByteArrayInputStream(bos.toByteArray()));
obj = in.readObject();
}
catch(IOException e) {
e.printStackTrace();
}
catch(ClassNotFoundException e) {
e.printStackTrace();
}
return obj;
}
}
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.
