Scientists have taught digital "ants" to determine the optimal algorithms for software

Scientists have taught digital "ants" to determine the optimal algorithms for software
Scientists have taught digital "ants" to determine the optimal algorithms for software
Anonim

Researchers from SibFU, together with colleagues, proposed to optimize the composition of multiversion software systems using the ant colony algorithm. The development will be in demand when creating software that controls the operation of devices and systems at nuclear power plants, in the energy industry and the space industry.

Image

A group of scientists from the Siberian Federal University and the Siberian State University of Science and Technology named after Academician M.F. Reshetnev proposed to optimize the composition of multiversion software systems using the ant colony algorithm. The main results of the study are published in Lecture Notes in Computer Science.

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

“When creating software (software) for complex devices and systems, we must provide for a variety of behavior algorithms in order to maximally insure a certain device or complex against possible dangerous situations. For example, we will have to "teach" the lunar rover to cope with rocky ground and avoid obstacles in several ways, and an artificial satellite - to effectively avoid burning cosmic particles.

But in multiversion software, there can be from three versions available to infinity in each module - there are initially many times more than we can include in the firmware. If, for example, we put too many algorithms in the lunar rover - even if they are very reliable - they will “eat up” a wild amount of computing power, and we do not need it 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 as cheap as possible, or represents something in between under the given constraints. And the ants will help us make this choice,”said Mikhail Saramud, Associate Professor of the Department of Informatics of the Siberian Federal University.

The researcher clarified that he has found a new application of the Ant Colony Algorithms, which is well known among it specialists. The first version of the ant algorithm was proposed by the scientist Marco Dorigo in the early 1990s. It is known that ants choose the most passable and shortest routes from the food source to the anthill. How do tiny and blind insects do it? The point is in the special odorous pheromones that they release.

Ants recognize a "trace" pheromone even in very low concentration and by its smell can determine not only the type of object, but also its size and shape. Focusing on the pheromone-marked road, insects easily find food found by neighbors in the anthill and, in turn, renew the pheromone trail. As soon as the food runs out, the “fragrant” marks, which have not been renewed for a long time, disappear and gradually disappear.

“Dorigo created a mathematical model for the behavior of ants looking for optimal paths from the colony to the food source. We can act on the graph in the same way.A graph is an abstract mathematical object, it can be represented as a set of nodes (vertices) connected by edges. If the first node is a conditional "anthill", then a lot of transitions to the goal (conditional "food") await us further. Which path to take?

In the case of our study, each node is the composition of a specific module. Let's say there are ten versions for each module. For multi-version software to work, you need to choose at least three versions from this set. It is necessary to enumerate all possible compositions of versions. Our virtual "ant-picker" wanders between these trains.

At the output, he receives a specific composition of the first module, the second, the third, and so on - and the digital agent also determines which transitions between nodes are optimal to achieve the goal. After the "ants" work, we get a complete picture of the reliability and actual cost of implementing the software system on this equipment. Then comes the firmware of the equipment, for which the virtual ant colony has chosen the optimal, competently combined composition of the software package,”the scientist continued.

It is noted that for virtual "ants" it does not matter at all what the programmable equipment will do in the future - to calculate or recognize patterns. The main thing that the “agents” pay attention to when going their way is reliability, resource intensity, cost and the probability of successful implementation of algorithms that will be included in the “optimal set”.

“In the new article, we have separately considered the method of multiple starts. The ant colony algorithm has a significant drawback - if the first "ants" launched by us pass along a non-optimal trajectory, but at the same time satisfy the specified conditions in terms of cost and reliability, then this pass will be counted as adequate - the next agents will follow the same route. But there is a better way.

Why would you go, say, to a store through all the wastelands of the area, if you can walk directly along a lighted road? What we offer: there are resources for 500 passes, for example. We launch the first 50 "ants", and send all subsequent ones only along the best path, which will be found by someone from the first batch of "scouts". This is how we optimized the algorithm, making it less random and more suitable for constructing the optimal composition of a multiversion complex,”the researcher summed up.

Popular by topic