By Kumar Ramakrishnan, Altis Consulting NZ
Ever wondered how to use discovery-based decision-making methods derived from real-world phenomena to drive artificial intelligence? Artificial intelligence, or AI for short, is a set of instructions implemented in a computational algorithm that enables computer aided decision-making tools to mirror human behaviour responses to action. It does this by collecting and analysing data from external or internal sources and predicts an outcome based on the optimal decision objective. The term ‘artificial intelligence’ was first used in 1956. In the 1960s, scientists were teaching computers how to mimic, or copy, human decision-making.
In this blog, I will review one of the most popular evolutionary based algorithms to solve real-world decision-making problems in layout/space optimisation. Evolutionary algorithms are forms of unsupervised Deep Learning that rely on fitness functions. Deep Learning is a type of Machine Learning that is inspired from biological networks and unsupervised when the input data is not labelled, classified, or categorised, therefore the outputs are unpredictable.
The layout optimisation involves packing smaller rectangle items into larger fixed size rectangular bins with the objective to minimise the number of bins utilised. There are many applications of bin packing, e.g., crepe-rubber cutting, shelving, container loading, wood, steel industry, newspaper columns, etc. Figure 1.0 shows a graphical representation of packing 13 smaller rectangles into identical larger bins of width 100 and height 100. The initial solution is derived by a placement heuristic that applies a score to pre-sort, rotate and determine the best bin and position in the bin to pack the 13 smaller rectangles. The pre-sorted order of the 13 rectangles, {(95,47), (98,44), (88,40), (71,49), (80,41), (66,42), (90,29), (87,29), (76,29), (83,19), (97,16), (75,15), (26,25)}, (width, height in brackets). This seeding step is required to initiate the evolutionary algorithm.
To evaluate if the algorithm found the best optimal decision, a theoretical lower bound is calculated, a simple lower bound is the sum of the total area of the small rectangles divided by the bin area, in the scenario above the theoretical lower bound is four bins. The initial seeding solution used five bins.
This input is then fed into the Genetic Algorithm (GA). In a nutshell GA is an evolutionary based algorithm. GA principles are derived from natural occurrences based on species evolution in each population which are influenced by several factors like hereditary, environmental pressure, food, etc. Members of the population are replaced by fittest surviving individual and as a result the domination of fitter individual in the population increases. The basic framework of a GA algorithm consists of 7 steps, which are, 1) initialisation, 2) evaluation, 3) selection, 4) crossover, 5) mutation, 6) recombination and 7) termination. In the initialisation phase, initial population containing P numbers of pre-sorted rectangles are randomly generated. This is followed by the evaluation phase where for each member of the current population, its fitness is evaluated. Next, comes the selection phase whereby a mating pool is created by selecting two random solutions from the current population and the fitter parent is chosen based on its stronger fitness measure. Consequently, a crossover operator is utilised to form pairs of elements from the mating pool and perform crossover on each pair to create offspring. In the mutation operations, a mutation strategy is implemented to mutate the elements of the strings obtained from crossover with a given probability and re-generate new solutions. Subsequently the recombination procedure replaces the parent with the offspring if the new solution is better than the parent and returns either the offspring or the parent back to the population pool for re-selection, thus forming a new generation of offspring obtained from crossover and mutation. Finally, a termination criterion ends the search based on a pre-defined stopping condition, e.g., number of iterations, time lapsed, etc.
The following example will be helpful to describe the crossover process (step 4); assuming parent 1 is the chosen fitter parent, rectangles packed in the following order; 1, 3, 9, 5, 2, 6, 4, 7, 8, 10, 11, 12, 13 and for parent 2; 8, 7, 6, 5, 10, 4, 3, 2, 1, 9, 11, 12, 13. The order crossover method starts by slicing the parents at two points, beginning and end of their packing order, for example, a) total number of rectangles divide by 2, 13/2 ~ 7 and b) total number of rectangles divide by 5, 10/5 ~ 3. Hence the sliced partial sequence is as following, parent 1; 1, 3, 9, 5, 2, 6, 4 | 7, 8, 10 | 11, 12, 13 and parent 2; 8, 7, 6, 5, 10, 4 | 3, 2, 1, 9 | 11, 12, 13. The new permutation is formed in the following way; by combining the third and first slices of the fitter parent in the order they appear to form the partial new parent; 11, 12, 13, 1, 3, 9, 5, 2, 6, 4 and to complete the new parent, the other parent’s second, third and first slices are used in the order they appear, skipping values already in the new partial parent, new parent’s rectangle complete packing order; 11, 12, 13, 1, 3, 9, 5, 2, 6, 4, 10, 8, 7. Hence in this way the new packing solutions for further evaluation in the GA are created. The fitness function is total area utilisation over the number of bins, excluding the bin with the highest utilisation. Figure 2.0 is the best solution from GA algorithm that meets the optimal decision objective, 4 bins.
Now imagine the same scenario is given to a human packer where they are provided the 13 items to pack and were told to pack them into exactly 4 bins, how would they approach the problem? As we know humans have sensors that detect different types of information, spatial awareness, complex cognitive skills and will follow the best practice rule to pack these items into the 4 bins, we can relate to this when packing our suitcases for travel. AI on the other hand will have to rely on IoT devices to first digitise the input data, in this case the shapes and sizes of the rectangles and bins, feed that into Genetic Algorithm to produce the best packing solution which can then be packed by the human packer or automated machine. I hope this blog has inspired you to learn more about Deep Learning algorithms and how it can be used to automate unsupervised complex decision-making problems.
If you want to find out more about this topic or enquire about our other services, please don’t hesitate to connect with us.
