The Device Chronicle interviews Nicolas Alvarez Gil, algorithm engineer at ArcelorMittal R&D on how mathematical algorithms are used to optimise steel production at scale. This interview was kindly arranged by ArcelorMittal R&D Chief Digital Officer Carlos Alba.
Nicolas, as a mathematical algorithm expert, speaks about how bio inspired algorithms are developed and applied practically in the steel production process.
Bio inspired algorithms
Nicolas begins by describing the bio inspired algorithms as algorithms whose structure and behavior are inspired by some phenomena found in nature. Nicolas says “Sometimes, it is surprising to see how intelligent nature can be if you look at natural evolution, animal or plants behaviors – and so the observation and study of nature can motivate the design of optimization algorithms. It is common to see cases where the study in a certain field helps and inspires the research in other non-directly related fields.”
The Genetic Algorithms (GA) and Ant Colony Optimization algorithms (ACO) are two well-known optimization algorithms that can illustrate this. Nicolas says that in an optimization problem, “a user will want to find a solution that maximizes or minimizes certain criteria (e.g. a production schedule that minimizes the production cost, a selection of objects that minimizes the total weight while maximizing the total value.” Nicolas adds that in many real-world optimization problems, due to their size and number of constraints, exact optimization algorithms cannot be used because they require an amount of computation time that may not be operational. Instead approximate algorithms such as the metaheuristics are used. Metaheuristics are optimization algorithms that can provide fairly good solutions in a reduced amount of time. They basically generate solutions and try to improve them iteratively until a certain termination criterion is met such as time, solutions quality, and so on.
How GAs improve the process
Nicolas explains that the Genetic Algorithms (GA) generate solutions and improve them mimicking the process of natural selection. Initially a first population of solutions is generated. Each solution of the optimization problem is seen as an individual. The algorithm consists in evolving the population getting better and better solutions. At each iteration, given a population (parents), another new population (children) is generated by combining characteristics of the parents (crossover or recombination of solutions), trying to improve the solutions. Then the best individuals of both populations (parents and children) are selected, and the process is repeated several times.
In the case of the Ant Colony Optimization algorithms (ACO), solutions are generated constructively by concatenating several decisions. The generation of new solutions is done replicating the way the ants find the shortest path from their nest to the food source: by pheromone deposit/evaporation mechanisms.
Initially, the ants do not know where the food is, so the first ants (explorers) select a random path and, if they find food, they come back to their home depositing pheromone in their selected path. Imagine two ants, A and B. They both go out looking for food, but A arrives at the food source following a shortest path compared with B. Both ants A and B come back to their home depositing pheromones. Pheromone evaporates with time. Hence, when an ant C goes out, it will follow the path of ant A since the pheromone is more intense because ant A arrives earlier, and thus there is less time for the pheromone to evaporate. Since ant C also chose the path of ant A, more pheromones were deposited. Then, as more and more ants choose the path of ant A, the pheromone becomes more and more intense, and finally all ants converge in that path: because it is the shortest one.
In the case of a ACO algorithm, the pheromone evaporation and deposition is replicated to find better solutions over time: the first ants generate initial solutions constructively taking multiple decisions (which job should be sequenced next, which object should I add the next to the bag). Those solutions are evaluated based on the optimization criteria. Then, the decisions taken in the construction of the better solution are enforced with pheromone, and the next ants are going to take those decisions with higher probability in the next generation of solution. The pheromone mechanism is like a learning process, since ants of the last iterations have information about which decision led to good solutions in the past. These are two examples (simplified to facilitated illustration) of how natural phenomena can inspire the behavior of optimization algorithms.
Genesis of the idea to use bio-inspired algorithms
Next, Nicolas addresses where the idea to use these bio-inspired algorithms came from. He says in ArcelorMittal Global R&D they are always looking for new approaches that can provide better solutions to the optimization problems found in the steel industry. He says that when you deal with complex problems such as the ones encountered in ArcelorMittal’s facilities, in most of the cases, it is not feasible to use exact optimization algorithms because they require a high computational time, and usually the solutions should be given in a few minutes, he says.
That is one of the reasons for choosing approximate algorithms such as the metaheuristics. In the past, it was more common to use classical heuristic rules, but sometimes the solution quality was not as good as desired. These heuristics rules evolved to the metaheuristics, which are more intelligent and can “learn” from previously generated solutions. Among the metaheuristics, we found some bio-inspired algorithms such as the GA and the ACO very interesting. These algorithms have been studied in the academic literature for many years already, and we found some of its characteristic very suitable for our problems:
With so-called “Any-time behavior” algorithms, Nicolas says you do not need to wait for the end of a complete execution process to have a solution, you can get a solution at any time. Many of these are population-based, and this means that the algorithm generates multiple solutions instead of just one. This is good for optimization problems where there are different confronted criteria to be optimized, and they provide a set of solutions from which you (or the final user) can choose the one that fits better each situation/scenario.
Some of them, such the ACO, are constructive metaheuristics. We found it very useful for generating solutions in highly constrained problems, where some constraints depend on the previous part of the sequence. They provide a framework where you can choose between exploration (find different solutions to the ones already obtained) and exploitation (look for similar solutions, near to the better ones) which is very convenient.
Normally the bio-inspired algorithms and the metaheuristic in general are a framework for the optimization process and they are very flexible to be adapted or combined with other strategies. These algorithms, widely studied in the literature, seemed to be promising for our problems for that reason, so we decided to adapt them for our real-world problems, and it was a success.
Applied in steel production
Nicolas described how these algorithms have been applied to the steel production process to create an optimal production schedule. This is the main challenge. Usually these algorithms have to be adapted and fine-tuned for each problem, and they also have to be combined with a mathematical model of the production constraints and cost functions. Addressing an industrial optimization problem involves managing a high number of constraints, different objectives to be optimized simultaneously, and the size of the problems is high. Some years ago, when the ACO was applied for the first time for the scheduling of one of our finishing lines, we collaborated with the inventors of the algorithm to find the best way to do it. Nowadays this collaboration with the Universite Libre de Bruxelles (ULB) is still on-going, organizing together a yearly workshop named “Industrial Applications of Metaheuristics” in The Genetic and Evolutionary Computation Conference to extend the research on how to best apply evolutionary algorithms to industrial problems
As an illustration, Nicolas uses the case of the scheduling of the finishing line to demonstrate how to apply these algorithms to find an optimal schedule. The problem consists in sequencing a set of coils (final format of the flat steel products), to find an ordering of the coils that reduces the production costs (less second quality material, better transitions, etc.). Producing two coils together has a cost associated that depends on the properties of the two coils.
Initially, each ant constructs one solution adding coils to the sequence one-by-one until all the coils have been chosen. For the generation of this initial population, each ant decides which coil to add next considering just the cost of the transitions (higher cost, lower probability of adding it), since there has not been any pheromone deposition yet. After each iteration, the solutions are evaluated according to the cost functions. Then, for each transition coil-to-coil, an amount of pheromone proportional to the fitness of the solutions that used that transitions is deposited. If a transition appears in the best solutions, it will have more pheromone.
For the next iteration, when an ant has to decide which coil to add to the sequence, it will take into account both the cost of the transition and the current amount of pheromone of that transition (the more pheromone, the more chances to choose that transition). Additionally, the pheromone slowly evaporated with the iterations, allowing the algorithm to explore other solutions.
Execution of these algorithms
Nicolas concludes by describing at a high level, the underlying Cloud and AI architecture that enables the execution and applications of these algorithms? He says the design and implementation of the optimization algorithm is the main challenge in the projects, but that his team needs to provide a complete solution able to get the information from the steel production plant system. This is MES, Level III that has the information about the orderbook, the required parameters, the situation of the facility and so on. Then, once the algorithm is executed, the optimized results are sent back to Level III. Nicolas says “This communication is always different because each plant has different legacy systems and the way to communicate the solution to the production crew is also different. In any case, we provide our client with a complete ad-hoc solution (GUI + model + algorithm) able to transmit the required information for each particular project. Additionally, we also design the user interface to be user-friendly, intuitive to use and to help the final user as much as possible. In some of our solutions the optimization is the main functionality but additional functionalities such as customized plots of inputs/outputs, assisted order selection tools (graphs analysis, outliers analysis and so on) are also offered, manual modifications/selection of the solutions and so on.
We wish Nicolas and his colleagues in ArcelorMittal R&D well as they continue on their journey optimising their production processes.
References:
HOLLAND, J. H. 1975. Adaptation in natural and artificial systems. The University of Michigan Press, Ann Harbor, MI.
REEVES, C. R. AND ROWE, J. E. 2002. Genetic Algorithms: Principles and Perspectives. A Guide to GA Theory. Kluwer Academic Publishers, Boston (USA).
DORIGO, M. AND STÜTZLE , T. 2002. The ant colony optimization metaheuristic: Algorithms, applications and advances. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds. International Series in Operations Research & Management Science, vol. 57. Kluwer Academic Publishers, Norwell, MA, 251–285.
BLUM, C. AND ROLI, R. 2003. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys, Vol. 35, No. 3, pp. 268–308.