"Dark-Grey-Box Optimization – developing of the new class of highly effective optimizers" – this project by Prof. Michał Przewoźniczek from our Faculty received a grant of over 1 million PLN from the National Science Centre.

Michał Przewoźniczek, Ph.D., university professor works in the Department of Computer Systems and Networks. His research includes Evolutionary Computation (EC), which provides optimization tools in various fields of science and technology. The National Science Centre appreciated our researcher's project titled "Dark-Grey-Box Optimization – developing of the new class of highly effective optimizers", submitted to the competition under the 23rd edition of the Opus program, and awarded PLN 1,362,600 for its implementation.

– Optimization is one of the foundations of our civilization, which we are rarely aware of. It applies to absolutely any area. The scientific goal of the project is to propose new optimizers and operators using the concept of dark-grey-box optimization. Recent research shows that in the field of evolutionary computation, such methods have the potential to provide results of much higher quality than current optimizers – says Prof. Michal Przewoźniczek.

The dark-grey-box methods stem from the so-called Genetic Algorithms (GA), which are a subgroup of evolutionary algorithms. They can be used to solve difficult computational problems that classical algorithms cannot deal with.
 

– Such problems are common and can be found in almost every field of science, technology or other areas around us. There are plenty of examples, such as preparing a production plan in a factory, determining the best route for a courier, designing the shape of an antenna, designing drug ingredients and generating programs to control autonomous robots, as well as designing an appropriate arrangement of rooms, developing an efficient public transport network, or improving the efficiency of natural resources usage in in order to simultaneously improve the quality of life and prevent the devastation of the natural environment – enumerates the scientist.

White-box and black-box

What is a dark-grey-box? First, we need to understand that in order to optimize anything, we need to code the solution. The two main types are: white-box optimization and black-box optimization. White-box methods require a thorough knowledge of the function that is being optimized and of its properties – that is when we can calculate, for example, its derivative. Black-box methods are used when we can evaluate the solution, but we don’t know the exact relationship between the variables of the problem – we don't know how the optimized function behaves because, for example, it is too complicated, or because calculating its derivative is impossible. However, optimization following such methods has significant limitations. About 10 years ago, Darrell Whitley (now one of the leading scientists in the field of evolutionary optimization) proposed a grey-box optimization method. We use it when we know only one thing about the problem, i.e. which variables are dependent on each other and which are not.

– By employing knowledge about the relationships between variables, scientists dealing with grey-box methods have proposed a number of different optimization methods which are much more conscious than in classic black-box optimization – explains Prof. Michal Przewoźniczek. – Grey-box algorithms are general purpose – they can be applied to any problem as long as we know the relationships between the variables. Unfortunately, in the case of many problems we cannot determine which variables are interdependent and which are not – in such cases only black-box algorithms are useful.

Neither white nor black, but… dark grey

Some researchers decided to use various types of statistical analysis to detect relationships between variables, which was a breakthrough in the field of evolutionary computing. However, according to our researcher, these methods also have a significant disadvantage.

– Statistics are not enough to make sure that variables are actually dependent (or not). You can always be wrong. The situation has changed in 2020. That is when, together with Marcin Komarnicki, we proposed the so-called Empirical Linkage Learning (ELL) – says Prof. Przewoźniczek. – ELL allows you to detect dependencies in black-box optimization and additionally ensures that the detected dependencies really exist. Hence, in the case of problems in which we do not know the relationships between the variables (and thus we can’t use the grey-box), these relationships can be detected using ELL. As a result, we can use very effective grey-box techniques in black-box optimization! The colour between grey and black is dark grey – hence the name for this group of methods.

The two papers, which Prof. Michał Przewoźniczek and Marcin Komarnicki published on this topic last year, were very well received (including a nomination for the Best Paper award at the best conference in the field ). The awarded publications are:
•    R. Tinos, M. W. Przewozniczek, D. Whitley, Iterated Local Search with Perturbation based on Variables Interaction for Pseudo-Boolean Optimization, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22), pp. 296–304, ACM, 2022.
•    M. W. Przewozniczek, R. Tinos, B. Frej, M. M. Komarnicki, On turning Black- into Dark Gray-optimization with the Direct Empirical Linkage Discovery and Partition Crossover, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22), pp. 269–277 ACM, 2022.

In the project "Dark-Grey-Box Optimization – developing of the new class of highly effective optimizers", researchers from our Faculty propose a completely new class of evolutionary optimizers referring to the idea of the so-called dark-grey-box. According to the scientists, these methods offer results of much higher quality than optimizers currently considered to be the most effective. Such methods are very promising because they involve a deliberate and conscious effort to understand the nature of the problem. Optimizers based on the concept of black-box or dark-grey-box can be used anywhere, for any optimization problem.