Siberian Federal University

This solution will be in demand when creating software that controls the operation of devices and systems at nuclear power plants, in the energy sector and in the space industry. The key research findings were published in Lecture Notes in Computer Science.

Multi-version software systems are widely used in those systems where the reliability and uninterrupted operation of the equipment are the fundamental requirements, and the probability of errors should be minimized in the nuclear, energy and space industries.

‘When creating software for complex devices and systems, we must provide many behavioural algorithms in order to protect any device or complex from potential dangerous situations as much as possible. For example, we will have to teach a lunar rover to cope with rocky soil and avoid obstacles in several ways, or an artificial satellite to effectively avoid burning cosmic particles. But in multi-version software, there can be from three to infinite number of versions in each module, and initially, there are several times more of them than we can include in the firmware. If, for example, we put too many algorithms into the lunar rover, even if they are extremely reliable, they will eat up a wild amount of computing power, but we do not want this at all. It is necessary to choose the optimal versions for each module so that the software package as a whole is either super reliable, or the cheapest-possible, or represents something in between with the restrictions given. And ants will help us make this choice!’ said Mikhail Saramud, associate professor of the Department of Informatics, SibFU.

The researcher specified that he had found a new application for the ant colony algorithm, which is well known among IT professionals. The first version of the algorithm was proposed by Marco Dorigo in the early '90s. Ants are known to choose the most passable and short routes from a food source to their anthill. How do tiny and blind insects do this? The point is in the special odorous pheromones that they secrete. Ants recognize a trace pheromone even in a very low concentration and by its smell can determine not only the type of object but also its size and shape. Guided by the pheromone-marked road, the insects easily find food found by neighbours in the anthill and, in turn, update the pheromone footprint. As soon as the food runs out, the fragrant labels, which have not been updated for a long time, are blown off and gradually disappear.

‘Dorigo created a mathematical model of the behaviour of ants looking for optimal paths from a colony to a food source. In the same way, we can impact a graph. A graph is an abstract mathematical object which can be represented as a set of nodes (vertices) connected by edges. If the first node is a conditional “anthill”, then further we will find many transitions to the goal (conditional “food”). Which way to choose? In the case of our study, each node is the composition of a specific module. Suppose there are ten versions for each module. For multi-version software to work, you need to choose at least three from these many versions. It is necessary to look through all possible composition of the versions. Between these compounds, our virtual ant-selector wanders. At the output, it receives the specific composition of the first module, the second, the third, and so on. Plus, the digital agent also determines which transitions between nodes are optimal to achieve the goal. After the work of ants we get a complete picture of the reliability and actual cost of implementing the software system on this equipment. Next comes firmware of the equipment for which the virtual ant colony has chosen the optimal and competently combined composition of the software complex,’ continued Mikhail Saramud.

It is noted that for virtual ants it does not matter at all what the programmed equipment will do in the future — whether to calculate or recognize images. The main thing the agents pay attention to on their way is reliability, resource consumption, cost and probability of successful implementation of algorithms which will be included in the optimal set.

‘In a new article, we separately examined the method of multiple starts. The ant colony algorithm has a significant drawback: if the first ants that we let out go along a non-optimal path but, at the same time, satisfy the given conditions in terms of cost and reliability, then this passage will be considered as adequate, and the following agents will go along the same route. But there is a more optimal way! Why would you go, say, to a store through all the wastelots of the neighbourhood, if you can go directly along the illuminated road? What we offer: there are resources for 500 passes, for example. We launch the first 50 ants, and we send all subsequent ones only along the best path that someone from the first party of “scouts” will find. This is how we optimized the algorithm, making it less random and more suitable for constructing the optimal composition of a multi-version complex,’ summed up Mikhail Saramud.